From de59fdf320240b5730229814a6d72dcc5e865b33 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 23 Oct 2026 18:23:44 +0530 Subject: [PATCH 1/4] =?UTF-8?q?docs(plan):=20#551=20PR=203=20=E2=80=94=20m?= =?UTF-8?q?easurement,=20acceptance=20and=20docs=20(steps=2022=E2=80=9326)?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_0169pNQsLcCEn48te9X9WuZW --- .../plans/2026-10-23-551-executor-removal.md | 89 ++++++++++++++++++- 1 file changed, 88 insertions(+), 1 deletion(-) diff --git a/docs/superpowers/plans/2026-10-23-551-executor-removal.md b/docs/superpowers/plans/2026-10-23-551-executor-removal.md index 471ddefab..468bd29ac 100644 --- a/docs/superpowers/plans/2026-10-23-551-executor-removal.md +++ b/docs/superpowers/plans/2026-10-23-551-executor-removal.md @@ -8,7 +8,7 @@ called "the spec" below. PRs target `v3`, merge commits. None uses a closing key |---|---|---| | 1 | 1–13: the engine runs every query (spec §3, §4) | `feat/551-engine-everywhere` | | 2 | 14–21: delete the executor's query path and the oracle, `test-hooks`, size gate (spec §5) | `feat/551-delete-executor` | -| 3 | measurement, acceptance, docs (spec §6, §7) | planned after PR 2 | +| 3 | 22–26: measurement, acceptance, docs (spec §6, §7) | `feat/551-measure-docs` | Each PR leaves `v3` with no unused code outside `cfg(test)` and the oracle's `cfg`, and updates the test counts. PR 1 changes `CLAUDE.md`'s module notes and the test counts only; `CHANGELOG.md` @@ -281,3 +281,90 @@ with `browser`, `wasm32-wasip1`) and leaves the suite passing with and without t `--features test-hooks`, the wasm targets and the coverage workflow's commands on the bench machine; the release binary's size and the deleted-test list (decision 13) in the PR description. `CHANGELOG.md`'s migration notes and the docs site stay for PR 3. + +## Decisions not fixed by the spec (PR 3) + +19. **Baseline build.** The A/B runs `1096e6a2` (`v3` before PR 1) against this branch. The + baseline gets this branch's `examples/perf_envelope.rs` (the new shapes of decision 20), as + earlier A/Bs added their shape to the base (`234cc3e`, `58c19dd`); nothing else changes on it. + The two builds run in parallel, each pinned to its own NUMA node (`numactl -N -m`), swapped + for the second round; 100K, 1M and 10M, with the default `--budget-secs` and `--cap-secs`. +20. **`:as-of` timestamp shapes (spec §6).** The envelope fixture's `tx_id`s rise with + `tx_count`, so it is the monotonic fixture. Two shapes are added: `as_of_ts` (the `as_of` + point query with `:as-of ""`) and `as_of_ts_scan` + (`[:find ?e ?a :as-of "<…>" :where [?e :age ?a]]`, rows checked). The non-monotonic fixture + is a copy of the 1M fixture rewritten with `LogWriter`: same records, each transaction's + `tx_id` taken from a fixed permutation of the source's `tx_id`s (so they fall and rise), built + by a new `perf_envelope` subcommand (`irregular `) at 1M only. Both shapes run on + both fixtures; the report adds the irregular fixture as a fourth column at 1M. The ISO time is + the `tx_id` of transaction `tx_half` in the fixture being measured, read at measure time with + `fact_log().tx_range(tx_half..=tx_half)` (the fixture metadata holds only `tx_half`, so cached + fixtures need no rebuild), and it names a time inside each fixture's history. +21. **Python round trip.** `minigraf-python`'s `v3` branch already has `bench/envelope.py` + (`db.query`, `next_batch(1000)`, `json.loads` per batch, one process per shape). The binding is + built with `maturin develop --release` against this branch through a Cargo `[patch]` on its + git dependency, without committing the patch; Python 3 on the bench machine. If the binding + does not build against `v3` today, the fix is a `minigraf-python` `v3` PR (pin bump), not this + PR. Measured on both builds: the 1M `attribute_scan` (166,666 rows) and `count_grouped`, + wall-time p50 and peak RSS, plus the full shape list at 1M on this branch only for the table. +22. **Acceptance mapping (spec §7).** Each #473 item and its test: + - large-state design: `docs/superpowers/specs/2026-10-11-streaming-engine-design.md` + (QRY-012 cap, pin + quarantine, a large transaction commits as a checkpoint); + - `count` over 10M facts in constant memory: no test today. A new ignored test in + `memory_limit_acceptance_test.rs`, `count_holds_no_rows`, runs + `[:find (count ?v) :where [?e ?a ?v]]` over 1M facts with `query_memory_limit` at 64 KiB + and gets the count: the meter bounds what the query holds whatever the fact count (#549), + so 1M is enough for the bound, and the envelope's 10M `count` row records the RSS; + - grouped `count` with 1M groups, and the cap: `grouped_count_1m_groups`; + - 5M derived facts and `max_derived_facts`: `recursive_acceptance_test::reach_5m`; + - closing a cursor after the first batch, with operator counters: + `cursor::tests::first_batch_then_close` (in memory and on a file) and + `tests/cursor_test.rs::close_after_first_batch`; + - 1M-fact `transact` holding one chunk: + `large_transaction_acceptance_test::one_million_fact_transact_holds_one_chunk`; + - Python round trip: decision 21, recorded in `docs/BENCHMARKS.md`; + - `tests/cursor_test.rs` unchanged: since #432 it gained tests (#543) and one test moved + from the deprecated `max_results` to `max_derived_facts` (#553), which the alias still + accepts; the PR states both. Binding suites: each binding's `v3` CI after its pin moves to + this PR's merge (post-merge step 26). + The `:limit` item stays open for #306. The #473 checklist is ticked with a link per item + after merge, by hand. +23. **CHANGELOG.** The eleven `Internal` entries "… run on the streaming engine" (#544 ×3, + #545 ×2, #546 ×2, #547 ×2, #548, #549 build side) become one `Added` entry, **"Every query runs on the streaming engine"** (#473, #551), that says what + a user sees (batches of 1,024, ids turned into values only for returned rows, bounded memory + per operator and `QRY-012`, cursors that stream, the executor and `PatternMatcher` gone) and + keeps each part's issue number and the figures that matter; the per-shape operator detail + moves to `docs/BENCHMARKS.md` and the docs site where it is not already there. #379 stays + its own entry. Three new `Breaking changes` entries for the answer changes: spec §4.1, §4.2 + and PR 1 deviation 4 (unknown predicate in a `not`/`not-join` body is `QRY-007` at open). + v2.x has no migration-notes section; the `Breaking changes` list is it. +24. **Docs site.** `content/architecture.md`: the module tree and the "Execute" step name the + engine as the only query path, `matcher.rs` goes, and the "Streaming engine" section's + "same rows as the executor" paragraph changes to the frozen answers, each under + `@since v3.0.0` with the v2.x text under `@until v3.0.0`. `content/datalog-reference.md` + gets the three answer changes where it documents `or`, `not` and predicates. A + `minigraf-docs` PR, merged after this one. +25. **Not in PR 3:** the v2.x-vs-v3 audit of the playground and docs queries (follow-up + `v3-followup-notes` item 2) runs after this PR merges, since it needs the final v3 answers; + it may add `Breaking changes` entries in its own PR. + +## PR 3 steps + +22. **Plan.** This section. +23. **Envelope shapes and the irregular fixture** (decision 20), with a test that the + `irregular` subcommand's copy has the source's facts and a falling `tx_id` (the example + builds under `cargo test --examples`). Then the measurements on the bench machine (decisions + 19, 21): results into `docs/BENCHMARKS.md`, a "Executor removal (#551)" subsection in the + envelope section (A/B table, `:as-of` timestamp table, notes), the "What is supported" and + the 10M rows of the first tables updated where the engine changed them, and the Python table + re-measured with a peak-RSS column per shape. Any shape more than 5% slower on the branch + than the baseline at any scale is investigated and reported before the PR. +24. **Acceptance test** `count_holds_no_rows` (decision 22), run with the others in + `memory_limit_acceptance_test.rs` on the bench machine; `smoke.yml` already runs the file. +25. **Docs:** `CHANGELOG.md` (decision 23), `ROADMAP.md` (#551 done, #473 open for #306), + `README.md` (any executor wording), `CLAUDE.md` and `docs/TEST_COVERAGE.md` counts; the + docs-site PR (decision 24). Full suite plain and with `--features test-hooks` on the bench + machine; Codex review. +26. **After merge** (by hand, not in the PR): #473 checklist ticked with links; #551 closed; + `minigraf-python` and the other bindings' `v3` pins moved to the merge, CI green (spec §7); + decision 25's audit. From fef18cf5977d40a6d254a5c0fc1f0839746f0586 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 23 Oct 2026 18:35:09 +0530 Subject: [PATCH 2/4] bench(envelope): :as-of time shapes and an -irregular fixture (#551) as_of_ts and as_of_ts_scan query :as-of the time of transaction tx_half. A scale -irregular measures a LogWriter copy of that fixture whose neighbouring transactions swap tx_ids, so times fall and rise and :as-of a time cannot become a counter bound. cargo test runs the example's test. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_0169pNQsLcCEn48te9X9WuZW --- Cargo.toml | 5 + examples/perf_envelope.rs | 231 +++++++++++++++++++++++++++++++++++--- 2 files changed, 220 insertions(+), 16 deletions(-) diff --git a/Cargo.toml b/Cargo.toml index 5fecd7414..ca540a6f1 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -81,6 +81,11 @@ uuid = { version = "1.0", features = ["v4", "js"] } name = "minigraf_bench" harness = false +# `cargo test` runs the envelope harness's unit tests (the -irregular fixture, #551). +[[example]] +name = "perf_envelope" +test = true + [features] default = [] # Deprecated, does nothing since v3.0.0: every build reorders query clauses diff --git a/examples/perf_envelope.rs b/examples/perf_envelope.rs index a68911356..e842caa8a 100644 --- a/examples/perf_envelope.rs +++ b/examples/perf_envelope.rs @@ -9,6 +9,12 @@ //! [--cap-secs 60] [--rebuild] //! ``` //! +//! A scale `-irregular` (such as `1m-irregular`) measures a copy of +//! that scale's fixture whose transaction times fall and rise (#551): the +//! same records rewritten with `LogWriter`, each pair of neighbouring +//! transactions swapping `tx_id`s, so `:as-of` with a timestamp cannot use +//! the transaction counter. +//! //! The `envelope` profile is `release` at opt-level 3, which is how an //! application's release build compiles the library; `release` itself (and //! `bench`, which inherits it) is tuned for the REPL binary's size. @@ -37,7 +43,7 @@ )] #[cfg(not(target_arch = "wasm32"))] -use minigraf::{Minigraf, OpenOptions}; +use minigraf::{FactFilter, LogWriter, Minigraf, OpenOptions}; #[cfg(not(target_arch = "wasm32"))] use serde_json::{Value as Json, json}; #[cfg(not(target_arch = "wasm32"))] @@ -70,6 +76,11 @@ fn main() -> anyhow::Result<()> { println!("{out}"); Ok(()) } + Some("__irregular") => { + let out = build_irregular(Path::new(&args[1]), Path::new(&args[2]))?; + println!("{out}"); + Ok(()) + } Some("__storage") => { let out = measure_storage(Path::new(&args[1]), Path::new(&args[2]))?; println!("{out}"); @@ -121,16 +132,36 @@ fn run(args: &[String]) -> anyhow::Result<()> { let mut results = Vec::new(); for label in &scales { - let n = parse_scale(label)?; - let fixture = dir.join(format!("fixture-v{FIXTURE_VERSION}-{label}.graph")); - let meta = fixture.with_extension("json"); - if rebuild || !fixture.exists() || !meta.exists() { - let _ = std::fs::remove_file(&fixture); - let _ = std::fs::remove_file(fixture.with_extension("graph.wal")); - eprintln!("perf_envelope: building {label} fixture ({n} facts)"); - let out = child(&exe, &["__build", path_str(&fixture), &n.to_string()])?; + let (base, irregular) = match label.strip_suffix("-irregular") { + Some(base) => (base, true), + None => (label.as_str(), false), + }; + let n = parse_scale(base)?; + let base_fixture = dir.join(format!("fixture-v{FIXTURE_VERSION}-{base}.graph")); + let meta = base_fixture.with_extension("json"); + if rebuild || !base_fixture.exists() || !meta.exists() { + let _ = std::fs::remove_file(&base_fixture); + let _ = std::fs::remove_file(base_fixture.with_extension("graph.wal")); + eprintln!("perf_envelope: building {base} fixture ({n} facts)"); + let out = child(&exe, &["__build", path_str(&base_fixture), &n.to_string()])?; std::fs::write(&meta, out.to_string())?; } + let fixture = if irregular { + let fixture = dir.join(format!("fixture-v{FIXTURE_VERSION}-{label}.graph")); + let meta = fixture.with_extension("json"); + if rebuild || !fixture.exists() || !meta.exists() { + let _ = std::fs::remove_file(&fixture); + eprintln!("perf_envelope: building {label} fixture"); + let out = child( + &exe, + &["__irregular", path_str(&base_fixture), path_str(&fixture)], + )?; + std::fs::write(&meta, out.to_string())?; + } + fixture + } else { + base_fixture + }; eprintln!("perf_envelope: measuring {label}"); let copy = dir.join(format!("measure-{label}.graph")); let storage = child(&exe, &["__storage", path_str(&fixture), path_str(©)]); @@ -139,7 +170,7 @@ fn run(args: &[String]) -> anyhow::Result<()> { let mut out = storage?; let meta = read_meta(&fixture)?; let mut queries = Vec::new(); - for (i, shape) in fixture_shapes(&meta).iter().enumerate() { + for (i, shape) in fixture_shapes(&fixture)?.iter().enumerate() { let q = child( &exe, &[ @@ -431,6 +462,54 @@ fn build(path: &Path, n: usize) -> anyhow::Result { })) } +/// Rewrites `src` into a new file at `dst` with `LogWriter`: the same records, +/// but each pair of neighbouring transactions swaps `tx_id`s, so the times +/// fall and rise. Returns `src`'s metadata with this file's size. +#[cfg(not(target_arch = "wasm32"))] +fn build_irregular(src: &Path, dst: &Path) -> anyhow::Result { + let start = Instant::now(); + let db = OpenOptions::new().read_only(true).path(src).open()?; + // tx_count -> tx_id, in tx_count order. + let mut txs: Vec<(u64, u64)> = Vec::new(); + let mut log = db.fact_log(&FactFilter::new())?; + while let Some(batch) = log.next_batch(10_000)? { + for r in batch { + if txs.last().is_none_or(|&(c, _)| c != r.tx_count) { + txs.push((r.tx_count, r.tx_id)); + } + } + } + let mut swapped = std::collections::HashMap::with_capacity(txs.len()); + for pair in txs.chunks(2) { + match pair { + [(a, ta), (b, tb)] => { + swapped.insert(*a, *tb); + swapped.insert(*b, *ta); + } + [(a, ta)] => { + swapped.insert(*a, *ta); + } + _ => unreachable!(), + } + } + let mut w = LogWriter::create(dst, OpenOptions::new())?; + let mut log = db.fact_log(&FactFilter::new())?; + while let Some(batch) = log.next_batch(10_000)? { + for mut r in batch { + r.tx_id = swapped[&r.tx_count]; + w.append(&r)?; + } + } + w.advance_tx_count(db.current_tx_count())?; + w.finish()?; + let mut meta = read_meta(src)?; + meta["irregular"] = json!(true); + meta["build_ms"] = json!(start.elapsed().as_secs_f64() * 1000.0); + meta["peak_rss_kb"] = json!(proc_status_kb("VmHWM")); + meta["file_bytes"] = json!(std::fs::metadata(dst)?.len()); + Ok(meta) +} + // ── Measure ─────────────────────────────────────────────────────────────────── #[cfg(not(target_arch = "wasm32"))] @@ -442,7 +521,7 @@ struct Shape { } #[cfg(not(target_arch = "wasm32"))] -fn shapes(e: usize, tx_half: u64, hot_tx_half: u64) -> Vec { +fn shapes(e: usize, tx_half: u64, tx_half_time: &str, hot_tx_half: u64) -> Vec { let m = e / 2; let leaf = e - 1; // :manager depth from :p{i} to :p0. @@ -555,6 +634,25 @@ fn shapes(e: usize, tx_half: u64, hot_tx_half: u64) -> Vec { query: format!("[:find ?a :as-of {tx_half} :where [:p{} :age ?a]]", m / 4), rows: 1, }, + // #551: `:as-of` with a time. On the fixture, transaction times rise + // with the counter, so the time becomes a counter bound; on an + // `-irregular` fixture they do not, and the read keeps the versions + // of the transactions at or before the time. + Shape { + name: "as_of_ts", + query: format!( + "[:find ?a :as-of \"{tx_half_time}\" :where [:p{} :age ?a]]", + m / 4 + ), + rows: 1, + }, + Shape { + name: "as_of_ts_scan", + query: format!("[:find ?e ?a :as-of \"{tx_half_time}\" :where [?e :age ?a]]"), + // Not checked: transactions sharing the millisecond of `tx_half` + // are included, and an -irregular fixture moves `tx_half`'s time. + rows: usize::MAX, + }, Shape { name: "valid_at", query: format!( @@ -602,12 +700,30 @@ fn read_meta(fixture: &Path) -> anyhow::Result { } #[cfg(not(target_arch = "wasm32"))] -fn fixture_shapes(meta: &Json) -> Vec { - shapes( +fn fixture_shapes(fixture: &Path) -> anyhow::Result> { + let meta = read_meta(fixture)?; + let tx_half = meta["tx_half"].as_u64().unwrap(); + Ok(shapes( meta["entities"].as_u64().unwrap() as usize, - meta["tx_half"].as_u64().unwrap(), + tx_half, + &tx_time(fixture, tx_half)?, meta["hot_tx_half"].as_u64().unwrap(), - ) + )) +} + +/// The time of transaction `tx_count` in `fixture`, as an ISO 8601 UTC string +/// with milliseconds. +#[cfg(not(target_arch = "wasm32"))] +fn tx_time(fixture: &Path, tx_count: u64) -> anyhow::Result { + let db = OpenOptions::new().read_only(true).path(fixture).open()?; + let mut log = db.fact_log(&FactFilter::new().tx_range(tx_count..=tx_count))?; + let rec = log + .next_batch(1)? + .and_then(|b| b.into_iter().next()) + .ok_or_else(|| anyhow::anyhow!("no transaction {tx_count}"))?; + let t = chrono::DateTime::from_timestamp_millis(i64::try_from(rec.tx_id)?) + .ok_or_else(|| anyhow::anyhow!("tx_id {} out of range", rec.tx_id))?; + Ok(t.format("%Y-%m-%dT%H:%M:%S%.3fZ").to_string()) } /// Open time and RSS after open, then checkpoint times, on a copy of the fixture. @@ -664,7 +780,7 @@ fn measure_query( budget_secs: u64, cap_secs: u64, ) -> anyhow::Result { - let shape = fixture_shapes(&read_meta(fixture)?).swap_remove(index); + let shape = fixture_shapes(fixture)?.swap_remove(index); // `recursive` derives about as many facts as the fixture holds. let db = OpenOptions::new() .read_only(true) @@ -786,3 +902,86 @@ fn proc_status_kb(field: &str) -> u64 { #[cfg(target_arch = "wasm32")] fn main() {} + +#[cfg(all(test, not(target_arch = "wasm32")))] +mod tests { + use super::*; + + fn records(path: &Path) -> Vec { + let db = OpenOptions::new() + .read_only(true) + .path(path) + .open() + .unwrap(); + let mut log = db.fact_log(&FactFilter::new()).unwrap(); + let mut out = Vec::new(); + while let Some(batch) = log.next_batch(1_000).unwrap() { + out.extend(batch); + } + out + } + + /// The `-irregular` copy holds the source's records with only their + /// `tx_id`s swapped pairwise, so its transaction times fall, and both + /// `:as-of` time shapes run on it. + #[test] + fn irregular_copy_keeps_records_and_falls() { + let dir = tempfile::tempdir().unwrap(); + let src = dir.path().join("fixture.graph"); + let dst = dir.path().join("fixture-irregular.graph"); + let meta = build(&src, 2 * FACTS_PER_ENTITY * BATCH_ENTITIES).unwrap(); + std::fs::write(src.with_extension("json"), meta.to_string()).unwrap(); + let out = build_irregular(&src, &dst).unwrap(); + std::fs::write(dst.with_extension("json"), out.to_string()).unwrap(); + + let (a, b) = (records(&src), records(&dst)); + assert_eq!(a.len(), b.len(), "same number of records"); + let strip = |r: &minigraf::FactRecord| { + let mut r = r.clone(); + r.tx_id = 0; + r + }; + assert!( + a.iter().zip(&b).all(|(x, y)| strip(x) == strip(y)), + "same records apart from tx_id" + ); + // One (tx_count, tx_id) per transaction, in tx_count order. + let txs = |rs: &[minigraf::FactRecord]| { + let mut t: Vec<(u64, u64)> = rs.iter().map(|r| (r.tx_count, r.tx_id)).collect(); + t.dedup(); + t + }; + let (src_txs, dst_txs) = (txs(&a), txs(&b)); + assert!( + dst_txs.windows(2).any(|w| w[1].1 < w[0].1), + "a transaction time falls" + ); + let times = |t: &[(u64, u64)]| { + let mut v: Vec = t.iter().map(|&(_, id)| id).collect(); + v.sort_unstable(); + v + }; + assert_eq!( + times(&src_txs), + times(&dst_txs), + "the same times, reassigned" + ); + + for fixture in [&src, &dst] { + let shapes = fixture_shapes(fixture).unwrap(); + let db = OpenOptions::new() + .read_only(true) + .path(fixture) + .open() + .unwrap(); + for name in ["as_of_ts", "as_of_ts_scan"] { + let shape = shapes.iter().find(|s| s.name == name).unwrap(); + let rows = drain(&db, &format!("(query {})", shape.query)).unwrap(); + assert!(rows >= 1, "{name} returns rows"); + if shape.rows != usize::MAX { + assert_eq!(rows, shape.rows, "{name} rows"); + } + } + } + } +} From 8a90ea3d8349d5440772a9ef2a6451f82f53183a Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 23 Oct 2026 18:43:14 +0530 Subject: [PATCH 3/4] test: count over every fact holds no rows (#473 acceptance, #551) count_holds_no_rows counts 1M facts under a 4 KiB query_memory_limit, so the meter bounds what an ungrouped count holds at any size. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_0169pNQsLcCEn48te9X9WuZW --- tests/memory_limit_acceptance_test.rs | 52 +++++++++++++++++++++++++-- 1 file changed, 50 insertions(+), 2 deletions(-) diff --git a/tests/memory_limit_acceptance_test.rs b/tests/memory_limit_acceptance_test.rs index c35bee530..17c3a615f 100644 --- a/tests/memory_limit_acceptance_test.rs +++ b/tests/memory_limit_acceptance_test.rs @@ -1,7 +1,8 @@ //! Acceptance tests for query memory accounting (#549 spec §6.2, and #575): //! a query whose state is large either completes or fails with `QRY-012` -//! under `OpenOptions::query_memory_limit`, and a cartesian product streams -//! instead of holding its rows. +//! under `OpenOptions::query_memory_limit`, a cartesian product streams +//! instead of holding its rows, and an ungrouped `count` holds no rows +//! (#473 acceptance, #551). //! //! Ignored by default; `.github/workflows/smoke.yml` runs them nightly, one //! at a time because the peak RSS is per process: @@ -29,6 +30,13 @@ const K: u32 = 13; /// than 5.7 GB at k = 13, #575); the engine holds a 3-row build side per join. const CARTESIAN_MAX_RSS: usize = 64 << 20; +/// What an ungrouped `count` over every fact may hold: one set of +/// accumulators. A query holding even one row id per fact would need +/// megabytes at 1M facts. +const COUNT_LIMIT: usize = 4 << 10; +/// Peak RSS the `count` may add: the reader's pages and one batch. +const COUNT_MAX_RSS: usize = 32 << 20; + /// `n` entities, each with its number as `:g`, checkpointed. fn groups_db(dir: &tempfile::TempDir, opts: OpenOptions) -> Minigraf { let db = opts.path(dir.path().join("groups.graph")).open().unwrap(); @@ -148,3 +156,43 @@ fn cartesian_k13_streams() { assert_eq!(err.code(), "QRY-012", "stopped by the limit"); assert!(err.to_string().contains("HashJoin"), "names HashJoin"); } + +/// `count` over every fact runs in memory that does not grow with the +/// facts: under a 4 KiB `query_memory_limit` it counts 1M facts, so the +/// meter (#549) bounds what it holds at any size. The envelope's `count` +/// shape records the RSS at 10M facts (`docs/BENCHMARKS.md`). +#[test] +#[ignore] +fn count_holds_no_rows() { + let query = "(query [:find (count ?v) :where [?e ?a ?v]])"; + let dir = tempfile::tempdir().unwrap(); + drop(groups_db(&dir, OpenOptions::new())); + let db = OpenOptions::new() + .query_memory_limit(COUNT_LIMIT) + .path(dir.path().join("groups.graph")) + .open() + .unwrap(); + let reset = std::fs::write("/proc/self/clear_refs", "5").is_ok(); + let before_kb = proc_status_kb("VmRSS"); + let start = std::time::Instant::now(); + let result = db.execute(query).unwrap(); + let peak_kb = proc_status_kb("VmHWM"); + let added = peak_kb.saturating_sub(before_kb) * 1024; + eprintln!( + "count_holds_no_rows: {:.2?}; peak RSS {} MiB, {} KiB added by the query", + start.elapsed(), + peak_kb / 1024, + added / 1024 + ); + let minigraf::QueryResult::QueryResults { results, .. } = result else { + panic!("expected query results"); + }; + assert_eq!(results.len(), 1, "one row"); + assert!( + matches!(results[0][0], minigraf::Value::Integer(n) if n == GROUPS as i64), + "counts every fact" + ); + if reset && peak_kb > 0 { + assert!(added < COUNT_MAX_RSS, "the count holds no rows"); + } +} From fe9badb93220a1155ad8280df50a5d6a9288aa29 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 24 Oct 2026 08:03:56 +0530 Subject: [PATCH 4/4] =?UTF-8?q?docs:=20#551=20PR=203=20=E2=80=94=20CHANGEL?= =?UTF-8?q?OG=20fold,=20ROADMAP,=20BENCHMARKS,=20test=20counts?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit One Added entry for the streaming engine replaces the per-PR Internal entries, with three Breaking changes for the answers that changed. docs/BENCHMARKS.md records the #551 A/B against 1096e6a2, the :as-of time shapes on a rising and an irregular fixture, and the Python round trip; every shape within 5% of the baseline except the point lookups, which #721 slowed and #726 restored to within 3%. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_0169pNQsLcCEn48te9X9WuZW --- CHANGELOG.md | 14 ++---- CLAUDE.md | 2 +- ROADMAP.md | 2 +- docs/BENCHMARKS.md | 108 ++++++++++++++++++++++++++++++++++-------- docs/TEST_COVERAGE.md | 16 ++++--- 5 files changed, 103 insertions(+), 39 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index b4c5efab3..3ca142f69 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -43,9 +43,12 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **One rule limit, `max_derived_facts`, on the total facts a rule query derives** (#553). `OpenOptions::max_derived_facts` and `:max-derived-facts` now limit every fact the rules of one query derive, across iterations and strata (the database's own facts do not count); they used to limit the new facts of one iteration. `OpenOptions::max_results` and `:max-results`, which already limited the total (#528), are deprecated aliases of it (`#[deprecated]` on the Rust field and builder method); the lower of the two applies, and a per-query value still replaces the database's. `OpenOptions::max_results` now defaults to no limit of its own, so it can lower the limit but not raise it: a caller who raised `max_results` above 1,000,000 must raise `max_derived_facts` instead. Neither ever limited the rows a query returns, whatever the name said; `:limit` (#306) will. A caller who lowered `max_derived_facts` to cap each iteration now caps the total, so a long recursion whose iterations each stayed under the limit can now fail with `INT-020`. The `INT-020` text now reads `evaluator: iteration or derived-fact limit exceeded: Max derived facts (N) exceeded. …`. The 1,000-iteration limit and the 1,000,000 default are unchanged. - **A rule head whose entity is not an entity fails with `QRY-013`** (#548). A rule head's first argument is the entity of the fact it derives and must be a ref or a keyword; a string, number, boolean or `nil` there now fails the query with the new code `QRY-013` (`rule head entity is not an entity: rule 'named' gives a String where a ref or a keyword is needed`). A positive rule used to fail with `INT-022`, and a rule with `not`, `not-join`, `or` or `or-join` silently dropped the row. A head variable the body does not bind now fails with `INT-022` on the `not`/`or` path too, which also dropped the row. - **A fact a rule derives has no metadata** (#548). `:db/valid-from`, `:db/valid-to`, `:db/tx-count` and `:db/tx-id` read from a derived fact (`(reach ?x ?y) [?x :reach ?y] [?x :db/tx-count ?c]`) now bind `nil`, and a constant (`[?x :db/tx-count 1]`) never matches one; a stored fact with the same attribute keeps its own. They used to bind the rule evaluator's working values: the time the query ran, forever, and a counter of its own. `:db/valid-at` still binds the query's valid time. +- **A `not` or nested `or` inside an `or` branch sees a variable an expression of the branch binds** (#551). The executor applied a branch's patterns, then its nested `or`s, then its `not`s, then its expressions, so a `not` or nested `or` reading a variable that only an expression of the branch binds saw it unbound. A branch now runs in the order a `:where` does (#625), and the `not` sees the binding. For example, over `[:x :n 1] [:y :n 2] [:z :n 5]`, `[:find ?e :where [?e :n ?v] (or-join [?e ?v] (and [(+ ?v 1) ?w] (not [?f :n ?w])) [?e :n 5])]` returned `:z` (the `not` matched any fact, so the first branch kept no row) and now returns `:y` and `:z`. Only such branches change. +- **An unknown predicate is an error when the query opens, wherever it is** (#551). Every predicate a query names, in an `or` branch (of the query or of a rule it evaluates) or a `not` / `not-join` body, is now looked up when the query opens, as top-level predicates and `:find` functions already were (#414): an unknown one fails with `QRY-007` whatever the data. Before, the executor looked it up only when a row reached it. In an `or` branch, a query whose rows never reached the predicate returned an answer, and now fails. In a `not` / `not-join` body the failure was swallowed: the body had no row, so the `not` kept every outer row and the query returned a wrong answer instead of an error. ### Added +- **Every query runs on a streaming engine** (#473: #544, #545, #546, #547, #548, #549, #551). The executor, which turned every live fact of each pattern's attribute into a `Fact` before matching, held each row's bindings in a map and copied the database into a `FactStorage` for every rule query, no longer runs queries: its query path, `PatternMatcher` and the old rule evaluators are gone (#551), and the release binary is 1,153 KiB instead of 1,286 KiB (CI's size check). A query is now a tree of operators that pass batches of up to 1,024 rows of ids, read from the index keys, and turn ids into values only for the rows they return (#530). A pattern reads the narrowest key range its constants allow (`[?e :a C]` reads the AVET range of `C`, #518); a later pattern is an `IndexNestedLoopJoin` when its entity is bound and a `HashJoin` otherwise, built on the side with the smaller estimate (with no shared variable, the smaller product, #575); per-fact pseudo-attributes read their source's metadata column (#594). `not` / `not-join` is an `AntiJoin` and `or` / `or-join` a `Union` and `Distinct`: a body or branch with the same rows for every outer row runs once into a hash table, any other runs per outer row from a one-row seed. Aggregates keep one entry per group (one set of accumulators when ungrouped), windows hold their rows, and rule queries derive each stratum's relations semi-naively, with the magic-set rewrite, then read them as patterns. `:as-of` with a time bounds the transaction counter when transaction times rise with it, and otherwise keeps the versions of transactions at or before the time. Cursors (`Minigraf::query`, `PreparedQuery::query`, `BrowserDb.query`) pull one batch at a time, and closing or dropping one stops the work; a cursor still answers from the database as it was when it opened. Every operator that keeps state counts it against `OpenOptions::query_memory_limit` (#549, below). Answers are the executor's, as a bag, except for the changes under Breaking changes: until #551 every query in the test suite was also run by the executor and the answers had to agree, and the answers of the suites that relied on that are recorded in `tests/answers/`. Measured with the #394 envelope at 1M facts, executor → engine, p50 and peak RSS (`docs/BENCHMARKS.md` has every shape at 100K, 1M and 10M): `[?e :name "…"]` 288 ms → 22 µs; an attribute scan of 166,666 rows drained with `next_batch(1000)` 58 → 7 MiB (458 → 7 MiB at 10M); `[:p :follows ?f] [?f :name ?n]` 796 ms → 50 µs; an entity-bound `not` 760 → 27 ms; `[:find (count ?v) :where [?e ?a ?v]]` 3.01 s → 457 ms and 728 → 7 MiB (6.6 GiB → 7 MiB at 10M); an `or-join` of two hashed branches 1.44 s → 80 ms; `(boss :p ?b)` 43.9 s → 2.14 ms and 2.6 GiB → 4 MiB; the whole transitive closure of `:manager` 51.0 s → 3.21 s and 4.7 GiB → 318 MiB; `:as-of` with a time, a point query, 1.65 s → 0.8 ms and 435 → 4 MiB (17.2 s and 3.6 GiB → 0.9 ms and 5 MiB at 10M). - **Transactions of any size on a file database, in bounded memory** (#473, part 8: #550). `transact` and `retract` are read one fact at a time: the whole command is never tokenized, parsed or materialised at once, and a statement reports the same error code as before whatever its size. A transaction becomes *large* when its facts would pass the new `OpenOptions::transaction_chunk_facts` (default 65,536, kept between 1 and 1,000,000): `Minigraf::execute` of a larger statement, or the `WriteTransaction` statement that takes its staged facts past it. A large transaction holds at most one chunk of facts in memory. It writes them a chunk at a time into copy-on-write trees that become the next generation, and commits as a checkpoint: no WAL entry, and the uncheckpointed facts of earlier transactions go into the same checkpoint. What a large transaction stores is what a small one stores, with two differences you can see: its `tx_id` is the time it became large, not its commit time (a default `:valid-from` takes that time too), and errors from different chunks of one statement come in chunk order. In a large `WriteTransaction` a rejected statement still leaves the transaction usable and the earlier statements' facts as they were; a fact too large to store is rejected at its statement (`WAL-003`) rather than at `commit`; a handle that has failed is refused when the transaction becomes large (`STG-046`) rather than at `commit`; and inside the transaction `:as-of` its own transaction number sees every finished statement, since they share one number (staged statements of a small transaction each have their own until `commit`). A crash at any point before a large transaction's commit leaves the database as it was; the WAL file exists, header only, from before its first page write, so a new file reopens too. The first checkpoint after a WAL is found at open, or after a large transaction is rolled back, now writes a meta page before it deletes the WAL. Measured at 1M facts against v3 before this change (one `execute`, or a `WriteTransaction` of 10 statements): peak memory above the input text goes from 1.3–2.4 GiB to at most 55 MiB at the default (under 10 MiB at 16,384); with sequential entities it is faster (3.9 s from 9.1 s for short values), with random entities about as fast for short values (9.5 s from 11.4 s in one `execute`) and slower for long ones over 10 statements (34 s from 22 s; 16,384 takes up to twice as long as the default with random entities), and a transaction of several statements over random entities can leave the file up to 1.8× larger, since each statement keeps the pages its base references until it ends; later checkpoints reuse that space. - **Queries inside a `WriteTransaction` read through a snapshot** (#550). They no longer copy every committed and pending fact into a new list: they read the committed indexes and the pending facts, with the transaction's staged facts read with the pending ones (or, in a large transaction, its working trees), and run on the streaming engine where it plans them, counted by `query_memory_limit`. - **Query memory accounting and `OpenOptions::query_memory_limit`** (#549). Every engine operator that keeps state counts an estimate of the bytes it holds, per entry, the same on every platform: a hash join's build side, a negation's or an `or`'s table, a distinct set, an aggregate's groups (`count-distinct` and `sum-distinct` members included), a window's rows, the facts a rule query derives and the stored facts it compares them with, and the query's entity and ident ids. Tables grow through `try_reserve`. The new `OpenOptions::query_memory_limit` (default `usize::MAX`, off) turns a query that would hold more into the new `QRY-012`, which frees what the query held and leaves the database and other queries as they were; through a cursor, the rows already returned stay returned. An allocation the allocator refuses is `QRY-012` too, in place of the abort. Rows passing between operators and the answer `execute` collects are not counted, nor are a write transaction's staged facts (at most one chunk, #550). @@ -98,17 +101,6 @@ 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 runs 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 ran the whole suite that way until the executor's query path was removed (#551). -- **Expressions and pseudo-attributes run on the streaming engine** (#473, part 2: #544, second PR). The engine now also runs expression clauses after its pattern (`[(> ?v 21)]`, `[(+ ?v 1) ?w]`, registered predicates), per-fact pseudo-attribute patterns on the pattern's entity (`:db/valid-from`, `:db/valid-to`, `:db/tx-count`, `:db/tx-id`), and keyword, UUID and float constants in the value position. A constant reads only the AVET ranges it can match: a keyword reads its own range and the range of refs to the entity it names, a UUID reads its ref range and the attribute's keywords, a float reads the attribute's floats. The executor's matching rules are kept (a keyword matches a ref to the entity it names, a UUID matches a keyword that names it, floats match within `f64::EPSILON`), and so are its errors (INT-026, QRY-007). `:db/valid-at`, which the executor matches against every fact of the entity, stays on the executor until joins (#545). -- **Cursors stream the queries the engine runs** (#473, part 2: #544, third PR). `Minigraf::query`, `PreparedQuery::query` and `BrowserDb.query` no longer compute the whole answer at open for these queries: the cursor pulls one batch of up to 1,024 rows from the engine's operators when it runs out of rows, and `close` or dropping it stops the work. An attribute scan drained with `next_batch(1000)` holds 7 MiB at 1M and 10M facts (was 58 and 458 MiB) and runs 3–17 % faster (#394 envelope). The answer is still the database as it was when the cursor opened, whatever is written or checkpointed while it is open. A read error that happens after some rows of a `next_batch` call were gathered is returned by the next call, after those rows. No API change. -- **Joins run on the streaming engine** (#473, part 3: #545, second PR). Queries of several patterns with stored attributes, with or without expression clauses, now run on the engine. Patterns run in the planner's order: the first is a scan, and each later one is an `IndexNestedLoopJoin` when its entity is a variable already bound (one entity range per row, committed and pending), or a `HashJoin` otherwise (value and attribute positions, cross products), built on the side with the smaller estimate. Joins follow the executor's rules (#545, first PR): floats are equal by IEEE `==`, a keyword equals a ref to the entity it names, and a variable keeps the value of its first pattern in the `:where` text. Measured at 1M facts (#394 envelope, p50 and peak RSS): `[:p :follows ?f] [?f :name ?n]` 796 ms → 50 µs and 322 → 4 MiB; `[:p :manager ?b] [?s :manager ?b] [?s :name ?n]` 1.67 s → 148 ms and 392–462 → 14 MiB; `[?e :follows ?f] [?f :group 7] [?f :name ?n]` 2.6 s → 1.1 s and 468–480 → 42 MiB. `or`, `not`, rules and aggregates still run on the executor. Results are unchanged (checked against the executor). -- **Pseudo-attributes across joins and `:db/valid-at` run on the streaming engine** (#473, part 3: #545, third PR). A per-fact pseudo-attribute pattern (`:db/valid-from`, `:db/valid-to`, `:db/tx-count`, `:db/tx-id`) reads the metadata of its source (#594, above): the source's scan or join fills a metadata column from the fact's key, and the pattern binds or checks against it. A `:db/valid-at` pattern joins with every visible fact of its entity, as `[e _ _]` would, with the query's valid time as a column. Measured at 10M facts (#394 envelope, p50 and peak RSS): `[:p :follows ?f] [?f :name ?n] [?f :db/tx-count ?t]` 34 s → 56 µs and 6.0–7.5 GiB → 4 MiB (3.2 s → 56 µs at 1M). Results are unchanged (checked against the executor). -- **`not` and `not-join` run on the streaming engine** (#473, part 4: #546, first PR). An `AntiJoin` keeps the outer rows for which the body has no row; it never deduplicates. A body that has the same rows for every outer row (its expressions and pseudo-attributes read only variables its own patterns bind) runs once, and its rows' values of the variables it shares with the outer row form a hash set. Any other body, and one whose first pattern's entity comes from the outer row, runs once per outer row from a one-row seed of the values it imports, stopping at its first row: an entity-bound body costs one index probe per row and holds nothing. Bodies are ordered with the imported variables counted as bound. Queries whose negation holds a rule invocation stay on the executor. Measured (#394 envelope, p50 and peak RSS): an entity-bound `not` (`[?e :group 7] (not [?e :age 7])`, run per row) 760 ms → 27 ms and 222 → 6 MiB at 1M facts, 8.7 s → 0.29 s and 1.2 GiB → 6 MiB at 10M; a `not-join` keyed on a value whose body has an expression (`(not-join [?a] [?f :group 17] [?f :age ?a] [(< ?a 50)])`, hashed) 1.29 s → 5.8 ms at 100K, over 60 s → 53 ms and 171 → 7 MiB at 1M, over 60 s → 0.57 s and 1.5 GiB → 9 MiB at 10M. Other workloads unchanged. Results are unchanged (checked against the executor). -- **Aggregates run on the streaming engine** (#473, part 5: #547, second PR). Queries with aggregates in `:find`, with or without `:with`, now run on the engine when their `:where` does. An `Aggregate` operator keeps one entry per group in a hash table, keyed on the grouping cells as groups compare values, and steps each aggregate as rows arrive: a query with no grouping variable holds one set of accumulators, whatever the input size. `count` reads only whether a cell is `nil` and `count-distinct` keeps the keys of its cells, so neither turns ids into values; other aggregates read values. When the input ends, the groups are sorted by their values, finished in that order and returned in batches. Measured (#394 envelope, p50 and peak RSS): `[:find (count ?v) :where [?e ?a ?v]]` 207 ms → 44 ms and 97 → 7 MiB at 100K facts, 3.01 s → 457 ms and 728 → 7 MiB at 1M, 29.6 s → 4.46 s and 6.6 GiB → 7 MiB at 10M; `[:find ?g (count ?e) :where [?e :group ?g]]` 31 → 5.9 ms at 100K, 397 → 61 ms and 97 → 7 MiB at 1M, 4.51 s → 614 ms and 901 → 7 MiB at 10M. Other workloads unchanged. Results are unchanged apart from the float group value above (checked against the executor). -- **Window functions run on the streaming engine** (#473, part 5: #547, third PR). Queries with window functions in `:find`, alone or over an aggregate's groups, now run on the engine when their `:where` does. A `Window` operator holds each input row's returned cells and the values of the variables the windows read, then computes every window with the code the executor runs (partitions, the sort, peers) and returns the rows in input order. Measured (#394 envelope, p50 and peak RSS): `[:find ?e (rank :over (:order-by ?a)) :where [?e :age ?a]]` 41.5 → 32.8 ms and 19 → 16 MiB at 100K facts, 601 → 434 ms and 140 → 109 MiB at 1M, 7.89 s → 5.65 s and 1,257 → 1,030 MiB at 10M. A window holds every row by nature, so memory still grows with the input. Other workloads unchanged. Results are unchanged (checked against the executor). -- **Rule queries run on the streaming engine** (#473, part 6: #548, second PR). A query that invokes a rule, at any depth, now runs on the engine when its body and the body of every rule it evaluates do. Each evaluated predicate has a relation: the facts its rules derive, held as rows of ids, a set (a fact derived twice, or equal to a stored fact, is kept once). `Recursive` derives the relations stratum by stratum before the body runs. Round 1 runs every rule over all facts; each later round runs a rule once per top-level invocation of its own stratum, that invocation reading only the facts the last round derived, so a fact is derived from new facts only (semi-naive). A rule that reads its own stratum otherwise (in an `or` branch, through a `[?x :p ?y]` or `[?x ?a ?v]` pattern, or `:db/valid-at`) runs over all facts every round. Scans read a relation's rows after the committed and pending facts, with `nil` metadata; entity probes use the relation's index. The query body is planned as any engine query, rule invocations read as patterns of their relations. The executor's `FactStorage` copy of the database for each rule query is gone on this path. Queries with an `:as-of` timestamp, or with a rule body the engine does not plan (an expression-only body, a nested `or`) stay on the executor. The binary-size gate on `v3` is 1,260 KiB until #551 removes the executor's query path (it was 1,230 KiB; this adds about 34 KiB). Measured (#394 envelope, executor → engine, p50 and peak RSS at 100K / 1M / 10M facts; `docs/BENCHMARKS.md`): `recursive_ancestors` (`(boss :p ?b)`, 5–7 ancestors through the magic-set rewrite) 2.71 s → 1.45 ms, 43.9 s → 2.14 ms, over 60 s → 3.04 ms, at 4 MiB instead of 253 MiB, 2.6 GiB and over 8.8 GiB; the whole transitive closure (`[:find ?x ?b :where (boss ?x ?b)]`, 72K, 889K and 10.6M derived facts) 3.04 s → 211 ms, 51.0 s → 3.21 s, over 60 s → 53.8 s, and 484 MiB → 45 MiB, 4.7 GiB → 318 MiB, over 8.8 GiB → 2.5 GiB. Other workloads unchanged. Results are unchanged (checked against the executor). -- **`or` and `or-join` run on the streaming engine** (#473, part 4: #546, second PR). A `Union` extends each outer row by every row of every branch; a `Distinct` then keeps one of each set of equal rows, comparing values as the executor does (`0.0` equals `-0.0`, a keyword never equals a ref, a row holding NaN is never a duplicate). Each branch is planned as a `not` body is: a branch with the same rows for every outer row runs once, into a table of its rows by their values of the variables it shares with the outer row; any other branch, and one whose first pattern's entity comes from the outer row, runs per outer row from a one-row seed. When the branches bind no new variable (every `or-join`, and an `or` that only filters), an outer row is returned once, from the first branch that has a row. A query whose first clause to run is an `or` starts from the empty row. These stay on the executor: a branch with a rule invocation, a nested `or`, or a predicate the function registry may not have; an `or` whose branches bind their own patterns' metadata; and a branch whose `not` reads a variable only the branch's expression binds. Measured (#394 envelope, p50 and peak RSS): an `or-join` of two branches keyed on a value (`[?e :group 7] [?e :age ?a] (or-join [?a] (and [?f :group 17] [?f :age ?a] [(< ?a 30)]) (and [?g :group 27] [?g :age ?a] [(> ?a 60)]))`, both hashed) 111 ms → 8.3 ms at 100K facts, 1.44 s → 80 ms and 306 → 7 MiB at 1M, 17.1 s → 0.86 s and 1.9 GiB → 12 MiB at 10M. Other workloads unchanged. Results are unchanged (checked against the executor). -- **A join with no shared variable builds on the side with the smaller product estimate** (#473, part 7: #549; #575). A `HashJoin` with no join key holds one side in full, and the planner compared the inner pattern with the outer side's cheapest pattern, so a chain of patterns sharing no variable built every later join on the growing outer side (3^(k−1) rows at the k-th join of the #575 fuzz shape). It now compares the inner pattern with the product of the outer patterns' estimates, so such a chain builds on each 3-row inner pattern. Answers do not change; joins with a key are planned as before. - **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. diff --git a/CLAUDE.md b/CLAUDE.md index 1f955f5de..cf73caa26 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -212,7 +212,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1714 tests** (1702 passing, 12 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). +**1716 tests** (1703 passing, 13 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). 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/ROADMAP.md b/ROADMAP.md index ca8672aa6..648ec55de 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -93,7 +93,7 @@ Scope — format and storage integrity: Scope — query API: -- Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`). The binding cursor objects follow. Behind the cursor, the streaming engine (#473) produces rows as they are pulled for the queries it runs (one pattern with expressions and pseudo-attributes, #544; joins of patterns, expressions and pseudo-attributes, `:db/valid-at`, #545); negation, aggregates, rules and transaction reads move to it in #546–#551, without API changes. Operators do not spill: memory follows operator state, with an opt-in per-query limit (`QRY-012`, #549). +- Cursor API: `Minigraf::query` and `PreparedQuery::query` return an owned `Cursor` that delivers rows in batches, with the answer fixed at open (#432; Rust API done on `v3`). The binding cursor objects follow. Behind the cursor, the streaming engine (#473) runs every query and produces rows as they are pulled: patterns, expressions and pseudo-attributes (#544), joins and `:db/valid-at` (#545), `not` and `or` (#546), aggregates and windows (#547), rules (#548), and transaction reads (#550); the executor's query path is gone (#551; done on `v3`). `:limit` (#306) is the one #473 acceptance item left, in v3.next. Operators do not spill: memory follows operator state, with an opt-in per-query limit (`QRY-012`, #549). - Fact-log iterator: `Minigraf::fact_log(&FactFilter)` streams every fact version (assertions and retractions, with `tx_count`, `tx_id` and valid-time bounds) in transaction order or storage order, filtered by attribute, attribute prefix, entity and tx range, with memory bounded by a window rather than the database (#430; Rust API done on `v3`). An open log pins its generation: checkpoints run but do not reuse its pages (#543; `API-013` deprecated). A raw log writer (#431) completes the extract-transform-load path; the binding objects follow with #462. - Read-only open: `OpenOptions::read_only` takes a shared lock, so several readers can hold a file at once, writes nothing to the file or its WAL (a WAL is applied in memory, a v7 file is read without migrating), and refuses writes with `API-014` (#429; Rust API done on `v3`). The bindings' `open_with_options` follows. - Raw log writer: `LogWriter` builds a new database from `FactRecord`s with their `tx_count`, `tx_id`, valid-time windows and assertion flags kept, gaps allowed (a purged transaction stays a hole for `:as-of`), at `.partial` renamed into place by `finish` (#431; Rust API done on `v3`). Completes extract (#429, #430), transform, load. The binding objects follow. diff --git a/docs/BENCHMARKS.md b/docs/BENCHMARKS.md index 5af10e26b..6833fd4bb 100644 --- a/docs/BENCHMARKS.md +++ b/docs/BENCHMARKS.md @@ -10,19 +10,24 @@ This section lists the graph sizes and query shapes that are tested, with their ### What is supported +Every query runs on the streaming engine since #551. The figures in this table are from the #551 A/B on an idle server (below); the storage and latency tables after it are the laptop run of 2026-10-11, before the engine. + | Workload | Tested up to | p50 / p99 at 10M facts | Notes | |---|---:|---:|---| -| Point lookup: bound entity and attribute, including `:as-of` and `:valid-at` | 10M facts | 12–14 µs / 20–48 µs | Flat from 100K to 10M | -| Entity with a long history (1,000 versions), current and `:as-of` | 10M facts | 0.26 ms / 0.30 ms | Grows with that entity's history, not the graph | -| Open a checkpointed file | 10M facts | 0.12 ms, 3 MiB RSS | Indexes are paged in on demand | -| Checkpoint after 1 new fact | 10M facts | 3.8 ms / 21 ms | Copy-on-write: cost follows the change | -| Attribute scan, attribute + value, grouped aggregation, joins | 1M facts | see below | Linear in the facts of the attributes they touch: about 0.1–0.5 s at 1M facts, seconds at 10M | -| Rule queries (recursion) | 10M facts | see below | On the streaming engine (#548): a rule with a constant (magic sets) takes 1.5–3 ms; a whole transitive closure grows with the facts it derives, about 3–5 µs and 250 bytes of RSS per derived fact | +| Point lookup: bound entity and attribute, including `:as-of` a counter and `:valid-at` | 10M facts | 18–20 µs / 22–27 µs | Flat from 100K to 10M | +| Point lookup `:as-of` a time | 10M facts | 0.92 ms / 0.93–0.96 ms | Resolving the time reads the DICT's transactions: 0.7 ms at 100K | +| Entity with a long history (1,000 versions), current and `:as-of` | 10M facts | 0.29–0.30 ms / 0.32–0.37 ms | Grows with that entity's history, not the graph | +| Attribute + value, joins that probe by entity or value | 10M facts | 17 µs–0.2 ms | `attribute_value`, `join_2`, `join_3_selective` | +| Open a checkpointed file | 10M facts | 0.13–0.23 ms, 3 MiB RSS | Indexes are paged in on demand | +| Checkpoint after 1 new fact | 10M facts | 1.1–1.5 ms / 2.2–2.9 ms | Copy-on-write: cost follows the change | +| Attribute scan, aggregates, `not`, `or`, joins that scan | 10M facts | see below | Linear in the facts they read, in bounded memory: 0.3–0.9 s for `not`/`or`/`count_grouped`, 2.5 s for a 1.67M-row scan in 7 MiB, 13 s for `join_3_scan` in 62 MiB | +| Rule queries (recursion) | 10M facts | see below | A rule with a constant (magic sets) takes 1.9 ms; a whole transitive closure grows with the facts it derives, about 5 µs and 250 bytes of RSS per derived fact | +| Window functions | 10M facts | 5.9–6.0 s | A window holds its whole input: 0.9 GiB for 1.67M rows | **Not supported yet:** - Graphs over 10M facts are not tested. -- Interactive latency for scans and joins at 10M facts. They take 3–21 s and materialize every fact of the attributes they touch, 0.7–3.6 GiB of RSS. +- Interactive latency for queries that read a whole attribute at 10M facts: 0.3–14 s. Their memory is bounded per operator, except windows and rule relations, which hold their rows; `OpenOptions::query_memory_limit` stops a query that passes it with `QRY-012` (#549). ### Storage @@ -54,7 +59,7 @@ This section lists the graph sizes and query shapes that are tested, with their | `join_3_scan` | `[?e :follows ?f] [?f :group 7] [?f :name ?n]` | 150 ms / 155 ms | 1.92 s / 1.96 s | 20.9 s / 21.2 s | | `recursive_ancestors` | `(boss :p{leaf} ?b)` over `:manager` (5–7 rows) | 2.71 s / 2.72 s | 40.1 s / 40.8 s | > 60 s (abandoned) | -`recursive_ancestors` at 1M was measured after the #528 fix, on the same machine and fixture. Below 100 runs, p99 is the slowest run. Shapes slower than about 75 ms ran fewer than 200 times; the full JSON report has run counts. +These are the executor's figures, before the streaming engine; the engine's are in the sections below, and every shape on today's code in [Executor removal (#551)](#executor-removal-551). `recursive_ancestors` at 1M was measured after the #528 fix, on the same machine and fixture. Below 100 runs, p99 is the slowest run. Shapes slower than about 75 ms ran fewer than 200 times; the full JSON report has run counts. Peak RSS per shape, each in its own process (baseline 4 MiB): @@ -77,7 +82,7 @@ The harness builds with `--profile envelope`: `release` at opt-level 3, which is ### Where the time goes (1M facts) -`perf` with frame pointers on `attribute_scan` and `join_3_selective`: +On the executor, before #544 (the executor's query path is gone since #551). `perf` with frame pointers on `attribute_scan` and `join_3_selective`: - **Up-front materialization (50–60%).** Before matching, the executor turns every live fact of each pattern's attribute into a `Fact` (`selective_fact_fetch` → `live_scan`). A pattern without a bound entity is read in full, so a selective join costs as much as scanning its widest attribute. The streaming engine (#473: `Scan` and `IndexNestedLoopJoin` operators) replaces this. - **DICT lookup per row (26–35%).** `uuid_of` does a B+tree `get` for every row's entity id (#530). @@ -184,19 +189,84 @@ The meter's estimate is within the spec's factor of two of the RSS a query adds Measuring this found that `Aggregate` built its sorted map of groups uncharged while its hash table was still alive: the meter read 282 MiB against 651 MiB of RSS. The map is now charged, and the table goes first, which also cut the real peak to the figure above. -### Python FFI round trip +### Executor removal (#551) -**Command**: `python bench/envelope.py --report envelope.json --scale ` in [minigraf-python](https://github.com/project-minigraf/minigraf-python) (`v3`), on the same fixtures and report. The binding is built with `maturin develop --release` against this commit. It runs the same queries through `db.query(...)`, drains them with `next_batch(1000)`, and decodes each JSON batch with `json.loads`. Python 3.14.7. +Since #551 every query runs on the engine and the executor's query path is gone. Before it, the queries the engine could not plan ran on the executor, which reads every fact of the patterns' attributes into memory; the envelope's case is `:as-of` with a time. `as_of_ts` is the `as_of` point query with `:as-of "