Skip to content

Commit e33ef31

Browse files
committed
perf: reuse cached dictionary value hashes in vectorized_append
1 parent 0da2151 commit e33ef31

1 file changed

Lines changed: 168 additions & 26 deletions

File tree

  • datafusion/physical-plan/src/aggregates/group_values/multi_group_by

‎datafusion/physical-plan/src/aggregates/group_values/multi_group_by/dictionary.rs‎

Lines changed: 168 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -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

Comments
 (0)