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    TextContains {
105        field: String,
106        value: Value,
107    },
108    TextContainsCi {
109        field: String,
110        value: Value,
111    },
112}
113
114///
115/// ExplainOrderBy
116///
117
118#[derive(Clone, Debug, Eq, PartialEq)]
119pub enum ExplainOrderBy {
120    None,
121    Fields(Vec<ExplainOrder>),
122}
123
124///
125/// ExplainOrder
126///
127
128#[derive(Clone, Debug, Eq, PartialEq)]
129pub struct ExplainOrder {
130    pub field: String,
131    pub direction: OrderDirection,
132}
133
134///
135/// ExplainPagination
136///
137
138#[derive(Clone, Debug, Eq, PartialEq)]
139pub enum ExplainPagination {
140    None,
141    Page { limit: Option<u32>, offset: u64 },
142}
143
144///
145/// ExplainDeleteLimit
146///
147
148#[derive(Clone, Debug, Eq, PartialEq)]
149pub enum ExplainDeleteLimit {
150    None,
151    Limit { max_rows: u32 },
152}
153
154///
155/// ExplainProjection
156///
157
158#[derive(Clone, Debug, Eq, PartialEq)]
159pub enum ExplainProjection {
160    All,
161}
162
163impl LogicalPlan {
164    /// Produce a stable, deterministic explanation of this logical plan.
165    #[must_use]
166    pub fn explain(&self) -> ExplainPlan {
167        let predicate = match &self.predicate {
168            Some(predicate) => ExplainPredicate::from_predicate(&normalize(predicate)),
169            None => ExplainPredicate::None,
170        };
171
172        let order_by = explain_order(self.order.as_ref());
173        let page = explain_page(self.page.as_ref());
174        let delete_limit = explain_delete_limit(self.delete_limit.as_ref());
175        let projection = ExplainProjection::from_spec(&self.projection);
176
177        ExplainPlan {
178            mode: self.mode,
179            access: ExplainAccessPath::from_access_plan(&self.access),
180            predicate,
181            order_by,
182            page,
183            delete_limit,
184            projection,
185            consistency: self.consistency,
186        }
187    }
188}
189
190impl ExplainAccessPath {
191    fn from_access_plan(access: &AccessPlan) -> Self {
192        match access {
193            AccessPlan::Path(path) => Self::from_path(path),
194            AccessPlan::Union(children) => {
195                Self::Union(children.iter().map(Self::from_access_plan).collect())
196            }
197            AccessPlan::Intersection(children) => {
198                Self::Intersection(children.iter().map(Self::from_access_plan).collect())
199            }
200        }
201    }
202
203    fn from_path(path: &AccessPath) -> Self {
204        match path {
205            AccessPath::ByKey(key) => Self::ByKey { key: *key },
206            AccessPath::ByKeys(keys) => Self::ByKeys { keys: keys.clone() },
207            AccessPath::KeyRange { start, end } => Self::KeyRange {
208                start: *start,
209                end: *end,
210            },
211            AccessPath::IndexPrefix { index, values } => Self::IndexPrefix {
212                name: index.name,
213                fields: index.fields.to_vec(),
214                prefix_len: values.len(),
215                values: values.clone(),
216            },
217            AccessPath::FullScan => Self::FullScan,
218        }
219    }
220}
221
222impl ExplainPredicate {
223    fn from_predicate(predicate: &Predicate) -> Self {
224        match predicate {
225            Predicate::True => Self::True,
226            Predicate::False => Self::False,
227            Predicate::And(children) => {
228                Self::And(children.iter().map(Self::from_predicate).collect())
229            }
230            Predicate::Or(children) => {
231                Self::Or(children.iter().map(Self::from_predicate).collect())
232            }
233            Predicate::Not(inner) => Self::Not(Box::new(Self::from_predicate(inner))),
234            Predicate::Compare(compare) => Self::from_compare(compare),
235            Predicate::IsNull { field } => Self::IsNull {
236                field: field.clone(),
237            },
238            Predicate::IsMissing { field } => Self::IsMissing {
239                field: field.clone(),
240            },
241            Predicate::IsEmpty { field } => Self::IsEmpty {
242                field: field.clone(),
243            },
244            Predicate::IsNotEmpty { field } => Self::IsNotEmpty {
245                field: field.clone(),
246            },
247            Predicate::MapContainsKey {
248                field,
249                key,
250                coercion,
251            } => Self::MapContainsKey {
252                field: field.clone(),
253                key: key.clone(),
254                coercion: coercion.clone(),
255            },
256            Predicate::MapContainsValue {
257                field,
258                value,
259                coercion,
260            } => Self::MapContainsValue {
261                field: field.clone(),
262                value: value.clone(),
263                coercion: coercion.clone(),
264            },
265            Predicate::MapContainsEntry {
266                field,
267                key,
268                value,
269                coercion,
270            } => Self::MapContainsEntry {
271                field: field.clone(),
272                key: key.clone(),
273                value: value.clone(),
274                coercion: coercion.clone(),
275            },
276            Predicate::TextContains { field, value } => Self::TextContains {
277                field: field.clone(),
278                value: value.clone(),
279            },
280            Predicate::TextContainsCi { field, value } => Self::TextContainsCi {
281                field: field.clone(),
282                value: value.clone(),
283            },
284        }
285    }
286
287    fn from_compare(compare: &ComparePredicate) -> Self {
288        Self::Compare {
289            field: compare.field.clone(),
290            op: compare.op,
291            value: compare.value.clone(),
292            coercion: compare.coercion.clone(),
293        }
294    }
295}
296
297fn explain_order(order: Option<&OrderSpec>) -> ExplainOrderBy {
298    let Some(order) = order else {
299        return ExplainOrderBy::None;
300    };
301
302    if order.fields.is_empty() {
303        return ExplainOrderBy::None;
304    }
305
306    ExplainOrderBy::Fields(
307        order
308            .fields
309            .iter()
310            .map(|(field, direction)| ExplainOrder {
311                field: field.clone(),
312                direction: *direction,
313            })
314            .collect(),
315    )
316}
317
318const fn explain_page(page: Option<&PageSpec>) -> ExplainPagination {
319    match page {
320        Some(page) => ExplainPagination::Page {
321            limit: page.limit,
322            offset: page.offset,
323        },
324        None => ExplainPagination::None,
325    }
326}
327
328const fn explain_delete_limit(limit: Option<&DeleteLimitSpec>) -> ExplainDeleteLimit {
329    match limit {
330        Some(limit) => ExplainDeleteLimit::Limit {
331            max_rows: limit.max_rows,
332        },
333        None => ExplainDeleteLimit::None,
334    }
335}
336
337impl ExplainProjection {
338    const fn from_spec(spec: &ProjectionSpec) -> Self {
339        match spec {
340            ProjectionSpec::All => Self::All,
341        }
342    }
343}
344
345///
346/// TESTS
347///
348
349#[cfg(test)]
350mod tests {
351    use super::*;
352    use crate::db::query::{FieldRef, Query, ReadConsistency};
353    use crate::model::index::IndexModel;
354    use crate::types::Ulid;
355    use crate::value::Value;
356    use crate::{
357        db::query::plan::{AccessPath, LogicalPlan, planner::PlannerEntity},
358        key::Key,
359    };
360
361    #[test]
362    fn explain_is_deterministic_for_same_query() {
363        let query = Query::<PlannerEntity>::new(ReadConsistency::MissingOk)
364            .filter(FieldRef::new("id").eq(Ulid::default()));
365
366        let plan_a = query.plan().expect("plan a");
367        let plan_b = query.plan().expect("plan b");
368
369        assert_eq!(plan_a.explain(), plan_b.explain());
370    }
371
372    #[test]
373    fn explain_is_deterministic_for_equivalent_predicates() {
374        let id = Ulid::default();
375
376        let query_a = Query::<PlannerEntity>::new(ReadConsistency::MissingOk)
377            .filter(FieldRef::new("id").eq(id))
378            .filter(FieldRef::new("other").eq("x"));
379
380        let query_b = Query::<PlannerEntity>::new(ReadConsistency::MissingOk)
381            .filter(FieldRef::new("other").eq("x"))
382            .filter(FieldRef::new("id").eq(id));
383
384        let plan_a = query_a.plan().expect("plan a");
385        let plan_b = query_b.plan().expect("plan b");
386
387        assert_eq!(plan_a.explain(), plan_b.explain());
388    }
389
390    #[test]
391    fn explain_reports_deterministic_index_choice() {
392        const INDEX_FIELDS: [&str; 1] = ["idx_a"];
393        const INDEX_A: IndexModel =
394            IndexModel::new("explain::idx_a", "explain::store", &INDEX_FIELDS, false);
395        const INDEX_B: IndexModel =
396            IndexModel::new("explain::idx_a_alt", "explain::store", &INDEX_FIELDS, false);
397
398        let mut indexes = [INDEX_B, INDEX_A];
399        indexes.sort_by(|left, right| left.name.cmp(right.name));
400        let chosen = indexes[0];
401
402        let plan = LogicalPlan::new(
403            AccessPath::IndexPrefix {
404                index: chosen,
405                values: vec![Value::Text("alpha".to_string())],
406            },
407            crate::db::query::ReadConsistency::MissingOk,
408        );
409
410        let explain = plan.explain();
411        match explain.access {
412            ExplainAccessPath::IndexPrefix {
413                name,
414                fields,
415                prefix_len,
416                ..
417            } => {
418                assert_eq!(name, "explain::idx_a");
419                assert_eq!(fields, vec!["idx_a"]);
420                assert_eq!(prefix_len, 1);
421            }
422            _ => panic!("expected index prefix"),
423        }
424    }
425
426    #[test]
427    fn explain_differs_for_semantic_changes() {
428        let plan_a = LogicalPlan::new(
429            AccessPath::ByKey(Key::Ulid(Ulid::from_u128(1))),
430            crate::db::query::ReadConsistency::MissingOk,
431        );
432        let plan_b = LogicalPlan::new(
433            AccessPath::FullScan,
434            crate::db::query::ReadConsistency::MissingOk,
435        );
436
437        assert_ne!(plan_a.explain(), plan_b.explain());
438    }
439}
icydb_core/db/query/plan/explain.rs

icydb_core/db/query/plan/
explain.rs
