Skip to content

Commit 14d1378

Browse files
committed
Avoid rehashing shared dictionaries in RepartitionExec
Cache dictionary value hashes per input partition while batches share the same values array. Account retained hashes with the memory pool and fall back to uncached hashing if the reservation is unavailable.
1 parent 5d9b7fd commit 14d1378

2 files changed

Lines changed: 337 additions & 15 deletions

File tree

‎datafusion/common/src/hash_utils.rs‎

Lines changed: 211 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,8 @@ use foldhash::fast::FixedState;
3030
#[cfg(not(feature = "force_hash_collisions"))]
3131
use itertools::Itertools;
3232
use std::hash::{BuildHasher, Hash, Hasher};
33+
#[cfg(not(feature = "force_hash_collisions"))]
34+
use std::sync::{Arc, Weak};
3335

3436
/// [`RandomState`] is optimized for speed and suitable for hash tables and
3537
/// bloom filters. [`QualityRandomState`] is optimized for statistical quality
@@ -679,6 +681,150 @@ fn hash_dictionary<K: ArrowDictionaryKeyType>(
679681
Ok(())
680682
}
681683

684+
#[cfg(not(feature = "force_hash_collisions"))]
685+
#[derive(Default)]
686+
struct DictionaryHashCacheEntry {
687+
/// Weak reference avoids retaining an input dictionary after its batch is released.
688+
values: Option<Weak<dyn Array>>,
689+
/// Hash for each value in `values`.
690+
hashes: Vec<u64>,
691+
/// Number of cache misses, used to verify reuse.
692+
#[cfg(test)]
693+
rebuilds: usize,
694+
}
695+
696+
#[cfg(not(feature = "force_hash_collisions"))]
697+
impl DictionaryHashCacheEntry {
698+
fn sync(&mut self, values: &ArrayRef, random_state: &impl HashState) -> Result<()> {
699+
let is_cached = self.values.as_ref().is_some_and(|cached| {
700+
std::ptr::addr_eq(cached.as_ptr(), Arc::as_ptr(values))
701+
});
702+
if is_cached {
703+
return Ok(());
704+
}
705+
706+
self.values = None;
707+
self.hashes.clear();
708+
self.hashes.resize(values.len(), 0);
709+
create_hashes([values], random_state, &mut self.hashes)?;
710+
#[cfg(test)]
711+
{
712+
self.rebuilds += 1;
713+
}
714+
self.values = Some(Arc::downgrade(values));
715+
Ok(())
716+
}
717+
718+
fn size(&self) -> usize {
719+
self.hashes.capacity() * size_of::<u64>()
720+
}
721+
}
722+
723+
/// Caches dictionary value hashes by column and values array identity.
724+
///
725+
/// Arrow arrays are immutable, so matching [`Arc`] identity is sufficient to
726+
/// reuse the cached hashes.
727+
///
728+
/// This is an internal API used by physical operators that hash multiple batches
729+
/// sharing the same dictionary values.
730+
#[doc(hidden)]
731+
pub struct DictionaryHashCache {
732+
/// Hash state used to build all cached hashes.
733+
random_state: RandomState,
734+
/// One cache entry per hashed column.
735+
#[cfg(not(feature = "force_hash_collisions"))]
736+
entries: Vec<DictionaryHashCacheEntry>,
737+
}
738+
739+
impl DictionaryHashCache {
740+
/// Creates a cache for hashes produced by `random_state`.
741+
pub fn new(random_state: RandomState) -> Self {
742+
Self {
743+
random_state,
744+
#[cfg(not(feature = "force_hash_collisions"))]
745+
entries: Vec::new(),
746+
}
747+
}
748+
749+
/// Hashes `arrays`, reusing dictionary value hashes while their values
750+
/// [`Arc`] remains unchanged.
751+
pub fn create_hashes<'a>(
752+
&mut self,
753+
arrays: &[ArrayRef],
754+
hashes_buffer: &'a mut [u64],
755+
) -> Result<&'a mut [u64]> {
756+
#[cfg(feature = "force_hash_collisions")]
757+
return create_hashes(arrays, &self.random_state, hashes_buffer);
758+
759+
#[cfg(not(feature = "force_hash_collisions"))]
760+
{
761+
if !arrays
762+
.iter()
763+
.any(|array| matches!(array.data_type(), DataType::Dictionary(_, _)))
764+
{
765+
self.entries = Vec::new();
766+
return create_hashes(arrays, &self.random_state, hashes_buffer);
767+
}
768+
769+
self.entries
770+
.resize_with(arrays.len(), DictionaryHashCacheEntry::default);
771+
772+
for (index, array) in arrays.iter().enumerate() {
773+
let rehash = index != 0;
774+
if matches!(array.data_type(), DataType::Dictionary(_, _)) {
775+
let entry = &mut self.entries[index];
776+
let array = array.as_ref();
777+
downcast_dictionary_array! {
778+
array => {
779+
entry.sync(array.values(), &self.random_state)?;
780+
dispatch_dictionary_scatter(
781+
array,
782+
&entry.hashes,
783+
hashes_buffer,
784+
rehash,
785+
);
786+
},
787+
_ => unreachable!()
788+
}
789+
} else {
790+
self.entries[index] = DictionaryHashCacheEntry::default();
791+
hash_single_array(
792+
array.as_ref(),
793+
&self.random_state,
794+
hashes_buffer,
795+
rehash,
796+
)?;
797+
}
798+
}
799+
Ok(hashes_buffer)
800+
}
801+
}
802+
803+
/// Returns the memory retained by cached dictionary value hashes.
804+
pub fn size(&self) -> usize {
805+
#[cfg(feature = "force_hash_collisions")]
806+
return 0;
807+
808+
#[cfg(not(feature = "force_hash_collisions"))]
809+
{
810+
self.entries.capacity() * size_of::<DictionaryHashCacheEntry>()
811+
+ self
812+
.entries
813+
.iter()
814+
.map(DictionaryHashCacheEntry::size)
815+
.sum::<usize>()
816+
}
817+
}
818+
819+
/// Drops all cached hashes.
820+
pub fn clear(&mut self) {
821+
#[cfg(not(feature = "force_hash_collisions"))]
822+
{
823+
self.entries = Vec::new();
824+
}
825+
}
826+
}
827+
682828
#[cfg(not(feature = "force_hash_collisions"))]
683829
fn hash_dictionary_with_child_hashing<K: ArrowDictionaryKeyType>(
684830
array: &DictionaryArray<K>,
@@ -1353,6 +1499,71 @@ mod tests {
13531499

13541500
use super::*;
13551501

1502+
#[cfg(not(feature = "force_hash_collisions"))]
1503+
fn dictionary_array(keys: Vec<Option<i32>>, values: ArrayRef) -> ArrayRef {
1504+
Arc::new(
1505+
DictionaryArray::<Int32Type>::try_new(Int32Array::from(keys), values)
1506+
.unwrap(),
1507+
)
1508+
}
1509+
1510+
#[cfg(not(feature = "force_hash_collisions"))]
1511+
#[test]
1512+
fn dictionary_hash_cache_reuses_and_invalidates_value_hashes() -> Result<()> {
1513+
let values: ArrayRef =
1514+
Arc::new(StringArray::from(vec![Some("a"), None, Some("ccc")]));
1515+
let first =
1516+
dictionary_array(vec![Some(0), Some(2), None, Some(1)], Arc::clone(&values));
1517+
let second =
1518+
dictionary_array(vec![Some(2), Some(0), Some(2), None], Arc::clone(&values));
1519+
let values_strong_count = Arc::strong_count(&values);
1520+
let random_state = RandomState::with_seed(42);
1521+
let mut cache = DictionaryHashCache::new(random_state.clone());
1522+
1523+
for array in [&first, &second] {
1524+
let mut expected = vec![0; array.len()];
1525+
create_hashes([array], &random_state, &mut expected)?;
1526+
let mut actual = vec![0; array.len()];
1527+
cache.create_hashes(std::slice::from_ref(array), &mut actual)?;
1528+
assert_eq!(actual, expected);
1529+
}
1530+
assert_eq!(cache.entries[0].rebuilds, 1);
1531+
assert_eq!(Arc::strong_count(&values), values_strong_count);
1532+
1533+
let replacement_values: ArrayRef =
1534+
Arc::new(StringArray::from(vec![Some("x"), None, Some("zzz")]));
1535+
let replacement =
1536+
dictionary_array(vec![Some(0), Some(2), None, Some(1)], replacement_values);
1537+
let mut expected = vec![0; replacement.len()];
1538+
create_hashes([&replacement], &random_state, &mut expected)?;
1539+
let mut actual = vec![0; replacement.len()];
1540+
cache.create_hashes(&[replacement], &mut actual)?;
1541+
1542+
assert_eq!(actual, expected);
1543+
assert_eq!(cache.entries[0].rebuilds, 2);
1544+
Ok(())
1545+
}
1546+
1547+
#[cfg(not(feature = "force_hash_collisions"))]
1548+
#[test]
1549+
fn dictionary_hash_cache_matches_composite_hashes() -> Result<()> {
1550+
let values: ArrayRef = Arc::new(StringArray::from(vec!["a", "bb", "ccc"]));
1551+
let dictionary = dictionary_array(vec![Some(2), Some(0), Some(1), None], values);
1552+
let primitive: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3, 4]));
1553+
let arrays = [primitive, dictionary];
1554+
let random_state = RandomState::with_seed(42);
1555+
let mut expected = vec![0; arrays[0].len()];
1556+
create_hashes(&arrays, &random_state, &mut expected)?;
1557+
1558+
let mut actual = vec![0; arrays[0].len()];
1559+
let mut cache = DictionaryHashCache::new(random_state);
1560+
cache.create_hashes(&arrays, &mut actual)?;
1561+
1562+
assert_eq!(actual, expected);
1563+
assert_eq!(cache.entries[1].rebuilds, 1);
1564+
Ok(())
1565+
}
1566+
13561567
#[cfg(not(feature = "force_hash_collisions"))]
13571568
#[derive(Default)]
13581569
struct TestHasher(u64);

0 commit comments

Comments
 (0)