Overview

Relevant source files

• Cargo.lock
• Cargo.toml
• README.md
• demos/llkv-sql-pong-demo/src/main.rs
• llkv-aggregate/README.md
• llkv-column-map/README.md
• llkv-csv/README.md
• llkv-expr/README.md
• llkv-join/README.md
• llkv-runtime/README.md
• llkv-sql/src/tpch.rs
• llkv-storage/README.md
• llkv-table/README.md
• llkv-tpch/.gitignore
• llkv-tpch/Cargo.toml
• llkv-tpch/DRAFT-PRE-FINAL.md

This document introduces the LLKV database system, its architectural principles, and the relationships between its constituent crates. It provides a high-level map of how SQL queries flow through the system from parsing to storage, and explains the role of Apache Arrow as the universal data interchange format.

For details on individual subsystems, see:

• Workspace organization and crate dependencies: Workspace and Crates
• SQL query processing pipeline: SQL Query Processing Pipeline
• Arrow integration details: Data Formats and Arrow Integration

What is LLKV

LLKV is an experimental SQL database implemented as a Rust workspace of 15 crates. It layers SQL processing, streaming query execution, and MVCC transaction management on top of pluggable key-value storage backends. The system uses Apache Arrow RecordBatch as its primary data representation at every layer, enabling zero-copy operations and SIMD-friendly columnar processing.

The architecture separates concerns into six distinct layers:

1. SQL Interface
2. Query Planning
3. Runtime and Orchestration
4. Query Execution
5. Table and Metadata Management
6. Storage and I/O

Each layer communicates through well-defined interfaces centered on Arrow data structures.

Sources: README.md:1-107 Cargo.toml:1-89

Core Design Principles

LLKV's design reflects several intentional trade-offs:

Sources: README.md:36-42 llkv-storage/README.md:12-22 llkv-expr/README.md:66-72

Workspace Structure

The LLKV workspace consists of 15 crates organized by layer:

Sources: Cargo.toml:9-26 Cargo.toml:67-87 README.md:44-53

Component Architecture and Data Flow

The following diagram shows the major components and how Arrow RecordBatch flows through the system:

Sources: README.md:44-72 Cargo.toml:67-87

graph TB
    User["User / Application"]
subgraph "llkv-sql Crate"
        SqlEngine["SqlEngine"]
Preprocessor["SQL Preprocessor"]
Parser["sqlparser"]
InsertBuffer["InsertBuffer"]
end
    
    subgraph "llkv-plan Crate"
        SelectPlan["SelectPlan"]
InsertPlan["InsertPlan"]
CreateTablePlan["CreateTablePlan"]
OtherPlans["Other Plan Types"]
end
    
    subgraph "llkv-expr Crate"
        Expr["Expr<F>"]
ScalarExpr["ScalarExpr<F>"]
end
    
    subgraph "llkv-runtime Crate"
        RuntimeContext["RuntimeContext"]
SessionHandle["SessionHandle"]
TxnSnapshot["TransactionSnapshot"]
end
    
    subgraph "llkv-executor Crate"
        TableExecutor["TableExecutor"]
StreamingOps["Streaming Operators"]
end
    
    subgraph "llkv-table Crate"
        Table["Table"]
SysCatalog["SysCatalog (Table 0)"]
FieldId["FieldId Resolution"]
end
    
    subgraph "llkv-column-map Crate"
        ColumnStore["ColumnStore"]
LogicalFieldId["LogicalFieldId"]
PhysicalKey["PhysicalKey Mapping"]
end
    
    subgraph "llkv-storage Crate"
        Pager["Pager Trait"]
MemPager["MemPager"]
SimdPager["SimdRDrivePager"]
end
    
    ArrowBatch["Arrow RecordBatch\n(Universal Format)"]
User -->|SQL String| SqlEngine
 
   SqlEngine --> Preprocessor
 
   Preprocessor --> Parser
 
   Parser -->|AST| SelectPlan
 
   Parser -->|AST| InsertPlan
 
   Parser -->|AST| CreateTablePlan
    
 
   SelectPlan --> Expr
 
   InsertPlan --> ScalarExpr
    
 
   SelectPlan --> RuntimeContext
 
   InsertPlan --> RuntimeContext
 
   CreateTablePlan --> RuntimeContext
    
 
   RuntimeContext --> SessionHandle
 
   RuntimeContext --> TxnSnapshot
 
   RuntimeContext --> TableExecutor
 
   RuntimeContext --> Table
    
 
   TableExecutor --> StreamingOps
 
   StreamingOps --> Table
    
 
   Table --> SysCatalog
 
   Table --> FieldId
 
   Table --> ColumnStore
    
 
   ColumnStore --> LogicalFieldId
 
   ColumnStore --> PhysicalKey
 
   ColumnStore --> Pager
    
 
   Pager --> MemPager
 
   Pager --> SimdPager
    
 
   Table -.->|Produces/Consumes| ArrowBatch
 
   StreamingOps -.->|Produces/Consumes| ArrowBatch
 
   ColumnStore -.->|Serializes/Deserializes| ArrowBatch
 
   SqlEngine -.->|Returns| ArrowBatch

End-to-End Query Execution

This diagram traces a SELECT query from SQL text to results, showing the concrete code entities involved:

Sources: README.md:56-63 llkv-sql/README.md:1-107 llkv-runtime/README.md:33-41 llkv-table/README.md:10-25

sequenceDiagram
    participant App as "Application"
    participant SqlEngine as "SqlEngine::execute()"
    participant Preprocessor as "preprocess_sql()"
    participant Parser as "sqlparser::Parser"
    participant Planner as "build_select_plan()"
    participant Runtime as "RuntimeContext::execute_plan()"
    participant Executor as "TableExecutor::execute()"
    participant Table as "Table::scan_stream()"
    participant ColStore as "ColumnStore::gather_columns()"
    participant Pager as "Pager::batch_get()"
    
    App->>SqlEngine: SELECT * FROM users WHERE age > 18
    
    Note over SqlEngine,Preprocessor: Dialect normalization
    SqlEngine->>Preprocessor: Normalize SQLite/DuckDB syntax
    
    SqlEngine->>Parser: Parse normalized SQL
    Parser-->>SqlEngine: Statement AST
    
    SqlEngine->>Planner: Translate AST to SelectPlan
    Note over Planner: Build SelectPlan with\nExpr<String> predicates
    Planner-->>SqlEngine: SelectPlan
    
    SqlEngine->>Runtime: execute_plan(SelectPlan)
    
    Note over Runtime: Acquire TransactionSnapshot\nResolve field names to FieldId
    
    Runtime->>Executor: execute(SelectPlan, context)
    
    Note over Executor: Compile Expr<FieldId>\ninto EvalProgram
    
    Executor->>Table: scan_stream(fields, predicate)
    
    Note over Table: Apply MVCC filtering\nPush down predicates
    
    Table->>ColStore: gather_columns(LogicalFieldId[])
    
    Note over ColStore: Map LogicalFieldId\nto PhysicalKey
    
    ColStore->>Pager: batch_get(PhysicalKey[])
    Pager-->>ColStore: EntryHandle[] (zero-copy)
    
    Note over ColStore: Deserialize Arrow buffers\nApply row_id filtering
    
    ColStore-->>Table: RecordBatch
    Table-->>Executor: RecordBatch
    
    Note over Executor: Apply projections\nEvaluate expressions
    
    Executor-->>Runtime: RecordBatch stream
    Runtime-->>SqlEngine: Vec<RecordBatch>
    SqlEngine-->>App: Query results

Key Features

MVCC Transaction Management

LLKV implements multi-version concurrency control with snapshot isolation:

• Every table includes three system columns: row_id (monotonic), created_by (transaction ID), and deleted_by (transaction ID or NULL)
• TxnIdManager in llkv-transaction allocates monotonic transaction IDs and tracks commit watermarks
• TransactionSnapshot captures a consistent view of the database at transaction start
• Auto-commit statements use TXN_ID_AUTO_COMMIT = 1
• Explicit transactions maintain both persistent and staging contexts for isolation

Sources: README.md:64-72 llkv-runtime/README.md:20-32 llkv-table/README.md:32-35

Zero-Copy Storage Pipeline

The storage layer supports zero-copy reads when backed by SimdRDrivePager:

1. ColumnStore maps LogicalFieldId to PhysicalKey
2. Pager::batch_get() returns EntryHandle wrappers around memory-mapped regions
3. Arrow arrays are deserialized directly from the mapped memory without intermediate copies
4. SIMD-aligned buffers enable vectorized predicate evaluation

Sources: llkv-column-map/README.md:19-41 llkv-storage/README.md:12-28 README.md:12-13

Compiled Expression Evaluation

Predicates and scalar expressions compile to stack-based bytecode:

• Expr<FieldId> structures in llkv-expr represent logical predicates
• ProgramCompiler in llkv-table translates expressions into EvalProgram bytecode
• DomainProgram tracks which row IDs satisfy predicates
• Bytecode evaluation uses stack-based execution for efficient vectorized operations

Sources: llkv-expr/README.md:1-88 llkv-table/README.md:10-18 README.md:46-53

SQL Logic Test Infrastructure

LLKV includes comprehensive SQL correctness testing:

• llkv-slt-tester wraps the sqllogictest framework
• LlkvSltRunner discovers .slt files and executes test suites
• Supports remote test fetching via .slturl pointer files
• Environment variable LLKV_SLT_STATS=1 enables detailed query statistics
• CI runs the full suite on Linux, macOS, and Windows

Sources: README.md:75-77 llkv-slt-tester/README.md:1-57

Getting Started

The main entry point is the llkv crate, which re-exports the SQL interface:

For persistent storage, use SimdRDrivePager instead of MemPager. For transaction control beyond auto-commit, obtain a SessionHandle via SqlEngine::session().

Sources: README.md:14-33 demos/llkv-sql-pong-demo/src/main.rs:386-393

Relationship to Related Projects

LLKV shares architectural concepts with Apache DataFusion but differs in several key areas:

LLKV deliberately avoids the DataFusion task scheduler to explore trade-offs in a synchronous execution model, while maintaining compatibility with the same SQL parser and Arrow memory layout.

Sources: README.md:36-42 README.md:8-13

Architecture

Relevant source files

• Cargo.lock
• Cargo.toml
• README.md
• demos/llkv-sql-pong-demo/src/main.rs
• llkv-aggregate/README.md
• llkv-column-map/README.md
• llkv-csv/README.md
• llkv-expr/README.md
• llkv-join/README.md
• llkv-runtime/README.md
• llkv-sql/src/tpch.rs
• llkv-storage/README.md
• llkv-table/README.md
• llkv-tpch/.gitignore
• llkv-tpch/Cargo.toml
• llkv-tpch/DRAFT-PRE-FINAL.md

This document describes the overall system architecture of LLKV, explaining its layered design, core abstractions, and how components interact to provide SQL functionality over key-value storage. For details on individual crates and their dependencies, see Workspace and Crates. For the end-to-end query execution flow, see SQL Query Processing Pipeline. For Arrow integration specifics, see Data Formats and Arrow Integration.

Layered Design

LLKV is organized into six architectural layers, each with focused responsibilities. Higher layers depend only on lower layers, and all layers communicate through Apache Arrow RecordBatch structures as the universal data interchange format.

Sources: Cargo.toml:1-89 README.md:44-53 llkv-sql/README.md:1-10 llkv-runtime/README.md:1-10 llkv-executor/README.md:1-10 llkv-table/README.md:1-18 llkv-storage/README.md:1-17

graph TB
    subgraph L1["Layer 1: User Interface"]
SQL["SQL Queries"]
REPL["CLI REPL"]
DEMO["Demo Applications"]
BENCH["TPC-H Benchmarks"]
end
    
    subgraph L2["Layer 2: SQL Processing"]
SQLENG["SqlEngine\nllkv-sql"]
PLAN["Query Plans\nllkv-plan"]
EXPR["Expression AST\nllkv-expr"]
end
    
    subgraph L3["Layer 3: Runtime & Orchestration"]
RUNTIME["RuntimeContext\nllkv-runtime"]
TXNMGR["TxnIdManager\nllkv-transaction"]
CATALOG["CatalogManager\nllkv-runtime"]
end
    
    subgraph L4["Layer 4: Query Execution"]
EXECUTOR["TableExecutor\nllkv-executor"]
AGG["Accumulators\nllkv-aggregate"]
JOIN["HashJoinExecutor\nllkv-join"]
end
    
    subgraph L5["Layer 5: Data Management"]
TABLE["Table\nllkv-table"]
COLMAP["ColumnStore\nllkv-column-map"]
SYSCAT["SysCatalog\nllkv-table"]
end
    
    subgraph L6["Layer 6: Storage"]
PAGER["Pager trait\nllkv-storage"]
MEMPAGER["MemPager"]
SIMDPAGER["SimdRDrivePager"]
end
    
 
   SQL --> SQLENG
 
   REPL --> SQLENG
 
   DEMO --> SQLENG
 
   BENCH --> SQLENG
    
 
   SQLENG --> PLAN
 
   SQLENG --> EXPR
 
   PLAN --> RUNTIME
    
 
   RUNTIME --> TXNMGR
 
   RUNTIME --> CATALOG
 
   RUNTIME --> EXECUTOR
 
   RUNTIME --> TABLE
    
 
   EXECUTOR --> AGG
 
   EXECUTOR --> JOIN
 
   EXECUTOR --> TABLE
    
 
   TABLE --> COLMAP
 
   TABLE --> SYSCAT
 
   COLMAP --> PAGER
 
   SYSCAT --> COLMAP
    
 
   PAGER --> MEMPAGER
 
   PAGER --> SIMDPAGER

Core Architectural Principles

Arrow-Native Data Flow

All data flowing between components is represented as Apache Arrow RecordBatch structures. This enables:

• Zero-copy operations : Arrow buffers can be passed between layers without serialization
• SIMD-friendly processing : Columnar layout supports vectorized operations
• Consistent memory model : All layers use the same in-memory representation

The RecordBatch abstraction appears at every boundary: SQL parsing produces plans that operate on batches, the executor streams batches, tables persist batches, and the column store chunks batches for storage.

Sources: README.md:10-12 README.md:22-23 llkv-table/README.md:10-11 llkv-column-map/README.md:10-14

Storage Abstraction Through Pager Trait

The Pager trait in llkv-storage provides a pluggable storage backend interface:

Both implementations satisfy the same batch get/put contract, allowing higher layers to remain storage-agnostic. The runtime uses dual-pager contexts: persistent storage for committed tables and in-memory staging for uncommitted transaction objects.

Sources: llkv-storage/README.md:12-22 llkv-runtime/README.md:26-32

MVCC Integration

Multi-version concurrency control (MVCC) is implemented as system metadata columns injected at the table layer:

• row_id: Monotonic row identifier
• created_by: Transaction ID that created this row version
• deleted_by: Transaction ID that deleted this row (or NULL if active)

These columns are stored alongside user data in ColumnStore, enabling snapshot isolation without separate version chains. The TxnIdManager in llkv-transaction allocates monotonic transaction IDs and tracks commit watermarks. The runtime enforces visibility rules during scans by filtering based on snapshot transaction IDs.

Sources: llkv-table/README.md:13-17 llkv-runtime/README.md:19-25 llkv-column-map/README.md:27-28

Component Interaction Patterns

Query Execution Flow

Sources: README.md:56-62 llkv-sql/README.md:15-20 llkv-runtime/README.md:12-17 llkv-executor/README.md:12-17 llkv-table/README.md:19-25 llkv-column-map/README.md:24-28

Dual-Context Transaction Management

The runtime maintains two execution contexts during explicit transactions. The persistent context operates on committed tables directly, while the staging context buffers newly created tables in memory. On commit, staged operations are replayed into the persistent context after the TxnIdManager confirms no conflicts and advances the commit watermark. On rollback, the staging context is dropped and all uncommitted work is discarded.

Sources: llkv-runtime/README.md:26-32 llkv-runtime/README.md:12-17

Column Storage and Logical Field Mapping

The ColumnStore maintains a mapping from LogicalFieldId (namespace + table ID + field ID) to physical storage keys. Each logical field has a descriptor chunk (metadata about the column), data chunks (Arrow-serialized column arrays), and row ID chunks (per-chunk row identifiers for filtering). This three-level mapping isolates user data from system metadata while allowing efficient scans and appends.

Sources: llkv-column-map/README.md:18-23 llkv-table/README.md:13-17 llkv-column-map/README.md:10-17

Key Abstractions

SqlEngine

Entry point for SQL execution. Located in llkv-sql, it:

• Preprocesses SQL for dialect compatibility (DuckDB, SQLite quirks)
• Parses with sqlparser crate
• Batches compatible INSERT statements
• Delegates execution to RuntimeContext
• Returns ExecutionResult enums

Sources: llkv-sql/README.md:1-20 README.md:56-59

RuntimeContext

Orchestration layer in llkv-runtime that:

• Executes all statement types (DDL, DML, queries)
• Manages transaction snapshots and MVCC injection
• Coordinates between table layer and executor
• Maintains catalog manager for schema metadata
• Implements dual-context staging for transactions

Sources: llkv-runtime/README.md:12-25 llkv-runtime/README.md:34-40

Table and ColumnStore

Table in llkv-table provides schema-aware APIs:

• Schema validation on CREATE TABLE and append
• MVCC column injection (row_id, created_by, deleted_by)
• Streaming scan API with predicate pushdown
• Integration with system catalog (table 0)

ColumnStore in llkv-column-map handles physical storage:

• Arrow-serialized column chunks
• Logical-to-physical key mapping
• Append pipeline with row-id sorting and last-writer-wins semantics
• Atomic multi-key commits through pager

Sources: llkv-table/README.md:12-25 llkv-column-map/README.md:12-28

TableExecutor

Execution engine in llkv-executor that:

• Streams RecordBatch results from table scans
• Evaluates projections, filters, and scalar expressions
• Coordinates with llkv-aggregate for aggregation
• Coordinates with llkv-join for join operations
• Applies MVCC visibility filters during scans

Sources: llkv-executor/README.md:1-17 README.md:60-61

Pager Trait

Storage abstraction in llkv-storage that:

• Exposes batch get/put over (PhysicalKey, EntryHandle) pairs
• Supports atomic multi-key updates
• Enables zero-copy reads when backed by memory-mapped storage
• Implementations: MemPager (heap), SimdRDrivePager (persistent)

Sources: llkv-storage/README.md:12-22 README.md:11-12

Crate Organization

The workspace contains 15 crates organized by layer:

For detailed dependency graphs and crate responsibilities, see Workspace and Crates.

Sources: Cargo.toml:67-87 README.md:44-53

Execution Model

Synchronous with Work-Stealing

LLKV defaults to synchronous execution using Rayon for parallelism:

• Query execution is synchronous, not async
• Rayon work-stealing parallelizes scans and projections
• Crossbeam channels coordinate between threads
• Embeds cleanly inside Tokio when needed (e.g., SLT test runner)

This design minimizes scheduler overhead for individual queries while maintaining high throughput for concurrent workloads.

Sources: README.md:38-41 llkv-column-map/README.md:32-34

Streaming Results

Queries produce results incrementally:

• TableExecutor yields fixed-size RecordBatches
• No full result set materialization
• Callers process batches via callback or iterator
• Join and aggregate operators buffer only necessary state

Sources: llkv-table/README.md:24-25 llkv-executor/README.md:14-17 llkv-join/README.md:19-22

Data Lifecycle

Write Path

1. User submits INSERT or UPDATE through SqlEngine
2. RuntimeContext validates schema and injects MVCC columns
3. Table::append validates RecordBatch schema
4. ColumnStore::append sorts by row_id, rewrites conflicts
5. Pager::batch_put commits Arrow-serialized chunks atomically
6. Transaction manager advances commit watermark

Read Path

1. User submits SELECT through SqlEngine
2. RuntimeContext acquires transaction snapshot
3. TableExecutor creates scan with projection and filter
4. Table::scan_stream initiates ColumnStream
5. ColumnStore fetches chunks via Pager::batch_get (zero-copy)
6. MVCC filtering applied using snapshot visibility rules
7. Executor evaluates expressions and streams RecordBatches to caller

Sources: README.md:56-62 llkv-column-map/README.md:24-28 llkv-table/README.md:19-25

Workspace and Crates

Relevant source files

• Cargo.lock
• Cargo.toml
• llkv-column-map/src/store/projection.rs
• llkv-expr/Cargo.toml
• llkv-expr/src/lib.rs
• llkv-expr/src/literal.rs
• llkv-plan/Cargo.toml
• llkv-plan/src/lib.rs
• llkv-storage/src/serialization.rs
• llkv-table/Cargo.toml

Purpose and Scope

This document details the Cargo workspace structure and the 15+ crates that comprise the LLKV database system. Each crate is designed with a single responsibility and well-defined interfaces, enabling independent testing and evolution of components. This page catalogs the role of each crate, their internal dependencies, and how they map to the system's layered architecture described in Architecture.

For information about how SQL queries flow through these crates, see SQL Query Processing Pipeline. For details on specific subsystems like storage or transactions, refer to sections 7 and following.

Workspace Overview

The LLKV workspace is defined in Cargo.toml:67-88 and contains 18 member crates organized into core system components, specialized operations, testing infrastructure, and demonstration applications.

Workspace Structure:

graph TB
    subgraph "Core System Crates"
        LLKV["llkv\n(main entry)"]
SQL["llkv-sql\n(SQL interface)"]
PLAN["llkv-plan\n(query plans)"]
EXPR["llkv-expr\n(expression AST)"]
RUNTIME["llkv-runtime\n(orchestration)"]
EXECUTOR["llkv-executor\n(execution)"]
TABLE["llkv-table\n(table layer)"]
COLMAP["llkv-column-map\n(column store)"]
STORAGE["llkv-storage\n(storage abstraction)"]
TXN["llkv-transaction\n(MVCC manager)"]
RESULT["llkv-result\n(error types)"]
end
    
    subgraph "Specialized Operations"
        AGG["llkv-aggregate\n(aggregation)"]
JOIN["llkv-join\n(joins)"]
CSV["llkv-csv\n(CSV import)"]
end
    
    subgraph "Testing Infrastructure"
        SLT["llkv-slt-tester\n(SQL logic tests)"]
TESTUTIL["llkv-test-utils\n(test utilities)"]
TPCH["llkv-tpch\n(TPC-H benchmarks)"]
end
    
    subgraph "Demonstrations"
        DEMO["llkv-sql-pong-demo\n(interactive demo)"]
end

Sources: Cargo.toml:67-88

Core System Crates

llkv

Purpose: Main library crate that re-exports the primary user-facing APIs from llkv-sql and llkv-runtime.

Key Dependencies: llkv-sql, llkv-runtime

Responsibilities:

• Provides the consolidated API surface for embedding LLKV
• Re-exports SqlEngine for SQL query execution
• Re-exports runtime components for programmatic database access

Sources: Cargo.toml:9-10

llkv-sql

Path: llkv-sql/

Purpose: SQL interface layer that parses SQL statements, preprocesses dialect-specific syntax, and translates them into typed query plans.

Key Dependencies:

• llkv-plan - Query plan structures
• llkv-expr - Expression AST
• llkv-runtime - Execution orchestration
• sqlparser - SQL parsing (version 0.59.0)

Responsibilities:

• SQL statement preprocessing for dialect compatibility
• AST-to-plan translation
• INSERT statement buffering optimization
• SQL query result formatting

Primary Types:

• SqlEngine - Main query interface

Sources: Cargo.toml21 llkv-plan/src/lib.rs:1-38

llkv-plan

Path: llkv-plan/

Purpose: Query planner that defines typed plan structures representing SQL operations.

Key Dependencies:

• llkv-expr - Expression types
• llkv-result - Error handling
• sqlparser - SQL AST types

Responsibilities:

• Plan structure definitions (SelectPlan, InsertPlan, UpdatePlan, DeletePlan)
• SQL-to-plan conversion utilities
• Subquery correlation tracking
• Plan graph serialization for debugging

Primary Types:

• SelectPlan, InsertPlan, UpdatePlan, DeletePlan, CreateTablePlan
• SubqueryCorrelatedTracker
• RangeSelectRows - Range-based row selection

Sources: llkv-plan/Cargo.toml:1-28 llkv-plan/src/lib.rs:1-38

llkv-expr

Path: llkv-expr/

Purpose: Expression AST definitions and literal value handling, independent of concrete Arrow scalar types.

Key Dependencies:

• arrow - Arrow data types

Responsibilities:

• Expression AST (Expr<T>, ScalarExpr<T>)
• Literal value representation (Literal enum)
• Type-aware predicate compilation (typed_predicate)
• Decimal value handling

Primary Types:

• Expr<T> - Generic expression with field identifier type parameter
• ScalarExpr<T> - Scalar expressions
• Literal - Untyped literal values
• DecimalValue - Fixed-precision decimal
• IntervalValue - Calendar interval

Sources: llkv-expr/Cargo.toml:1-19 llkv-expr/src/lib.rs:1-21 llkv-expr/src/literal.rs:1-446

llkv-runtime

Path: llkv-runtime/

Purpose: Runtime orchestration layer providing MVCC transaction management, session handling, and system catalog coordination.

Key Dependencies:

• llkv-executor - Query execution
• llkv-table - Table operations
• llkv-transaction - MVCC snapshots

Responsibilities:

• Transaction lifecycle management
• Session state tracking
• System catalog access
• Query plan execution coordination
• MVCC snapshot creation and cleanup

Primary Types:

• RuntimeContext - Main runtime state
• Session - Per-connection state

Sources: Cargo.toml19

llkv-executor

Path: llkv-executor/

Purpose: Query execution engine that evaluates plans and produces streaming results.

Key Dependencies:

• llkv-plan - Plan structures
• llkv-expr - Expression evaluation
• llkv-table - Table scans
• llkv-aggregate - Aggregation
• llkv-join - Join algorithms

Responsibilities:

• SELECT plan execution
• Projection and filtering
• Aggregation coordination
• Join execution
• Streaming RecordBatch production

Sources: Cargo.toml14

llkv-table

Path: llkv-table/

Purpose: Schema-aware table abstraction providing high-level data operations over columnar storage.

Key Dependencies:

• llkv-column-map - Column storage
• llkv-expr - Predicate compilation
• llkv-storage - Storage backend
• arrow - RecordBatch representation

Responsibilities:

• Schema validation and enforcement
• MVCC metadata injection (row_id, created_by, deleted_by)
• Predicate compilation and optimization
• RecordBatch append/scan operations
• Column data type management

Primary Types:

• Table - Main table interface
• TablePlanner - Query optimization
• TableExecutor - Execution strategies

Sources: llkv-table/Cargo.toml:1-60 llkv-column-map/src/store/projection.rs:1-728

llkv-column-map

Path: llkv-column-map/

Purpose: Columnar storage layer that chunks Arrow arrays and manages the mapping from logical fields to physical storage keys.

Key Dependencies:

• llkv-storage - Pager abstraction
• llkv-expr - Field identifiers
• arrow - Array serialization

Responsibilities:

• Column chunk management (serialization/deserialization)
• LogicalFieldId → PhysicalKey mapping
• Multi-column gather operations with caching
• Row visibility filtering
• Chunk metadata tracking (min/max values)

Primary Types:

• ColumnStore<P> - Main storage interface
• LogicalFieldId - Namespaced field identifier
• MultiGatherContext - Reusable context for multi-column reads
• GatherNullPolicy - Null handling strategies

Sources: Cargo.toml12 llkv-column-map/src/store/projection.rs:38-227

llkv-storage

Path: llkv-storage/

Purpose: Storage abstraction layer defining the Pager trait and providing implementations for in-memory and persistent backends.

Key Dependencies:

• simd-r-drive - SIMD-optimized persistent storage (optional)
• arrow - Buffer types

Responsibilities:

• Pager trait definition (batch_get/batch_put)
• Zero-copy array serialization format
• MemPager - In-memory HashMap backend
• SimdRDrivePager - Memory-mapped persistent backend
• Physical key allocation

Primary Types:

• Pager trait
• MemPager, SimdRDrivePager
• PhysicalKey - Storage location identifier
• Serialization format with custom encoding (see llkv-storage/src/serialization.rs:1-586)

Sources: Cargo.toml22 llkv-storage/src/serialization.rs:1-130

llkv-transaction

Path: llkv-transaction/

Purpose: MVCC transaction manager providing snapshot isolation and row visibility determination.

Key Dependencies:

• llkv-result - Error types

Responsibilities:

• Transaction ID allocation
• MVCC snapshot creation
• Commit watermark tracking
• Row visibility rules enforcement

Primary Types:

• TransactionManager
• Snapshot - Transaction isolation view
• TxnId - Transaction identifier

Sources: Cargo.toml25

llkv-result

Path: llkv-result/

Purpose: Common error and result types used throughout the system.

Key Dependencies: None (foundational crate)

Responsibilities:

• Error enum with all error variants
• Result<T> type alias
• Error conversion traits

Sources: Cargo.toml18

Specialized Operations Crates

llkv-aggregate

Path: llkv-aggregate/

Purpose: Aggregate function evaluation including accumulators and distinct value tracking.

Key Dependencies:

• arrow - Array operations

Responsibilities:

• Aggregate function implementations (SUM, AVG, COUNT, MIN, MAX)
• Accumulator state management
• DISTINCT value tracking
• Group-by hash table operations

Sources: Cargo.toml11

llkv-join

Path: llkv-join/

Purpose: Join algorithm implementations.

Key Dependencies:

• arrow - RecordBatch operations
• llkv-expr - Join predicates

Responsibilities:

• Hash join implementation
• Nested loop join
• Join key extraction
• Result materialization

Sources: Cargo.toml16

llkv-csv

Path: llkv-csv/

Purpose: CSV file ingestion and export utilities.

Key Dependencies:

• llkv-table - Table operations
• arrow - CSV reader integration

Responsibilities:

• CSV to RecordBatch conversion
• Bulk insert optimization
• Schema inference from CSV headers

Sources: Cargo.toml13

Testing Infrastructure Crates

llkv-test-utils

Path: llkv-test-utils/

Purpose: Shared test utilities including tracing setup and common test fixtures.

Key Dependencies:

• tracing-subscriber - Logging configuration

Responsibilities:

• Consistent tracing initialization across tests
• Common test helpers
• Auto-initialization feature for convenience

Sources: Cargo.toml24

llkv-slt-tester

Path: llkv-slt-tester/

Purpose: SQL Logic Test runner providing standardized correctness testing.

Key Dependencies:

• llkv-sql - SQL execution
• sqllogictest - Test framework (version 0.28.4)

Responsibilities:

• .slt file discovery and execution
• Remote test suite fetching (.slturl files)
• Test result comparison
• AsyncDB adapter for LLKV

Primary Types:

• LlkvSltRunner - Test runner
• EngineHarness - Adapter interface

Sources: Cargo.toml20

llkv-tpch

Path: llkv-tpch/

Purpose: TPC-H benchmark suite for performance testing.

Key Dependencies:

• llkv - Database interface
• llkv-sql - SQL execution
• tpchgen - Data generation (version 2.0.1)

Responsibilities:

• TPC-H data generation at various scale factors
• Query execution (Q1-Q22)
• Performance measurement
• Benchmark result reporting

Sources: Cargo.toml62

Demonstration Applications

llkv-sql-pong-demo

Path: demos/llkv-sql-pong-demo/

Purpose: Interactive demonstration showing LLKV's SQL capabilities through a Pong game implemented in SQL.

Key Dependencies:

• llkv-sql - SQL execution
• crossterm - Terminal UI (version 0.29.0)

Responsibilities:

• Terminal-based interactive interface
• Real-time SQL query execution
• Game state management via SQL tables
• User input handling

graph LR
    LLKV["llkv"]
SQL["llkv-sql"]
PLAN["llkv-plan"]
EXPR["llkv-expr"]
RUNTIME["llkv-runtime"]
EXECUTOR["llkv-executor"]
TABLE["llkv-table"]
COLMAP["llkv-column-map"]
STORAGE["llkv-storage"]
TXN["llkv-transaction"]
RESULT["llkv-result"]
AGG["llkv-aggregate"]
JOIN["llkv-join"]
CSV["llkv-csv"]
SLT["llkv-slt-tester"]
TESTUTIL["llkv-test-utils"]
TPCH["llkv-tpch"]
DEMO["llkv-sql-pong-demo"]
LLKV --> SQL
 
   LLKV --> RUNTIME
    
 
   SQL --> PLAN
 
   SQL --> EXPR
 
   SQL --> RUNTIME
 
   SQL --> EXECUTOR
 
   SQL --> TABLE
 
   SQL --> TXN
    
 
   RUNTIME --> EXECUTOR
 
   RUNTIME --> TABLE
 
   RUNTIME --> TXN
    
 
   EXECUTOR --> PLAN
 
   EXECUTOR --> EXPR
 
   EXECUTOR --> TABLE
 
   EXECUTOR --> AGG
 
   EXECUTOR --> JOIN
    
 
   TABLE --> COLMAP
 
   TABLE --> EXPR
 
   TABLE --> PLAN
 
   TABLE --> STORAGE
    
 
   COLMAP --> STORAGE
 
   COLMAP --> EXPR
    
 
   PLAN --> EXPR
 
   PLAN --> RESULT
    
 
   CSV --> TABLE
    
 
   TXN --> RESULT
 
   STORAGE --> RESULT
 
   EXPR --> RESULT
 
   COLMAP --> RESULT
 
   TABLE --> RESULT
    
 
   SLT --> SQL
 
   SLT --> RUNTIME
 
   SLT --> TESTUTIL
    
 
   TPCH --> LLKV
 
   TPCH --> SQL
    
 
   DEMO --> SQL

Sources: Cargo.toml86

Crate Dependency Graph

The following diagram shows the direct dependencies between workspace crates. Arrows point from dependent crates to their dependencies.

Crate Dependencies:

Sources: Cargo.toml:9-25 llkv-table/Cargo.toml:14-31 llkv-plan/Cargo.toml:14-24

Key Observations:

1. llkv-result is a foundational crate with no internal dependencies, consumed by nearly all other crates for error handling.

2. llkv-expr depends only on llkv-result, making it a stable base for expression handling across the system.

3. llkv-plan builds on llkv-expr and adds plan-specific structures.

4. llkv-storage and llkv-transaction** are independent of each other, allowing flexibility in storage backend selection.

5. llkv-table integrates storage, expressions, and planning to provide a cohesive data layer.

6. llkv-executor coordinates specialized operations (aggregate, join) and table access.

7. llkv-runtime sits at the top of the execution stack, orchestrating transactions and query execution.

8. llkv-sql ties together all layers to provide the SQL interface.

Mapping Crates to System Layers

This diagram shows how workspace crates map to the architectural layers described in Architecture.

Layered Architecture Mapping:

Sources: Cargo.toml:67-88

External Dependencies

The workspace declares several critical external dependencies that enable core functionality.

Apache Arrow Ecosystem

Version: 57.0.0

Crates:

• arrow - Core Arrow functionality with prettyprint and IPC features
• arrow-array - Array implementations
• arrow-schema - Schema types
• arrow-buffer - Buffer management
• arrow-ord - Ordering operations

Usage: Arrow provides the universal columnar data format throughout LLKV. RecordBatch is used as the data interchange format at every layer, enabling zero-copy operations and SIMD-friendly processing.

Sources: Cargo.toml:32-36

SQL Parsing

Crate: sqlparser
Version: 0.59.0

Usage: Parses SQL text into AST nodes. Used by llkv-sql and llkv-plan to convert SQL queries into typed plan structures.

Sources: Cargo.toml52

SIMD-Optimized Storage

Crate: simd-r-drive
Version: 0.15.5-alpha

Usage: Provides memory-mapped, SIMD-accelerated persistent storage backend. The SimdRDrivePager implementation in llkv-storage uses this for zero-copy array access.

Related: simd-r-drive-entry-handle for Arrow buffer integration

Sources: Cargo.toml:26-27

Testing and Benchmarking

Key Dependencies:

Sources: Cargo.toml:40-62

Utilities

Key Dependencies:

Sources: Cargo.toml:37-64

Workspace Configuration

The workspace is configured with shared package metadata and dependency versions to ensure consistency across all crates.

Shared Package Metadata:

Build Settings:

• Edition: 2024 (Rust 2024 edition)
• Resolver: Version 2 (new dependency resolver)
• Version: 0.8.2-alpha (all crates share this version)

Sources: Cargo.toml:1-8 Cargo.toml88

Summary Table

Sources: Cargo.toml:1-89

SQL Query Processing Pipeline

Relevant source files

• README.md
• demos/llkv-sql-pong-demo/src/main.rs
• llkv-executor/README.md
• llkv-plan/README.md
• llkv-sql/README.md
• llkv-sql/src/sql_engine.rs
• llkv-sql/src/tpch.rs
• llkv-tpch/.gitignore
• llkv-tpch/Cargo.toml
• llkv-tpch/DRAFT-PRE-FINAL.md

Purpose and Scope

This document describes the end-to-end SQL query processing pipeline in LLKV, from raw SQL text input to final results. It covers the five major stages: SQL preprocessing, parsing, plan translation, execution coordination, and result formatting.

For information about the specific plan structures created during translation, see Plan Structures. For details on how plans are executed to produce results, see Query Execution. For the user-facing SqlEngine API, see SqlEngine API.

Overview

The SQL query processing pipeline transforms user-provided SQL text into Arrow RecordBatch results through a series of well-defined stages. The primary entry point is SqlEngine::execute(), which orchestrates the entire flow while maintaining transaction boundaries and handling cross-statement optimizations like INSERT buffering.

Sources: llkv-sql/src/sql_engine.rs:933-998

graph TB
    SQL["Raw SQL Text"]
PREPROCESS["Stage 1: SQL Preprocessing\nDialect Normalization"]
PARSE["Stage 2: Parsing\nsqlparser → AST"]
TRANSLATE["Stage 3: Plan Translation\nAST → PlanStatement"]
EXECUTE["Stage 4: Plan Execution\nRuntimeEngine"]
RESULTS["Stage 5: Result Formatting\nRuntimeStatementResult"]
SQL --> PREPROCESS
 
   PREPROCESS --> PARSE
 
   PARSE --> TRANSLATE
 
   TRANSLATE --> EXECUTE
 
   EXECUTE --> RESULTS
    
 
   PREPROCESS --> |preprocess_sql_input| PREPROCESS_IMPL["• preprocess_tpch_connect_syntax()\n• preprocess_create_type_syntax()\n• preprocess_exclude_syntax()\n• preprocess_trailing_commas_in_values()\n• preprocess_empty_in_lists()\n• preprocess_index_hints()\n• preprocess_reindex_syntax()\n• preprocess_bare_table_in_clauses()"]
PARSE --> |parse_sql_with_recursion_limit| PARSER["sqlparser::Parser\nPARSER_RECURSION_LIMIT = 200"]
TRANSLATE --> |translate_statement| PLANNER["• SelectPlan\n• InsertPlan\n• UpdatePlan\n• DeletePlan\n• CreateTablePlan\n• DDL Plans"]
EXECUTE --> |engine.execute_statement| RUNTIME["RuntimeEngine\n• Transaction Management\n• MVCC Snapshots\n• Catalog Operations"]
style PREPROCESS fill:#f9f9f9
    style PARSE fill:#f9f9f9
    style TRANSLATE fill:#f9f9f9
    style EXECUTE fill:#f9f9f9
    style RESULTS fill:#f9f9f9

Stage 1: SQL Preprocessing

Before parsing, the SQL text undergoes a series of preprocessing transformations to normalize dialect-specific syntax. This allows LLKV to accept SQL written for SQLite, DuckDB, and other dialects while presenting a consistent AST to the planner.

Preprocessing Transformations

Sources: llkv-sql/src/sql_engine.rs:623-873 llkv-sql/src/tpch.rs:1-17

Fallback Trigger Preprocessing

If parsing fails and the SQL contains CREATE TRIGGER, the engine applies an additional preprocess_sqlite_trigger_shorthand() transformation and retries. This handles SQLite's optional BEFORE/AFTER timing and FOR EACH ROW clauses by injecting defaults that sqlparser expects.

Sources: llkv-sql/src/sql_engine.rs:941-957 llkv-sql/src/sql_engine.rs:771-842

Stage 2: Parsing

Parsing is delegated to the sqlparser crate, which produces a Vec<Statement> AST. LLKV configures the parser with:

• Dialect: GenericDialect to accept a wide range of SQL syntax
• Recursion Limit: PARSER_RECURSION_LIMIT = 200 (raised from sqlparser's default of 50 to handle deeply nested queries in test suites)

The parse_sql_with_recursion_limit() helper function wraps sqlparser's API to apply this custom limit.

Sources: llkv-sql/src/sql_engine.rs:317-324 llkv-sql/src/sql_engine.rs:939-957

Stage 3: Plan Translation

Each parsed Statement is translated into a strongly-typed PlanStatement that the runtime can execute. This translation happens through statement-specific methods in SqlEngine.

graph TB
    AST["sqlparser::ast::Statement"]
SELECT["Statement::Query"]
INSERT["Statement::Insert"]
UPDATE["Statement::Update"]
DELETE["Statement::Delete"]
CREATE["Statement::CreateTable"]
DROP["Statement::Drop"]
TRANSACTION["Statement::StartTransaction\nStatement::Commit\nStatement::Rollback"]
ALTER["Statement::AlterTable"]
OTHER["Other DDL/DML"]
SELECT_PLAN["translate_query()\n→ SelectPlan"]
INSERT_PLAN["buffer_insert()\n→ InsertPlan or buffered"]
UPDATE_PLAN["translate_update()\n→ UpdatePlan"]
DELETE_PLAN["translate_delete()\n→ DeletePlan"]
CREATE_PLAN["translate_create_table()\n→ CreateTablePlan"]
DROP_PLAN["translate_drop()\n→ PlanStatement::Drop*"]
TXN_RUNTIME["Direct runtime delegation\nflush INSERT buffer first"]
ALTER_PLAN["translate_alter_table()\n→ PlanStatement::Alter*"]
OTHER_PLAN["translate_* methods\n→ PlanStatement::*"]
AST --> SELECT
 
   AST --> INSERT
 
   AST --> UPDATE
 
   AST --> DELETE
 
   AST --> CREATE
 
   AST --> DROP
 
   AST --> TRANSACTION
 
   AST --> ALTER
 
   AST --> OTHER
    
 
   SELECT --> SELECT_PLAN
 
   INSERT --> INSERT_PLAN
 
   UPDATE --> UPDATE_PLAN
 
   DELETE --> DELETE_PLAN
 
   CREATE --> CREATE_PLAN
 
   DROP --> DROP_PLAN
 
   TRANSACTION --> TXN_RUNTIME
 
   ALTER --> ALTER_PLAN
 
   OTHER --> OTHER_PLAN
    
 
   SELECT_PLAN --> RUNTIME["RuntimeEngine::execute_statement()"]
INSERT_PLAN --> BUFFER_CHECK{"Buffering\nenabled?"}
BUFFER_CHECK -->|Yes| BUFFER["InsertBuffer\naccumulates rows"]
BUFFER_CHECK -->|No| RUNTIME
 
   UPDATE_PLAN --> RUNTIME
 
   DELETE_PLAN --> RUNTIME
 
   CREATE_PLAN --> RUNTIME
 
   DROP_PLAN --> RUNTIME
 
   TXN_RUNTIME --> RUNTIME
 
   ALTER_PLAN --> RUNTIME
 
   OTHER_PLAN --> RUNTIME
    
 
   BUFFER --> FLUSH_CHECK{"Flush\nneeded?"}
FLUSH_CHECK -->|Yes| FLUSH["Flush buffered rows"]
FLUSH_CHECK -->|No| CONTINUE["Continue buffering"]
FLUSH --> RUNTIME

Statement Routing

Sources: llkv-sql/src/sql_engine.rs:960-998

Translation Process

The translation process involves:

1. Column Resolution: Identifier strings are resolved to FieldId references using the runtime's catalog
2. Expression Translation: SQL expressions are converted to Expr<String>, then resolved to Expr<FieldId>
3. Subquery Handling: Correlated subqueries are tracked with placeholder generation
4. Parameter Binding: SQL placeholders (?, $1, :name) are mapped to parameter indices

Sources: llkv-sql/src/sql_engine.rs:1000-5000 (various translate_* methods)

sequenceDiagram
    participant SqlEngine
    participant Catalog as "RuntimeContext\nCatalog"
    participant ExprTranslator
    participant PlanBuilder
    
    SqlEngine->>Catalog: resolve_table("users")
    Catalog-->>SqlEngine: TableId(namespace=0, table=1)
    
    SqlEngine->>Catalog: resolve_column("id", TableId)
    Catalog-->>SqlEngine: ColumnResolution(FieldId)
    
    SqlEngine->>ExprTranslator: translate_expr(sqlparser::Expr)
    ExprTranslator->>ExprTranslator: Build Expr<String>
    ExprTranslator->>Catalog: resolve_identifiers()
    Catalog-->>ExprTranslator: Expr<FieldId>
    ExprTranslator-->>SqlEngine: Expr<FieldId>
    
    SqlEngine->>PlanBuilder: Create SelectPlan
    Note over PlanBuilder: Attach projections,\nfilters, sorts, limits
    PlanBuilder-->>SqlEngine: PlanStatement::Select(SelectPlan)

Stage 4: Plan Execution

Once a PlanStatement is constructed, it is passed to RuntimeEngine::execute_statement() for execution. The runtime coordinates:

• Transaction Management: Ensures each statement executes within a transaction snapshot
• MVCC Enforcement: Filters rows based on visibility rules
• Catalog Operations: Updates system catalog for DDL statements
• Executor Invocation: Delegates SelectPlan execution to llkv-executor

Execution Routing by Statement Type

Sources: llkv-sql/src/sql_engine.rs:587-609 llkv-runtime/ (RuntimeEngine implementation)

Stage 5: Result Formatting

The runtime returns a RuntimeStatementResult enum that represents the outcome of statement execution. SqlEngine surfaces this directly to callers via the execute() method, or converts it to Vec<RecordBatch> for the sql() convenience method.

Result Types

Sources: llkv-runtime/ (RuntimeStatementResult definition), llkv-sql/src/sql_engine.rs:933-998

Prepared Statements and Parameters

LLKV supports parameterized queries through a prepared statement mechanism that handles three parameter syntaxes:

• Positional (numbered): ?, ?1, ?2, $1, $2
• Named: :name, :id
• Auto-incremented: Sequential ? placeholders

Parameter Processing Pipeline

Sources: llkv-sql/src/sql_engine.rs:71-206 llkv-sql/src/sql_engine.rs:278-297

Parameter Substitution

During plan execution with parameters, the engine performs a second pass to replace sentinel strings (__llkv_param__N__) with the actual Literal values provided by the caller. This two-phase approach allows the same PlanStatement to be reused across multiple executions with different parameter values.

Sources: llkv-sql/src/sql_engine.rs:194-206

INSERT Buffering

SqlEngine includes an optional INSERT buffering optimization that batches consecutive INSERT ... VALUES statements targeting the same table. This is disabled by default but can be enabled with set_insert_buffering(true) for bulk ingestion workloads.

stateDiagram-v2
    [*] --> NoBuffer : buffering disabled
    NoBuffer --> NoBuffer : INSERT → immediate execute
    
    [*] --> BufferEmpty : buffering enabled
    BufferEmpty --> BufferActive : INSERT(table, cols, rows)
    
    BufferActive --> BufferActive : INSERT(same table/cols) accumulate rows
    BufferActive --> Flush : Different table
    BufferActive --> Flush : Different columns
    BufferActive --> Flush : Different conflict action
    BufferActive --> Flush : Row count ≥ MAX_BUFFERED_INSERT_ROWS
    BufferActive --> Flush : Non-INSERT statement
    BufferActive --> Flush : Transaction boundary
    
    Flush --> RuntimeExecution : Create InsertPlan from accumulated rows
    RuntimeExecution --> BufferEmpty : Reset buffer
    
    NoBuffer --> [*]
    BufferEmpty --> [*]

Buffering Logic

Sources: llkv-sql/src/sql_engine.rs:410-495 llkv-sql/src/sql_engine.rs:887-905

Buffer Flush Triggers

Sources: llkv-sql/src/sql_engine.rs:410-495

Error Handling and Table Mapping

The pipeline includes special error handling for table-not-found scenarios. When the runtime returns Error::NotFound or catalog-related errors, SqlEngine::execute_plan_statement() rewrites them to user-friendly messages like "Catalog Error: Table 'users' does not exist".

This mapping is skipped for CREATE VIEW and DROP VIEW statements where the "table" name refers to the view being created/dropped rather than a referenced table.

Sources: llkv-sql/src/sql_engine.rs:558-609

Data Formats and Arrow Integration

Relevant source files

• Cargo.lock
• Cargo.toml
• llkv-aggregate/README.md
• llkv-column-map/README.md
• llkv-column-map/src/store/projection.rs
• llkv-csv/README.md
• llkv-expr/Cargo.toml
• llkv-expr/README.md
• llkv-expr/src/lib.rs
• llkv-expr/src/literal.rs
• llkv-join/README.md
• llkv-plan/Cargo.toml
• llkv-plan/src/lib.rs
• llkv-runtime/README.md
• llkv-storage/README.md
• llkv-storage/src/serialization.rs
• llkv-table/Cargo.toml
• llkv-table/README.md

Purpose and Scope

This page documents how Apache Arrow columnar data structures serve as the universal data interchange format throughout LLKV. It covers the supported Arrow data types, the custom zero-copy serialization format used for persistence, and how RecordBatch flows between layers.

For information about how expressions evaluate over Arrow data, see Expression System. For details on storage pager abstractions, see Pager Interface and SIMD Optimization.

Arrow as the Universal Data Format

LLKV is Arrow-native : every layer of the system produces, consumes, and operates on arrow::record_batch::RecordBatch structures. This design choice enables:

• Zero-copy data access across layer boundaries
• SIMD-friendly vectorized operations via contiguous columnar buffers
• Unified type system from SQL parsing through storage
• Efficient interoperability with external Arrow-compatible tools

The following table maps system layers to their Arrow usage:

Sources: Cargo.toml32 llkv-table/README.md:10-11 llkv-column-map/README.md10 llkv-storage/README.md10

RecordBatch Flow Diagram

Key Data Flow Observations:

1. INSERT Path : RecordBatch → schema validation → MVCC column injection → column chunking → serialization → pager write
2. SELECT Path : Pager read → deserialization → column gather → RecordBatch construction → streaming to executor
3. Zero-Copy : EntryHandle wraps memory-mapped regions that Arrow arrays reference directly without copying

Sources: llkv-column-map/src/store/projection.rs:240-446 llkv-storage/src/serialization.rs:226-254 llkv-table/README.md:19-25

Supported Arrow Data Types

LLKV supports the following Arrow primitive and complex types:

Primitive Types

Variable-Length Types

Complex Types

Null Handling:
The current serialization format does not yet support null bitmaps. Arrays with null_count() > 0 will return an error during serialization. Null support is planned for future releases.

Sources: llkv-storage/src/serialization.rs:144-165 llkv-storage/src/serialization.rs:199-224 llkv-expr/src/literal.rs:78-94

Custom Serialization Format

Why Not Arrow IPC?

LLKV uses a custom minimal serialization format instead of Arrow's standard IPC (Inter-Process Communication) format for several reasons:

Trade-offs:

graph LR
    subgraph "Arrow IPC Format"
        IPC_SCHEMA["Schema object\nframing metadata"]
IPC_PADDING["Padding alignment\n8/64 byte boundaries"]
IPC_BUFFERS["Buffer pointers\n+ offsets"]
IPC_SIZE["Larger file size\n~20-40% overhead"]
end
    
    subgraph "LLKV Custom Format"
        CUSTOM_HEADER["24-byte header\nfixed size"]
CUSTOM_PAYLOAD["Raw buffer bytes\ncontiguous"]
CUSTOM_ZERO["Zero-copy rebuild\ndirect mmap"]
CUSTOM_SIZE["Minimal size\nno framing"]
end
    
 
   IPC_SCHEMA --> IPC_SIZE
 
   IPC_PADDING --> IPC_SIZE
 
   IPC_BUFFERS --> IPC_SIZE
    
 
   CUSTOM_HEADER --> CUSTOM_SIZE
 
   CUSTOM_PAYLOAD --> CUSTOM_ZERO

Design Goals:

1. Minimal headers : 24-byte fixed header, no schema objects per array
2. Predictable payloads : contiguous buffers for mmap-friendly access
3. True zero-copy : reconstruct ArrayData referencing original buffer directly
4. Stable on-disk codes : type tags are compile-time pinned to prevent corruption

Sources: llkv-storage/src/serialization.rs:1-28 llkv-storage/src/serialization.rs:41-135

Serialization Format Details

Header Structure

Every serialized array begins with a 24-byte header:

Offset  Size  Field
------  ----  -----
0-3     4     Magic bytes: b"ARR0"
4       1     Layout code (Primitive=0, FslFloat32=1, Varlen=2, Struct=3)
5       1     Type code (PrimType enum value)
6       1     Precision (for Decimal128) or padding
7       1     Scale (for Decimal128) or padding
8-15    8     Array length (u64, element count)
16-19   4     extra_a (layout-specific u32)
20-23   4     extra_b (layout-specific u32)
24+     var   Payload (layout-specific buffer bytes)

Layout Variants

Primitive Layout

For fixed-width types (Int32, Float64, etc.):

• extra_a: Length of values buffer in bytes
• extra_b: Unused (0)
• Payload: Raw values buffer

Varlen Layout

For variable-length types (Utf8, Binary, etc.):

• extra_a: Length of offsets buffer in bytes
• extra_b: Length of values buffer in bytes
• Payload: Offsets buffer followed by values buffer

FixedSizeList Layout

Special optimization for vector embeddings:

• extra_a: List size (elements per list)
• extra_b: Total child buffer length in bytes
• Payload: Contiguous child Float32 buffer

This enables direct SIMD access to embedding vectors without indirection.

Struct Layout

For nested composite types:

• extra_a: Unused (0)
• extra_b: IPC payload length in bytes
• Payload: Arrow IPC-serialized struct array

Struct types fall back to Arrow IPC format because their complex nested structure doesn't benefit from the custom layout.

Sources: llkv-storage/src/serialization.rs:44-135 llkv-storage/src/serialization.rs:256-378

graph TB
    PAGER["Pager::batch_get"]
HANDLE["EntryHandle\nmemory-mapped region"]
BUFFER["Arrow Buffer\nslice of EntryHandle"]
ARRAYDATA["ArrayData\nreferences Buffer"]
ARRAY["Concrete Array\nInt32Array, etc."]
PAGER --> HANDLE
 
   HANDLE --> BUFFER
 
   BUFFER --> ARRAYDATA
 
   ARRAYDATA --> ARRAY
    
    style HANDLE fill:#f9f9f9
    style BUFFER fill:#f9f9f9

Zero-Copy Deserialization

EntryHandle Integration

The EntryHandle type from simd-r-drive-entry-handle provides a zero-copy wrapper around memory-mapped buffers:

Key Operations:

1. Pager read : Returns GetResult::Raw { key, bytes: EntryHandle }
2. Buffer slice : EntryHandle::as_arrow_buffer() creates an Arrow Buffer view
3. ArrayData build : ArrayData::builder().add_buffer(buffer).build()
4. Array cast : make_array(data) produces typed arrays

The entire chain avoids copying data — Arrow arrays directly reference the memory-mapped region.

Alignment Requirements:

Decimal128 requires 16-byte alignment. If the EntryHandle buffer is not properly aligned, the deserializer copies it to an aligned buffer:

Sources: llkv-storage/src/serialization.rs:429-559 llkv-column-map/src/store/projection.rs:619-629

graph TB
    ROWIDS["row_ids: &[u64]\nrequested rows"]
FIELDIDS["field_ids: &[LogicalFieldId]\nrequested columns"]
PLANS["FieldPlan\nper-column metadata"]
CHUNKS["Chunk selection\ncandidate_indices"]
BATCH_GET["Pager::batch_get\nfetch chunks"]
CACHE["Chunk cache\nArrayRef map"]
GATHER["gather_rows_from_chunks\nper-type specialization"]
ARRAYS["Vec<ArrayRef>\none per field"]
SCHEMA["Arrow Schema\nField metadata"]
RECORDBATCH["RecordBatch::try_new"]
ROWIDS --> PLANS
 
   FIELDIDS --> PLANS
 
   PLANS --> CHUNKS
 
   CHUNKS --> BATCH_GET
 
   BATCH_GET --> CACHE
 
   CACHE --> GATHER
 
   GATHER --> ARRAYS
 
   ARRAYS --> RECORDBATCH
 
   SCHEMA --> RECORDBATCH

RecordBatch Construction and Projection

Gather Operations

The ColumnStore::gather_rows family of methods reconstructs RecordBatch from chunked columns:

Projection Flow:

1. Prepare context : Load column descriptors, determine chunk candidates
2. Batch fetch : Request all needed chunks from pager in one call
3. Type-specific gather : Dispatch to specialized routines based on DataType
4. Null policy : Apply GatherNullPolicy (ErrorOnMissing, IncludeNulls, DropNulls)
5. Schema construction : Build Schema with correct field names and nullability
6. RecordBatch assembly : RecordBatch::try_new(schema, arrays)

Type Dispatch Table:

Sources: llkv-column-map/src/store/projection.rs:245-446 llkv-column-map/src/store/projection.rs:636-726

graph TB
    BATCH["RecordBatch\nuser data"]
TABLE_SCHEMA["Stored Schema\nfrom catalog"]
VALIDATE["Schema validation"]
FIELD_CHECK["Field count\nname\ntype match"]
MVCC["Inject MVCC columns\nrow_id, created_by,\ndeleted_by"]
EXTENDED["Extended RecordBatch"]
COLMAP["ColumnStore::append"]
BATCH --> VALIDATE
 
   TABLE_SCHEMA --> VALIDATE
 
   VALIDATE --> FIELD_CHECK
 
   FIELD_CHECK -->|Pass| MVCC
 
   FIELD_CHECK -->|Fail| ERROR["Error::SchemaMismatch"]
MVCC --> EXTENDED
 
   EXTENDED --> COLMAP

Schema Validation

Table-Level Schema Enforcement

The Table layer validates incoming RecordBatch schemas against the stored table schema before appending:

Validation Rules:

1. Field count : Batch must have exactly the same number of columns as the table schema
2. Field names : Column names must match (case-sensitive)
3. Field types : DataType must match exactly (no implicit coercion)
4. Nullability : Currently not strictly enforced (planned improvement)

MVCC Column Injection:

After validation, the table appends three system columns:

• row_id (UInt64): Unique row identifier
• created_by (UInt64): Transaction ID that created the row
• deleted_by (UInt64): Transaction ID that deleted the row (0 if active)

These columns are stored in separate logical namespaces but physically alongside user data.

Sources: llkv-table/README.md:14-17 llkv-column-map/README.md:26-28

graph LR
    SQL_LITERAL["SQL Literal\n123, 'text', etc."]
LITERAL["Literal enum\nInteger, String, etc."]
SCHEMA["Table Schema\nArrow DataType"]
NATIVE["Native Value\ni32, String, etc."]
ARRAY["Arrow Array\nInt32Array, etc."]
SQL_LITERAL --> LITERAL
 
   LITERAL --> SCHEMA
 
   SCHEMA --> NATIVE
 
   NATIVE --> ARRAY

Type Mapping from SQL to Arrow

Literal Conversion

The llkv-expr crate defines a Literal enum that captures untyped SQL values before schema resolution:

Supported Literal Types:

Conversion Mechanism:

The FromLiteral trait provides type-aware conversion:

Implementations perform range checking and type validation:

Sources: llkv-expr/src/literal.rs:78-94 llkv-expr/src/literal.rs:156-219 llkv-expr/src/literal.rs:395-419

Performance Characteristics

Zero-Copy Benefits

The combination of Arrow's columnar layout and the custom serialization format delivers measurable performance benefits:

Chunking Strategy

The ColumnStore organizes data into chunks sized for cache locality and pager efficiency:

• Target chunk size : Configurable, typically 64KB-256KB per column
• Row alignment : All columns in a table share the same row boundaries per chunk
• Append optimization : Incoming batches are chunked and sorted by row_id before persistence

This design minimizes pager I/O and maximizes CPU cache hit rates during scans.

Sources: llkv-column-map/README.md:24-28 llkv-storage/README.md:15-17

Integration with External Tools

Arrow Compatibility

Because LLKV uses standard Arrow data structures at its boundaries, it can integrate with the broader Arrow ecosystem:

• Export : Query results can be serialized to Arrow IPC files for external processing
• Import : Arrow IPC files can be read and ingested via Table::append
• Parquet : Future work could add direct Parquet read/write using Arrow's parquet crate
• DataFusion : LLKV's table scan APIs could potentially integrate as a DataFusion TableProvider

Current Limitations

1. Null support : The serialization format doesn't yet handle null bitmaps
2. Nested types : Only Struct and FixedSizeList<Float32> are fully supported
3. Dictionary encoding : Not yet implemented (planned)
4. Compression : No built-in compression (relies on storage-layer features)

Sources: llkv-storage/src/serialization.rs:257-260 llkv-column-map/README.md:10-11

Summary

LLKV's Arrow-native architecture provides:

• Universal interchange format via RecordBatch across all layers
• Zero-copy operations through EntryHandle and memory-mapped buffers
• Custom serialization optimized for mmap and SIMD access patterns
• Type safety from SQL literals through to persisted columns
• SIMD-friendly layout for efficient vectorized query evaluation

The trade-off of using a custom format instead of Arrow IPC is reduced flexibility (no nulls yet, fewer complex types) in exchange for smaller files, faster scans, and true zero-copy deserialization.

For details on how Arrow arrays are evaluated during query execution, see Scalar Evaluation and NumericKernels. For information on how MVCC metadata is stored alongside Arrow columns, see Column Storage and ColumnStore.

SQL Interface

Relevant source files

• README.md
• demos/llkv-sql-pong-demo/src/main.rs
• llkv-aggregate/src/lib.rs
• llkv-sql/src/lib.rs
• llkv-sql/src/sql_engine.rs
• llkv-sql/src/sql_value.rs
• llkv-sql/src/tpch.rs
• llkv-tpch/.gitignore
• llkv-tpch/Cargo.toml
• llkv-tpch/DRAFT-PRE-FINAL.md

The SQL Interface layer provides the primary user-facing entry point for executing SQL statements against LLKV. It consists of the llkv-sql crate, which wraps the underlying runtime and provides SQL parsing, preprocessing, statement caching, and result formatting.

This document covers the SqlEngine struct and its methods, SQL preprocessing and dialect normalization, and the INSERT buffering optimization system. For information about query planning after SQL parsing, see Query Planning. For runtime execution, see the Architecture section at #2.

Sources: llkv-sql/src/lib.rs:1-51 README.md:47-48

Core Components

The SQL Interface layer is centered around three main subsystems:

Sources: llkv-sql/src/sql_engine.rs:365-556

SqlEngine Structure

The SqlEngine wraps a RuntimeEngine instance and adds SQL-specific functionality including statement caching, INSERT buffering, and configurable behavior flags. The insert_buffer field holds accumulated literal INSERT payloads when buffering is enabled.

Sources: llkv-sql/src/sql_engine.rs:496-509 llkv-sql/src/sql_engine.rs:421-471

SQL Statement Processing Flow

The statement processing flow consists of:

1. Preprocessing: SQL text undergoes dialect normalization via regex-based transformations
2. Parsing: sqlparser with increased recursion limit (200 vs default 50) produces AST
3. Planning: AST nodes are translated to typed PlanStatement structures
4. Buffering (INSERT only): Literal INSERT statements may be accumulated in InsertBuffer
5. Execution: Plans are passed to RuntimeEngine for execution
6. Result collection: RuntimeStatementResult instances are collected and returned

Sources: llkv-sql/src/sql_engine.rs:933-991 llkv-sql/src/sql_engine.rs:318-324

Public API Methods

Core Execution Methods

The SqlEngine exposes two primary execution methods:

The execute method handles arbitrary SQL (DDL, DML, queries) and returns statement results. The sql method is a convenience wrapper that enforces single-SELECT semantics and extracts Arrow batches from the result stream.

Sources: llkv-sql/src/sql_engine.rs:921-991 llkv-sql/src/sql_engine.rs:1009-1052

Prepared Statements

Prepared statements support three placeholder syntaxes:

• Positional: ? (auto-numbered), ?1, $1 (explicit index)
• Named: :param_name

Placeholders are tracked via thread-local ParameterState during parsing, converted to sentinel strings like __llkv_param__1__, and stored in a PreparedPlan with parameter count metadata. The statement_cache field provides a statement-level cache keyed by SQL text.

Sources: llkv-sql/src/sql_engine.rs:77-206 llkv-sql/src/sql_engine.rs:278-297

Configuration Methods

The set_insert_buffering method controls cross-statement INSERT accumulation. When disabled (default), each INSERT executes immediately. When enabled, compatible INSERTs targeting the same table are batched together up to MAX_BUFFERED_INSERT_ROWS (8192 rows).

Sources: llkv-sql/src/sql_engine.rs:615-621 llkv-sql/src/sql_engine.rs:879-905 llkv-sql/src/sql_engine.rs:410-414

SQL Preprocessing System

The preprocessing layer normalizes SQL dialects before parsing to handle incompatibilities between SQLite, DuckDB, and sqlparser expectations.

graph TB
    RAW["Raw SQL String"]
TPCH["preprocess_tpch_connect_syntax\n(strip CONNECT TO statements)"]
TYPE["preprocess_create_type_syntax\n(CREATE TYPE → CREATE DOMAIN)"]
EXCLUDE["preprocess_exclude_syntax\n(quote qualified names in EXCLUDE)"]
COMMA["preprocess_trailing_commas_in_values\n(remove trailing commas)"]
EMPTY["preprocess_empty_in_lists\n(expr IN () → constant)"]
INDEX["preprocess_index_hints\n(strip INDEXED BY / NOT INDEXED)"]
REINDEX["preprocess_reindex_syntax\n(REINDEX → VACUUM REINDEX)"]
BARE["preprocess_bare_table_in_clauses\n(IN table → IN (SELECT * FROM))"]
TRIGGER["preprocess_sqlite_trigger_shorthand\n(add AFTER / FOR EACH ROW)"]
PARSER["sqlparser::Parser"]
RAW --> TPCH
 
   TPCH --> TYPE
 
   TYPE --> EXCLUDE
 
   EXCLUDE --> COMMA
 
   COMMA --> EMPTY
 
   EMPTY --> INDEX
 
   INDEX --> REINDEX
 
   REINDEX --> BARE
 
   BARE --> PARSER
    
    PARSER -.parse error.-> TRIGGER
 
   TRIGGER --> PARSER

Each preprocessing function is implemented as a regex-based transformer:

The trigger preprocessor is only invoked on parse errors containing CREATE TRIGGER, as it requires more complex regex patterns to inject missing timing and row-level clauses.

Sources: llkv-sql/src/sql_engine.rs:623-873

Regex Pattern Details

Static OnceLock<Regex> instances cache compiled patterns across invocations:

For example, the empty IN list handler uses:

(?i)(\([^)]*\)|x'[0-9a-fA-F]*'|'(?:[^']|'')*'|[a-zA-Z_][a-zA-Z0-9_]*(?:\.[a-zA-Z_][a-zA-Z0-9_]*)*|\d+(?:\.\d+)?)\s+(NOT\s+)?IN\s*\(\s*\)

This matches expressions (parenthesized, hex literals, strings, identifiers, numbers) followed by [NOT] IN () and replaces with boolean expressions that preserve evaluation side effects while producing constant results.

Sources: llkv-sql/src/sql_engine.rs:691-720

Parameter Placeholder System

The parameter system uses thread-local state to track placeholders during statement preparation:

1. Scope Creation: ParameterScope::new() initializes thread-local ParameterState
2. Registration: Each placeholder calls register_placeholder(raw) which:
   • For ?: auto-increments index
   • For ?N or $N: uses explicit numeric index
   • For :name: assigns next available index and stores mapping
3. Sentinel Generation: placeholder_marker(index) creates __llkv_param__N__ string
4. Parsing: Sentinel strings are parsed as string literals in the SQL AST
5. Binding: execute_prepared replaces sentinels with SqlParamValue instances

The ParameterState struct tracks:

• assigned: FxHashMap<String, usize> - named parameter to index mapping
• next_auto: usize - next index for ? placeholders
• max_index: usize - highest parameter index seen

Sources: llkv-sql/src/sql_engine.rs:77-206 llkv-sql/src/sql_engine.rs:1120-1235

graph TB
    subgraph "INSERT Processing Decision"
        INSERT["Statement::Insert"]
CLASSIFY["classify_insert"]
VALUES["PreparedInsert::Values"]
IMMEDIATE["PreparedInsert::Immediate"]
end
    
    subgraph "Buffering Logic"
        ENABLED{"Buffering\nEnabled?"}
COMPAT{"Can Buffer\nAccept?"}
THRESHOLD{">= MAX_BUFFERED_INSERT_ROWS\n(8192)?"}
BUFFER["InsertBuffer::push_statement"]
FLUSH["flush_buffered_insert"]
EXECUTE["execute_plan_statement"]
end
    
 
   INSERT --> CLASSIFY
 
   CLASSIFY --> VALUES
 
   CLASSIFY --> IMMEDIATE
    
 
   VALUES --> ENABLED
 
   ENABLED -->|No| EXECUTE
 
   ENABLED -->|Yes| COMPAT
    
 
   COMPAT -->|No| FLUSH
 
   COMPAT -->|Yes| BUFFER
 
   FLUSH --> BUFFER
    
 
   BUFFER --> THRESHOLD
 
   THRESHOLD -->|Yes| FLUSH
 
   THRESHOLD -->|No| RETURN["Return placeholder result"]
IMMEDIATE --> EXECUTE

INSERT Buffering System

The INSERT buffering system batches compatible literal INSERT statements to reduce planning overhead for bulk ingest workloads.

Buffer Structure

The InsertBuffer struct accumulates rows across multiple INSERT statements:

Key fields:

• table_name, columns, on_conflict: compatibility key for buffering
• rows: accumulated literal values from all buffered statements
• statement_row_counts: per-statement row counts to emit individual results
• total_rows: sum of statement_row_counts for threshold checking

Sources: llkv-sql/src/sql_engine.rs:421-471

Buffering Conditions

An INSERT can be buffered if:

1. The InsertSource is Values (literal rows) or a constant SELECT
2. Buffering is enabled via insert_buffering_enabled flag
3. Either no buffer exists or InsertBuffer::can_accept returns true:
   • table_name matches exactly
   • columns match exactly (same names, same order)
   • on_conflict action matches

When the buffer reaches MAX_BUFFERED_INSERT_ROWS (8192), it is flushed automatically. Flush also occurs on:

• Transaction boundaries (BEGIN, COMMIT, ROLLBACK)
• Incompatible INSERT statement
• Engine drop
• Explicit set_insert_buffering(false) call

Sources: llkv-sql/src/sql_engine.rs:452-470 llkv-sql/src/sql_engine.rs:2028-2146 llkv-sql/src/sql_engine.rs:410-414

Buffer Flush Process

The flush process:

1. Extracts InsertBuffer from RefCell<Option<InsertBuffer>>
2. Constructs single InsertPlan with all accumulated rows
3. Executes via execute_statement
4. Receives single RuntimeStatementResult::Insert with total rows inserted
5. Splits result into per-statement results using statement_row_counts vector
6. Returns vector of results matching original statement order

This allows bulk execution while preserving per-statement result semantics.

Sources: llkv-sql/src/sql_engine.rs:2028-2146

Value Handling

The SqlValue enum represents literal values during SQL processing:

The SqlValue::try_from_expr function handles:

• Unary operators (negation for numeric types, intervals)
• CAST expressions (particularly to DATE)
• Nested expressions
• Dictionary/struct literals
• Binary operations (addition, subtraction, bitshift for constant folding)
• Typed strings (DATE '2024-01-01')

Interval arithmetic is performed at constant-folding time:

• Date32 + Interval → Date32
• Interval + Date32 → Date32
• Date32 - Interval → Date32
• Date32 - Date32 → Interval
• Interval +/- Interval → Interval

Sources: llkv-sql/src/sql_value.rs:16-320

Error Handling

The SQL layer maps table-related errors to catalog-specific error messages:

The execute_plan_statement method applies error mapping except for CREATE VIEW and DROP VIEW statements, where the "table" name refers to the view being created/dropped rather than a referenced table.

Sources: llkv-sql/src/sql_engine.rs:558-609 llkv-sql/src/sql_engine.rs511

Thread Safety and Cloning

The SqlEngine::clone implementation creates a new session:

This ensures each cloned engine has an independent:

• RuntimeSession (transaction state, temporary namespace)
• insert_buffer (no shared buffering across sessions)
• statement_cache (independent prepared statement cache)

The warning message indicates this is typically not intended usage, as most applications should use a single shared SqlEngine instance across threads (enabled by interior mutability via RefCell and atomic types).

Sources: llkv-sql/src/sql_engine.rs:522-540

SqlEngine API

Relevant source files

• llkv-aggregate/src/lib.rs
• llkv-executor/README.md
• llkv-plan/README.md
• llkv-sql/README.md
• llkv-sql/src/lib.rs
• llkv-sql/src/sql_engine.rs
• llkv-sql/src/sql_value.rs

Purpose and Scope

The SqlEngine provides the primary user-facing API for executing SQL statements against LLKV databases. It accepts SQL text, parses it, translates it to typed execution plans, and delegates to the runtime layer for evaluation. This page documents the SqlEngine struct's construction, methods, prepared statement handling, and configuration options.

For information about SQL preprocessing and dialect handling, see SQL Preprocessing and Dialect Handling. For details on INSERT buffering behavior, see INSERT Buffering System. For query planning internals, see Plan Structures.

Sources: llkv-sql/src/lib.rs:1-51 llkv-sql/README.md:1-68

SqlEngine Architecture Overview

The SqlEngine sits at the top of the LLKV SQL processing stack, coordinating parsing, planning, and execution:

Diagram: SqlEngine Position in SQL Processing Stack

graph TB
    User["User Code"]
SqlEngine["SqlEngine\n(llkv-sql)"]
Parser["sqlparser\nAST Generation"]
Preprocessor["SQL Preprocessor\nDialect Normalization"]
Planner["Plan Translation\nAST → PlanStatement"]
Runtime["RuntimeEngine\n(llkv-runtime)"]
Executor["llkv-executor\nQuery Execution"]
Table["llkv-table\nTable Layer"]
User -->|execute sql| SqlEngine
 
   User -->|sql select| SqlEngine
 
   User -->|prepare sql| SqlEngine
    
 
   SqlEngine --> Preprocessor
 
   Preprocessor --> Parser
 
   Parser --> Planner
 
   Planner --> Runtime
 
   Runtime --> Executor
 
   Executor --> Table
    
 
   SqlEngine -.->|owns| Runtime
 
   SqlEngine -.->|manages| InsertBuffer["InsertBuffer\nBatching State"]
SqlEngine -.->|caches| StmtCache["statement_cache\nPreparedPlan Cache"]

The SqlEngine wraps a RuntimeEngine, manages statement caching and INSERT buffering, and provides convenience methods for single-statement queries (sql()) and multi-statement execution (execute()).

Sources: llkv-sql/src/sql_engine.rs:496-509 llkv-sql/src/lib.rs:1-51

Constructing a SqlEngine

Basic Construction

Diagram: SqlEngine Construction Flow

The most common constructor is SqlEngine::new(), which accepts a pager and creates a new runtime context:

Sources: llkv-sql/src/sql_engine.rs:615-621

Table: SqlEngine Constructor Methods

Sources: llkv-sql/src/sql_engine.rs:543-556 llkv-sql/src/sql_engine.rs:615-621 llkv-sql/src/sql_engine.rs:879-885

Core Query Execution Methods

execute() - Multi-Statement Execution

The execute() method processes one or more SQL statements from a string and returns a vector of results:

Diagram: execute() Method Execution Flow

The execution pipeline:

1. Preprocessing : SQL text undergoes dialect normalization via preprocess_sql_input() llkv-sql/src/sql_engine.rs:1556-1564
2. Parsing : sqlparser converts normalized text to AST with recursion limit of 200 llkv-sql/src/sql_engine.rs324
3. Statement Loop : Each statement is translated to a PlanStatement and either buffered (for INSERTs) or executed immediately
4. Result Collection : Results are accumulated and returned as Vec<SqlStatementResult>

Sources: llkv-sql/src/sql_engine.rs:933-1044

sql() - Single SELECT Execution

The sql() method enforces single-statement SELECT semantics and returns Arrow RecordBatch results:

Key differences from execute():

• Accepts only a single statement
• Statement must be a SELECT query
• Returns Vec<RecordBatch> directly rather than RuntimeStatementResult
• Automatically collects streaming results

Sources: llkv-sql/src/sql_engine.rs:1046-1085

Prepared Statements

Prepared Statement Flow

Diagram: Prepared Statement Creation and Caching

prepare() Method

The prepare() method parses SQL with placeholders and caches the resulting plan:

Placeholder syntax supported:

• ? - Positional parameter (auto-increments)
• ?N - Numbered parameter (1-indexed)
• $N - PostgreSQL-style numbered parameter
• :name - Named parameter

Sources: llkv-sql/src/sql_engine.rs:1296-1376 llkv-sql/src/sql_engine.rs:86-132

Parameter Binding Mechanism

Parameter registration occurs via thread-local ParameterScope:

Diagram: Parameter Registration and Sentinel Generation

The parameter translation process:

1. During parsing, placeholders are intercepted and converted to sentinel strings: __llkv_param__N__
2. ParameterState tracks placeholder-to-index mappings in thread-local storage
3. At execution time, sentinel strings are replaced with actual parameter values

Sources: llkv-sql/src/sql_engine.rs:71-206

SqlParamValue Type

Parameter values are represented by the SqlParamValue enum:

Table: SqlParamValue Variants and Conversions

Sources: llkv-sql/src/sql_engine.rs:208-276

execute_prepared() Method

Execute a prepared statement with bound parameters:

Parameter substitution occurs in two phases:

1. Literal Substitution : Sentinels in Expr<String> are replaced via substitute_parameter_literals() llkv-sql/src/sql_engine.rs:1453-1497
2. Plan Value Substitution : Sentinels in Vec<PlanValue> are replaced via substitute_parameter_plan_values() llkv-sql/src/sql_engine.rs:1499-1517

Sources: llkv-sql/src/sql_engine.rs:1378-1451

Transaction Control

The SqlEngine supports explicit transaction boundaries via SQL statements:

Diagram: Transaction State Machine

Transaction management methods:

Transaction boundaries automatically flush the INSERT buffer to ensure consistent visibility semantics.

Sources: llkv-sql/src/sql_engine.rs:970-990 llkv-sql/src/sql_engine.rs:912-914

INSERT Buffering System

Buffer Architecture

Diagram: INSERT Buffer Accumulation and Flush

InsertBuffer Structure

The InsertBuffer struct accumulates literal INSERT payloads:

Sources: llkv-sql/src/sql_engine.rs:421-471

Buffer Compatibility

An INSERT can join the buffer if it matches:

1. Table Name : Target table must match buffer.table_name
2. Column List : Columns must match buffer.columns exactly
3. Conflict Action : on_conflict strategy must match

Sources: llkv-sql/src/sql_engine.rs:452-459

Flush Conditions

The buffer flushes when:

Table: INSERT Buffer Flush Triggers

Enabling/Disabling Buffering

INSERT buffering is controlled by the set_insert_buffering() method:

• Disabled by default to maintain statement-level transaction semantics
• Enable for bulk loading to reduce planning overhead
• Disabling flushes buffer to ensure pending rows are persisted

Sources: llkv-sql/src/sql_engine.rs:898-905

classDiagram
    class RuntimeStatementResult {<<enum>>\nSelect\nInsert\nUpdate\nDelete\nCreateTable\nDropTable\nCreateIndex\nDropIndex\nAlterTable\nCreateView\nDropView\nVacuum\nTransaction}
    
    class SelectVariant {+SelectExecution execution}
    
    class InsertVariant {+table_name: String\n+rows_inserted: usize}
    
    class UpdateVariant {+table_name: String\n+rows_updated: usize}
    
    RuntimeStatementResult --> SelectVariant
    RuntimeStatementResult --> InsertVariant
    RuntimeStatementResult --> UpdateVariant

Result Types

RuntimeStatementResult

The execute() and execute_prepared() methods return Vec<RuntimeStatementResult>:

Diagram: RuntimeStatementResult Variants

Key result variants:

Table: Common RuntimeStatementResult Variants

Sources: llkv-sql/src/lib.rs49

SelectExecution

SELECT queries return a SelectExecution handle for streaming results:

The sql() method automatically collects batches via execution.collect():

Sources: llkv-sql/src/sql_engine.rs:1065-1080

Configuration Methods

session() - Access Runtime Session

Provides access to the underlying RuntimeSession for transaction introspection or advanced error handling.

Sources: llkv-sql/src/sql_engine.rs:917-919

context_arc() - Access Runtime Context

Internal method to retrieve the shared RuntimeContext for engine composition.

Sources: llkv-sql/src/sql_engine.rs:875-877

Testing Utilities

StatementExpectation

Test harnesses can register expectations to control buffer flushing:

When a statement expectation is registered, the INSERT buffer flushes before executing that statement to ensure test assertions observe correct row counts.

Sources: llkv-sql/src/sql_engine.rs:64-315

Example Usage

Sources: llkv-sql/src/sql_engine.rs:299-309

Thread Safety and Cloning

The SqlEngine implements Clone with special semantics:

Warning : Cloning a SqlEngine creates a new RuntimeSession, not a shared reference. Each clone has independent transaction state and INSERT buffers.

Sources: llkv-sql/src/sql_engine.rs:522-540

Error Handling

Table Not Found Errors

The SqlEngine remaps generic errors to user-friendly catalog errors:

This converts low-level NotFound errors into: Catalog Error: Table 'tablename' does not exist

Sources: llkv-sql/src/sql_engine.rs:558-585

SQL Preprocessing and Dialect Handling

Relevant source files

• llkv-sql/Cargo.toml
• llkv-sql/src/sql_engine.rs
• llkv-test-utils/README.md

Purpose and Scope

SQL preprocessing is the first stage in LLKV's query processing pipeline, responsible for normalizing SQL syntax from various dialects before the statement reaches the parser. This system allows LLKV to accept SQL written for SQLite, DuckDB, and TPC-H tooling while using the standard sqlparser library, which has limited dialect support.

The preprocessing layer transforms dialect-specific syntax into forms that sqlparser can parse, enabling compatibility with SQL Logic Tests and real-world SQL scripts without modifying the parser itself. This page documents the preprocessing transformations and their implementation.

For information about what happens after preprocessing (SQL parsing and plan generation), see SQL Query Processing Pipeline. For details on the SqlEngine API that invokes preprocessing, see SqlEngine API.

Preprocessing in the Query Pipeline

SQL preprocessing occurs immediately before parsing in both the execute and prepare code paths. The following diagram shows where preprocessing fits in the overall query execution flow:

Diagram: SQL Preprocessing Pipeline Position

flowchart TB
    Input["SQL String Input"]
Preprocess["preprocess_sql_input()"]
Parse["sqlparser::Parser::parse()"]
Plan["Plan Generation"]
Execute["Query Execution"]
Input --> Preprocess
 
   Preprocess --> Parse
 
   Parse --> Plan
 
   Plan --> Execute
    
    subgraph "Preprocessing Transformations"
        direction TB
        TPC["TPC-H CONNECT removal"]
CreateType["CREATE TYPE → CREATE DOMAIN"]
Exclude["EXCLUDE syntax normalization"]
Trailing["Trailing comma removal"]
EmptyIn["Empty IN list handling"]
IndexHints["Index hint stripping"]
Reindex["REINDEX → VACUUM REINDEX"]
BareTable["Bare table IN expansion"]
TPC --> CreateType
 
       CreateType --> Exclude
 
       Exclude --> Trailing
 
       Trailing --> BareTable
 
       BareTable --> EmptyIn
 
       EmptyIn --> IndexHints
 
       IndexHints --> Reindex
    end
    
    Preprocess -.chains.-> TPC
    Reindex -.final.-> Parse

Sources: llkv-sql/src/sql_engine.rs:936-1001

The preprocess_sql_input method chains all dialect transformations in a specific order, with each transformation receiving the output of the previous one. If parsing fails after preprocessing and the SQL contains CREATE TRIGGER, a fallback preprocessor (preprocess_sqlite_trigger_shorthand) is applied before retrying the parse.

Diagram: Preprocessing Execution Sequence with Fallback

sequenceDiagram
    participant Caller
    participant SqlEngine
    participant Preprocess as "preprocess_sql_input"
    participant Parser as "sqlparser"
    participant Fallback as "preprocess_sqlite_trigger_shorthand"
    
    Caller->>SqlEngine: execute(sql)
    SqlEngine->>Preprocess: preprocess(sql)
    
    Note over Preprocess: Chain all transformations
    
    Preprocess-->>SqlEngine: processed_sql
    SqlEngine->>Parser: parse(processed_sql)
    
    alt Parse Success
        Parser-->>SqlEngine: AST
    else Parse Error + "CREATE TRIGGER"
        Parser-->>SqlEngine: ParseError
        SqlEngine->>Fallback: expand_trigger_syntax(processed_sql)
        Fallback-->>SqlEngine: expanded_sql
        SqlEngine->>Parser: parse(expanded_sql)
        Parser-->>SqlEngine: AST or Error
    end
    
    SqlEngine-->>Caller: Results

Sources: llkv-sql/src/sql_engine.rs:936-958

Supported Dialect Transformations

LLKV implements nine distinct preprocessing transformations, each targeting specific dialect compatibility issues. The following table summarizes each transformation:

Sources: llkv-sql/src/sql_engine.rs:628-842 llkv-sql/src/sql_engine.rs:992-1001

TPC-H CONNECT Statement Removal

The TPC-H benchmark tooling generates CONNECT TO <database>; directives in referential integrity scripts. Since LLKV operates within a single database context, these statements are treated as no-ops and stripped during preprocessing.

Transformation:

Sources: llkv-sql/src/sql_engine.rs:623-630

CREATE TYPE to CREATE DOMAIN Conversion

DuckDB uses CREATE TYPE name AS basetype for type aliases, but sqlparser only supports the SQL standard CREATE DOMAIN syntax. This preprocessor converts the DuckDB syntax to the standard form.

Transformation:

Implementation: Uses static regex patterns initialized via OnceLock for thread-safe lazy compilation.

Sources: llkv-sql/src/sql_engine.rs:634-657

EXCLUDE Syntax Normalization

When EXCLUDE clauses contain qualified identifiers (e.g., schema.table.column), sqlparser requires them to be quoted. This preprocessor wraps qualified names in double quotes.

Transformation:

Sources: llkv-sql/src/sql_engine.rs:659-676

Trailing Comma Removal in VALUES

DuckDB permits trailing commas in VALUES clauses like VALUES ('v2',), but sqlparser rejects them. This preprocessor removes trailing commas before closing parentheses.

Transformation:

Sources: llkv-sql/src/sql_engine.rs:678-689

Empty IN List Handling

SQLite allows degenerate IN () and NOT IN () expressions. Since sqlparser rejects these, the preprocessor converts them to constant boolean expressions while preserving the original expression evaluation (in case of side effects).

Transformation:

The pattern matches various expression forms: parenthesized expressions, quoted strings, hex literals, identifiers, and numbers.

Sources: llkv-sql/src/sql_engine.rs:691-720

Index Hint Stripping

SQLite supports query optimizer hints like FROM table INDEXED BY index_name and FROM table NOT INDEXED. Since sqlparser doesn't support this syntax and LLKV makes its own index decisions, these hints are stripped during preprocessing.

Transformation:

Sources: llkv-sql/src/sql_engine.rs:722-739

REINDEX to VACUUM REINDEX Conversion

SQLite supports REINDEX index_name as a standalone statement, but sqlparser only recognizes REINDEX as part of VACUUM syntax. This preprocessor converts the standalone form.

Transformation:

Sources: llkv-sql/src/sql_engine.rs:741-757

Bare Table IN Clause Expansion

SQLite allows expr IN tablename as shorthand for expr IN (SELECT * FROM tablename). The preprocessor expands this shorthand to the subquery form that sqlparser requires.

Transformation:

The pattern avoids matching IN ( which is already a valid subquery.

Sources: llkv-sql/src/sql_engine.rs:844-873

SQLite Trigger Shorthand Expansion

SQLite allows omitting the trigger timing (defaults to AFTER) and the FOR EACH ROW clause (defaults to row-level triggers). sqlparser requires both to be explicit. This preprocessor injects the missing clauses.

Transformation:

This is a fallback preprocessor that only runs if initial parsing fails and the SQL contains CREATE TRIGGER. The implementation uses complex regex patterns to handle optional dotted identifiers with various quoting styles.

Sources: llkv-sql/src/sql_engine.rs:759-842 llkv-sql/src/sql_engine.rs:944-957

graph TB
    subgraph "SqlEngine Methods"
        Execute["execute(sql)"]
Prepare["prepare(sql)"]
PreprocessInput["preprocess_sql_input(sql)"]
end
    
    subgraph "Static Regex Patterns"
        CreateTypeRE["CREATE_TYPE_REGEX"]
DropTypeRE["DROP_TYPE_REGEX"]
ExcludeRE["EXCLUDE_REGEX"]
TrailingRE["TRAILING_COMMA_REGEX"]
EmptyInRE["EMPTY_IN_REGEX"]
IndexHintRE["INDEX_HINT_REGEX"]
ReindexRE["REINDEX_REGEX"]
BareTableRE["BARE_TABLE_IN_REGEX"]
TimingRE["TIMING_REGEX"]
ForEachBeginRE["FOR_EACH_BEGIN_REGEX"]
ForEachWhenRE["FOR_EACH_WHEN_REGEX"]
end
    
    subgraph "Preprocessor Methods"
        TPC["preprocess_tpch_connect_syntax"]
CreateType["preprocess_create_type_syntax"]
Exclude["preprocess_exclude_syntax"]
Trailing["preprocess_trailing_commas_in_values"]
EmptyIn["preprocess_empty_in_lists"]
IndexHints["preprocess_index_hints"]
Reindex["preprocess_reindex_syntax"]
BareTable["preprocess_bare_table_in_clauses"]
Trigger["preprocess_sqlite_trigger_shorthand"]
end
    
 
   Execute --> PreprocessInput
 
   Prepare --> PreprocessInput
    
 
   PreprocessInput --> TPC
 
   PreprocessInput --> CreateType
 
   PreprocessInput --> Exclude
 
   PreprocessInput --> Trailing
 
   PreprocessInput --> BareTable
 
   PreprocessInput --> EmptyIn
 
   PreprocessInput --> IndexHints
 
   PreprocessInput --> Reindex
    
    CreateType -.uses.-> CreateTypeRE
    CreateType -.uses.-> DropTypeRE
    Exclude -.uses.-> ExcludeRE
    Trailing -.uses.-> TrailingRE
    EmptyIn -.uses.-> EmptyInRE
    IndexHints -.uses.-> IndexHintRE
    Reindex -.uses.-> ReindexRE
    BareTable -.uses.-> BareTableRE
    Trigger -.uses.-> TimingRE
    Trigger -.uses.-> ForEachBeginRE
    Trigger -.uses.-> ForEachWhenRE

Implementation Architecture

The preprocessing system is implemented using a combination of regex transformations and string manipulation. The following diagram shows the key components:

Diagram: Preprocessing Implementation Components

Sources: llkv-sql/src/sql_engine.rs:640-842 llkv-sql/src/sql_engine.rs:992-1001

Regex Pattern Management

All regex patterns are stored in OnceLock static variables for thread-safe lazy initialization. This ensures patterns are compiled once per process and reused across all preprocessing operations, avoiding the overhead of repeated compilation.

Pattern Initialization Example:

The patterns use case-insensitive matching ((?i)) and word boundaries (\b) to avoid false matches within identifiers or string literals.

Sources: llkv-sql/src/sql_engine.rs:640-650 llkv-sql/src/sql_engine.rs:661-669 llkv-sql/src/sql_engine.rs:682-686

Preprocessing Order

The order of transformations matters because later transformations may depend on earlier ones. The current order:

1. TPC-H CONNECT removal - Must happen first to remove non-SQL directives
2. CREATE TYPE conversion - Normalizes DDL before other transformations
3. EXCLUDE syntax - Handles qualified names in projection lists
4. Trailing comma removal - Fixes VALUES clause syntax
5. Bare table IN expansion - Converts shorthand to subqueries before empty IN check
6. Empty IN handling - Must come after bare table expansion to avoid conflicts
7. Index hint stripping - Removes query hints from FROM clauses
8. REINDEX conversion - Must be last to avoid interfering with VACUUM statements

Sources: llkv-sql/src/sql_engine.rs:992-1001

Parser Integration

The preprocessed SQL is passed to sqlparser with a custom recursion limit to handle deeply nested queries from test suites:

The default sqlparser recursion limit (50) is insufficient for some SQLite test suite queries, so LLKV uses 200 to balance compatibility with stack safety.

Sources: llkv-sql/src/sql_engine.rs:318-324

Testing and Validation

The preprocessing transformations are validated through:

1. SQL Logic Tests (SLT) - The llkv-slt-tester runs thousands of SQLite test cases that exercise various dialect features
2. TPC-H Benchmarks - The llkv-tpch crate verifies compatibility with TPC-H SQL scripts
3. Unit Tests - Individual preprocessor functions are tested in isolation

The preprocessing system is designed to be conservative: it only transforms patterns that are known to cause parser errors, and it preserves the original SQL semantics whenever possible.

Sources: llkv-sql/src/sql_engine.rs:623-1001 llkv-sql/Cargo.toml:1-34

Future Considerations

The preprocessing approach is a pragmatic solution that enables broad dialect compatibility without modifying sqlparser. However, it has limitations:

• Fragile regex patterns - Complex transformations like trigger shorthand expansion use intricate regex that may not handle all edge cases
• Limited context awareness - String-based transformations cannot distinguish between SQL keywords and string literals containing those keywords
• Maintenance burden - Each new dialect feature requires a new preprocessor

The long-term solution is to contribute dialect-specific parsing improvements back to sqlparser, eliminating the need for preprocessing. The trigger shorthand transformation includes a TODO comment noting that proper SQLite dialect support in sqlparser would eliminate that preprocessor entirely.

Sources: llkv-sql/src/sql_engine.rs:765-770

INSERT Buffering System

Relevant source files

• llkv-executor/README.md
• llkv-plan/README.md
• llkv-sql/README.md
• llkv-sql/src/sql_engine.rs

The INSERT Buffering System is an optimization layer within llkv-sql that batches multiple consecutive INSERT ... VALUES statements for the same table into a single execution plan. This dramatically reduces planning overhead when bulk-loading data from SQL scripts containing thousands of individual INSERT statements. The system preserves per-statement result semantics while amortizing the cost of plan construction and table access across large batches.

For information about how INSERT plans are structured and executed, see Plan Structures.

Purpose and Design Goals

The buffering system addresses a specific performance bottleneck: SQL scripts generated by database export tools often contain tens of thousands of individual INSERT INTO table VALUES (...) statements. Without buffering, each statement incurs the full cost of parsing, planning, catalog lookup, and MVCC overhead. The buffer accumulates compatible INSERT statements and flushes them as a single batch, achieving order-of-magnitude throughput improvements for bulk ingestion workloads.

Key design constraints:

• Optional : Disabled by default to preserve immediate visibility semantics for unit tests and interactive workloads
• Transparent : Callers receive per-statement results as if each INSERT executed independently
• Safe : Flushes automatically at transaction boundaries, table changes, and buffer size limits
• Compatible : Integrates with statement expectation mechanisms used by the SQL Logic Test harness

Sources: llkv-sql/src/sql_engine.rs:410-520

Architecture Overview

Figure 1: INSERT Buffering Architecture

The system operates as a stateful accumulator within SqlEngine. Incoming INSERT statements are classified as either PreparedInsert::Values (bufferable literals) or PreparedInsert::Immediate (non-bufferable subqueries or expressions). Compatible VALUES inserts accumulate in the buffer until a flush trigger fires, at which point the buffer constructs a single InsertPlan and emits individual RuntimeStatementResult::Insert entries for each original statement.

Sources: llkv-sql/src/sql_engine.rs:416-509

Buffer Data Structures

InsertBuffer

Figure 2: Buffer Data Structure

The InsertBuffer struct maintains five critical pieces of state:

The statement_row_counts vector preserves the boundary between original INSERT statements so that flush_buffer_results() can emit one RuntimeStatementResult::Insert per statement with the correct row count.

Sources: llkv-sql/src/sql_engine.rs:421-471

PreparedInsert Classification

Figure 3: INSERT Classification Flow

The prepare_insert() method analyzes each INSERT statement and returns PreparedInsert::Values only when the source is a literal VALUES clause or a SELECT that evaluates to constants (e.g., SELECT 1, 'foo'). All other forms—subqueries referencing tables, expressions requiring runtime evaluation, or DEFAULT VALUES—become PreparedInsert::Immediate and bypass buffering.

Sources: llkv-sql/src/sql_engine.rs:473-487

Buffer Lifecycle and Flush Triggers

Flush Conditions

The buffer flushes automatically when any of the following conditions occur:

Sources: llkv-sql/src/sql_engine.rs:414-1127

Buffer State Machine

Figure 4: Buffer State Machine

The buffer exists in one of three states: Empty (no buffer allocated), Buffering (accumulating rows), or Flushing (emitting results). Transitions from Buffering to Flushing occur automatically based on the triggers listed above. After flushing, the state returns to Empty unless a new compatible INSERT immediately follows, in which case a fresh buffer is allocated.

Sources: llkv-sql/src/sql_engine.rs:514-1201

Integration with SqlEngine::execute()

Figure 5: Execute Loop with Buffer Integration

The execute() method iterates through parsed statements, dispatching INSERT statements to buffer_insert() and all other statements to execute_statement() after flushing. This ensures that the buffer never holds rows across non-INSERT operations or transaction boundaries.

Sources: llkv-sql/src/sql_engine.rs:933-990

buffer_insert() Implementation Details

Decision Flow

Figure 6: buffer_insert() Decision Tree

The buffer_insert() method performs three levels of gating:

1. Expectation check : If the SLT harness expects an error or specific row count, bypass buffering entirely
2. Buffering enabled check : If insert_buffering_enabled is false, execute immediately
3. Compatibility check : If the INSERT is incompatible with the current buffer, flush and start a new buffer

Sources: llkv-sql/src/sql_engine.rs:1101-1201

Compatibility Rules

An INSERT can be added to the existing buffer if and only if:

This ensures that all buffered statements can be collapsed into a single InsertPlan with uniform semantics. Different column orderings, conflict actions, or target tables require separate batches.

Sources: llkv-sql/src/sql_engine.rs:452-459

Statement Expectation Handling

The SQL Logic Test harness uses thread-local expectations to signal that a specific statement should produce an error or affect a precise number of rows. The buffering system respects these hints by forcing immediate execution when expectations are present:

Figure 7: Statement Expectation Flow

graph TB
    SLTHarness["SLT Harness"]
RegisterExpectation["register_statement_expectation()"]
ThreadLocal["PENDING_STATEMENT_EXPECTATIONS\nthread_local!"]
Execute["SqlEngine::execute()"]
NextExpectation["next_statement_expectation()"]
BufferInsert["buffer_insert()"]
SLTHarness -->|before statement| RegisterExpectation
 
   RegisterExpectation --> ThreadLocal
 
   Execute --> NextExpectation
 
   NextExpectation --> ThreadLocal
 
   NextExpectation --> BufferInsert
    
 
   BufferInsert -->|Error or Count| ImmediateExec["Execute immediately\nbypass buffer"]
BufferInsert -->|Ok| MayBuffer["May buffer if enabled"]

When next_statement_expectation() returns StatementExpectation::Error or StatementExpectation::Count(n), the buffer_insert() method sets execute_immediately = true and flushes any existing buffer before executing the current statement. This preserves test correctness while still allowing buffering for the majority of statements that have no expectations.

Sources: llkv-sql/src/sql_engine.rs:64-1127

sequenceDiagram
    participant Caller
    participant FlushBuffer as "flush_buffer_results()"
    participant Buffer as "InsertBuffer"
    participant PlanStmt as "PlanStatement::Insert"
    participant Runtime as "RuntimeEngine"
    
    Caller->>FlushBuffer: flush_buffer_results()
    FlushBuffer->>Buffer: Take buffer from RefCell
    
    alt Buffer is None
        FlushBuffer-->>Caller: Ok(Vec::new())
    else Buffer has data
        FlushBuffer->>PlanStmt: Construct InsertPlan\n(table, columns, rows, on_conflict)
        FlushBuffer->>Runtime: execute_statement(plan)
        Runtime-->>FlushBuffer: RuntimeStatementResult::Insert\n(total_rows_inserted)
        
        Note over FlushBuffer: Verify total_rows matches sum(statement_row_counts)
        
        loop For each statement_row_count
            FlushBuffer->>FlushBuffer: Create RuntimeStatementResult::Insert\n(statement_rows)
        end
        
        FlushBuffer-->>Caller: Vec<SqlStatementResult>
    end

flush_buffer_results() Mechanics

The flush operation reconstructs per-statement results from the accumulated buffer state:

Figure 8: Flush Sequence

The flush process:

1. Takes ownership of the buffer from the RefCell
2. Constructs a single InsertPlan with all buffered rows
3. Executes the plan via the runtime
4. Splits the total row count across the original statements using statement_row_counts
5. Returns a vector of per-statement results

This ensures that callers receive results as if each INSERT executed independently, even though the runtime processed them as a single batch.

Sources: llkv-sql/src/sql_engine.rs:2094-2169 (Note: The flush implementation is in the broader file, exact line range may vary)

Performance Characteristics

Throughput Improvement

Buffering provides dramatic performance gains for bulk INSERT workloads:

The improvement stems from:

• Amortized planning : One plan for 8,192 rows instead of 8,192 plans
• Batch MVCC overhead : Single transaction coordinator call instead of thousands
• Reduced catalog lookups : One schema resolution instead of per-statement lookups
• Vectorized column operations : Arrow batch processing instead of row-by-row appends

Sources: llkv-sql/README.md:36-41

Memory Usage

The buffer is bounded at MAX_BUFFERED_INSERT_ROWS = 8192 rows. Peak memory usage depends on the row width:

Peak Memory = MAX_BUFFERED_INSERT_ROWS × (Σ column_size + MVCC_overhead)

For a typical table with 10 columns averaging 50 bytes each:

8,192 rows × (10 columns × 50 bytes + 24 bytes MVCC) ≈ 4.3 MB

This predictable ceiling makes buffering safe for long-running workloads without risking unbounded memory growth.

Sources: llkv-sql/src/sql_engine.rs:410-414

API Surface

Enabling and Disabling

The set_insert_buffering(false) call automatically flushes any pending rows before disabling, ensuring visibility guarantees.

Sources: llkv-sql/src/sql_engine.rs:887-905

Manual Flush

Manual flushes are useful when the caller needs to checkpoint progress or ensure specific INSERT statements are visible before proceeding.

Sources: llkv-sql/src/sql_engine.rs:1003-1010

Drop Hook

The SqlEngine destructor automatically flushes the buffer to prevent data loss:

This ensures that buffered rows are persisted even if the caller forgets to flush explicitly.

Sources: llkv-sql/src/sql_engine.rs:513-520

Limitations and Edge Cases

Non-Bufferable INSERT Forms

The following INSERT patterns always execute immediately:

• INSERT ... SELECT with table references
• INSERT ... DEFAULT VALUES
• INSERT with expressions requiring runtime evaluation (e.g., NOW(), RANDOM())
• INSERT with parameters or placeholders

These patterns cannot be safely batched because their semantics depend on execution context.

Transaction Isolation

The buffer flushes at transaction boundaries (BEGIN, COMMIT, ROLLBACK) to preserve isolation semantics. This means:

The first INSERT's visibility is not guaranteed until the BEGIN statement forces a flush.

Conflict Handling

All buffered statements must share the same InsertConflictAction. Mixing ON CONFLICT IGNORE and ON CONFLICT REPLACE requires separate batches:

Sources: llkv-sql/src/sql_engine.rs:452-1201

Query Planning

Relevant source files

• llkv-executor/Cargo.toml
• llkv-executor/README.md
• llkv-executor/src/lib.rs
• llkv-plan/README.md
• llkv-plan/src/plans.rs
• llkv-sql/README.md
• llkv-sql/src/sql_engine.rs

Purpose and Scope

Query planning is the layer that translates parsed SQL statements into strongly-typed plan structures that can be executed by the runtime engine. The llkv-plan crate defines these plan types and provides utilities for representing queries, expressions, and subquery relationships in a form that execution layers can consume without re-parsing SQL.

This page covers the plan structures themselves and how they are constructed from SQL input. For information about how expressions within plans are evaluated, see Expression System. For details on subquery correlation tracking and placeholder generation, see Subquery and Correlation Handling. For execution of these plans, see Query Execution.

Plan Structures Overview

The planning layer defines distinct plan types for each category of SQL statement. All plan types are defined in llkv-plan/src/plans.rs and flow through the PlanStatement enum for execution dispatch.

Core Plan Types

Sources: llkv-plan/src/plans.rs:177-256 llkv-plan/src/plans.rs:640-655 llkv-plan/src/plans.rs:662-667 llkv-plan/src/plans.rs:687-692

SelectPlan Structure

Diagram: SelectPlan Component Structure

The SelectPlan struct at llkv-plan/src/plans.rs:800-825 contains all information needed to execute a SELECT query. It separates table references, join specifications, projections, filters, aggregations, and ordering to allow execution layers to optimize each phase independently.

Sources: llkv-plan/src/plans.rs:27-67 llkv-plan/src/plans.rs:794-825

SQL-to-Plan Translation Pipeline

The translation from SQL text to plan structures occurs in SqlEngine within the llkv-sql crate. The process involves multiple stages to handle dialect differences and build strongly-typed plans.

Diagram: SQL-to-Plan Translation Flow

sequenceDiagram
    participant User
    participant SqlEngine as "SqlEngine"
    participant Preprocessor as "SQL Preprocessing"
    participant Parser as "sqlparser::Parser"
    participant Translator as "Plan Translator"
    participant Runtime as "RuntimeEngine"
    
    User->>SqlEngine: execute(sql_text)
    
    SqlEngine->>Preprocessor: preprocess_sql_input()
    Note over Preprocessor: Strip CONNECT TO\nNormalize CREATE TYPE\nFix EXCLUDE syntax\nExpand IN clauses
    Preprocessor-->>SqlEngine: processed_sql
    
    SqlEngine->>Parser: Parser::parse_sql()
    Parser-->>SqlEngine: Vec<Statement> (AST)
    
    loop "For each Statement"
        SqlEngine->>Translator: translate_statement()
        
        alt "INSERT statement"
            Translator->>Translator: translate_insert()
            Note over Translator: Parse VALUES/SELECT\nNormalize conflict action\nBuild PreparedInsert
            Translator-->>SqlEngine: PreparedInsert
            SqlEngine->>SqlEngine: buffer_insert()\nor flush immediately
        else "SELECT statement"
            Translator->>Translator: translate_select()
            Note over Translator: Build SelectPlan\nTranslate expressions\nTrack subqueries
            Translator-->>SqlEngine: SelectPlan
        else "UPDATE/DELETE"
            Translator->>Translator: translate_update()/delete()
            Translator-->>SqlEngine: UpdatePlan/DeletePlan
        else "DDL statement"
            Translator->>Translator: translate_create_table()\ncreate_index(), etc.
            Translator-->>SqlEngine: CreateTablePlan/etc.
        end
        
        SqlEngine->>Runtime: execute_statement(plan)
        Runtime-->>SqlEngine: RuntimeStatementResult
    end
    
    SqlEngine-->>User: Vec<RuntimeStatementResult>

Sources: llkv-sql/src/sql_engine.rs:933-958 llkv-sql/src/sql_engine.rs:628-757

Statement Translation Functions

The SqlEngine contains dedicated translation methods for each statement type:

Sources: llkv-sql/src/sql_engine.rs:974-1067

SELECT Translation Details

The translate_select() method at llkv-sql/src/sql_engine.rs2162 performs the following operations:

1. Extract table references from FROM clause into Vec<TableRef>
2. Parse join specifications into Vec<JoinMetadata> structures
3. Translate WHERE clause to Expr<String> and discover correlated subqueries
4. Process projections into Vec<SelectProjection> with computed expressions
5. Handle aggregates by extracting AggregateExpr from projections and HAVING
6. Translate GROUP BY clause to canonical column names
7. Process ORDER BY into Vec<OrderByPlan> with sort specifications
8. Handle compound queries (UNION/INTERSECT/EXCEPT) via CompoundSelectPlan

Sources: llkv-sql/src/sql_engine.rs:2162-2578

Expression Representation in Plans

Plans use two forms of expressions from the llkv-expr crate:

• Expr<String>: Boolean predicates using unresolved column names (as strings)
• ScalarExpr<String>: Scalar expressions (also with string column references)

graph LR
    SQL["SQL: WHERE age > 18"]
AST["sqlparser AST\nBinaryExpr"]
ExprString["Expr<String>\nCompare(Column('age'), Gt, Literal(18))"]
ExprFieldId["Expr<FieldId>\nCompare(Column(field_7), Gt, Literal(18))"]
Bytecode["EvalProgram\nStack-based bytecode"]
SQL --> AST
 
   AST --> ExprString
 
   ExprString --> ExprFieldId
 
   ExprFieldId --> Bytecode
    
    ExprString -.stored in plan.-> SelectPlan
    ExprFieldId -.resolved at execution.-> Executor
    Bytecode -.compiled for evaluation.-> Table

These string-based expressions are later resolved to Expr<FieldId> and ScalarExpr<FieldId> during execution when the catalog provides field mappings. This two-stage approach separates planning from schema resolution.

Diagram: Expression Evolution Through Planning and Execution

The translation from SQL expressions to Expr<String> happens in llkv-sql/src/sql_engine.rs:1647-1947 The resolution to Expr<FieldId> occurs in the executor's translate_predicate() function at llkv-executor/src/translation/predicate.rs

Sources: llkv-expr/src/expr.rs llkv-sql/src/sql_engine.rs:1647-1947 llkv-plan/src/plans.rs:28-34

Join Planning

Join specifications are represented in two components:

JoinMetadata Structure

The JoinMetadata struct at llkv-plan/src/plans.rs:781-792 captures a single join between consecutive tables:

• left_table_index : Index into SelectPlan.tables vector for the left table
• join_type : One of Inner, Left, Right, or Full
• on_condition : Optional ON clause filter expression

JoinPlan Types

The JoinPlan enum at llkv-plan/src/plans.rs:763-773 defines supported join semantics:

Diagram: JoinPlan Variants

The executor converts JoinPlan to llkv_join::JoinType during execution. When SelectPlan.joins is empty but multiple tables exist, the executor performs a Cartesian product (cross join).

Sources: llkv-plan/src/plans.rs:758-792 llkv-executor/src/lib.rs:542-554

Aggregation Planning

Aggregates are represented through the AggregateExpr structure defined at llkv-plan/src/plans.rs:1025-1102:

Aggregate Function Types

Diagram: AggregateFunction Variants

GROUP BY Handling

When a SELECT contains a GROUP BY clause:

1. Column names from GROUP BY are stored in SelectPlan.group_by as canonical strings
2. Aggregate expressions are collected in SelectPlan.aggregates
3. Non-aggregate projections must reference GROUP BY columns
4. HAVING clause (if present) is stored in SelectPlan.having as Expr<String>

The executor groups rows based on group_by columns, evaluates aggregates within each group, and applies the HAVING filter to group results.

Sources: llkv-plan/src/plans.rs:1025-1102 llkv-executor/src/lib.rs:1185-1597

Subquery Representation

Subqueries appear in two contexts within plans:

Filter Subqueries

FilterSubquery at llkv-plan/src/plans.rs:36-45 represents correlated subqueries used in WHERE/HAVING predicates via Expr::Exists:

• id : Unique identifier matching Expr::Exists(SubqueryId)
• plan : Nested SelectPlan for the subquery
• correlated_columns : Mappings from placeholder names to outer query columns

Scalar Subqueries

ScalarSubquery at llkv-plan/src/plans.rs:48-56 represents subqueries that produce single values in projections via ScalarExpr::ScalarSubquery:

Correlated Column Tracking

The CorrelatedColumn struct at llkv-plan/src/plans.rs:59-67 describes how outer columns are bound into inner subqueries:

During execution, the executor substitutes placeholder references with actual values from the outer query's current row.

Sources: llkv-plan/src/plans.rs:36-67 llkv-sql/src/sql_engine.rs:1980-2124

Plan Value Types

The PlanValue enum at llkv-plan/src/plans.rs:73-83 represents literal values within plans:

These values appear in:

• INSERT literal rows (InsertPlan with InsertSource::Rows)
• UPDATE assignments (AssignmentValue::Literal)
• Computed constant expressions

The executor converts PlanValue instances to Arrow arrays via plan_values_to_arrow_array() at llkv-executor/src/lib.rs:302-410

Sources: llkv-plan/src/plans.rs:73-161 llkv-executor/src/lib.rs:302-410

Plan Execution Interface

Plans flow to the runtime through the PlanStatement enum:

Diagram: Plan Execution Dispatch Flow

The RuntimeEngine::execute_statement() method dispatches each plan variant to the appropriate handler:

• SELECT : Passed to QueryExecutor for streaming execution
• INSERT/UPDATE/DELETE : Applied via Table with MVCC tracking
• DDL : Processed by CatalogManager to modify schema metadata

Sources: llkv-runtime/src/statements.rs llkv-sql/src/sql_engine.rs:587-609 llkv-executor/src/lib.rs:523-569

Compound Query Planning

Set operations (UNION, INTERSECT, EXCEPT) are represented through CompoundSelectPlan at llkv-plan/src/plans.rs:969-996:

• CompoundOperator : Union, Intersect, or Except
• CompoundQuantifier : Distinct (deduplicate) or All (keep duplicates)

The executor evaluates the initial plan, then applies each operation sequentially, combining results according to set semantics. Deduplication for DISTINCT quantifiers uses hash-based row encoding.

Sources: llkv-plan/src/plans.rs:946-996 llkv-executor/src/lib.rs:590-686

Plan Structures

Relevant source files

• llkv-executor/Cargo.toml
• llkv-executor/README.md
• llkv-executor/src/lib.rs
• llkv-plan/README.md
• llkv-plan/src/plans.rs
• llkv-sql/README.md

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<TableRef>"]
TableRef["TableRef\nschema, table, alias"]
end
    
    subgraph "Join Specification"
        Joins["joins: Vec<JoinMetadata>"]
JoinMetadata["JoinMetadata\nleft_table_index\njoin_type\non_condition"]
JoinPlan["JoinPlan\nInner/Left/Right/Full"]
end
    
    subgraph "Projections"
        Projections["projections:\nVec<SelectProjection>"]
AllColumns["AllColumns"]
AllColumnsExcept["AllColumnsExcept"]
Column["Column\nname, alias"]
Computed["Computed\nexpr, alias"]
end
    
    subgraph "Filtering"
        Filter["filter: Option<SelectFilter>"]
SelectFilter["SelectFilter\npredicate\nsubqueries"]
FilterSubquery["FilterSubquery\nid, plan,\ncorrelated_columns"]
end
    
    subgraph "Aggregation"
        Aggregates["aggregates:\nVec<AggregateExpr>"]
GroupBy["group_by: Vec<String>"]
Having["having:\nOption<Expr>"]
end
    
    subgraph "Ordering & Modifiers"
        OrderBy["order_by:\nVec<OrderByPlan>"]
Distinct["distinct: bool"]
end
    
    subgraph "Compound Operations"
        Compound["compound:\nOption<CompoundSelectPlan>"]
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:

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]:

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:

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:

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:

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:

InsertSource Variants

InsertConflictAction Variants

SQLite-compatible conflict resolution actions:

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

UpdatePlan and DeletePlan

UpdatePlan

UpdatePlan specifies row updates with optional filtering:

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:

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):

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

DDL Plan Structures

CreateTablePlan

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

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

PlanColumnSpec

PlanColumnSpec describes individual column metadata:

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:

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:

AlterTableOperation variants:

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

Additional DDL Plans

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:

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

Subquery and Correlation Handling

Relevant source files

• llkv-executor/Cargo.toml
• llkv-executor/src/lib.rs
• llkv-plan/src/plans.rs
• llkv-sql/src/sql_engine.rs

This page documents how LLKV handles subqueries and correlated column references during query planning and execution. Subqueries can appear in WHERE clauses (as EXISTS predicates) or in SELECT projections (as scalar subqueries). When a subquery references columns from its outer query, it is called a correlated subquery , requiring special handling to bind outer row values during execution.

For information about expression evaluation and compilation, see Expression System. For query execution flow, see Query Execution.

Purpose and Scope

Subquery handling in LLKV involves three distinct phases:

1. Detection and Tracking - During SQL translation, the planner identifies subqueries and tracks which outer columns they reference
2. Placeholder Injection - Correlated columns are replaced with synthetic placeholder identifiers in the subquery's expression tree
3. Binding and Execution - At runtime, for each outer row, placeholders are replaced with actual values and the subquery is executed

This document covers the data structures, algorithms, and execution flow for both filter subqueries (EXISTS/NOT EXISTS) and scalar subqueries (single-value returns).

Core Data Structures

LLKV represents subqueries and their correlation metadata through several interconnected structures defined in llkv-plan.

classDiagram
    class SelectFilter {+Expr~String~ predicate\n+Vec~FilterSubquery~ subqueries}
    
    class FilterSubquery {+SubqueryId id\n+Box~SelectPlan~ plan\n+Vec~CorrelatedColumn~ correlated_columns}
    
    class ScalarSubquery {+SubqueryId id\n+Box~SelectPlan~ plan\n+Vec~CorrelatedColumn~ correlated_columns}
    
    class CorrelatedColumn {+String placeholder\n+String column\n+Vec~String~ field_path}
    
    class SelectPlan {+Vec~TableRef~ tables\n+Option~SelectFilter~ filter\n+Vec~ScalarSubquery~ scalar_subqueries\n+Vec~SelectProjection~ projections}
    
    SelectPlan --> SelectFilter : filter
    SelectPlan --> ScalarSubquery : scalar_subqueries
    SelectFilter --> FilterSubquery : subqueries
    FilterSubquery --> CorrelatedColumn : correlated_columns
    ScalarSubquery --> CorrelatedColumn : correlated_columns
    FilterSubquery --> SelectPlan : plan
    ScalarSubquery --> SelectPlan : plan

Subquery Plan Structures

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

Field Descriptions

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

Correlation Tracking During Planning

During SQL-to-plan translation, LLKV uses the SubqueryCorrelatedTracker to detect when a subquery references outer columns. This tracker is passed through the expression translation pipeline and records each outer column access.

graph TB
    subgraph "SQL Translation Phase"
        SQL["SQL Query String"]
Parser["sqlparser AST"]
end
    
    subgraph "Subquery Detection"
        TranslateExpr["translate_predicate / translate_scalar"]
Tracker["SubqueryCorrelatedTracker"]
Resolver["IdentifierResolver"]
end
    
    subgraph "Placeholder Injection"
        OuterColumn["Outer Column Reference"]
Placeholder["Synthetic Placeholder"]
Recording["CorrelatedColumn Entry"]
end
    
    subgraph "Plan Output"
        FilterSubquery["FilterSubquery"]
ScalarSubquery["ScalarSubquery"]
SelectPlan["SelectPlan"]
end
    
 
   SQL --> Parser
 
   Parser --> TranslateExpr
 
   TranslateExpr --> Tracker
 
   TranslateExpr --> Resolver
    
 
   Tracker --> OuterColumn
 
   OuterColumn --> Placeholder
 
   Placeholder --> Recording
    
 
   Recording --> FilterSubquery
 
   Recording --> ScalarSubquery
 
   FilterSubquery --> SelectPlan
 
   ScalarSubquery --> SelectPlan

Tracker Architecture

Sources: llkv-sql/src/sql_engine.rs24 llkv-sql/src/sql_engine.rs:326-363

Placeholder Generation

When the tracker detects an outer column reference in a subquery, it:

1. Generates a unique placeholder string (e.g., "__correlated_0__")
2. Records the mapping: placeholder → (outer_column, field_path)
3. Returns the placeholder to the expression translator
4. The placeholder is embedded in the subquery's expression tree instead of the original column name

This allows the subquery plan to be "generic" - it references placeholders that will be bound to actual values at execution time.

Sources: llkv-sql/src/sql_engine.rs:337-351

Tracker Extension Traits

The SubqueryCorrelatedTrackerExt trait provides a convenience method to request placeholders directly from catalog resolution results, avoiding repetitive unpacking of ColumnResolution fields.

The SubqueryCorrelatedTrackerOptionExt trait enables chaining optional tracker references through nested translation helpers without explicit as_mut() calls.

Sources: llkv-sql/src/sql_engine.rs:337-363

Subquery Types and Execution

LLKV supports two categories of subqueries, each with distinct execution semantics.

sequenceDiagram
    participant Executor as QueryExecutor
    participant Filter as Filter Evaluation
    participant Subquery as EXISTS Subquery
    participant Binding as Binding Logic
    participant Inner as Inner SelectPlan
    
    Executor->>Filter: evaluate_predicate_mask()
    Filter->>Filter: encounter Expr::Exists
    Filter->>Subquery: evaluate_exists_subquery()
    Subquery->>Binding: collect_correlated_bindings()
    Binding->>Binding: extract outer row values
    Binding-->>Subquery: bindings map
    Subquery->>Inner: bind_select_plan()
    Inner->>Inner: replace placeholders with values
    Inner-->>Subquery: bound SelectPlan
    Subquery->>Executor: execute_select(bound_plan)
    Executor-->>Subquery: SelectExecution stream
    Subquery->>Subquery: check if num_rows > 0
    Subquery-->>Filter: boolean result
    Filter-->>Executor: BooleanArray mask

Filter Subqueries (EXISTS Predicates)

Filter subqueries appear in WHERE clauses as EXISTS or NOT EXISTS predicates. They return a boolean indicating whether the subquery produced any rows.

Sources: llkv-executor/src/lib.rs:773-792

Scalar Subqueries (Projection Values)

Scalar subqueries appear in SELECT projections and must return exactly one column and at most one row. They are evaluated into a single literal value for each outer row.

Sources: llkv-executor/src/lib.rs:794-891

sequenceDiagram
    participant Executor as QueryExecutor
    participant Projection as Projection Logic
    participant Subquery as Scalar Subquery Evaluator
    participant Binding as Binding Logic
    participant Inner as Inner SelectPlan
    
    Executor->>Projection: evaluate_projection_expression()
    Projection->>Projection: encounter ScalarExpr::ScalarSubquery
    Projection->>Subquery: evaluate_scalar_subquery_numeric()
    
    loop For each outer row
        Subquery->>Subquery: evaluate_scalar_subquery_literal()
        Subquery->>Binding: collect_correlated_bindings()
        Binding-->>Subquery: bindings for current row
        Subquery->>Inner: bind_select_plan()
        Inner-->>Subquery: bound plan
        Subquery->>Executor: execute_select()
        Executor-->>Subquery: result batches
        Subquery->>Subquery: validate single column/row
        Subquery->>Subquery: convert to Literal
        Subquery-->>Projection: literal value
    end
    
    Projection->>Projection: build NumericArray from literals
    Projection-->>Executor: computed column array

Binding Process

The binding process replaces placeholder identifiers in a subquery plan with actual values from the current outer row.

Correlated Binding Collection

The collect_correlated_bindings function builds a map from placeholder strings to concrete Literal values by:

1. Iterating over each CorrelatedColumn in the subquery metadata
2. Looking up the outer column in the current RecordBatch
3. Extracting the value at the current row index
4. Converting the Arrow array value to a Literal
5. Storing the mapping: placeholder → Literal

Sources: Referenced in llkv-executor/src/lib.rs781 llkv-executor/src/lib.rs802

graph LR
    subgraph "Input"
        OuterBatch["RecordBatch\n(outer query result)"]
RowIndex["Current Row Index"]
Metadata["Vec<CorrelatedColumn>"]
end
    
    subgraph "Processing"
        Iterate["For each CorrelatedColumn"]
Lookup["Find column in schema"]
Extract["Extract array[row_idx]"]
Convert["Convert to Literal"]
end
    
    subgraph "Output"
        Bindings["FxHashMap<placeholder, Literal>"]
end
    
 
   OuterBatch --> Iterate
 
   RowIndex --> Iterate
 
   Metadata --> Iterate
    
 
   Iterate --> Lookup
 
   Lookup --> Extract
 
   Extract --> Convert
 
   Convert --> Bindings

Plan Binding

The bind_select_plan function takes a subquery SelectPlan and a bindings map, then recursively replaces:

• Placeholder column references in filter expressions with Expr::Literal
• Placeholder column references in projections with ScalarExpr::Literal
• Placeholder column references in HAVING clauses
• Placeholder references in nested subqueries

This produces a new SelectPlan that is fully "grounded" with the outer row's values and can be executed independently.

Sources: Referenced in llkv-executor/src/lib.rs782 llkv-executor/src/lib.rs803

Execution Flow: EXISTS Subquery Example

Consider the query:

Planning Phase

Sources: llkv-plan/src/plans.rs:36-46

Execution Phase

Sources: llkv-executor/src/lib.rs:773-792

Execution Flow: Scalar Subquery Example

Consider the query:

Planning Phase

Sources: llkv-plan/src/plans.rs:48-56

Execution Phase

Sources: llkv-executor/src/lib.rs:834-891

Cross-Product Integration

When subqueries appear in cross-product (multi-table) queries, the binding process works identically but must resolve outer column names through the combined schema.

Cross-Product Expression Context

The CrossProductExpressionContext maintains:

• Combined schema from all tables in the FROM clause
• Column lookup map (qualified names → column indices)
• Numeric array cache for evaluated expressions
• Synthetic field ID allocation for subquery results

When evaluating a filter or projection expression that contains subqueries, the context:

1. Detects subquery references by SubqueryId
2. Calls the appropriate evaluator (evaluate_exists_subquery or evaluate_scalar_subquery_numeric)
3. Passes the combined schema and current row to the binding logic
4. Caches numeric results for scalar subqueries to avoid re-evaluation

Sources: llkv-executor/src/lib.rs:1329-1383 llkv-executor/src/lib.rs:1429-1502

Validation and Error Handling

The executor enforces several constraints on subquery results:

Error Examples

Scalar Subquery: Multiple Columns

Scalar Subquery: Multiple Rows

Sources: llkv-executor/src/lib.rs:808-819

Subquery ID Assignment

SubqueryId is a newtype wrapper around usize defined in llkv-expr. The planner assigns sequential IDs as it encounters subqueries during translation, ensuring each subquery has a unique identifier that persists from planning through execution.

The executor uses these IDs to:

• Look up subquery metadata in the plan's scalar_subqueries or filter's subqueries vectors
• Match subquery references in expression trees (ScalarExpr::ScalarSubquery or Expr::Exists) to their plans
• Cache evaluation results (for scalar subqueries appearing multiple times)

Sources: [llkv-expr referenced in llkv-plan/src/plans.rs15](https://github.com/jzombie/rust-llkv/blob/4dc34c1f/llkv-expr referenced in llkv-plan/src/plans.rs#L15-L15)

Recursive Subquery Support

LLKV supports nested subqueries where an inner subquery can itself contain subqueries. The binding process is recursive:

1. Bind outer-level placeholders in the top-level subquery plan
2. For any nested subqueries within that plan, repeat the binding process
3. Continue until all correlation layers are resolved

This is handled automatically by bind_select_plan which traverses the entire plan tree.

Sources: Referenced in llkv-executor/src/lib.rs782 llkv-executor/src/lib.rs803

Performance Considerations

Correlation Overhead

Correlated subqueries are executed once per outer row, which can be expensive:

• An outer query returning N rows with a correlated subquery executes N + 1 queries total
• For scalar subqueries in projections with multiple references, results are cached per subquery ID
• EXISTS subqueries short-circuit as soon as a matching row is found (first batch with num_rows() > 0)

Uncorrelated Subqueries

If a subquery contains no correlated columns (empty correlated_columns vector), it could theoretically be executed once and reused. However, LLKV's current implementation still executes it per outer row. Future optimizations could detect this case and cache the result.

Sources: llkv-executor/src/lib.rs:773-891

Summary

LLKV's subquery handling follows a three-phase model:

1. Planning : The SubqueryCorrelatedTracker detects outer column references and generates placeholders. Plans are built with FilterSubquery or ScalarSubquery structures containing correlation metadata.

2. Binding : At execution time, collect_correlated_bindings extracts outer row values and bind_select_plan replaces placeholders with literals, producing a grounded plan.

3. Execution : The bound plan is executed as an independent query. EXISTS subqueries return a boolean; scalar subqueries return a single literal (or NULL if empty).

This design keeps the subquery plan generic during planning and binds it dynamically at execution time, enabling proper correlation semantics while maintaining the separation between planning and execution layers.

Sources: llkv-plan/src/plans.rs:28-67 llkv-sql/src/sql_engine.rs24 llkv-sql/src/sql_engine.rs:326-363 llkv-executor/src/lib.rs:773-891

Expression System

Relevant source files

• llkv-executor/Cargo.toml
• llkv-executor/src/lib.rs
• llkv-executor/src/translation/expression.rs
• llkv-executor/src/translation/schema.rs
• llkv-expr/src/expr.rs
• llkv-plan/src/plans.rs
• llkv-table/src/planner/program.rs

The expression system provides the intermediate representation for predicates, projections, and computations in LLKV. It defines a strongly-typed Abstract Syntax Tree (AST) that decouples query logic from concrete storage formats, enabling optimization and efficient evaluation against Apache Arrow data structures.

This page covers the overall architecture of the expression system. For details on specific components:

• Expression AST structure and types: see 5.1
• Column name resolution and translation: see 5.2
• Bytecode compilation and normalization: see 5.3
• Scalar evaluation engine: see 5.4
• Aggregate function evaluation: see 5.5

Purpose and Scope

The expression system serves three primary functions:

1. Representation : Defines generic AST types (Expr<F>, ScalarExpr<F>) parameterized over field identifiers, supporting both string-based column names (during planning) and integer field IDs (during execution)

2. Translation : Resolves column names to storage field identifiers by consulting the catalog, enabling type-safe access to table columns

3. Compilation : Transforms normalized expressions into stack-based bytecode (EvalProgram, DomainProgram) for efficient vectorized evaluation

The system is located primarily in llkv-expr/, with translation logic in llkv-executor/src/translation/ and compilation in llkv-table/src/planner/program.rs.

Sources: llkv-expr/src/expr.rs:1-749 llkv-executor/src/translation/expression.rs:1-424 llkv-table/src/planner/program.rs:1-710

Expression Type Hierarchy

LLKV uses two primary expression types, both generic over the field identifier type F:

Expression Types

Type Parameterization Flow

Sources: llkv-expr/src/expr.rs:14-333 llkv-plan/src/plans.rs:28-67 llkv-executor/src/translation/expression.rs:18-174

Expression Lifecycle

Expressions flow through multiple stages from SQL text to execution against storage:

Stage 1: Planning

The SQL layer (llkv-sql) parses SQL statements and constructs plan structures containing expressions. At this stage, column references use string names from the SQL text:

• Predicates : Stored as Expr<'static, String> in SelectFilter
• Projections : Stored as ScalarExpr<String> in SelectProjection::Computed
• Assignments : Stored as ScalarExpr<String> in UpdatePlan::assignments

Sources: llkv-plan/src/plans.rs:28-34 llkv-sql/src/translator/mod.rs (inferred from architecture)

Stage 2: Translation

The executor translates string-based expressions to field-ID-based expressions by consulting the table schema:

1. Column Resolution : translate_predicate and translate_scalar walk the expression tree
2. Schema Lookup : Each column name is resolved to a FieldId using ExecutorSchema::resolve
3. Type Inference : For computed projections, infer_computed_data_type determines the Arrow data type
4. Special Columns : System columns like "rowid" map to special field IDs (e.g., ROW_ID_FIELD_ID)

Translation is implemented via iterative traversal to avoid stack overflow on deeply nested expressions (50k+ nodes).

Sources: llkv-executor/src/translation/expression.rs:18-174 llkv-executor/src/translation/expression.rs:176-387 llkv-executor/src/translation/schema.rs:53-123

Stage 3: Compilation

The table layer compiles Expr<FieldId> into bytecode for efficient evaluation:

1. Normalization : normalize_predicate applies De Morgan's laws and flattens nested AND/OR nodes

2. Compilation : ProgramCompiler::compile generates two programs:

   • EvalProgram: Stack-based bytecode for predicate evaluation
   • DomainProgram: Bytecode for tracking which fields affect row visibility

3. Fusion Optimization : Multiple predicates on the same field are fused into a single FusedAnd operation

graph TB
    Input["Expr<FieldId>\nNOT(age > 18 AND status = 'active')"]
Norm["normalize_predicate\nApply De Morgan's law"]
Normal["Expr<FieldId>\nOR([\n NOT(age > 18),\n NOT(status = 'active')\n])"]
Compile["ProgramCompiler::compile"]
subgraph "Output Programs"
        Eval["EvalProgram\nops: [\n PushCompare(age, Gt, 18),\n Not,\n PushCompare(status, Eq, 'active'),\n Not,\n Or(2)\n]"]
Domain["DomainProgram\nops: [\n PushCompareDomain(...),\n PushCompareDomain(...),\n Union(2)\n]"]
end
    
 
   Input --> Norm
 
   Norm --> Normal
 
   Normal --> Compile
 
   Compile --> Eval
 
   Compile --> Domain

Sources: llkv-table/src/planner/program.rs:286-318 llkv-table/src/planner/program.rs:416-516 llkv-table/src/planner/program.rs:550-631

Stage 4: Evaluation

Compiled programs are executed against Arrow RecordBatch data:

1. EvalProgram : Evaluates predicates row-by-row using a value stack, producing boolean results
2. DomainProgram : Identifies which row IDs could possibly match (used for optimization)
3. ScalarExpr : Evaluated via NumericKernels for vectorized arithmetic operations

The evaluation engine handles Arrow's columnar format efficiently through zero-copy operations and SIMD-friendly algorithms.

Sources: llkv-table/src/planner/evaluator.rs (inferred from architecture), llkv-executor/src/lib.rs:254-296

Key Components

ProgramCompiler

Compiles normalized expressions into bytecode:

Key Optimizations :

• Predicate Fusion : gather_fused detects multiple predicates on the same field and emits FusedAnd operations
• Domain Caching : Domain programs are memoized by expression identity to avoid recompilation
• Stack-Based Evaluation : Operations push/pop from a value stack, avoiding recursive evaluation overhead

Sources: llkv-table/src/planner/program.rs:257-284 llkv-table/src/planner/program.rs:416-516 llkv-table/src/planner/program.rs:518-542

Bytecode Operations

EvalOp Variants

DomainOp Variants

Sources: llkv-table/src/planner/program.rs:36-67 llkv-table/src/planner/program.rs:221-254

Expression Translation

Translation resolves column names to field IDs through schema lookup:

Special Handling :

• Rowid Column : "rowid" (case-insensitive) maps to ROW_ID_FIELD_ID constant
• Flexible Matching : Supports qualified names (table.column) and unqualified names (column)
• Error Handling : Unknown columns produce descriptive error messages with the column name

Sources: llkv-executor/src/translation/expression.rs:390-407 llkv-executor/src/translation/expression.rs:410-423

Type Inference

The executor infers Arrow data types for computed projections to construct the output schema:

Type Inference Rules

Numeric Type Normalization : Small integers (Int8, Int16, Int32, Boolean) normalize to Int64, while all floating-point types normalize to Float64. This simplifies arithmetic evaluation.

Sources: llkv-executor/src/translation/schema.rs:53-123 llkv-executor/src/translation/schema.rs:125-147 llkv-executor/src/translation/schema.rs:149-243

Subquery Support

Expressions support two types of subqueries:

EXISTS Predicates

Used in WHERE clauses to test for row existence:

• Structure : Expr::Exists(SubqueryExpr{id, negated})
• Planning : Stored in SelectFilter::subqueries with correlated column bindings
• Evaluation : Executor binds outer row values to correlated columns, executes subquery plan, returns true if any rows match

Scalar Subqueries

Used in projections to return a single value:

• Structure : ScalarExpr::ScalarSubquery(ScalarSubqueryExpr{id})
• Planning : Stored in SelectPlan::scalar_subqueries with correlated column bindings
• Evaluation : Executor binds outer row values, executes subquery, extracts single value
• Error Handling : Returns error if subquery returns multiple rows or columns

Sources: llkv-expr/src/expr.rs:42-63 llkv-plan/src/plans.rs:36-56 llkv-executor/src/lib.rs:774-839

Normalization

Expression normalization applies logical transformations before compilation:

De Morgan's Laws

NOT is pushed down through AND/OR using De Morgan's laws:

• NOT(A AND B) → NOT(A) OR NOT(B)
• NOT(A OR B) → NOT(A) AND NOT(B)
• NOT(NOT(A)) → A

Flattening

Nested AND/OR nodes are flattened:

• AND(A, AND(B, C)) → AND(A, B, C)
• OR(A, OR(B, C)) → OR(A, B, C)

Special Cases

• NOT(Literal(true)) → Literal(false)
• NOT(IsNull{expr, false}) → IsNull{expr, true}

Sources: llkv-table/src/planner/program.rs:286-343

Expression Operators

Binary Operators (BinaryOp)

Comparison Operators (CompareOp)

Comparisons in ScalarExpr::Compare return 1 for true, 0 for false, NULL for NULL propagation.

Sources: llkv-expr/src/expr.rs:270-293

Memory Management

Expression Lifetimes

The 'a lifetime parameter in Expr<'a, F> allows borrowed operators to avoid allocations:

• Operator::In(&'a [Literal]): Borrows slice from call site
• Operator::StartsWith{pattern: &'a str, ...}: Borrows pattern string
• Filter<'a, F>: Contains borrowed Operator<'a>

Owned Variants : EvalProgram and DomainProgram use OwnedOperator and OwnedFilter for storage, converting borrowed operators to owned values.

Zero-Copy Pattern

During evaluation, predicates borrow from the compiled program rather than cloning operators, enabling zero-copy predicate evaluation against Arrow arrays.

Sources: llkv-expr/src/expr.rs:295-333 llkv-table/src/planner/program.rs:69-143

Expression AST

Relevant source files

• llkv-executor/src/translation/expression.rs
• llkv-executor/src/translation/schema.rs
• llkv-expr/src/expr.rs
• llkv-table/src/planner/program.rs

Purpose and Scope

This document describes the expression Abstract Syntax Tree (AST) defined in the llkv-expr crate. The expression AST provides type-aware, Arrow-native data structures for representing boolean predicates and scalar expressions throughout the LLKV system. These AST nodes are decoupled from SQL parsing and can be parameterized by field identifier types, enabling reuse across multiple processing stages.

For information about how expressions are translated between field identifier types, see Expression Translation. For details on how expressions are compiled into executable bytecode, see Program Compilation. For scalar evaluation mechanics, see Scalar Evaluation and NumericKernels.

Sources: llkv-expr/src/expr.rs:1-8

Expression Type Hierarchy

The llkv-expr crate defines two primary expression enums:

• Expr<'a, F> - Boolean/predicate expressions that evaluate to true or false
• ScalarExpr<F> - Arithmetic/scalar expressions that produce typed values

graph TB
    subgraph "Expression Type System"
        EXPR["Expr<'a, F>\nBoolean Predicates"]
SCALAR["ScalarExpr<F>\nScalar Values"]
EXPR --> LOGICAL["Logical Operators\nAnd, Or, Not"]
EXPR --> PRED["Pred(Filter)\nField Predicates"]
EXPR --> COMPARE["Compare\nScalar Comparisons"]
EXPR --> INLIST["InList\nSet Membership"]
EXPR --> ISNULL["IsNull\nNull Checks"]
EXPR --> LITERAL["Literal(bool)\nConstant Boolean"]
EXPR --> EXISTS["Exists\nSubquery Predicates"]
SCALAR --> COLUMN["Column(F)\nField Reference"]
SCALAR --> SLITERAL["Literal\nConstant Value"]
SCALAR --> BINARY["Binary\nArithmetic Ops"]
SCALAR --> SNOT["Not\nLogical Negation"]
SCALAR --> SISNULL["IsNull\nNull Test"]
SCALAR --> AGG["Aggregate\nAggregate Functions"]
SCALAR --> GETFIELD["GetField\nStruct Access"]
SCALAR --> CAST["Cast\nType Conversion"]
SCALAR --> SCOMPARE["Compare\nBoolean Result"]
SCALAR --> COALESCE["Coalesce\nFirst Non-Null"]
SCALAR --> SUBQ["ScalarSubquery\nSubquery Value"]
SCALAR --> CASE["Case\nConditional Logic"]
SCALAR --> RANDOM["Random\nRandom Number"]
COMPARE -.uses.-> SCALAR
        INLIST -.uses.-> SCALAR
        ISNULL -.uses.-> SCALAR
    end
    
    style EXPR fill:#e8f5e9
    style SCALAR fill:#e1f5ff

Both types are generic over a field identifier parameter F, which allows the same AST structure to be used with different field representations (typically String column names during planning, or FieldId numeric identifiers during execution).

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

Expr<'a, F> - Boolean Expressions

The Expr<'a, F> enum represents boolean predicate expressions that evaluate to true or false. These are primarily used in WHERE clauses, JOIN conditions, and HAVING clauses.

Expr Variants

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

Expr Construction Helpers

The Expr type provides builder methods for common patterns:

These helpers simplify construction of common predicate patterns during query planning.

Sources: llkv-expr/src/expr.rs:65-84

Filter and Operator Types

The Pred variant wraps a Filter<'a, F> struct, which represents a single predicate against a field:

The Operator<'a> enum defines comparison operations over untyped Literal values:

The Operator type uses borrowed slices for In and borrowed string slices for pattern matching to avoid allocations in common cases.

Sources: llkv-expr/src/expr.rs:295-358

ScalarExpr - Scalar Expressions

The ScalarExpr<F> enum represents arithmetic and scalar expressions that produce typed values. These are used in SELECT projections, computed columns, ORDER BY clauses, and as operands in comparisons.

graph TB
    subgraph "ScalarExpr Evaluation Categories"
        SIMPLE["Simple Values"]
ARITH["Arithmetic"]
LOGIC["Logical"]
STRUCT["Structured"]
CONTROL["Control Flow"]
SPECIAL["Special Functions"]
SIMPLE --> COLUMN["Column(F)\nField reference"]
SIMPLE --> LITERAL["Literal\nConstant value"]
ARITH --> BINARY["Binary\nleft op right"]
ARITH --> CAST["Cast\nType conversion"]
LOGIC --> NOT["Not\nLogical negation"]
LOGIC --> ISNULL["IsNull\nNull test"]
LOGIC --> COMPARE["Compare\nComparison"]
STRUCT --> GETFIELD["GetField\nStruct field access"]
STRUCT --> AGGREGATE["Aggregate\nAggregate function"]
CONTROL --> CASE["Case\nCASE expression"]
CONTROL --> COALESCE["Coalesce\nFirst non-null"]
SPECIAL --> SUBQUERY["ScalarSubquery\nScalar subquery"]
SPECIAL --> RANDOM["Random\nRandom number"]
end

ScalarExpr Variants

Sources: llkv-expr/src/expr.rs:86-143

Arithmetic and Binary Operations

The Binary variant supports arithmetic and logical operations:

BinaryOp Variants:

Sources: llkv-expr/src/expr.rs:270-282

Comparison Operations

The Compare variant in ScalarExpr produces a boolean (1/0) result:

CompareOp Variants:

Sources: llkv-expr/src/expr.rs:284-293 llkv-expr/src/expr.rs:119-124

AggregateCall Variants

The Aggregate(AggregateCall<F>) variant wraps aggregate function calls:

Each aggregate (except CountStar) operates on a ScalarExpr<F> rather than just a column, enabling complex expressions like AVG(col1 + col2) or SUM(-col1).

Sources: llkv-expr/src/expr.rs:145-176

Struct Field Access

The GetField variant extracts fields from struct-typed expressions:

This represents dot-notation access like user.address.city, which is nested as:

GetField {
    base: GetField {
        base: Column(user),
        field_name: "address"
    },
    field_name: "city"
}

Sources: llkv-expr/src/expr.rs:107-113

CASE Expressions

The Case variant implements SQL CASE expressions:

• Simple CASE: operand is Some, branches test equality
• Searched CASE: operand is None, branches evaluate conditions
• ELSE clause: Handled by else_expr field

Sources: llkv-expr/src/expr.rs:129-137

ScalarExpr Helper Methods

Builder methods simplify construction:

Sources: llkv-expr/src/expr.rs:178-268

Subquery Expression Types

The expression AST includes dedicated types for correlated and scalar subqueries:

SubqueryExpr

Used in Expr::Exists for boolean subquery predicates:

The id references a subquery definition stored separately (typically in the enclosing plan), and negated indicates NOT EXISTS.

Sources: llkv-expr/src/expr.rs:49-56

ScalarSubqueryExpr

Used in ScalarExpr::ScalarSubquery for value-producing subqueries:

This represents subqueries that return a single scalar value, used in expressions like SELECT (SELECT MAX(price) FROM orders) + 10.

Sources: llkv-expr/src/expr.rs:58-63

SubqueryId

Both subquery types use SubqueryId as an opaque identifier:

This ID is resolved during execution by looking up the subquery definition in the parent plan's metadata.

Sources: llkv-expr/src/expr.rs:45-47

graph LR
    subgraph "Expression Translation Pipeline"
        SQL["SQL Text"]
PLAN["Query Plan\nExpr<String>\nScalarExpr<String>"]
TRANS["Translation\nresolve_field_id()"]
EXEC["Execution\nExpr<FieldId>\nScalarExpr<FieldId>"]
EVAL["Evaluation\nRecordBatch Results"]
SQL --> PLAN
 
       PLAN --> TRANS
 
       TRANS --> EXEC
 
       EXEC --> EVAL
    end

Generic Field Parameter

The expression AST is parameterized by field identifier type F, enabling reuse across different processing stages:

Common instantiations:

• Expr<'a, String> - Used during query planning with column names
• Expr<'a, FieldId> - Used during execution with numeric field IDs
• ScalarExpr<String> - Planning-time scalar expressions
• ScalarExpr<FieldId> - Execution-time scalar expressions

The translation from String to FieldId occurs in llkv-executor/src/translation/expression.rs using catalog lookups to resolve column names to their internal numeric identifiers.

Sources: llkv-executor/src/translation/expression.rs:18-174

Literal Values

Both expression types use the Literal enum from llkv-expr to represent untyped constant values:

Literal values are type-agnostic at the AST level. Type coercion and validation occur during execution when column types are known.

Sources: llkv-expr/src/expr.rs10 llkv-executor/src/translation/schema.rs:53-123

graph TB
    subgraph "Type Inference Rules"
        SCALAR["ScalarExpr<FieldId>"]
SCALAR --> LITERAL["Literal → Literal type"]
SCALAR --> COLUMN["Column → Schema lookup"]
SCALAR --> BINARY["Binary → Int64 or Float64"]
SCALAR --> NOT["Not → Int64 (boolean)"]
SCALAR --> ISNULL["IsNull → Int64 (boolean)"]
SCALAR --> COMPARE["Compare → Int64 (boolean)"]
SCALAR --> AGG["Aggregate → Int64"]
SCALAR --> GETFIELD["GetField → Struct field type"]
SCALAR --> CAST["Cast → Target type"]
SCALAR --> CASE["Case → Int64 or Float64"]
SCALAR --> COALESCE["Coalesce → Int64 or Float64"]
SCALAR --> RANDOM["Random → Float64"]
SCALAR --> SUBQUERY["ScalarSubquery → Utf8 (TODO)"]
BINARY --> FLOATCHECK["Contains Float64?"]
FLOATCHECK -->|Yes| FLOAT64["Float64"]
FLOATCHECK -->|No| INT64["Int64"]
CASE --> CASECHECK["Branches use Float64?"]
CASECHECK -->|Yes| CASEFLOAT["Float64"]
CASECHECK -->|No| CASEINT["Int64"]
end

Expression Type Inference

During execution planning, the system infers output types for ScalarExpr based on operand types:

The inference logic is implemented in infer_computed_data_type() and expression_uses_float(), which recursively analyze expression trees to determine output types.

Sources: llkv-executor/src/translation/schema.rs:53-271

Expression Normalization

Before compilation, predicates undergo normalization to flatten nested AND/OR structures and apply De Morgan's laws:

Normalization Rules:

1. Flatten AND: And([And([a, b]), c]) → And([a, b, c])
2. Flatten OR: Or([Or([a, b]), c]) → Or([a, b, c])
3. De Morgan's AND: Not(And([a, b])) → Or([Not(a), Not(b)])
4. De Morgan's OR: Not(Or([a, b])) → And([Not(a), Not(b)])
5. Double Negation: Not(Not(expr)) → expr
6. Literal Negation: Not(Literal(true)) → Literal(false)
7. IsNull Negation: Not(IsNull { expr, negated }) → IsNull { expr, negated: !negated }

This normalization simplifies subsequent optimization and compilation steps.

Sources: llkv-table/src/planner/program.rs:286-343

Expression Compilation

Normalized expressions are compiled into two bytecode programs:

1. EvalProgram - Stack-based evaluation of predicates
2. DomainProgram - Set-based domain analysis for row filtering

The compilation process:

• Detects fusable predicates (multiple conditions on same field)
• Builds domain programs for NOT operations
• Produces postorder bytecode for stack-based evaluation

Sources: llkv-table/src/planner/program.rs:256-631

Expression AST Usage Flow

Key stages:

1. SQL Parsing - External sqlparser produces SQL AST
2. Plan Building - llkv-plan converts SQL AST to Expr<String>
3. Translation - llkv-executor resolves column names to FieldId
4. Normalization - llkv-table flattens and optimizes structure
5. Compilation - llkv-table produces bytecode programs
6. Execution - llkv-table evaluates against RecordBatch data

Sources: llkv-expr/src/expr.rs:1-8 llkv-executor/src/translation/expression.rs:18-174 llkv-table/src/planner/program.rs:256-631

Expression Translation

Relevant source files

• llkv-executor/src/translation/expression.rs
• llkv-executor/src/translation/schema.rs
• llkv-expr/src/expr.rs
• llkv-table/src/planner/program.rs

Purpose and Scope

Expression Translation is the process of converting expressions from using string-based column names to using internal field identifiers. This transformation bridges the gap between the SQL interface layer (which references columns by name) and the execution layer (which references columns by numeric FieldId). This page covers the translation phase that occurs after query planning but before expression compilation.

For information about the expression AST structure, see Expression AST. For information about how translated expressions are compiled into bytecode, see Program Compilation.

Translation Phase in Query Pipeline

The expression translation phase sits between SQL planning and execution, converting symbolic column references to physical field identifiers.

Translation Phase Detail

graph LR
    SQL["SQL WHERE\nname = 'Alice'"]
AST["sqlparser AST"]
EXPRSTR["Expr<String>\nColumn('name')"]
CATALOG["Schema Lookup"]
EXPRFID["Expr<FieldId>\nColumn(42)"]
COMPILE["Bytecode\nCompilation"]
SQL --> AST
 
   AST --> EXPRSTR
 
   EXPRSTR --> CATALOG
 
   CATALOG --> EXPRFID
 
   EXPRFID --> COMPILE
    
    style EXPRSTR fill:#fff5e1
    style EXPRFID fill:#ffe1e1

Sources: Based on Diagram 5 from system architecture overview

The translation process resolves all column name strings to their corresponding FieldId values by consulting the table schema. This enables the downstream execution engine to work with stable numeric identifiers rather than string lookups.

Generic Expression Types

Both Expr and ScalarExpr are generic over the field identifier type, parameterized as F.

Type Parameter Instantiations

graph TB
    subgraph "Generic Types"
        EXPR["Expr<'a, F>"]
SCALAR["ScalarExpr<F>"]
FILTER["Filter<'a, F>\n{field_id: F, op: Operator}"]
end
    
    subgraph "String-Based (Planning)"
        EXPRSTR["Expr<'static, String>"]
SCALARSTR["ScalarExpr<String>"]
FILTERSTR["Filter<'static, String>"]
end
    
    subgraph "FieldId-Based (Execution)"
        EXPRFID["Expr<'static, FieldId>"]
SCALARFID["ScalarExpr<FieldId>"]
FILTERFID["Filter<'static, FieldId>"]
end
    
    EXPR -.instantiated as.-> EXPRSTR
    EXPR -.instantiated as.-> EXPRFID
    SCALAR -.instantiated as.-> SCALARSTR
    SCALAR -.instantiated as.-> SCALARFID
    FILTER -.instantiated as.-> FILTERSTR
    FILTER -.instantiated as.-> FILTERFID
    
    EXPRSTR ==translate_predicate==> EXPRFID
    SCALARSTR ==translate_scalar==> SCALARFID

Sources: llkv-expr/src/expr.rs:14-43 llkv-executor/src/translation/expression.rs:18-27

The generic parameter F allows the same AST structure to be used at different stages of query processing, with type safety enforcing that planning-phase expressions cannot be mixed with execution-phase expressions.

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

Translation Functions

The llkv-executor crate provides two primary translation functions that recursively transform expression trees.

translate_predicate

Translates boolean predicate expressions (Expr<String> → Expr<FieldId>).

Predicate Translation Flow

Sources: llkv-executor/src/translation/expression.rs:18-174

Function Signature:

The function accepts:

• expr: The predicate expression with string column references
• schema: The table schema for column name resolution
• unknown_column: Error constructor for unresolved column names

Sources: llkv-executor/src/translation/expression.rs:18-27

translate_scalar

Translates scalar value expressions (ScalarExpr<String> → ScalarExpr<FieldId>).

Function Signature:

Sources: llkv-executor/src/translation/expression.rs:176-185

Variant-Specific Translation

The translation process handles each expression variant differently:

Sources: llkv-executor/src/translation/expression.rs:86-143 llkv-executor/src/translation/expression.rs:197-386

graph TD
    START["Column Name String"]
ROWID_CHECK{"Is 'rowid'\n(case-insensitive)?"}
ROWID["Return\nROW_ID_FIELD_ID"]
LOOKUP["schema.resolve(name)"]
FOUND{"Found in\nschema?"}
RETURN_FID["Return\ncolumn.field_id"]
ERROR["Invoke\nunknown_column\ncallback"]
START --> ROWID_CHECK
 
   ROWID_CHECK -->|Yes| ROWID
 
   ROWID_CHECK -->|No| LOOKUP
 
   LOOKUP --> FOUND
 
   FOUND -->|Yes| RETURN_FID
 
   FOUND -->|No| ERROR

Field Resolution

The core of translation is resolving string column names to numeric field identifiers.

Field Resolution Logic

Sources: llkv-executor/src/translation/expression.rs:390-407

Special Column: rowid

The system provides a special pseudo-column named rowid that references the internal row identifier:

The rowid column is:

• Case-insensitive (accepts "ROWID", "rowid", "RowId", etc.)
• Available in all tables automatically
• Mapped to constant ROW_ID_FIELD_ID from llkv_table::ROW_ID_FIELD_ID
• Corresponds to ROW_ID_COLUMN_NAME constant from llkv_column_map::ROW_ID_COLUMN_NAME

Sources: llkv-executor/src/translation/expression.rs:399-401 llkv-executor/src/translation/expression.rs2 llkv-executor/src/translation/expression.rs5

Schema Lookup

For non-special columns, resolution uses the ExecutorSchema::resolve method:

The schema lookup:

1. Searches for a column with the given name
2. Returns the ExecutorColumn if found
3. Extracts the field_id from the column metadata
4. Invokes the error callback if not found

Sources: llkv-executor/src/translation/expression.rs:403-406

graph TB
    START["Initial Expression"]
PUSH_ENTER["Push Enter Frame"]
POP["Pop Frame"]
FRAME_TYPE{"Frame Type?"}
ENTER_NODE["Enter Node"]
NODE_TYPE{"Node Type?"}
AND_OR["And/Or"]
NOT["Not"]
LEAF["Leaf (Pred,\nCompare, etc.)"]
PUSH_EXIT["Push Exit Frame"]
PUSH_CHILDREN["Push Child\nEnter Frames\n(reversed)"]
PUSH_EXIT_NOT["Push Exit Frame"]
PUSH_INNER["Push Inner\nEnter Frame"]
TRANSLATE_LEAF["Translate Leaf\nPush to result_stack"]
EXIT_NODE["Exit Node"]
POP_RESULTS["Pop child results\nfrom result_stack"]
BUILD_NODE["Build translated\nparent node"]
PUSH_RESULT["Push to result_stack"]
DONE{"Stack\nempty?"}
RETURN["Return final result"]
START --> PUSH_ENTER
 
   PUSH_ENTER --> POP
 
   POP --> FRAME_TYPE
    
 
   FRAME_TYPE -->|Enter| ENTER_NODE
 
   FRAME_TYPE -->|Exit| EXIT_NODE
 
   FRAME_TYPE -->|Leaf| TRANSLATE_LEAF
    
 
   ENTER_NODE --> NODE_TYPE
 
   NODE_TYPE --> AND_OR
 
   NODE_TYPE --> NOT
 
   NODE_TYPE --> LEAF
    
 
   AND_OR --> PUSH_EXIT
 
   PUSH_EXIT --> PUSH_CHILDREN
 
   PUSH_CHILDREN --> POP
    
 
   NOT --> PUSH_EXIT_NOT
 
   PUSH_EXIT_NOT --> PUSH_INNER
 
   PUSH_INNER --> POP
    
 
   LEAF --> TRANSLATE_LEAF
 
   TRANSLATE_LEAF --> POP
    
 
   EXIT_NODE --> POP_RESULTS
 
   POP_RESULTS --> BUILD_NODE
 
   BUILD_NODE --> PUSH_RESULT
 
   PUSH_RESULT --> POP
    
 
   POP --> DONE
 
   DONE -->|No| FRAME_TYPE
 
   DONE -->|Yes| RETURN

Traversal Strategy

Translation uses an iterative traversal approach to avoid stack overflow on deeply nested expressions.

Iterative Traversal Algorithm

Sources: llkv-executor/src/translation/expression.rs:39-174

Frame-Based Pattern

The translation uses a frame-based traversal pattern with two stacks:

Work Stack (owned_stack): Contains frames representing work to be done

• OwnedFrame::Enter(expr): Visit a node and potentially expand it
• OwnedFrame::Exit(context): Collect child results and build parent node
• OwnedFrame::Leaf(translated): Push a fully translated leaf node

Result Stack (result_stack): Contains translated expressions ready to be consumed by parent nodes

Sources: llkv-executor/src/translation/expression.rs:48-63

Traversal Example

For the expression And([Pred(name_col), Pred(age_col)]):