@@ -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+
8197fn 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`.
97121fn 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