alopex_sql/planner/
logical_plan.rs

1//! Logical plan representation for query execution.
2//!
3//! This module defines [`LogicalPlan`], which represents the logical structure
4//! of a query after parsing and semantic analysis. The logical plan is used
5//! by the executor to produce query results.
6//!
7//! # Plan Structure
8//!
9//! Logical plans form a tree structure where:
10//! - Leaf nodes are typically scans or DDL operations
11//! - Internal nodes represent transformations (filter, sort, limit)
12//! - DML operations (insert, update, delete) are also represented
13//!
14//! # Examples
15//!
16//! ```
17//! use alopex_sql::planner::logical_plan::LogicalPlan;
18//! use alopex_sql::planner::{Projection, TypedExpr, TypedExprKind, SortExpr};
19//! use alopex_sql::planner::types::ResolvedType;
20//! use alopex_sql::Span;
21//!
22//! // SELECT * FROM users ORDER BY name LIMIT 10
23//! let scan = LogicalPlan::Scan {
24//!     table: "users".to_string(),
25//!     projection: Projection::All(vec!["id".to_string(), "name".to_string()]),
26//! };
27//!
28//! let sort = LogicalPlan::Sort {
29//!     input: Box::new(scan),
30//!     order_by: vec![SortExpr::asc(TypedExpr::column_ref(
31//!         "users".to_string(),
32//!         "name".to_string(),
33//!         1,
34//!         ResolvedType::Text,
35//!         Span::default(),
36//!     ))],
37//! };
38//!
39//! let limit = LogicalPlan::Limit {
40//!     input: Box::new(sort),
41//!     limit: Some(10),
42//!     offset: None,
43//! };
44//! ```
45
46use crate::catalog::{IndexMetadata, TableMetadata};
47use crate::planner::aggregate_expr::AggregateExpr;
48use crate::planner::typed_expr::{Projection, SortExpr, TypedAssignment, TypedExpr};
49
50/// Logical query plan representation.
51///
52/// This enum represents all possible logical operations that can be performed.
53/// Plans are organized into three categories:
54///
55/// 1. **Query Plans**: Read operations (Scan, Filter, Sort, Limit)
56/// 2. **DML Plans**: Data modification (Insert, Update, Delete)
57/// 3. **DDL Plans**: Schema modification (CreateTable, DropTable, CreateIndex, DropIndex)
58#[derive(Debug, Clone)]
59pub enum LogicalPlan {
60    // === Query Plans ===
61    /// Table scan operation.
62    ///
63    /// Scans all rows from a table with the specified projection.
64    /// This is typically the leaf node of query plans.
65    Scan {
66        /// Table name to scan.
67        table: String,
68        /// Columns to project (after wildcard expansion).
69        projection: Projection,
70    },
71
72    /// Filter operation (WHERE clause).
73    ///
74    /// Filters rows from the input plan based on a predicate.
75    Filter {
76        /// Input plan to filter.
77        input: Box<LogicalPlan>,
78        /// Filter predicate (must evaluate to Boolean).
79        predicate: TypedExpr,
80    },
81
82    /// Aggregate operation (GROUP BY / aggregation).
83    ///
84    /// Aggregates rows from the input plan using group keys and aggregate expressions.
85    Aggregate {
86        /// Input plan to aggregate.
87        input: Box<LogicalPlan>,
88        /// Group-by key expressions (empty for global aggregation).
89        group_keys: Vec<TypedExpr>,
90        /// Aggregate expressions to compute.
91        aggregates: Vec<AggregateExpr>,
92        /// HAVING filter applied after aggregation.
93        having: Option<TypedExpr>,
94    },
95
96    /// Sort operation (ORDER BY clause).
97    ///
98    /// Sorts rows from the input plan based on sort expressions.
99    Sort {
100        /// Input plan to sort.
101        input: Box<LogicalPlan>,
102        /// Sort expressions with direction.
103        order_by: Vec<SortExpr>,
104    },
105
106    /// Limit operation (LIMIT/OFFSET clause).
107    ///
108    /// Limits the number of rows from the input plan.
109    Limit {
110        /// Input plan to limit.
111        input: Box<LogicalPlan>,
112        /// Maximum number of rows to return.
113        limit: Option<u64>,
114        /// Number of rows to skip.
115        offset: Option<u64>,
116    },
117
118    // === DML Plans ===
119    /// INSERT operation.
120    ///
121    /// Inserts one or more rows into a table.
122    /// When columns are omitted in the SQL statement, the Planner fills in
123    /// all columns from TableMetadata in definition order.
124    Insert {
125        /// Target table name.
126        table: String,
127        /// Column names (always populated, never empty).
128        /// If omitted in SQL, filled from TableMetadata.column_names().
129        columns: Vec<String>,
130        /// Values to insert (one Vec per row, each value corresponds to a column).
131        values: Vec<Vec<TypedExpr>>,
132    },
133
134    /// UPDATE operation.
135    ///
136    /// Updates rows in a table that match an optional filter.
137    Update {
138        /// Target table name.
139        table: String,
140        /// Assignments (SET column = value).
141        assignments: Vec<TypedAssignment>,
142        /// Optional filter predicate (WHERE clause).
143        filter: Option<TypedExpr>,
144    },
145
146    /// DELETE operation.
147    ///
148    /// Deletes rows from a table that match an optional filter.
149    Delete {
150        /// Target table name.
151        table: String,
152        /// Optional filter predicate (WHERE clause).
153        filter: Option<TypedExpr>,
154    },
155
156    // === DDL Plans ===
157    /// CREATE TABLE operation.
158    ///
159    /// Creates a new table with the specified metadata.
160    CreateTable {
161        /// Table metadata (name, columns, constraints).
162        table: TableMetadata,
163        /// If true, don't error if table already exists.
164        if_not_exists: bool,
165        /// Raw WITH options to be validated during execution.
166        with_options: Vec<(String, String)>,
167    },
168
169    /// DROP TABLE operation.
170    ///
171    /// Drops an existing table.
172    DropTable {
173        /// Table name to drop.
174        name: String,
175        /// If true, don't error if table doesn't exist.
176        if_exists: bool,
177    },
178
179    /// CREATE INDEX operation.
180    ///
181    /// Creates a new index on a table column.
182    CreateIndex {
183        /// Index metadata (name, table, column, method, options).
184        index: IndexMetadata,
185        /// If true, don't error if index already exists.
186        if_not_exists: bool,
187    },
188
189    /// DROP INDEX operation.
190    ///
191    /// Drops an existing index.
192    DropIndex {
193        /// Index name to drop.
194        name: String,
195        /// If true, don't error if index doesn't exist.
196        if_exists: bool,
197    },
198}
199
200impl LogicalPlan {
201    pub fn operation_name(&self) -> &'static str {
202        match self {
203            LogicalPlan::Scan { .. }
204            | LogicalPlan::Filter { .. }
205            | LogicalPlan::Aggregate { .. }
206            | LogicalPlan::Sort { .. }
207            | LogicalPlan::Limit { .. } => "SELECT",
208            LogicalPlan::Insert { .. } => "INSERT",
209            LogicalPlan::Update { .. } => "UPDATE",
210            LogicalPlan::Delete { .. } => "DELETE",
211            LogicalPlan::CreateTable { .. } => "CREATE TABLE",
212            LogicalPlan::DropTable { .. } => "DROP TABLE",
213            LogicalPlan::CreateIndex { .. } => "CREATE INDEX",
214            LogicalPlan::DropIndex { .. } => "DROP INDEX",
215        }
216    }
217
218    /// Creates a new Scan plan.
219    pub fn scan(table: String, projection: Projection) -> Self {
220        LogicalPlan::Scan { table, projection }
221    }
222
223    /// Creates a new Filter plan.
224    pub fn filter(input: LogicalPlan, predicate: TypedExpr) -> Self {
225        LogicalPlan::Filter {
226            input: Box::new(input),
227            predicate,
228        }
229    }
230
231    /// Creates a new Aggregate plan.
232    pub fn aggregate(
233        input: LogicalPlan,
234        group_keys: Vec<TypedExpr>,
235        aggregates: Vec<AggregateExpr>,
236        having: Option<TypedExpr>,
237    ) -> Self {
238        LogicalPlan::Aggregate {
239            input: Box::new(input),
240            group_keys,
241            aggregates,
242            having,
243        }
244    }
245
246    /// Creates a new Sort plan.
247    pub fn sort(input: LogicalPlan, order_by: Vec<SortExpr>) -> Self {
248        LogicalPlan::Sort {
249            input: Box::new(input),
250            order_by,
251        }
252    }
253
254    /// Creates a new Limit plan.
255    pub fn limit(input: LogicalPlan, limit: Option<u64>, offset: Option<u64>) -> Self {
256        LogicalPlan::Limit {
257            input: Box::new(input),
258            limit,
259            offset,
260        }
261    }
262
263    /// Creates a new Insert plan.
264    pub fn insert(table: String, columns: Vec<String>, values: Vec<Vec<TypedExpr>>) -> Self {
265        LogicalPlan::Insert {
266            table,
267            columns,
268            values,
269        }
270    }
271
272    /// Creates a new Update plan.
273    pub fn update(
274        table: String,
275        assignments: Vec<TypedAssignment>,
276        filter: Option<TypedExpr>,
277    ) -> Self {
278        LogicalPlan::Update {
279            table,
280            assignments,
281            filter,
282        }
283    }
284
285    /// Creates a new Delete plan.
286    pub fn delete(table: String, filter: Option<TypedExpr>) -> Self {
287        LogicalPlan::Delete { table, filter }
288    }
289
290    /// Creates a new CreateTable plan.
291    pub fn create_table(
292        table: TableMetadata,
293        if_not_exists: bool,
294        with_options: Vec<(String, String)>,
295    ) -> Self {
296        LogicalPlan::CreateTable {
297            table,
298            if_not_exists,
299            with_options,
300        }
301    }
302
303    /// Creates a new DropTable plan.
304    pub fn drop_table(name: String, if_exists: bool) -> Self {
305        LogicalPlan::DropTable { name, if_exists }
306    }
307
308    /// Creates a new CreateIndex plan.
309    pub fn create_index(index: IndexMetadata, if_not_exists: bool) -> Self {
310        LogicalPlan::CreateIndex {
311            index,
312            if_not_exists,
313        }
314    }
315
316    /// Creates a new DropIndex plan.
317    pub fn drop_index(name: String, if_exists: bool) -> Self {
318        LogicalPlan::DropIndex { name, if_exists }
319    }
320
321    /// Returns the name of this plan variant.
322    pub fn name(&self) -> &'static str {
323        match self {
324            LogicalPlan::Scan { .. } => "Scan",
325            LogicalPlan::Filter { .. } => "Filter",
326            LogicalPlan::Aggregate { .. } => "Aggregate",
327            LogicalPlan::Sort { .. } => "Sort",
328            LogicalPlan::Limit { .. } => "Limit",
329            LogicalPlan::Insert { .. } => "Insert",
330            LogicalPlan::Update { .. } => "Update",
331            LogicalPlan::Delete { .. } => "Delete",
332            LogicalPlan::CreateTable { .. } => "CreateTable",
333            LogicalPlan::DropTable { .. } => "DropTable",
334            LogicalPlan::CreateIndex { .. } => "CreateIndex",
335            LogicalPlan::DropIndex { .. } => "DropIndex",
336        }
337    }
338
339    /// Returns true if this is a query plan (Scan, Filter, Sort, Limit).
340    pub fn is_query(&self) -> bool {
341        matches!(
342            self,
343            LogicalPlan::Scan { .. }
344                | LogicalPlan::Filter { .. }
345                | LogicalPlan::Aggregate { .. }
346                | LogicalPlan::Sort { .. }
347                | LogicalPlan::Limit { .. }
348        )
349    }
350
351    /// Returns true if this is a DML plan (Insert, Update, Delete).
352    pub fn is_dml(&self) -> bool {
353        matches!(
354            self,
355            LogicalPlan::Insert { .. } | LogicalPlan::Update { .. } | LogicalPlan::Delete { .. }
356        )
357    }
358
359    /// Returns true if this is a DDL plan (CreateTable, DropTable, CreateIndex, DropIndex).
360    pub fn is_ddl(&self) -> bool {
361        matches!(
362            self,
363            LogicalPlan::CreateTable { .. }
364                | LogicalPlan::DropTable { .. }
365                | LogicalPlan::CreateIndex { .. }
366                | LogicalPlan::DropIndex { .. }
367        )
368    }
369
370    /// Returns the input plan if this is a transformation (Filter, Aggregate, Sort, Limit).
371    pub fn input(&self) -> Option<&LogicalPlan> {
372        match self {
373            LogicalPlan::Filter { input, .. }
374            | LogicalPlan::Aggregate { input, .. }
375            | LogicalPlan::Sort { input, .. }
376            | LogicalPlan::Limit { input, .. } => Some(input),
377            _ => None,
378        }
379    }
380
381    /// Returns the table name if this plan operates on a single table.
382    pub fn table_name(&self) -> Option<&str> {
383        match self {
384            LogicalPlan::Scan { table, .. }
385            | LogicalPlan::Insert { table, .. }
386            | LogicalPlan::Update { table, .. }
387            | LogicalPlan::Delete { table, .. } => Some(table),
388            LogicalPlan::CreateTable { table, .. } => Some(&table.name),
389            LogicalPlan::DropTable { name, .. } => Some(name),
390            LogicalPlan::CreateIndex { index, .. } => Some(&index.table),
391            LogicalPlan::DropIndex { .. } => None,
392            LogicalPlan::Filter { input, .. }
393            | LogicalPlan::Aggregate { input, .. }
394            | LogicalPlan::Sort { input, .. }
395            | LogicalPlan::Limit { input, .. } => input.table_name(),
396        }
397    }
398}
399
400#[cfg(test)]
401mod tests {
402    use super::*;
403    use crate::ast::expr::Literal;
404    use crate::ast::span::Span;
405    use crate::catalog::ColumnMetadata;
406    use crate::planner::typed_expr::ProjectedColumn;
407    use crate::planner::types::ResolvedType;
408
409    fn create_test_table_metadata() -> TableMetadata {
410        TableMetadata::new(
411            "users",
412            vec![
413                ColumnMetadata::new("id", ResolvedType::Integer)
414                    .with_primary_key(true)
415                    .with_not_null(true),
416                ColumnMetadata::new("name", ResolvedType::Text).with_not_null(true),
417                ColumnMetadata::new("email", ResolvedType::Text),
418            ],
419        )
420        .with_primary_key(vec!["id".to_string()])
421    }
422
423    #[test]
424    fn test_scan_plan() {
425        let plan = LogicalPlan::scan(
426            "users".to_string(),
427            Projection::All(vec![
428                "id".to_string(),
429                "name".to_string(),
430                "email".to_string(),
431            ]),
432        );
433
434        assert_eq!(plan.name(), "Scan");
435        assert!(plan.is_query());
436        assert!(!plan.is_dml());
437        assert!(!plan.is_ddl());
438        assert_eq!(plan.table_name(), Some("users"));
439        assert!(plan.input().is_none());
440    }
441
442    #[test]
443    fn test_filter_plan() {
444        let scan = LogicalPlan::scan("users".to_string(), Projection::All(vec![]));
445        let predicate = TypedExpr::column_ref(
446            "users".to_string(),
447            "id".to_string(),
448            0,
449            ResolvedType::Integer,
450            Span::default(),
451        );
452
453        let plan = LogicalPlan::filter(scan, predicate);
454
455        assert_eq!(plan.name(), "Filter");
456        assert!(plan.is_query());
457        assert!(plan.input().is_some());
458        assert_eq!(plan.table_name(), Some("users"));
459    }
460
461    #[test]
462    fn test_sort_plan() {
463        let scan = LogicalPlan::scan("users".to_string(), Projection::All(vec![]));
464        let sort_expr = SortExpr::asc(TypedExpr::column_ref(
465            "users".to_string(),
466            "name".to_string(),
467            1,
468            ResolvedType::Text,
469            Span::default(),
470        ));
471
472        let plan = LogicalPlan::sort(scan, vec![sort_expr]);
473
474        assert_eq!(plan.name(), "Sort");
475        assert!(plan.is_query());
476    }
477
478    #[test]
479    fn test_limit_plan() {
480        let scan = LogicalPlan::scan("users".to_string(), Projection::All(vec![]));
481        let plan = LogicalPlan::limit(scan, Some(10), Some(5));
482
483        assert_eq!(plan.name(), "Limit");
484        assert!(plan.is_query());
485
486        if let LogicalPlan::Limit { limit, offset, .. } = &plan {
487            assert_eq!(*limit, Some(10));
488            assert_eq!(*offset, Some(5));
489        } else {
490            panic!("Expected Limit plan");
491        }
492    }
493
494    #[test]
495    fn test_nested_query_plan() {
496        // SELECT * FROM users WHERE id > 5 ORDER BY name LIMIT 10
497        let scan = LogicalPlan::scan(
498            "users".to_string(),
499            Projection::All(vec!["id".to_string(), "name".to_string()]),
500        );
501
502        let predicate = TypedExpr::literal(
503            Literal::Boolean(true),
504            ResolvedType::Boolean,
505            Span::default(),
506        );
507        let filter = LogicalPlan::filter(scan, predicate);
508
509        let sort_expr = SortExpr::asc(TypedExpr::column_ref(
510            "users".to_string(),
511            "name".to_string(),
512            1,
513            ResolvedType::Text,
514            Span::default(),
515        ));
516        let sort = LogicalPlan::sort(filter, vec![sort_expr]);
517
518        let limit = LogicalPlan::limit(sort, Some(10), None);
519
520        // Verify the plan tree
521        assert_eq!(limit.name(), "Limit");
522        assert_eq!(limit.table_name(), Some("users"));
523
524        let sort_plan = limit.input().unwrap();
525        assert_eq!(sort_plan.name(), "Sort");
526
527        let filter_plan = sort_plan.input().unwrap();
528        assert_eq!(filter_plan.name(), "Filter");
529
530        let scan_plan = filter_plan.input().unwrap();
531        assert_eq!(scan_plan.name(), "Scan");
532        assert!(scan_plan.input().is_none());
533    }
534
535    #[test]
536    fn test_insert_plan() {
537        let value1 = TypedExpr::literal(
538            Literal::Number("1".to_string()),
539            ResolvedType::Integer,
540            Span::default(),
541        );
542        let value2 = TypedExpr::literal(
543            Literal::String("Alice".to_string()),
544            ResolvedType::Text,
545            Span::default(),
546        );
547
548        let plan = LogicalPlan::insert(
549            "users".to_string(),
550            vec!["id".to_string(), "name".to_string()],
551            vec![vec![value1, value2]],
552        );
553
554        assert_eq!(plan.name(), "Insert");
555        assert!(plan.is_dml());
556        assert!(!plan.is_query());
557        assert!(!plan.is_ddl());
558        assert_eq!(plan.table_name(), Some("users"));
559
560        if let LogicalPlan::Insert {
561            table,
562            columns,
563            values,
564        } = &plan
565        {
566            assert_eq!(table, "users");
567            assert_eq!(columns, &vec!["id".to_string(), "name".to_string()]);
568            assert_eq!(values.len(), 1);
569            assert_eq!(values[0].len(), 2);
570        } else {
571            panic!("Expected Insert plan");
572        }
573    }
574
575    #[test]
576    fn test_update_plan() {
577        let assignment = TypedAssignment::new(
578            "name".to_string(),
579            1,
580            TypedExpr::literal(
581                Literal::String("Bob".to_string()),
582                ResolvedType::Text,
583                Span::default(),
584            ),
585        );
586
587        let filter = TypedExpr::literal(
588            Literal::Boolean(true),
589            ResolvedType::Boolean,
590            Span::default(),
591        );
592
593        let plan = LogicalPlan::update("users".to_string(), vec![assignment], Some(filter));
594
595        assert_eq!(plan.name(), "Update");
596        assert!(plan.is_dml());
597        assert_eq!(plan.table_name(), Some("users"));
598    }
599
600    #[test]
601    fn test_delete_plan() {
602        let filter = TypedExpr::column_ref(
603            "users".to_string(),
604            "id".to_string(),
605            0,
606            ResolvedType::Integer,
607            Span::default(),
608        );
609
610        let plan = LogicalPlan::delete("users".to_string(), Some(filter));
611
612        assert_eq!(plan.name(), "Delete");
613        assert!(plan.is_dml());
614        assert_eq!(plan.table_name(), Some("users"));
615    }
616
617    #[test]
618    fn test_create_table_plan() {
619        let table = create_test_table_metadata();
620        let plan = LogicalPlan::create_table(table, false, vec![]);
621
622        assert_eq!(plan.name(), "CreateTable");
623        assert!(plan.is_ddl());
624        assert!(!plan.is_dml());
625        assert!(!plan.is_query());
626        assert_eq!(plan.table_name(), Some("users"));
627    }
628
629    #[test]
630    fn test_drop_table_plan() {
631        let plan = LogicalPlan::drop_table("users".to_string(), true);
632
633        assert_eq!(plan.name(), "DropTable");
634        assert!(plan.is_ddl());
635        assert_eq!(plan.table_name(), Some("users"));
636
637        if let LogicalPlan::DropTable { name, if_exists } = &plan {
638            assert_eq!(name, "users");
639            assert!(*if_exists);
640        } else {
641            panic!("Expected DropTable plan");
642        }
643    }
644
645    #[test]
646    fn test_create_index_plan() {
647        let index = IndexMetadata::new(0, "idx_users_name", "users", vec!["name".into()]);
648        let plan = LogicalPlan::create_index(index, false);
649
650        assert_eq!(plan.name(), "CreateIndex");
651        assert!(plan.is_ddl());
652        assert_eq!(plan.table_name(), Some("users"));
653    }
654
655    #[test]
656    fn test_drop_index_plan() {
657        let plan = LogicalPlan::drop_index("idx_users_name".to_string(), false);
658
659        assert_eq!(plan.name(), "DropIndex");
660        assert!(plan.is_ddl());
661        // DropIndex doesn't have table_name directly
662        assert!(plan.table_name().is_none());
663    }
664
665    #[test]
666    fn test_projection_columns() {
667        let col1 = ProjectedColumn::new(TypedExpr::column_ref(
668            "users".to_string(),
669            "id".to_string(),
670            0,
671            ResolvedType::Integer,
672            Span::default(),
673        ));
674        let col2 = ProjectedColumn::with_alias(
675            TypedExpr::column_ref(
676                "users".to_string(),
677                "name".to_string(),
678                1,
679                ResolvedType::Text,
680                Span::default(),
681            ),
682            "user_name".to_string(),
683        );
684
685        let plan = LogicalPlan::scan("users".to_string(), Projection::Columns(vec![col1, col2]));
686
687        if let LogicalPlan::Scan { projection, .. } = &plan {
688            assert_eq!(projection.len(), 2);
689        } else {
690            panic!("Expected Scan plan");
691        }
692    }
693}
alopex_sql/planner/logical_plan.rs

alopex_sql/planner/
logical_plan.rs
