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

icydb_core/db/query/plan/
explain.rs
