icydb_core/db/query/plan/
explain.rs

1//! Deterministic, read-only explanation of logical plans; must not execute or validate.
2
3use super::{
4    AccessPath, AccessPlan, DeleteLimitSpec, LogicalPlan, OrderDirection, OrderSpec, PageSpec,
5    ProjectionSpec,
6};
7use crate::db::query::QueryMode;
8use crate::db::query::predicate::{
9    CompareOp, ComparePredicate, Predicate, coercion::CoercionSpec, normalize,
10};
11use crate::{db::query::ReadConsistency, key::Key, value::Value};
12
13///
14/// ExplainPlan
15///
16/// Stable, deterministic projection of a `LogicalPlan` for observability.
17///
18
19#[derive(Clone, Debug, Eq, PartialEq)]
20pub struct ExplainPlan {
21    pub mode: QueryMode,
22    pub access: ExplainAccessPath,
23    pub predicate: ExplainPredicate,
24    pub order_by: ExplainOrderBy,
25    pub page: ExplainPagination,
26    pub delete_limit: ExplainDeleteLimit,
27    pub projection: ExplainProjection,
28    pub consistency: ReadConsistency,
29}
30
31///
32/// ExplainAccessPath
33///
34
35#[derive(Clone, Debug, Eq, PartialEq)]
36pub enum ExplainAccessPath {
37    ByKey {
38        key: Key,
39    },
40    ByKeys {
41        keys: Vec<Key>,
42    },
43    KeyRange {
44        start: Key,
45        end: Key,
46    },
47    IndexPrefix {
48        name: &'static str,
49        fields: Vec<&'static str>,
50        prefix_len: usize,
51        values: Vec<Value>,
52    },
53    FullScan,
54    Union(Vec<Self>),
55    Intersection(Vec<Self>),
56}
57
58///
59/// ExplainPredicate
60///
61
62#[derive(Clone, Debug, Eq, PartialEq)]
63pub enum ExplainPredicate {
64    None,
65    True,
66    False,
67    And(Vec<Self>),
68    Or(Vec<Self>),
69    Not(Box<Self>),
70    Compare {
71        field: String,
72        op: CompareOp,
73        value: Value,
74        coercion: CoercionSpec,
75    },
76    IsNull {
77        field: String,
78    },
79    IsMissing {
80        field: String,
81    },
82    IsEmpty {
83        field: String,
84    },
85    IsNotEmpty {
86        field: String,
87    },
88    MapContainsKey {
89        field: String,
90        key: Value,
91        coercion: CoercionSpec,
92    },
93    MapContainsValue {
94        field: String,
95        value: Value,
96        coercion: CoercionSpec,
97    },
98    MapContainsEntry {
99        field: String,
100        key: Value,
101        value: Value,
102        coercion: CoercionSpec,
103    },
104}
105
106///
107/// ExplainOrderBy
108///
109
110#[derive(Clone, Debug, Eq, PartialEq)]
111pub enum ExplainOrderBy {
112    None,
113    Fields(Vec<ExplainOrder>),
114}
115
116///
117/// ExplainOrder
118///
119
120#[derive(Clone, Debug, Eq, PartialEq)]
121pub struct ExplainOrder {
122    pub field: String,
123    pub direction: OrderDirection,
124}
125
126///
127/// ExplainPagination
128///
129
130#[derive(Clone, Debug, Eq, PartialEq)]
131pub enum ExplainPagination {
132    None,
133    Page { limit: Option<u32>, offset: u64 },
134}
135
136///
137/// ExplainDeleteLimit
138///
139
140#[derive(Clone, Debug, Eq, PartialEq)]
141pub enum ExplainDeleteLimit {
142    None,
143    Limit { max_rows: u32 },
144}
145
146///
147/// ExplainProjection
148///
149
150#[derive(Clone, Debug, Eq, PartialEq)]
151pub enum ExplainProjection {
152    All,
153}
154
155impl LogicalPlan {
156    /// Produce a stable, deterministic explanation of this logical plan.
157    #[must_use]
158    pub fn explain(&self) -> ExplainPlan {
159        let predicate = match &self.predicate {
160            Some(predicate) => ExplainPredicate::from_predicate(&normalize(predicate)),
161            None => ExplainPredicate::None,
162        };
163
164        let order_by = explain_order(self.order.as_ref());
165        let page = explain_page(self.page.as_ref());
166        let delete_limit = explain_delete_limit(self.delete_limit.as_ref());
167        let projection = ExplainProjection::from_spec(&self.projection);
168
169        ExplainPlan {
170            mode: self.mode,
171            access: ExplainAccessPath::from_access_plan(&self.access),
172            predicate,
173            order_by,
174            page,
175            delete_limit,
176            projection,
177            consistency: self.consistency,
178        }
179    }
180}
181
182impl ExplainAccessPath {
183    fn from_access_plan(access: &AccessPlan) -> Self {
184        match access {
185            AccessPlan::Path(path) => Self::from_path(path),
186            AccessPlan::Union(children) => {
187                Self::Union(children.iter().map(Self::from_access_plan).collect())
188            }
189            AccessPlan::Intersection(children) => {
190                Self::Intersection(children.iter().map(Self::from_access_plan).collect())
191            }
192        }
193    }
194
195    fn from_path(path: &AccessPath) -> Self {
196        match path {
197            AccessPath::ByKey(key) => Self::ByKey { key: *key },
198            AccessPath::ByKeys(keys) => Self::ByKeys { keys: keys.clone() },
199            AccessPath::KeyRange { start, end } => Self::KeyRange {
200                start: *start,
201                end: *end,
202            },
203            AccessPath::IndexPrefix { index, values } => Self::IndexPrefix {
204                name: index.name,
205                fields: index.fields.to_vec(),
206                prefix_len: values.len(),
207                values: values.clone(),
208            },
209            AccessPath::FullScan => Self::FullScan,
210        }
211    }
212}
213
214impl ExplainPredicate {
215    fn from_predicate(predicate: &Predicate) -> Self {
216        match predicate {
217            Predicate::True => Self::True,
218            Predicate::False => Self::False,
219            Predicate::And(children) => {
220                Self::And(children.iter().map(Self::from_predicate).collect())
221            }
222            Predicate::Or(children) => {
223                Self::Or(children.iter().map(Self::from_predicate).collect())
224            }
225            Predicate::Not(inner) => Self::Not(Box::new(Self::from_predicate(inner))),
226            Predicate::Compare(compare) => Self::from_compare(compare),
227            Predicate::IsNull { field } => Self::IsNull {
228                field: field.clone(),
229            },
230            Predicate::IsMissing { field } => Self::IsMissing {
231                field: field.clone(),
232            },
233            Predicate::IsEmpty { field } => Self::IsEmpty {
234                field: field.clone(),
235            },
236            Predicate::IsNotEmpty { field } => Self::IsNotEmpty {
237                field: field.clone(),
238            },
239            Predicate::MapContainsKey {
240                field,
241                key,
242                coercion,
243            } => Self::MapContainsKey {
244                field: field.clone(),
245                key: key.clone(),
246                coercion: coercion.clone(),
247            },
248            Predicate::MapContainsValue {
249                field,
250                value,
251                coercion,
252            } => Self::MapContainsValue {
253                field: field.clone(),
254                value: value.clone(),
255                coercion: coercion.clone(),
256            },
257            Predicate::MapContainsEntry {
258                field,
259                key,
260                value,
261                coercion,
262            } => Self::MapContainsEntry {
263                field: field.clone(),
264                key: key.clone(),
265                value: value.clone(),
266                coercion: coercion.clone(),
267            },
268        }
269    }
270
271    fn from_compare(compare: &ComparePredicate) -> Self {
272        Self::Compare {
273            field: compare.field.clone(),
274            op: compare.op,
275            value: compare.value.clone(),
276            coercion: compare.coercion.clone(),
277        }
278    }
279}
280
281fn explain_order(order: Option<&OrderSpec>) -> ExplainOrderBy {
282    let Some(order) = order else {
283        return ExplainOrderBy::None;
284    };
285
286    if order.fields.is_empty() {
287        return ExplainOrderBy::None;
288    }
289
290    ExplainOrderBy::Fields(
291        order
292            .fields
293            .iter()
294            .map(|(field, direction)| ExplainOrder {
295                field: field.clone(),
296                direction: *direction,
297            })
298            .collect(),
299    )
300}
301
302const fn explain_page(page: Option<&PageSpec>) -> ExplainPagination {
303    match page {
304        Some(page) => ExplainPagination::Page {
305            limit: page.limit,
306            offset: page.offset,
307        },
308        None => ExplainPagination::None,
309    }
310}
311
312const fn explain_delete_limit(limit: Option<&DeleteLimitSpec>) -> ExplainDeleteLimit {
313    match limit {
314        Some(limit) => ExplainDeleteLimit::Limit {
315            max_rows: limit.max_rows,
316        },
317        None => ExplainDeleteLimit::None,
318    }
319}
320
321impl ExplainProjection {
322    const fn from_spec(spec: &ProjectionSpec) -> Self {
323        match spec {
324            ProjectionSpec::All => Self::All,
325        }
326    }
327}
328
329///
330/// TESTS
331///
332
333#[cfg(test)]
334mod tests {
335    use super::*;
336    use crate::db::query::{Query, ReadConsistency, eq};
337    use crate::model::index::IndexModel;
338    use crate::types::Ulid;
339    use crate::value::Value;
340    use crate::{
341        db::query::plan::{AccessPath, LogicalPlan, planner::PlannerEntity},
342        key::Key,
343    };
344
345    #[test]
346    fn explain_is_deterministic_for_same_query() {
347        let query = Query::<PlannerEntity>::new(ReadConsistency::MissingOk)
348            .filter(eq("id", Ulid::default()));
349
350        let plan_a = query.plan().expect("plan a");
351        let plan_b = query.plan().expect("plan b");
352
353        assert_eq!(plan_a.explain(), plan_b.explain());
354    }
355
356    #[test]
357    fn explain_is_deterministic_for_equivalent_predicates() {
358        let id = Ulid::default();
359        let query_a = Query::<PlannerEntity>::new(ReadConsistency::MissingOk)
360            .filter(eq("id", id))
361            .filter(eq("other", "x"));
362        let query_b = Query::<PlannerEntity>::new(ReadConsistency::MissingOk)
363            .filter(eq("other", "x"))
364            .filter(eq("id", id));
365
366        let plan_a = query_a.plan().expect("plan a");
367        let plan_b = query_b.plan().expect("plan b");
368
369        assert_eq!(plan_a.explain(), plan_b.explain());
370    }
371
372    #[test]
373    fn explain_reports_deterministic_index_choice() {
374        const INDEX_FIELDS: [&str; 1] = ["idx_a"];
375        const INDEX_A: IndexModel =
376            IndexModel::new("explain::idx_a", "explain::store", &INDEX_FIELDS, false);
377        const INDEX_B: IndexModel =
378            IndexModel::new("explain::idx_a_alt", "explain::store", &INDEX_FIELDS, false);
379
380        let mut indexes = [INDEX_B, INDEX_A];
381        indexes.sort_by(|left, right| left.name.cmp(right.name));
382        let chosen = indexes[0];
383
384        let plan = LogicalPlan::new(
385            AccessPath::IndexPrefix {
386                index: chosen,
387                values: vec![Value::Text("alpha".to_string())],
388            },
389            crate::db::query::ReadConsistency::MissingOk,
390        );
391
392        let explain = plan.explain();
393        match explain.access {
394            ExplainAccessPath::IndexPrefix {
395                name,
396                fields,
397                prefix_len,
398                ..
399            } => {
400                assert_eq!(name, "explain::idx_a");
401                assert_eq!(fields, vec!["idx_a"]);
402                assert_eq!(prefix_len, 1);
403            }
404            _ => panic!("expected index prefix"),
405        }
406    }
407
408    #[test]
409    fn explain_differs_for_semantic_changes() {
410        let plan_a = LogicalPlan::new(
411            AccessPath::ByKey(Key::Ulid(Ulid::from_u128(1))),
412            crate::db::query::ReadConsistency::MissingOk,
413        );
414        let plan_b = LogicalPlan::new(
415            AccessPath::FullScan,
416            crate::db::query::ReadConsistency::MissingOk,
417        );
418
419        assert_ne!(plan_a.explain(), plan_b.explain());
420    }
421}
icydb_core/db/query/plan/explain.rs

icydb_core/db/query/plan/
explain.rs
