Skip to content

Commit 7f493a5

Browse files
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/join_fuzz.rs‎

Lines changed: 132 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -662,6 +662,124 @@ async fn test_right_mark_join_1k_binary_filtered() {
662662
}
663663
}
664664

665+
// In the tests above, most key groups hold one row: the i32 tests draw the join keys
666+
// `(a, b)` from 10,000 values for 1000 rows, and the binary ones from random bytes.
667+
// The tests below draw them from 25 values, so each streamed row matches about 40
668+
// buffered rows. Sort-merge join pairs a streamed row with its matches in runs, which
669+
// end where a buffered batch ends or where the output batch fills.
670+
671+
#[tokio::test]
672+
async fn test_inner_join_1k_low_cardinality() {
673+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
674+
JoinFuzzTestCase::new(
675+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
676+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
677+
JoinType::Inner,
678+
None,
679+
)
680+
.run_test(&[HjSmj, NljHj], false)
681+
.await
682+
}
683+
}
684+
685+
#[tokio::test]
686+
async fn test_inner_join_1k_low_cardinality_filtered() {
687+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
688+
JoinFuzzTestCase::new(
689+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
690+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
691+
JoinType::Inner,
692+
Some(Box::new(col_lt_col_filter)),
693+
)
694+
.run_test(&[HjSmj, NljHj], false)
695+
.await
696+
}
697+
}
698+
699+
#[tokio::test]
700+
async fn test_left_join_1k_low_cardinality() {
701+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
702+
JoinFuzzTestCase::new(
703+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
704+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
705+
JoinType::Left,
706+
None,
707+
)
708+
.run_test(&[HjSmj, NljHj], false)
709+
.await
710+
}
711+
}
712+
713+
#[tokio::test]
714+
async fn test_left_join_1k_low_cardinality_filtered() {
715+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
716+
JoinFuzzTestCase::new(
717+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
718+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
719+
JoinType::Left,
720+
Some(Box::new(col_lt_col_filter)),
721+
)
722+
.run_test(&[HjSmj, NljHj], false)
723+
.await
724+
}
725+
}
726+
727+
#[tokio::test]
728+
async fn test_right_join_1k_low_cardinality() {
729+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
730+
JoinFuzzTestCase::new(
731+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
732+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
733+
JoinType::Right,
734+
None,
735+
)
736+
.run_test(&[HjSmj, NljHj], false)
737+
.await
738+
}
739+
}
740+
741+
#[tokio::test]
742+
async fn test_right_join_1k_low_cardinality_filtered() {
743+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
744+
JoinFuzzTestCase::new(
745+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
746+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
747+
JoinType::Right,
748+
Some(Box::new(col_lt_col_filter)),
749+
)
750+
.run_test(&[HjSmj, NljHj], false)
751+
.await
752+
}
753+
}
754+
755+
#[tokio::test]
756+
async fn test_full_join_1k_low_cardinality() {
757+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
758+
JoinFuzzTestCase::new(
759+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
760+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
761+
JoinType::Full,
762+
None,
763+
)
764+
.run_test(&[HjSmj, NljHj], false)
765+
.await
766+
}
767+
}
768+
769+
#[tokio::test]
770+
async fn test_full_join_1k_low_cardinality_filtered() {
771+
for (left_extra, right_extra) in [(true, true), (false, true), (true, false)] {
772+
JoinFuzzTestCase::new(
773+
make_staggered_batches_i32_with_key_range(1000, 5, left_extra),
774+
make_staggered_batches_i32_with_key_range(1000, 5, right_extra),
775+
JoinType::Full,
776+
Some(Box::new(col_lt_col_filter)),
777+
)
778+
.run_test(&[HjSmj, NljHj], false)
779+
.await
780+
}
781+
}
782+
665783
type JoinFilterBuilder = Box<dyn Fn(Arc<Schema>, Arc<Schema>) -> JoinFilter>;
666784

667785
struct JoinFuzzTestCase {
@@ -1392,12 +1510,25 @@ async fn test_nested_loop_join_spill_fuzz() {
13921510
/// two sorted int32 columns 'a', 'b' ranged from 0..99 as join columns
13931511
/// two random int32 columns 'x', 'y' as other columns
13941512
fn make_staggered_batches_i32(len: usize, with_extra_column: bool) -> Vec<RecordBatch> {
1513+
make_staggered_batches_i32_with_key_range(len, 100, with_extra_column)
1514+
}
1515+
1516+
/// Like [`make_staggered_batches_i32`], but with 'a' and 'b' drawn from
1517+
/// `0..key_range`, so that a small `key_range` makes few, large key groups
1518+
fn make_staggered_batches_i32_with_key_range(
1519+
len: usize,
1520+
key_range: i32,
1521+
with_extra_column: bool,
1522+
) -> Vec<RecordBatch> {
13951523
let mut rng = rand::rng();
13961524
let mut input12: Vec<(i32, i32)> = vec![(0, 0); len];
13971525
let mut input3: Vec<i32> = vec![0; len];
13981526
let mut input4: Vec<i32> = vec![0; len];
13991527
for v in &mut input12 {
1400-
*v = (rng.random_range(0..100), rng.random_range(0..100));
1528+
*v = (
1529+
rng.random_range(0..key_range),
1530+
rng.random_range(0..key_range),
1531+
);
14011532
}
14021533
rng.fill(&mut input3[..]);
14031534
rng.fill(&mut input4[..]);

‎datafusion/physical-plan/benches/sort_merge_join.rs‎

Lines changed: 81 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -27,11 +27,13 @@ use arrow::array::{Int64Array, RecordBatch, StringArray};
2727
use arrow::compute::SortOptions;
2828
use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
2929
use criterion::{BenchmarkId, Criterion, criterion_group, criterion_main};
30-
use datafusion_common::NullEquality;
30+
use datafusion_common::{JoinSide, NullEquality};
3131
use datafusion_execution::TaskContext;
32-
use datafusion_physical_expr::expressions::col;
32+
use datafusion_expr::Operator;
33+
use datafusion_physical_expr::expressions::{BinaryExpr, Column, col};
3334
use datafusion_physical_plan::collect;
34-
use datafusion_physical_plan::joins::{SortMergeJoinExec, utils::JoinOn};
35+
use datafusion_physical_plan::joins::SortMergeJoinExec;
36+
use datafusion_physical_plan::joins::utils::{ColumnIndex, JoinFilter, JoinOn};
3537
use datafusion_physical_plan::test::TestMemoryExec;
3638
use tokio::runtime::Runtime;
3739

@@ -104,11 +106,45 @@ fn schema() -> SchemaRef {
104106
]))
105107
}
106108

109+
/// The join filter `left.data < right.data`.
110+
fn data_lt_filter() -> JoinFilter {
111+
let column_indices = vec![
112+
ColumnIndex {
113+
index: 1,
114+
side: JoinSide::Left,
115+
},
116+
ColumnIndex {
117+
index: 1,
118+
side: JoinSide::Right,
119+
},
120+
];
121+
let intermediate_schema = Schema::new(vec![
122+
Field::new("left_data", DataType::Int64, false),
123+
Field::new("right_data", DataType::Int64, false),
124+
]);
125+
let expression = Arc::new(BinaryExpr::new(
126+
Arc::new(Column::new("left_data", 0)),
127+
Operator::Lt,
128+
Arc::new(Column::new("right_data", 1)),
129+
));
130+
JoinFilter::new(expression, column_indices, Arc::new(intermediate_schema))
131+
}
132+
107133
fn do_join(
108134
left: Arc<dyn datafusion_physical_plan::ExecutionPlan>,
109135
right: Arc<dyn datafusion_physical_plan::ExecutionPlan>,
110136
join_type: datafusion_common::JoinType,
111137
rt: &Runtime,
138+
) -> usize {
139+
do_join_with_filter(left, right, join_type, None, rt)
140+
}
141+
142+
fn do_join_with_filter(
143+
left: Arc<dyn datafusion_physical_plan::ExecutionPlan>,
144+
right: Arc<dyn datafusion_physical_plan::ExecutionPlan>,
145+
join_type: datafusion_common::JoinType,
146+
filter: Option<JoinFilter>,
147+
rt: &Runtime,
112148
) -> usize {
113149
let on: JoinOn = vec![(
114150
col("key", &left.schema()).unwrap(),
@@ -118,7 +154,7 @@ fn do_join(
118154
left,
119155
right,
120156
on,
121-
None,
157+
filter,
122158
join_type,
123159
vec![SortOptions::default()],
124160
NullEquality::NullEqualsNothing,
@@ -168,6 +204,47 @@ fn bench_smj(c: &mut Criterion) {
168204
});
169205
}
170206

207+
// 1:100 Inner Join — 20K left, 20K right, 200 distinct keys
208+
// Every streamed row matches 100 buffered rows, so the join emits 2M rows.
209+
{
210+
let n = 20_000;
211+
let key_mod = 200;
212+
let left_batches = build_sorted_batches(n, key_mod, &s);
213+
let right_batches = build_sorted_batches(n, key_mod, &s);
214+
group.bench_function(BenchmarkId::new("inner_1to100", n), |b| {
215+
b.iter(|| {
216+
let left = make_exec(&left_batches, &s);
217+
let right = make_exec(&right_batches, &s);
218+
do_join(left, right, datafusion_common::JoinType::Inner, &rt)
219+
})
220+
});
221+
}
222+
223+
// 1:100 Left Join with a filter — 20K left, 20K right, 200 distinct keys
224+
// As in `inner_1to100`, every streamed row matches 100 buffered rows on the key,
225+
// but here the pairs go through deferred filtering. `left.data < right.data`
226+
// keeps about half of them, and none of the last streamed row of each key, which
227+
// is null-joined.
228+
{
229+
let n = 20_000;
230+
let key_mod = 200;
231+
let left_batches = build_sorted_batches(n, key_mod, &s);
232+
let right_batches = build_sorted_batches(n, key_mod, &s);
233+
group.bench_function(BenchmarkId::new("left_1to100_filtered", n), |b| {
234+
b.iter(|| {
235+
let left = make_exec(&left_batches, &s);
236+
let right = make_exec(&right_batches, &s);
237+
do_join_with_filter(
238+
left,
239+
right,
240+
datafusion_common::JoinType::Left,
241+
Some(data_lt_filter()),
242+
&rt,
243+
)
244+
})
245+
});
246+
}
247+
171248
// Left Join — 100K each, ~5% unmatched on left
172249
{
173250
let n = 100_000;

0 commit comments

Comments
 (0)