Repository navigation
Commit 7f493a5
authored
perf: append sort-merge join output pairs in bulk (apache#26277)
## Which issue does this PR close?
- Part of apache#20910.
## Rationale for this change
A sort-merge join in which each row matches many rows on the other side
spends most of its time recording the matches. For every buffered row of
the key group, `pair_streamed_row_with_group` calls
`append_output_pair`, which looks up the current chunk and appends one
value to each of two `UInt64Builder`s, and then advances the scan by one
row.
In DataFusion Comet, which runs DataFusion 55.2.0, a sort-merge join of
1M rows in which every row matches 100 rows (105M joined rows feeding a
`sum`) spent 46% of its active CPU in these two functions, against 14%
in the `take` that builds the output batches.
## What changes are included in this PR?
- `pair_streamed_row_with_group` pairs the streamed row with the rest of
the scanning buffered batch at once, capped by the room left in the
output batch. The new `BufferedData::scanning_remaining` gives those
rows, and `BufferedData::scanning_advance_by` moves the scan past them.
- The new `StreamedBatch::append_output_pairs` appends a run of one row,
as in a one-to-one join, directly. Longer runs go to
`append_output_range`, which extends the chunk's streamed indices with
`repeat_n` and its buffered indices with the range of rows, and appends
their validity with one `append_n_non_nulls`. It is kept out of line so
that the one-row path doesn't pay for its setup.
- `StreamedJoinedChunk` keeps its indices in `Vec<u64>`s, as hash join
does, with a `NullBufferBuilder` for the buffered nulls, instead of in
`UInt64Builder`s. That takes the per-row null and capacity checks out of
the bulk append, and `freeze_streamed` builds the arrays with
`UInt64Array::try_new`, which skips the `ArrayData` that
`PrimitiveBuilder::finish` builds for every chunk
(apache/arrow-rs#11717).
- The chunk lookup is now `chunk_for`, which keeps only its check inline
and starts a new chunk in a cold `start_chunk`. With that, one-to-one
joins are slightly faster than on `main`.
- `append_output_pair`'s only remaining caller passed a null buffered
index, so it is now `append_null_joined_pair`. `scanning_advance` is
replaced by `scanning_advance_by(1)`.
The pairs, their order and the chunks they go to are unchanged, so
freezing, filtering and spilling see the same indices as before.
## What is the testing strategy for this PR?
- The existing sort-merge join tests cover this path for every join
type, including those that run with batch sizes of 1, 2 and 50 and those
that spill.
- The join fuzz tests, which compare sort-merge and hash join results
across join types, pass (`cargo test -p datafusion --features
extended_tests --test fuzz -- join_fuzz`). Most of their key groups hold
one row, though, so only 3–5% of their appends are runs of more than one
row, and none is cut by the output batch. The new low-cardinality cases,
`test_{inner,left,right,full}_join_1k_low_cardinality` and their
`_filtered` variants, draw the keys from 25 values. In each of them
about 30% of the appends are runs of more than one row, 14,000–19,000
runs are cut by the output batch, and 51,000–56,000 end at a buffered
batch boundary with the group continuing in the next one.
- New `join_inner_group_spans_buffered_and_output_batches`, next to
`join_with_group_spanning_batches_rescanned_per_streamed_row`, which
uses one-row buffered batches. In the new test the key group spans
buffered batches of 3, 2 and 1 rows and the batch size is 4, so runs of
several rows end both at the end of a buffered batch and when the output
batch fills.
- New benchmark cases `inner_1to100`, in which every streamed row
matches 100 buffered rows, and `left_1to100_filtered`, which joins the
same inputs with a filter, so that the pairs go through deferred
filtering.
`sort_merge_join` benchmark against `main`, the median of seven
interleaved runs of each binary on an Apple M3 Max:
| Case | `main` | This PR | Change |
| --- | --- | --- | --- |
| `inner_1to1` | 1.484 ms | 1.427 ms | −3.9% |
| `inner_1to10` | 12.89 ms | 8.755 ms | −32.1% |
| `inner_1to100` (new) | 24.89 ms | 15.98 ms | −35.8% |
| `left_1to100_filtered` (new) | 53.56 ms | 44.59 ms | −16.8% |
| `left_1to1_unmatched` | 1.485 ms | 1.428 ms | −3.8% |
| `left_semi_1to10` | 0.607 ms | 0.607 ms | 0.0% |
| `left_anti_partial` | 0.763 ms | 0.764 ms | +0.1% |
| `inner_group_spans_buffered_batches/512` | 4.052 ms | 2.981 ms |
−26.4% |
| `inner_group_spans_buffered_batches/64` | 5.286 ms | 3.929 ms | −25.7%
|
| `inner_group_spans_buffered_batches/8` | 15.52 ms | 12.41 ms | −20.1%
|
The semi and anti cases don't use this stream, and they moved by 0.1% at
most. Keeping the bulk path and the chunk creation inline instead made
the one-to-one cases about 5% slower than `main`. Keeping the indices in
`UInt64Builder`s, with a loop of `append_value` for a run's buffered
indices, made the cases with several matches per row 7–20% slower.
In DataFusion Comet (apache/datafusion-comet#6907), a prototype of the
bulk path on 55.2.0 cut the native sort-merge join's CPU time by 39% at
100 matches per row and by 46% at 1000. At 100 matches per row that took
it from twice the time of Spark's whole-stage-codegen sort-merge join to
the same time.
## Are there any user-facing changes?
No. Sort-merge joins in which rows match many rows run faster.1 parent 13a65f0 commit 7f493a5
4 files changed
Lines changed: 418 additions & 61 deletions
File tree
- datafusion
- core/tests/fuzz_cases
- physical-plan
- benches
- src/joins/sort_merge_join
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
662 | 662 | | |
663 | 663 | | |
664 | 664 | | |
| 665 | + | |
| 666 | + | |
| 667 | + | |
| 668 | + | |
| 669 | + | |
| 670 | + | |
| 671 | + | |
| 672 | + | |
| 673 | + | |
| 674 | + | |
| 675 | + | |
| 676 | + | |
| 677 | + | |
| 678 | + | |
| 679 | + | |
| 680 | + | |
| 681 | + | |
| 682 | + | |
| 683 | + | |
| 684 | + | |
| 685 | + | |
| 686 | + | |
| 687 | + | |
| 688 | + | |
| 689 | + | |
| 690 | + | |
| 691 | + | |
| 692 | + | |
| 693 | + | |
| 694 | + | |
| 695 | + | |
| 696 | + | |
| 697 | + | |
| 698 | + | |
| 699 | + | |
| 700 | + | |
| 701 | + | |
| 702 | + | |
| 703 | + | |
| 704 | + | |
| 705 | + | |
| 706 | + | |
| 707 | + | |
| 708 | + | |
| 709 | + | |
| 710 | + | |
| 711 | + | |
| 712 | + | |
| 713 | + | |
| 714 | + | |
| 715 | + | |
| 716 | + | |
| 717 | + | |
| 718 | + | |
| 719 | + | |
| 720 | + | |
| 721 | + | |
| 722 | + | |
| 723 | + | |
| 724 | + | |
| 725 | + | |
| 726 | + | |
| 727 | + | |
| 728 | + | |
| 729 | + | |
| 730 | + | |
| 731 | + | |
| 732 | + | |
| 733 | + | |
| 734 | + | |
| 735 | + | |
| 736 | + | |
| 737 | + | |
| 738 | + | |
| 739 | + | |
| 740 | + | |
| 741 | + | |
| 742 | + | |
| 743 | + | |
| 744 | + | |
| 745 | + | |
| 746 | + | |
| 747 | + | |
| 748 | + | |
| 749 | + | |
| 750 | + | |
| 751 | + | |
| 752 | + | |
| 753 | + | |
| 754 | + | |
| 755 | + | |
| 756 | + | |
| 757 | + | |
| 758 | + | |
| 759 | + | |
| 760 | + | |
| 761 | + | |
| 762 | + | |
| 763 | + | |
| 764 | + | |
| 765 | + | |
| 766 | + | |
| 767 | + | |
| 768 | + | |
| 769 | + | |
| 770 | + | |
| 771 | + | |
| 772 | + | |
| 773 | + | |
| 774 | + | |
| 775 | + | |
| 776 | + | |
| 777 | + | |
| 778 | + | |
| 779 | + | |
| 780 | + | |
| 781 | + | |
| 782 | + | |
665 | 783 | | |
666 | 784 | | |
667 | 785 | | |
| |||
1392 | 1510 | | |
1393 | 1511 | | |
1394 | 1512 | | |
| 1513 | + | |
| 1514 | + | |
| 1515 | + | |
| 1516 | + | |
| 1517 | + | |
| 1518 | + | |
| 1519 | + | |
| 1520 | + | |
| 1521 | + | |
| 1522 | + | |
1395 | 1523 | | |
1396 | 1524 | | |
1397 | 1525 | | |
1398 | 1526 | | |
1399 | 1527 | | |
1400 | | - | |
| 1528 | + | |
| 1529 | + | |
| 1530 | + | |
| 1531 | + | |
1401 | 1532 | | |
1402 | 1533 | | |
1403 | 1534 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
27 | 27 | | |
28 | 28 | | |
29 | 29 | | |
30 | | - | |
| 30 | + | |
31 | 31 | | |
32 | | - | |
| 32 | + | |
| 33 | + | |
33 | 34 | | |
34 | | - | |
| 35 | + | |
| 36 | + | |
35 | 37 | | |
36 | 38 | | |
37 | 39 | | |
| |||
104 | 106 | | |
105 | 107 | | |
106 | 108 | | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
107 | 133 | | |
108 | 134 | | |
109 | 135 | | |
110 | 136 | | |
111 | 137 | | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
112 | 148 | | |
113 | 149 | | |
114 | 150 | | |
| |||
118 | 154 | | |
119 | 155 | | |
120 | 156 | | |
121 | | - | |
| 157 | + | |
122 | 158 | | |
123 | 159 | | |
124 | 160 | | |
| |||
168 | 204 | | |
169 | 205 | | |
170 | 206 | | |
| 207 | + | |
| 208 | + | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
| 212 | + | |
| 213 | + | |
| 214 | + | |
| 215 | + | |
| 216 | + | |
| 217 | + | |
| 218 | + | |
| 219 | + | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
| 230 | + | |
| 231 | + | |
| 232 | + | |
| 233 | + | |
| 234 | + | |
| 235 | + | |
| 236 | + | |
| 237 | + | |
| 238 | + | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
171 | 248 | | |
172 | 249 | | |
173 | 250 | | |
| |||
0 commit comments