xudong963 opened a new pull request, #23741: URL: https://github.com/apache/datafusion/pull/23741
## Which issue does this PR close? None. This draft PR was requested without a tracking issue. ## Rationale for this change Joins with two inequality predicates, such as interval-overlap joins, currently cannot use the single-predicate Piecewise Merge Join path and may fall back to a nested-loop evaluation. IEJoin evaluates this pattern with two sorted orders, an inverse permutation, and a bitmap, avoiding materializing the candidate cross product. The implementation is experimental and disabled by default. ## What changes are included in this PR? - Add `IEJoinExec` for Inner joins with exactly two `<`, `<=`, `>`, or `>=` predicates. - Support optional equality keys by co-partitioning the inputs and rechecking complete equality keys after hash grouping. - Preserve additional join predicates as residual filters and exclude volatile expressions from IEJoin driver selection. - Implement bounded-batch output streaming, hierarchical sparse bitmap scans, memory-pool accounting, and controlled resource-exhaustion errors. - Add planner selection behind `datafusion.optimizer.enable_ie_join`, which defaults to `false`. - Add differential, null/NaN/signed-zero, forced-hash-collision, multi-word bitmap, cross-batch cursor, memory-limit, SQLLogicTest, planner integration, and dictionary-buffer reservation coverage. - Add an IEJoin benchmark and document the new configuration option. The initial scope is Inner joins only. Outer, semi, and anti joins and spilling are not included. ## Are these changes tested? Yes. The following checks pass on the current `main` base: - `cargo fmt --all -- --check` - `CARGO_INCREMENTAL=0 CARGO_PROFILE_DEV_DEBUG=0 cargo clippy -j 1 --all-targets --all-features -- -D warnings` - `./ci/scripts/doc_prettier_check.sh --write --allow-dirty` - Feature-enabled `datafusion-physical-plan` IEJoin unit tests: 10 passed, including all 16 operator pairs, both null-equality modes, forced hash collisions, a 5,000-row bitmap group, and cross-batch cursor retention. - `physical_planner::tests::ie_join_plans_and_executes_keyed_interval_overlap` - `datafusion/sqllogictest/test_files/ie_join.slt` The extended workspace test command was also attempted locally. Compilation reached final test-binary linking, but the shared development disk ran out of space (`errno=28`) before the suite could execute; no test failure or compiler diagnostic was reported. Draft CI can run the complete suite. ## Are there any user-facing changes? Yes. This adds the experimental `datafusion.optimizer.enable_ie_join` configuration option, disabled by default, and exports `IEJoinExec` and `IEJoinCondition` from `datafusion-physical-plan`. The configuration documentation is updated. There are no breaking changes. -- 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]
