Skip to content

Commit d0d993d

Browse files
authored
fix: NestedLoopJoinExec emits spurious unmatched-left rows with multiple probe partitions (apache#22791)
## Problem `NestedLoopJoinExec` can return incorrect and non deterministic results for LEFT, RIGHT and FULL joins when the probe side has more than one partition (the common case for any join whose condition is not a pure equijoin). Some unmatched left rows are emitted twice: once correctly and once again as an extra NULL padded row. ## Proof Correct answer is 5 (every t1 row is unmatched). Verify with `target_partitions = 1`. With multiple partitions an unpatched build intermittently returns 6, 7 or 8. Because it is a scheduling race, run it a few times to observe the divergence. ```sql set datafusion.execution.target_partitions = 4; set datafusion.execution.batch_size = 2; create table t1(v bigint) as values (4),(72),(41),(98),(91); create table t2(s varchar, w bigint) as values ('aaaaaaaaaaaaaaaa', 1),('bbbbbbbbbbbbbbbb', 2),('cccccccccccccccc', 3); select count(*) as left_join_rows from t1 left join t2 on (t1.v < t2.w and t2.s <= 'A'); ``` ## Solution The probe streams share a `probe_threads_counter`; the stream that drives it to 0 is the one that emits unmatched left rows, after all partitions finish probing. In `handle_emit_left_unmatched`, after `process_left_unmatched` returns `Ok(false)`, `maybe_flush_ready_batch()` can return early with a ready batch before the state advances to `Done`. The stream stays in `EmitLeftUnmatched`, so the next poll re enters `process_left_unmatched` with `left_emit_idx == 0` and decrements the counter a second time. The counter then reaches 0 before every partition has finished probing, so a partition emits unmatched left rows early. The fix decrements the counter at most once per probe stream using a new `probe_completed_reported` flag (reset per chunk in the memory limited path). All 42 existing `nested_loop_join` tests pass. This is separate from apache#22641, which covers the memory limited spill fallback path; this bug reproduces with unbounded memory and with spilling disabled.
1 parent 8036b94 commit d0d993d

2 files changed

Lines changed: 83 additions & 5 deletions

File tree

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

Lines changed: 39 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1064,6 +1064,17 @@ pub(crate) struct NestedLoopJoinStream {
10641064

10651065
/// Memory-limited spill fallback state. See [`SpillState`] for details.
10661066
spill_state: SpillState,
1067+
1068+
/// Whether this stream has already reported probe completion for the current
1069+
/// left chunk via [`JoinLeftData::report_probe_completed`]. The shared
1070+
/// probe-threads counter must be decremented exactly once per probe stream;
1071+
/// without this guard a stream that yields a ready batch while finishing the
1072+
/// `EmitLeftUnmatched` state (and is then re-polled with `left_emit_idx`
1073+
/// still 0) would decrement the counter twice, driving it to zero
1074+
/// prematurely and causing a sibling partition to emit unmatched-left rows
1075+
/// before all partitions finished probing (spurious NULL-padded rows).
1076+
/// Reset to `false` when starting a new left chunk in memory-limited mode.
1077+
probe_completed_reported: bool,
10671078
}
10681079

10691080
pub(crate) struct NestedLoopJoinMetrics {
@@ -1337,6 +1348,7 @@ impl NestedLoopJoinStream {
13371348
handled_empty_output: false,
13381349
should_track_unmatched_right: need_produce_right_in_final(join_type),
13391350
spill_state,
1351+
probe_completed_reported: false,
13401352
}
13411353
}
13421354

@@ -1863,6 +1875,10 @@ impl NestedLoopJoinStream {
18631875
self.buffered_left_data = None;
18641876
self.left_probe_idx = 0;
18651877
self.left_emit_idx = 0;
1878+
// Each memory-limited chunk gets a fresh per-chunk
1879+
// `JoinLeftData`/counter, so allow this stream to report
1880+
// completion again for the next chunk.
1881+
self.probe_completed_reported = false;
18661882
self.state = NLJState::BufferingLeft;
18671883
} else if self.is_memory_limited()
18681884
&& self.should_track_unmatched_right
@@ -2341,7 +2357,9 @@ impl NestedLoopJoinStream {
23412357
/// true -> continue in the same EmitLeftUnmatched state
23422358
/// false -> next state (Done)
23432359
fn process_left_unmatched(&mut self) -> Result<bool> {
2344-
let left_data = self.get_left_data()?;
2360+
// Clone the shared `Arc<JoinLeftData>` so the immutable borrow of `self`
2361+
// ends here and we can update `self.probe_completed_reported` below.
2362+
let left_data = Arc::clone(self.get_left_data()?);
23452363
let left_batch = left_data.batch();
23462364

23472365
// ========
@@ -2350,9 +2368,25 @@ impl NestedLoopJoinStream {
23502368

23512369
// Early return if join type can't have unmatched rows
23522370
let join_type_no_produce_left = !need_produce_result_in_final(self.join_type);
2353-
// Early return if another thread is already processing unmatched rows
2354-
let handled_by_other_partition =
2355-
self.left_emit_idx == 0 && !left_data.report_probe_completed();
2371+
// Early return if another thread is already processing unmatched rows.
2372+
//
2373+
// The shared probe-threads counter must be decremented exactly once per
2374+
// probe stream. This function can be re-entered with `left_emit_idx`
2375+
// still 0 (e.g. when a ready batch was flushed via an early return in
2376+
// `handle_emit_left_unmatched` before the state advanced), so guard the
2377+
// decrement with `probe_completed_reported` instead of relying solely on
2378+
// `left_emit_idx == 0`. Decrementing twice would drive the counter to
2379+
// zero prematurely and let a partition emit unmatched-left rows before
2380+
// all partitions finished probing, producing spurious NULL-padded rows.
2381+
let handled_by_other_partition = if self.probe_completed_reported {
2382+
// Already counted this stream's completion; if we're the designated
2383+
// emitter we have `left_emit_idx > 0` (or are mid-emit) and continue,
2384+
// otherwise another partition is handling emission.
2385+
self.left_emit_idx == 0
2386+
} else {
2387+
self.probe_completed_reported = true;
2388+
self.left_emit_idx == 0 && !left_data.report_probe_completed()
2389+
};
23562390
// Stop processing unmatched rows, the caller will go to the next state
23572391
let finished = self.left_emit_idx >= left_batch.num_rows();
23582392

@@ -2368,7 +2402,7 @@ impl NestedLoopJoinStream {
23682402
let end_idx = std::cmp::min(start_idx + self.batch_size, left_batch.num_rows());
23692403

23702404
if let Some(batch) =
2371-
self.process_left_unmatched_range(left_data, start_idx, end_idx)?
2405+
self.process_left_unmatched_range(&left_data, start_idx, end_idx)?
23722406
{
23732407
self.output_buffer.push_batch(batch)?;
23742408
}

‎datafusion/sqllogictest/test_files/joins.slt‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5527,3 +5527,47 @@ DROP TABLE t1;
55275527

55285528
statement ok
55295529
DROP TABLE t2;
5530+
5531+
# Regression test for a LEFT JOIN with a non-equijoin predicate (forces
5532+
# NestedLoopJoinExec) and a multi-partition probe side. Previously the unmatched
5533+
# left rows could be emitted before all partitions finished probing, adding
5534+
# spurious NULL-padded rows. The result must include every left row exactly once.
5535+
statement ok
5536+
set datafusion.execution.target_partitions = 4;
5537+
5538+
statement ok
5539+
set datafusion.execution.batch_size = 2;
5540+
5541+
statement ok
5542+
CREATE TABLE nlj_left(id INT, v INT) AS VALUES (1, 4), (2, 72), (3, 41), (4, 98), (5, 91);
5543+
5544+
statement ok
5545+
CREATE TABLE nlj_right(w INT) AS VALUES (49), (58), (83), (3), (76);
5546+
5547+
query III
5548+
SELECT id, v, w FROM nlj_left LEFT JOIN nlj_right ON nlj_left.v < nlj_right.w ORDER BY id, w;
5549+
----
5550+
1 4 49
5551+
1 4 58
5552+
1 4 76
5553+
1 4 83
5554+
2 72 76
5555+
2 72 83
5556+
3 41 49
5557+
3 41 58
5558+
3 41 76
5559+
3 41 83
5560+
4 98 NULL
5561+
5 91 NULL
5562+
5563+
statement ok
5564+
DROP TABLE nlj_left;
5565+
5566+
statement ok
5567+
DROP TABLE nlj_right;
5568+
5569+
statement ok
5570+
set datafusion.execution.target_partitions = 4;
5571+
5572+
statement ok
5573+
reset datafusion.execution.batch_size;

0 commit comments

Comments
 (0)