adityamukho · Oct 23, 2026 · Oct 23, 2026 · Oct 23, 2026 · Oct 23, 2026 · Oct 23, 2026
@@ -61,6 +61,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - **A float constant in a pattern matches equal floats only** (#706). A float written in a pattern's value position, or bound to a `$slot` of a prepared query, matched every stored float within an absolute `f64::EPSILON` (about `2.2e-16`), so `[?e :m/x 0.0]` returned an entity whose `:m/x` is `1e-17`, while `[?e :m/x ?v] [(= ?v 0.0)]` did not. Above 1.0 the epsilon is smaller than the gap between adjacent floats, so only floats smaller than about `2.2e-16` in magnitude were affected: every one of them matched `0.0`, and `1e-20` matched `5e-20`. Float constants now compare by IEEE `==`, as joins, predicates and the indexes do: `0.0` matches `-0.0` and nothing else changes. The fix covers patterns in queries, rule bodies and `not` / `or` bodies, on the executor and the streaming engine. Nothing stored was wrong. The same fix ships in v2.0.10.
 - **WAL entries of more than 1,000,000 facts replay** (#686). A WAL entry of more than 1,000,000 facts was taken as damage: replay stopped there, and the next open cut the WAL off at that entry, so after a crash, kill or close without a checkpoint that transaction and every later one in the WAL were lost, though each had committed. The writer had no such limit. Since #550 no v3 transaction writes such an entry, but a WAL left by v2.x can hold one. Replay now takes an entry's fact count as damage only when the bytes after it cannot hold that many facts. Affected every release since v0.5.0. Also fixed in v2.0.10.
 - **A recursive rule query no longer joins a rule's new facts with every magic-set fact** (#694). On the engine (#548), each round after the first runs a recursive rule from the facts the last round derived, then joins the rest of its body. The rest kept the order the planner chose for the whole body, so the next clause could share no variable with the new facts: after the magic-set rewrite of `(reach :n0 ?to)`, the body `(magic ?from) [?from :next ?mid] (reach ?mid ?to)` joined each new `reach` fact with every `magic` fact, then probed `:next` once per pair. The rest of the body is now planned with the new facts' variables bound, each next pattern sharing a variable with those bound before it when one can. Answers are unchanged. Nightly `recursion` benchmarks (bench profile): `fanout/w10_d3` 4.94 s → 22.6 ms (it was about 94 ms on the executor before #548), `chain/depth_100` 699 ms → 41.5 ms, `chain/depth_10` 1.15 ms → 0.68 ms.
+- **A join on a bound value probes the index instead of reading the whole attribute** (#721). #694's fix ordered a recursive rule's delta run so that the next pattern shares a variable with the new facts, but when that variable is the pattern's value (`[?x :manager ?y]` after the delta `(boss ?y ?z)`) the join was a `HashJoin` holding every `:manager` fact, rebuilt every round: `(boss :leaf ?b)` over a management tree took 1.8 s at 1M facts and 35 s at 10M instead of 2–3 ms. Such a join, on a constant attribute, is now an `IndexNestedLoopJoin` on the value: per row, the AVET ranges of the values that join-equal it (a keyword and a ref to the entity it names, either way; `0.0` and `-0.0`) and the attribute's uncheckpointed facts with those values, read once per query. A keyword's entity is a hash of its name, so a row whose value is an entity finds the keyword that names it only where the query made the entity from that keyword (a rule head, or a keyword its rule calls name); otherwise, on an attribute with keyword values, the join becomes the hash join it was before. Answers are unchanged. Measured with the #394 envelope (bench machine, p50 and peak RSS at 100K / 1M / 10M facts): `recursive_ancestors` 100 ms / 1.80 s / 35.0 s → 1.1 / 1.4 / 1.9 ms, 610 MiB → 4 MiB at 10M; `join_3_selective` (`[:p :manager ?b] [?s :manager ?b] [?s :name ?n]`) 10.4 ms / 144 ms / 2.36 s → 0.21 / 0.20 / 0.20 ms; other shapes unchanged. Nightly `recursion` benchmarks (in memory, bench profile): the new `ancestors/w10_d4` 97.7 → 15.1 ms, `chain/depth_100` 41.4 → 20.8 ms, `fanout/w10_d3` 22.7 → 20.8 ms. In memory every fact is uncheckpointed, and the first value probe reads the attribute's uncheckpointed facts once per query (12 ms for 11,110 facts), so `ancestors` stays above its 0.27 ms before #694.
 - **`BrowserDb` errors carry their error code** (#673). The browser API (`@minigraf/browser`) rejected with the error's top-level message only, such as `Unknown command: nosuchcommand`, while every other API reports `[PRS-001] Unknown command: nosuchcommand`. Every `BrowserDb` rejection now goes through `MinigrafError`, so it starts with its code. Host errors that have no code yet (no IndexedDB, an import blob whose length is not a multiple of the page size) are unchanged.
 - **Prepared queries use the database's rule limit** (#549). `PreparedQuery::execute` and `query` ran a rule query with the default `max_derived_facts` of 1,000,000 whatever `OpenOptions` set; they now use the database's limit, as `execute` does, and its `query_memory_limit`.
 - **An `or` branch in a rule body knows the registered predicates** (#548). A rule with `or`/`or-join` evaluated its branches with the built-in functions only, so a predicate registered with `register_predicate` in a branch (`(or [(big? ?v)] [?x :special true])`) was unknown there. Branches now get the database's functions, as the rest of the rule body does.

@@ -147,7 +147,7 @@ cargo run < demos/demo_negation.txt
    - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute`
    - `magic_sets.rs`: Magic-sets rewriting for demand-driven recursive rule evaluation (not applied to rules with `not`/`not-join`)
 
-3a. **`src/query/engine/`** — Streaming query engine (#473), runs every query (#551): `plan.rs` (the operator tree of every query, or the executor's error code for it: patterns, expression clauses, `not`/`not-join` and `or`/`or-join`, and rule invocations, read as patterns of their relations (`plan_rules`, #548; a magic-set head constant is `HeadArg::Const`), in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; an `or` branch or a `not` body is planned as a `:where` is; a clause list with no pattern first starts from `Seed`; a constant no cell equals is `Term::Never`, a scan that reads nothing; `:as-of` resolved when the query opens (`Snapshot::tx_bound`: a counter bound when `tx_id` rises with `tx_count`, else `TxBound::Timestamp`: committed `tx_count` ranges and pending `tx_id <= t`); a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, aggregates with `:with`, and window functions, over an aggregate's groups too), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, `HashJoin` otherwise; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`), `window.rs` (`Window`, #547: holds each input row's passed-on cells and its named variables' values, then computes every window with `datalog::aggregate::windows`, the executor's code, and returns the rows in input order), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `relation.rs`/`recursive.rs` (#548: rule queries; a relation per evaluated predicate holds its derived rows, a set by `encode_value` identity, appended per round so `Old`/`Delta`/`Full` are ranges; `Recursive` runs each stratum's semi-naive rounds, one run per same-stratum top-level invocation, a rule reading its stratum otherwise run in full every round; scans read derived rows after committed and pending ones, with `nil` metadata), `meter.rs` (#549: one `Meter` per query, shared by every holder of state through a `Held` — hash join build sides, `not`/`or` tables, distinct sets, aggregate groups, window rows, rule relations and their temporaries, `IdSpace`; each entry charged by a per-entry estimate before it is inserted, containers grown with `try_reserve`, released on `rewind`/`close`/drop; over `OpenOptions::query_memory_limit`, or a refused allocation, is `QRY-012`; `Stream::close` drops the operator tree, keeping its counters). `mod.rs`: `Operator` (`next_batch`/`rewind`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` run every query on it: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it.
+3a. **`src/query/engine/`** — Streaming query engine (#473), runs every query (#551): `plan.rs` (the operator tree of every query, or the executor's error code for it: patterns, expression clauses, `not`/`not-join` and `or`/`or-join`, and rule invocations, read as patterns of their relations (`plan_rules`, #548; a magic-set head constant is `HeadArg::Const`), in `optimizer::plan` order, then the `or`s in text order, then the deferred `not`s; an `or` branch or a `not` body is planned as a `:where` is; a clause list with no pattern first starts from `Seed`; a constant no cell equals is `Term::Never`, a scan that reads nothing; `:as-of` resolved when the query opens (`Snapshot::tx_bound`: a counter bound when `tx_id` rises with `tx_count`, else `TxBound::Timestamp`: committed `tx_count` ranges and pending `tx_id <= t`); a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, aggregates with `:with`, and window functions, over an aggregate's groups too), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, or, under a constant attribute and entity not constant, its value (#721: per outer row the AVET ranges of the values that join-equal it and the attribute's pending facts with its key, read once per query in `IdSpace::probes`; an entity cell needs the keyword naming it, known only where the query made the entity from a keyword (rule heads, magic seeds), else the join becomes the planner's `HashJoin`); `HashJoin` otherwise, and on a relation; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `aggregate.rs` (`Aggregate`, #547: a hash table of groups keyed on cells as `Value`'s `Ord` compares values, one entry when ungrouped; `count`/`count-distinct` on cells, other aggregates on values via `datalog::aggregate::Agg`; groups sorted by value and finished in that order; a float group shows its least value by `value_order`), `window.rs` (`Window`, #547: holds each input row's passed-on cells and its named variables' values, then computes every window with `datalog::aggregate::windows`, the executor's code, and returns the rows in input order), `union.rs`/`distinct.rs` (`Union` and `Distinct`, #546: each `or` branch planned as a `not` body is, hashed into a table or run per outer row; then one row per distinct binding, as the executor's `Value`s compare), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `relation.rs`/`recursive.rs` (#548: rule queries; a relation per evaluated predicate holds its derived rows, a set by `encode_value` identity, appended per round so `Old`/`Delta`/`Full` are ranges; `Recursive` runs each stratum's semi-naive rounds, one run per same-stratum top-level invocation, a rule reading its stratum otherwise run in full every round; scans read derived rows after committed and pending ones, with `nil` metadata), `meter.rs` (#549: one `Meter` per query, shared by every holder of state through a `Held` — hash join build sides, `not`/`or` tables, distinct sets, aggregate groups, window rows, rule relations and their temporaries, `IdSpace`; each entry charged by a per-entry estimate before it is inserted, containers grown with `try_reserve`, released on `rewind`/`close`/drop; over `OpenOptions::query_memory_limit`, or a refused allocation, is `QRY-012`; `Stream::close` drops the operator tree, keeping its counters). `mod.rs`: `Operator` (`next_batch`/`rewind`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` run every query on it: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it.
 
 4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396)
 
@@ -212,7 +212,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are
 
 ## Test Coverage
 
-**1709 tests** (1697 passing, 12 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551).
+**1713 tests** (1701 passing, 12 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.

@@ -154,6 +154,39 @@ pub fn fanout_graph(width: usize, depth: usize) -> Arc<Minigraf> {
     Arc::new(db)
 }
 
+/// In-memory DB with the fan-out tree of [`fanout_graph`] pointing up: each
+/// node has `[:n<child> :up :n<parent>]`, and `(anc ?x ?a)` is every
+/// ancestor of `?x` (#721). Returns the database and the last leaf's id.
+pub fn ancestor_tree(width: usize, depth: usize) -> (Arc<Minigraf>, usize) {
+    let db = Minigraf::in_memory().unwrap();
+    let mut edges: Vec<(usize, usize)> = Vec::new();
+    let mut current_level = vec![0usize];
+    let mut next_id = 1usize;
+    for _ in 0..depth {
+        let mut next_level = Vec::new();
+        for &parent in &current_level {
+            for _ in 0..width {
+                edges.push((next_id, parent));
+                next_level.push(next_id);
+                next_id += 1;
+            }
+        }
+        current_level = next_level;
+    }
+    for chunk in edges.chunks(200) {
+        let mut cmd = String::from("(transact [");
+        for (child, parent) in chunk {
+            cmd.push_str(&format!("[:n{} :up :n{}]", child, parent));
+        }
+        cmd.push_str("])");
+        db.execute(&cmd).unwrap();
+    }
+    db.execute("(rule [(anc ?x ?a) [?x :up ?a]])").unwrap();
+    db.execute("(rule [(anc ?x ?a) [?x :up ?p] (anc ?p ?a)])")
+        .unwrap();
+    (Arc::new(db), next_id - 1)
+}
+
 /// In-memory DB with n value facts AND n-1 chain reference facts.
 /// Total ≈ 2n facts. Used for join_3pattern benchmarks.
 ///

@@ -323,6 +323,24 @@ fn bench_recursion(c: &mut Criterion) {
         );
         group.finish();
     }
+
+    // ancestors: the same tree pointing up, from a leaf (#721). After the
+    // magic-set rewrite, each round joins `[?x :up ?p]` on its value.
+    {
+        let mut group = c.benchmark_group("recursion/ancestors");
+        group.sample_size(10);
+        let (label, width, depth) = ("w10_d4", 10usize, 4usize);
+        group.bench_with_input(
+            BenchmarkId::from_parameter(label),
+            &(width, depth),
+            |b, &(width, depth)| {
+                let (db, leaf) = helpers::ancestor_tree(width, depth);
+                let q = format!("(query [:find ?a :where (anc :n{leaf} ?a)])");
+                b.iter(|| db.execute(&q).unwrap());
+            },
+        );
+        group.finish();
+    }
 }
 
 // ── Task 8: open/ ─────────────────────────────────────────────────────────────

@@ -4,9 +4,9 @@
 
 | | Default features | With `--features test-hooks` |
 |---|---|---|
-| **Passing** | 1,697 | 1,713 |
+| **Passing** | 1,701 | 1,717 |
 | **Ignored** | 12 | 13 |
-| **Total** | 1,709 | 1,726 |
+| **Total** | 1,713 | 1,730 |
 
 **Verified**: 2026-10-23 with `cargo test --quiet`.
 
@@ -414,6 +414,7 @@ These tests compare the database against an independent answer rather than a sin
   - Each in memory, on a file with pending facts and after a checkpoint, against their frozen answers.
   - Engine unit tests check routing (`:as-of` timestamps, a rule body with no pattern, a three-argument call and a write transaction) and derived rows read across batches before and after a checkpoint. `relation.rs` unit tests check row identity and the `Old` / `Delta` / `Full` ranges.
   - Every delta run of the magic-set rewrite of a recursive rule joins each clause on a variable bound before it, with no keyless join (`rule_delta_runs_join_on_a_bound_variable`, #694). An optimizer unit test checks `plan_after`'s connected order.
+  - A join on a bound value probes its AVET ranges and pending facts (#721): the delta run of the ancestors shape probes `[?x :manager ?y]` by value, in memory and on a half-checkpointed file (`rule_delta_probes_a_bound_value`); a value join reads only the probed keys, through a pending retraction (`value_probe_reads_only_the_probed_keys`); keyword and ref from either side, an entity cell no keyword was recorded for (the hash-join fallback), `0.0`/`-0.0`, long strings, `:as-of` and `:valid-at`, in memory, checkpointed and pending (`value_probe_matches_as_joins_do`); a fallback in the middle of a batch joins the rows before it, the rest of the batch and later batches once each (`value_probe_falls_back_mid_batch`).
 - **`:db/valid-at` in rule bodies** (`tests/recursive_rules_test.rs`, #617): a `:db/valid-at` pattern in a rule definition, in its `not` and `not-join` bodies and in its `or` branches binds the query's valid time, on the semi-naive, stratified and magic-sets paths.
 - **Rules calling `not` / `or` rules** (`tests/not_join_test.rs`, #628)
   - A rule calling a rule with `not-join`, `not` or `or` returns that rule's rows, with a free and a literal argument and through a forwarding rule.