rushdb_query/planner/
explain.rs

1//! Planner answers for `EXPLAIN`: the exact cardinality of the most
2//! selective index leaf, and the unindexed walk a query would start with.
3
4use rushdb_lmpg::reader::TryRead;
5use rushdb_types::model::LogicalType;
6
7use super::{
8    collect_leaves, expansions, family_id, is_range_leaf, labels_for, leaf_estimate, normalize,
9    property_id, target_estimate,
10};
11use crate::{Expr, FieldPred, QueryError};
12
13/// Exact most-selective index-leaf cardinality for a predicate, for `EXPLAIN`
14///. Uses the maintained derived posting cardinality when the view
15/// carries it, so `EXPLAIN` need not materialize candidates. Returns `None`
16/// when no leaf is index-eligible (a full scan).
17///
18/// # Errors
19/// Propagates storage/engine read errors from the estimate lookup.
20pub fn explain_cardinality<R: TryRead>(
21    snap: &R,
22    tenant: rushdb_types::ids::TenantId,
23    labels: &[String],
24    where_: &Expr,
25) -> Result<Option<u64>, QueryError> {
26    let mut leaves = Vec::new();
27    collect_leaves(where_, &mut leaves);
28    let mut best: Option<u64> = None;
29    for leaf in leaves {
30        // Range leaves now get a bounded histogram *estimate* from
31        // `leaf_estimate` for the planner's own cost ordering, but this
32        // field is contractually exact — excluded structurally (by leaf
33        // shape), not by filtering the `u64::MAX` sentinel, so that estimate
34        // can never leak in here. See `is_range_leaf`.
35        if is_range_leaf(leaf) {
36            continue;
37        }
38        if let Some(estimate) = leaf_estimate(snap, tenant, leaf, labels)? {
39            // `u64::MAX` marks an unknown/unbounded leaf; only a known exact
40            // cardinality is useful for EXPLAIN.
41            if estimate != u64::MAX {
42                best = Some(best.map_or(estimate, |current| current.min(estimate)));
43            }
44        }
45    }
46    Ok(best)
47}
48
49/// The unindexed walk a query would start with, for `EXPLAIN`: the
50/// property of the most selective eligible leaf when no declared ordered
51/// index serves it, and the owners carrying that property (under `labels`
52/// when given), which the planner visits one point read at a time.
53///
54/// # Errors
55/// Propagates storage reads from the estimate and support lookups.
56pub fn explain_walk<R: TryRead>(
57    snap: &R,
58    tenant: rushdb_types::ids::TenantId,
59    labels: &[String],
60    where_: &Expr,
61) -> Result<Option<(String, u64, Vec<String>)>, QueryError> {
62    let mut leaves = Vec::new();
63    collect_leaves(where_, &mut leaves);
64    let mut eligible = Vec::new();
65    for leaf in leaves {
66        if let Some(estimate) = leaf_estimate(snap, tenant, leaf, labels)? {
67            eligible.push((estimate, leaf));
68        }
69    }
70    eligible.sort_by_key(|(estimate, _)| *estimate);
71    let Some((_, leaf)) = eligible.first() else {
72        return Ok(None);
73    };
74    if crate::index_access::answers(snap, tenant, leaf, labels)? {
75        return Ok(None);
76    }
77    let Expr::Field(
78        FieldPred::Eq(name, _)
79        | FieldPred::In(name, _)
80        | FieldPred::Gt(name, _)
81        | FieldPred::Gte(name, _)
82        | FieldPred::Lt(name, _)
83        | FieldPred::Lte(name, _),
84    ) = leaf
85    else {
86        return Ok(None);
87    };
88    let norm = normalize(name);
89    let Some(fid) = family_id(snap, tenant, &norm)? else {
90        return Ok(None);
91    };
92    let kind = rushdb_types::ids::OwnerKind::Record;
93    let mut owners = 0u64;
94    let mut walked_labels = std::collections::BTreeSet::new();
95    for ty in [
96        LogicalType::Utf8,
97        LogicalType::Int64,
98        LogicalType::Float64,
99        LogicalType::Boolean,
100        LogicalType::DateTime,
101    ] {
102        let Some(pid) = property_id(snap, tenant, fid, ty)? else {
103            continue;
104        };
105        for label in labels_for(snap, tenant, pid, labels)? {
106            owners = owners.saturating_add(rushdb_lmpg::derived::prop_support_label(
107                snap, tenant, kind, pid, &label,
108            )?);
109            walked_labels.insert(label);
110        }
111    }
112    Ok(Some((norm, owners, walked_labels.into_iter().collect())))
113}
114
115/// The traversal the planner answers by expanding backwards from its
116/// targets, for `EXPLAIN` and the unindexed-walk check: the estimated
117/// number of targets it starts from (the smallest, when several are
118/// expanded). `None` when no traversal conjunct is expanded.
119///
120/// # Errors
121/// Propagates storage reads from the estimates.
122pub fn explain_expansion<R: TryRead>(
123    snap: &R,
124    tenant: rushdb_types::ids::TenantId,
125    labels: &[String],
126    where_: &Expr,
127) -> Result<Option<u64>, QueryError> {
128    let mut leaves = Vec::new();
129    collect_leaves(where_, &mut leaves);
130    let mut eligible = Vec::new();
131    let mut traversals = Vec::new();
132    for leaf in leaves {
133        match leaf {
134            Expr::Related(rel) if !rel.cycle => traversals.push(rel),
135            _ => {
136                if let Some(estimate) = leaf_estimate(snap, tenant, leaf, labels)? {
137                    eligible.push((estimate, leaf));
138                }
139            }
140        }
141    }
142    let mut best: Option<u64> = None;
143    for (_, rel) in expansions(snap, tenant, labels, &eligible, traversals)?.expand {
144        let targets = target_estimate(snap, tenant, rel)?;
145        best = Some(best.map_or(targets, |current| current.min(targets)));
146    }
147    Ok(best)
148}
rushdb_query/planner/explain.rs

rushdb_query/planner/
explain.rs
