# 317 — Boundary Window Reconciliation > **Status: Proposed, not started (2026-09-21).** Nothing here is implemented. The > measurements in §2 are real and reproducible > (`take_bounded_fanout::measure::depth2_exists_chain_rename`). The code facts cited were > checked against this tree (branch `bounded-fanout`, `9846363`). Everything else is > specification and argument, and §12 lists what is least certain. > > **What this is.** A from-scratch answer to the limited backfill cascade > ([RUNAWAY-PUSH-FINDINGS §3](../follow-ups/RUNAWAY-PUSH-FINDINGS.md#3-the-unbounded-join-push-perf-11), > [316 §17.5](316-SCOPED-JOIN-PARENT-INDEX-DESIGN.md#175-investigate-change-scoped-window-reconciliation)), > written without regard to what has been built for it. It changes *how a limiter decides > what is in its window*. It keeps the bounded fan-out cut built under 316 §17.5, demoted > from a correctness mechanism to an optimization (§6). > > **Relation to 316 §17.5.** That section first sketched "change-scoped window > reconciliation" in four steps, then built something smaller — the cut, with the refill > left mid-push — and recorded why. Two parts of that record do not survive §2. Its cost > argument (a `reconcile` phase threaded through fourteen operators and the pipeline > driver) is upstream's cost and not this engine's (§5.3). And its "Still open" claim that > a nested EXISTS cascade "is limited to one child's rows within one partition" is wrong > for the outer window. This doc is the four-step sketch made concrete; "retain the old > window" is answered by member keys (§5.1). > > **History.** The first design of Zero's `Take` kept every member of the window (Matt, > 2026-09-21). The operator that shipped, and that this engine ported, keeps a count and a > bound. This design goes back to members. --- ## 1. One defect, not six Every fault found in this area has the same shape. | # | Symptom | Where | What went wrong | | --- | --- | --- | --- | | 1 | The cascade: `limit` removes each refill with a parent that is removed next | findings §3, 316 §3.5 | The refill read a parent that was still owed the delta | | 2 | `Exists` cache poisoning: a doomed row kept past the cut; on `main`, a `Remove` of a row the view never held | `039274b` | One refill scan met same-key parents in different states — it starts `At` the bound row, which may still be owed the delta — and the first one answered for the rest | | 3 | Upstream's `[i2, i9]` for `[i2, i3]` | `rocicorp/mono#6617` tip, §17.5 obligation 4 | A window left short by a deferred refill admitted an add as if its input were exhausted | | 4 | Upstream's overlay loses its bound mid-push | §17.5 obligation 1 | The overlay reads the live bound, which disappears at the first in-window remove | | 5 | Depth 2, removes, inner order aligned with the window: 2N changes, O(N²) when flipped | §2 | The outer refill admitted roots doomed by an inner fan-out that was still open | | 6 | Depth 2, adds, inner order opposed to the window: 2N changes | §2 | Nothing was misread. Every delivery legitimately displaced the bound, because deliveries did not arrive in the window's order | The common cause: **a limiter decides which rows are in its window from a read — or from an arrival order — taken while the graph is mid-transition.** The cut, the late cut, the short-window rule, the cache guard, upstream's gate and upstream's pending rule each make one more of those decisions come out right. None of them removes the decisions. Row 6 shows the limit of that approach: no rule about reads can fix it, because no read is wrong. ## 2. Measurements: the cut is a depth-1 mechanism `issue.whereExists(comment, c => c.whereExists(author, name = 'bot')).orderBy(id).limit(10)`. One comment per issue; every doomed comment is by author 1. Author 1 is renamed away and then back. `aligned` means comment ids run with issue ids; `opposed` reverses the comment → issue map, so the inner fan-out (which runs in comment order) delivers against the window's order. N = 2,000, release, memory leaf. A many-to-many EXISTS through a junction table is this shape (316 §1.2's R2), so it is not exotic. Changes that reach the sink (a minimal answer is 10 to 20): | Cell | Rindle `bounded-fanout` | Upstream `grgbkr/multi-phase-push` (`1d041c64c`) | | --- | --- | --- | | away, aligned | **3,990** (26 ms) | 10 (11 ms) | | away, aligned, both joins flipped | **3,990** (3.2 s; 48.7 s at N = 8k) | 10 (0.58 s) | | away, opposed | 10 | 10 | | back, aligned | 10 | 10 | | back, opposed | **3,990** (19 ms) | **3,990** (41 ms) | | back, opposed, both joins flipped | **3,990** (1.6 s; 25.8 s at N = 8k) | **3,990** (38.6 s) | Rindle: `cargo test --release -p rindle --features testkit --test it -- take_bounded_fanout::measure::depth2_exists_chain_rename --ignored --nocapture`. Upstream: the same probe ported to vitest and run at the PR's tip. Three readings. 1. **Rindle's change counts are identical with `RINDLE_FANOUT_CUT=off`.** The join that fans out (`comment ⋈ author`) has no governing `Take`: `first_take_downstream` gives up at a `JoinChild` port (`graph.rs:3685`). Its pre-change band has no upper edge, so the outer `Take`'s mid-push refill admits an issue whose comment has not been delivered yet. 2. **The last hop is governed, and its cut works when the order cooperates.** In `back, aligned` the outer hop drops 1,990 parents at the cut and the sink sees 10 changes. In both cascading cells it drops **0**, because every root is inside the window at the moment its delivery lands — in one cell because the refill just pulled it in on stale inner state, in the other because it belongs there for the moment. 3. **Deferring the refill fixes one cell, not both.** Upstream's boundary refill sees post-change state at every depth, so `away, aligned` is 10. `back, opposed` is 3,990 in both engines: a deferred refill does nothing for displacement. ## 3. Why depth 1 works, and why that does not extend The bounded fan-out rests on two facts about **order**: 1. The fan-out runs in the window's order, so the first `limit` adds to arrive are final and the late cut can end the fan-out. 2. The fan-out's pre-change band has an upper edge at the cut, so a refill — which starts at the live bound, at or past the cut — meets only post-change rows. Both hold because the join that fans out is the one the `Take` governs: its parent fetch is sorted in the `Take`'s order, and it can read the `Take`'s bound. One level down neither holds. The join that fans out is ordered by its own parent table and cannot see the bound. Row 5 of §1 is fact 2 failing; row 6 is fact 1 failing. **Pushing the cut down** — an inner parent is owed the delta iff one of its roots is within the captured cut — is self-consistent for removes: the owed set is fixed at capture, the refill admits only roots past the cut, so nothing becomes newly owed. It costs an ancestor probe per inner row, and it needs a second allow-list walk, upward through `Cap`, `FlippedJoin` and the OR fans, re-argued per depth. It cannot fix row 6: an opposed-order add is within the bound when it arrives. The other route needs no argument per depth. Once the source write is committed, no fan-out is in flight at any level and no overlay is live. A fetch made then is just a fetch. ## 4. Principle > **Pushes keep held rows exact. A fetch decides membership, once, at the push boundary.** Pushes and fetches are good at different jobs. A push carries a delta to a row that something holds state for. A fetch answers "which `limit` rows", and it is trustworthy only when nothing is in flight — which, at arbitrary depth, is the boundary and nowhere else. Terms used below: | Term | Meaning | | --- | --- | | limiter | `Take` or `Cap` | | window | One partition of a limiter | | member | A row the limiter has emitted an `Add` for and not yet a `Remove`. Known by key (§5.1) | | held | A row some limiter counts as a member, or the view contains | | dirty | A window whose members may differ from the first `limit` rows of its input, post-change | | boundary | The point in `try_source_push` after the source has pushed to every connection and committed its write | | published bound | What a window reports to a governed join's cut (`Take::window_at`). It never sorts before a member | ## 5. Design ### 5.1 A limiter knows its members `Cap` already does: `StorageValue::Cap { size, pks }`. `Take` keeps `StorageValue::Take { size, bound }` (`storage.rs:67`) and *infers* membership as "sorts at or before the bound, and passes upstream right now". That inference is what fails mid-push: upstream is in transition, so "passes right now" is not "was emitted". Fault 2's phantom `Remove` and [#594](../follow-ups/flat-receiver-remove-of-non-existent-node.md) — a window counting rows the consumer was never sent — are both the inference diverging from the emission log. `Take` gains `members`: the sort keys of its members, in order. `Take` requires a sort that includes the primary key, so a sort key identifies a row. With it: - Membership is exact. A `Remove` or `Child` for a non-member is dropped, whatever its position. - An `Add` can be **absorbed** — noted, not emitted — because the limiter can later tell a row it has emitted from one it has not. Without identity only the refill can be deferred, which is as far as upstream's branch goes and why row 6 survives there. - `members` changes only together with an emitted `Add` or `Remove`. The window and the consumer cannot disagree. At rest, `size == members.len()` and `bound == members.last()`. During a push `size` and `bound` are **not written** (§5.2); they describe the last reconciled window, and they are what the cut reads. ### 5.2 Push rules: bookkeeping, no fetches A change for a never-hydrated partition is dropped, as today (`take.rs:461`, `cap.rs:218`). Otherwise, for a change about row `r`: | Change | Condition | Action | | --- | --- | --- | | `Child` | `r` is a member | Forward | | `Child` | otherwise | Drop | | `Remove` | `r` is a member | Remove `r` from `members`, then forward. Mark dirty | | `Remove` | `r` was absorbed in this push | Forget it | | `Remove` | otherwise | Drop | | `Add` | `r` could enter: it sorts at or before the published bound, or the window was short at its last reconcile | Absorb: record the key (§5.4). Mark dirty. Emit nothing | | `Add` | otherwise | Drop, and evict upstream child state as today (`evict_upstream_if_full`) | | `Edit` | old row is a member | Update its key, then forward. If the key moved, mark dirty and raise the published bound to it if it now sorts later | | `Edit` | old row is not a member, new row could enter | Absorb the new key. Mark dirty | | `Edit` | otherwise | Drop | Two rules carry the design: - **A member's `Remove` is forwarded at once.** Its node is in hand and agrees, through the overlays, with what the consumer holds. At the boundary the row may no longer pass — or exist — so it could not be fetched. - **An `Add` is never emitted during a push.** Whether `r` belongs in the window depends on everything else the source change does, at every depth, in an order the limiter does not control. "Mark dirty" appends `(limiter, window key)` to a worklist on the `Graph`, once. ### 5.3 The boundary is one call site `try_source_push` already has an outer boundary: `scope_publish_all`, where design 316 publishes the scope directories the push touched (`graph.rs:4121`). The drain goes between `s.try_push(...)` returning `Ok` and that call: the write is committed, the source overlay is cleared (`source_common.rs:1225`), and nothing is in flight. It runs before the publish because a reconcile emits ordinary pushes, whose parent-port arms maintain the directory. Upstream threads `reconcile()` through every operator because its operators know only their input and output. Here the graph is an arena: a dirty window is a `NodeId` and a key, and the drain is a loop in one function. - **Order: upstream first.** A reconcile fetches through every limiter upstream of it, so those must already be reconciled. A reconcile's own emissions flow toward the sink and can only dirty limiters downstream of it. So the drain takes dirty windows in topological order, re-reading the worklist as it grows, and each window reconciles once. (Operators are built after their inputs, so ascending `NodeId` is expected to be such an order — S1 checks it.) - **Split edits.** A split `Edit` pushes and writes each half separately (`source_common.rs:1417`). Windows stay dirty across both halves and reconcile once. - **Failure.** If the push parked a runtime error, the drain is skipped; the host discards the engine, as today. The reconcile scan carries the §6.6 deadline checkpoint that the backfill scan carries now. - **Scope.** One source change. Draining once per transaction would coalesce more and is a separate decision (§12). ### 5.4 Reconcile Let `start` be the earliest position at which the window's membership may differ: the smallest absorbed key, the new position of a member whose key moved, or — if there is only a deficit — just past the published bound. Let `k` be the number of members sorting before `start`. Then ``` W' = (the k members before start) ∪ (the first limit − k rows of input.fetch(start: At(start))) for m in members ∖ W': members −= m; push Remove(m) // m still passes: fetch its node by key for w in W' ∖ members: members += w; push Add(w) // node from the scan size = |members|; bound = last(members); clear absorbed, dirty, provisional bound ``` `Remove`s go first so the output never exceeds `limit`. `members` is updated before each push, so a reentrant `fetch` through the limiter during its own emission sees exactly what has been emitted. That replaces `row_hidden_from_fetch`. With nothing absorbed this is a deferred refill: `start` is past the bound, every member is retained, and the scan fetches the deficit. A window that was already short and absorbed nothing has nothing past its bound and fetches nothing — the short-window rule, surviving as a shortcut and no longer as an invariant others lean on. **The exact shortcut.** The hot path is one row: an insert at the top of a list. If every absorbed key is still held (at most `limit` of them, none discarded) and no provisional bound was published (§6.3), the candidates are fully known and `W' = first limit of (members ∪ absorbed)`, computed from keys, plus a deficit fetch if that is still short and the window was not exhausted. Each entrant and each displaced member then costs one fetch by key — for a top-of-list insert two, against today's two-row reverse probe. Anything else takes the scan, which is bounded by `limit` rows and happens only for a push that delivered at least a window's worth of adds. ### 5.5 Fetch through a limiter answers from `members` Both regimes of `Take::fetch` (`take.rs:290`) stream the input and keep a row iff it is a member, in place of the comparison against the partition's bound. `MAX_BOUND` stays as the scan stop for the unconstrained regime. A nested window read while it is dirty — by a parent join building a relationship — therefore shows exactly the rows its consumer has been sent. ### 5.6 `Cap` `Cap` is `Take` without order, and it is already most of the way there: membership by PK set, an `Add` admitted when there is room and dropped when there is not, `Child` and `Edit` forwarded by membership. It has no displacement, so admitting an `Add` at once is final up to bounded churn and needs no read. Its one mid-push fetch is the refill in `push_remove` (`cap.rs:273`), and that is the only change: forward the `Remove`, mark dirty, and refill at the boundary from the first partition rows not in the set. This matters more than §17.5 allowed. A `Cap` partition's cascade is bounded by the partition, but a partition can be large — every member of an organization under `org.whereExists(members, m => m.whereExists(role, …))` — and each step is a fetch through the inner gate. `Skip` is not a limiter in this sense. It is stateless, its bound is the AST's fixed start, and it never fetches on a push (`skip.rs:18`). ### 5.7 What this deletes Every mid-push fetch in `Take`, and the machinery that exists to make them safe: - the displacement probe (`take.rs:528`, `:530`); - the predecessor probe (`take.rs:598`) and the refill scan (`take.rs:620`); - the four fetches of the edit matrix (`take.rs:743`, `:754`, `:784`, `:821`), and with them the `(oldCmp, newCmp)` case analysis — an edit becomes "forward if a member, update the key, mark dirty"; - `row_hidden_from_fetch` and its guard; - the short-window rule as an invariant (`take.rs:589`), and the late cut's lowering (`graph.rs:3796`), which returns in a simpler form (§6.3). `Take` becomes bookkeeping plus one procedure that runs when nothing else does. Limiters stop being a source of mixed-state reads; the `Exists` cache guard (`exists.rs:125`) stays, as defence for the fetches joins still make mid-push. ## 6. The cut, re-licensed ### 6.1 The rule Once membership is decided by fetch, deliveries no longer decide anything about rows nothing holds. So: > A join may skip delivering a child change to parent `p` if > (a) no limiter downstream counts `p` as a member, and nothing between the join and that > limiter keeps state per parent; > (b) `p` reads post-change for the rest of the push; and > (c) any window `p` could enter is dirty by the boundary, or cannot admit `p`. The engine already behaves this way one level down: a limiter drops every push for a partition it has not hydrated and lets the next fetch re-derive it. ### 6.2 The last hop (built) For a parent past the published bound of a full window: (a) holds because the published bound never sorts before a member, and the allow-list walk (`first_take_downstream`) admits only row-preserving, per-row-stateless nodes; (b) is the overlay's upper edge (`join_overlay_for`, `graph.rs:2402`); (c) holds because such a parent enters only through a vacancy, and a vacancy is a member's `Remove`, which marks the window dirty. The cut carries over as built, reading a bound that no longer moves mid-push. Its argument gets shorter: it no longer has to show that a mid-push refill sees the right thing, because there is none. ### 6.3 The late cut, as a provisional bound Absorbing adds would cost the depth-1 rename-back its `O(limit)`: a short window has no bound to cut at, so all N parents would be delivered and absorbed. The scan pins (`take_bounded_fanout::scan_ends_at_the_cut`) hold that line. A limiter therefore keeps the best `limit` absorbed keys in a bounded heap. Once members plus heap reach `limit`, it publishes the `limit`-th smallest as a **provisional bound**, which only ever lowers. The join's existing `lower` path picks it up and ends the fan-out. This is safe out of order and under later removes, by §6.1: a skipped row holds nothing and reads post-change, and the window is dirty. The price is that reconcile takes the scan instead of the exact shortcut (§5.4). ### 6.4 Below O(N) at depth ≥ 2 (not in scope) Under this design an inner fan-out is still delivered in full: about 1–2 µs a row unflipped in §2's non-cascading cells (10–17 ms at N = 8k). The same rule licenses narrowing it. Its deliveries reach a limiter first — the EXISTS child's `Cap`, or a nested `Take` — and that limiter drops everything outside its hydrated partitions. So the parents that can observe the delta are bounded by the consumer's hydrated partition keys, and the inner parent fetch can be constrained to them when they are fewer than the fan-in. That is 316's narrowing, with the demand set read from limiter storage, and 316 S5's crossover applies (`narrow_max_parents`). It is a separate axis and should not be built before §11's S4. The doomed-tail scan — post-change rows that fail, between the window and its next survivors — remains, as in every design so far. A flipped plan or a better index shortens it; nothing here does. ## 7. Correctness argument Four invariants, then an induction. - **I1 — emission is membership.** `members` changes only in the same step as an emitted `Add` or `Remove`. So what a limiter counts is what its consumer was sent. - **I2 — quiescent reads.** A limiter fetches only at the boundary: source committed, no overlay, no fan-out in flight at any depth, every upstream limiter reconciled. Such a fetch returns what a fresh query over the post-change data would return for that input. - **I3 — members hear everything.** No delivery addressed to a member is skipped. For the cut that holds because the published bound never sorts before a member. 311's pre-check and 316's narrowing skip deliveries too, under their own arguments; §12 lists re-reading them against a bound that moves only at the boundary. - **I4 — dirty is complete.** If the first `limit` rows post-change differ from `members`, the window is dirty at the boundary. They differ only if a member left — delivered by I3, which marks dirty — or a non-member entered. A non-member at or before the published bound was delivered its `Add`, which marks dirty; one past it can enter only through a vacancy, which is the first case. A short window has no cut, so every `Add` is delivered. A provisional bound is published only after adds were absorbed, so the window is already dirty. Induction, upstream first: a limiter with no limiter upstream reconciles by I2 to the first `limit` rows of a settled input; its emissions are ordinary pushes. Every limiter downstream then reconciles over settled inputs by the same argument. Non-members hold nothing, so at the end every held row has received every delta (I3) and every window equals the fresh answer (I2, I4). That is view-after-write == fresh-query. What this argument does not need is the point: no statement about which rows a mid-push scan may meet, no ordering of deliveries, no depth. ## 8. Costs - **Memory.** One sort key per row in every maintained window. On the client the view holds those rows already. On the daemon it is new: a family root keeps one window per binding, so `limit × bindings` keys. `Cap` pays this today for EXISTS. If it bites: store a hash per member and recover order by fetch, as now (§12). - **Reconcile work.** The exact shortcut keeps a single-row change at a constant number of keyed fetches. A scan is at most `limit` rows and is paid only by pushes that are already fan-out sized. - **Emission moves later.** Adds reach the consumer after the source change's last connection has pushed, not in the middle of it. Nothing downstream is known to depend on the old position; §10's differential lanes are the check. - **Still O(N):** inner deliveries at depth ≥ 2, and the doomed-tail scan (§6.4). ## 9. Alternatives considered | Alternative | Why not | | --- | --- | | The cut with a mid-push refill (316 §17.5 as built) | Correct and measured at depth 1. One level down the cut never engages (§2) | | Upstream's `TakeGate` + `reconcile` | Fixes aligned removes at any depth; leaves opposed adds (§2). The gate must be opened around the `Take`'s own scans; the overlay reads a live bound that disappears mid-push; the pending window is a third state its readers must know | | The cut, a captured bound, and a deferred refill | The same coverage as upstream with the bound fixed. At depth 2 every inner delivery after the first in-window remove starts an outer fan-out against a pending window, so that third state is on the main path, in `window_at`, in both eviction guards and in the short-window rule | | Push the cut down to inner joins | §3: sound for removes, an ancestor probe per row, an upward allow-list per depth, and nothing for opposed adds | | Keep the mid-push path when every in-flight fan-out is governed; defer otherwise | Two limiters to keep correct instead of one, and the intricate one is the one kept | | Let the cascade run and coalesce the output | Fixes the change count and none of the work; the O(N²) flipped cells remain | ## 10. Verification - **Pins from §2:** at most `2 × limit` changes in all four cells, flipped and not, at depth 2 and depth 3, plus a leaf-rows-scanned pin in the style of `scan_ends_at_the_cut`. - **Both paths through the whole `it` suite** and every fuzz lane while the kill switch exists, as the cut had. The widened decorated-push lanes already mutate every table of an OR-ed, flipped, depth-3 skeleton; each gains an assertion that the boundary path fired. - **Operator state after later writes:** `exists_partition_churn_leak.rs`, `take_partition_leak.rs` and the #594 regressions stay green unchanged. Eviction parity is the part of §5 most likely to need a second look. - **One source change through more than one connection, in both orders** (`take_bounded_fanout.rs`), and both halves of a split edit hitting one window. - **A self-join** where one source change edits a member's sort key through the parent connection and fans out through the child connection — the case the published bound's "never before a member" rule exists for. - **Optional:** a small TLA+ model beside the four in `tla/` — one window, `limit` 2, four rows, arbitrary deliveries then a boundary — checking I1 and I4. ## 11. Slices | Slice | Content | Gate | | --- | --- | --- | | S0 | `Take` stores `members`; `fetch` answers from them; behaviour otherwise unchanged | Every lane green on the unchanged push paths. Reviewable alone | | S1 | The dirty worklist and the drain in `try_source_push`; §5.2 and §5.4 for changes that arrive while a child fan-out is in flight; kill switch | §10's pins; both paths green | | S2 | The provisional bound (§6.3) | The scan pins and the depth-1 `measure` table unchanged | | S3 | Every change takes the same routine; delete the in-place paths (§5.7) | Both paths green one last time, then the switch goes | | S4 | `Cap` (§5.6) | A large-partition probe | | S5 | Inner narrowing (§6.4) | Its own design pass against 316 | ## 12. Open questions 1. **Boundary `Remove`s.** A displaced member still passes, so its node is fetched by key post-change. The flat `Remove` is row-only (`flat.rs:64`) and the view's remove path consumes only the row, so the node's subtree should not matter — but a nested limiter's `Remove` also enters an outer join's child port, and this is the #594 class. Pin it first. If the whole row were stored per member, the fetch could go. 2. **Key representation.** Sort key, whole row, or hash — a memory trade on the daemon (§8). Needs a number from a family workload before S0 fixes the storage shape. 3. **Eviction parity.** Rows absorbed and then not admitted sit past the new bound with hydrated upstream partitions until something touches them. That matches today's non-members left behind by a bound that moved down, but it is argued, not measured. 4. **Drain per transaction** instead of per source change. The rules tolerate a window that stays dirty across changes. Whether anything else does is unexamined. 5. **311 and 316.** A reconcile scan from `start` carries a `start`, so 311's observation rule ignores it as it ignores refills today. 316 §7.4 ("limit movement and empty scopes") should be re-read against a bound that moves only at the boundary. 6. **Upstream.** The same split would need member identity in `take.ts`. Row 6 of §1 is open on their branch.