Repository navigation
Commit 16cce96
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
- physical-plan/src/joins
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
22 | 22 | | |
23 | 23 | | |
24 | 24 | | |
| 25 | + | |
25 | 26 | | |
26 | 27 | | |
27 | 28 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
| 133 | + | |
| 134 | + | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1961 | 1961 | | |
1962 | 1962 | | |
1963 | 1963 | | |
1964 | | - | |
1965 | 1964 | | |
1966 | | - | |
| 1965 | + | |
| 1966 | + | |
| 1967 | + | |
| 1968 | + | |
| 1969 | + | |
| 1970 | + | |
| 1971 | + | |
| 1972 | + | |
| 1973 | + | |
| 1974 | + | |
| 1975 | + | |
| 1976 | + | |
| 1977 | + | |
| 1978 | + | |
| 1979 | + | |
| 1980 | + | |
1967 | 1981 | | |
1968 | 1982 | | |
1969 | 1983 | | |
| |||
0 commit comments