From 041c1c478022f611937f91477d5584e0a619850c Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 14 Oct 2026 13:50:00 +0530 Subject: [PATCH 1/5] docs: plan for the streaming engine's operator core (#544) Three PRs: key-level reads, Scan, Project, planner v1 and the oracle; Filter/Bind, pseudo-attributes and cross-kind constants; the lazy cursor, measurement and docs. Limit/Offset move to #306. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- .../plans/2026-10-14-544-operator-core.md | 220 ++++++++++++++++++ 1 file changed, 220 insertions(+) create mode 100644 docs/superpowers/plans/2026-10-14-544-operator-core.md diff --git a/docs/superpowers/plans/2026-10-14-544-operator-core.md b/docs/superpowers/plans/2026-10-14-544-operator-core.md new file mode 100644 index 0000000000..dec7c1cc2f --- /dev/null +++ b/docs/superpowers/plans/2026-10-14-544-operator-core.md @@ -0,0 +1,220 @@ +# Operator core, Scan and oracle harness (#544) — Plan + +Spec: `docs/superpowers/specs/2026-10-11-streaming-engine-design.md` §5, §6.1 (without +the joins), §6.3, §9 (#473, part 2 of 9). Folds in #518 (branch `perf/518-avet-lookup`, +fe545dc) and #530. PRs target `v3`; no closing keyword for #473. #518 and #530 close by +hand (`gh issue close`) when the PR that fixes each merges. + +| PR | Steps | Branch | +|---|---|---| +| 1 | 1–6: key-level reads (#518 rebased), cells and batches, `Scan`, `Project`, planner v1 for plain single patterns, routing, oracle | `feat/544-operator-core` | +| 2 | 7–9: `Filter`/`Bind`, pseudo-attribute columns, cross-kind constants | `feat/544-exprs` | +| 3 | 10–12: lazy cursor with `close` and counters, measurement, docs | `feat/544-lazy-cursor` | + +Each PR leaves `v3` with no unused code, and updates the test counts and `CHANGELOG.md` +for what it ships. + +## Design decisions not fixed by the spec + +1. **Which queries run on the new engine (#544).** `engine::plan` returns `None`, and the + query runs on the existing executor, unless all of these hold: + - no rule invocation, `not`, `not-join`, `or`, `or-join`; + - exactly one pattern with a real attribute; any other pattern is a pseudo-attribute + pattern (PR 2) whose entity is the same term as the real pattern's, and which + `optimizer::plan` orders after it (if it is ordered first, today's matcher binds it + over every fact of the entity, which is a join: #545); + - `:find` holds plain variables only (aggregates and windows: #547); + - `:as-of` is absent or a counter (`AsOf::Timestamp` filters on `tx_id`, not a key + bound; it stays on the executor until #551); + - no transaction overlay (`facts_override`): reads inside a `WriteTransaction` stay on + the executor until #550 (§8.4); + - each pattern position is a variable, `_`, or a constant kind the PR handles (PR 1: + entity keyword/UUID; attribute keyword; value string, integer, boolean, `nil`; + PR 2 adds value keyword, UUID and float, §5.4). + The check runs after `INT-026`, `INT-027`, `QRY-007` and `check_find_functions`, so + every error of today's executor is raised first, by the same code. +2. **Cells.** `enum Cell { Eid(u64), Iid(u64), Val(Scalar) }`, + `enum Scalar { Null, Bool(bool), Int(i64), Float(f64), Str(Arc), Long(ValueRef) }`. + Pseudo-attribute values are `Val(Int)` cells (and `Val(Null)` for `:db/valid-at` under + `:any-valid-time`), not a separate `Meta` variant: a variable bound by a pseudo-attribute + and by a real value must compare as today's `Value::Integer`s do, and one integer + variant gives that without a cross-variant rule. Deviation from spec §5.2 (`Meta(i64)`). + A pending string over 64 bytes is `Str`; committed ones are `Long`. Equal long strings + on both sides only need one form when a join compares them, so canonicalising (a DICT + long-value lookup) is #545's. +3. **Batches.** `struct Batch { len: usize, cols: Vec> }`, at most + `BATCH_ROWS = 1024` rows; the planner gives each variable a column index + (`Slots`). An operator is `trait Operator: Send { fn next_batch(&mut self) -> + Result>; fn close(&mut self); fn counters(&self) -> Counters }`. + `open` is the constructor. +4. **Ids (§5.3).** `IdSpace` per query: DICT ids from the committed reader, provisional + ids from `next_eid` / `next_iid` of the snapshot's meta upwards (in-memory: from 1), + with forward and reverse maps. `Project` turns ids back through the DICT or the + reverse map. Counting its bytes is #549's, with the rest of the accounting (no + reader of the count before then). +5. **Committed reads stay lock-free between batches.** `CommittedReader` gains a + key-level method: + `live_keys(&self, index, prefix, resume: Option<&[u8]>, as_of, max, out: &mut Vec) -> Result>>`. + It is `OnDiskReader::live_scan` made resumable: it stops only at a triple boundary + once `max` entries are out, and returns the triple to resume after (seek to + `triple ‖ 0xFF`), so a triple's net-assert decision never spans two calls. A + `LeafCursor` borrows the reader, so it is rebuilt per batch by seek (one root-to-leaf + walk per 1,024 rows), as `FactLog` already does. `live_scan` itself becomes a loop + over `live_keys`; `live_facts` keeps its signature for the executor. Plus the + DICT accessors the engine needs: `eid_of`, `iid_of`, `uuid_of`, `name_of`, + `tx_id_of`, `long_value`, `next_ids`. The default trait impls cover readers + without keys (tests' `MemoryReader`, if any): `None` → no committed side. +6. **Pending facts and net-assert.** Every pending fact is newer than every committed + one, so a triple with any pending record in the snapshot (position `< n`, + `tx_count ≤ as_of`) is decided by its pending records alone, by the rule of + `net_asserted_facts`; a triple without one is decided by the committed keys. `Scan` + therefore: + - at open, if there is a committed reader and the pending range is non-empty, builds + `shadow: HashSet>`, the id-form triple bytes of the pending triples in its + range whose entity, attribute and ref/keyword value are all in the DICT (others + cannot equal a committed triple). Its bytes are counted as query state. For an + in-memory database (no reader) it is empty and costs nothing; + - reads committed keys, dropping a triple in `shadow`; + - then reads the pending range (EAVT/AEVT `BTreeMap` resumed by key under a short + read lock; AVET/VAET shapes read the attribute's AEVT range, or every pending fact + when the attribute is unbound, and filter), grouping by triple and applying the + net-assert rule per group. + Output order is committed (index order) then pending (pending index order). The + planner records no order in #544: nothing consumes it before `Sort` elision (#547), + which needs a merged order and will add it. Deviation from spec §6.1 ("output in the + index's order"). +7. **Index choice** (`optimizer::select_index` extended, used by `Scan`): entity bound → + EAVT (`e` or `e a` prefix); attribute and value bound → AVET (`a v`, #518's prefixes + and value kinds); value a ref with attribute unbound → VAET; attribute bound → AEVT; + otherwise EAVT whole. Residual positions (e.g. the value of `[:e ?a "x"]`, a repeated + variable as in `[?x :a ?x]`, compared with today's exact `Value` equality) are + checked on decoded keys before any id is translated. +8. **#518.** Its key prefixes (`attribute_value_prefix`, `attribute_string_prefix`, + `attribute_kind_prefix`) and its tests come over; `Scan` uses them. Its changes to + `selective_fact_fetch` and the new `live_facts` scans do not: the executor stays as + it is, as the oracle. `tests/live_reads_test.rs` from the branch is rewritten to + compare engine scans with whole-attribute reads. The #518 envelope rows move to PR 3's + measurement. +9. **Oracle (§9).** A `test-oracle` Cargo feature (and `cfg(test)`) turns on a hook in + the one place queries are routed (decision 10): every query the new engine accepts + is also run by `DatalogExecutor` on the same `Snapshot` (`set_snapshot`), and the rows + are compared as bags (rows keyed by `encode_value`, NaN canonical); a mismatch panics + with both row counts and the query text only (no values: CodeQL). The existing suites + run under the feature in a new CI job (`rust.yml`: `cargo test --features test-oracle`), + which is how the model-based, property, golden-corpus and integration suites become + differential without being edited. `tests/engine_oracle_test.rs` adds targeted + shapes: every index choice, `:as-of`, retraction and re-assertion across a checkpoint + (pending shadowing committed), keyword-as-ref and UUID-as-keyword values, floats + within epsilon, long strings, in-memory and file-backed, before and after reopen. +10. **Routing.** Every query reaches `DatalogExecutor::execute_query` (`Minigraf::query` + and `execute`, `PreparedQuery` after substitution, `BrowserDb`), so the engine is + tried there, once: after the checks every query passes first, `engine::plan` and + `engine::run` on the executor's snapshot, and the executor's own path + (`execute_query_on_executor`) on `None`. `PreparedQuery` therefore plans per + execution; keeping the operator tree across executions (spec §6.3 last paragraph) + is #545's, when planning has join order worth caching. +11. **`Limit` / `Offset`.** Nothing in the query language reaches them until `:limit` + syntax (#306), so adding them now is unused code. They move to #306, which is + already next after #473; `close` propagation, which the cursor uses, stays here + (PR 3). Deviation from the issue's checklist; the issue gets a comment. + +## Steps + +### 1. Key-level committed reads (PR 1) +- Rebase the useful parts of fe545dc (decision 8): `keys.rs` prefixes and their unit + tests. +- `CommittedReader::live_keys` and the DICT accessors (decision 5); `live_scan` rewritten + over `live_keys`. +- Unit tests (`reader.rs`): `live_keys` with `max` = 1, 2, 7, 1024 concatenated equals + `live_scan` over random histories (the existing random-history differential test + extended); a triple with > `SEEK_AFTER` history entries straddling a batch boundary; + `as_of` cuts. + +### 2. Cells, batches, ids (PR 1) +- `src/query/engine/{mod,cell,batch,ids}.rs` (decisions 2–4). +- Unit tests: provisional ids are stable within a query, never collide with DICT ids, + round-trip through `Project`; byte counting grows with distinct ids. + +### 3. `Scan` (PR 1) +- `src/query/engine/scan.rs` (decisions 6, 7): index choice, committed walk, shadow set, + pending walk, net-assert, `:as-of` counter, `:valid-at` / default "now" from the + snapshot / `:any-valid-time`, residual checks, output cells. +- Differential unit tests against `Snapshot::live_facts_of_scans` + the executor's + valid-time step, over random histories with checkpoints between transactions, for + every index choice. + +### 4. `Project` and planner v1 (PR 1) +- `src/query/engine/{project,plan}.rs`: eligibility (decision 1, PR 1 subset), slots, + `Scan` → `Project` tree; `Project` keeps the `:find` columns, drops rows with a `:find` + variable no clause binds (as `extract_variables` does: such a query returns no rows) + and turns cells into `Value`s for the rows it returns only (#530). + +### 5. Routing and oracle (PR 1) +- Decision 10 (eager in PR 1: `engine::run` drains the tree into a `QueryResult`, so the + cursor is unchanged until PR 3), decision 9 (feature, hook, CI job, + `tests/engine_oracle_test.rs`). +- `cargo test --features test-oracle` over the whole suite locally; any mismatch is a + bug in the engine, or a plan-dependent answer of today's executor (spec §5.4), which + narrows eligibility and goes to #545. + +### 6. PR 1 checks +- `cargo fmt`, clippy (native, `wasm`, `browser`/wasm32 targets), `cargo test`, + `cargo test --features test-oracle`, binary size (`binary-size.yml` budget). +- #379 point queries and #518's `attribute_value` on the envelope at 100K/1M on the + bench machine (`perf_envelope`): no regression on point queries; `attribute_value` + at 1M near #518's 11 µs. Close #518 by hand after merge. + +### 7. `Filter` and `Bind` (PR 2) +- `Filter` for `Expr { binding: None }`, `Bind` for `Expr { binding: Some }`: build a + `Binding` of the expression's variables only (cells → `Value`), `eval_expr`, drop the + row on `Err`; `Bind` turns the result back into a cell through `IdSpace`. Placement + follows `optimizer::plan` (earliest point its variables are bound; never-bound + variables → end → every row dropped, as today). + +### 8. Pseudo-attributes (PR 2) +- `Scan` emits `valid-from`, `valid-to`, `tx-count` and, only when a pattern asks for it, + `tx-id` (a DICT lookup per committed row; pending facts carry it) as `Val(Int)` + columns; the planner wires each pseudo-attribute pattern to them (variable → that + column, constant → a residual check, `:db/valid-at` → a constant column). `INT-026` + unchanged. + +### 9. Cross-kind constants (PR 2) +- Value keyword `:k`: AVET ranges for `Keyword(k)` and `Ref(edn_to_entity_id(:k))` + (note: a keyword whose name parses as a UUID is that UUID, as `edn_to_entity_id` + does, not its v5 hash; spec §5.3/§5.4 say "uuidv5", which the plan corrects). +- Value UUID `u`: `Ref(u)` range, plus the attribute's keyword range filtered by + `edn_to_entity_id(name) == u`. +- Value float: the attribute's float range, filtered within `f64::EPSILON`. +- Entity and attribute positions keep today's rules (entity: keyword/UUID only; + attribute: keyword only; other constants → no rows, as `match_component` gives). +- Oracle tests for each (the issue's "cross-kind matching rules pinned by oracle tests"). + +### 10. Lazy cursor (PR 3) +- `Cursor` holds the operator tree and the snapshot; `next_batch(max_rows)` pulls + internal batches until `max_rows` rows are ready; errors surface from `next_batch` + (already `Result`). `size_hint` stays `(0, None)` for engine cursors. `close` and drop + call `close` down the tree. +- `Counters` (rows in/out, batches) on every operator; acceptance test (spec §10): + close after the first batch, counters show no further rows read. +- Spec §10 acceptance test for snapshots: a lazy cursor's answer is unchanged by writes + and page-freeing checkpoints between batches (on top of #543's test, now with real + laziness). +- `tests/cursor_test.rs` and binding suites unchanged. + +### 11. Measurement (PR 3) +- #394 envelope at 100K, 1M, 10M on the bench machine, idle: point queries, attribute + scan, `attribute_value`; peak RSS of an attribute scan over 1M facts streamed in + batches of 1,000. `docs/BENCHMARKS.md`: #518 note and rows. + +### 12. Docs (PR 3) +- `CHANGELOG.md` (v3.0.0): single-pattern queries stream; `[?e :a C]` reads the AVET + range (#518); ids until projection (#530). +- `CLAUDE.md` module list (`src/query/engine/`), test count; `ROADMAP.md`; + `docs/TEST_COVERAGE.md`; `README.md` count. +- Docs site (`../minigraf-docs`): `content/architecture.md` query-engine section under + `@since v3.0.0`. +- Comment on #544 for decision 11 (`Limit`/`Offset` → #306), and on #306. + +## Bindings + +No public API change and no new error code, so no binding cascade. From afc67c9e10cecf5fc3058804d4d6dc61ba56fad9 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 14 Oct 2026 13:50:08 +0530 Subject: [PATCH 2/5] feat(query): streaming engine core, Scan over live keys, oracle (#544) Part 2 of the streaming engine (#473), first PR. Queries with one pattern and plain :find variables run on a new engine in src/query/engine/: - CommittedReader::key_source gives key-level reads: live_keys walks an index range with net-assert on keys and resumes after a whole triple, so a read holds no lock between batches; DICT accessors. - Scan reads the committed range (EAVT, AEVT or AVET by the bound positions; [?e :a C] reads the AVET range of C, #518), leaving out the triples a pending record decides, then the pending range by whole (entity, attribute) runs. Cells hold ids until Project (#530); pending entities and idents get provisional ids. - Every other query, and reads inside a write transaction, stay on the executor. The executor is the oracle: under cfg(test) and the test-oracle feature each engine query also runs there and the answers must agree; CI runs the whole suite with the feature. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- .github/workflows/rust.yml | 11 ++ Cargo.toml | 3 + src/graph/storage.rs | 150 +++++++++++++++++ src/query/datalog/executor.rs | 36 +++++ src/query/engine/batch.rs | 30 ++++ src/query/engine/cell.rs | 45 ++++++ src/query/engine/ids.rs | 116 +++++++++++++ src/query/engine/mod.rs | 70 ++++++++ src/query/engine/oracle.rs | 51 ++++++ src/query/engine/plan.rs | 134 +++++++++++++++ src/query/engine/project.rs | 48 ++++++ src/query/engine/scan.rs | 277 ++++++++++++++++++++++++++++++++ src/query/engine/tests.rs | 194 ++++++++++++++++++++++ src/query/mod.rs | 1 + src/storage/dict.rs | 2 +- src/storage/keys.rs | 15 ++ src/storage/mod.rs | 48 +++++- src/storage/persistent_facts.rs | 71 ++++++++ src/storage/reader.rs | 144 +++++++++++++---- 19 files changed, 1411 insertions(+), 35 deletions(-) create mode 100644 src/query/engine/batch.rs create mode 100644 src/query/engine/cell.rs create mode 100644 src/query/engine/ids.rs create mode 100644 src/query/engine/mod.rs create mode 100644 src/query/engine/oracle.rs create mode 100644 src/query/engine/plan.rs create mode 100644 src/query/engine/project.rs create mode 100644 src/query/engine/scan.rs create mode 100644 src/query/engine/tests.rs diff --git a/.github/workflows/rust.yml b/.github/workflows/rust.yml index 5884caefec..21eaac7908 100644 --- a/.github/workflows/rust.yml +++ b/.github/workflows/rust.yml @@ -36,3 +36,14 @@ jobs: env: RUSTDOCFLAGS: "--cfg docsrs" run: cargo doc --all-features --no-deps + + # The streaming engine (#473) runs beside the existing executor until #551. + # With this feature every query the engine runs is also run by the executor, + # and a different answer fails the test, so the whole suite (model-based, + # property, golden corpus, integration) checks the engine. + oracle: + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v3 + - name: Run tests with the executor as the engine's oracle + run: cargo test --features test-oracle diff --git a/Cargo.toml b/Cargo.toml index 1aaca2ae99..02a3d57870 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -83,6 +83,9 @@ harness = false [features] default = [] wasm = [] +# Run the existing executor beside the streaming engine and compare every +# answer (#473 spec §9). Tests only. +test-oracle = [] browser = [ "dep:wasm-bindgen", "dep:wasm-bindgen-futures", diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 069526c6da..776e8aba77 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -246,6 +246,156 @@ impl Snapshot { } } +/// Where a pending walk ([`Snapshot::pending_live`]) resumes: after this +/// index key, the last of the last whole run it returned. +#[derive(Debug, Clone)] +pub(crate) enum PendingResume { + Eavt(crate::storage::index::EavtKey), + Aevt(crate::storage::index::AevtKey), +} + +impl Snapshot { + /// The pending records of `scan` in the snapshot with `tx_count <= as_of` + /// (all when `None`), assertions and retractions, in no set order. + pub(crate) fn pending_records( + &self, + scan: crate::storage::Scan<'_>, + as_of: Option, + ) -> Result> { + let p = self.read_pending()?; + let mut facts = Vec::new(); + pending_facts_of_scan(&p, self.pending_len, scan, as_of, &mut facts)?; + Ok(facts) + } + + /// The pending facts of `scan` in the snapshot that survive net-assert at + /// `as_of` among the pending records, appended to `out` in pending index + /// order (EAVT, or AEVT for [`Scan::Attribute`](crate::storage::Scan)). + /// + /// Reads whole `(entity, attribute)` runs, so every record of a triple is + /// decided together, and stops after the run that brings the facts out to + /// `max` or more. Starts after `resume` and sets it to where the next call + /// starts; returns false once the range is done. Holds the pending read + /// lock for one call only. + pub(crate) fn pending_live( + &self, + scan: crate::storage::Scan<'_>, + as_of: Option, + resume: &mut Option, + max: usize, + out: &mut Vec, + ) -> Result { + use crate::storage::Scan; + use crate::storage::index::{AevtKey, EavtKey}; + use std::ops::Bound::{Excluded, Included, Unbounded}; + let p = self.read_pending()?; + let walk = RunWalk { + p: &p, + len: self.pending_len, + as_of, + max, + }; + let stopped = match scan { + Scan::Attribute(attribute) => { + let from = match resume.take() { + Some(PendingResume::Aevt(k)) => Excluded(k), + _ => Included(AevtKey::attribute_start(attribute)), + }; + walk.run( + p.indexes.aevt.range((from, Unbounded)), + |k| k.attribute == attribute, + |k| (&k.entity, k.attribute.as_str()), + out, + )? + .map(PendingResume::Aevt) + } + Scan::All | Scan::Entity(_) | Scan::EntityAttribute(..) => { + let start = match scan { + Scan::Entity(e) => EavtKey::entity_start(*e), + Scan::EntityAttribute(e, a) => EavtKey::entity_attribute_start(*e, a), + _ => EavtKey::entity_start(EntityId::nil()), + }; + let from = match resume.take() { + Some(PendingResume::Eavt(k)) => Excluded(k), + _ => Included(start), + }; + walk.run( + p.indexes.eavt.range((from, Unbounded)), + |k| match scan { + Scan::Entity(e) => k.entity == *e, + Scan::EntityAttribute(e, a) => k.entity == *e && k.attribute == a, + _ => true, + }, + |k| (&k.entity, k.attribute.as_str()), + out, + )? + .map(PendingResume::Eavt) + } + }; + let more = stopped.is_some(); + *resume = stopped; + Ok(more) + } +} + +/// One call of [`Snapshot::pending_live`] over one pending index. +struct RunWalk<'a> { + p: &'a PendingStore, + len: usize, + as_of: Option, + max: usize, +} + +impl<'a> RunWalk<'a> { + /// Walk `entries` while `in_range`, deciding each `(entity, attribute)` run + /// (`run_of`) with [`net_asserted_facts`]. Returns the last key of the + /// last run when it stopped early, `None` when the range is done. + fn run( + &self, + entries: impl Iterator, + in_range: impl Fn(&K) -> bool, + run_of: impl Fn(&K) -> (&EntityId, &str), + out: &mut Vec, + ) -> Result> { + let mut run: Vec = Vec::new(); + let mut first: Option<&K> = None; + let mut last: Option<&K> = None; + let mut emitted = 0usize; + for (k, &pos) in entries { + if !in_range(k) { + break; + } + if let (Some(f), Some(l)) = (first, last) + && run_of(f) != run_of(k) + { + emitted += flush_run(&mut run, out); + if emitted >= self.max { + return Ok(Some(l.clone())); + } + first = None; + } + first.get_or_insert(k); + last = Some(k); + if pos < self.len { + let f = pending_fact(self.p, pos)?; + if self.as_of.is_none_or(|n| f.tx_count <= n) { + run.push(f); + } + } + } + flush_run(&mut run, out); + Ok(None) + } +} + +/// Move the net-asserted facts of `run` onto `out`; returns how many. +fn flush_run(run: &mut Vec, out: &mut Vec) -> usize { + let live = net_asserted_facts(std::mem::take(run)); + let n = live.len(); + out.extend(live); + n +} + impl Default for FactStorage { fn default() -> Self { Self::new() diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 70c806c959..3132e9aa7f 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -509,6 +509,42 @@ impl DatalogExecutor { return Err(err_coded!(ErrorCode::Int027)); } + // The streaming engine runs the queries it has operators for (#473). + // Reads inside a write transaction (`facts_override`) stay here (#550). + if self.facts_override.is_none() + && let Some(plan) = crate::query::engine::plan(&query) + { + let snapshot = self.read_snapshot()?; + if let Some(result) = crate::query::engine::run(&snapshot, plan) { + #[cfg(any(test, feature = "test-oracle"))] + crate::query::engine::oracle::check( + &result, + &self.oracle(snapshot).execute_query_on_executor(query), + ); + return result; + } + } + self.execute_query_on_executor(query) + } + + /// This executor over `snapshot`, for the engine's oracle (#473 spec §9). + #[cfg(any(test, feature = "test-oracle"))] + fn oracle(&self, snapshot: Snapshot) -> DatalogExecutor { + DatalogExecutor { + storage: self.storage.clone(), + snapshot: Some(snapshot), + facts_override: None, + read_now_floor: self.read_now_floor, + rules: self.rules.clone(), + functions: self.functions.clone(), + max_derived_facts: self.max_derived_facts, + max_results: self.max_results, + } + } + + /// [`Self::execute_query`] on this executor, after the checks every + /// query passes first. + fn execute_query_on_executor(&self, query: DatalogQuery) -> Result { // Compute query-level valid_at value for :db/valid-at pseudo-attribute binding. let now = self.read_now(); let valid_at_value = match &query.valid_at { diff --git a/src/query/engine/batch.rs b/src/query/engine/batch.rs new file mode 100644 index 0000000000..84de920368 --- /dev/null +++ b/src/query/engine/batch.rs @@ -0,0 +1,30 @@ +//! Columnar batches of rows (#473 spec §5.1). + +use super::cell::Cell; + +/// At most [`BATCH_ROWS`](super::BATCH_ROWS) rows, one column per variable +/// slot of the plan. +#[derive(Debug)] +pub(crate) struct Batch { + pub(crate) cols: Vec>, + pub(crate) len: usize, +} + +impl Batch { + pub(crate) fn new(width: usize) -> Self { + Batch { + cols: vec![Vec::new(); width], + len: 0, + } + } + + /// Append one row. Every slot must be filled. + pub(crate) fn push(&mut self, row: &mut [Option]) { + for (col, cell) in self.cols.iter_mut().zip(row.iter_mut()) { + if let Some(cell) = cell.take() { + col.push(cell); + } + } + self.len += 1; + } +} diff --git a/src/query/engine/cell.rs b/src/query/engine/cell.rs new file mode 100644 index 0000000000..27769ca5ff --- /dev/null +++ b/src/query/engine/cell.rs @@ -0,0 +1,45 @@ +//! Cells: the values operators exchange (#473 spec §5.2). + +use crate::storage::keys::{KeyValue, ValueRef}; +use std::sync::Arc; + +/// One value in a row. Entities and keywords are ids in the query's +/// [`IdSpace`](super::ids::IdSpace); everything else is a [`Scalar`]. +#[derive(Debug, Clone, PartialEq)] +pub(crate) enum Cell { + /// An entity: a DICT entity id, or a provisional id. + Eid(u64), + /// An ident used as a value (a keyword, or an attribute): a DICT ident + /// id, or a provisional id. + Iid(u64), + Val(Scalar), +} + +/// A value that is neither an entity nor a keyword. +#[derive(Debug, Clone, PartialEq)] +pub(crate) enum Scalar { + Null, + Bool(bool), + Int(i64), + Float(f64), + /// A committed string of up to 64 bytes, or a pending string. + Str(Arc), + /// A committed string over 64 bytes, by where it is stored. + Long(ValueRef), +} + +impl Cell { + /// The cell of a committed key value. + pub(crate) fn of_key(v: &KeyValue) -> Cell { + match v { + KeyValue::Null => Cell::Val(Scalar::Null), + KeyValue::Bool(b) => Cell::Val(Scalar::Bool(*b)), + KeyValue::Int(n) => Cell::Val(Scalar::Int(*n)), + KeyValue::Float(f) => Cell::Val(Scalar::Float(*f)), + KeyValue::Str(s) => Cell::Val(Scalar::Str(Arc::from(s.as_str()))), + KeyValue::LongStr { vref, .. } => Cell::Val(Scalar::Long(*vref)), + KeyValue::Keyword(iid) => Cell::Iid(u64::from(*iid)), + KeyValue::Ref(eid) => Cell::Eid(*eid), + } + } +} diff --git a/src/query/engine/ids.rs b/src/query/engine/ids.rs new file mode 100644 index 0000000000..6885e0f120 --- /dev/null +++ b/src/query/engine/ids.rs @@ -0,0 +1,116 @@ +//! One id space per query (#473 spec §5.3). +//! +//! Committed entities and idents have DICT ids. Pending facts hold UUIDs and +//! strings; those the DICT lacks get provisional ids, from the generation's +//! `next_eid` / `next_iid` upwards, the first time the query meets them. +//! Provisional ids are never written anywhere. + +use crate::error::{ErrorCode, err_coded}; +use crate::graph::types::EntityId; +use crate::storage::KeySource; +use anyhow::Result; +use std::collections::HashMap; +use std::sync::Arc; + +pub(crate) struct IdSpace { + /// The first provisional ids: every DICT id is below them. + dict_eids: u64, + dict_iids: u64, + next_eid: u64, + next_iid: u64, + eid_by_uuid: HashMap, + uuid_by_eid: HashMap, + iid_by_name: HashMap, u64>, + name_by_iid: HashMap>, +} + +impl IdSpace { + pub(crate) fn new(keys: Option<&dyn KeySource>) -> Self { + let (eids, iids) = keys.map_or((0, 0), |k| { + let (e, i) = k.next_ids(); + (e, u64::from(i)) + }); + IdSpace { + dict_eids: eids, + dict_iids: iids, + next_eid: eids, + next_iid: iids, + eid_by_uuid: HashMap::new(), + uuid_by_eid: HashMap::new(), + iid_by_name: HashMap::new(), + name_by_iid: HashMap::new(), + } + } + + /// The id of `uuid`: its DICT id, or a provisional one. + pub(crate) fn eid(&mut self, keys: Option<&dyn KeySource>, uuid: &EntityId) -> Result { + if let Some(&e) = self.eid_by_uuid.get(uuid) { + return Ok(e); + } + let e = match keys.map(|k| k.eid_of(uuid)).transpose()?.flatten() { + Some(e) => e, + None => { + let e = self.next_eid; + self.next_eid += 1; + e + } + }; + self.eid_by_uuid.insert(*uuid, e); + self.uuid_by_eid.insert(e, *uuid); + Ok(e) + } + + /// The id of the ident `name`: its DICT id, or a provisional one. + pub(crate) fn iid(&mut self, keys: Option<&dyn KeySource>, name: &str) -> Result { + if let Some(&i) = self.iid_by_name.get(name) { + return Ok(i); + } + let i = match keys.map(|k| k.iid_of(name)).transpose()?.flatten() { + Some(i) => u64::from(i), + None => { + let i = self.next_iid; + self.next_iid += 1; + i + } + }; + let name: Arc = Arc::from(name); + self.iid_by_name.insert(name.clone(), i); + self.name_by_iid.insert(i, name); + Ok(i) + } + + /// The entity with id `eid`. + pub(crate) fn uuid(&mut self, keys: Option<&dyn KeySource>, eid: u64) -> Result { + if let Some(u) = self.uuid_by_eid.get(&eid) { + return Ok(*u); + } + let Some(k) = keys.filter(|_| eid < self.dict_eids) else { + return Err(err_coded!( + ErrorCode::Int049, + format!("query engine: unknown entity id {eid}") + )); + }; + let u = k.uuid_of(eid)?; + self.uuid_by_eid.insert(eid, u); + self.eid_by_uuid.insert(u, eid); + Ok(u) + } + + /// The ident with id `iid`. + pub(crate) fn name(&mut self, keys: Option<&dyn KeySource>, iid: u64) -> Result> { + if let Some(n) = self.name_by_iid.get(&iid) { + return Ok(n.clone()); + } + let k = keys.filter(|_| iid < self.dict_iids); + let (Some(k), Ok(i)) = (k, u32::try_from(iid)) else { + return Err(err_coded!( + ErrorCode::Int049, + format!("query engine: unknown ident id {iid}") + )); + }; + let n: Arc = Arc::from(k.ident_of(i)?); + self.name_by_iid.insert(iid, n.clone()); + self.iid_by_name.insert(n.clone(), iid); + Ok(n) + } +} diff --git a/src/query/engine/mod.rs b/src/query/engine/mod.rs new file mode 100644 index 0000000000..7e6882ab7e --- /dev/null +++ b/src/query/engine/mod.rs @@ -0,0 +1,70 @@ +//! Streaming query engine (#473): operators that pass batches of id cells +//! over one [`Snapshot`]. +//! +//! Built beside the existing executor (spec §9): [`plan`] says which queries +//! run here, and the executor runs the rest. Under `cfg(test)` and the +//! `test-oracle` feature, every query run here is also run by the executor +//! and the answers are compared ([`oracle`]). + +mod batch; +mod cell; +mod ids; +#[cfg(any(test, feature = "test-oracle"))] +pub(crate) mod oracle; +mod plan; +mod project; +mod scan; +#[cfg(all(test, not(target_arch = "wasm32")))] +mod tests; + +use crate::graph::storage::Snapshot; +use crate::query::datalog::executor::QueryResult; +use crate::storage::KeySource; +use anyhow::Result; +use ids::IdSpace; +pub(crate) use plan::{Plan, plan}; + +#[cfg(test)] +thread_local! { + /// Queries this thread ran on the engine (tests check routing with it). + pub(crate) static RUNS: std::cell::Cell = const { std::cell::Cell::new(0) }; +} + +/// Most rows in one internal batch (spec §5.1). +pub(crate) const BATCH_ROWS: usize = 1024; + +/// What every operator of one query reads and shares. +pub(crate) struct Ctx<'a> { + snapshot: &'a Snapshot, + /// Key-level reads of the committed generation; `None` for an in-memory + /// database. + keys: Option<&'a dyn KeySource>, + ids: IdSpace, +} + +/// Run `plan` over `snapshot`, or `None` when the snapshot's committed +/// reader has no keys (a test reader) and the executor must run it. +pub(crate) fn run(snapshot: &Snapshot, plan: Plan) -> Option> { + let keys = match &snapshot.committed { + Some(reader) => Some(reader.key_source()?), + None => None, + }; + #[cfg(test)] + RUNS.with(|r| r.set(r.get() + 1)); + Some(execute(snapshot, keys, plan)) +} + +fn execute(snapshot: &Snapshot, keys: Option<&dyn KeySource>, plan: Plan) -> Result { + let Plan { scan, find, vars } = plan; + let mut results = Vec::new(); + let mut ctx = Ctx { + snapshot, + keys, + ids: IdSpace::new(keys), + }; + let mut scan = scan::Scan::new(scan); + while let Some(batch) = scan.next_batch(&mut ctx)? { + results.extend(project::project(&batch, &find, &mut ctx)?); + } + Ok(QueryResult::QueryResults { vars, results }) +} diff --git a/src/query/engine/oracle.rs b/src/query/engine/oracle.rs new file mode 100644 index 0000000000..ab323d3e18 --- /dev/null +++ b/src/query/engine/oracle.rs @@ -0,0 +1,51 @@ +//! The existing executor as an oracle for the engine (#473 spec §9). + +use crate::query::datalog::executor::QueryResult; +use crate::storage::index::encode_value; +use anyhow::Result; + +/// Panic unless `engine` and `oracle` give the same answer: both errors, or +/// the same columns and the same rows as a bag. Messages hold counts and +/// column names only, never values. +/// +/// Built only for tests (`cfg(test)`, the `test-oracle` feature), where a +/// panic is how a disagreement fails the test. +#[allow(clippy::panic)] +pub(crate) fn check(engine: &Result, oracle: &Result) { + match (engine, oracle) { + (Err(_), Err(_)) => {} + ( + Ok(QueryResult::QueryResults { + vars: v1, + results: r1, + }), + Ok(QueryResult::QueryResults { + vars: v2, + results: r2, + }), + ) => { + assert!( + v1 == v2, + "engine and oracle columns differ: {v1:?} vs {v2:?}" + ); + assert!( + bag(r1) == bag(r2), + "engine and oracle rows differ for {v1:?}: {} vs {} rows", + r1.len(), + r2.len() + ); + } + (Ok(_), Err(_)) => panic!("engine answered where the oracle failed"), + (Err(_), Ok(_)) => panic!("engine failed where the oracle answered"), + (Ok(_), Ok(_)) => panic!("engine or oracle gave a non-query result"), + } +} + +fn bag(rows: &[Vec]) -> Vec>> { + let mut bag: Vec>> = rows + .iter() + .map(|r| r.iter().map(encode_value).collect()) + .collect(); + bag.sort(); + bag +} diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs new file mode 100644 index 0000000000..1d8195e80b --- /dev/null +++ b/src/query/engine/plan.rs @@ -0,0 +1,134 @@ +//! Planner v1 (#473 spec §6.3): which queries the engine runs, and their +//! operator trees. +//! +//! #544 runs a query whose `:where` is one pattern with a stored attribute, +//! and whose `:find` holds plain variables. Every other query runs on the +//! existing executor (spec §9). + +use crate::graph::types::{EntityId, Value}; +use crate::query::datalog::matcher::edn_to_entity_id; +use crate::query::datalog::types::{ + AsOf, AttributeSpec, DatalogQuery, EdnValue, FindSpec, ValidAt, WhereClause, +}; +use std::collections::HashMap; + +/// One position of a pattern. +#[derive(Debug, Clone)] +pub(crate) enum Term { + /// `_` or a `?_` variable: matches anything, binds nothing. + Any, + /// The first occurrence of a variable: binds its slot. + Bind(usize), + /// A later occurrence of a variable: must equal its slot. + Eq(usize), + Const(C), +} + +/// The valid-time test of a query. +#[derive(Debug, Clone, Copy)] +pub(crate) enum Valid { + /// No `:valid-at`: valid at the snapshot's "now". + Now, + At(i64), + Any, +} + +/// What a `Scan` reads. +#[derive(Debug, Clone)] +pub(crate) struct ScanSpec { + pub(crate) e: Term, + pub(crate) a: Term, + pub(crate) v: Term, + pub(crate) as_of: Option, + pub(crate) valid: Valid, + /// Number of variable slots. + pub(crate) width: usize, +} + +#[derive(Debug)] +pub(crate) struct Plan { + pub(crate) scan: ScanSpec, + /// The slot of each `:find` variable. + pub(crate) find: Vec, + pub(crate) vars: Vec, +} + +/// The plan of `query`, or `None` when the engine does not run it yet. +pub(crate) fn plan(query: &DatalogQuery) -> Option { + let as_of = match &query.as_of { + None => None, + Some(AsOf::Counter(n)) => Some(*n), + // A timestamp is not a key bound; a slot is resolved before this. + Some(AsOf::Timestamp(_) | AsOf::Slot(_)) => return None, + }; + let valid = match &query.valid_at { + None => Valid::Now, + Some(ValidAt::Timestamp(t)) => Valid::At(*t), + Some(ValidAt::AnyValidTime) => Valid::Any, + Some(ValidAt::Slot(_)) => return None, + }; + let [WhereClause::Pattern(p)] = query.where_clauses.as_slice() else { + return None; + }; + let AttributeSpec::Real(attribute) = &p.attribute else { + return None; + }; + let mut slots = HashMap::new(); + let e = term(&p.entity, &mut slots, |c| match c { + EdnValue::Keyword(_) | EdnValue::Uuid(_) => edn_to_entity_id(c).ok(), + _ => None, + })?; + let a = term(attribute, &mut slots, |c| match c { + EdnValue::Keyword(k) => Some(k.clone()), + _ => None, + })?; + let v = term(&p.value, &mut slots, |c| match c { + EdnValue::String(s) => Some(Value::String(s.clone())), + EdnValue::Integer(n) => Some(Value::Integer(*n)), + EdnValue::Boolean(b) => Some(Value::Boolean(*b)), + EdnValue::Nil => Some(Value::Null), + _ => None, + })?; + let mut find = Vec::with_capacity(query.find.len()); + for spec in &query.find { + let FindSpec::Variable(var) = spec else { + return None; + }; + // The parser rejects a variable no clause binds (PRS-080). + find.push(*slots.get(var)?); + } + Some(Plan { + scan: ScanSpec { + e, + a, + v, + as_of, + valid, + width: slots.len(), + }, + find, + vars: query.find.iter().map(FindSpec::display_name).collect(), + }) +} + +/// The term of one pattern position; `None` for a constant `konst` does not +/// take, or a symbol that is not a variable. +fn term( + edn: &EdnValue, + slots: &mut HashMap, + konst: impl Fn(&EdnValue) -> Option, +) -> Option> { + match edn { + EdnValue::Symbol(s) if s == "_" || s.starts_with("?_") => Some(Term::Any), + EdnValue::Symbol(s) if s.starts_with('?') => Some(match slots.get(s) { + Some(&slot) => Term::Eq(slot), + None => { + let slot = slots.len(); + slots.insert(s.clone(), slot); + Term::Bind(slot) + } + }), + EdnValue::Symbol(_) => None, + c => konst(c).map(Term::Const), + } +} diff --git a/src/query/engine/project.rs b/src/query/engine/project.rs new file mode 100644 index 0000000000..1aafc01ef8 --- /dev/null +++ b/src/query/engine/project.rs @@ -0,0 +1,48 @@ +//! `Project` (#473 spec §6.1): the `:find` columns of a batch, as values. +//! +//! Only rows that are returned are converted, so a query reads ids until +//! the end (#530). + +use super::Ctx; +use super::batch::Batch; +use super::cell::{Cell, Scalar}; +use crate::graph::types::Value; +use anyhow::Result; + +/// The rows of `batch`, with the cells of the slots `find` as values. +pub(crate) fn project(batch: &Batch, find: &[usize], ctx: &mut Ctx<'_>) -> Result>> { + let mut rows = Vec::with_capacity(batch.len); + for i in 0..batch.len { + let mut row = Vec::with_capacity(find.len()); + for &slot in find { + let cell = batch.cols.get(slot).and_then(|c| c.get(i)); + row.push(match cell { + Some(cell) => value(cell, ctx)?, + None => Value::Null, + }); + } + rows.push(row); + } + Ok(rows) +} + +fn value(cell: &Cell, ctx: &mut Ctx<'_>) -> Result { + Ok(match cell { + Cell::Eid(e) => Value::Ref(ctx.ids.uuid(ctx.keys, *e)?), + Cell::Iid(i) => Value::Keyword(ctx.ids.name(ctx.keys, *i)?.to_string()), + Cell::Val(Scalar::Null) => Value::Null, + Cell::Val(Scalar::Bool(b)) => Value::Boolean(*b), + Cell::Val(Scalar::Int(n)) => Value::Integer(*n), + Cell::Val(Scalar::Float(f)) => Value::Float(*f), + Cell::Val(Scalar::Str(s)) => Value::String(s.to_string()), + Cell::Val(Scalar::Long(vref)) => match ctx.keys { + Some(k) => Value::String(k.long_value(*vref)?), + None => { + return Err(crate::error::err_coded!( + crate::error::ErrorCode::Int049, + "query engine: long value without a committed reader" + )); + } + }, + }) +} diff --git a/src/query/engine/scan.rs b/src/query/engine/scan.rs new file mode 100644 index 0000000000..8a615ad278 --- /dev/null +++ b/src/query/engine/scan.rs @@ -0,0 +1,277 @@ +//! `Scan` (#473 spec §6.1): one pattern over one key range of the snapshot. +//! +//! Every pending fact is newer than every committed one, so a triple with a +//! pending record in the snapshot (at or before `:as-of`) is decided by its +//! pending records alone, and a triple without one by its committed keys +//! (#379). `Scan` reads the committed range first, leaving out the triples a +//! pending record decides (the shadow set), then the pending range. + +use super::batch::Batch; +use super::cell::{Cell, Scalar}; +use super::plan::{ScanSpec, Term, Valid}; +use super::{BATCH_ROWS, Ctx}; +use crate::graph::storage::PendingResume; +use crate::graph::types::{Fact, Value}; +use crate::storage::keys::{self, Index, KeyFact, KeyValue, SHORT_STRING_MAX}; +use crate::storage::{KeySource, Scan as Range}; +use anyhow::Result; +use std::collections::HashSet; +use std::sync::Arc; + +pub(crate) struct Scan { + spec: ScanSpec, + state: State, + keys_buf: Vec, + facts_buf: Vec, +} + +enum State { + Start, + Committed(Committed), + Pending(Option), + Done, +} + +/// The committed half of the read. +struct Committed { + index: Index, + prefix: Vec, + resume: Option>, + /// The value constant when the range does not fix it. + value: Option, + /// Triples a pending record decides, as [`keys::entity_attribute_value_prefix`]. + shadow: HashSet>, +} + +impl Scan { + pub(crate) fn new(spec: ScanSpec) -> Self { + Scan { + spec, + state: State::Start, + keys_buf: Vec::new(), + facts_buf: Vec::new(), + } + } + + pub(crate) fn next_batch(&mut self, ctx: &mut Ctx<'_>) -> Result> { + loop { + let mut batch = Batch::new(self.spec.width); + match &mut self.state { + State::Start => self.state = open(&self.spec, ctx)?, + State::Committed(c) => { + let Some(keys) = ctx.keys else { + self.state = State::Pending(None); + continue; + }; + self.keys_buf.clear(); + c.resume = keys.live_keys( + c.index, + &c.prefix, + c.resume.as_deref(), + self.spec.as_of, + BATCH_ROWS, + &mut self.keys_buf, + )?; + let valid = valid_at(self.spec.valid, ctx); + let mut row = vec![None; self.spec.width]; + for kf in &self.keys_buf { + if !visible(valid, kf.vf, kf.vt) + || c.value.as_ref().is_some_and(|v| *v != kf.v) + || (!c.shadow.is_empty() + && c.shadow.contains(&keys::entity_attribute_value_prefix( + kf.e, kf.a, &kf.v, + ))) + { + continue; + } + if fill(&self.spec.e, &mut row, || Ok(Cell::Eid(kf.e)))? + && fill(&self.spec.a, &mut row, || Ok(Cell::Iid(u64::from(kf.a))))? + && fill(&self.spec.v, &mut row, || Ok(Cell::of_key(&kf.v)))? + { + batch.push(&mut row); + } + row.iter_mut().for_each(|c| *c = None); + } + if c.resume.is_none() { + self.state = State::Pending(None); + } + } + State::Pending(resume) => { + self.facts_buf.clear(); + let more = ctx.snapshot.pending_live( + range(&self.spec), + self.spec.as_of, + resume, + BATCH_ROWS, + &mut self.facts_buf, + )?; + let valid = valid_at(self.spec.valid, ctx); + let mut row = vec![None; self.spec.width]; + for f in &self.facts_buf { + if !visible(valid, f.valid_from, f.valid_to) + || matches!(&self.spec.v, Term::Const(v) if *v != f.value) + { + continue; + } + let keys = ctx.keys; + let ids = &mut ctx.ids; + if fill(&self.spec.e, &mut row, || { + Ok(Cell::Eid(ids.eid(keys, &f.entity)?)) + })? && fill(&self.spec.a, &mut row, || { + Ok(Cell::Iid(ids.iid(keys, &f.attribute)?)) + })? && fill(&self.spec.v, &mut row, || value_cell(ids, keys, &f.value))? + { + batch.push(&mut row); + } + row.iter_mut().for_each(|c| *c = None); + } + if !more { + self.state = State::Done; + } + } + State::Done => return Ok(None), + } + if batch.len > 0 { + return Ok(Some(batch)); + } + } + } +} + +/// Resolve the committed range of `spec` and the pending triples that +/// shadow it. +fn open(spec: &ScanSpec, ctx: &mut Ctx<'_>) -> Result { + let Some(keys) = ctx.keys else { + return Ok(State::Pending(None)); + }; + let pending = State::Pending(None); + let e = match &spec.e { + Term::Const(u) => match keys.eid_of(u)? { + Some(e) => Some(e), + None => return Ok(pending), + }, + _ => None, + }; + let a = match &spec.a { + Term::Const(name) => match keys.iid_of(name)? { + Some(a) => Some(a), + None => return Ok(pending), + }, + _ => None, + }; + let v = match &spec.v { + Term::Const(value) => match key_value(keys, value)? { + Some(v) => Some(v), + None => return Ok(pending), + }, + _ => None, + }; + let (index, prefix, value) = match (e, a, v) { + (Some(e), Some(a), Some(v)) => ( + Index::Eavt, + keys::entity_attribute_value_prefix(e, a, &v), + None, + ), + (Some(e), Some(a), None) => (Index::Eavt, keys::entity_attribute_prefix(e, a), None), + (Some(e), None, v) => (Index::Eavt, keys::entity_prefix(e), v), + (None, Some(a), Some(v)) => (Index::Avet, keys::attribute_value_prefix(a, &v), None), + (None, Some(a), None) => (Index::Aevt, keys::attribute_prefix(a), None), + (None, None, v) => (Index::Eavt, Vec::new(), v), + }; + let mut shadow = HashSet::new(); + for f in ctx.snapshot.pending_records(range(spec), spec.as_of)? { + if let Some(t) = committed_triple(keys, &f)? { + shadow.insert(t); + } + } + Ok(State::Committed(Committed { + index, + prefix, + resume: None, + value, + shadow, + })) +} + +/// The pending range of `spec`. +fn range(spec: &ScanSpec) -> Range<'_> { + match (&spec.e, &spec.a) { + (Term::Const(e), Term::Const(a)) => Range::EntityAttribute(e, a), + (Term::Const(e), _) => Range::Entity(e), + (_, Term::Const(a)) => Range::Attribute(a), + _ => Range::All, + } +} + +/// The triple bytes of `f` as committed keys hold them, or `None` when no +/// committed fact can have its triple (an entity, ident or long string the +/// generation does not hold). +fn committed_triple(keys: &dyn KeySource, f: &Fact) -> Result>> { + let (Some(e), Some(a)) = (keys.eid_of(&f.entity)?, keys.iid_of(&f.attribute)?) else { + return Ok(None); + }; + Ok(key_value(keys, &f.value)?.map(|v| keys::entity_attribute_value_prefix(e, a, &v))) +} + +/// `value` as committed keys hold it, or `None` when no committed key can. +fn key_value(keys: &dyn KeySource, value: &Value) -> Result> { + Ok(match value { + Value::Null => Some(KeyValue::Null), + Value::Boolean(b) => Some(KeyValue::Bool(*b)), + Value::Integer(n) => Some(KeyValue::Int(*n)), + Value::Float(f) => Some(KeyValue::Float(*f)), + Value::String(s) if s.len() <= SHORT_STRING_MAX => Some(KeyValue::Str(s.clone())), + Value::String(s) => keys.long_value_ref(s)?.map(|vref| keys::long_str(s, vref)), + Value::Keyword(k) => keys.iid_of(k)?.map(KeyValue::Keyword), + Value::Ref(u) => keys.eid_of(u)?.map(KeyValue::Ref), + }) +} + +/// The cell of a pending fact's value. +fn value_cell( + ids: &mut super::ids::IdSpace, + keys: Option<&dyn KeySource>, + value: &Value, +) -> Result { + Ok(match value { + Value::Null => Cell::Val(Scalar::Null), + Value::Boolean(b) => Cell::Val(Scalar::Bool(*b)), + Value::Integer(n) => Cell::Val(Scalar::Int(*n)), + Value::Float(f) => Cell::Val(Scalar::Float(*f)), + Value::String(s) => Cell::Val(Scalar::Str(Arc::from(s.as_str()))), + Value::Keyword(k) => Cell::Iid(ids.iid(keys, k)?), + Value::Ref(u) => Cell::Eid(ids.eid(keys, u)?), + }) +} + +/// The valid time a fact must cover, `None` for any. +fn valid_at(valid: Valid, ctx: &Ctx<'_>) -> Option { + match valid { + Valid::Now => Some(ctx.snapshot.now()), + Valid::At(t) => Some(t), + Valid::Any => None, + } +} + +fn visible(valid: Option, vf: i64, vt: i64) -> bool { + valid.is_none_or(|t| vf <= t && t < vt) +} + +/// Apply one position to `row`: bind its slot, or check it against the slot +/// an earlier position bound. Returns false when the row does not match. +fn fill( + term: &Term, + row: &mut [Option], + cell: impl FnOnce() -> Result, +) -> Result { + match term { + Term::Any | Term::Const(_) => Ok(true), + Term::Bind(slot) => { + if let Some(s) = row.get_mut(*slot) { + *s = Some(cell()?); + } + Ok(true) + } + Term::Eq(slot) => Ok(row.get(*slot).and_then(Option::as_ref) == Some(&cell()?)), + } +} diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs new file mode 100644 index 0000000000..4b2f5e3a61 --- /dev/null +++ b/src/query/engine/tests.rs @@ -0,0 +1,194 @@ +//! Targeted shapes for the engine. Every query here also runs on the +//! executor, and the answers must agree (`oracle::check`), so these tests +//! check the engine against the executor over histories chosen to reach each +//! index choice, net-assert across committed and pending records, `:as-of`, +//! valid time, long strings, and cross-kind values. + +use super::RUNS; +use crate::QueryResult; +use crate::db::Minigraf; + +fn runs() -> usize { + RUNS.with(std::cell::Cell::get) +} + +/// Rows of `query`, which must run on the engine. +fn rows(db: &Minigraf, query: &str) -> usize { + let before = runs(); + let QueryResult::QueryResults { results, .. } = db.execute(query).unwrap() else { + panic!("expected query results"); + }; + assert_eq!(runs(), before + 1, "query ran on the engine"); + results.len() +} + +fn long(tag: u32) -> String { + format!("{}{tag}", "a long string kept in a value page ".repeat(3)) +} + +/// One batch of history, numbered `round`: assertions, retractions, +/// re-assertions in new windows, refs, keywords, long strings. +fn write_round(db: &Minigraf, round: u32) { + for p in 0..6u32 { + let s = (round + p) % 3; + db.execute(&format!( + "(transact [[:p{p} :person/status :s{s}] [:p{p} :person/age {age}] \ + [:p{p} :person/friend :p{f}] [:p{p} :person/name \"n{p}\"] \ + [:p{p} :person/bio \"{bio}\"] [:p{p} :person/ok {ok}] [:p{p} :person/self :p{p}]])", + age = 20 + round % 4, + f = (p + round) % 6, + bio = long(p % 2), + ok = (round + p) % 2 == 0, + )) + .unwrap(); + if (round + p) % 2 == 0 { + db.execute(&format!( + "(retract [[:p{p} :person/status :s{s}] [:p{p} :person/age {}]])", + 20 + round % 4 + )) + .unwrap(); + } + if (round + p) % 3 == 0 { + db.execute(&format!( + "(transact {{:valid-from \"2023-01-01\" :valid-to \"2023-06-30\"}} \ + [[:p{p} :person/name \"n{p}\"] [:p{p} :person/null nil]])" + )) + .unwrap(); + } + } +} + +/// Every query shape the planner takes, at several `:as-of` and valid times. +fn queries(tx: u64) -> Vec { + let shapes = [ + "[?e ?a ?v]", + "[?e :person/status ?v]", + "[?e :person/bio ?v]", + "[:p1 ?a ?v]", + "[:p1 :person/age ?v]", + "[?e :person/name \"n2\"]", + "[?e :person/age 21]", + "[?e :person/ok true]", + "[?e :person/null nil]", + "[?e ?a 22]", + "[:p2 ?a \"n2\"]", + "[?e :person/self ?e]", + "[?e ?a ?a]", + "[_ :person/friend ?v]", + "[?_x :person/age ?v]", + "[:nobody ?a ?v]", + "[?e :no/such ?v]", + "[?e :person/name \"no such name\"]", + ]; + let mut out = Vec::new(); + for shape in shapes { + let find = ["?e", "?a", "?v"] + .into_iter() + .filter(|v| shape.contains(v)) + .collect::>(); + if find.is_empty() { + continue; + } + let find = find.join(" "); + for temporal in [ + String::new(), + ":valid-at :any-valid-time".to_string(), + ":valid-at \"2023-03-01\"".to_string(), + format!(":as-of {} :valid-at :any-valid-time", tx / 2), + format!(":as-of {}", tx.saturating_sub(1)), + ":as-of 1".to_string(), + ] { + out.push(format!("(query [:find {find} {temporal} :where {shape}])")); + } + } + out +} + +fn check_all(db: &Minigraf) -> usize { + let tx = db.current_tx_count(); + queries(tx).iter().map(|q| rows(db, q)).sum() +} + +#[test] +fn engine_matches_executor_in_memory() { + let db = Minigraf::in_memory().unwrap(); + for round in 0..4 { + write_round(&db, round); + assert!(check_all(&db) > 0, "the history answers some queries"); + } +} + +#[test] +fn engine_matches_executor_across_checkpoints_and_reopen() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("engine.graph"); + { + let db = Minigraf::open(&path).unwrap(); + for round in 0..4 { + write_round(&db, round); + // Pending facts on top of committed ones. + check_all(&db); + db.checkpoint().unwrap(); + // Committed facts only. + check_all(&db); + } + // Pending records that retract and re-window committed triples. + write_round(&db, 4); + check_all(&db); + } + let db = Minigraf::open(&path).unwrap(); + assert!( + check_all(&db) > 0, + "the reopened history answers some queries" + ); + db.checkpoint().unwrap(); + check_all(&db); +} + +/// Answers of more than one batch, read through the committed and pending +/// halves of a scan. +#[test] +fn engine_reads_many_batches() { + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("big.graph")).unwrap(); + let facts: String = (0..3000) + .map(|i| format!("[:e{i} :big/n {i}] [:e{i} :big/tag :t{}]", i % 7)) + .collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + db.checkpoint().unwrap(); + let more: String = (3000..4500) + .map(|i| format!("[:e{i} :big/n {i}]")) + .collect(); + db.execute(&format!("(transact [{more}])")).unwrap(); + db.execute("(retract [[:e5 :big/n 5] [:e3001 :big/n 3001]])") + .unwrap(); + assert_eq!( + rows(&db, "(query [:find ?e ?n :where [?e :big/n ?n]])"), + 4498 + ); + assert_eq!( + rows(&db, "(query [:find ?e ?a ?v :where [?e ?a ?v]])"), + 7498 + ); + assert_eq!(rows(&db, "(query [:find ?t :where [:e3 :big/tag ?t]])"), 1); + assert_eq!(rows(&db, "(query [:find ?e :where [?e :big/n 2999]])"), 1); +} + +/// The executor still runs what the engine does not: two patterns, rules, +/// aggregates, `:as-of` a timestamp. +#[test] +fn other_queries_stay_on_the_executor() { + let db = Minigraf::in_memory().unwrap(); + write_round(&db, 0); + for q in [ + "(query [:find ?e ?n :where [?e :person/name ?n] [?e :person/age ?a]])", + "(query [:find (count ?e) :where [?e :person/name ?n]])", + "(query [:find ?e :as-of \"2099-01-01T00:00:00Z\" :where [?e :person/name ?n]])", + "(query [:find ?v :where [?e :person/status ?v] [(= ?v :s1)]])", + "(query [:find ?e :where [?e :person/status :s1]])", + ] { + let before = runs(); + db.execute(q).unwrap(); + assert_eq!(runs(), before, "query stayed on the executor"); + } +} diff --git a/src/query/mod.rs b/src/query/mod.rs index c2a1cf2f4d..8114cf1749 100644 --- a/src/query/mod.rs +++ b/src/query/mod.rs @@ -1 +1,2 @@ pub mod datalog; +pub(crate) mod engine; diff --git a/src/storage/dict.rs b/src/storage/dict.rs index 594443fd77..97d1f5e131 100644 --- a/src/storage/dict.rs +++ b/src/storage/dict.rs @@ -214,7 +214,7 @@ impl<'a> DictReader<'a> { } /// The committed long value equal to `s`, if any (§6.3 dedup). - fn find_long_value(&mut self, s: &str) -> Result> { + pub fn find_long_value(&mut self, s: &str) -> Result> { if self.root == 0 { return Ok(None); } diff --git a/src/storage/keys.rs b/src/storage/keys.rs index 77e3ec0210..721f6d821e 100644 --- a/src/storage/keys.rs +++ b/src/storage/keys.rs @@ -614,6 +614,21 @@ pub fn attribute_prefix(a: u32) -> Vec { k } +/// Key prefix of every EAVT entry of `(e, a, v)`: the same bytes for every +/// record of one triple, whichever index it was read from. +pub fn entity_attribute_value_prefix(e: u64, a: u32, v: &KeyValue) -> Vec { + let mut k = entity_attribute_prefix(e, a); + put_value(&mut k, v); + k +} + +/// Key prefix of every AVET entry of attribute `a` with value `v` (#518). +pub fn attribute_value_prefix(a: u32, v: &KeyValue) -> Vec { + let mut k = attribute_prefix(a); + put_value(&mut k, v); + k +} + // ─── DICT keys (§5.2) ──────────────────────────────────────────────────────── pub const DICT_UUID_TO_EID: u8 = 0x01; diff --git a/src/storage/mod.rs b/src/storage/mod.rs index 46254bd893..6d4ccc3c7a 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -415,21 +415,57 @@ pub trait CommittedReader: Send + Sync { fn log_source(&self) -> Option<&dyn LogSource> { None } + + /// Key-level access for the query engine, if this reader has keys. + fn key_source(&self) -> Option<&dyn KeySource> { + None + } } -/// Key-level access to one committed generation, for the fact log (#430). +/// Key-level reads of one committed generation: the dictionary and the live +/// keys of each index (#473 spec §5, §6.1). /// -/// Implemented by [`reader::OnDiskReader`]. Only EAVT and AEVT are walked. -pub trait LogSource { - /// The `last_checkpointed_tx_count` of this generation: every committed - /// fact has a `tx_count` at or below it. - fn last_tx(&self) -> u64; +/// Implemented by [`reader::OnDiskReader`]. +pub trait KeySource: Send + Sync { + /// `(next_eid, next_iid)` of this generation: every DICT id is below them. + fn next_ids(&self) -> (u64, u32); /// The entity id of `entity`, if it has any committed fact. fn eid_of(&self, entity: &crate::graph::types::EntityId) -> Result>; /// The ident id of `ident`, if it is in the dictionary. fn iid_of(&self, ident: &str) -> Result>; + /// The entity with id `eid`. + fn uuid_of(&self, eid: u64) -> Result; /// The ident with id `iid`. fn ident_of(&self, iid: u32) -> Result; + /// The long string stored at `vref`. + fn long_value(&self, vref: keys::ValueRef) -> Result; + /// Where the long string `s` is stored, if a committed fact holds it. + fn long_value_ref(&self, s: &str) -> Result>; + /// The keys of `index` that start with `prefix` and survive net-assert at + /// `as_of`, decoded, appended to `out` in key order. + /// + /// Starts after the triple `resume` (from the start when `None`). Stops + /// at the first triple boundary once `max` keys are out, and returns the + /// last whole triple read, to resume after; `None` when the range is done. + /// A triple's decision therefore never spans two calls. + fn live_keys( + &self, + index: keys::Index, + prefix: &[u8], + resume: Option<&[u8]>, + as_of: Option, + max: usize, + out: &mut Vec, + ) -> Result>>; +} + +/// Key-level access to one committed generation, for the fact log (#430). +/// +/// Implemented by [`reader::OnDiskReader`]. Only EAVT and AEVT are walked. +pub trait LogSource: KeySource { + /// The `last_checkpointed_tx_count` of this generation: every committed + /// fact has a `tx_count` at or below it. + fn last_tx(&self) -> u64; /// Visit, in key order, the keys of `index` that start with `prefix` and /// sort after `after` (all of them when `None`), until `visit` returns false. fn walk( diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index 6a2e939d18..172dd3327e 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -2497,6 +2497,76 @@ mod tests { } } + /// The committed live read of `scan` taken by `live_keys` in calls of at + /// most `max` keys, resumed after each, equals one `live_facts` read: the + /// same records in the same order, for every `max`. + fn assert_live_keys_resume( + pfs: &PersistentFactStorage, + scans: &[crate::storage::Scan<'_>], + as_ofs: &[Option], + ) { + use crate::storage::Scan; + use crate::storage::keys::{self, Index}; + let snap = pfs.storage().snapshot().unwrap(); + let reader = snap.committed.as_ref().expect("a committed generation"); + let src = reader.key_source().expect("keys"); + for &scan in scans { + let (index, prefix) = match scan { + Scan::All => (Index::Eavt, Vec::new()), + Scan::Entity(e) => match src.eid_of(e).unwrap() { + Some(e) => (Index::Eavt, keys::entity_prefix(e)), + None => continue, + }, + Scan::EntityAttribute(e, a) => { + match (src.eid_of(e).unwrap(), src.iid_of(a).unwrap()) { + (Some(e), Some(a)) => (Index::Eavt, keys::entity_attribute_prefix(e, a)), + _ => continue, + } + } + Scan::Attribute(a) => match src.iid_of(a).unwrap() { + Some(a) => (Index::Aevt, keys::attribute_prefix(a)), + None => continue, + }, + }; + for &as_of in as_ofs { + let whole: Vec<_> = reader + .live_facts(scan, as_of) + .unwrap() + .into_iter() + .map(|f| (f.entity, f.attribute, f.tx_count, f.valid_from, f.valid_to)) + .collect(); + for max in [1, 2, 7, 1024] { + let mut got = Vec::new(); + let mut resume = None; + let mut calls = 0; + loop { + let mut out = Vec::new(); + resume = src + .live_keys(index, &prefix, resume.as_deref(), as_of, max, &mut out) + .unwrap(); + calls += 1; + for kf in out { + got.push(( + src.uuid_of(kf.e).unwrap(), + src.ident_of(kf.a).unwrap(), + kf.tx_count, + kf.vf, + kf.vt, + )); + } + if resume.is_none() { + break; + } + } + assert!(got == whole, "resumed live_keys equal one live read"); + if max == 1 && whole.len() > 2 { + assert!(calls > 1, "a small max splits the read"); + } + } + } + } + } + /// Random histories: assertions in several valid-time windows, retractions, /// re-assertions, several values per attribute, long values, many /// transactions per checkpoint. Live reads match net-assert over every @@ -2563,6 +2633,7 @@ mod tests { Some(now), ]; assert_live_reads_match(&pfs, &model, &scans, &as_ofs); + assert_live_keys_resume(&pfs, &scans, &as_ofs); } // Pending facts on top of committed ones. for _ in 0..12 { diff --git a/src/storage/reader.rs b/src/storage/reader.rs index e3f23974a1..3a87b72972 100644 --- a/src/storage/reader.rs +++ b/src/storage/reader.rs @@ -8,9 +8,9 @@ use crate::graph::types::{EntityId, Fact}; use crate::storage::btree::{LeafCursor, MutexStorageBackend, prefix_scan}; use crate::storage::cache::PageCache; use crate::storage::dict::{DictReader, SharedDictCache}; -use crate::storage::keys::{self, Index, KeyFact}; +use crate::storage::keys::{self, Index, KeyFact, ValueRef}; use crate::storage::meta::MetaPage; -use crate::storage::{CommittedReader, LogSource, Scan, StorageBackend}; +use crate::storage::{CommittedReader, KeySource, LogSource, Scan, StorageBackend}; use anyhow::Result; use std::sync::{Arc, Mutex}; @@ -20,7 +20,11 @@ pub struct OnDiskReader { cache: Arc, eavt_root: u64, aevt_root: u64, + avet_root: u64, + vaet_root: u64, dict_root: u64, + next_eid: u64, + next_iid: u32, last_tx: u64, shared: SharedDictCache, } @@ -32,7 +36,11 @@ impl OnDiskReader { cache, eavt_root: meta.eavt_root, aevt_root: meta.aevt_root, + avet_root: meta.avet_root, + vaet_root: meta.vaet_root, dict_root: meta.dict_root, + next_eid: meta.next_eid, + next_iid: meta.next_iid, last_tx: meta.last_checkpointed_tx_count, shared: SharedDictCache::default(), } @@ -62,7 +70,35 @@ impl OnDiskReader { impl OnDiskReader { /// Facts of `index` entries starting with `prefix` that survive net-assert - /// at `as_of`, decided on the key bytes (#379, spec §5.3). + /// at `as_of`, decided on the key bytes (#379, spec §5.3). Only kept + /// entries are decoded and translated through the dictionary. + fn live_scan( + &self, + index: Index, + root: u64, + prefix: &[u8], + as_of: Option, + dict: &mut DictReader<'_>, + ) -> Result> { + let mut out = Vec::new(); + self.live_walk(index, root, prefix, None, as_of, usize::MAX, &mut |k| { + out.push(dict.fact(&KeyFact::decode(index, k)?)?); + Ok(()) + })?; + Ok(out) + } + + fn root(&self, index: Index) -> u64 { + match index { + Index::Eavt => self.eavt_root, + Index::Aevt => self.aevt_root, + Index::Avet => self.avet_root, + Index::Vaet => self.vaet_root, + } + } + + /// Visit the keys of `index` entries starting with `prefix` that survive + /// net-assert at `as_of`, in key order, starting after the triple `resume`. /// /// The history of one triple is contiguous and newest first, so its first /// transaction at or before `as_of` decides it (#435): a transaction that @@ -72,22 +108,36 @@ impl OnDiskReader { /// over. Entries that are passed over are skipped one by one, and /// after [`SEEK_AFTER`] of them in one triple the cursor seeks past the run, /// so a long history costs O(log) page visits while a short one costs no - /// seek. Only kept entries are decoded and translated through the dictionary. - fn live_scan( + /// seek. + /// + /// Stops at the first triple boundary once `max` keys were visited and + /// returns the last whole triple, to resume after; `None` when the range + /// is done. + #[allow(clippy::too_many_arguments)] + fn live_walk( &self, index: Index, root: u64, prefix: &[u8], + resume: Option<&[u8]>, as_of: Option, - dict: &mut DictReader<'_>, - ) -> Result> { - let mut out = Vec::new(); + max: usize, + visit: &mut dyn FnMut(&[u8]) -> Result<()>, + ) -> Result>> { if root == 0 { - return Ok(out); + return Ok(None); } let mut cursor = LeafCursor::new(root, Some(prefix), &self.backend, &self.cache)?; + if let Some(after) = resume { + // Past every entry of the triple: `tx↓` starts below 0xFF, and the + // next triple differs from this one within its length. + let mut target = after.to_vec(); + target.push(0xFF); + cursor.seek(&target)?; + } let mut triple: Vec = Vec::new(); let mut group = TxGroup::default(); + let mut visited = 0usize; // Entries of the current triple are hidden from here on. let mut dead = false; let mut skipped = 0usize; @@ -103,7 +153,10 @@ impl OnDiskReader { let tx = r.tx_desc()?; let new_triple = key_triple != triple.as_slice(); if new_triple { - group.flush(index, dict, &mut out)?; + visited += group.flush(visit)?; + if visited >= max && !triple.is_empty() { + return Ok(Some(triple)); + } triple.clear(); triple.extend_from_slice(key_triple); dead = false; @@ -121,8 +174,8 @@ impl OnDiskReader { } } _ => { - group.flush(index, dict, &mut out)?; - return Ok(out); + group.flush(visit)?; + return Ok(None); } }; match step { @@ -143,7 +196,7 @@ impl OnDiskReader { if group.tx.is_some_and(|decided| decided != tx) { // The triple's newest transaction decided it; this // older entry and the rest of the triple are hidden. - group.flush(index, dict, &mut out)?; + visited += group.flush(visit)?; dead = true; skipped = 1; continue; @@ -181,26 +234,23 @@ struct TxGroup { } impl TxGroup { - /// Emit the group's assertions unless it holds a retraction, and reset it. - fn flush( - &mut self, - index: Index, - dict: &mut DictReader<'_>, - out: &mut Vec, - ) -> Result<()> { + /// Visit the group's assertions unless it holds a retraction, and reset + /// it. Returns the number visited. + fn flush(&mut self, visit: &mut dyn FnMut(&[u8]) -> Result<()>) -> Result { let group = std::mem::take(self); - if !group.retracted { - for key in group.assertions { - out.push(dict.fact(&KeyFact::decode(index, &key)?)?); - } + if group.retracted { + return Ok(0); } - Ok(()) + for key in &group.assertions { + visit(key)?; + } + Ok(group.assertions.len()) } } -impl LogSource for OnDiskReader { - fn last_tx(&self) -> u64 { - self.last_tx +impl KeySource for OnDiskReader { + fn next_ids(&self) -> (u64, u32) { + (self.next_eid, self.next_iid) } fn eid_of(&self, entity: &EntityId) -> Result> { @@ -211,10 +261,44 @@ impl LogSource for OnDiskReader { self.dict().iid_of(ident) } + fn uuid_of(&self, eid: u64) -> Result { + self.dict().uuid_of(eid) + } + fn ident_of(&self, iid: u32) -> Result { self.dict().name_of(iid) } + fn long_value(&self, vref: ValueRef) -> Result { + self.dict().long_value(vref) + } + + fn long_value_ref(&self, s: &str) -> Result> { + self.dict().find_long_value(s) + } + + fn live_keys( + &self, + index: Index, + prefix: &[u8], + resume: Option<&[u8]>, + as_of: Option, + max: usize, + out: &mut Vec, + ) -> Result>> { + let root = self.root(index); + self.live_walk(index, root, prefix, resume, as_of, max, &mut |k| { + out.push(KeyFact::decode(index, k)?); + Ok(()) + }) + } +} + +impl LogSource for OnDiskReader { + fn last_tx(&self) -> u64 { + self.last_tx + } + fn walk( &self, index: Index, @@ -261,6 +345,10 @@ impl CommittedReader for OnDiskReader { Some(self) } + fn key_source(&self) -> Option<&dyn KeySource> { + Some(self) + } + fn live_facts(&self, scan: Scan<'_>, as_of: Option) -> Result> { let mut dict = self.dict(); let (index, root, prefix) = match scan { From fe2ae864ab0894224cddb2a7908935bd3433cca7 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 14 Oct 2026 13:52:09 +0530 Subject: [PATCH 3/5] docs: engine module and test counts (#544) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- CLAUDE.md | 6 ++++-- README.md | 2 +- docs/TEST_COVERAGE.md | 3 ++- 3 files changed, 7 insertions(+), 4 deletions(-) diff --git a/CLAUDE.md b/CLAUDE.md index 6858540cd9..d063993ebd 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -118,7 +118,7 @@ cargo run < demos/demo_negation.txt - `btree.rs`: On-disk B+tree over byte keys (`build_btree`, `cow_insert`, `LeafCursor` with `seek`, `prefix_scan`, `get`, `MutexStorageBackend`) - `dict.rs`: `DictReader` (id ↔ UUID/ident, tx timestamps, long values) and `Encoder` (checkpoint-time id assignment and key building) - `value_pages.rs`: append-only value pages for strings over 64 bytes - - `reader.rs`: `OnDiskReader` — covering reads of committed facts (`CommittedReader`); `live_facts` decides net-assert on index keys (#379) + - `reader.rs`: `OnDiskReader` — covering reads of committed facts (`CommittedReader`, `KeySource`); `live_facts` and the resumable `live_keys` decide net-assert on index keys (#379) - `verify.rs`: integrity walk for `Minigraf::verify` (tree order, index digests, DICT, page accounting) and the source choice for `rebuild_indexes` (#373) - `meta.rs` / `page.rs` / `freelist.rs`: meta pages A/B, the common page header and allocator (skips quarantined ids), free-list chain - `pins.rs`: `Pins` / `GenerationPin` — generations held by open snapshots and the quarantine of pages checkpoints freed after them (#543) @@ -139,6 +139,8 @@ cargo run < demos/demo_negation.txt - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute` - `magic_sets.rs`: Magic-sets rewriting for demand-driven recursive rule evaluation (not applied to rules with `not`/`not-join`) +3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: one pattern, plain `:find` variables, today), `scan.rs` (one pattern over a committed key range via `CommittedReader::key_source`/`live_keys`, then the pending range by whole runs), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids), `project.rs` (ids → values for returned rows only), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every engine query also runs on the executor and must agree). `DatalogExecutor::execute_query` tries it first. + 4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396) 5. **`src/repl.rs`** — Interactive REPL; TTY-aware (suppresses prompts/banner for piped input) @@ -202,7 +204,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1473 tests** (1463 passing, 10 ignored; unit + integration + doc). +**1477 tests** (1467 passing, 10 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/README.md b/README.md index aff16e0ae2..6cab5daf35 100644 --- a/README.md +++ b/README.md @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1446 tests +cargo test # run 1477 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index f43bda86d8..584799f6d6 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-14 with `cargo test --quiet` -**Result**: 1,463 passing tests and 10 ignored tests (1,473 total) +**Result**: 1,467 passing tests and 10 ignored tests (1,477 total) This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). `tests/property_test.rs` writes random histories (batched transacts, retracts, write transactions, checkpoints) in memory and to a file, and compares random queries (one to three joined patterns, `not` or `not-join`, a comparison predicate, `:as-of`, `:valid-at` or `:any-valid-time`) with a reference evaluator, on the open file and after a reopen; a query error fails the test (#386). `tests/crash_kill_test.rs` kills a child process running a seeded workload (multi-valued batches, batched retracts, five checkpoint modes) at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries and `verify`, again after a second reopen and after a checkpoint plus reopen (#384). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Page-count tests (#497) check that a CRC-valid meta whose `page_count` is past the end of the file (one page past, 2^50, `u64::MAX`; with the other slot valid or damaged; with or without a WAL) and a file cut short by one page, three pages or down to three pages are `STG-044` at open, with the file unchanged and not grown, while a `page_count` exactly at the end opens; that a checkpoint whose pages did not all reach the backend fails with `INT-049` before writing its meta, and the file reopens at the previous generation; and that `verify` at a meta counting pages past the end reports `STG-044` without scanning to that count. Through `Minigraf` (`tests/integrity_test.rs`), a file truncated by one or three pages and a file whose meta was rewritten with `page_count` 2^50 and a valid CRC are `STG-044` read-write and read-only, with no WAL created and the file length unchanged. The `file_header` fuzz input from #497 is a corpus seed. A sub-page test (#506, `tests/integrity_test.rs`) checks that a file of 1 to 4,095 bytes is `STG-045` read-write and read-only, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes writes when it is a prefix of the first meta page or all zeros; a file-backend unit test checks that `partial_page` returns the bytes past the last whole page. The `corrupt_file` fuzzer no longer skips files under one page: they must fail to open or open empty, and the #506 input is a corpus seed. Damaged v7 fact page tests (#496) check that a page in the counted fact range whose type byte is anything but the fact-page type (zero, `0x01`, the v2.x B+tree types, `0xFF`, a zeroed page; first and last page) is `STG-014` rather than skipped, while a range derived from the first index root skips only v2.x B+tree pages; that opening such a v7 file read-write or read-only fails with `STG-014` and writes nothing; and, in `tests/migration_matrix_test.rs`, that the golden `v7_basic.graph` with page 1's type byte changed or page 1 overwritten with noise fails both opens with the file unchanged and no WAL created. Both inputs are `fact_page` corpus seeds. Merged from the v2.x line: `tests/edge_cases_test.rs` checks the same refusal and acceptance through `Minigraf::open` on a database checkpointed twice (#506). Torn-WAL-tail tests (#513) check that opening a WAL writer cuts off a partial last entry (cut in the checksum, the header or the payload) or an entry with a bad checksum and everything after it, then appends where replay reaches, and leaves an intact WAL byte for byte; that an append that fails part-way makes every later append `WAL-007` while a rejected oversize fact (`WAL-003`, nothing written) does not; through `Minigraf`, that the failed transaction is not applied, later `transact` and `commit` are `WAL-007`, and a `checkpoint()` makes writes work again; and, in `tests/wal_test.rs`, that a commit made after reopening a crash-left WAL with each kind of torn tail survives a second crash. The fault matrix (#390, `src/fault_matrix.rs`) drives a test-only fault plan through the real file backend, WAL and directory fsync: an EIO, a short or torn write (1, 40 and 4,095 bytes), a full disk that keeps failing every later write, a failed fsync, and a failed fsync that also loses the writes since the last good one ("fsyncgate"), each at every write or sync call of a transact, a transact that creates the WAL, an automatic checkpoint, `checkpoint()`, the close-time checkpoint and `rebuild_indexes()`, on a database committed over two checkpoints with multi-valued, retracted and long values and entries pending in the WAL. After each fault, the handle holds the old facts or those plus the whole transaction, never part of one; after a failed checkpoint another is `STG-046`; a later write succeeds or is `WAL-007`/`STG-046`; a kill and reopen gives exactly the handle's facts, plus the failed transaction whole or not at all, and `verify` finds nothing; and a commit after recovery survives another kill. Two more tests fill the disk halfway through a checkpoint (`STG-046`, reads unchanged, reopen intact), and fail the fsync after a checkpoint's meta write and then retry the checkpoint, crashing at each of its writes: the retry is refused and every reopen is intact (without the refusal, a reopen hits `STG-029`). Unit tests check the fault plan's counting, and that a `rebuild_indexes` refused with `STG-041` leaves the handle usable. Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `API-011` from `transact` and from `WriteTransaction::execute`, and a later statement's window committed when two statements of a `WriteTransaction` give one fact different windows. Window-validation tests (#436) check that `check_valid_windows` rejects an empty window, an inverted one, and a `:valid-to` at or before the transaction time when `:valid-from` is left out, but not retractions; that `execute` rejects each such `transact` (both bounds, equal bounds, `:valid-to` only, a per-fact bound inverting the transaction's window) with `API-019` without writing or taking a `tx_count`, in memory, checkpointed and after reopen; that `tx.execute()` rejects them and the transaction still commits its other statements; that `commit()` rejects a default `valid_from` that has passed the `:valid-to` by commit time; and that `FactStorage::transact_batch` takes no `tx_count` on rejection. Statement-order tests (#477, `tests/statement_order_test.rs`) run every mix of two statements on one fact inside a `WriteTransaction` (retract then assert, assert then retract, two retracts, two windows, after a committed assertion and on an empty database) and check that reads inside the transaction and the committed rows agree, in memory, checkpointed and after reopen; that other facts of an overridden statement survive; that the commit is one transaction without the overridden records; and that two windows in one statement are `API-011` from `tx.execute()` while the rest commits. A unit test checks the commit collapse keeps each fact's newest statement in order. A log-writer test checks that an inverted window is `API-019`, a second window of a fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction `API-020` in either order, each leaving the writer usable and the output exact, while duplicate retractions, identical repeats and the same fact in the next transaction are accepted. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011`, a retraction of an asserted fact in one transaction `API-020`, an empty window `API-019` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Query-validation tests (#406, #414) check that a plain `:find` variable or a window function's argument, `:partition-by` or `:order-by` variable that no `:where` clause binds (including `?_` wildcards) is `PRS-080` from both `execute()` and `prepare()`, naming the variable, while variables bound by a pattern, an attribute position, a rule call, an expression binding, an `or-join`, every branch of an `or`, a pseudo-attribute or a window spec are accepted, and bind slots are not mistaken for `:find` variables; and that an unknown aggregate is `QRY-010` and an unknown window function `QRY-011` on an empty database, when no row matches, when rows match, through a rule query and through a prepared query, while a registered UDF in either position returns an empty result on an empty database. Coverage-gate tests (#396) check that replay stops at a WAL entry whose first fact is longer than 10 MB or that claims more than 1M facts, that a WAL writer cannot be opened in a missing directory, and that a failed cut of a torn WAL tail fails the open and leaves the file as it was; that a short v7 page and a slot past the record count are `INT-024`; that a migration backup meta of another generation or file length is not used (`STG-032`, file unchanged), and a torn first meta with data in page 1 is `STG-032`, not a new file; that `save` with nothing pending writes nothing, `into_backend` saves pending facts, and `rebuild_indexes` with nothing checkpointed commits the pending facts; and that unsorted or repeated B+tree input and a stored key inserted with another value are `INT-049`, a tree pointer to a free-list page is `STG-013` from `get`, a leaf walk and a copy-on-write insert, and the read-only `MutexStorageBackend` refuses writes, syncs and close. A page-cache test holds two threads in the backend read so both miss the same page, and checks that both get the one cached copy; before it, that path ran only when the scheduler happened to race the threads, and the gate flapped. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 956 passing; ten that spawn threads or a child process are ignored on WASI. These are not counted above. A WAL test checks that a checkpoint with no facts to flush still removes a WAL whose entries are all already in the file, and the golden-corpus test now requires the WAL to be gone after a checkpoint for the `stale_wal` fixtures too (#457). A WAL test checks that closing a handle opened with `wal_checkpoint_threshold(usize::MAX)`, in both sync modes, leaves the `.graph` file byte for byte as it was and keeps the WAL, whose entries replay on the next open, and a unit test closes an in-memory handle under the same setting (#476). A recursive-rule test checks that a rule query on a database with more live facts than `max_results` returns its answer, with a bound and with a free first argument, and that a query deriving more facts than its `:max-results` is still `INT-020` (#528). A log-writer test runs the online backup from `docs/DURABILITY.md`: it copies a read-write handle with an uncheckpointed transaction through `fact_log` and `LogWriter` while another thread writes past the automatic checkpoint threshold, and checks that the copy verifies clean, holds exactly the records the log returned and the counter read after the log opened, and that every concurrent write reaches the source's file once the log is dropped (#398). @@ -14,6 +14,7 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value - **Multi-value and index-key correctness** (`tests/multi_value_test.rs`, 10 tests): same-transaction multi-valued facts surviving query-time dedup, retracting several values of one attribute in one call, valid-time stints (facts differing only in valid time), maximum-value-size boundaries, and format v8 index keys (value bytes + assert/retract flag) (#287, #371). - **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration (including v7→v8 index rebuild and v1–v6 rejection via `STG-028`), WAL replay, checksums, corruption handling, and fault injection. - **Reliability and concurrency**: concurrent reads and writes, rollback behavior, same-process handle exclusion, cross-process locking, PID namespaces, NFS and container lock behavior, SIGKILL recovery, and queries seeing each concurrent transaction whole and reading one state for all their patterns, including while a checkpoint runs (`tests/snapshot_atomicity_test.rs`, #554, #555, #558). Generation pins (#543): a pinned generation's pages are never written by later saves or index rebuilds and are reused once the pin is dropped (by page id, `storage::persistent_facts`, `storage::pins`, `storage::page`); fact logs stay correct while checkpoints, rebuilds and concurrent writers run, and see whole transactions only (`tests/fact_log_test.rs`). Query and prepared-query cursors keep their answer and their pages across writes, checkpoints and index rebuilds, and the file stops growing once they close (`tests/cursor_test.rs`); a snapshot leaves out facts appended after it on every scan (`graph::storage`); a crash at every write point of a save with a pinned generation loses no fact and no page, and the reopened database reuses the quarantined ids (`storage::persistent_facts`); the browser withholds free pages a pinned generation may read and releases them once out of force (`storage::pins::split_released`, and a `#[wasm_bindgen_test]` with an open `BrowserDb` cursor). +- **Streaming query engine** (#473, #544): every query the engine runs is also run by the existing executor under `cfg(test)` and the `test-oracle` feature, and the answers must agree (`query::engine::oracle`); CI runs the whole suite with the feature, so the model-based, property, golden-corpus and integration suites check the engine. `query::engine::tests` reaches every index choice, net-assert of pending records over committed ones, `:as-of`, valid time, long strings and reads of several batches, in memory, across checkpoints and after reopen, and checks which queries stay on the executor. Resumed `live_keys` reads equal one live read over random histories (`storage::persistent_facts`). - **Public diagnostics**: structured parser, query, storage, WAL, API, and internal error codes; the error-code registry is checked against [`ERROR_REFERENCE.md`](ERROR_REFERENCE.md). - **Compatibility and quality**: golden-file corpus of released file formats, cross-platform format compatibility, property-based tests, long-haul smoke coverage, a weekly soak at 10M facts with a 5-hour churn (#392), XTDB/Datomic semantic compatibility, grammar conformance, and rustdoc examples. From ef90b707a261155cfc47a7e6bb889dc1962699f4 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 14 Oct 2026 13:53:14 +0530 Subject: [PATCH 4/5] test(query): float constants stay on the executor (#544) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- src/query/engine/tests.rs | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 4b2f5e3a61..1fbffcf8ab 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -174,8 +174,8 @@ fn engine_reads_many_batches() { assert_eq!(rows(&db, "(query [:find ?e :where [?e :big/n 2999]])"), 1); } -/// The executor still runs what the engine does not: two patterns, rules, -/// aggregates, `:as-of` a timestamp. +/// The executor still runs what the engine does not: two patterns, +/// aggregates, `:as-of` a timestamp, expressions, keyword and float constants. #[test] fn other_queries_stay_on_the_executor() { let db = Minigraf::in_memory().unwrap(); @@ -186,6 +186,8 @@ fn other_queries_stay_on_the_executor() { "(query [:find ?e :as-of \"2099-01-01T00:00:00Z\" :where [?e :person/name ?n]])", "(query [:find ?v :where [?e :person/status ?v] [(= ?v :s1)]])", "(query [:find ?e :where [?e :person/status :s1]])", + // Floats match within an epsilon, not by key (PR 2). + "(query [:find ?e :where [?e :person/age 21.0]])", ] { let before = runs(); db.execute(q).unwrap(); From aa7e4429ae08f257fbbce8dc29cd29c0db5782fc Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Wed, 14 Oct 2026 14:12:19 +0530 Subject: [PATCH 5/5] docs: CHANGELOG for the engine's first PR (#544) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01HyLscCUuJ1GQpdAeX79EdR --- CHANGELOG.md | 1 + 1 file changed, 1 insertion(+) diff --git a/CHANGELOG.md b/CHANGELOG.md index fee97fd446..3965cb112f 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -55,6 +55,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Internal +- **Single-pattern queries run on a new streaming engine** (#473, part 2: #544, first PR). A query whose `:where` is one pattern and whose `:find` holds plain variables now runs on operators that read index keys in batches of 1,024 rows and turn ids into values only for the rows they return (#530, for these queries). A pattern with a constant attribute and value, `[?e :a C]`, reads the AVET range of `C` instead of every fact of the attribute (#518). Measured at 1M facts (#394 envelope, `[?e :name "…"]`): 344 ms → 20 µs and 142 → 3 MiB; an attribute scan of 166,666 rows 577 → 268 ms and 172 → 57 MiB; point and `:as-of` queries 10–30 % faster. Every other query, and reads inside a `WriteTransaction`, run on the existing executor as before. Results are unchanged: in tests, every query the engine runs is also run by the executor and the answers must agree, and CI runs the whole suite that way (`test-oracle` feature). - **Committed reads hide superseded history on index keys** (#379). A query's committed facts are now reduced to the ones that survive net-assert (each fact's assertion from its newest transaction, unless that transaction retracted it; #435) while walking the index keys, before any fact is built. Only surviving entries are decoded and translated through the dictionary. A transaction that retracted a triple hides everything older in it, and a long run of hidden entries is skipped with one `seek`. `:as-of N` point and attribute queries now take the same index path instead of reading every fact in the file. On a checkpointed file with 2,000 superseded values, a point query takes 1.03 ms instead of 4.61 ms, an attribute scan 1.24 ms instead of 5.87 ms, and an `:as-of` point query 23 µs instead of 5.6 ms (at depth 1). Results are unchanged: the executor still applies net-assert to committed and pending facts together, and a pending fact is always newer than a committed one. - **B+tree reads no longer follow leaf sibling links** (v8 storage format, PR 1 of 5; #374). Every index scan uses a cursor that walks down from the root and keeps the path, with a forward `seek` that climbs only as far as needed. This prepares for copy-on-write index pages, which cannot keep sibling links. The file format and query results are unchanged. Concurrent 100k-fact scans take 25–37 % less time and checkpointing after one fact at 10k facts 9 % less; single point lookups and attribute scans are 2–6 % slower (about 0.4 µs per lookup). A corrupted child pointer now fails with STG-013 (wrong page type) or INT-049 (cycle) instead of following a bad link.