You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "SubhamSinghal (via GitHub)" <gi...@apache.org> on 2026/07/24 16:23:06 UTC
[PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on PR #23870:
URL: https://github.com/apache/datafusion/pull/23870#issuecomment-5268242319
Thanks @SubhamSinghal I'll check it today
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23870:
URL: https://github.com/apache/datafusion/pull/23870#issuecomment-5214582231
> Sorry for tagging you everywhere
No worries. I'm happy to help. Should we split the benchmark in a new pr so we can assess easily?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #23870:
URL: https://github.com/apache/datafusion/pull/23870#issuecomment-5072291128
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/23870?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `87.37024%` with `73 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 80.72%. Comparing base ([`592eeab`](https://app.codecov.io/gh/apache/datafusion/commit/592eeab9cca76fc84fc12a4c03e46967eaa895e2?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`5ec1790`](https://app.codecov.io/gh/apache/datafusion/commit/5ec1790897998f9ef1b21dd710f685dfd93fe771?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 2 commits behind head on main.
| [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/23870?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [...lan/src/joins/piecewise\_merge\_join/classic\_join.rs](https://app.codecov.io/gh/apache/datafusion/pull/23870?src=pr&el=tree&filepath=datafusion%2Fphysical-plan%2Fsrc%2Fjoins%2Fpiecewise_merge_join%2Fclassic_join.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1wbGFuL3NyYy9qb2lucy9waWVjZXdpc2VfbWVyZ2Vfam9pbi9jbGFzc2ljX2pvaW4ucnM=) | 87.45% | [8 Missing and 63 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/23870?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...ysical-plan/src/joins/piecewise\_merge\_join/exec.rs](https://app.codecov.io/gh/apache/datafusion/pull/23870?src=pr&el=tree&filepath=datafusion%2Fphysical-plan%2Fsrc%2Fjoins%2Fpiecewise_merge_join%2Fexec.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1wbGFuL3NyYy9qb2lucy9waWVjZXdpc2VfbWVyZ2Vfam9pbi9leGVjLnJz) | 71.42% | [2 Missing :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/23870?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #23870 +/- ##
========================================
Coverage 80.71% 80.72%
========================================
Files 1090 1090
Lines 370339 370906 +567
Branches 370339 370906 +567
========================================
+ Hits 298925 299411 +486
- Misses 53605 53607 +2
- Partials 17809 17888 +79
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/23870?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #23870:
URL: https://github.com/apache/datafusion/pull/23870#issuecomment-5144369279
@adriangb @comphead Can you please review this PR?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #23870:
URL: https://github.com/apache/datafusion/pull/23870#issuecomment-5214483602
@kumarUjjawal Can you review this PR? Sorry for tagging you everywhere
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #23870:
URL: https://github.com/apache/datafusion/pull/23870#issuecomment-5241780002
Thanks @2010YOUY01 @viirya @kumarUjjawal for review. I have refactored code and split existence join in separate stream. This also enabled few more optimisations. PTAL.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on PR #23870:
URL: https://github.com/apache/datafusion/pull/23870#issuecomment-5148372550
Oh nice! @coderfender FYI
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb merged PR #23870:
URL: https://github.com/apache/datafusion/pull/23870
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #23870:
URL: https://github.com/apache/datafusion/pull/23870#issuecomment-5214878148
benchmark PR: https://github.com/apache/datafusion/pull/24160
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #23870:
URL: https://github.com/apache/datafusion/pull/23870#issuecomment-5268020612
@comphead
- P1 — Classic Left/Full PiecewiseMergeJoin can silently drop unmatched rows pre-PR; the fix ships without a regression test -- Added UT in 2b73c41200016c9da23ae429e5849d28a3b7131f
- P1 — Extreme-key extraction uses sort_to_indices(..., Some(1)) (O(N log N) full sort) instead of the O(N) MinAccumulator/MaxAccumulator pattern DataFusion already uses - fixed in 2b73c41200016c9da23ae429e5849d28a3b7131f
- P2 — No benchmark despite "magnitudes faster" performance claim -- benchmark PR: https://github.com/apache/datafusion/pull/24160
- P2 — No fuzz coverage for PWMJ LeftSemi/LeftAnti in join_fuzz.rs -- added fuzz test in d3cec1334861894a69127190d13f9f9ffe26ce8c
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23870:
URL: https://github.com/apache/datafusion/pull/23870#issuecomment-5224325739
> This high-level approach LGTM, I might not be able to do detailed follow-up review timely, but it should be good to go if others can do the review.
Thanks you @2010YOUY01 I will move this forward from here.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #23870:
URL: https://github.com/apache/datafusion/pull/23870#issuecomment-5224138428
Thank you for this really nice PR, I got some suggestions:
- (optional) Split the implementation for semi/anti to a new stream: although the high-level algorithm is similar, semi/anti and regular joins are still different relational operator, and have different algorithm/optimization details, separating them can make the code easier to maintain. (sorry I only figured this out after writing the original suggestion in https://github.com/apache/datafusion/pull/18392#issuecomment-4277614451)
If you opt to leave it to a follow-up, we might need some renaming/doc updates to avoid confusion. The existing term `classic_join` means non semi/anti joins, and now we're implementing semi/anti joins inside `classic_join.rs`
- Move most UTs to sqllogictests: as sqls are easier to maintain and stronger, they can also also exercise potential related optimizations like swap joins. I think for UT only basic/demo tests are needed.
This high-level approach LGTM, I might not be able to do detailed follow-up review timely, but it should be good to go if others can do the review.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat(pwmj): support LeftSemi/LeftAnti existence joins via classic scan [datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on PR #23870:
URL: https://github.com/apache/datafusion/pull/23870#issuecomment-5241957781
Thanks @SubhamSinghal this PR is on my list today!
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org