andygrove opened a new pull request, #23673: URL: https://github.com/apache/datafusion/pull/23673
## Which issue does this PR close? <!-- No existing issue; this is a self-contained performance improvement. Happy to file a tracking issue if preferred. --> - N/A ## Rationale for this change The `MaterializingSortMergeJoinStream` (used for inner/left/right/full joins) produces output one row at a time in `join_partial`. When a single streamed row matches a run of buffered rows — i.e. a high fan-out join — each matched row incurs: - a `VecDeque` index lookup in `scanning_idx()`, - two more `VecDeque` index computations inside `scanning_advance()`, and - two individual `UInt64Builder::append_value` calls. The buffered rows that match within a single buffered batch always form a **contiguous index range**, so this per-row work is unnecessary overhead that scales with the number of output rows. ## What changes are included in this PR? - Add `StreamedBatch::append_output_range`, which appends a contiguous run of buffered indices against the current streamed index in bulk (`append_value_n` + `append_slice`) instead of one pair at a time. A reusable scratch buffer (`buffered_index_scratch`) materializes the index range, and a `len == 1` fast path keeps the common one-row-per-key case free of scratch-buffer overhead. - Add `BufferedData::scanning_advance_by(n)` and `scanning_batch_remaining()` so the scan cursor can advance by a whole run at once. `join_partial` now computes the run length (capped by the remaining output-batch capacity) and appends the whole run in a single step. The FULL-join null-joined branch is likewise updated to `extend` a range rather than pushing per row. No behavior change — output is identical, only the way indices are accumulated changes. ### Benchmark results (`cargo bench --bench sort_merge_join`) | Benchmark | Before | After | Change | |---|---|---|---| | `inner_1to10` (1:10 fan-out, 1M output rows) | 13.28 ms | 10.18 ms | **~23% faster** | | `inner_1to1` | 2.76 ms | 2.68 ms | neutral | | `left_1to1_unmatched` | 2.73 ms | 2.67 ms | neutral | The semi/anti benchmarks use a different stream (`BitwiseSortMergeJoinStream`) that is unchanged. ## Are these changes tested? Covered by existing tests: - 64 sort-merge-join unit tests in `datafusion-physical-plan` pass. - The `sort_merge_join.slt` sqllogictest passes. ## Are there any user-facing changes? No. -- 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]
