lora_database/database/
explain.rs

1//! `Database::explain` — plan-only query inspection.
2//!
3//! `explain` parses, analyzes, and compiles a query, then returns the
4//! resulting [`QueryPlan`]. The executor is *never* invoked, so calling
5//! `explain` on a mutating query (CREATE / MERGE / SET / DELETE / REMOVE)
6//! reports the plan without producing any side effects.
7//!
8//! `params` is accepted for API symmetry with `execute()` and reserved
9//! for a future cost model — v1 does not consult parameter values when
10//! producing the plan tree.
11
12use std::any::Any;
13use std::collections::BTreeMap;
14
15use lora_compiler::{plan_tree_from_compiled, PlanTree, PlanTreeNode};
16use lora_executor::{classify_stream, plan_result_columns, LoraValue};
17use lora_store::{GraphStats, GraphStorage, GraphStorageMut};
18
19use crate::database::Database;
20use crate::error::LoraError;
21use crate::explain::{PlanShape, QueryPlan};
22
23impl<S> Database<S>
24where
25    S: GraphStorage + GraphStorageMut + Any + Clone + Send + Sync + 'static,
26{
27    /// Compile `query` and return the plan that *would* run.
28    ///
29    /// The executor is not invoked: `explain` is a pure planning call
30    /// and never produces side effects. Mutating queries return their
31    /// plan without touching the graph.
32    ///
33    /// `params` is accepted for symmetry with `execute()`. The returned
34    /// plan is identical regardless of the parameter values today;
35    /// future cost-model work may use parameter values for selectivity
36    /// estimation, so callers should pass real values when they have
37    /// them.
38    pub fn explain(
39        &self,
40        query: &str,
41        _params: Option<BTreeMap<String, LoraValue>>,
42    ) -> Result<QueryPlan, LoraError> {
43        let (store, store_epoch) = self.read_store_with_epoch_deadline(None)?;
44        let compiled = self
45            .compile_query_cached(query, &*store, store_epoch)
46            .map_err(LoraError::from_anyhow)?;
47        let mut tree = plan_tree_from_compiled(&compiled);
48        let stats = store.graph_stats();
49        annotate_estimated_rows(&mut tree, &stats);
50        let shape: PlanShape = classify_stream(&compiled).into();
51        let result_columns = plan_result_columns(&compiled.physical);
52        Ok(QueryPlan {
53            query: query.to_string(),
54            tree,
55            shape,
56            result_columns,
57        })
58    }
59}
60
61/// Walk a `PlanTree` and fill `estimated_rows` for the operators whose
62/// cardinality is derivable from the cheap [`GraphStats`] snapshot.
63/// Currently:
64/// * `NodeScan` → `node_count`
65/// * `NodeByLabelScan` → sum of per-label counts (handles `:A|B`)
66/// * `NodeByPropertyScan` → uniform-distribution heuristic from
67///   distinct-value count, when both label and property are recorded
68/// * `NodeByPropertyRangeScan`, `NodeByTextScan`, `NodeByPointScan` → a
69///   fraction of the label count, as the optimizer scores them
70///
71/// Operators that aren't covered keep the existing `None`. The
72/// optimizer doesn't *use* these numbers yet — it's `EXPLAIN`-only —
73/// but populating them now is what unlocks the cost model in a
74/// follow-up.
75pub(crate) fn annotate_estimated_rows(tree: &mut PlanTree, stats: &GraphStats) {
76    annotate_node(&mut tree.root, stats);
77}
78
79fn annotate_node(node: &mut PlanTreeNode, stats: &GraphStats) {
80    node.estimated_rows = match node.operator.as_str() {
81        "NodeScan" => Some(stats.node_count as u64),
82        "NodeByLabelScan" => labels_estimate(node, stats),
83        "NodeByPropertyScan" => property_equality_estimate(node, stats),
84        // The same selectivity guesses the optimizer scores seeks with
85        // (`score_logical_op`), so EXPLAIN shows what the planner assumed.
86        "NodeByPropertyRangeScan" => {
87            let two_sided = node.details.contains_key("lo") && node.details.contains_key("hi");
88            labels_estimate(node, stats).map(|n| n.div_ceil(if two_sided { 4 } else { 3 }))
89        }
90        "NodeByTextScan" => {
91            let denom = match node.details.get("predicate").map(String::as_str) {
92                Some("CONTAINS") => 2,
93                _ => 4,
94            };
95            labels_estimate(node, stats).map(|n| n.div_ceil(denom))
96        }
97        "NodeByPointScan" => labels_estimate(node, stats).map(|n| n.div_ceil(5)),
98        _ => None,
99    };
100    for child in &mut node.children {
101        annotate_node(child, stats);
102    }
103}
104
105fn labels_estimate(node: &PlanTreeNode, stats: &GraphStats) -> Option<u64> {
106    let labels = node.details.get("labels")?;
107    // `labels` is a humanised string from `label_groups_str`; we only
108    // attempt the simple `:Foo` form for v1 cost.
109    let trimmed = labels.trim_start_matches(':');
110    let bare = trimmed.split('|').next()?.trim();
111    stats.label_count(bare)
112}
113
114fn property_equality_estimate(node: &PlanTreeNode, stats: &GraphStats) -> Option<u64> {
115    let property = node.details.get("key")?;
116    let labels = node.details.get("labels")?;
117    let trimmed = labels.trim_start_matches(':');
118    let bare = trimmed.split('|').next()?.trim();
119    stats.estimate_node_property_equality(bare, property)
120}
lora_database/database/explain.rs

lora_database/database/
explain.rs
