corium_query/
plan.rs

1//! Clause ordering and index selection.
2//!
3//! Ordering is greedy selectivity ordering: start from the most selective
4//! bound pattern and repeatedly pick the cheapest runnable clause, using
5//! per-attribute statistics from the database. Explicit clause order is the
6//! tiebreak, matching the Datomic performance model users know.
7
8use std::collections::BTreeSet;
9
10use corium_core::IndexOrder;
11
12use crate::ast::{Clause, Term, Var, clause_vars};
13use crate::exec::ExecCtx;
14
15/// How a pattern scan is keyed.
16#[derive(Clone, Copy, Debug, Eq, PartialEq)]
17pub struct ScanChoice {
18    /// Chosen covering index.
19    pub order: IndexOrder,
20    /// Number of leading components bound into the scan prefix.
21    pub prefix_len: usize,
22}
23
24/// Picks the covering index and prefix length for one pattern lookup.
25///
26/// `avet_ok` says whether the bound attribute participates in AVET;
27/// `v_is_ref` whether the bound value is an entity reference.
28///
29/// A bound `a` never yields a full scan: AEVT (or AVET) always gives at
30/// least a one-component prefix — the property the roadmap requires.
31#[must_use]
32#[allow(clippy::fn_params_excessive_bools)]
33pub fn choose_index(
34    e_bound: bool,
35    a_bound: bool,
36    v_bound: bool,
37    avet_ok: bool,
38    v_is_ref: bool,
39) -> ScanChoice {
40    if e_bound {
41        let prefix_len = 1 + usize::from(a_bound) + usize::from(a_bound && v_bound);
42        return ScanChoice {
43            order: IndexOrder::Eavt,
44            prefix_len,
45        };
46    }
47    if a_bound {
48        if v_bound && avet_ok {
49            return ScanChoice {
50                order: IndexOrder::Avet,
51                prefix_len: 2,
52            };
53        }
54        // References are always covered by VAET: a bound ref value plus the
55        // attribute makes a two-component reverse-index prefix.
56        if v_bound && v_is_ref {
57            return ScanChoice {
58                order: IndexOrder::Vaet,
59                prefix_len: 2,
60            };
61        }
62        return ScanChoice {
63            order: IndexOrder::Aevt,
64            prefix_len: 1,
65        };
66    }
67    if v_bound && v_is_ref {
68        return ScanChoice {
69            order: IndexOrder::Vaet,
70            prefix_len: 1,
71        };
72    }
73    ScanChoice {
74        order: IndexOrder::Eavt,
75        prefix_len: 0,
76    }
77}
78
79/// Cost class, compared before magnitude: runnable filters first, then
80/// patterns by estimated fan-out, then rule calls, then `not`/`or` subplans
81/// and filters whose inputs are not yet bound. Classes keep semantics safe:
82/// negation and disjunction always run after every clause that could bind
83/// their variables.
84type Cost = (u8, usize);
85
86const CLASS_FILTER: u8 = 0;
87const CLASS_PATTERN: u8 = 1;
88const CLASS_RULE: u8 = 2;
89const CLASS_SUBPLAN: u8 = 3;
90
91/// Orders `clauses` for execution given the initially bound variables.
92///
93/// Returns indices into `clauses`. Predicates and functions run as soon as
94/// their inputs are bound; patterns are chosen by estimated fan-out;
95/// `not`/`or` run once their shared variables have had a chance to bind.
96#[must_use]
97pub fn order_clauses(
98    clauses: &[Clause],
99    initially_bound: &BTreeSet<Var>,
100    ctx: &ExecCtx<'_>,
101) -> Vec<usize> {
102    let mut bound = initially_bound.clone();
103    let mut remaining: Vec<usize> = (0..clauses.len()).collect();
104    let mut ordered = Vec::with_capacity(clauses.len());
105    while !remaining.is_empty() {
106        let best = remaining
107            .iter()
108            .enumerate()
109            .min_by_key(|(position, index)| (cost(&clauses[**index], &bound, ctx), *position))
110            .map_or(0, |(position, _)| position);
111        let index = remaining.remove(best);
112        bound.extend(clause_vars(&clauses[index]));
113        ordered.push(index);
114    }
115    ordered
116}
117
118fn term_bound(term: &Term, bound: &BTreeSet<Var>) -> bool {
119    match term {
120        Term::Const(_) => true,
121        Term::Var(v) => bound.contains(v),
122        Term::Blank => false,
123    }
124}
125
126fn cost(clause: &Clause, bound: &BTreeSet<Var>, ctx: &ExecCtx<'_>) -> Cost {
127    match clause {
128        Clause::Pattern(pattern) => {
129            let Some(db) = ctx.db(&pattern.src) else {
130                return (CLASS_PATTERN, usize::MAX);
131            };
132            let stats = db.planner_stats();
133            let a = match &pattern.a {
134                Term::Const(form) => ctx.attr_of(db, form),
135                _ => None,
136            };
137            let a_known = matches!(&pattern.a, Term::Const(_))
138                || matches!(&pattern.a, Term::Var(v) if bound.contains(v));
139            let e_known = term_bound(&pattern.e, bound);
140            let v_known = term_bound(&pattern.v, bound);
141            if a_known && a.is_none() && matches!(&pattern.a, Term::Var(_)) {
142                // Attribute known only at runtime: assume a per-attribute scan.
143                let estimate = (stats.total_datoms / stats.per_attr.len().max(1)).max(1);
144                return (CLASS_PATTERN, estimate);
145            }
146            (CLASS_PATTERN, stats.estimate(e_known, a, v_known))
147        }
148        Clause::Pred { args, .. } | Clause::Fn { args, .. } => {
149            let runnable = args
150                .iter()
151                .all(|t| term_bound(t, bound) || matches!(t, Term::Blank));
152            if runnable {
153                (CLASS_FILTER, 0)
154            } else {
155                (CLASS_SUBPLAN, 0)
156            }
157        }
158        Clause::RuleCall { .. } => (CLASS_RULE, 0),
159        Clause::Not { .. } | Clause::Or { .. } => (CLASS_SUBPLAN, 0),
160    }
161}
corium_query/plan.rs

corium_query/
plan.rs
