@@ -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,27 @@ 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+
240+ /// Whether any group column is dictionary encoded.
241+ has_dictionary : bool ,
242+
232243 /// Random state for creating hashes
233244 random_state : RandomState ,
234245}
235246
247+ #[ derive( Default ) ]
248+ struct DictionaryHashCache {
249+ /// Dictionary values these hashes belong to.
250+ values : Option < Weak < dyn Array > > ,
251+ /// Hash for each dictionary value.
252+ hashes : Vec < u64 > ,
253+ /// Number of times values were hashed.
254+ #[ cfg( test) ]
255+ rebuilds : usize ,
256+ }
257+
236258/// Buffers to store intermediate results in `vectorized_append`
237259/// and `vectorized_equal_to`, for reducing memory allocation
238260struct VectorizedOperationBuffers {
@@ -292,6 +314,29 @@ impl VectorizedOperationBuffers {
292314 }
293315}
294316
317+ impl DictionaryHashCache {
318+ fn update (
319+ & mut self ,
320+ values : & ArrayRef ,
321+ random_state : & RandomState ,
322+ ) -> Result < & [ u64 ] > {
323+ let unchanged = self . values . as_ref ( ) . is_some_and ( |cached| {
324+ std:: ptr:: addr_eq ( cached. as_ptr ( ) , Arc :: as_ptr ( values) )
325+ } ) ;
326+ if !unchanged {
327+ self . hashes . clear ( ) ;
328+ self . hashes . resize ( values. len ( ) , 0 ) ;
329+ create_hashes ( [ values] , random_state, & mut self . hashes ) ?;
330+ self . values = Some ( Arc :: downgrade ( values) ) ;
331+ #[ cfg( test) ]
332+ {
333+ self . rebuilds += 1 ;
334+ }
335+ }
336+ Ok ( & self . hashes )
337+ }
338+ }
339+
295340impl < const STREAMING : bool > GroupValuesColumn < STREAMING > {
296341 // ========================================================================
297342 // Initialization functions
@@ -301,6 +346,10 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
301346 pub fn try_new ( schema : SchemaRef ) -> Result < Self > {
302347 let map = HashTable :: with_capacity ( 0 ) ;
303348 let group_values = Self :: build_group_columns ( & schema) ?;
349+ let has_dictionary = schema
350+ . fields ( )
351+ . iter ( )
352+ . any ( |field| matches ! ( field. data_type( ) , DataType :: Dictionary ( _, _) ) ) ;
304353 Ok ( Self {
305354 schema,
306355 map,
@@ -310,10 +359,58 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
310359 map_size : 0 ,
311360 group_values,
312361 hashes_buffer : Default :: default ( ) ,
362+ dictionary_hash_cache : Default :: default ( ) ,
363+ has_dictionary,
313364 random_state : crate :: aggregates:: AGGREGATION_HASH_SEED ,
314365 } )
315366 }
316367
368+ fn create_hashes ( & mut self , cols : & [ ArrayRef ] , hashes : & mut [ u64 ] ) -> Result < ( ) > {
369+ if !self . has_dictionary {
370+ create_hashes ( cols, & self . random_state , hashes) ?;
371+ return Ok ( ( ) ) ;
372+ }
373+
374+ self . dictionary_hash_cache
375+ . resize_with ( cols. len ( ) , DictionaryHashCache :: default) ;
376+ for ( index, ( array, cache) ) in cols
377+ . iter ( )
378+ . zip ( self . dictionary_hash_cache . iter_mut ( ) )
379+ . enumerate ( )
380+ {
381+ let array = array. as_ref ( ) ;
382+ if matches ! ( array. data_type( ) , DataType :: Dictionary ( _, _) ) {
383+ downcast_dictionary_array ! {
384+ array => {
385+ let value_hashes = cache. update( array. values( ) , & self . random_state) ?;
386+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
387+ scatter_dictionary_hashes(
388+ array,
389+ value_hashes,
390+ hashes,
391+ index != 0 ,
392+ ) ;
393+ #[ cfg( feature = "force_hash_collisions" ) ]
394+ hash_single_array(
395+ array,
396+ & self . random_state,
397+ hashes,
398+ index != 0 ,
399+ ) ?;
400+ self . group_values[ index]
401+ . set_dictionary_hashes( array. values( ) , value_hashes) ;
402+ } ,
403+ _ => unreachable!( ) ,
404+ }
405+ } else {
406+ * cache = DictionaryHashCache :: default ( ) ;
407+ hash_single_array ( array, & self . random_state , hashes, index != 0 ) ?;
408+ }
409+ }
410+
411+ Ok ( ( ) )
412+ }
413+
317414 /// Build one fresh [`GroupColumn`] per field in the schema.
318415 ///
319416 /// Used at construction time (`try_new`) and to repopulate the column
@@ -383,10 +480,10 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
383480 groups. clear ( ) ;
384481
385482 // 1.1 Calculate the group keys for the group values
386- let batch_hashes = & mut self . hashes_buffer ;
483+ let mut batch_hashes = mem :: take ( & mut self . hashes_buffer ) ;
387484 batch_hashes. clear ( ) ;
388485 batch_hashes. resize ( n_rows, 0 ) ;
389- create_hashes ( cols, & self . random_state , batch_hashes) ?;
486+ self . create_hashes ( cols, & mut batch_hashes) ?;
390487
391488 for ( row, & target_hash) in batch_hashes. iter ( ) . enumerate ( ) {
392489 let entry = self
@@ -459,6 +556,8 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
459556 groups. push ( group_idx) ;
460557 }
461558
559+ self . hashes_buffer = batch_hashes;
560+
462561 Ok ( ( ) )
463562 }
464563
@@ -487,7 +586,7 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
487586 let mut batch_hashes = mem:: take ( & mut self . hashes_buffer ) ;
488587 batch_hashes. clear ( ) ;
489588 batch_hashes. resize ( n_rows, 0 ) ;
490- create_hashes ( cols, & self . random_state , & mut batch_hashes) ?;
589+ self . create_hashes ( cols, & mut batch_hashes) ?;
491590
492591 // General steps for one round `vectorized equal_to & append`:
493592 // 1. Collect vectorized context by checking hash values of `cols` in `map`,
@@ -1103,6 +1202,12 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
11031202 + self . emit_group_index_list_buffer . allocated_size ( )
11041203 + self . vectorized_operation_buffers . size ( )
11051204 + self . hashes_buffer . allocated_size ( )
1205+ + self . dictionary_hash_cache . allocated_size ( )
1206+ + self
1207+ . dictionary_hash_cache
1208+ . iter ( )
1209+ . map ( |cache| cache. hashes . allocated_size ( ) )
1210+ . sum :: < usize > ( )
11061211 }
11071212
11081213 fn is_empty ( & self ) -> bool {
@@ -1247,6 +1352,8 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
12471352 self . map_size = self . map . capacity ( ) * size_of :: < ( u64 , usize ) > ( ) ;
12481353 self . hashes_buffer . clear ( ) ;
12491354 self . hashes_buffer . shrink_to ( num_rows) ;
1355+ self . dictionary_hash_cache . clear ( ) ;
1356+ self . dictionary_hash_cache . shrink_to_fit ( ) ;
12501357
12511358 // Such structures are only used in `non-streaming` case
12521359 if !STREAMING {
@@ -1283,12 +1390,12 @@ mod tests {
12831390 use std:: { collections:: HashMap , sync:: Arc } ;
12841391
12851392 use arrow:: array:: {
1286- Array , ArrayRef , DurationMicrosecondArray , FixedSizeBinaryArray , Float16Array ,
1287- Int32Array , Int64Array , PrimitiveArray , RecordBatch , StringArray ,
1393+ Array , ArrayRef , DictionaryArray , DurationMicrosecondArray , FixedSizeBinaryArray ,
1394+ Float16Array , Int32Array , Int64Array , PrimitiveArray , RecordBatch , StringArray ,
12881395 StringViewArray , UInt32Array ,
12891396 } ;
12901397 use arrow:: datatypes:: {
1291- DataType , Decimal32Type , Decimal64Type , Field , Schema , SchemaRef ,
1398+ DataType , Decimal32Type , Decimal64Type , Field , Int32Type , Schema , SchemaRef ,
12921399 } ;
12931400 use arrow:: {
12941401 compute:: { concat_batches, take} ,
@@ -2112,6 +2219,7 @@ mod tests {
21122219
21132220 let mut gv = GroupValuesColumn :: < false > :: try_new ( Arc :: clone ( & schema) ) . unwrap ( ) ;
21142221 gv. intern ( & [ labels, categories] , & mut vec ! [ ] ) . unwrap ( ) ;
2222+ assert_eq ! ( gv. dictionary_hash_cache[ 1 ] . rebuilds, 1 ) ;
21152223 let out = gv. emit ( EmitTo :: All ) . unwrap ( ) ;
21162224
21172225 assert_eq ! ( out[ 0 ] . len( ) , n_groups) ;
@@ -2124,6 +2232,37 @@ mod tests {
21242232 assert_eq ! ( out[ 1 ] . as_dictionary:: <Int8Type >( ) . values( ) . len( ) , 2 ) ;
21252233 }
21262234
2235+ #[ test]
2236+ fn dictionary_hashes_follow_values_arc ( ) {
2237+ let schema = Arc :: new ( Schema :: new ( vec ! [ Field :: new(
2238+ "category" ,
2239+ DataType :: Dictionary ( Box :: new( DataType :: Int32 ) , Box :: new( DataType :: Utf8 ) ) ,
2240+ true ,
2241+ ) ] ) ) ;
2242+ let values: ArrayRef = Arc :: new ( StringArray :: from ( vec ! [ Some ( "a" ) , None :: <& str >] ) ) ;
2243+ let batch = |keys, values| -> ArrayRef {
2244+ Arc :: new ( DictionaryArray :: < Int32Type > :: new (
2245+ Int32Array :: from ( keys) ,
2246+ values,
2247+ ) )
2248+ } ;
2249+ let first = batch ( vec ! [ Some ( 0 ) , Some ( 1 ) , None ] , Arc :: clone ( & values) ) ;
2250+ let second = batch ( vec ! [ Some ( 1 ) , Some ( 0 ) ] , Arc :: clone ( & values) ) ;
2251+ let replacement_values: ArrayRef =
2252+ Arc :: new ( StringArray :: from ( vec ! [ Some ( "a" ) , None :: <& str >] ) ) ;
2253+ let replacement = batch ( vec ! [ Some ( 0 ) , Some ( 1 ) ] , replacement_values) ;
2254+ let mut group_values = GroupValuesColumn :: < false > :: try_new ( schema) . unwrap ( ) ;
2255+
2256+ let mut first_groups = vec ! [ ] ;
2257+ group_values. intern ( & [ first] , & mut first_groups) . unwrap ( ) ;
2258+ group_values. intern ( & [ second] , & mut vec ! [ ] ) . unwrap ( ) ;
2259+ assert_eq ! ( group_values. dictionary_hash_cache[ 0 ] . rebuilds, 1 ) ;
2260+
2261+ group_values. intern ( & [ replacement] , & mut vec ! [ ] ) . unwrap ( ) ;
2262+ assert_eq ! ( group_values. dictionary_hash_cache[ 0 ] . rebuilds, 2 ) ;
2263+ assert_eq ! ( first_groups[ 1 ] , first_groups[ 2 ] ) ;
2264+ }
2265+
21272266 #[ test]
21282267 fn test_intern_for_vectorized_group_values ( ) {
21292268 let data_set = VectorizedTestDataSet :: new ( ) ;
0 commit comments