Repository navigation
chore: refactor SortMergeJoin bitwise stream to generators and simplify to be textbook like as possible - #23761
Merged
rluvaton merged 8 commits intoJul 28, 2026
Conversation
Member
Author
|
run benchmark smj |
|
🤖 Benchmark running (GKE) | trigger CPU Details (lscpu)Comparing let-claude-try-refactor-bitwise-stream-to-use-generator (d3e32e9) to ed22a4a (merge-base) diff using: smj File an issue against this benchmark runner |
mbutrovich
self-requested a review
July 21, 2026 14:54
Contributor
|
Love to see a negative line count! |
|
🤖 Benchmark completed (GKE) | trigger Instance: CPU Details (lscpu)Details
Resource Usagesmj — base (merge-base)
smj — branch
File an issue against this benchmark runner |
Codecov Report❌ Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## main #23761 +/- ##
==========================================
- Coverage 80.67% 80.66% -0.01%
==========================================
Files 1094 1095 +1
Lines 371770 372197 +427
Branches 371770 372197 +427
==========================================
+ Hits 299907 300233 +326
- Misses 53964 54032 +68
- Partials 17899 17932 +33 ☔ View full report in Codecov by Harness. 🚀 New features to boost your workflow:
|
…e when waiting for inputs
Member
Author
Now its not due to added tests to make sure we are not counting child/consumer time, but the stream file still have negative line count! |
rluvaton
marked this pull request as ready for review
July 26, 2026 20:25
Member
Author
|
@mbutrovich Can you please review? 😅 |
Contributor
I'll find some time this week, definitely. Thanks for the PR! |
Contributor
|
Out of curiosity, is the non-bitwise SMJ stream up next? |
Member
Author
if I can make it more readable yes, afterward I will try to migrate the new hash aggregate exec |
mbutrovich
approved these changes
Jul 28, 2026
mbutrovich
left a comment
mbutrovich
left a comment
Contributor
There was a problem hiding this comment.
Thanks for tackling this, @rluvaton! It reads much better now.
Traced the control flow by hand against the removed poll-based version: every branch (outer/inner key groups crossing batch boundaries, filtered and unfiltered, spill buffer vs spill file, inner exhaustion mid-group) produces the same state transitions. PendingBoundary, batch_emitted, buffering_inner_pending, and spill_stream_has_data only existed to survive unwinding out of poll_join on Pending; with await the function suspends in place, so removing them is correct, not just simpler.
The two new sync fast paths (try_skip_inner_key_group, try_process_key_match) skip the async machinery when a key group does not reach a batch boundary. Checked their output against the general path for that case and they compute the same cursor and matched-bit state.
CI is green (clippy, cargo test, extended_tests), the existing semi/anti/mark fuzz tests in join_fuzz.rs exercise this stream end to end, and the posted smj benchmark shows no regression.
One request before merge: datafusion/physical-plan/src/joins/sort_merge_join/bitwise_stream.rs:744 notes that the clock now keeps running across spill read-back, where before a genuine Pending from the spill stream stopped the per-call timer early and that wait was invisible to join_time. That is a real change to what the metric measures, not just an implementation detail. Please add a line to the PR description calling this out, since it currently says "no user-facing changes" and join_time is visible in EXPLAIN ANALYZE.
github-merge-queue
Bot
removed this pull request from the merge queue due to failed status checks
Jul 28, 2026
rluvaton
deleted the
let-claude-try-refactor-bitwise-stream-to-use-generator
branch
July 28, 2026 19:57
13 tasks done
kosiew
pushed a commit
to kosiew/datafusion
that referenced
this pull request
Aug 12, 2026
…fy to be textbook like as possible (apache#23761) ## Which issue does this PR close? N/A ## Rationale for this change SortMergeJoin bitwise stream implementation is very complex and hard to understand while on paper it should be pretty simple. the reason for that is we have to store state between polls (we had `boundary`) and handle the case where both can get `Poll::Pending` from child and `Poll::Ready` from child which further complicate the code ## What changes are included in this PR? 1. Move to async generators 2. Rewrote main loop to be textbook like as possible (this was entirely written by Claude Fable, sorry, I tried manually but the code was too complex to hold in my head 😅 ) ## Are these changes tested? existing tests ## Are there any user-facing changes? The join_time now includes the time to read from the async spill stream between pending which is arguable more correct since this time is part of the operator, although long waits between pending calls will be counted in the op `join_time` while the alternative is not counting the read from file and decoding...
alamb
pushed a commit
that referenced
this pull request
Nov 12, 2026
…luation (#26027) (#27356) ## Which issue does this PR close? - Part of #23805 (the 54.2.0 patch release tracking issue). - Backport of #26027 to `branch-54`. #26027 fixed #26001. ## Rationale for this change With a sort-merge join (`datafusion.optimizer.prefer_hash_join = false`), a `LEFT`, `RIGHT` or `FULL` join with an extra join filter fails with `Arrow error: Invalid argument error: Column '...' is declared as non-nullable but contains null values` when the NULL-padded side has `NOT NULL` columns referenced by the filter. Hash join returns the correct result for the same queries. This is a failed query, which makes it eligible for backport as a correctness fix. The four new sqllogictest queries fail on `branch-54` exactly as on `main`. #26027 fixed it on `main` (labelled `v56.0.0`); it is on `branch-56` but not on `branch-54`. It was requested for `branch-54` on #26868 (#26868 (comment)), "to prevent regressions on upgrade to 54". ## What changes are included in this PR? - A `git cherry-pick -x` of 8248a57 (#26027, by @CuteChuanChuan), with the conflicts in `materializing_stream.rs` resolved by hand. The sort-merge join on this branch predates the generator refactor (#23761, #23976), so the surrounding code differs. - `datafusion/physical-plan/src/joins/sort_merge_join/materializing_stream.rs`: `MaterializingSortMergeJoinStream::try_new` builds the filter schema once with the buffered-side fields marked nullable, and filter evaluation uses it. It is only built when the join needs deferred filtering. This branch has no cached `deferred_filtering` field and calls `needs_deferred_filtering(&self.filter, self.join_type)` where it is needed, so the filter schema is built from that call; there is no other change in the constructor. The filter result of a NULL-padded row does not affect the output, so this does not change results. - `datafusion/sqllogictest/test_files/sort_merge_join.slt`: the cases from #26027, unchanged (they applied cleanly). ## Are these changes tested? Yes. On this branch (Rust 1.95.0) I ran: - `cargo test -p datafusion-sqllogictest --test sqllogictests -- join`: all 14 matching files pass, including `sort_merge_join.slt` with the new cases. - With the change in `materializing_stream.rs` reverted and the new slt cases kept, the four new queries fail with the Arrow error above (`sort_merge_join.slt` lines 990, 997, 1004 and 1013). - `cargo test -p datafusion-physical-plan --lib`: 1439 passed. - `cargo fmt --all -- --check` and `cargo clippy -p datafusion-physical-plan --all-targets --all-features -- -D warnings` pass. ## Are there any user-facing changes? No. Bug fix only; no public API change. 🤖 Generated with [Claude Code](https://claude.com/claude-code) Co-authored-by: Yu-Chuan Hung <[email protected]> Co-authored-by: Claude Sonnet 5.5 <[email protected]>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Which issue does this PR close?
N/A
Rationale for this change
SortMergeJoin bitwise stream implementation is very complex and hard to understand while on paper it should be pretty simple.
the reason for that is we have to store state between polls (we had
boundary) and handle the case where both can getPoll::Pendingfrom child andPoll::Readyfrom child which further complicate the codeWhat changes are included in this PR?
(this was entirely written by Claude Fable, sorry, I tried manually but the code was too complex to hold in my head 😅 )
Are these changes tested?
existing tests
Are there any user-facing changes?
The join_time now includes the time to read from the async spill stream between pending which is arguable more correct since this time is part of the operator, although long waits between pending calls will be counted in the op
join_timewhile the alternative is not counting the read from file and decoding...