From 16ebd1239efe5bae3afaffec9b2e8b2710742ea6 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Mon, 24 Aug 2026 09:46:31 +0530 Subject: [PATCH 1/3] perf: push down not/not-join clauses and short-circuit or/or-join branches #248: optimizer::plan() now places Not/NotJoin at the earliest position where their required variables are bound by preceding patterns, instead of always deferring them to a post-filter after every pattern (and after Or/OrJoin). A clause that can only be satisfied via an Or/OrJoin binding is still deferred, since plan() has no visibility into those clauses. This shrinks the executor's two large not-filter blocks into small per-clause helper calls reused for both the inline and deferred paths. #250: apply_or_clauses now short-circuits once evaluated branches already cover every incoming binding. Always safe for or-join (branches are projected to already-bound outer keys before merging, so a skipped branch could only re-derive an existing row). For plain or, only safe when no evaluated branch has introduced a variable beyond the incoming scope, since a later branch legitimately could bind a new variable differently for an already-covered key otherwise. Benchmarks: negation/not_pushdown_selectivity shows up to ~55% faster at high exclusion rates; disjunction/or_short_circuit and disjunction/or_join_short_circuit show ~11% and ~27% improvement on fully-redundant branches. Co-Authored-By: Claude Sonnet 5 Claude-Session: https://claude.ai/code/session_01YMWSutMLJJ7Y5b8hs9ZaCU --- CHANGELOG.md | 4 + benches/helpers/mod.rs | 41 ++ benches/minigraf_bench.rs | 76 +++ src/query/datalog/evaluator.rs | 4 +- src/query/datalog/executor.rs | 1012 ++++++++++++++++---------------- src/query/datalog/optimizer.rs | 228 ++++++- tests/disjunction_test.rs | 212 ++++++- 7 files changed, 1067 insertions(+), 510 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index b293109d8f..9c07f5fc22 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -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 produced 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 diff --git a/benches/helpers/mod.rs b/benches/helpers/mod.rs index 8bac312e53..6b9dea532c 100644 --- a/benches/helpers/mod.rs +++ b/benches/helpers/mod.rs @@ -227,6 +227,47 @@ pub fn populate_with_not_rule(n: usize, excluded: usize) -> Arc { 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 { + 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 diff --git a/benches/minigraf_bench.rs b/benches/minigraf_bench.rs index 813d859d09..e8f27bc8d8 100644 --- a/benches/minigraf_bench.rs +++ b/benches/minigraf_bench.rs @@ -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. diff --git a/src/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index 347a4d4b98..08835ecad2 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -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(), ); diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 6c3b6e6c0b..9667521f9f 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -517,18 +517,27 @@ impl DatalogExecutor { } } - // Collect Pattern and Expr top-level clauses for the planner. - // Not/NotJoin/Or/OrJoin are extracted separately below and applied as post-filters. + // Collect Pattern, Expr, Not, and NotJoin top-level clauses for the planner. + // Or/OrJoin are extracted separately below and applied as a post-pass. let plan_clauses: Vec = query .where_clauses .iter() - .filter(|c| matches!(c, WhereClause::Pattern(_) | WhereClause::Expr { .. })) + .filter(|c| { + matches!( + c, + WhereClause::Pattern(_) + | WhereClause::Expr { .. } + | WhereClause::Not(_) + | WhereClause::NotJoin { .. } + ) + }) .cloned() .collect(); - let planned = optimizer::plan(plan_clauses, &self.indexes); + let (planned, deferred_not_clauses) = optimizer::plan(plan_clauses, &self.indexes); - // Process planned clauses in order: Pattern → expand bindings, Expr → filter/extend. + // Process planned clauses in order: Pattern → expand bindings, Expr → filter/extend, + // Not/NotJoin → shrink bindings as soon as their variables are bound (#248). let mut bindings: Vec = vec![Binding::new()]; for (clause, hint) in planned { match clause { @@ -557,16 +566,35 @@ impl DatalogExecutor { }) .collect(); } + WhereClause::Not(body) => { + bindings = apply_not_clause( + bindings, + &body, + filtered_facts.clone(), + valid_at_value.clone(), + ®istry, + ); + } + WhereClause::NotJoin { join_vars, clauses } => { + bindings = apply_not_join_clause( + bindings, + &join_vars, + &clauses, + filtered_facts.clone(), + valid_at_value.clone(), + ®istry, + ); + } _ => {} } } - // Apply Or/OrJoin clauses (post-pass: after pattern matching, before not/expr) + // Apply Or/OrJoin clauses (post-pass: after pattern matching, before deferred not/expr) let rules_guard = self .rules .read() .map_err(|_| anyhow!("rules lock poisoned"))?; - let bindings = apply_or_clauses( + let mut bindings = apply_or_clauses( &query.where_clauses, bindings, filtered_facts.clone(), @@ -577,308 +605,35 @@ impl DatalogExecutor { )?; drop(rules_guard); - // Apply not-filter for WhereClause::Not and WhereClause::NotJoin clauses - // (no rules involved — pure post-filter) - #[cfg_attr(feature = "wasm", allow(unused_mut))] - let mut not_clauses: Vec<&Vec> = query - .where_clauses - .iter() - .filter_map(|c| match c { - WhereClause::Not(inner) => Some(inner), - _ => None, - }) - .collect(); - + // Apply Not/NotJoin clauses the planner couldn't place inline (#248) — their + // variables are only bound by the Or/OrJoin pass above, so they must run here, + // after it. Sorted cheapest-first, same as the pre-#248 post-filter ordering. #[cfg_attr(feature = "wasm", allow(unused_mut))] - let mut not_join_clauses: Vec<(Vec, Vec)> = query - .where_clauses - .iter() - .filter_map(|c| match c { - WhereClause::NotJoin { join_vars, clauses } => { - Some((join_vars.clone(), clauses.clone())) - } - _ => None, - }) - .collect(); - - // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). - #[cfg(not(feature = "wasm"))] - not_clauses.sort_by_key(|body| optimizer::clause_cost(&WhereClause::Not(body.to_vec()))); - // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + let mut deferred_not_clauses = deferred_not_clauses; #[cfg(not(feature = "wasm"))] - not_join_clauses.sort_by_key(|(vars, clauses)| { - optimizer::clause_cost(&WhereClause::NotJoin { - join_vars: vars.clone(), - clauses: clauses.clone(), - }) - }); - - let not_filtered: Vec<_> = if not_clauses.is_empty() && not_join_clauses.is_empty() { - bindings - } else { - // Pre-compute exclusion sets — one evaluation per not-body, not per outer binding. - // - // For each not-body, run pattern matching once against `filtered_facts` to get - // all bindings where the body is satisfiable. Then collect the "join keys" (the - // subset of variables that appear in the outer bindings) into a HashSet. - // The filter loop below does one O(1) probe per outer binding instead of a full - // pattern match. - // - // Edge case: expr-only bodies (no patterns) produce no pre-computed set and fall - // through to `not_body_matches` as before (rare, already fast). - use std::collections::HashSet; - - // --- Not bodies --- - // Each element: either Some((has_expr, HashSet of excluded join-key tuples)) or None - // (expr-only, use slow path). `has_expr` is computed once here during pre-compute, - // not inside the per-binding filter closure. - let not_exclusion_sets: Vec = not_clauses - .iter() - .map(|not_body| { - let has_expr = not_body - .iter() - .any(|c| matches!(c, WhereClause::Expr { .. })); - let patterns: Vec<_> = not_body - .iter() - .filter_map(|c| match c { - WhereClause::Pattern(p) => Some(p.clone()), - _ => None, - }) - .collect(); - if patterns.is_empty() { - // Expr-only body: no pre-computation possible. - return None; - } - let matcher = PatternMatcher::from_slice_with_valid_at( - filtered_facts.clone(), - valid_at_value.clone(), - ); - let body_bindings = matcher.match_patterns(&patterns); - // Store all body bindings as sorted (key, value) vecs for probing. - // Normalize values (e.g. keyword entities → Ref) so that probe keys from - // the outer binding match body bindings regardless of representation. - let exclusion_set: HashSet> = body_bindings - .into_iter() - .map(|mut b| { - // Drop hidden metadata keys (prefixed `__f`) - b.retain(|k, _| !k.starts_with("__f")); - let mut kv: Vec<(String, Value)> = b - .into_iter() - .map(|(k, v)| (k, normalize_value(&v))) - .collect(); - kv.sort_unstable_by(|a, b| a.0.cmp(&b.0)); - kv - }) - .collect(); - Some((has_expr, exclusion_set)) - }) - .collect(); - - // --- Not-join bodies --- - // Each entry: Some((has_expr, key_vars, HashSet)) where key_vars are the join_vars - // that actually appear in ALL body binding rows (the intersection of join_vars and - // vars bound in every row). This handles cases like `not-join [?u ?r]` where the - // body only binds `?r`. - // - // Values are normalized: Value::Keyword(k) that represents an entity keyword is - // converted to Value::Ref(uuid) so that probe keys from the outer binding (which - // may store entity references as keywords) match the body bindings (which bind - // entity fields as Value::Ref). `has_expr` is computed once here, not per-binding. - let not_join_exclusion_sets: Vec = not_join_clauses - .iter() - .map(|(join_vars, nj_clauses)| { - let has_expr = nj_clauses - .iter() - .any(|c| matches!(c, WhereClause::Expr { .. })); - let patterns: Vec<_> = nj_clauses - .iter() - .filter_map(|c| match c { - WhereClause::Pattern(p) => Some(p.clone()), - _ => None, - }) - .collect(); - if patterns.is_empty() { - return None; - } - let matcher = PatternMatcher::from_slice_with_valid_at( - filtered_facts.clone(), - valid_at_value.clone(), - ); - let body_bindings = matcher.match_patterns(&patterns); - if body_bindings.is_empty() { - return Some((has_expr, join_vars.clone(), HashSet::new())); - } - let key_vars: Vec = join_vars - .iter() - .filter(|v| body_bindings.iter().all(|b| b.contains_key(*v))) - .cloned() - .collect(); - let exclusion_set: HashSet> = body_bindings - .into_iter() - .map(|b| { - let mut kv: Vec<(String, Value)> = key_vars - .iter() - .filter_map(|v| { - b.get(v).map(|val| (v.clone(), normalize_value(val))) - }) - .collect(); - kv.sort_unstable_by(|a, b| a.0.cmp(&b.0)); - kv - }) - .collect(); - Some((has_expr, key_vars, exclusion_set)) - }) - .collect(); - - bindings - .into_iter() - .filter(|binding| { - // Check not-bodies via pre-computed exclusion sets (fast path) or - // via not_body_matches (slow path for expr-only bodies). - for (not_body, exclusion_entry) in - not_clauses.iter().zip(not_exclusion_sets.iter()) - { - match exclusion_entry { - Some((has_expr, exclusion_set)) => { - if exclusion_set.is_empty() && !has_expr { - // No excluding bindings → this outer binding is safe. - continue; - } - if !has_expr { - // Fast path: probe exclusion set using the outer binding's - // values for the join variables, normalized for consistency. - if let Some(sample) = exclusion_set.iter().next() { - let key: Vec<(String, Value)> = sample - .iter() - .filter_map(|(var, _)| { - binding - .get(var) - .map(|val| (var.clone(), normalize_value(val))) - }) - .collect(); - if key.len() == sample.len() { - // All join vars are bound in the outer binding. - if exclusion_set.contains(&key) { - return false; - } - continue; - } - // Outer binding is underspecified (fewer vars than - // the exclusion set key) — fall back to slow path. - if not_body_matches( - not_body, - binding, - filtered_facts.clone(), - valid_at_value.clone(), - ®istry, - ) { - return false; - } - continue; - } - } - // Slow path fallback (expr clauses or empty exclusion set with exprs) - if not_body_matches( - not_body, - binding, - filtered_facts.clone(), - valid_at_value.clone(), - ®istry, - ) { - return false; - } - } - None => { - // Expr-only body: slow path. - if not_body_matches( - not_body, - binding, - filtered_facts.clone(), - valid_at_value.clone(), - ®istry, - ) { - return false; - } - } - } - } - - // Check not-join-bodies. - for ((join_vars, nj_clauses), nj_exclusion_entry) in - not_join_clauses.iter().zip(not_join_exclusion_sets.iter()) - { - match nj_exclusion_entry { - Some((has_expr, key_vars, exclusion_set)) => { - if !has_expr { - if key_vars.is_empty() { - // Body bound no join vars: if exclusion set non-empty, - // exclude all outer bindings (body always succeeds). - if !exclusion_set.is_empty() { - return false; - } - continue; - } - // Build probe key from outer binding using key_vars. - // Normalize values so keyword entities match ref entities. - let mut key: Vec<(String, Value)> = key_vars - .iter() - .filter_map(|v| { - binding - .get(v) - .map(|val| (v.clone(), normalize_value(val))) - }) - .collect(); - key.sort_unstable_by(|a, b| a.0.cmp(&b.0)); - if key.len() == key_vars.len() { - if exclusion_set.contains(&key) { - return false; - } - continue; - } - // Outer binding underspecified relative to the not-join body — - // fall back to the slow path so the body is correctly evaluated. - if evaluate_not_join( - join_vars, - nj_clauses, - binding, - filtered_facts.clone(), - ®istry, - ) { - return false; - } - continue; - } - // Fall through to slow path if expr clauses present. - if evaluate_not_join( - join_vars, - nj_clauses, - binding, - filtered_facts.clone(), - ®istry, - ) { - return false; - } - } - None => { - if evaluate_not_join( - join_vars, - nj_clauses, - binding, - filtered_facts.clone(), - ®istry, - ) { - return false; - } - } - } - } - true - }) - .collect() - }; + deferred_not_clauses.sort_by_key(optimizer::clause_cost); + for clause in deferred_not_clauses { + bindings = match clause { + WhereClause::Not(body) => apply_not_clause( + bindings, + &body, + filtered_facts.clone(), + valid_at_value.clone(), + ®istry, + ), + WhereClause::NotJoin { join_vars, clauses } => apply_not_join_clause( + bindings, + &join_vars, + &clauses, + filtered_facts.clone(), + valid_at_value.clone(), + ®istry, + ), + _ => bindings, + }; + } - let results = - apply_post_processing(not_filtered, &query.find, &query.with_vars, ®istry)?; + let results = apply_post_processing(bindings, &query.find, &query.with_vars, ®istry)?; Ok(QueryResult::QueryResults { vars: query.find.iter().map(|s| s.display_name()).collect(), @@ -992,12 +747,20 @@ impl DatalogExecutor { } } - // Collect Pattern and Expr top-level clauses for the planner. + // Collect Pattern, Expr, Not, and NotJoin top-level clauses for the planner. // Rule invocations are converted to WhereClause::Pattern against derived_storage. let mut plan_clauses: Vec = query .where_clauses .iter() - .filter(|c| matches!(c, WhereClause::Pattern(_) | WhereClause::Expr { .. })) + .filter(|c| { + matches!( + c, + WhereClause::Pattern(_) + | WhereClause::Expr { .. } + | WhereClause::Not(_) + | WhereClause::NotJoin { .. } + ) + }) .cloned() .collect(); @@ -1030,9 +793,10 @@ impl DatalogExecutor { plan_clauses.push(WhereClause::Pattern(pattern)); } - let planned = optimizer::plan(plan_clauses, &self.indexes); + let (planned, deferred_not_clauses) = optimizer::plan(plan_clauses, &self.indexes); - // Process planned clauses in order: Pattern → expand, Expr → filter/extend. + // Process planned clauses in order: Pattern → expand, Expr → filter/extend, + // Not/NotJoin → shrink bindings as soon as their variables are bound (#248). let mut bindings: Vec = vec![Binding::new()]; for (clause, hint) in planned { match clause { @@ -1061,6 +825,24 @@ impl DatalogExecutor { }) .collect(); } + WhereClause::Not(body) => { + bindings = apply_not_clause_derived( + bindings, + &body, + derived_facts.clone(), + valid_at_value.clone(), + ®istry, + ); + } + WhereClause::NotJoin { join_vars, clauses } => { + bindings = apply_not_join_clause_derived( + bindings, + &join_vars, + &clauses, + derived_facts.clone(), + ®istry, + ); + } _ => {} } } @@ -1070,7 +852,7 @@ impl DatalogExecutor { .rules .read() .map_err(|_| anyhow!("rules lock poisoned"))?; - let bindings = apply_or_clauses( + let mut bindings = apply_or_clauses( &query.where_clauses, bindings, derived_facts.clone(), @@ -1081,166 +863,35 @@ impl DatalogExecutor { )?; drop(rules_guard); - // Apply not-post-filter for WhereClause::Not and WhereClause::NotJoin clauses - // in the query body. (The StratifiedEvaluator handles `not`/`not-join` in rule - // bodies; this handles them appearing directly in the query body alongside rule - // invocations.) + // Apply Not/NotJoin clauses the planner couldn't place inline (#248) — their + // variables are only bound by the Or/OrJoin pass above. (The StratifiedEvaluator + // handles `not`/`not-join` in rule bodies; this handles them appearing directly + // in the query body alongside rule invocations.) #[cfg_attr(feature = "wasm", allow(unused_mut))] - let mut not_clauses: Vec<&Vec> = query - .where_clauses - .iter() - .filter_map(|c| match c { - WhereClause::Not(inner) => Some(inner), - _ => None, - }) - .collect(); - - #[cfg_attr(feature = "wasm", allow(unused_mut))] - let mut not_join_clauses: Vec<(Vec, Vec)> = query - .where_clauses - .iter() - .filter_map(|c| match c { - WhereClause::NotJoin { join_vars, clauses } => { - Some((join_vars.clone(), clauses.clone())) - } - _ => None, - }) - .collect(); - - // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + let mut deferred_not_clauses = deferred_not_clauses; #[cfg(not(feature = "wasm"))] - not_clauses.sort_by_key(|body| optimizer::clause_cost(&WhereClause::Not(body.to_vec()))); - // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). - #[cfg(not(feature = "wasm"))] - not_join_clauses.sort_by_key(|(vars, clauses)| { - optimizer::clause_cost(&WhereClause::NotJoin { - join_vars: vars.clone(), - clauses: clauses.clone(), - }) - }); - - let not_filtered: Vec<_> = if not_clauses.is_empty() && not_join_clauses.is_empty() { - bindings - } else { - bindings - .into_iter() - .filter(|binding| { - for not_body in ¬_clauses { - // Collect pattern and rule-invocation clauses into patterns. - let substituted: Vec = not_body - .iter() - .filter_map(|c| match c { - WhereClause::Pattern(p) => { - Some(crate::query::datalog::evaluator::substitute_pattern( - p, binding, - )) - } - WhereClause::RuleInvocation { predicate, args } => { - // Convert rule invocation to a pattern against derived storage. - // Apply the current binding to any variables in args first. - let resolved_args: Vec = args - .iter() - .map(|a| match a { - EdnValue::Symbol(s) if s.starts_with('?') => { - // Look up the bound value and convert back to EdnValue - binding - .get(s) - .map(|v| match v { - Value::Keyword(k) => { - EdnValue::Keyword(k.clone()) - } - Value::String(s) => { - EdnValue::String(s.clone()) - } - Value::Integer(i) => EdnValue::Integer(*i), - Value::Float(f) => EdnValue::Float(*f), - Value::Boolean(b) => EdnValue::Boolean(*b), - Value::Ref(u) => EdnValue::Uuid(*u), - Value::Null => EdnValue::Nil, - }) - .unwrap_or_else(|| a.clone()) - } - other => other.clone(), - }) - .collect(); - // Safety: match arms guarantee len()==1 or len()==2. - let pattern = match resolved_args.len() { - 1 => { - #[allow(clippy::indexing_slicing)] - let entity = resolved_args[0].clone(); - Pattern::new( - entity, - EdnValue::Keyword(format!(":{}", predicate)), - EdnValue::Symbol("?_rule_value".to_string()), - ) - } - 2 => { - #[allow(clippy::indexing_slicing)] - let entity = resolved_args[0].clone(); - #[allow(clippy::indexing_slicing)] - let value = resolved_args[1].clone(); - Pattern::new( - entity, - EdnValue::Keyword(format!(":{}", predicate)), - value, - ) - } - _ => return None, - }; - Some(crate::query::datalog::evaluator::substitute_pattern( - &pattern, binding, - )) - } - _ => None, - }) - .collect(); - - // Compute not_bindings: if no patterns, seed with current binding. - let m = PatternMatcher::from_slice_with_valid_at( - derived_facts.clone(), - valid_at_value.clone(), - ); - let mut not_bindings: Vec = if substituted.is_empty() { - vec![binding.clone()] - } else { - m.match_patterns(&substituted) - .into_iter() - .map(|mut nb| { - for (k, v) in binding { - nb.entry(k.clone()).or_insert_with(|| v.clone()); - } - nb - }) - .collect() - }; - - // Apply Expr clauses from the not body. - // Errors (e.g. unknown UDF predicate) are treated as "no match". - not_bindings = apply_expr_clauses(not_bindings, not_body, ®istry) - .unwrap_or_default(); - if !not_bindings.is_empty() { - return false; // not condition violated - } - } - // Use the already-acquired registry instead of re-acquiring the lock. - for (join_vars, nj_clauses) in ¬_join_clauses { - if evaluate_not_join( - join_vars, - nj_clauses, - binding, - derived_facts.clone(), - ®istry, - ) { - return false; - } - } - true - }) - .collect() - }; + deferred_not_clauses.sort_by_key(optimizer::clause_cost); + for clause in deferred_not_clauses { + bindings = match clause { + WhereClause::Not(body) => apply_not_clause_derived( + bindings, + &body, + derived_facts.clone(), + valid_at_value.clone(), + ®istry, + ), + WhereClause::NotJoin { join_vars, clauses } => apply_not_join_clause_derived( + bindings, + &join_vars, + &clauses, + derived_facts.clone(), + ®istry, + ), + _ => bindings, + }; + } - let results = - apply_post_processing(not_filtered, &query.find, &query.with_vars, ®istry)?; + let results = apply_post_processing(bindings, &query.find, &query.with_vars, ®istry)?; Ok(QueryResult::QueryResults { vars: query.find.iter().map(|s| s.display_name()).collect(), @@ -1363,6 +1014,313 @@ fn not_body_matches( !not_bindings.is_empty() } +/// Filter `bindings` through a single `(not ...)` body, for the rule-free query path +/// (`execute_query`). Used both inline — as `plan()` pushes a `Not` clause to the +/// earliest position where its variables are bound — and for clauses `plan()` had to +/// defer (evaluated last, after Or/OrJoin, exactly as before push-down existed). +/// +/// Precomputes one exclusion set from the body's patterns (matched once against +/// `filtered_facts`, independent of `bindings`), then probes it per binding — same +/// fast path as the pre-#248 post-filter, just scoped to one clause at a time. +fn apply_not_clause( + bindings: Vec, + not_body: &[WhereClause], + filtered_facts: Arc<[Fact]>, + valid_at_value: Value, + registry: &FunctionRegistry, +) -> Vec { + let has_expr = not_body + .iter() + .any(|c| matches!(c, WhereClause::Expr { .. })); + let patterns: Vec = not_body + .iter() + .filter_map(|c| match c { + WhereClause::Pattern(p) => Some(p.clone()), + _ => None, + }) + .collect(); + + if patterns.is_empty() { + // Expr-only body: no pre-computation possible, fall back to per-binding eval. + return bindings + .into_iter() + .filter(|b| { + !not_body_matches( + not_body, + b, + filtered_facts.clone(), + valid_at_value.clone(), + registry, + ) + }) + .collect(); + } + + let matcher = + PatternMatcher::from_slice_with_valid_at(filtered_facts.clone(), valid_at_value.clone()); + let exclusion_set: std::collections::HashSet> = matcher + .match_patterns(&patterns) + .into_iter() + .map(|mut b| { + b.retain(|k, _| !k.starts_with("__f")); + let mut kv: Vec<(String, Value)> = b + .into_iter() + .map(|(k, v)| (k, normalize_value(&v))) + .collect(); + kv.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + kv + }) + .collect(); + + if exclusion_set.is_empty() && !has_expr { + // No excluding bindings anywhere — every outer binding is safe. + return bindings; + } + + bindings + .into_iter() + .filter(|binding| { + if !has_expr && let Some(sample) = exclusion_set.iter().next() { + let key: Vec<(String, Value)> = sample + .iter() + .filter_map(|(var, _)| { + binding + .get(var) + .map(|val| (var.clone(), normalize_value(val))) + }) + .collect(); + if key.len() == sample.len() { + return !exclusion_set.contains(&key); + } + // Outer binding is underspecified (fewer vars than the exclusion set + // key) — fall back to the slow path. + } + !not_body_matches( + not_body, + binding, + filtered_facts.clone(), + valid_at_value.clone(), + registry, + ) + }) + .collect() +} + +/// Filter `bindings` through a single `(not-join [...] ...)` body, for the rule-free +/// query path (`execute_query`). Mirrors [`apply_not_clause`] but keys the exclusion +/// set on `join_vars` (the subset actually bound in every body row) instead of all +/// body variables. +fn apply_not_join_clause( + bindings: Vec, + join_vars: &[String], + nj_clauses: &[WhereClause], + filtered_facts: Arc<[Fact]>, + valid_at_value: Value, + registry: &FunctionRegistry, +) -> Vec { + let has_expr = nj_clauses + .iter() + .any(|c| matches!(c, WhereClause::Expr { .. })); + let patterns: Vec = nj_clauses + .iter() + .filter_map(|c| match c { + WhereClause::Pattern(p) => Some(p.clone()), + _ => None, + }) + .collect(); + + if patterns.is_empty() { + return bindings + .into_iter() + .filter(|b| { + !evaluate_not_join(join_vars, nj_clauses, b, filtered_facts.clone(), registry) + }) + .collect(); + } + + let matcher = + PatternMatcher::from_slice_with_valid_at(filtered_facts.clone(), valid_at_value.clone()); + let body_bindings = matcher.match_patterns(&patterns); + + let key_vars: Vec = if body_bindings.is_empty() { + join_vars.to_vec() + } else { + join_vars + .iter() + .filter(|v| body_bindings.iter().all(|b| b.contains_key(*v))) + .cloned() + .collect() + }; + let exclusion_set: std::collections::HashSet> = body_bindings + .iter() + .map(|b| { + let mut kv: Vec<(String, Value)> = key_vars + .iter() + .filter_map(|v| b.get(v).map(|val| (v.clone(), normalize_value(val)))) + .collect(); + kv.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + kv + }) + .collect(); + + bindings + .into_iter() + .filter(|binding| { + if !has_expr { + if key_vars.is_empty() { + // Body bound no join vars: if exclusion set non-empty, the body + // always succeeds, so it excludes every outer binding. + return exclusion_set.is_empty(); + } + let mut key: Vec<(String, Value)> = key_vars + .iter() + .filter_map(|v| { + binding + .get(v) + .map(|val| (v.clone(), normalize_value(val))) + }) + .collect(); + key.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + if key.len() == key_vars.len() { + return !exclusion_set.contains(&key); + } + // Outer binding underspecified relative to the not-join body — fall + // back to the slow path so the body is correctly evaluated. + } + !evaluate_not_join(join_vars, nj_clauses, binding, filtered_facts.clone(), registry) + }) + .collect() +} + +/// Returns true if `not_body` is satisfied against `binding` (i.e. the outer binding +/// should be excluded) — for the rules query path (`execute_query_with_rules`), where +/// a `not` body may contain `WhereClause::RuleInvocation` against `derived_facts` +/// (all referenced rules are pre-evaluated by the `StratifiedEvaluator` before this +/// runs). No exclusion-set precomputation here: rule-invocation args are resolved +/// per binding, same as the pre-#248 post-filter. +fn not_clause_violated_via_rules( + not_body: &[WhereClause], + binding: &Binding, + derived_facts: Arc<[Fact]>, + valid_at_value: Value, + registry: &FunctionRegistry, +) -> bool { + use crate::query::datalog::evaluator::substitute_pattern; + + let substituted: Vec = not_body + .iter() + .filter_map(|c| match c { + WhereClause::Pattern(p) => Some(substitute_pattern(p, binding)), + WhereClause::RuleInvocation { predicate, args } => { + // Convert rule invocation to a pattern against derived storage. + // Apply the current binding to any variables in args first. + let resolved_args: Vec = args + .iter() + .map(|a| match a { + EdnValue::Symbol(s) if s.starts_with('?') => { + // Look up the bound value and convert back to EdnValue + binding + .get(s) + .map(|v| match v { + Value::Keyword(k) => EdnValue::Keyword(k.clone()), + Value::String(s) => EdnValue::String(s.clone()), + Value::Integer(i) => EdnValue::Integer(*i), + Value::Float(f) => EdnValue::Float(*f), + Value::Boolean(b) => EdnValue::Boolean(*b), + Value::Ref(u) => EdnValue::Uuid(*u), + Value::Null => EdnValue::Nil, + }) + .unwrap_or_else(|| a.clone()) + } + other => other.clone(), + }) + .collect(); + // Safety: match arms guarantee len()==1 or len()==2. + let pattern = match resolved_args.len() { + 1 => { + #[allow(clippy::indexing_slicing)] + let entity = resolved_args[0].clone(); + Pattern::new( + entity, + EdnValue::Keyword(format!(":{}", predicate)), + EdnValue::Symbol("?_rule_value".to_string()), + ) + } + 2 => { + #[allow(clippy::indexing_slicing)] + let entity = resolved_args[0].clone(); + #[allow(clippy::indexing_slicing)] + let value = resolved_args[1].clone(); + Pattern::new(entity, EdnValue::Keyword(format!(":{}", predicate)), value) + } + _ => return None, + }; + Some(substitute_pattern(&pattern, binding)) + } + _ => None, + }) + .collect(); + + let m = PatternMatcher::from_slice_with_valid_at(derived_facts.clone(), valid_at_value); + let mut not_bindings: Vec = if substituted.is_empty() { + vec![binding.clone()] + } else { + m.match_patterns(&substituted) + .into_iter() + .map(|mut nb| { + for (k, v) in binding { + nb.entry(k.clone()).or_insert_with(|| v.clone()); + } + nb + }) + .collect() + }; + + // Apply Expr clauses from the not body. Errors (e.g. unknown UDF predicate) are + // treated as "no match" so the outer row is kept (not-condition not violated). + not_bindings = apply_expr_clauses(not_bindings, not_body, registry).unwrap_or_default(); + !not_bindings.is_empty() +} + +/// Filter `bindings` through a single `(not ...)` body for the rules query path. +/// See [`not_clause_violated_via_rules`]. +fn apply_not_clause_derived( + bindings: Vec, + not_body: &[WhereClause], + derived_facts: Arc<[Fact]>, + valid_at_value: Value, + registry: &FunctionRegistry, +) -> Vec { + bindings + .into_iter() + .filter(|b| { + !not_clause_violated_via_rules( + not_body, + b, + derived_facts.clone(), + valid_at_value.clone(), + registry, + ) + }) + .collect() +} + +/// Filter `bindings` through a single `(not-join [...] ...)` body for the rules query +/// path — no exclusion-set fast path here (matches the pre-#248 post-filter, which +/// never had one for this path either). +fn apply_not_join_clause_derived( + bindings: Vec, + join_vars: &[String], + nj_clauses: &[WhereClause], + derived_facts: Arc<[Fact]>, + registry: &FunctionRegistry, +) -> Vec { + bindings + .into_iter() + .filter(|b| !evaluate_not_join(join_vars, nj_clauses, b, derived_facts.clone(), registry)) + .collect() +} + /// Extract plain variable values from bindings (non-aggregate path). fn extract_variables( bindings: Vec>, @@ -1386,14 +1344,6 @@ fn extract_variables( } type Binding = std::collections::HashMap; -/// Internal type alias for pre-computed not-body exclusion sets. -type NotExclusionEntry = Option<(bool, std::collections::HashSet>)>; -/// Internal type alias for pre-computed not-join exclusion sets. -type NotJoinExclusionEntry = Option<( - bool, - Vec, - std::collections::HashSet>, -)>; /// Unified post-processing: handles plain-variable extraction, aggregation, /// window functions, and mixed (aggregate + window) queries. @@ -1893,10 +1843,9 @@ pub(crate) fn apply_or_clauses( let sorted_or_branches: Vec<&Vec> = { #[cfg_attr(feature = "wasm", allow(unused_mut))] let mut b: Vec<&Vec> = branches.iter().collect(); - // Sort branches by cost ascending so cheaper branches evaluate first. + // Sort branches by cost ascending so cheaper branches evaluate first, + // maximizing the chance the short-circuit below fires early (#250). // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). - // Note: all branches still evaluated (no short-circuit); ordering is - // infrastructure for issue #250. #[cfg(not(feature = "wasm"))] b.sort_by_key(|br| optimizer::branch_cost(br)); b @@ -1948,6 +1897,15 @@ pub(crate) fn apply_or_clauses( let mut seen_keys: std::collections::HashSet> = std::collections::HashSet::new(); + // Variable names already bound in the incoming scope — used below to detect + // whether a branch introduces a *new* variable (#250 short-circuit gating). + #[cfg(not(feature = "wasm"))] + let incoming_var_names: std::collections::HashSet = bindings + .iter() + .flat_map(|b| b.keys().cloned()) + .filter(|k| !k.starts_with("__")) + .collect(); + for branch in &sorted_or_branches { let branch_result = evaluate_branch( branch, @@ -1970,6 +1928,57 @@ pub(crate) fn apply_or_clauses( union_bindings.push(b); } } + + // Short-circuit (#250): unlike or-join, a plain `or` branch's newly + // introduced variables DO survive into the merged result (see the + // `or_insert_with` merge below), so two branches matching the same + // shared key can legitimately produce different, both-needed rows. + // Skipping a branch is only safe when the branches evaluated so far + // introduce no variable beyond what's already bound in the incoming + // scope — i.e. this `or` is a pure filter (all branches bind the same + // new-var set per the parser's or-safety check), so any further match on + // an already-covered key would just re-derive an identical row. + #[cfg(not(feature = "wasm"))] + { + let branch_var_names: std::collections::HashSet<&str> = union_bindings + .iter() + .flat_map(|bb| bb.keys().map(|k| k.as_str())) + .filter(|k| !k.starts_with("__")) + .collect(); + let is_pure_filter = !branch_var_names.is_empty() + && branch_var_names + .iter() + .all(|v| incoming_var_names.contains(*v)); + if is_pure_filter { + let covered: std::collections::HashSet> = + union_bindings + .iter() + .map(|b| { + let mut k: Vec<(String, Value)> = branch_var_names + .iter() + .filter_map(|v| { + b.get(*v).map(|val| (v.to_string(), val.clone())) + }) + .collect(); + k.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + k + }) + .collect(); + let fully_covered = bindings.iter().all(|incoming| { + let mut k: Vec<(String, Value)> = branch_var_names + .iter() + .filter_map(|v| { + incoming.get(*v).map(|val| (v.to_string(), val.clone())) + }) + .collect(); + k.sort_unstable_by(|a, b| a.0.cmp(&b.0)); + covered.contains(&k) + }); + if fully_covered { + break; + } + } + } } // Determine shared variable names: variables present in both @@ -2049,10 +2058,9 @@ pub(crate) fn apply_or_clauses( let sorted_oj_branches: Vec<&Vec> = { #[cfg_attr(feature = "wasm", allow(unused_mut))] let mut b: Vec<&Vec> = branches.iter().collect(); - // Sort branches by cost ascending so cheaper branches evaluate first. + // Sort branches by cost ascending so cheaper branches evaluate first, + // maximizing the chance the short-circuit below fires early (#250). // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). - // Note: all branches still evaluated (no short-circuit); ordering is - // infrastructure for issue #250. #[cfg(not(feature = "wasm"))] b.sort_by_key(|br| optimizer::branch_cost(br)); b @@ -2070,9 +2078,28 @@ pub(crate) fn apply_or_clauses( } let empty_seed: Vec = vec![HashMap::new()]; - let mut projected: Vec = Vec::new(); let mut seen_proj: std::collections::HashSet> = std::collections::HashSet::new(); + let mut branch_map: HashMap, Vec> = HashMap::new(); + + // Distinct join_vars-keyed tuples required by the incoming bindings (#250). + // Every branch is projected to outer_keys below, which are all variables + // already bound before this or-join runs — a branch can never introduce a + // variable that survives into the result. So once every required key has at + // least one match, a further (costlier) branch matching that same key can + // only add a row identical to one already merged, which the dedup below + // would drop anyway — unlike plain `or`, this holds regardless of what the + // branch itself binds internally. + #[cfg(not(feature = "wasm"))] + let required_keys: std::collections::HashSet> = bindings + .iter() + .map(|incoming| { + join_vars + .iter() + .filter_map(|v| incoming.get(v).map(|val| (v.clone(), val.clone()))) + .collect::>() + }) + .collect(); for branch in &sorted_oj_branches { let branch_result = evaluate_branch( @@ -2094,19 +2121,18 @@ pub(crate) fn apply_or_clauses( b.iter().map(|(k, v)| (k.clone(), v.clone())).collect(); key.sort_unstable_by(|a, b| a.0.cmp(&b.0)); if seen_proj.insert(key) { - projected.push(b); + let bkey: Vec<(String, Value)> = join_vars + .iter() + .filter_map(|v| b.get(v).map(|val| (v.clone(), val.clone()))) + .collect(); + branch_map.entry(bkey).or_default().push(b); } } - } - // Build HashMap keyed on join_vars tuple. - let mut branch_map: HashMap, Vec> = HashMap::new(); - for b in projected { - let key: Vec<(String, Value)> = join_vars - .iter() - .filter_map(|v| b.get(v).map(|val| (v.clone(), val.clone()))) - .collect(); - branch_map.entry(key).or_default().push(b); + #[cfg(not(feature = "wasm"))] + if required_keys.iter().all(|k| branch_map.contains_key(k)) { + break; + } } let mut result: Vec = Vec::new(); diff --git a/src/query/datalog/optimizer.rs b/src/query/datalog/optimizer.rs index d769a9c078..dd8eb47635 100644 --- a/src/query/datalog/optimizer.rs +++ b/src/query/datalog/optimizer.rs @@ -117,23 +117,64 @@ fn pattern_bound_vars(p: &Pattern) -> Vec { vars } +/// Collect all logic-variable names referenced anywhere within a slice of where +/// clauses — used to determine a `Not`/`NotJoin` clause's dependency on preceding +/// bindings. Walks `Pattern` positions, `Expr` trees (+ output binding), nested +/// `Not`/`NotJoin` bodies, and `RuleInvocation` arguments. +fn clause_ref_vars(clauses: &[WhereClause]) -> std::collections::HashSet { + let mut vars = std::collections::HashSet::new(); + for clause in clauses { + match clause { + WhereClause::Pattern(p) => vars.extend(pattern_bound_vars(p)), + WhereClause::Expr { expr, binding } => { + vars.extend(expr_vars(expr)); + if let Some(b) = binding { + vars.insert(b.clone()); + } + } + WhereClause::Not(inner) => vars.extend(clause_ref_vars(inner)), + WhereClause::NotJoin { clauses: inner, .. } => vars.extend(clause_ref_vars(inner)), + WhereClause::RuleInvocation { args, .. } => { + for a in args { + if let EdnValue::Symbol(s) = a + && s.starts_with('?') + { + vars.insert(s.clone()); + } + } + } + _ => {} + } + } + vars +} + /// Plan a list of where clauses: assign index hints to Pattern entries, push Expr /// entries to the earliest position where all their variables are bound by preceding -/// patterns, and (non-wasm) sort patterns by selectivity. +/// patterns, push `Not`/`NotJoin` entries to the earliest position where all their +/// required variables are bound by preceding patterns, and (non-wasm) sort patterns +/// by selectivity. +/// +/// `Pattern`, `Expr`, `Not`, and `NotJoin` variants may be passed in. `Or`, `OrJoin`, +/// and top-level `RuleInvocation` are handled by the executor and must not appear here. /// -/// Only `WhereClause::Pattern` and `WhereClause::Expr` variants should be passed in. -/// `Not`, `NotJoin`, `Or`, `OrJoin`, and `RuleInvocation` variants are handled by -/// the executor/evaluator and must not appear here. +/// A `Not`/`NotJoin` clause whose required variables (all body variables for `Not`; +/// `join_vars` for `NotJoin`) are never fully bound by any prefix of the planned +/// patterns is returned in the second element (`deferred`) rather than being placed — +/// it depends on a binding source outside this clause list (e.g. an `Or`/`OrJoin` +/// clause, which the executor applies after this plan) and must be evaluated by the +/// executor's post-filter instead, to avoid running it before its dependency is bound. /// -/// Returns an interleaved `Vec<(WhereClause, Option)>` where Pattern entries -/// carry `Some(hint)` and Expr entries carry `None`. +/// Returns `(interleaved, deferred)` where `interleaved` pairs each Pattern with +/// `Some(hint)` and each Expr/Not/NotJoin with `None`. pub fn plan( clauses: Vec, _indexes: &crate::storage::index::Indexes, -) -> Vec<(WhereClause, Option)> { - // Separate into patterns (with hints) and exprs. +) -> (Vec<(WhereClause, Option)>, Vec) { + // Separate into patterns (with hints), exprs, and not/not-join clauses. let mut patterns: Vec<(WhereClause, IndexHint)> = Vec::new(); let mut exprs: Vec = Vec::new(); + let mut not_clauses: Vec = Vec::new(); for clause in clauses { match &clause { @@ -142,6 +183,7 @@ pub fn plan( patterns.push((clause, hint)); } WhereClause::Expr { .. } => exprs.push(clause), + WhereClause::Not(_) | WhereClause::NotJoin { .. } => not_clauses.push(clause), // Other variants must not be passed to plan(); silently skip. _ => {} } @@ -193,7 +235,52 @@ pub fn plan( result.insert(insert_pos, (expr_clause, None)); } - result + // Sort not/not-join clauses cheapest-first — tie-break for clauses that land at + // the same insertion point, mirroring the executor's previous post-filter ordering. + #[cfg(not(feature = "wasm"))] + not_clauses.sort_by_key(clause_cost); + + let mut deferred: Vec = Vec::new(); + for nc in not_clauses { + let required: std::collections::HashSet = match &nc { + WhereClause::Not(body) => clause_ref_vars(body), + WhereClause::NotJoin { join_vars, .. } => join_vars + .iter() + .filter(|v| !v.starts_with("?_")) + .cloned() + .collect(), + // Unreachable: only Not/NotJoin are pushed into not_clauses above. + _ => Default::default(), + }; + + if required.is_empty() { + // No dependency on any binding — safe to run before everything else. + result.insert(0, (nc, None)); + continue; + } + + let mut bound: std::collections::HashSet = Default::default(); + let mut insert_pos: Option = None; + for (pos, (clause, _)) in result.iter().enumerate() { + if let WhereClause::Pattern(p) = clause { + bound.extend(pattern_bound_vars(p)); + if required.is_subset(&bound) { + insert_pos = Some(pos + 1); + break; + } + } + } + + match insert_pos { + Some(pos) => result.insert(pos, (nc, None)), + // Required variables are never fully bound by these patterns alone — the + // clause depends on a binding source outside this plan (e.g. Or/OrJoin). + // Defer to the executor's post-filter, which runs after that dependency. + None => deferred.push(nc), + } + } + + (result, deferred) } /// Static 4-tier cardinality estimate for a single pattern. @@ -341,7 +428,7 @@ mod tests { let p2 = make_pattern(entity_lit(), kw(":name"), var("v")); // selectivity 2 (entity + attr) let p1_attr = p1.attribute.clone(); let p2_attr = p2.attribute.clone(); - let planned = plan( + let (planned, _deferred) = plan( vec![WhereClause::Pattern(p1), WhereClause::Pattern(p2)], &Indexes::new(), ); @@ -425,7 +512,7 @@ mod tests { { use crate::storage::index::Indexes; let p = WhereClause::Pattern(make_pattern(var("e"), kw(":val"), var("v"))); - let planned = plan(vec![p], &Indexes::new()); + let (planned, _deferred) = plan(vec![p], &Indexes::new()); assert!( planned[0].1.is_some(), "Pattern entry must carry Some(IndexHint)" @@ -443,7 +530,7 @@ mod tests { expr: Expr::Lit(Value::Boolean(true)), binding: None, }; - let planned = plan(vec![p, expr], &Indexes::new()); + let (planned, _deferred) = plan(vec![p, expr], &Indexes::new()); let expr_entry = planned .iter() .find(|(c, _)| matches!(c, WhereClause::Expr { .. })); @@ -473,7 +560,7 @@ mod tests { ), binding: None, }; - let planned = plan(vec![p1, p2, p3, expr], &Indexes::new()); + let (planned, _deferred) = plan(vec![p1, p2, p3, expr], &Indexes::new()); assert_eq!(planned.len(), 4); // Item at index 2 must be the Expr (pushed after p2 which binds ?v at index 1). assert!( @@ -496,7 +583,7 @@ mod tests { expr: Expr::Lit(Value::Boolean(true)), binding: None, }; - let planned = plan(vec![p1, expr], &Indexes::new()); + let (planned, _deferred) = plan(vec![p1, expr], &Indexes::new()); assert_eq!(planned.len(), 2); assert!( matches!(planned[1].0, WhereClause::Expr { .. }), @@ -518,7 +605,7 @@ mod tests { ), binding: None, }; - let planned = plan(vec![p1, expr], &Indexes::new()); + let (planned, _deferred) = plan(vec![p1, expr], &Indexes::new()); assert_eq!(planned.len(), 2); assert!( matches!(planned[1].0, WhereClause::Expr { .. }), @@ -526,6 +613,117 @@ mod tests { ); } + // ── Not/NotJoin push-down (#248) ───────────────────────────────────── + + #[cfg(not(feature = "wasm"))] + #[test] + fn test_not_pushed_after_binding_pattern() { + use crate::storage::index::Indexes; + // p1 binds ?e/?n, p2 binds ?e/?v. Not body needs ?v, bound at p2 (pos 1). + // Expected: [p1, p2, not, p3]. + let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":name"), var("n"))); + let p2 = WhereClause::Pattern(make_pattern(var("e"), kw(":val"), var("v"))); + let p3 = WhereClause::Pattern(make_pattern(var("e"), kw(":dept"), var("d"))); + let not_clause = WhereClause::Not(vec![WhereClause::Pattern(make_pattern( + var("v"), + kw(":flag"), + EdnValue::Boolean(true), + ))]); + let (planned, deferred) = plan(vec![p1, p2, p3, not_clause], &Indexes::new()); + assert_eq!(planned.len(), 4); + assert!(deferred.is_empty(), "not clause must be placeable"); + assert!( + matches!(planned[2].0, WhereClause::Not(_)), + "Not must be at index 2, right after the pattern binding ?v" + ); + assert!( + matches!(planned[3].0, WhereClause::Pattern(_)), + "p3 must be pushed after the not clause" + ); + } + + #[cfg(not(feature = "wasm"))] + #[test] + fn test_not_with_unbound_var_is_deferred() { + use crate::storage::index::Indexes; + // Not body references ?z, which no pattern in this list ever binds + // (e.g. it's bound only by an Or clause the executor applies afterward). + let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":name"), var("n"))); + let not_clause = WhereClause::Not(vec![WhereClause::Pattern(make_pattern( + var("z"), + kw(":flag"), + EdnValue::Boolean(true), + ))]); + let (planned, deferred) = plan(vec![p1, not_clause.clone()], &Indexes::new()); + assert_eq!(planned.len(), 1, "unplaceable not clause must not appear in planned list"); + assert_eq!(deferred.len(), 1, "unplaceable not clause must be deferred"); + assert_eq!(deferred[0], not_clause); + } + + #[cfg(not(feature = "wasm"))] + #[test] + fn test_not_join_pushed_to_correct_position() { + use crate::storage::index::Indexes; + // not-join requires only ?e bound (join_vars), which p1 binds at pos 0. + // A local existential ?x inside the body is NOT required from the outer scope. + let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":name"), var("n"))); + let p2 = WhereClause::Pattern(make_pattern(var("e"), kw(":val"), var("v"))); + let nj = WhereClause::NotJoin { + join_vars: vec!["?e".to_string()], + clauses: vec![WhereClause::Pattern(make_pattern( + var("e"), + kw(":blocked-by"), + var("x"), + ))], + }; + let (planned, deferred) = plan(vec![p1, p2, nj], &Indexes::new()); + assert_eq!(planned.len(), 3); + assert!(deferred.is_empty()); + assert!( + matches!(planned[1].0, WhereClause::NotJoin { .. }), + "NotJoin must be placed right after the pattern binding ?e (index 0)" + ); + } + + #[cfg(not(feature = "wasm"))] + #[test] + fn test_not_join_unbound_join_var_is_deferred() { + use crate::storage::index::Indexes; + let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":name"), var("n"))); + let nj = WhereClause::NotJoin { + join_vars: vec!["?missing".to_string()], + clauses: vec![WhereClause::Pattern(make_pattern( + var("missing"), + kw(":blocked-by"), + var("x"), + ))], + }; + let (planned, deferred) = plan(vec![p1, nj], &Indexes::new()); + assert_eq!(planned.len(), 1); + assert_eq!(deferred.len(), 1, "not-join with unbound join var must be deferred"); + } + + #[cfg(not(feature = "wasm"))] + #[test] + fn test_not_with_no_required_vars_goes_first() { + use crate::storage::index::Indexes; + // Not body is fully self-contained (no outer vars referenced) — safe to run + // before every pattern. + let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":name"), var("n"))); + let not_clause = WhereClause::Not(vec![WhereClause::Pattern(make_pattern( + entity_lit(), + kw(":flag"), + EdnValue::Boolean(true), + ))]); + let (planned, deferred) = plan(vec![p1, not_clause], &Indexes::new()); + assert_eq!(planned.len(), 2); + assert!(deferred.is_empty()); + assert!( + matches!(planned[0].0, WhereClause::Not(_)), + "Not clause with no required vars must be placed first" + ); + } + // ── cost model tests ────────────────────────────────────────────────── // These tests call pattern_cost / branch_cost / clause_cost which are // unconditional (available on all targets). diff --git a/tests/disjunction_test.rs b/tests/disjunction_test.rs index 14d1d6f74e..db20805c45 100644 --- a/tests/disjunction_test.rs +++ b/tests/disjunction_test.rs @@ -1,6 +1,8 @@ //! Integration tests for Phase 7.3: or / or-join disjunction. -use minigraf::{Minigraf, OpenOptions, QueryResult}; +use minigraf::{Minigraf, OpenOptions, QueryResult, Value}; +use std::sync::Arc; +use std::sync::atomic::{AtomicUsize, Ordering}; fn db() -> Minigraf { OpenOptions::new().open_memory().unwrap() @@ -379,3 +381,211 @@ fn test_or_join_does_not_return_duplicate_bindings() { "or-join entity matching both branches must appear exactly once" ); } + +// ── Issue #250: short-circuit or/or-join branch evaluation ───────────────── + +/// (19) or-join short-circuit is always safe (branches are projected to outer_keys +/// before merging, so a branch can't smuggle in a new distinguishing variable): +/// once the cheap branch covers every incoming join-var key, the expensive branch +/// (guarded by a call-counting predicate) must never run. +#[test] +fn test_or_join_short_circuits_expensive_branch_when_fully_covered() { + let db = db(); + let calls = Arc::new(AtomicUsize::new(0)); + let calls_inner = calls.clone(); + db.register_predicate("expensive?", move |_v: &Value| { + calls_inner.fetch_add(1, Ordering::SeqCst); + true + }) + .unwrap(); + + // e1 also has :flag true — if the expensive branch actually ran (i.e. the + // short-circuit didn't fire), it would match e1 and invoke the counter, even + // though e1 is already covered by the cheap branch. Without this overlap, the + // expensive branch's own pattern would match nothing regardless of whether it + // runs, and the `calls == 0` assertion below would pass vacuously. + db.execute( + r#"(transact [[:e1 :cheap true] [:e1 :flag true] [:e2 :cheap true] [:e3 :cheap true]])"#, + ) + .unwrap(); + + let r = db + .execute( + r#"(query [:find ?e + :where [?e ?_a ?_v] + (or-join [?e] + [?e :cheap true] + (and [?e :flag true] [(expensive? ?e)]))])"#, + ) + .unwrap(); + + assert_eq!( + result_count(&r), + 3, + "all three entities match via the cheap branch alone" + ); + assert_eq!( + calls.load(Ordering::SeqCst), + 0, + "expensive branch must be skipped once the cheap branch covers every group" + ); +} + +/// (20) or-join correctness when the cheap branch covers only some incoming keys: +/// the fallback branch must still run for the uncovered ones, and results must +/// include matches contributed by it. +#[test] +fn test_or_join_falls_back_to_expensive_branch_when_not_fully_covered() { + let db = db(); + let calls = Arc::new(AtomicUsize::new(0)); + let calls_inner = calls.clone(); + db.register_predicate("expensive?", move |_v: &Value| { + calls_inner.fetch_add(1, Ordering::SeqCst); + true + }) + .unwrap(); + + db.execute(r#"(transact [[:e1 :cheap true] [:e2 :flag true]])"#) + .unwrap(); + + let r = db + .execute( + r#"(query [:find ?e + :where [?e ?_a ?_v] + (or-join [?e] + [?e :cheap true] + (and [?e :flag true] [(expensive? ?e)]))])"#, + ) + .unwrap(); + + assert_eq!( + result_count(&r), + 2, + "e1 via the cheap branch, e2 via the fallback branch" + ); + assert!( + calls.load(Ordering::SeqCst) >= 1, + "fallback branch must run for the group the cheap branch didn't cover" + ); +} + +/// (20b) Proves branch reordering itself (not declaration order) drives the skip: +/// the expensive branch is declared FIRST, but has a genuinely higher `branch_cost` +/// (a 1-bound pattern, cost 100) than the cheap branch (which pairs a 2-bound +/// pattern with an unrelated fully-bound one, so `branch_cost`'s min-over-patterns +/// is 1). If `branch_cost`-based sorting were broken (e.g. reverted to declaration +/// order), the expensive branch — written first — would run before coverage is +/// established and invoke the counter. +#[test] +fn test_or_join_short_circuit_relies_on_cost_sort_not_declaration_order() { + let db = db(); + let calls = Arc::new(AtomicUsize::new(0)); + let calls_inner = calls.clone(); + db.register_predicate("expensive?", move |_v: &Value| { + calls_inner.fetch_add(1, Ordering::SeqCst); + true + }) + .unwrap(); + + // :tracked seeds exactly {e1, e2, e3} as the incoming set — deliberately not + // `[?e ?_a ?_v]`, which would also pull in :marker-ent (it has its own fact) + // and produce two incoming rows for e1 (one per fact), muddying the coverage + // check this test is actually after. + db.execute( + r#"(transact [ + [:e1 :tracked true] [:e1 :cheap true] [:e1 :flag true] + [:e2 :tracked true] [:e2 :cheap true] + [:e3 :tracked true] [:e3 :cheap true] + [:marker-ent :m true] + ])"#, + ) + .unwrap(); + + let r = db + .execute( + r#"(query [:find ?e + :where [?e :tracked true] + (or-join [?e] + (and [?e ?attr true] [(expensive? ?e)]) + (and [?e :cheap true] [:marker-ent :m true]))])"#, + ) + .unwrap(); + + assert_eq!( + result_count(&r), + 3, + "all three entities match via the cost-cheaper branch alone" + ); + assert_eq!( + calls.load(Ordering::SeqCst), + 0, + "the cost-100 branch must be sorted after the cost-1 branch and then skipped, \ + even though it appears first in the query text" + ); +} + +/// (21) Plain `or` short-circuits too, when it's a pure filter (no branch introduces +/// a variable beyond what's already bound in the incoming scope). +#[test] +fn test_or_short_circuits_pure_filter_when_fully_covered() { + let db = db(); + let calls = Arc::new(AtomicUsize::new(0)); + let calls_inner = calls.clone(); + db.register_predicate("expensive?", move |_v: &Value| { + calls_inner.fetch_add(1, Ordering::SeqCst); + true + }) + .unwrap(); + + db.execute( + r#"(transact [[:e1 :status :active] [:e2 :status :active] [:e3 :flag true]])"#, + ) + .unwrap(); + + let r = db + .execute( + r#"(query [:find ?e + :where [?e :status ?_s] + (or [?e :status :active] + (and [?e :flag true] [(expensive? ?e)]))])"#, + ) + .unwrap(); + + assert_eq!( + result_count(&r), + 2, + "e1 and e2 both match via the cheap branch alone" + ); + assert_eq!( + calls.load(Ordering::SeqCst), + 0, + "expensive branch must be skipped once the cheap branch covers every incoming entity" + ); +} + +/// (22) Correctness guard: a plain `or` whose branches introduce a *new* variable +/// must never short-circuit, even if every incoming key is already "covered" by the +/// cheaper branch — a later branch can legitimately bind that new variable to a +/// different value for the same shared key, and dropping it would silently lose a +/// valid result row. This is the scenario that makes `or` (unlike `or-join`) unsafe +/// to skip on coverage alone. +#[test] +fn test_or_never_skips_branches_that_introduce_new_variables() { + let db = db(); + db.execute(r#"(transact [[:e1 :id true] [:e1 :typeA :va] [:e1 :typeB :vb]])"#) + .unwrap(); + + let r = db + .execute( + r#"(query [:find ?e ?v + :where [?e :id true] + (or [?e :typeA ?v] [?e :typeB ?v])])"#, + ) + .unwrap(); + + assert_eq!( + result_count(&r), + 2, + "both branches must contribute a row for ?e=:e1, since ?v differs between them" + ); +} From 735dbbd10a074d55585b17aac2c063475535d1a4 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Mon, 24 Aug 2026 09:47:20 +0530 Subject: [PATCH 2/3] style: cargo fmt Co-Authored-By: Claude Sonnet 5 Claude-Session: https://claude.ai/code/session_01YMWSutMLJJ7Y5b8hs9ZaCU --- src/query/datalog/executor.rs | 14 ++++++++------ src/query/datalog/optimizer.rs | 12 ++++++++++-- tests/disjunction_test.rs | 6 ++---- 3 files changed, 20 insertions(+), 12 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 9667521f9f..0bd7561051 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -1174,11 +1174,7 @@ fn apply_not_join_clause( } let mut key: Vec<(String, Value)> = key_vars .iter() - .filter_map(|v| { - binding - .get(v) - .map(|val| (v.clone(), normalize_value(val))) - }) + .filter_map(|v| binding.get(v).map(|val| (v.clone(), normalize_value(val)))) .collect(); key.sort_unstable_by(|a, b| a.0.cmp(&b.0)); if key.len() == key_vars.len() { @@ -1187,7 +1183,13 @@ fn apply_not_join_clause( // Outer binding underspecified relative to the not-join body — fall // back to the slow path so the body is correctly evaluated. } - !evaluate_not_join(join_vars, nj_clauses, binding, filtered_facts.clone(), registry) + !evaluate_not_join( + join_vars, + nj_clauses, + binding, + filtered_facts.clone(), + registry, + ) }) .collect() } diff --git a/src/query/datalog/optimizer.rs b/src/query/datalog/optimizer.rs index dd8eb47635..b7a6409794 100644 --- a/src/query/datalog/optimizer.rs +++ b/src/query/datalog/optimizer.rs @@ -655,7 +655,11 @@ mod tests { EdnValue::Boolean(true), ))]); let (planned, deferred) = plan(vec![p1, not_clause.clone()], &Indexes::new()); - assert_eq!(planned.len(), 1, "unplaceable not clause must not appear in planned list"); + assert_eq!( + planned.len(), + 1, + "unplaceable not clause must not appear in planned list" + ); assert_eq!(deferred.len(), 1, "unplaceable not clause must be deferred"); assert_eq!(deferred[0], not_clause); } @@ -700,7 +704,11 @@ mod tests { }; let (planned, deferred) = plan(vec![p1, nj], &Indexes::new()); assert_eq!(planned.len(), 1); - assert_eq!(deferred.len(), 1, "not-join with unbound join var must be deferred"); + assert_eq!( + deferred.len(), + 1, + "not-join with unbound join var must be deferred" + ); } #[cfg(not(feature = "wasm"))] diff --git a/tests/disjunction_test.rs b/tests/disjunction_test.rs index db20805c45..43f1dde561 100644 --- a/tests/disjunction_test.rs +++ b/tests/disjunction_test.rs @@ -537,10 +537,8 @@ fn test_or_short_circuits_pure_filter_when_fully_covered() { }) .unwrap(); - db.execute( - r#"(transact [[:e1 :status :active] [:e2 :status :active] [:e3 :flag true]])"#, - ) - .unwrap(); + db.execute(r#"(transact [[:e1 :status :active] [:e2 :status :active] [:e3 :flag true]])"#) + .unwrap(); let r = db .execute( From 26a5ea034c0e5662d1ee71caac4197c141419ff7 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Mon, 24 Aug 2026 10:10:37 +0530 Subject: [PATCH 3/3] fix: correct Not clause cost ordering and wildcard-var handling in push-down Two nits from ultrareview on PR #344: - Not/NotJoin clauses landing at the same insertion point came out in reverse cost order, since each result.insert(pos, ..) shifts an already-inserted clause one slot later. Sorting descending by cost before inserting corrects this (the insertion reversal then produces the intended ascending/cheapest-first order). - The Not arm's required-variable computation didn't exempt `?_`-prefixed wildcard vars, unlike the NotJoin arm and the parser's own outer_vars_from_clause. A `(not [?e :attr ?_x])` body was deferred to the post-filter as if ?_x needed to be bound by an outer clause, even though the wildcard convention means it never does. Co-Authored-By: Claude Sonnet 5 Claude-Session: https://claude.ai/code/session_01YMWSutMLJJ7Y5b8hs9ZaCU --- src/query/datalog/optimizer.rs | 91 ++++++++++++++++++++++++++++++++-- 1 file changed, 87 insertions(+), 4 deletions(-) diff --git a/src/query/datalog/optimizer.rs b/src/query/datalog/optimizer.rs index b7a6409794..ed4e959c2a 100644 --- a/src/query/datalog/optimizer.rs +++ b/src/query/datalog/optimizer.rs @@ -235,15 +235,25 @@ pub fn plan( result.insert(insert_pos, (expr_clause, None)); } - // Sort not/not-join clauses cheapest-first — tie-break for clauses that land at - // the same insertion point, mirroring the executor's previous post-filter ordering. + // Sort not/not-join clauses most-expensive-first: each `result.insert(pos, ..)` + // below shifts an already-inserted clause at the same `pos` one slot later, so + // processing in descending cost order lands the cheapest clause at `pos` last — + // i.e. final relative order at any shared insertion point comes out ascending + // (cheapest first), mirroring the executor's previous post-filter ordering. #[cfg(not(feature = "wasm"))] - not_clauses.sort_by_key(clause_cost); + not_clauses.sort_by_key(|c| std::cmp::Reverse(clause_cost(c))); let mut deferred: Vec = Vec::new(); for nc in not_clauses { let required: std::collections::HashSet = match &nc { - WhereClause::Not(body) => clause_ref_vars(body), + // `?_`-prefixed vars are the wildcard idiom (e.g. `(not [?e :attr ?_x])`) + // and never need to be bound by an outer clause — same convention the + // NotJoin arm below already applies to `join_vars`, and that + // `check_not_join_safety`/`outer_vars_from_clause` (parser.rs) apply. + WhereClause::Not(body) => clause_ref_vars(body) + .into_iter() + .filter(|v| !v.starts_with("?_")) + .collect(), WhereClause::NotJoin { join_vars, .. } => join_vars .iter() .filter(|v| !v.starts_with("?_")) @@ -732,6 +742,79 @@ mod tests { ); } + #[cfg(not(feature = "wasm"))] + #[test] + fn test_not_wildcard_var_does_not_block_placement() { + use crate::storage::index::Indexes; + // `?_x` is the wildcard idiom — it must not count as an outer dependency, + // matching the parser's own treatment of `?_`-prefixed vars (and the + // NotJoin arm's `join_vars` filter below). + let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":val"), var("v"))); + let p2 = WhereClause::Pattern(make_pattern(var("e"), kw(":other"), var("o"))); + let not_clause = WhereClause::Not(vec![WhereClause::Pattern(make_pattern( + var("e"), + kw(":name"), + var("_x"), + ))]); + let (planned, deferred) = plan(vec![p1, p2, not_clause], &Indexes::new()); + assert_eq!(planned.len(), 3); + assert!( + deferred.is_empty(), + "a Not body referencing only ?e (bound) and ?_x (wildcard) must be placeable" + ); + assert!( + matches!(planned[1].0, WhereClause::Not(_)), + "Not must be pushed right after the pattern binding ?e, not deferred to the end" + ); + } + + #[cfg(not(feature = "wasm"))] + #[test] + fn test_multiple_not_clauses_at_same_position_stay_cheapest_first() { + use crate::storage::index::Indexes; + // Both Not bodies need only ?e (bound by p1) and land at the same insertion + // point. The cheaper one (fully-bound pattern, cost 1) must end up before + // the more expensive one (2-bound pattern, cost 10) in the final plan. + let p1 = WhereClause::Pattern(make_pattern(var("e"), kw(":val"), var("v"))); + let expensive_not = WhereClause::Not(vec![WhereClause::Pattern(make_pattern( + var("e"), + kw(":flag"), + EdnValue::Boolean(true), + ))]); + // Two patterns so `branch_cost`'s min-over-patterns is dragged down to 1 by + // the fully-bound (unrelated) second pattern, while `clause_ref_vars` still + // only requires ?e (the unrelated pattern references no variables). + let cheap_not = WhereClause::Not(vec![ + WhereClause::Pattern(make_pattern( + var("e"), + kw(":other-flag"), + EdnValue::Boolean(true), + )), + WhereClause::Pattern(make_pattern(entity_lit(), kw(":marker"), str_val("x"))), + ]); + // Declared expensive-first, so a naive "preserve input order" bug wouldn't + // be masked by already-correct declaration order. + let (planned, deferred) = plan( + vec![p1, expensive_not.clone(), cheap_not.clone()], + &Indexes::new(), + ); + assert_eq!(planned.len(), 3); + assert!(deferred.is_empty()); + let cheap_pos = planned + .iter() + .position(|(c, _)| c == &cheap_not) + .expect("cheap not must be placed"); + let expensive_pos = planned + .iter() + .position(|(c, _)| c == &expensive_not) + .expect("expensive not must be placed"); + assert!( + cheap_pos < expensive_pos, + "cheaper Not clause must run before the more expensive one when both \ + land at the same insertion point" + ); + } + // ── cost model tests ────────────────────────────────────────────────── // These tests call pattern_cost / branch_cost / clause_cost which are // unconditional (available on all targets).