@@ -30,6 +30,8 @@ use foldhash::fast::FixedState;
3030#[ cfg( not( feature = "force_hash_collisions" ) ) ]
3131use itertools:: Itertools ;
3232use std:: hash:: { BuildHasher , Hash , Hasher } ;
33+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
34+ use std:: sync:: { Arc , Weak } ;
3335
3436/// [`RandomState`] is optimized for speed and suitable for hash tables and
3537/// bloom filters. [`QualityRandomState`] is optimized for statistical quality
@@ -679,6 +681,150 @@ fn hash_dictionary<K: ArrowDictionaryKeyType>(
679681 Ok ( ( ) )
680682}
681683
684+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
685+ #[ derive( Default ) ]
686+ struct DictionaryHashCacheEntry {
687+ /// Weak reference avoids retaining an input dictionary after its batch is released.
688+ values : Option < Weak < dyn Array > > ,
689+ /// Hash for each value in `values`.
690+ hashes : Vec < u64 > ,
691+ /// Number of cache misses, used to verify reuse.
692+ #[ cfg( test) ]
693+ rebuilds : usize ,
694+ }
695+
696+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
697+ impl DictionaryHashCacheEntry {
698+ fn sync ( & mut self , values : & ArrayRef , random_state : & impl HashState ) -> Result < ( ) > {
699+ let is_cached = self . values . as_ref ( ) . is_some_and ( |cached| {
700+ std:: ptr:: addr_eq ( cached. as_ptr ( ) , Arc :: as_ptr ( values) )
701+ } ) ;
702+ if is_cached {
703+ return Ok ( ( ) ) ;
704+ }
705+
706+ self . values = None ;
707+ self . hashes . clear ( ) ;
708+ self . hashes . resize ( values. len ( ) , 0 ) ;
709+ create_hashes ( [ values] , random_state, & mut self . hashes ) ?;
710+ #[ cfg( test) ]
711+ {
712+ self . rebuilds += 1 ;
713+ }
714+ self . values = Some ( Arc :: downgrade ( values) ) ;
715+ Ok ( ( ) )
716+ }
717+
718+ fn size ( & self ) -> usize {
719+ self . hashes . capacity ( ) * size_of :: < u64 > ( )
720+ }
721+ }
722+
723+ /// Caches dictionary value hashes by column and values array identity.
724+ ///
725+ /// Arrow arrays are immutable, so matching [`Arc`] identity is sufficient to
726+ /// reuse the cached hashes.
727+ ///
728+ /// This is an internal API used by physical operators that hash multiple batches
729+ /// sharing the same dictionary values.
730+ #[ doc( hidden) ]
731+ pub struct DictionaryHashCache {
732+ /// Hash state used to build all cached hashes.
733+ random_state : RandomState ,
734+ /// One cache entry per hashed column.
735+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
736+ entries : Vec < DictionaryHashCacheEntry > ,
737+ }
738+
739+ impl DictionaryHashCache {
740+ /// Creates a cache for hashes produced by `random_state`.
741+ pub fn new ( random_state : RandomState ) -> Self {
742+ Self {
743+ random_state,
744+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
745+ entries : Vec :: new ( ) ,
746+ }
747+ }
748+
749+ /// Hashes `arrays`, reusing dictionary value hashes while their values
750+ /// [`Arc`] remains unchanged.
751+ pub fn create_hashes < ' a > (
752+ & mut self ,
753+ arrays : & [ ArrayRef ] ,
754+ hashes_buffer : & ' a mut [ u64 ] ,
755+ ) -> Result < & ' a mut [ u64 ] > {
756+ #[ cfg( feature = "force_hash_collisions" ) ]
757+ return create_hashes ( arrays, & self . random_state , hashes_buffer) ;
758+
759+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
760+ {
761+ if !arrays
762+ . iter ( )
763+ . any ( |array| matches ! ( array. data_type( ) , DataType :: Dictionary ( _, _) ) )
764+ {
765+ self . entries = Vec :: new ( ) ;
766+ return create_hashes ( arrays, & self . random_state , hashes_buffer) ;
767+ }
768+
769+ self . entries
770+ . resize_with ( arrays. len ( ) , DictionaryHashCacheEntry :: default) ;
771+
772+ for ( index, array) in arrays. iter ( ) . enumerate ( ) {
773+ let rehash = index != 0 ;
774+ if matches ! ( array. data_type( ) , DataType :: Dictionary ( _, _) ) {
775+ let entry = & mut self . entries [ index] ;
776+ let array = array. as_ref ( ) ;
777+ downcast_dictionary_array ! {
778+ array => {
779+ entry. sync( array. values( ) , & self . random_state) ?;
780+ dispatch_dictionary_scatter(
781+ array,
782+ & entry. hashes,
783+ hashes_buffer,
784+ rehash,
785+ ) ;
786+ } ,
787+ _ => unreachable!( )
788+ }
789+ } else {
790+ self . entries [ index] = DictionaryHashCacheEntry :: default ( ) ;
791+ hash_single_array (
792+ array. as_ref ( ) ,
793+ & self . random_state ,
794+ hashes_buffer,
795+ rehash,
796+ ) ?;
797+ }
798+ }
799+ Ok ( hashes_buffer)
800+ }
801+ }
802+
803+ /// Returns the memory retained by cached dictionary value hashes.
804+ pub fn size ( & self ) -> usize {
805+ #[ cfg( feature = "force_hash_collisions" ) ]
806+ return 0 ;
807+
808+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
809+ {
810+ self . entries . capacity ( ) * size_of :: < DictionaryHashCacheEntry > ( )
811+ + self
812+ . entries
813+ . iter ( )
814+ . map ( DictionaryHashCacheEntry :: size)
815+ . sum :: < usize > ( )
816+ }
817+ }
818+
819+ /// Drops all cached hashes.
820+ pub fn clear ( & mut self ) {
821+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
822+ {
823+ self . entries = Vec :: new ( ) ;
824+ }
825+ }
826+ }
827+
682828#[ cfg( not( feature = "force_hash_collisions" ) ) ]
683829fn hash_dictionary_with_child_hashing < K : ArrowDictionaryKeyType > (
684830 array : & DictionaryArray < K > ,
@@ -1353,6 +1499,71 @@ mod tests {
13531499
13541500 use super :: * ;
13551501
1502+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
1503+ fn dictionary_array ( keys : Vec < Option < i32 > > , values : ArrayRef ) -> ArrayRef {
1504+ Arc :: new (
1505+ DictionaryArray :: < Int32Type > :: try_new ( Int32Array :: from ( keys) , values)
1506+ . unwrap ( ) ,
1507+ )
1508+ }
1509+
1510+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
1511+ #[ test]
1512+ fn dictionary_hash_cache_reuses_and_invalidates_value_hashes ( ) -> Result < ( ) > {
1513+ let values: ArrayRef =
1514+ Arc :: new ( StringArray :: from ( vec ! [ Some ( "a" ) , None , Some ( "ccc" ) ] ) ) ;
1515+ let first =
1516+ dictionary_array ( vec ! [ Some ( 0 ) , Some ( 2 ) , None , Some ( 1 ) ] , Arc :: clone ( & values) ) ;
1517+ let second =
1518+ dictionary_array ( vec ! [ Some ( 2 ) , Some ( 0 ) , Some ( 2 ) , None ] , Arc :: clone ( & values) ) ;
1519+ let values_strong_count = Arc :: strong_count ( & values) ;
1520+ let random_state = RandomState :: with_seed ( 42 ) ;
1521+ let mut cache = DictionaryHashCache :: new ( random_state. clone ( ) ) ;
1522+
1523+ for array in [ & first, & second] {
1524+ let mut expected = vec ! [ 0 ; array. len( ) ] ;
1525+ create_hashes ( [ array] , & random_state, & mut expected) ?;
1526+ let mut actual = vec ! [ 0 ; array. len( ) ] ;
1527+ cache. create_hashes ( std:: slice:: from_ref ( array) , & mut actual) ?;
1528+ assert_eq ! ( actual, expected) ;
1529+ }
1530+ assert_eq ! ( cache. entries[ 0 ] . rebuilds, 1 ) ;
1531+ assert_eq ! ( Arc :: strong_count( & values) , values_strong_count) ;
1532+
1533+ let replacement_values: ArrayRef =
1534+ Arc :: new ( StringArray :: from ( vec ! [ Some ( "x" ) , None , Some ( "zzz" ) ] ) ) ;
1535+ let replacement =
1536+ dictionary_array ( vec ! [ Some ( 0 ) , Some ( 2 ) , None , Some ( 1 ) ] , replacement_values) ;
1537+ let mut expected = vec ! [ 0 ; replacement. len( ) ] ;
1538+ create_hashes ( [ & replacement] , & random_state, & mut expected) ?;
1539+ let mut actual = vec ! [ 0 ; replacement. len( ) ] ;
1540+ cache. create_hashes ( & [ replacement] , & mut actual) ?;
1541+
1542+ assert_eq ! ( actual, expected) ;
1543+ assert_eq ! ( cache. entries[ 0 ] . rebuilds, 2 ) ;
1544+ Ok ( ( ) )
1545+ }
1546+
1547+ #[ cfg( not( feature = "force_hash_collisions" ) ) ]
1548+ #[ test]
1549+ fn dictionary_hash_cache_matches_composite_hashes ( ) -> Result < ( ) > {
1550+ let values: ArrayRef = Arc :: new ( StringArray :: from ( vec ! [ "a" , "bb" , "ccc" ] ) ) ;
1551+ let dictionary = dictionary_array ( vec ! [ Some ( 2 ) , Some ( 0 ) , Some ( 1 ) , None ] , values) ;
1552+ let primitive: ArrayRef = Arc :: new ( Int32Array :: from ( vec ! [ 1 , 2 , 3 , 4 ] ) ) ;
1553+ let arrays = [ primitive, dictionary] ;
1554+ let random_state = RandomState :: with_seed ( 42 ) ;
1555+ let mut expected = vec ! [ 0 ; arrays[ 0 ] . len( ) ] ;
1556+ create_hashes ( & arrays, & random_state, & mut expected) ?;
1557+
1558+ let mut actual = vec ! [ 0 ; arrays[ 0 ] . len( ) ] ;
1559+ let mut cache = DictionaryHashCache :: new ( random_state) ;
1560+ cache. create_hashes ( & arrays, & mut actual) ?;
1561+
1562+ assert_eq ! ( actual, expected) ;
1563+ assert_eq ! ( cache. entries[ 1 ] . rebuilds, 1 ) ;
1564+ Ok ( ( ) )
1565+ }
1566+
13561567 #[ cfg( not( feature = "force_hash_collisions" ) ) ]
13571568 #[ derive( Default ) ]
13581569 struct TestHasher ( u64 ) ;
0 commit comments