99//! *streamed* side and the *buffered* side), compares join keys, and
1010//! produces joined `RecordBatch`es.
1111
12+ use std:: borrow:: { Borrow , Cow } ;
1213use std:: cmp:: Ordering ;
1314use std:: collections:: VecDeque ;
1415use std:: fmt:: Debug ;
@@ -31,16 +32,16 @@ use crate::{PhysicalExpr, SendableRecordBatchStream};
3132use arrow:: array:: { types:: UInt64Type , * } ;
3233use arrow:: buffer:: BooleanBuffer ;
3334use arrow:: compute:: {
34- self , BatchCoalescer , SortOptions , concat_batches , filter_record_batch , interleave ,
35- take_arrays,
35+ self , BatchCoalescer , FilterBuilder , SortOptions , concat_batches ,
36+ filter_record_batch , interleave , take_arrays,
3637} ;
3738use arrow:: datatypes:: { Schema , SchemaRef } ;
3839use arrow:: record_batch:: RecordBatchOptions ;
3940use datafusion_common:: cast:: { as_boolean_array, as_uint64_array} ;
4041use datafusion_common:: instant:: Instant ;
4142use datafusion_common:: {
42- DataFusionError , JoinSide , JoinType , NullEquality , Result , ScalarValue , exec_err,
43- internal_err,
43+ DataFusionError , JoinSide , JoinType , NullEquality , Result , exec_err,
44+ internal_datafusion_err , internal_err,
4445} ;
4546use datafusion_execution:: memory_pool:: MemoryReservation ;
4647use datafusion_execution:: runtime_env:: RuntimeEnv ;
@@ -81,18 +82,18 @@ impl MatchedChunk {
8182
8283 /// Keeps the pairs whose bit is set in `mask`.
8384 fn filter ( & self , mask : & BooleanBuffer ) -> Result < Self > {
84- let mask = BooleanArray :: new ( mask. clone ( ) , None ) ;
85+ let predicate = FilterBuilder :: new ( & BooleanArray :: new ( mask. clone ( ) , None ) )
86+ . optimize ( )
87+ . build ( ) ;
8588 Ok ( Self {
8689 buffered_batch_idx : self . buffered_batch_idx ,
87- streamed_indices : as_uint64_array ( & compute:: filter (
88- & self . streamed_indices ,
89- & mask,
90- ) ?) ?
90+ streamed_indices : as_uint64_array (
91+ & predicate. filter ( & self . streamed_indices ) ?,
92+ ) ?
9193 . clone ( ) ,
92- buffered_indices : as_uint64_array ( & compute:: filter (
93- & self . buffered_indices ,
94- & mask,
95- ) ?) ?
94+ buffered_indices : as_uint64_array (
95+ & predicate. filter ( & self . buffered_indices ) ?,
96+ ) ?
9697 . clone ( ) ,
9798 filtered : self . filtered ,
9899 } )
@@ -487,12 +488,13 @@ pub(super) struct MaterializingSortMergeJoinStream {
487488 /// streamed row (see [`Self::pair_filtered_run`]), and at freeze for the
488489 /// remaining pairs (see [`Self::freeze_inner_filtered`]). Outer joins keep
489490 /// a rejected pair for the deferred pipeline, which may null-join its row.
491+ /// Only an Inner join filters early, so its streamed side is the left input.
490492 pub early_filtering : bool ,
491- /// The join input whose rows are streamed: the right one for a Right join,
492- /// the left one otherwise. The join filter's column indices name join inputs.
493- pub streamed_side : JoinSide ,
494493 /// The indices of every buffered column, for materializing all of them
495494 pub buffered_columns : Vec < usize > ,
495+ /// The buffered columns that the join filter reads, in the filter's order.
496+ /// Empty unless `early_filtering`.
497+ pub buffered_filter_columns : Vec < usize > ,
496498 /// How many pairs the Inner join's filter has evaluated at freeze so far
497499 /// (see [`Self::filter_first_pays`])
498500 pub freeze_filter_evaluated : usize ,
@@ -754,14 +756,23 @@ impl MaterializingSortMergeJoinStream {
754756 semi/anti/mark joins use BitwiseSortMergeJoinStream"
755757 ) ;
756758 let join_time = join_metrics. join_time ( ) ;
757- let ( streamed_side , buffered_side) = if join_type == JoinType :: Right {
758- ( JoinSide :: Right , JoinSide :: Left )
759+ let buffered_side = if join_type == JoinType :: Right {
760+ JoinSide :: Left
759761 } else {
760- ( JoinSide :: Left , JoinSide :: Right )
762+ JoinSide :: Right
761763 } ;
762764 let deferred_filtering = needs_deferred_filtering ( filter. as_ref ( ) , join_type) ;
763765 let early_filtering = join_type == JoinType :: Inner && filter. is_some ( ) ;
764766 let buffered_columns = ( 0 ..buffered_schema. fields ( ) . len ( ) ) . collect ( ) ;
767+ let buffered_filter_columns = match & filter {
768+ Some ( f) if early_filtering => f
769+ . column_indices ( )
770+ . iter ( )
771+ . filter ( |c| c. side == JoinSide :: Right )
772+ . map ( |c| c. index )
773+ . collect ( ) ,
774+ _ => vec ! [ ] ,
775+ } ;
765776 let filter_schema = if deferred_filtering && let Some ( f) = & filter {
766777 let mut fields = Vec :: with_capacity ( f. schema ( ) . fields ( ) . len ( ) ) ;
767778 for ( column_index, field) in
@@ -798,8 +809,8 @@ impl MaterializingSortMergeJoinStream {
798809 deferred_filtering,
799810 filter_schema,
800811 early_filtering,
801- streamed_side,
802812 buffered_columns,
813+ buffered_filter_columns,
803814 freeze_filter_evaluated : 0 ,
804815 freeze_filter_passed : 0 ,
805816 filter,
@@ -1016,20 +1027,20 @@ impl MaterializingSortMergeJoinStream {
10161027 return Ok ( None ) ;
10171028 } ;
10181029 let streamed = & self . streamed_batch . batch ;
1019- let streamed_idx = self . streamed_batch . idx ;
1030+ let streamed_idx = UInt64Array :: from_value ( self . streamed_batch . idx as u64 , len ) ;
10201031 let columns = filter
10211032 . column_indices ( )
10221033 . iter ( )
10231034 . map ( |column_index| match column_index. side {
1024- JoinSide :: None => internal_err ! ( "Unexpected JoinSide::None in filter" ) ,
1025- side if side == self . streamed_side => ScalarValue :: try_from_array (
1035+ JoinSide :: Left => Ok ( compute:: take (
10261036 streamed. column ( column_index. index ) ,
1027- streamed_idx,
1028- ) ?
1029- . to_array_of_size ( len ) ,
1030- _ => Ok ( buffered
1037+ & streamed_idx,
1038+ None ,
1039+ ) ? ) ,
1040+ JoinSide :: Right => Ok ( buffered
10311041 . column ( column_index. index )
10321042 . slice ( buffered_start, len) ) ,
1043+ JoinSide :: None => internal_err ! ( "Unexpected JoinSide::None in filter" ) ,
10331044 } )
10341045 . collect :: < Result < Vec < _ > > > ( ) ?;
10351046 let passed = evaluate_join_filter ( filter, filter. schema ( ) , columns, len) ?;
@@ -1913,9 +1924,8 @@ impl MaterializingSortMergeJoinStream {
19131924 let left_columns =
19141925 materialize_left_columns ( & self . streamed_batch . batch , & combined_left_indices) ?;
19151926
1916- let chunk_refs: Vec < & MatchedChunk > = matched_chunks. iter ( ) . collect ( ) ;
19171927 let right_columns = self . materialize_right_columns (
1918- & chunk_refs ,
1928+ matched_chunks ,
19191929 total_matched_rows,
19201930 & self . buffered_columns ,
19211931 ) ?;
@@ -1943,25 +1953,10 @@ impl MaterializingSortMergeJoinStream {
19431953 if let Some ( f) = & self . filter {
19441954 debug_assert ! ( self . deferred_filtering) ;
19451955 let schema = self . filter_schema . as_ref ( ) . unwrap_or_else ( || f. schema ( ) ) ;
1946- let filter_batch = RecordBatch :: try_new_with_options (
1947- Arc :: clone ( schema) ,
1948- filter_columns,
1949- & RecordBatchOptions :: new ( ) . with_row_count ( Some ( total_matched_rows) ) ,
1950- ) ?;
1951- let filter_result = f
1952- . expression ( )
1953- . evaluate ( & filter_batch) ?
1954- . into_array ( filter_batch. num_rows ( ) ) ?;
1955-
1956- let filter_result_mask = as_boolean_array ( & filter_result) ?;
1957-
1958- // Convert NULL filter results to false — NULL means "not satisfied"
1959- // per SQL semantics, same as Left/Right outer joins.
1960- let mask = if filter_result_mask. null_count ( ) > 0 {
1961- compute:: prep_null_mask_filter ( filter_result_mask)
1962- } else {
1963- filter_result_mask. clone ( )
1964- } ;
1956+ let mask = BooleanArray :: new (
1957+ evaluate_join_filter ( f, schema, filter_columns, total_matched_rows) ?,
1958+ None ,
1959+ ) ;
19651960
19661961 self . joined_record_batches . push_batch_with_filter_metadata (
19671962 output_batch,
@@ -2048,46 +2043,40 @@ impl MaterializingSortMergeJoinStream {
20482043 let num_rows = unfiltered. iter ( ) . map ( |c| c. len ( ) ) . sum ( ) ;
20492044 let streamed_indices =
20502045 concat_indices ( unfiltered. iter ( ) . map ( |c| & c. streamed_indices ) ) ?;
2051- let buffered_filter_columns: Vec < usize > = filter
2052- . column_indices ( )
2053- . iter ( )
2054- . filter ( |c| c. side != self . streamed_side && c. side != JoinSide :: None )
2055- . map ( |c| c. index )
2056- . collect ( ) ;
20572046 let mut buffered_arrays = self
20582047 . materialize_right_columns (
20592048 & unfiltered,
20602049 num_rows,
2061- & buffered_filter_columns,
2050+ & self . buffered_filter_columns ,
20622051 ) ?
20632052 . into_iter ( ) ;
20642053 let columns = filter
20652054 . column_indices ( )
20662055 . iter ( )
20672056 . map ( |column_index| match column_index. side {
2068- JoinSide :: None => {
2069- internal_err ! ( "Unexpected JoinSide::None in filter" )
2070- }
2071- side if side == self . streamed_side => take_column (
2057+ JoinSide :: Left => take_column (
20722058 self . streamed_batch . batch . column ( column_index. index ) ,
20732059 & streamed_indices,
20742060 ) ,
2075- _ => buffered_arrays. next ( ) . ok_or_else ( || {
2076- DataFusionError :: Internal (
2077- "missing buffered filter column" . to_string ( ) ,
2078- )
2061+ JoinSide :: Right => buffered_arrays. next ( ) . ok_or_else ( || {
2062+ internal_datafusion_err ! ( "missing buffered filter column" )
20792063 } ) ,
2064+ JoinSide :: None => {
2065+ internal_err ! ( "Unexpected JoinSide::None in filter" )
2066+ }
20802067 } )
20812068 . collect :: < Result < Vec < _ > > > ( ) ?;
2082- let passed =
2083- evaluate_join_filter ( filter, filter. schema ( ) , columns, num_rows) ?;
20842069 self . freeze_filter_evaluated += num_rows;
2085- self . freeze_filter_passed += passed. count_set_bits ( ) ;
2086- Some ( passed)
2070+ Some ( evaluate_join_filter (
2071+ filter,
2072+ filter. schema ( ) ,
2073+ columns,
2074+ num_rows,
2075+ ) ?)
20872076 } ;
20882077
20892078 // Keep the pairs that passed, in order.
2090- let mut kept: Vec < MatchedChunk > = Vec :: with_capacity ( matched_chunks. len ( ) ) ;
2079+ let mut kept: Vec < Cow < MatchedChunk > > = Vec :: with_capacity ( matched_chunks. len ( ) ) ;
20912080 let mut kept_rows = 0 ;
20922081 let mut offset = 0 ;
20932082 for chunk in matched_chunks {
@@ -2098,14 +2087,15 @@ impl MaterializingSortMergeJoinStream {
20982087 offset += len;
20992088 let count = mask. count_set_bits ( ) ;
21002089 if count == len {
2101- kept. push ( chunk . clone ( ) ) ;
2090+ kept. push ( Cow :: Borrowed ( chunk ) ) ;
21022091 } else if count > 0 {
2103- kept. push ( chunk. filter ( & mask) ?) ;
2092+ kept. push ( Cow :: Owned ( chunk. filter ( & mask) ?) ) ;
21042093 }
2094+ self . freeze_filter_passed += count;
21052095 kept_rows += count;
21062096 }
21072097 _ => {
2108- kept. push ( chunk . clone ( ) ) ;
2098+ kept. push ( Cow :: Borrowed ( chunk ) ) ;
21092099 kept_rows += len;
21102100 }
21112101 }
@@ -2117,12 +2107,8 @@ impl MaterializingSortMergeJoinStream {
21172107 let streamed_indices = concat_indices ( kept. iter ( ) . map ( |c| & c. streamed_indices ) ) ?;
21182108 let streamed_columns =
21192109 materialize_left_columns ( & self . streamed_batch . batch , & streamed_indices) ?;
2120- let kept_refs: Vec < & MatchedChunk > = kept. iter ( ) . collect ( ) ;
2121- let buffered_columns = self . materialize_right_columns (
2122- & kept_refs,
2123- kept_rows,
2124- & self . buffered_columns ,
2125- ) ?;
2110+ let buffered_columns =
2111+ self . materialize_right_columns ( & kept, kept_rows, & self . buffered_columns ) ?;
21262112 let output_batch = RecordBatch :: try_new (
21272113 Arc :: clone ( & self . schema ) ,
21282114 [ streamed_columns, buffered_columns] . concat ( ) ,
@@ -2144,9 +2130,8 @@ impl MaterializingSortMergeJoinStream {
21442130 concat_indices ( matched_chunks. iter ( ) . map ( |c| & c. streamed_indices ) ) ?;
21452131 let streamed_columns =
21462132 materialize_left_columns ( & self . streamed_batch . batch , & streamed_indices) ?;
2147- let chunk_refs: Vec < & MatchedChunk > = matched_chunks. iter ( ) . collect ( ) ;
21482133 let buffered_columns = self . materialize_right_columns (
2149- & chunk_refs ,
2134+ matched_chunks ,
21502135 total_matched_rows,
21512136 & self . buffered_columns ,
21522137 ) ?;
@@ -2209,20 +2194,23 @@ impl MaterializingSortMergeJoinStream {
22092194 /// for a single fetch. When multiple batches are involved, `interleave`
22102195 /// gathers columns across sources. A null-row sentinel at source index 0
22112196 /// handles null right indices (unmatched streamed rows).
2212- fn materialize_right_columns (
2197+ fn materialize_right_columns < C : Borrow < MatchedChunk > > (
22132198 & self ,
2214- matched_chunks : & [ & MatchedChunk ] ,
2199+ matched_chunks : & [ C ] ,
22152200 total_matched_rows : usize ,
22162201 columns : & [ usize ] ,
22172202 ) -> Result < Vec < ArrayRef > > {
2218- let first_batch_idx = matched_chunks[ 0 ] . buffered_batch_idx ;
2219- let single_source = matched_chunks
2220- . iter ( )
2221- . all ( |c| c. buffered_batch_idx == first_batch_idx) ;
2203+ let chunks = || {
2204+ matched_chunks
2205+ . iter ( )
2206+ . map ( |c| -> & MatchedChunk { c. borrow ( ) } )
2207+ } ;
2208+ let first_batch_idx = matched_chunks[ 0 ] . borrow ( ) . buffered_batch_idx ;
2209+ let single_source = chunks ( ) . all ( |c| c. buffered_batch_idx == first_batch_idx) ;
22222210
22232211 if single_source {
22242212 let combined_right_indices =
2225- concat_indices ( matched_chunks . iter ( ) . map ( |c| & c. buffered_indices ) ) ?;
2213+ concat_indices ( chunks ( ) . map ( |c| & c. buffered_indices ) ) ?;
22262214
22272215 return fetch_right_columns_by_idxs (
22282216 & self . buffered_data ,
@@ -2239,9 +2227,7 @@ impl MaterializingSortMergeJoinStream {
22392227 // `interleave` walks a null buffer for *every* output row as soon as
22402228 // any input is nullable, so an always-present sentinel would tax the
22412229 // common all-matched case.
2242- let needs_null_sentinel = matched_chunks
2243- . iter ( )
2244- . any ( |c| c. buffered_indices . null_count ( ) > 0 ) ;
2230+ let needs_null_sentinel = chunks ( ) . any ( |c| c. buffered_indices . null_count ( ) > 0 ) ;
22452231 let source_offset = usize:: from ( needs_null_sentinel) ;
22462232
22472233 // Map each distinct `buffered_batch_idx` to a contiguous source
@@ -2296,8 +2282,7 @@ impl MaterializingSortMergeJoinStream {
22962282 // (`source_data` is gathered from it), so the table is the only
22972283 // added state, and it is transient: sized to the span this freeze
22982284 // touches rather than held across freezes.
2299- let ( min_batch_idx, max_batch_idx) = matched_chunks
2300- . iter ( )
2285+ let ( min_batch_idx, max_batch_idx) = chunks ( )
23012286 . fold ( ( usize:: MAX , 0usize ) , |( lo, hi) , c| {
23022287 ( lo. min ( c. buffered_batch_idx ) , hi. max ( c. buffered_batch_idx ) )
23032288 } ) ;
@@ -2314,7 +2299,7 @@ impl MaterializingSortMergeJoinStream {
23142299 Vec :: with_capacity ( matched_chunks. len ( ) . min ( source_of_batch. len ( ) ) ) ;
23152300 let mut interleave_indices: Vec < ( usize , usize ) > =
23162301 Vec :: with_capacity ( total_matched_rows) ;
2317- for chunk in matched_chunks {
2302+ for chunk in chunks ( ) {
23182303 let batch_idx = chunk. buffered_batch_idx ;
23192304 let right = & chunk. buffered_indices ;
23202305 let slot = & mut source_of_batch[ batch_idx - min_batch_idx] ;
@@ -2570,17 +2555,13 @@ fn fetch_right_columns_from_batch_by_idxs(
25702555) -> Result < Vec < ArrayRef > > {
25712556 match & buffered_batch. batch {
25722557 BufferedBatchState :: InMemory ( batch) => {
2573- let arrays: Vec < ArrayRef > = columns
2574- . iter ( )
2575- . map ( |& c| Arc :: clone ( batch. column ( c) ) )
2576- . collect ( ) ;
2558+ let arrays = columns. iter ( ) . map ( |& c| batch. column ( c) ) ;
25772559 if let Some ( range) = is_contiguous_range ( buffered_indices) {
2578- Ok ( arrays
2579- . iter ( )
2580- . map ( |a| a. slice ( range. start , range. len ( ) ) )
2581- . collect ( ) )
2560+ Ok ( arrays. map ( |a| a. slice ( range. start , range. len ( ) ) ) . collect ( ) )
25822561 } else {
2583- Ok ( take_arrays ( & arrays, buffered_indices, None ) ?)
2562+ arrays
2563+ . map ( |a| Ok ( compute:: take ( a. as_ref ( ) , buffered_indices, None ) ?) )
2564+ . collect ( )
25842565 }
25852566 }
25862567 BufferedBatchState :: Spilled ( _) => {
@@ -2593,7 +2574,7 @@ fn fetch_right_columns_from_batch_by_idxs(
25932574
25942575/// Concatenates the index arrays of several chunks into one.
25952576fn concat_indices < ' a > (
2596- indices : impl ExactSizeIterator < Item = & ' a UInt64Array > ,
2577+ indices : impl Iterator < Item = & ' a UInt64Array > ,
25972578) -> Result < UInt64Array > {
25982579 let arrays: Vec < & dyn Array > = indices. map ( |a| a as & dyn Array ) . collect ( ) ;
25992580 match arrays. as_slice ( ) {
0 commit comments