This documentation is part of the "Projects with Books" initiative at zenOSmosis.

The source code for this project is available on GitHub.

Plan Structures

Relevant source files

Purpose and Scope

Plan structures are strongly-typed representations of SQL statements that bridge the SQL parsing layer and the execution layer. Defined in the llkv-plan crate, these structures capture the logical intent of SQL operations without retaining parser-specific AST details. The planner translates sqlparser ASTs into plan instances, which the runtime then dispatches to execution engines.

This page documents the structure and organization of plan types. For information about how correlated subqueries and scalar subqueries are represented and tracked, see Subquery and Correlation Handling.

Sources: llkv-plan/src/plans.rs:1-10 llkv-plan/README.md:10-16

Plan Type Hierarchy

LLKV organizes plan structures into three primary categories based on their SQL statement class:

Diagram: Plan Type Organization

graph TB
    Plans["Plan Structures\n(llkv-plan)"]
DDL["DDL Plans\nSchema Operations"]
DML["DML Plans\nData Modifications"]
Query["Query Plans\nData Retrieval"]
Plans --> DDL
 
   Plans --> DML
 
   Plans --> Query
    
 
   DDL --> CreateTablePlan
 
   DDL --> DropTablePlan
 
   DDL --> CreateViewPlan
 
   DDL --> DropViewPlan
 
   DDL --> CreateIndexPlan
 
   DDL --> DropIndexPlan
 
   DDL --> ReindexPlan
 
   DDL --> AlterTablePlan
 
   DDL --> RenameTablePlan
    
 
   DML --> InsertPlan
 
   DML --> UpdatePlan
 
   DML --> DeletePlan
 
   DML --> TruncatePlan
    
 
   Query --> SelectPlan
 
   Query --> CompoundSelectPlan
    
 
   SelectPlan --> TableRef
 
   SelectPlan --> JoinMetadata
 
   SelectPlan --> SelectProjection
 
   SelectPlan --> SelectFilter
 
   SelectPlan --> AggregateExpr
 
   SelectPlan --> OrderByPlan

Plans are consumed by llkv-runtime for execution orchestration and by llkv-executor for query evaluation. Each plan type encodes the necessary metadata for its corresponding operation without requiring re-parsing or runtime AST traversal.

Sources: llkv-plan/src/plans.rs:163-358 llkv-plan/src/plans.rs:620-703 llkv-plan/src/plans.rs:794-1023

SelectPlan Structure

SelectPlan represents SELECT queries and is the most complex plan type. It aggregates multiple sub-components to describe table references, join relationships, projections, filters, aggregates, and ordering.

Diagram: SelectPlan Component Structure

graph TB
    SelectPlan["SelectPlan\nllkv-plan/src/plans.rs:801"]
subgraph "Table Sources"
        Tables["tables: Vec&lt;TableRef&gt;"]
TableRef["TableRef\nschema, table, alias"]
end
    
    subgraph "Join Specification"
        Joins["joins: Vec&lt;JoinMetadata&gt;"]
JoinMetadata["JoinMetadata\nleft_table_index\njoin_type\non_condition"]
JoinPlan["JoinPlan\nInner/Left/Right/Full"]
end
    
    subgraph "Projections"
        Projections["projections:\nVec&lt;SelectProjection&gt;"]
AllColumns["AllColumns"]
AllColumnsExcept["AllColumnsExcept"]
Column["Column\nname, alias"]
Computed["Computed\nexpr, alias"]
end
    
    subgraph "Filtering"
        Filter["filter: Option&lt;SelectFilter&gt;"]
SelectFilter["SelectFilter\npredicate\nsubqueries"]
FilterSubquery["FilterSubquery\nid, plan,\ncorrelated_columns"]
end
    
    subgraph "Aggregation"
        Aggregates["aggregates:\nVec&lt;AggregateExpr&gt;"]
GroupBy["group_by: Vec&lt;String&gt;"]
Having["having:\nOption&lt;Expr&gt;"]
end
    
    subgraph "Ordering & Modifiers"
        OrderBy["order_by:\nVec&lt;OrderByPlan&gt;"]
Distinct["distinct: bool"]
end
    
    subgraph "Compound Operations"
        Compound["compound:\nOption&lt;CompoundSelectPlan&gt;"]
CompoundOps["Union/Intersect/Except\nDistinct/All"]
end
    
 
   SelectPlan --> Tables
 
   SelectPlan --> Joins
 
   SelectPlan --> Projections
 
   SelectPlan --> Filter
 
   SelectPlan --> Aggregates
 
   SelectPlan --> OrderBy
 
   SelectPlan --> Compound
    
 
   Tables --> TableRef
 
   Joins --> JoinMetadata
 
   JoinMetadata --> JoinPlan
 
   Projections --> AllColumns
 
   Projections --> AllColumnsExcept
 
   Projections --> Column
 
   Projections --> Computed
 
   Filter --> SelectFilter
 
   SelectFilter --> FilterSubquery
 
   Aggregates --> GroupBy
 
   Aggregates --> Having
 
   Compound --> CompoundOps

Sources: llkv-plan/src/plans.rs:794-944

TableRef - Table References

TableRef represents a table source in the FROM clause, with optional aliasing:

Field	Type	Description
`schema`	`String`	Schema/namespace identifier (empty for default)
`table`	`String`	Table name
`alias`	`Option<String>`	Optional alias for qualified name resolution

The display_name() method returns the alias if present, otherwise the qualified name. This enables consistent column name resolution during expression translation.

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

JoinMetadata - Join Specification

JoinMetadata describes how adjacent tables in the tables vector are connected. Each entry links tables[left_table_index] with tables[left_table_index + 1]:

Field	Type	Description
`left_table_index`	`usize`	Index into `SelectPlan.tables`
`join_type`	`JoinPlan`	Inner, Left, Right, or Full
`on_condition`	`Option<Expr<String>>`	Optional ON clause predicate

The JoinPlan enum mirrors llkv_join::JoinType but exists in the plan layer to avoid circular dependencies.

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

SelectProjection - Projection Variants

SelectProjection specifies which columns appear in the result set:

Variant	Fields	Description
`AllColumns`	-	SELECT * (all columns from all tables)
`AllColumnsExcept`	`exclude: Vec<String>`	SELECT * EXCEPT (col1, col2, ...)
`Column`	`name: String`
`alias: Option<String>`	Named column with optional alias
`Computed`	`expr: ScalarExpr<String>`
`alias: String`	Computed expression (e.g., col1 + col2 AS sum)

The executor translates these into ScanProjection instances that specify which columns to fetch from storage.

Sources: llkv-plan/src/plans.rs:998-1013

AggregateExpr - Aggregate Functions

AggregateExpr describes aggregate function calls in SELECT or HAVING clauses:

Diagram: AggregateExpr Variants

graph LR
    AggregateExpr["AggregateExpr"]
CountStar["CountStar\nalias, distinct"]
Column["Column\ncolumn, alias,\nfunction, distinct"]
Functions["AggregateFunction"]
Count["Count"]
SumInt64["SumInt64"]
TotalInt64["TotalInt64"]
MinInt64["MinInt64"]
MaxInt64["MaxInt64"]
CountNulls["CountNulls"]
GroupConcat["GroupConcat"]
AggregateExpr --> CountStar
 
   AggregateExpr --> Column
 
   Column --> Functions
 
   Functions --> Count
 
   Functions --> SumInt64
 
   Functions --> TotalInt64
 
   Functions --> MinInt64
 
   Functions --> MaxInt64
 
   Functions --> CountNulls
 
   Functions --> GroupConcat

The executor delegates to llkv-aggregate for accumulator-based evaluation.

Sources: llkv-plan/src/plans.rs:1028-1120

OrderByPlan - Sort Specification

OrderByPlan defines ORDER BY clause semantics:

Field	Type	Description
`target`	`OrderTarget`	Column name, projection index, or All
`sort_type`	`OrderSortType`	Native or CastTextToInteger
`ascending`	`bool`	Sort direction (ASC/DESC)
`nulls_first`	`bool`	NULL placement (NULLS FIRST/LAST)

OrderTarget variants:

Column(String) - Sort by named column
Index(usize) - Sort by projection position (1-based in SQL)
All - Specialized SQLite behavior for sorting all columns

Sources: llkv-plan/src/plans.rs:1195-1217

CompoundSelectPlan - Set Operations

CompoundSelectPlan represents UNION, INTERSECT, and EXCEPT operations:

Field	Type	Description
`initial`	`Box<SelectPlan>`	First SELECT in the compound
`operations`	`Vec<CompoundSelectComponent>`	Subsequent set operations

Each CompoundSelectComponent contains:

operator: CompoundOperator (Union, Intersect, Except)
quantifier: CompoundQuantifier (Distinct, All)
plan: SelectPlan for the right-hand side

The executor processes these sequentially, maintaining distinct caches for DISTINCT quantifiers.

Sources: llkv-plan/src/plans.rs:946-996

InsertPlan Structure

InsertPlan encapsulates data insertion operations with conflict resolution strategies:

Field	Type	Description
`table`	`String`	Target table name
`columns`	`Vec<String>`	Column names (empty means all columns)
`source`	`InsertSource`	Data source (rows, batches, or SELECT)
`on_conflict`	`InsertConflictAction`	Conflict resolution strategy

InsertSource Variants

Variant	Description
`Rows(Vec<Vec<PlanValue>>)`	Explicit value rows from INSERT VALUES
`Batches(Vec<RecordBatch>)`	Pre-materialized Arrow batches
`Select { plan: Box<SelectPlan> }`	INSERT INTO ... SELECT ...

InsertConflictAction Variants

SQLite-compatible conflict resolution actions:

Variant	Behavior
`None`	Standard behavior - fail on constraint violation
`Replace`	UPDATE existing row on conflict (INSERT OR REPLACE)
`Ignore`	Skip conflicting rows (INSERT OR IGNORE)
`Abort`	Abort transaction on conflict
`Fail`	Fail statement without rollback
`Rollback`	Rollback entire transaction

Sources: llkv-plan/src/plans.rs:620-655

UpdatePlan and DeletePlan

UpdatePlan

UpdatePlan specifies row updates with optional filtering:

Field	Type	Description
`table`	`String`	Target table name
`assignments`	`Vec<ColumnAssignment>`	Column updates
`filter`	`Option<Expr<String>>`	WHERE clause predicate

Each ColumnAssignment contains:

column: Target column name
value: AssignmentValue (literal or expression)

AssignmentValue variants:

Literal(PlanValue) - Static value (e.g., SET col = 42)
Expression(ScalarExpr<String>) - Computed value (e.g., SET col = col + 1)

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

DeletePlan

DeletePlan specifies row deletions:

Field	Type	Description
`table`	`String`	Target table name
`filter`	`Option<Expr<String>>`	WHERE clause predicate

A missing filter indicates DELETE FROM table (deletes all rows).

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

TruncatePlan

TruncatePlan represents TRUNCATE TABLE (removes all rows, resets sequences):

Field	Type	Description
`table`	`String`	Target table name

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

DDL Plan Structures

CreateTablePlan

CreateTablePlan defines table creation with schema, constraints, and data sources:

Field	Type	Description
`name`	`String`	Table name
`if_not_exists`	`bool`	Skip if table exists
`or_replace`	`bool`	Replace existing table
`columns`	`Vec<PlanColumnSpec>`	Column definitions
`source`	`Option<CreateTableSource>`	Optional CREATE TABLE AS data
`namespace`	`Option<String>`	Storage namespace (e.g., "temp")
`foreign_keys`	`Vec<ForeignKeySpec>`	Foreign key constraints
`multi_column_uniques`	`Vec<MultiColumnUniqueSpec>`	Multi-column UNIQUE constraints

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

PlanColumnSpec

PlanColumnSpec describes individual column metadata:

Field	Type	Description
`name`	`String`	Column name
`data_type`	`DataType`	Arrow data type
`nullable`	`bool`	NULL allowed
`primary_key`	`bool`	PRIMARY KEY constraint
`unique`	`bool`	UNIQUE constraint
`check_expr`	`Option<String>`	CHECK constraint SQL expression

The IntoPlanColumnSpec trait enables ergonomic column specification using tuples like ("col_name", DataType::Int64, NotNull).

Sources: llkv-plan/src/plans.rs:499-605

CreateIndexPlan

CreateIndexPlan specifies index creation:

Field	Type	Description
`name`	`Option<String>`	Index name (auto-generated if None)
`table`	`String`	Target table
`unique`	`bool`	UNIQUE index constraint
`if_not_exists`	`bool`	Skip if index exists
`columns`	`Vec<IndexColumnPlan>`	Indexed columns with sort order

Each IndexColumnPlan specifies:

name: Column name
ascending: Sort direction (ASC/DESC)
nulls_first: NULL placement

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

AlterTablePlan

AlterTablePlan represents ALTER TABLE operations:

Field	Type	Description
`table_name`	`String`	Target table
`if_exists`	`bool`	Skip if table missing
`operation`	`AlterTableOperation`	Specific operation

AlterTableOperation variants:

Variant	Fields	Description
`RenameColumn`	`old_column_name: String`
`new_column_name: String`	RENAME COLUMN
`SetColumnDataType`	`column_name: String`
`new_data_type: String`	ALTER COLUMN SET DATA TYPE
`DropColumn`	`column_name: String`
`if_exists: bool`
`cascade: bool`	DROP COLUMN

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

Additional DDL Plans

Plan Type	Purpose	Key Fields
`DropTablePlan`	DROP TABLE	`name`, `if_exists`
`CreateViewPlan`	CREATE VIEW	`name`, `view_definition`, `select_plan`
`DropViewPlan`	DROP VIEW	`name`, `if_exists`
`RenameTablePlan`	RENAME TABLE	`current_name`, `new_name`, `if_exists`
`DropIndexPlan`	DROP INDEX	`name`, `canonical_name`, `if_exists`
`ReindexPlan`	REINDEX	`name`, `canonical_name`

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

PlanValue - Value Representation

PlanValue provides a type-safe representation of literal values in plans, bridging SQL literals and Arrow arrays:

Variant	Description
`Null`	SQL NULL
`Integer(i64)`	Integer value (booleans stored as 0/1)
`Float(f64)`	Floating-point value
`Decimal(DecimalValue)`	Fixed-precision decimal
`String(String)`	Text value
`Date32(i32)`	Date (days since epoch)
`Struct(FxHashMap<String, PlanValue>)`	Nested struct value
`Interval(IntervalValue)`	Interval (months, days, nanos)

PlanValue implements From<T> for common types (i64, f64, String, bool) for ergonomic plan construction. The plan_value_from_literal() function converts llkv_expr::Literal to PlanValue, and plan_value_from_array() extracts values from Arrow arrays during INSERT SELECT operations.

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

Plan Translation Flow

Diagram: Plan Translation and Execution Flow

Plans serve as the interface contract between the SQL layer (llkv-sql) and the execution layer (llkv-runtime, llkv-executor). The translation layer in llkv-sql converts sqlparser AST nodes into strongly-typed plan structures, which the runtime validates and dispatches to appropriate executors.

Sources: llkv-plan/README.md:13-33 llkv-executor/README.md:12-31

Plan Construction Patterns

Builder Pattern for SelectPlan

SelectPlan uses fluent builder methods for incremental construction:

Sources: llkv-plan/src/plans.rs:827-943

Tuple-Based Column Specs

PlanColumnSpec implements IntoPlanColumnSpec for tuples, enabling concise table definitions:

Sources: llkv-plan/src/plans.rs:548-605

Integration with Expression System

Plans reference expressions from llkv-expr using parameterized types:

Expr<String>: Boolean predicates with column names (WHERE, HAVING, ON clauses)
ScalarExpr<String>: Scalar expressions with column names (projections, assignments)

The executor translates these to Expr<FieldId> and ScalarExpr<FieldId> after resolving column names against table schemas. For details on expression evaluation, see Expression AST and Expression Translation.

Sources: llkv-plan/src/plans.rs:28-34 llkv-plan/src/plans.rs:666-674

Keyboard shortcuts

rust-llkv Documentation