# Content temporarily unavailable # Eager indexed ordered-window repair oracle review Reviewed source head: `ff731ad1c` on `perf-ordered-loader`, with the perf fix in `44c90e0ad` and the null-ordering fix in `ff731ad1c`. The base is `65992aacd` (`main` with #1650). ## Contract and evidence An ordered, limited live query over an eager source with an index on its leading order term must show the first `limit` rows after `offset` of the eligible source rows after every change. The authority is `packages/db/src/query/live/ARCHITECTURE.md`, "Ordered requests, continuation, and recovery" and "Atomic window publication", and the documented order in `docs/guides/live-queries.md`: nulls first by default, NaN greater than every non-null value, ties by key. Work is a separate law. With an index, the source delivers at most `2 * (offset + limit) + tied rows + 1` rows per change. That is one reacquired prefix of the window, the tie group at its boundary, one refill of at most the window, and the changed row. The bound does not grow with source size. Each generated source holds 200 eligible filler rows outside every window, so a read that resends every matching row exceeds it. A NaN or null boundary cannot be expressed as a cursor (`canExpressCursorOrder`), so the documented full-source fallback applies and only the rows law is checked while such a rank is present. An unindexed source also falls back to full source. The owner is the "eager indexed ordered windows" section of `packages/db/tests/query/ordered-work-oracle.property.test.ts`. Its model is a plain array sorted by the documented order. It shares no code with the loader, the comparator, or the index. ### Original failure On `65992aacd`, a visible delete or an eligibility change delivered 202 to 206 rows against a bound of 5 to 8: "rows delivered by step 1: expected 202 to be less than or equal to 5". The ordered-prefix repair's local read was predicate-only, so it resent every matching row. In the rindle "list: newest 50 open" case this cost 1.107 ms per insert/delete pair at 10,000 issues. ### Repair - `requestSnapshot` reads only the first `limit` matching local rows when the subscription has an order index, the request has `orderBy` and `limit`, and the source is eager. An on-demand source keeps the full delivery that its repair chain relies on. - An eager source's repair may settle synchronously, so its tie and refill steps finish inside one graph run. Without this, widening a window after a repair published twice: once after the tie request and again after the refill. That broke two pagination-oracle laws ("keeps a NaN window coherent through equal and changed source ranks" and "rebuilds the full boundary when widening after an out-of-window rank update"). ### Alternative (b), considered and rejected Moving the bounded read into `loadOrderedPrefixRepair` through `requestLimitedSnapshot` gave 2.28 ms per pair, slower than `main`. The profile showed `ascComparator` at 27%, `getPairOrNextLower` at 25%, and the BTree index's take loop at 18.5% self time. The cause is semantic, not per-call setup: `requestLimitedSnapshot` skips keys already sent to the query, so after a repair it walks past the whole visible window, one tree descent per step, and loads the next `limit` rows instead of resending the prefix. That also grows the query's private state on every change. ### Null ordering `findIndexForField` served a descending, nulls-first query with an ascending, nulls-first index wrapped in `ReverseIndex`. Reversing the index moved its null group to the end. On `44c90e0ad` the pinned case failed with "expected [ 1000 ] to deeply equal [ +0 ]", and both campaigns failed. `ReverseIndex` now takes the requested null placement and reads the null group from that end. ## Mutant results | Mutant | Outcome | | --------------------------------------------------- | ---------------------------------------------------------------------------- | | Original predicate-only repair read (`65992aacd`) | Assertion failure, work law: 202 > 5. | | Ordered read without its limit (M3) | Assertion failure, work law: 202 > 5. | | Bounded read for on-demand sources too (M4) | Assertion failure in 2 pagination-oracle cases. | | Never repair after a visible change (M5) | Assertion failure, rows law: `expected [ 2 ] to deeply equal [ 1 ]`. | | Read `limit + 1` rows | Assertion failure, work law: 4 > 3. | | Read `limit - 1` rows (M1) | Survives. Equivalent at the public observation, see below. | | Read in the reversed direction (M2) | Survives. Equivalent at the public observation, see below. | | Eager repair stays asynchronous | Assertion failure in the same 2 pagination-oracle cases (split publication). | | `ReverseIndex` ignores the requested null placement | Assertion failure in 3 of 4 tests, rows law. | M1 and M2 deliver no more rows than the bound allows, and the refill and tie-boundary chain still reaches the correct window. A tighter work bound cannot reject them, because they deliver the same number of rows or fewer. The extra refill request they cause is an internal request count, not a public observation of this law. Both are equivalent within the tested domain. ## Benchmark `scripts/bench/incremental-update.ts` gains a "list: newest 50 open" case with a visible issue delete. With an index at 10,000 issues, its median per-write latency is 0.63–0.70 ms on `main` and 0.17–0.18 ms with the fix. Without an index it stays near 4 ms, because the full-source path is unchanged. Overall geomean is 0.95–0.96× against `main`, with a same-code noise run of 1.00×. ## ORC-012 requirement audit | Requirement | Outcome | | ----------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | ORC-001 | Applicable. The rows and work laws and their authority are above. The claim covers eager sources only. On-demand providers keep their own work laws in this owner. | | ORC-002 | Applicable. The model sorts plain rows by the documented order with its own comparator. It does not import the loader, the index, or `makeComparator`. | | ORC-003 | Applicable. The section's opening prose states both laws, the bound's derivation, the grammar, the production path, the checkpoint and the limits. | | ORC-004 | Applicable. The grammar crosses sync and local-only writes, index present or absent, both directions, one or two order terms, limit 1–3, offset 0–1, and upserts and deletes over ids 0–29 with ranks 0–15, NaN and null. The pinned delete case and the pinned null case reconstruct the reported traces. The work law skips only steps whose boundary value is NaN or null; it asserts on 88.5% of indexed single-term steps. The reversed-index oracle covers `nulls: 'last'`. Excluded: on-demand sources and custom collation. | | ORC-005 | Applicable. The driver runs a real live-query Collection over a real eager Collection. It counts rows a snapshot returns from `currentStateAsChanges`, rows the source delivers to the query's subscription (which include index refills), and rows `entries()` yields. | | ORC-006 | Applicable. The original code and the mutants above reach the checkpoint. Each outcome is classified. | | ORC-007 | Applicable. Each campaign runs with fixed seed 2044 and with a random or replay seed through `oracleRandomParameters`, property `ordered-work.eager-indexed-window`. | | ORC-008 | Applicable. The model keeps only the current rows. Order is derived from them. | | ORC-009 | Applicable. "Read rows", "delivered rows" and "scanned rows" are work observations, not production states. | | ORC-010 | Applicable, with a gap. Cleanup runs in a `finally` block, so a cleanup error after an assertion failure would replace it. No run showed a cleanup failure. | | ORC-011 | Inapplicable. No reviewer named a fault shared by the model and production. | | ORC-012 | This record. | | ORC-013 | Applicable. The work bound is a threshold law. The `limit + 1` mutant exceeds it by one row (4 > 3). | | ORC-014 | Inapplicable. No controlled provider supplies a premise. | ## Unresolved - Per-change work for on-demand sources is not bounded by this owner. - A reversed read gathers the whole nullish group on each read: it builds a set of the nullish keys, sorts them, and calls the filter once on each. So a read costs O(m log m) in the nullish group size m, even when it returns no nullish key. The work law bounds filter calls on non-null keys by `n` and allows one filter call per nullish key. Large nullish groups are rare in ordered windows, so the reader keeps this cost for simpler code. The bounded nullish read of `d2bb4c3f0` was replaced by this simpler reader in the follow-up commit; a later index-API change that removed per-read group sorts was reverted (`e0ab7e0f5`). Reads of equal non-null values still sort each group, as on `main`. - An initial full-source ordered load over an eager source stays asynchronous, as on `main`. #1896 states a general rule for synchronous results, so this is a likely gap; it is the next change, not this one. ## Review follow-up (2026-10-06) A code review of this branch found eight issues. The probes, the RED output and the mutant runs are in the PR evidence; this section records the outcomes. | Finding | Outcome | | ------------------------------------------------------------------------ | ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | R1: a reversed index sorted and filtered every nullish key on each read | Fixed. The new reversed-index oracle (`reverse-index-oracle.property.test.ts`) bounds filter calls by the position of the n-th accepted key. RED on the branch: 5,000 filter calls for n = 50 among 5,000 nullish keys. A follow-up simplified the reader: each read now gathers the nullish group, and the law allows one filter call per nullish key while still bounding non-null filter calls by `n` (see Unresolved). A follow-up (`afe19e442`) also removed the per-read sort of an equal-value group, through a new index API and write-path upkeep. It was reverted in `e0ab7e0f5`: that sort is old behavior on `main` and not part of this regression, so the change did not earn its code weight. See Unresolved. | | R2: a second order term took the bounded read into a full in-memory sort | Fixed. The bounded read applies only to one order term. The eager-window oracle gains a second order term and a scan law (one pass per change). RED: 400 rows scanned against a bound of 201. Removing the gate fails it. | | R3: ARCHITECTURE.md contradicted the synchronous repair | Fixed. Both passages now name the eager ordered-prefix exception. | | R4: the synchronous gate also matched full-source requests | Fixed by narrowing the gate. A lifecycle witness checks that an eager `fn.where` ordered window is `loading` at creation; it fails on the widened gate and passes on `main`. | | R5: index refills were not counted | Fixed. The oracle also counts rows delivered to the subscription and bounds the initial load. The unbounded-refill mutant now fails (200 > 3); before, the refill ran only during the initial load, which the law did not bound. | | R6: the work law skipped every history with a NaN or null rank | Fixed. It skips only an inexpressible boundary and counts tie groups at the boundary, over a larger domain. A mutant that resends about 20 domain rows fails (23 > 3). | | R7: the reader returns two tie-key orders | Documented, not changed. The query breaks ties by ascending key, so the reviewer's fix would put nullish keys in the wrong order. The reversed-index oracle states the reader's order. | | R8: `sourceHoldsAllRows` was optional and always set | Fixed. It is required. | | R10: a `null` cursor in a nulls-first reversed read | Refuted. A cursor at `null` is past the nullish group, so the non-null keys are the correct result. The order law passed on the original code at 20× runs. | After these fixes, the original predicate-only read, `limit + 1`, the resend-domain mutant and the unbounded refill all fail. `limit - 1` (M1) still survives, as above. ## Second review follow-up (2026-10-06) A high-effort code review of `308bb12b9` raised nine findings. Each was checked with a probe on this branch and on `main`, or with a mutant. | Finding | Outcome | | --------------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | 1: a synchronous prefix repair holds no publication gate, so a later asynchronous step could publish a partial window | Refuted for both named paths. A repair whose boundary enters a NaN tie group falls back to a full-source read (204 rows delivered) and publishes `[61,62]` once, as on `main`. A blocked LEFT-joined filter publishes nothing while blocked and `[2,3]` once after release, as on `main`. The eager-window oracle now asserts one publication per change whose window equals the model, and pins the NaN tie-group repair. A mutant with `main`'s asynchronous gate also passes this law: single-change histories publish once under both designs, and the pagination laws own window moves. | | 2: `ReverseIndex` requires `nullsFirst` | Low. `ReverseIndex` is a read-time wrapper that `findIndexForField` builds; no caller outside this package constructs it. The parameter then defaulted to `false`; the external review below showed that default was wrong for a nulls-last index, and omission now means plain reversal. | | 3: a bounded read skips stale rows kept after a failed truncate replay | Refuted. An eager collection never calls `loadSubset`, so it has no replay demand to fail (the probe recorded no calls). Source cleanup puts every dependent live query in its terminal error, on this branch and on `main`. | | 4: two-term and unindexed eager repairs settled synchronously | Fixed. The loader oracle pins that an eager prefix repair settles synchronously only for a bounded read. RED on `308bb12b9`: the two-term and unindexed cases settled before `loadMore` returned. The gate now uses the same bounded-read fact as the subscription; the old gate fails 2 cases. | | 5: the source-holds-all-rows rule was coded twice | Fixed. The loader computes the bounded-read fact once and passes it to `requestSnapshot`, which no longer checks the sync mode, the index or the term count. A subscription that ignores the flag reads 206 rows where the bound is 5. | | 6: the bounded read repeats index discovery and could fall back to a full sort | Partly confirmed. Index discovery per repair costs one scan of the collection's index list and is kept. A silent fall back to a full sort was not caught: the scan law allowed one pass. A bounded step must now scan no more rows than its work bound; a mutant that disables the index read in `getOrderedKeys` fails (406 > 204). | | 7: each reversed read gathers the nullish group | Accepted design (see Unresolved). | | 8: two tie-key orders cut through a NaN tie group | Duplicate of R7. A NaN boundary cannot be a cursor, so the loader reads the full source whatever the tie order, and the window publishes once with the right rows. | | 9: `sourceHoldsAllRows` defaulted to true for an unknown source | Fixed. It reads the resolved source collection, which is never undefined there. | ## External review follow-up (2026-10-07) An external review of `3dc581394` raised three findings, each with a reproduction against `9e8ed9978`. All three were confirmed and fixed. | Finding | Outcome | | --------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | | 1 (P1): a bounded repair kept a distant joined row instead of the next eligible row | Confirmed, a regression of this change. The law is the eager-window rows law: the window equals the first `limit` eligible rows. A full window is evidence of that only when every row the source sends passes the filter; a LEFT-joined filter drops rows after the source's `limit`, and a row that an earlier live update sent can fill the window. The eager-window oracle gained a filter dimension (source predicate, function filter, LEFT-joined marker), a label-only `touch` command, a `delete-visible` command, and a campaign fixed to the joined premise (`ordered-work.eager-joined-window`). RED on `3dc581394` for the pinned history (root ranks 1..10, markers on even ids, limit 1, touch 10, delete 2): rows `[10]` where `[4]` is expected; `9e8ed9978` gives `[4]`. Fix: a plan with a joined filter keeps the full local read, so it also keeps `main`'s asynchronous repair. Re-admitting joined plans fails the pinned case on both sync paths and the fixed-seed joined campaign (an assertion failure); the random joined campaign catches it on about a third of seeds. A function filter, residual predicates, inner joins, `groupBy`, `distinct` and custom collations already require the full source, so they never reach the bounded read; the function filter is in the grammar and passes. | | 2 (P2): a reversed read required an `eq` lookup that admission does not check | Confirmed. The reader now gathers the nullish group with `equalityLookup`, which every index implements. A range-only index witness reads in both null placements, and a public witness orders a descending snapshot and a limited live query through it. RED on `3dc581394`: `Unsupported operation: eq` from every read; the public witness passes on `9e8ed9978`. A mutant that calls `lookup('eq')` again fails 3 cases with that runtime failure. | | 3 (P2): the `nullsFirst = false` default changed plain reversal over a nulls-last index | Confirmed. Omitting the argument now reads the original index's reversed walk, as earlier releases did; `findIndexForField` always passes it. A legacy witness pins the earlier release's keys for BTree and Basic indexes (`takeFromStart(3)` is `[1, 3, 2]`, `take(3, null)` is `[3, 2]`); RED on `3dc581394` returned `[3, 2, 1]`. The old default fails both cases. | Two observations made while extending the oracle are outside this change: - An unindexed or indexed joined plan reads its full source twice per change (402 rows scanned where the source holds 201), on `9e8ed9978` too. The scan law now covers source-filter plans only. - When rows tie on every `orderBy` term, a joined query returns them in the joined result key's order, not the source key's: for ties at rank 11 among ids 2 and 10 with limit 1, both commits return `[10]`. The live-queries guide promises order only by `orderBy` terms, so the joined window is compared as any valid first `limit` rows. The source-filter window still compares exact ids, which assumes ties by source key; that assumption is unsupported by the guide and is open.