@@ -58,7 +58,7 @@ use crate::{
5858 metrics:: { ExecutionPlanMetricsSet , MetricsSet } ,
5959} ;
6060
61- use arrow:: array:: { Array , ArrayRef , BooleanBufferBuilder } ;
61+ use arrow:: array:: { Array , ArrayRef , AsArray , BooleanBufferBuilder } ;
6262use arrow:: compute:: concat_batches;
6363use arrow:: datatypes:: SchemaRef ;
6464use arrow:: record_batch:: RecordBatch ;
@@ -680,8 +680,9 @@ impl From<&HashJoinExec> for HashJoinExecBuilder {
680680/// hash table is updated by iterating the build-side rows in reverse order, which keeps rows
681681/// with smaller indices "on the top" of hash table. The build-side batches are first
682682/// concatenated in their input order. The hash table is then filled from slices of the
683- /// concatenated batch, at most as long as the largest build-side batch, starting from the
684- /// last slice. Each slice is inserted with the offset of its first row in the concatenated batch.
683+ /// concatenated batch, at most as long as the largest build-side batch (or the longest
684+ /// key dictionary, when that is longer), starting from the last slice. Each slice is
685+ /// inserted with the offset of its first row in the concatenated batch.
685686///
686687/// Example of build phase for 3 record batches, filled from slices of 3 rows:
687688///
@@ -3222,20 +3223,29 @@ fn build_in_memory(
32223223 // Arc is used instead of Box to allow sharing with SharedBuildAccumulator for hash map pushdown
32233224 let mut hashmap = new_join_hashmap ( num_rows, & mut reservation, metrics) ?;
32243225
3226+ // Every slice shares the whole dictionary of a dictionary key, which
3227+ // `create_hashes` hashes on each call: a slice at least as long as the
3228+ // dictionary keeps that cost linear in the build rows.
3229+ let chunk_rows = left_values
3230+ . iter ( )
3231+ . filter_map ( |values| values. as_any_dictionary_opt ( ) )
3232+ . map ( |dict| dict. values ( ) . len ( ) )
3233+ . fold ( max_batch_rows, usize:: max) ;
3234+
32253235 let scratch_reservation = reservation. new_empty ( ) ;
32263236 if prepared {
32273237 scratch_reservation. try_grow ( prepared:: prepared_scratch_bytes (
3228- max_batch_rows ,
3238+ chunk_rows ,
32293239 on_left. len ( ) ,
32303240 null_equality,
32313241 ) ?) ?;
32323242 }
32333243 // The maximum is known: avoid geometric growth and its excess capacity.
3234- let mut hashes_buffer = Vec :: with_capacity ( max_batch_rows ) ;
3235- // `max_batch_rows ` is 0 when the build side is empty
3236- let chunk_rows = max_batch_rows . max ( 1 ) ;
3244+ let mut hashes_buffer = Vec :: with_capacity ( chunk_rows . min ( num_rows ) ) ;
3245+ // `chunk_rows ` is 0 when the build side is empty
3246+ let chunk_rows = chunk_rows . max ( 1 ) ;
32373247
3238- // Update the hashmap from slices of at most `max_batch_rows ` rows,
3248+ // Update the hashmap from slices of at most `chunk_rows ` rows,
32393249 // starting from the last one, so rows with smaller indices end up on
32403250 // top of the chains. Each slice is indexed at its offset in `batch`.
32413251 for offset in ( 0 ..num_rows) . step_by ( chunk_rows) . rev ( ) {
@@ -5143,6 +5153,86 @@ mod tests {
51435153 Ok ( ( ) )
51445154 }
51455155
5156+ /// Build batches sharing one key dictionary that is longer than each batch
5157+ /// fill the hash map from slices longer than the batches, which must join
5158+ /// as if the build side were a single batch.
5159+ #[ tokio:: test]
5160+ async fn join_keeps_build_order_with_dictionary_keys ( ) -> Result < ( ) > {
5161+ let dict_type =
5162+ DataType :: Dictionary ( Box :: new ( DataType :: Int32 ) , Box :: new ( DataType :: Utf8 ) ) ;
5163+ let schema = Arc :: new ( Schema :: new ( vec ! [
5164+ Field :: new( "a1" , DataType :: Int32 , false ) ,
5165+ Field :: new( "b1" , dict_type. clone( ) , true ) ,
5166+ ] ) ) ;
5167+ // Concatenation keeps a dictionary shared by every batch as is, so the
5168+ // 12 build rows are filled from slices of 5 rows: [0, 5), [5, 10) and
5169+ // [10, 12), each crossing the 2-row batch boundaries.
5170+ let values: ArrayRef = Arc :: new ( StringArray :: from ( vec ! [ "x" , "y" , "z" , "w" , "v" ] ) ) ;
5171+ let batch = |a : Vec < i32 > , keys : Vec < Option < i32 > > | -> Result < RecordBatch > {
5172+ let b1 = DictionaryArray :: < Int32Type > :: try_new (
5173+ Int32Array :: from ( keys) ,
5174+ Arc :: clone ( & values) ,
5175+ ) ?;
5176+ Ok ( RecordBatch :: try_new (
5177+ Arc :: clone ( & schema) ,
5178+ vec ! [ Arc :: new( Int32Array :: from( a) ) , Arc :: new( b1) ] ,
5179+ ) ?)
5180+ } ;
5181+ let batches = vec ! [
5182+ batch( vec![ 1 , 2 ] , vec![ Some ( 0 ) , None ] ) ?,
5183+ batch( vec![ 3 , 4 ] , vec![ Some ( 1 ) , Some ( 2 ) ] ) ?,
5184+ batch( vec![ 5 , 6 ] , vec![ Some ( 0 ) , Some ( 1 ) ] ) ?,
5185+ batch( vec![ 7 , 8 ] , vec![ Some ( 3 ) , Some ( 0 ) ] ) ?,
5186+ batch( vec![ 9 , 10 ] , vec![ None , Some ( 1 ) ] ) ?,
5187+ batch( vec![ 11 , 12 ] , vec![ Some ( 0 ) , Some ( 1 ) ] ) ?,
5188+ ] ;
5189+ let right_schema = Arc :: new ( Schema :: new ( vec ! [
5190+ Field :: new( "a2" , DataType :: Int32 , false ) ,
5191+ Field :: new( "b2" , dict_type, true ) ,
5192+ ] ) ) ;
5193+ let right = RecordBatch :: try_new (
5194+ Arc :: clone ( & right_schema) ,
5195+ vec ! [
5196+ Arc :: new( Int32Array :: from( vec![ 10 , 30 ] ) ) ,
5197+ Arc :: new( DictionaryArray :: <Int32Type >:: try_new(
5198+ Int32Array :: from( vec![ 0 , 1 ] ) ,
5199+ Arc :: new( StringArray :: from( vec![ "x" , "y" ] ) ) ,
5200+ ) ?) ,
5201+ ] ,
5202+ ) ?;
5203+ let on = vec ! [ (
5204+ Arc :: new( Column :: new_with_schema( "b1" , & schema) ?) as _,
5205+ Arc :: new( Column :: new_with_schema( "b2" , & right_schema) ?) as _,
5206+ ) ] ;
5207+ let left = TestMemoryExec :: try_new_exec ( & [ batches] , Arc :: clone ( & schema) , None ) ?;
5208+ let right = TestMemoryExec :: try_new_exec ( & [ vec ! [ right] ] , right_schema, None ) ?;
5209+ let ( _, output, _) = join_collect (
5210+ left,
5211+ right,
5212+ on,
5213+ & JoinType :: Inner ,
5214+ NullEquality :: NullEqualsNothing ,
5215+ prepare_task_ctx ( 8192 , false ) ,
5216+ )
5217+ . await ?;
5218+
5219+ assert_snapshot ! ( batches_to_string( & output) , @r"
5220+ +----+----+----+----+
5221+ | a1 | b1 | a2 | b2 |
5222+ +----+----+----+----+
5223+ | 1 | x | 10 | x |
5224+ | 5 | x | 10 | x |
5225+ | 8 | x | 10 | x |
5226+ | 11 | x | 10 | x |
5227+ | 3 | y | 30 | y |
5228+ | 6 | y | 30 | y |
5229+ | 10 | y | 30 | y |
5230+ | 12 | y | 30 | y |
5231+ +----+----+----+----+
5232+ " ) ;
5233+ Ok ( ( ) )
5234+ }
5235+
51465236 /// A build side without any batch has no rows to fill the hash map from.
51475237 #[ tokio:: test]
51485238 async fn join_build_side_without_batches ( ) -> Result < ( ) > {
0 commit comments