diff --git a/docs/superpowers/specs/2026-05-15-cost-based-optimizer-design.md b/docs/superpowers/specs/2026-05-15-cost-based-optimizer-design.md new file mode 100644 index 000000000..e972828a2 --- /dev/null +++ b/docs/superpowers/specs/2026-05-15-cost-based-optimizer-design.md @@ -0,0 +1,161 @@ +# Design: Cost-Based Optimizer Extensions (Wave 2 PR 2) + +**Issue**: #205 (cost-based optimizer extensions for new clause types) +**Date**: 2026-05-15 +**Branch**: single worktree + PR + +--- + +## Summary + +Extend `optimizer.rs` with a static cardinality cost model and use it to order `not`/`not-join` clauses and `or`/`or-join` branches by estimated evaluation cost. Cheap filters run first; expensive ones only process the bindings that survived earlier filters. + +Aggregation post-processing cost estimation is **out of scope** — aggregation always runs last and cannot be reordered. + +Follow-up issue for Or short-circuit optimization (which builds on this cost model): #250. + +--- + +## Current Behaviour + +- `not`/`not-join` clauses are applied in source order — an expensive not-clause that scans many facts runs before a cheap one, wasting work on bindings that would have been rejected cheaply. +- `or`/`or-join` branches are evaluated in source order — no cost-based selection. +- The optimizer has no concept of cost for clause types other than `Pattern` and `Expr`. + +--- + +## Design + +### 1. Cost model — `optimizer.rs` + +#### `pattern_cost(p: &Pattern) -> u64` (private) + +Static 4-tier model derived from the existing `selectivity_score()`: + +| Bound EAV components | Cost | +|---|---| +| 3 (all bound) | 1 | +| 2 | 10 | +| 1 | 100 | +| 0 (nothing bound) | 10,000 | + +#### `pub fn clause_cost(clause: &WhereClause) -> u64` + +| Clause type | Cost formula | +|---|---| +| `Pattern(p)` | `pattern_cost(p)` | +| `Expr { .. }` | 0 (pure computation, no fact scan) | +| `Not(body)` | `min(pattern_cost(p) for p in body patterns)`, or 0 if body has no patterns | +| `NotJoin { clauses, .. }` | same as `Not` using `clauses` | +| `Or(branches)` | `sum(branch_cost(b) for b in branches)` | +| `OrJoin { branches, .. }` | same as `Or` | +| other | `u64::MAX` (never passed; defensive) | + +#### `pub fn branch_cost(branch: &[WhereClause]) -> u64` + +`min(pattern_cost(p) for p in branch patterns)`, or 0 if branch has no patterns. + +**Rationale for `min` in not/or bodies**: In a multi-pattern join, the most selective pattern (lowest cardinality) dominates — the join can never produce more rows than the smallest input. Using `min` avoids overestimating the cost of a body that contains at least one highly selective pattern. + +**WASM behaviour**: `clause_cost()` and `branch_cost()` are unconditional (available on all targets). The *sorting* call sites are gated behind `#[cfg(not(feature = "wasm"))]`, consistent with the existing pattern ordering gate. + +--- + +### 2. Executor changes — `executor.rs` + +#### `not`/`not-join` ordering + +In both `execute_query()` and `execute_query_with_rules()`, after extracting `not_clauses` and `not_join_clauses` and before the filter loop, sort each by `clause_cost()` ascending: + +```rust +// 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.clone()))); + +// WASM omission: small datasets + determinism — see optimizer::selectivity_score(). +#[cfg(not(feature = "wasm"))] +not_join_clauses.sort_by_key(|(vars, body)| { + optimizer::clause_cost(&WhereClause::NotJoin { + join_vars: vars.clone(), + clauses: body.clone(), + }) +}); +``` + +**Effect**: Cheap not-filters run first. Bindings rejected by a cheap filter never reach more expensive filters. No change to semantics. + +#### `or`/`or-join` branch ordering + +In `apply_or_clauses()`, before evaluating branches in both the fast path (no Not in branches) and the slow path (seeded), sort branches by `branch_cost()` ascending: + +```rust +// WASM omission: small datasets + determinism — see optimizer::selectivity_score(). +// Note: all branches are still evaluated (no short-circuit); this ordering is +// infrastructure for #250. See that issue for the short-circuit optimization. +#[cfg(not(feature = "wasm"))] +let sorted_branches: Vec<_> = { + let mut b = branches.to_vec(); + b.sort_by_key(|br| optimizer::branch_cost(br)); + b +}; +// iterate sorted_branches instead of branches +``` + +--- + +### 3. Evaluator changes — `evaluator.rs` + +The `StratifiedEvaluator` mixed-rules loop applies `not`/`not-join` as post-filters in the `'binding:` loop. After extracting `not_clauses` and `not_join_clauses` (which already happens before the `'binding:` loop), sort both collections by `clause_cost()` ascending: + +```rust +// 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.clone()))); + +// 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(), + }) +}); +``` + +--- + +### 4. Testing + +**`optimizer.rs` unit tests** — `clause_cost()` and `branch_cost()`: +- Fully-bound pattern → cost 1 +- 2-bound pattern → cost 10 +- 1-bound pattern → cost 100 +- Unbound pattern → cost 10,000 +- `Not` body: one selective + one full-scan pattern → cost = 1 (min) +- `Not` body with no patterns (expr-only) → cost 0 +- `Or` with two branches → cost = sum of branch min-costs +- `branch_cost` of empty branch → 0 + +**`executor.rs` integration tests** — not ordering: +- Query with two `not` clauses in expensive-first source order → results identical to cheap-first order (correctness regression guard) +- Query with two `not` clauses where cheap one eliminates most bindings → results correct + +**Validation**: The existing `bench_negation` group in `benches/minigraf_bench.rs` provides the baseline for measuring `not`-ordering improvement. No new benchmark group is added in this PR. + +--- + +## Invariants Preserved + +- **Correctness**: Sorting only changes evaluation order, never the set of bindings that satisfy a clause. The `not` filter is semantically commutative when applied to independent not-bodies over the same outer binding set. +- **WASM portability**: Cost functions unconditional; sorting gated behind `#[cfg(not(feature = "wasm"))]`. +- **Backwards compatibility**: No change to `plan()` signature or return type. `clause_cost()` and `branch_cost()` are new public additions. + +--- + +## Files Changed + +| File | Change | +|------|--------| +| `src/query/datalog/optimizer.rs` | New `pattern_cost()`, `clause_cost()`, `branch_cost()` | +| `src/query/datalog/executor.rs` | Cost-sorted `not_clauses`, `not_join_clauses` in both query functions; cost-sorted branches in `apply_or_clauses()` | +| `src/query/datalog/evaluator.rs` | Cost-sorted `not_clauses`, `not_join_clauses` in mixed-rules loop | diff --git a/src/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index 0e6a6a52e..5de1ce537 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -766,7 +766,8 @@ impl StratifiedEvaluator { } } - let not_clauses: Vec> = rule + #[cfg_attr(feature = "wasm", allow(unused_mut))] + let mut not_clauses: Vec> = rule .body .iter() .filter_map(|c| match c { @@ -775,7 +776,8 @@ impl StratifiedEvaluator { }) .collect(); - let not_join_clauses: Vec<(Vec, Vec)> = rule + #[cfg_attr(feature = "wasm", allow(unused_mut))] + let mut not_join_clauses: Vec<(Vec, Vec)> = rule .body .iter() .filter_map(|c| match c { @@ -786,6 +788,20 @@ impl StratifiedEvaluator { }) .collect(); + // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + #[cfg(not(feature = "wasm"))] + not_clauses.sort_by_key(|body| { + crate::query::datalog::optimizer::clause_cost(&WhereClause::Not(body.clone())) + }); + // WASM omission: small datasets + determinism — see optimizer::selectivity_score(). + #[cfg(not(feature = "wasm"))] + not_join_clauses.sort_by_key(|(vars, clauses)| { + crate::query::datalog::optimizer::clause_cost(&WhereClause::NotJoin { + join_vars: vars.clone(), + clauses: clauses.clone(), + }) + }); + // Compute once; reuse for plan loop, apply_or_clauses, not-body matching. let accumulated_facts: Arc<[Fact]> = Arc::from(accumulated.get_asserted_facts()?); diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 77a074fee..a8d88405f 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -571,7 +571,8 @@ impl DatalogExecutor { // Apply not-filter for WhereClause::Not and WhereClause::NotJoin clauses // (no rules involved — pure post-filter) - let not_clauses: Vec<&Vec> = query + #[cfg_attr(feature = "wasm", allow(unused_mut))] + let mut not_clauses: Vec<&Vec> = query .where_clauses .iter() .filter_map(|c| match c { @@ -580,7 +581,8 @@ impl DatalogExecutor { }) .collect(); - let not_join_clauses: Vec<(Vec, Vec)> = query + #[cfg_attr(feature = "wasm", allow(unused_mut))] + let mut not_join_clauses: Vec<(Vec, Vec)> = query .where_clauses .iter() .filter_map(|c| match c { @@ -591,6 +593,18 @@ impl DatalogExecutor { }) .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(). + #[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 { @@ -1039,7 +1053,8 @@ impl DatalogExecutor { // 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.) - let not_clauses: Vec<&Vec> = query + #[cfg_attr(feature = "wasm", allow(unused_mut))] + let mut not_clauses: Vec<&Vec> = query .where_clauses .iter() .filter_map(|c| match c { @@ -1048,7 +1063,8 @@ impl DatalogExecutor { }) .collect(); - let not_join_clauses: Vec<(Vec, Vec)> = query + #[cfg_attr(feature = "wasm", allow(unused_mut))] + let mut not_join_clauses: Vec<(Vec, Vec)> = query .where_clauses .iter() .filter_map(|c| match c { @@ -1059,6 +1075,18 @@ impl DatalogExecutor { }) .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(). + #[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 { @@ -1830,10 +1858,21 @@ pub(crate) fn apply_or_clauses( for clause in clauses { match clause { WhereClause::Or(branches) => { + 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. + // 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 + }; // If any branch contains Not/NotJoin clauses (which need bound variables // from the outer scope to evaluate correctly), fall back to the classic // seeded-branch evaluation to preserve correctness. - let any_branch_has_not = branches.iter().any(|b| { + let any_branch_has_not = sorted_or_branches.iter().any(|b| { b.iter() .any(|c| matches!(c, WhereClause::Not(_) | WhereClause::NotJoin { .. })) }); @@ -1843,7 +1882,7 @@ pub(crate) fn apply_or_clauses( let mut seen: std::collections::HashSet> = std::collections::HashSet::new(); let mut result: Vec = Vec::new(); - for branch in branches { + for branch in &sorted_or_branches { let branch_result = evaluate_branch( branch, bindings.clone(), @@ -1877,7 +1916,7 @@ pub(crate) fn apply_or_clauses( let mut seen_keys: std::collections::HashSet> = std::collections::HashSet::new(); - for branch in branches { + for branch in &sorted_or_branches { let branch_result = evaluate_branch( branch, empty_seed.clone(), @@ -1975,6 +2014,17 @@ pub(crate) fn apply_or_clauses( join_vars, branches, } => { + 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. + // 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 + }; let outer_keys: std::collections::HashSet = bindings.iter().flat_map(|b| b.keys().cloned()).collect(); @@ -1992,7 +2042,7 @@ pub(crate) fn apply_or_clauses( let mut seen_proj: std::collections::HashSet> = std::collections::HashSet::new(); - for branch in branches { + for branch in &sorted_oj_branches { let branch_result = evaluate_branch( branch, empty_seed.clone(), @@ -5421,6 +5471,7 @@ mod or_hash_join_tests { #[cfg(test)] mod pushdown_tests { use crate::graph::FactStorage; + use crate::graph::types::Value; use crate::query::datalog::executor::{DatalogExecutor, QueryResult}; use crate::query::datalog::parser::parse_datalog_command; @@ -5518,4 +5569,51 @@ mod pushdown_tests { panic!("expected QueryResults"); } } + + #[test] + fn test_not_clause_ordering_correctness() { + // Two `not` clauses given in expensive-first source order; results must be + // identical regardless of which order the optimizer chooses to evaluate them. + // This is a correctness regression guard — semantics must not change. + let storage = FactStorage::new(); + let executor = DatalogExecutor::new(storage); + + // Transact 3 items: widget, gadget, doohickey + executor + .execute( + parse_datalog_command( + r#"(transact [[:item1 :item/name "widget"] + [:item2 :item/name "gadget"] + [:item3 :item/name "doohickey"]])"#, + ) + .unwrap(), + ) + .unwrap(); + + // Query: find items that are NOT "widget" AND NOT "gadget" + // Clauses are given in expensive-first order to exercise the cost-based sort. + let result = executor + .execute( + parse_datalog_command( + r#"(query [:find ?name + :where [?e :item/name ?name] + (not [?e :item/name "gadget"]) + (not [?e :item/name "widget"])])"#, + ) + .unwrap(), + ) + .unwrap(); + + match result { + QueryResult::QueryResults { results, .. } => { + assert_eq!(results.len(), 1, "only doohickey should pass"); + if let Value::String(ref s) = results[0][0] { + assert_eq!(s.as_str(), "doohickey", "result should be doohickey"); + } else { + panic!("expected a String value for the result"); + } + } + _ => panic!("expected QueryResults"), + } + } } diff --git a/src/query/datalog/optimizer.rs b/src/query/datalog/optimizer.rs index a741b984e..d769a9c07 100644 --- a/src/query/datalog/optimizer.rs +++ b/src/query/datalog/optimizer.rs @@ -39,6 +39,10 @@ fn attr_is_index_bound(a: &AttributeSpec) -> bool { /// Count the number of non-variable components in a pattern. /// Higher score = more selective. +/// +/// Gated on non-wasm: WASM/browser targets typically work with small datasets where +/// the overhead of computing scores and sorting can equal or exceed the benefit. +/// Source order is preserved on WASM for deterministic, debuggable query behaviour. #[cfg(not(feature = "wasm"))] fn selectivity_score(p: &Pattern) -> u8 { let e = !is_variable(&p.entity); @@ -145,6 +149,7 @@ pub fn plan( // Stable sort patterns by selectivity descending (non-wasm only). // Preserves original order for ties, ensuring deterministic output. + // WASM omission: see selectivity_score() — small datasets, determinism. #[cfg(not(feature = "wasm"))] patterns.sort_by_key(|(clause, _)| { if let WhereClause::Pattern(p) = clause { @@ -191,6 +196,75 @@ pub fn plan( result } +/// Static 4-tier cardinality estimate for a single pattern. +/// +/// Derived from selectivity_score but returns u64 cost (lower = cheaper) rather +/// than a selectivity score. Available on all targets; on WASM the dead_code lint +/// is suppressed because the sorting call-sites are omitted there. +#[cfg_attr(feature = "wasm", allow(dead_code))] +fn pattern_cost(p: &Pattern) -> u64 { + let e = !is_variable(&p.entity); + let a = attr_is_index_bound(&p.attribute); + let v = !is_variable(&p.value); + match (e as u8) + (a as u8) + (v as u8) { + 3 => 1, + 2 => 10, + 1 => 100, + _ => 10_000, + } +} + +/// Estimated cost for a body/branch slice — the minimum `pattern_cost` across all +/// Pattern clauses, or 0 if the body contains no patterns (expr-only bodies are +/// cheap pure computation). +/// +/// Rationale for `min`: In a multi-pattern join the most selective pattern dominates — +/// the join cannot produce more rows than the smallest input. +/// +/// Available on all targets; on WASM the dead_code lint is suppressed because +/// the sorting call-sites are omitted there. +#[cfg_attr(feature = "wasm", allow(dead_code))] +pub fn branch_cost(branch: &[WhereClause]) -> u64 { + branch + .iter() + .filter_map(|c| { + if let WhereClause::Pattern(p) = c { + Some(pattern_cost(p)) + } else { + None + } + }) + .min() + .unwrap_or(0) +} + +/// Estimated evaluation cost for any `WhereClause`. +/// +/// | Clause type | Cost | +/// |--------------------|------| +/// | `Pattern` | `pattern_cost(p)` | +/// | `Expr` | 0 (pure computation) | +/// | `Not(body)` | `branch_cost(body)` | +/// | `NotJoin{clauses}` | `branch_cost(clauses)` | +/// | `Or(branches)` | sum of `branch_cost` per branch | +/// | `OrJoin{branches}` | sum of `branch_cost` per branch | +/// | other | `u64::MAX` (defensive; not expected in practice) | +/// +/// Available on all targets; on WASM the dead_code lint is suppressed because +/// the sorting call-sites are omitted there. +#[cfg_attr(feature = "wasm", allow(dead_code))] +pub fn clause_cost(clause: &WhereClause) -> u64 { + match clause { + WhereClause::Pattern(p) => pattern_cost(p), + WhereClause::Expr { .. } => 0, + WhereClause::Not(body) => branch_cost(body), + WhereClause::NotJoin { clauses, .. } => branch_cost(clauses), + WhereClause::Or(branches) => branches.iter().map(|b| branch_cost(b)).sum(), + WhereClause::OrJoin { branches, .. } => branches.iter().map(|b| branch_cost(b)).sum(), + _ => u64::MAX, + } +} + #[cfg(test)] mod tests { use super::*; @@ -451,4 +525,196 @@ mod tests { "Expr with unbound var must be last" ); } + + // ── cost model tests ────────────────────────────────────────────────── + // These tests call pattern_cost / branch_cost / clause_cost which are + // unconditional (available on all targets). + + #[test] + fn test_pattern_cost_fully_bound() { + // entity bound (UUID), attribute real keyword, value bound literal — 3 bound → cost 1 + let p = Pattern::new( + EdnValue::Uuid(Uuid::new_v4()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::String("Alice".to_string()), + ); + assert_eq!(pattern_cost(&p), 1); + } + + #[test] + fn test_pattern_cost_two_bound() { + // attribute + value bound, entity variable — 2 bound → cost 10 + let p = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::String("Alice".to_string()), + ); + assert_eq!(pattern_cost(&p), 10); + } + + #[test] + fn test_pattern_cost_one_bound() { + // only attribute bound — 1 bound → cost 100 + let p = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::Symbol("?v".to_string()), + ); + assert_eq!(pattern_cost(&p), 100); + } + + #[test] + fn test_pattern_cost_unbound() { + // all variables — 0 bound → cost 10_000 + let p = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Symbol("?a".to_string()), + EdnValue::Symbol("?v".to_string()), + ); + assert_eq!(pattern_cost(&p), 10_000); + } + + #[test] + fn test_clause_cost_pattern_two_bound() { + // clause_cost delegates to pattern_cost for Pattern variant + // attr + value bound = 2 → cost 10 + let p = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::String("Alice".to_string()), + ); + assert_eq!(clause_cost(&WhereClause::Pattern(p)), 10); + } + + #[test] + fn test_clause_cost_expr_is_zero() { + // Expr is pure computation — cost 0 + let clause = WhereClause::Expr { + expr: Expr::Lit(Value::Integer(42)), + binding: None, + }; + assert_eq!(clause_cost(&clause), 0); + } + + #[test] + fn test_clause_cost_not_body_uses_min() { + // Not body: one cost-10 pattern + one cost-10_000 pattern → min = 10 + let selective = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::String("Alice".to_string()), + ); + let full_scan = Pattern::new( + EdnValue::Symbol("?x".to_string()), + EdnValue::Symbol("?a".to_string()), + EdnValue::Symbol("?v".to_string()), + ); + let clause = WhereClause::Not(vec![ + WhereClause::Pattern(selective), + WhereClause::Pattern(full_scan), + ]); + assert_eq!(clause_cost(&clause), 10); + } + + #[test] + fn test_clause_cost_not_body_expr_only_is_zero() { + // Not body with no patterns (expr only) → cost 0 + let clause = WhereClause::Not(vec![WhereClause::Expr { + expr: Expr::Lit(Value::Integer(1)), + binding: None, + }]); + assert_eq!(clause_cost(&clause), 0); + } + + #[test] + fn test_branch_cost_empty_branch() { + // Empty branch → 0 + assert_eq!(branch_cost(&[]), 0); + } + + #[test] + fn test_branch_cost_expr_only_is_zero() { + // Branch with only Expr clauses → 0 + let branch = vec![WhereClause::Expr { + expr: Expr::Lit(Value::Integer(99)), + binding: None, + }]; + assert_eq!(branch_cost(&branch), 0); + } + + #[test] + fn test_clause_cost_or_sums_branch_costs() { + // Or with two branches: + // branch 1: one pattern with cost 10 (attr+value bound) + // branch 2: one pattern with cost 100 (attr only bound) + // clause_cost(Or) = sum = 110 + let b1 = vec![WhereClause::Pattern(Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::String("Alice".to_string()), + ))]; + let b2 = vec![WhereClause::Pattern(Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/age".to_string()), + EdnValue::Symbol("?v".to_string()), + ))]; + let clause = WhereClause::Or(vec![b1, b2]); + assert_eq!(clause_cost(&clause), 110); // 10 + 100 + } + + #[test] + fn test_clause_cost_not_join_uses_branch_cost() { + // NotJoin with one selective pattern (cost 10) → cost 10 + let p = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::String("Alice".to_string()), + ); + let clause = WhereClause::NotJoin { + join_vars: vec!["?e".to_string()], + clauses: vec![WhereClause::Pattern(p)], + }; + assert_eq!(clause_cost(&clause), 10); + } + + #[test] + fn test_clause_cost_or_join_sums_branch_costs() { + // OrJoin with two branches: cost 10 + cost 100 = 110 + let b1 = vec![WhereClause::Pattern(Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::String("Alice".to_string()), + ))]; + let b2 = vec![WhereClause::Pattern(Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/age".to_string()), + EdnValue::Symbol("?v".to_string()), + ))]; + let clause = WhereClause::OrJoin { + join_vars: vec!["?e".to_string()], + branches: vec![b1, b2], + }; + assert_eq!(clause_cost(&clause), 110); + } + + #[test] + fn test_clause_cost_not_body_fully_bound_min_is_one() { + // Not body: one fully-bound pattern (cost 1) + one full-scan (cost 10_000) + // clause_cost → min = 1 + let fully_bound = Pattern::new( + EdnValue::Uuid(Uuid::new_v4()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::String("Alice".to_string()), + ); + let full_scan = Pattern::new( + EdnValue::Symbol("?x".to_string()), + EdnValue::Symbol("?a".to_string()), + EdnValue::Symbol("?v".to_string()), + ); + let clause = WhereClause::Not(vec![ + WhereClause::Pattern(full_scan), + WhereClause::Pattern(fully_bound), + ]); + assert_eq!(clause_cost(&clause), 1); + } }