icydb_core/db/query/explain/
execution.rs

1//! Module: query::explain::execution
2//! Responsibility: stable execution-descriptor vocabulary for EXPLAIN.
3//! Does not own: logical plan projection or rendering logic.
4//! Boundary: execution descriptor types consumed by explain renderers.
5
6use crate::{
7    db::query::{
8        explain::{ExplainAccessPath, ExplainPlan, ExplainPredicate},
9        plan::AggregateKind,
10        trace::TraceReuseEvent,
11    },
12    value::Value,
13};
14use std::fmt::{self, Debug};
15
16#[cfg_attr(
17    doc,
18    doc = "ExplainPropertyMap\n\nStable ordered property map for EXPLAIN metadata.\nKeeps deterministic key order without `BTreeMap`."
19)]
20#[derive(Clone, Default, Eq, PartialEq)]
21pub struct ExplainPropertyMap {
22    entries: Vec<(&'static str, Value)>,
23}
24
25impl ExplainPropertyMap {
26    /// Build an empty EXPLAIN property map.
27    #[must_use]
28    pub const fn new() -> Self {
29        Self {
30            entries: Vec::new(),
31        }
32    }
33
34    /// Insert or replace one stable property.
35    pub fn insert(&mut self, key: &'static str, value: Value) -> Option<Value> {
36        match self
37            .entries
38            .binary_search_by_key(&key, |(existing_key, _)| *existing_key)
39        {
40            Ok(index) => Some(std::mem::replace(&mut self.entries[index].1, value)),
41            Err(index) => {
42                self.entries.insert(index, (key, value));
43                None
44            }
45        }
46    }
47
48    /// Borrow one property value by key.
49    #[must_use]
50    pub fn get(&self, key: &str) -> Option<&Value> {
51        self.entries
52            .binary_search_by_key(&key, |(existing_key, _)| *existing_key)
53            .ok()
54            .map(|index| &self.entries[index].1)
55    }
56
57    /// Return whether the property map contains the given key.
58    #[must_use]
59    #[cfg(test)]
60    pub fn contains_key(&self, key: &str) -> bool {
61        self.get(key).is_some()
62    }
63
64    /// Return whether the property map is empty.
65    #[must_use]
66    pub const fn is_empty(&self) -> bool {
67        self.entries.is_empty()
68    }
69
70    /// Iterate over all stored properties in deterministic key order.
71    pub fn iter(&self) -> impl Iterator<Item = (&'static str, &Value)> {
72        self.entries.iter().map(|(key, value)| (*key, value))
73    }
74}
75
76impl Debug for ExplainPropertyMap {
77    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
78        let mut map = f.debug_map();
79        for (key, value) in self.iter() {
80            map.entry(&key, value);
81        }
82        map.finish()
83    }
84}
85
86#[cfg_attr(
87    doc,
88    doc = "ExplainAggregateTerminalPlan\n\nCombined EXPLAIN payload for one scalar aggregate request."
89)]
90#[derive(Clone, Debug, Eq, PartialEq)]
91pub struct ExplainAggregateTerminalPlan {
92    pub(in crate::db) query: ExplainPlan,
93    pub(in crate::db) terminal: AggregateKind,
94    pub(in crate::db) execution: ExplainExecutionDescriptor,
95}
96
97#[cfg_attr(
98    doc,
99    doc = "ExplainExecutionOrderingSource\n\nOrdering-origin label used by execution EXPLAIN output."
100)]
101#[derive(Clone, Copy, Debug, Eq, PartialEq)]
102pub enum ExplainExecutionOrderingSource {
103    AccessOrder,
104    Materialized,
105    IndexSeekFirst { fetch: usize },
106    IndexSeekLast { fetch: usize },
107}
108
109#[cfg_attr(
110    doc,
111    doc = "ExplainExecutionMode\n\nExecution mode used by EXPLAIN descriptors."
112)]
113#[derive(Clone, Copy, Debug, Eq, PartialEq)]
114pub enum ExplainExecutionMode {
115    Streaming,
116    Materialized,
117}
118
119#[cfg_attr(
120    doc,
121    doc = "ExplainExecutionDescriptor\n\nScalar execution descriptor consumed by terminal EXPLAIN surfaces.\nKeeps execution projection centralized for renderers."
122)]
123#[derive(Clone, Debug, Eq, PartialEq)]
124pub struct ExplainExecutionDescriptor {
125    pub(in crate::db) access_strategy: ExplainAccessPath,
126    pub(in crate::db) covering_projection: bool,
127    pub(in crate::db) aggregation: AggregateKind,
128    pub(in crate::db) execution_mode: ExplainExecutionMode,
129    pub(in crate::db) ordering_source: ExplainExecutionOrderingSource,
130    pub(in crate::db) limit: Option<u32>,
131    pub(in crate::db) cursor: bool,
132    pub(in crate::db) node_properties: ExplainPropertyMap,
133}
134
135#[cfg_attr(
136    doc,
137    doc = "ExplainExecutionNodeType\n\nExecution-node vocabulary for EXPLAIN descriptors."
138)]
139#[derive(Clone, Copy, Debug, Eq, PartialEq)]
140pub enum ExplainExecutionNodeType {
141    ByKeyLookup,
142    ByKeysLookup,
143    PrimaryKeyRangeScan,
144    IndexPrefixScan,
145    IndexRangeScan,
146    IndexMultiLookup,
147    IndexBranchSet,
148    FullScan,
149    Union,
150    Intersection,
151    IndexPredicatePrefilter,
152    ResidualFilter,
153    OrderByAccessSatisfied,
154    OrderByMaterializedSort,
155    DistinctPreOrdered,
156    DistinctMaterialized,
157    ProjectionMaterialized,
158    CoveringRead,
159    LimitOffset,
160    CursorResume,
161    IndexRangeLimitPushdown,
162    TopNSeek,
163    AggregateCount,
164    AggregateExists,
165    AggregateMin,
166    AggregateMax,
167    AggregateFirst,
168    AggregateLast,
169    AggregateSum,
170    AggregateSeekFirst,
171    AggregateSeekLast,
172    GroupedAggregateHashMaterialized,
173    GroupedAggregateOrderedMaterialized,
174    SecondaryOrderPushdown,
175}
176
177#[cfg_attr(
178    doc,
179    doc = "ExplainExecutionNodeDescriptor\n\nCanonical execution-node descriptor for EXPLAIN renderers.\nOptional fields are node-family specific."
180)]
181#[derive(Clone, Debug, Eq, PartialEq)]
182pub struct ExplainExecutionNodeDescriptor {
183    pub(in crate::db) node_type: ExplainExecutionNodeType,
184    pub(in crate::db) execution_mode: ExplainExecutionMode,
185    pub(in crate::db) access_strategy: Option<ExplainAccessPath>,
186    pub(in crate::db) predicate_pushdown: Option<String>,
187    pub(in crate::db) filter_expr: Option<String>,
188    pub(in crate::db) residual_filter_expr: Option<String>,
189    pub(in crate::db) residual_filter_predicate: Option<ExplainPredicate>,
190    pub(in crate::db) projection: Option<String>,
191    pub(in crate::db) ordering_source: Option<ExplainExecutionOrderingSource>,
192    pub(in crate::db) limit: Option<u32>,
193    pub(in crate::db) cursor: Option<bool>,
194    pub(in crate::db) covering_scan: Option<bool>,
195    pub(in crate::db) rows_expected: Option<u64>,
196    pub(in crate::db) children: Vec<Self>,
197    pub(in crate::db) node_properties: ExplainPropertyMap,
198}
199
200///
201/// FinalizedQueryDiagnostics
202///
203/// FinalizedQueryDiagnostics freezes one immutable execution-explain
204/// diagnostics artifact after descriptor assembly and plan-level diagnostics
205/// projection are complete.
206/// Session and SQL wrappers render this artifact directly instead of
207/// reconstructing verbose diagnostics from separate local line builders.
208///
209
210#[derive(Clone, Debug, Eq, PartialEq)]
211pub(in crate::db) struct FinalizedQueryDiagnostics {
212    pub(in crate::db) execution: ExplainExecutionNodeDescriptor,
213    pub(in crate::db) route_diagnostics: Vec<String>,
214    pub(in crate::db) logical_diagnostics: Vec<String>,
215    pub(in crate::db) reuse: Option<TraceReuseEvent>,
216}
217
218impl ExplainAggregateTerminalPlan {
219    /// Borrow the underlying query explain payload.
220    #[must_use]
221    pub const fn query(&self) -> &ExplainPlan {
222        &self.query
223    }
224
225    /// Return terminal aggregate kind.
226    #[must_use]
227    pub const fn terminal(&self) -> AggregateKind {
228        self.terminal
229    }
230
231    /// Borrow projected execution descriptor.
232    #[must_use]
233    pub const fn execution(&self) -> &ExplainExecutionDescriptor {
234        &self.execution
235    }
236
237    #[must_use]
238    pub(in crate::db) const fn new(
239        query: ExplainPlan,
240        terminal: AggregateKind,
241        execution: ExplainExecutionDescriptor,
242    ) -> Self {
243        Self {
244            query,
245            terminal,
246            execution,
247        }
248    }
249}
250
251impl ExplainExecutionDescriptor {
252    /// Borrow projected access strategy.
253    #[must_use]
254    pub const fn access_strategy(&self) -> &ExplainAccessPath {
255        &self.access_strategy
256    }
257
258    /// Return whether projection can be served from index payload only.
259    #[must_use]
260    pub const fn covering_projection(&self) -> bool {
261        self.covering_projection
262    }
263
264    /// Return projected aggregate kind.
265    #[must_use]
266    pub const fn aggregation(&self) -> AggregateKind {
267        self.aggregation
268    }
269
270    /// Return projected execution mode.
271    #[must_use]
272    pub const fn execution_mode(&self) -> ExplainExecutionMode {
273        self.execution_mode
274    }
275
276    /// Return projected ordering source.
277    #[must_use]
278    pub const fn ordering_source(&self) -> ExplainExecutionOrderingSource {
279        self.ordering_source
280    }
281
282    /// Return projected execution limit.
283    #[must_use]
284    pub const fn limit(&self) -> Option<u32> {
285        self.limit
286    }
287
288    /// Return whether continuation was applied.
289    #[must_use]
290    pub const fn cursor(&self) -> bool {
291        self.cursor
292    }
293
294    /// Borrow projected execution node properties.
295    #[must_use]
296    pub const fn node_properties(&self) -> &ExplainPropertyMap {
297        &self.node_properties
298    }
299}
300
301impl FinalizedQueryDiagnostics {
302    /// Construct one immutable execution diagnostics artifact.
303    #[must_use]
304    pub(in crate::db) const fn new(
305        execution: ExplainExecutionNodeDescriptor,
306        route_diagnostics: Vec<String>,
307        logical_diagnostics: Vec<String>,
308        reuse: Option<TraceReuseEvent>,
309    ) -> Self {
310        Self {
311            execution,
312            route_diagnostics,
313            logical_diagnostics,
314            reuse,
315        }
316    }
317
318    /// Borrow the frozen execution descriptor carried by this artifact.
319    #[must_use]
320    pub(in crate::db) const fn execution(&self) -> &ExplainExecutionNodeDescriptor {
321        &self.execution
322    }
323}
324
325impl ExplainAggregateTerminalPlan {
326    /// Build an execution-node descriptor for aggregate terminal plans.
327    #[must_use]
328    pub fn execution_node_descriptor(&self) -> ExplainExecutionNodeDescriptor {
329        let mut node_properties = self.execution.node_properties.clone();
330        node_properties.insert("aggregate_contract", Value::from("singleton"));
331        node_properties.insert(
332            "aggregate_physical",
333            Value::from(scalar_aggregate_physical_label(
334                self.execution.ordering_source,
335            )),
336        );
337
338        ExplainExecutionNodeDescriptor {
339            node_type: match self.execution.ordering_source {
340                ExplainExecutionOrderingSource::IndexSeekFirst { .. } => {
341                    ExplainExecutionNodeType::AggregateSeekFirst
342                }
343                ExplainExecutionOrderingSource::IndexSeekLast { .. } => {
344                    ExplainExecutionNodeType::AggregateSeekLast
345                }
346                ExplainExecutionOrderingSource::AccessOrder
347                | ExplainExecutionOrderingSource::Materialized => {
348                    self.terminal.explain_execution_node_type()
349                }
350            },
351            execution_mode: self.execution.execution_mode,
352            access_strategy: Some(self.execution.access_strategy.clone()),
353            predicate_pushdown: None,
354            filter_expr: None,
355            residual_filter_expr: None,
356            residual_filter_predicate: None,
357            projection: None,
358            ordering_source: Some(self.execution.ordering_source),
359            limit: self.execution.limit,
360            cursor: Some(self.execution.cursor),
361            covering_scan: Some(self.execution.covering_projection),
362            rows_expected: None,
363            children: Vec::new(),
364            node_properties,
365        }
366    }
367}
368
369const fn scalar_aggregate_physical_label(
370    ordering_source: ExplainExecutionOrderingSource,
371) -> &'static str {
372    match ordering_source {
373        ExplainExecutionOrderingSource::IndexSeekFirst { .. } => "scalar_seek_first",
374        ExplainExecutionOrderingSource::IndexSeekLast { .. } => "scalar_seek_last",
375        ExplainExecutionOrderingSource::AccessOrder
376        | ExplainExecutionOrderingSource::Materialized => "scalar_terminal",
377    }
378}
379
380impl AggregateKind {
381    /// Return the canonical explain execution-node type for this aggregate
382    /// terminal kind when no seek-first/seek-last override applies.
383    #[must_use]
384    pub(in crate::db) const fn explain_execution_node_type(self) -> ExplainExecutionNodeType {
385        match self {
386            Self::Count => ExplainExecutionNodeType::AggregateCount,
387            Self::Exists => ExplainExecutionNodeType::AggregateExists,
388            Self::Min => ExplainExecutionNodeType::AggregateMin,
389            Self::Max => ExplainExecutionNodeType::AggregateMax,
390            Self::First => ExplainExecutionNodeType::AggregateFirst,
391            Self::Last => ExplainExecutionNodeType::AggregateLast,
392            Self::Sum | Self::Avg => ExplainExecutionNodeType::AggregateSum,
393        }
394    }
395}
396
397impl ExplainExecutionNodeType {
398    /// Return the stable string label used by explain renderers.
399    #[must_use]
400    pub const fn as_str(self) -> &'static str {
401        match self {
402            Self::ByKeyLookup => "ByKeyLookup",
403            Self::ByKeysLookup => "ByKeysLookup",
404            Self::PrimaryKeyRangeScan => "PrimaryKeyRangeScan",
405            Self::IndexPrefixScan => "IndexPrefixScan",
406            Self::IndexRangeScan => "IndexRangeScan",
407            Self::IndexMultiLookup => "IndexMultiLookup",
408            Self::IndexBranchSet => "IndexBranchSet",
409            Self::FullScan => "FullScan",
410            Self::Union => "Union",
411            Self::Intersection => "Intersection",
412            Self::IndexPredicatePrefilter => "IndexPredicatePrefilter",
413            Self::ResidualFilter => "ResidualFilter",
414            Self::OrderByAccessSatisfied => "OrderByAccessSatisfied",
415            Self::OrderByMaterializedSort => "OrderByMaterializedSort",
416            Self::DistinctPreOrdered => "DistinctPreOrdered",
417            Self::DistinctMaterialized => "DistinctMaterialized",
418            Self::ProjectionMaterialized => "ProjectionMaterialized",
419            Self::CoveringRead => "CoveringRead",
420            Self::LimitOffset => "LimitOffset",
421            Self::CursorResume => "CursorResume",
422            Self::IndexRangeLimitPushdown => "IndexRangeLimitPushdown",
423            Self::TopNSeek => "TopNSeek",
424            Self::AggregateCount => "AggregateCount",
425            Self::AggregateExists => "AggregateExists",
426            Self::AggregateMin => "AggregateMin",
427            Self::AggregateMax => "AggregateMax",
428            Self::AggregateFirst => "AggregateFirst",
429            Self::AggregateLast => "AggregateLast",
430            Self::AggregateSum => "AggregateSum",
431            Self::AggregateSeekFirst => "AggregateSeekFirst",
432            Self::AggregateSeekLast => "AggregateSeekLast",
433            Self::GroupedAggregateHashMaterialized => "GroupedAggregateHashMaterialized",
434            Self::GroupedAggregateOrderedMaterialized => "GroupedAggregateOrderedMaterialized",
435            Self::SecondaryOrderPushdown => "SecondaryOrderPushdown",
436        }
437    }
438
439    /// Return the owning execution layer label for this node type.
440    #[must_use]
441    pub const fn layer_label(self) -> &'static str {
442        crate::db::query::explain::nodes::layer_label(self)
443    }
444}
445
446impl ExplainExecutionNodeDescriptor {
447    /// Visit this execution-descriptor tree in deterministic preorder.
448    pub(in crate::db) fn for_each_preorder(&self, visit: &mut impl FnMut(&Self)) {
449        visit(self);
450
451        for child in self.children() {
452            child.for_each_preorder(visit);
453        }
454    }
455
456    /// Return whether this descriptor tree contains the requested node type.
457    #[must_use]
458    pub(in crate::db) fn contains_type(&self, target: ExplainExecutionNodeType) -> bool {
459        let mut found = false;
460        self.for_each_preorder(&mut |node| {
461            if node.node_type() == target {
462                found = true;
463            }
464        });
465
466        found
467    }
468
469    /// Return node type.
470    #[must_use]
471    pub const fn node_type(&self) -> ExplainExecutionNodeType {
472        self.node_type
473    }
474
475    /// Return execution mode.
476    #[must_use]
477    pub const fn execution_mode(&self) -> ExplainExecutionMode {
478        self.execution_mode
479    }
480
481    /// Borrow optional access strategy annotation.
482    #[must_use]
483    pub const fn access_strategy(&self) -> Option<&ExplainAccessPath> {
484        self.access_strategy.as_ref()
485    }
486
487    /// Borrow optional predicate pushdown annotation.
488    #[must_use]
489    pub fn predicate_pushdown(&self) -> Option<&str> {
490        self.predicate_pushdown.as_deref()
491    }
492
493    /// Borrow optional semantic scalar filter expression annotation.
494    #[must_use]
495    pub fn filter_expr(&self) -> Option<&str> {
496        self.filter_expr.as_deref()
497    }
498
499    /// Borrow the optional explicit residual scalar filter expression.
500    #[must_use]
501    pub fn residual_filter_expr(&self) -> Option<&str> {
502        self.residual_filter_expr.as_deref()
503    }
504
505    /// Borrow the optional derived residual predicate annotation emitted
506    /// alongside `filter_expr` when execution still benefits from predicate
507    /// pushdown labeling.
508    #[must_use]
509    pub const fn residual_filter_predicate(&self) -> Option<&ExplainPredicate> {
510        self.residual_filter_predicate.as_ref()
511    }
512
513    /// Return whether this node carries any residual filter annotation.
514    #[must_use]
515    pub const fn has_residual_filter(&self) -> bool {
516        self.residual_filter_expr.is_some() || self.residual_filter_predicate.is_some()
517    }
518
519    /// Borrow optional projection annotation.
520    #[must_use]
521    pub fn projection(&self) -> Option<&str> {
522        self.projection.as_deref()
523    }
524
525    /// Return optional ordering source annotation.
526    #[must_use]
527    pub const fn ordering_source(&self) -> Option<ExplainExecutionOrderingSource> {
528        self.ordering_source
529    }
530
531    /// Return optional limit annotation.
532    #[must_use]
533    pub const fn limit(&self) -> Option<u32> {
534        self.limit
535    }
536
537    /// Return optional continuation annotation.
538    #[must_use]
539    pub const fn cursor(&self) -> Option<bool> {
540        self.cursor
541    }
542
543    /// Return optional covering-scan annotation.
544    #[must_use]
545    pub const fn covering_scan(&self) -> Option<bool> {
546        self.covering_scan
547    }
548
549    /// Return optional row-count expectation annotation.
550    #[must_use]
551    pub const fn rows_expected(&self) -> Option<u64> {
552        self.rows_expected
553    }
554
555    /// Borrow child execution nodes.
556    #[must_use]
557    pub const fn children(&self) -> &[Self] {
558        self.children.as_slice()
559    }
560
561    /// Borrow node properties.
562    #[must_use]
563    pub const fn node_properties(&self) -> &ExplainPropertyMap {
564        &self.node_properties
565    }
566}
567
568pub(in crate::db::query::explain) const fn execution_mode_label(
569    mode: ExplainExecutionMode,
570) -> &'static str {
571    match mode {
572        ExplainExecutionMode::Streaming => "Streaming",
573        ExplainExecutionMode::Materialized => "Materialized",
574    }
575}
576
577pub(in crate::db::query::explain) const fn ordering_source_label(
578    ordering_source: ExplainExecutionOrderingSource,
579) -> &'static str {
580    match ordering_source {
581        ExplainExecutionOrderingSource::AccessOrder => "AccessOrder",
582        ExplainExecutionOrderingSource::Materialized => "Materialized",
583        ExplainExecutionOrderingSource::IndexSeekFirst { .. } => "IndexSeekFirst",
584        ExplainExecutionOrderingSource::IndexSeekLast { .. } => "IndexSeekLast",
585    }
586}
587
588///
589/// TESTS
590///
591
592#[cfg(test)]
593mod tests {
594    use crate::db::query::explain::{
595        ExplainExecutionMode, ExplainExecutionNodeDescriptor, ExplainExecutionNodeType,
596        ExplainPropertyMap,
597    };
598
599    fn node(
600        node_type: ExplainExecutionNodeType,
601        children: Vec<ExplainExecutionNodeDescriptor>,
602    ) -> ExplainExecutionNodeDescriptor {
603        ExplainExecutionNodeDescriptor {
604            node_type,
605            execution_mode: ExplainExecutionMode::Materialized,
606            access_strategy: None,
607            predicate_pushdown: None,
608            filter_expr: None,
609            residual_filter_expr: None,
610            residual_filter_predicate: None,
611            projection: None,
612            ordering_source: None,
613            limit: None,
614            cursor: None,
615            covering_scan: None,
616            rows_expected: None,
617            children,
618            node_properties: ExplainPropertyMap::new(),
619        }
620    }
621
622    #[test]
623    fn execution_node_contains_type_scans_preorder_tree() {
624        let root = node(
625            ExplainExecutionNodeType::Union,
626            vec![
627                node(ExplainExecutionNodeType::FullScan, Vec::new()),
628                node(
629                    ExplainExecutionNodeType::Intersection,
630                    vec![node(ExplainExecutionNodeType::ResidualFilter, Vec::new())],
631                ),
632            ],
633        );
634
635        assert!(root.contains_type(ExplainExecutionNodeType::ResidualFilter));
636        assert!(!root.contains_type(ExplainExecutionNodeType::TopNSeek));
637    }
638
639    #[test]
640    fn execution_node_preorder_visits_parent_before_children() {
641        let root = node(
642            ExplainExecutionNodeType::Union,
643            vec![
644                node(ExplainExecutionNodeType::FullScan, Vec::new()),
645                node(
646                    ExplainExecutionNodeType::Intersection,
647                    vec![node(ExplainExecutionNodeType::ResidualFilter, Vec::new())],
648                ),
649            ],
650        );
651        let mut visited = Vec::new();
652
653        root.for_each_preorder(&mut |node| visited.push(node.node_type()));
654
655        assert_eq!(
656            visited,
657            vec![
658                ExplainExecutionNodeType::Union,
659                ExplainExecutionNodeType::FullScan,
660                ExplainExecutionNodeType::Intersection,
661                ExplainExecutionNodeType::ResidualFilter,
662            ],
663        );
664    }
665}
icydb_core/db/query/explain/execution.rs

icydb_core/db/query/explain/
execution.rs
