Skip to content

Commit 185ddc4

Browse files
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/config.rs‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1031,6 +1031,25 @@ config_namespace! {
10311031
/// Default: 128 MB
10321032
pub max_spill_file_size_bytes: ConfigNonZeroUsize, default = non_zero_usize_default(128 * 1024 * 1024)
10331033

1034+
/// Enables the memory-limited fallback for `NestedLoopJoinExec` join
1035+
/// types that emit unmatched left rows in the final output (LEFT, LEFT
1036+
/// SEMI, LEFT ANTI, LEFT MARK, FULL) when the right side has multiple
1037+
/// partitions.
1038+
///
1039+
/// This fallback coordinates per-chunk left state (visited bitmap and
1040+
/// probe-thread counter) across all right-side partitions, which
1041+
/// assumes every partition runs in the same process. Distributed
1042+
/// engines that execute each output partition as an independent task
1043+
/// (e.g. Ballista, datafusion-distributed) build a separate coordinator
1044+
/// per task and poll only one partition, so the cross-partition
1045+
/// counter never reaches zero and the fallback would stall. Such
1046+
/// engines should set this to `false`: the coordinated fallback is then
1047+
/// disabled for left-emitting multi-partition joins, which instead fail
1048+
/// with a resource-exhaustion error under memory pressure rather than
1049+
/// deadlocking. Single-partition and non-left-emitting joins are
1050+
/// unaffected and always keep the fallback.
1051+
pub enable_nlj_coordinated_fallback: bool, default = true
1052+
10341053
/// Number of files to read in parallel when inferring schema and statistics
10351054
pub meta_fetch_concurrency: ConfigNonZeroUsize, default = non_zero_usize_default(32)
10361055

0 commit comments

Comments
 (0)