Skip to content

Commit e1aa5f4

Browse files
committed
perf: reuse dictionary hashes in aggregation
1 parent 4ede583 commit e1aa5f4

2 files changed

Lines changed: 154 additions & 11 deletions

File tree

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

Lines changed: 19 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -195,16 +195,29 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> DictionaryGroupValuesColumn<K> {
195195
/// array; without this the per-batch cost is O(dictionary cardinality)
196196
/// rather than O(rows). `take_n` remaps `inner` and clears
197197
/// `cached_values`, forcing a rebuild.
198-
fn sync_value_cache(&mut self, dict_values: &ArrayRef) {
198+
fn sync_value_cache_with_hashes(
199+
&mut self,
200+
dict_values: &ArrayRef,
201+
hashes: Option<&[u64]>,
202+
) {
199203
if self.is_cached(dict_values) {
200204
return;
201205
}
202-
self.hash_values(dict_values);
206+
if let Some(hashes) = hashes.filter(|hashes| hashes.len() == dict_values.len()) {
207+
self.val_hashes.clear();
208+
self.val_hashes.extend_from_slice(hashes);
209+
} else {
210+
self.hash_values(dict_values);
211+
}
203212
self.val_to_inner.clear();
204213
self.val_to_inner.resize(dict_values.len(), usize::MAX);
205214
self.cached_values = Some(Arc::downgrade(dict_values));
206215
}
207216

217+
fn sync_value_cache(&mut self, dict_values: &ArrayRef) {
218+
self.sync_value_cache_with_hashes(dict_values, None);
219+
}
220+
208221
fn find_or_insert_value(
209222
&mut self,
210223
dict_values: &ArrayRef,
@@ -351,6 +364,10 @@ impl<K: ArrowDictionaryKeyType + Send + Sync> GroupColumn
351364
self.check_key_overflow()
352365
}
353366

367+
fn set_dictionary_hashes(&mut self, values: &ArrayRef, hashes: &[u64]) {
368+
self.sync_value_cache_with_hashes(values, Some(hashes));
369+
}
370+
354371
fn vectorized_equal_to(
355372
&mut self,
356373
lhs_rows: &[usize],

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

Lines changed: 135 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,7 @@ pub mod primitive;
2929
pub mod row_backed;
3030

3131
use std::mem::{self, size_of};
32-
use std::sync::Arc;
32+
use std::sync::{Arc, Weak};
3333

3434
use crate::aggregates::group_values::GroupValues;
3535
use crate::aggregates::group_values::multi_group_by::{
@@ -45,9 +45,11 @@ use arrow::datatypes::{
4545
BinaryViewType, DataType, Field, Int8Type, Int16Type, Int32Type, Int64Type, Schema,
4646
SchemaRef, StringViewType, UInt8Type, UInt16Type, UInt32Type, UInt64Type,
4747
};
48+
use arrow::downcast_dictionary_array;
4849
use datafusion_common::float_semantics::{has_float_leaf, normalize_floats};
49-
use datafusion_common::hash_utils::RandomState;
50-
use datafusion_common::hash_utils::create_hashes;
50+
#[cfg(not(feature = "force_hash_collisions"))]
51+
use datafusion_common::hash_utils::scatter_dictionary_hashes;
52+
use datafusion_common::hash_utils::{RandomState, create_hashes, hash_single_array};
5153
use datafusion_common::{Result, not_impl_err};
5254
use datafusion_execution::memory_pool::proxy::{HashTableAllocExt, VecAllocExt};
5355
use datafusion_expr::{EmitTo, GroupSelection};
@@ -95,6 +97,9 @@ pub trait GroupColumn: Send + Sync {
9597
/// The vectorized version `append_val`
9698
fn vectorized_append(&mut self, array: &ArrayRef, rows: &[usize]) -> Result<()>;
9799

100+
/// Installs hashes already computed for a dictionary values array.
101+
fn set_dictionary_hashes(&mut self, _values: &ArrayRef, _hashes: &[u64]) {}
102+
98103
/// Returns the number of rows stored in this builder
99104
fn len(&self) -> usize;
100105

@@ -229,10 +234,24 @@ pub struct GroupValuesColumn<const STREAMING: bool> {
229234
/// reused buffer to store hashes
230235
hashes_buffer: Vec<u64>,
231236

237+
/// Cached hashes for dictionary values in each group column.
238+
dictionary_hash_cache: Vec<DictionaryHashCache>,
239+
232240
/// Random state for creating hashes
233241
random_state: RandomState,
234242
}
235243

244+
#[derive(Default)]
245+
struct DictionaryHashCache {
246+
/// Dictionary values these hashes belong to.
247+
values: Option<Weak<dyn Array>>,
248+
/// Hash for each dictionary value.
249+
hashes: Vec<u64>,
250+
/// Number of times values were hashed.
251+
#[cfg(test)]
252+
rebuilds: usize,
253+
}
254+
236255
/// Buffers to store intermediate results in `vectorized_append`
237256
/// and `vectorized_equal_to`, for reducing memory allocation
238257
struct VectorizedOperationBuffers {
@@ -292,6 +311,29 @@ impl VectorizedOperationBuffers {
292311
}
293312
}
294313

314+
impl DictionaryHashCache {
315+
fn update(
316+
&mut self,
317+
values: &ArrayRef,
318+
random_state: &RandomState,
319+
) -> Result<&[u64]> {
320+
let unchanged = self.values.as_ref().is_some_and(|cached| {
321+
std::ptr::addr_eq(cached.as_ptr(), Arc::as_ptr(values))
322+
});
323+
if !unchanged {
324+
self.hashes.clear();
325+
self.hashes.resize(values.len(), 0);
326+
create_hashes([values], random_state, &mut self.hashes)?;
327+
self.values = Some(Arc::downgrade(values));
328+
#[cfg(test)]
329+
{
330+
self.rebuilds += 1;
331+
}
332+
}
333+
Ok(&self.hashes)
334+
}
335+
}
336+
295337
impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
296338
// ========================================================================
297339
// Initialization functions
@@ -310,10 +352,52 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
310352
map_size: 0,
311353
group_values,
312354
hashes_buffer: Default::default(),
355+
dictionary_hash_cache: Default::default(),
313356
random_state: crate::aggregates::AGGREGATION_HASH_SEED,
314357
})
315358
}
316359

360+
fn create_hashes(&mut self, cols: &[ArrayRef], hashes: &mut [u64]) -> Result<()> {
361+
self.dictionary_hash_cache
362+
.resize_with(cols.len(), DictionaryHashCache::default);
363+
for (index, (array, cache)) in cols
364+
.iter()
365+
.zip(self.dictionary_hash_cache.iter_mut())
366+
.enumerate()
367+
{
368+
let array = array.as_ref();
369+
if matches!(array.data_type(), DataType::Dictionary(_, _)) {
370+
downcast_dictionary_array! {
371+
array => {
372+
let value_hashes = cache.update(array.values(), &self.random_state)?;
373+
#[cfg(not(feature = "force_hash_collisions"))]
374+
scatter_dictionary_hashes(
375+
array,
376+
value_hashes,
377+
hashes,
378+
index != 0,
379+
);
380+
#[cfg(feature = "force_hash_collisions")]
381+
hash_single_array(
382+
array,
383+
&self.random_state,
384+
hashes,
385+
index != 0,
386+
)?;
387+
self.group_values[index]
388+
.set_dictionary_hashes(array.values(), value_hashes);
389+
},
390+
_ => unreachable!(),
391+
}
392+
} else {
393+
*cache = DictionaryHashCache::default();
394+
hash_single_array(array, &self.random_state, hashes, index != 0)?;
395+
}
396+
}
397+
398+
Ok(())
399+
}
400+
317401
/// Build one fresh [`GroupColumn`] per field in the schema.
318402
///
319403
/// Used at construction time (`try_new`) and to repopulate the column
@@ -383,10 +467,10 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
383467
groups.clear();
384468

385469
// 1.1 Calculate the group keys for the group values
386-
let batch_hashes = &mut self.hashes_buffer;
470+
let mut batch_hashes = mem::take(&mut self.hashes_buffer);
387471
batch_hashes.clear();
388472
batch_hashes.resize(n_rows, 0);
389-
create_hashes(cols, &self.random_state, batch_hashes)?;
473+
self.create_hashes(cols, &mut batch_hashes)?;
390474

391475
for (row, &target_hash) in batch_hashes.iter().enumerate() {
392476
let entry = self
@@ -459,6 +543,8 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
459543
groups.push(group_idx);
460544
}
461545

546+
self.hashes_buffer = batch_hashes;
547+
462548
Ok(())
463549
}
464550

@@ -487,7 +573,7 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
487573
let mut batch_hashes = mem::take(&mut self.hashes_buffer);
488574
batch_hashes.clear();
489575
batch_hashes.resize(n_rows, 0);
490-
create_hashes(cols, &self.random_state, &mut batch_hashes)?;
576+
self.create_hashes(cols, &mut batch_hashes)?;
491577

492578
// General steps for one round `vectorized equal_to & append`:
493579
// 1. Collect vectorized context by checking hash values of `cols` in `map`,
@@ -1103,6 +1189,12 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
11031189
+ self.emit_group_index_list_buffer.allocated_size()
11041190
+ self.vectorized_operation_buffers.size()
11051191
+ self.hashes_buffer.allocated_size()
1192+
+ self.dictionary_hash_cache.allocated_size()
1193+
+ self
1194+
.dictionary_hash_cache
1195+
.iter()
1196+
.map(|cache| cache.hashes.allocated_size())
1197+
.sum::<usize>()
11061198
}
11071199

11081200
fn is_empty(&self) -> bool {
@@ -1247,6 +1339,8 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
12471339
self.map_size = self.map.capacity() * size_of::<(u64, usize)>();
12481340
self.hashes_buffer.clear();
12491341
self.hashes_buffer.shrink_to(num_rows);
1342+
self.dictionary_hash_cache.clear();
1343+
self.dictionary_hash_cache.shrink_to_fit();
12501344

12511345
// Such structures are only used in `non-streaming` case
12521346
if !STREAMING {
@@ -1283,12 +1377,12 @@ mod tests {
12831377
use std::{collections::HashMap, sync::Arc};
12841378

12851379
use arrow::array::{
1286-
Array, ArrayRef, DurationMicrosecondArray, FixedSizeBinaryArray, Float16Array,
1287-
Int32Array, Int64Array, PrimitiveArray, RecordBatch, StringArray,
1380+
Array, ArrayRef, DictionaryArray, DurationMicrosecondArray, FixedSizeBinaryArray,
1381+
Float16Array, Int32Array, Int64Array, PrimitiveArray, RecordBatch, StringArray,
12881382
StringViewArray, UInt32Array,
12891383
};
12901384
use arrow::datatypes::{
1291-
DataType, Decimal32Type, Decimal64Type, Field, Schema, SchemaRef,
1385+
DataType, Decimal32Type, Decimal64Type, Field, Int32Type, Schema, SchemaRef,
12921386
};
12931387
use arrow::{
12941388
compute::{concat_batches, take},
@@ -2112,6 +2206,7 @@ mod tests {
21122206

21132207
let mut gv = GroupValuesColumn::<false>::try_new(Arc::clone(&schema)).unwrap();
21142208
gv.intern(&[labels, categories], &mut vec![]).unwrap();
2209+
assert_eq!(gv.dictionary_hash_cache[1].rebuilds, 1);
21152210
let out = gv.emit(EmitTo::All).unwrap();
21162211

21172212
assert_eq!(out[0].len(), n_groups);
@@ -2124,6 +2219,37 @@ mod tests {
21242219
assert_eq!(out[1].as_dictionary::<Int8Type>().values().len(), 2);
21252220
}
21262221

2222+
#[test]
2223+
fn dictionary_hashes_follow_values_arc() {
2224+
let schema = Arc::new(Schema::new(vec![Field::new(
2225+
"category",
2226+
DataType::Dictionary(Box::new(DataType::Int32), Box::new(DataType::Utf8)),
2227+
true,
2228+
)]));
2229+
let values: ArrayRef = Arc::new(StringArray::from(vec![Some("a"), None::<&str>]));
2230+
let batch = |keys, values| -> ArrayRef {
2231+
Arc::new(DictionaryArray::<Int32Type>::new(
2232+
Int32Array::from(keys),
2233+
values,
2234+
))
2235+
};
2236+
let first = batch(vec![Some(0), Some(1), None], Arc::clone(&values));
2237+
let second = batch(vec![Some(1), Some(0)], Arc::clone(&values));
2238+
let replacement_values: ArrayRef =
2239+
Arc::new(StringArray::from(vec![Some("a"), None::<&str>]));
2240+
let replacement = batch(vec![Some(0), Some(1)], replacement_values);
2241+
let mut group_values = GroupValuesColumn::<false>::try_new(schema).unwrap();
2242+
2243+
let mut first_groups = vec![];
2244+
group_values.intern(&[first], &mut first_groups).unwrap();
2245+
group_values.intern(&[second], &mut vec![]).unwrap();
2246+
assert_eq!(group_values.dictionary_hash_cache[0].rebuilds, 1);
2247+
2248+
group_values.intern(&[replacement], &mut vec![]).unwrap();
2249+
assert_eq!(group_values.dictionary_hash_cache[0].rebuilds, 2);
2250+
assert_eq!(first_groups[1], first_groups[2]);
2251+
}
2252+
21272253
#[test]
21282254
fn test_intern_for_vectorized_group_values() {
21292255
let data_set = VectorizedTestDataSet::new();

0 commit comments

Comments
 (0)