Skip to content

Commit d49dd6d

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

2 files changed

Lines changed: 167 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: 148 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,27 @@ 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+
240+
/// Whether any group column is dictionary encoded.
241+
has_dictionary: bool,
242+
232243
/// Random state for creating hashes
233244
random_state: RandomState,
234245
}
235246

247+
#[derive(Default)]
248+
struct DictionaryHashCache {
249+
/// Dictionary values these hashes belong to.
250+
values: Option<Weak<dyn Array>>,
251+
/// Hash for each dictionary value.
252+
hashes: Vec<u64>,
253+
/// Number of times values were hashed.
254+
#[cfg(test)]
255+
rebuilds: usize,
256+
}
257+
236258
/// Buffers to store intermediate results in `vectorized_append`
237259
/// and `vectorized_equal_to`, for reducing memory allocation
238260
struct VectorizedOperationBuffers {
@@ -292,6 +314,29 @@ impl VectorizedOperationBuffers {
292314
}
293315
}
294316

317+
impl DictionaryHashCache {
318+
fn update(
319+
&mut self,
320+
values: &ArrayRef,
321+
random_state: &RandomState,
322+
) -> Result<&[u64]> {
323+
let unchanged = self.values.as_ref().is_some_and(|cached| {
324+
std::ptr::addr_eq(cached.as_ptr(), Arc::as_ptr(values))
325+
});
326+
if !unchanged {
327+
self.hashes.clear();
328+
self.hashes.resize(values.len(), 0);
329+
create_hashes([values], random_state, &mut self.hashes)?;
330+
self.values = Some(Arc::downgrade(values));
331+
#[cfg(test)]
332+
{
333+
self.rebuilds += 1;
334+
}
335+
}
336+
Ok(&self.hashes)
337+
}
338+
}
339+
295340
impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
296341
// ========================================================================
297342
// Initialization functions
@@ -301,6 +346,10 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
301346
pub fn try_new(schema: SchemaRef) -> Result<Self> {
302347
let map = HashTable::with_capacity(0);
303348
let group_values = Self::build_group_columns(&schema)?;
349+
let has_dictionary = schema
350+
.fields()
351+
.iter()
352+
.any(|field| matches!(field.data_type(), DataType::Dictionary(_, _)));
304353
Ok(Self {
305354
schema,
306355
map,
@@ -310,10 +359,58 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
310359
map_size: 0,
311360
group_values,
312361
hashes_buffer: Default::default(),
362+
dictionary_hash_cache: Default::default(),
363+
has_dictionary,
313364
random_state: crate::aggregates::AGGREGATION_HASH_SEED,
314365
})
315366
}
316367

368+
fn create_hashes(&mut self, cols: &[ArrayRef], hashes: &mut [u64]) -> Result<()> {
369+
if !self.has_dictionary {
370+
create_hashes(cols, &self.random_state, hashes)?;
371+
return Ok(());
372+
}
373+
374+
self.dictionary_hash_cache
375+
.resize_with(cols.len(), DictionaryHashCache::default);
376+
for (index, (array, cache)) in cols
377+
.iter()
378+
.zip(self.dictionary_hash_cache.iter_mut())
379+
.enumerate()
380+
{
381+
let array = array.as_ref();
382+
if matches!(array.data_type(), DataType::Dictionary(_, _)) {
383+
downcast_dictionary_array! {
384+
array => {
385+
let value_hashes = cache.update(array.values(), &self.random_state)?;
386+
#[cfg(not(feature = "force_hash_collisions"))]
387+
scatter_dictionary_hashes(
388+
array,
389+
value_hashes,
390+
hashes,
391+
index != 0,
392+
);
393+
#[cfg(feature = "force_hash_collisions")]
394+
hash_single_array(
395+
array,
396+
&self.random_state,
397+
hashes,
398+
index != 0,
399+
)?;
400+
self.group_values[index]
401+
.set_dictionary_hashes(array.values(), value_hashes);
402+
},
403+
_ => unreachable!(),
404+
}
405+
} else {
406+
*cache = DictionaryHashCache::default();
407+
hash_single_array(array, &self.random_state, hashes, index != 0)?;
408+
}
409+
}
410+
411+
Ok(())
412+
}
413+
317414
/// Build one fresh [`GroupColumn`] per field in the schema.
318415
///
319416
/// Used at construction time (`try_new`) and to repopulate the column
@@ -383,10 +480,10 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
383480
groups.clear();
384481

385482
// 1.1 Calculate the group keys for the group values
386-
let batch_hashes = &mut self.hashes_buffer;
483+
let mut batch_hashes = mem::take(&mut self.hashes_buffer);
387484
batch_hashes.clear();
388485
batch_hashes.resize(n_rows, 0);
389-
create_hashes(cols, &self.random_state, batch_hashes)?;
486+
self.create_hashes(cols, &mut batch_hashes)?;
390487

391488
for (row, &target_hash) in batch_hashes.iter().enumerate() {
392489
let entry = self
@@ -459,6 +556,8 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
459556
groups.push(group_idx);
460557
}
461558

559+
self.hashes_buffer = batch_hashes;
560+
462561
Ok(())
463562
}
464563

@@ -487,7 +586,7 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
487586
let mut batch_hashes = mem::take(&mut self.hashes_buffer);
488587
batch_hashes.clear();
489588
batch_hashes.resize(n_rows, 0);
490-
create_hashes(cols, &self.random_state, &mut batch_hashes)?;
589+
self.create_hashes(cols, &mut batch_hashes)?;
491590

492591
// General steps for one round `vectorized equal_to & append`:
493592
// 1. Collect vectorized context by checking hash values of `cols` in `map`,
@@ -1103,6 +1202,12 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
11031202
+ self.emit_group_index_list_buffer.allocated_size()
11041203
+ self.vectorized_operation_buffers.size()
11051204
+ self.hashes_buffer.allocated_size()
1205+
+ self.dictionary_hash_cache.allocated_size()
1206+
+ self
1207+
.dictionary_hash_cache
1208+
.iter()
1209+
.map(|cache| cache.hashes.allocated_size())
1210+
.sum::<usize>()
11061211
}
11071212

11081213
fn is_empty(&self) -> bool {
@@ -1247,6 +1352,8 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
12471352
self.map_size = self.map.capacity() * size_of::<(u64, usize)>();
12481353
self.hashes_buffer.clear();
12491354
self.hashes_buffer.shrink_to(num_rows);
1355+
self.dictionary_hash_cache.clear();
1356+
self.dictionary_hash_cache.shrink_to_fit();
12501357

12511358
// Such structures are only used in `non-streaming` case
12521359
if !STREAMING {
@@ -1283,12 +1390,12 @@ mod tests {
12831390
use std::{collections::HashMap, sync::Arc};
12841391

12851392
use arrow::array::{
1286-
Array, ArrayRef, DurationMicrosecondArray, FixedSizeBinaryArray, Float16Array,
1287-
Int32Array, Int64Array, PrimitiveArray, RecordBatch, StringArray,
1393+
Array, ArrayRef, DictionaryArray, DurationMicrosecondArray, FixedSizeBinaryArray,
1394+
Float16Array, Int32Array, Int64Array, PrimitiveArray, RecordBatch, StringArray,
12881395
StringViewArray, UInt32Array,
12891396
};
12901397
use arrow::datatypes::{
1291-
DataType, Decimal32Type, Decimal64Type, Field, Schema, SchemaRef,
1398+
DataType, Decimal32Type, Decimal64Type, Field, Int32Type, Schema, SchemaRef,
12921399
};
12931400
use arrow::{
12941401
compute::{concat_batches, take},
@@ -2112,6 +2219,7 @@ mod tests {
21122219

21132220
let mut gv = GroupValuesColumn::<false>::try_new(Arc::clone(&schema)).unwrap();
21142221
gv.intern(&[labels, categories], &mut vec![]).unwrap();
2222+
assert_eq!(gv.dictionary_hash_cache[1].rebuilds, 1);
21152223
let out = gv.emit(EmitTo::All).unwrap();
21162224

21172225
assert_eq!(out[0].len(), n_groups);
@@ -2124,6 +2232,37 @@ mod tests {
21242232
assert_eq!(out[1].as_dictionary::<Int8Type>().values().len(), 2);
21252233
}
21262234

2235+
#[test]
2236+
fn dictionary_hashes_follow_values_arc() {
2237+
let schema = Arc::new(Schema::new(vec![Field::new(
2238+
"category",
2239+
DataType::Dictionary(Box::new(DataType::Int32), Box::new(DataType::Utf8)),
2240+
true,
2241+
)]));
2242+
let values: ArrayRef = Arc::new(StringArray::from(vec![Some("a"), None::<&str>]));
2243+
let batch = |keys, values| -> ArrayRef {
2244+
Arc::new(DictionaryArray::<Int32Type>::new(
2245+
Int32Array::from(keys),
2246+
values,
2247+
))
2248+
};
2249+
let first = batch(vec![Some(0), Some(1), None], Arc::clone(&values));
2250+
let second = batch(vec![Some(1), Some(0)], Arc::clone(&values));
2251+
let replacement_values: ArrayRef =
2252+
Arc::new(StringArray::from(vec![Some("a"), None::<&str>]));
2253+
let replacement = batch(vec![Some(0), Some(1)], replacement_values);
2254+
let mut group_values = GroupValuesColumn::<false>::try_new(schema).unwrap();
2255+
2256+
let mut first_groups = vec![];
2257+
group_values.intern(&[first], &mut first_groups).unwrap();
2258+
group_values.intern(&[second], &mut vec![]).unwrap();
2259+
assert_eq!(group_values.dictionary_hash_cache[0].rebuilds, 1);
2260+
2261+
group_values.intern(&[replacement], &mut vec![]).unwrap();
2262+
assert_eq!(group_values.dictionary_hash_cache[0].rebuilds, 2);
2263+
assert_eq!(first_groups[1], first_groups[2]);
2264+
}
2265+
21272266
#[test]
21282267
fn test_intern_for_vectorized_group_values() {
21292268
let data_set = VectorizedTestDataSet::new();

0 commit comments

Comments
 (0)