@@ -58,7 +58,7 @@ use crate::{
5858 metrics:: { ExecutionPlanMetricsSet , MetricsSet } ,
5959} ;
6060
61- use arrow:: array:: { Array , ArrayRef , AsArray , BooleanBufferBuilder } ;
61+ use arrow:: array:: { Array , ArrayData , ArrayRef , BooleanBufferBuilder } ;
6262use arrow:: compute:: concat_batches;
6363use arrow:: datatypes:: SchemaRef ;
6464use arrow:: record_batch:: RecordBatch ;
@@ -103,6 +103,30 @@ pub(crate) const HASH_JOIN_SEED: SeededRandomState =
103103
104104const ARRAY_MAP_CREATED_COUNT_METRIC_NAME : & str = "array_map_created_count" ;
105105
106+ /// The length of the longest array under `data` that `create_hashes` hashes
107+ /// in full whatever slice of `data` it gets: everything beneath a dictionary
108+ /// or a list view, at any depth.
109+ fn unsliced_hash_len ( data : & ArrayData ) -> usize {
110+ let own = match data. data_type ( ) {
111+ DataType :: Dictionary ( _, _)
112+ | DataType :: ListView ( _)
113+ | DataType :: LargeListView ( _) => subtree_max_len ( & data. child_data ( ) [ 0 ] ) ,
114+ _ => 0 ,
115+ } ;
116+ data. child_data ( )
117+ . iter ( )
118+ . map ( unsliced_hash_len)
119+ . fold ( own, usize:: max)
120+ }
121+
122+ /// The longest array anywhere in `data`, including `data` itself.
123+ fn subtree_max_len ( data : & ArrayData ) -> usize {
124+ data. child_data ( )
125+ . iter ( )
126+ . map ( subtree_max_len)
127+ . fold ( data. len ( ) , usize:: max)
128+ }
129+
106130/// Decides whether the build side should be joined with an [`ArrayMap`]
107131/// (perfect hash join), returning the `(min, max)` key range to build it over.
108132///
@@ -681,8 +705,9 @@ impl From<&HashJoinExec> for HashJoinExecBuilder {
681705/// with smaller indices "on the top" of hash table. The build-side batches are first
682706/// concatenated in their input order. The hash table is then filled from slices of the
683707/// 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.
708+ /// values under a dictionary or list view in a key, when that is longer), starting
709+ /// from the last slice. Each slice is inserted with the offset of its first row in
710+ /// the concatenated batch.
686711///
687712/// Example of build phase for 3 record batches, filled from slices of 3 rows:
688713///
@@ -3216,14 +3241,15 @@ fn build_in_memory(
32163241 // Arc is used instead of Box to allow sharing with SharedBuildAccumulator for hash map pushdown
32173242 let mut hashmap = new_join_hashmap ( num_rows, & mut reservation, metrics) ?;
32183243
3219- // Every slice shares the whole dictionary of a dictionary key, which
3220- // `create_hashes` hashes on each call: a slice at least as long as the
3221- // dictionary keeps that cost linear in the build rows.
3244+ // Every slice shares everything beneath a dictionary or list view,
3245+ // at any depth of a key, which `create_hashes` hashes on each call: a
3246+ // slice at least as long as the longest of those arrays keeps that
3247+ // cost linear in the build rows. No slice is longer than the build side.
32223248 let chunk_rows = left_values
32233249 . iter ( )
3224- . filter_map ( |values| values. as_any_dictionary_opt ( ) )
3225- . map ( |dict| dict . values ( ) . len ( ) )
3226- . fold ( max_batch_rows , usize :: max ) ;
3250+ . map ( |values| unsliced_hash_len ( & values. to_data ( ) ) )
3251+ . fold ( max_batch_rows , usize :: max )
3252+ . min ( num_rows ) ;
32273253
32283254 let scratch_reservation = reservation. new_empty ( ) ;
32293255 if prepared {
@@ -3234,7 +3260,7 @@ fn build_in_memory(
32343260 ) ?) ?;
32353261 }
32363262 // The maximum is known: avoid geometric growth and its excess capacity.
3237- let mut hashes_buffer = Vec :: with_capacity ( chunk_rows. min ( num_rows ) ) ;
3263+ let mut hashes_buffer = Vec :: with_capacity ( chunk_rows) ;
32383264 // `chunk_rows` is 0 when the build side is empty
32393265 let chunk_rows = chunk_rows. max ( 1 ) ;
32403266
@@ -3478,10 +3504,11 @@ mod tests {
34783504 use crate :: joins:: join_hash_map:: ProbeOffset :: AtRow ;
34793505 use arrow:: array:: {
34803506 Array , ArrayRef , AsArray , BinaryViewArray , Date32Array , DictionaryArray ,
3481- Float32Array , Float64Array , Int32Array , Int64Array , StringArray , StringViewArray ,
3482- StructArray , UInt32Array , UInt64Array ,
3507+ FixedSizeListArray , Float32Array , Float64Array , Int32Array , Int64Array ,
3508+ ListArray , ListViewArray , StringArray , StringViewArray , StructArray , UInt32Array ,
3509+ UInt64Array ,
34833510 } ;
3484- use arrow:: buffer:: NullBuffer ;
3511+ use arrow:: buffer:: { NullBuffer , OffsetBuffer , ScalarBuffer } ;
34853512 use arrow:: datatypes:: { DataType , Field , Float32Type , Float64Type , Int32Type } ;
34863513 use datafusion_common:: hash_utils:: create_hashes;
34873514 use datafusion_common:: stats:: Precision ;
@@ -5146,6 +5173,66 @@ mod tests {
51465173 Ok ( ( ) )
51475174 }
51485175
5176+ /// Only what a slice cannot cut counts, which is everything below a
5177+ /// dictionary or a list view, also below a struct or a list, but not the
5178+ /// child of a plain list or fixed size list.
5179+ #[ test]
5180+ fn unsliced_hash_len_counts_shared_values_at_any_depth ( ) -> Result < ( ) > {
5181+ let dict: ArrayRef = Arc :: new ( DictionaryArray :: < Int32Type > :: try_new (
5182+ Int32Array :: from ( vec ! [ 0 , 1 ] ) ,
5183+ Arc :: new ( StringArray :: from ( vec ! [ "a" , "b" , "c" , "d" , "e" ] ) ) ,
5184+ ) ?) ;
5185+ let in_struct: ArrayRef = Arc :: new ( StructArray :: from ( vec ! [ (
5186+ Arc :: new( Field :: new( "d" , dict. data_type( ) . clone( ) , false ) ) ,
5187+ Arc :: clone( & dict) ,
5188+ ) ] ) ) ;
5189+ let list_view: ArrayRef = Arc :: new ( ListViewArray :: new (
5190+ Arc :: new ( Field :: new_list_field ( DataType :: Int32 , false ) ) ,
5191+ ScalarBuffer :: from ( vec ! [ 0 , 1 ] ) ,
5192+ ScalarBuffer :: from ( vec ! [ 1 , 1 ] ) ,
5193+ Arc :: new ( Int32Array :: from ( vec ! [ 1 , 2 , 3 , 4 ] ) ) ,
5194+ None ,
5195+ ) ) ;
5196+ let list: ArrayRef =
5197+ Arc :: new ( ListArray :: from_iter_primitive :: < Int32Type , _ , _ > ( vec ! [
5198+ Some ( vec![ Some ( 1 ) , Some ( 2 ) , Some ( 3 ) ] ) ,
5199+ Some ( vec![ Some ( 4 ) , Some ( 5 ) , Some ( 6 ) , Some ( 7 ) ] ) ,
5200+ ] ) ) ;
5201+ let fixed_size_list: ArrayRef = Arc :: new ( FixedSizeListArray :: new (
5202+ Arc :: new ( Field :: new_list_field ( DataType :: Int32 , false ) ) ,
5203+ 2 ,
5204+ Arc :: new ( Int32Array :: from ( vec ! [ 1 , 2 , 3 , 4 , 5 , 6 ] ) ) ,
5205+ None ,
5206+ ) ) ;
5207+ let list_of_dict: ArrayRef = Arc :: new ( ListArray :: new (
5208+ Arc :: new ( Field :: new_list_field ( dict. data_type ( ) . clone ( ) , false ) ) ,
5209+ OffsetBuffer :: from_lengths ( [ 1 , 1 ] ) ,
5210+ Arc :: clone ( & dict) ,
5211+ None ,
5212+ ) ) ;
5213+ let dict_of_list: ArrayRef = Arc :: new ( DictionaryArray :: < Int32Type > :: try_new (
5214+ Int32Array :: from ( vec ! [ 0 , 1 ] ) ,
5215+ Arc :: clone ( & list) ,
5216+ ) ?) ;
5217+ for ( array, expected) in [
5218+ ( dict. slice ( 1 , 1 ) , 5 ) ,
5219+ ( in_struct. slice ( 1 , 1 ) , 5 ) ,
5220+ ( list_view. slice ( 0 , 1 ) , 4 ) ,
5221+ ( list. slice ( 0 , 1 ) , 0 ) ,
5222+ ( fixed_size_list. slice ( 1 , 1 ) , 0 ) ,
5223+ ( list_of_dict. slice ( 1 , 1 ) , 5 ) ,
5224+ ( dict_of_list. slice ( 1 , 1 ) , 7 ) ,
5225+ ] {
5226+ assert_eq ! (
5227+ unsliced_hash_len( & array. to_data( ) ) ,
5228+ expected,
5229+ "{}" ,
5230+ array. data_type( )
5231+ ) ;
5232+ }
5233+ Ok ( ( ) )
5234+ }
5235+
51495236 /// Build batches sharing one key dictionary that is longer than each batch
51505237 /// fill the hash map from slices longer than the batches, which must join
51515238 /// as if the build side were a single batch.
0 commit comments