xudong963 commented on issue #24157:
URL: https://github.com/apache/datafusion/issues/24157#issuecomment-5213230805
## Proposed stacked PR plan
Dependency order:
```text
main
└─ PR 1: planner refactor
└─ PR 2: unkeyed IEJoinExec
└─ PR 3: equality keys and residual filters
└─ PR 4: planner and configuration integration
└─ PR 5: benchmarks
```
### PR 1 — `refactor(core): extract range-join planning helpers`
A behavior-preserving planner refactor:
- Extract construction of a physical `JoinFilter` from a logical join
expression.
- Extract cross-input expression classification and inequality
normalization, including operand swapping.
- Reuse the helpers in the existing Piecewise Merge Join planning path.
- Add focused tests showing that existing PWMJ and fallback plans do not
change.
- Do not add IEJoin symbols, configuration, or behavior.
This removes unrelated refactoring from the eventual IEJoin planner diff.
### PR 2 — `feat(physical-plan): add unkeyed IEJoinExec`
Introduce the smallest complete and directly usable execution operator:
- Add `IEJoinCondition` and `IEJoinExec`.
- Support bounded inner joins with exactly two range conditions and no
equality keys.
- Implement input materialization, memory reservation, the two sorted
orders, inverse permutation, sparse bitmap scan, bounded output batches, and
bounded work per stream poll.
- Reject unsupported operators, volatile conditions, type mismatches, and
unbounded inputs with clear errors.
- Export the operator for programmatic construction, but do not select it
from the SQL planner.
- Cover all operator pairs, strict/non-strict boundaries, NULL, NaN, signed
zero, empty inputs, bitmap word boundaries, cross-batch cursor continuation,
memory limits, and dictionary-buffer accounting.
The algorithm, stream, and execution-plan adapter should stay together in
this PR because none is independently useful or testable as production
functionality.
### PR 3 — `feat(physical-plan): support keyed and residual IEJoin
predicates`
Extend the physical operator without changing planner behavior:
- Add optional equality keys and co-partitioned input requirements.
- Group rows by equality-key hash and recheck complete keys before output.
- Support `NullEquality`.
- Support an additional residual `JoinFilter`.
- Forward the `force_hash_collisions` feature needed for collision testing.
- Add keyed differential, multiple-key, residual-filter, null-equality, and
forced-hash-collision tests.
The public construction API should remain compatible between PR 2 and PR 3,
either through an options/builder shape established in PR 2 or by retaining the
unkeyed constructor as a convenience API.
### PR 4 — `feat(core): plan IEJoin for two range predicates`
Add the user-facing opt-in:
- Select IEJoin only for eligible inner, non-null-aware joins with at least
two non-volatile cross-input range predicates.
- Use two normalized predicates as IEJoin drivers and preserve every other
conjunct as a residual filter.
- Support both keyed and unkeyed planning.
- Add `datafusion.optimizer.enable_ie_join`, defaulting to `false`.
- Update generated configuration documentation and information-schema
expectations.
- Add physical-planner unit tests and SQLLogicTests for keyed, unkeyed,
reversed-expression, residual-filter, disabled-option, and fallback cases.
- Keep the configuration/API-change labeling and release-note impact
isolated to this PR.
### PR 5 — `bench(physical-plan): add IEJoin benchmarks`
Add performance evidence without production-code changes:
- Compare unkeyed IEJoin with `NestedLoopJoinExec`.
- Compare keyed IEJoin with `HashJoinExec` plus residual filtering.
- Include input construction, materialization, sorting, and complete output
collection.
- Validate result cardinality before measuring.
- Document the benchmark command and representative results in the PR
description.
Each PR should compile and pass its focused tests independently. Formatting
and clippy run on every layer; the full workspace test suite and documentation
formatting checks run on the top of the stack.
#23741 can remain a Draft umbrella while the stack is prepared. Its
description should link these PRs and show their dependency/merge order; review
should happen on the individual layers rather than on the cumulative Draft diff.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
