SubhamSinghal opened a new pull request, #25467: URL: https://github.com/apache/datafusion/pull/25467
## Which issue does this PR close? Part of #17427. ## Rationale for this change `PiecewiseMergeJoinExec` supported every Semi/Anti existence join but rejected `LeftMark`/`RightMark`, falling back to `NestedLoopJoinExec`. Mark joins answer the same per-row existence question Semi/Anti already answer -- they just keep every row instead of filtering by it, attaching the answer as a boolean `mark` column. No algorithmic reason forces a single range predicate onto the slower path for these. ## What changes are included in this PR? - `LeftMark` served by `ExistencePWMJStream` (`existence_join.rs`): same watermark as `LeftSemi`/`LeftAnti`, but the final pass emits every buffered row with a `mark` column built from it instead of slicing. - `RightMark` served by `RightExistencePWMJStream` (`right_existence_join.rs`): buffered-extreme comparison factored into a shared `matched_mask`; `RightMark` keeps every streamed row and appends the comparison as `mark`, folding NULL to `false` (mark is documented to never be NULL). - `PiecewiseMergeJoinExec::try_new` and the physical planner no longer reject/exclude Mark joins from the PWMJ path. - `RightMark`'s `maintains_input_order` corrected: appending a column doesn't reorder rows, so it now matches `RightSemi`/`RightAnti` instead of a placeholder `false`. - Documented (in `try_new`) and pinned (SLT) an invariant: null-aware `LeftMark` (scalar `NOT IN`) can never reach PWMJ, since it always requires a non-empty equi-join `on`, while PWMJ only activates when `on` is empty. `PiecewiseMergeJoinExec` has no `null_aware` field and always builds a non-nullable `mark`, so this must hold. | | PWMJ | NestedLoopJoin | speedup | |---|---|---|---| | LeftMark, all_match | 246 µs | 77.7 ms | ~316× | | LeftMark, no_match | 224 µs | 78.6 ms | ~350× | | LeftMark, half_match | 245 µs | 78.6 ms | ~320× | | RightMark, all_match | 20.5 µs | 78.8 ms | ~3845× | | RightMark, no_match | 20.4 µs | 78.9 ms | ~3866× | | RightMark, half_match | 20.5 µs | 78.6 ms | ~3834× | ## What is the testing strategy for this PR? - Unit tests (`existence_join.rs`, `right_existence_join.rs`): `join_left_mark`, `join_right_mark`, all-NULL-buffered-side cases for both, `RightMark` NaN/-0.0 handling, a `RightMark` NULL-streamed-key case against a non-null buffered extreme, and a `RightMark` coalescer order-preservation case. - `pwmj.slt`: `LeftMark` has no SQL syntax of its own, so it's reached via `EXISTS` inside a disjunction (`x > 100 OR EXISTS (...)`), with `EXPLAIN` pinning `PiecewiseMergeJoin: join_type=LeftMark`. Covers real NULL buffered keys and List/LargeList/FixedSizeList/Dictionary keys. Also pins that a size-skewed range mark join never gets swapped to `RightMark` (PWMJ's `swap_inputs` is unimplemented) and that the null-aware `NOT IN` invariant above holds, plan and result both. - `RightMark` has no SQL path today (no optimizer rule constructs it), so it's covered only by unit tests and the fuzz test below. - `fuzz_pwmj_matches_nested_loop` (`join_fuzz.rs`, `extended_tests`): both Mark types added to the differential fuzz matrix against a `NestedLoopJoinExec` oracle, compared as `(id, mark)` pairs across randomized `i32`/`f64` inputs, operators, partition counts, and NULL/duplicate keys. - Proto roundtrip tests updated: the wire-rejection test no longer expects Mark types to fail (no wire format change was needed -- the shared `JoinType` enum already covered them), and a new test executes both the original and roundtripped plan and compares output row-for-row, including `mark`. - `cargo fmt`, `cargo clippy`, and `cargo doc` all pass clean on the touched crates. ## Are there any user-facing changes? Yes: queries that decorrelate to a `LeftMark`/`RightMark` join with a single range predicate (no equi-join key) and no other filter now use `PiecewiseMergeJoinExec` instead of `NestedLoopJoinExec` -- a plan-shape and performance change, not a semantic one. No public API 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]
