SubhamSinghal opened a new pull request, #26287: URL: https://github.com/apache/datafusion/pull/26287
## Which issue does this PR close? - Part of #18221 (and the PiecewiseMergeJoin EPIC #17427). ## Rationale for this change On large inputs the classic `PiecewiseMergeJoin` (Inner/Left/Right/Full) can be slower than `NestedLoopJoin`. For example, before #25840, `l JOIN r ON l.a < r.b` over 100K×100K rows at the default `target_partitions` took 1.41s with PWMJ and 1.26s with NLJ. A profile of the 1K×1M case (`sample`, `target_partitions = 1`) shows the time goes to copying output rather than to comparisons: | where | share of busy samples | |---|---| | `take` repeating each matched streamed row | 32% | | `BatchCoalescer` `memmove` of every column | 30% | | downstream `sum` (the query itself) | 10% | | per-streamed-row fixed cost (`RecordBatch`, allocations, coalescer bookkeeping) | ~13% | For every matched streamed row, the join takes `UInt32Array::from_value(row, count)`, gathers the streamed row `count` times, slices the buffered suffix, and builds a `RecordBatch` from them. `BatchCoalescer` then copies all of it again, so the streamed columns are written twice. #25840 made finding each row's first match a binary search and settles never-matching rows before the sort, but it kept this emission path, so on current `main` the cost above is still paid for every matched streamed row. ## What changes are included in this PR? The classic join builds each output batch directly, and `BatchCoalescer` is removed from this path. Matched rows: - The output is kept as runs: `(buffered start, len)`, paired with one streamed row index per output row. - Once `batch_size` rows are pending, or the stream batch ends: - Buffered columns are copied run by run with `MutableArrayData::try_extend`, which is a `memcpy` for fixed-width types. - Streamed columns are gathered with one `take` per column. Rows that match nothing are emitted with null columns for the other side, as zero-copy slices in batches of at most `batch_size` (`push_null_padded`): - Streamed rows that can never match (`Right`/`Full`), which #25840 settles before the sort, are selected with one `filter_record_batch`. When every row of a stream batch is unmatched, `filter` returns the input columns as a slice and copies nothing. - Unmatched buffered rows (`Left`/`Full`), in the final pass, are the prefix before the `min_marked` watermark plus any trailing NULL keys (#26043). They are sliced from the buffered side without a `concat_batches`. ## Benchmarks The pwmj suite from https://github.com/apache/datafusion/pull/25839 (100K buffered keys, 2M streamed rows, five match regimes × INNER/LEFT/RIGHT/FULL). Reproduce with: `cargo run -p datafusion-benchmarks --release --bin benchmark_runner -- pwmj` | regime | main (ms) | this PR (ms) | speedup | |---|---|---|---| | no_match, null_heavy: Inner, Left | 2.2–2.3 | 2.2–2.3 | 1.00× | | no_match, null_heavy: Right, Full | 3.2–3.4 | 2.5–2.6 | **1.28–1.31×** | | half_match | 248–250 | 28–29 | **8.6–8.9×** | | selective | 488–495 | 47–48 | **10.3–10.5×** | | all_match (200M output rows) | 167 | 159–162 | 1.04–1.05× | ## What is the testing strategy for this PR? - Four new unit tests in `classic_join.rs`: - `join_full_less_than_splits_suffixes_across_batches`: at `batch_size = 4`, a buffered suffix straddles an output batch, and never-matching streamed rows, matched rows and unmatched buffered rows all appear. It asserts both the rows and the batch sizes `[1, 4, 2, 1]`. - `join_right_less_than_empty_buffered`: a Right join with an empty buffered side, where every streamed row is padded with nulls. - `join_right_less_than_never_matching_rows_split_by_batch_size`: more never-matching streamed rows than `batch_size`, which must be split into batches of at most `batch_size`, in input order, ahead of the matched rows. - `join_left_less_than_unmatched_prefix_and_trailing_nulls`: a Left join on `<` whose unmatched buffered rows are a prefix longer than `batch_size` plus trailing NULL keys, which sort last for `<`. ## Are there any user-facing changes? 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]
