icydb_core/db/query/
planner.rs

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

icydb_core/db/query/
planner.rs
