Skip to content

Commit 43f567a

Browse files
authored
fix: account for hash-join row-index storage (apache#25508)
## Which issue does this PR close? Addresses the shared accounting bug identified while reviewing [apache#25491](apache#25491 (comment)). Split out so it can be reviewed and backported independently of prepared-build reuse. ## Rationale for this change Hash joins reserve memory for their hash buckets, but omit the row-index vector used to link build rows with the same key. As a result, a join can allocate beyond its admitted budget and underreport its build memory. For example, 100 million build rows need an additional 400 MB for this vector that the memory pool currently does not see. ## What changes are included in this PR? The shared hash-map constructor now reserves the bucket estimate and row-index storage together before allocating either, and includes both in the build-memory metric. This covers ordinary CollectLeft and partitioned joins, using four bytes per row for the u32 representation and eight for u64. Perfect-hash array maps keep their existing accounting. ## What is the testing strategy for this PR? A regression gives the constructor one byte less than the complete budget and checks that it refuses the allocation without charging the pool or metric. It also verifies success at the exact limit and release on drop. The test fails against the original constructor and passes with this fix. All 533 hash-join tests, full workspace Clippy with all targets/features and warnings denied, formatting, and whitespace checks pass on this branch. The combined prepared-build branch also passed the extended workspace run with this constructor fix (11,995 Rust tests and 521 SQL test files; eight tests ignored). Local checks used Rust 1.98.1 and temporary source overrides for the requested public releases of Arrow 60.0.0, object_store 0.14.2, sqlparser 0.63.0, and compression-codecs 0.4.42 because the registry mirror lacked them. No dependency or lockfile changes are included. Ordinary-path benchmark comparisons for the combined branch, including the accounting fix, are reported in apache#25491; they are not an isolated performance claim for this fix. ## Are there any user-facing changes? Hash joins using these maps account for their row-index storage in memory limits and build-memory metrics. A budget that previously succeeded only because this allocation was omitted can now be rejected before allocation.
1 parent 0e3c398 commit 43f567a

1 file changed

Lines changed: 48 additions & 2 deletions

File tree

  • datafusion/physical-plan/src/joins/hash_join

‎datafusion/physical-plan/src/joins/hash_join/exec.rs‎

Lines changed: 48 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2797,13 +2797,27 @@ fn new_join_hashmap(
27972797

27982798
if num_rows > u32::MAX as usize {
27992799
let estimated_hashtable_size =
2800-
estimate_memory_size::<(u64, u64)>(num_rows, fixed_size_u64)?;
2800+
estimate_memory_size::<(u64, u64)>(num_rows, fixed_size_u64)?
2801+
// Each build row also owns an index in the duplicate-key chain.
2802+
.checked_add(num_rows * size_of::<u64>())
2803+
.ok_or_else(|| {
2804+
datafusion_common::exec_datafusion_err!(
2805+
"Hash join table size overflow"
2806+
)
2807+
})?;
28012808
reservation.try_grow(estimated_hashtable_size)?;
28022809
metrics.build_mem_used.add(estimated_hashtable_size);
28032810
Ok(Box::new(JoinHashMapU64::with_capacity(num_rows)))
28042811
} else {
28052812
let estimated_hashtable_size =
2806-
estimate_memory_size::<(u32, u64)>(num_rows, fixed_size_u32)?;
2813+
estimate_memory_size::<(u32, u64)>(num_rows, fixed_size_u32)?
2814+
// Each build row also owns an index in the duplicate-key chain.
2815+
.checked_add(num_rows * size_of::<u32>())
2816+
.ok_or_else(|| {
2817+
datafusion_common::exec_datafusion_err!(
2818+
"Hash join table size overflow"
2819+
)
2820+
})?;
28072821
reservation.try_grow(estimated_hashtable_size)?;
28082822
metrics.build_mem_used.add(estimated_hashtable_size);
28092823
Ok(Box::new(JoinHashMapU32::with_capacity(num_rows)))
@@ -3218,6 +3232,38 @@ mod tests {
32183232
use rstest::*;
32193233
use rstest_reuse::*;
32203234

3235+
#[test]
3236+
fn hash_map_admits_row_indices_before_allocation() -> Result<()> {
3237+
use datafusion_execution::memory_pool::{GreedyMemoryPool, MemoryPool};
3238+
3239+
let rows = 1024;
3240+
let buckets =
3241+
estimate_memory_size::<(u32, u64)>(rows, size_of::<JoinHashMapU32>())?;
3242+
let bytes = buckets + rows * size_of::<u32>();
3243+
for (limit, succeeds) in [(bytes - 1, false), (bytes, true)] {
3244+
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(limit));
3245+
let mut reservation = MemoryConsumer::new("row indices").register(&pool);
3246+
let metrics = BuildProbeJoinMetrics::new(0, &ExecutionPlanMetricsSet::new());
3247+
let result = new_join_hashmap(rows, &mut reservation, &metrics);
3248+
if succeeds {
3249+
let map = result?;
3250+
assert_eq!(reservation.size(), bytes);
3251+
assert_eq!(metrics.build_mem_used.value(), bytes);
3252+
drop(map);
3253+
} else {
3254+
assert!(matches!(
3255+
result,
3256+
Err(datafusion_common::DataFusionError::ResourcesExhausted(_))
3257+
));
3258+
assert_eq!(reservation.size(), 0);
3259+
assert_eq!(metrics.build_mem_used.value(), 0);
3260+
}
3261+
drop(reservation);
3262+
assert_eq!(pool.reserved(), 0);
3263+
}
3264+
Ok(())
3265+
}
3266+
32213267
#[derive(Debug)]
32223268
struct PartitionedTestExec {
32233269
cache: Arc<PlanProperties>,

0 commit comments

Comments
 (0)