Skip to content

Commit 9d916ab

Browse files
committed
bench: add filtered inner sort-merge join cases
Adds `sort_merge_join` benchmark cases for Inner joins with a filter: - `inner_1to10_filtered` and `inner_1to100_filtered`, in which every streamed row matches 10 or 100 buffered rows and `left.data < right.data` keeps about half of the pairs. - `inner_1to10_high_pass_filtered`, in which `left.data <> right.data` keeps 90% of the pairs, and its `_narrow` variant over just the `key` and `data` columns, where the filter reads half of the output columns. - `inner_1to1000_selective_filtered`, in which every streamed row matches 1000 buffered rows and `left.data > right.data` keeps about 5% of the 2M pairs. This is the shape of TPC-DS q72's `catalog_sales` to `inventory` join.
1 parent 14b3edd commit 9d916ab

1 file changed

Lines changed: 127 additions & 1 deletion

File tree

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

Lines changed: 127 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -78,6 +78,22 @@ fn build_sorted_batches_with_size(
7878
batches
7979
}
8080

81+
/// Like [`build_sorted_batches`], but with only the `key` and `data` columns of
82+
/// [`narrow_schema`].
83+
fn build_narrow_sorted_batches(num_rows: usize, key_mod: usize) -> Vec<RecordBatch> {
84+
let s = schema();
85+
let narrow = narrow_schema();
86+
build_sorted_batches(num_rows, key_mod, &s)
87+
.into_iter()
88+
.map(|b| {
89+
b.project(&[0, 1])
90+
.unwrap()
91+
.with_schema(Arc::clone(&narrow))
92+
.unwrap()
93+
})
94+
.collect()
95+
}
96+
8197
fn make_exec(
8298
batches: &[RecordBatch],
8399
schema: &SchemaRef,
@@ -93,8 +109,21 @@ fn schema() -> SchemaRef {
93109
]))
94110
}
95111

112+
/// The `key` and `data` columns of [`schema`].
113+
fn narrow_schema() -> SchemaRef {
114+
Arc::new(Schema::new(vec![
115+
Field::new("key", DataType::Int64, false),
116+
Field::new("data", DataType::Int64, false),
117+
]))
118+
}
119+
96120
/// The join filter `left.data < right.data`.
97121
fn data_lt_filter() -> JoinFilter {
122+
data_filter(Operator::Lt)
123+
}
124+
125+
/// The join filter `left.data <op> right.data`.
126+
fn data_filter(op: Operator) -> JoinFilter {
98127
let column_indices = vec![
99128
ColumnIndex {
100129
index: 1,
@@ -111,7 +140,7 @@ fn data_lt_filter() -> JoinFilter {
111140
]);
112141
let expression = Arc::new(BinaryExpr::new(
113142
Arc::new(Column::new("left_data", 0)),
114-
Operator::Lt,
143+
op,
115144
Arc::new(Column::new("right_data", 1)),
116145
));
117146
JoinFilter::new(expression, column_indices, Arc::new(intermediate_schema))
@@ -232,6 +261,103 @@ fn bench_smj(c: &mut Criterion) {
232261
});
233262
}
234263

264+
// 1:10 and 1:100 Inner Joins with a filter. `left.data < right.data` keeps
265+
// about half of the pairs. A streamed row meets a run of 10 or 100 buffered
266+
// rows, so its pairs are filtered at freeze.
267+
for (n, key_mod, name) in [
268+
(100_000, 10_000, "inner_1to10_filtered"),
269+
(20_000, 200, "inner_1to100_filtered"),
270+
] {
271+
let left_batches = build_sorted_batches(n, key_mod, &s);
272+
let right_batches = build_sorted_batches(n, key_mod, &s);
273+
group.bench_function(BenchmarkId::new(name, n), |b| {
274+
b.iter(|| {
275+
let left = make_exec(&left_batches, &s);
276+
let right = make_exec(&right_batches, &s);
277+
do_join_with_filter(
278+
left,
279+
right,
280+
datafusion_common::JoinType::Inner,
281+
Some(data_lt_filter()),
282+
&rt,
283+
)
284+
})
285+
});
286+
}
287+
288+
// 1:10 Inner Joins with a filter that keeps most pairs — 100K left, 100K right,
289+
// 10K distinct keys. `left.data <> right.data` drops only the pair of a row with
290+
// itself, keeping 90% of the pairs. The narrow case joins just `key` and `data`,
291+
// so the filter reads half of the output columns.
292+
{
293+
let n = 100_000;
294+
let key_mod = 10_000;
295+
let left_batches = build_sorted_batches(n, key_mod, &s);
296+
let right_batches = build_sorted_batches(n, key_mod, &s);
297+
group.bench_function(
298+
BenchmarkId::new("inner_1to10_high_pass_filtered", n),
299+
|b| {
300+
b.iter(|| {
301+
let left = make_exec(&left_batches, &s);
302+
let right = make_exec(&right_batches, &s);
303+
do_join_with_filter(
304+
left,
305+
right,
306+
datafusion_common::JoinType::Inner,
307+
Some(data_filter(Operator::NotEq)),
308+
&rt,
309+
)
310+
})
311+
},
312+
);
313+
let narrow = narrow_schema();
314+
let left_batches = build_narrow_sorted_batches(n, key_mod);
315+
let right_batches = build_narrow_sorted_batches(n, key_mod);
316+
group.bench_function(
317+
BenchmarkId::new("inner_1to10_high_pass_filtered_narrow", n),
318+
|b| {
319+
b.iter(|| {
320+
let left = make_exec(&left_batches, &narrow);
321+
let right = make_exec(&right_batches, &narrow);
322+
do_join_with_filter(
323+
left,
324+
right,
325+
datafusion_common::JoinType::Inner,
326+
Some(data_filter(Operator::NotEq)),
327+
&rt,
328+
)
329+
})
330+
},
331+
);
332+
}
333+
334+
// 1:1000 Inner Join with a selective filter — 2K left, 20K right, 20 keys
335+
// Every streamed row meets a run of 1000 buffered rows, the shape of TPC-DS
336+
// q72's `catalog_sales` to `inventory` join. Each key's 100 streamed rows take
337+
// the smallest of its `data` values, so `left.data > right.data` keeps about
338+
// 5% of the 2M pairs. Such runs are filtered as they are paired.
339+
{
340+
let keys = 20;
341+
let left_batches = build_sorted_batches(keys * 100, keys, &s);
342+
let right_batches = build_sorted_batches(keys * 1000, keys, &s);
343+
group.bench_function(
344+
BenchmarkId::new("inner_1to1000_selective_filtered", keys * 1000),
345+
|b| {
346+
b.iter(|| {
347+
let left = make_exec(&left_batches, &s);
348+
let right = make_exec(&right_batches, &s);
349+
do_join_with_filter(
350+
left,
351+
right,
352+
datafusion_common::JoinType::Inner,
353+
Some(data_filter(Operator::Gt)),
354+
&rt,
355+
)
356+
})
357+
},
358+
);
359+
}
360+
235361
// Left Join — 100K each, ~5% unmatched on left
236362
{
237363
let n = 100_000;

0 commit comments

Comments
 (0)