Plan Structures

Loading…

Plan Structures

Relevant source files

• llkv-expr/src/expr.rs
• llkv-plan/src/lib.rs
• llkv-plan/src/plans.rs
• llkv-table/src/resolvers/identifier.rs

This document describes the logical plan data structures defined in the llkv-plan crate. These structures represent parsed and validated SQL operations before execution. For information about how plans are created from SQL AST, see Subquery and Correlation Handling. For details on expression compilation and evaluation, see Expression System.

Purpose and Scope

Plan structures are the intermediate representation (IR) between SQL parsing and query execution. The SQL parser produces AST nodes from sqlparser-rs, which the planner translates into strongly-typed plan structures. The executor consumes these plans to produce results. Plans carry all semantic information needed for execution: table references, column specifications, predicates, projections, aggregations, and ordering constraints.

All plan types are defined in llkv-plan/src/plans.rs

Sources: llkv-plan/src/plans.rs:1-1263

Plan Statement Hierarchy

All executable statements are represented by the PlanStatement enum, which serves as the top-level discriminated union of all plan types.

Sources: llkv-plan/src/plans.rs:1244-1263

graph TB
    PlanStatement["PlanStatement\n(Top-level enum)"]
subgraph "Transaction Control"
        BeginTransaction["BeginTransaction"]
CommitTransaction["CommitTransaction"]
RollbackTransaction["RollbackTransaction"]
end
    
    subgraph "DDL Operations"
        CreateTable["CreateTablePlan"]
DropTable["DropTablePlan"]
CreateView["CreateViewPlan"]
DropView["DropViewPlan"]
CreateIndex["CreateIndexPlan"]
DropIndex["DropIndexPlan"]
Reindex["ReindexPlan"]
AlterTable["AlterTablePlan"]
end
    
    subgraph "DML Operations"
        Insert["InsertPlan"]
Update["UpdatePlan"]
Delete["DeletePlan"]
Truncate["TruncatePlan"]
end
    
    subgraph "Query Operations"
        Select["SelectPlan"]
end
    
 
   PlanStatement --> BeginTransaction
 
   PlanStatement --> CommitTransaction
 
   PlanStatement --> RollbackTransaction
    
 
   PlanStatement --> CreateTable
 
   PlanStatement --> DropTable
 
   PlanStatement --> CreateView
 
   PlanStatement --> DropView
 
   PlanStatement --> CreateIndex
 
   PlanStatement --> DropIndex
 
   PlanStatement --> Reindex
 
   PlanStatement --> AlterTable
    
 
   PlanStatement --> Insert
 
   PlanStatement --> Update
 
   PlanStatement --> Delete
 
   PlanStatement --> Truncate
    
 
   PlanStatement --> Select

DDL Plan Structures

DDL (Data Definition Language) plans modify database schema: creating, altering, and dropping tables, views, and indexes.

CreateTablePlan

The CreateTablePlan structure defines table creation operations, including optional data sources for CREATE TABLE AS SELECT.

Sources: llkv-plan/src/plans.rs:176-203

PlanColumnSpec

Column specifications carry metadata from the planner to the executor, including type, nullability, and constraints.

Sources: llkv-plan/src/plans.rs:503-546

CreateTableSource

The CreateTableSource enum specifies data sources for CREATE TABLE AS operations:

Sources: llkv-plan/src/plans.rs:607-617

AlterTablePlan

The AlterTablePlan structure defines table modification operations:

Sources: llkv-plan/src/plans.rs:364-406

Index Plans

Index management is handled by three plan types:

Sources: llkv-plan/src/plans.rs:433-358

DML Plan Structures

DML (Data Manipulation Language) plans modify table data: inserting, updating, and deleting rows.

graph TB
    InsertPlan["InsertPlan"]
InsertSource["InsertSource\n(enum)"]
Rows["Rows\nVec<Vec<PlanValue>>"]
Batches["Batches\nVec<RecordBatch>"]
SelectSource["Select\nBox<SelectPlan>"]
ConflictAction["InsertConflictAction"]
None["None"]
Replace["Replace"]
Ignore["Ignore"]
Abort["Abort"]
Fail["Fail"]
Rollback["Rollback"]
InsertPlan -->|source| InsertSource
 
   InsertPlan -->|on_conflict| ConflictAction
    
 
   InsertSource --> Rows
 
   InsertSource --> Batches
 
   InsertSource --> SelectSource
    
 
   ConflictAction --> None
 
   ConflictAction --> Replace
 
   ConflictAction --> Ignore
 
   ConflictAction --> Abort
 
   ConflictAction --> Fail
 
   ConflictAction --> Rollback

InsertPlan

The InsertPlan includes SQLite-style conflict resolution actions (INSERT OR REPLACE, INSERT OR IGNORE, etc.) to handle constraint violations.

Sources: llkv-plan/src/plans.rs:623-656

UpdatePlan

The UpdatePlan structure defines row update operations:

Each ColumnAssignment maps a column to an AssignmentValue:

Sources: llkv-plan/src/plans.rs:661-681

DeletePlan and TruncatePlan

Both plans remove rows from tables:

• DeletePlan: Removes rows matching an optional filter predicate
• TruncatePlan: Removes all rows (no filter)

Sources: llkv-plan/src/plans.rs:687-702

graph TB
    SelectPlan["SelectPlan"]
Tables["tables: Vec<TableRef>\nFROM clause tables"]
Joins["joins: Vec<JoinMetadata>\nJoin specifications"]
Projections["projections: Vec<SelectProjection>\nSELECT list"]
Filter["filter: Option<SelectFilter>\nWHERE clause"]
Having["having: Option<Expr>\nHAVING clause"]
GroupBy["group_by: Vec<String>\nGROUP BY columns"]
OrderBy["order_by: Vec<OrderByPlan>\nORDER BY specs"]
Aggregates["aggregates: Vec<AggregateExpr>\nAggregate functions"]
ScalarSubqueries["scalar_subqueries: Vec<ScalarSubquery>\nScalar subquery plans"]
Compound["compound: Option<CompoundSelectPlan>\nUNION/INTERSECT/EXCEPT"]
SelectPlan --> Tables
 
   SelectPlan --> Joins
 
   SelectPlan --> Projections
 
   SelectPlan --> Filter
 
   SelectPlan --> Having
 
   SelectPlan --> GroupBy
 
   SelectPlan --> OrderBy
 
   SelectPlan --> Aggregates
 
   SelectPlan --> ScalarSubqueries
 
   SelectPlan --> Compound

SelectPlan Structure

The SelectPlan is the most complex plan type, representing SELECT queries with projections, filters, joins, aggregates, ordering, and compound operations.

Core SelectPlan Fields

Sources: llkv-plan/src/plans.rs:800-864

TableRef and JoinMetadata

Table references include optional aliases and schema qualifications:

Join metadata connects consecutive tables in the tables vector:

Sources: llkv-plan/src/plans.rs:708-792

SelectProjection

The SelectProjection enum defines what columns appear in results:

Sources: llkv-plan/src/plans.rs:1007-1021

SelectFilter and Subqueries

The SelectFilter structure bundles predicates with correlated subqueries:

Scalar subqueries (used in projections) follow a similar structure:

Sources: llkv-plan/src/plans.rs:28-67

AggregateExpr

Aggregate expressions define computations over grouped data:

Sources: llkv-plan/src/plans.rs:1036-1128

OrderByPlan

Ordering specifications include target, direction, and null handling:

Sources: llkv-plan/src/plans.rs:1203-1225

graph TB
    ExprTypes["Expression Types"]
Expr["Expr<F>\nBoolean expressions"]
ScalarExpr["ScalarExpr<F>\nScalar computations"]
Filter["Filter<F>\nSingle-field predicates"]
Operator["Operator\nComparison operators"]
ExprVariants["Expr variants"]
And["And(Vec<Expr>)"]
Or["Or(Vec<Expr>)"]
Not["Not(Box<Expr>)"]
Pred["Pred(Filter)"]
Compare["Compare{left, op, right}"]
InList["InList{expr, list, negated}"]
IsNull["IsNull{expr, negated}"]
Literal["Literal(bool)"]
Exists["Exists(SubqueryExpr)"]
ScalarVariants["ScalarExpr variants"]
Column["Column(F)"]
Lit["Literal(Literal)"]
Binary["Binary{left, op, right}"]
Aggregate["Aggregate(AggregateCall)"]
Cast["Cast{expr, data_type}"]
Case["Case{operand, branches, else_expr}"]
Coalesce["Coalesce(Vec)"]
ScalarSubquery["ScalarSubquery(ScalarSubqueryExpr)"]
ExprTypes --> Expr
 
   ExprTypes --> ScalarExpr
 
   Expr --> Filter
 
   Filter --> Operator
    
 
   Expr --> ExprVariants
 
   ExprVariants --> And
 
   ExprVariants --> Or
 
   ExprVariants --> Not
 
   ExprVariants --> Pred
 
   ExprVariants --> Compare
 
   ExprVariants --> InList
 
   ExprVariants --> IsNull
 
   ExprVariants --> Literal
 
   ExprVariants --> Exists
    
 
   ScalarExpr --> ScalarVariants
 
   ScalarVariants --> Column
 
   ScalarVariants --> Lit
 
   ScalarVariants --> Binary
 
   ScalarVariants --> Aggregate
 
   ScalarVariants --> Cast
 
   ScalarVariants --> Case
 
   ScalarVariants --> Coalesce
 
   ScalarVariants --> ScalarSubquery

Expression Integration

Plans embed expression trees from llkv-expr for predicates, projections, and computed values.

Expression Type Hierarchy

Sources: llkv-expr/src/expr.rs:14-183

Expr - Boolean Predicates

The Expr type represents boolean-valued expressions used in WHERE, HAVING, and ON clauses. The generic parameter F allows different field identifier types (commonly String for column names):

Sources: llkv-expr/src/expr.rs:14-123

ScalarExpr - Scalar Computations

The ScalarExpr type represents scalar-valued expressions used in projections and assignments:

Sources: llkv-expr/src/expr.rs:125-307

Operator Types

The Operator enum defines comparison and pattern matching operations applied to single fields:

Sources: llkv-expr/src/expr.rs:372-428

graph LR
    PlanValue["PlanValue\n(enum)"]
Null["Null"]
Integer["Integer(i64)"]
Float["Float(f64)"]
Decimal["Decimal(DecimalValue)"]
String["String(String)"]
Date32["Date32(i32)"]
Struct["Struct(FxHashMap)"]
Interval["Interval(IntervalValue)"]
PlanValue --> Null
 
   PlanValue --> Integer
 
   PlanValue --> Float
 
   PlanValue --> Decimal
 
   PlanValue --> String
 
   PlanValue --> Date32
 
   PlanValue --> Struct
 
   PlanValue --> Interval

Supporting Types

PlanValue

The PlanValue enum represents runtime values in plans, providing a type-safe wrapper for literals and computed values:

PlanValue implements From<T> for common types, enabling ergonomic construction:

Sources: llkv-plan/src/plans.rs:73-161

Foreign Key Specifications

Foreign key constraints are defined by ForeignKeySpec:

Sources: llkv-plan/src/plans.rs:412-427

graph TB
    CompoundSelectPlan["CompoundSelectPlan"]
Initial["initial: Box<SelectPlan>\nFirst query"]
Operations["operations: Vec<CompoundSelectComponent>\nSubsequent operations"]
Component["CompoundSelectComponent"]
Operator["operator:\nUnion / Intersect / Except"]
Quantifier["quantifier:\nDistinct / All"]
Plan["plan: SelectPlan\nRight-hand query"]
CompoundSelectPlan --> Initial
 
   CompoundSelectPlan --> Operations
    
 
   Operations --> Component
 
   Component --> Operator
 
   Component --> Quantifier
 
   Component --> Plan

Compound Queries

Compound queries (UNION, INTERSECT, EXCEPT) are represented by CompoundSelectPlan:

This structure allows arbitrary chains of set operations:

• SELECT ... UNION ALL SELECT ... INTERSECT SELECT ...

Sources: llkv-plan/src/plans.rs:954-1004

Plan Construction Example

A typical SELECT plan construction follows this pattern:

This produces a plan for: SELECT id, age + 1 AS next_age FROM users WHERE age >= 18 ORDER BY id

Sources: llkv-plan/src/plans.rs:831-952

Dismiss

Refresh this wiki

Enter email to refresh