Skip to content

Commit 34ac929

Browse files
docs(plans): Σ.SP spillable-join arc — grace-join demotion design; resolve MEMORY_BUDGET decision gate
Upstream check (2026-07-11): spillable hash join has not landed through DataFusion 54.0.0; apache/datafusion#17267 is still a design-stage proposal epic. Per the MEMORY_BUDGET gate, the paging arc proceeds in-repo as plan-time grace-partitioned join demotion driven by the Σ.JS.2 grounded estimates. Phases: 0 = post-Σ.MW.1 32GB re-baseline, 1 = Inner GraceHashJoinExec behind EMAT_GRACE_JOIN (default OFF), 2 = semi/anti + full-suite A/B default decision, 3 = upstream watch. Co-Authored-By: Claude Fable 5 <[email protected]>
1 parent 801479e commit 34ac929

2 files changed

Lines changed: 124 additions & 0 deletions

File tree

‎docs/plans/MEMORY_BUDGET.md‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -167,3 +167,13 @@ Decision gate: reassess after the next DataFusion upgrade (spillable
167167
hash join is on their roadmap); if not landed, prototype (3) then (2),
168168
each behind a tri-state, each validated with the FULL 22q suite on the
169169
32 GB box (isolated A/Bs of memory levers do not transfer — proven above).
170+
171+
**Gate resolved 2026-07-11:** upstream spillable hash join has NOT
172+
landed through DataFusion 54.0.0 (June 2026; proposal epic
173+
apache/datafusion#17267 still design-stage). Meanwhile the landscape
174+
moved: Q09 was solved at the plan level (Σ.JS.1/Σ.JS.2, PRs #176/#178)
175+
and the parted tar pit was scan-width, not paging (Σ.MW.1, PR #179 —
176+
the union multiplied decode width by the part count; with the budget
177+
split the parted single-node suite completes). The paging arc continues
178+
as **grace-partitioned join demotion** driven by the Σ.JS.2 grounded
179+
estimates — see [SPILLABLE_JOIN.md](SPILLABLE_JOIN.md).

‎docs/plans/SPILLABLE_JOIN.md‎

Lines changed: 114 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,114 @@
1+
# Σ.SP — Spillable-join arc: grace-partitioned join demotion
2+
3+
Status: **Phase 0 (design + box re-baseline), 2026-07-11.** Successor to
4+
the "paging arc" in [MEMORY_BUDGET.md](MEMORY_BUDGET.md) — that doc's
5+
decision gate said *reassess after the next DataFusion upgrade*; the
6+
reassessment is done and recorded here.
7+
8+
## Why now, and what changed since MEMORY_BUDGET.md
9+
10+
The paging arc was framed when Q09 thrashed and parted-SF100 tar-pitted.
11+
Both of those are gone by other means:
12+
13+
- **Q09 is solved at the plan level** (Σ.JS.1/Σ.JS.2, PRs #176/#178):
14+
honest join-side estimates keep builds small; SF=100 flat suite 51.8 s.
15+
- **The parted tar pit was scan-width, not paging** (Σ.MW.1, PR #179):
16+
the multi-file union multiplied decode width by the part count. With
17+
the budget split, the full parted single-node SF=100 suite completes
18+
(47.7 s / 22.4 GB peak on the 36 GB dev box — first complete run
19+
anywhere; 32 GB box validation pending, Phase 0).
20+
21+
What remains for THIS arc is the last structural weakness: **oversized
22+
tracked join builds cannot yield memory.** DF 53's `HashJoinExec` cannot
23+
spill; under a cap it deadlocks (the refuted 0.7×RAM blanket cap), and
24+
against the `ElasticFloorPool` it fails the query cleanly at best,
25+
kernel-OOMs at worst when the growth is bursty. Today's exposure:
26+
27+
- Q18/Q21-class plans (giant semi/anti/inner builds) ride the margin on
28+
32 GB boxes: ~28 GB peaks that pass or die on page-cache luck.
29+
- Any hostile/ad-hoc workload (not TPC-H) can synthesize a build larger
30+
than RAM and there is no graceful degradation.
31+
32+
## Upstream status (checked 2026-07-11)
33+
34+
- Spillable hash join has **not landed through DataFusion 54.0.0**
35+
(June 2026, latest). The proposal epic is
36+
[apache/datafusion#17267](https://github.com/apache/datafusion/issues/17267)
37+
(hybrid hash join with greedy partition spilling) — design stage,
38+
"not yet fully underway". apache/datafusion#12952 and #1599 are the
39+
long-running asks.
40+
- Conclusion per the MEMORY_BUDGET decision gate: build in-repo, keep
41+
it a *demotion* (stock plans untouched unless the estimate says
42+
danger), and treat upstream as the eventual replacement.
43+
44+
## Design: plan-time demotion, not runtime panic
45+
46+
The upstream proposal spills *reactively* (notice memory pressure
47+
mid-build, spill largest partitions). We have something DF doesn't: the
48+
Σ.JS.2 **grounded bottom-up row/byte estimates** at plan time. That
49+
enables the simpler, more predictable half of the design space:
50+
51+
**A physical rule (`GraceJoinDemotionRule`, after Σ.JS.1 in the preset
52+
chain) rewrites a `HashJoinExec` whose GROUNDED build-side estimate
53+
exceeds a budget into a `GraceHashJoinExec`.**
54+
55+
- **Budget:** `EMAT_GRACE_BUILD_BYTES` tri-state. AUTO = demote when
56+
estimated build bytes > `f × sensed MemAvailable at plan time`
57+
(start f = 0.5; the Σ.AI.6c sensor already exists and is cached).
58+
Ungrounded estimates never demote (same honesty rule as Σ.JS.1 —
59+
no decision without proof), so TPC-H flat plans are untouched:
60+
bench == release means banked numbers cannot move.
61+
- **Operator (`GraceHashJoinExec`):** classic grace hash join.
62+
1. Partition BOTH inputs to `K` spill files by `hash(join keys)`
63+
(reuse DF's IPC spill-file machinery used by sort/agg spills).
64+
2. Join partition pairs sequentially with a stock in-memory
65+
`HashJoinExec` over per-partition record-batch streams; a pair
66+
whose build still exceeds the budget recurses with a different
67+
hash seed (bounded depth, then hard error).
68+
3. `K` = ceil(estimated build bytes / (budget / 2)) rounded to a
69+
power of two, min 4.
70+
- **Join types, phased:** Inner first (Phase 1); LeftSemi/LeftAnti
71+
(the Q21 shape) in Phase 2; outer joins only if evidence demands.
72+
- **Memory accounting:** partition write buffers + the per-pair build
73+
reserve from the session pool, so the ElasticFloorPool sees the
74+
truth. Spill bytes/files surfaced as metrics
75+
(`grace_partitions`, `grace_spill_bytes`, `grace_recursions`).
76+
77+
### Why demotion instead of a spilling retrofit of HashJoinExec
78+
79+
- The refuted-cap evidence shows mid-build reactive spilling under
80+
DF 53's scheduling is deadlock-prone (concurrent reservations wait on
81+
each other). A demoted plan never enters that regime: partitioning is
82+
streaming with O(K buffers) memory, and each pair-join is sized to
83+
fit by construction.
84+
- SMJ demotion was already tried and refuted (MEMORY_BUDGET evidence
85+
table: SMJ+cap = `ResourcesExhausted`, SMJ unbounded = kernel OOM).
86+
- Plan-time demotion is testable deterministically (feed the rule a
87+
plan with grounded stats; assert the rewrite), matching the Σ.JS test
88+
discipline.
89+
90+
## Phases
91+
92+
- **Phase 0 — re-baseline (cheap, decisive).** One 32 GB box run of the
93+
post-Σ.MW.1 parted single-node suite. If Q18/Q21 now pass with the
94+
width fix, the arc's default posture can stay conservative (demotion
95+
fires only on genuinely-oversized builds, expected: none in TPC-H).
96+
Exit: banked baseline + updated exposure list.
97+
- **Phase 1 — Inner grace join behind `EMAT_GRACE_JOIN` (default OFF).**
98+
Operator + demotion rule + unit/property tests (result parity vs
99+
stock join across seeds/partition counts, spill-file cleanup,
100+
accounting) + a synthetic oversized-build workload that OOMs stock
101+
and completes demoted.
102+
- **Phase 2 — semi/anti support + full-suite A/B.** The 22q protocol on
103+
the 32 GB box, flat + parted, default-ON decision by the same rule as
104+
every memory lever: zero regression on healthy runs, graceful
105+
degradation on pressure runs.
106+
- **Phase 3 — upstream watch.** When apache/datafusion#17267 lands,
107+
benchmark theirs vs ours; prefer deleting ours.
108+
109+
## Non-goals
110+
111+
- Replacing the ElasticFloorPool (it stays as the last-resort guard).
112+
- Spilling aggregates/sorts (DF already does; multi-level merge since
113+
DF 50).
114+
- Symmetric/streaming joins.

0 commit comments

Comments
 (0)