SubhamSinghal opened a new pull request, #23870:
URL: https://github.com/apache/datafusion/pull/23870
## Which issue does this close?
Part of #17427 (Make `PiecewiseMergeJoin` work in DataFusion). Adds
`LeftSemi` / `LeftAnti` support, one of the epic's checklist items. Supersedes
the stale #18392, taking the alternative approach that @2010YOUY01 suggested
there (reuse the classic join path for generality) rather than a dedicated
existence stream.
## Rationale for this change
An inequality-correlated `EXISTS` / `NOT EXISTS` (e.g. `WHERE EXISTS (SELECT
1 FROM r WHERE l.x < r.y)`) has no equi-key, so it decorrelates to a `LeftSemi`
/ `LeftAnti` join with a single range predicate. Today `PiecewiseMergeJoinExec`
rejects existence joins (`not_impl_err!`) and these queries fall back to
`NestedLoopJoinExec`, which is O(n*m).
Microbenchmark (20K × 20K rows, single inequality,
`enable_piecewise_merge_join`
on vs off), added in this PR as `piecewise_merge_join_semi_anti`:
| Case | PWMJ | NestedLoopJoin | Speedup |
|------------------------------|----------|----------------|---------|
| LeftSemi, high selectivity | ~0.50 ms | ~75 ms | ~150× |
| LeftAnti, high selectivity | ~0.44 ms | ~75 ms | ~170× |
| LeftSemi, low selectivity | ~0.48 ms | ~76 ms | ~158× |
| LeftAnti, low selectivity | ~0.48 ms | ~75 ms | ~155× |
## What changes are included in this PR?
**Existence joins (`LeftSemi` / `LeftAnti`) for `PiecewiseMergeJoin`:**
- Route `LeftSemi` / `LeftAnti` with a single range predicate to
`PiecewiseMergeJoinExec` in the physical planner (still gated behind
`enable_piecewise_merge_join`, default `false`).
- Reuse the classic scan: on the first match, mark the matching
buffered-row suffix in the visited bitmap and emit from it in the final pass
(`LeftSemi` = marked rows, `LeftAnti` = unmarked; NULL join keys are never
marked, so they are correctly excluded from Semi and included in Anti). Only
left-side columns are produced.
- `RightSemi` / `RightAnti` / `Mark` remain unsupported (they require
swapping the inputs); they are still rejected in `try_new` and excluded in the
planner. Left as a follow-up.
- Two small optimizations so existence marking stays O(buffered), not
O(n*m): stop scanning a batch after the first match (the marked suffix is
maximal), and a cross-batch low-water mark so later batches only mark
not-yet-marked rows.
- Updated the operator docstring to describe the implemented classic-reuse
path and keep the min/max fast-path as a documented follow-up.
## Are these changes tested?
Yes.
- 33 unit tests in `classic_join.rs` covering `LeftSemi` / `LeftAnti`
across `<`, `<=`, `>`, `>=`; NULL join keys; all-null streamed side; empty
inputs; `Date32` keys; multi-batch and multi-partition streamed inputs; and the
low-water-mark skip branch.
- End-to-end SLT coverage in `pwmj.slt` for `EXISTS` / `NOT EXISTS`
(including NULLs) with `EXPLAIN` assertions confirming the plan uses
`PiecewiseMergeJoin`.
- The multi-partition test also guards the final-pass counter fix.
## Are there any user-facing changes?
No behaviour change by default: `enable_piecewise_merge_join` remains
`false`. When enabled, single-range-predicate `LeftSemi` / `LeftAnti` joins are
planned as `PiecewiseMergeJoin` instead of `NestedLoopJoin`. No 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]
