Skip to content

Commit b6b2e0e

Browse files
fwojciecjayzhan211
andauthored
fix: keep the hash join build map reserved while the dynamic filter holds it (#26994)
## Which issue does this PR close? - Closes #26980. ## Rationale for this change A `Partitioned` hash join frees its build reservation when the partition's stream ends, but the dynamic filter and the build accumulator keep the build map until the plan is dropped, so a finished join's maps stay allocated while the pool counts them as free. In a query with several stages, later operators reserve the whole pool on top of them, and the process can be killed by the OS instead of failing with `ResourcesExhausted`. #26980 has the cause and the measurements. This takes the first fix direction from the issue: the reservation travels with the map, so the memory stays charged for as long as anything holds the map. This does not reduce memory use or free the maps sooner. A memory-limited query that only fit because a finished join's maps were not counted can now fail with `ResourcesExhausted`, and the finished join then shows up among the top consumers in the error. ## What changes are included in this PR? - `ReservedMap` (`joins/mod.rs`): a `Map` and the reservation its memory is charged to, in one `Arc`. `JoinBuildData`, `PushdownStrategy::Map` and `HashTableLookupExpr` hold it in place of `Arc<Map>`, so every holder of the map holds its charge. - `build_in_memory`: charges the hash table or array map and the pruning bitmap to a reservation created with `new_empty()` from the build reservation, so the consumer name and error text do not change. The batch, key arrays and visited bitmap stay on the build reservation and are released with the stream as before. - `HashTableLookupExpr::new`: keeps its signature and wraps each map without a reservation, for the `datafusion-proto` and `datafusion-pruning` tests. `new_reserved` is the crate-internal constructor the join uses. - `PreparedHashJoinBuild::reserved_bytes`: sums both reservations, so its value is unchanged. Not in this PR: - Releasing the maps once every partition has finished probing, the second fix direction in #26980, frees the memory sooner but changes when the filter is updated, so it is left for a follow-up. I can open an issue for it. - `PushdownStrategy::InList` arrays share the prepared build batch and have the same lifetime gap, bounded by `hash_join_inlist_pushdown_max_size` (128 KiB per partition by default). - *Added after merging #26249:* the hash tables that the routed lookup builds from IN-list partitions (`in_list_hash_map`) and the merged pruning bitmap are not reserved either. The hash tables grow with the IN lists, which the same limit caps, and the bitmap is at most 128 KiB. ## What is the testing strategy for this PR? - `build_map_stays_reserved_with_dynamic_filter` in `hash_join/exec.rs`, over `CollectLeft` and `Partitioned`. After the join's stream is dropped, `pool.reserved()` equals the map plus pruning bitmap bytes (`Partitioned`) or the whole build (`CollectLeft`). After the plan is dropped, the filter is the last holder and both modes equal the map plus bitmap bytes. After the filter is dropped, it is 0. On `main` the `Partitioned` case fails at the first assertion with 0 reserved against 136,288 expected; ~~`CollectLeft` passes on `main` too.~~ *Corrected in review:* `CollectLeft` fails after the plan is dropped, with 0 reserved against 136,288 expected, so the test also covers a filter that outlives the plan. - *Added in review:* `array_map_stays_reserved_with_dynamic_filter`, over the same two modes. Its keys are dense, unlike the first test's, so the build map is an array map without a pruning bitmap. After the plan is dropped, `pool.reserved()` equals the `ArrayMap` estimate; after the filter is dropped, it is 0. On `main` both modes fail after the plan is dropped with 0 reserved against 160,000 expected. With only the `array_map_key_range` argument reverted to the build reservation, this test fails and the other 1,820 `joins::` tests pass. - *Added after merging #26249:* `routed_maps_stay_reserved_with_dynamic_filter` runs the `Partitioned` join over two hash partitions, so the filter is the routed lookup. The maps stay reserved after every stream ends, the amount does not change when the plan is dropped, and it is 0 after the filter is dropped. On `main` nothing is reserved once the streams end. If the routed lookup holds the maps without their reservation, this test fails and no other `joins::` test does. - The test from #26980, run on this branch (not added here: it needs a global allocator): | Run | Allocated after the stream is dropped | Reserved | Reserved on `main` | |---|---|---|---| | 1. `Partitioned`, dynamic filter off | 0.2 MiB | 0.0 MiB | 0.0 MiB | | 2. `Partitioned`, dynamic filter on | 151.5 MiB | 151.3 MiB | 0.0 MiB | | 3. `CollectLeft`, dynamic filter on | 182.0 MiB | 181.8 MiB | 181.8 MiB | Dropping the plan frees everything in all three runs. ## Are there any user-facing changes? No API change; `HashTableLookupExpr::new` is unchanged. Under a memory limit, a query whose finished joins' maps were not counted before can now fail with `ResourcesExhausted`, and spilling operators under the same limit can spill earlier. AI assistance: written with Claude Code (Claude Fable 5.1). I reported the original case, reproduced the issue, reviewed the diff and ran the tests above. --------- Co-authored-by: Jay Zhan <[email protected]>
1 parent c28a6de commit b6b2e0e

5 files changed

Lines changed: 342 additions & 55 deletions

File tree

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

Lines changed: 218 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@ use crate::joins::utils::{
3333
OnceAsync, OnceFut, asymmetric_join_output_partitioning, emits_unmatched_left_rows,
3434
is_existence_join, reorder_output_after_swap, swap_join_projection, update_hash,
3535
};
36-
use crate::joins::{JoinOn, JoinOnRef, PartitionMode, SharedBitmapBuilder};
36+
use crate::joins::{JoinOn, JoinOnRef, PartitionMode, ReservedMap, SharedBitmapBuilder};
3737
use crate::metrics::{Count, MetricBuilder, MetricCategory};
3838
use crate::projection::{
3939
EmbeddedProjection, JoinData, ProjectionExec, try_embed_projection,
@@ -191,8 +191,9 @@ fn array_map_key_range(
191191

192192
/// Immutable build buffers and their durable reservation.
193193
struct JoinBuildData {
194-
/// Hash table with row indices into `batch`, also shared with dynamic filters.
195-
map: Arc<Map>,
194+
/// Hash table with row indices into `batch`, charged to its own
195+
/// reservation because it is also shared with dynamic filters.
196+
map: Arc<ReservedMap>,
196197
/// The input rows for the build side.
197198
batch: RecordBatch,
198199
/// Evaluated build-side key expressions, with float `-0.0` rewritten to
@@ -3189,13 +3190,16 @@ fn build_in_memory(
31893190
) -> Result<JoinLeftData> {
31903191
let is_phj_candidate = is_perfect_hash_join_candidate(on_left, schema)?;
31913192

3193+
// Bound before the map so error paths release the map before its charge.
3194+
let mut map_reservation = reservation.new_empty();
3195+
31923196
let (join_hash_map, batch, left_values) = if let Some((min_val, max_val)) =
31933197
array_map_key_range(
31943198
bounds.as_ref(),
31953199
schema,
31963200
batches,
31973201
on_left,
3198-
&mut reservation,
3202+
&mut map_reservation,
31993203
config.execution.perfect_hash_join_small_build_threshold,
32003204
config.execution.perfect_hash_join_min_key_density,
32013205
null_equality,
@@ -3218,7 +3222,7 @@ fn build_in_memory(
32183222
// Use `u32` indices for the JoinHashMap when num_rows ≤ u32::MAX, otherwise use the
32193223
// `u64` indice variant
32203224
// Arc is used instead of Box to allow sharing with SharedBuildAccumulator for hash map pushdown
3221-
let mut hashmap = new_join_hashmap(num_rows, &mut reservation, metrics)?;
3225+
let mut hashmap = new_join_hashmap(num_rows, &mut map_reservation, metrics)?;
32223226

32233227
let scratch_reservation = reservation.new_empty();
32243228
if prepared {
@@ -3314,7 +3318,7 @@ fn build_in_memory(
33143318
})
33153319
.transpose()?;
33163320

3317-
let map = Arc::new(join_hash_map);
3321+
let map = Arc::new(ReservedMap::new(join_hash_map, map_reservation));
33183322

33193323
// For an ordinary build, nothing reads the strategy unless this join's own
33203324
// dynamic filter accumulator exists. A prepared build is shared with joins
@@ -3358,10 +3362,10 @@ fn build_in_memory(
33583362
.map(Arc::new),
33593363
_ => None,
33603364
};
3361-
// Held for the join's lifetime, so charge it like the maps; it is
3362-
// optional, so skip it rather than fail when the pool is full.
3365+
// Shared with the map, so charge it with the map; it is optional,
3366+
// so skip it rather than fail when the pool is full.
33633367
let pruning_bitmap = pruning_bitmap.filter(|bitmap| {
3364-
let ok = reservation.try_grow(bitmap.size()).is_ok();
3368+
let ok = map.try_grow(bitmap.size()).is_ok();
33653369
if ok {
33663370
metrics.build_mem_used.add(bitmap.size());
33673371
}
@@ -3541,14 +3545,21 @@ mod tests {
35413545
Ok(())
35423546
}
35433547

3544-
/// Runs a join whose 200 keys spread over 2M would size a pruning bitmap
3545-
/// at the 128 KiB cap, and reports the bytes the build side reserved.
3546-
///
3547-
/// Forces the IN-list threshold off: under `force_hash_collisions` every
3548-
/// key hashes to the same bucket, so `num_of_distinct_key()` no longer
3549-
/// reflects the real 200 distinct keys and would otherwise take the
3550-
/// IN-list branch instead of the one under test.
3551-
async fn build_mem_used(limit: usize, dynamic_filters: bool) -> Result<usize> {
3548+
/// 200 keys spread over 2M: sparse enough for a hash map rather than an
3549+
/// array map, and sizing a pruning bitmap at the 128 KiB cap.
3550+
fn sparse_keys() -> Vec<i64> {
3551+
(0..200).map(|i| i * 10_000).collect()
3552+
}
3553+
3554+
/// A build side of [`sparse_keys`], a probe side with three of them, and
3555+
/// the join keys.
3556+
struct SparseKeyJoinInputs {
3557+
build: Arc<dyn ExecutionPlan>,
3558+
probe: Arc<dyn ExecutionPlan>,
3559+
on: JoinOn,
3560+
}
3561+
3562+
fn sparse_key_join_inputs() -> Result<SparseKeyJoinInputs> {
35523563
let schema = Arc::new(Schema::new(vec![Field::new("k", DataType::Int64, false)]));
35533564
let batch = |keys: Vec<i64>| {
35543565
let column = Arc::new(Int64Array::from(keys)) as ArrayRef;
@@ -3559,8 +3570,22 @@ mod tests {
35593570
Arc::new(Column::new_with_schema("k", &schema)?) as _,
35603571
Arc::new(Column::new_with_schema("k", &schema)?) as _,
35613572
)];
3562-
let build = batch((0..200).map(|i| i * 10_000).collect())?;
3563-
let probe = batch(vec![0, 500_000, 1_500_000])?;
3573+
Ok(SparseKeyJoinInputs {
3574+
build: batch(sparse_keys())?,
3575+
probe: batch(vec![0, 500_000, 1_500_000])?,
3576+
on,
3577+
})
3578+
}
3579+
3580+
/// Runs a join over [`sparse_key_join_inputs`] and reports the bytes the
3581+
/// build side reserved.
3582+
///
3583+
/// Forces the IN-list threshold off: under `force_hash_collisions` every
3584+
/// key hashes to the same bucket, so `num_of_distinct_key()` no longer
3585+
/// reflects the real 200 distinct keys and would otherwise take the
3586+
/// IN-list branch instead of the one under test.
3587+
async fn build_mem_used(limit: usize, dynamic_filters: bool) -> Result<usize> {
3588+
let SparseKeyJoinInputs { build, probe, on } = sparse_key_join_inputs()?;
35643589
let join = if dynamic_filters {
35653590
hash_join_with_dynamic_filter(build, probe, on, JoinType::Inner)?.0
35663591
} else {
@@ -3606,6 +3631,180 @@ mod tests {
36063631
Ok(())
36073632
}
36083633

3634+
/// The dynamic filter shares the build map and can outlive the join's
3635+
/// stream and plan, so the map stays reserved until the last holder drops
3636+
/// it, not only until the partition's stream ends.
3637+
#[rstest]
3638+
#[tokio::test]
3639+
async fn build_map_stays_reserved_with_dynamic_filter(
3640+
#[values(PartitionMode::CollectLeft, PartitionMode::Partitioned)]
3641+
mode: PartitionMode,
3642+
) -> Result<()> {
3643+
let SparseKeyJoinInputs { build, probe, on } = sparse_key_join_inputs()?;
3644+
let (join, filter) = hash_join_with_dynamic_filter_and_mode(
3645+
build,
3646+
probe,
3647+
on,
3648+
JoinType::Inner,
3649+
mode,
3650+
)?;
3651+
let join: Arc<dyn ExecutionPlan> = Arc::new(join);
3652+
3653+
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1 << 20));
3654+
let runtime = RuntimeEnvBuilder::new()
3655+
.with_memory_pool(Arc::clone(&pool))
3656+
.build_arc()?;
3657+
let mut config = SessionConfig::new();
3658+
config
3659+
.options_mut()
3660+
.optimizer
3661+
.hash_join_inlist_pushdown_max_size = 0;
3662+
let task_ctx = Arc::new(
3663+
TaskContext::default()
3664+
.with_runtime(runtime)
3665+
.with_session_config(config),
3666+
);
3667+
let batches = common::collect(join.execute(0, task_ctx)?).await?;
3668+
assert_eq!(batches.iter().map(|b| b.num_rows()).sum::<usize>(), 3);
3669+
3670+
let build_mem_used = join
3671+
.metrics()
3672+
.unwrap()
3673+
.sum_by_name("build_mem_used")
3674+
.unwrap()
3675+
.as_usize();
3676+
let keys = sparse_keys();
3677+
let map_bytes =
3678+
estimate_memory_size::<(u32, u64)>(keys.len(), size_of::<JoinHashMapU32>())?
3679+
+ keys.len() * size_of::<u32>();
3680+
let keys_array: ArrayRef = Arc::new(Int64Array::from(keys.clone()));
3681+
let bitmap_bytes = KeyRangeBitmap::try_new(
3682+
&keys_array,
3683+
&ScalarValue::Int64(Some(0)),
3684+
&ScalarValue::Int64(Some(keys[keys.len() - 1])),
3685+
keys.len(),
3686+
)
3687+
.map_or(0, |bitmap| bitmap.size());
3688+
let expected = match mode {
3689+
// The stream is gone; only the map and its bitmap are still held.
3690+
PartitionMode::Partitioned => map_bytes + bitmap_bytes,
3691+
PartitionMode::CollectLeft => build_mem_used,
3692+
PartitionMode::Auto => unreachable!(),
3693+
};
3694+
assert_eq!(pool.reserved(), expected);
3695+
3696+
// The filter is the last holder.
3697+
drop(join);
3698+
assert_eq!(pool.reserved(), map_bytes + bitmap_bytes);
3699+
drop(filter);
3700+
assert_eq!(pool.reserved(), 0);
3701+
Ok(())
3702+
}
3703+
3704+
/// Dense keys build an `ArrayMap`, which is charged to the map's own
3705+
/// reservation in `array_map_key_range` rather than the build's.
3706+
#[rstest]
3707+
#[tokio::test]
3708+
async fn array_map_stays_reserved_with_dynamic_filter(
3709+
#[values(PartitionMode::CollectLeft, PartitionMode::Partitioned)]
3710+
mode: PartitionMode,
3711+
) -> Result<()> {
3712+
let schema = Arc::new(Schema::new(vec![Field::new("k", DataType::Int64, false)]));
3713+
let batch = |keys: Vec<i64>| {
3714+
let column = Arc::new(Int64Array::from(keys)) as ArrayRef;
3715+
let batch = RecordBatch::try_new(Arc::clone(&schema), vec![column])?;
3716+
TestMemoryExec::try_new_exec(&[vec![batch]], Arc::clone(&schema), None)
3717+
};
3718+
let on = vec![(
3719+
Arc::new(Column::new_with_schema("k", &schema)?) as _,
3720+
Arc::new(Column::new_with_schema("k", &schema)?) as _,
3721+
)];
3722+
let (join, filter) = hash_join_with_dynamic_filter_and_mode(
3723+
batch((0..20_000).collect())?,
3724+
batch(vec![0, 5, 15])?,
3725+
on,
3726+
JoinType::Inner,
3727+
mode,
3728+
)?;
3729+
let join: Arc<dyn ExecutionPlan> = Arc::new(join);
3730+
3731+
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1 << 22));
3732+
let runtime = RuntimeEnvBuilder::new()
3733+
.with_memory_pool(Arc::clone(&pool))
3734+
.build_arc()?;
3735+
let mut config = SessionConfig::new();
3736+
config
3737+
.options_mut()
3738+
.optimizer
3739+
.hash_join_inlist_pushdown_max_size = 0;
3740+
let task_ctx = Arc::new(
3741+
TaskContext::default()
3742+
.with_runtime(runtime)
3743+
.with_session_config(config),
3744+
);
3745+
let batches = common::collect(join.execute(0, task_ctx)?).await?;
3746+
assert_eq!(batches.iter().map(|b| b.num_rows()).sum::<usize>(), 3);
3747+
assert_phj_used(&join.metrics().unwrap(), true);
3748+
3749+
drop(join);
3750+
assert_eq!(
3751+
pool.reserved(),
3752+
ArrayMap::estimate_memory_size(0, 19_999, 20_000)
3753+
);
3754+
drop(filter);
3755+
assert_eq!(pool.reserved(), 0);
3756+
Ok(())
3757+
}
3758+
3759+
/// With rows in more than one build partition, the filter is a routed lookup
3760+
/// that holds every partition's map, so the maps stay reserved until it is
3761+
/// dropped.
3762+
#[cfg(not(feature = "force_hash_collisions"))]
3763+
#[tokio::test]
3764+
async fn routed_maps_stay_reserved_with_dynamic_filter() -> Result<()> {
3765+
let SparseKeyJoinInputs { build, probe, on } = sparse_key_join_inputs()?;
3766+
let repartition = |input: Arc<dyn ExecutionPlan>, key: &PhysicalExprRef| {
3767+
let partitioning = Partitioning::Hash(vec![Arc::clone(key)], 2);
3768+
RepartitionExec::try_new(input, partitioning)
3769+
};
3770+
let (join, filter) = hash_join_with_dynamic_filter_and_mode(
3771+
Arc::new(repartition(build, &on[0].0)?),
3772+
Arc::new(repartition(probe, &on[0].1)?),
3773+
on,
3774+
JoinType::Inner,
3775+
PartitionMode::Partitioned,
3776+
)?;
3777+
let join: Arc<dyn ExecutionPlan> = Arc::new(join);
3778+
3779+
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1 << 20));
3780+
let runtime = RuntimeEnvBuilder::new()
3781+
.with_memory_pool(Arc::clone(&pool))
3782+
.build_arc()?;
3783+
let mut config = SessionConfig::new();
3784+
config
3785+
.options_mut()
3786+
.optimizer
3787+
.hash_join_inlist_pushdown_max_size = 0;
3788+
let task_ctx = Arc::new(
3789+
TaskContext::default()
3790+
.with_runtime(runtime)
3791+
.with_session_config(config),
3792+
);
3793+
let batches = crate::execution_plan::collect(Arc::clone(&join), task_ctx).await?;
3794+
assert_eq!(batches.iter().map(|b| b.num_rows()).sum::<usize>(), 3);
3795+
assert!(format!("{:?}", filter.current()?).contains("routed by"));
3796+
3797+
// Every stream is gone; only the maps and their bitmaps are still held.
3798+
let reserved = pool.reserved();
3799+
assert!(reserved > 0);
3800+
// The filter is the last holder.
3801+
drop(join);
3802+
assert_eq!(pool.reserved(), reserved);
3803+
drop(filter);
3804+
assert_eq!(pool.reserved(), 0);
3805+
Ok(())
3806+
}
3807+
36093808
#[derive(Debug)]
36103809
struct PartitionedTestExec {
36113810
cache: Arc<PlanProperties>,

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

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,7 @@ impl fmt::Debug for PreparedHashJoinBuild {
4545
impl PreparedHashJoinBuild {
4646
/// Return the retained build reservation, excluding all per-probe state.
4747
pub fn reserved_bytes(&self) -> usize {
48-
self.build.reservation.size()
48+
self.build.reservation.size() + self.build.map.reserved_bytes()
4949
}
5050

5151
/// Return the complete build row count, including duplicate and null keys.
@@ -290,8 +290,8 @@ impl HashJoinExecBuilder {
290290
/// executions. An existing expression handle is preserved for its probe
291291
/// consumers, while the build-report accumulator is reset.
292292
/// * Retain a prepared-build lease if a dynamic-filter expression outlives
293-
/// this plan. Its array/map references preserve allocation lifetime, but
294-
/// the lease is what preserves the corresponding memory charge.
293+
/// this plan. The map carries its own charge, but the IN-list arrays
294+
/// share the build batch, and the lease is what preserves their charge.
295295
/// * Attach after physical optimizations that rewrite the build child.
296296
/// Probe-only rewrites must preserve the attached join's `left()`; replacing
297297
/// it or making incompatible key, mode, or join-type changes fails.

0 commit comments

Comments
 (0)