@@ -54,12 +54,18 @@ pub struct DictionaryGroupValuesColumn<K: ArrowDictionaryKeyType + Send + Sync>
5454 null_inner_slot : Option < usize > ,
5555 /// Hash seed — must match `create_hashes` so hashes are consistent across calls.
5656 random_state : RandomState ,
57- /// Reusable scratch buffer mapping `val_idx → inner_slot` across batches.
57+ /// Maps `val_idx → inner_slot` for the values array in `cached_values`.
58+ ///
59+ /// Valid only while `cached_values` is `Some` and matches the incoming
60+ /// values array; `usize::MAX` means "not yet resolved". Entries are only
61+ /// ever filled in, never invalidated, because `inner` slots are stable
62+ /// under append. `take_n` remaps `inner` and therefore drops the cache.
5863 val_to_inner : Vec < usize > ,
59- /// Reusable hash buffer for the dictionary values array.
64+ /// Hashes of the values array in `cached_values`, one per `val_idx` .
6065 val_hashes : Vec < u64 > ,
61- /// The last `dict.values()` Arc hashed in `append_val`. When the incoming
62- /// values array is `ptr_eq` to this, `val_hashes` can be reused directly.
66+ /// The values array that `val_hashes` and `val_to_inner` were built for.
67+ /// When an incoming `dict.values()` is `Arc::ptr_eq` to this, both caches
68+ /// are reused instead of being rebuilt. See [`Self::sync_value_cache`].
6369 cached_values : Option < ArrayRef > ,
6470 _phantom : PhantomData < K > ,
6571}
@@ -175,6 +181,28 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> DictionaryGroupValuesColumn<K> {
175181 . unwrap ( ) ;
176182 }
177183
184+ /// Makes `val_hashes` and `val_to_inner` correspond to `dict_values`,
185+ /// reusing them when they were already built for this same values array.
186+ ///
187+ /// `take`, `filter` and repartitioning clone the values `Arc` and rewrite
188+ /// only the keys, so batches in a partition usually share one values
189+ /// array; without this the per-batch cost is O(dictionary cardinality)
190+ /// rather than O(rows). `take_n` remaps `inner` and clears
191+ /// `cached_values`, forcing a rebuild.
192+ fn sync_value_cache ( & mut self , dict_values : & ArrayRef ) {
193+ if self
194+ . cached_values
195+ . as_ref ( )
196+ . is_some_and ( |c| Arc :: ptr_eq ( c, dict_values) )
197+ {
198+ return ;
199+ }
200+ self . hash_values ( dict_values) ;
201+ self . val_to_inner . clear ( ) ;
202+ self . val_to_inner . resize ( dict_values. len ( ) , usize:: MAX ) ;
203+ self . cached_values = Some ( Arc :: clone ( dict_values) ) ;
204+ }
205+
178206 fn find_or_insert_value (
179207 & mut self ,
180208 dict_values : & ArrayRef ,
@@ -302,24 +330,7 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> GroupColumn
302330 }
303331 Some ( val_idx) => {
304332 let dict_values = dict. values ( ) ;
305- // check if the dictionary values array we are hashing was already seen.
306- // if its arc was already stored we dont need to rehash the entire array again
307- // if its new hash the entire array and store an arc ptr for future use
308- let cache_hit = self
309- . cached_values
310- . as_ref ( )
311- . is_some_and ( |c| Arc :: ptr_eq ( c, dict_values) ) ;
312- if !cache_hit {
313- self . val_hashes . clear ( ) ;
314- self . val_hashes . resize ( dict_values. len ( ) , 0 ) ;
315- create_hashes (
316- std:: slice:: from_ref ( dict_values) ,
317- & self . random_state ,
318- & mut self . val_hashes ,
319- )
320- . unwrap ( ) ;
321- self . cached_values = Some ( Arc :: clone ( dict_values) ) ;
322- }
333+ self . sync_value_cache ( dict_values) ;
323334 self . find_or_insert_value ( dict_values, val_idx, self . val_hashes [ val_idx] ) ?
324335 }
325336 } ;
@@ -401,11 +412,12 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> GroupColumn
401412 let dict = array. as_dictionary :: < K > ( ) ;
402413 let dict_keys = dict. keys ( ) ;
403414 let dict_values = dict. values ( ) ;
404- let num_distinct = dict_values. len ( ) ;
405415
406- self . hash_values ( dict_values) ;
407- self . val_to_inner . clear ( ) ;
408- self . val_to_inner . resize ( num_distinct, usize:: MAX ) ;
416+ // Reuses `val_hashes`/`val_to_inner` when this batch carries the same
417+ // values array as the last one, which is the common case downstream of
418+ // a repartition or filter. Previously this unconditionally re-hashed
419+ // and re-initialised both buffers, costing O(D) per batch.
420+ self . sync_value_cache ( dict_values) ;
409421
410422 self . group_to_inner . try_reserve ( rows. len ( ) ) . map_err ( |e| {
411423 DataFusionError :: ArrowError (
@@ -918,4 +930,134 @@ mod tests {
918930 assert_eq ! ( str_values( & out) [ 127 ] , Some ( "v127" . into( ) ) ) ;
919931 assert_eq ! ( out. as_dictionary:: <Int8Type >( ) . values( ) . len( ) , 128 ) ;
920932 }
933+
934+ fn dict_with_values ( keys : & [ Option < i32 > ] , values : & ArrayRef ) -> ArrayRef {
935+ Arc :: new ( DictionaryArray :: < Int32Type > :: new (
936+ Int32Array :: from ( keys. to_vec ( ) ) ,
937+ Arc :: clone ( values) ,
938+ ) )
939+ }
940+
941+ /// A cache rebuild resets every `val_to_inner` entry to `usize::MAX`, so
942+ /// an entry resolved by an earlier batch surviving a later one proves the
943+ /// dictionary was not re-hashed in between.
944+ #[ test]
945+ fn cache_survives_batches_sharing_a_values_array ( ) {
946+ let values: ArrayRef =
947+ Arc :: new ( StringArray :: from ( vec ! [ Some ( "a" ) , Some ( "b" ) , Some ( "c" ) ] ) ) ;
948+ let mut col = utf8_col ( ) ;
949+
950+ col. vectorized_append ( & dict_with_values ( & [ Some ( 0 ) ] , & values) , & [ 0 ] )
951+ . unwrap ( ) ;
952+ let slot_a = col. val_to_inner [ 0 ] ;
953+ assert_ne ! ( slot_a, usize :: MAX ) ;
954+
955+ col. vectorized_append ( & dict_with_values ( & [ Some ( 1 ) ] , & values) , & [ 0 ] )
956+ . unwrap ( ) ;
957+
958+ assert_eq ! ( col. val_to_inner[ 0 ] , slot_a, "cache was rebuilt" ) ;
959+ assert_ne ! ( col. val_to_inner[ 1 ] , usize :: MAX ) ;
960+ assert_eq ! (
961+ col. val_to_inner[ 2 ] ,
962+ usize :: MAX ,
963+ "unreferenced value resolved"
964+ ) ;
965+ assert ! (
966+ col. cached_values
967+ . as_ref( )
968+ . is_some_and( |c| Arc :: ptr_eq( c, & values) )
969+ ) ;
970+ assert_eq ! ( col. inner. len( ) , 2 ) ;
971+ }
972+
973+ /// `take` clones the values `Arc` and rewrites only the keys, which is the
974+ /// property the `ptr_eq` check relies on. Pin that arrow behaviour.
975+ #[ test]
976+ fn take_preserves_values_arc_so_cache_hits ( ) {
977+ let values: ArrayRef = Arc :: new ( StringArray :: from ( vec ! [ Some ( "a" ) , Some ( "b" ) ] ) ) ;
978+ let batch = dict_with_values ( & [ Some ( 0 ) , Some ( 1 ) , Some ( 0 ) ] , & values) ;
979+ let taken = take ( & * batch, & Int32Array :: from ( vec ! [ 2 , 0 ] ) , None ) . unwrap ( ) ;
980+ assert ! (
981+ Arc :: ptr_eq( taken. as_dictionary:: <Int32Type >( ) . values( ) , & values) ,
982+ "take must not copy the values array"
983+ ) ;
984+
985+ let mut col = utf8_col ( ) ;
986+ col. vectorized_append ( & batch, & [ 0 , 1 , 2 ] ) . unwrap ( ) ;
987+ let slot_b = col. val_to_inner [ 1 ] ;
988+ col. vectorized_append ( & taken, & [ 0 , 1 ] ) . unwrap ( ) ;
989+
990+ assert_eq ! ( col. val_to_inner[ 1 ] , slot_b, "cache was rebuilt" ) ;
991+ assert_eq ! ( col. inner. len( ) , 2 ) ;
992+ }
993+
994+ /// A genuinely different values array must rebuild the cache, and equal
995+ /// values across the two arrays must still dedup to one inner slot.
996+ #[ test]
997+ fn distinct_values_arcs_rebuild_cache_but_still_dedup ( ) {
998+ let mut col = utf8_col ( ) ;
999+ let first = i32_dict ( & [ Some ( 0 ) ] , & [ Some ( "a" ) ] ) ;
1000+ let second = i32_dict ( & [ Some ( 0 ) ] , & [ Some ( "a" ) ] ) ;
1001+ col. vectorized_append ( & first, & [ 0 ] ) . unwrap ( ) ;
1002+ col. vectorized_append ( & second, & [ 0 ] ) . unwrap ( ) ;
1003+
1004+ assert ! (
1005+ col. cached_values. as_ref( ) . is_some_and( |c| Arc :: ptr_eq(
1006+ c,
1007+ second. as_dictionary:: <Int32Type >( ) . values( )
1008+ ) ) ,
1009+ "cache should track the most recent values array"
1010+ ) ;
1011+ assert_eq ! ( col. inner. len( ) , 1 , "'a' must dedup across both arrays" ) ;
1012+ assert_eq ! ( col. len( ) , 2 ) ;
1013+ }
1014+
1015+ /// `take_n` remaps inner slots, so the cached `val_idx → inner_slot` map
1016+ /// must not survive it.
1017+ #[ test]
1018+ fn take_n_invalidates_value_cache ( ) {
1019+ let values: ArrayRef = Arc :: new ( StringArray :: from ( vec ! [ Some ( "a" ) , Some ( "b" ) ] ) ) ;
1020+ let mut col = utf8_col ( ) ;
1021+ col. vectorized_append ( & dict_with_values ( & [ Some ( 0 ) , Some ( 1 ) ] , & values) , & [ 0 , 1 ] )
1022+ . unwrap ( ) ;
1023+
1024+ let _emitted = col. take_n ( 1 ) ;
1025+ assert ! (
1026+ col. cached_values. is_none( ) ,
1027+ "take_n remaps inner slots and must drop the cache"
1028+ ) ;
1029+
1030+ col. vectorized_append ( & dict_with_values ( & [ Some ( 0 ) , Some ( 1 ) ] , & values) , & [ 0 , 1 ] )
1031+ . unwrap ( ) ;
1032+
1033+ let out = Box :: new ( col) . build ( ) ;
1034+ let d = out. as_dictionary :: < Int32Type > ( ) ;
1035+ let vals = d. values ( ) . as_string :: < i32 > ( ) ;
1036+ let got: Vec < & str > = d
1037+ . keys ( )
1038+ . iter ( )
1039+ . map ( |k| vals. value ( k. unwrap ( ) as usize ) )
1040+ . collect ( ) ;
1041+ assert_eq ! ( got, vec![ "b" , "a" , "b" ] ) ;
1042+ }
1043+
1044+ /// `append_val` fills `val_hashes` but not `val_to_inner`; mixing it with
1045+ /// `vectorized_append` must not duplicate a value or reuse a stale slot.
1046+ #[ test]
1047+ fn scalar_and_vectorized_append_share_cache_consistently ( ) {
1048+ let values: ArrayRef = Arc :: new ( StringArray :: from ( vec ! [ Some ( "a" ) , Some ( "b" ) ] ) ) ;
1049+ let batch = dict_with_values ( & [ Some ( 0 ) , Some ( 1 ) ] , & values) ;
1050+ let mut col = utf8_col ( ) ;
1051+
1052+ col. append_val ( & batch, 0 ) . unwrap ( ) ;
1053+ assert ! (
1054+ col. cached_values
1055+ . as_ref( )
1056+ . is_some_and( |c| Arc :: ptr_eq( c, & values) )
1057+ ) ;
1058+
1059+ col. vectorized_append ( & batch, & [ 0 , 1 ] ) . unwrap ( ) ;
1060+ assert_eq ! ( col. inner. len( ) , 2 , "'a' must not be duplicated" ) ;
1061+ assert_eq ! ( col. len( ) , 3 ) ;
1062+ }
9211063}
0 commit comments