Skip to content

Commit 16cce96

Browse files
authored
fix: emit deferred unmatched rows when memory-limited NestedLoopJoin exhausts its left side (apache#24746)
## Which issue does this PR close? - Closes apache#24745. ## Rationale for this change A memory-limited `NestedLoopJoinExec` silently returned fewer rows than the same query with an ample memory pool. No error was raised, so the loss is invisible to the caller. In memory-limited mode the left side is processed in chunks and the right side is replayed for each chunk. A per-right-batch match bitmap therefore cannot be emitted as soon as one chunk finishes probing it — a later chunk may still match those rows. The operator already handles this by merging each bitmap into `SpillStateActive::global_right_bitmaps` and deferring emission to `NLJState::EmitGlobalRightUnmatched`, which is reached from `handle_emit_left_unmatched` once the left side is exhausted. `handle_buffering_left` had a separate early exit: ```rust if active.pending_batches.is_empty() { // No data at all — go directly to Done self.left_exhausted = true; self.state = NLJState::Done; return ControlFlow::Continue(()); } ``` Despite the comment, this also fires on the load that follows the final left chunk, when the left side is exhausted and there is nothing more to buffer. Ending the stream there discards the accumulated bitmaps, so every probe-side row that no chunk matched is dropped. Instrumenting a failing `LEFT JOIN` showed 39 bitmap merges and zero emissions, with the completion path only ever running while `left_exhausted` was still `false`. The affected queries reach the operator as swapped join types (`Right`, `RightAnti`, `RightSemi`) or as `Full`, so the rows needing unmatched emission are on the operator's probe side. Measured against an unlimited pool (`l` = 200 rows, `r` = 90 rows, `target_partitions = 1`, `batch_size = 16`, 64-byte pool): | query | ample | memory-limited (before) | | --- | --- | --- | | `NOT EXISTS (... l.v > r.w)` | 2 | 0 | | `LEFT JOIN ... ON l.v > r.w` | 9336 | 9334 | | `FULL JOIN ... ON l.v > r.w` | 9339 | 9337 | `INNER` and explicit `RIGHT JOIN` were already correct. This is pre-existing rather than a regression from apache#24675: that PR only changes the spill gate in the same file, and its condition (`need_produce_result_in_final(join_type) && right_partition_count > 1`) does not cover this path. ## What changes are included in this PR? Route that early exit to `EmitGlobalRightUnmatched` instead of `Done` when the join tracks unmatched probe-side rows, clearing `right_data` so a fresh replay pass is opened. A left side that was empty from the start keeps its previous behaviour: no bitmaps have been accumulated, so that state reports nothing unmatched and finishes immediately. Spilling is preserved rather than refused — the fix corrects the emission instead of turning these queries into `ResourcesExhausted` errors. ## Are these changes tested? Yes, `datafusion/core/tests/memory_limit/nlj_spill_unmatched.rs` adds three tests comparing memory-limited results against an ample pool for `LEFT JOIN`, `LEFT ANTI`, and `FULL JOIN`. Without the production change they fail with `0 instead of 2`, `9334 instead of 9336`, and `9337 instead of 9339`; with it they pass. The existing `nested_loop_join` unit tests (46) and the wider `joins` suite (1116) pass unchanged, including `test_nlj_memory_limited_right_join`, which asserts that a spilling `RIGHT` join still returns its unmatched rows. ## Are there any user-facing changes? No API changes. Queries that previously lost rows under a memory limit now return the correct result.
1 parent 791b32e commit 16cce96

3 files changed

Lines changed: 164 additions & 2 deletions

File tree

‎datafusion/core/tests/memory_limit/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@ use std::sync::{Arc, LazyLock};
2222

2323
#[cfg(feature = "extended_tests")]
2424
mod memory_limit_validation;
25+
mod nlj_spill_unmatched;
2526
mod repartition_mem_limit;
2627
mod union_nullable_spill;
2728
mod view_spill_compaction;
Lines changed: 147 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,147 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! Memory-limited `NestedLoopJoinExec` must not drop unmatched rows.
19+
//!
20+
//! When the join spills, per-right-batch match bitmaps are accumulated across
21+
//! left chunks and their emission is deferred until every chunk has been
22+
//! probed. The load that follows the final chunk finds no left batches left,
23+
//! and that exit used to end the stream immediately — discarding the
24+
//! accumulated bitmaps, so rows that no chunk ever matched were never emitted.
25+
26+
use std::sync::Arc;
27+
28+
use arrow::array::{Int32Array, RecordBatch};
29+
use arrow::datatypes::{DataType, Field, Schema};
30+
use datafusion::prelude::*;
31+
use datafusion_execution::runtime_env::RuntimeEnvBuilder;
32+
33+
/// Deterministic table whose join keys repeat, so most rows match and only a
34+
/// few remain unmatched.
35+
fn table(rows: usize, value_column: &str, seed: u64) -> RecordBatch {
36+
let mut state = seed;
37+
let mut next = || {
38+
state = state
39+
.wrapping_mul(6364136223846793005)
40+
.wrapping_add(1442695040888963407);
41+
state >> 33
42+
};
43+
let schema = Arc::new(Schema::new(vec![
44+
Field::new("k", DataType::Int32, true),
45+
Field::new(value_column, DataType::Int32, true),
46+
]));
47+
let keys: Vec<Option<i32>> = (0..rows).map(|_| Some((next() % 10) as i32)).collect();
48+
let values: Vec<Option<i32>> =
49+
(0..rows).map(|_| Some((next() % 60) as i32)).collect();
50+
RecordBatch::try_new(
51+
schema,
52+
vec![
53+
Arc::new(Int32Array::from(keys)),
54+
Arc::new(Int32Array::from(values)),
55+
],
56+
)
57+
.unwrap()
58+
}
59+
60+
/// Run `sql`, optionally under a memory limit, returning the sorted rows.
61+
async fn run(sql: &str, memory_limit: Option<usize>) -> Vec<String> {
62+
let config = SessionConfig::new()
63+
.with_target_partitions(1)
64+
.with_batch_size(16);
65+
let runtime = match memory_limit {
66+
Some(bytes) => RuntimeEnvBuilder::new()
67+
.with_memory_limit(bytes, 1.0)
68+
.build_arc()
69+
.unwrap(),
70+
None => RuntimeEnvBuilder::new().build_arc().unwrap(),
71+
};
72+
let ctx = SessionContext::new_with_config_rt(config, runtime);
73+
ctx.register_batch("l", table(200, "v", 11)).unwrap();
74+
ctx.register_batch("r", table(90, "w", 16)).unwrap();
75+
76+
let batches = ctx.sql(sql).await.unwrap().collect().await.unwrap();
77+
let mut rows = vec![];
78+
for batch in &batches {
79+
for row in 0..batch.num_rows() {
80+
let cells: Vec<String> = (0..batch.num_columns())
81+
.map(|col| {
82+
datafusion_common::ScalarValue::try_from_array(batch.column(col), row)
83+
.unwrap()
84+
.to_string()
85+
})
86+
.collect();
87+
rows.push(cells.join("|"));
88+
}
89+
}
90+
rows.sort();
91+
rows
92+
}
93+
94+
/// A non-equi `LEFT JOIN` is planned as a `NestedLoopJoinExec`; the optimizer
95+
/// swaps the inputs, so the rows needing unmatched emission end up on the
96+
/// join's probe side. Spilling must not lose them.
97+
#[tokio::test]
98+
async fn left_join_keeps_unmatched_rows_when_spilling() {
99+
let sql = "SELECT l.k, r.w FROM l LEFT JOIN r ON l.v > r.w";
100+
101+
let ample = run(sql, None).await;
102+
let limited = run(sql, Some(64)).await;
103+
104+
assert_eq!(
105+
limited,
106+
ample,
107+
"memory-limited execution returned {} rows instead of {}",
108+
limited.len(),
109+
ample.len()
110+
);
111+
}
112+
113+
/// `LEFT ANTI` returns only unmatched rows, so losing them empties the result.
114+
#[tokio::test]
115+
async fn left_anti_join_keeps_unmatched_rows_when_spilling() {
116+
let sql = "SELECT l.k, l.v FROM l \
117+
WHERE NOT EXISTS (SELECT 1 FROM r WHERE l.v > r.w)";
118+
119+
let ample = run(sql, None).await;
120+
let limited = run(sql, Some(64)).await;
121+
122+
assert!(!ample.is_empty(), "expected the query to match some rows");
123+
assert_eq!(
124+
limited,
125+
ample,
126+
"memory-limited execution returned {} rows instead of {}",
127+
limited.len(),
128+
ample.len()
129+
);
130+
}
131+
132+
/// `FULL JOIN` needs unmatched emission on both sides.
133+
#[tokio::test]
134+
async fn full_join_keeps_unmatched_rows_when_spilling() {
135+
let sql = "SELECT l.k, r.w FROM l FULL JOIN r ON l.v > r.w";
136+
137+
let ample = run(sql, None).await;
138+
let limited = run(sql, Some(64)).await;
139+
140+
assert_eq!(
141+
limited,
142+
ample,
143+
"memory-limited execution returned {} rows instead of {}",
144+
limited.len(),
145+
ample.len()
146+
);
147+
}

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

Lines changed: 16 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1961,9 +1961,23 @@ impl NestedLoopJoinStream {
19611961
}
19621962

19631963
if active.pending_batches.is_empty() {
1964-
// No data at all — go directly to Done
19651964
self.left_exhausted = true;
1966-
self.state = NLJState::Done;
1965+
// Reached both when the left side was empty from the start and when
1966+
// the previous chunk consumed the last of it, so this load finds
1967+
// nothing left. In the latter case earlier chunks have already
1968+
// merged their per-batch bitmaps into `global_right_bitmaps`, and
1969+
// those unmatched probe-side rows are still waiting to be emitted.
1970+
// Going straight to `Done` would discard them, silently dropping
1971+
// rows. `EmitGlobalRightUnmatched` replays the spilled right side
1972+
// and emits them; with no bitmaps accumulated it reports nothing
1973+
// unmatched and finishes immediately, so a genuinely empty left
1974+
// side behaves as before.
1975+
self.state = if self.should_track_unmatched_right {
1976+
self.right_data = None;
1977+
NLJState::EmitGlobalRightUnmatched
1978+
} else {
1979+
NLJState::Done
1980+
};
19671981
return ControlFlow::Continue(());
19681982
}
19691983

0 commit comments

Comments
 (0)