featherdb_query/planner/
plan.rs

1//! Logical plan definition and methods
2
3use super::cte::CommonTableExpression;
4use super::types::{IndexRange, JoinType, SortOrder};
5use crate::expr::Expr;
6use featherdb_catalog::{Index, Table};
7use featherdb_core::Permissions;
8use std::sync::Arc;
9
10/// Logical plan - represents a query as a tree of relational operators
11#[derive(Debug, Clone)]
12pub enum LogicalPlan {
13    /// Scan a table
14    Scan {
15        table: Arc<Table>,
16        alias: Option<String>,
17        projection: Option<Vec<usize>>,
18        filter: Option<Expr>,
19    },
20
21    /// Index scan - uses an index for efficient lookups
22    /// This provides 100-1000x speedup for indexed queries
23    IndexScan {
24        /// Table being scanned
25        table: Arc<Table>,
26        /// Table alias
27        alias: Option<String>,
28        /// Index to use for the scan
29        index: Index,
30        /// Column index in the table that the index covers (for single-column indexes)
31        index_column: usize,
32        /// Range to scan in the index
33        range: IndexRange,
34        /// Additional filter for non-indexed predicates
35        /// Applied after index lookup
36        residual_filter: Option<Expr>,
37        /// Projection columns
38        projection: Option<Vec<usize>>,
39    },
40
41    /// Direct primary key lookup - O(log N) instead of O(N) scan
42    /// Used when ALL primary key columns have equality predicates
43    PkSeek {
44        table: Arc<Table>,
45        alias: Option<String>,
46        /// One expression per PK column, in PK order
47        key_values: Vec<Expr>,
48        /// Non-PK predicates applied after lookup
49        residual_filter: Option<Expr>,
50        /// Projection columns
51        projection: Option<Vec<usize>>,
52    },
53
54    /// Direct primary key range scan - O(range_size) instead of O(N)
55    /// Used when PK column has range predicates (>=, >, <=, <)
56    PkRangeScan {
57        table: Arc<Table>,
58        alias: Option<String>,
59        /// Range bounds for PK scan
60        range: IndexRange,
61        /// Non-PK predicates applied after lookup
62        residual_filter: Option<Expr>,
63        /// Projection columns
64        projection: Option<Vec<usize>>,
65    },
66
67    /// Filter rows
68    Filter {
69        input: Box<LogicalPlan>,
70        predicate: Expr,
71    },
72
73    /// Project columns
74    Project {
75        input: Box<LogicalPlan>,
76        exprs: Vec<(Expr, String)>,
77    },
78
79    /// Join two inputs
80    Join {
81        left: Box<LogicalPlan>,
82        right: Box<LogicalPlan>,
83        join_type: JoinType,
84        condition: Option<Expr>,
85    },
86
87    /// Aggregate
88    Aggregate {
89        input: Box<LogicalPlan>,
90        group_by: Vec<Expr>,
91        aggregates: Vec<(Expr, String)>,
92    },
93
94    /// Sort
95    Sort {
96        input: Box<LogicalPlan>,
97        order_by: Vec<(Expr, SortOrder)>,
98    },
99
100    /// Limit output rows
101    Limit {
102        input: Box<LogicalPlan>,
103        limit: Option<usize>,
104        offset: usize,
105    },
106
107    /// Distinct
108    Distinct { input: Box<LogicalPlan> },
109
110    /// Insert rows
111    Insert {
112        table: Arc<Table>,
113        columns: Vec<String>,
114        values: Vec<Vec<Expr>>,
115    },
116
117    /// Update rows
118    Update {
119        table: Arc<Table>,
120        assignments: Vec<(String, Expr)>,
121        filter: Option<Expr>,
122    },
123
124    /// Delete rows
125    Delete {
126        table: Arc<Table>,
127        filter: Option<Expr>,
128    },
129
130    /// Create table
131    CreateTable { table: Table },
132
133    /// Drop table
134    DropTable { name: String, if_exists: bool },
135
136    /// Empty relation (for queries with no FROM)
137    EmptyRelation,
138
139    /// Explain plan - shows query execution plan with cost estimates
140    Explain {
141        /// The plan to explain
142        input: Box<LogicalPlan>,
143        /// Whether to show detailed costs
144        verbose: bool,
145        /// Whether to actually run the query and show execution stats
146        analyze: bool,
147    },
148
149    /// Window function evaluation
150    Window {
151        /// Input plan
152        input: Box<LogicalPlan>,
153        /// Window function expressions with their output aliases
154        window_exprs: Vec<(Expr, String)>,
155    },
156
157    /// Alter table schema
158    AlterTable {
159        /// Name of the table to alter
160        table_name: String,
161        /// Operations to perform
162        operations: Vec<featherdb_catalog::AlterTableOp>,
163    },
164
165    /// Common Table Expression (CTE) - WITH clause
166    /// Materializes CTE results and makes them available as virtual tables
167    WithCte {
168        /// CTE definitions (name, columns, plan, is_recursive)
169        ctes: Vec<CommonTableExpression>,
170        /// The main query that uses the CTEs
171        query: Box<LogicalPlan>,
172    },
173
174    /// Scan a CTE by name
175    CteScan {
176        /// Name of the CTE being scanned
177        cte_name: String,
178        /// Table alias (e.g. `eng_dept e1` → alias = Some("e1"))
179        alias: Option<String>,
180        /// Output column names (bare, without prefix)
181        columns: Vec<String>,
182    },
183
184    /// Subquery scan - executes a subquery and provides its results
185    SubqueryScan {
186        /// The subquery plan
187        subquery: Box<LogicalPlan>,
188        /// Unique identifier for tracking
189        subquery_id: usize,
190        /// Output alias
191        alias: Option<String>,
192    },
193
194    /// Semi-join - optimized execution for EXISTS/IN subqueries
195    /// Returns rows from left where at least one matching row exists in right
196    SemiJoin {
197        left: Box<LogicalPlan>,
198        right: Box<LogicalPlan>,
199        condition: Option<Expr>,
200        /// True for EXISTS, false for NOT EXISTS / NOT IN
201        positive: bool,
202    },
203
204    /// Anti-join - returns rows from left where NO matching row exists in right
205    /// Used for NOT IN / NOT EXISTS optimization
206    AntiJoin {
207        left: Box<LogicalPlan>,
208        right: Box<LogicalPlan>,
209        condition: Option<Expr>,
210    },
211
212    /// Grant permissions on a table to an API key (v0.4.0)
213    Grant {
214        /// Permissions to grant (SELECT, INSERT, UPDATE, DELETE, ALL)
215        privileges: Permissions,
216        /// Table name, or None for wildcard (all tables)
217        table: Option<String>,
218        /// The API key ID to grant permissions to
219        grantee: String,
220    },
221
222    /// Revoke permissions from an API key (v0.4.0)
223    Revoke {
224        /// Permissions to revoke (SELECT, INSERT, UPDATE, DELETE, ALL)
225        privileges: Permissions,
226        /// Table name, or None for wildcard (all tables)
227        table: Option<String>,
228        /// The API key ID to revoke permissions from
229        grantee: String,
230    },
231
232    /// Show grants for a table or API key (v0.4.0)
233    ShowGrants {
234        /// Target of SHOW GRANTS query
235        target: ShowGrantsTarget,
236    },
237
238    /// UNION / UNION ALL - combines results of two queries
239    Union {
240        left: Box<LogicalPlan>,
241        right: Box<LogicalPlan>,
242        /// If true, keep duplicates (UNION ALL). If false, deduplicate (UNION).
243        all: bool,
244    },
245
246    /// INTERSECT / INTERSECT ALL - returns rows common to both queries
247    Intersect {
248        left: Box<LogicalPlan>,
249        right: Box<LogicalPlan>,
250        /// If true, keep duplicates (INTERSECT ALL). If false, deduplicate.
251        all: bool,
252    },
253
254    /// EXCEPT / EXCEPT ALL - returns rows in left but not in right
255    Except {
256        left: Box<LogicalPlan>,
257        right: Box<LogicalPlan>,
258        /// If true, keep duplicates (EXCEPT ALL). If false, deduplicate.
259        all: bool,
260    },
261
262    /// CREATE VIEW - stores a named query definition
263    CreateView {
264        name: String,
265        query: Box<LogicalPlan>,
266        /// The original SQL of the view query (for re-planning on scan)
267        query_sql: String,
268        /// Column aliases for the view
269        columns: Vec<String>,
270    },
271
272    /// DROP VIEW
273    DropView { name: String, if_exists: bool },
274
275    /// CREATE INDEX
276    CreateIndex {
277        index_name: String,
278        table_name: String,
279        columns: Vec<String>,
280        unique: bool,
281    },
282}
283
284/// Target for SHOW GRANTS query
285#[derive(Debug, Clone)]
286pub enum ShowGrantsTarget {
287    /// SHOW GRANTS ON <table>
288    Table(String),
289    /// SHOW GRANTS FOR '<api_key_id>'
290    ApiKey(String),
291}
292
293impl LogicalPlan {
294    /// Get output column names
295    pub fn output_columns(&self) -> Vec<String> {
296        match self {
297            LogicalPlan::Scan { table, alias, .. } => {
298                let prefix = alias.as_ref().unwrap_or(&table.name);
299                table
300                    .columns
301                    .iter()
302                    .map(|c| format!("{}.{}", prefix, c.name))
303                    .collect()
304            }
305            LogicalPlan::IndexScan { table, alias, .. } => {
306                let prefix = alias.as_ref().unwrap_or(&table.name);
307                table
308                    .columns
309                    .iter()
310                    .map(|c| format!("{}.{}", prefix, c.name))
311                    .collect()
312            }
313            LogicalPlan::PkSeek { table, alias, .. } => {
314                let prefix = alias.as_ref().unwrap_or(&table.name);
315                table
316                    .columns
317                    .iter()
318                    .map(|c| format!("{}.{}", prefix, c.name))
319                    .collect()
320            }
321            LogicalPlan::PkRangeScan { table, alias, .. } => {
322                let prefix = alias.as_ref().unwrap_or(&table.name);
323                table
324                    .columns
325                    .iter()
326                    .map(|c| format!("{}.{}", prefix, c.name))
327                    .collect()
328            }
329            LogicalPlan::Project { exprs, .. } => {
330                exprs.iter().map(|(_, name)| name.clone()).collect()
331            }
332            LogicalPlan::Filter { input, .. } => input.output_columns(),
333            LogicalPlan::Join { left, right, .. } => {
334                let mut cols = left.output_columns();
335                cols.extend(right.output_columns());
336                cols
337            }
338            LogicalPlan::Aggregate {
339                group_by,
340                aggregates,
341                ..
342            } => {
343                let mut cols: Vec<String> = group_by
344                    .iter()
345                    .enumerate()
346                    .map(|(i, _)| format!("group_{}", i))
347                    .collect();
348                cols.extend(aggregates.iter().map(|(_, name)| name.clone()));
349                cols
350            }
351            LogicalPlan::Sort { input, .. } => input.output_columns(),
352            LogicalPlan::Limit { input, .. } => input.output_columns(),
353            LogicalPlan::Distinct { input } => input.output_columns(),
354            LogicalPlan::Window {
355                input,
356                window_exprs,
357            } => {
358                // Window adds columns to the input
359                let mut cols = input.output_columns();
360                cols.extend(window_exprs.iter().map(|(_, name)| name.clone()));
361                cols
362            }
363            LogicalPlan::WithCte { query, .. } => query.output_columns(),
364            LogicalPlan::CteScan {
365                cte_name,
366                alias,
367                columns,
368            } => {
369                let prefix = alias.as_ref().unwrap_or(cte_name);
370                columns
371                    .iter()
372                    .map(|c| {
373                        // Strip any existing prefix and re-prefix
374                        let bare = c.split('.').next_back().unwrap_or(c);
375                        format!("{}.{}", prefix, bare)
376                    })
377                    .collect()
378            }
379            LogicalPlan::SubqueryScan {
380                subquery, alias, ..
381            } => {
382                let cols = subquery.output_columns();
383                if let Some(a) = alias {
384                    cols.iter()
385                        .map(|c| {
386                            if let Some(name) = c.split('.').next_back() {
387                                format!("{}.{}", a, name)
388                            } else {
389                                format!("{}.{}", a, c)
390                            }
391                        })
392                        .collect()
393                } else {
394                    cols
395                }
396            }
397            LogicalPlan::SemiJoin { left, .. } => left.output_columns(),
398            LogicalPlan::AntiJoin { left, .. } => left.output_columns(),
399            LogicalPlan::Union { left, .. } => left.output_columns(),
400            LogicalPlan::Intersect { left, .. } => left.output_columns(),
401            LogicalPlan::Except { left, .. } => left.output_columns(),
402            LogicalPlan::CreateView { columns, .. } if !columns.is_empty() => columns.clone(),
403            _ => vec![],
404        }
405    }
406
407    /// Collect all column references from expressions in the plan
408    /// Returns tuples of (table, column_name)
409    pub fn collect_column_references(&self) -> Vec<(Option<String>, String)> {
410        let mut refs = Vec::new();
411        self.collect_column_references_recursive(&mut refs);
412        refs
413    }
414
415    fn collect_column_references_recursive(&self, refs: &mut Vec<(Option<String>, String)>) {
416        match self {
417            LogicalPlan::Scan { filter, .. } | LogicalPlan::Delete { filter, .. } => {
418                if let Some(f) = filter {
419                    refs.extend(f.collect_column_references());
420                }
421            }
422            LogicalPlan::IndexScan {
423                residual_filter: Some(f),
424                ..
425            } => {
426                refs.extend(f.collect_column_references());
427            }
428            LogicalPlan::IndexScan {
429                residual_filter: None,
430                ..
431            } => {}
432            LogicalPlan::PkSeek {
433                key_values,
434                residual_filter,
435                ..
436            } => {
437                for expr in key_values {
438                    refs.extend(expr.collect_column_references());
439                }
440                if let Some(f) = residual_filter {
441                    refs.extend(f.collect_column_references());
442                }
443            }
444            LogicalPlan::PkRangeScan {
445                residual_filter: Some(f),
446                ..
447            } => {
448                refs.extend(f.collect_column_references());
449            }
450            LogicalPlan::PkRangeScan {
451                residual_filter: None,
452                ..
453            } => {}
454            LogicalPlan::Filter { input, predicate } => {
455                refs.extend(predicate.collect_column_references());
456                input.collect_column_references_recursive(refs);
457            }
458            LogicalPlan::Project { input, exprs } => {
459                for (expr, _) in exprs {
460                    refs.extend(expr.collect_column_references());
461                }
462                input.collect_column_references_recursive(refs);
463            }
464            LogicalPlan::Join {
465                left,
466                right,
467                condition,
468                ..
469            } => {
470                if let Some(c) = condition {
471                    refs.extend(c.collect_column_references());
472                }
473                left.collect_column_references_recursive(refs);
474                right.collect_column_references_recursive(refs);
475            }
476            LogicalPlan::Aggregate {
477                input,
478                group_by,
479                aggregates,
480            } => {
481                for expr in group_by {
482                    refs.extend(expr.collect_column_references());
483                }
484                for (expr, _) in aggregates {
485                    refs.extend(expr.collect_column_references());
486                }
487                input.collect_column_references_recursive(refs);
488            }
489            LogicalPlan::Sort { input, order_by } => {
490                for (expr, _) in order_by {
491                    refs.extend(expr.collect_column_references());
492                }
493                input.collect_column_references_recursive(refs);
494            }
495            LogicalPlan::Limit { input, .. }
496            | LogicalPlan::Distinct { input }
497            | LogicalPlan::Explain { input, .. }
498            | LogicalPlan::SubqueryScan {
499                subquery: input, ..
500            } => {
501                input.collect_column_references_recursive(refs);
502            }
503            LogicalPlan::Update {
504                filter,
505                assignments,
506                ..
507            } => {
508                if let Some(f) = filter {
509                    refs.extend(f.collect_column_references());
510                }
511                for (_, expr) in assignments {
512                    refs.extend(expr.collect_column_references());
513                }
514            }
515            LogicalPlan::Insert { values, .. } => {
516                for row in values {
517                    for expr in row {
518                        refs.extend(expr.collect_column_references());
519                    }
520                }
521            }
522            LogicalPlan::Window {
523                input,
524                window_exprs,
525            } => {
526                for (expr, _) in window_exprs {
527                    refs.extend(expr.collect_column_references());
528                }
529                input.collect_column_references_recursive(refs);
530            }
531            LogicalPlan::WithCte { ctes, query } => {
532                for cte in ctes {
533                    cte.query.collect_column_references_recursive(refs);
534                }
535                query.collect_column_references_recursive(refs);
536            }
537            LogicalPlan::SemiJoin {
538                left,
539                right,
540                condition,
541                ..
542            }
543            | LogicalPlan::AntiJoin {
544                left,
545                right,
546                condition,
547            } => {
548                if let Some(c) = condition {
549                    refs.extend(c.collect_column_references());
550                }
551                left.collect_column_references_recursive(refs);
552                right.collect_column_references_recursive(refs);
553            }
554            LogicalPlan::Union { left, right, .. }
555            | LogicalPlan::Intersect { left, right, .. }
556            | LogicalPlan::Except { left, right, .. } => {
557                left.collect_column_references_recursive(refs);
558                right.collect_column_references_recursive(refs);
559            }
560            _ => {}
561        }
562    }
563}
featherdb_query/planner/plan.rs

featherdb_query/planner/
plan.rs
