Skip to content

Commit 8f279e1

Browse files
perf(aggregate): reuse dictionary hashes and group mappings (apache#26826)
## Which issue does this PR close? Closes apache#26812. ## Rationale for this change Dictionary batches often share one values array while only their keys change. Partial aggregation was rehashing the same dictionary values for every batch. ## What changes are included in this PR? The non-streaming group table now caches dictionary value hashes while the values `Arc` is unchanged. A single dictionary group key can also map known keys directly to group indices. ```text Dictionary batch | v single dictionary column + complete cached mapping? | yes | no v v keys -> cached group IDs per-column hashing | | eligible dictionary fallback | | cached value hashes hash column | | scatter through keys -----+ | v hash/equality group lookup ``` New keys, changed or oversized dictionaries, and partial emission use the normal fallback. Multi-column hashing keeps the same semantics as `create_hashes`. The benchmark fixtures are split into apache#27246. ## What is the testing strategy for this PR? Unit tests cover cached and uncached hash consistency, unseen keys, changed dictionaries, null groups, partial emission, and forced collisions. Hosted cases from apache#27246 show [alternating dictionary-only](apache#26826 (comment)) 1.30× faster; [alternating dictionary + Int32](apache#26826 (comment)) and [fresh dictionaries](apache#26826 (comment)) flat; and [shared dictionary + Int32](apache#26826 (comment)) 1.14× faster at 32K values and 1.28× at 100K. Exact-head hosted suites with RLE dictionary reads enabled on both sides: - [TPC-H](apache#27249 (comment)): 796.01 → 799.79 ms (0.5% higher). - [TPC-DS](apache#27249 (comment)): 9.02 → 8.88 s (1.6% lower). - [ClickBench](apache#27249 (comment)): 38.26 → 38.16 s (0.3% lower). ## Are there any user-facing changes? No. --------- Co-authored-by: Jay Zhan <[email protected]>
1 parent adffd19 commit 8f279e1

3 files changed

Lines changed: 509 additions & 42 deletions

File tree

‎datafusion/common/src/hash_utils.rs‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -670,6 +670,51 @@ fn dispatch_dictionary_scatter<K: ArrowDictionaryKeyType>(
670670
}
671671
}
672672

673+
/// Scatters precomputed dictionary value hashes through `array`'s keys.
674+
///
675+
/// # Public Only for Internal Use:
676+
///
677+
/// This is not a public API and is for internal use only; see [API policy] for details.
678+
///
679+
/// [API policy]: https://datafusion.apache.org/contributor-guide/api-health.html#internal-public-apis
680+
#[doc(hidden)]
681+
#[cfg(not(feature = "force_hash_collisions"))]
682+
pub fn scatter_dictionary_hashes<K: ArrowDictionaryKeyType>(
683+
array: &DictionaryArray<K>,
684+
dict_hashes: &[u64],
685+
hashes_buffer: &mut [u64],
686+
multi_col: bool,
687+
) -> Result<()> {
688+
if dict_hashes.len() != array.values().len() {
689+
return _internal_err!(
690+
"Expected {} dictionary hashes, got {}",
691+
array.values().len(),
692+
dict_hashes.len()
693+
);
694+
}
695+
dispatch_dictionary_scatter(array, dict_hashes, hashes_buffer, multi_col);
696+
Ok(())
697+
}
698+
699+
/// Hashes one column into `hashes_buffer` exactly as [`create_hashes`] does
700+
/// for that column; `rehash` is `true` for every column after the first.
701+
///
702+
/// # Public Only for Internal Use:
703+
///
704+
/// This is not a public API and is for internal use only; see [API policy] for details.
705+
///
706+
/// [API policy]: https://datafusion.apache.org/contributor-guide/api-health.html#internal-public-apis
707+
#[doc(hidden)]
708+
#[cfg(not(feature = "force_hash_collisions"))]
709+
pub fn hash_column(
710+
array: &dyn Array,
711+
random_state: &impl HashState,
712+
hashes_buffer: &mut [u64],
713+
rehash: bool,
714+
) -> Result<()> {
715+
hash_single_array(array, random_state, hashes_buffer, rehash)
716+
}
717+
673718
/// Hash the values in a dictionary array.
674719
#[cfg(not(feature = "force_hash_collisions"))]
675720
fn hash_dictionary<K: ArrowDictionaryKeyType>(

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

Lines changed: 91 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -54,6 +54,11 @@ pub struct DictionaryGroupValuesColumn<K: ArrowDictionaryKeyType + Send + Sync>
5454
/// were built for. A matching live array reuses both caches without
5555
/// retaining an input dictionary after its batch is released.
5656
cached_values: Option<Weak<dyn Array>>,
57+
/// Whether the outer table guarantees each append creates a new group, so
58+
/// inner slots and group indices are identical.
59+
values_are_group_unique: bool,
60+
#[cfg(test)]
61+
hash_builds: usize,
5762
_phantom: PhantomData<K>,
5863
}
5964

@@ -71,6 +76,9 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> DictionaryGroupValuesColumn<K> {
7176
val_to_inner: Vec::default(),
7277
val_hashes: Vec::default(),
7378
cached_values: None,
79+
values_are_group_unique: false,
80+
#[cfg(test)]
81+
hash_builds: 0,
7482
_phantom: PhantomData,
7583
}
7684
}
@@ -157,6 +165,10 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> DictionaryGroupValuesColumn<K> {
157165
}
158166

159167
fn hash_values(&mut self, values: &ArrayRef) {
168+
#[cfg(test)]
169+
{
170+
self.hash_builds += 1;
171+
}
160172
self.cached_values = None;
161173
self.val_hashes.clear();
162174
self.val_hashes.resize(values.len(), 0);
@@ -171,7 +183,8 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> DictionaryGroupValuesColumn<K> {
171183
fn is_cached(&self, values: &ArrayRef) -> bool {
172184
self.cached_values
173185
.as_ref()
174-
.is_some_and(|cached| std::ptr::addr_eq(cached.as_ptr(), Arc::as_ptr(values)))
186+
.and_then(Weak::upgrade)
187+
.is_some_and(|cached| Arc::ptr_eq(&cached, values))
175188
}
176189

177190
/// Makes `val_hashes` and `val_to_inner` correspond to `dict_values`,
@@ -192,6 +205,17 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> DictionaryGroupValuesColumn<K> {
192205
self.cached_values = Some(Arc::downgrade(dict_values));
193206
}
194207

208+
fn insert_value(&mut self, dict_values: &ArrayRef, val_idx: usize) -> Result<usize> {
209+
if self.values_are_group_unique {
210+
let slot = self.group_to_inner.len();
211+
debug_assert_eq!(slot, self.inner.len());
212+
self.inner.append_val(dict_values, val_idx)?;
213+
Ok(slot)
214+
} else {
215+
self.find_or_insert_value(dict_values, val_idx, self.val_hashes[val_idx])
216+
}
217+
}
218+
195219
fn find_or_insert_value(
196220
&mut self,
197221
dict_values: &ArrayRef,
@@ -331,13 +355,61 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> GroupColumn
331355
Some(val_idx) => {
332356
let dict_values = dict.values();
333357
self.sync_value_cache(dict_values);
334-
self.find_or_insert_value(dict_values, val_idx, self.val_hashes[val_idx])?
358+
self.insert_value(dict_values, val_idx)?
335359
}
336360
};
337361
self.group_to_inner.push(inner_slot);
338362
self.check_key_overflow()
339363
}
340364

365+
fn dictionary_hashes<'a>(
366+
&'a mut self,
367+
values: &ArrayRef,
368+
group_unique: bool,
369+
) -> Option<&'a [u64]> {
370+
self.values_are_group_unique = group_unique;
371+
self.sync_value_cache(values);
372+
Some(&self.val_hashes)
373+
}
374+
375+
fn try_map_dictionary_groups(
376+
&self,
377+
array: &ArrayRef,
378+
groups: &mut Vec<usize>,
379+
) -> bool {
380+
if !self.values_are_group_unique {
381+
return false;
382+
}
383+
384+
let dictionary = array.as_dictionary::<K>();
385+
if !self.is_cached(dictionary.values()) {
386+
return false;
387+
}
388+
389+
let keys = dictionary.keys();
390+
let raw_keys = keys.values();
391+
let nulls = keys.nulls();
392+
groups.clear();
393+
for row in 0..dictionary.len() {
394+
let group = if nulls.is_some_and(|nulls| nulls.is_null(row)) {
395+
self.null_inner_slot.unwrap_or(usize::MAX)
396+
} else {
397+
self.val_to_inner[raw_keys[row].as_usize()]
398+
};
399+
if group == usize::MAX {
400+
groups.clear();
401+
return false;
402+
}
403+
groups.push(group);
404+
}
405+
true
406+
}
407+
408+
#[cfg(test)]
409+
fn dictionary_hash_builds(&self) -> usize {
410+
self.hash_builds
411+
}
412+
341413
fn vectorized_equal_to(
342414
&mut self,
343415
lhs_rows: &[usize],
@@ -452,11 +524,7 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> GroupColumn
452524
self.val_to_inner[val_idx] = if dict_values.is_null(val_idx) {
453525
self.find_or_insert_null()?
454526
} else {
455-
self.find_or_insert_value(
456-
dict_values,
457-
val_idx,
458-
self.val_hashes[val_idx],
459-
)?
527+
self.insert_value(dict_values, val_idx)?
460528
};
461529
}
462530
self.group_to_inner.push(self.val_to_inner[val_idx]);
@@ -472,11 +540,7 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> GroupColumn
472540
self.val_to_inner[val_idx] = if dict_values.is_null(val_idx) {
473541
self.find_or_insert_null()?
474542
} else {
475-
self.find_or_insert_value(
476-
dict_values,
477-
val_idx,
478-
self.val_hashes[val_idx],
479-
)?
543+
self.insert_value(dict_values, val_idx)?
480544
};
481545
}
482546
self.val_to_inner[val_idx]
@@ -571,34 +635,28 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> GroupColumn
571635
let emitted: ArrayRef =
572636
Arc::new(DictionaryArray::<K>::new(emitted_keys, compact_emit_values));
573637

574-
// Null deferred to last so null_inner_slot is always the highest index
575-
// and check_key_overflow can subtract it without a false overflow.
638+
// Preserve group order so inner slots remain equal to group indices
639+
// when this is the only grouping column.
576640
let remaining = self.group_to_inner[n..].to_vec();
577641
let mut old_to_new = vec![usize::MAX; old_inner_len];
578642
let mut new_to_old: Vec<usize> = Vec::new();
579-
let mut null_old_slot: Option<usize> = None;
580643
for &old in &remaining {
581-
if all_inner_values.is_null(old) {
582-
if null_old_slot.is_none() {
583-
null_old_slot = Some(old);
584-
}
585-
continue;
586-
}
587644
if old_to_new[old] == usize::MAX {
588645
old_to_new[old] = new_to_old.len();
589646
new_to_old.push(old);
590647
}
591648
}
592-
if let Some(old) = null_old_slot {
593-
old_to_new[old] = new_to_old.len();
594-
new_to_old.push(old);
595-
}
596649

597650
self.value_dedup = HashTable::new();
598651
self.value_dedup_size = 0;
599652
self.null_inner_slot = None;
600653

601-
self.hash_values(&all_inner_values);
654+
if self.values_are_group_unique {
655+
self.cached_values = None;
656+
self.val_hashes.clear();
657+
} else {
658+
self.hash_values(&all_inner_values);
659+
}
602660

603661
for (new_slot, &old_slot) in new_to_old.iter().enumerate() {
604662
if all_inner_values.is_null(old_slot) {
@@ -610,11 +668,13 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> GroupColumn
610668
self.inner
611669
.append_val(&all_inner_values, old_slot)
612670
.expect("append value failed in take_n");
613-
self.value_dedup.insert_accounted(
614-
(self.val_hashes[old_slot], new_slot),
615-
|&(entry_hash, _)| entry_hash,
616-
&mut self.value_dedup_size,
617-
);
671+
if !self.values_are_group_unique {
672+
self.value_dedup.insert_accounted(
673+
(self.val_hashes[old_slot], new_slot),
674+
|&(entry_hash, _)| entry_hash,
675+
&mut self.value_dedup_size,
676+
);
677+
}
618678
}
619679
}
620680

0 commit comments

Comments
 (0)