@@ -232,6 +232,42 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> DictionaryGroupValuesColumn<K> {
232232 }
233233 }
234234
235+ /// Compares the value at `val_idx` against `inner[lhs_slot]` directly,
236+ /// memorizing `lhs_slot` in `val_to_inner` when they are equal.
237+ ///
238+ /// Each distinct value occupies exactly one slot in `inner`, so an equal
239+ /// comparison proves `lhs_slot` is the slot for `val_idx` without probing
240+ /// `value_dedup` or hashing. An unequal result is deliberately not
241+ /// memoized: it says which slot the value is *not* in, not which one it
242+ /// is. That is what keeps `val_to_inner` fill-only and never stale.
243+ ///
244+ /// Callers must have run [`Self::sync_value_cache`] for `dict_values`.
245+ ///
246+ /// Only called on a `val_to_inner` miss. It takes the fields it needs
247+ /// rather than `&mut self`, so the caller's hot loop can keep its slices
248+ /// of `val_to_inner` and `group_to_inner` in registers across the call.
249+ #[ cold]
250+ #[ inline( never) ]
251+ fn equal_to_uncached (
252+ val_to_inner : & mut [ usize ] ,
253+ inner : & dyn GroupColumn ,
254+ null_array : & ArrayRef ,
255+ dict_values : & ArrayRef ,
256+ val_idx : usize ,
257+ lhs_slot : usize ,
258+ ) -> bool {
259+ let equal = if dict_values. is_null ( val_idx) {
260+ inner. equal_to ( lhs_slot, null_array, 0 )
261+ } else {
262+ inner. equal_to ( lhs_slot, dict_values, val_idx)
263+ } ;
264+
265+ if equal {
266+ val_to_inner[ val_idx] = lhs_slot;
267+ }
268+ equal
269+ }
270+
235271 fn find_or_insert_null ( & mut self ) -> Result < usize > {
236272 if let Some ( slot) = self . null_inner_slot {
237273 return Ok ( slot) ;
@@ -242,38 +278,13 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> DictionaryGroupValuesColumn<K> {
242278 Ok ( slot)
243279 }
244280
245- fn build_lookup_table (
246- & self ,
247- dict_values : & ArrayRef ,
248- val_hashes : & [ u64 ] ,
249- ) -> Vec < usize > {
250- let num_distinct = dict_values. len ( ) ;
251- let mut table = vec ! [ usize :: MAX ; num_distinct + 1 ] ;
252- let inner = & * self . inner ;
253- for val_idx in 0 ..num_distinct {
254- if dict_values. is_null ( val_idx) {
255- table[ val_idx] = self . null_inner_slot . unwrap_or ( usize:: MAX ) ;
256- } else {
257- let hash = val_hashes[ val_idx] ;
258- if let Some ( & ( _, slot) ) =
259- self . value_dedup . find ( hash, |& ( entry_hash, slot) | {
260- entry_hash == hash && inner. equal_to ( slot, dict_values, val_idx)
261- } )
262- {
263- table[ val_idx] = slot;
264- }
265- }
266- }
267- table[ num_distinct] = self . null_inner_slot . unwrap_or ( usize:: MAX ) ;
268- table
269- }
270-
271- /// Per-row fallback for `vectorized_equal_to` used when the number of rows
272- /// to check is smaller than the dictionary cardinality, making the O(D)
273- /// lookup-table build more expensive than direct value comparison.
281+ /// Per-row fallback for `vectorized_equal_to` used when the values array is
282+ /// not cached and the number of rows to check is smaller than the
283+ /// dictionary cardinality, making the O(D) hashing in `sync_value_cache`
284+ /// more expensive than direct value comparison.
274285 ///
275286 /// `#[cold]` + `#[inline(never)]` keeps this code out of the hot
276- /// lookup-table loops in `vectorized_equal_to` so LLVM can pipeline them.
287+ /// `val_to_inner` loops in `vectorized_equal_to` so LLVM can pipeline them.
277288 #[ cold]
278289 #[ inline( never) ]
279290 fn equal_to_per_row (
@@ -348,12 +359,12 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> GroupColumn
348359 let dict = array. as_dictionary :: < K > ( ) ;
349360 let dict_keys = dict. keys ( ) ;
350361 let dict_values = dict. values ( ) ;
351- let num_distinct = dict_values. len ( ) ;
352362
353- // The fallback is in a separate #[cold] function so its code does not
354- // appear inline here and cannot prevent LLVM from pipelining / unrolling
355- // the hot lookup-table loops below.
356- if rhs_rows. len ( ) < num_distinct {
363+ let cached = self
364+ . cached_values
365+ . as_ref ( )
366+ . is_some_and ( |c| Arc :: ptr_eq ( c, dict_values) ) ;
367+ if !cached && rhs_rows. len ( ) < dict_values. len ( ) {
357368 self . equal_to_per_row (
358369 lhs_rows,
359370 dict_values,
@@ -363,44 +374,64 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> GroupColumn
363374 ) ;
364375 return ;
365376 }
377+ self . sync_value_cache ( dict_values) ;
366378
367- let mut val_hashes = vec ! [ 0u64 ; dict_values. len( ) ] ;
368- create_hashes (
369- std:: slice:: from_ref ( dict_values) ,
370- & self . random_state ,
371- & mut val_hashes,
372- )
373- . unwrap ( ) ;
374- let lookup = self . build_lookup_table ( dict_values, & val_hashes) ;
375-
379+ let raw_keys = dict_keys. values ( ) ;
376380 let group_to_inner = self . group_to_inner . as_slice ( ) ;
377-
381+ let val_to_inner = self . val_to_inner . as_mut_slice ( ) ;
382+ let inner = & * self . inner ;
383+ let null_array = & self . null_array ;
384+ let null_inner_slot = self . null_inner_slot ;
378385 if dict_keys. null_count ( ) == 0 {
379386 // No null keys : skip the get_bit guard: we only ever write false,
380387 // so overwriting an already-false bit is a no-op.
381- let raw_keys = dict_keys. values ( ) ;
382388 for ( idx, ( & lhs_row, & rhs_row) ) in
383389 lhs_rows. iter ( ) . zip ( rhs_rows. iter ( ) ) . enumerate ( )
384390 {
385- let rhs_slot = lookup[ raw_keys[ rhs_row] . as_usize ( ) ] ;
386- if rhs_slot == usize:: MAX || group_to_inner[ lhs_row] != rhs_slot {
391+ let val_idx = raw_keys[ rhs_row] . as_usize ( ) ;
392+ let lhs_slot = group_to_inner[ lhs_row] ;
393+ let equal = match val_to_inner[ val_idx] {
394+ usize:: MAX => Self :: equal_to_uncached (
395+ val_to_inner,
396+ inner,
397+ null_array,
398+ dict_values,
399+ val_idx,
400+ lhs_slot,
401+ ) ,
402+ slot => slot == lhs_slot,
403+ } ;
404+ if !equal {
387405 equal_to_results. set_bit ( idx, false ) ;
388406 }
389407 }
390408 } else {
391409 let null_buf = dict_keys. nulls ( ) . unwrap ( ) ;
392- let raw_keys = dict_keys. values ( ) ;
393410 for ( idx, ( & lhs_row, & rhs_row) ) in
394411 lhs_rows. iter ( ) . zip ( rhs_rows. iter ( ) ) . enumerate ( )
395412 {
396413 if equal_to_results. get_bit ( idx) {
397- let val_idx = if null_buf. is_null ( rhs_row) {
398- num_distinct
414+ // A null key is not a position in the values array, so it
415+ // resolves straight to the null slot instead of going
416+ // through `val_to_inner`.
417+ let lhs_slot = group_to_inner[ lhs_row] ;
418+ let equal = if null_buf. is_null ( rhs_row) {
419+ null_inner_slot == Some ( lhs_slot)
399420 } else {
400- raw_keys[ rhs_row] . as_usize ( )
421+ let val_idx = raw_keys[ rhs_row] . as_usize ( ) ;
422+ match val_to_inner[ val_idx] {
423+ usize:: MAX => Self :: equal_to_uncached (
424+ val_to_inner,
425+ inner,
426+ null_array,
427+ dict_values,
428+ val_idx,
429+ lhs_slot,
430+ ) ,
431+ slot => slot == lhs_slot,
432+ }
401433 } ;
402- let rhs_slot = lookup[ val_idx] ;
403- if rhs_slot == usize:: MAX || group_to_inner[ lhs_row] != rhs_slot {
434+ if !equal {
404435 equal_to_results. set_bit ( idx, false ) ;
405436 }
406437 }
@@ -1060,4 +1091,101 @@ mod tests {
10601091 assert_eq ! ( col. inner. len( ) , 2 , "'a' must not be duplicated" ) ;
10611092 assert_eq ! ( col. len( ) , 3 ) ;
10621093 }
1094+
1095+ /// On a cache miss `vectorized_equal_to` compares against the group's own
1096+ /// slot: an equal result proves the slot and is cached, an unequal one
1097+ /// only rules that slot out and must leave the entry unresolved.
1098+ #[ test]
1099+ fn vectorized_equal_to_caches_only_equal_results ( ) {
1100+ let mut col = utf8_col ( ) ;
1101+ col. vectorized_append (
1102+ & i32_dict ( & [ Some ( 0 ) , Some ( 1 ) ] , & [ Some ( "a" ) , Some ( "b" ) ] ) ,
1103+ & [ 0 , 1 ] ,
1104+ )
1105+ . unwrap ( ) ;
1106+ let ( group_a, group_b) = ( 0 , 1 ) ;
1107+ let slot_a = col. group_to_inner [ group_a] ;
1108+ let slot_b = col. group_to_inner [ group_b] ;
1109+
1110+ // A new values array in the opposite order, so `val_idx` != slot.
1111+ // Two rows for two values keeps the per-row fallback out of the way.
1112+ let ( idx_b, idx_a) = ( 0 , 1 ) ;
1113+ let values: ArrayRef = Arc :: new ( StringArray :: from ( vec ! [ Some ( "b" ) , Some ( "a" ) ] ) ) ;
1114+ let a_then_b =
1115+ dict_with_values ( & [ Some ( idx_a as i32 ) , Some ( idx_b as i32 ) ] , & values) ;
1116+
1117+ // "a" vs group a is equal, "b" vs group a is not.
1118+ let mut buf = all_true ( 2 ) ;
1119+ col. vectorized_equal_to ( & [ group_a, group_a] , & a_then_b, & [ 0 , 1 ] , & mut buf) ;
1120+ assert_eq ! ( bool_vec( & buf) , vec![ true , false ] ) ;
1121+ assert_eq ! ( col. val_to_inner[ idx_a] , slot_a) ;
1122+ assert_eq ! (
1123+ col. val_to_inner[ idx_b] ,
1124+ usize :: MAX ,
1125+ "unequal result was cached"
1126+ ) ;
1127+
1128+ // Later, "b" vs group b fills the entry that was left unresolved.
1129+ let only_b = dict_with_values ( & [ Some ( idx_b as i32 ) ] , & values) ;
1130+ let mut buf = all_true ( 1 ) ;
1131+ col. vectorized_equal_to ( & [ group_b] , & only_b, & [ 0 ] , & mut buf) ;
1132+ assert_eq ! ( bool_vec( & buf) , vec![ true ] ) ;
1133+ assert_eq ! ( col. val_to_inner[ idx_b] , slot_b) ;
1134+ }
1135+
1136+ /// A non-null key pointing at a null value and a null key must both
1137+ /// compare equal to the null group, and only the former goes through
1138+ /// `val_to_inner`.
1139+ #[ test]
1140+ fn vectorized_equal_to_matches_null_value_and_null_key_to_null_group ( ) {
1141+ let mut col = utf8_col ( ) ;
1142+ col. vectorized_append ( & i32_dict ( & [ None , Some ( 0 ) ] , & [ Some ( "a" ) ] ) , & [ 0 , 1 ] )
1143+ . unwrap ( ) ;
1144+ let ( null_group, group_a) = ( 0 , 1 ) ;
1145+ let null_slot = col. null_inner_slot . unwrap ( ) ;
1146+
1147+ let idx_null = 0 ;
1148+ let values: ArrayRef = Arc :: new ( StringArray :: from ( vec ! [ None , Some ( "a" ) ] ) ) ;
1149+ let batch = dict_with_values (
1150+ & [ Some ( idx_null as i32 ) , Some ( idx_null as i32 ) , None ] ,
1151+ & values,
1152+ ) ;
1153+
1154+ // null value vs null group, null value vs group a, null key vs null group.
1155+ let mut buf = all_true ( 3 ) ;
1156+ col. vectorized_equal_to (
1157+ & [ null_group, group_a, null_group] ,
1158+ & batch,
1159+ & [ 0 , 1 , 2 ] ,
1160+ & mut buf,
1161+ ) ;
1162+ assert_eq ! ( bool_vec( & buf) , vec![ true , false , true ] ) ;
1163+ assert_eq ! ( col. val_to_inner[ idx_null] , null_slot) ;
1164+ }
1165+
1166+ /// Fewer rows than values in an uncached values array takes the per-row
1167+ /// fallback, which must not rebuild the cache for that array.
1168+ #[ test]
1169+ fn vectorized_equal_to_small_batch_of_new_values_skips_cache_rebuild ( ) {
1170+ let old_values: ArrayRef = Arc :: new ( StringArray :: from ( vec ! [ Some ( "a" ) ] ) ) ;
1171+ let mut col = utf8_col ( ) ;
1172+ col. vectorized_append ( & dict_with_values ( & [ Some ( 0 ) ] , & old_values) , & [ 0 ] )
1173+ . unwrap ( ) ;
1174+ let group_a = 0 ;
1175+
1176+ // One row against three values in an array the cache has not seen.
1177+ let new_values: ArrayRef =
1178+ Arc :: new ( StringArray :: from ( vec ! [ Some ( "x" ) , Some ( "a" ) , Some ( "y" ) ] ) ) ;
1179+ let idx_a = 1 ;
1180+ let only_a = dict_with_values ( & [ Some ( idx_a) ] , & new_values) ;
1181+ let mut buf = all_true ( 1 ) ;
1182+ col. vectorized_equal_to ( & [ group_a] , & only_a, & [ 0 ] , & mut buf) ;
1183+ assert_eq ! ( bool_vec( & buf) , vec![ true ] ) ;
1184+ assert ! (
1185+ col. cached_values
1186+ . as_ref( )
1187+ . is_some_and( |c| Arc :: ptr_eq( c, & old_values) ) ,
1188+ "fallback must leave the cache on the previous values array"
1189+ ) ;
1190+ }
10631191}
0 commit comments