icydb_core/db/query/
planner.rs

1use crate::{
2    db::primitives::filter::{Cmp, FilterExpr},
3    prelude::*,
4    traits::EntityKind,
5};
6use std::fmt::{self, Display};
7
8///
9/// QueryPlan
10///
11
12#[derive(Debug)]
13pub enum QueryPlan {
14    FullScan,
15    Index(IndexPlan),
16    Keys(Vec<Key>),
17    /// Inclusive range over primary keys.
18    Range(Key, Key),
19}
20
21impl fmt::Display for QueryPlan {
22    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
23        match self {
24            Self::Index(plan) => write!(f, "Index({plan})"),
25
26            Self::Keys(keys) => {
27                // Show up to 5 keys, then ellipsize
28                let preview: Vec<String> = keys.iter().take(5).map(|k| format!("{k:?}")).collect();
29
30                if keys.len() > 5 {
31                    write!(f, "Keys[{}… total {}]", preview.join(", "), keys.len())
32                } else {
33                    write!(f, "Keys[{}]", preview.join(", "))
34                }
35            }
36
37            Self::Range(start, end) => {
38                write!(f, "Range({start:?} → {end:?})")
39            }
40
41            Self::FullScan => write!(f, "FullScan"),
42        }
43    }
44}
45
46///
47/// IndexPlan
48///
49
50#[derive(Debug)]
51pub struct IndexPlan {
52    pub index: &'static IndexModel,
53    pub values: Vec<Value>,
54}
55
56impl Display for IndexPlan {
57    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
58        let values: Vec<String> = self.values.iter().map(|v| format!("{v:?}")).collect();
59        write!(f, "index={} values=[{}]", self.index, values.join(", "))
60    }
61}
62
63///
64/// QueryPlanner
65///
66
67#[derive(Debug)]
68pub struct QueryPlanner {
69    pub filter: Option<FilterExpr>,
70}
71
72impl QueryPlanner {
73    #[must_use]
74    /// Create a planner from an optional filter expression.
75    pub fn new(filter: Option<&FilterExpr>) -> Self {
76        Self {
77            filter: filter.cloned(),
78        }
79    }
80
81    #[must_use]
82    /// Generate a query plan for the given entity type.
83    ///
84    /// Index plans are only produced when all equality values are indexable;
85    /// otherwise the planner falls back to a scan.
86    pub fn plan<E: EntityKind>(&self) -> QueryPlan {
87        // If filter is a primary key match
88        // this would handle One and Many queries
89        if let Some(plan) = self.extract_from_filter::<E>() {
90            return plan;
91        }
92
93        // check for index matches
94        // THIS WILL DO THE INDEX LOOKUPS
95        if !E::INDEXES.is_empty()
96            && let Some(plan) = self.extract_from_index::<E>()
97        {
98            return plan;
99        }
100
101        // Fallback: do a full scan
102        QueryPlan::FullScan
103    }
104
105    // extract_from_filter
106    fn extract_from_filter<E: EntityKind>(&self) -> Option<QueryPlan> {
107        let Some(filter) = &self.filter else {
108            return None;
109        };
110
111        match filter {
112            FilterExpr::Clause(clause) if clause.field == E::PRIMARY_KEY => match clause.cmp {
113                Cmp::Eq => clause.value.as_key().map(|key| QueryPlan::Keys(vec![key])),
114
115                Cmp::In => {
116                    if let Value::List(values) = &clause.value {
117                        let mut keys = values
118                            .iter()
119                            .filter_map(Value::as_key_coerced)
120                            .collect::<Vec<_>>();
121                        if keys.is_empty() {
122                            return Some(QueryPlan::Keys(Vec::new()));
123                        }
124                        keys.sort_unstable();
125                        keys.dedup();
126                        Some(QueryPlan::Keys(keys))
127                    } else {
128                        None
129                    }
130                }
131
132                _ => None,
133            },
134
135            _ => None,
136        }
137    }
138
139    // extract_from_index: build a leftmost equality prefix in terms of Value.
140    // Skip index planning when any equality value is not indexable.
141    fn extract_from_index<E: EntityKind>(&self) -> Option<QueryPlan> {
142        let Some(filter) = &self.filter else {
143            return None;
144        };
145
146        let mut best: Option<(usize, IndexPlan)> = None;
147
148        for index in E::INDEXES {
149            // Build leftmost equality prefix (only == supported for hashed indexes)
150            let mut values: Vec<Value> = Vec::with_capacity(index.fields.len());
151            let mut unusable = false;
152
153            for field in index.fields {
154                if let Some(v) = Self::find_eq_value(filter, field) {
155                    if v.to_index_fingerprint().is_none() {
156                        unusable = true;
157                        break;
158                    }
159                    values.push(v);
160                } else {
161                    break; // stop at first non-match
162                }
163            }
164
165            // Skip indexes that produced no equality prefix
166            if unusable || values.is_empty() {
167                continue;
168            }
169
170            let score = values.len();
171            let cand = (score, IndexPlan { index, values });
172
173            match &best {
174                Some((best_score, _)) if *best_score >= score => { /* keep current best */ }
175                _ => best = Some(cand),
176            }
177        }
178
179        best.map(|(_, plan)| QueryPlan::Index(plan))
180    }
181
182    /// Find an equality clause (`field == ?`) anywhere in the filter tree and return the Value.
183    fn find_eq_value(filter: &FilterExpr, field: &str) -> Option<Value> {
184        match filter {
185            FilterExpr::Clause(c) if c.field == field && matches!(c.cmp, Cmp::Eq) => {
186                Some(c.value.clone())
187            }
188            // Walk conjunctive subtrees
189            FilterExpr::And(list) => list.iter().find_map(|f| Self::find_eq_value(f, field)),
190            _ => None,
191        }
192    }
193}
icydb_core/db/query/planner.rs

icydb_core/db/query/
planner.rs
