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

rushdb_query/planner/
explain.rs
