Skip to content

Commit c4910e0

Browse files
authored
fix: refuse memory-limited NestedLoopJoin fallback for left-emission joins with a multi-partition probe side (apache#24675)
## Which issue does this PR close? - Closes apache#22641. ## Rationale for this change The memory-limited fallback returns wrong rows for join types whose final emission reads the visited-left bitmap (LEFT, LEFT SEMI, LEFT ANTI, LEFT MARK) when the probe side has more than one partition. The fallback rebuilds a per-partition `JoinLeftData` per left chunk with `probe_threads_counter == 1` and a per-partition bitmap, so every partition believes it is the last to finish probing and emits its own unmatched set, from a bitmap that only saw its own right rows. Unmatched rows are emitted once per partition, and rows matched only in another partition are emitted as unmatched. Proof, using this file's own `build_table` / `prepare_join_filter` / `multi_partitioned_join_collect` fixtures (4 right partitions) with a 100-byte memory limit versus unbounded: ```rust for join_type in [JoinType::Left, JoinType::LeftAnti] { // unbounded memory -> correct; 100-byte pool -> memory-limited fallback let (_, correct, _) = multi_partitioned_join_collect(left, right, &join_type, Some(filter), ample_ctx).await?; let (_, wrong, _) = multi_partitioned_join_collect(left, right, &join_type, Some(filter), tight_ctx).await?; } // Left: correct=19 memory_limited=49 // LeftAnti: correct=1 memory_limited=31 ``` The existing gate covers only FULL. This extends it to every `need_produce_result_in_final` type, so an over-budget build side fails with `ResourcesExhausted` instead of returning wrong rows. Right-side emission types (RIGHT, RIGHT SEMI, RIGHT ANTI, RIGHT MARK) keep the fallback: each partition owns its right rows exclusively, so their bitmaps are complete per partition. Proper cross-partition coordination of the left bitmap, which would re-enable the fallback for these types, is apache#22038. ## What changes are included in this PR? The `full_join_multi_partition` condition in `NestedLoopJoinExec::execute` becomes `need_produce_result_in_final(self.join_type) && right_partition_count > 1`, with the comment updated to describe the failure mode. `test_overallocation` moves LEFT/LEFT SEMI/LEFT ANTI/LEFT MARK from the succeed-via-fallback group (which collected but never checked the row values) into the must-OOM group alongside FULL. ## Are these changes tested? `test_overallocation` now asserts the `ResourcesExhausted` refusal for all five gated join types with a multi-partition probe side, and still asserts fallback success for Inner and the right-emission types. All 42 `nested_loop_join` tests pass; `./dev/rust_lint.sh` is clean. ## Are there any user-facing changes? Left-family nested loop joins with a multi-partition probe side whose build side exceeds the memory budget now fail with `ResourcesExhausted` instead of returning incorrect results. No API changes.
1 parent d1fc4b3 commit c4910e0

1 file changed

Lines changed: 136 additions & 35 deletions

File tree

‎datafusion/physical-plan/src/joins/nested_loop_join.rs‎

Lines changed: 136 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -658,20 +658,23 @@ impl ExecutionPlan for NestedLoopJoinExec {
658658
// Determine if memory-limited mode is possible.
659659
// Conditions:
660660
// 1. Disk manager supports temp files (needed for spilling).
661-
// 2. FULL join with multiple right partitions is not yet supported
662-
// in the memory-limited path. FULL join needs to track BOTH left-side
663-
// matches (for unmatched left rows) AND right-side matches (for
664-
// unmatched right rows). That path builds a per-partition
665-
// `JoinLeftData` with `probe_threads_counter == 1`, so each
666-
// partition emits unmatched left rows based only on its own
667-
// right-side matches, producing incorrect duplicate output for
668-
// left rows that match in another partition. Other join types
669-
// that need only one-sided final emission (LEFT, LEFT SEMI,
670-
// LEFT ANTI, LEFT MARK) have a similar latent issue in that path.
671-
let full_join_multi_partition =
672-
matches!(self.join_type, JoinType::Full) && right_partition_count > 1;
661+
// 2. Join types whose final emission reads the visited-left bitmap
662+
// (LEFT, LEFT SEMI, LEFT ANTI, LEFT MARK, FULL) need that bitmap
663+
// complete across every probe partition. The memory-limited path
664+
// builds a per-partition `JoinLeftData` with
665+
// `probe_threads_counter == 1`, so with more than one right
666+
// partition each partition emits from a bitmap that only saw its
667+
// own right rows: unmatched rows are emitted once per partition,
668+
// and rows matched only in another partition are emitted as
669+
// unmatched. Refusing the fallback turns those wrong results into
670+
// a plain ResourcesExhausted error. Right-side emission types are
671+
// safe because each partition owns its right rows exclusively.
672+
// Cross-partition coordination of the left bitmap is tracked in
673+
// https://github.com/apache/datafusion/issues/22038.
674+
let left_emission_multi_partition =
675+
need_produce_result_in_final(self.join_type) && right_partition_count > 1;
673676
let can_spill = context.runtime_env().disk_manager.tmp_files_enabled()
674-
&& !full_join_multi_partition;
677+
&& !left_emission_multi_partition;
675678

676679
let build_side_data = self.build_side_data.try_once(|| {
677680
let stream = self.left.execute(0, Arc::clone(&context))?;
@@ -4000,12 +4003,10 @@ pub(crate) mod tests {
40004003

40014004
// Join types that support memory-limited fallback should succeed
40024005
// even under tight memory limits (they spill to disk instead of OOM).
4006+
// Right-side emission types are safe with multiple right partitions
4007+
// because each partition owns its right rows exclusively.
40034008
let fallback_join_types = vec![
40044009
JoinType::Inner,
4005-
JoinType::Left,
4006-
JoinType::LeftSemi,
4007-
JoinType::LeftAnti,
4008-
JoinType::LeftMark,
40094010
JoinType::Right,
40104011
JoinType::RightSemi,
40114012
JoinType::RightAnti,
@@ -4030,24 +4031,34 @@ pub(crate) mod tests {
40304031
.await?;
40314032
}
40324033

4033-
// FULL JOIN with multiple right partitions is intentionally not
4034-
// supported in the fallback path yet (cross-partition left-bitmap
4035-
// coordination is missing). It should still OOM under tight memory.
4036-
let runtime = RuntimeEnvBuilder::new()
4037-
.with_memory_limit(100, 1.0)
4038-
.build_arc()?;
4039-
let task_ctx = TaskContext::default().with_runtime(runtime);
4040-
let task_ctx = Arc::new(task_ctx);
4041-
let err = multi_partitioned_join_collect(
4042-
Arc::clone(&left),
4043-
Arc::clone(&right),
4044-
&JoinType::Full,
4045-
Some(filter.clone()),
4046-
task_ctx,
4047-
)
4048-
.await
4049-
.unwrap_err();
4050-
assert_contains!(err.to_string(), "Resources exhausted");
4034+
// Join types whose final emission reads the visited-left bitmap are
4035+
// intentionally not supported in the fallback path with multiple right
4036+
// partitions (cross-partition left-bitmap coordination is missing;
4037+
// per-partition bitmaps emit wrong rows). They must OOM cleanly instead.
4038+
let gated_join_types = vec![
4039+
JoinType::Left,
4040+
JoinType::LeftSemi,
4041+
JoinType::LeftAnti,
4042+
JoinType::LeftMark,
4043+
JoinType::Full,
4044+
];
4045+
for join_type in &gated_join_types {
4046+
let runtime = RuntimeEnvBuilder::new()
4047+
.with_memory_limit(100, 1.0)
4048+
.build_arc()?;
4049+
let task_ctx = TaskContext::default().with_runtime(runtime);
4050+
let task_ctx = Arc::new(task_ctx);
4051+
let err = multi_partitioned_join_collect(
4052+
Arc::clone(&left),
4053+
Arc::clone(&right),
4054+
join_type,
4055+
Some(filter.clone()),
4056+
task_ctx,
4057+
)
4058+
.await
4059+
.unwrap_err();
4060+
assert_contains!(err.to_string(), "Resources exhausted");
4061+
}
40514062

40524063
Ok(())
40534064
}
@@ -4160,6 +4171,96 @@ pub(crate) mod tests {
41604171
Ok(())
41614172
}
41624173

4174+
#[tokio::test]
4175+
async fn test_nlj_memory_limited_left_semi_join() -> Result<()> {
4176+
let task_ctx = task_ctx_with_memory_limit(50, 16)?;
4177+
let left = build_left_table();
4178+
let right = build_right_table();
4179+
let filter = prepare_join_filter();
4180+
4181+
let (columns, batches, metrics) =
4182+
join_collect(left, right, &JoinType::LeftSemi, Some(filter), task_ctx)
4183+
.await?;
4184+
4185+
assert_eq!(columns, vec!["a1", "b1", "c1"]);
4186+
4187+
assert!(
4188+
metrics.spill_count().unwrap_or(0) > 0,
4189+
"Expected spilling to occur under tight memory limit"
4190+
);
4191+
4192+
// Left semi: only left rows that matched at least one right row.
4193+
allow_duplicates!(assert_snapshot!(batches_to_sort_string(&batches), @r"
4194+
+----+----+----+
4195+
| a1 | b1 | c1 |
4196+
+----+----+----+
4197+
| 5 | 5 | 50 |
4198+
+----+----+----+
4199+
"));
4200+
Ok(())
4201+
}
4202+
4203+
#[tokio::test]
4204+
async fn test_nlj_memory_limited_left_anti_join() -> Result<()> {
4205+
let task_ctx = task_ctx_with_memory_limit(50, 16)?;
4206+
let left = build_left_table();
4207+
let right = build_right_table();
4208+
let filter = prepare_join_filter();
4209+
4210+
let (columns, batches, metrics) =
4211+
join_collect(left, right, &JoinType::LeftAnti, Some(filter), task_ctx)
4212+
.await?;
4213+
4214+
assert_eq!(columns, vec!["a1", "b1", "c1"]);
4215+
4216+
assert!(
4217+
metrics.spill_count().unwrap_or(0) > 0,
4218+
"Expected spilling to occur under tight memory limit"
4219+
);
4220+
4221+
// Left anti: left rows that did NOT match any right row.
4222+
allow_duplicates!(assert_snapshot!(batches_to_sort_string(&batches), @r"
4223+
+----+----+-----+
4224+
| a1 | b1 | c1 |
4225+
+----+----+-----+
4226+
| 11 | 8 | 110 |
4227+
| 9 | 8 | 90 |
4228+
+----+----+-----+
4229+
"));
4230+
Ok(())
4231+
}
4232+
4233+
#[tokio::test]
4234+
async fn test_nlj_memory_limited_left_mark_join() -> Result<()> {
4235+
let task_ctx = task_ctx_with_memory_limit(50, 16)?;
4236+
let left = build_left_table();
4237+
let right = build_right_table();
4238+
let filter = prepare_join_filter();
4239+
4240+
let (columns, batches, metrics) =
4241+
join_collect(left, right, &JoinType::LeftMark, Some(filter), task_ctx)
4242+
.await?;
4243+
4244+
assert_eq!(columns, vec!["a1", "b1", "c1", "mark"]);
4245+
4246+
assert!(
4247+
metrics.spill_count().unwrap_or(0) > 0,
4248+
"Expected spilling to occur under tight memory limit"
4249+
);
4250+
4251+
// Left mark: all left rows with a bool column indicating match.
4252+
allow_duplicates!(assert_snapshot!(batches_to_sort_string(&batches), @r"
4253+
+----+----+-----+-------+
4254+
| a1 | b1 | c1 | mark |
4255+
+----+----+-----+-------+
4256+
| 11 | 8 | 110 | false |
4257+
| 5 | 5 | 50 | true |
4258+
| 9 | 8 | 90 | false |
4259+
+----+----+-----+-------+
4260+
"));
4261+
Ok(())
4262+
}
4263+
41634264
#[tokio::test]
41644265
async fn test_nlj_fits_in_memory_no_spill() -> Result<()> {
41654266
// Use a large memory limit — everything fits, no spilling needed.

0 commit comments

Comments
 (0)