From 52c5445fc4767fd346621373d65dcdc2fdbe25d4 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sun, 11 Oct 2026 20:21:35 +0530 Subject: [PATCH 1/4] docs(spec): streaming query engine design (#473) Snapshots with page quarantine, columnar id batches, the operator set, memory accounting with an optional cap (QRY-012), large transactions committed as checkpoints, oracle-based migration and the sub-issue plan. Refs #473 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_012wXxZguv7PgKQjMMH4yJ5h --- .../2026-10-11-streaming-engine-design.md | 336 ++++++++++++++++++ 1 file changed, 336 insertions(+) create mode 100644 docs/superpowers/specs/2026-10-11-streaming-engine-design.md diff --git a/docs/superpowers/specs/2026-10-11-streaming-engine-design.md b/docs/superpowers/specs/2026-10-11-streaming-engine-design.md new file mode 100644 index 0000000000..c199a3e8bc --- /dev/null +++ b/docs/superpowers/specs/2026-10-11-streaming-engine-design.md @@ -0,0 +1,336 @@ +# Streaming query engine — Design + +**Issue:** #473 (streaming, pull-based operator pipeline behind the cursor API; follow-up to #432) +**Milestone:** v3.0.0, branch `v3`, file format v8 (no format change) +**Folds in:** #518 (AVET lookups, parked on `perf/518-avet-lookup`), #530 (ids until projection) +**Followed by:** #306/#310 (`:limit`/`:offset` syntax and the 10M acceptance test), #185 (profiler) +**Status:** design approved 2026-10-11; not implemented + +## 1. Problem + +`Minigraf::query` returns a `Cursor` (#432), but the answer is computed when the cursor +opens: `execute_query` loads the facts its patterns touch into a `Vec`, the +`PatternMatcher` joins them into `Vec>` bindings, and the cursor +walks the final `Vec`. Memory follows input size, not answer size: + +- `[?e :entity-type :type/function]` over 10M facts reads every fact of the attribute, + materialises each one with UUIDs and owned strings, then keeps ten rows. +- `count` over 10M facts holds 10M bindings before counting. +- A recursive rule holds its whole input in a `FactStorage` plus a `BTreeSet` of seen facts. +- A 1M-fact `transact` is parsed into one `Vec`, staged, and written as one WAL entry. +- Closing a cursor early saves nothing: the work is already done. + +A cursor also has no snapshot of its own. The answer is fixed because it is computed at +open. Once it is computed lazily, a checkpoint that frees and reuses pages under an open +cursor would corrupt its reads. The fact log (#430) avoids this today by refusing +checkpoints while a log is open (`API-013`). + +## 2. Goals and non-goals + +Goals are #473's: + +1. **Memory follows operator state, not input size.** Pipelined operators hold one batch. + Only the stateful operators hold more, and the planner avoids that state where index + order allows. +2. **Incremental delivery** with early termination, cancellation and backpressure. +3. **Streaming aggregation**, one pass, hash- or sort-grouped. +4. **Consistent snapshots** at open; writes committed later do not change the answer. +5. **Streaming transactions**: a large `transact` never holds more than one chunk of + parsed facts. + +Non-goals: +- No Datalog semantics change. `:find` keeps returning a bag. +- No file-format change. The `.graph` layout stays v8. +- No parallel execution (the operator model does not preclude it). +- No spilling and no `spill_dir`. +- No public API change: `Cursor`, `Batch`, `PreparedQuery` and every binding are untouched. + +## 3. Decisions + +| # | Question | Decision | +|---|---|---| +| D1 | Scope for v3.0.0 | All of #473: every operator, `Recursive`, streaming transact | +| D2 | Snapshot | Pin the committed generation; copy the pending facts the plan reads; quarantine freed pages in memory (§4) | +| D3 | Fact log | Moves to the same pin; `API-013` stays registered, deprecated | +| D4 | Migration | New engine alongside the old one; the old one is a test-only oracle, deleted before v3.0.0 (§9) | +| D5 | `:limit` | #473 builds the `Limit` operator; #306/#310 add the syntax afterwards and take the 10M acceptance test | +| D6 | Large state | No default budget, no spill; byte accounting, `try_reserve` growth, an optional cap that raises one new QRY code (§7) | +| D7 | Row format | Columnar batches with plan-time variable slots; entities and idents stay DICT ids until `Project` (§5) | + +## 4. Snapshots + +### 4.1 What a cursor holds + +At open, under the storage read lock, a cursor takes: + +1. **A committed snapshot**: the active meta page's generation and its five tree roots, + as an `OnDiskReader` over those roots. The reader never looks at a newer meta. +2. **A pin** on that generation (§4.2), released on `close` or drop. +3. **The pending facts the plan reads.** Each `Scan` in the plan copies the pending facts + in its range (the same ranges `FactStorage::get_live_facts` serves today). Pending + facts are those not yet checkpointed, so the copy is bounded by + `wal_checkpoint_threshold` (default 1,000 entries). With checkpointing disabled the + copy follows the pending set; that is the documented cost of disabling it. +4. **The `tx_count` bound** at open, applied to the copied pending facts. +5. **Provisional ids** (§5.3) for pending entities and idents that the DICT does not have. + +After that the cursor needs no lock. Writers and checkpoints proceed. + +### 4.2 Page quarantine + +A checkpoint is copy-on-write: it writes only pages the active meta does not reference, +and the pages the new meta stops referencing go on the free list (`finish_free_list`). +The *next* checkpoint may hand them out and overwrite them. A cursor pinned to an older +generation may still read them. + +The allocator therefore keeps, in memory only, a **quarantine**: for each checkpoint, +the generation it produced and the ids it freed. An id freed by the checkpoint that +produced generation `g` is reachable from every generation `< g`. While any pin `< g` +exists, `PageAllocator::alloc` skips that id: it stays listed as free, and +`finish_free_list` lists it again with the read-but-unused ids. When the oldest pin +drops, the quarantine entries at or below the new oldest pin are released. + +Properties: +- **No format change.** On disk, a quarantined page is an ordinary free page. +- **Crash-safe.** After a crash nothing is pinned, so every free page is reusable. +- **Growth is bounded by the pin.** While a cursor is open the file grows by the pages + the intervening checkpoints free, as in LMDB with a long reader. `verify()` already + counts free pages; nothing changes there. +- **Page cache.** A quarantined id is never rewritten, so a cached page can never serve + another generation's bytes. + +The in-memory (`MemoryBackend`) and browser (`BrowserBufferBackend`) backends go through +the same allocator, so they quarantine the same way. A browser flush writes dirty pages +only, which never include a quarantined page. + +### 4.3 Fact log (D3) + +`Minigraf::fact_log` pins its generation the same way and copies its pending facts at +open. Checkpoints no longer fail while a log is open, and `log_pins()` stops gating the +automatic checkpoint (`db.rs:767`, `db.rs:1602`). `API-013` stays in the registry and in +`docs/ERROR_REFERENCE.md`, marked deprecated, and is never raised again. + +`rebuild_indexes` rewrites every tree; it also proceeds, since pinned pages are +quarantined like any other freed page. + +## 5. Rows + +### 5.1 Batches + +A `Batch` (internal; the public `Batch` wraps it) holds up to 1,024 rows as one column +per variable slot. The planner numbers the variables of each operator's output, so a +column is found by index, never by name. `HashMap` bindings are gone from +the new engine. + +### 5.2 Cells + +```rust +enum Cell { + Eid(u64), // entity: DICT id or provisional id + Iid(u64), // ident (attribute or keyword value): DICT id or provisional id + Val(ValueRef), // string, integer, float, boolean, null; long strings by vref +} +``` + +Ids stay ids through joins, filters, sorts and aggregation. `Project` turns the cells of +the rows it returns into `Value`s, so a query that keeps ten rows translates ten rows +(#530). Literals in the query are resolved to ids once, at plan time; a literal the DICT +and the snapshot do not know resolves to "no match", so its `Scan` is empty. + +### 5.3 Provisional ids + +Pending facts carry UUIDs and strings. At open the snapshot gives each pending entity +and ident that the DICT does not hold a provisional id from `next_eid` / `next_iid` +upwards, in a map private to the cursor. The whole snapshot then has one id space. +Provisional ids are never written; a checkpoint assigns real ids independently. + +### 5.4 Cross-kind matching + +The matcher today lets a keyword constant `:k` match `Keyword(k)` and `Ref(uuidv5(k))`, +lets a UUID constant match a ref or a keyword naming that entity, compares floats within +an epsilon, and matches `nil` to `Null`. The new engine keeps every one of these rules: + +- **Constants** resolve to every id they can match: `:k` to `Iid(k)` and to the `Eid` + of `uuidv5(k)` if that entity exists. These are the AVET probes #518 built + (`ValueProbe`), now in id form. +- **Join keys** compare `Iid(k)` equal to `Eid(e)` exactly when `e = uuidv5(k)`. The + snapshot resolves that per ident lazily and caches it; the number of idents bounds it. +- **Floats** keep the matcher's epsilon rule. A join on a float-valued variable uses the + same comparison as today; the oracle tests (§9) pin which rows match. + +## 6. Operators + +All operators implement `open` / `next_batch() -> Result>` / `close`. +`close` propagates to the children, so a closed cursor stops all upstream work. + +### 6.1 Pipelined (hold one batch) + +- **`Scan`** over EAVT, AEVT, AVET or VAET, chosen by which pattern positions are bound. + It merges the committed snapshot's keys with the copied pending facts per triple and + decides net-assert on keys (#379), with the `:as-of` bound and `:valid-at` / + `:any-valid-time` pushed into the walk. Attribute+value patterns read AVET (#518's + `Scan::AttributeValue` / `AttributeKind` and its string/float/keyword/ref rules). + Output is in index order, and the plan knows that order. +- **`IndexNestedLoopJoin`**: for each outer batch, probes the inner pattern's index with + the bound positions. The default join when the inner pattern has a usable index. +- **`Filter`** / **`Expr`**: predicates and bindings from expression clauses. +- **`Project`**: column selection and id→value translation (§5.2). +- **`Union`** for `or` / `or-join`. +- **`Limit`** / **`Offset`**: stop pulling, then `close` the child. + +### 6.2 Stateful (hold more than a batch) + +- **`HashJoin`**: builds on the smaller side when neither side has a usable index. +- **`NotJoin`** / anti-join: hashes the right side. +- **`Distinct`**: hash on the row. Used only where the engine deduplicates today (`or` + branches, `count-distinct`, the recursive relation). Plain `:find` stays a bag. +- **`Sort`**: in memory; skipped when index order already gives the order; becomes + top-k under a `Limit`. +- **`Aggregate`**: ungrouped aggregates run in constant memory; grouped ones hash on the + key, or stream sort-grouped when the child is ordered on it. +- **`Window`**: today's window functions over a partitioned, ordered input. +- **`Recursive`**: semi-naive fixpoint per stratum. The delta and the accumulated + relation are hash relations of id rows, replacing `FactStorage` plus + `BTreeSet seen_facts`. Magic sets and stratification stay as rewrites in front of the + planner. `max_derived_facts` (`INT-020`) still bounds the accumulated relation. + +### 6.3 Planner + +`optimizer.rs` and `prepared.rs` produce an operator tree instead of a clause order for +the matcher. Rules: + +1. Pick each pattern's index from its bound positions; prefer AVET for `[?e :a C]`. +2. Order joins by the existing selectivity estimates; use `IndexNestedLoopJoin` when the + inner side is indexable, else `HashJoin` on the smaller side. +3. Use sort-grouped aggregation and skip `Sort` when the input order allows. +4. Push `Limit` into `Sort` (top-k). + +A `PreparedQuery` keeps its plan and re-resolves only its bind slots and literals per +execution. Each operator counts rows in, rows out, batches and bytes held; the profiler +(#185) reads these counters. + +`optimizer.rs` is disabled under the `wasm` feature today. The new planner keeps that +gate on join reordering only; index choice and operator selection run on every target. + +## 7. Memory (D6) + +- **No default budget and no spilling.** Streaming makes large state rare: only the + operators in §6.2 hold more than a batch. +- **Accounting.** Each stateful operator tracks the bytes it holds and grows its tables + with `try_reserve`, so an allocation failure becomes an error instead of an abort + where the allocator reports it. (With Linux overcommit it rarely does; the cap below + is the dependable control.) +- **Optional cap.** `OpenOptions::query_memory_limit(bytes)`, off by default + (`usize::MAX`). When the bytes held by one query's stateful operators would pass it, + the query fails with a new code, **`QRY-012`: query memory limit exceeded**, naming the + operator and the limit. The cursor is closed; the database is unaffected. +- `max_results` keeps its meaning for `execute` only. A cursor has no result cap. +- **Bindings.** Every binding gets `query_memory_limit` on its `OpenOptions` record and + the `QRY-012` code. UniFFI shims map the `usize::MAX` sentinel to `i64::MAX`, as for + `wal_checkpoint_threshold`. Adding an `ErrorCode` variant breaks the UniFFI bindings + until they regenerate, so the binding PRs follow the core PR. + +## 8. Transactions + +### 8.1 Parsing + +`transact` and `retract` go through a streaming EDN parser that yields statements, which +are materialised into facts in chunks (default 4,096 facts). Validation (value limits, +valid windows, `check_one_window_per_triple`, `API-011`) runs per chunk; the duplicate +check across chunks reads the transaction's own facts through `Scan` (§8.3). + +### 8.2 Where chunks go + +A transaction below `wal_checkpoint_threshold` facts is written exactly as today: one +WAL entry at commit, then applied to the pending store. + +A transaction that reaches the threshold switches to **writing its chunks into +copy-on-write pages**, the way `LogWriter` (#431) builds batched checkpoints: + +1. On the switch it fixes its `tx_count` (known: the write lock is held) and its + `tx_id` (the current time; the lock keeps it monotonic). Facts staged so far are + stamped and inserted first. +2. Each later chunk is encoded and `cow_insert`ed into working copies of the trees. + Pages written by this transaction and superseded within it are reused at once; pages + of the active generation it supersedes are freed at commit. +3. **Commit** checkpoints the pending store into the same working trees, writes the new + meta page and deletes the WAL: the transaction commits as a checkpoint. +4. **Rollback** or a crash before the meta write leaves the active meta and its free + list untouched. Every page the transaction wrote was either on that free list or past + the committed `page_count`, so the next checkpoint reuses or overwrites it as usual, + exactly as after a crash mid-checkpoint. The allocator skips quarantined ids here too. + +This replaces the "append each chunk to the WAL" wording in #473. That wording still +left all facts in the in-memory pending store after commit, so a 1M-fact `transact` +would hold 1M facts in memory and fail the acceptance test in §10. Writing large +transactions as a checkpoint keeps the WAL format and the small-transaction path +unchanged. + +A transaction's `tx_id` is the switch time instead of the commit time for large +transactions. Both lie inside the write lock, so the order of transactions and their +`tx_count`s do not change. The change is noted in `CHANGELOG.md`. + +### 8.3 Reading your own writes + +A `WriteTransaction`'s queries see a snapshot whose committed part is the working trees +(when it has switched) and whose pending part is the pending store plus the chunks not +yet inserted. It is the same `Scan` over a different snapshot. + +Schema validation and the v8 multi-value fix (#371, #287) are unaffected. + +## 9. Migration and testing (D4) + +- The new engine is built in `src/query/engine/` beside the existing executor. A query + runs on the new engine when every clause it uses has an operator; otherwise on the old + path. Each sub-issue widens that set. +- **Oracle.** The old path stays as a test-only oracle (`#[cfg(test)]` and a + `test-oracle` feature for integration tests). Differential tests run every query in + these suites through both engines and compare row bags: + - the model-based test (`tests/model_based_test.rs`, `tests/reference_model/`), + - the property tests (`tests/property_test.rs`), + - the golden corpus (`tests/golden_corpus_test.rs`), + - the existing integration suites, through a test hook on `execute`. +- When every query runs on the new engine, the old path and the oracle hook are deleted. + This happens before v3.0.0. +- `tests/cursor_test.rs` and every binding suite pass unchanged throughout. +- **Measurements.** The #394 envelope at 100K/1M/10M on an idle machine before and after + each phase; the #379 point queries are the regression guard. + +## 10. Acceptance tests + +From #473, with the `:limit` test moved to #306/#310 (D5): + +- [ ] `count` over 10M facts runs in constant memory. +- [ ] Grouped `count` with 1M groups completes with memory proportional to the groups; + with `query_memory_limit` below that, it fails with `QRY-012`. +- [ ] A recursive rule deriving 5M facts completes with memory proportional to the + derived relation; `max_derived_facts` still stops a runaway rule. +- [ ] Closing a cursor after the first batch stops upstream work (operator counters). +- [ ] A cursor's answer is unchanged by writes and checkpoints made while it is open, + including checkpoints that free pages it reads; the fact log likewise. +- [ ] A 1M-fact `transact` never holds more than one chunk of parsed facts. +- [ ] Python binding round trip with batches of 1,000; wall time and RSS in the envelope. +- [ ] Every existing `execute`, cursor and binding test passes unchanged. +- [ ] `[?e :a C]` reads only `C`'s AVET range (#518's envelope numbers hold). + +## 11. Delivery + +Sub-issues under #473, each a PR to `v3` with no closing keyword for #473: + +1. **Snapshots and page quarantine** (§4): pins, quarantine in `PageAllocator`, cursor + and fact-log snapshots, `API-013` deprecated. +2. **Operator core** (§5, §6.1 minus joins, §6.3 v1, §9 harness): `Batch`/`Cell`, + provisional ids, `Scan` over all four indexes including #518, `Filter`, `Project`, + `Limit`/`Offset`, single-pattern queries on the new engine, the oracle harness. +3. **Joins**: `IndexNestedLoopJoin`, `HashJoin`, join planning. +4. **Negation and disjunction**: `NotJoin`, `Union`, `Distinct`. +5. **Aggregation and ordering**: `Aggregate`, `Sort`, `Window`. +6. **Recursion**: `Recursive` with magic sets and stratification; rule queries move over. +7. **Memory accounting and cap** (§7): `QRY-012`, `OpenOptions::query_memory_limit`, + bindings. +8. **Streaming transactions** (§8). +9. **Removal and measurement**: delete the old engine and oracle hook, run the envelope + at 100K/1M/10M, update docs. + +After #473: `:limit`/`:offset` syntax with the 10M acceptance test (#306/#310), then the +profiler (#185). From 013dd74ac65167c85833c5412fa76d01d435597e Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sun, 11 Oct 2026 22:11:13 +0530 Subject: [PATCH 2/4] docs(spec): precise wording; snapshots share pending facts; large-transaction statement rules (#473) Checked every claim against the code: pending store and checkpoint terms, in-memory databases, pseudo-attributes, max_results, float join keys, last-statement-wins across chunks. Refs #473 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_012wXxZguv7PgKQjMMH4yJ5h --- .../2026-10-11-streaming-engine-design.md | 537 +++++++++--------- 1 file changed, 272 insertions(+), 265 deletions(-) diff --git a/docs/superpowers/specs/2026-10-11-streaming-engine-design.md b/docs/superpowers/specs/2026-10-11-streaming-engine-design.md index c199a3e8bc..d4ac9d87c1 100644 --- a/docs/superpowers/specs/2026-10-11-streaming-engine-design.md +++ b/docs/superpowers/specs/2026-10-11-streaming-engine-design.md @@ -1,336 +1,343 @@ # Streaming query engine — Design **Issue:** #473 (streaming, pull-based operator pipeline behind the cursor API; follow-up to #432) -**Milestone:** v3.0.0, branch `v3`, file format v8 (no format change) -**Folds in:** #518 (AVET lookups, parked on `perf/518-avet-lookup`), #530 (ids until projection) -**Followed by:** #306/#310 (`:limit`/`:offset` syntax and the 10M acceptance test), #185 (profiler) -**Status:** design approved 2026-10-11; not implemented +**Sub-issues:** #543–#551 (§12) +**Milestone:** v3.0.0, branch `v3`. The `.graph` file format stays v8 and the WAL format stays v2. +**Folds in:** #518 (AVET reads, parked on branch `perf/518-avet-lookup`), #530 (ids until projection) +**Followed by:** #306/#310 (`:limit`/`:offset` syntax and the 10M-fact `:limit` acceptance test), #185 (profiler) +**Status:** design approved 2026-10-11, revised the same day (§11 lists the changes from the approved summary); not implemented -## 1. Problem +## 1. Terms -`Minigraf::query` returns a `Cursor` (#432), but the answer is computed when the cursor -opens: `execute_query` loads the facts its patterns touch into a `Vec`, the -`PatternMatcher` joins them into `Vec>` bindings, and the cursor -walks the final `Vec`. Memory follows input size, not answer size: +- **Committed facts**: facts in the B+trees that the active meta page references. +- **Generation**: the number in a meta page. Each checkpoint writes a meta page with the next generation. A generation names one set of tree roots. +- **Pending store**: `FactData` inside `FactStorage` (`src/graph/storage.rs`): an in-memory `Vec` plus in-memory EAVT/AEVT `BTreeMap` indexes from key to position in that `Vec`. It holds every fact committed after the active generation. It is append-only between checkpoints; a checkpoint clears it (`post_checkpoint_clear`). For a file-backed database the WAL holds the same facts durably, and replay rebuilds the pending store on open. An in-memory database (`Minigraf::in_memory`) has no B+trees: every fact is in its pending store, permanently. +- **Checkpoint**: writes the pending store into the B+trees copy-on-write, writes a new meta page, deletes the WAL and clears the pending store. It runs when the WAL holds `wal_checkpoint_threshold` *entries* (transactions, default 1,000), on `Minigraf::checkpoint`, and on close. +- **Statement**: one `transact` or `retract` command, i.e. one `execute` call. A `WriteTransaction` holds one or more statements. +- **Chunk**: a bounded group of facts parsed from one statement (§8.1). -- `[?e :entity-type :type/function]` over 10M facts reads every fact of the attribute, - materialises each one with UUIDs and owned strings, then keeps ten rows. +## 2. Problem + +`Minigraf::query` returns a `Cursor` (#432), but `Cursor::from_result` wraps an answer that the executor has already computed in full: + +1. `execute_query` fetches the facts its patterns touch as a `Vec` (`filter_facts_for_query`, `selective_fact_fetch`). +2. `PatternMatcher` joins them into `Vec`, where `Bindings` is `HashMap`. +3. Post-processing (`not`, `or`, expressions, aggregation, window functions, projection) runs over that `Vec`. + +Memory therefore follows the facts read, not the rows returned: + +- `[?e :entity-type :type/function]` over 10M facts materialises every fact of the attribute, with UUIDs and owned strings, before returning any row. - `count` over 10M facts holds 10M bindings before counting. -- A recursive rule holds its whole input in a `FactStorage` plus a `BTreeSet` of seen facts. -- A 1M-fact `transact` is parsed into one `Vec`, staged, and written as one WAL entry. -- Closing a cursor early saves nothing: the work is already done. +- A rule query copies its base facts into a `FactStorage` and keeps a `BTreeSet seen_facts` of every base and derived fact (`RecursiveEvaluator::evaluate_recursive_rules`). +- `execute` parses a whole `transact` into one `Vec`. A `WriteTransaction` keeps all its staged facts in `pending_facts` until commit. The commit writes one WAL entry and then appends every fact to the pending store, where they stay until the next checkpoint. +- Closing a cursor early saves no work. + +A cursor has no snapshot of its own today; its answer is fixed only because it is computed at open. Once operators read lazily, two things can change under an open cursor: + +- A checkpoint clears the pending store. +- A later checkpoint can reuse pages that the cursor's generation still references. -A cursor also has no snapshot of its own. The answer is fixed because it is computed at -open. Once it is computed lazily, a checkpoint that frees and reuses pages under an open -cursor would corrupt its reads. The fact log (#430) avoids this today by refusing -checkpoints while a log is open (`API-013`). +`FactLog` (#430) avoids both by pinning: while a log is open, automatic checkpoints are skipped and `Minigraf::checkpoint` fails with `API-013`. -## 2. Goals and non-goals +## 3. Goals and non-goals -Goals are #473's: +Goals (#473): -1. **Memory follows operator state, not input size.** Pipelined operators hold one batch. - Only the stateful operators hold more, and the planner avoids that state where index - order allows. -2. **Incremental delivery** with early termination, cancellation and backpressure. -3. **Streaming aggregation**, one pass, hash- or sort-grouped. -4. **Consistent snapshots** at open; writes committed later do not change the answer. -5. **Streaming transactions**: a large `transact` never holds more than one chunk of - parsed facts. +1. Memory follows operator state, not input size. A pipelined operator holds at most one batch. Only the operators in §6.2 hold more. +2. Batches reach the caller as they are produced. `Limit` stops the work early, and `close` stops all work. +3. Aggregates run in one pass over their input. +4. A cursor's answer is the database as of the moment it opened, whatever is written or checkpointed afterwards. +5. A `transact` of any size holds at most one chunk of parsed facts in memory (file-backed databases; §8.4). Non-goals: -- No Datalog semantics change. `:find` keeps returning a bag. -- No file-format change. The `.graph` layout stays v8. -- No parallel execution (the operator model does not preclude it). -- No spilling and no `spill_dir`. -- No public API change: `Cursor`, `Batch`, `PreparedQuery` and every binding are untouched. - -## 3. Decisions - -| # | Question | Decision | -|---|---|---| -| D1 | Scope for v3.0.0 | All of #473: every operator, `Recursive`, streaming transact | -| D2 | Snapshot | Pin the committed generation; copy the pending facts the plan reads; quarantine freed pages in memory (§4) | -| D3 | Fact log | Moves to the same pin; `API-013` stays registered, deprecated | -| D4 | Migration | New engine alongside the old one; the old one is a test-only oracle, deleted before v3.0.0 (§9) | -| D5 | `:limit` | #473 builds the `Limit` operator; #306/#310 add the syntax afterwards and take the 10M acceptance test | -| D6 | Large state | No default budget, no spill; byte accounting, `try_reserve` growth, an optional cap that raises one new QRY code (§7) | -| D7 | Row format | Columnar batches with plan-time variable slots; entities and idents stay DICT ids until `Project` (§5) | + +- No change to Datalog semantics: every query returns the same rows, as a bag, as today. +- No change to the `.graph` format or the WAL format. +- No parallel execution. +- No spilling to disk and no `spill_dir`. +- No change to the public API: `Cursor`, `Batch`, `PreparedQuery`, `FactLog` and every binding keep their signatures. ## 4. Snapshots -### 4.1 What a cursor holds +### 4.1 Contents + +A cursor's snapshot is taken once, at open, while holding the pending store's read lock (`FactData`'s `RwLock`). It consists of: + +1. **The committed reader**: the `Arc` of the active generation. It reads only the roots of that generation. An in-memory database has none. +2. **A pin** on that generation (§4.2), released when the cursor is closed or dropped. +3. **The pending store as of open**: an `Arc` of the current `FactData` and its length `n` at open. The cursor reads pending positions `0..n` only (§4.3). +4. **The valid-time "now"**: read once, at open, and used for the default `:valid-at`. -At open, under the storage read lock, a cursor takes: +The lock is held only while these four are taken. After that the cursor holds no lock across `next_batch` calls. Writers and checkpoints proceed. -1. **A committed snapshot**: the active meta page's generation and its five tree roots, - as an `OnDiskReader` over those roots. The reader never looks at a newer meta. -2. **A pin** on that generation (§4.2), released on `close` or drop. -3. **The pending facts the plan reads.** Each `Scan` in the plan copies the pending facts - in its range (the same ranges `FactStorage::get_live_facts` serves today). Pending - facts are those not yet checkpointed, so the copy is bounded by - `wal_checkpoint_threshold` (default 1,000 entries). With checkpointing disabled the - copy follows the pending set; that is the documented cost of disabling it. -4. **The `tx_count` bound** at open, applied to the copied pending facts. -5. **Provisional ids** (§5.3) for pending entities and idents that the DICT does not have. +`Minigraf` handles and cursors share these objects by `Arc`. A cursor keeps the file and its lock open until the cursor is closed, as `FactLog` does today. -After that the cursor needs no lock. Writers and checkpoints proceed. +### 4.2 Pins and page quarantine -### 4.2 Page quarantine +A checkpoint writes only pages that the active meta does not reference. The ids it stops referencing (`freed` in `btree::cow_insert`) go on the free list that the new meta records. Today the next checkpoint may hand those ids out again (`PageAllocator::alloc`) and write new contents to them, while a cursor of an older generation might still read them. -A checkpoint is copy-on-write: it writes only pages the active meta does not reference, -and the pages the new meta stops referencing go on the free list (`finish_free_list`). -The *next* checkpoint may hand them out and overwrite them. A cursor pinned to an older -generation may still read them. +`PersistentFactStorage` therefore keeps two in-memory structures: -The allocator therefore keeps, in memory only, a **quarantine**: for each checkpoint, -the generation it produced and the ids it freed. An id freed by the checkpoint that -produced generation `g` is reachable from every generation `< g`. While any pin `< g` -exists, `PageAllocator::alloc` skips that id: it stays listed as free, and -`finish_free_list` lists it again with the read-but-unused ids. When the oldest pin -drops, the quarantine entries at or below the new oldest pin are released. +- **Pins**: a count of open cursors and fact logs per generation. +- **Quarantine**: for each checkpoint, the generation `g` it produced and the ids in its `freed` list. Those ids are referenced by generations below `g`, and by none from `g` on. + +`PageAllocator::alloc` does not hand out an id that is in the quarantine entry of some generation `g`, while a pin on a generation below `g` exists. The id stays free on disk, and `finish_free_list` lists it again, as it already does for ids it read but did not hand out. When a pin is released, the quarantine entries no remaining pin needs are discarded. Properties: -- **No format change.** On disk, a quarantined page is an ordinary free page. -- **Crash-safe.** After a crash nothing is pinned, so every free page is reusable. -- **Growth is bounded by the pin.** While a cursor is open the file grows by the pages - the intervening checkpoints free, as in LMDB with a long reader. `verify()` already - counts free pages; nothing changes there. -- **Page cache.** A quarantined id is never rewritten, so a cached page can never serve - another generation's bytes. -The in-memory (`MemoryBackend`) and browser (`BrowserBufferBackend`) backends go through -the same allocator, so they quarantine the same way. A browser flush writes dirty pages -only, which never include a quarantined page. +- **No format change.** On disk, a quarantined id is an ordinary free-list entry. +- **After a crash or reopen** there are no pins and no quarantine, so every free id can be reused. +- **File growth.** While a cursor is open, the file can grow by the pages that the checkpoints run meanwhile replace, as in LMDB with a long-lived reader. `verify()` still holds: quarantined ids are on the free list. +- **Page cache.** An id is not rewritten while a pinned generation can read it, so `PageCache` never returns another generation's page to a pinned reader. +- **Backends.** `FileBackend`, `MemoryBackend` and `BrowserBufferBackend` all go through `PageAllocator`, so the rule applies to each. A `BrowserDb` flush to IndexedDB writes only dirty pages, and a quarantined page is never dirty. + +### 4.3 Pending facts under a checkpoint + +A checkpoint today clears the pending store in place. It will instead replace `FactData`'s pending part (`facts`, `pending_keys`, `pending_indexes`) with a new, empty one. The old one stays alive while any cursor holds its `Arc`, and no writer appends to it after the swap. -### 4.3 Fact log (D3) +A cursor's pending reads are therefore stable: -`Minigraf::fact_log` pins its generation the same way and copies its pending facts at -open. Checkpoints no longer fail while a log is open, and `log_pins()` stops gating the -automatic checkpoint (`db.rs:767`, `db.rs:1602`). `API-013` stays in the registry and in -`docs/ERROR_REFERENCE.md`, marked deprecated, and is never raised again. +- Positions `0..n` of its `FactData` never move, because the store is append-only. +- Positions `≥ n` are facts committed after the cursor opened, so they are skipped. +- A pending index range is resumed by key after each batch, under a short read lock. A key inserted after open belongs to a position `≥ n`, so it is skipped too. -`rebuild_indexes` rewrites every tree; it also proceeds, since pinned pages are -quarantined like any other freed page. +The snapshot copies nothing, so an in-memory database, whose facts are all pending, opens a cursor in constant time. This is the mechanism `FactLog` uses today (`log_snapshot` returns the reader and the pending length), extended so that a checkpoint can proceed. + +### 4.4 Fact log + +`Minigraf::fact_log` takes the same snapshot (§4.1) and the same pin. Checkpoints no longer wait for open logs: `log_pins()` no longer gates the automatic checkpoint (`db.rs:767`, `db.rs:1602`), and `Minigraf::checkpoint` and `rebuild_indexes` no longer fail with `API-013`. `API-013` stays in `ErrorCode` and in `docs/ERROR_REFERENCE.md`, marked deprecated, and is no longer raised. `rebuild_indexes` replaces every tree page, so with a pin held it grows the file by the size of the indexes until the pin is released. ## 5. Rows ### 5.1 Batches -A `Batch` (internal; the public `Batch` wraps it) holds up to 1,024 rows as one column -per variable slot. The planner numbers the variables of each operator's output, so a -column is found by index, never by name. `HashMap` bindings are gone from -the new engine. +Operators exchange an internal batch of at most 1,024 rows, stored as one column per variable. The planner assigns each variable a slot number, so operators address columns by index, never by name. The public `Batch` is built from internal batches by `Project` (§6.1). ### 5.2 Cells ```rust enum Cell { - Eid(u64), // entity: DICT id or provisional id - Iid(u64), // ident (attribute or keyword value): DICT id or provisional id - Val(ValueRef), // string, integer, float, boolean, null; long strings by vref + Eid(u64), // an entity: a DICT entity id, or a provisional id (§5.3) + Iid(u64), // an ident used as a value (a keyword): a DICT ident id, or a provisional id + Val(ValueRef), // a string, integer, float, boolean or null; long strings by value-page reference + Meta(i64), // a pseudo-attribute value (§5.5) } ``` -Ids stay ids through joins, filters, sorts and aggregation. `Project` turns the cells of -the rows it returns into `Value`s, so a query that keeps ten rows translates ten rows -(#530). Literals in the query are resolved to ids once, at plan time; a literal the DICT -and the snapshot do not know resolves to "no match", so its `Scan` is empty. +Joins, filters, sorts and aggregation compare and hash cells. `Project` converts the cells of the rows it returns into `Value`s. A query that returns ten rows converts ten rows (#530). + +### 5.3 Ids of pending entities and idents + +Pending facts hold UUIDs and strings, not ids. When a `Scan` reads a pending fact, it converts the entity, and a keyword value, to an id: + +1. If the committed reader's DICT has the UUID or ident, use the DICT id. +2. Otherwise, use a **provisional id** from a map private to the cursor. Ids are assigned from the snapshot's `next_eid` / `next_iid` upwards, the first time each UUID or ident is met. + +Every cell of a cursor is in one id space. Provisional ids are never written to disk. The provisional map is query state and counts towards the memory accounting of §7. For an in-memory database every entity and keyword is provisional, so the map grows with the distinct entities and keywords the query reads. -### 5.3 Provisional ids +Query literals are converted the same way when the plan is built. A literal that the DICT and the pending store both lack gets a provisional id that no fact carries, so its `Scan` returns nothing. -Pending facts carry UUIDs and strings. At open the snapshot gives each pending entity -and ident that the DICT does not hold a provisional id from `next_eid` / `next_iid` -upwards, in a map private to the cursor. The whole snapshot then has one id space. -Provisional ids are never written; a checkpoint assigns real ids independently. +### 5.4 Matching across kinds -### 5.4 Cross-kind matching +The new engine reproduces the matcher's rules exactly (`PatternMatcher::match_component` and `normalize_join_value`, `src/query/datalog/matcher.rs`): -The matcher today lets a keyword constant `:k` match `Keyword(k)` and `Ref(uuidv5(k))`, -lets a UUID constant match a ref or a keyword naming that entity, compares floats within -an epsilon, and matches `nil` to `Null`. The new engine keeps every one of these rules: +- **Keyword constant `:k`** matches the value `Keyword(:k)` and the value `Ref(uuidv5(:k))`. A `Scan` for `[?e :a :k]` reads both AVET ranges; these are #518's `ValueProbe`s, converted to ids. +- **UUID constant `u`** matches the value `Ref(u)` and any keyword value `:k` with `uuidv5(:k) = u`. +- **`nil`** matches `Null`. +- **Float constant** matches a float value within the matcher's epsilon. `Scan` reads every float of the attribute (#518's `ValueKind::Float`) and filters. +- **Join keys.** A keyword cell `Iid(k)` is hashed and compared as `Eid` of `uuidv5(k)`: the DICT id if that UUID has one, else a provisional id. The row keeps the cell bound first, as `matcher.rs` keeps the value bound first. +- **Float join keys.** Today the hash-join path compares floats with `Value`'s `Eq` (exact), and the nested-loop path compares them with `match_component` (epsilon). Which one applies depends on the plan. #545 fixes one rule for both paths, using the oracle tests (§9) to find the queries whose answer changes. Any change goes in `CHANGELOG.md`. -- **Constants** resolve to every id they can match: `:k` to `Iid(k)` and to the `Eid` - of `uuidv5(k)` if that entity exists. These are the AVET probes #518 built - (`ValueProbe`), now in id form. -- **Join keys** compare `Iid(k)` equal to `Eid(e)` exactly when `e = uuidv5(k)`. The - snapshot resolves that per ident lazily and caches it; the number of idents bounds it. -- **Floats** keep the matcher's epsilon rule. A join on a float-valued variable uses the - same comparison as today; the oracle tests (§9) pin which rows match. +### 5.5 Pseudo-attributes + +`:db/valid-from`, `:db/valid-to`, `:db/tx-count` and `:db/tx-id` read metadata of the fact matched by another pattern on the same entity. Today the matcher carries this metadata in hidden bindings named `__fvf_`, `__fvt_`, `__ftc_` and `__fti_`. In the new engine, `Scan` outputs these four values as `Meta` columns of the fact it matched, and the planner wires a pseudo-attribute pattern to them. `:db/valid-at` is a constant of the query. ## 6. Operators -All operators implement `open` / `next_batch() -> Result>` / `close`. -`close` propagates to the children, so a closed cursor stops all upstream work. - -### 6.1 Pipelined (hold one batch) - -- **`Scan`** over EAVT, AEVT, AVET or VAET, chosen by which pattern positions are bound. - It merges the committed snapshot's keys with the copied pending facts per triple and - decides net-assert on keys (#379), with the `:as-of` bound and `:valid-at` / - `:any-valid-time` pushed into the walk. Attribute+value patterns read AVET (#518's - `Scan::AttributeValue` / `AttributeKind` and its string/float/keyword/ref rules). - Output is in index order, and the plan knows that order. -- **`IndexNestedLoopJoin`**: for each outer batch, probes the inner pattern's index with - the bound positions. The default join when the inner pattern has a usable index. -- **`Filter`** / **`Expr`**: predicates and bindings from expression clauses. -- **`Project`**: column selection and id→value translation (§5.2). -- **`Union`** for `or` / `or-join`. -- **`Limit`** / **`Offset`**: stop pulling, then `close` the child. - -### 6.2 Stateful (hold more than a batch) - -- **`HashJoin`**: builds on the smaller side when neither side has a usable index. -- **`NotJoin`** / anti-join: hashes the right side. -- **`Distinct`**: hash on the row. Used only where the engine deduplicates today (`or` - branches, `count-distinct`, the recursive relation). Plain `:find` stays a bag. -- **`Sort`**: in memory; skipped when index order already gives the order; becomes - top-k under a `Limit`. -- **`Aggregate`**: ungrouped aggregates run in constant memory; grouped ones hash on the - key, or stream sort-grouped when the child is ordered on it. -- **`Window`**: today's window functions over a partitioned, ordered input. -- **`Recursive`**: semi-naive fixpoint per stratum. The delta and the accumulated - relation are hash relations of id rows, replacing `FactStorage` plus - `BTreeSet seen_facts`. Magic sets and stratification stay as rewrites in front of the - planner. `max_derived_facts` (`INT-020`) still bounds the accumulated relation. +Every operator implements `open`, `next_batch() -> Result>` and `close`. `close` closes the operator's children. Closing a cursor therefore closes every operator under it, and no operator does further work. + +### 6.1 Operators that hold at most one batch + +- **`Scan`** reads one key range of EAVT, AEVT, AVET or VAET, chosen from the pattern positions that are constants or bound: + - It merges the committed reader's keys with the pending facts at positions `0..n` of the same range, per `(e, a, v)`. + - It decides net-assert per `(e, a, v)` on keys, as `CommittedReader::live_facts` does (#379). + - It applies the `:as-of` bound and the `:valid-at` / `:any-valid-time` test while reading. + - Its output is in the index's order, and the planner records that order. + - `[?e :a C]` reads the AVET range of `C`, with #518's encoding rules for strings, floats, keywords and refs. + - `IndexNestedLoopJoin` (below) uses `Scan` to read one range per outer row. +- **`IndexNestedLoopJoin`**: for each outer batch, reads the inner pattern's range once per outer row, using the outer row's bound values. +- **`Filter`**: keeps the rows whose expression clause (`WhereClause::Expr` without a binding) is true. +- **`Bind`**: adds a column computed by an expression clause with a binding. +- **`Project`**: keeps the `:find` columns and converts cells to `Value`s (§5.2). +- **`Union`**: concatenates the outputs of the branches of an `or` / `or-join`. It is followed by `Distinct` (§6.2), because `or` removes duplicate rows today (`apply_or_clauses`). +- **`Limit`** / **`Offset`**: `Limit` stops pulling from its child after `n` rows and closes it. + +### 6.2 Operators that hold more than one batch + +Each of these holds state whose size depends on the data. They are the only operators counted by §7. + +- **`HashJoin`**: builds a hash table on one input and streams the other. Used when neither input can be read by index for the join. +- **`AntiJoin`**: for `not` and `not-join`. Builds a hash set of the inner rows' join keys, then streams the outer rows whose key is absent. +- **`Distinct`**: a hash set of rows. Placed only where the engine removes duplicates today: after `or` / `or-join`, inside `count-distinct` and `sum-distinct`, and in the recursive relation. `:find` without these returns a bag, as today. +- **`Sort`**: sorts its input in memory. The planner omits it when the input order already satisfies it. Under a `Limit` of `n`, it keeps the best `n` rows only. +- **`Aggregate`**: + - Without grouping variables it holds one accumulator per aggregate. + - With grouping variables it holds one accumulator per group in a hash table. + - When its input is ordered on the grouping variables, it holds one group at a time. +- **`Window`**: holds one partition at a time, ordered by its `:order-by`. +- **`Recursive`**: evaluates one stratum by semi-naive iteration: + - It holds the accumulated relation and the current delta as hash sets of id rows. These replace the `FactStorage` copy and `seen_facts`. + - Magic-set rewriting (`magic_sets.rs`) and stratification (`stratification.rs`) still run before planning. + - The three existing `INT-020` limits keep their meaning: 1,000 iterations; `max_derived_facts` new facts per iteration; `max_results` facts derived in total (base facts excluded, #528). ### 6.3 Planner -`optimizer.rs` and `prepared.rs` produce an operator tree instead of a clause order for -the matcher. Rules: - -1. Pick each pattern's index from its bound positions; prefer AVET for `[?e :a C]`. -2. Order joins by the existing selectivity estimates; use `IndexNestedLoopJoin` when the - inner side is indexable, else `HashJoin` on the smaller side. -3. Use sort-grouped aggregation and skip `Sort` when the input order allows. -4. Push `Limit` into `Sort` (top-k). - -A `PreparedQuery` keeps its plan and re-resolves only its bind slots and literals per -execution. Each operator counts rows in, rows out, batches and bytes held; the profiler -(#185) reads these counters. - -`optimizer.rs` is disabled under the `wasm` feature today. The new planner keeps that -gate on join reordering only; index choice and operator selection run on every target. - -## 7. Memory (D6) - -- **No default budget and no spilling.** Streaming makes large state rare: only the - operators in §6.2 hold more than a batch. -- **Accounting.** Each stateful operator tracks the bytes it holds and grows its tables - with `try_reserve`, so an allocation failure becomes an error instead of an abort - where the allocator reports it. (With Linux overcommit it rarely does; the cap below - is the dependable control.) -- **Optional cap.** `OpenOptions::query_memory_limit(bytes)`, off by default - (`usize::MAX`). When the bytes held by one query's stateful operators would pass it, - the query fails with a new code, **`QRY-012`: query memory limit exceeded**, naming the - operator and the limit. The cursor is closed; the database is unaffected. -- `max_results` keeps its meaning for `execute` only. A cursor has no result cap. -- **Bindings.** Every binding gets `query_memory_limit` on its `OpenOptions` record and - the `QRY-012` code. UniFFI shims map the `usize::MAX` sentinel to `i64::MAX`, as for - `wal_checkpoint_threshold`. Adding an `ErrorCode` variant breaks the UniFFI bindings - until they regenerate, so the binding PRs follow the core PR. +`optimizer.rs` and `prepared.rs` produce an operator tree instead of a clause order for `PatternMatcher`. The planner: + +1. Chooses each pattern's index from its constant or bound positions, choosing AVET for `[?e :a C]`. +2. Orders joins by the existing selectivity estimates. The join is an `IndexNestedLoopJoin` when the inner pattern has a constant or bound position that an index covers, otherwise a `HashJoin` that builds on the input with the smaller estimate. +3. Omits `Sort` when the input order satisfies it, and chooses the ordered `Aggregate` when the input is ordered on the grouping variables. +4. Places a `Limit` above a `Sort` inside the `Sort` (top `n`). + +`optimizer.rs` does not reorder joins under the `wasm` feature today. The planner keeps that rule for join order only; index choice and operator choice run on every target. + +A `PreparedQuery` keeps its operator tree and converts only its bind values and literals on each execution. + +Each operator counts rows in, rows out, batches and, for §6.2 operators, bytes held. The profiler (#185) reads these counts. + +## 7. Memory + +- **No default limit and no spilling.** Only the §6.2 operators hold more than a batch, and the planner avoids them where index order allows. +- **Accounting.** Each §6.2 operator, and the provisional id map (§5.3), keeps a count of the bytes it holds. It grows its tables with `try_reserve`, so an allocation the allocator refuses becomes an error instead of an abort. On Linux with memory overcommit the allocator seldom refuses, so the limit below is the dependable control. +- **Optional limit.** `OpenOptions::query_memory_limit(bytes)` sets a limit, off by default (`usize::MAX`). When the bytes counted for one query would exceed it, the query fails with a new error, **`QRY-012` query memory limit exceeded**, naming the operator and the limit. The cursor is closed, and the database and other cursors are unaffected. +- **`max_results`** keeps its current meaning: the number of facts rules may derive in one query (§6.2). A cursor has no limit on the rows it returns. +- **Bindings.** Every binding gets `query_memory_limit` on its `OpenOptions` record and the `QRY-012` code. UniFFI shims map `usize::MAX` to `i64::MAX`, as for `wal_checkpoint_threshold`. A new `ErrorCode` variant breaks the UniFFI bindings until they regenerate, so the binding PRs follow the core PR. ## 8. Transactions -### 8.1 Parsing +### 8.1 Parsing in chunks + +`execute` passes `transact` and `retract` text to a parser that yields one statement at a time. Within a statement, it yields the statement's facts in chunks of `TX_CHUNK_FACTS` facts. This is a constant, not an option; #550 sets it by measurement, starting at 4,096. + +The input text is the caller's string and is not counted; the bound is on parsed facts. Each chunk is validated as a statement is today: +- value limits; +- `check_valid_windows`: `API-019`, with a default `valid_from` taken as the transaction's `tx_id`; +- the one-window-per-triple rule (`API-011`) within the statement (§8.3). + +### 8.2 Small and large transactions + +A transaction stays **small** while its staged facts number at most `TX_CHUNK_FACTS`. A small transaction commits exactly as today: +1. `keep_last_statement`; +2. one `tx_id` and `tx_count`; +3. one WAL entry, written and synced; +4. the facts appended to the pending store. + +When a staged fact would exceed `TX_CHUNK_FACTS`, the transaction becomes **large**, once and for good, while holding the write lock: + +1. It fixes its `tx_count` (the next counter) and its `tx_id` (the current time). The write lock serialises transactions, so both are higher than every earlier transaction's. +2. It stamps the facts staged so far and writes them, as in step 3. +3. It writes each later chunk into **working trees**: copies of the active generation's five tree roots, extended copy-on-write with `btree::cow_insert` through the DICT `Encoder`, value pages and a `PageAllocator`. The working trees are the next generation's trees. Nothing moves their pages later. A page that a later chunk replaces is handled by its origin: + - one the active generation references goes to the `freed` list of the commit; + - one this transaction wrote returns to the transaction's allocator and can be reused within the transaction. +4. **Commit** is a checkpoint: + - the pending store's facts are inserted into the same working trees; + - the pages are synced; + - the new meta page is written and synced; + - the WAL is deleted; + - the pending store is replaced (§4.3). + + Failure handling is that of a checkpoint today: a failure after anything may have been written marks the handle failed (`STG-046`), and the outcome is known only after reopening. +5. **Rollback** (explicit, or by dropping the transaction) discards the working roots, the transaction's allocator and the DICT `Encoder`. + +Large transactions do not write to the WAL. Their durability point is the meta page write, as for a checkpoint. + +`tx_id` changes meaning for large transactions only. It is the time the transaction became large, not the time it committed. Both lie inside the write lock, so the order of `tx_id`s and `tx_count`s across transactions is unchanged. `CHANGELOG.md` records this. + +### 8.3 Last statement wins, and API-011, across chunks + +Two rules apply to the facts of one transaction today: -`transact` and `retract` go through a streaming EDN parser that yields statements, which -are materialised into facts in chunks (default 4,096 facts). Validation (value limits, -valid windows, `check_one_window_per_triple`, `API-011`) runs per chunk; the duplicate -check across chunks reads the transaction's own facts through `Scan` (§8.3). +- **One window per triple within a statement**: a statement that asserts one `(e, a, v)` with two valid-time windows is rejected with `API-011`. A rejected statement stages nothing, and the transaction stays usable. +- **The last statement wins**: when several statements write one `(e, a, v)`, only the last statement's facts for it are committed (`keep_last_statement`, #477). -### 8.2 Where chunks go +A large transaction cannot keep its statements in memory, so it applies both rules to the working trees. When a statement starts, the transaction records the working roots as the **statement base**. Until the statement ends, pages that the base references are not reused (§4.2's rule, applied within the transaction). -A transaction below `wal_checkpoint_threshold` facts is written exactly as today: one -WAL entry at commit, then applied to the pending store. +For each fact of triple `T` in a chunk: -A transaction that reaches the threshold switches to **writing its chunks into -copy-on-write pages**, the way `LogWriter` (#431) builds batched checkpoints: +1. The EAVT keys of `T` with this transaction's `tx_count` that are in the statement base came from earlier statements. They are removed from the working trees in all four indexes. EAVT keys are covering, so each one gives the other three keys. +2. The EAVT keys of `T` with this transaction's `tx_count` that are in the working trees but not in the base came from this statement. If one has a different window, the statement fails with `API-011`. The working roots are set back to the statement base, the pages written since are returned to the allocator, and the transaction stays usable. -1. On the switch it fixes its `tx_count` (known: the write lock is held) and its - `tx_id` (the current time; the lock keeps it monotonic). Facts staged so far are - stamped and inserted first. -2. Each later chunk is encoded and `cow_insert`ed into working copies of the trees. - Pages written by this transaction and superseded within it are reused at once; pages - of the active generation it supersedes are freed at commit. -3. **Commit** checkpoints the pending store into the same working trees, writes the new - meta page and deletes the WAL: the transaction commits as a checkpoint. -4. **Rollback** or a crash before the meta write leaves the active meta and its free - list untouched. Every page the transaction wrote was either on that free list or past - the committed `page_count`, so the next checkpoint reuses or overwrites it as usual, - exactly as after a crash mid-checkpoint. The allocator skips quarantined ids here too. +When the statement ends, its base is dropped. -This replaces the "append each chunk to the WAL" wording in #473. That wording still -left all facts in the in-memory pending store after commit, so a 1M-fact `transact` -would hold 1M facts in memory and fail the acceptance test in §10. Writing large -transactions as a checkpoint keeps the WAL format and the small-transaction path -unchanged. +This needs a copy-on-write delete in `btree.rs`, which does not exist today. #550 adds it, either as part of `cow_insert` or alongside it. A leaf that a delete leaves with no keys is removed from its parent. A leaf left with fewer keys stays as it is: `verify()` checks key order and separator bounds, not fill. -A transaction's `tx_id` is the switch time instead of the commit time for large -transactions. Both lie inside the write lock, so the order of transactions and their -`tx_count`s do not change. The change is noted in `CHANGELOG.md`. +### 8.4 Reading your own writes -### 8.3 Reading your own writes +A query inside a `WriteTransaction` reads a snapshot (§4.1) that consists of: +- for a large transaction, the working trees, in place of the active generation; +- the pending store; +- the transaction's staged facts that are not yet in the working trees: all of them for a small transaction, at most one chunk for a large one. -A `WriteTransaction`'s queries see a snapshot whose committed part is the working trees -(when it has switched) and whose pending part is the pending store plus the chunks not -yet inserted. It is the same `Scan` over a different snapshot. +### 8.5 Scope + +§8.2–§8.4 apply to file-backed databases. + +An in-memory database keeps every fact in its pending store (§1), so a large transaction's facts end up in memory however it is written. It uses the chunked parser (§8.1) and the small-transaction path at every size. + +`BrowserDb` writes through its own path (`src/browser/mod.rs`), which checkpoints after every `transact` (`pfs.save()`) into in-memory pages (`BrowserBufferBackend`). It keeps that path; its pages are in memory in any case. Schema validation and the v8 multi-value fix (#371, #287) are unaffected. -## 9. Migration and testing (D4) - -- The new engine is built in `src/query/engine/` beside the existing executor. A query - runs on the new engine when every clause it uses has an operator; otherwise on the old - path. Each sub-issue widens that set. -- **Oracle.** The old path stays as a test-only oracle (`#[cfg(test)]` and a - `test-oracle` feature for integration tests). Differential tests run every query in - these suites through both engines and compare row bags: - - the model-based test (`tests/model_based_test.rs`, `tests/reference_model/`), - - the property tests (`tests/property_test.rs`), - - the golden corpus (`tests/golden_corpus_test.rs`), - - the existing integration suites, through a test hook on `execute`. -- When every query runs on the new engine, the old path and the oracle hook are deleted. - This happens before v3.0.0. -- `tests/cursor_test.rs` and every binding suite pass unchanged throughout. -- **Measurements.** The #394 envelope at 100K/1M/10M on an idle machine before and after - each phase; the #379 point queries are the regression guard. +## 9. Migration and testing + +- The new engine is built in `src/query/engine/`, beside the existing executor. + - A query runs on the new engine when every clause it uses has an operator, and on the existing executor otherwise. + - Each sub-issue moves more clause kinds over. +- **Oracle.** The existing executor stays available to tests as an oracle (under `#[cfg(test)]`, and under a `test-oracle` Cargo feature for `tests/`). Differential tests run each query through both engines and compare the rows as bags, over: + - `tests/model_based_test.rs` with `tests/reference_model/`; + - `tests/property_test.rs`; + - `tests/golden_corpus_test.rs`; + - the other integration suites, through a test hook on `execute`. +- When every clause kind runs on the new engine, the existing executor, the oracle feature and the hook are deleted. This happens before v3.0.0 (#551). +- `tests/cursor_test.rs` and every binding's test suite pass, unchanged, after each sub-issue. +- **Measurement.** After each sub-issue, the #394 envelope at 100K, 1M and 10M facts on an otherwise idle machine. The #379 point queries must not regress. ## 10. Acceptance tests -From #473, with the `:limit` test moved to #306/#310 (D5): - -- [ ] `count` over 10M facts runs in constant memory. -- [ ] Grouped `count` with 1M groups completes with memory proportional to the groups; - with `query_memory_limit` below that, it fails with `QRY-012`. -- [ ] A recursive rule deriving 5M facts completes with memory proportional to the - derived relation; `max_derived_facts` still stops a runaway rule. -- [ ] Closing a cursor after the first batch stops upstream work (operator counters). -- [ ] A cursor's answer is unchanged by writes and checkpoints made while it is open, - including checkpoints that free pages it reads; the fact log likewise. -- [ ] A 1M-fact `transact` never holds more than one chunk of parsed facts. -- [ ] Python binding round trip with batches of 1,000; wall time and RSS in the envelope. +From #473. The `:limit` test moves to #306/#310, since it needs the syntax. + +- [ ] `count` over 10M facts holds memory independent of the number of facts. +- [ ] Grouped `count` with 1M groups completes, holding memory proportional to the number of groups. With `query_memory_limit` below that, it fails with `QRY-012`. +- [ ] A recursive rule deriving 5M facts completes, holding memory proportional to the derived relation. `max_derived_facts` and `max_results` still stop a runaway rule with `INT-020`. +- [ ] Closing a cursor after its first batch: the operator counters show no further rows read. +- [ ] A cursor's answer is unchanged by writes and checkpoints made while it is open, including checkpoints that free pages it reads. The same holds for a fact log. +- [ ] A 1M-fact `transact` on a file-backed database holds at most `TX_CHUNK_FACTS` parsed facts at any time. +- [ ] Python binding round trip with batches of 1,000 rows; wall time and peak RSS recorded in the #394 envelope. - [ ] Every existing `execute`, cursor and binding test passes unchanged. -- [ ] `[?e :a C]` reads only `C`'s AVET range (#518's envelope numbers hold). - -## 11. Delivery - -Sub-issues under #473, each a PR to `v3` with no closing keyword for #473: - -1. **Snapshots and page quarantine** (§4): pins, quarantine in `PageAllocator`, cursor - and fact-log snapshots, `API-013` deprecated. -2. **Operator core** (§5, §6.1 minus joins, §6.3 v1, §9 harness): `Batch`/`Cell`, - provisional ids, `Scan` over all four indexes including #518, `Filter`, `Project`, - `Limit`/`Offset`, single-pattern queries on the new engine, the oracle harness. -3. **Joins**: `IndexNestedLoopJoin`, `HashJoin`, join planning. -4. **Negation and disjunction**: `NotJoin`, `Union`, `Distinct`. -5. **Aggregation and ordering**: `Aggregate`, `Sort`, `Window`. -6. **Recursion**: `Recursive` with magic sets and stratification; rule queries move over. -7. **Memory accounting and cap** (§7): `QRY-012`, `OpenOptions::query_memory_limit`, - bindings. -8. **Streaming transactions** (§8). -9. **Removal and measurement**: delete the old engine and oracle hook, run the envelope - at 100K/1M/10M, update docs. - -After #473: `:limit`/`:offset` syntax with the 10M acceptance test (#306/#310), then the -profiler (#185). +- [ ] `[?e :a C]` reads only the AVET range of `C`; #518's envelope result (1M facts: 274 ms → 11 µs) holds. + +## 11. Changes from the approved summary + +The design approved on 2026-10-11 changed as follows when checked against the code: + +1. **Pending facts are shared, not copied, at open (§4.3).** An in-memory database keeps every fact pending, so a copy would copy the database. +2. **Large transactions commit as a checkpoint (§8.2), not as WAL chunks.** Chunks in the WAL would still be appended to the pending store at commit, so a 1M-fact transaction would end up in memory. WAL chunks streamed straight into the trees at commit would also work, but would need a WAL format change, two writes per fact, and an unindexed WAL for reading your own writes (§8.4). +3. **Last statement wins and `API-011` across chunks (§8.3)** need a statement base and a B+tree delete. +4. **`max_results`** limits the facts rules derive (#528), not the rows a query returns. #473's text said otherwise. +5. **Float join keys (§5.4)** differ between today's two join paths. #545 settles one rule. + +## 12. Delivery + +Sub-issues of #473, in order. Each is one or more PRs to `v3`, and none uses a closing keyword for #473. + +1. **#543 Snapshots and page quarantine** (§4): pins, quarantine in `PageAllocator`, the pending-store swap at checkpoint, cursor and fact-log snapshots, `API-013` deprecated. +2. **#544 Operator core** (§5, §6.1 without the joins, §6.3, §9): batches and cells, provisional ids, pseudo-attribute columns, `Scan` over all four indexes including #518 (rebased from `perf/518-avet-lookup`), `Filter`, `Bind`, `Project`, `Limit`/`Offset`, single-pattern queries on the new engine, the oracle tests. +3. **#545 Joins**: `IndexNestedLoopJoin`, `HashJoin`, join planning, the float join rule (§5.4). +4. **#546 Negation and disjunction**: `AntiJoin`, `Union`, `Distinct`. +5. **#547 Aggregation and ordering**: `Aggregate`, `Sort`, `Window`. +6. **#548 Recursion**: `Recursive`, with rule queries moved to the new engine. +7. **#549 Memory accounting and limit** (§7): `QRY-012`, `OpenOptions::query_memory_limit`, bindings. +8. **#550 Streaming transactions** (§8): chunked parser, large transactions, statement bases, the B+tree delete. +9. **#551 Removal and measurement**: delete the existing executor and the oracle, envelope at 100K/1M/10M, documentation. + +After #473: `:limit`/`:offset` syntax with the 10M-fact acceptance test (#306/#310), then the profiler (#185). From ab57e6aedf36a910e013fb6889a78bad2e184ed0 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sun, 11 Oct 2026 22:26:50 +0530 Subject: [PATCH 3/4] docs(spec): address review of the streaming engine design (#473) Whole snapshots (single-append commit, one-step checkpoint publish), quarantine in rebuild_indexes and BrowserDb page release, fact log without the write lock, executor behaviours made explicit, large transaction commit order, recovery and statement rollback. Refs #473 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_012wXxZguv7PgKQjMMH4yJ5h --- .../2026-10-11-streaming-engine-design.md | 190 ++++++++++++------ 1 file changed, 128 insertions(+), 62 deletions(-) diff --git a/docs/superpowers/specs/2026-10-11-streaming-engine-design.md b/docs/superpowers/specs/2026-10-11-streaming-engine-design.md index d4ac9d87c1..24a02307d2 100644 --- a/docs/superpowers/specs/2026-10-11-streaming-engine-design.md +++ b/docs/superpowers/specs/2026-10-11-streaming-engine-design.md @@ -10,8 +10,9 @@ ## 1. Terms - **Committed facts**: facts in the B+trees that the active meta page references. -- **Generation**: the number in a meta page. Each checkpoint writes a meta page with the next generation. A generation names one set of tree roots. -- **Pending store**: `FactData` inside `FactStorage` (`src/graph/storage.rs`): an in-memory `Vec` plus in-memory EAVT/AEVT `BTreeMap` indexes from key to position in that `Vec`. It holds every fact committed after the active generation. It is append-only between checkpoints; a checkpoint clears it (`post_checkpoint_clear`). For a file-backed database the WAL holds the same facts durably, and replay rebuilds the pending store on open. An in-memory database (`Minigraf::in_memory`) has no B+trees: every fact is in its pending store, permanently. +- **Generation**: the `u64` in a meta page. Each checkpoint writes a meta page whose generation is one more than the active one, so generations are totally ordered by number, and a lower number is an older generation. A generation names one set of tree roots. +- **`FactData`**: the struct behind `FactStorage`'s `Arc>` (`src/graph/storage.rs`). It holds the committed reader (`committed`, §4.1) and the pending store. +- **Pending store**: the part of `FactData` that holds facts committed after the active generation: an in-memory `Vec` (`facts`), a duplicate-detection set (`pending_keys`), and in-memory EAVT/AEVT `BTreeMap` indexes from key to position in `facts` (`pending_indexes`). It is append-only between checkpoints; a checkpoint clears it (`post_checkpoint_clear`). For a file-backed database the WAL holds the same facts durably, and replay rebuilds the pending store on open. An in-memory database (`Minigraf::in_memory`) has no B+trees: every fact is in its pending store, permanently. - **Checkpoint**: writes the pending store into the B+trees copy-on-write, writes a new meta page, deletes the WAL and clears the pending store. It runs when the WAL holds `wal_checkpoint_threshold` *entries* (transactions, default 1,000), on `Minigraf::checkpoint`, and on close. - **Statement**: one `transact` or `retract` command, i.e. one `execute` call. A `WriteTransaction` holds one or more statements. - **Chunk**: a bounded group of facts parsed from one statement (§8.1). @@ -32,12 +33,19 @@ Memory therefore follows the facts read, not the rows returned: - `execute` parses a whole `transact` into one `Vec`. A `WriteTransaction` keeps all its staged facts in `pending_facts` until commit. The commit writes one WAL entry and then appends every fact to the pending store, where they stay until the next checkpoint. - Closing a cursor early saves no work. -A cursor has no snapshot of its own today; its answer is fixed only because it is computed at open. Once operators read lazily, two things can change under an open cursor: +A cursor today retains no storage snapshot: `Minigraf::query` runs the executor to completion and then builds the cursor from the result (`db.rs:819–831`), so the answer cannot change. Once operators read lazily, two things can change under an open cursor: - A checkpoint clears the pending store. -- A later checkpoint can reuse pages that the cursor's generation still references. +- The pages a checkpoint stops referencing go on the free list, and a later checkpoint can hand them out and write new contents to them while the cursor still reads the older generation. -`FactLog` (#430) avoids both by pinning: while a log is open, automatic checkpoints are skipped and `Minigraf::checkpoint` fails with `API-013`. +`FactLog` (#430) avoids both today: while a log is open, `execute` skips the automatic checkpoint (`db.rs:764–769`), and `PersistentFactStorage::save` and `rebuild_indexes` fail with `API-013` (`persistent_facts.rs:417–423`, `707–712`). + +Two windows in today's code also matter once a snapshot can be taken at any moment: + +- `WriteTransaction::commit` appends its facts to the pending store one `load_fact` call at a time (`db.rs:1594–1597`), each under its own write lock, so a reader between two calls sees part of the transaction. +- A checkpoint sets the new committed reader (`set_committed_reader`, via `activate`) and clears the pending store (`post_checkpoint_clear`) under two separate write locks, so a reader between the two sees the checkpointed facts both as committed and as pending. + +§4.1 removes both windows. ## 3. Goals and non-goals @@ -46,8 +54,8 @@ Goals (#473): 1. Memory follows operator state, not input size. A pipelined operator holds at most one batch. Only the operators in §6.2 hold more. 2. Batches reach the caller as they are produced. `Limit` stops the work early, and `close` stops all work. 3. Aggregates run in one pass over their input. -4. A cursor's answer is the database as of the moment it opened, whatever is written or checkpointed afterwards. -5. A `transact` of any size holds at most one chunk of parsed facts in memory (file-backed databases; §8.4). +4. A cursor's answer is the database as it was when the cursor took its snapshot (§4.1): every transaction whose facts were in the pending store or the committed trees at that instant, and no other, whatever is written or checkpointed afterwards. +5. A `transact` of any size holds at most `TX_CHUNK_FACTS` parsed facts in memory (file-backed databases; §8). Non-goals: @@ -61,14 +69,21 @@ Non-goals: ### 4.1 Contents -A cursor's snapshot is taken once, at open, while holding the pending store's read lock (`FactData`'s `RwLock`). It consists of: +`FactData` changes shape: the pending store moves into its own `Arc`, so that `FactData` holds `committed: Option>` and `pending: Arc`. `PendingStore` keeps `facts`, `pending_keys` and `pending_indexes` behind its own `RwLock`. + +A cursor's snapshot is taken once, at open, while holding `FactData`'s read lock. It is not taken under the database's write lock (`Inner::write_lock`), so opening a cursor never waits for a write transaction. The snapshot consists of: -1. **The committed reader**: the `Arc` of the active generation. It reads only the roots of that generation. An in-memory database has none. +1. **The committed reader**: a clone of `committed`, the `Arc` of the active generation's reader. It reads only the roots of that generation. An in-memory database has none. 2. **A pin** on that generation (§4.2), released when the cursor is closed or dropped. -3. **The pending store as of open**: an `Arc` of the current `FactData` and its length `n` at open. The cursor reads pending positions `0..n` only (§4.3). -4. **The valid-time "now"**: read once, at open, and used for the default `:valid-at`. +3. **The pending store**: a clone of `pending`, and its length `n` (`facts.len()`). The cursor reads pending positions `0..n` only (§4.3). +4. **The valid-time "now"**: read once, here, and used for the default `:valid-at`. -The lock is held only while these four are taken. After that the cursor holds no lock across `next_batch` calls. Writers and checkpoints proceed. +After that the cursor holds no lock across `next_batch` calls, and writers and checkpoints proceed. + +Two rules make every snapshot whole: + +- **A commit appends all of a transaction's facts to the pending store under one write lock.** `transact_batch` and `retract` already do (`storage.rs:172–177`, `274–279`). `WriteTransaction::commit` and WAL replay change from one `load_fact` per fact to one batch append. +- **A checkpoint publishes in one step.** After the new meta page is synced, it sets `committed` to the new generation's reader and `pending` to a new, empty `PendingStore`, both under one write lock on `FactData`. It no longer calls `post_checkpoint_clear`. `Minigraf` handles and cursors share these objects by `Arc`. A cursor keeps the file and its lock open until the cursor is closed, as `FactLog` does today. @@ -78,34 +93,39 @@ A checkpoint writes only pages that the active meta does not reference. The ids `PersistentFactStorage` therefore keeps two in-memory structures: -- **Pins**: a count of open cursors and fact logs per generation. -- **Quarantine**: for each checkpoint, the generation `g` it produced and the ids in its `freed` list. Those ids are referenced by generations below `g`, and by none from `g` on. +- **Pins**: for each generation, the number of open cursors and fact logs whose snapshot reads it. +- **Quarantine**: for each checkpoint, the generation `g` it produced and the ids it stopped referencing: its `freed` list, plus every page of the trees that `rebuild_indexes` replaces. Generation `g − 1` references those ids; generations `g` and later do not. An id that was already free in generation `g − 1` is not in the entry: no pinned reader of `g − 1` or later reads it, and a reader older than `g − 1` is protected by the entry of the checkpoint that freed it. -`PageAllocator::alloc` does not hand out an id that is in the quarantine entry of some generation `g`, while a pin on a generation below `g` exists. The id stays free on disk, and `finish_free_list` lists it again, as it already does for ids it read but did not hand out. When a pin is released, the quarantine entries no remaining pin needs are discarded. +The rule: **an id in the entry of generation `g` is not handed out while any generation below `g` is pinned.** Equivalently, with `p` the lowest pinned generation, every entry with `g > p` is in force. + +- `PageAllocator::alloc` skips an id in force. The id stays free on disk, and `finish_free_list` lists it again, as it already does for ids it read but did not hand out. +- `rebuild_indexes` builds its pool from the free list minus the pages it keeps (`persistent_facts.rs:540–567`). It also removes the ids in force. +- When a pin is released and `p` rises, each entry with `g ≤ p` is discarded and its ids become ordinary free ids. With no pins, every entry is discarded. Properties: - **No format change.** On disk, a quarantined id is an ordinary free-list entry. - **After a crash or reopen** there are no pins and no quarantine, so every free id can be reused. - **File growth.** While a cursor is open, the file can grow by the pages that the checkpoints run meanwhile replace, as in LMDB with a long-lived reader. `verify()` still holds: quarantined ids are on the free list. -- **Page cache.** An id is not rewritten while a pinned generation can read it, so `PageCache` never returns another generation's page to a pinned reader. -- **Backends.** `FileBackend`, `MemoryBackend` and `BrowserBufferBackend` all go through `PageAllocator`, so the rule applies to each. A `BrowserDb` flush to IndexedDB writes only dirty pages, and a quarantined page is never dirty. +- **Page cache.** An id in force is not rewritten, so `PageCache` never returns another generation's contents for it to a pinned reader. +- **Backends.** `FileBackend`, `MemoryBackend` and `BrowserBufferBackend` all allocate through `PageAllocator`, so the rule applies to each. +- **`BrowserDb`.** After each commit, `BrowserDb` today drops the bytes of the pages that commit freed, from the in-memory buffer and from IndexedDB (`take_released`, `BrowserBufferBackend::release`, `browser/mod.rs:358–362`, `464–470`; #440). That assumes a freed page is never read again, which a pinned cursor breaks. `take_released` will therefore withhold the ids in force and return them once their entry is discarded, so their bytes are released at a later commit. A quarantined page is not written, so it is never in the dirty set that a flush sends to IndexedDB. ### 4.3 Pending facts under a checkpoint -A checkpoint today clears the pending store in place. It will instead replace `FactData`'s pending part (`facts`, `pending_keys`, `pending_indexes`) with a new, empty one. The old one stays alive while any cursor holds its `Arc`, and no writer appends to it after the swap. +A checkpoint replaces `FactData`'s `pending` with a new, empty `PendingStore` (§4.1). The old `PendingStore` stays alive while any cursor holds its `Arc`, and no writer appends to it after the swap. A cursor's pending reads are therefore stable: -- Positions `0..n` of its `FactData` never move, because the store is append-only. +- Positions `0..n` of its `PendingStore` never move, because the store is append-only. - Positions `≥ n` are facts committed after the cursor opened, so they are skipped. - A pending index range is resumed by key after each batch, under a short read lock. A key inserted after open belongs to a position `≥ n`, so it is skipped too. -The snapshot copies nothing, so an in-memory database, whose facts are all pending, opens a cursor in constant time. This is the mechanism `FactLog` uses today (`log_snapshot` returns the reader and the pending length), extended so that a checkpoint can proceed. +The snapshot copies nothing, so an in-memory database, whose facts are all pending, opens a cursor in constant time. `FactLog` today snapshots the same way (`log_snapshot` returns the committed reader and the pending length), but it must block checkpoints because a checkpoint clears the pending store in place. ### 4.4 Fact log -`Minigraf::fact_log` takes the same snapshot (§4.1) and the same pin. Checkpoints no longer wait for open logs: `log_pins()` no longer gates the automatic checkpoint (`db.rs:767`, `db.rs:1602`), and `Minigraf::checkpoint` and `rebuild_indexes` no longer fail with `API-013`. `API-013` stays in `ErrorCode` and in `docs/ERROR_REFERENCE.md`, marked deprecated, and is no longer raised. `rebuild_indexes` replaces every tree page, so with a pin held it grows the file by the size of the indexes until the pin is released. +`Minigraf::fact_log` takes the same snapshot (§4.1) and the same pin. It no longer holds the write lock while it opens (`db.rs:866–871`); the two rules of §4.1 give it a whole snapshot. Checkpoints no longer wait for open logs: `execute` and `WriteTransaction::commit` no longer skip the automatic checkpoint when `log_pins()` is non-zero (`db.rs:767`, `db.rs:1602`), and `PersistentFactStorage::save` and `rebuild_indexes` no longer fail with `API-013`. `API-013` stays in `ErrorCode` and in `docs/ERROR_REFERENCE.md`, marked deprecated, and is no longer raised. `rebuild_indexes` replaces every tree page, so with a pin held it grows the file by the size of the indexes until the pin is released. ## 5. Rows @@ -135,7 +155,7 @@ Pending facts hold UUIDs and strings, not ids. When a `Scan` reads a pending fac Every cell of a cursor is in one id space. Provisional ids are never written to disk. The provisional map is query state and counts towards the memory accounting of §7. For an in-memory database every entity and keyword is provisional, so the map grows with the distinct entities and keywords the query reads. -Query literals are converted the same way when the plan is built. A literal that the DICT and the pending store both lack gets a provisional id that no fact carries, so its `Scan` returns nothing. +Query literals are converted the same way when the plan is built, after the cross-kind expansion of §5.4: a keyword literal `:k` becomes both `Iid(:k)` and the `Eid` of `uuidv5(:k)`, and a UUID literal `u` becomes both `Eid(u)` and `Iid` of every keyword whose `uuidv5` is `u`, which the `Scan` finds through #518's `ValueKind::Keyword` range. Each converted form that the DICT and the pending store both lack gets a provisional id that no fact carries, so the range for that form is empty. ### 5.4 Matching across kinds @@ -145,15 +165,18 @@ The new engine reproduces the matcher's rules exactly (`PatternMatcher::match_co - **UUID constant `u`** matches the value `Ref(u)` and any keyword value `:k` with `uuidv5(:k) = u`. - **`nil`** matches `Null`. - **Float constant** matches a float value within the matcher's epsilon. `Scan` reads every float of the attribute (#518's `ValueKind::Float`) and filters. -- **Join keys.** A keyword cell `Iid(k)` is hashed and compared as `Eid` of `uuidv5(k)`: the DICT id if that UUID has one, else a provisional id. The row keeps the cell bound first, as `matcher.rs` keeps the value bound first. +- **Join keys.** For hashing and equality only, a keyword cell `Iid(k)` is treated as the `Eid` of `uuidv5(k)`: the DICT id if that UUID has one, else a provisional id. The cell stored in the output row is not changed: it is one of the two input cells, and `Project` returns its kind (a keyword or a ref). +- **Which input cell a row keeps.** When the two sides of a join hold different kinds for one variable, `matcher.rs` keeps the value bound by the pattern it evaluated first (`merged = existing`, `matcher.rs:428–453`). Evaluation order is the optimizer's order, so today the projected kind depends on the plan. #545 fixes one rule, defined on the query text rather than on operator order (the first pattern in `:where` order that binds the variable), and records the queries whose answer changes in `CHANGELOG.md`. - **Float join keys.** Today the hash-join path compares floats with `Value`'s `Eq` (exact), and the nested-loop path compares them with `match_component` (epsilon). Which one applies depends on the plan. #545 fixes one rule for both paths, using the oracle tests (§9) to find the queries whose answer changes. Any change goes in `CHANGELOG.md`. ### 5.5 Pseudo-attributes -`:db/valid-from`, `:db/valid-to`, `:db/tx-count` and `:db/tx-id` read metadata of the fact matched by another pattern on the same entity. Today the matcher carries this metadata in hidden bindings named `__fvf_`, `__fvt_`, `__ftc_` and `__fti_`. In the new engine, `Scan` outputs these four values as `Meta` columns of the fact it matched, and the planner wires a pseudo-attribute pattern to them. `:db/valid-at` is a constant of the query. +`:db/valid-from`, `:db/valid-to`, `:db/tx-count` and `:db/tx-id` read metadata of the fact matched by another pattern on the same entity. A query that uses one of these four without `:valid-at :any-valid-time` fails with `INT-026` before it reads anything (`executor.rs:502–507`); the new engine keeps that check. Today the matcher carries this metadata in hidden bindings named `__fvf_`, `__fvt_`, `__ftc_` and `__fti_`. In the new engine, `Scan` outputs these four values as `Meta` columns of the fact it matched, and the planner wires a pseudo-attribute pattern to them. `:db/valid-at` is a constant of the query. ## 6. Operators +The new engine reproduces every observable behaviour of the existing executor, including the rules stated in this section; the oracle tests (§9) check it. Where today's answer depends on the plan (§5.4), the sub-issue named there fixes one rule. + Every operator implements `open`, `next_batch() -> Result>` and `close`. `close` closes the operator's children. Closing a cursor therefore closes every operator under it, and no operator does further work. ### 6.1 Operators that hold at most one batch @@ -166,10 +189,14 @@ Every operator implements `open`, `next_batch() -> Result>` and `c - `[?e :a C]` reads the AVET range of `C`, with #518's encoding rules for strings, floats, keywords and refs. - `IndexNestedLoopJoin` (below) uses `Scan` to read one range per outer row. - **`IndexNestedLoopJoin`**: for each outer batch, reads the inner pattern's range once per outer row, using the outer row's bound values. -- **`Filter`**: keeps the rows whose expression clause (`WhereClause::Expr` without a binding) is true. -- **`Bind`**: adds a column computed by an expression clause with a binding. +- **`Filter`**: keeps the rows for which an expression clause without a binding (`WhereClause::Expr { binding: None }`) evaluates to a truthy value (`is_truthy`). +- **`Bind`**: adds a column holding the value of an expression clause with a binding. +- **Expression errors.** For `Filter` and `Bind`, a row whose expression fails to evaluate (a type mismatch, division by zero, an unbound variable) is dropped, not reported (`executor.rs:565–580`). An unknown function name is reported as an error when the query is planned, before any row is read (`executor.rs:521–531`). - **`Project`**: keeps the `:find` columns and converts cells to `Value`s (§5.2). -- **`Union`**: concatenates the outputs of the branches of an `or` / `or-join`. It is followed by `Distinct` (§6.2), because `or` removes duplicate rows today (`apply_or_clauses`). +- **`Union`**: for `or` and `or-join`. `apply_or_clauses` (`executor.rs:1833–2169`) evaluates them in one of two ways today, and the new engine reproduces each: + - **Seeded** (some branch contains `not` / `not-join`): each branch is evaluated with every incoming row as input; the branch outputs are concatenated, and duplicates are removed over the user-visible variables (names not starting with `__`). + - **Unseeded** (otherwise): each branch is evaluated once, without input rows, and the branch outputs are concatenated with duplicates removed. The result is then hash-joined with the incoming rows on the user-visible variables that both bind, by exact `Value` equality; a merged row keeps the incoming row's value for every variable the incoming row binds, and duplicates are removed over the merged row. When no variable is shared, the result replaces the incoming rows. Branches may be skipped once earlier branches cover every incoming row (#250). + - Both ways deduplicate, so `Union` is followed by `Distinct` (§6.2). Whether the two ways give the same rows for every query is not established; the oracle tests (§9) compare the new engine with whichever way today's executor takes. - **`Limit`** / **`Offset`**: `Limit` stops pulling from its child after `n` rows and closes it. ### 6.2 Operators that hold more than one batch @@ -178,16 +205,19 @@ Each of these holds state whose size depends on the data. They are the only oper - **`HashJoin`**: builds a hash table on one input and streams the other. Used when neither input can be read by index for the join. - **`AntiJoin`**: for `not` and `not-join`. Builds a hash set of the inner rows' join keys, then streams the outer rows whose key is absent. -- **`Distinct`**: a hash set of rows. Placed only where the engine removes duplicates today: after `or` / `or-join`, inside `count-distinct` and `sum-distinct`, and in the recursive relation. `:find` without these returns a bag, as today. +- **`Distinct`**: a hash set of rows. Placed only where the engine removes duplicates today: after `or` / `or-join` (§6.1), inside `count-distinct` and `sum-distinct`, and in the recursive relation. A `:find` without these returns a bag, as today. - **`Sort`**: sorts its input in memory. The planner omits it when the input order already satisfies it. Under a `Limit` of `n`, it keeps the best `n` rows only. - **`Aggregate`**: - Without grouping variables it holds one accumulator per aggregate. - With grouping variables it holds one accumulator per group in a hash table. - When its input is ordered on the grouping variables, it holds one group at a time. -- **`Window`**: holds one partition at a time, ordered by its `:order-by`. + - The grouping variables are the plain variables of `:find`, plus the `:with` variables when `:find` has no window function. With a window function, `:with` variables do not group (`executor.rs:1422–1443`). + - With no input rows, a query whose `:find` is only `count` / `count-distinct` aggregates returns one row of zeros; any other aggregate query returns no rows (`executor.rs:1405–1419`). + - `Null` inputs are skipped. Registered aggregates (`FunctionRegistry`) run through their init, step and finalise functions. Groups and errors are handled as `compute_aggregation` handles them (`executor.rs:1483–1525`). +- **`Window`**: holds one partition at a time, ordered by its `:order-by`. It computes `sum`, `count`, `min`, `max`, `avg`, `rank`, `row-number` and registered window functions, with ties and output order as `apply_window_functions` computes them (`executor.rs:1540` onwards). - **`Recursive`**: evaluates one stratum by semi-naive iteration: - It holds the accumulated relation and the current delta as hash sets of id rows. These replace the `FactStorage` copy and `seen_facts`. - - Magic-set rewriting (`magic_sets.rs`) and stratification (`stratification.rs`) still run before planning. + - Its base facts are the snapshot's facts after the `:as-of` and `:valid-at` filters, as today (`executor.rs:686–729`). Magic-set rewriting (`magic_sets.rs`) and its seed facts, and stratification (`stratification.rs`), still run before planning; the seed facts are visible only to that query. - The three existing `INT-020` limits keep their meaning: 1,000 iterations; `max_derived_facts` new facts per iteration; `max_results` facts derived in total (base facts excluded, #528). ### 6.3 Planner @@ -199,7 +229,7 @@ Each of these holds state whose size depends on the data. They are the only oper 3. Omits `Sort` when the input order satisfies it, and chooses the ordered `Aggregate` when the input is ordered on the grouping variables. 4. Places a `Limit` above a `Sort` inside the `Sort` (top `n`). -`optimizer.rs` does not reorder joins under the `wasm` feature today. The planner keeps that rule for join order only; index choice and operator choice run on every target. +Under the `wasm` feature the executor today orders by cost neither joins (`optimizer.rs`), nor `or` branches, nor deferred negation clauses (`executor.rs:625–629`, `1844–1850`). The planner keeps those three exceptions; index choice and operator choice run on every target. A `PreparedQuery` keeps its operator tree and converts only its bind values and literals on each execution. @@ -226,57 +256,85 @@ The input text is the caller's string and is not counted; the bound is on parsed ### 8.2 Small and large transactions -A transaction stays **small** while its staged facts number at most `TX_CHUNK_FACTS`. A small transaction commits exactly as today: -1. `keep_last_statement`; -2. one `tx_id` and `tx_count`; +A `WriteTransaction` today stages each statement's facts in `pending_facts` with a **synthetic** `tx_count`, one per statement and increasing (`stage_pending_facts`, `db.rs:1524–1536`). Reads inside the transaction and `keep_last_statement` use these synthetic counters. At commit the transaction takes its one real `tx_count` and `tx_id`. + +A transaction stays **small** while its staged facts number at most `TX_CHUNK_FACTS`. A small transaction commits as today, except that step 4 is one batch append (§4.1): +1. `keep_last_statement` over the staged facts; +2. one real `tx_id` and `tx_count`, stamped on every fact; 3. one WAL entry, written and synced; -4. the facts appended to the pending store. +4. the facts appended to the pending store under one write lock. + +When staging a fact would make the count exceed `TX_CHUNK_FACTS`, the transaction becomes **large**, once and for good. The write lock is held throughout, as for every `WriteTransaction` today. -When a staged fact would exceed `TX_CHUNK_FACTS`, the transaction becomes **large**, once and for good, while holding the write lock: +1. It fixes its real `tx_count` (the next counter) and its `tx_id` (the current time). The write lock serialises transactions, so both are higher than every earlier transaction's. +2. It applies `keep_last_statement` to the staged facts of the statements before the current one, stamps them, and inserts them into the **working trees**: + - The working trees start as the active generation's five tree roots and grow copy-on-write through `btree::cow_insert`, the DICT `Encoder`, value pages and a `PageAllocator` of the transaction's own. + - The working trees are the next generation's trees: no later step copies or moves their pages. +3. It records the statement base for the current statement (§8.3), then inserts the current statement's staged facts, and each later chunk, by the rules of §8.3. +4. A page that an insert replaces is handled by its origin: + - a page the active generation references goes to the commit's `freed` list; + - a page this transaction wrote returns to the transaction's allocator, except while a statement base references it (§8.3). +5. **Commit** is a checkpoint, in this order: + 1. The pending store's facts are inserted into the working trees. + 2. All pages written are synced. + 3. The new meta page is written and synced. Its `last_checkpointed_tx_count` is this transaction's `tx_count`. **This write is the commit point.** + 4. `committed` and `pending` are published (§4.1). + 5. The WAL is deleted, as a checkpoint deletes it. -1. It fixes its `tx_count` (the next counter) and its `tx_id` (the current time). The write lock serialises transactions, so both are higher than every earlier transaction's. -2. It stamps the facts staged so far and writes them, as in step 3. -3. It writes each later chunk into **working trees**: copies of the active generation's five tree roots, extended copy-on-write with `btree::cow_insert` through the DICT `Encoder`, value pages and a `PageAllocator`. The working trees are the next generation's trees. Nothing moves their pages later. A page that a later chunk replaces is handled by its origin: - - one the active generation references goes to the `freed` list of the commit; - - one this transaction wrote returns to the transaction's allocator and can be reused within the transaction. -4. **Commit** is a checkpoint: - - the pending store's facts are inserted into the same working trees; - - the pages are synced; - - the new meta page is written and synced; - - the WAL is deleted; - - the pending store is replaced (§4.3). +**Crash recovery:** +- A crash before step 3 completes leaves the previous meta page active. The transaction is absent, and the WAL replays the earlier transactions as usual. +- A crash after step 3 leaves the new meta page active, and possibly the old WAL. Every WAL entry has a `tx_count` at most this transaction's, so replay skips all of them as already checkpointed. This is the existing rule for a WAL left behind by a checkpoint. - Failure handling is that of a checkpoint today: a failure after anything may have been written marks the handle failed (`STG-046`), and the outcome is known only after reopening. -5. **Rollback** (explicit, or by dropping the transaction) discards the working roots, the transaction's allocator and the DICT `Encoder`. +**Failures** are handled as for a checkpoint today: +- A failure in steps 1–3, after any page may have been written, marks the handle failed (`STG-046`). Whether the transaction committed is known only after reopening, as when a WAL sync fails today. +- A failure in step 5 happens after the commit point, so the transaction is committed, and the error is handled as a checkpoint's failed WAL deletion is today. -Large transactions do not write to the WAL. Their durability point is the meta page write, as for a checkpoint. +6. **Rollback** (explicit, or by dropping the transaction) discards the working roots, the transaction's allocator and its DICT `Encoder`. Nothing on disk changes: every page the transaction wrote was free in the active generation, or lay beyond its `page_count`. -`tx_id` changes meaning for large transactions only. It is the time the transaction became large, not the time it committed. Both lie inside the write lock, so the order of `tx_id`s and `tx_count`s across transactions is unchanged. `CHANGELOG.md` records this. +Large transactions write nothing to the WAL. Their durability point is the meta page write. + +`tx_id` changes meaning for large transactions only: it is the time the transaction became large, not the time it committed. A default `valid_from` is that `tx_id`. Both times lie inside the write lock, so the order of `tx_id`s and `tx_count`s across transactions is unchanged. `CHANGELOG.md` records this. ### 8.3 Last statement wins, and API-011, across chunks Two rules apply to the facts of one transaction today: -- **One window per triple within a statement**: a statement that asserts one `(e, a, v)` with two valid-time windows is rejected with `API-011`. A rejected statement stages nothing, and the transaction stays usable. -- **The last statement wins**: when several statements write one `(e, a, v)`, only the last statement's facts for it are committed (`keep_last_statement`, #477). +- **One window per triple within a statement.** A statement that asserts one `(e, a, v)` with two different valid-time windows is rejected with `API-011` (`check_one_window_per_triple`, which looks at assertions only, `storage.rs:607–621`). A rejected statement stages nothing, and the transaction stays usable. +- **The last statement wins.** When several statements write records (assertions or retractions) of one `(e, a, v)`, only the records of the last of those statements are committed (`keep_last_statement`, `db.rs:1697–1722`, #477). + +A `transact` statement holds only assertions and a `retract` statement only retractions, so the records of one triple within one statement are all of one kind. -A large transaction cannot keep its statements in memory, so it applies both rules to the working trees. When a statement starts, the transaction records the working roots as the **statement base**. Until the statement ends, pages that the base references are not reused (§4.2's rule, applied within the transaction). +A large transaction cannot keep its statements in memory, so it applies both rules to the working trees. When a statement starts, the transaction records its **statement base**, the state that a rejected statement returns to: +- the five working roots; +- the allocator's state; +- the DICT `Encoder`'s next ids; +- the value-page append position. -For each fact of triple `T` in a chunk: +Until the statement ends, a page that the base references is not reused, even if the transaction wrote it. -1. The EAVT keys of `T` with this transaction's `tx_count` that are in the statement base came from earlier statements. They are removed from the working trees in all four indexes. EAVT keys are covering, so each one gives the other three keys. -2. The EAVT keys of `T` with this transaction's `tx_count` that are in the working trees but not in the base came from this statement. If one has a different window, the statement fails with `API-011`. The working roots are set back to the statement base, the pages written since are returned to the allocator, and the transaction stays usable. +For each record of triple `T` in a chunk, in order: -When the statement ends, its base is dropped. +1. **Earlier statements.** The EAVT keys of `T` with this transaction's `tx_count` that are in the statement base came from earlier statements. They are removed from all four indexes of the working trees. EAVT keys are covering, so each one gives the other three keys. +2. **This statement.** For an assertion: if the working trees hold an assertion key of `T` with this `tx_count` that is not in the base and has a different window, the statement fails with `API-011`. A key equal to one already present is not inserted again. +3. Otherwise the record's keys are inserted into all four indexes. + +When a statement fails (`API-011`, or any other validation error), the transaction returns to the statement base: +- the working roots are set back; +- the allocator's ids handed out since the base return to its free set; +- the `Encoder` forgets the ids it assigned since the base; +- the value-page append position is set back; +- the page-cache entries of the returned ids are dropped. + +The transaction stays usable. When a statement ends without failing, its base is dropped, and the pages the base alone referenced can be reused. This needs a copy-on-write delete in `btree.rs`, which does not exist today. #550 adds it, either as part of `cow_insert` or alongside it. A leaf that a delete leaves with no keys is removed from its parent. A leaf left with fewer keys stays as it is: `verify()` checks key order and separator bounds, not fill. ### 8.4 Reading your own writes -A query inside a `WriteTransaction` reads a snapshot (§4.1) that consists of: -- for a large transaction, the working trees, in place of the active generation; -- the pending store; -- the transaction's staged facts that are not yet in the working trees: all of them for a small transaction, at most one chunk for a large one. +A query inside a `WriteTransaction` reads a snapshot (§4.1) whose parts are: +- **committed:** the working trees for a large transaction, in place of the active generation; +- **pending:** the pending store; +- **staged:** the transaction's staged facts not yet in the working trees. For a small transaction that is all of them, with their synthetic counters as today. For a large transaction it is empty: a query runs between statements, and by then every finished statement is in the working trees. ### 8.5 Scope @@ -326,6 +384,14 @@ The design approved on 2026-10-11 changed as follows when checked against the co 4. **`max_results`** limits the facts rules derive (#528), not the rows a query returns. #473's text said otherwise. 5. **Float join keys (§5.4)** differ between today's two join paths. #545 settles one rule. +After an independent review against the code (Codex, 2026-10-11): + +6. **Snapshots are whole (§4.1).** `WriteTransaction::commit` and WAL replay append a transaction in one batch, and a checkpoint publishes the new committed reader and the empty pending store under one lock. Today both happen in steps (§2). +7. **`rebuild_indexes` and `BrowserDb` respect the quarantine (§4.2).** `rebuild_indexes` builds its page pool from the free list, and `BrowserDb` drops the bytes of freed pages after each commit (#440); both would otherwise reuse or drop pages a pinned cursor reads. +8. **`FactLog` no longer takes the write lock to open (§4.4).** +9. **Behaviours of today's executor made explicit (§5.5, §6):** `INT-026` for pseudo-attributes, expression errors drop the row, the two `or` evaluation paths, `:with` grouping, the zero row for `count`-only queries, window functions, the `wasm` exceptions. +10. **Large-transaction commit order, crash recovery and statement rollback stated in full (§8.2, §8.3).** + ## 12. Delivery Sub-issues of #473, in order. Each is one or more PRs to `v3`, and none uses a closing keyword for #473. From 562b7676f01d833ae7efecd69d0495fae1ad6797 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sun, 11 Oct 2026 22:36:12 +0530 Subject: [PATCH 4/4] docs(spec): derived-fact limit follows #553 (#473) Refs #473 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_012wXxZguv7PgKQjMMH4yJ5h --- .../specs/2026-10-11-streaming-engine-design.md | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/docs/superpowers/specs/2026-10-11-streaming-engine-design.md b/docs/superpowers/specs/2026-10-11-streaming-engine-design.md index 24a02307d2..6e27860c4e 100644 --- a/docs/superpowers/specs/2026-10-11-streaming-engine-design.md +++ b/docs/superpowers/specs/2026-10-11-streaming-engine-design.md @@ -218,7 +218,7 @@ Each of these holds state whose size depends on the data. They are the only oper - **`Recursive`**: evaluates one stratum by semi-naive iteration: - It holds the accumulated relation and the current delta as hash sets of id rows. These replace the `FactStorage` copy and `seen_facts`. - Its base facts are the snapshot's facts after the `:as-of` and `:valid-at` filters, as today (`executor.rs:686–729`). Magic-set rewriting (`magic_sets.rs`) and its seed facts, and stratification (`stratification.rs`), still run before planning; the seed facts are visible only to that query. - - The three existing `INT-020` limits keep their meaning: 1,000 iterations; `max_derived_facts` new facts per iteration; `max_results` facts derived in total (base facts excluded, #528). + - It raises `INT-020` at two limits: 1,000 iterations, and `max_derived_facts` facts derived in total, base facts not counted. #553 merges today's `max_results` (total derived facts, #528) and `max_derived_facts` (new facts per iteration) into that one limit, keeping `max_results` as a deprecated alias. If #553 has not landed when #548 does, `Recursive` enforces both of today's limits. ### 6.3 Planner @@ -240,7 +240,7 @@ Each operator counts rows in, rows out, batches and, for §6.2 operators, bytes - **No default limit and no spilling.** Only the §6.2 operators hold more than a batch, and the planner avoids them where index order allows. - **Accounting.** Each §6.2 operator, and the provisional id map (§5.3), keeps a count of the bytes it holds. It grows its tables with `try_reserve`, so an allocation the allocator refuses becomes an error instead of an abort. On Linux with memory overcommit the allocator seldom refuses, so the limit below is the dependable control. - **Optional limit.** `OpenOptions::query_memory_limit(bytes)` sets a limit, off by default (`usize::MAX`). When the bytes counted for one query would exceed it, the query fails with a new error, **`QRY-012` query memory limit exceeded**, naming the operator and the limit. The cursor is closed, and the database and other cursors are unaffected. -- **`max_results`** keeps its current meaning: the number of facts rules may derive in one query (§6.2). A cursor has no limit on the rows it returns. +- **`max_derived_facts`** (§6.2, #553) limits the facts rules derive in one query. Neither it nor `max_results` limits the rows a query returns, and a cursor has no such limit. - **Bindings.** Every binding gets `query_memory_limit` on its `OpenOptions` record and the `QRY-012` code. UniFFI shims map `usize::MAX` to `i64::MAX`, as for `wal_checkpoint_threshold`. A new `ErrorCode` variant breaks the UniFFI bindings until they regenerate, so the binding PRs follow the core PR. ## 8. Transactions @@ -366,7 +366,7 @@ From #473. The `:limit` test moves to #306/#310, since it needs the syntax. - [ ] `count` over 10M facts holds memory independent of the number of facts. - [ ] Grouped `count` with 1M groups completes, holding memory proportional to the number of groups. With `query_memory_limit` below that, it fails with `QRY-012`. -- [ ] A recursive rule deriving 5M facts completes, holding memory proportional to the derived relation. `max_derived_facts` and `max_results` still stop a runaway rule with `INT-020`. +- [ ] A recursive rule deriving 5M facts completes, holding memory proportional to the derived relation. `max_derived_facts` (#553) still stops a runaway rule with `INT-020`. - [ ] Closing a cursor after its first batch: the operator counters show no further rows read. - [ ] A cursor's answer is unchanged by writes and checkpoints made while it is open, including checkpoints that free pages it reads. The same holds for a fact log. - [ ] A 1M-fact `transact` on a file-backed database holds at most `TX_CHUNK_FACTS` parsed facts at any time. @@ -381,7 +381,7 @@ The design approved on 2026-10-11 changed as follows when checked against the co 1. **Pending facts are shared, not copied, at open (§4.3).** An in-memory database keeps every fact pending, so a copy would copy the database. 2. **Large transactions commit as a checkpoint (§8.2), not as WAL chunks.** Chunks in the WAL would still be appended to the pending store at commit, so a 1M-fact transaction would end up in memory. WAL chunks streamed straight into the trees at commit would also work, but would need a WAL format change, two writes per fact, and an unindexed WAL for reading your own writes (§8.4). 3. **Last statement wins and `API-011` across chunks (§8.3)** need a statement base and a B+tree delete. -4. **`max_results`** limits the facts rules derive (#528), not the rows a query returns. #473's text said otherwise. +4. **`max_results`** limits the facts rules derive (#528), not the rows a query returns; #473's text said otherwise. #553 merges it into `max_derived_facts` (v3.0.0). 5. **Float join keys (§5.4)** differ between today's two join paths. #545 settles one rule. After an independent review against the code (Codex, 2026-10-11):