Skip to content

Commit 622354f

Browse files
perf: reuse cached dictionary value slots in vectorized_equal_to (apache#25652)
## Which issue does this PR close? - Closes apache#25219. ## Rationale for this change Follow-up to apache#25185. `vectorized_equal_to` was left untouched and still rebuilt the same `val_idx -> inner_slot` map from scratch on every batch. ## What changes are included in this PR? - Added `lookup_inner_slot`, which resolves a single `val_idx` to its slot in `inner` and memorizes the result in `val_to_inner`. - Changed `vectorized_equal_to` to call `sync_value_cache` and resolve slots lazily per row. - Removed `build_lookup_table`, the `rhs_rows.len() < num_distinct` guard and `equal_to_per_row`. ## What is the testing strategy for this PR? Covered by the existing `dictionary.rs` unit tests. ## Are there any user-facing changes? No. This is an internal performance change with no public API or behaviour change.
1 parent 1aed7dc commit 622354f

1 file changed

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

Comments
 (0)