adityamukho · Aug 24, 2026 · Aug 24, 2026 · Aug 24, 2026 · Aug 24, 2026
@@ -111,6 +111,10 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 
   This required fixing `PageCache` itself: capacity `0` previously meant *unbounded* (the eviction loop's `capacity > 0` guard skipped eviction but insertion still ran unconditionally), which would have made this change strictly worse — an ever-growing duplicate of every page ever read, never reclaimed. `PageCache::new(0)` now means the cache is disabled outright: `get_or_load` always reads through to the backend and `put_dirty` is a no-op. No existing caller passed `0` before this change, so no other behaviour is affected.
 
+- **`not`/`not-join` clauses are pushed to the earliest position where their variables are bound** (#248): `optimizer::plan()` now accepts `Not`/`NotJoin` alongside `Pattern`/`Expr` and interleaves each one right after the pattern that completes its required variables, instead of always applying it as a global post-filter after every pattern (and after `or`/`or-join`). This shrinks the intermediate binding set flowing into any patterns that follow it in the plan. A clause whose variables are only ever bound by an `or`/`or-join` (not by any pattern in the same clause list) is deferred to the post-filter exactly as before — `or`/`or-join` isn't visible to the planner, so pushing it early would run the clause before its dependency exists. Benchmark: `negation/not_pushdown_selectivity` (10k facts, three joins after the `not`) shows the effect scaling with the excluded fraction, from ~2% at 0% excluded up to ~55% faster at 100% excluded.
+
+- **`or`/`or-join` branches can now short-circuit** (#250): branches are still sorted cheapest-first (landed earlier), but once the branches evaluated so far already produce a match for every incoming binding, remaining (costlier) branches are skipped instead of always being evaluated. This is always safe for `or-join` — branches are projected down to already-bound outer variables before merging, so a skipped branch could only have produc
8000
ed a row identical to one already kept. For plain `or`, it's only safe when the branches evaluated so far introduce no variable beyond what's already bound in the incoming scope (a pure filter) — a branch that binds a genuinely new variable can legitimately contribute a distinct row for an already-"covered" key, so that case still evaluates every branch, exactly as before. Benchmark: `disjunction/or_short_circuit` and `disjunction/or_join_short_circuit` (10k facts, both branches fully covering) show ~11% and ~27% improvement respectively.
+
 ## v1.2.3 — 2026-08-10
 
 No changes to the core crate. Released so the language bindings have a version

@@ -227,6 +227,47 @@ pub fn populate_with_not_rule(n: usize, excluded: usize) -> Arc<Minigraf> {
     Arc::new(db)
 }
 
+/// In-memory DB with `n` value facts, `excluded` banned entities, and three more
+/// attributes (`:x`, `:y`, `:z`) present on every entity.
+///
+/// Schema:
+///   `:e{i} :val {i}` for i in 0..n
+///   `:e{i} :banned true` for i in 0..excluded
+///   `:e{i} :x true`, `:e{i} :y true`, `:e{i} :z true` for i in 0..n
+///
+/// Used for the `not` push-down benchmark (#248): with `not` deferred to the end
+/// (pre-push-down), `:x`/`:y`/`:z` all join against the full `n`-row binding set;
+/// with `not` pushed to right after `?e` is bound (post-push-down), they join
+/// against the already-`excluded`-filtered set instead.
+///   `(query [:find ?e :where [?e :val ?v] (not [?e :banned true]) \
+///            [?e :x true] [?e :y true] [?e :z true]])`
+pub fn populate_with_not_pushdown(n: usize, excluded: usize) -> Arc<Minigraf> {
+    let db = Minigraf::in_memory().unwrap();
+    insert_val_facts(&db, n);
+    for batch_start in (0..excluded).step_by(100) {
+        let batch_end = (batch_start + 100).min(excluded);
+        let mut cmd = String::from("(transact [");
+        for i in batch_start..batch_end {
+            cmd.push_str(&format!("[:e{} :banned true]", i));
+        }
+        cmd.push_str("])");
+        db.execute(&cmd).unwrap();
+    }
+    for batch_start in (0..n).step_by(100) {
+        let batch_end = (batch_start + 100).min(n);
+        let mut cmd = String::from("(transact [");
+        for i in batch_start..batch_end {
+            cmd.push_str(&format!(
+                "[:e{i} :x true] [:e{i} :y true] [:e{i} :z true]",
+                i = i
+            ));
+        }
+        cmd.push_str("])");
+        db.execute(&cmd).unwrap();
+    }
+    Arc::new(db)
+}
+
 // ── Disjunction fixtures ──────────────────────────────────────────────────────
 
 /// In-memory DB with `n` value facts plus `a_count` entities with `:tag-a` and

@@ -815,6 +815,39 @@ fn bench_negation(c: &mut Criterion) {
         group.finish();
     }
 
+    // not/pushdown_selectivity: fixed 10k DB with three extra joins (:x/:y/:z) after
+    // the `not` clause. Vary the excluded fraction to show how much intermediate
+    // binding-set size the #248 push-down avoids carrying through those joins.
+    {
+        let mut group = c.benchmark_group("negation/not_pushdown_selectivity");
+        group.sample_size(10);
+        let n = 10_000;
+        for &(label, pct) in &[
+            ("excl_0pct", 0usize),
+            ("excl_25pct", 25),
+            ("excl_50pct", 50),
+            ("excl_75pct", 75),
+            ("excl_100pct", 100),
+        ] {
+            let excluded = n * pct / 100;
+            group.bench_with_input(
+                BenchmarkId::from_parameter(label),
+                &excluded,
+                |b, &excluded| {
+                    let db = helpers::populate_with_not_pushdown(n, excluded);
+                    b.iter(|| {
+                        db.execute(
+                            "(query [:find ?e :where [?e :val ?v] (not [?e :banned true]) \
+                             [?e :x true] [?e :y true] [?e :z true]])",
+                        )
+                        .unwrap()
+                    });
+                },
+            );
+        }
+        group.finish();
+    }
+
     // not/rule_body: `not` inside a rule body (StratifiedEvaluator overhead).
     // Rule: `(eligible ?x) :- [?x :val ?v] (not [?x :blocked true])`
     // 10% of entities are blocked.
@@ -977,6 +1010,49 @@ fn bench_disjunction(c: &mut Criterion) {
         group.finish();
     }
 
+    // or/short_circuit: both branches fully cover every entity (tag-a and tag-b are
+    // both present on all `n` entities), so branch 1 alone already satisfies every
+    // incoming binding. Pre-#250 this always evaluates and hash-joins branch 2 as
+    // well; post-#250 it's skipped once branch 1's coverage is complete.
+    {
+        let mut group = c.benchmark_group("disjunction/or_short_circuit");
+        group.sample_size(10);
+        group.warm_up_time(std::time::Duration::from_millis(500));
+        for &(label, n) in SCALES {
+            group.bench_with_input(BenchmarkId::from_parameter(label), &n, |b, &n| {
+                let db = helpers::populate_with_or_tags(n, n, n);
+                b.iter(|| {
+                    db.execute(
+                        "(query [:find ?e :where [?e :val ?v] \
+                         (or [?e :tag-a true] [?e :tag-b true])])",
+                    )
+                    .unwrap()
+                });
+            });
+        }
+        group.finish();
+    }
+
+    // or-join/short_circuit: same fully-covering setup, using `or-join`.
+    {
+        let mut group = c.benchmark_group("disjunction/or_join_short_circuit");
+        group.sample_size(10);
+        group.warm_up_time(std::time::Duration::from_millis(500));
+        for &(label, n) in SCALES {
+            group.bench_with_input(BenchmarkId::from_parameter(label), &n, |b, &n| {
+                let db = helpers::populate_with_or_tags(n, n, n);
+                b.iter(|| {
+                    db.execute(
+                        "(query [:find ?e :where [?e :val ?v] \
+                         (or-join [?e] [?e :tag-a true] [?e :tag-b true])])",
+                    )
+                    .unwrap()
+                });
+            });
+        }
+        group.finish();
+    }
+
     // or/rule_body: `or` inside a rule body (mixed-rules path overhead).
     // Rule: `(tagged ?x) :- (or [?x :tag-a true] [?x :tag-b true])`
     // Half have tag-a, half have tag-b → all entities match.

@@ -808,7 +808,9 @@ impl StratifiedEvaluator {
                 let matcher = PatternMatcher::from_slice(accumulated_facts.clone());
 
                 // Plan: assigns index hints + pushes Expr to earliest binding position.
-                let planned = crate::query::datalog::optimizer::plan(
+                // Not/NotJoin are excluded from plan_clauses above, so `deferred` is
+                // always empty here — rule bodies keep their existing not-filter path.
+                let (planned, _deferred) = crate::query::datalog::optimizer::plan(
                     plan_clauses,
                     &crate::storage::index::Indexes::new(),
                 );