@@ -29,7 +29,7 @@ pub mod primitive;
2929pub mod row_backed;
3030
3131use std:: mem:: { self , size_of} ;
32- use std:: sync:: Arc ;
32+ use std:: sync:: { Arc , Weak } ;
3333
3434use crate :: aggregates:: group_values:: GroupValues ;
3535use crate :: aggregates:: group_values:: multi_group_by:: {
@@ -45,9 +45,11 @@ use arrow::datatypes::{
4545 BinaryViewType , DataType , Field , Int8Type , Int16Type , Int32Type , Int64Type , Schema ,
4646 SchemaRef , StringViewType , UInt8Type , UInt16Type , UInt32Type , UInt64Type ,
4747} ;
48+ use arrow:: downcast_dictionary_array;
4849use datafusion_common:: float_semantics:: { has_float_leaf, normalize_floats} ;
49- use datafusion_common:: hash_utils:: RandomState ;
50- use datafusion_common:: hash_utils:: create_hashes;
50+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
51+ use datafusion_common:: hash_utils:: scatter_dictionary_hashes;
52+ use datafusion_common:: hash_utils:: { RandomState , create_hashes, hash_single_array} ;
5153use datafusion_common:: { Result , not_impl_err} ;
5254use datafusion_execution:: memory_pool:: proxy:: { HashTableAllocExt , VecAllocExt } ;
5355use datafusion_expr:: { EmitTo , GroupSelection } ;
@@ -95,6 +97,9 @@ pub trait GroupColumn: Send + Sync {
9597 /// The vectorized version `append_val`
9698 fn vectorized_append ( & mut self , array : & ArrayRef , rows : & [ usize ] ) -> Result < ( ) > ;
9799
100+ /// Installs hashes already computed for a dictionary values array.
101+ fn set_dictionary_hashes ( & mut self , _values : & ArrayRef , _hashes : & [ u64 ] ) { }
102+
98103 /// Returns the number of rows stored in this builder
99104 fn len ( & self ) -> usize ;
100105
@@ -229,10 +234,24 @@ pub struct GroupValuesColumn<const STREAMING: bool> {
229234 /// reused buffer to store hashes
230235 hashes_buffer : Vec < u64 > ,
231236
237+ /// Cached hashes for dictionary values in each group column.
238+ dictionary_hash_cache : Vec < DictionaryHashCache > ,
239+
232240 /// Random state for creating hashes
233241 random_state : RandomState ,
234242}
235243
244+ #[ derive( Default ) ]
245+ struct DictionaryHashCache {
246+ /// Dictionary values these hashes belong to.
247+ values : Option < Weak < dyn Array > > ,
248+ /// Hash for each dictionary value.
249+ hashes : Vec < u64 > ,
250+ /// Number of times values were hashed.
251+ #[ cfg( test) ]
252+ rebuilds : usize ,
253+ }
254+
236255/// Buffers to store intermediate results in `vectorized_append`
237256/// and `vectorized_equal_to`, for reducing memory allocation
238257struct VectorizedOperationBuffers {
@@ -292,6 +311,29 @@ impl VectorizedOperationBuffers {
292311 }
293312}
294313
314+ impl DictionaryHashCache {
315+ fn update (
316+ & mut self ,
317+ values : & ArrayRef ,
318+ random_state : & RandomState ,
319+ ) -> Result < & [ u64 ] > {
320+ let unchanged = self . values . as_ref ( ) . is_some_and ( |cached| {
321+ std:: ptr:: addr_eq ( cached. as_ptr ( ) , Arc :: as_ptr ( values) )
322+ } ) ;
323+ if !unchanged {
324+ self . hashes . clear ( ) ;
325+ self . hashes . resize ( values. len ( ) , 0 ) ;
326+ create_hashes ( [ values] , random_state, & mut self . hashes ) ?;
327+ self . values = Some ( Arc :: downgrade ( values) ) ;
328+ #[ cfg( test) ]
329+ {
330+ self . rebuilds += 1 ;
331+ }
332+ }
333+ Ok ( & self . hashes )
334+ }
335+ }
336+
295337impl < const STREAMING : bool > GroupValuesColumn < STREAMING > {
296338 // ========================================================================
297339 // Initialization functions
@@ -310,10 +352,52 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
310352 map_size : 0 ,
311353 group_values,
312354 hashes_buffer : Default :: default ( ) ,
355+ dictionary_hash_cache : Default :: default ( ) ,
313356 random_state : crate :: aggregates:: AGGREGATION_HASH_SEED ,
314357 } )
315358 }
316359
360+ fn create_hashes ( & mut self , cols : & [ ArrayRef ] , hashes : & mut [ u64 ] ) -> Result < ( ) > {
361+ self . dictionary_hash_cache
362+ . resize_with ( cols. len ( ) , DictionaryHashCache :: default) ;
363+ for ( index, ( array, cache) ) in cols
364+ . iter ( )
365+ . zip ( self . dictionary_hash_cache . iter_mut ( ) )
366+ . enumerate ( )
367+ {
368+ let array = array. as_ref ( ) ;
369+ if matches ! ( array. data_type( ) , DataType :: Dictionary ( _, _) ) {
370+ downcast_dictionary_array ! {
371+ array => {
372+ let value_hashes = cache. update( array. values( ) , & self . random_state) ?;
373+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
374+ scatter_dictionary_hashes(
375+ array,
376+ value_hashes,
377+ hashes,
378+ index != 0 ,
379+ ) ;
380+ #[ cfg( feature = "force_hash_collisions" ) ]
381+ hash_single_array(
382+ array,
383+ & self . random_state,
384+ hashes,
385+ index != 0 ,
386+ ) ?;
387+ self . group_values[ index]
388+ . set_dictionary_hashes( array. values( ) , value_hashes) ;
389+ } ,
390+ _ => unreachable!( ) ,
391+ }
392+ } else {
393+ * cache = DictionaryHashCache :: default ( ) ;
394+ hash_single_array ( array, & self . random_state , hashes, index != 0 ) ?;
395+ }
396+ }
397+
398+ Ok ( ( ) )
399+ }
400+
317401 /// Build one fresh [`GroupColumn`] per field in the schema.
318402 ///
319403 /// Used at construction time (`try_new`) and to repopulate the column
@@ -383,10 +467,10 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
383467 groups. clear ( ) ;
384468
385469 // 1.1 Calculate the group keys for the group values
386- let batch_hashes = & mut self . hashes_buffer ;
470+ let mut batch_hashes = mem :: take ( & mut self . hashes_buffer ) ;
387471 batch_hashes. clear ( ) ;
388472 batch_hashes. resize ( n_rows, 0 ) ;
389- create_hashes ( cols, & self . random_state , batch_hashes) ?;
473+ self . create_hashes ( cols, & mut batch_hashes) ?;
390474
391475 for ( row, & target_hash) in batch_hashes. iter ( ) . enumerate ( ) {
392476 let entry = self
@@ -459,6 +543,8 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
459543 groups. push ( group_idx) ;
460544 }
461545
546+ self . hashes_buffer = batch_hashes;
547+
462548 Ok ( ( ) )
463549 }
464550
@@ -487,7 +573,7 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
487573 let mut batch_hashes = mem:: take ( & mut self . hashes_buffer ) ;
488574 batch_hashes. clear ( ) ;
489575 batch_hashes. resize ( n_rows, 0 ) ;
490- create_hashes ( cols, & self . random_state , & mut batch_hashes) ?;
576+ self . create_hashes ( cols, & mut batch_hashes) ?;
491577
492578 // General steps for one round `vectorized equal_to & append`:
493579 // 1. Collect vectorized context by checking hash values of `cols` in `map`,
@@ -1103,6 +1189,12 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
11031189 + self . emit_group_index_list_buffer . allocated_size ( )
11041190 + self . vectorized_operation_buffers . size ( )
11051191 + self . hashes_buffer . allocated_size ( )
1192+ + self . dictionary_hash_cache . allocated_size ( )
1193+ + self
1194+ . dictionary_hash_cache
1195+ . iter ( )
1196+ . map ( |cache| cache. hashes . allocated_size ( ) )
1197+ . sum :: < usize > ( )
11061198 }
11071199
11081200 fn is_empty ( & self ) -> bool {
@@ -1247,6 +1339,8 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
12471339 self . map_size = self . map . capacity ( ) * size_of :: < ( u64 , usize ) > ( ) ;
12481340 self . hashes_buffer . clear ( ) ;
12491341 self . hashes_buffer . shrink_to ( num_rows) ;
1342+ self . dictionary_hash_cache . clear ( ) ;
1343+ self . dictionary_hash_cache . shrink_to_fit ( ) ;
12501344
12511345 // Such structures are only used in `non-streaming` case
12521346 if !STREAMING {
@@ -1283,12 +1377,12 @@ mod tests {
12831377 use std:: { collections:: HashMap , sync:: Arc } ;
12841378
12851379 use arrow:: array:: {
1286- Array , ArrayRef , DurationMicrosecondArray , FixedSizeBinaryArray , Float16Array ,
1287- Int32Array , Int64Array , PrimitiveArray , RecordBatch , StringArray ,
1380+ Array , ArrayRef , DictionaryArray , DurationMicrosecondArray , FixedSizeBinaryArray ,
1381+ Float16Array , Int32Array , Int64Array , PrimitiveArray , RecordBatch , StringArray ,
12881382 StringViewArray , UInt32Array ,
12891383 } ;
12901384 use arrow:: datatypes:: {
1291- DataType , Decimal32Type , Decimal64Type , Field , Schema , SchemaRef ,
1385+ DataType , Decimal32Type , Decimal64Type , Field , Int32Type , Schema , SchemaRef ,
12921386 } ;
12931387 use arrow:: {
12941388 compute:: { concat_batches, take} ,
@@ -2112,6 +2206,7 @@ mod tests {
21122206
21132207 let mut gv = GroupValuesColumn :: < false > :: try_new ( Arc :: clone ( & schema) ) . unwrap ( ) ;
21142208 gv. intern ( & [ labels, categories] , & mut vec ! [ ] ) . unwrap ( ) ;
2209+ assert_eq ! ( gv. dictionary_hash_cache[ 1 ] . rebuilds, 1 ) ;
21152210 let out = gv. emit ( EmitTo :: All ) . unwrap ( ) ;
21162211
21172212 assert_eq ! ( out[ 0 ] . len( ) , n_groups) ;
@@ -2124,6 +2219,37 @@ mod tests {
21242219 assert_eq ! ( out[ 1 ] . as_dictionary:: <Int8Type >( ) . values( ) . len( ) , 2 ) ;
21252220 }
21262221
2222+ #[ test]
2223+ fn dictionary_hashes_follow_values_arc ( ) {
2224+ let schema = Arc :: new ( Schema :: new ( vec ! [ Field :: new(
2225+ "category" ,
2226+ DataType :: Dictionary ( Box :: new( DataType :: Int32 ) , Box :: new( DataType :: Utf8 ) ) ,
2227+ true ,
2228+ ) ] ) ) ;
2229+ let values: ArrayRef = Arc :: new ( StringArray :: from ( vec ! [ Some ( "a" ) , None :: <& str >] ) ) ;
2230+ let batch = |keys, values| -> ArrayRef {
2231+ Arc :: new ( DictionaryArray :: < Int32Type > :: new (
2232+ Int32Array :: from ( keys) ,
2233+ values,
2234+ ) )
2235+ } ;
2236+ let first = batch ( vec ! [ Some ( 0 ) , Some ( 1 ) , None ] , Arc :: clone ( & values) ) ;
2237+ let second = batch ( vec ! [ Some ( 1 ) , Some ( 0 ) ] , Arc :: clone ( & values) ) ;
2238+ let replacement_values: ArrayRef =
2239+ Arc :: new ( StringArray :: from ( vec ! [ Some ( "a" ) , None :: <& str >] ) ) ;
2240+ let replacement = batch ( vec ! [ Some ( 0 ) , Some ( 1 ) ] , replacement_values) ;
2241+ let mut group_values = GroupValuesColumn :: < false > :: try_new ( schema) . unwrap ( ) ;
2242+
2243+ let mut first_groups = vec ! [ ] ;
2244+ group_values. intern ( & [ first] , & mut first_groups) . unwrap ( ) ;
2245+ group_values. intern ( & [ second] , & mut vec ! [ ] ) . unwrap ( ) ;
2246+ assert_eq ! ( group_values. dictionary_hash_cache[ 0 ] . rebuilds, 1 ) ;
2247+
2248+ group_values. intern ( & [ replacement] , & mut vec ! [ ] ) . unwrap ( ) ;
2249+ assert_eq ! ( group_values. dictionary_hash_cache[ 0 ] . rebuilds, 2 ) ;
2250+ assert_eq ! ( first_groups[ 1 ] , first_groups[ 2 ] ) ;
2251+ }
2252+
21272253 #[ test]
21282254 fn test_intern_for_vectorized_group_values ( ) {
21292255 let data_set = VectorizedTestDataSet :: new ( ) ;
0 commit comments