@@ -65,7 +65,7 @@ use crate::{
6565 metrics:: { ExecutionPlanMetricsSet , MetricsSet } ,
6666} ;
6767
68- use arrow:: array:: { Array , ArrayRef , BooleanBufferBuilder , new_null_array} ;
68+ use arrow:: array:: { Array , ArrayRef , BooleanBufferBuilder , UInt64Array , new_null_array} ;
6969use arrow:: datatypes:: SchemaRef ;
7070use arrow:: record_batch:: RecordBatch ;
7171use arrow:: util:: bit_util;
@@ -177,43 +177,50 @@ fn try_create_array_map(
177177 let mem_size = ArrayMap :: estimate_memory_size ( min_val, max_val, num_row) ;
178178 reservation. try_grow ( mem_size) ?;
179179
180- // Evaluate key expressions per-batch and concatenate only key columns
181- let left_values = concat_key_value_arrays ( on_left, batches. iter ( ) ) ?;
180+ // Evaluate key expressions per-batch and concatenate for ArrayMap construction
181+ let per_batch_keys: Vec < Vec < ArrayRef > > = batches
182+ . iter ( )
183+ . map ( |batch| evaluate_expressions_to_arrays ( on_left, batch) )
184+ . collect :: < Result < Vec < _ > > > ( ) ?;
185+ let left_values: Vec < ArrayRef > = if per_batch_keys. is_empty ( ) || on_left. is_empty ( ) {
186+ on_left
187+ . iter ( )
188+ . map ( |_| new_null_array ( & DataType :: Null , 0 ) )
189+ . collect ( )
190+ } else {
191+ let num_keys = on_left. len ( ) ;
192+ ( 0 ..num_keys)
193+ . map ( |key_idx| {
194+ let arrays: Vec < & dyn Array > = per_batch_keys
195+ . iter ( )
196+ . map ( |keys| keys[ key_idx] . as_ref ( ) )
197+ . collect ( ) ;
198+ Ok ( arrow:: compute:: concat ( & arrays) ?)
199+ } )
200+ . collect :: < Result < Vec < _ > > > ( ) ?
201+ } ;
182202
183203 let array_map = ArrayMap :: try_new ( & left_values[ 0 ] , min_val, max_val) ?;
184204
185205 Ok ( Some ( ( array_map, left_values) ) )
186206}
187207
188- /// Evaluate key expressions per-batch and concatenate only the resulting key
189- /// column arrays. This avoids `concat_batches` on the full data (which would
190- /// duplicate all columns in memory) while still providing contiguous key arrays
191- /// for `equal_rows_arr`.
192- fn concat_key_value_arrays < ' a > (
193- on : & [ PhysicalExprRef ] ,
194- batches : impl Iterator < Item = & ' a RecordBatch > ,
195- ) -> Result < Vec < ArrayRef > > {
196- let batches: Vec < & RecordBatch > = batches. collect ( ) ;
197- if batches. is_empty ( ) || on. is_empty ( ) {
198- return Ok ( on
199- . iter ( )
200- . map ( |_| new_null_array ( & DataType :: Null , 0 ) )
201- . collect ( ) ) ;
202- }
203- // Evaluate key expressions for each batch
204- let per_batch_keys: Vec < Vec < ArrayRef > > = batches
208+ /// Convert flat indices (used in the visited bitmap) to packed composite indices
209+ /// `(batch_idx << 32) | row_idx` used by `build_batch_from_indices`.
210+ pub ( super ) fn flat_to_packed_indices (
211+ flat_indices : & UInt64Array ,
212+ batch_offsets : & [ usize ] ,
213+ ) -> UInt64Array {
214+ flat_indices
215+ . values ( )
205216 . iter ( )
206- . map ( |batch| evaluate_expressions_to_arrays ( on, batch) )
207- . collect :: < Result < Vec < _ > > > ( ) ?;
208- // Transpose and concatenate: for each key column, concat across all batches
209- let num_keys = on. len ( ) ;
210- ( 0 ..num_keys)
211- . map ( |key_idx| {
212- let arrays: Vec < & dyn Array > = per_batch_keys
213- . iter ( )
214- . map ( |keys| keys[ key_idx] . as_ref ( ) )
215- . collect ( ) ;
216- Ok ( arrow:: compute:: concat ( & arrays) ?)
217+ . map ( |& flat_val| {
218+ let flat = flat_val as usize ;
219+ let batch_idx = batch_offsets
220+ . partition_point ( |& o| o <= flat)
221+ . saturating_sub ( 1 ) ;
222+ let row_idx = flat - batch_offsets[ batch_idx] ;
223+ ( ( batch_idx as u64 ) << 32 ) | ( row_idx as u64 )
217224 } )
218225 . collect ( )
219226}
@@ -231,8 +238,9 @@ pub(super) struct JoinLeftData {
231238 /// batch_offsets[i] is the starting flat index for batches[i].
232239 /// Has length batches.len() + 1 (last element is total row count).
233240 batch_offsets : Vec < usize > ,
234- /// The build side on expressions values (concatenated key columns only)
235- values : Vec < ArrayRef > ,
241+ /// The build side key expression values, per batch.
242+ /// values_per_batch[batch_idx][key_idx] is the key column array for that batch.
243+ values_per_batch : Vec < Vec < ArrayRef > > ,
236244 /// Shared bitmap builder for visited left indices
237245 visited_indices_bitmap : SharedBitmapBuilder ,
238246 /// Counter of running probe-threads, potentially
@@ -283,9 +291,9 @@ impl JoinLeftData {
283291 & self . batch_offsets
284292 }
285293
286- /// returns a reference to the build side expressions values
287- pub ( super ) fn values ( & self ) -> & [ ArrayRef ] {
288- & self . values
294+ /// returns a reference to the build side key expressions values, per batch
295+ pub ( super ) fn values_per_batch ( & self ) -> & [ Vec < ArrayRef > ] {
296+ & self . values_per_batch
289297 }
290298
291299 /// returns a reference to the visited indices bitmap
@@ -2018,8 +2026,8 @@ async fn collect_left_input(
20182026 _ => None ,
20192027 } ;
20202028
2021- let ( join_hash_map, left_values , should_reverse_batches ) =
2022- if let Some ( ( array_map , left_value ) ) = try_create_array_map (
2029+ let ( join_hash_map, should_reverse_batches ) = if let Some ( ( array_map , _left_value ) ) =
2030+ try_create_array_map (
20232031 & bounds,
20242032 & schema,
20252033 & batches,
@@ -2029,61 +2037,57 @@ async fn collect_left_input(
20292037 config. execution . perfect_hash_join_min_key_density ,
20302038 null_equality,
20312039 ) ? {
2032- array_map_created_count. add ( 1 ) ;
2033- metrics. build_mem_used . add ( array_map. size ( ) ) ;
2040+ array_map_created_count. add ( 1 ) ;
2041+ metrics. build_mem_used . add ( array_map. size ( ) ) ;
20342042
2035- ( Map :: ArrayMap ( array_map) , left_value, false )
2043+ ( Map :: ArrayMap ( array_map) , false )
2044+ } else {
2045+ // Estimation of memory size, required for hashtable, prior to allocation.
2046+ // Final result can be verified using `RawTable.allocation_info()`
2047+ let fixed_size_u32 = size_of :: < JoinHashMapU32 > ( ) ;
2048+ let fixed_size_u64 = size_of :: < JoinHashMapU64 > ( ) ;
2049+
2050+ // Use `u32` indices for the JoinHashMap when num_rows ≤ u32::MAX, otherwise use the
2051+ // `u64` indice variant
2052+ // Arc is used instead of Box to allow sharing with SharedBuildAccumulator for hash map pushdown
2053+ let mut hashmap: Box < dyn JoinHashMapType > = if num_rows > u32:: MAX as usize {
2054+ let estimated_hashtable_size =
2055+ estimate_memory_size :: < ( u64 , u64 ) > ( num_rows, fixed_size_u64) ?;
2056+ reservation. try_grow ( estimated_hashtable_size) ?;
2057+ metrics. build_mem_used . add ( estimated_hashtable_size) ;
2058+ Box :: new ( JoinHashMapU64 :: with_capacity ( num_rows) )
20362059 } else {
2037- // Estimation of memory size, required for hashtable, prior to allocation.
2038- // Final result can be verified using `RawTable.allocation_info()`
2039- let fixed_size_u32 = size_of :: < JoinHashMapU32 > ( ) ;
2040- let fixed_size_u64 = size_of :: < JoinHashMapU64 > ( ) ;
2041-
2042- // Use `u32` indices for the JoinHashMap when num_rows ≤ u32::MAX, otherwise use the
2043- // `u64` indice variant
2044- // Arc is used instead of Box to allow sharing with SharedBuildAccumulator for hash map pushdown
2045- let mut hashmap: Box < dyn JoinHashMapType > = if num_rows > u32:: MAX as usize {
2046- let estimated_hashtable_size =
2047- estimate_memory_size :: < ( u64 , u64 ) > ( num_rows, fixed_size_u64) ?;
2048- reservation. try_grow ( estimated_hashtable_size) ?;
2049- metrics. build_mem_used . add ( estimated_hashtable_size) ;
2050- Box :: new ( JoinHashMapU64 :: with_capacity ( num_rows) )
2051- } else {
2052- let estimated_hashtable_size =
2053- estimate_memory_size :: < ( u32 , u64 ) > ( num_rows, fixed_size_u32) ?;
2054- reservation. try_grow ( estimated_hashtable_size) ?;
2055- metrics. build_mem_used . add ( estimated_hashtable_size) ;
2056- Box :: new ( JoinHashMapU32 :: with_capacity ( num_rows) )
2057- } ;
2058-
2059- let mut hashes_buffer = Vec :: new ( ) ;
2060- let mut offset = 0 ;
2061-
2062- let batches_iter = batches. iter ( ) . rev ( ) ;
2063-
2064- // Updating hashmap starting from the last batch
2065- for batch in batches_iter. clone ( ) {
2066- hashes_buffer. clear ( ) ;
2067- hashes_buffer. resize ( batch. num_rows ( ) , 0 ) ;
2068- update_hash (
2069- & on_left,
2070- batch,
2071- & mut * hashmap,
2072- offset,
2073- & random_state,
2074- & mut hashes_buffer,
2075- 0 ,
2076- true ,
2077- ) ?;
2078- offset += batch. num_rows ( ) ;
2079- }
2060+ let estimated_hashtable_size =
2061+ estimate_memory_size :: < ( u32 , u64 ) > ( num_rows, fixed_size_u32) ?;
2062+ reservation. try_grow ( estimated_hashtable_size) ?;
2063+ metrics. build_mem_used . add ( estimated_hashtable_size) ;
2064+ Box :: new ( JoinHashMapU32 :: with_capacity ( num_rows) )
2065+ } ;
20802066
2081- // Evaluate key expressions per-batch and concatenate only the key columns
2082- // (avoids concat_batches on the full data, saving memory)
2083- let left_values = concat_key_value_arrays ( & on_left, batches_iter. clone ( ) ) ?;
2067+ let mut hashes_buffer = Vec :: new ( ) ;
2068+ let mut offset = 0 ;
2069+
2070+ let batches_iter = batches. iter ( ) . rev ( ) ;
2071+
2072+ // Updating hashmap starting from the last batch
2073+ for batch in batches_iter. clone ( ) {
2074+ hashes_buffer. clear ( ) ;
2075+ hashes_buffer. resize ( batch. num_rows ( ) , 0 ) ;
2076+ update_hash (
2077+ & on_left,
2078+ batch,
2079+ & mut * hashmap,
2080+ offset,
2081+ & random_state,
2082+ & mut hashes_buffer,
2083+ 0 ,
2084+ true ,
2085+ ) ?;
2086+ offset += batch. num_rows ( ) ;
2087+ }
20842088
2085- ( Map :: HashMap ( hashmap) , left_values , true )
2086- } ;
2089+ ( Map :: HashMap ( hashmap) , true )
2090+ } ;
20872091
20882092 // For HashMap: reverse the batches to match the hash map's flat index ordering.
20892093 // The hash map is built iterating in reverse (last batch first), so flat index 0
@@ -2096,7 +2100,27 @@ async fn collect_left_input(
20962100 batches. reverse ( ) ;
20972101 }
20982102
2099- // Compute batch_offsets (prefix sum of batch sizes) for flat-to-(batch,row) conversion
2103+ // Evaluate key expressions per-batch (no concatenation needed for equal_rows_arr)
2104+ let values_per_batch: Vec < Vec < ArrayRef > > = if batches. is_empty ( ) {
2105+ let empty_batch = RecordBatch :: new_empty ( Arc :: clone ( & schema) ) ;
2106+ let empty_keys = on_left
2107+ . iter ( )
2108+ . map ( |c| c. evaluate ( & empty_batch) ?. into_array ( 0 ) )
2109+ . collect :: < Result < Vec < _ > > > ( ) ?;
2110+ vec ! [ empty_keys]
2111+ } else {
2112+ batches
2113+ . iter ( )
2114+ . map ( |batch| {
2115+ on_left
2116+ . iter ( )
2117+ . map ( |c| c. evaluate ( batch) ?. into_array ( batch. num_rows ( ) ) )
2118+ . collect :: < Result < Vec < _ > > > ( )
2119+ } )
2120+ . collect :: < Result < Vec < _ > > > ( ) ?
2121+ } ;
2122+
2123+ // Compute batch_offsets (prefix sum of batch sizes) for flat-to-packed index conversion
21002124 let batch_offsets = {
21012125 let mut offsets = Vec :: with_capacity ( batches. len ( ) + 1 ) ;
21022126 offsets. push ( 0usize ) ;
@@ -2124,23 +2148,38 @@ async fn collect_left_input(
21242148 let membership = if num_rows == 0 {
21252149 PushdownStrategy :: Empty
21262150 } else {
2127- // If the build side is small enough we can use IN list pushdown.
2128- // If it's too big we fall back to pushing down a reference to the hash table.
2129- // See `PushdownStrategy` for more details.
2130- let estimated_size = left_values
2151+ // For membership testing, we need concatenated key columns.
2152+ // Concat from the per-batch values.
2153+ let concat_values: Vec < ArrayRef > =
2154+ if values_per_batch. is_empty ( ) || values_per_batch[ 0 ] . is_empty ( ) {
2155+ vec ! [ ]
2156+ } else {
2157+ let num_keys = values_per_batch[ 0 ] . len ( ) ;
2158+ ( 0 ..num_keys)
2159+ . map ( |key_idx| {
2160+ let arrays: Vec < & dyn Array > = values_per_batch
2161+ . iter ( )
2162+ . map ( |keys| keys[ key_idx] . as_ref ( ) )
2163+ . collect ( ) ;
2164+ Ok ( arrow:: compute:: concat ( & arrays) ?)
2165+ } )
2166+ . collect :: < Result < Vec < _ > > > ( ) ?
2167+ } ;
2168+
2169+ let estimated_size = concat_values
21312170 . iter ( )
21322171 . map ( |arr| arr. get_array_memory_size ( ) )
21332172 . sum :: < usize > ( ) ;
2134- if left_values . is_empty ( )
2135- || left_values [ 0 ] . is_empty ( )
2173+ if concat_values . is_empty ( )
2174+ || concat_values [ 0 ] . is_empty ( )
21362175 || estimated_size > config. optimizer . hash_join_inlist_pushdown_max_size
21372176 || map. num_of_distinct_key ( )
21382177 > config
21392178 . optimizer
21402179 . hash_join_inlist_pushdown_max_distinct_values
21412180 {
21422181 PushdownStrategy :: Map ( Arc :: clone ( & map) )
2143- } else if let Some ( in_list_values) = build_struct_inlist_values ( & left_values ) ? {
2182+ } else if let Some ( in_list_values) = build_struct_inlist_values ( & concat_values ) ? {
21442183 PushdownStrategy :: InList ( in_list_values)
21452184 } else {
21462185 PushdownStrategy :: Map ( Arc :: clone ( & map) )
@@ -2156,7 +2195,7 @@ async fn collect_left_input(
21562195 schema : Arc :: clone ( & schema) ,
21572196 batches,
21582197 batch_offsets,
2159- values : left_values ,
2198+ values_per_batch ,
21602199 visited_indices_bitmap : Mutex :: new ( visited_indices_bitmap) ,
21612200 probe_threads_counter : AtomicUsize :: new ( probe_threads_count) ,
21622201 _reservation : reservation,
@@ -4416,7 +4455,8 @@ mod tests {
44164455 let mut build_indices_buffer = Vec :: new ( ) ;
44174456 let ( l, r, _) = lookup_join_hashmap (
44184457 & join_hash_map,
4419- & [ left_keys_values] ,
4458+ & [ vec ! [ left_keys_values] ] ,
4459+ & [ 0 , left. num_rows ( ) ] ,
44204460 & [ right_keys_values] ,
44214461 NullEquality :: NullEqualsNothing ,
44224462 & hashes_buffer,
@@ -4477,7 +4517,8 @@ mod tests {
44774517 let mut build_indices_buffer = Vec :: new ( ) ;
44784518 let ( l, r, _) = lookup_join_hashmap (
44794519 & join_hash_map,
4480- & [ left_keys_values] ,
4520+ & [ vec ! [ left_keys_values] ] ,
4521+ & [ 0 , left. num_rows ( ) ] ,
44814522 & [ right_keys_values] ,
44824523 NullEquality :: NullEqualsNothing ,
44834524 & hashes_buffer,
0 commit comments