icydb_core/db/query/plan/
mod.rs

1//! Query plan contracts, planning, and validation wiring.
2
3mod group;
4mod planner;
5#[cfg(test)]
6mod tests;
7pub(crate) mod validate;
8
9use crate::{
10    db::{
11        access::{
12            AccessPath, AccessPlan, PushdownApplicability, SecondaryOrderPushdownEligibility,
13            SecondaryOrderPushdownRejection,
14        },
15        direction::Direction,
16        predicate::{MissingRowPolicy, PredicateExecutionModel},
17        query::explain::ExplainAccessPath,
18    },
19    model::entity::{EntityModel, resolve_field_slot},
20    value::Value,
21};
22use std::ops::Bound;
23#[cfg(test)]
24use std::ops::{Deref, DerefMut};
25
26pub(in crate::db) use group::{GroupedExecutorHandoff, grouped_executor_handoff};
27pub use validate::PlanError;
28pub(crate) use validate::{GroupPlanError, validate_group_query_semantics};
29
30///
31/// QueryMode
32///
33/// Discriminates load vs delete intent at planning time.
34/// Encodes mode-specific fields so invalid states are unrepresentable.
35/// Mode checks are explicit and stable at execution time.
36///
37
38#[derive(Clone, Copy, Debug, Eq, PartialEq)]
39pub enum QueryMode {
40    Load(LoadSpec),
41    Delete(DeleteSpec),
42}
43
44impl QueryMode {
45    /// True if this mode represents a load intent.
46    #[must_use]
47    pub const fn is_load(&self) -> bool {
48        match self {
49            Self::Load(_) => true,
50            Self::Delete(_) => false,
51        }
52    }
53
54    /// True if this mode represents a delete intent.
55    #[must_use]
56    pub const fn is_delete(&self) -> bool {
57        match self {
58            Self::Delete(_) => true,
59            Self::Load(_) => false,
60        }
61    }
62}
63
64///
65/// LoadSpec
66///
67/// Mode-specific fields for load intents.
68/// Encodes pagination without leaking into delete intents.
69///
70#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
71pub struct LoadSpec {
72    pub limit: Option<u32>,
73    pub offset: u32,
74}
75
76impl LoadSpec {
77    /// Create an empty load spec.
78    #[must_use]
79    pub const fn new() -> Self {
80        Self {
81            limit: None,
82            offset: 0,
83        }
84    }
85}
86
87///
88/// DeleteSpec
89///
90/// Mode-specific fields for delete intents.
91/// Encodes delete limits without leaking into load intents.
92///
93
94#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
95pub struct DeleteSpec {
96    pub limit: Option<u32>,
97}
98
99impl DeleteSpec {
100    /// Create an empty delete spec.
101    #[must_use]
102    pub const fn new() -> Self {
103        Self { limit: None }
104    }
105}
106
107///
108/// OrderDirection
109/// Executor-facing ordering direction (applied after filtering).
110///
111#[derive(Clone, Copy, Debug, Eq, PartialEq)]
112pub enum OrderDirection {
113    Asc,
114    Desc,
115}
116
117impl OrderDirection {
118    /// Convert canonical order direction into execution scan direction.
119    #[must_use]
120    pub(in crate::db) const fn as_direction(self) -> Direction {
121        match self {
122            Self::Asc => Direction::Asc,
123            Self::Desc => Direction::Desc,
124        }
125    }
126
127    /// Convert execution scan direction into canonical order direction.
128    #[must_use]
129    pub(in crate::db) const fn from_direction(direction: Direction) -> Self {
130        match direction {
131            Direction::Asc => Self::Asc,
132            Direction::Desc => Self::Desc,
133        }
134    }
135}
136
137///
138/// OrderSpec
139/// Executor-facing ordering specification.
140///
141
142#[derive(Clone, Debug, Eq, PartialEq)]
143pub(crate) struct OrderSpec {
144    pub(crate) fields: Vec<(String, OrderDirection)>,
145}
146
147///
148/// DeleteLimitSpec
149/// Executor-facing delete bound with no offsets.
150///
151
152#[derive(Clone, Copy, Debug, Eq, PartialEq)]
153pub(crate) struct DeleteLimitSpec {
154    pub max_rows: u32,
155}
156
157///
158/// PageSpec
159/// Executor-facing pagination specification.
160///
161
162#[derive(Clone, Debug, Eq, PartialEq)]
163pub(crate) struct PageSpec {
164    pub limit: Option<u32>,
165    pub offset: u32,
166}
167
168///
169/// AggregateKind
170///
171/// Canonical aggregate terminal taxonomy owned by query planning.
172/// All layers (query, explain, fingerprint, executor) must interpret aggregate
173/// terminal semantics through this single enum authority.
174///
175
176#[allow(dead_code)]
177#[derive(Clone, Copy, Debug, Eq, PartialEq)]
178pub enum AggregateKind {
179    Count,
180    Exists,
181    Min,
182    Max,
183    First,
184    Last,
185}
186
187impl AggregateKind {
188    /// Return whether this terminal kind is `COUNT`.
189    #[must_use]
190    pub(in crate::db) const fn is_count(self) -> bool {
191        matches!(self, Self::Count)
192    }
193
194    /// Return whether this terminal kind supports explicit field targets.
195    #[must_use]
196    pub(in crate::db) const fn supports_field_targets(self) -> bool {
197        matches!(self, Self::Min | Self::Max)
198    }
199
200    /// Return whether this terminal kind belongs to the extrema family.
201    #[must_use]
202    pub(in crate::db) const fn is_extrema(self) -> bool {
203        self.supports_field_targets()
204    }
205
206    /// Return whether this terminal kind supports first/last value projection.
207    #[must_use]
208    pub(in crate::db) const fn supports_terminal_value_projection(self) -> bool {
209        matches!(self, Self::First | Self::Last)
210    }
211
212    /// Return whether reducer updates for this kind require a decoded id payload.
213    #[must_use]
214    pub(in crate::db) const fn requires_decoded_id(self) -> bool {
215        !matches!(self, Self::Count | Self::Exists)
216    }
217
218    /// Return the canonical extrema traversal direction for this terminal kind.
219    #[must_use]
220    pub(in crate::db) const fn extrema_direction(self) -> Option<Direction> {
221        match self {
222            Self::Min => Some(Direction::Asc),
223            Self::Max => Some(Direction::Desc),
224            Self::Count | Self::Exists | Self::First | Self::Last => None,
225        }
226    }
227
228    /// Return the canonical non-short-circuit materialized reduction direction.
229    #[must_use]
230    pub(in crate::db) const fn materialized_fold_direction(self) -> Direction {
231        match self {
232            Self::Min => Direction::Desc,
233            Self::Count | Self::Exists | Self::Max | Self::First | Self::Last => Direction::Asc,
234        }
235    }
236
237    /// Return the canonical grouped aggregate fingerprint tag (v1).
238    #[must_use]
239    pub(in crate::db) const fn fingerprint_tag_v1(self) -> u8 {
240        match self {
241            Self::Count => 0x01,
242            Self::Exists => 0x02,
243            Self::Min => 0x03,
244            Self::Max => 0x04,
245            Self::First => 0x05,
246            Self::Last => 0x06,
247        }
248    }
249
250    /// Return true when this kind can use bounded aggregate probe hints.
251    #[must_use]
252    pub(in crate::db) const fn supports_bounded_probe_hint(self) -> bool {
253        !self.is_count()
254    }
255
256    /// Derive a bounded aggregate probe fetch hint for this kind.
257    #[must_use]
258    pub(in crate::db) fn bounded_probe_fetch_hint(
259        self,
260        direction: Direction,
261        offset: usize,
262        page_limit: Option<usize>,
263    ) -> Option<usize> {
264        match self {
265            Self::Exists | Self::First => Some(offset.saturating_add(1)),
266            Self::Min if direction == Direction::Asc => Some(offset.saturating_add(1)),
267            Self::Max if direction == Direction::Desc => Some(offset.saturating_add(1)),
268            Self::Last => page_limit.map(|limit| offset.saturating_add(limit)),
269            Self::Count | Self::Min | Self::Max => None,
270        }
271    }
272}
273
274/// Compatibility alias for grouped planning callsites.
275pub(crate) type GroupAggregateKind = AggregateKind;
276
277///
278/// GroupAggregateSpec
279///
280/// One grouped aggregate terminal specification declared at query-plan time.
281/// `target_field` remains optional so future field-target grouped terminals can
282/// reuse this contract without mutating the wrapper shape.
283///
284
285#[derive(Clone, Debug, Eq, PartialEq)]
286pub(crate) struct GroupAggregateSpec {
287    pub(crate) kind: AggregateKind,
288    pub(crate) target_field: Option<String>,
289}
290
291impl GroupAggregateSpec {
292    /// Return the canonical grouped aggregate terminal kind.
293    #[must_use]
294    pub(crate) const fn kind(&self) -> AggregateKind {
295        self.kind
296    }
297
298    /// Return the optional grouped aggregate target field.
299    #[must_use]
300    pub(crate) fn target_field(&self) -> Option<&str> {
301        self.target_field.as_deref()
302    }
303}
304
305///
306/// FieldSlot
307///
308/// Canonical resolved field reference used by logical planning.
309/// `index` is the stable slot in `EntityModel::fields`; `field` is retained
310/// for diagnostics and explain surfaces.
311///
312
313#[derive(Clone, Debug, Eq, PartialEq)]
314pub(crate) struct FieldSlot {
315    index: usize,
316    field: String,
317}
318
319impl FieldSlot {
320    /// Resolve one field name into its canonical model slot.
321    #[must_use]
322    pub(crate) fn resolve(model: &EntityModel, field: &str) -> Option<Self> {
323        let index = resolve_field_slot(model, field)?;
324        let canonical = model
325            .fields
326            .get(index)
327            .map_or(field, |model_field| model_field.name);
328
329        Some(Self {
330            index,
331            field: canonical.to_string(),
332        })
333    }
334
335    /// Build one field slot directly for tests that need invalid slot shapes.
336    #[cfg(test)]
337    #[must_use]
338    pub(crate) fn from_parts_for_test(index: usize, field: impl Into<String>) -> Self {
339        Self {
340            index,
341            field: field.into(),
342        }
343    }
344
345    /// Return the stable slot index in `EntityModel::fields`.
346    #[must_use]
347    pub(crate) const fn index(&self) -> usize {
348        self.index
349    }
350
351    /// Return the diagnostic field label associated with this slot.
352    #[must_use]
353    pub(crate) fn field(&self) -> &str {
354        &self.field
355    }
356}
357
358///
359/// GroupedExecutionConfig
360///
361/// Declarative grouped-execution budget policy selected by query planning.
362/// This remains planner-owned input; executor policy bridges may still apply
363/// defaults and enforcement strategy at runtime boundaries.
364///
365
366#[derive(Clone, Copy, Debug, Eq, PartialEq)]
367pub(crate) struct GroupedExecutionConfig {
368    pub(crate) max_groups: u64,
369    pub(crate) max_group_bytes: u64,
370}
371
372impl GroupedExecutionConfig {
373    /// Build one grouped execution config with explicit hard limits.
374    #[must_use]
375    pub(crate) const fn with_hard_limits(max_groups: u64, max_group_bytes: u64) -> Self {
376        Self {
377            max_groups,
378            max_group_bytes,
379        }
380    }
381
382    /// Build one unbounded grouped execution config.
383    #[must_use]
384    pub(crate) const fn unbounded() -> Self {
385        Self::with_hard_limits(u64::MAX, u64::MAX)
386    }
387
388    /// Return grouped hard limit for maximum groups.
389    #[must_use]
390    pub(crate) const fn max_groups(&self) -> u64 {
391        self.max_groups
392    }
393
394    /// Return grouped hard limit for estimated grouped bytes.
395    #[must_use]
396    pub(crate) const fn max_group_bytes(&self) -> u64 {
397        self.max_group_bytes
398    }
399}
400
401impl Default for GroupedExecutionConfig {
402    fn default() -> Self {
403        Self::unbounded()
404    }
405}
406
407///
408/// GroupSpec
409///
410/// Declarative GROUP BY stage contract attached to a validated base plan.
411/// This wrapper is intentionally semantic-only; field-slot resolution and
412/// execution-mode derivation remain executor-owned boundaries.
413///
414
415#[derive(Clone, Debug, Eq, PartialEq)]
416pub(crate) struct GroupSpec {
417    pub(crate) group_fields: Vec<FieldSlot>,
418    pub(crate) aggregates: Vec<GroupAggregateSpec>,
419    pub(crate) execution: GroupedExecutionConfig,
420}
421
422///
423/// ScalarPlan
424///
425/// Pure scalar logical query intent produced by the planner.
426///
427/// A `ScalarPlan` represents the access-independent query semantics:
428/// predicate/filter, ordering, distinct behavior, pagination/delete windows,
429/// and read-consistency mode.
430///
431/// Design notes:
432/// - Predicates are applied *after* data access
433/// - Ordering is applied after filtering
434/// - Pagination is applied after ordering (load only)
435/// - Delete limits are applied after ordering (delete only)
436/// - Missing-row policy is explicit and must not depend on access strategy
437///
438/// This struct is the logical compiler stage output and intentionally excludes
439/// access-path details.
440///
441
442#[derive(Clone, Debug, Eq, PartialEq)]
443pub(crate) struct ScalarPlan {
444    /// Load vs delete intent.
445    pub(crate) mode: QueryMode,
446
447    /// Optional residual predicate applied after access.
448    pub(crate) predicate: Option<PredicateExecutionModel>,
449
450    /// Optional ordering specification.
451    pub(crate) order: Option<OrderSpec>,
452
453    /// Optional distinct semantics over ordered rows.
454    pub(crate) distinct: bool,
455
456    /// Optional delete bound (delete intents only).
457    pub(crate) delete_limit: Option<DeleteLimitSpec>,
458
459    /// Optional pagination specification.
460    pub(crate) page: Option<PageSpec>,
461
462    /// Missing-row policy for execution.
463    pub(crate) consistency: MissingRowPolicy,
464}
465
466///
467/// GroupPlan
468///
469/// Pure grouped logical intent emitted by grouped planning.
470/// Group metadata is carried through one canonical `GroupSpec` contract.
471///
472
473#[derive(Clone, Debug, Eq, PartialEq)]
474pub(crate) struct GroupPlan {
475    pub(crate) scalar: ScalarPlan,
476    pub(crate) group: GroupSpec,
477}
478
479///
480/// LogicalPlan
481///
482/// Exclusive logical query intent emitted by planning.
483/// Scalar and grouped semantics are distinct variants by construction.
484///
485
486#[derive(Clone, Debug, Eq, PartialEq)]
487pub(crate) enum LogicalPlan {
488    Scalar(ScalarPlan),
489    Grouped(GroupPlan),
490}
491
492impl LogicalPlan {
493    /// Borrow scalar semantic fields shared by scalar/grouped logical variants.
494    #[must_use]
495    pub(in crate::db) const fn scalar_semantics(&self) -> &ScalarPlan {
496        match self {
497            Self::Scalar(plan) => plan,
498            Self::Grouped(plan) => &plan.scalar,
499        }
500    }
501
502    /// Borrow scalar semantic fields mutably across logical variants.
503    #[must_use]
504    #[cfg(test)]
505    pub(in crate::db) const fn scalar_semantics_mut(&mut self) -> &mut ScalarPlan {
506        match self {
507            Self::Scalar(plan) => plan,
508            Self::Grouped(plan) => &mut plan.scalar,
509        }
510    }
511}
512
513#[cfg(test)]
514impl Deref for LogicalPlan {
515    type Target = ScalarPlan;
516
517    fn deref(&self) -> &Self::Target {
518        self.scalar_semantics()
519    }
520}
521
522#[cfg(test)]
523impl DerefMut for LogicalPlan {
524    fn deref_mut(&mut self) -> &mut Self::Target {
525        self.scalar_semantics_mut()
526    }
527}
528
529///
530/// AccessPlannedQuery
531///
532/// Access-planned query produced after access-path selection.
533/// Binds one pure `LogicalPlan` to one chosen `AccessPlan`.
534///
535
536#[derive(Clone, Debug, Eq, PartialEq)]
537pub(crate) struct AccessPlannedQuery<K> {
538    pub(crate) logical: LogicalPlan,
539    pub(crate) access: AccessPlan<K>,
540}
541
542impl<K> AccessPlannedQuery<K> {
543    /// Construct an access-planned query from logical + access stages.
544    #[must_use]
545    pub(crate) const fn from_parts(logical: LogicalPlan, access: AccessPlan<K>) -> Self {
546        Self { logical, access }
547    }
548
549    /// Decompose into logical + access stages.
550    #[must_use]
551    pub(crate) fn into_parts(self) -> (LogicalPlan, AccessPlan<K>) {
552        (self.logical, self.access)
553    }
554
555    /// Convert this plan into grouped logical form with one explicit group spec.
556    #[must_use]
557    pub(in crate::db) fn into_grouped(self, group: GroupSpec) -> Self {
558        let Self { logical, access } = self;
559        let scalar = match logical {
560            LogicalPlan::Scalar(plan) => plan,
561            LogicalPlan::Grouped(plan) => plan.scalar,
562        };
563
564        Self {
565            logical: LogicalPlan::Grouped(GroupPlan { scalar, group }),
566            access,
567        }
568    }
569
570    /// Borrow scalar semantic fields shared by scalar/grouped logical variants.
571    #[must_use]
572    pub(in crate::db) const fn scalar_plan(&self) -> &ScalarPlan {
573        self.logical.scalar_semantics()
574    }
575
576    /// Borrow grouped semantic fields when this plan is grouped.
577    #[must_use]
578    pub(in crate::db) const fn grouped_plan(&self) -> Option<&GroupPlan> {
579        match &self.logical {
580            LogicalPlan::Scalar(_) => None,
581            LogicalPlan::Grouped(plan) => Some(plan),
582        }
583    }
584
585    /// Borrow scalar semantic fields mutably across logical variants.
586    #[must_use]
587    #[cfg(test)]
588    pub(in crate::db) const fn scalar_plan_mut(&mut self) -> &mut ScalarPlan {
589        self.logical.scalar_semantics_mut()
590    }
591
592    /// Construct a minimal access-planned query with only an access path.
593    ///
594    /// Predicates, ordering, and pagination may be attached later.
595    #[cfg(test)]
596    pub(crate) fn new(
597        access: crate::db::access::AccessPath<K>,
598        consistency: MissingRowPolicy,
599    ) -> Self {
600        Self {
601            logical: LogicalPlan::Scalar(crate::db::query::plan::ScalarPlan {
602                mode: QueryMode::Load(LoadSpec::new()),
603                predicate: None,
604                order: None,
605                distinct: false,
606                delete_limit: None,
607                page: None,
608                consistency,
609            }),
610            access: AccessPlan::path(access),
611        }
612    }
613}
614
615#[cfg(test)]
616impl<K> Deref for AccessPlannedQuery<K> {
617    type Target = ScalarPlan;
618
619    fn deref(&self) -> &Self::Target {
620        self.scalar_plan()
621    }
622}
623
624#[cfg(test)]
625impl<K> DerefMut for AccessPlannedQuery<K> {
626    fn deref_mut(&mut self) -> &mut Self::Target {
627        self.scalar_plan_mut()
628    }
629}
630
631fn order_fields_as_direction_refs(
632    order_fields: &[(String, OrderDirection)],
633) -> Vec<(&str, Direction)> {
634    order_fields
635        .iter()
636        .map(|(field, direction)| (field.as_str(), direction.as_direction()))
637        .collect()
638}
639
640fn applicability_from_eligibility(
641    eligibility: SecondaryOrderPushdownEligibility,
642) -> PushdownApplicability {
643    match eligibility {
644        SecondaryOrderPushdownEligibility::Rejected(
645            SecondaryOrderPushdownRejection::NoOrderBy
646            | SecondaryOrderPushdownRejection::AccessPathNotSingleIndexPrefix,
647        ) => PushdownApplicability::NotApplicable,
648        other => PushdownApplicability::Applicable(other),
649    }
650}
651
652// Core matcher for secondary ORDER BY pushdown eligibility.
653fn match_secondary_order_pushdown_core(
654    model: &EntityModel,
655    order_fields: &[(&str, Direction)],
656    index_name: &'static str,
657    index_fields: &[&'static str],
658    prefix_len: usize,
659) -> SecondaryOrderPushdownEligibility {
660    let Some((last_field, last_direction)) = order_fields.last() else {
661        return SecondaryOrderPushdownEligibility::Rejected(
662            SecondaryOrderPushdownRejection::NoOrderBy,
663        );
664    };
665    if *last_field != model.primary_key.name {
666        return SecondaryOrderPushdownEligibility::Rejected(
667            SecondaryOrderPushdownRejection::MissingPrimaryKeyTieBreak {
668                field: model.primary_key.name.to_string(),
669            },
670        );
671    }
672
673    let expected_direction = *last_direction;
674    for (field, direction) in order_fields {
675        if *direction != expected_direction {
676            return SecondaryOrderPushdownEligibility::Rejected(
677                SecondaryOrderPushdownRejection::MixedDirectionNotEligible {
678                    field: (*field).to_string(),
679                },
680            );
681        }
682    }
683
684    let actual_non_pk_len = order_fields.len().saturating_sub(1);
685    let matches_expected_suffix = actual_non_pk_len
686        == index_fields.len().saturating_sub(prefix_len)
687        && order_fields
688            .iter()
689            .take(actual_non_pk_len)
690            .map(|(field, _)| *field)
691            .zip(index_fields.iter().skip(prefix_len).copied())
692            .all(|(actual, expected)| actual == expected);
693    let matches_expected_full = actual_non_pk_len == index_fields.len()
694        && order_fields
695            .iter()
696            .take(actual_non_pk_len)
697            .map(|(field, _)| *field)
698            .zip(index_fields.iter().copied())
699            .all(|(actual, expected)| actual == expected);
700    if matches_expected_suffix || matches_expected_full {
701        return SecondaryOrderPushdownEligibility::Eligible {
702            index: index_name,
703            prefix_len,
704        };
705    }
706
707    SecondaryOrderPushdownEligibility::Rejected(
708        SecondaryOrderPushdownRejection::OrderFieldsDoNotMatchIndex {
709            index: index_name,
710            prefix_len,
711            expected_suffix: index_fields
712                .iter()
713                .skip(prefix_len)
714                .map(|field| (*field).to_string())
715                .collect(),
716            expected_full: index_fields
717                .iter()
718                .map(|field| (*field).to_string())
719                .collect(),
720            actual: order_fields
721                .iter()
722                .take(actual_non_pk_len)
723                .map(|(field, _)| (*field).to_string())
724                .collect(),
725        },
726    )
727}
728
729// Evaluate pushdown eligibility for ORDER BY + single index-prefix shapes.
730fn assess_secondary_order_pushdown_for_applicable_shape(
731    model: &EntityModel,
732    order_fields: &[(&str, Direction)],
733    index_name: &'static str,
734    index_fields: &[&'static str],
735    prefix_len: usize,
736) -> SecondaryOrderPushdownEligibility {
737    match_secondary_order_pushdown_core(model, order_fields, index_name, index_fields, prefix_len)
738}
739
740// Evaluate secondary ORDER BY pushdown over one access-planned query.
741fn assess_secondary_order_pushdown_for_plan<K>(
742    model: &EntityModel,
743    order_fields: Option<&[(&str, Direction)]>,
744    access_plan: &AccessPlan<K>,
745) -> SecondaryOrderPushdownEligibility {
746    let Some(order_fields) = order_fields else {
747        return SecondaryOrderPushdownEligibility::Rejected(
748            SecondaryOrderPushdownRejection::NoOrderBy,
749        );
750    };
751    if order_fields.is_empty() {
752        return SecondaryOrderPushdownEligibility::Rejected(
753            SecondaryOrderPushdownRejection::NoOrderBy,
754        );
755    }
756
757    let Some(access) = access_plan.as_path() else {
758        if let Some((index, prefix_len)) = access_plan.first_index_range_details() {
759            return SecondaryOrderPushdownEligibility::Rejected(
760                SecondaryOrderPushdownRejection::AccessPathIndexRangeUnsupported {
761                    index: index.name,
762                    prefix_len,
763                },
764            );
765        }
766
767        return SecondaryOrderPushdownEligibility::Rejected(
768            SecondaryOrderPushdownRejection::AccessPathNotSingleIndexPrefix,
769        );
770    };
771    if let Some((index, values)) = access.as_index_prefix() {
772        if values.len() > index.fields.len() {
773            return SecondaryOrderPushdownEligibility::Rejected(
774                SecondaryOrderPushdownRejection::InvalidIndexPrefixBounds {
775                    prefix_len: values.len(),
776                    index_field_len: index.fields.len(),
777                },
778            );
779        }
780
781        return assess_secondary_order_pushdown_for_applicable_shape(
782            model,
783            order_fields,
784            index.name,
785            index.fields,
786            values.len(),
787        );
788    }
789    if let Some((index, prefix_len)) = access.index_range_details() {
790        return SecondaryOrderPushdownEligibility::Rejected(
791            SecondaryOrderPushdownRejection::AccessPathIndexRangeUnsupported {
792                index: index.name,
793                prefix_len,
794            },
795        );
796    }
797
798    SecondaryOrderPushdownEligibility::Rejected(
799        SecondaryOrderPushdownRejection::AccessPathNotSingleIndexPrefix,
800    )
801}
802
803/// Evaluate the secondary-index ORDER BY pushdown matrix for one plan.
804pub(crate) fn assess_secondary_order_pushdown_from_parts<K>(
805    model: &EntityModel,
806    logical: &ScalarPlan,
807    access: &AccessPlan<K>,
808) -> SecondaryOrderPushdownEligibility {
809    let order_fields = logical
810        .order
811        .as_ref()
812        .map(|order| order_fields_as_direction_refs(&order.fields));
813
814    assess_secondary_order_pushdown_for_plan(model, order_fields.as_deref(), access)
815}
816
817/// Evaluate the secondary-index ORDER BY pushdown matrix for one plan.
818pub(crate) fn assess_secondary_order_pushdown<K>(
819    model: &EntityModel,
820    plan: &AccessPlannedQuery<K>,
821) -> SecondaryOrderPushdownEligibility {
822    assess_secondary_order_pushdown_from_parts(model, plan.scalar_plan(), &plan.access)
823}
824
825/// Derive pushdown applicability from one plan already validated by planner semantics.
826pub(in crate::db) fn derive_secondary_pushdown_applicability_validated<K>(
827    model: &EntityModel,
828    plan: &AccessPlannedQuery<K>,
829) -> PushdownApplicability {
830    let logical = plan.scalar_plan();
831    debug_assert!(
832        !matches!(logical.order.as_ref(), Some(order) if order.fields.is_empty()),
833        "validated plan must not contain an empty ORDER BY specification",
834    );
835
836    applicability_from_eligibility(assess_secondary_order_pushdown(model, plan))
837}
838
839#[cfg(test)]
840/// Evaluate pushdown eligibility only when secondary-index ORDER BY is applicable.
841pub(crate) fn assess_secondary_order_pushdown_if_applicable<K>(
842    model: &EntityModel,
843    plan: &AccessPlannedQuery<K>,
844) -> PushdownApplicability {
845    derive_secondary_pushdown_applicability_validated(model, plan)
846}
847
848/// Evaluate pushdown applicability for plans that have already passed full
849/// logical/executor validation.
850#[cfg(test)]
851pub(crate) fn assess_secondary_order_pushdown_if_applicable_validated<K>(
852    model: &EntityModel,
853    plan: &AccessPlannedQuery<K>,
854) -> PushdownApplicability {
855    derive_secondary_pushdown_applicability_validated(model, plan)
856}
857
858pub(crate) use planner::{PlannerError, plan_access};
859
860///
861/// AccessPlanProjection
862///
863/// Shared visitor for projecting `AccessPlan` / `AccessPath` into
864/// diagnostics-specific representations.
865///
866
867pub(crate) trait AccessPlanProjection<K> {
868    type Output;
869
870    fn by_key(&mut self, key: &K) -> Self::Output;
871    fn by_keys(&mut self, keys: &[K]) -> Self::Output;
872    fn key_range(&mut self, start: &K, end: &K) -> Self::Output;
873    fn index_prefix(
874        &mut self,
875        index_name: &'static str,
876        index_fields: &[&'static str],
877        prefix_len: usize,
878        values: &[Value],
879    ) -> Self::Output;
880    fn index_range(
881        &mut self,
882        index_name: &'static str,
883        index_fields: &[&'static str],
884        prefix_len: usize,
885        prefix: &[Value],
886        lower: &Bound<Value>,
887        upper: &Bound<Value>,
888    ) -> Self::Output;
889    fn full_scan(&mut self) -> Self::Output;
890    fn union(&mut self, children: Vec<Self::Output>) -> Self::Output;
891    fn intersection(&mut self, children: Vec<Self::Output>) -> Self::Output;
892}
893
894/// Project an access plan by exhaustively walking canonical access variants.
895pub(crate) fn project_access_plan<K, P>(plan: &AccessPlan<K>, projection: &mut P) -> P::Output
896where
897    P: AccessPlanProjection<K>,
898{
899    plan.project(projection)
900}
901
902impl<K> AccessPlan<K> {
903    // Project this plan by recursively visiting all access nodes.
904    fn project<P>(&self, projection: &mut P) -> P::Output
905    where
906        P: AccessPlanProjection<K>,
907    {
908        match self {
909            Self::Path(path) => path.project(projection),
910            Self::Union(children) => {
911                let children = children
912                    .iter()
913                    .map(|child| child.project(projection))
914                    .collect();
915                projection.union(children)
916            }
917            Self::Intersection(children) => {
918                let children = children
919                    .iter()
920                    .map(|child| child.project(projection))
921                    .collect();
922                projection.intersection(children)
923            }
924        }
925    }
926}
927
928impl<K> AccessPath<K> {
929    // Project one concrete path variant via the shared projection surface.
930    fn project<P>(&self, projection: &mut P) -> P::Output
931    where
932        P: AccessPlanProjection<K>,
933    {
934        match self {
935            Self::ByKey(key) => projection.by_key(key),
936            Self::ByKeys(keys) => projection.by_keys(keys),
937            Self::KeyRange { start, end } => projection.key_range(start, end),
938            Self::IndexPrefix { index, values } => {
939                projection.index_prefix(index.name, index.fields, values.len(), values)
940            }
941            Self::IndexRange { spec } => projection.index_range(
942                spec.index().name,
943                spec.index().fields,
944                spec.prefix_values().len(),
945                spec.prefix_values(),
946                spec.lower(),
947                spec.upper(),
948            ),
949            Self::FullScan => projection.full_scan(),
950        }
951    }
952}
953
954pub(crate) fn project_explain_access_path<P>(
955    access: &ExplainAccessPath,
956    projection: &mut P,
957) -> P::Output
958where
959    P: AccessPlanProjection<Value>,
960{
961    match access {
962        ExplainAccessPath::ByKey { key } => projection.by_key(key),
963        ExplainAccessPath::ByKeys { keys } => projection.by_keys(keys),
964        ExplainAccessPath::KeyRange { start, end } => projection.key_range(start, end),
965        ExplainAccessPath::IndexPrefix {
966            name,
967            fields,
968            prefix_len,
969            values,
970        } => projection.index_prefix(name, fields, *prefix_len, values),
971        ExplainAccessPath::IndexRange {
972            name,
973            fields,
974            prefix_len,
975            prefix,
976            lower,
977            upper,
978        } => projection.index_range(name, fields, *prefix_len, prefix, lower, upper),
979        ExplainAccessPath::FullScan => projection.full_scan(),
980        ExplainAccessPath::Union(children) => {
981            let children = children
982                .iter()
983                .map(|child| project_explain_access_path(child, projection))
984                .collect();
985            projection.union(children)
986        }
987        ExplainAccessPath::Intersection(children) => {
988            let children = children
989                .iter()
990                .map(|child| project_explain_access_path(child, projection))
991                .collect();
992            projection.intersection(children)
993        }
994    }
995}
996
997///
998/// TESTS
999///
1000
1001#[cfg(test)]
1002mod access_projection_tests {
1003    use super::*;
1004    use crate::{model::index::IndexModel, value::Value};
1005
1006    const TEST_INDEX_FIELDS: [&str; 2] = ["group", "rank"];
1007    const TEST_INDEX: IndexModel = IndexModel::new(
1008        "tests::group_rank",
1009        "tests::store",
1010        &TEST_INDEX_FIELDS,
1011        false,
1012    );
1013
1014    #[derive(Default)]
1015    struct AccessPlanEventProjection {
1016        events: Vec<&'static str>,
1017        union_child_counts: Vec<usize>,
1018        intersection_child_counts: Vec<usize>,
1019        seen_index: Option<(&'static str, usize, usize, usize)>,
1020    }
1021
1022    impl AccessPlanProjection<u64> for AccessPlanEventProjection {
1023        type Output = ();
1024
1025        fn by_key(&mut self, _key: &u64) -> Self::Output {
1026            self.events.push("by_key");
1027        }
1028
1029        fn by_keys(&mut self, keys: &[u64]) -> Self::Output {
1030            self.events.push("by_keys");
1031            assert_eq!(keys, [2, 3].as_slice());
1032        }
1033
1034        fn key_range(&mut self, start: &u64, end: &u64) -> Self::Output {
1035            self.events.push("key_range");
1036            assert_eq!((*start, *end), (4, 9));
1037        }
1038
1039        fn index_prefix(
1040            &mut self,
1041            index_name: &'static str,
1042            index_fields: &[&'static str],
1043            prefix_len: usize,
1044            values: &[Value],
1045        ) -> Self::Output {
1046            self.events.push("index_prefix");
1047            self.seen_index = Some((index_name, index_fields.len(), prefix_len, values.len()));
1048        }
1049
1050        fn index_range(
1051            &mut self,
1052            index_name: &'static str,
1053            index_fields: &[&'static str],
1054            prefix_len: usize,
1055            prefix: &[Value],
1056            lower: &Bound<Value>,
1057            upper: &Bound<Value>,
1058        ) -> Self::Output {
1059            self.events.push("index_range");
1060            self.seen_index = Some((index_name, index_fields.len(), prefix_len, prefix.len()));
1061            assert_eq!(lower, &Bound::Included(Value::Uint(8)));
1062            assert_eq!(upper, &Bound::Excluded(Value::Uint(12)));
1063        }
1064
1065        fn full_scan(&mut self) -> Self::Output {
1066            self.events.push("full_scan");
1067        }
1068
1069        fn union(&mut self, children: Vec<Self::Output>) -> Self::Output {
1070            self.events.push("union");
1071            self.union_child_counts.push(children.len());
1072        }
1073
1074        fn intersection(&mut self, children: Vec<Self::Output>) -> Self::Output {
1075            self.events.push("intersection");
1076            self.intersection_child_counts.push(children.len());
1077        }
1078    }
1079
1080    #[test]
1081    fn project_access_plan_walks_canonical_access_variants() {
1082        let plan: AccessPlan<u64> = AccessPlan::Union(vec![
1083            AccessPlan::path(AccessPath::ByKey(1)),
1084            AccessPlan::path(AccessPath::ByKeys(vec![2, 3])),
1085            AccessPlan::path(AccessPath::KeyRange { start: 4, end: 9 }),
1086            AccessPlan::path(AccessPath::IndexPrefix {
1087                index: TEST_INDEX,
1088                values: vec![Value::Uint(7)],
1089            }),
1090            AccessPlan::path(AccessPath::index_range(
1091                TEST_INDEX,
1092                vec![Value::Uint(7)],
1093                Bound::Included(Value::Uint(8)),
1094                Bound::Excluded(Value::Uint(12)),
1095            )),
1096            AccessPlan::Intersection(vec![
1097                AccessPlan::path(AccessPath::FullScan),
1098                AccessPlan::path(AccessPath::ByKey(11)),
1099            ]),
1100        ]);
1101
1102        let mut projection = AccessPlanEventProjection::default();
1103        project_access_plan(&plan, &mut projection);
1104
1105        assert_eq!(projection.union_child_counts, vec![6]);
1106        assert_eq!(projection.intersection_child_counts, vec![2]);
1107        assert_eq!(projection.seen_index, Some((TEST_INDEX.name, 2, 1, 1)));
1108        assert!(
1109            projection.events.contains(&"by_key"),
1110            "projection must visit by-key variants"
1111        );
1112        assert!(
1113            projection.events.contains(&"by_keys"),
1114            "projection must visit by-keys variants"
1115        );
1116        assert!(
1117            projection.events.contains(&"key_range"),
1118            "projection must visit key-range variants"
1119        );
1120        assert!(
1121            projection.events.contains(&"index_prefix"),
1122            "projection must visit index-prefix variants"
1123        );
1124        assert!(
1125            projection.events.contains(&"index_range"),
1126            "projection must visit index-range variants"
1127        );
1128        assert!(
1129            projection.events.contains(&"full_scan"),
1130            "projection must visit full-scan variants"
1131        );
1132    }
1133
1134    #[derive(Default)]
1135    struct ExplainAccessEventProjection {
1136        events: Vec<&'static str>,
1137        union_child_counts: Vec<usize>,
1138        intersection_child_counts: Vec<usize>,
1139        seen_index: Option<(&'static str, usize, usize, usize)>,
1140    }
1141
1142    impl AccessPlanProjection<Value> for ExplainAccessEventProjection {
1143        type Output = ();
1144
1145        fn by_key(&mut self, key: &Value) -> Self::Output {
1146            self.events.push("by_key");
1147            assert_eq!(key, &Value::Uint(10));
1148        }
1149
1150        fn by_keys(&mut self, keys: &[Value]) -> Self::Output {
1151            self.events.push("by_keys");
1152            assert_eq!(keys, [Value::Uint(20), Value::Uint(30)].as_slice());
1153        }
1154
1155        fn key_range(&mut self, start: &Value, end: &Value) -> Self::Output {
1156            self.events.push("key_range");
1157            assert_eq!((start, end), (&Value::Uint(40), &Value::Uint(90)));
1158        }
1159
1160        fn index_prefix(
1161            &mut self,
1162            index_name: &'static str,
1163            index_fields: &[&'static str],
1164            prefix_len: usize,
1165            values: &[Value],
1166        ) -> Self::Output {
1167            self.events.push("index_prefix");
1168            self.seen_index = Some((index_name, index_fields.len(), prefix_len, values.len()));
1169        }
1170
1171        fn index_range(
1172            &mut self,
1173            index_name: &'static str,
1174            index_fields: &[&'static str],
1175            prefix_len: usize,
1176            prefix: &[Value],
1177            lower: &Bound<Value>,
1178            upper: &Bound<Value>,
1179        ) -> Self::Output {
1180            self.events.push("index_range");
1181            self.seen_index = Some((index_name, index_fields.len(), prefix_len, prefix.len()));
1182            assert_eq!(lower, &Bound::Included(Value::Uint(8)));
1183            assert_eq!(upper, &Bound::Excluded(Value::Uint(12)));
1184        }
1185
1186        fn full_scan(&mut self) -> Self::Output {
1187            self.events.push("full_scan");
1188        }
1189
1190        fn union(&mut self, children: Vec<Self::Output>) -> Self::Output {
1191            self.events.push("union");
1192            self.union_child_counts.push(children.len());
1193        }
1194
1195        fn intersection(&mut self, children: Vec<Self::Output>) -> Self::Output {
1196            self.events.push("intersection");
1197            self.intersection_child_counts.push(children.len());
1198        }
1199    }
1200
1201    #[test]
1202    fn project_explain_access_path_walks_canonical_access_variants() {
1203        let access = ExplainAccessPath::Union(vec![
1204            ExplainAccessPath::ByKey {
1205                key: Value::Uint(10),
1206            },
1207            ExplainAccessPath::ByKeys {
1208                keys: vec![Value::Uint(20), Value::Uint(30)],
1209            },
1210            ExplainAccessPath::KeyRange {
1211                start: Value::Uint(40),
1212                end: Value::Uint(90),
1213            },
1214            ExplainAccessPath::IndexPrefix {
1215                name: TEST_INDEX.name,
1216                fields: vec!["group", "rank"],
1217                prefix_len: 1,
1218                values: vec![Value::Uint(7)],
1219            },
1220            ExplainAccessPath::IndexRange {
1221                name: TEST_INDEX.name,
1222                fields: vec!["group", "rank"],
1223                prefix_len: 1,
1224                prefix: vec![Value::Uint(7)],
1225                lower: Bound::Included(Value::Uint(8)),
1226                upper: Bound::Excluded(Value::Uint(12)),
1227            },
1228            ExplainAccessPath::Intersection(vec![
1229                ExplainAccessPath::FullScan,
1230                ExplainAccessPath::ByKey {
1231                    key: Value::Uint(10),
1232                },
1233            ]),
1234        ]);
1235
1236        let mut projection = ExplainAccessEventProjection::default();
1237        project_explain_access_path(&access, &mut projection);
1238
1239        assert_eq!(projection.union_child_counts, vec![6]);
1240        assert_eq!(projection.intersection_child_counts, vec![2]);
1241        assert_eq!(projection.seen_index, Some((TEST_INDEX.name, 2, 1, 1)));
1242        assert!(
1243            projection.events.contains(&"by_key"),
1244            "projection must visit by-key variants"
1245        );
1246        assert!(
1247            projection.events.contains(&"by_keys"),
1248            "projection must visit by-keys variants"
1249        );
1250        assert!(
1251            projection.events.contains(&"key_range"),
1252            "projection must visit key-range variants"
1253        );
1254        assert!(
1255            projection.events.contains(&"index_prefix"),
1256            "projection must visit index-prefix variants"
1257        );
1258        assert!(
1259            projection.events.contains(&"index_range"),
1260            "projection must visit index-range variants"
1261        );
1262        assert!(
1263            projection.events.contains(&"full_scan"),
1264            "projection must visit full-scan variants"
1265        );
1266    }
1267}
icydb_core/db/query/plan/mod.rs

icydb_core/db/query/plan/
mod.rs
