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

icydb_core/db/query/plan/
explain.rs
