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        // Planner does not validate filter semantics; callers must validate separately.
88        // If filter is a primary key match
89        // this would handle One and Many queries
90        if let Some(plan) = self.extract_from_filter::<E>() {
91            return plan;
92        }
93
94        // check for index matches
95        // THIS WILL DO THE INDEX LOOKUPS
96        if !E::INDEXES.is_empty()
97            && let Some(plan) = self.extract_from_index::<E>()
98        {
99            return plan;
100        }
101
102        // Fallback: do a full scan
103        QueryPlan::FullScan
104    }
105
106    // extract_from_filter
107    fn extract_from_filter<E: EntityKind>(&self) -> Option<QueryPlan> {
108        let Some(filter) = &self.filter else {
109            return None;
110        };
111
112        match filter {
113            FilterExpr::Clause(clause) if clause.field == E::PRIMARY_KEY => match clause.cmp {
114                Cmp::Eq => clause.value.as_key().map(|key| QueryPlan::Keys(vec![key])),
115
116                Cmp::In => {
117                    if let Value::List(values) = &clause.value {
118                        let mut keys = values
119                            .iter()
120                            .filter_map(Value::as_key_coerced)
121                            .collect::<Vec<_>>();
122                        if keys.is_empty() {
123                            return Some(QueryPlan::Keys(Vec::new()));
124                        }
125                        keys.sort_unstable();
126                        keys.dedup();
127                        Some(QueryPlan::Keys(keys))
128                    } else {
129                        None
130                    }
131                }
132
133                _ => None,
134            },
135
136            _ => None,
137        }
138    }
139
140    // extract_from_index: build a leftmost equality prefix in terms of Value.
141    // Skip index planning when any equality value is not indexable.
142    fn extract_from_index<E: EntityKind>(&self) -> Option<QueryPlan> {
143        let Some(filter) = &self.filter else {
144            return None;
145        };
146
147        let mut best: Option<(usize, IndexPlan)> = None;
148
149        for index in E::INDEXES {
150            // Build leftmost equality prefix (only == supported for hashed indexes)
151            let mut values: Vec<Value> = Vec::with_capacity(index.fields.len());
152            let mut unusable = false;
153
154            for field in index.fields {
155                if let Some(v) = Self::find_eq_value(filter, field) {
156                    if v.to_index_fingerprint().is_none() {
157                        unusable = true;
158                        break;
159                    }
160                    values.push(v);
161                } else {
162                    break; // stop at first non-match
163                }
164            }
165
166            // Skip indexes that produced no equality prefix
167            if unusable || values.is_empty() {
168                continue;
169            }
170
171            let score = values.len();
172            let cand = (score, IndexPlan { index, values });
173
174            match &best {
175                Some((best_score, _)) if *best_score >= score => { /* keep current best */ }
176                _ => best = Some(cand),
177            }
178        }
179
180        best.map(|(_, plan)| QueryPlan::Index(plan))
181    }
182
183    /// Find an equality clause (`field == ?`) anywhere in the filter tree and return the Value.
184    fn find_eq_value(filter: &FilterExpr, field: &str) -> Option<Value> {
185        match filter {
186            FilterExpr::Clause(c) if c.field == field && matches!(c.cmp, Cmp::Eq) => {
187                Some(c.value.clone())
188            }
189            // Walk conjunctive subtrees
190            FilterExpr::And(list) => list.iter().find_map(|f| Self::find_eq_value(f, field)),
191            _ => None,
192        }
193    }
194}
icydb_core/db/query/planner.rs

icydb_core/db/query/
planner.rs
