diff --git a/CHANGELOG.md b/CHANGELOG.md index b4c5efab34..3ca142f693 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 1f955f5de0..cf73caa264 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/Cargo.toml b/Cargo.toml index 5fecd74145..ca540a6f11 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/ROADMAP.md b/ROADMAP.md index ca8672aa62..648ec55de6 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 5af10e26b9..6833fd4bb8 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 "