adityamukho · Oct 23, 2026 · Oct 23, 2026
@@ -58,6 +58,8 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 
 ### Fixed
 
+- **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.
+
 - **`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.

@@ -143,7 +143,7 @@ cargo run < demos/demo_negation.txt
    - `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection; a positive edge to a rule with `not`/`not-join`/`or`/`or-join` also raises the caller, off a cycle (#628)
    - `rules.rs`: `RuleRegistry` — thread-safe rule management
    - `types.rs`: `EdnValue`, `Pattern`, `DatalogQuery`, `AsOf`, `ValidAt`, `WhereClause` (incl. `Not`, `NotJoin`); `PseudoAttr` enum, `AttributeSpec` wrapper
-   - `optimizer.rs`: Selectivity-based join reordering on every build (the `wasm` feature is a deprecated no-op). `reorder()` gates every reordering site; tests turn it off per thread (`set_reorder`, `minigraf::__reorder` under `test-oracle`, #596); `plan_seeded` orders a body with its imported variables counted as bound, and `subplans()` lets tests force the engine's negation bodies and `or` branches hashed or correlated (`set_subplans`, `minigraf::__subplans`, #546)
+   - `optimizer.rs`: Selectivity-based join reordering on every build (the `wasm` feature is a deprecated no-op). `reorder()` gates every reordering site; tests turn it off per thread (`set_reorder`, `minigraf::__reorder` under `test-oracle`, #596); `plan_seeded` orders a body with its imported variables counted as bound, `plan_after` orders a rule body's clauses after its delta, each joining on a variable bound before it where one can (#694), and `subplans()` lets tests force the engine's negation bodies and `or` branches hashed or correlated (`set_subplans`, `minigraf::__subplans`, #546)
    - `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`)
 
@@ -212,7 +212,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are
 
 ## Test Coverage
 
-**1767 tests** (1753 passing, 14 ignored; unit + integration + doc).
+**1769 tests** (1755 passing, 14 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.

@@ -282,6 +282,26 @@ pub fn plan(
 pub(crate) fn plan_seeded(
     clauses: Vec<WhereClause>,
     seeded: &std::collections::HashSet<String>,
+) -> (Vec<(WhereClause, Option<IndexHint>)>, Vec<WhereClause>) {
+    plan_ordered(clauses, seeded, false)
+}
+
+/// [`plan_seeded`] for the clauses after a pattern that runs first, binding
+/// `seeded` (a rule body's delta, #694): each next pattern shares a variable
+/// with those bound before it when one does, the most selective of those as
+/// the bound variables stand, so no pattern joins as a product while one
+/// could join on a key. Cost only: no answer depends on the order.
+pub(crate) fn plan_after(
+    clauses: Vec<WhereClause>,
+    seeded: &std::collections::HashSet<String>,
+) -> (Vec<(WhereClause, Option<IndexHint>)>, Vec<WhereClause>) {
+    plan_ordered(clauses, seeded, true)
+}
+
+fn plan_ordered(
+    clauses: Vec<WhereClause>,
+    seeded: &std::collections::HashSet<String>,
+    connected: bool,
 ) -> (Vec<(WhereClause, Option<IndexHint>)>, Vec<WhereClause>) {
     // Separate into patterns (with hints), exprs, and not/not-join clauses.
     let mut patterns: Vec<(WhereClause, IndexHint)> = Vec::new();
@@ -317,6 +337,10 @@ pub(crate) fn plan_seeded(
         });
     }
 
+    if connected && reorder() {
+        patterns = connect(patterns, seeded);
+    }
+
     // Start with sorted patterns only.
     let mut result: Vec<(WhereClause, Option<IndexHint>)> = patterns
         .into_iter()
@@ -471,6 +495,43 @@ pub(crate) fn plan_seeded(
     (result, deferred)
 }
 
+/// Reorder `patterns` (sorted by selectivity) so that each shares a variable
+/// with `seeded` or a pattern before it, when any remaining one does: the
+/// highest [`selectivity_score`] given the variables bound so far, the
+/// earliest on a tie. A pattern sharing none comes next only when no
+/// remaining pattern shares one. `?_` wildcards join nothing.
+fn connect(
+    mut patterns: Vec<(WhereClause, IndexHint)>,
+    seeded: &std::collections::HashSet<String>,
+) -> Vec<(WhereClause, IndexHint)> {
+    let vars = |c: &WhereClause| match c {
+        WhereClause::Pattern(p) => pattern_bound_vars(p)
+            .into_iter()
+            .filter(|v| !v.starts_with("?_"))
+            .collect(),
+        _ => Vec::new(),
+    };
+    let mut bound = seeded.clone();
+    let mut out = Vec::with_capacity(patterns.len());
+    while !patterns.is_empty() {
+        let mut best: Option<(usize, u8)> = None;
+        for (i, (c, _)) in patterns.iter().enumerate() {
+            let WhereClause::Pattern(p) = c else { continue };
+            if !vars(c).iter().any(|v| bound.contains(v)) {
+                continue;
+            }
+            let score = selectivity_score(p, &bound);
+            if best.is_none_or(|(_, b)| score > b) {
+                best = Some((i, score));
+            }
+        }
+        let next = patterns.remove(best.map_or(0, |(i, _)| i));
+        bound.extend(vars(&next.0));
+        out.push(next);
+    }
+    out
+}
+
 /// Static 4-tier cardinality estimate for a single pattern.
 ///
 /// Derived from selectivity_score but returns u64 cost (lower = cheaper) rather
@@ -606,6 +667,59 @@ mod tests {
         assert_eq!(first(&planned)[1], "?x", "text order");
     }
 
+    /// #694: after a first pattern binding `seeded`, each next pattern
+    /// shares a variable with those bound before it when any does.
+    #[test]
+    fn plan_after_joins_each_pattern_on_a_bound_variable() {
+        // The magic-sets body of `reach` after its `(reach ?mid ?to)` delta:
+        // 
8000
`magic` alone is the more selective, but shares nothing yet.
+        let body = vec![
+            WhereClause::Pattern(make_pattern(
+                var("from"),
+                kw(":magic"),
+                EdnValue::Boolean(true),
+            )),
+            WhereClause::Pattern(make_pattern(var("from"), kw(":next"), var("mid"))),
+        ];
+        let attrs = |planned: &[(WhereClause, Option<IndexHint>)]| -> Vec<String> {
+            planned
+                .iter()
+                .map(|(c, _)| match c {
+                    WhereClause::Pattern(p) => format!("{:?}", p.attribute),
+                    _ => "other".to_string(),
+                })
+                .collect()
+        };
+        let seeded: std::collections::HashSet<String> =
+            ["?mid".to_string(), "?to".to_string()].into();
+        let (before, _) = plan_seeded(body.clone(), &seeded);
+        assert!(attrs(&before)[0].contains(":magic"), "selectivity alone");
+        let (after, _) = plan_after(body.clone(), &seeded);
+        assert!(attrs(&after)[0].contains(":next"));
+        assert!(attrs(&after)[1].contains(":magic"));
+
+        // A chain: each step joins the one before it, not the selective
+        // `:root` that shares nothing until `?w` is bound.
+        let chain = vec![
+            WhereClause::Pattern(make_pattern(var("w"), kw(":root"), EdnValue::Boolean(true))),
+            WhereClause::Pattern(make_pattern(var("w"), kw(":b"), var("x"))),
+            WhereClause::Pattern(make_pattern(var("x"), kw(":c"), var("z"))),
+        ];
+        let seeded: std::collections::HashSet<String> = ["?z".to_string()].into();
+        let (after, _) = plan_after(chain.clone(), &seeded);
+        let order = attrs(&after);
+        assert!(order[0].contains(":c") && order[1].contains(":b") && order[2].contains(":root"));
+
+        // No pattern shares a variable: selectivity order.
+        let seeded: std::collections::HashSet<String> = ["?q".to_string()].into();
+        let (after, _) = plan_after(chain.clone(), &seeded);
+        assert!(attrs(&after)[0].contains(":root"));
+
+        let _off = set_reorder(false);
+        let (after, _) = plan_after(body, &["?mid".to_string()].into());
+        assert!(attrs(&after)[0].contains(":magic"), "text order");
+    }
+
     #[test]
     fn subplans_switch_is_per_thread_and_restored() {
         assert_eq!(subplans(), Subplans::Choose);

@@ -334,15 +334,27 @@ fn clauses(b: &mut Builder, clauses: &[WhereClause], first: Option<&Pattern>) ->
     }) {
         return None;
     }
-    let (mut planned, deferred) = optimizer::plan(clauses.to_vec());
-    if let Some(p) = first.filter(|_| optimizer::reorder())
-        && let Some(i) = planned
+    // With `first`, the rest are ordered after it, its variables bound, each
+    // joining on a variable bound before it where one can (#694).
+    let at = first.filter(|_| optimizer::reorder()).and_then(|p| {
+        clauses
             .iter()
-            .position(|(c, _)| matches!(c, WhereClause::Pattern(q) if q == p))
-    {
-        let c = planned.remove(i);
-        planned.insert(0, c);
-    }
+            .position(|c| matches!(c, WhereClause::Pattern(q) if q == p))
+    });
+    let (planned, deferred) = match at {
+        Some(i) => {
+            let mut rest = clauses.to_vec();
+            let head = rest.remove(i);
+            let seeded: HashSet<String> = match &head {
+                WhereClause::Pattern(p) => optimizer::pattern_bound_vars(p).into_iter().collect(),
+                _ => HashSet::new(),
+            };
+            let (mut planned, deferred) = optimizer::plan_after(rest, &seeded);
+            planned.insert(0, (head, None));
+            (planned, deferred)
+        }
+        None => optimizer::plan(clauses.to_vec()),
+    };
     for (c, _) in planned {
         b.clause(c)?;
     }
@@ -669,7 +681,7 @@ fn rule_plan(
     let mut deltas = Vec::new();
     if !naive {
         for (i, delta) in own.iter().enumerate() {
-            let ranges = own
+            let mut ranges: Vec<(Pattern, Range)> = own
                 .iter()
                 .enumerate()
                 .map(|(j, p)| {
@@ -681,6 +693,10 @@ fn rule_plan(
                     (p.clone(), range)
                 })
                 .collect();
+            // The delta's range first: the pattern planned first takes it
+            // even when an equal invocation comes before it (#694).
+            let d = ranges.remove(i);
+            ranges.insert(0, d);
             deltas.push(run(ranges, Some(delta))?);
         }
     }

@@ -1856,6 +1856,72 @@ fn rule_queries_read_derived_rows_in_batches() {
     }
 }
 
+/// A rule body's delta run joins each later clause on a variable bound
+/// before it where one can (#694). Magic sets turn `(reach :n0 ?to)` into
+/// `(magic ?from) [?from :next ?mid] (reach ?mid ?to)`; the run from the
+/// `reach` delta took `magic` next, sharing nothing with it, and joined
+/// every delta row with every magic row.
+#[test]
+fn rule_delta_runs_join_on_a_bound_variable() {
+    use super::plan::{JoinKind, Step};
+    use crate::query::datalog::parser::parse_datalog_command;
+    use crate::query::datalog::rules::RuleRegistry;
+    use crate::query::datalog::types::DatalogCommand;
+    let mut registry = RuleRegistry::new();
+    for rule in [
+        "(rule [(reach ?from ?to) [?from :next ?to]])",
+        "(rule [(reach ?from ?to) [?from :next ?mid] (reach ?mid ?to)])",
+    ] {
+        let DatalogCommand::Rule(r) = parse_datalog_command(rule).unwrap() else {
+            panic!("expected a rule");
+        };
+        registry.register_rule("reach".to_string(), r).unwrap();
+    }
+    let DatalogCommand::Query(query) =
+        parse_datalog_command("(query [:find ?to :where (reach :n0 ?to)])").unwrap()
+    else {
+        panic!("expected a query");
+    };
+    let (rewritten, seeds) =
+        crate::query::datalog::magic_sets::rewrite(&query, &registry).expect("magic sets apply");
+    let attrs: Vec<&str> = seeds.iter().map(|(_, a, _)| a.as_str()).collect();
+    let plan = super::plan_rules(&query, &rewritten, &attrs).expect("the engine plans it");
+    let mut runs = 0;
+    for (_, rules) in &plan.strata {
+        for rule in rules {
+            for run in &rule.deltas {
+                runs += 1;
+                for step in &run.plan.steps {
+                    if let Step::Join(j) = step {
+                        assert!(
+                            !(matches!(j.kind, JoinKind::Hash { .. }) && j.keys.is_empty()),
+                            "a delta run of {} joins as a product",
+                            rule.predicate
+                        );
+                    }
+                }
+            }
+        }
+    }
+    assert!(runs >= 2, "the recursive rules have delta runs");
+
+    // The answers on a fan-out tree, engine and executor agreeing.
+    let db = Minigraf::in_memory().unwrap();
+    let mut edges = String::new();
+    for p in 0..11 {
+        for c in 0..10 {
+            edges.push_str(&format!("[:n{p} :next :n{}]", 1 + p * 10 + c));
+        }
+    }
+    db.execute(&format!("(transact [{edges}])")).unwrap();
+    db.execute("(rule [(reach ?from ?to) [?from :next ?to]])")
+        .unwrap();
+    db.execute("(rule [(reach ?from ?to) [?from :next ?mid] (reach ?mid ?to)])")
+        .unwrap();
+    assert_eq!(rows(&db, "(query [:find ?to :where (reach :n0 ?to)])"), 110);
+    assert_eq!(rows(&db, "(query [:find ?to :where (reach :n1 ?to)])"), 10);
+}
+
 // ── #549: query memory accounting ──────────────────────────────────────────
 
 /// A checkpointed database of `n` entities, each with integers `:a` and