adityamukho · Oct 20, 2026 · Oct 20, 2026 · Oct 20, 2026 · Oct 20, 2026
@@ -29,3 +29,21 @@ jobs:
         run: cargo test --lib size_per_fact_in_433_shape_1m -- --include-ignored --nocapture
         env:
           RUST_BACKTRACE: 1
+
+  # #548: a recursive rule deriving about 5M facts completes, and its peak
+  # RSS follows the derived relation.
+  recursive-acceptance:
+    name: Recursive rules at 5M derived facts
+    runs-on: ubuntu-latest
+    timeout-minutes: 45
+
+    steps:
+      - uses: actions/checkout@v4
+
+      - name: Install Rust stable
+        uses: dtolnay/rust-toolchain@stable
+
+      - name: Run the acceptance test
+        run: cargo test --profile bench --test recursive_acceptance_test -- --ignored --nocapture
+        env:
+          RUST_BACKTRACE: 1
@@ -97,7 +97,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - **`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 (`test-oracle`).
 - **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 (`test-oracle`).
 - **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 (`test-oracle`).
-- **Rule queries run on the streami
8000
ng 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 inside a write transaction, 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 at 100K facts, p50 and peak RSS): `recursive_ancestors` (`(boss :p<leaf> ?b)`, five ancestors through the magic-set rewrite) 2.72 s → 1.40 ms and 253 → 4 MiB. Other workloads unchanged. Results are unchanged (`test-oracle`).
+- **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 inside a write transaction, 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<leaf> ?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 (`test-oracle`).
 - **`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 (`test-oracle`).
 - **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.
@@ -115,6 +115,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - **Pseudo-attribute sources (#594).** `tests/pseudo_source_test.rs` covers the source rule (nearest earlier pattern in the text, two pseudo-attributes sharing one, every fact through `[?e ?a _]`, constants by entity id, `$slot`s by name), `PRS-081` for each shape with no source, reading the outer fact from `not`, `not-join` (listed and unlisted variable), `or` (never a sibling branch) and `or-join`, closed rule bodies, and `:db/valid-at`. Parser, optimizer and matcher unit tests cover the hidden variables, their placement and the join variables a crossed `not-join` gains. The plan-independence matrix gains the pseudo-attribute shapes.
 - **Answers that depend on the plan fail the tests (#596).** A test-only switch (`minigraf::__reorder`, `test-oracle` feature) turns off every place the native build reorders: the pattern selectivity sort, the `not`/`not-join` and `or`/`or-join` cost sorts and the `or` short-circuits (#250), and the engine's `HashJoin` build side. `tests/plan_independence_test.rs` runs a matrix of queries (joins, expressions, rules, `or`/`or-join`, `not`/`not-join`, keyword and ref, floats, long strings, aggregates, time travel), in memory and on file, through `execute` and a cursor, with the switch on and off, and requires the same rows. Under `test-oracle` the model-based (#385) and property (#386) tests also run every generated query with the switch off.
 - **Rule queries on the engine (#548).** `tests/recursive_engine_test.rs` (10 tests) runs rule queries in memory, on a file with pending facts and after a checkpoint, and under `test-oracle` against the executor: transitive closure (linear and non-linear), mutual recursion, strata whose `not` and `or` rules recurse, rules that read their stratum outside a top-level invocation, derived facts seen by every pattern, the identity of derived facts, `nil` metadata, heads, both `INT-020` limits, and rule queries with aggregates, `not-join`, `or` and windows. Every existing rule suite (`recursive_rules_test`, `negation_test`, `disjunction_test`, `magic_sets_test`, the model-based and property tests) now runs its rule queries on the engine with the oracle. Engine unit tests cover routing and derived rows read across batches.
+- **Recursive rules at 5M derived facts (#473 acceptance, #548).** `tests/recursive_acceptance_test.rs` (ignored; the nightly smoke workflow runs it) derives 4,882,500 `reach` facts in 62 rounds over a layered graph of 155,000 edges and checks that every one is returned and that the query's peak RSS stays under 256 bytes per derived fact (169 measured); the default `max_derived_facts` then stops the same rule with `INT-020`. The #394 envelope has a `recursive` shape: the whole transitive closure of `:manager`, with no constant, so no magic sets.
 - **Negation bodies in both forms (#546).** A second test-only switch (`minigraf::__subplans`, `test-oracle` feature) forces the engine's `not` / `not-join` bodies to run hashed or correlated. `tests/plan_independence_test.rs` runs every query with the body forms chosen, forced hashed and forced correlated, each with reordering on and off; its matrix gains negations over floats near zero, `0.0` and `-0.0`, keywords and refs of one entity, long strings, bodies reading an imported variable they do not bind, variable-free bodies and `:db/valid-at`. `tests/negation_equality_test.rs` checks the changed answers on every executor path, in memory and after a checkpoint. The property test's rerun also forces hashed bodies. Engine unit tests cover the form the planner picks, routing, multiplicity, failing expressions in bodies, and that a hashed body is read once and a correlated one probes once per row.
 - **Disjunctions (#546).** `tests/or_equality_test.rs` checks the changed `or` / `or-join` answers through `execute` and a cursor, in memory and after a checkpoint. `tests/plan_independence_test.rs` gains disjunctions (keywords meeting refs, floats near zero, long strings as keys, branches naming different outer variables or no join variable, a branch with `not`, an `or` with nothing before it, a cross product, `:db/valid-at` in a branch), run with branches chosen, forced hashed and forced correlated. The property test generates `or` and `or-join` over bound variables, with a reference evaluator that deduplicates the rows they keep. Engine unit tests run every disjunction shape with each branch form forced against the executor, and cover routing, the form the planner picks, `Distinct`, and that a hashed branch is read once.
 - **Aggregates and windows (#547).** `src/query/datalog/aggregate.rs` unit tests check every accumulator over every order of small inputs (exact float sums against hand-computed values, cancellation, subnormals, signed zeros, infinities and NaN, integer saturation, errors decided at the end) and that the value order is total. `tests/aggregate_window_rules_test.rs` checks the changed answers; `tests/plan_independence_test.rs` gains aggregate, window and mixed queries over ties, keywords and refs, and floats.

@@ -206,7 +206,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are
 
 ## Test Coverage
 
-**1701 tests** (1691 passing, 10 ignored; unit + integration + doc).
+**1702 tests** (1691 passing, 11 ignored; unit + integration + doc).
 See `docs/TEST_COVERAGE.md` for the full per-file breakdown.
 
 **Testing conventions** — see the Testing Conventions section below before writing any tests.

@@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit
 
 ```bash
 cargo run          # interactive Datalog REPL
-cargo test         # run 1701 tests
+cargo test         # run 1702 tests
 cargo run < demos/demo_recursive.txt   # recursive rules demo
 ```