Repository navigation
Commit 185ddc4
authored
Share per-chunk JoinLeftData across right partitions in NLJ memory-limited fallback (apache#22038)
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and
enhancements and this helps us generate change logs for our releases.
You can link an issue to this PR using the GitHub syntax. For example
`Closes apache#123` indicates that this PR will close issue apache#123.
-->
- Closes apache#24764.
## Rationale for this change
The memory-limited fallback path builds a **per-output-partition**
`JoinLeftData` for each left chunk, with `probe_threads_counter == 1`.
The single-pass path instead shares one `JoinLeftData` seeded via
`collect_left_input(.., probe_threads_count)`. With a private visited
bitmap per partition, each right partition sees only its own right rows,
so unmatched left rows would be emitted once per partition, and rows
matched only in another partition would be emitted as unmatched.
Because those results would be wrong, `main` **refuses the fallback**
for the affected join types rather than producing them:
```rust
let left_emission_multi_partition =
need_produce_result_in_final(self.join_type) && right_partition_count > 1;
let can_spill = context.runtime_env().disk_manager.tmp_files_enabled()
&& !left_emission_multi_partition;
```
So the state on `main` today is not incorrect output but a **missing
capability**: with `target_partitions > 1`, a `LEFT` / `LEFT SEMI` /
`LEFT ANTI` / `LEFT MARK` / `FULL` nested loop join has no spilling path
at all and fails with `ResourcesExhausted` under memory pressure. This
PR makes those joins spill instead.
(When this PR was first opened the guard covered only `FULL`, so the
wrong results were still reachable for the other join types. apache#21833 and
apache#24675 have since widened it to every left-emitting type, which is why
the framing above differs from the original description.)
## What changes are included in this PR?
A plan-level `FallbackCoordinator` that:
- Owns the shared left spill stream and the per-chunk
`MemoryReservation`, so each chunk is read exactly once no matter how
many partitions probe it,
- Has the first partition reaching a chunk become its "leader": it loads
the chunk and publishes an `Arc<JoinLeftData>` (with
`probe_threads_counter == right_partition_count`) into a shared slot,
- Lets every other right partition take an `Arc` clone of that same
`JoinLeftData`, so the visited bitmap and probe-thread counter are
shared exactly as in the single-pass `collect_left_input` path,
- Releases the slot only after the partition that drives the counter to
zero finishes emitting unmatched left rows for the chunk, then notifies
waiters so the next chunk can be loaded.
The per-chunk in-flight fetch and release are driven through future
fields on `SpillStateActive` (`chunk_fetch_in_flight` /
`chunk_release_in_flight`), polled across `poll_next` iterations.
Partitions waiting for a chunk sleep on a `Notify` rather than
busy-looping, and every early return after a leader claim clears
`loader_in_flight` and wakes waiters so a failed load cannot leave
others parked.
The `left_emission_multi_partition` guard is removed, so these join
types now take the coordinated path.
`datafusion.execution.enable_nlj_coordinated_fallback` (default `true`)
lets distributed engines opt out. The coordination assumes all right
partitions run **in the same process**; an engine that runs each
partition as an independent task would get one coordinator per task, so
the shared probe-thread counter would never reach zero and the fallback
would stall. Setting the flag to `false` restores the current fail-fast
behavior for the affected join types.
### Rebase notes (2026-08-28)
Rebased onto current `main`. Two things changed underneath this PR:
- **`main` now shares the spilled left side across partitions itself**,
resolving a shared `OnceAsync<LeftLoad>` so the left child is executed
and spilled exactly once. That was one half of this PR's original design
(`left_spill_fut: OnceFut<LeftSpillData>`), so that half is dropped in
favor of `main`'s mechanism. What remains — and what `main` still lacks
— is sharing the per-chunk visited bitmap and probe-thread counter.
- **apache#24746 added `EmitGlobalRightUnmatched` routing** so the
memory-limited path does not drop deferred unmatched probe-side rows
when the left side is exhausted. That routing is preserved on the
coordinator's exhausted-left path, and its three regression tests in
`datafusion/core/tests/memory_limit/nlj_spill_unmatched.rs` pass.
Design discussion from the original round:
apache#21833 (comment)
and
apache#21833 (comment).
## Are these changes tested?
Yes:
- **Seven** multi-partition memory-limited correctness tests in
`nested_loop_join.rs`: one each for `LEFT`, `FULL`, `LEFT SEMI`, `LEFT
ANTI`, `LEFT MARK`, plus two multi-chunk cases (`LEFT`, `FULL`) that
exercise the chunk hand-off between leaders. Each compares the
memory-limited result against the unrestricted one. All seven fail on
`main` (as `ResourcesExhausted`) and pass here.
- Multi-partition cases added to `nested_loop_join_spill.slt`, including
an `EXPLAIN ANALYZE` assertion on `spill_count` so the tests fail if the
fallback silently stops being taken.
- `enable_nlj_coordinated_fallback` listed in `information_schema.slt`.
Regression-checked after the rebase: 55 NLJ unit tests, 1125 `joins`
tests, 36 `memory_limit` tests (including the three apache#24746 tests above),
259 `datafusion-proto` tests, and the `nested_loop_join*` /
`information_schema` sqllogictest files. `cargo clippy --all-targets
--all-features -- -D warnings` is clean.
## Are there any user-facing changes?
Yes, two:
- `LEFT`, `LEFT SEMI`, `LEFT ANTI`, `LEFT MARK`, and `FULL` nested loop
joins over a multi-partition right side now spill under memory pressure
instead of failing with `ResourcesExhausted`.
- New config option
`datafusion.execution.enable_nlj_coordinated_fallback` (default `true`),
documented in `docs/source/user-guide/configs.md`. No public API
signature changes.
<!--
If there are any breaking changes to public APIs, please add the `api
change` label.
-->1 parent c14633e commit 185ddc4
6 files changed
Lines changed: 1655 additions & 241 deletions
File tree
- datafusion
- common/src
- physical-plan/src/joins
- sqllogictest/test_files
- docs/source
- library-user-guide/upgrading
- user-guide
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1031 | 1031 | | |
1032 | 1032 | | |
1033 | 1033 | | |
| 1034 | + | |
| 1035 | + | |
| 1036 | + | |
| 1037 | + | |
| 1038 | + | |
| 1039 | + | |
| 1040 | + | |
| 1041 | + | |
| 1042 | + | |
| 1043 | + | |
| 1044 | + | |
| 1045 | + | |
| 1046 | + | |
| 1047 | + | |
| 1048 | + | |
| 1049 | + | |
| 1050 | + | |
| 1051 | + | |
| 1052 | + | |
1034 | 1053 | | |
1035 | 1054 | | |
1036 | 1055 | | |
| |||
0 commit comments