Skip to content

Commit 401b3ee

Browse files
committed
fix(repartition): account dictionary hash cache
1 parent 747baf5 commit 401b3ee

2 files changed

Lines changed: 127 additions & 33 deletions

File tree

‎datafusion/common/src/hash_utils.rs‎

Lines changed: 58 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -39,7 +39,8 @@ type DictionaryHashEntry = (Weak<dyn Array>, Vec<u64>);
3939
pub struct CachingArrayHasher {
4040
/// Stored with the cache so value hashes cannot cross hash seeds.
4141
random_state: RandomState,
42-
/// One entry per column. Weak identity avoids retaining dictionary values.
42+
/// One entry per column. Weak identity avoids retaining dictionary values,
43+
/// and keeps their allocation reserved so a new `Arc` can't reuse the address.
4344
dictionaries: Vec<Option<DictionaryHashEntry>>,
4445
}
4546

@@ -117,9 +118,9 @@ impl CachingArrayHasher {
117118
.take()
118119
.map(|(_, hashes)| hashes)
119120
.unwrap_or_default();
120-
hashes.resize(values.len(), 0);
121121
// Fresh hashing leaves null value slots unchanged.
122-
hashes.fill(0);
122+
hashes.clear();
123+
hashes.resize(values.len(), 0);
123124
hash_single_array(
124125
values.as_ref(),
125126
&self.random_state,
@@ -148,6 +149,11 @@ impl CachingArrayHasher {
148149
Some((values.upgrade()?, hashes))
149150
}
150151

152+
/// Drops all cached value hashes. Later batches rehash and refill the cache.
153+
pub fn clear(&mut self) {
154+
self.dictionaries.fill(None);
155+
}
156+
151157
/// Returns the allocated size of the cache.
152158
pub fn size(&self) -> usize {
153159
self.dictionaries.capacity() * size_of::<Option<DictionaryHashEntry>>()
@@ -1525,11 +1531,9 @@ mod tests {
15251531
hasher: &CachingArrayHasher,
15261532
column_index: usize,
15271533
expected_values: &ArrayRef,
1528-
) -> *const u64 {
1529-
let (cached_values, value_hashes) =
1530-
hasher.dictionary_hashes(column_index).unwrap();
1534+
) {
1535+
let (cached_values, _) = hasher.dictionary_hashes(column_index).unwrap();
15311536
assert!(Arc::ptr_eq(&cached_values, expected_values));
1532-
value_hashes.as_ptr()
15331537
}
15341538

15351539
#[cfg(not(feature = "force_hash_collisions"))]
@@ -1546,7 +1550,7 @@ mod tests {
15461550
assert_hashes_match(&mut hasher, &first_batch, &random_state)?;
15471551

15481552
assert!(hasher.dictionary_hashes(0).is_none());
1549-
let value_hash_allocation = assert_cached_values(&hasher, 1, &dictionary_values);
1553+
assert_cached_values(&hasher, 1, &dictionary_values);
15501554

15511555
// A later batch has new plain values and dictionary keys, but shares
15521556
// the dictionary values array and therefore its cached hashes.
@@ -1555,10 +1559,7 @@ mod tests {
15551559
string_dictionary(vec![1, 0], &dictionary_values),
15561560
];
15571561
assert_hashes_match(&mut hasher, &second_batch, &random_state)?;
1558-
assert_eq!(
1559-
assert_cached_values(&hasher, 1, &dictionary_values),
1560-
value_hash_allocation
1561-
);
1562+
assert_cached_values(&hasher, 1, &dictionary_values);
15621563
Ok(())
15631564
}
15641565

@@ -1575,8 +1576,8 @@ mod tests {
15751576
];
15761577
let mut hasher = caching_hasher(&first_batch, &random_state);
15771578
assert_hashes_match(&mut hasher, &first_batch, &random_state)?;
1578-
let country_hash_allocation = assert_cached_values(&hasher, 0, &country_values);
1579-
let status_hash_allocation = assert_cached_values(&hasher, 1, &status_values);
1579+
assert_cached_values(&hasher, 0, &country_values);
1580+
assert_cached_values(&hasher, 1, &status_values);
15801581

15811582
// Aggregation batches can rebuild one dictionary while another group
15821583
// column continues to share its values array.
@@ -1587,14 +1588,8 @@ mod tests {
15871588
string_dictionary(vec![0, 1], &status_values),
15881589
];
15891590
assert_hashes_match(&mut hasher, &second_batch, &random_state)?;
1590-
assert_eq!(
1591-
assert_cached_values(&hasher, 0, &new_country_values),
1592-
country_hash_allocation
1593-
);
1594-
assert_eq!(
1595-
assert_cached_values(&hasher, 1, &status_values),
1596-
status_hash_allocation
1597-
);
1591+
assert_cached_values(&hasher, 0, &new_country_values);
1592+
assert_cached_values(&hasher, 1, &status_values);
15981593
assert_eq!(hasher.dictionary_hashes(0).unwrap().1[1], 0);
15991594

16001595
// Reverse the transition: the first dictionary stays shared while the
@@ -1606,14 +1601,47 @@ mod tests {
16061601
string_dictionary(vec![1, 0], &new_status_values),
16071602
];
16081603
assert_hashes_match(&mut hasher, &third_batch, &random_state)?;
1609-
assert_eq!(
1610-
assert_cached_values(&hasher, 0, &new_country_values),
1611-
country_hash_allocation
1612-
);
1613-
assert_eq!(
1614-
assert_cached_values(&hasher, 1, &new_status_values),
1615-
status_hash_allocation
1616-
);
1604+
assert_cached_values(&hasher, 0, &new_country_values);
1605+
assert_cached_values(&hasher, 1, &new_status_values);
1606+
Ok(())
1607+
}
1608+
1609+
#[cfg(not(feature = "force_hash_collisions"))]
1610+
#[test]
1611+
fn caching_array_hasher_skips_rehash_only_for_same_values_arc() -> Result<()> {
1612+
let random_state = RandomState::with_seed(0);
1613+
let values: ArrayRef = Arc::new(StringArray::from(vec!["a", "b"]));
1614+
let batch = vec![string_dictionary(vec![0, 1], &values)];
1615+
let mut hasher = caching_hasher(&batch, &random_state);
1616+
let mut hashes = vec![0; 2];
1617+
hasher.create_hashes(&batch, &mut hashes)?;
1618+
let fresh = hashes.clone();
1619+
1620+
// Poison the cached hashes: only a cache hit can return the sentinel.
1621+
const SENTINEL: u64 = 0xDEAD_BEEF;
1622+
hasher.dictionaries[0].as_mut().unwrap().1.fill(SENTINEL);
1623+
1624+
let same_arc = vec![string_dictionary(vec![1, 0], &values)];
1625+
hasher.create_hashes(&same_arc, &mut hashes)?;
1626+
assert_eq!(hashes, vec![SENTINEL; 2]);
1627+
1628+
// Equal contents behind a different `Arc` is a miss.
1629+
let equal_values: ArrayRef = Arc::new(StringArray::from(vec!["a", "b"]));
1630+
let new_arc = vec![string_dictionary(vec![0, 1], &equal_values)];
1631+
hasher.create_hashes(&new_arc, &mut hashes)?;
1632+
assert_eq!(hashes, fresh);
1633+
1634+
// A dropped values array must not be matched by a later allocation.
1635+
hasher.dictionaries[0].as_mut().unwrap().1.fill(SENTINEL);
1636+
drop(new_arc);
1637+
drop(equal_values);
1638+
for _ in 0..1000 {
1639+
let reused: ArrayRef = Arc::new(StringArray::from(vec!["a", "b"]));
1640+
let batch = vec![string_dictionary(vec![0, 1], &reused)];
1641+
hasher.create_hashes(&batch, &mut hashes)?;
1642+
assert_eq!(hashes, fresh);
1643+
hasher.dictionaries[0].as_mut().unwrap().1.fill(SENTINEL);
1644+
}
16171645
Ok(())
16181646
}
16191647

‎datafusion/physical-plan/src/repartition/mod.rs‎

Lines changed: 69 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -21,8 +21,6 @@ use super::{
2121
use crate::coalesce::LimitedBatchCoalescer;
2222
use crate::execution_plan::{CardinalityEffect, EvaluationType, SchedulingType};
2323
use crate::hash_utils::CachingArrayHasher;
24-
#[cfg(test)]
25-
use crate::hash_utils::create_hashes;
2624
use crate::metrics::{BaselineMetrics, SpillMetrics};
2725
use crate::projection::{ProjectionExec, all_columns, make_with_child, update_expr};
2826
use crate::sorts::streaming_merge::StreamingMergeBuilder;
@@ -51,7 +49,7 @@ use datafusion_common::{
5149
use datafusion_common::{Result, not_impl_err};
5250
use datafusion_common_runtime::SpawnedTask;
5351
use datafusion_execution::TaskContext;
54-
use datafusion_execution::memory_pool::MemoryConsumer;
52+
use datafusion_execution::memory_pool::{MemoryConsumer, MemoryReservation};
5553
use datafusion_expr::ColumnarValue;
5654
use datafusion_physical_expr::{EquivalenceProperties, PhysicalExpr, RangePartitioning};
5755
use datafusion_physical_expr_common::physical_expr::PhysicalExprRef;
@@ -615,6 +613,8 @@ impl RepartitionExecState {
615613
// preserve_order depends on partition index to start from 0
616614
if preserve_order { 0 } else { i },
617615
num_input_partitions,
616+
MemoryConsumer::new(format!("{name} hash cache[{i}]"))
617+
.register(context.memory_pool()),
618618
));
619619

620620
// In a separate task, wait for each input to be done
@@ -1050,6 +1050,17 @@ impl BatchPartitioner {
10501050
})
10511051
}
10521052

1053+
/// Accounts the retained dictionary hash cache in `reservation`. If the
1054+
/// pool refuses it, drops the cache so later batches pay the uncached cost.
1055+
fn reserve_hash_cache(&mut self, reservation: &MemoryReservation) {
1056+
if let BatchPartitionerState::Hash { hasher, .. } = &mut self.state
1057+
&& reservation.try_resize(hasher.size()).is_err()
1058+
{
1059+
hasher.clear();
1060+
reservation.resize(hasher.size());
1061+
}
1062+
}
1063+
10531064
/// Create a new [`BatchPartitioner`] for round-robin repartitioning.
10541065
///
10551066
/// # Parameters
@@ -2282,6 +2293,7 @@ impl RepartitionExec {
22822293
/// output partitions based on the desired partitioning
22832294
///
22842295
/// `output_channels` holds the output sending channels for each output partition
2296+
#[expect(clippy::too_many_arguments)]
22852297
async fn pull_from_input(
22862298
mut stream: SendableRecordBatchStream,
22872299
mut output_channels: HashMap<usize, OutputChannel>,
@@ -2290,6 +2302,7 @@ impl RepartitionExec {
22902302
metrics: RepartitionMetrics,
22912303
input_partition: usize,
22922304
num_input_partitions: usize,
2305+
hash_cache_reservation: MemoryReservation,
22932306
) -> Result<()> {
22942307
let mut partitioner = match (partitioning, range_router) {
22952308
(Partitioning::Range(range_partitioning), Some(router)) => {
@@ -2348,6 +2361,7 @@ impl RepartitionExec {
23482361
}
23492362
timer.done();
23502363
}
2364+
partitioner.reserve_hash_cache(&hash_cache_reservation);
23512365

23522366
// If the input stream is endless, we may spin forever and
23532367
// never yield back to tokio. See
@@ -2650,6 +2664,7 @@ mod tests {
26502664

26512665
use super::*;
26522666
use crate::empty::EmptyExec;
2667+
use crate::hash_utils::create_hashes;
26532668
use crate::projection::ProjectionExpr;
26542669
use crate::streaming::{PartitionStream, StreamingTableExec};
26552670
use crate::test::TestMemoryExec;
@@ -2837,6 +2852,57 @@ mod tests {
28372852
);
28382853
}
28392854

2855+
#[test]
2856+
fn hash_partitioner_caches_and_reserves_dictionary_hashes() -> Result<()> {
2857+
use datafusion_execution::memory_pool::{GreedyMemoryPool, MemoryPool};
2858+
2859+
let dictionary_type =
2860+
DataType::Dictionary(Box::new(DataType::Int32), Box::new(DataType::Utf8));
2861+
let schema =
2862+
Arc::new(Schema::new(vec![Field::new("key", dictionary_type, true)]));
2863+
let values: ArrayRef = Arc::new(StringArray::from(vec!["a", "bb", "ccc"]));
2864+
let batch = RecordBatch::try_new(
2865+
Arc::clone(&schema),
2866+
vec![Arc::new(DictionaryArray::<Int32Type>::try_new(
2867+
Int32Array::from(vec![0, 1, 2]),
2868+
Arc::clone(&values),
2869+
)?)],
2870+
)?;
2871+
let cached = |partitioner: &BatchPartitioner| {
2872+
let BatchPartitionerState::Hash { hasher, .. } = &partitioner.state else {
2873+
unreachable!()
2874+
};
2875+
(hasher.size(), hasher.dictionary_hashes(0).map(|(v, _)| v))
2876+
};
2877+
2878+
// The pool has room: the cache is kept and reserved.
2879+
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1024));
2880+
let reservation = MemoryConsumer::new("cache").register(&pool);
2881+
let mut partitioner = BatchPartitioner::new_hash_partitioner(
2882+
vec![col("key", &schema)?],
2883+
4,
2884+
metrics::Time::new(),
2885+
)?;
2886+
partitioner
2887+
.partition_iter(batch.clone())?
2888+
.collect::<Result<Vec<_>>>()?;
2889+
partitioner.reserve_hash_cache(&reservation);
2890+
let (size, cached_values) = cached(&partitioner);
2891+
assert!(Arc::ptr_eq(&cached_values.unwrap(), &values));
2892+
assert!(size >= 3 * size_of::<u64>());
2893+
assert_eq!(pool.reserved(), size);
2894+
2895+
// The pool has no room: the cache is dropped, partitioning still works.
2896+
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(8));
2897+
let reservation = MemoryConsumer::new("cache").register(&pool);
2898+
partitioner.reserve_hash_cache(&reservation);
2899+
assert!(cached(&partitioner).1.is_none());
2900+
partitioner
2901+
.partition_iter(batch)?
2902+
.collect::<Result<Vec<_>>>()?;
2903+
Ok(())
2904+
}
2905+
28402906
#[tokio::test]
28412907
async fn one_to_many_round_robin() -> Result<()> {
28422908
// define input partitions

0 commit comments

Comments
 (0)