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    /// Borrow optional projection annotation.
514    #[must_use]
515    pub fn projection(&self) -> Option<&str> {
516        self.projection.as_deref()
517    }
518
519    /// Return optional ordering source annotation.
520    #[must_use]
521    pub const fn ordering_source(&self) -> Option<ExplainExecutionOrderingSource> {
522        self.ordering_source
523    }
524
525    /// Return optional limit annotation.
526    #[must_use]
527    pub const fn limit(&self) -> Option<u32> {
528        self.limit
529    }
530
531    /// Return optional continuation annotation.
532    #[must_use]
533    pub const fn cursor(&self) -> Option<bool> {
534        self.cursor
535    }
536
537    /// Return optional covering-scan annotation.
538    #[must_use]
539    pub const fn covering_scan(&self) -> Option<bool> {
540        self.covering_scan
541    }
542
543    /// Return optional row-count expectation annotation.
544    #[must_use]
545    pub const fn rows_expected(&self) -> Option<u64> {
546        self.rows_expected
547    }
548
549    /// Borrow child execution nodes.
550    #[must_use]
551    pub const fn children(&self) -> &[Self] {
552        self.children.as_slice()
553    }
554
555    /// Borrow node properties.
556    #[must_use]
557    pub const fn node_properties(&self) -> &ExplainPropertyMap {
558        &self.node_properties
559    }
560}
561
562pub(in crate::db::query::explain) const fn execution_mode_label(
563    mode: ExplainExecutionMode,
564) -> &'static str {
565    match mode {
566        ExplainExecutionMode::Streaming => "Streaming",
567        ExplainExecutionMode::Materialized => "Materialized",
568    }
569}
570
571pub(in crate::db::query::explain) const fn ordering_source_label(
572    ordering_source: ExplainExecutionOrderingSource,
573) -> &'static str {
574    match ordering_source {
575        ExplainExecutionOrderingSource::AccessOrder => "AccessOrder",
576        ExplainExecutionOrderingSource::Materialized => "Materialized",
577        ExplainExecutionOrderingSource::IndexSeekFirst { .. } => "IndexSeekFirst",
578        ExplainExecutionOrderingSource::IndexSeekLast { .. } => "IndexSeekLast",
579    }
580}
581
582///
583/// TESTS
584///
585
586#[cfg(test)]
587mod tests {
588    use crate::db::query::explain::{
589        ExplainExecutionMode, ExplainExecutionNodeDescriptor, ExplainExecutionNodeType,
590        ExplainPropertyMap,
591    };
592
593    fn node(
594        node_type: ExplainExecutionNodeType,
595        children: Vec<ExplainExecutionNodeDescriptor>,
596    ) -> ExplainExecutionNodeDescriptor {
597        ExplainExecutionNodeDescriptor {
598            node_type,
599            execution_mode: ExplainExecutionMode::Materialized,
600            access_strategy: None,
601            predicate_pushdown: None,
602            filter_expr: None,
603            residual_filter_expr: None,
604            residual_filter_predicate: None,
605            projection: None,
606            ordering_source: None,
607            limit: None,
608            cursor: None,
609            covering_scan: None,
610            rows_expected: None,
611            children,
612            node_properties: ExplainPropertyMap::new(),
613        }
614    }
615
616    #[test]
617    fn execution_node_contains_type_scans_preorder_tree() {
618        let root = node(
619            ExplainExecutionNodeType::Union,
620            vec![
621                node(ExplainExecutionNodeType::FullScan, Vec::new()),
622                node(
623                    ExplainExecutionNodeType::Intersection,
624                    vec![node(ExplainExecutionNodeType::ResidualFilter, Vec::new())],
625                ),
626            ],
627        );
628
629        assert!(root.contains_type(ExplainExecutionNodeType::ResidualFilter));
630        assert!(!root.contains_type(ExplainExecutionNodeType::TopNSeek));
631    }
632
633    #[test]
634    fn execution_node_preorder_visits_parent_before_children() {
635        let root = node(
636            ExplainExecutionNodeType::Union,
637            vec![
638                node(ExplainExecutionNodeType::FullScan, Vec::new()),
639                node(
640                    ExplainExecutionNodeType::Intersection,
641                    vec![node(ExplainExecutionNodeType::ResidualFilter, Vec::new())],
642                ),
643            ],
644        );
645        let mut visited = Vec::new();
646
647        root.for_each_preorder(&mut |node| visited.push(node.node_type()));
648
649        assert_eq!(
650            visited,
651            vec![
652                ExplainExecutionNodeType::Union,
653                ExplainExecutionNodeType::FullScan,
654                ExplainExecutionNodeType::Intersection,
655                ExplainExecutionNodeType::ResidualFilter,
656            ],
657        );
658    }
659}
icydb_core/db/query/explain/execution.rs

icydb_core/db/query/explain/
execution.rs
