Support IEJoin for inner joins with two range predicates
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Is your feature request related to a problem or challenge?
Interval-overlap joins and similar workloads commonly contain two cross-input inequality predicates, for example:
```sql
left.start_at <= right.end_at
AND right.start_at <= left.end_at
```
DataFusion can currently exploit a single range predicate with `PiecewiseMergeJoinExec`. With two range predicates, an unkeyed join may use `NestedLoopJoinExec`, while a join with equality keys may use `HashJoinExec` and evaluate both inequalities as residual filters. These plans can examine or materialize a large candidate set even when the final result is small.
This is a concrete implementation follow-up to the broader range-join performance issue #8393.
### Describe the solution you'd like
Add an experimental `IEJoinExec` physical operator for bounded inner joins driven by exactly two cross-input `<`, `<=`, `>`, or `>=` predicates.
The initial implementation should:
- Support unkeyed joins and optional equality keys.
- Normalize range predicates to left-input expression, operator, and right-input expression.
- Use two sorted orders, an inverse permutation, and a sparse bitmap to enumerate matches.
- Recheck complete equality keys after hash grouping so hash collisions cannot affect correctness.
- Preserve any additional join predicates as residual filters.
- Exclude volatile expressions from IEJoin driver selection.
- Emit bounded output batches, bound work performed by each stream poll, account for memory-pool usage, and return controlled resource-exhaustion errors.
- Be selected by the physical planner only when an experimental configuration option is enabled; the option should default to `false`.
The initial scope excludes outer, semi, anti, and null-aware joins, as well as spilling.
### Describe alternatives you've considered
- Continue using `NestedLoopJoinExec` for unkeyed joins. This is general but may evaluate a quadratic candidate space.
- Use `HashJoinExec` for equality keys and apply inequalities as residual filters. This helps keyed workloads but can still produce a large candidate set within each key.
- Extend `PiecewiseMergeJoinExec`. It is designed around a single range predicate and does not use both inequalities to prune candidates.
- Wait for a more general range-join framework. IEJoin is a focused first step for the common two-inequality pattern and can remain opt-in while its scope evolves.
### Additional context
Draft implementation and initial benchmark results are available in #23741.
The implementation spans the physical operator, keyed and residual-filter support, planner integration, configuration and documentation, end-to-end tests, and benchmarks. To keep each change independently reviewable, it will be delivered as a stack of smaller PRs; the proposed stack is documented in a follow-up comment.
Contributor guide
Research direction
Start by reading the draft implementation and benchmark results in issue #23741, then review the proposed stack in the follow-up comment. The work spans the physical operator, planner integration, configuration and documentation, end-to-end tests, and benchmarks. Done means an opt-in IEJoin supports the stated bounded inner-join scope while preserving residual predicates and resource controls.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- backend, databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100