spg_engine/
plan_cache.rs

1//! v6.3.0 — Engine-level plan cache.
2//!
3//! Caches the post-`prepare()` `Statement` (clock-rewritten,
4//! ORDER-BY-position-resolved, JOIN-reordered) keyed on the raw SQL
5//! string. Hit path skips parse + clock rewrite + JOIN reorder — for
6//! a 5-table JOIN that's the dominant cost.
7//!
8//! `statistics_version` and `source_tables` are stored on the entry
9//! so v6.3.1 can invalidate selectively when ANALYZE bumps the stats
10//! version, or when DDL changes one of the source tables.
11//!
12//! `describe_columns` is reserved for v6.3.3 Describe pre-Execute —
13//! v6.3.0 leaves it empty.
14//!
15//! Cache is bounded by `PLAN_CACHE_MAX_ENTRIES` (256). Eviction is
16//! LRU via a `VecDeque<String>` move-to-back on get. Both `get` and
17//! `insert` are sub-microsecond at 256 entries.
18
19use alloc::collections::{BTreeMap, VecDeque};
20use alloc::string::String;
21use alloc::vec::Vec;
22
23use spg_sql::ast::{Expr, FromClause, FromJoin, SelectItem, SelectStatement, Statement, TableRef};
24use spg_storage::ColumnSchema;
25
26/// Hard cap on plan-cache entries. At 256 the cap holds the typical
27/// app's reusable statement set without unbounded growth; at average
28/// 4 KiB per cached AST the worst-case footprint is 1 MiB per
29/// Engine. NOT a frozen surface — v6.3.x can re-tune.
30pub(crate) const PLAN_CACHE_MAX_ENTRIES: usize = 256;
31
32/// One cached plan. The cached `stmt` is the same one
33/// `Engine::prepare()` would return — parse + clock rewrite +
34/// ORDER-BY position resolution + JOIN reorder all already applied.
35#[derive(Debug, Clone)]
36pub struct PreparedPlan {
37    pub stmt: Statement,
38    /// Statistics version snapshot at prepare time. v6.3.1 compares
39    /// this against the live statistics version and evicts on
40    /// mismatch. v6.3.0 stores it but doesn't consult on lookup.
41    pub statistics_version: u64,
42    /// Tables referenced by `stmt` (deduplicated, lexical order).
43    /// v6.3.1 uses this for selective DDL/ANALYZE invalidation.
44    pub source_tables: Vec<String>,
45    /// Column shape v6.3.3 will populate for `Describe statement`.
46    /// v6.3.0 leaves this empty.
47    pub describe_columns: Vec<ColumnSchema>,
48}
49
50#[derive(Debug, Clone)]
51pub struct PlanCache {
52    /// SQL string → cached plan. `BTreeMap` for deterministic
53    /// iteration (test stability); ordering of LRU is tracked
54    /// separately in `lru`.
55    entries: BTreeMap<String, PreparedPlan>,
56    /// LRU queue. Newest entry at the back. `get` moves the
57    /// referenced key to the back; `insert` pushes to the back and
58    /// evicts the front when at cap.
59    lru: VecDeque<String>,
60    /// v6.5.6 — runtime-configurable cap. Defaults to
61    /// `PLAN_CACHE_MAX_ENTRIES` (256); spg-server reads
62    /// `SPG_PLAN_CACHE_MAX` env at startup and overrides via
63    /// `PlanCache::with_max_entries`.
64    max_entries: usize,
65}
66
67impl Default for PlanCache {
68    fn default() -> Self {
69        Self {
70            entries: BTreeMap::new(),
71            lru: VecDeque::new(),
72            max_entries: PLAN_CACHE_MAX_ENTRIES,
73        }
74    }
75}
76
77impl PlanCache {
78    pub fn new() -> Self {
79        Self::default()
80    }
81
82    /// v6.5.6 — runtime cap override. Operator-tunable via
83    /// `SPG_PLAN_CACHE_MAX` env at startup. Minimum 1; values
84    /// above the compile-time `PLAN_CACHE_MAX_ENTRIES` are
85    /// clamped down to it (defensive backstop against runaway
86    /// configs).
87    pub fn set_max_entries(&mut self, n: usize) {
88        self.max_entries = n.max(1).min(PLAN_CACHE_MAX_ENTRIES);
89    }
90
91    pub fn max_entries(&self) -> usize {
92        self.max_entries
93    }
94
95    pub fn len(&self) -> usize {
96        self.entries.len()
97    }
98
99    pub fn is_empty(&self) -> bool {
100        self.entries.is_empty()
101    }
102
103    /// Read-only peek without LRU promotion. Used by introspection
104    /// and v6.3.1 tests that want to inspect a cached plan's
105    /// metadata without mutating the cache.
106    pub fn get_snapshot(&self, sql: &str) -> Option<&PreparedPlan> {
107        self.entries.get(sql)
108    }
109
110    /// Returns the cached plan if present and promotes it to most-
111    /// recently-used. Returns `None` on miss.
112    pub fn get(&mut self, sql: &str) -> Option<&PreparedPlan> {
113        if !self.entries.contains_key(sql) {
114            return None;
115        }
116        if let Some(idx) = self.lru.iter().position(|k| k == sql) {
117            let key = self.lru.remove(idx).expect("idx came from position()");
118            self.lru.push_back(key);
119        }
120        self.entries.get(sql)
121    }
122
123    /// Inserts (or replaces) the plan. Evicts the oldest entry if
124    /// we'd exceed `PLAN_CACHE_MAX_ENTRIES`.
125    pub fn insert(&mut self, sql: String, plan: PreparedPlan) {
126        if self.entries.contains_key(&sql) {
127            if let Some(idx) = self.lru.iter().position(|k| k == &sql) {
128                let key = self.lru.remove(idx).expect("idx came from position()");
129                self.lru.push_back(key);
130            }
131            self.entries.insert(sql, plan);
132            return;
133        }
134        if self.entries.len() >= self.max_entries {
135            if let Some(oldest) = self.lru.pop_front() {
136                self.entries.remove(&oldest);
137            }
138        }
139        self.lru.push_back(sql.clone());
140        self.entries.insert(sql, plan);
141    }
142
143    pub fn clear(&mut self) {
144        self.entries.clear();
145        self.lru.clear();
146    }
147
148    /// v6.3.1 will use this for explicit invalidation. v6.3.0
149    /// exposes it for tests + future use.
150    pub fn evict(&mut self, sql: &str) -> Option<PreparedPlan> {
151        let plan = self.entries.remove(sql)?;
152        if let Some(idx) = self.lru.iter().position(|k| k == sql) {
153            self.lru.remove(idx);
154        }
155        Some(plan)
156    }
157
158    /// v6.3.1 will use this to evict every plan that references a
159    /// specific table.
160    pub fn evict_referencing(&mut self, table: &str) -> usize {
161        let to_evict: Vec<String> = self
162            .entries
163            .iter()
164            .filter_map(|(k, p)| {
165                if p.source_tables.iter().any(|t| t == table) {
166                    Some(k.clone())
167                } else {
168                    None
169                }
170            })
171            .collect();
172        let n = to_evict.len();
173        for k in to_evict {
174            self.entries.remove(&k);
175            if let Some(idx) = self.lru.iter().position(|x| x == &k) {
176                self.lru.remove(idx);
177            }
178        }
179        n
180    }
181}
182
183/// Walk a `Statement` and collect every distinct table name referenced
184/// by its FROM clauses (including JOIN tables and subquery FROMs).
185/// Used by `PreparedPlan::source_tables` for v6.3.1 selective
186/// invalidation.
187pub fn collect_source_tables(stmt: &Statement) -> Vec<String> {
188    let mut out: Vec<String> = Vec::new();
189    match stmt {
190        Statement::Select(s) => collect_from_select(s, &mut out),
191        Statement::Insert(s) => push_unique(&mut out, &s.table),
192        Statement::Update(s) => {
193            push_unique(&mut out, &s.table);
194            if let Some(w) = &s.where_ {
195                collect_expr(w, &mut out);
196            }
197        }
198        Statement::Delete(s) => {
199            push_unique(&mut out, &s.table);
200            if let Some(w) = &s.where_ {
201                collect_expr(w, &mut out);
202            }
203        }
204        Statement::Explain(inner) => {
205            collect_from_select(&inner.inner, &mut out);
206        }
207        _ => {}
208    }
209    out.sort();
210    out.dedup();
211    out
212}
213
214fn collect_from_select(s: &SelectStatement, out: &mut Vec<String>) {
215    if let Some(from) = &s.from {
216        collect_from_clause(from, out);
217    }
218    if let Some(w) = &s.where_ {
219        collect_expr(w, out);
220    }
221    if let Some(h) = &s.having {
222        collect_expr(h, out);
223    }
224    for item in &s.items {
225        if let SelectItem::Expr { expr, .. } = item {
226            collect_expr(expr, out);
227        }
228    }
229    for (_, peer) in &s.unions {
230        collect_from_select(peer, out);
231    }
232}
233
234fn collect_from_clause(from: &FromClause, out: &mut Vec<String>) {
235    collect_table_ref(&from.primary, out);
236    for j in &from.joins {
237        collect_from_join(j, out);
238    }
239}
240
241fn collect_from_join(j: &FromJoin, out: &mut Vec<String>) {
242    collect_table_ref(&j.table, out);
243    if let Some(on) = &j.on {
244        collect_expr(on, out);
245    }
246}
247
248fn collect_table_ref(t: &TableRef, out: &mut Vec<String>) {
249    push_unique(out, &t.name);
250}
251
252fn collect_expr(e: &Expr, out: &mut Vec<String>) {
253    match e {
254        Expr::AggregateOrdered { call, order_by, .. } => {
255            collect_expr(call, out);
256            for o in order_by {
257                collect_expr(&o.expr, out);
258            }
259        }
260        Expr::ScalarSubquery(inner) => collect_from_select(inner, out),
261        Expr::Exists { subquery, .. } => collect_from_select(subquery, out),
262        Expr::InSubquery { expr, subquery, .. } => {
263            collect_expr(expr, out);
264            collect_from_select(subquery, out);
265        }
266        Expr::Binary { lhs, rhs, .. } => {
267            collect_expr(lhs, out);
268            collect_expr(rhs, out);
269        }
270        Expr::Unary { expr, .. } => collect_expr(expr, out),
271        Expr::Cast { expr, .. } => collect_expr(expr, out),
272        Expr::IsNull { expr, .. } => collect_expr(expr, out),
273        Expr::Like { expr, pattern, .. } => {
274            collect_expr(expr, out);
275            collect_expr(pattern, out);
276        }
277        Expr::FunctionCall { args, .. } => {
278            for a in args {
279                collect_expr(a, out);
280            }
281        }
282        Expr::WindowFunction {
283            args,
284            partition_by,
285            order_by,
286            ..
287        } => {
288            for a in args {
289                collect_expr(a, out);
290            }
291            for p in partition_by {
292                collect_expr(p, out);
293            }
294            for (o, _, _) in order_by {
295                collect_expr(o, out);
296            }
297        }
298        Expr::Extract { source, .. } => collect_expr(source, out),
299        Expr::Array(items) => {
300            for elem in items {
301                collect_expr(elem, out);
302            }
303        }
304        Expr::ArraySubscript { target, index } => {
305            collect_expr(target, out);
306            collect_expr(index, out);
307        }
308        Expr::AnyAll { expr, array, .. } => {
309            collect_expr(expr, out);
310            collect_expr(array, out);
311        }
312        Expr::InList { expr, list, .. } => {
313            collect_expr(expr, out);
314            for item in list {
315                collect_expr(item, out);
316            }
317        }
318        Expr::Case {
319            operand,
320            branches,
321            else_branch,
322        } => {
323            if let Some(o) = operand {
324                collect_expr(o, out);
325            }
326            for (w, t) in branches {
327                collect_expr(w, out);
328                collect_expr(t, out);
329            }
330            if let Some(e) = else_branch {
331                collect_expr(e, out);
332            }
333        }
334        Expr::Literal(_) | Expr::Column(_) | Expr::Placeholder(_) => {}
335    }
336}
337
338fn push_unique(out: &mut Vec<String>, s: &str) {
339    if !out.iter().any(|x| x == s) {
340        out.push(String::from(s));
341    }
342}
343
344// ── unit tests ────────────────────────────────────────────────────
345
346#[cfg(test)]
347mod tests {
348    use super::*;
349    use alloc::string::ToString;
350    use spg_sql::parser::parse_statement;
351
352    fn dummy_plan(version: u64, tables: &[&str]) -> PreparedPlan {
353        let stmt = parse_statement("SELECT 1").expect("trivial SELECT parses");
354        PreparedPlan {
355            stmt,
356            statistics_version: version,
357            source_tables: tables.iter().map(|s| s.to_string()).collect(),
358            describe_columns: Vec::new(),
359        }
360    }
361
362    #[test]
363    fn new_cache_is_empty() {
364        let cache = PlanCache::new();
365        assert!(cache.is_empty());
366        assert_eq!(cache.len(), 0);
367    }
368
369    #[test]
370    fn insert_then_get_returns_the_plan() {
371        let mut cache = PlanCache::new();
372        cache.insert("SELECT 1".into(), dummy_plan(0, &["t"]));
373        assert_eq!(cache.len(), 1);
374        let plan = cache.get("SELECT 1").expect("hit");
375        assert_eq!(plan.source_tables, alloc::vec!["t".to_string()]);
376    }
377
378    #[test]
379    fn miss_returns_none() {
380        let mut cache = PlanCache::new();
381        cache.insert("SELECT 1".into(), dummy_plan(0, &[]));
382        assert!(cache.get("SELECT 2").is_none());
383    }
384
385    #[test]
386    fn replace_overwrites_existing_entry() {
387        let mut cache = PlanCache::new();
388        cache.insert("SELECT 1".into(), dummy_plan(1, &["a"]));
389        cache.insert("SELECT 1".into(), dummy_plan(2, &["b"]));
390        assert_eq!(cache.len(), 1);
391        let plan = cache.get("SELECT 1").expect("hit");
392        assert_eq!(plan.statistics_version, 2);
393    }
394
395    #[test]
396    fn lru_evicts_oldest_at_cap() {
397        let mut cache = PlanCache::new();
398        for i in 0..PLAN_CACHE_MAX_ENTRIES {
399            cache.insert(alloc::format!("SELECT {i}"), dummy_plan(i as u64, &[]));
400        }
401        assert_eq!(cache.len(), PLAN_CACHE_MAX_ENTRIES);
402        cache.insert("SELECT new".into(), dummy_plan(999, &[]));
403        assert_eq!(cache.len(), PLAN_CACHE_MAX_ENTRIES);
404        assert!(cache.get("SELECT 0").is_none());
405        assert!(cache.get("SELECT new").is_some());
406    }
407
408    #[test]
409    fn get_promotes_lru_position() {
410        let mut cache = PlanCache::new();
411        cache.insert("a".into(), dummy_plan(0, &[]));
412        cache.insert("b".into(), dummy_plan(0, &[]));
413        cache.insert("c".into(), dummy_plan(0, &[]));
414        // Touch "a" to make it MRU.
415        let _ = cache.get("a");
416        // Fill to cap so the next insert evicts. After we touched "a",
417        // "b" should be the oldest now.
418        for i in 0..(PLAN_CACHE_MAX_ENTRIES - 3) {
419            cache.insert(alloc::format!("filler{i}"), dummy_plan(0, &[]));
420        }
421        cache.insert("trigger".into(), dummy_plan(0, &[]));
422        assert!(
423            cache.get("a").is_some(),
424            "a was MRU after get(); should survive"
425        );
426        assert!(cache.get("b").is_none(), "b should be evicted");
427    }
428
429    #[test]
430    fn clear_drops_everything() {
431        let mut cache = PlanCache::new();
432        cache.insert("a".into(), dummy_plan(0, &[]));
433        cache.insert("b".into(), dummy_plan(0, &[]));
434        cache.clear();
435        assert!(cache.is_empty());
436        assert!(cache.get("a").is_none());
437    }
438
439    #[test]
440    fn evict_referencing_drops_only_matching_plans() {
441        let mut cache = PlanCache::new();
442        cache.insert("a".into(), dummy_plan(0, &["users"]));
443        cache.insert("b".into(), dummy_plan(0, &["orders"]));
444        cache.insert("c".into(), dummy_plan(0, &["users", "orders"]));
445        let n = cache.evict_referencing("users");
446        assert_eq!(n, 2);
447        assert!(cache.get("a").is_none());
448        assert!(cache.get("b").is_some());
449        assert!(cache.get("c").is_none());
450    }
451
452    #[test]
453    fn collect_source_tables_from_simple_select() {
454        let stmt = parse_statement("SELECT a, b FROM t1 WHERE x = 1").expect("parses");
455        let tables = collect_source_tables(&stmt);
456        assert_eq!(tables, alloc::vec!["t1".to_string()]);
457    }
458
459    #[test]
460    fn collect_source_tables_from_join() {
461        let stmt =
462            parse_statement("SELECT * FROM t1 JOIN t2 ON t1.a = t2.b JOIN t3 ON t2.c = t3.d")
463                .expect("parses");
464        let tables = collect_source_tables(&stmt);
465        assert_eq!(
466            tables,
467            alloc::vec!["t1".to_string(), "t2".to_string(), "t3".to_string()]
468        );
469    }
470
471    #[test]
472    fn collect_source_tables_dedupes_self_join() {
473        let stmt = parse_statement("SELECT * FROM t1 a JOIN t1 b ON a.x = b.y").expect("parses");
474        let tables = collect_source_tables(&stmt);
475        assert_eq!(tables, alloc::vec!["t1".to_string()]);
476    }
477}
spg_engine/plan_cache.rs

spg_engine/
plan_cache.rs
