Overview

Loading…

Overview

Relevant source files

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

Purpose and Scope

LLKV is an embedded SQL database system implemented in Rust that combines Apache Arrow’s columnar memory format with a key-value storage backend. This document provides a high-level introduction to the system architecture, component organization, and core data flows.

For detailed information about specific subsystems, see:

• Architecture and component organization : Architecture
• SQL query processing : SQL Interface and Query Planning
• Storage implementation : Storage Layer
• Metadata management : Catalog and Metadata Management

System Architecture

LLKV is organized as a Rust workspace containing 15 specialized crates that form a layered architecture. The system processes SQL queries through multiple stages—parsing, planning, execution—before ultimately persisting data in a memory-mapped key-value store.

graph TB
    subgraph "User Interface"
        SqlEngine["SqlEngine\n(llkv-sql)"]
PreparedStatement["PreparedStatement"]
end
    
    subgraph "Query Processing"
        Parser["SQL Parser\n(sqlparser-rs)"]
Planner["Query Planner\n(llkv-plan)"]
ExprSystem["Expression System\n(llkv-expr)"]
end
    
    subgraph "Execution"
        QueryExecutor["QueryExecutor\n(llkv-executor)"]
RuntimeEngine["RuntimeEngine\n(llkv-runtime)"]
Aggregate["AggregateAccumulator\n(llkv-aggregate)"]
Join["Hash Join\n(llkv-join)"]
end
    
    subgraph "Data Management"
        Table["Table\n(llkv-table)"]
SysCatalog["SysCatalog\nTable ID = 0"]
Scanner["Scanner\n(llkv-scan)"]
TxManager["TransactionManager\n(llkv-transaction)"]
end
    
    subgraph "Storage"
        ColumnStore["ColumnStore\n(llkv-column-map)"]
ArrowBatches["RecordBatch\nArrow Arrays"]
Pager["Pager Trait\n(llkv-storage)"]
end
    
    subgraph "Persistence"
        SimdRDrive["simd-r-drive\nMemory-Mapped K-V"]
EntryHandle["EntryHandle\nByte Blobs"]
end
    
 
   SqlEngine --> Parser
 
   Parser --> Planner
 
   Planner --> ExprSystem
 
   Planner --> QueryExecutor
 
   QueryExecutor --> RuntimeEngine
 
   QueryExecutor --> Aggregate
 
   QueryExecutor --> Join
 
   RuntimeEngine --> Table
 
   RuntimeEngine --> TxManager
 
   Table --> SysCatalog
 
   Table --> Scanner
 
   Scanner --> ColumnStore
 
   ColumnStore --> ArrowBatches
 
   ColumnStore --> Pager
 
   Pager --> SimdRDrive
 
   SimdRDrive --> EntryHandle
    
    style SqlEngine fill:#e8e8e8
    style ColumnStore fill:#e8e8e8
    style SimdRDrive fill:#e8e8e8

Layered Architecture

Diagram: End-to-End System Layering

The system flows from SQL text at the top through progressive layers of abstraction down to persistent storage. Each layer is implemented as one or more dedicated crates with well-defined responsibilities.

Sources: Cargo.toml:1-109 llkv-sql/src/sql_engine.rs:1-100 llkv-executor/src/lib.rs:1-100

Workspace Structure

The LLKV workspace is divided into 15 crates, each handling a specific concern. The following diagram maps crate names to their primary responsibilities:

Diagram: Crate Dependency Structure

graph LR
    subgraph "Foundation"
        types["llkv-types\nShared types\nLogicalFieldId"]
result["llkv-result\nError handling\nError enum"]
storage["llkv-storage\nPager trait\nMemPager"]
end
    
    subgraph "Expression & Planning"
        expr["llkv-expr\nExpression AST\nScalarExpr, Expr"]
plan["llkv-plan\nQuery plans\nSelectPlan, InsertPlan"]
end
    
    subgraph "Execution"
        executor["llkv-executor\nQuery execution\nQueryExecutor"]
compute["llkv-compute\nCompute kernels\nNumericKernels"]
aggregate["llkv-aggregate\nAggregation\nAggregateAccumulator"]
join["llkv-join\nJoin ops\nhash_join"]
scan["llkv-scan\nTable scans\nScanner"]
end
    
    subgraph "Data Management"
        table["llkv-table\nTable abstraction\nTable, SysCatalog"]
colmap["llkv-column-map\nColumn store\nColumnStore"]
transaction["llkv-transaction\nMVCC\nTransactionManager"]
end
    
    subgraph "User Interface"
        sql["llkv-sql\nSQL engine\nSqlEngine"]
runtime["llkv-runtime\nRuntime engine\nRuntimeEngine"]
end
    
    subgraph "Utilities"
        csv["llkv-csv\nCSV import/export"]
threading["llkv-threading\nThread pool"]
testutils["llkv-test-utils\nTest helpers"]
slttester["llkv-slt-tester\nSQLite test harness"]
end
    
 
   types -.-> expr
 
   types -.-> storage
 
   types -.-> table
 
   result -.-> storage
 
   result -.-> table
 
   storage -.-> colmap
 
   expr -.-> plan
 
   expr -.-> compute
 
   plan -.-> executor
 
   colmap -.-> table
 
   table -.-> executor
 
   executor -.-> runtime
 
   runtime -.-> sql

This diagram shows the primary dependency flow between crates. Foundation crates (llkv-types, llkv-result, llkv-storage) provide shared infrastructure. Middle layers handle query planning and execution. Top layers expose the SQL interface.

Sources: Cargo.toml:2-26 Cargo.toml:37-96

Key Components

SQL Interface Layer

The SqlEngine struct in llkv-sql is the primary entry point for executing SQL statements. It handles statement parsing, preprocessing, and orchestrates execution through the runtime layer.

Diagram: SQL Interface Entry Points

graph TD
    User["Application Code"]
SqlEngine["SqlEngine::new(pager)"]
Execute["SqlEngine::execute(sql)"]
Sql["SqlEngine::sql(sql)"]
Prepare["SqlEngine::prepare(sql)"]
User --> SqlEngine
 
   SqlEngine --> Execute
 
   SqlEngine --> Sql
 
   SqlEngine --> Prepare
    
 
   Execute --> Parse["parse_sql_with_recursion_limit"]
Parse --> Preprocess["preprocess_sql_input"]
Preprocess --> BuildPlan["build_*_plan methods"]
BuildPlan --> RuntimeExec["RuntimeEngine::execute_statement"]
Sql --> Execute
 
   Prepare --> PreparedStatement["PreparedStatement"]

The SqlEngine provides three primary methods: execute() for mixed statements, sql() for SELECT queries returning RecordBatch results, and prepare() for parameterized statements.

Sources: llkv-sql/src/sql_engine.rs:440-486 llkv-sql/src/sql_engine.rs:1045-1134 llkv-sql/src/sql_engine.rs:1560-1612

Query Planning

The llkv-plan crate transforms parsed SQL AST into executable plans. Key plan types include:

Sources: [llkv-plan crate referenced in llkv-executor/src/lib.rs31-35](https://github.com/jzombie/rust-llkv/blob/89777726/llkv-plan crate referenced in llkv-executor/src/lib.rs#L31-L35)

Expression System

The llkv-expr crate defines two core expression types:

• Expr<F>: Boolean predicate expressions for filtering (used in WHERE clauses)
• ScalarExpr<F>: Scalar value expressions for projections and computations

Both are generic over field identifier type F, allowing translation from string column names to numeric FieldId identifiers.

Sources: llkv-executor/src/lib.rs:23-26

graph TB
    subgraph "Logical Layer"
        RecordBatch["RecordBatch\nArrow columnar format"]
Schema["Schema\nColumn definitions"]
end
    
    subgraph "Column Store Layer"
        ColumnStore["ColumnStore"]
ColumnDescriptor["ColumnDescriptor\nLinked list of chunks"]
ChunkMetadata["ChunkMetadata\nmin, max, size, nulls"]
end
    
    subgraph "Physical Layer"
        Pager["Pager trait\nbatch_get, batch_put"]
MemPager["MemPager"]
SimdRDrive["simd-r-drive\nMemory-mapped storage"]
end
    
    subgraph "Persistence"
        EntryHandle["EntryHandle\nByte blob references"]
PhysicalKeys["Physical keys (u64)"]
end
    
 
   RecordBatch --> ColumnStore
 
   Schema --> ColumnStore
 
   ColumnStore --> ColumnDescriptor
 
   ColumnDescriptor --> ChunkMetadata
 
   ColumnDescriptor --> Pager
 
   Pager --> MemPager
 
   Pager --> SimdRDrive
 
   MemPager --> EntryHandle
 
   SimdRDrive --> EntryHandle
 
   EntryHandle --> PhysicalKeys

Storage Architecture

LLKV stores data in a columnar format using Apache Arrow, persisted through a key-value storage backend:

Diagram: Storage Architecture Layers

Arrow RecordBatches are decomposed into individual column chunks, each serialized and stored via the Pager trait. The simd-r-drive backend provides memory-mapped, SIMD-optimized key-value operations.

Sources: Cargo.lock:126-143 Cargo.lock:671-687 [llkv-column-map references in llkv-executor/src/lib.rs20](https://github.com/jzombie/rust-llkv/blob/89777726/llkv-column-map references in llkv-executor/src/lib.rs#L20-L20)

Query Execution Flow

The following diagram traces a SELECT query through the execution pipeline:

Diagram: SELECT Query Execution Sequence

Query execution proceeds in two phases: (1) filter evaluation to collect matching row IDs, and (2) column gathering to assemble the final RecordBatch. Metadata-based chunk pruning optimizes filter evaluation by skipping chunks that cannot contain matching rows.

Sources: llkv-sql/src/sql_engine.rs:1596-1612 llkv-executor/src/lib.rs:519-563

Data Model

Tables and Schemas

Every table in LLKV has:

• A unique numeric table_id
• A Schema defining column names, types, and nullability
• Optional constraints (primary key, foreign keys, unique, check)
• Optional indexes (single-column and multi-column)

graph TB
    SysCatalog["SysCatalog (Table 0)"]
TableMeta["TableMeta records"]
ColMeta["ColMeta records"]
IndexMeta["Index metadata"]
ConstraintMeta["Constraint records"]
TriggerMeta["Trigger definitions"]
SysCatalog --> TableMeta
 
   SysCatalog --> ColMeta
 
   SysCatalog --> IndexMeta
 
   SysCatalog --> ConstraintMeta
 
   SysCatalog --> TriggerMeta
    
    UserTable1["User Table 1"]
UserTable2["User Table 2"]
TableMeta -.describes.-> UserTable1
    TableMeta -.describes.-> UserTable2
    ColMeta -.describes.-> UserTable1
    ColMeta -.describes.-> UserTable2

System Catalog

Table ID 0 is reserved for the SysCatalog, a special table that stores metadata about all other tables, columns, indexes, triggers, and constraints. The catalog is self-describing—it uses the same columnar storage as user tables.

Diagram: System Catalog Structure

All DDL operations (CREATE TABLE, ALTER TABLE, etc.) modify the system catalog. At startup, the catalog is read to reconstruct the complete database schema.

Sources: [llkv-sql/src/sql_engine.rs references to SysCatalog](https://github.com/jzombie/rust-llkv/blob/89777726/llkv-sql/src/sql_engine.rs references to SysCatalog)

Columnar Storage

Data is stored column-wise using Apache Arrow’s in-memory format, with each column divided into chunks. Each chunk contains:

• Serialized Arrow array data
• Row ID bitmap (which rows are present)
• Metadata (min/max values, null count, size)

This organization enables:

• Efficient predicate pushdown (skip chunks via min/max)
• Vectorized operations on decompressed data
• Compaction (merging small chunks)

Sources: [llkv-executor/src/lib.rs references to ColumnStore and RecordBatch](https://github.com/jzombie/rust-llkv/blob/89777726/llkv-executor/src/lib.rs references to ColumnStore and RecordBatch)

Transaction Support

LLKV implements Multi-Version Concurrency Control (MVCC) using hidden columns:

The TransactionManager in llkv-transaction coordinates transaction boundaries and assigns transaction IDs. Queries automatically filter rows based on the current transaction’s visibility rules.

Sources: [llkv-transaction crate in Cargo.toml24](https://github.com/jzombie/rust-llkv/blob/89777726/llkv-transaction crate in Cargo.toml#L24-L24)

External Dependencies

LLKV relies on several external crates for core functionality:

Sources: Cargo.toml:40-49 Cargo.lock:126-143 Cargo.lock:671-687

Usage Example

Sources: llkv-sql/src/sql_engine.rs:443-485

Summary

LLKV is a layered SQL database system that marries Apache Arrow’s columnar format with key-value storage. The architecture separates concerns across 15 crates, enabling modular development and testing. Queries flow from SQL text through parsing, planning, and execution stages before accessing columnar data persisted in a memory-mapped store. The system supports transactions, indexes, constraints, and SQL features including joins, aggregations, and subqueries.

For deeper exploration of specific subsystems, consult the following sections:

• Architecture - Detailed crate organization and dependencies
• SQL Interface - SQL preprocessing and dialect handling
• Query Execution - Execution strategies and optimizations
• Storage Layer - Column store implementation details
• Catalog and Metadata Management - Schema management and type system

Sources: Cargo.toml:1-109 llkv-sql/src/sql_engine.rs:1-100 llkv-executor/src/lib.rs:1-100

Dismiss

Refresh this wiki

Enter email to refresh

Architecture

Loading…

Architecture

Relevant source files

• .github/workflows/build.docs.yml
• Cargo.lock
• Cargo.toml
• demos/llkv-sql-pong-demo/assets/llkv-sql-pong-screenshot.png
• dev-docs/doc-preview.md
• llkv-executor/Cargo.toml
• llkv-join/Cargo.toml
• llkv-plan/Cargo.toml
• llkv-sql/Cargo.toml
• llkv-table/Cargo.toml
• llkv-test-utils/Cargo.toml

This page describes the overall architectural design of LLKV, including the layered system structure, key design decisions, and how major components interact. For detailed information about individual crates and their responsibilities, see Workspace and Crates. For the end-to-end query execution flow, see SQL Query Processing Pipeline. For details on Arrow integration and data representation, see Data Formats and Arrow Integration.

Architectural Overview

LLKV is a columnar SQL database that stores Apache Arrow data structures directly in a key-value persistence layer. The architecture consists of six distinct layers, each implemented as one or more Rust crates. The system translates SQL statements into query plans, executes those plans against columnar table storage, and persists data using memory-mapped key-value stores.

The core architectural innovation is the llkv-column-map layer, which bridges Apache Arrow’s in-memory columnar format with the simd-r-drive key-value storage backend. This design enables zero-copy operations on columnar data while maintaining ACID properties through the underlying storage engine.

Sources: Cargo.toml:1-109 high-level overview diagrams

System Layers

The following diagram shows the six architectural layers with their implementing crates and key data structures:

graph TB
    subgraph "Layer 1: User Interface"
        SQL["llkv-sql\nSqlEngine"]
DEMO["llkv-sql-pong-demo"]
TPCH["llkv-tpch"]
CSV["llkv-csv"]
end
    
    subgraph "Layer 2: Query Processing"
        PARSER["sqlparser-rs\nParser, Statement"]
PLANNER["llkv-plan\nSelectPlan, InsertPlan"]
EXPR["llkv-expr\nExpr, ScalarExpr"]
end
    
    subgraph "Layer 3: Execution"
        EXECUTOR["llkv-executor\nTableExecutor"]
RUNTIME["llkv-runtime\nDatabaseRuntime"]
AGGREGATE["llkv-aggregate\nAccumulator"]
JOIN["llkv-join\nhash_join"]
COMPUTE["llkv-compute\nNumericKernels"]
end
    
    subgraph "Layer 4: Data Management"
        TABLE["llkv-table\nTable, SysCatalog"]
TRANSACTION["llkv-transaction\nTransaction"]
SCAN["llkv-scan\nScanOp"]
end
    
    subgraph "Layer 5: Storage - Arrow Native"
        COLMAP["llkv-column-map\nColumnStore, ColumnDescriptor"]
STORAGE["llkv-storage\nPager trait"]
ARROW["arrow-array\nRecordBatch, ArrayRef"]
end
    
    subgraph "Layer 6: Persistence - Key-Value"
        PAGER["Pager implementations\nbatch_get, batch_put"]
SIMD["simd-r-drive\nRDrive, EntryHandle"]
end
    
 
   SQL --> PARSER
 
   PARSER --> PLANNER
 
   PLANNER --> EXPR
 
   EXPR --> EXECUTOR
    
 
   EXECUTOR --> AGGREGATE
 
   EXECUTOR --> JOIN
 
   EXECUTOR --> COMPUTE
 
   EXECUTOR --> RUNTIME
    
 
   RUNTIME --> TABLE
 
   RUNTIME --> TRANSACTION
 
   TABLE --> SCAN
    
 
   SCAN --> COLMAP
 
   TABLE --> COLMAP
 
   COLMAP --> ARROW
 
   COLMAP --> STORAGE
    
 
   STORAGE --> PAGER
 
   PAGER --> SIMD

Each layer has well-defined responsibilities. Layer 1 provides user-facing interfaces. Layer 2 translates SQL into executable plans. Layer 3 executes those plans using specialized operators. Layer 4 manages logical tables and transactions. Layer 5 implements columnar storage using Arrow data structures. Layer 6 provides persistent key-value storage with memory-mapping.

Sources: Cargo.toml:2-26 llkv-sql/Cargo.toml:1-45 llkv-executor/Cargo.toml:1-48 llkv-table/Cargo.toml:1-72

Key Architectural Decisions

Arrow-Native Columnar Storage

The system uses Apache Arrow as its native in-memory data format. All data is represented as RecordBatch instances containing ArrayRef columns. This design decision enables:

• Zero-copy interoperability with Arrow-based analytics tools
• Vectorized computation using Arrow kernels
• Efficient memory layouts for SIMD operations
• Type-safe column operations through Arrow’s schema system

The arrow dependency (version 57.1.0) provides the foundation for all data operations.

Key-Value Persistence Backend

Rather than implementing a custom storage engine, LLKV persists data through the Pager trait abstraction defined in llkv-storage. The primary implementation uses simd-r-drive (version 0.15.5-alpha), a memory-mapped key-value store with SIMD-optimized operations.

This design separates logical data management from physical storage concerns. The Pager trait defines operations:

• alloc() - allocate new storage keys
• batch_get() - retrieve multiple values
• batch_put() - atomically write multiple key-value pairs
• free() - release storage keys

Modular Crate Organization

The workspace contains 15+ specialized crates, each focused on a specific concern. This modularity enables:

• Independent testing and benchmarking per crate
• Clear dependency boundaries
• Parallel development across subsystems
• Selective feature compilation

Core crates follow a naming convention: llkv-{subsystem}. Foundational crates like llkv-types and llkv-result provide shared types and error handling used throughout the system.

MVCC Transaction Isolation

The system implements Multi-Version Concurrency Control through llkv-transaction. Each table row includes system columns created_by and deleted_by that track transaction visibility. The Transaction struct manages transaction state and visibility rules.

Sources: Cargo.toml:37-96 llkv-storage/Cargo.toml:1-48 llkv-table/Cargo.toml:20-41

Component Organization

The following diagram maps the workspace crates to their architectural roles:

Dependencies flow upward through the layers. Lower-level crates like llkv-types and llkv-storage have no dependencies on higher layers. The llkv-sql crate sits at the top, orchestrating all subsystems.

Sources: Cargo.toml:2-26 Cargo.toml:55-74

Data Flow Architecture

Data flows through the system in two primary patterns: write operations (INSERT, UPDATE, DELETE) and read operations (SELECT).

flowchart LR
 
   SQL["SQL Statement"] --> PARSE["sqlparser\nparse()"]
PARSE --> PLAN["llkv-plan\nInsertPlan"]
PLAN --> RUNTIME["DatabaseRuntime\nexecute_insert_plan()"]
RUNTIME --> TABLE["Table\nappend()"]
TABLE --> COLMAP["ColumnStore\nappend()"]
COLMAP --> CHUNK["Chunking\nLWW deduplication"]
CHUNK --> SERIAL["Serialize\nArrow arrays"]
SERIAL --> PAGER["Pager\nbatch_put()"]
PAGER --> KV["simd-r-drive\nEntryHandle"]

Write Path

Write operations follow a path from SQL parsing through plan creation, runtime execution, table operations, column store append, chunking/deduplication, serialization, and finally persistence via the Pager trait.

flowchart LR
 
   SQL["SQL Statement"] --> PARSE["sqlparser\nparse()"]
PARSE --> PLAN["llkv-plan\nSelectPlan"]
PLAN --> EXECUTOR["TableExecutor\nexecute_select()"]
EXECUTOR --> FILTER["Phase 1:\nfilter_row_ids()"]
FILTER --> GATHER["Phase 2:\ngather_rows()"]
GATHER --> COLMAP["ColumnStore\ngather()"]
COLMAP --> PAGER["Pager\nbatch_get()"]
PAGER --> DESER["Deserialize\nArrow arrays"]
DESER --> BATCH["RecordBatch\nassembly"]
BATCH --> RESULT["Query Results"]

The ColumnStore::append() method implements Last-Write-Wins semantics for upserts by detecting duplicate row IDs and replacing older values.

Read Path

Read operations use a two-phase approach: first collecting matching row IDs via predicate evaluation, then gathering column data for those rows. This minimizes data movement by filtering before gathering.

Sources: llkv-sql/Cargo.toml:20-38 llkv-executor/Cargo.toml:20-42 llkv-table/Cargo.toml:20-41

Storage Architecture: Arrow to Key-Value Bridge

The llkv-column-map crate implements the critical bridge between Arrow’s columnar format and key-value storage:

graph TB
    subgraph "Logical Layer"
        FIELD["LogicalFieldId\n(table_id, field_name)"]
ROWID["RowId\n(u64)"]
end
    
    subgraph "Column Organization"
        CATALOG["ColumnCatalog\nfield_id → ColumnDescriptor"]
DESC["ColumnDescriptor\nlinked list of chunks"]
META["ChunkMetadata\n(min, max, size, null_count)"]
end
    
    subgraph "Physical Storage"
        CHUNK["Data Chunks\nserialized Arrow arrays"]
RIDARRAY["RowId Arrays\nsorted u64 arrays"]
PKEY["Physical Keys\n(chunk_pk, rid_pk)"]
end
    
    subgraph "Key-Value Layer"
        ENTRY["EntryHandle\nbyte blobs"]
MMAP["Memory-Mapped Files"]
end
    
 
   FIELD --> CATALOG
 
   CATALOG --> DESC
 
   DESC --> META
 
   META --> CHUNK
 
   CHUNK --> PKEY
 
   DESC --> RIDARRAY
 
   RIDARRAY --> PKEY
 
   PKEY --> ENTRY
 
   ENTRY --> MMAP
    
    ROWID -.used for.-> RIDARRAY

The ColumnCatalog maps logical field identifiers to physical storage. Each column is represented by a ColumnDescriptor that maintains a linked list of data chunks. Each chunk contains:

• A serialized Arrow array (the actual column data)
• A corresponding sorted array of row IDs
• Metadata including min/max values for predicate pushdown
• Physical keys (chunk_pk, rid_pk) pointing to storage

The ChunkMetadata enables chunk pruning during scans: chunks whose min/max ranges don’t overlap with query predicates can be skipped entirely.

Data chunks are stored as serialized byte blobs accessed through EntryHandle instances from simd-r-drive. The storage layer uses memory-mapped files for efficient I/O.

Sources: llkv-column-map/Cargo.toml:1-65 llkv-storage/Cargo.toml:1-48 Cargo.toml:85-86

System Catalog

The system catalog (table ID 0) stores metadata about all tables, columns, indexes, and constraints. It is itself stored in the same ColumnStore as user data, creating a self-describing bootstrapped system.

The SysCatalog struct provides typed access to catalog tables. The CatalogManager coordinates table lifecycle operations (CREATE, ALTER, DROP) by manipulating catalog entries.

Table ID ranges partition the namespace:

• ID 0: System catalog
• IDs 1-999: User tables
• IDs 1000+: Information schema views
• IDs 10000+: Temporary tables

This design allows the catalog to leverage the same storage, transaction, and query infrastructure as user data.

Sources: llkv-table/Cargo.toml:20-41

Dismiss

Refresh this wiki

Enter email to refresh

Workspace and Crates

Loading…

Workspace and Crates

Relevant source files

• .github/workflows/build.docs.yml
• Cargo.lock
• Cargo.toml
• demos/llkv-sql-pong-demo/assets/llkv-sql-pong-screenshot.png
• dev-docs/doc-preview.md
• llkv-executor/Cargo.toml
• llkv-join/Cargo.toml
• llkv-plan/Cargo.toml
• llkv-sql/Cargo.toml
• llkv-table/Cargo.toml
• llkv-test-utils/Cargo.toml

Purpose and Scope

This document describes the modular workspace structure of the LLKV codebase, detailing the 22 crates that comprise the system, their responsibilities, and interdependencies. Each crate serves a specific architectural layer, enabling separation of concerns and independent development. For information about the overall system architecture and how these crates fit into the layered design, see Architecture. For details about specific subsystems like SQL processing or storage, refer to the respective sections in the table of contents.

Sources: Cargo.toml:1-109

Workspace Configuration

LLKV uses a Cargo workspace to manage multiple interdependent crates under a unified build system. The workspace is configured with resolver = "2", enabling the newer dependency resolver that provides more predictable builds across different platforms and feature combinations.

All workspace members share common metadata including version 0.8.5-alpha, Apache-2.0 license, and Rust edition 2024. Workspace-level lints enforce quality standards, prohibiting print statements to stdout/stderr and disallowing specific methods like Box::leak.

Sources: Cargo.toml:2-28 Cargo.toml:29-35 Cargo.toml:98-104

Crate Dependency Architecture

Sources: Cargo.toml:37-96 llkv-table/Cargo.toml:20-40 llkv-executor/Cargo.toml:20-41 llkv-sql/Cargo.toml:20-37

Foundation Crates

llkv-types

The llkv-types crate provides the shared type system used throughout LLKV. It defines fundamental data types, field identifiers, and type conversions that enable type-safe operations across all layers. This crate has no internal LLKV dependencies, making it the true foundation upon which other crates build.

Purpose: Shared type definitions and type system infrastructure
Key Exports: Type enums, field identifiers, type conversion utilities
Internal Dependencies: None
External Dependencies: Minimal (bitcode, serde)

Sources: Cargo.toml74 llkv-table/Cargo.toml33 llkv-executor/Cargo.toml35

llkv-result

The llkv-result crate defines error types and result handling patterns used throughout the system. It provides a unified error type hierarchy that enables precise error reporting and recovery across all subsystem boundaries.

Purpose: Centralized error handling and result types
Key Exports: LlkvResult type alias, error enums
Internal Dependencies: None
External Dependencies: thiserror (for error derivation)

Sources: Cargo.toml64 llkv-table/Cargo.toml30 llkv-executor/Cargo.toml30

llkv-storage

The llkv-storage crate abstracts the underlying key-value storage layer through the Pager trait. It provides batch operations (batch_get, batch_put, alloc, free) that enable efficient bulk access to the persistent storage backend. When the simd-r-drive-support feature is enabled, it provides an implementation using the SIMD-optimized memory-mapped key-value store.

Purpose: Storage abstraction layer and pager interface
Key Exports: Pager trait, storage implementations
Internal Dependencies: llkv-types, llkv-result
External Dependencies: simd-r-drive (conditional)

Sources: Cargo.toml69 llkv-table/Cargo.toml32 llkv-sql/Cargo.toml29

Data Management Crates

llkv-column-map

The llkv-column-map crate implements the Arrow-native columnar storage engine. It manages data organized in chunks with metadata (min/max values, null counts) and provides operations like append (with Last-Write-Wins semantics), gather (row ID to RecordBatch assembly), filtering, and compaction. The ColumnStore and ColumnCatalog types bridge Apache Arrow’s in-memory format with the persistent key-value backend.

Purpose: Columnar data storage with Arrow integration
Key Exports: ColumnStore, ColumnCatalog, ColumnDescriptor
Internal Dependencies: llkv-types, llkv-storage
External Dependencies: arrow, croaring (for bitmap indexes)

Sources: Cargo.toml57 llkv-table/Cargo.toml26 llkv-executor/Cargo.toml25 llkv-sql/Cargo.toml22

llkv-table

The llkv-table crate provides the Table abstraction that represents a logical table with a schema. It integrates the columnar storage with catalog management, MVCC column injection, and scan operations. The SysCatalog within this crate stores metadata about all tables (Table 0 stores information about Tables 1+). The CatalogManager handles table lifecycle operations including create, alter, and drop.

Purpose: Table abstraction, catalog management, and metadata storage
Key Exports: Table, SysCatalog, CatalogManager, TableMeta, ColMeta
Internal Dependencies: llkv-types, llkv-result, llkv-storage, llkv-column-map, llkv-expr, llkv-scan, llkv-compute, llkv-plan
External Dependencies: arrow, arrow-array, arrow-schema, bitcode

Sources: Cargo.toml70 llkv-table/Cargo.toml:1-72 llkv-executor/Cargo.toml33 llkv-sql/Cargo.toml30

llkv-scan

The llkv-scan crate implements table scanning operations with predicate evaluation. It provides efficient row filtering using vectorized operations and bitmap indexes, enabling predicate pushdown to minimize data movement during query execution.

Purpose: Table scan operations and predicate evaluation
Key Exports: Scan iterators, filter evaluation functions
Internal Dependencies: llkv-types, llkv-column-map, llkv-expr
External Dependencies: arrow, croaring

Sources: Cargo.toml66 llkv-table/Cargo.toml31 llkv-executor/Cargo.toml31 llkv-plan/Cargo.toml26

Expression and Computation Crates

llkv-expr

The llkv-expr crate defines the expression Abstract Syntax Tree (AST) used throughout query processing. It includes Expr for general expressions and ScalarExpr for scalar computations. The crate provides expression translation (string column names to FieldId identifiers), compilation into bytecode (EvalProgram, DomainProgram), and optimization passes.

Purpose: Expression AST, translation, and compilation
Key Exports: Expr, ScalarExpr, EvalProgram, expression translators
Internal Dependencies: llkv-types, llkv-result
External Dependencies: arrow, time (for date/time handling)

Sources: Cargo.toml61 llkv-table/Cargo.toml28 llkv-executor/Cargo.toml27 llkv-sql/Cargo.toml25 llkv-plan/Cargo.toml24

llkv-compute

The llkv-compute crate implements vectorized compute kernels for scalar expression evaluation. It provides the NumericKernels system for optimized arithmetic, comparison, and logical operations on Arrow arrays. These kernels leverage SIMD instructions where possible for high-performance data processing.

Purpose: Vectorized compute kernels for expression evaluation
Key Exports: NumericKernels, scalar evaluation functions
Internal Dependencies: llkv-types, llkv-expr
External Dependencies: arrow

Sources: Cargo.toml58 llkv-table/Cargo.toml27 llkv-executor/Cargo.toml26 llkv-sql/Cargo.toml23 llkv-plan/Cargo.toml23

Query Processing Crates

llkv-plan

The llkv-plan crate converts SQL Abstract Syntax Trees (from sqlparser-rs) into executable query plans. It defines plan structures including SelectPlan, InsertPlan, UpdatePlan, DeletePlan, and DDL plans. The planner handles subquery correlation tracking, expression binding, and plan optimization.

Purpose: SQL-to-plan conversion and query planning
Key Exports: SelectPlan, InsertPlan, plan builder types
Internal Dependencies: llkv-types, llkv-result, llkv-expr, llkv-compute, llkv-scan, llkv-storage, llkv-column-map
External Dependencies: arrow, sqlparser, regex, time

Sources: Cargo.toml63 llkv-plan/Cargo.toml:1-42 llkv-executor/Cargo.toml29 llkv-sql/Cargo.toml26

llkv-executor

The llkv-executor crate executes query plans to produce results. It implements the TablePlanner and TableExecutor that optimize and execute table-level operations, including full table scans, filtered scans, aggregations, joins, and sorting. The executor uses parallel processing (via rayon) where beneficial and provides streaming result iteration.

Purpose: Query plan execution engine
Key Exports: TableExecutor, TablePlanner, execution functions
Internal Dependencies: llkv-types, llkv-result, llkv-expr, llkv-compute, llkv-plan, llkv-scan, llkv-table, llkv-storage, llkv-column-map, llkv-aggregate, llkv-join, llkv-threading
External Dependencies: arrow, rayon, croaring

Sources: Cargo.toml60 llkv-executor/Cargo.toml:1-47 llkv-sql/Cargo.toml24

llkv-aggregate

The llkv-aggregate crate implements aggregate function evaluation for GROUP BY queries. It provides accumulators for functions like SUM, AVG, COUNT, MIN, MAX, and handles DISTINCT aggregation using bitmap sets. The aggregation engine supports both hash-based and sort-based strategies.

Purpose: Aggregate function evaluation and accumulation
Key Exports: Accumulator types, aggregation operators
Internal Dependencies: llkv-types, llkv-expr, llkv-compute
External Dependencies: arrow, croaring

Sources: Cargo.toml56 llkv-executor/Cargo.toml24

llkv-join

The llkv-join crate implements table join operations using hash join algorithms. It supports INNER, LEFT, RIGHT, and FULL OUTER joins with optimizations for build/probe side selection and parallel hash table construction. The join implementation integrates with the table scan and filter systems for efficient multi-table queries.

Purpose: Table join operations and algorithms
Key Exports: Join operators, hash join implementation
Internal Dependencies: llkv-types, llkv-result, llkv-expr, llkv-table, llkv-storage, llkv-column-map, llkv-threading
External Dependencies: arrow, rayon, rustc-hash

Sources: Cargo.toml62 llkv-join/Cargo.toml:1-44 llkv-executor/Cargo.toml28

Runtime and Transaction Crates

llkv-runtime

The llkv-runtime crate provides the runtime engine that orchestrates query execution with transaction management. It integrates the executor, table management, and transaction systems, providing the high-level API for executing SQL statements within transactional contexts. The runtime manages catalog operations, schema validation, and result formatting.

Purpose: Runtime orchestration and transaction coordination
Key Exports: Runtime engine, execution context
Internal Dependencies: llkv-types, llkv-result, llkv-table, llkv-executor, llkv-transaction, llkv-storage
External Dependencies: arrow

Sources: Cargo.toml65 llkv-sql/Cargo.toml28

llkv-transaction

The llkv-transaction crate implements Multi-Version Concurrency Control (MVCC) for transactional semantics. It manages transaction identifiers, version visibility, and isolation. The system injects created_by and deleted_by columns into tables to track row versions, enabling snapshot isolation for concurrent queries.

Purpose: MVCC transaction management
Key Exports: Transaction manager, transaction ID generation
Internal Dependencies: llkv-types
External Dependencies: None (minimal)

Sources: Cargo.toml73 llkv-sql/Cargo.toml31

SQL Interface Crates

llkv-sql

The llkv-sql crate provides the primary SQL interface through the SqlEngine type. It handles SQL parsing (using sqlparser-rs), preprocessing (dialect normalization), plan building, and execution. The engine includes an INSERT buffering system that batches multiple INSERT statements for improved bulk insert performance. This is the main entry point for executing SQL statements against LLKV.

Purpose: SQL parsing, preprocessing, and execution interface
Key Exports: SqlEngine, SQL execution methods
Internal Dependencies: llkv-types, llkv-result, llkv-expr, llkv-plan, llkv-executor, llkv-runtime, llkv-table, llkv-storage, llkv-column-map, llkv-compute, llkv-transaction
External Dependencies: arrow, sqlparser, regex

Sources: Cargo.toml68 llkv-sql/Cargo.toml:1-44

Utility and Support Crates

llkv-csv

The llkv-csv crate provides utilities for importing and exporting CSV data to/from LLKV tables. It handles schema inference, data type conversion, and batch processing for efficient bulk data operations.

Purpose: CSV import/export functionality
Key Exports: CSV reader/writer utilities
Internal Dependencies: llkv-table, llkv-types
External Dependencies: arrow, csv

Sources: Cargo.toml59

llkv-test-utils

The llkv-test-utils crate provides testing utilities used across the workspace. When the auto-init feature is enabled, it automatically initializes tracing at test binary startup via the ctor crate, simplifying test debugging. This crate is marked as a development dependency in most other crates.

Purpose: Shared test utilities and test infrastructure
Key Exports: Test helpers, tracing initialization
Internal Dependencies: None
External Dependencies: tracing, tracing-subscriber, ctor (optional)

Sources: Cargo.toml71 llkv-test-utils/Cargo.toml:1-34 llkv-table/Cargo.toml45

llkv-threading

The llkv-threading crate provides threading utilities and abstractions used by parallelized operations in the executor and join crates. It wraps rayon patterns and provides consistent threading primitives across the codebase.

Purpose: Threading utilities and parallel processing abstractions
Key Exports: Thread pool management, parallel iterators
Internal Dependencies: llkv-types
External Dependencies: rayon, crossbeam-channel

Sources: Cargo.toml72 llkv-executor/Cargo.toml34 llkv-join/Cargo.toml27

Application and Demo Crates

llkv (Main Library)

The root llkv crate serves as the main library crate, aggregating and re-exporting key types and functions from the specialized crates. It provides a unified API surface for external consumers of the LLKV database system.

Purpose: Main library aggregation and public API
Key Exports: Re-exports from llkv-sql and other core crates
Internal Dependencies: llkv-sql and other workspace crates
External Dependencies: Inherited from dependencies

Sources: Cargo.toml5 Cargo.toml55

llkv-sql-pong-demo

An interactive terminal-based demonstration application that showcases LLKV’s SQL capabilities through a ping-pong game scenario. The demo creates tables, inserts data, and executes queries to demonstrate SQL functionality in an engaging way.

Purpose: Interactive SQL demonstration
Key Exports: Demo application binary
Internal Dependencies: llkv-sql
External Dependencies: crossterm (for terminal UI)

Sources: Cargo.toml4

llkv-slt-tester

The llkv-slt-tester crate implements a SQLLogicTest runner for LLKV. It executes standardized SQL test suites to verify correctness against established database behavior expectations, enabling regression testing and compatibility validation.

Purpose: SQLLogicTest execution and validation
Key Exports: Test runner binary
Internal Dependencies: llkv-sql
External Dependencies: sqllogictest, libtest-mimic

Sources: Cargo.toml67

llkv-tpch

The llkv-tpch crate implements the TPC-H benchmark suite for LLKV. It generates TPC-H schema and data, executes the 22 standard TPC-H queries, and measures performance metrics. This crate is used for performance evaluation and regression testing.

Purpose: TPC-H benchmark execution
Key Exports: Benchmark runner binary
Internal Dependencies: llkv-sql, llkv-csv
External Dependencies: tpchgen

Sources: Cargo.toml23

Workspace Dependencies Overview

The following table summarizes key external dependencies used across the workspace:

Sources: Cargo.toml:37-96

Crate Interdependency Matrix

Sources: Cargo.toml:37-96 llkv-table/Cargo.toml:20-40 llkv-executor/Cargo.toml:20-41 llkv-sql/Cargo.toml:20-37 llkv-join/Cargo.toml:20-32 llkv-plan/Cargo.toml:20-36

Build Configuration and Features

The workspace defines several build profiles and configuration options:

• resolver = “2” : Uses Cargo’s newer dependency resolver for more consistent builds
• edition = “2024” : Uses the latest Rust edition (2024)
• samply profile : Inherits from release with debug symbols enabled for profiling

Workspace lints enforce code quality by denying print statements and specific unsafe operations. Individual crates may enable conditional features like simd-r-drive-support for the storage backend.

Sources: Cargo.toml27 Cargo.toml32 Cargo.toml:98-109 llkv-sql/Cargo.toml40

Dismiss

Refresh this wiki

Enter email to refresh

SQL Query Processing Pipeline

Loading…

SQL Query Processing Pipeline

Relevant source files

• .github/workflows/build.docs.yml
• demos/llkv-sql-pong-demo/assets/llkv-sql-pong-screenshot.png
• dev-docs/doc-preview.md
• llkv-executor/src/lib.rs
• llkv-expr/src/expr.rs
• llkv-plan/Cargo.toml
• llkv-plan/src/plans.rs
• llkv-sql/Cargo.toml
• llkv-sql/src/sql_engine.rs
• llkv-test-utils/Cargo.toml

Purpose and Scope

This page describes the end-to-end flow of SQL query processing in LLKV, from raw SQL text input to Arrow RecordBatch results. It covers the major pipeline stages: parsing, preprocessing, planning, execution, and result formatting. For detailed information about specific components, see:

• SQL interface and the SqlEngine API: SQL Interface
• Plan structure details: Query Planning
• Expression translation and compilation: Expression System
• Execution implementation details: Query Execution

Pipeline Overview

The SQL query processing pipeline transforms user SQL statements through several stages before producing results:

Sources: llkv-sql/src/sql_engine.rs:1-100 [Diagram 2 from overview](https://github.com/jzombie/rust-llkv/blob/89777726/Diagram 2 from overview)

flowchart TB
    Input["SQL Text\n(User Input)"]
Preprocess["SQL Preprocessing\npreprocess_* functions"]
Parse["SQL Parsing\nsqlparser::Parser"]
AST["sqlparser::ast::Statement"]
Plan["Query Planning\nbuild_*_plan functions"]
PlanStmt["PlanStatement"]
Execute["Execution\nRuntimeEngine::execute_statement"]
Result["RuntimeStatementResult"]
Batches["Vec<RecordBatch>"]
Input --> Preprocess
 
   Preprocess --> Parse
 
   Parse --> AST
 
   AST --> Plan
 
   Plan --> PlanStmt
 
   PlanStmt --> Execute
 
   Execute --> Result
 
   Result --> Batches
    
    style Input fill:#f9f9f9
    style Batches fill:#f9f9f9

SQL Preprocessing Stage

Before parsing, LLKV applies several preprocessing transformations to normalize SQL syntax across different dialects (SQLite, DuckDB, PostgreSQL). This stage rewrites incompatible syntax into forms that sqlparser can handle.

Preprocessing Functions

The preprocessing pipeline is applied sequentially in SqlEngine::execute:

Sources: llkv-sql/src/sql_engine.rs:759-1006 llkv-sql/src/sql_engine.rs:1395-1460

Parsing Stage

After preprocessing, the SQL text is parsed using the sqlparser crate with a configurable recursion limit to handle deeply nested queries.

Parser Configuration

The parser is configured with:

• Dialect : GenericDialect (supports multiple SQL dialects)
• Recursion limit : 200 (set via PARSER_RECURSION_LIMIT constant)
• Parameter tracking : Thread-local ParameterScope for prepared statement placeholders

The parser produces a vector of sqlparser::ast::Statement objects. Each statement is then converted to a PlanStatement for execution.

Sources: llkv-sql/src/sql_engine.rs:395-400 llkv-sql/src/sql_engine.rs:1464-1481 llkv-sql/src/sql_engine.rs:223-256

Statement Type Dispatch

Once parsed, statements are dispatched to specialized planning functions based on their type. The SqlEngine maintains an optional InsertBuffer to batch consecutive literal INSERT statements for improved throughput.

Sources: llkv-sql/src/sql_engine.rs:1482-2800 llkv-sql/src/sql_engine.rs:486-547

flowchart TB
    AST["sqlparser::ast::Statement"]
Dispatch{"Statement Type"}
CreateTable["build_create_table_plan"]
DropTable["build_drop_table_plan"]
AlterTable["build_alter_table_plan"]
CreateView["build_create_view_plan"]
DropView["build_drop_view_plan"]
CreateIndex["build_create_index_plan"]
DropIndex["build_drop_index_plan"]
Reindex["build_reindex_plan"]
RenameTable["build_rename_table_plan"]
Insert["build_insert_plan"]
InsertBuffer["InsertBuffer::push_statement\n(batching optimization)"]
Update["build_update_plan"]
Delete["build_delete_plan"]
Truncate["build_truncate_plan"]
Select["build_select_plan"]
Explain["wrap in Explain plan"]
Set["handle SET statement"]
Show["handle SHOW statement"]
Begin["handle BEGIN TRANSACTION"]
Commit["handle COMMIT"]
Rollback["handle ROLLBACK"]
Savepoint["handle SAVEPOINT"]
Release["handle RELEASE"]
Vacuum["handle VACUUM"]
Pragma["handle PRAGMA"]
PlanStmt["PlanStatement"]
AST --> Dispatch
    
 
   Dispatch -->|CREATE TABLE| CreateTable
 
   Dispatch -->|DROP TABLE| DropTable
 
   Dispatch -->|ALTER TABLE| AlterTable
 
   Dispatch -->|CREATE VIEW| CreateView
 
   Dispatch -->|DROP VIEW| DropView
 
   Dispatch -->|CREATE INDEX| CreateIndex
 
   Dispatch -->|DROP INDEX| DropIndex
 
   Dispatch -->|VACUUM REINDEX| Reindex
 
   Dispatch -->|ALTER TABLE RENAME| RenameTable
    
 
   Dispatch -->|INSERT| Insert
    Insert -.may buffer.-> InsertBuffer
 
   Dispatch -->|UPDATE| Update
 
   Dispatch -->|DELETE| Delete
 
   Dispatch -->|TRUNCATE| Truncate
    
 
   Dispatch -->|SELECT| Select
 
   Dispatch -->|EXPLAIN| Explain
    
 
   Dispatch -->|SET| Set
 
   Dispatch -->|SHOW| Show
 
   Dispatch -->|BEGIN| Begin
 
   Dispatch -->|COMMIT| Commit
 
   Dispatch -->|ROLLBACK| Rollback
 
   Dispatch -->|SAVEPOINT| Savepoint
 
   Dispatch -->|RELEASE| Release
 
   Dispatch -->|VACUUM| Vacuum
 
   Dispatch -->|PRAGMA| Pragma
    
 
   CreateTable --> PlanStmt
 
   DropTable --> PlanStmt
 
   AlterTable --> PlanStmt
 
   CreateView --> PlanStmt
 
   DropView --> PlanStmt
 
   CreateIndex --> PlanStmt
 
   DropIndex --> PlanStmt
 
   Reindex --> PlanStmt
 
   RenameTable --> PlanStmt
 
   Insert --> PlanStmt
 
   InsertBuffer --> PlanStmt
 
   Update --> PlanStmt
 
   Delete --> PlanStmt
 
   Truncate --> PlanStmt
 
   Select --> PlanStmt
 
   Explain --> PlanStmt

Planning Stage

The planning stage converts sqlparser::ast::Statement nodes into typed PlanStatement objects. This involves:

1. Column resolution : Mapping string column names to FieldId identifiers via the system catalog
2. Expression translation : Converting sqlparser::ast::Expr to llkv_expr::expr::Expr and ScalarExpr
3. Subquery tracking : Recording correlated subqueries with placeholder bindings
4. Validation : Ensuring referenced tables and columns exist

SELECT Plan Construction

For SELECT statements, the planner builds a SelectPlan containing:

Sources: llkv-sql/src/sql_engine.rs:2801-3500 llkv-plan/src/plans.rs:705-850

Expression Translation

Expression translation converts SQL expressions into the llkv_expr AST, which uses FieldId instead of string column names. This enables efficient field access during execution.

Sources: llkv-plan/src/translation/expression.rs:1-500 llkv-sql/src/sql_engine.rs:4000-4500

flowchart LR
    SQLExpr["sqlparser::ast::Expr\n(column names as strings)"]
Resolver["IdentifierResolver\n(catalog lookups)"]
Translation["translate_scalar / translate_predicate"]
LLKVExpr["llkv_expr::expr::ScalarExpr<FieldId>\nllkv_expr::expr::Expr<FieldId>"]
SQLExpr --> Translation
    Resolver -.provides.-> Translation
 
   Translation --> LLKVExpr

flowchart TB
    PlanStmt["PlanStatement"]
Execute["RuntimeEngine::execute_statement"]
DDL{"Statement Type"}
CreateTableExec["execute_create_table\n(allocate table_id, register schema)"]
DropTableExec["execute_drop_table\n(remove from catalog)"]
AlterTableExec["execute_alter_table\n(modify schema)"]
CreateViewExec["execute_create_view\n(store view definition)"]
CreateIndexExec["execute_create_index\n(build index structures)"]
InsertExec["execute_insert\n(convert to RecordBatch, append)"]
UpdateExec["execute_update\n(filter + rewrite rows)"]
DeleteExec["execute_delete\n(mark rows deleted via MVCC)"]
TruncateExec["execute_truncate\n(clear all rows)"]
SelectExec["QueryExecutor::execute_select\n(scan, filter, project, aggregate)"]
Result["RuntimeStatementResult"]
PlanStmt --> Execute
 
   Execute --> DDL
    
 
   DDL -->|CreateTable| CreateTableExec
 
   DDL -->|DropTable| DropTableExec
 
   DDL -->|AlterTable| AlterTableExec
 
   DDL -->|CreateView| CreateViewExec
 
   DDL -->|CreateIndex| CreateIndexExec
    
 
   DDL -->|Insert| InsertExec
 
   DDL -->|Update| UpdateExec
 
   DDL -->|Delete| DeleteExec
 
   DDL -->|Truncate| TruncateExec
    
 
   DDL -->|Select| SelectExec
    
 
   CreateTableExec --> Result
 
   DropTableExec --> Result
 
   AlterTableExec --> Result
 
   CreateViewExec --> Result
 
   CreateIndexExec --> Result
 
   InsertExec --> Result
 
   UpdateExec --> Result
 
   DeleteExec --> Result
 
   TruncateExec --> Result
 
   SelectExec --> Result

Execution Stage

The RuntimeEngine receives a PlanStatement and dispatches it to the appropriate execution handler:

Sources: llkv-runtime/src/lib.rs:1-500 llkv-sql/src/sql_engine.rs:706-745

flowchart TB
    SelectPlan["SelectPlan"]
Executor["QueryExecutor::execute_select"]
Strategy{"Execution Strategy"}
NoTable["execute_select_without_table\n(constant projection)"]
Compound["execute_compound_select\n(UNION/EXCEPT/INTERSECT)"]
GroupBy["execute_group_by_single_table\n(hash aggregation)"]
CrossProduct["execute_cross_product\n(nested loop join)"]
Aggregates["execute_aggregates\n(full-table aggregation)"]
Projection["execute_projection\n(scan + filter + project)"]
ScanStream["Table::scan_stream\n(streaming batches)"]
FilterEval["filter_row_ids\n(predicate evaluation)"]
Gather["gather_rows\n(assemble RecordBatch)"]
Sort["lexsort_to_indices\n(ORDER BY)"]
LimitOffset["take + offset\n(LIMIT/OFFSET)"]
SelectExecution["SelectExecution\n(result wrapper)"]
SelectPlan --> Executor
 
   Executor --> Strategy
    
 
   Strategy -->|tables.is_empty| NoTable
 
   Strategy -->|compound.is_some| Compound
 
   Strategy -->|!group_by.is_empty| GroupBy
 
   Strategy -->|tables.len > 1| CrossProduct
 
   Strategy -->|!aggregates.is_empty| Aggregates
 
   Strategy -->|single table| Projection
    
 
   Projection --> ScanStream
 
   ScanStream --> FilterEval
 
   FilterEval --> Gather
 
   Gather --> Sort
 
   Sort --> LimitOffset
    
 
   NoTable --> SelectExecution
 
   Compound --> SelectExecution
 
   GroupBy --> SelectExecution
 
   CrossProduct --> SelectExecution
 
   Aggregates --> SelectExecution
 
   LimitOffset --> SelectExecution

SELECT Execution Flow

SELECT statement execution is the most complex path, involving multiple optimization strategies:

Sources: llkv-executor/src/lib.rs:519-563 llkv-executor/src/scan.rs:1-500

Two-Phase Execution for Filtering

When a WHERE clause is present, execution follows a two-phase approach:

1. Phase 1: Row ID Collection

   • Evaluate predicates against stored data
   • Use chunk metadata for pruning (min/max values)
   • Build bitmap of matching row IDs

2. Phase 2: Data Gathering

   • Fetch only projected columns for matching rows
   • Assemble Arrow RecordBatch from gathered data

Sources: llkv-executor/src/scan.rs:200-400 [Diagram 6 from overview](https://github.com/jzombie/rust-llkv/blob/89777726/Diagram 6 from overview)

flowchart LR
    RuntimeResult["RuntimeStatementResult"]
Branch{"Result Type"}
DDLResult["CreateTable/DropTable/etc\n(metadata only)"]
DMLResult["Insert/Update/Delete\n(row count)"]
SelectResult["Select\n(SelectExecution)"]
SelectExec["SelectExecution"]
Stream["stream(callback)\n(iterate batches)"]
IntoBatches["into_batches()\n(collect all)"]
IntoRows["into_rows()\n(materialize)"]
Batches["Vec<RecordBatch>"]
RuntimeResult --> Branch
 
   Branch -->|DDL| DDLResult
 
   Branch -->|DML| DMLResult
 
   Branch -->|SELECT| SelectResult
    
 
   SelectResult --> SelectExec
 
   SelectExec --> Stream
 
   SelectExec --> IntoBatches
 
   SelectExec --> IntoRows
    
 
   Stream --> Batches
 
   IntoBatches --> Batches

Result Formatting

All execution paths ultimately produce a RuntimeStatementResult, which is converted to Arrow RecordBatch objects for SELECT queries:

The SelectExecution type provides three consumption modes:

Sources: llkv-executor/src/types/execution.rs:1-300 llkv-sql/src/sql_engine.rs:1100-1150

Optimization Points in the Pipeline

Several optimization strategies are applied throughout the pipeline:

1. SQL Preprocessing Optimizations

• Empty IN list rewriting : x IN () becomes constant false, enabling early elimination
• Index hint removal : Allows the planner to make optimal index choices without user hints

Sources: llkv-sql/src/sql_engine.rs:835-856 llkv-sql/src/sql_engine.rs:858-875

2. INSERT Buffering

• Batching : Consecutive literal INSERT statements are buffered until reaching MAX_BUFFERED_INSERT_ROWS (8192)
• Throughput : Dramatically reduces planning overhead for bulk ingest workloads
• Semantics : Disabled by default to preserve transactional visibility

Sources: llkv-sql/src/sql_engine.rs:486-547 llkv-sql/src/sql_engine.rs:1200-1300

3. Predicate Pushdown

• Chunk pruning : Min/max metadata on column chunks enables skipping irrelevant data
• Vectorized evaluation : SIMD instructions accelerate predicate evaluation within chunks

Sources: llkv-executor/src/scan.rs:300-400

4. Projection Pushdown

• Lazy column loading : Only requested columns are fetched from storage
• Computed projection caching : Identical expressions are evaluated once and reused

Sources: llkv-executor/src/lib.rs:469-501

5. Fast Paths

• Constant SELECT : Queries without tables avoid storage access entirely
• Full table scan : Queries without predicates stream directly without bitmap construction

Sources: llkv-executor/src/lib.rs:533-534

Parameter Binding for Prepared Statements

The pipeline supports parameterized queries via PreparedStatement:

Parameter placeholders are normalized during preprocessing:

• ?, ?N, $N: Positional parameters (1-indexed)
• :name: Named parameters (converted to indices)

Sources: llkv-sql/src/sql_engine.rs:78-283 llkv-sql/src/sql_engine.rs:354-373

Summary

The SQL query processing pipeline in LLKV follows a clear multi-stage architecture:

1. Preprocessing : Normalize SQL dialect differences
2. Parsing : Convert text to AST (sqlparser)
3. Planning : Build typed PlanStatement with column resolution
4. Execution : Execute via RuntimeEngine and QueryExecutor
5. Result Formatting : Return Arrow RecordBatch objects

Key design principles:

• Dialect flexibility : Preprocessing enables SQLite, DuckDB, and PostgreSQL syntax
• Type safety : Early resolution of column names to FieldId prevents runtime errors
• Streaming execution : Large result sets never require full materialization
• Optimization opportunities : Metadata pruning, SIMD evaluation, and projection pushdown reduce data movement

For implementation details of specific stages, refer to the linked subsystem pages.

Dismiss

Refresh this wiki

Enter email to refresh

Data Formats and Arrow Integration

Loading…

Data Formats and Arrow Integration

Relevant source files

• Cargo.lock
• Cargo.toml
• llkv-column-map/Cargo.toml
• llkv-column-map/src/gather.rs
• llkv-column-map/src/store/projection.rs
• llkv-csv/src/writer.rs
• llkv-sql/tests/pager_io_tests.rs
• llkv-table/examples/direct_comparison.rs
• llkv-table/examples/performance_benchmark.rs
• llkv-table/examples/test_streaming.rs
• llkv-table/src/table.rs

This page explains how Apache Arrow serves as the foundational columnar data format throughout LLKV, covering the types supported, serialization strategies, and integration points across the system. Arrow provides the in-memory representation for all data operations, from SQL query results to storage layer batches.

For information about how Arrow data flows through query execution, see Query Execution. For details on how the storage layer persists Arrow arrays, see Column Storage and ColumnStore.

RecordBatch as the Universal Data Container

The arrow::record_batch::RecordBatch type is the primary data exchange unit across all LLKV layers. A RecordBatch represents a columnar slice of data with a fixed schema, where each column is an ArrayRef (type-erased Arrow array).

Sources: llkv-table/src/table.rs:6-9 llkv-table/examples/test_streaming.rs:1-9

graph TB
    RecordBatch["RecordBatch"]
Schema["Schema\n(arrow::datatypes::Schema)"]
Columns["Vec<ArrayRef>\n(arrow::array::ArrayRef)"]
RecordBatch --> Schema
 
   RecordBatch --> Columns
    
 
   Schema --> Fields["Vec<Field>\nColumn Names + Types"]
Columns --> Array1["Column 0: ArrayRef"]
Columns --> Array2["Column 1: ArrayRef"]
Columns --> Array3["Column N: ArrayRef"]
Array1 --> UInt64Array["UInt64Array\n(row_id column)"]
Array2 --> Int64Array["Int64Array\n(user data)"]
Array3 --> StringArray["StringArray\n(text data)"]

RecordBatch Construction Pattern

All data inserted into tables must arrive as a RecordBatch with specific metadata:

Sources: llkv-table/src/table.rs:231-438 llkv-table/examples/test_streaming.rs:18-58

Schema and Field Metadata

The arrow::datatypes::Schema describes the structure of a RecordBatch. LLKV extends Arrow’s schema system with custom metadata to track column identity and table ownership.

Field Metadata Convention

Each user column’s Field carries a field_id metadata entry that encodes either:

• User columns: A raw FieldId (0-2047) that gets namespaced to a LogicalFieldId
• MVCC columns: A pre-computed LogicalFieldId for created_by / deleted_by

Sources: llkv-table/src/table.rs:243-320 llkv-table/constants.rs (FIELD_ID_META_KEY)

graph TB
    Field["arrow::datatypes::Field"]
FieldName["name: String"]
DataType["data_type: DataType"]
Nullable["nullable: bool"]
Metadata["metadata: HashMap<String, String>"]
Field --> FieldName
 
   Field --> DataType
 
   Field --> Nullable
 
   Field --> Metadata
    
 
   Metadata --> FieldIdKey["'field_id' → '42'\n(user column)"]
Metadata --> LFidKey["'field_id' → '8589934634'\n(MVCC column)"]
FieldIdKey -.converted to.-> UserLFid["LogicalFieldId::for_user(table_id, 42)"]
LFidKey -.direct use.-> SystemLFid["LogicalFieldId::for_mvcc_created_by(table_id)"]

Schema Reconstruction from Catalog

The Table::schema() method reconstructs an Arrow Schema by querying the system catalog for column names and combining them with type information from the column store:

Sources: llkv-table/src/table.rs:519-549

sequenceDiagram
    participant Caller
    participant Table
    participant ColumnStore
    participant SysCatalog
    
    Caller->>Table: schema()
    Table->>ColumnStore: user_field_ids_for_table(table_id)
    ColumnStore-->>Table: Vec<LogicalFieldId>
    Table->>SysCatalog: get_cols_meta(field_ids)
    SysCatalog-->>Table: Vec<ColMeta>
    Table->>ColumnStore: data_type(lfid) for each
    ColumnStore-->>Table: DataType
    Table->>Table: Build Field with metadata
    Table-->>Caller: Arc<Schema>

Supported Arrow Data Types

LLKV’s column store supports the following Arrow data types for user columns:

Sources: llkv-column-map/src/store/projection.rs:135-185 llkv-column-map/src/gather.rs:10-18

Type Dispatch Strategy

The column store uses Rust enums to dispatch operations per data type, ensuring type-safe handling without runtime reflection:

Sources: llkv-column-map/src/store/projection.rs:99-236 llkv-column-map/src/store/projection.rs:237-395

graph TB
    ColumnOutputBuilder["ColumnOutputBuilder\n(enum per type)"]
ColumnOutputBuilder --> Utf8["Utf8 { builder, len_capacity, value_capacity }"]
ColumnOutputBuilder --> LargeUtf8["LargeUtf8 { builder, len_capacity, value_capacity }"]
ColumnOutputBuilder --> Binary["Binary { builder, len_capacity, value_capacity }"]
ColumnOutputBuilder --> LargeBinary["LargeBinary { builder, len_capacity, value_capacity }"]
ColumnOutputBuilder --> Boolean["Boolean { builder, len_capacity }"]
ColumnOutputBuilder --> Decimal128["Decimal128 { builder, precision, scale }"]
ColumnOutputBuilder --> Primitive["Primitive(PrimitiveBuilderKind)"]
ColumnOutputBuilder --> Passthrough["Passthrough (Struct arrays)"]
Primitive --> UInt64Builder["UInt64 { builder, len_capacity }"]
Primitive --> Int64Builder["Int64 { builder, len_capacity }"]
Primitive --> Float64Builder["Float64 { builder, len_capacity }"]
Primitive --> OtherPrimitives["... (10 more primitive types)"]

Array Builders and Construction

Arrow provides builder types (arrow::array::*Builder) for incrementally constructing arrays. LLKV’s projection layer wraps these builders with capacity management to minimize allocations during multi-batch operations.

Capacity Pre-Allocation Strategy

The ColumnOutputBuilder tracks allocated capacity separately from Arrow’s builder to avoid repeated re-allocations:

Sources: llkv-column-map/src/store/projection.rs:189-234 llkv-column-map/src/store/projection.rs:398-457

graph LR
    RequestedLen["Requested Len"]
ValueBytesHint["Value Bytes Hint"]
RequestedLen --> Check["len_capacity < len?"]
ValueBytesHint --> Check2["value_capacity < bytes?"]
Check -->|Yes| Reallocate["Recreate Builder\nwith_capacity(len, bytes)"]
Check2 -->|Yes| Reallocate
    
 
   Check -->|No| Reuse["Reuse Existing Builder"]
Check2 -->|No| Reuse
    
 
   Reallocate --> UpdateCapacity["Update cached capacities"]
UpdateCapacity --> Append["append_value()
or append_null()"]
Reuse --> Append

String and Binary Builder Pattern

Variable-length types require two capacity dimensions:

• Length capacity: Number of values
• Value capacity: Total bytes across all values

Sources: llkv-column-map/src/store/projection.rs:398-411 llkv-column-map/src/store/projection.rs:413-426

graph TB
    subgraph "In-Memory Layer"
        RecordBatch1["RecordBatch\n(user input)"]
ArrayRef1["ArrayRef\n(Int64Array, StringArray, etc.)"]
end
    
    subgraph "Serialization Layer"
        Serialize["serialize_array()\n(Arrow IPC encoding)"]
Deserialize["deserialize_array()\n(Arrow IPC decoding)"]
end
    
    subgraph "Storage Layer"
        ChunkBlob["EntryHandle\n(byte blob)"]
Pager["Pager::batch_put()"]
PhysicalKey["PhysicalKey\n(u64 identifier)"]
end
    
 
   RecordBatch1 --> ArrayRef1
 
   ArrayRef1 --> Serialize
 
   Serialize --> ChunkBlob
 
   ChunkBlob --> Pager
 
   Pager --> PhysicalKey
    
    PhysicalKey -.read.-> Pager
    Pager -.read.-> ChunkBlob
 
   ChunkBlob --> Deserialize
 
   Deserialize --> ArrayRef1

Serialization and Storage Integration

Arrow arrays are serialized to byte blobs using Arrow’s IPC format before persistence in the key-value store. The column store maintains a separation between logical Arrow representation and physical storage:

Sources: llkv-column-map/src/serialization.rs (deserialize_array function), llkv-column-map/src/store/projection.rs17

Chunk Organization

Large columns are split into multiple chunks (default 65,536 rows per chunk). Each chunk stores:

• Value array: Serialized Arrow array with actual data
• Row ID array: Separate UInt64Array mapping row IDs to array indices

Sources: llkv-column-map/src/store/descriptor.rs (ChunkMetadata, ColumnDescriptor), llkv-column-map/src/store/mod.rs (DEFAULT_CHUNK_TARGET_ROWS)

graph TB
    GatherNullPolicy["GatherNullPolicy"]
GatherNullPolicy --> ErrorOnMissing["ErrorOnMissing\nMissing row → Error"]
GatherNullPolicy --> IncludeNulls["IncludeNulls\nMissing row → NULL in output"]
GatherNullPolicy --> DropNulls["DropNulls\nMissing row → omit from output"]
ErrorOnMissing -.used by.-> InnerJoin["Inner Joins\nStrict row matches"]
IncludeNulls -.used by.-> OuterJoin["Outer Joins\nNULL padding"]
DropNulls -.used by.-> Projection["Filtered Projections\nRemove incomplete rows"]

Null Handling

Arrow’s nullable columns use a separate validity bitmap. LLKV’s GatherNullPolicy enum controls how nulls propagate during row gathering:

Sources: llkv-column-map/src/store/projection.rs:40-48 llkv-table/src/table.rs:589-645

Null Bitmap Semantics

Arrow arrays maintain a separate NullBuffer (bit-packed). When gathering rows, the system must:

1. Check if the source array position is valid (array.is_valid(idx))
2. Append null to the builder if invalid, or the value if valid

Sources: llkv-column-map/src/gather.rs:369-402

graph LR
    subgraph "CSV Export"
        ScanStream["Table::scan_stream()"]
RecordBatch2["RecordBatch stream"]
ArrowCSV["arrow::csv::Writer"]
CSVFile["CSV File"]
ScanStream --> RecordBatch2
 
       RecordBatch2 --> ArrowCSV
 
       ArrowCSV --> CSVFile
    end
    
    subgraph "CSV Import"
        CSVInput["CSV File"]
Parser["csv-core parser"]
Builders["Array Builders"]
RecordBatch3["RecordBatch"]
TableAppend["Table::append()"]
CSVInput --> Parser
 
       Parser --> Builders
 
       Builders --> RecordBatch3
 
       RecordBatch3 --> TableAppend
    end

Arrow Integration Points

CSV Import and Export

The llkv-csv crate uses Arrow’s native CSV writer (arrow::csv::WriterBuilder) for exports and custom parsing for imports:

Sources: llkv-csv/src/writer.rs:196-267 llkv-csv/src/reader.rs

SQL Query Results

All SQL query results are returned as RecordBatch instances, enabling zero-copy integration with Arrow-based tools:

Sources: llkv-runtime/src/lib.rs (RuntimeStatementResult enum), llkv-sql/src/lib.rs (SqlEngine::execute)

graph TB
    AggregateExpr["Aggregate Expression\n(SUM, AVG, MIN, MAX)"]
AggregateExpr --> ArrowKernel["arrow::compute kernels\n(sum, min, max)"]
AggregateExpr --> CustomAccumulator["Custom Accumulator\n(COUNT DISTINCT, etc.)"]
ArrowKernel --> PrimitiveArray["PrimitiveArray<T>"]
CustomAccumulator --> AnyArray["ArrayRef (any type)"]
PrimitiveArray -.vectorized ops.-> SIMDPath["SIMD-accelerated compute"]
AnyArray -.type-erased dispatch.-> SlowPath["Generic accumulation"]

Arrow-Native Aggregations

Aggregate functions operate directly on Arrow arrays using arrow::compute kernels where possible:

Sources: llkv-aggregate/src/lib.rs (aggregate accumulators), llkv-compute/src/kernels.rs (NumericKernels)

Data Type Conversion Table

The following table maps SQL types to Arrow types as materialized in the system:

Sources: llkv-plan/src/types.rs (SQL type mapping), llkv-types/src/arrow.rs (DataType conversion)

RecordBatch Flow Summary

Sources: llkv-table/src/table.rs:231-438 llkv-column-map/src/store/mod.rs (append logic)

Performance Considerations

Vectorization Benefits

Arrow’s columnar layout enables SIMD operations in compute kernels:

• Primitive aggregations: arrow::compute::sum, min, max use SIMD
• Filtering: Bit-packed boolean arrays enable fast predicate evaluation
• Null bitmap checks: Batch validity checks avoid per-row branches

Memory Efficiency

Columnar storage provides superior compression and cache locality:

• Compression ratio: Homogeneous columns compress better than row-based formats
• Cache efficiency: Scanning a single column loads contiguous memory
• Null optimization: Sparse nulls use minimal space (1 bit per value)

graph TB
    GatherContextPool["GatherContextPool"]
GatherContextPool --> AcquireContext["acquire(field_ids)"]
AcquireContext --> CheckCache["Check HashMap\nfor cached context"]
CheckCache -->|Hit| ReuseContext["Reuse MultiGatherContext"]
CheckCache -->|Miss| CreateNew["Create new context"]
ReuseContext --> Execute["Execute gather operation"]
CreateNew --> Execute
    
 
   Execute --> ReleaseContext["Release context back to pool"]
ReleaseContext --> StoreInPool["Store in HashMap\n(max 4 per field set)"]

Builder Reuse Strategy

The MultiGatherContext pools ColumnOutputBuilder instances to avoid repeated allocations during streaming scans:

Sources: llkv-column-map/src/store/projection.rs:651-691

Key Takeaways:

• RecordBatch is the universal data container for all operations
• Field metadata tracks column identity via field_id keys
• Type dispatch uses Rust enums to handle 18+ Arrow data types efficiently
• Serialization uses Arrow IPC format for persistence
• Null handling respects Arrow’s validity bitmaps with configurable policies
• Integration is native: CSV, SQL results, and storage all speak Arrow

Dismiss

Refresh this wiki

Enter email to refresh

SQL Interface

Loading…

SQL Interface

Relevant source files

• llkv-executor/src/lib.rs
• llkv-sql/src/lib.rs
• llkv-sql/src/sql_engine.rs
• llkv-tpch/Cargo.toml
• llkv-tpch/DRAFT.md
• llkv-tpch/src/lib.rs
• llkv-tpch/src/main.rs
• llkv-tpch/src/queries.rs

The SQL Interface provides the primary user-facing API for interacting with LLKV databases through SQL statements. This layer is responsible for parsing SQL text, preprocessing dialect-specific syntax, translating Abstract Syntax Trees (AST) into execution plans, and delegating to the runtime engine for actual execution.

For information about query planning and execution, see Query Planning and Query Execution. For details on the underlying runtime that executes plans, see Architecture.

Purpose and Scope

The SQL Interface layer (llkv-sql crate) serves as the entry point for SQL-based database operations. It bridges the gap between SQL text written by users and the Arrow-native columnar storage engine, handling:

• SQL Parsing : Converting SQL strings into Abstract Syntax Trees using sqlparser-rs
• Dialect Normalization : Preprocessing SQL to handle syntax variations from SQLite, DuckDB, and PostgreSQL
• Statement Translation : Converting ASTs into typed execution plans (PlanStatement structures)
• Execution Coordination : Delegating plans to the RuntimeEngine and formatting results
• Transaction Management : Coordinating multi-statement transactions with MVCC support
• Performance Optimization : Batching INSERT statements to reduce planning overhead

The SQL Interface does not execute queries directly—it delegates all data operations to the runtime and executor layers. Its primary responsibility is accurate SQL-to-plan translation while preserving user intent across different SQL dialects.

Sources : llkv-sql/src/lib.rs:1-52 llkv-sql/src/sql_engine.rs:1-60

Architecture Overview

The SQL Interface operates as a stateful wrapper around the RuntimeEngine, maintaining session state, prepared statement caches, and insert buffering state. The core workflow proceeds through several stages:

SQL Interface Processing Pipeline

graph TB
    User["User Application"]
SqlEngine["SqlEngine"]
Preprocess["SQL Preprocessing"]
Parser["sqlparser-rs\nGenericDialect"]
Translator["Statement Translation"]
Runtime["RuntimeEngine"]
Results["RecordBatch / RowCount"]
User -->|execute sql| SqlEngine
 
   SqlEngine -->|1. Preprocess| Preprocess
 
   Preprocess -->|Normalized SQL| Parser
 
   Parser -->|AST Statement| Translator
 
   Translator -->|PlanStatement| Runtime
 
   Runtime -->|RuntimeStatementResult| SqlEngine
 
   SqlEngine -->|Vec<RecordBatch>| Results
 
   Results -->|Query Results| User
    
    subgraph "llkv-sql Crate"
        SqlEngine
        Preprocess
        Translator
    end
    
    subgraph "External Dependencies"
        Parser
    end
    
    subgraph "llkv-runtime Crate"
        Runtime
    end

The SqlEngine maintains several internal subsystems:

1. Statement Cache : Thread-safe prepared statement storage (RwLock<FxHashMap<String, Arc<PreparedPlan>>>)
2. Insert Buffer : Cross-statement INSERT batching for bulk ingest (RefCell<Option<InsertBuffer>>)
3. Session State : Transaction context and configuration flags
4. Information Schema Cache : Lazy metadata refresh tracking

Sources : llkv-sql/src/sql_engine.rs:572-621 [Diagram 1 from overview](https://github.com/jzombie/rust-llkv/blob/89777726/Diagram 1 from overview)

SqlEngine Structure

The SqlEngine struct encapsulates all SQL processing state and exposes methods for executing SQL statements:

SqlEngine Class Structure

classDiagram
    class SqlEngine {-engine: RuntimeEngine\n-default_nulls_first: AtomicBool\n-insert_buffer: RefCell~Option~InsertBuffer~~\n-insert_buffering_enabled: AtomicBool\n-information_schema_ready: AtomicBool\n-statement_cache: RwLock~FxHashMap~String PreparedPlan~~\n+new(pager) SqlEngine\n+with_context(context, nulls_first) SqlEngine\n+execute(sql) Result~Vec~RuntimeStatementResult~~\n+sql(sql) Result~Vec~RecordBatch~~\n+prepare(sql) Result~PreparedStatement~\n+execute_prepared(stmt, params) Result~Vec~RuntimeStatementResult~~\n+session() RuntimeSession\n+runtime_context() Arc~RuntimeContext~}
    
    class RuntimeEngine {+execute_statement(plan) Result~RuntimeStatementResult~\n+context() Arc~RuntimeContext~}
    
    class PreparedStatement {-inner: Arc~PreparedPlan~\n+parameter_count() usize}
    
    class InsertBuffer {-table_name: String\n-columns: Vec~String~\n-rows: Vec~Vec~PlanValue~~\n-on_conflict: InsertConflictAction\n+can_accept(table, cols, conflict) bool\n+should_flush() bool}
    
    SqlEngine --> RuntimeEngine : delegates to
    SqlEngine --> PreparedStatement : creates
    SqlEngine --> InsertBuffer : maintains

Sources : llkv-sql/src/sql_engine.rs:572-621 llkv-sql/src/sql_engine.rs:354-373 llkv-sql/src/sql_engine.rs:487-547

Statement Execution Flow

A typical SQL execution proceeds through the following phases:

Statement Execution Sequence

Sources : llkv-sql/src/sql_engine.rs:1533-1633 llkv-sql/src/sql_engine.rs:2134-2285

SQL Preprocessing System

Before parsing, the SQL Interface applies multiple preprocessing passes to normalize syntax variations across different SQL dialects:

Each preprocessor runs as a regex-based rewrite pass before the SQL text reaches sqlparser-rs. This allows LLKV to accept SQL from multiple dialects while using a single parser.

Sources : llkv-sql/src/sql_engine.rs:759-1006 llkv-sql/src/sql_engine.rs:771-793

Prepared Statements and Parameters

The SQL Interface supports prepared statements with parameterized queries. Parameters use placeholder syntax compatible with multiple dialects:

Parameter Processing Flow

graph LR
    subgraph "Parameter Placeholder Formats"
        Q1["? \n(anonymous)"]
Q2["?N \n(numbered)"]
Dollar["$N \n(PostgreSQL)"]
Named[":name \n(named)"]
end
    
    subgraph "Parameter Processing"
        Register["register_placeholder(raw)"]
State["ParameterState"]
Index["assigned: HashMap<String, usize>"]
end
    
    subgraph "Execution"
        Prepare["SqlEngine::prepare(sql)"]
PrepStmt["PreparedStatement"]
Execute["execute_prepared(stmt, params)"]
Bind["Bind params to plan"]
end
    
 
   Q1 --> Register
 
   Q2 --> Register
 
   Dollar --> Register
 
   Named --> Register
 
   Register --> State
 
   State --> Index
 
   Index --> Prepare
 
   Prepare --> PrepStmt
 
   PrepStmt --> Execute
 
   Execute --> Bind

Parameter placeholders are registered during parsing and replaced with internal sentinel values (__llkv_param__N__). When executing a prepared statement, the sentinel values are substituted with actual parameter values before plan execution.

Sources : llkv-sql/src/sql_engine.rs:78-282 llkv-sql/src/sql_engine.rs:354-373 llkv-sql/src/sql_engine.rs:1707-1773

INSERT Buffering Optimization

To improve bulk insert performance, the SQL Interface can buffer multiple consecutive INSERT ... VALUES statements and execute them as a single batched operation. This dramatically reduces planning overhead for large data loads:

INSERT Buffer State Machine

stateDiagram-v2
    [*] --> Empty : engine created
    Empty --> Buffering : INSERT with VALUES
    Buffering --> Buffering : compatible INSERT
    Buffering --> Flushing : incompatible statement
    Buffering --> Flushing : buffer threshold reached
    Flushing --> Empty : execute batched insert
    Flushing --> Buffering : new INSERT after flush
    Empty --> [*]
    
    note right of Buffering
        Accumulate rows while:
        - Same table
        - Same columns
        - Same conflict action
        - Below MAX_BUFFERED_INSERT_ROWS
    end note
    
    note right of Flushing
        Execute single INSERT with
        all accumulated rows
    end note

Buffering is disabled by default to preserve per-statement semantics for unit tests. Long-running workloads can enable buffering via set_insert_buffering(true) to achieve significant performance gains on bulk ingests.

Sources : llkv-sql/src/sql_engine.rs:487-547 llkv-sql/src/sql_engine.rs:2134-2285

graph TD
    AST["sqlparser::ast::Statement"]
subgraph "DDL Statements"
        CreateTable["CreateTable"]
AlterTable["AlterTable"]
DropTable["DropTable"]
CreateView["CreateView"]
CreateIndex["CreateIndex"]
end
    
    subgraph "DML Statements"
        Query["Query (SELECT)"]
Insert["Insert"]
Update["Update"]
Delete["Delete"]
end
    
    subgraph "Transaction Control"
        Begin["BEGIN"]
Commit["COMMIT"]
Rollback["ROLLBACK"]
end
    
    subgraph "PlanStatement Variants"
        SelectPlan["SelectPlan"]
InsertPlan["InsertPlan"]
UpdatePlan["UpdatePlan"]
DeletePlan["DeletePlan"]
CreateTablePlan["CreateTablePlan"]
AlterTablePlan["AlterTablePlan"]
BeginTxn["BeginTransaction"]
CommitTxn["CommitTransaction"]
end
    
 
   AST --> CreateTable
 
   AST --> AlterTable
 
   AST --> DropTable
 
   AST --> Query
 
   AST --> Insert
 
   AST --> Update
 
   AST --> Delete
 
   AST --> Begin
 
   AST --> Commit
    
 
   CreateTable --> CreateTablePlan
 
   AlterTable --> AlterTablePlan
 
   Query --> SelectPlan
 
   Insert --> InsertPlan
 
   Update --> UpdatePlan
 
   Delete --> DeletePlan
 
   Begin --> BeginTxn
 
   Commit --> CommitTxn

Statement Translation Process

Once SQL is parsed into an AST, the SQL Interface translates each Statement variant into a corresponding PlanStatement:

AST to Plan Translation

Translation involves:

1. Identifier Resolution : Converting string column names to FieldId values via IdentifierResolver
2. Expression Translation : Building typed expression trees from AST nodes
3. Type Inference : Determining result types for computed columns
4. Validation : Checking for unknown tables, duplicate columns, type mismatches

Sources : llkv-sql/src/sql_engine.rs:2287-3500 llkv-executor/src/lib.rs:89-93

Integration with Runtime and Executor

The SQL Interface delegates all actual execution to lower layers:

Layer Integration Diagram

The SQL Interface owns the RuntimeEngine instance and delegates PlanStatement execution to it. The runtime coordinates with the executor for query execution and the table layer for DDL operations.

Sources : llkv-sql/src/sql_engine.rs:706-745 [llkv-runtime/src/lib.rs (implied)](https://github.com/jzombie/rust-llkv/blob/89777726/llkv-runtime/src/lib.rs (implied)) [Diagram 1 from overview](https://github.com/jzombie/rust-llkv/blob/89777726/Diagram 1 from overview)

Example Usage

Basic usage of the SqlEngine:

Sources : llkv-sql/src/sql_engine.rs:443-485 llkv-sql/src/lib.rs:1-52

Key Design Principles

The SQL Interface embodies several architectural decisions:

1. Dialect Tolerance : Accept SQL from multiple databases through preprocessing rather than forking the parser
2. Lazy Validation : Validate table existence and column types during plan translation, not parsing
3. Stateful Optimization : Maintain cross-statement state (insert buffer, prepared statement cache) for performance
4. Delegate Execution : Never directly manipulate storage; always route through runtime abstractions
5. Arrow Native : Return query results as Arrow RecordBatch structures for zero-copy integration
6. Session Isolation : Each SqlEngine instance owns its transaction state and constraint enforcement mode

These principles allow the SQL Interface to serve as a stable, predictable API surface while the underlying execution engine evolves independently.

Sources : llkv-sql/src/sql_engine.rs:1-60 llkv-sql/src/lib.rs:1-52 [Diagram 2 from overview](https://github.com/jzombie/rust-llkv/blob/89777726/Diagram 2 from overview)

Dismiss

Refresh this wiki

Enter email to refresh

SqlEngine API

Loading…

SqlEngine API

Relevant source files

• llkv-executor/src/lib.rs
• llkv-sql/src/lib.rs
• llkv-sql/src/sql_engine.rs
• llkv-tpch/Cargo.toml
• llkv-tpch/DRAFT.md
• llkv-tpch/src/lib.rs
• llkv-tpch/src/main.rs
• llkv-tpch/src/queries.rs

This document describes the SqlEngine struct, which is the primary user-facing interface for executing SQL statements in LLKV. The SqlEngine parses SQL text using sqlparser-rs, converts it into execution plans, and delegates to the RuntimeEngine for execution. For details on how SQL syntax is normalized before parsing, see SQL Preprocessing and Dialect Handling. For information about the INSERT batching optimization, see INSERT Buffering System.

Sources: llkv-sql/src/sql_engine.rs:441-486 llkv-sql/src/lib.rs:1-52

SqlEngine Struct and Core Components

The SqlEngine struct wraps a RuntimeEngine and adds SQL parsing, statement caching, INSERT buffering, and dialect preprocessing capabilities.

Diagram: SqlEngine component structure and user interaction

graph TB
    SqlEngine["SqlEngine"]
RuntimeEngine["RuntimeEngine"]
RuntimeContext["RuntimeContext<Pager>"]
InsertBuffer["InsertBuffer"]
StatementCache["Statement Cache"]
InfoSchema["Information Schema"]
SqlEngine -->|contains| RuntimeEngine
 
   SqlEngine -->|maintains| InsertBuffer
 
   SqlEngine -->|maintains| StatementCache
 
   SqlEngine -->|tracks| InfoSchema
 
   RuntimeEngine -->|contains| RuntimeContext
 
   RuntimeContext -->|manages| Tables["Tables"]
RuntimeContext -->|manages| Catalog["System Catalog"]
User["User Code"] -->|execute sql| SqlEngine
 
   User -->|prepare sql| SqlEngine
 
   User -->|sql query| SqlEngine
 
   SqlEngine -->|execute_statement| RuntimeEngine
 
   RuntimeEngine -->|Result| SqlEngine
 
   SqlEngine -->|RecordBatch[]| User

Sources: llkv-sql/src/sql_engine.rs:572-620

SqlEngine Fields

Sources: llkv-sql/src/sql_engine.rs:572-586

Construction and Configuration

Creating a SqlEngine

Diagram: SqlEngine construction paths

Sources: llkv-sql/src/sql_engine.rs:751-757 llkv-sql/src/sql_engine.rs:627-633

Constructor Methods

Configuration Options:

• default_nulls_first : Controls whether NULL values sort first (true) or last (false) in ORDER BY clauses when NULLS FIRST/LAST is not explicitly specified
• INSERT buffering : Disabled by default; enable via set_insert_buffering(true) for bulk loading workloads

Sources: llkv-sql/src/sql_engine.rs:751-757 llkv-sql/src/sql_engine.rs:627-633 llkv-sql/src/sql_engine.rs:1431-1449

Statement Execution

Primary Execution Methods

Diagram: Statement execution flow through SqlEngine

Sources: llkv-sql/src/sql_engine.rs:1109-1194 llkv-sql/src/sql_engine.rs:1196-1236 llkv-sql/src/sql_engine.rs:1715-1765

Execution Method Details

Sources: llkv-sql/src/sql_engine.rs:1109-1194 llkv-sql/src/sql_engine.rs:1196-1236 llkv-sql/src/sql_engine.rs:1238-1272 llkv-sql/src/sql_engine.rs:1715-1765 llkv-sql/src/sql_engine.rs:1767-1816

RuntimeStatementResult Variants

The RuntimeStatementResult enum represents the outcome of executing different statement types:

Sources: llkv-runtime/src/lib.rs (inferred from context), llkv-sql/src/lib.rs50

Prepared Statements and Parameter Binding

Parameter Placeholder Syntax

LLKV supports multiple parameter placeholder styles for prepared statements:

Sources: llkv-sql/src/sql_engine.rs:94-133 llkv-sql/src/sql_engine.rs:258-268

Parameter Binding Flow

Diagram: Prepared statement lifecycle with parameter binding

Sources: llkv-sql/src/sql_engine.rs:1715-1765 llkv-sql/src/sql_engine.rs:1767-1816 llkv-sql/src/sql_engine.rs:223-256

SqlParamValue Types

The SqlParamValue enum represents typed parameter values:

Conversion methods:

• as_literal(&self) -> Literal - Converts to internal Literal type for expression evaluation
• as_plan_value(&self) -> PlanValue - Converts to PlanValue for INSERT operations

Sources: llkv-sql/src/sql_engine.rs:285-316

graph TB
    subgraph "Statement Processing"
        Parse["parse_statement()"]
Canonical["canonicalize_insert()"]
PreparedInsert["PreparedInsert"]
end
    
    subgraph "Buffer Management"
        BufferDecision{"Can Buffer?"}
BufferAdd["buffer.push_statement()"]
BufferFlush["flush_buffer()"]
BufferCheck{"buffer.should_flush()?"}
end
    
    subgraph "Execution"
        BuildPlan["InsertPlan::from_buffer"]
Execute["execute_insert_plan()"]
end
    
 
   Parse -->|INSERT statement| Canonical
 
   Canonical -->|VALUES only| PreparedInsert
 
   PreparedInsert --> BufferDecision
    
 
   BufferDecision -->|Yes: same table, same columns, same on_conflict| BufferAdd
 
   BufferDecision -->|No: different params| BufferFlush
    
 
   BufferAdd --> BufferCheck
 
   BufferCheck -->|Yes: >= 8192 rows| BufferFlush
 
   BufferCheck -->|No: continue| Continue["Continue processing"]
BufferFlush --> BuildPlan
 
   BuildPlan --> Execute
 
   Execute -->|Multiple Insert results| Results["Vec<RuntimeStatementResult>"]

INSERT Buffering System

The INSERT buffering system batches multiple literal INSERT ... VALUES statements together to reduce planning overhead during bulk loading operations.

Buffering Architecture

Diagram: INSERT buffering decision tree and execution flow

Sources: llkv-sql/src/sql_engine.rs:486-546 llkv-sql/src/sql_engine.rs:1869-2008

InsertBuffer Configuration

Buffer acceptance rules:

1. Table name must match exactly
2. Column list must match exactly
3. on_conflict action must match
4. Only literal VALUES are buffered (subqueries flush immediately)

Flush triggers:

1. Row count reaches MAX_BUFFERED_INSERT_ROWS
2. Next INSERT targets different table/columns/conflict action
3. Non-INSERT statement encountered
4. execute() completes (flush remaining)
5. SqlEngine is dropped

Sources: llkv-sql/src/sql_engine.rs:486-546 llkv-sql/src/sql_engine.rs:1431-1449

graph LR
    Input["Raw SQL String"]
TPCH["preprocess_tpch_connect_syntax"]
CreateType["preprocess_create_type_syntax"]
Exclude["preprocess_exclude_syntax"]
TrailingComma["preprocess_trailing_commas_in_values"]
EmptyIn["preprocess_empty_in_lists"]
IndexHints["preprocess_index_hints"]
Reindex["preprocess_reindex_syntax"]
TriggerShorthand["preprocess_sqlite_trigger_shorthand"]
BareTable["preprocess_bare_table_in_clauses"]
Parser["sqlparser::Parser"]
AST["Vec<Statement>"]
Input --> TPCH
 
   TPCH --> CreateType
 
   CreateType --> Exclude
 
   Exclude --> TrailingComma
 
   TrailingComma --> EmptyIn
 
   EmptyIn --> IndexHints
 
   IndexHints --> Reindex
 
   Reindex --> TriggerShorthand
 
   TriggerShorthand --> BareTable
 
   BareTable --> Parser
 
   Parser --> AST

SQL Preprocessing

Before parsing with sqlparser, the SQL text undergoes multiple normalization passes to handle dialect-specific syntax variations. This allows LLKV to accept SQL from SQLite, DuckDB, PostgreSQL, and other sources.

Preprocessing Pipeline

Diagram: SQL preprocessing transformation pipeline

Sources: llkv-sql/src/sql_engine.rs:1024-1103

Preprocessing Transformations

Sources: llkv-sql/src/sql_engine.rs:759-1006

Session and Transaction Management

Accessing the RuntimeSession

The SqlEngine::session() method provides access to the underlying RuntimeSession, which manages transaction state and constraint enforcement:

Key session methods:

• begin_transaction(kind) - Start a new transaction
• commit_transaction() - Commit the current transaction
• rollback_transaction() - Abort the current transaction
• set_constraint_enforcement_mode(mode) - Control when constraints are checked
• execute_insert_plan(plan) - Direct plan execution (bypasses SQL parsing)
• execute_select_plan(plan) - Direct SELECT execution

Sources: llkv-sql/src/sql_engine.rs:1412-1424

Constraint Enforcement Modes

The session supports two constraint enforcement modes:

Deferred mode is useful for bulk loading when referential integrity violations may occur temporarily during the load process.

Sources: llkv-table/src/catalog/manager.rs (inferred from TpchToolkit usage), llkv-tpch/src/lib.rs:274-278

stateDiagram-v2
    [*] --> Uninitialized: SqlEngine::new()
    Uninitialized --> Checking : Query references information_schema
    Checking --> Initializing : ensure_information_schema_ready()
    Initializing --> Ready : refresh_information_schema()
    Ready --> Ready : Subsequent queries
    Ready --> Invalidated : DDL statement (CREATE/DROP TABLE, etc.)
    Invalidated --> Checking : Next information_schema query
    Checking --> Ready : Already initialized

Information Schema

The SqlEngine lazily initializes the information_schema tables on first access to avoid startup overhead. Querying information_schema.tables, information_schema.columns, or other information schema views triggers initialization.

Information Schema Lifecycle

Diagram: Information schema initialization and invalidation lifecycle

Key methods:

• ensure_information_schema_ready() - Initialize if not already ready
• invalidate_information_schema() - Mark as stale after schema changes
• refresh_information_schema() - Delegate to RuntimeEngine for rebuild

Invalidation triggers:

• CREATE TABLE, DROP TABLE
• ALTER TABLE
• CREATE VIEW, DROP VIEW

Sources: llkv-sql/src/sql_engine.rs:648-660 llkv-sql/src/sql_engine.rs:706-745

graph LR
    Execute["execute_plan_statement"]
RuntimeEngine["RuntimeEngine::execute_statement"]
Error["Error::NotFound or\nInvalidArgumentError"]
MapError["map_table_error"]
UserError["Error::CatalogError:\n'Table does not exist'"]
Execute -->|delegates| RuntimeEngine
 
   RuntimeEngine -->|returns| Error
 
   Execute -->|table name available| MapError
 
   MapError -->|transforms| UserError
 
   UserError -->|propagates| User["User Code"]

Error Handling and Diagnostics

Error Mapping

The SqlEngine transforms generic storage errors into user-friendly SQL errors, particularly for table lookup failures:

Diagram: Error mapping for table lookup failures

Error transformation rules:

1. Error::NotFound → Error::CatalogError("Table '...' does not exist")
2. Generic “unknown table” messages → Catalog error with table name
3. View-related operations (CREATE VIEW, DROP VIEW) skip mapping

Sources: llkv-sql/src/sql_engine.rs:677-745

Statement Expectations (Test Harness)

For test infrastructure, the SqlEngine supports registering expected outcomes for statements:

Expectation types:

• StatementExpectation::Ok - Statement should succeed
• StatementExpectation::Error - Statement should fail
• StatementExpectation::Count(n) - Statement should affect n rows

Sources: llkv-sql/src/sql_engine.rs:65-391

Advanced Usage Examples

Bulk Loading with INSERT Buffering

Sources: llkv-sql/src/sql_engine.rs:1431-1449 llkv-sql/src/sql_engine.rs:2010-2027

Prepared Statements with Named Parameters

Sources: llkv-sql/src/sql_engine.rs:1715-1816

Direct Plan Execution (Advanced)

For performance-critical code paths, bypass SQL parsing by executing plans directly:

Sources: llkv-sql/src/sql_engine.rs:1412-1424 llkv-runtime/src/lib.rs (InsertPlan structure inferred)

Key Constants

Sources: llkv-sql/src/sql_engine.rs:78-588

Dismiss

Refresh this wiki

Enter email to refresh

SQL Preprocessing and Dialect Handling

Loading…

SQL Preprocessing and Dialect Handling

Relevant source files

• llkv-executor/src/lib.rs
• llkv-sql/src/sql_engine.rs

This document describes the SQL preprocessing layer that normalizes SQL syntax from multiple dialects (SQLite, DuckDB, PostgreSQL) before parsing. The preprocessor transforms dialect-specific syntax into forms that the sqlparser-rs library can parse, enabling broad compatibility across different SQL variants.

For information about the overall SQL execution flow, see SqlEngine API. For details on how SQL parameters are bound to prepared statements, see Plan Structures.

Purpose and Architecture

The SQL preprocessing system transforms SQL text through a series of regex-based rewriting rules before passing it to sqlparser-rs. This architecture allows LLKV to accept SQL from various dialects without forking the parser library or implementing a custom parser.

Key components :

• SqlEngine::preprocess_sql_input() - main preprocessing orchestrator
• Individual preprocessing functions for each dialect feature
• Thread-local parameter state tracking
• Regex-based pattern matching and replacement

flowchart LR
    RawSQL["Raw SQL Text\n(SQLite/DuckDB/PostgreSQL)"]
Preprocess["preprocess_sql_input()"]
subgraph "Preprocessing Steps"
        TPCH["TPC-H CONNECT removal"]
CreateType["CREATE TYPE → DOMAIN"]
Exclude["EXCLUDE qualifier handling"]
Trailing["Trailing comma removal"]
BareTable["Bare table IN conversion"]
EmptyIn["Empty IN list handling"]
IndexHints["Index hint removal"]
Reindex["REINDEX normalization"]
Trigger["Trigger shorthand expansion"]
end
    
    Parser["sqlparser::Parser"]
AST["Statement AST"]
RawSQL --> Preprocess
 
   Preprocess --> TPCH
 
   TPCH --> CreateType
 
   CreateType --> Exclude
 
   Exclude --> Trailing
 
   Trailing --> BareTable
 
   BareTable --> EmptyIn
 
   EmptyIn --> IndexHints
 
   IndexHints --> Reindex
 
   Reindex --> Trigger
 
   Trigger --> Parser
 
   Parser --> AST

The preprocessing layer sits between raw SQL input and the generic SQL parser:

Sources : llkv-sql/src/sql_engine.rs:1116-1125

Preprocessing Pipeline

The preprocess_sql_input() function applies transformations in a specific order to handle interdependencies between rules:

Sources : llkv-sql/src/sql_engine.rs:1116-1125

flowchart TD
    Input["SQL Input String"]
Step1["preprocess_tpch_connect_syntax()"]
Step2["preprocess_create_type_syntax()"]
Step3["preprocess_exclude_syntax()"]
Step4["preprocess_trailing_commas_in_values()"]
Step5["preprocess_bare_table_in_clauses()"]
Step6["preprocess_empty_in_lists()"]
Step7["preprocess_index_hints()"]
Step8["preprocess_reindex_syntax()"]
Output["Normalized SQL"]
Input --> Step1
 
   Step1 --> Step2
 
   Step2 --> Step3
 
   Step3 --> Step4
 
   Step4 --> Step5
 
   Step5 --> Step6
 
   Step6 --> Step7
 
   Step7 --> Step8
 
   Step8 --> Output
    
    Note1["Removes TPC-H CONNECT statements"]
Note2["Converts DuckDB type aliases"]
Note3["Quotes qualified identifiers"]
Note4["Removes trailing commas in VALUES"]
Note5["Wraps bare tables in subqueries"]
Note6["Converts empty IN to constant predicates"]
Note7["Strips SQLite index hints"]
Note8["Converts standalone REINDEX"]
Step1 -.-> Note1
 
   Step2 -.-> Note2
 
   Step3 -.-> Note3
 
   Step4 -.-> Note4
 
   Step5 -.-> Note5
 
   Step6 -.-> Note6
 
   Step7 -.-> Note7
 
   Step8 -.-> Note8

Dialect-Specific Transformations

TPC-H CONNECT Statement Removal

TPC-H benchmark scripts include CONNECT TO database; directives that are no-ops in LLKV (single database system). The preprocessor strips these statements entirely.

Implementation : llkv-sql/src/sql_engine.rs:759-766

Pattern : CONNECT TO <identifier>;

Action : Remove statement

CREATE TYPE → CREATE DOMAIN Conversion

DuckDB uses CREATE TYPE name AS basetype for type aliases, but sqlparser-rs only supports the SQL standard CREATE DOMAIN syntax. The preprocessor performs bidirectional conversion:

CREATE TYPE myint AS INTEGER  →  CREATE DOMAIN myint AS INTEGER
DROP TYPE myint               →  DROP DOMAIN myint

Regex patterns :

• CREATE TYPE → CREATE DOMAIN
• DROP TYPE → DROP DOMAIN

Implementation : llkv-sql/src/sql_engine.rs:775-793

Sources : llkv-sql/src/sql_engine.rs:775-793

EXCLUDE Clause Qualified Name Handling

DuckDB allows qualified identifiers in EXCLUDE clauses: SELECT * EXCLUDE (schema.table.col). The preprocessor wraps these in double quotes for parser compatibility:

EXCLUDE (schema.table.col)  →  EXCLUDE ("schema.table.col")

Pattern : EXCLUDE\s*\(\s*([a-zA-Z_][a-zA-Z0-9_]*(?:\.[a-zA-Z_][a-zA-Z0-9_]*)+)\s*\)

Implementation : llkv-sql/src/sql_engine.rs:795-812

Sources : llkv-sql/src/sql_engine.rs:795-812

Trailing Comma Removal in VALUES Clauses

DuckDB permits trailing commas in tuple literals: VALUES ('v2',). The preprocessor removes these for parser compatibility:

VALUES (1, 2,)  →  VALUES (1, 2)

Pattern : ,(\s*)\)

Replacement : $1)

Implementation : llkv-sql/src/sql_engine.rs:814-825

Sources : llkv-sql/src/sql_engine.rs:814-825

Empty IN List Handling

SQLite allows degenerate forms expr IN () and expr NOT IN () which sqlparser-rs rejects. The preprocessor converts these to constant boolean expressions while preserving expression evaluation (for potential side effects):

expr IN ()      →  (expr = NULL AND 0 = 1)  -- always false
expr NOT IN ()  →  (expr = NULL OR 1 = 1)   -- always true

Regex : Matches parenthesized expressions, quoted strings, hex literals, identifiers, or numbers followed by [NOT] IN ()

Implementation : llkv-sql/src/sql_engine.rs:827-856

Sources : llkv-sql/src/sql_engine.rs:827-856

SQLite Index Hint Removal

SQLite query optimizer hints (INDEXED BY index_name, NOT INDEXED) are stripped since LLKV makes its own index selection decisions:

FROM table INDEXED BY idx_name  →  FROM table
FROM table NOT INDEXED           →  FROM table

Pattern : \s+(INDEXED\s+BY\s+[a-zA-Z_][a-zA-Z0-9_]*|NOT\s+INDEXED)\b

Implementation : llkv-sql/src/sql_engine.rs:858-875

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

REINDEX Syntax Normalization

SQLite supports standalone REINDEX index_name statements, but sqlparser-rs only recognizes REINDEX within VACUUM statements. The preprocessor converts:

REINDEX my_index  →  VACUUM REINDEX my_index

Pattern : \bREINDEX\s+([a-zA-Z_][a-zA-Z0-9_]*(?:\.[a-zA-Z_][a-zA-Z0-9_]*)*)\b

Implementation : llkv-sql/src/sql_engine.rs:877-893

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

SQLite Trigger Shorthand Expansion

SQLite allows omitting trigger timing (BEFORE/AFTER, defaults to AFTER) and the FOR EACH ROW clause (defaults to row-level triggers). The sqlparser-rs library requires these to be explicit, so the preprocessor injects them when missing.

Transformation example :

Regex approach :

1. Detect missing timing keyword and inject AFTER
2. Detect missing FOR EACH ROW before BEGIN or WHEN and inject it

Implementation : llkv-sql/src/sql_engine.rs:895-978

Note : This is marked as a temporary workaround. The proper fix would be extending sqlparser-rs’s SQLiteDialect::parse_statement to handle these optional clauses.

Sources : llkv-sql/src/sql_engine.rs:895-978

Bare Table Names in IN Clauses

SQLite allows expr IN tablename as shorthand for expr IN (SELECT * FROM tablename). The preprocessor converts this to the explicit subquery form:

col IN users  →  col IN (SELECT * FROM users)

Pattern : \b(NOT\s+)?IN\s+([a-zA-Z_][a-zA-Z0-9_]*(?:\.[a-zA-Z_][a-zA-Z0-9_]*)*)(\s|$|;|,|\))

Avoids : Already-parenthesized expressions (IN (...))

Implementation : llkv-sql/src/sql_engine.rs:980-1009

Sources : llkv-sql/src/sql_engine.rs:980-1009

SQL Parameter System

The parameter system enables prepared statements with placeholder binding. Parameters can use various syntaxes across different SQL dialects:

Parameter State Management

Thread-local state tracks parameter registration during statement preparation:

Key functions :

• ParameterScope::new() - initializes thread-local state llkv-sql/src/sql_engine.rs:228-237
• register_placeholder(raw: &str) - assigns indices to parameters llkv-sql/src/sql_engine.rs:258-268
• placeholder_marker(index: usize) - generates internal sentinel llkv-sql/src/sql_engine.rs:270-272

Sources : llkv-sql/src/sql_engine.rs:78-282

flowchart TD
    Input["Raw Parameter String"]
CheckAuto{"Is '?' ?"}
IncrementAuto["Increment next_auto\nReturn new index"]
CheckCache{"Already registered?"}
ReturnCached["Return cached index"]
ParseType{"Parameter type"}
ParseNumeric["Parse numeric index\n(?N or $N)"]
AssignNamed["Assign max_index + 1\n(:name)"]
UpdateCache["Store in assigned map\nUpdate max_index"]
Return["Return index"]
Input --> CheckAuto
    CheckAuto --
 Yes --> IncrementAuto
    CheckAuto --
 No --> CheckCache
    CheckCache --
 Yes --> ReturnCached
    CheckCache --
 No --> ParseType
    
    ParseType -- "?N or $N" --> ParseNumeric
    ParseType -- ":name" --> AssignNamed
    
 
   ParseNumeric --> UpdateCache
 
   AssignNamed --> UpdateCache
 
   UpdateCache --> Return
 
   IncrementAuto --> Return

Parameter Index Assignment

The ParameterState::register() method normalizes different parameter syntaxes to unified indices:

Sources : llkv-sql/src/sql_engine.rs:94-133

Parameter Sentinel System

During plan building, parameters are represented as sentinel strings that can be recognized and replaced during execution:

Functions :

• placeholder_marker(index) - generates sentinel llkv-sql/src/sql_engine.rs:270-272
• literal_placeholder(index) - wraps in Literal::String llkv-sql/src/sql_engine.rs:274-276
• parse_placeholder_marker(text) - extracts index from sentinel llkv-sql/src/sql_engine.rs:278-282

Sources : llkv-sql/src/sql_engine.rs:78-282

Integration with SqlEngine Execution

The preprocessing pipeline integrates with the main SQL execution flow:

Trigger retry logic : If initial parsing fails and the SQL contains CREATE TRIGGER, the engine applies the trigger shorthand preprocessing and retries. This is a fallback for cases where the initial preprocessing pipeline doesn’t catch all trigger variations.

Sources : llkv-sql/src/sql_engine.rs:1057-1083

Recursion Limit Configuration

The parser recursion limit is set higher than sqlparser-rs’s default to accommodate deeply nested SQL expressions common in test suites:

This prevents stack overflows while still protecting against pathological inputs.

Sources : llkv-sql/src/sql_engine.rs:393-400

Design Rationale

Why Regex-Based Preprocessing?

The preprocessing approach uses regex pattern matching rather than extending the parser for several reasons:

1. Non-invasive : Does not require forking or patching sqlparser-rs
2. Composable : Multiple transformations can be chained independently
3. Maintainable : Each dialect feature is isolated in its own function
4. Sufficient : Handles syntactic transformations without semantic analysis

Trade-offs

The current regex-based approach is pragmatic for the current set of dialect differences. If the number of transformations grows significantly, a proper parser extension may become necessary.

Sources : llkv-sql/src/sql_engine.rs:759-1009

Summary

The SQL preprocessing layer provides broad dialect compatibility through a pipeline of targeted string transformations:

• TPC-H compatibility : Strips CONNECT statements
• DuckDB compatibility : Type aliases, trailing commas, qualified EXCLUDE
• SQLite compatibility : Trigger shorthand, empty IN lists, index hints, bare table IN, REINDEX
• PostgreSQL compatibility : $N parameter syntax

The system is extensible—new dialect features can be added as additional preprocessing functions without disrupting existing transformations.

Sources : llkv-sql/src/sql_engine.rs:759-1125

Dismiss

Refresh this wiki

Enter email to refresh

INSERT Buffering System

Loading…

INSERT Buffering System

Relevant source files

• llkv-executor/src/lib.rs
• llkv-sql/src/sql_engine.rs

The INSERT Buffering System is a performance optimization that batches multiple consecutive INSERT ... VALUES statements into a single execution operation. This system reduces planning and execution overhead by accumulating literal row data across statement boundaries and flushing them together, achieving significant throughput improvements for bulk ingestion workloads while preserving per-statement result semantics.

For information about SQL statement execution in general, see SQL Interface. For details on how INSERT statements are planned and translated, see Query Planning.

Purpose and Scope

The buffering system operates at the SQL engine layer, intercepting INSERT statements before they reach the runtime executor. It analyzes each INSERT to determine if it contains literal values that can be safely accumulated, or if it requires immediate execution due to complex source expressions (e.g., INSERT ... SELECT). The system maintains buffering state across multiple execute() calls, making it suitable for workloads that stream SQL scripts containing thousands of INSERT statements.

In scope:

• Buffering of INSERT ... VALUES statements with literal row data
• Automatic flushing based on configurable thresholds and statement boundaries
• Per-statement result tracking for compatibility with test harnesses
• Conflict resolution action compatibility (REPLACE, IGNORE, etc.)

Out of scope:

• Buffering of INSERT statements with subqueries or SELECT sources
• Cross-table buffering (only same-table INSERTs are batched)
• Transaction-aware buffering strategies

System Architecture

Sources: llkv-sql/src/sql_engine.rs:1057-1114 llkv-sql/src/sql_engine.rs:1231-1338 llkv-sql/src/sql_engine.rs:1423-1557

Core Data Structures

classDiagram
    class InsertBuffer {-String table_name\n-Vec~String~ columns\n-InsertConflictAction on_conflict\n-usize total_rows\n-Vec~usize~ statement_row_counts\n-Vec~Vec~PlanValue~~ rows\n+new() InsertBuffer\n+can_accept() bool\n+push_statement()\n+should_flush() bool}
    
    class PreparedInsert {<<enumeration>>\nValues\nImmediate}
    
    class SqlEngine {-RefCell~Option~InsertBuffer~~ insert_buffer\n-AtomicBool insert_buffering_enabled\n+buffer_insert() BufferedInsertResult\n+flush_buffer_results() Vec~SqlStatementResult~\n+set_insert_buffering()}
    
    SqlEngine --> InsertBuffer : contains
    SqlEngine --> PreparedInsert : produces

InsertBuffer

The InsertBuffer struct accumulates literal row data across multiple INSERT statements while tracking per-statement row counts for result reporting.

Field descriptions:

Sources: llkv-sql/src/sql_engine.rs:497-547

Configuration and Thresholds

MAX_BUFFERED_INSERT_ROWS

The buffering system enforces a maximum row threshold to prevent unbounded memory growth during bulk ingestion:

When total_rows reaches this threshold, the buffer automatically flushes before accepting additional statements. This value balances memory usage against amortized planning overhead.

Sources: llkv-sql/src/sql_engine.rs490

Enabling and Disabling Buffering

Buffering is disabled by default to preserve immediate execution semantics for unit tests and applications that depend on synchronous error reporting. Long-running workloads can opt in via the set_insert_buffering method:

Sources: llkv-sql/src/sql_engine.rs:1022-1029 llkv-sql/src/sql_engine.rs583

sequenceDiagram
    participant App
    participant SqlEngine
    participant InsertBuffer
    
    App->>SqlEngine: set_insert_buffering(true)
    SqlEngine->>SqlEngine: Store enabled flag
    
    Note over App,SqlEngine: Buffering now active
    
    App->>SqlEngine: execute("INSERT INTO t VALUES (1)")
    SqlEngine->>InsertBuffer: Create or append
    App->>SqlEngine: execute("INSERT INTO t VALUES (2)")
    SqlEngine->>InsertBuffer: Append to existing
    
    App->>SqlEngine: set_insert_buffering(false)
    SqlEngine->>InsertBuffer: flush_buffer_results()
    InsertBuffer->>SqlEngine: Return per-statement results

Buffering Decision Flow

The buffer_insert method implements the core buffering logic, determining whether an INSERT should be accumulated or executed immediately:

Immediate Execution Conditions

Buffering is bypassed under the following conditions:

1. Statement Expectation is Error or Count: Test harnesses use expectations to validate synchronous error reporting and exact row counts
2. Buffering Disabled: The insert_buffering_enabled flag is false (default state)
3. Non-literal Source: The INSERT uses a SELECT subquery or other dynamic source
4. Buffer Incompatibility: The INSERT targets a different table, column list, or conflict action

Sources: llkv-sql/src/sql_engine.rs:1231-1338

flowchart TD
    START["buffer_insert(insert, expectation)"]
CHECK_EXPECT{"expectation ==\nError |Count?"}
CHECK_ENABLED{"buffering_enabled?"}
PREPARE["prepare_insert insert"]
CHECK_TYPE{"PreparedInsert type?"}
CHECK_COMPAT{"buffer.can_accept ?"}
CHECK_FULL{"buffer.should_flush ?"}
EXEC_IMM["Execute immediately Return flushed + current"]
CREATE_BUF["Create new InsertBuffer"]
APPEND_BUF["buffer.push_statement"]
FLUSH_BUF["flush_buffer_results"]
RETURN_PLACE["Return placeholder result"]
START --> CHECK_EXPECT
 CHECK_EXPECT -->|Yes|EXEC_IMM
 CHECK_EXPECT -->|No|CHECK_ENABLED
 CHECK_ENABLED -->|No|EXEC_IMM
 CHECK_ENABLED -->|Yes|PREPARE
 PREPARE --> CHECK_TYPE
 CHECK_TYPE -->|Immediate|EXEC_IMM
 CHECK_TYPE -->|Values|CHECK_COMPAT
 CHECK_COMPAT -->|No|FLUSH_BUF
 CHECK_COMPAT -->|Yes|APPEND_BUF
 FLUSH_BUF --> CREATE_BUF
 CREATE_BUF --> RETURN_PLACE
 APPEND_BUF --> CHECK_FULL
 CHECK_FULL -->|Yes|FLUSH_BUF
 CHECK_FULL -->|No| RETURN_PLACE

Insert Canonicalization

The prepare_insert method analyzes the INSERT statement and converts it into one of two canonical forms:

PreparedInsert::Values

Literal VALUES clauses (including constant SELECT forms like SELECT 1, 2) are rewritten into Vec<Vec<PlanValue>> rows for buffering:

Conversion logic:

flowchart LR
    SQL["INSERT INTO users (id, name)\nVALUES (1, 'Alice')"]
AST["sqlparser::ast::Insert"]
CHECK{"Source type?"}
VALUES["SetExpr::Values"]
SELECT["SetExpr::Select"]
CONST{"Constant SELECT?"}
CONVERT["Convert to Vec~Vec~PlanValue~~"]
PREP_VAL["PreparedInsert::Values"]
PREP_IMM["PreparedInsert::Immediate"]
SQL --> AST
 
   AST --> CHECK
 
   CHECK -->|VALUES| VALUES
 
   CHECK -->|SELECT| SELECT
 
   VALUES --> CONVERT
 
   SELECT --> CONST
 
   CONST -->|Yes| CONVERT
 
   CONST -->|No| PREP_IMM
 
   CONVERT --> PREP_VAL

The method iterates over each row in the VALUES clause, converting SQL expressions to PlanValue variants:

Sources: llkv-sql/src/sql_engine.rs:1504-1524

flowchart LR
    COMPLEX["INSERT INTO t\nSELECT * FROM source"]
PLAN["build_select_plan()"]
WRAP["InsertPlan { source: InsertSource::Select }"]
PREP["PreparedInsert::Immediate"]
COMPLEX --> PLAN
 
   PLAN --> WRAP
 
   WRAP --> PREP

PreparedInsert::Immediate

Non-literal sources (subqueries, complex expressions) are wrapped in a fully-planned InsertPlan for immediate execution:

Sources: llkv-sql/src/sql_engine.rs:1543-1552

flowchart TD
    START["can_accept(table, columns, on_conflict)"]
CHECK_TABLE{"table_name == table?"}
CHECK_COLS{"columns == columns?"}
CHECK_CONFLICT{"on_conflict == on_conflict?"}
ACCEPT["Return true"]
REJECT["Return false"]
START --> CHECK_TABLE
 
   CHECK_TABLE -->|No| REJECT
 
   CHECK_TABLE -->|Yes| CHECK_COLS
 
   CHECK_COLS -->|No| REJECT
 
   CHECK_COLS -->|Yes| CHECK_CONFLICT
 
   CHECK_CONFLICT -->|No| REJECT
 
   CHECK_CONFLICT -->|Yes| ACCEPT

Buffer Compatibility Checking

The can_accept method ensures that only compatible INSERTs are batched together:

Compatibility requirements:

Sources: llkv-sql/src/sql_engine.rs:528-535

flowchart TD
    subgraph "During execute()"
        STMT{"Statement Type"}
INSERT["INSERT"]
TRANS["Transaction Boundary\n(BEGIN/COMMIT/ROLLBACK)"]
OTHER["Other Statement\n(SELECT, UPDATE, etc.)"]
end
    
    subgraph "Buffer State"
        SIZE{"total_rows >=\nMAX_BUFFERED_INSERT_ROWS?"}
COMPAT{"can_accept()?"}
end
    
    subgraph "Explicit Triggers"
        DROP["SqlEngine::drop()"]
DISABLE["set_insert_buffering(false)"]
MANUAL["flush_pending_inserts()"]
end
    
    FLUSH["flush_buffer_results()"]
STMT --> INSERT
 
   STMT --> TRANS
 
   STMT --> OTHER
 
   INSERT --> SIZE
 
   INSERT --> COMPAT
 
   SIZE -->|Yes| FLUSH
 
   COMPAT -->|No| FLUSH
 
   TRANS --> FLUSH
 
   OTHER --> FLUSH
 
   DROP --> FLUSH
 
   DISABLE --> FLUSH
 
   MANUAL --> FLUSH

Flush Triggers

The buffer flushes under multiple conditions to maintain correctness and predictable memory usage:

Automatic Flush Conditions

Sources: llkv-sql/src/sql_engine.rs:544-546 llkv-sql/src/sql_engine.rs:1098-1111 llkv-sql/src/sql_engine.rs:592-596

Manual Flush API

Applications can force a flush via the flush_pending_inserts public method:

This is useful when the application needs to ensure all buffered data is persisted before performing a read operation or checkpoint.

Sources: llkv-sql/src/sql_engine.rs:1132-1134

sequenceDiagram
    participant Buffer as InsertBuffer
    participant Engine as SqlEngine
    participant Runtime as RuntimeEngine
    
    Note over Buffer: Buffer contains 3 statements:\n10, 20, 15 rows
    
    Engine->>Buffer: Take buffer (45 total rows)
    Buffer-->>Engine: InsertBuffer instance
    
    Engine->>Engine: Build InsertPlan with all 45 rows
    Engine->>Runtime: execute_statement(InsertPlan)
    Runtime->>Runtime: Persist all rows atomically
    Runtime-->>Engine: RuntimeStatementResult::Insert(45)
    
    Engine->>Engine: Split into per-statement results
    Note over Engine: [10 rows, 20 rows, 15 rows]
    
    Engine-->>Engine: Return Vec~SqlStatementResult~

Flush Execution and Result Splitting

When the buffer flushes, all accumulated rows are executed as a single InsertPlan, then the result is split back into per-statement results:

Implementation details:

1. The buffer is moved out of the RefCell to prevent reentrancy issues
2. A single InsertPlan is constructed with InsertSource::Rows(all_rows)
3. The plan executes via RuntimeEngine::execute_statement
4. The returned row count is validated against total_rows
5. Per-statement results are reconstructed using statement_row_counts

Sources: llkv-sql/src/sql_engine.rs:1342-1407

Result Reconstruction

The flush method maintains the illusion of per-statement execution by reconstructing individual RuntimeStatementResult::Insert instances:

This ensures compatibility with test harnesses and applications that inspect per-statement results.

Sources: llkv-sql/src/sql_engine.rs:1389-1406

flowchart TD
    EXPECT["register_statement_expectation(expectation)"]
THREAD_LOCAL["PENDING_STATEMENT_EXPECTATIONS\n(thread-local queue)"]
EXEC["execute(sql)"]
NEXT["next_statement_expectation()"]
CHECK{"Expectation Type"}
OK["StatementExpectation::Ok\n(buffer eligible)"]
ERROR["StatementExpectation::Error\n(execute immediately)"]
COUNT["StatementExpectation::Count\n(execute immediately)"]
EXPECT --> THREAD_LOCAL
 
   EXEC --> NEXT
 
   NEXT --> THREAD_LOCAL
 
   THREAD_LOCAL --> CHECK
 
   CHECK --> OK
 
   CHECK --> ERROR
 
   CHECK --> COUNT

Statement Expectations Integration

The SQL Logic Test (SLT) harness uses statement expectations to validate error handling and row counts. The buffering system respects these expectations by bypassing the buffer when necessary:

Expectation types:

Sources: llkv-sql/src/sql_engine.rs:375-391 llkv-sql/src/sql_engine.rs:1240-1250

Performance Characteristics

The buffering system provides substantial performance improvements for bulk ingestion workloads:

Planning Overhead Reduction

Without buffering, each INSERT statement incurs:

1. SQL parsing (via sqlparser)
2. Plan construction (InsertPlan allocation)
3. Schema validation (column name resolution)
4. Runtime plan dispatch

With buffering, these costs are amortized across all buffered statements, executing once per flush rather than once per statement.

Batch Size Impact

The default threshold of 8192 rows balances several factors:

Sources: llkv-sql/src/sql_engine.rs490

sequenceDiagram
    participant App
    participant SqlEngine
    participant Buffer as InsertBuffer
    participant Runtime
    
    App->>SqlEngine: execute("BEGIN TRANSACTION")
    SqlEngine->>Buffer: flush_buffer_results()
    Buffer-->>SqlEngine: (empty, no pending data)
    SqlEngine->>Runtime: begin_transaction()
    
    App->>SqlEngine: execute("INSERT INTO t VALUES (1)")
    SqlEngine->>Buffer: Buffer statement
    
    App->>SqlEngine: execute("COMMIT")
    SqlEngine->>Buffer: flush_buffer_results()
    Buffer->>Runtime: execute_statement(InsertPlan)
    Runtime-->>Buffer: Success
    SqlEngine->>Runtime: commit_transaction()

Integration with Transaction Boundaries

The buffering system automatically flushes at transaction boundaries to maintain ACID semantics:

This ensures that all buffered writes are persisted before the transaction commits, preventing data loss or inconsistency.

Sources: llkv-sql/src/sql_engine.rs:1094-1102

Conflict Resolution Compatibility

The buffer preserves conflict resolution semantics by tracking the on_conflict action:

The buffer’s can_accept method ensures that only statements with identical conflict actions are batched together, preserving the semantic behavior of each INSERT.

Sources: llkv-sql/src/sql_engine.rs:1441-1455 llkv-sql/src/sql_engine.rs:528-535

Drop Safety

The SqlEngine implements a Drop handler to ensure that buffered data is persisted when the engine goes out of scope:

This prevents data loss when applications terminate without explicitly flushing or disabling buffering.

Sources: llkv-sql/src/sql_engine.rs:590-597

Key Code Entities

Sources: llkv-sql/src/sql_engine.rs:490-1557

Dismiss

Refresh this wiki

Enter email to refresh

Query Planning

Loading…

Query Planning

Relevant source files

• .github/workflows/build.docs.yml
• demos/llkv-sql-pong-demo/assets/llkv-sql-pong-screenshot.png
• dev-docs/doc-preview.md
• llkv-expr/src/expr.rs
• llkv-plan/Cargo.toml
• llkv-plan/src/lib.rs
• llkv-plan/src/plans.rs
• llkv-sql/Cargo.toml
• llkv-table/src/resolvers/identifier.rs
• llkv-test-utils/Cargo.toml

Purpose and Scope

The query planning layer converts parsed SQL abstract syntax trees (AST) into structured logical plans that execution engines can process. This document covers the planning architecture, plan types, translation process, and validation steps. For information about the SQL parsing that precedes planning, see SQL Interface. For details about the plan structures themselves, see Plan Structures. For subquery correlation handling, see Subquery and Correlation Handling. For expression compilation and evaluation, see Expression System. For plan execution, see Query Execution.

Sources: llkv-plan/src/lib.rs:1-49 llkv-plan/src/plans.rs:1-6

Architecture Overview

The llkv-plan crate sits between the SQL parsing layer and the execution layer. It receives SQL ASTs from sqlparser-rs and produces logical plan structures consumed by llkv-executor and llkv-runtime. The crate is organized into several focused modules:

Sources: llkv-plan/src/lib.rs:1-49 llkv-plan/Cargo.toml:1-43

Planning Process Flow

The planning process begins when the SQL layer invokes translation functions that walk the parsed AST and construct typed plan structures. The process involves multiple phases:

Identifier Resolution : During translation, column references like "users.name" or "u.address.city" must be resolved to canonical column names. The IdentifierResolver in llkv-table handles this by consulting the TableCatalog and applying alias rules.

sequenceDiagram
    participant Parser as sqlparser
    participant Translator as translation module
    participant Validator as validation module
    participant Builder as Plan builders
    participant Catalog as TableCatalog
    participant Output as Logical Plans
    
    Parser->>Translator: Statement AST
    
    Note over Translator: Identify statement type\n(SELECT, INSERT, DDL, etc.)
    
    Translator->>Validator: Check schema references
    Validator->>Catalog: Resolve table names
    Catalog-->>Validator: TableMetadataView
    Validator-->>Translator: Validated identifiers
    
    Translator->>Builder: Construct plan with validated data
    
    alt SELECT statement
        Builder->>Builder: Build SelectPlan\n- Parse projections\n- Translate WHERE\n- Extract aggregates\n- Build join metadata
    else INSERT statement
        Builder->>Builder: Build InsertPlan\n- Parse column list\n- Convert values\n- Set conflict action
    else DDL statement
        Builder->>Builder: Build DDL Plan\n- Extract schema info\n- Validate constraints
    end
    
    Builder->>Validator: Final validation pass
    Validator-->>Builder: Approved
    
    Builder->>Output: Typed logical plan

Expression Translation : Predicate and scalar expressions are translated from SQL AST nodes into the llkv-expr expression types (Expr, ScalarExpr). This translation involves converting SQL operators to expression operators, resolving function calls, and tracking subquery placeholders.

Subquery Discovery : The translation layer identifies correlated subqueries in WHERE and SELECT clauses, assigns them unique SubqueryId identifiers, and builds FilterSubquery or ScalarSubquery metadata structures that track which outer columns are referenced.

Sources: llkv-plan/src/plans.rs:1-100 llkv-table/src/resolvers/identifier.rs:1-260

Plan Type Categories

Plans are organized by SQL statement category. Each category has distinct plan structures tailored to its execution requirements:

DDL Plans

Data Definition Language plans modify schema and structure:

DML Plans

Data Manipulation Language plans modify table contents:

Query Plans

SELECT statements produce the most complex plans with nested substructures:

Sources: llkv-plan/src/plans.rs:164-1620

Plan Construction Patterns

Plan structures expose builder-style APIs for incremental construction:

Builder Methods

Most plan types provide fluent builder methods:

CreateTablePlan::new("users")
    .with_if_not_exists(true)
    .with_columns(vec![
        PlanColumnSpec::new("id", DataType::Int64, false)
            .with_primary_key(true),
        PlanColumnSpec::new("name", DataType::Utf8, true),
    ])
    .with_namespace(Some("main".to_string()))

SelectPlan Construction

SelectPlan is built incrementally as the translator walks the SQL AST:

SelectPlan::new("users")
    .with_projections(projections)
    .with_filter(Some(SelectFilter {
        predicate: expr,
        subqueries: vec![],
    }))
    .with_aggregates(aggregates)
    .with_order_by(order_by)
    .with_group_by(group_by_columns)

The with_tables constructor supports multi-table queries:

SelectPlan::with_tables(vec![
    TableRef::new("main", "orders"),
    TableRef::new("main", "customers"),
])
.with_joins(vec![
    JoinMetadata {
        left_table_index: 0,
        join_type: JoinPlan::Inner,
        on_condition: Some(join_expr),
    },
])

Join Metadata

JoinMetadata replaces the older parallel join_types and join_filters vectors by bundling join information into a single structure per join operation. Each entry describes how tables[i] connects to tables[i+1]:

Sources: llkv-plan/src/plans.rs:176-952 llkv-plan/src/plans.rs:756-792

Subquery Plan Structures

Subqueries appear in two contexts and use distinct plan structures:

Filter Subqueries

Used in WHERE clauses with EXISTS predicates:

The SubqueryId links the predicate’s Expr::Exists node to the corresponding FilterSubquery in the subqueries vector.

Scalar Subqueries

Used in SELECT projections to return a single value:

Correlated Column Tracking

When a subquery references outer query columns, the planner injects placeholder column names and tracks the mapping:

CorrelatedColumn {
    placeholder: "__subquery_corr_0_users_id",  // Injected into subquery
    column: "users.id",                          // Actual outer column
    field_path: vec![],                          // Empty for simple columns
}

For struct field references like users.address.city:

CorrelatedColumn {
    placeholder: "__subquery_corr_0_users_address",
    column: "users.address",
    field_path: vec!["city".to_string()],
}

Sources: llkv-plan/src/plans.rs:23-68 llkv-expr/src/expr.rs:42-65

graph TD
    LOGICAL["Logical Plans\n(SelectPlan, InsertPlan, etc.)"]
LOGICAL --> PHYS_BUILD["Physical plan builder\nllkv-plan::physical"]
PHYS_BUILD --> PHYS["PhysicalPlan"]
PHYS --> SCAN["TableScanPlan\nAccess path selection"]
PHYS --> JOIN_EXEC["Join algorithm choice\n(hash join, nested loop)"]
PHYS --> AGG_EXEC["Aggregation strategy"]
PHYS --> SORT_EXEC["Sort algorithm"]
SCAN --> FULL["Full table scan"]
SCAN --> INDEX["Index scan"]
SCAN --> FILTER_SCAN["Filtered scan with pushdown"]
PHYS --> EXEC["llkv-executor\nQuery execution"]

Physical Planning

While logical plans represent what operations to perform, physical plans specify how to execute them with specific algorithms and data access patterns:

The table_scan module provides build_table_scan_plan which analyzes predicates to determine the optimal scan strategy:

TableScanProjectionSpec {
    columns: Vec<String>,           // Columns to retrieve
    filter: Option<Expr>,           // Pushed-down filter
    order_by: Vec<OrderByPlan>,     // Sort requirements
    limit: Option<usize>,           // Row limit
}

This physical plan metadata guides the executor in choosing between:

• Full scans : No filter, read all rows
• Filter scans : Predicate evaluation during scan
• Index scans : Use indexes when available and beneficial

Sources: llkv-plan/src/physical.rs:1-50 (inferred), llkv-plan/src/table_scan.rs:1-50 (inferred)

Translation and Validation

Translation Process

The translation modules convert SQL AST nodes to plan structures while preserving semantic meaning:

Projection Translation :

• SELECT * → SelectProjection::AllColumns
• SELECT * EXCEPT (x) → SelectProjection::AllColumnsExcept
• SELECT col → SelectProjection::Column { name, alias }
• SELECT expr AS name → SelectProjection::Computed { expr, alias }

Predicate Translation : SQL predicates are converted to Expr trees:

• WHERE a = 1 AND b < 2 → Expr::And([Filter(a=1), Filter(b<2)])
• WHERE x IN (1,2,3) → Expr::Pred(Filter { op: Operator::In(...) })
• WHERE EXISTS (SELECT ...) → Expr::Exists(SubqueryExpr { id, negated })

Aggregate Translation : Aggregate functions map to AggregateExpr variants:

• COUNT(*) → AggregateExpr::CountStar
• SUM(col) → AggregateExpr::Column { function: SumInt64, ... }
• AVG(DISTINCT col) → AggregateExpr::Column { distinct: true, ... }

Validation Helpers

The validation module enforces constraints during plan construction:

The validation module provides helper functions that translators invoke at critical points:

• Before plan construction : Validate referenced tables exist
• During expression building : Resolve column identifiers
• After plan assembly : Final consistency checks

Canonical Value Conversion

The canonical module converts PlanValue instances to CanonicalScalar for internal processing:

PlanValue::Integer(42) → CanonicalScalar::Int64(42)
PlanValue::String("abc") → CanonicalScalar::String("abc")
PlanValue::Decimal(dec) → CanonicalScalar::Decimal(dec)

This normalization ensures consistent value representation across plan construction and execution.

Sources: llkv-plan/src/translation.rs:1-50 (inferred), llkv-plan/src/validation.rs:1-50 (inferred), llkv-plan/src/canonical.rs:1-50 (inferred), llkv-plan/src/plans.rs:126-161

Plan Metadata and Auxiliary Types

Plans contain rich metadata to guide execution:

PlanValue

Represents literal values in plans:

ColumnAssignment

UPDATE plans use ColumnAssignment to specify modifications:

ColumnAssignment {
    column: "age",
    value: AssignmentValue::Literal(PlanValue::Integer(25)),
}

ColumnAssignment {
    column: "updated_at",
    value: AssignmentValue::Expression(
        ScalarExpr::Column("current_timestamp")
    ),
}

Constraint Specifications

CREATE TABLE plans include constraint metadata:

PlanColumnSpec {
    name: "id",
    data_type: DataType::Int64,
    nullable: false,
    primary_key: true,
    unique: true,
    check_expr: None,
}

ForeignKeySpec {
    name: Some("fk_orders_customer"),
    columns: vec!["customer_id"],
    referenced_table: "customers",
    referenced_columns: vec!["id"],
    on_delete: ForeignKeyAction::Restrict,
    on_update: ForeignKeyAction::NoAction,
}

MultiColumnUniqueSpec {
    name: Some("unique_email_username"),
    columns: vec!["email", "username"],
}

Sources: llkv-plan/src/plans.rs:73-161 llkv-plan/src/plans.rs:167-427 llkv-plan/src/plans.rs:660-682 llkv-plan/src/plans.rs:499-546

Traversal and Program Compilation

AST Traversal

The traversal module provides generic postorder traversal for deeply nested ASTs:

traverse_postorder(
    root_node,
    |node| { /* pre-visit logic */ },
    |node| { /* post-visit logic */ }
)

This pattern supports:

• Subquery discovery during SELECT translation
• Expression normalization
• Dead code elimination in predicates

Program Compilation

Plans containing expressions are compiled into evaluation programs for efficient execution. The ProgramCompiler converts Expr trees into bytecode-like instruction sequences:

Expr → EvalProgram → Execution

The compiled programs optimize:

• Predicate evaluation order
• Short-circuit boolean logic
• Literal folding
• Domain program generation for chunk pruning

Sources: llkv-plan/src/traversal.rs:1-50 (inferred), llkv-plan/src/lib.rs:38-42

sequenceDiagram
    participant Planner as llkv-plan
    participant Runtime as llkv-runtime
    participant Executor as llkv-executor
    participant Table as llkv-table
    
    Planner->>Runtime: Logical Plan
    Runtime->>Runtime: Acquire transaction context
    
    alt SELECT Plan
        Runtime->>Executor: execute_select(plan, txn)
        Executor->>Executor: Build execution pipeline
        Executor->>Table: scan with filter
        Table-->>Executor: RecordBatch stream
        Executor->>Executor: Apply aggregations, joins, sorts
        Executor-->>Runtime: Final RecordBatch
    else INSERT Plan
        Runtime->>Runtime: Convert InsertSource to batches
        Runtime->>Table: append(batches)
        Table-->>Runtime: Row count
    else UPDATE/DELETE Plan
        Runtime->>Executor: execute_update/delete(plan, txn)
        Executor->>Table: filter + modify
        Table-->>Runtime: Row count
    else DDL Plan
        Runtime->>Table: Modify catalog/schema
        Table-->>Runtime: Success
    end
    
    Runtime->>Planner: Execution result

Integration with Execution

Plans flow from the planning layer to execution through well-defined interfaces:

The execution layer consumes plan metadata to:

1. Determine table access order
2. Select join algorithms
3. Push down predicates to storage
4. Apply aggregations and sorts
5. Stream results incrementally

Sources: llkv-plan/src/plans.rs:1-1620 llkv-executor/src/lib.rs:1-50 (inferred), llkv-runtime/src/lib.rs:1-50 (inferred)

Dismiss

Refresh this wiki

Enter email to refresh

Plan Structures

Loading…

Plan Structures

Relevant source files

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

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

Purpose and Scope

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

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

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

Plan Statement Hierarchy

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

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

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

DDL Plan Structures

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

CreateTablePlan

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

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

PlanColumnSpec

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

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

CreateTableSource

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

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

AlterTablePlan

The AlterTablePlan structure defines table modification operations:

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

Index Plans

Index management is handled by three plan types:

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

DML Plan Structures

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

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

InsertPlan

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

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

UpdatePlan

The UpdatePlan structure defines row update operations:

Each ColumnAssignment maps a column to an AssignmentValue:

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

DeletePlan and TruncatePlan

Both plans remove rows from tables:

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

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

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

SelectPlan Structure

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

Core SelectPlan Fields

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

TableRef and JoinMetadata

Table references include optional aliases and schema qualifications:

Join metadata connects consecutive tables in the tables vector:

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

SelectProjection

The SelectProjection enum defines what columns appear in results:

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

SelectFilter and Subqueries

The SelectFilter structure bundles predicates with correlated subqueries:

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

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

AggregateExpr

Aggregate expressions define computations over grouped data:

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

OrderByPlan

Ordering specifications include target, direction, and null handling:

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

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

Expression Integration

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

Expression Type Hierarchy

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

Expr - Boolean Predicates

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

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

ScalarExpr - Scalar Computations

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

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

Operator Types

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

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

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

Supporting Types

PlanValue

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

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

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

Foreign Key Specifications

Foreign key constraints are defined by ForeignKeySpec:

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

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

Compound Queries

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

This structure allows arbitrary chains of set operations:

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

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

Plan Construction Example

A typical SELECT plan construction follows this pattern:

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

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

Dismiss

Refresh this wiki

Enter email to refresh

Subquery and Correlation Handling

Loading…

Subquery and Correlation Handling

Relevant source files

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

Purpose and Scope

This document explains how LLKV handles correlated and uncorrelated subqueries in SQL queries. It covers the expression AST structures for representing subqueries, the plan-level metadata for tracking correlation relationships, and the placeholder system used during query planning.

For information about query plan structures more broadly, see Plan Structures. For expression evaluation and compilation, see Expression System.

Overview

LLKV supports two categories of subqueries:

1. Predicate Subqueries - Used in WHERE clauses with EXISTS or NOT EXISTS
2. Scalar Subqueries - Used in SELECT projections or expressions, returning a single value

Both types can be either correlated (referencing columns from outer queries) or uncorrelated (self-contained). Correlated subqueries require special handling to capture outer column references and inject them as parameters during evaluation.

The system uses a multi-stage approach:

• Planning Phase : Assign unique SubqueryId values and build metadata
• Translation Phase : Replace correlated column references with placeholders
• Execution Phase : Evaluate subqueries per outer row, binding placeholder values

Sources: llkv-expr/src/expr.rs:45-65 llkv-plan/src/plans.rs:27-67

Subquery Identification System

SubqueryId

Each subquery within a query plan receives a unique SubqueryId identifier. This allows the executor to distinguish multiple subqueries and manage their evaluation contexts separately.

SubqueryId Assignment Flow

graph TB
    Query["Main Query\n(SELECT Plan)"]
Filter["WHERE Clause\n(SelectFilter)"]
Proj["SELECT List\n(Projections)"]
Sub1["EXISTS Subquery\nSubqueryId(0)"]
Sub2["Scalar Subquery\nSubqueryId(1)"]
Sub3["EXISTS Subquery\nSubqueryId(2)"]
Query --> Filter
 
   Query --> Proj
 
   Filter --> Sub1
 
   Filter --> Sub3
 
   Proj --> Sub2
    
    Sub1 -.references.-> Meta1["FilterSubquery\nid=0\nplan + correlations"]
Sub2 -.references.-> Meta2["ScalarSubquery\nid=1\nplan + correlations"]
Sub3 -.references.-> Meta3["FilterSubquery\nid=2\nplan + correlations"]

The planner assigns sequential IDs during query translation. Each subquery expression (Expr::Exists or ScalarExpr::ScalarSubquery) holds its assigned ID, while the full subquery plan and correlation metadata are stored separately in the parent SelectPlan.

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

Expression AST Structures

SubqueryExpr for Predicates

The SubqueryExpr structure appears in boolean expressions as Expr::Exists variants. It supports negation for NOT EXISTS semantics.

Example WHERE clause : WHERE EXISTS (SELECT 1 FROM orders WHERE orders.customer_id = customers.id)

The predicate tree contains Expr::Exists(SubqueryExpr { id: SubqueryId(0), negated: false }), while SelectPlan.filter.subqueries[0] holds the actual subquery plan and correlation data.

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

ScalarSubqueryExpr for Projections

Scalar subqueries return a single value per outer row and appear in ScalarExpr trees. They carry the expected data type for validation.

Example projection : SELECT name, (SELECT COUNT(*) FROM orders WHERE orders.customer_id = customers.id) AS order_count

The expression is ScalarExpr::ScalarSubquery(ScalarSubqueryExpr { id: SubqueryId(0), data_type: Int64 }), with full plan details in SelectPlan.scalar_subqueries[0].

Sources: llkv-expr/src/expr.rs:58-65 llkv-plan/src/plans.rs:47-56

Plan-Level Metadata Structures

classDiagram
    class FilterSubquery {+SubqueryId id\n+Box~SelectPlan~ plan\n+Vec~CorrelatedColumn~ correlated_columns}
    
    class CorrelatedColumn {+String placeholder\n+String column\n+Vec~String~ field_path}
    
    class SelectFilter {+Expr predicate\n+Vec~FilterSubquery~ subqueries}
    
    SelectFilter --> FilterSubquery : contains
    FilterSubquery --> CorrelatedColumn : tracks correlations
    FilterSubquery --> SelectPlan : nested plan

FilterSubquery

This structure captures all metadata needed to evaluate an EXISTS predicate during query execution.

Field Descriptions :

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

ScalarSubquery

Parallel structure for scalar subqueries used in projections:

The plan must produce exactly one row with one column. If the subquery returns zero rows, the executor produces NULL. Multiple rows trigger a runtime error.

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

CorrelatedColumn

Describes a single correlated column reference captured from the outer query:

Example :

• Outer Query : SELECT * FROM customers WHERE ...
• Subquery : SELECT 1 FROM orders WHERE orders.customer_id = customers.id
• CorrelatedColumn : { placeholder: "$corr_0", column: "id", field_path: [] }

During subquery evaluation, the executor binds $corr_0 to the current outer row’s id value.

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

Correlation Tracking System

sequenceDiagram
    participant Planner
    participant Tracker as SubqueryCorrelatedTracker
    participant SubqueryPlan
    
    Planner->>Tracker: new()
    Planner->>Tracker: track_column("customers.id")
    Tracker-->>Planner: placeholder = "$corr_0"
    
    Planner->>SubqueryPlan: Replace "customers.id" with "$corr_0"
    
    Planner->>Tracker: finalize()
    Tracker-->>Planner: Vec<CorrelatedColumn>

Placeholder Naming Convention

The planner module exports SUBQUERY_CORRELATED_PLACEHOLDER_PREFIX which defines the prefix for generated placeholder names. The helper function subquery_correlated_placeholder(index) produces names like $corr_0, $corr_1, etc.

Tracking Workflow :

1. Create SubqueryCorrelatedTracker when entering subquery translation
2. For each outer column reference, call track_column(canonical_name) → returns placeholder
3. Replace column reference in subquery AST with placeholder
4. Call finalize() to extract Vec<CorrelatedColumn> for plan metadata

Sources: llkv-plan/src/lib.rs:43-46

SubqueryCorrelatedColumnTracker

This type (referenced in exports) manages the mapping between outer columns and generated placeholders. It ensures each unique outer column gets one placeholder regardless of how many times it’s referenced in the subquery.

Deduplication Example :

The tracker creates only one CorrelatedColumn entry with a single placeholder $corr_0 that both references use.

Sources: llkv-plan/src/lib.rs:44-45

Integration with Plan Structures

SelectPlan Storage

The SelectPlan structure holds subquery metadata in dedicated fields:

Storage Pattern :

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

Builder Methods

The SelectPlan provides fluent builder methods for attaching subquery metadata:

The planner typically calls these after translating the main query and all nested subqueries.

Sources: llkv-plan/src/plans.rs:895-909

Identifier Resolution During Correlation

graph TB
    OuterQuery["Outer Query\ntable=customers\nalias=c"]
SubqueryScope["Subquery Scope\ntable=orders\nalias=o"]
Identifier["Column Reference:\n'c.id'"]
Resolver["IdentifierResolver"]
OuterQuery --> Context1["IdentifierContext\ntable_id=1\nalias=Some('c')"]
SubqueryScope --> Context2["IdentifierContext\ntable_id=2\nalias=Some('o')"]
Identifier --> Resolver
 
   Resolver --> Decision{"Which scope?"}
Decision -->|Outer| Correlated["Mark as correlated\nGenerate placeholder"]
Decision -->|Inner| Local["Resolve locally"]

IdentifierContext for Outer Scopes

When translating a correlated subquery, the planner maintains an IdentifierContext that tracks which columns belong to outer query scopes vs. the subquery’s own tables.

Resolution Process :

1. Check if identifier starts with outer table alias → mark correlated
2. Check if identifier matches outer table columns (when no alias) → mark correlated
3. Otherwise, resolve within subquery’s own table scope

Sources: llkv-table/src/resolvers/identifier.rs:8-66

ColumnResolution Structure

The resolver produces ColumnResolution objects that distinguish simple column references from nested field access:

For correlated columns, this resolution data flows into CorrelatedColumn.field_path, enabling struct-typed correlation like outer_table.struct_column.nested_field.

Sources: llkv-table/src/resolvers/identifier.rs:68-100

Execution Flow

Evaluation Steps :

1. Outer Row Context : For each row from outer query, create evaluation context
2. Placeholder Binding : Extract values for correlated columns from outer row
3. Subquery Execution : Run inner query with bound placeholder values
4. Result Integration : EXISTS → boolean, Scalar → value, integrate into outer query

The executor must evaluate correlated subqueries once per outer row, making them potentially expensive. Uncorrelated subqueries can be evaluated once and cached.

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

Example: Correlated EXISTS Subquery

Consider this SQL query:

Planning Phase Output

SelectPlan Structure :

SelectPlan {
    tables: [TableRef { table: "customers", alias: Some("c") }],
    projections: [
        Column { name: "name", alias: None },
        Column { name: "id", alias: None }
    ],
    filter: Some(SelectFilter {
        predicate: Expr::Exists(SubqueryExpr {
            id: SubqueryId(0),
            negated: false
        }),
        subqueries: [
            FilterSubquery {
                id: SubqueryId(0),
                plan: Box::new(SelectPlan {
                    tables: [TableRef { table: "orders", alias: Some("o") }],
                    filter: Some(SelectFilter {
                        predicate: Expr::And([
                            Compare { 
                                left: Column("customer_id"), 
                                op: Eq, 
                                right: Column("$corr_0") 
                            },
                            Compare { 
                                left: Column("status"), 
                                op: Eq, 
                                right: Literal("pending") 
                            }
                        ]),
                        subqueries: []
                    }),
                    projections: [Computed { expr: Literal(1), alias: "1" }]
                }),
                correlated_columns: [
                    CorrelatedColumn {
                        placeholder: "$corr_0",
                        column: "id",
                        field_path: []
                    }
                ]
            }
        ]
    }),
    // ... other fields ...
}

Translation Details

The subquery’s filter now compares o.customer_id against the placeholder $corr_0 instead of directly referencing the outer column.

Sources: llkv-plan/src/plans.rs:27-67 llkv-expr/src/expr.rs:49-56

Key Design Decisions

Why Separate FilterSubquery and ScalarSubquery?

Different evaluation semantics:

• EXISTS : Returns boolean, short-circuits on first match
• Scalar : Must verify exactly one row returned, extracts value

Having distinct types allows the executor to apply appropriate validation and optimization strategies.

Why Store SubqueryId in Expression AST?

Decouples expression evaluation from subquery execution context. The expression tree remains lightweight and can be cloned/transformed without carrying full subquery plans. The executor looks up metadata by ID when needed.

Why Use String Placeholders?

String placeholders like $corr_0 integrate naturally with the existing column resolution system. The executor can treat them as special “virtual columns” that get their values from outer row context rather than table scans.

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

Dismiss

Refresh this wiki

Enter email to refresh

Expression System

Loading…

Expression System

Relevant source files

• .github/workflows/build.docs.yml
• demos/llkv-sql-pong-demo/assets/llkv-sql-pong-screenshot.png
• dev-docs/doc-preview.md
• llkv-expr/src/expr.rs
• llkv-plan/Cargo.toml
• llkv-plan/src/plans.rs
• llkv-sql/Cargo.toml
• llkv-test-utils/Cargo.toml

The Expression System provides the foundational Abstract Syntax Tree (AST) and type system for representing predicates, scalar computations, and aggregate functions throughout LLKV’s query processing pipeline. This system decouples expression semantics from concrete Arrow data types through a generic design that allows expressions to be built, translated, optimized, and evaluated independently.

For information about query planning structures that contain these expressions, see Query Planning. For details on how expressions are executed and evaluated, see Query Execution.

Purpose and Scope

This page documents the expression representation layer defined primarily in llkv-expr, covering:

• Boolean predicate expressions (Expr) for WHERE and HAVING clauses
• Scalar arithmetic expressions (ScalarExpr) for projections and computed columns
• Operator types and literal value representations
• Subquery integration points
• Generic field identifier patterns that enable expression translation from column names to internal field IDs

graph TB
    subgraph "Boolean Expression Layer"
        Expr["Expr<'a, F>\nBoolean Predicates"]
ExprAnd["And(Vec<Expr>)"]
ExprOr["Or(Vec<Expr>)"]
ExprNot["Not(Box<Expr>)"]
ExprPred["Pred(Filter)"]
ExprCompare["Compare{left, op, right}"]
ExprInList["InList{expr, list, negated}"]
ExprIsNull["IsNull{expr, negated}"]
ExprLiteral["Literal(bool)"]
ExprExists["Exists(SubqueryExpr)"]
end
    
    subgraph "Scalar Expression Layer"
        ScalarExpr["ScalarExpr<F>\nArithmetic/Values"]
SEColumn["Column(F)"]
SELiteral["Literal(Literal)"]
SEBinary["Binary{left, op, right}"]
SENot["Not(Box<ScalarExpr>)"]
SEIsNull["IsNull{expr, negated}"]
SEAggregate["Aggregate(AggregateCall)"]
SEGetField["GetField{base, field_name}"]
SECast["Cast{expr, data_type}"]
SECompare["Compare{left, op, right}"]
SECoalesce["Coalesce(Vec<ScalarExpr>)"]
SEScalarSubquery["ScalarSubquery(ScalarSubqueryExpr)"]
SECase["Case{operand, branches, else_expr}"]
SERandom["Random"]
end
    
    subgraph "Filter Layer"
        Filter["Filter<'a, F>"]
FilterField["field_id: F"]
FilterOp["op: Operator<'a>"]
end
    
    subgraph "Operator Types"
        Operator["Operator<'a>"]
OpEquals["Equals(Literal)"]
OpRange["Range{lower, upper}"]
OpGT["GreaterThan(Literal)"]
OpLT["LessThan(Literal)"]
OpIn["In(&'a [Literal])"]
OpStartsWith["StartsWith{pattern, case_sensitive}"]
OpEndsWith["EndsWith{pattern, case_sensitive}"]
OpContains["Contains{pattern, case_sensitive}"]
OpIsNull["IsNull"]
OpIsNotNull["IsNotNull"]
end
    
 
   Expr --> ExprAnd
 
   Expr --> ExprOr
 
   Expr --> ExprNot
 
   Expr --> ExprPred
 
   Expr --> ExprCompare
 
   Expr --> ExprInList
 
   Expr --> ExprIsNull
 
   Expr --> ExprLiteral
 
   Expr --> ExprExists
    
 
   ExprPred --> Filter
 
   ExprCompare --> ScalarExpr
 
   ExprInList --> ScalarExpr
 
   ExprIsNull --> ScalarExpr
    
 
   Filter --> FilterField
 
   Filter --> FilterOp
 
   FilterOp --> Operator
    
 
   Operator --> OpEquals
 
   Operator --> OpRange
 
   Operator --> OpGT
 
   Operator --> OpLT
 
   Operator --> OpIn
 
   Operator --> OpStartsWith
 
   Operator --> OpEndsWith
 
   Operator --> OpContains
 
   Operator --> OpIsNull
 
   Operator --> OpIsNotNull
    
 
   ScalarExpr --> SEColumn
 
   ScalarExpr --> SELiteral
 
   ScalarExpr --> SEBinary
 
   ScalarExpr --> SENot
 
   ScalarExpr --> SEIsNull
 
   ScalarExpr --> SEAggregate
 
   ScalarExpr --> SEGetField
 
   ScalarExpr --> SECast
 
   ScalarExpr --> SECompare
 
   ScalarExpr --> SECoalesce
 
   ScalarExpr --> SEScalarSubquery
 
   ScalarExpr --> SECase
 
   ScalarExpr --> SERandom

The Expression System serves as the intermediate representation between SQL parsing and physical execution, allowing optimizations and transformations to occur independently of storage details.

Expression Type Hierarchy

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

Boolean Expressions: Expr<’a, F>

The Expr<'a, F> enum represents logical boolean expressions used in WHERE clauses, HAVING clauses, and JOIN conditions. The generic type parameter F represents field identifiers, allowing the same expression structure to work with string column names during planning and numeric field IDs during execution.

Core Expression Variants

The Expr type provides helper methods for constructing common patterns:

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

Scalar Expressions: ScalarExpr

The ScalarExpr<F> enum represents expressions that compute scalar values, used in SELECT projections, computed columns, and as operands in boolean expressions. These expressions can reference columns, perform arithmetic, call functions, and handle complex nested computations.

Scalar Expression Variants

Operators and Filters

Binary Arithmetic Operators

The BinaryOp enum defines arithmetic and logical operations:

Sources: llkv-expr/src/expr.rs:309-338

Comparison Operators

The CompareOp enum defines relational comparisons:

Sources: llkv-expr/src/expr.rs:340-363

Filter Operators

The Filter<'a, F> struct combines a field identifier with an Operator<'a> to represent single-field predicates. The Operator enum supports specialized operations optimized for columnar storage:

The Operator::Range variant uses Rust’s std::ops::Bound enum to represent inclusive/exclusive bounds, enabling efficient representation of expressions like WHERE age BETWEEN 18 AND 65 or WHERE timestamp >= '2024-01-01'.

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

Literal Value System

The Expression System uses Literal (defined in llkv-expr) to represent untyped constant values in expressions. These are separate from Arrow’s scalar types and provide a lightweight representation that can be coerced to concrete types during execution based on column schemas.

The PlanValue enum (defined in llkv-plan) serves a similar purpose at the plan level, with the conversion function plan_value_from_literal() bridging between the two representations.

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

graph TB
    subgraph "AggregateCall Variants"
        AggregateCall["AggregateCall<F>"]
CountStar["CountStar"]
Count["Count{expr, distinct}"]
Sum["Sum{expr, distinct}"]
Total["Total{expr, distinct}"]
Avg["Avg{expr, distinct}"]
Min["Min(Box<ScalarExpr>)"]
Max["Max(Box<ScalarExpr>)"]
CountNulls["CountNulls(Box<ScalarExpr>)"]
GroupConcat["GroupConcat{expr, distinct, separator}"]
end
    
 
   AggregateCall --> CountStar
 
   AggregateCall --> Count
 
   AggregateCall --> Sum
 
   AggregateCall --> Total
 
   AggregateCall --> Avg
 
   AggregateCall --> Min
 
   AggregateCall --> Max
 
   AggregateCall --> CountNulls
 
   AggregateCall --> GroupConcat
    
 
   Count --> ScalarExprArg["Box<ScalarExpr<F>>"]
Sum --> ScalarExprArg
 
   Total --> ScalarExprArg
 
   Avg --> ScalarExprArg
 
   GroupConcat --> ScalarExprArg

Aggregate Functions

The AggregateCall<F> enum represents aggregate function calls within scalar expressions. Unlike simple column aggregates, these operate on arbitrary expressions:

The key distinction is that each aggregate (except CountStar) accepts a Box<ScalarExpr<F>> rather than just a column name, enabling complex expressions like AVG(col1 + col2) or SUM(-price).

Sources: llkv-expr/src/expr.rs:184-215

Subquery Integration

The Expression System provides integration points for correlated and scalar subqueries through specialized types:

SubqueryExpr

Used in boolean Expr::Exists predicates to represent EXISTS or NOT EXISTS subqueries:

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

ScalarSubqueryExpr

Used in ScalarExpr::ScalarSubquery to represent scalar subqueries that return a single value:

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

SubqueryId

A lightweight wrapper around u32 that uniquely identifies a subquery within a query plan:

The actual subquery definitions are stored in the parent plan structure (e.g., SelectPlan::scalar_subqueries or SelectFilter::subqueries), with expressions referencing them by ID. This design allows the same subquery to be referenced multiple times without duplication.

Sources: llkv-expr/src/expr.rs:45-65 llkv-plan/src/plans.rs:27-67

Generic Field Identifier Pattern

The generic type parameter F in Expr<'a, F>, ScalarExpr<F>, and Filter<'a, F> enables the same expression structure to work at different stages of query processing:

1. Planning Stage : F = String - Expressions use human-readable column names from SQL
2. Translation Stage : F = FieldId - Expressions use table-local field identifiers
3. Execution Stage : F = LogicalFieldId - Expressions use namespace-qualified field identifiers for MVCC columns

This design allows expression trees to be built during SQL parsing, translated to internal identifiers during planning, and evaluated efficiently during execution without changing the fundamental expression structure. The translation process is documented in section Expression Translation.

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

Expression Construction Helpers

Both Expr and ScalarExpr provide builder-style helper methods to simplify expression construction in code:

Boolean Expression Helpers

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

Scalar Expression Helpers

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

Integration with Query Plans

The Expression System integrates with query plans through several key structures defined in llkv-plan:

SelectFilter

Wraps a boolean expression with associated correlated subqueries:

FilterSubquery

Describes a correlated subquery referenced by an EXISTS predicate:

ScalarSubquery

Describes a scalar subquery referenced in a projection expression:

CorrelatedColumn

Maps placeholder column names used in subquery expressions to actual outer query columns:

Plans attach these structures to represent the full expression context, allowing executors to evaluate subqueries with proper outer row bindings.

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

Expression System Data Flow

Sources: llkv-expr/src/expr.rs llkv-plan/src/plans.rs:27-1032

Key Design Principles

Type-Safe Generic Design

The generic field identifier pattern (F in Expr<'a, F>) provides compile-time type safety while allowing the same expression structure to work at different pipeline stages. This eliminates the need for multiple parallel expression type hierarchies.

Deferred Type Resolution

Literal values remain untyped until evaluation time, when they are coerced based on the target column’s Arrow DataType. This allows expressions like WHERE age > 18 to work correctly whether age is Int8, Int32, or Int64.

Zero-Copy Operator Patterns

The Operator::In(&'a [Literal]) variant borrows a slice of literals rather than owning a Vec, enabling stack-allocated IN lists without heap allocation for common small cases.

Expression Rewriting Support

The is_trivially_true() and is_full_range_for() helper methods enable query optimizers to identify and eliminate redundant predicates without deep tree traversals.

Subquery Indirection

Subqueries are represented by SubqueryId references rather than inline nested plans, allowing the same subquery to be referenced multiple times without duplication and enabling separate optimization of inner and outer queries.

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

Dismiss

Refresh this wiki

Enter email to refresh

Expression AST

Loading…

Expression AST

Relevant source files

• llkv-expr/src/expr.rs
• llkv-plan/src/plans.rs

Purpose and Scope

The Expression AST defines the abstract syntax tree for all logical and arithmetic expressions in LLKV. This module provides the core data structures used to represent predicates, scalar computations, aggregations, and subqueries throughout the query processing pipeline. The AST is type-agnostic and decoupled from Arrow’s concrete scalar types, allowing expressions to be constructed, transformed, and optimized before being bound to specific table schemas.

For information about translating expressions from string column names to field identifiers, see Expression Translation. For information about compiling expressions into executable bytecode, see Program Compilation. For information about evaluating expressions against data, see Scalar Evaluation and NumericKernels.

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

Expression System Architecture

The expression system consists of two primary AST types that serve distinct purposes in query processing:

Expr<'a, F> represents boolean-valued expressions used in WHERE clauses, HAVING clauses, and join conditions. These expressions combine logical operators (AND, OR, NOT) with predicates that test column values against literals or ranges.

graph TB
    subgraph "Boolean Predicates"
        Expr["Expr<'a, F>\nBoolean logic"]
Filter["Filter<'a, F>\nField predicate"]
Operator["Operator<'a>\nComparison operators"]
end
    
    subgraph "Value Expressions"
        ScalarExpr["ScalarExpr<F>\nArithmetic expressions"]
BinaryOp["BinaryOp\n+, -, *, /, %"]
CompareOp["CompareOp\n=, !=, <, >"]
AggregateCall["AggregateCall<F>\nCOUNT, SUM, AVG"]
end
    
    subgraph "Supporting Types"
        Literal["Literal\nType-agnostic values"]
SubqueryExpr["SubqueryExpr\nEXISTS predicate"]
ScalarSubqueryExpr["ScalarSubqueryExpr\nScalar subquery"]
end
    
 
   Expr --> Filter
 
   Filter --> Operator
 
   Expr --> ScalarExpr
 
   ScalarExpr --> BinaryOp
 
   ScalarExpr --> CompareOp
 
   ScalarExpr --> AggregateCall
 
   ScalarExpr --> Literal
 
   Expr --> SubqueryExpr
 
   ScalarExpr --> ScalarSubqueryExpr
 
   Operator --> Literal

ScalarExpr<F> represents value-producing expressions used in SELECT projections, computed columns, and UPDATE assignments. These expressions support arithmetic operations, function calls, type casts, and complex nested computations.

Both types are parameterized by a generic field identifier type F, enabling the same AST structures to be used with different column reference schemes (e.g., String names during planning, FieldId integers during execution).

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

Boolean Predicate Expressions

The Expr<'a, F> enum represents logical expressions that evaluate to boolean values. It forms the foundation for filtering operations throughout the query engine.

graph TD
    Expr["Expr<'a, F>"]
And["And(Vec<Expr>)\nLogical conjunction"]
Or["Or(Vec<Expr>)\nLogical disjunction"]
Not["Not(Box<Expr>)\nLogical negation"]
Pred["Pred(Filter)\nField predicate"]
Compare["Compare\nScalar comparison"]
InList["InList\nSet membership"]
IsNull["IsNull\nNULL test"]
Literal["Literal(bool)\nConstant boolean"]
Exists["Exists(SubqueryExpr)\nCorrelated EXISTS"]
Expr --> And
 
   Expr --> Or
 
   Expr --> Not
 
   Expr --> Pred
 
   Expr --> Compare
 
   Expr --> InList
 
   Expr --> IsNull
 
   Expr --> Literal
 
   Expr --> Exists

Expr Variants

The And and Or variants accept vectors of expressions, allowing efficient representation of multi-way logical operations without deep nesting. The Pred variant wraps a Filter<'a, F> structure for simple single-column predicates, which can be efficiently pushed down to storage layer scanning operations.

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

Filter and Operator Types

The Filter<'a, F> structure encapsulates a single predicate against a field, combining a field identifier with an operator:

The Operator<'a> enum defines comparison and pattern-matching operations over untyped Literal values:

The In operator accepts a borrowed slice of literals to avoid allocations for small, static IN lists. The pattern-matching operators (StartsWith, EndsWith, Contains) support both case-sensitive and case-insensitive matching.

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

graph TD
    ScalarExpr["ScalarExpr<F>"]
Column["Column(F)\nField reference"]
Literal["Literal\nConstant value"]
Binary["Binary\nArithmetic operation"]
Not["Not\nLogical negation"]
IsNull["IsNull\nNULL test"]
Aggregate["Aggregate\nAggregate function"]
GetField["GetField\nStruct field access"]
Cast["Cast\nType conversion"]
Compare["Compare\nBoolean comparison"]
Coalesce["Coalesce\nFirst non-NULL"]
ScalarSubquery["ScalarSubquery\nSubquery result"]
Case["Case\nConditional expression"]
Random["Random\nRandom number"]
ScalarExpr --> Column
 
   ScalarExpr --> Literal
 
   ScalarExpr --> Binary
 
   ScalarExpr --> Not
 
   ScalarExpr --> IsNull
 
   ScalarExpr --> Aggregate
 
   ScalarExpr --> GetField
 
   ScalarExpr --> Cast
 
   ScalarExpr --> Compare
 
   ScalarExpr --> Coalesce
 
   ScalarExpr --> ScalarSubquery
 
   ScalarExpr --> Case
 
   ScalarExpr --> Random

Scalar Value Expressions

The ScalarExpr<F> enum represents expressions that produce scalar values. These are used in SELECT projections, computed columns, ORDER BY clauses, and anywhere a value (rather than a boolean) is needed.

ScalarExpr Variants

The Binary variant supports arithmetic operators (+, -, *, /, %) as well as logical operators (AND, OR) and bitwise shift operators (<<, >>). The Compare variant produces boolean results (represented as 1/0 integers) from comparisons like col1 > col2.

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

Binary and Comparison Operators

The BinaryOp enum defines arithmetic and logical binary operators:

The CompareOp enum defines comparison operators for scalar expressions:

These operators enable complex arithmetic expressions like (price * quantity * (1 - discount)) > 1000 and nested logical operations like (col1 + col2) > (col3 * 2) AND status = 'active'.

Sources: llkv-expr/src/expr.rs:309-363

Aggregate Function Calls

The AggregateCall<F> enum represents aggregate function invocations within scalar expressions. Unlike simple column aggregates, these variants operate on full expressions, enabling aggregations like AVG(col1 + col2) or SUM(-price).

graph LR
    AggregateCall["AggregateCall<F>"]
CountStar["CountStar\nCOUNT(*)"]
Count["Count { expr, distinct }\nCOUNT(expr)"]
Sum["Sum { expr, distinct }\nSUM(expr)"]
Total["Total { expr, distinct }\nTOTAL(expr)"]
Avg["Avg { expr, distinct }\nAVG(expr)"]
Min["Min(expr)\nMIN(expr)"]
Max["Max(expr)\nMAX(expr)"]
CountNulls["CountNulls(expr)\nCOUNT_NULLS(expr)"]
GroupConcat["GroupConcat { expr, distinct, separator }\nGROUP_CONCAT(expr)"]
AggregateCall --> CountStar
 
   AggregateCall --> Count
 
   AggregateCall --> Sum
 
   AggregateCall --> Total
 
   AggregateCall --> Avg
 
   AggregateCall --> Min
 
   AggregateCall --> Max
 
   AggregateCall --> CountNulls
 
   AggregateCall --> GroupConcat

AggregateCall Variants

All variants except CountStar accept a Box<ScalarExpr<F>>, allowing aggregates to operate on computed expressions. For example, SUM(price * quantity) is represented as:

AggregateCall::Sum {
    expr: Box::new(ScalarExpr::Binary {
        left: Box::new(ScalarExpr::Column("price")),
        op: BinaryOp::Multiply,
        right: Box::new(ScalarExpr::Column("quantity")),
    }),
    distinct: false,
}

Sources: llkv-expr/src/expr.rs:184-215 llkv-expr/src/expr.rs:217-307

Subquery Integration

The expression AST supports two forms of subquery integration: boolean EXISTS predicates and scalar subqueries that produce single values.

Boolean EXISTS Subqueries

The SubqueryExpr structure represents a correlated EXISTS predicate within a boolean expression:

The id field references a subquery definition stored separately in the query plan (see FilterSubquery in llkv-plan/src/plans.rs:36-45), while negated indicates whether the SQL used NOT EXISTS. The separation of subquery metadata from the expression tree allows the same subquery to be referenced multiple times without duplication.

Scalar Subqueries

The ScalarSubqueryExpr structure represents a subquery that returns a single scalar value:

graph TB
    SelectPlan["SelectPlan"]
ExprFilter["filter: Option<SelectFilter>"]
SelectFilter["SelectFilter"]
Predicate["predicate: Expr<'static, String>"]
FilterSubqueries["subqueries: Vec<FilterSubquery>"]
ScalarSubqueries["scalar_subqueries: Vec<ScalarSubquery>"]
Projections["projections: Vec<SelectProjection>"]
ComputedProj["Computed { expr, alias }"]
ScalarExpr["expr: ScalarExpr<String>"]
SelectPlan --> ExprFilter
 
   ExprFilter --> SelectFilter
 
   SelectFilter --> Predicate
 
   SelectFilter --> FilterSubqueries
    
 
   SelectPlan --> ScalarSubqueries
 
   SelectPlan --> Projections
 
   Projections --> ComputedProj
 
   ComputedProj --> ScalarExpr
    
    Predicate -.references.-> FilterSubqueries
    ScalarExpr -.references.-> ScalarSubqueries

Scalar subqueries appear in value-producing contexts like SELECT (SELECT MAX(price) FROM items) AS max_price or WHERE quantity > (SELECT AVG(quantity) FROM inventory). The data_type field captures the Arrow data type of the subquery’s output column, enabling type checking during expression compilation.

The query planner populates the subqueries field in SelectFilter and the scalar_subqueries field in SelectPlan with complete subquery definitions, while expressions reference them by SubqueryId. This architecture enables efficient subquery execution and correlation tracking during query evaluation.

Sources: llkv-expr/src/expr.rs:45-66 llkv-plan/src/plans.rs:27-67

Literal Values

Expressions reference the Literal type from the llkv-expr crate’s literal module to represent constant values. The literal system is type-agnostic, deferring concrete type resolution until expressions are evaluated against actual table schemas.

The Literal enum (defined in llkv-expr/src/literal.rs) supports:

• Null : SQL NULL value
• Int128(i128) : Integer literals (wide representation to handle all integer sizes)
• Float64(f64) : Floating-point literals
• Decimal128(DecimalValue) : Fixed-precision decimal literals
• String(String) : Text literals
• Boolean(bool) : True/false literals
• Date32(i32) : Date literals (days since Unix epoch)
• Struct(Vec <(String, Literal)>): Structured data literals
• Interval(IntervalValue) : Time interval literals

The use of Int128 for integer literals allows the expression system to represent values that may exceed i64 range during intermediate computations, with overflow checks deferred to evaluation time. The Decimal128 variant uses the DecimalValue type from llkv-types to maintain precision and scale metadata.

Literals can be constructed through From trait implementations, enabling ergonomic expression building:

Sources: llkv-expr/src/expr.rs10

Type Parameterization and Field References

Both Expr<'a, F> and ScalarExpr<F> are parameterized by a generic type F that represents field identifiers. This design enables the same AST structures to be used at different stages of query processing with different column reference schemes:

graph LR
    subgraph "Planning Stage"
        ExprString["Expr<'static, String>\nColumn names"]
ScalarString["ScalarExpr<String>\nColumn names"]
end
    
    subgraph "Translation Stage"
        Translator["Expression Translator"]
end
    
    subgraph "Execution Stage"
        ExprFieldId["Expr<'static, FieldId>\nNumeric IDs"]
ScalarFieldId["ScalarExpr<FieldId>\nNumeric IDs"]
end
    
 
   ExprString --> Translator
 
   ScalarString --> Translator
 
   Translator --> ExprFieldId
 
   Translator --> ScalarFieldId

Common Type Instantiations

The lifetime parameter 'a in Expr<'a, F> represents the lifetime of borrowed data in Operator::In(&'a [Literal]), allowing filter expressions to reference static IN lists without heap allocation. Most expressions use 'static lifetime, indicating no borrowed data.

Field Reference Translation

The expression translation system (see Expression Translation) converts expressions from string-based column names to numeric FieldId identifiers by walking the AST and resolving names against table schemas. This transformation is represented by the generic parameter substitution:

Expr<'static, String>  →  Expr<'static, FieldId>
ScalarExpr<String>     →  ScalarExpr<FieldId>

The generic design allows the same expression evaluation logic to work with both naming schemes without code duplication, while maintaining type safety at compile time.

Sources: llkv-expr/src/expr.rs:14-21 llkv-expr/src/expr.rs:125-134 llkv-expr/src/expr.rs:365-370

Expression Construction Helpers

Both Expr and ScalarExpr provide builder methods for ergonomic AST construction:

Expr Helpers

ScalarExpr Helpers

These helpers simplify expression construction in query planners and translators by providing clearer semantics than direct enum variant construction.

Sources: llkv-expr/src/expr.rs:67-86 llkv-expr/src/expr.rs:217-307

Expression Analysis Methods

The Expr type provides utility methods for analyzing expression structure and optimizing query execution:

The is_trivially_true() method identifies expressions that cannot filter out any rows, such as:

• Unbounded range filters: Operator::Range { lower: Unbounded, upper: Unbounded }
• Literal true values: Expr::Literal(true)

Scan executors use this method to skip predicate evaluation entirely when the filter is guaranteed to match all rows, avoiding unnecessary computation.

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

graph TB
    subgraph "Query Plans"
        SelectPlan["SelectPlan"]
InsertPlan["InsertPlan"]
UpdatePlan["UpdatePlan"]
DeletePlan["DeletePlan"]
end
    
    subgraph "Expression Usage"
        FilterUsage["filter: Option<SelectFilter>\nWHERE clauses"]
HavingUsage["having: Option<Expr>\nHAVING clauses"]
ProjUsage["projections with ScalarExpr\nSELECT list"]
UpdateExpr["assignments with ScalarExpr\nSET clauses"]
JoinOn["on_condition in JoinMetadata\nJOIN ON clauses"]
end
    
 
   SelectPlan --> FilterUsage
 
   SelectPlan --> HavingUsage
 
   SelectPlan --> ProjUsage
 
   SelectPlan --> JoinOn
    
 
   UpdatePlan --> UpdateExpr
 
   UpdatePlan --> FilterUsage
    
 
   DeletePlan --> FilterUsage

Integration with Query Plans

Expressions integrate deeply with the query planning system defined in llkv-plan:

Expression Usage in Plans

All plan-level expressions use String as the field identifier type since plans are constructed during SQL parsing before schema resolution. The query executor translates these to FieldId-based expressions before evaluation.

Sources: llkv-plan/src/plans.rs:27-34 llkv-plan/src/plans.rs:660-692 llkv-plan/src/plans.rs:794-828

Dismiss

Refresh this wiki

Enter email to refresh

Expression Translation

Loading…

Expression Translation

Relevant source files

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

Purpose and Scope

Expression Translation is the process of converting expressions that reference columns by name (as strings) into expressions that reference columns by numeric field identifiers (FieldId). This translation bridges the gap between the SQL parsing/planning layer—which operates on human-readable column names—and the execution layer, which requires efficient numeric field identifiers for accessing columnar storage.

This page documents the translation mechanisms, key functions, and integration points. For information about the expression AST types themselves, see Expression AST. For details on how translated expressions are compiled into executable programs, see Program Compilation.

Sources: llkv-expr/src/expr.rs:1-819 llkv-executor/src/lib.rs:87-97

The Parameterized Expression Type System

The LLKV expression system uses generic type parameters to support multiple identifier types throughout the query processing pipeline. All expression types are parameterized over a field identifier type F:

The parameterization allows the same expression structures to be used with different identifier representations:

• During Planning : Expr<'static, String> and ScalarExpr<String> use column names as parsed from SQL
• During Execution : Expr<'static, FieldId> and ScalarExpr<FieldId> use numeric field identifiers for efficient storage access

graph TD
    subgraph "SQL Parsing Layer"
        SQL["SQL Query Text"]
PARSER["sqlparser"]
AST["SQL AST"]
end
    
    subgraph "Planning Layer"
        PLANNER["Query Planner"]
EXPR_STRING["Expr<String>\nScalarExpr<String>"]
PLAN["SelectPlan"]
end
    
    subgraph "Translation Layer"
        TRANSLATOR["translate_scalar\ntranslate_predicate"]
SCHEMA["Schema / Catalog"]
RESOLVER["IdentifierResolver"]
end
    
    subgraph "Execution Layer"
        EXPR_FIELDID["Expr<FieldId>\nScalarExpr<FieldId>"]
EVALUATOR["Expression Evaluator"]
STORAGE["Column Store"]
end
    
 
   SQL --> PARSER
 
   PARSER --> AST
 
   AST --> PLANNER
 
   PLANNER --> EXPR_STRING
 
   EXPR_STRING --> PLAN
    
 
   PLAN --> TRANSLATOR
 
   SCHEMA --> TRANSLATOR
 
   RESOLVER --> TRANSLATOR
 
   TRANSLATOR --> EXPR_FIELDID
    
 
   EXPR_FIELDID --> EVALUATOR
 
   EVALUATOR --> STORAGE

This design separates concerns: the planner manipulates human-readable names without needing catalog knowledge, while the executor works with resolved numeric identifiers that map directly to physical storage locations.

Diagram: Expression Translation Flow from SQL to Execution

Sources: llkv-expr/src/expr.rs:14-182 llkv-executor/src/lib.rs:87-97

Core Translation Functions

The translation layer exposes a set of functions for converting string-based expressions to field ID-based expressions. These functions are defined in the llkv-plan crate’s translation module and re-exported by llkv-executor for convenience.

Primary Translation Functions

The _with variants accept an IdentifierResolver reference for more complex scenarios (multi-table queries, subqueries, etc.), while the simpler variants accept a schema directly and construct a resolver internally.

Usage Pattern

Translation functions follow a consistent pattern: they take a string-based expression, schema/resolver information, and an error handler closure. The error handler is invoked when a column name cannot be resolved, allowing callers to customize error messages:

The error closure receives the unresolved column name and returns an appropriate error type. This pattern appears throughout the executor when translating expressions from plans:

Sources: llkv-executor/src/lib.rs:87-97 llkv-executor/src/lib.rs:485-489 llkv-executor/src/lib.rs:1054-1059

Schema-Based Resolution

Column name resolution relies on Arrow schema information to map string identifiers to numeric field IDs. The resolution process handles case-insensitive matching and validates that referenced columns actually exist in the schema.

graph LR
    subgraph "Input"
        EXPR_STR["ScalarExpr<String>"]
COLUMN_NAME["Column Name: 'user_id'"]
end
    
    subgraph "Resolution Context"
        SCHEMA["Arrow Schema"]
FIELDS["Field Definitions"]
METADATA["Field Metadata"]
end
    
    subgraph "Resolution Process"
        NORMALIZE["Normalize Name\n(case-insensitive)"]
LOOKUP["Lookup in Schema"]
EXTRACT_ID["Extract FieldId"]
end
    
    subgraph "Output"
        EXPR_FIELD["ScalarExpr<FieldId>"]
FIELD_ID["FieldId: 42"]
end
    
 
   COLUMN_NAME --> NORMALIZE
 
   SCHEMA --> LOOKUP
 
   NORMALIZE --> LOOKUP
 
   LOOKUP --> EXTRACT_ID
 
   EXTRACT_ID --> FIELD_ID
    
 
   EXPR_STR --> NORMALIZE
 
   EXTRACT_ID --> EXPR_FIELD

Resolution Workflow

Diagram: Column Name to FieldId Resolution

The resolve_field_id_from_schema function performs the core resolution logic. It searches the schema’s field definitions for a matching column name and extracts the associated field ID from the field’s metadata.

Schema Structure

Arrow schemas used during translation contain:

• Field Definitions : Name, data type, nullability
• Field Metadata : Key-value pairs including the numeric field ID
• Nested Field Support : For struct types, schemas may contain nested field hierarchies

The translation process must handle qualified names (e.g., table.column), nested field access (e.g., user.address.city), and alias resolution when applicable.

Sources: llkv-executor/src/lib.rs:87-97

Field Path Resolution for Nested Fields

When expressions reference nested fields within struct types, the translation process must resolve not just the top-level column but the entire field path. This is handled through the IdentifierResolver and ColumnResolution types provided by llkv-table/catalog.

graph TD
    subgraph "Input Expression"
        NESTED["GetField Expression"]
BASE["base: user"]
FIELD["field_name: 'address'"]
SUBFIELD["field_name: 'city'"]
end
    
    subgraph "Resolver"
        RESOLVER["IdentifierResolver"]
CONTEXT["IdentifierContext"]
end
    
    subgraph "Resolution Result"
        COL_RES["ColumnResolution"]
COL_NAME["column(): 'user'"]
FIELD_PATH["field_path(): ['address', 'city']"]
FIELD_ID["Resolved FieldId"]
end
    
 
   NESTED --> RESOLVER
 
   CONTEXT --> RESOLVER
 
   RESOLVER --> COL_RES
 
   COL_RES --> COL_NAME
 
   COL_RES --> FIELD_PATH
 
   COL_RES --> FIELD_ID

ColumnResolution Structure

Diagram: Nested Field Resolution

The ColumnResolution type encapsulates the resolution result, providing:

• The base column name
• The field path for nested access (empty for top-level columns)
• The resolved field ID for storage access

This information is used during correlated subquery tracking and when translating GetField expressions in the scalar expression tree.

Sources: llkv-sql/src/sql_engine.rs:37-38 llkv-sql/src/sql_engine.rs:420-427

Translation in Multi-Table Contexts

When translating expressions for queries involving multiple tables (joins, cross products, subqueries), the translation process must disambiguate column references that may appear in multiple tables. This is handled by the IdentifierResolver which maintains context about available tables and their schemas.

IdentifierContext and Resolution

The IdentifierContext type (from llkv-table/catalog) represents the set of tables and columns available in a given scope. During translation:

1. Outer Scope Tracking : For subqueries, outer table contexts are tracked separately
2. Column Disambiguation : Qualified names (e.g., table.column) are resolved against the appropriate table
3. Ambiguity Detection : Unqualified references to columns that exist in multiple tables produce errors

The translate_predicate_with and translate_scalar_with functions accept an IdentifierResolver reference that encapsulates this context:

Sources: llkv-sql/src/sql_engine.rs:37-38

Error Handling and Diagnostics

Translation failures occur when column names cannot be resolved. The error handling strategy uses caller-provided closures to generate context-specific error messages.

Error Patterns

The error closure pattern allows the caller to include query-specific context in error messages. This is particularly important for debugging complex queries where the same expression type might be used in multiple contexts.

Resolution Failure Example

When translate_scalar encounters a ScalarExpr::Column(name) variant and the name cannot be found in the schema, it invokes the error closure:

Sources: llkv-executor/src/lib.rs:485-489 llkv-executor/src/lib.rs:1054-1059

graph TB
    subgraph "Planning Phase"
        SQL["SQL Statement"]
PARSE["Parse & Build Plan"]
PLAN["SelectPlan\nUpdatePlan\netc."]
EXPR_STR["Expressions with\nString identifiers"]
end
    
    subgraph "Execution Preparation"
        GET_TABLE["Get Table Handle"]
SCHEMA_FETCH["Fetch Schema"]
TRANSLATE["Translation Functions"]
EXPR_FIELD["Expressions with\nFieldId identifiers"]
end
    
    subgraph "Execution Phase"
        BUILD_SCAN["Build ScanProjection"]
COMPILE["Compile to EvalProgram"]
EVALUATE["Evaluate Against Batches"]
RESULTS["RecordBatch Results"]
end
    
 
   SQL --> PARSE
 
   PARSE --> PLAN
 
   PLAN --> EXPR_STR
    
 
   PLAN --> GET_TABLE
 
   GET_TABLE --> SCHEMA_FETCH
 
   SCHEMA_FETCH --> TRANSLATE
 
   EXPR_STR --> TRANSLATE
 
   TRANSLATE --> EXPR_FIELD
    
 
   EXPR_FIELD --> BUILD_SCAN
 
   BUILD_SCAN --> COMPILE
 
   COMPILE --> EVALUATE
 
   EVALUATE --> RESULTS

Integration with Query Execution Pipeline

Expression translation occurs at the boundary between planning and execution. Plans produced by the SQL layer contain string-based expressions, which are translated as execution structures are built.

Translation Points in Execution

Diagram: Translation in the Execution Pipeline

Key Translation Points

1. Filter Translation : When building scan plans, WHERE clause expressions are translated before being passed to the scan optimizer
2. Projection Translation : Computed columns in SELECT projections are translated before evaluation
3. Aggregate Translation : Aggregate function arguments are translated to resolve column references
4. Join Condition Translation : ON clause expressions for joins are translated in the context of both joined tables

The executor’s ensure_computed_projection function demonstrates this integration. It translates a string-based expression, infers its result data type, and registers it as a computed projection for the scan:

This function encapsulates the full translation workflow: resolve column names, infer types, and prepare the translated expression for execution.

Sources: llkv-executor/src/lib.rs:470-501 llkv-executor/src/lib.rs:87-97

Translation of Complex Expression Types

The translation process must handle all variants of the expression AST, recursively translating nested expressions while preserving structure and semantics.

Recursive Translation Table

For predicate expressions (Expr<F>):

The translation process maintains the expression tree structure while substituting field identifiers, ensuring that evaluation semantics remain unchanged.

Sources: llkv-expr/src/expr.rs:125-182 llkv-expr/src/expr.rs:14-66

Performance Considerations

Expression translation is performed once during query execution setup, not per-row or per-batch. The translated expressions are then compiled into evaluation programs (see Program Compilation) which are reused across all batches in the query result.

Translation Caching

The executor maintains caches to avoid redundant translation work:

• Computed Projection Cache : Stores translated expressions keyed by their string representation to avoid re-translating identical expressions in the same query
• Column Projection Cache : Maps field IDs to projection indices to reuse existing projections when multiple expressions reference the same column

This caching strategy is evident in functions like ensure_computed_projection, which checks the cache before performing translation:

Sources: llkv-executor/src/lib.rs:470-501

Dismiss

Refresh this wiki

Enter email to refresh

Program Compilation

Loading…

Program Compilation

Relevant source files

• .github/workflows/build.docs.yml
• demos/llkv-sql-pong-demo/assets/llkv-sql-pong-screenshot.png
• dev-docs/doc-preview.md
• llkv-expr/src/expr.rs
• llkv-plan/Cargo.toml
• llkv-plan/src/plans.rs
• llkv-sql/Cargo.toml
• llkv-test-utils/Cargo.toml

Purpose and Scope

Program compilation transforms expression ASTs into executable bytecode optimized for evaluation. This intermediate representation enables efficient vectorized operations and simplifies the runtime evaluation engine. The compilation phase bridges the gap between high-level expression trees and low-level execution kernels.

This page covers the compilation of ScalarExpr and filter Expr trees into EvalProgram and DomainProgram bytecode respectively. For information about the expression AST structure, see Expression AST. For how compiled programs are evaluated, see Scalar Evaluation and NumericKernels.

Compilation Pipeline Overview

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

Compilation Targets

The compilation system produces two distinct bytecode formats depending on the expression context:

EvalProgram Structure

EvalProgram compiles scalar expressions into a stack-based bytecode suitable for vectorized evaluation. Each instruction operates on Arrow arrays, producing intermediate or final results:

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

flowchart TB
    subgraph ScalarInput["Scalar Expression Tree"]
ROOT["Binary: Add"]
LEFT["Binary: Multiply"]
RIGHT["Cast: Float64"]
COL1["Column: field_id=1"]
LIT1["Literal: 10"]
COL2["Column: field_id=2"]
end
    
 
   ROOT --> LEFT
 
   ROOT --> RIGHT
 
   LEFT --> COL1
 
   LEFT --> LIT1
 
   RIGHT --> COL2
    
    subgraph Bytecode["EvalProgram Bytecode"]
I1["LOAD_COLUMN field_id=1"]
I2["LOAD_LITERAL 10"]
I3["MULTIPLY"]
I4["LOAD_COLUMN field_id=2"]
I5["CAST Float64"]
I6["ADD"]
end
    
 
   I1 --> I2
 
   I2 --> I3
 
   I3 --> I4
 
   I4 --> I5
 
   I5 --> I6
    
    subgraph Execution["Execution"]
STACK["Evaluation Stack\nArray-based operations"]
RESULT["Result Array"]
end
    
 
   I6 --> STACK
 
   STACK --> RESULT

DomainProgram Structure

DomainProgram compiles filter predicates into bytecode optimized for boolean evaluation and row filtering. The program operates on column metadata and data chunks to identify matching rows:

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

flowchart TB
    subgraph FilterInput["Filter Expression Tree"]
AND["And"]
PRED1["Pred: field_id=1 > 100"]
PRED2["Pred: field_id=2 IN values"]
NOT["Not"]
PRED3["Pred: field_id=3 LIKE pattern"]
end
    
 
   AND --> PRED1
 
   AND --> NOT
 
   NOT --> PRED2
 
   AND --> PRED3
    
    subgraph DomainBytecode["DomainProgram Bytecode"]
D1["EVAL_PRED field_id=1\nGreaterThan 100"]
D2["EVAL_PRED field_id=2\nIn values"]
D3["NEGATE"]
D4["EVAL_PRED field_id=3\nContains pattern"]
D5["AND_ALL"]
end
    
 
   D1 --> D2
 
   D2 --> D3
 
   D3 --> D4
 
   D4 --> D5
    
    subgraph BitmapOps["Bitmap Operations"]
B1["Bitmap: field_id=1 matches"]
B2["Bitmap: field_id=2 matches"]
B3["Bitmap: NOT operation"]
B4["Bitmap: field_id=3 matches"]
B5["Bitmap: AND operation"]
FINAL["Final: matching row IDs"]
end
    
 
   D5 --> B1
 
   B1 --> B2
 
   B2 --> B3
 
   B3 --> B4
 
   B4 --> B5
 
   B5 --> FINAL

Expression Analysis and Type Inference

Before bytecode generation, the compiler analyzes the expression tree to:

1. Resolve data types - Each expression node’s output type is inferred from its inputs and operation
2. Validate operations - Ensure type compatibility for binary operations and function calls
3. Track dependencies - Identify which columns and subqueries the expression requires
4. Detect constant subexpressions - Find opportunities for constant folding

Sources: llkv-expr/src/expr.rs:125-182 llkv-expr/src/expr.rs:309-363

Compilation Optimizations

The compilation phase applies several optimization passes to improve evaluation performance:

Constant Folding

Expressions involving only literal values are evaluated at compile time:

Expression Simplification

Algebraic identities and boolean logic simplifications reduce instruction count:

Dead Code Elimination

Unreachable code paths in Case expressions are removed:

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

Bytecode Generation

After optimization, the compiler generates bytecode instructions by walking the expression tree in post-order (depth-first). Each expression variant maps to one or more bytecode instructions:

Scalar Expression Instruction Mapping

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

Filter Expression Instruction Mapping

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

Subquery Handling

Correlated subqueries require special compilation handling. The compiler generates placeholder references that are resolved during execution:

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

flowchart TB
    subgraph Outer["Outer Query Expression"]
FILTER["Filter with EXISTS"]
SUBQUERY["Subquery: SubqueryId=1\nCorrelated columns"]
end
    
    subgraph Compilation["Compilation Strategy"]
PLACEHOLDER["Generate EVAL_SUBQUERY\ninstruction with ID"]
CORRELATION["Track correlated\ncolumn mappings"]
DEFER["Defer actual subquery\ncompilation to executor"]
end
    
    subgraph Execution["Runtime Resolution"]
BIND["Bind outer row values\nto correlated placeholders"]
EVAL_SUB["Execute subquery plan\nwith bound values"]
COLLECT["Collect subquery\nresult set"]
BOOLEAN["Convert to boolean\nfor EXISTS/IN"]
end
    
 
   FILTER --> SUBQUERY
 
   SUBQUERY --> PLACEHOLDER
 
   PLACEHOLDER --> CORRELATION
 
   CORRELATION --> DEFER
    
 
   DEFER --> BIND
 
   BIND --> EVAL_SUB
 
   EVAL_SUB --> COLLECT
 
   COLLECT --> BOOLEAN

Aggregate Function Compilation

Aggregate expressions within scalar contexts (e.g., COUNT(*) + 1) compile to instructions that reference pre-computed aggregate results:

Sources: llkv-expr/src/expr.rs:184-215

flowchart LR
    subgraph AggExpr["Aggregate Expression"]
AGG_CALL["AggregateCall\nCountStar / Sum / Avg"]
end
    
    subgraph Compilation["Compilation"]
REF["Generate AGG_REFERENCE\ninstruction"]
METADATA["Store aggregate metadata\nfunction type, distinct flag"]
end
    
    subgraph PreExecution["Pre-Execution Phase"]
COMPUTE["Executor computes\naggregate values"]
STORE["Store in aggregate\nresult table"]
end
    
    subgraph Evaluation["Expression Evaluation"]
LOOKUP["AGG_REFERENCE instruction\nlooks up pre-computed value"]
BROADCAST["Broadcast scalar result\nto array length"]
CONTINUE["Continue with remaining\nexpression operations"]
end
    
 
   AGG_CALL --> REF
 
   REF --> METADATA
 
   METADATA --> COMPUTE
 
   COMPUTE --> STORE
 
   STORE --> LOOKUP
 
   LOOKUP --> BROADCAST
 
   BROADCAST --> CONTINUE

Integration with Execution Layer

Compiled programs are executed by the compute kernels layer, which provides vectorized implementations of each bytecode instruction:

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

flowchart TB
    subgraph Programs["Compiled Programs"]
EP["EvalProgram"]
DP["DomainProgram"]
end
    
    subgraph ComputeLayer["llkv-compute Kernels"]
ARITHMETIC["Arithmetic Kernels\nadd_arrays, multiply_arrays"]
COMPARISON["Comparison Kernels\ngt_arrays, eq_arrays"]
CAST_K["Cast Kernels\ncast_array"]
LOGICAL["Logical Kernels\nand_bitmaps, or_bitmaps"]
STRING["String Kernels\ncontains, starts_with"]
end
    
    subgraph Execution["Execution Context"]
BATCH["Input RecordBatch\nColumn arrays"]
STACK["Evaluation Stack"]
BITMAP["Bitmap Accumulator"]
end
    
    subgraph Results["Evaluation Results"]
SCALAR_OUT["Array of computed\nscalar values"]
FILTER_OUT["Bitmap of matching\nrow IDs"]
end
    
 
   EP --> ARITHMETIC
 
   EP --> COMPARISON
 
   EP --> CAST_K
    
 
   DP --> COMPARISON
 
   DP --> LOGICAL
 
   DP --> STRING
    
 
   ARITHMETIC --> STACK
 
   COMPARISON --> STACK
 
   CAST_K --> STACK
    
 
   LOGICAL --> BITMAP
 
   STRING --> BITMAP
    
 
   BATCH --> STACK
 
   BATCH --> BITMAP
    
 
   STACK --> SCALAR_OUT
 
   BITMAP --> FILTER_OUT

Compilation Performance Considerations

The compilation phase is designed to amortize its cost over repeated evaluations:

Compilation Cache Strategy

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

Summary

The compilation phase transforms high-level expression ASTs into efficient bytecode programs optimized for vectorized execution. By separating compilation from evaluation, the system achieves:

• Performance : Bytecode enables efficient stack-based evaluation with Arrow kernels
• Reusability : Compiled programs can be cached and reused across query invocations
• Optimization : Multiple optimization passes improve runtime performance
• Type Safety : Type inference and validation occur during compilation, not evaluation
• Maintainability : Clear separation between compilation and execution concerns

The compiled EvalProgram and DomainProgram bytecode formats serve as the bridge between query planning and execution, enabling the query engine to efficiently evaluate complex scalar computations and filter predicates over columnar data.

Dismiss

Refresh this wiki

Enter email to refresh

Scalar Evaluation and NumericKernels

Loading…

Scalar Evaluation and NumericKernels

Relevant source files

• llkv-csv/src/writer.rs
• llkv-expr/src/expr.rs
• llkv-plan/src/plans.rs
• llkv-table/examples/direct_comparison.rs
• llkv-table/examples/performance_benchmark.rs
• llkv-table/examples/test_streaming.rs
• llkv-table/src/table.rs

Purpose and Scope

This page documents the scalar expression evaluation engine in LLKV, covering how ScalarExpr instances are computed against columnar data to produce results for projections, filters, and computed columns. The evaluation system operates on Apache Arrow arrays and leverages vectorization for performance.

For information about the expression AST structure and variants, see Expression AST. For how expressions are translated from SQL column names to field identifiers, see Expression Translation. For the bytecode compilation pipeline, see Program Compilation. For aggregate function evaluation, see Aggregation System.

ScalarExpr Variants

The ScalarExpr<F> enum represents all scalar computations that can be performed in LLKV. Each variant corresponds to a specific type of operation that produces a single value per row.

Sources: llkv-expr/src/expr.rs:126-182

graph TB
    ScalarExpr["ScalarExpr<F>"]
ScalarExpr --> Column["Column(F)\nDirect column reference"]
ScalarExpr --> Literal["Literal(Literal)\nConstant value"]
ScalarExpr --> Binary["Binary\nArithmetic operations"]
ScalarExpr --> Not["Not(Box<ScalarExpr>)\nLogical negation"]
ScalarExpr --> IsNull["IsNull\nNULL test"]
ScalarExpr --> Aggregate["Aggregate(AggregateCall)\nAggregate functions"]
ScalarExpr --> GetField["GetField\nStruct field access"]
ScalarExpr --> Cast["Cast\nType conversion"]
ScalarExpr --> Compare["Compare\nComparison ops"]
ScalarExpr --> Coalesce["Coalesce\nFirst non-null"]
ScalarExpr --> ScalarSubquery["ScalarSubquery\nSubquery result"]
ScalarExpr --> Case["Case\nCASE expression"]
ScalarExpr --> Random["Random\nRandom number"]
Binary --> BinaryOp["BinaryOp:\nAdd, Subtract, Multiply,\nDivide, Modulo,\nAnd, Or,\nBitwiseShiftLeft,\nBitwiseShiftRight"]
Compare --> CompareOp["CompareOp:\nEq, NotEq,\nLt, LtEq,\nGt, GtEq"]

The generic type parameter F represents the field identifier type, which is typically String (for SQL column names) or FieldId (for translated physical column identifiers).

Binary Operations

Binary operations perform arithmetic or logical computations between two scalar expressions. The BinaryOp enum defines the supported operators:

Sources: llkv-expr/src/expr.rs:310-338

Binary expressions are constructed recursively, allowing complex nested computations:

Comparison Operations

Comparison operations produce boolean results (represented as 1/0 integers) by comparing two scalar expressions. The CompareOp enum defines six comparison operators:

Sources: llkv-expr/src/expr.rs:341-363

Comparisons are represented as a ScalarExpr::Compare variant that contains the left operand, operator, and right operand. When evaluated, they produce a boolean value that follows SQL three-valued logic (true, false, NULL).

Evaluation Pipeline

The evaluation of scalar expressions follows a multi-stage pipeline from SQL text to computed Arrow arrays:

Sources: llkv-expr/src/expr.rs:1-819 llkv-table/src/table.rs:29-30

graph LR
    SQL["SQL Expression\n'col1 + col2 * 10'"]
Parse["SQL Parser\nsqlparser-rs"]
Translate["Expression Translation\nString → FieldId"]
Compile["Program Compilation\nScalarExpr → EvalProgram"]
Execute["Evaluation Engine\nVectorized Execution"]
Result["Arrow Array\nComputed Results"]
SQL --> Parse
 
   Parse --> Translate
 
   Translate --> Compile
 
   Compile --> Execute
 
   Execute --> Result
    
    Compile -.uses.-> ProgramCompiler["ProgramCompiler\nllkv-compute"]
Execute -.operates on.-> ArrowArrays["Arrow Arrays\nColumnar Data"]

The key stages are:

1. Parsing : SQL expressions are parsed into AST nodes by sqlparser-rs
2. Translation : Column names (strings) are resolved to FieldId identifiers
3. Compilation : ScalarExpr is compiled into bytecode by ProgramCompiler
4. Execution : The bytecode is evaluated against Arrow columnar data

Type System and Casting

LLKV uses Arrow’s type system for scalar evaluation. The Cast variant of ScalarExpr performs explicit type conversions:

Sources: llkv-expr/src/expr.rs:154-157

The data_type field is an Arrow DataType that specifies the target type for the conversion. Type casting follows Arrow’s casting rules and handles conversions between:

• Numeric types (integers, floats, decimals)
• String types (UTF-8)
• Temporal types (Date32, timestamps)
• Boolean types
• Struct types

Invalid casts produce NULL values following SQL semantics.

Null Handling and Propagation

Scalar expressions implement SQL three-valued logic where NULL values propagate through most operations. The IsNull variant provides explicit NULL testing:

Sources: llkv-expr/src/expr.rs:139-142

When negated is false, this evaluates to 1 (true) if the expression is NULL, 0 (false) otherwise. When negated is true, it performs the inverse test (IS NOT NULL).

The Coalesce variant provides NULL-coalescing behavior, returning the first non-NULL value from a list of expressions:

Sources: llkv-expr/src/expr.rs165

This is used to implement SQL’s COALESCE(expr1, expr2, ...) function.

CASE Expressions

The Case variant implements SQL CASE expressions with optional operand and ELSE branches:

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

This represents both simple and searched CASE expressions:

• Simple CASE : When operand is Some, each branch’s WHEN expression is compared to the operand
• Searched CASE : When operand is None, each branch’s WHEN expression is evaluated as a boolean

The branches vector contains (WHEN, THEN) pairs evaluated in order. If no branch matches, else_expr is returned, or NULL if else_expr is None.

graph TB
    subgraph "Row-by-Row Evaluation (Avoided)"
        Row1["Row 1:\ncol1=10, col2=5\n→ 10 + 5 = 15"]
Row2["Row 2:\ncol1=20, col2=3\n→ 20 + 3 = 23"]
Row3["Row 3:\ncol1=15, col2=7\n→ 15 + 7 = 22"]
end
    
    subgraph "Vectorized Evaluation (Used)"
        Col1["Int64Array\n[10, 20, 15]"]
Col2["Int64Array\n[5, 3, 7]"]
Result["Int64Array\n[15, 23, 22]"]
Col1 --> VectorAdd["Vectorized Add\nSIMD Operations"]
Col2 --> VectorAdd
 
       VectorAdd --> Result
    end
    
    style Row1 fill:#f9f9f9
    style Row2 fill:#f9f9f9
    style Row3 fill:#f9f9f9

Vectorization Strategy

Expression evaluation in LLKV leverages Apache Arrow’s columnar format for vectorized execution. Rather than evaluating expressions row-by-row, operations process entire arrays at once.

Sources: llkv-table/src/table.rs:1-681

Key benefits of vectorization:

1. SIMD Instructions : Modern CPUs can process multiple values simultaneously
2. Reduced Overhead : Eliminates per-row interpretation overhead
3. Cache Efficiency : Columnar layout improves CPU cache utilization
4. Arrow Compute Kernels : Leverages highly optimized Arrow implementations

graph TB
    Expr["ScalarExpr::Binary\nop=Add"]
Dispatch["Type Dispatch"]
Expr --> Dispatch
    
 
   Dispatch --> Int64["Int64Array\nAdd kernel"]
Dispatch --> Int32["Int32Array\nAdd kernel"]
Dispatch --> Float64["Float64Array\nAdd kernel"]
Dispatch --> Decimal128["Decimal128Array\nAdd kernel"]
Int64 --> Result1["Int64Array result"]
Int32 --> Result2["Int32Array result"]
Float64 --> Result3["Float64Array result"]
Decimal128 --> Result4["Decimal128Array result"]

Numeric Type Dispatch

LLKV handles multiple numeric types through Arrow’s type system. The evaluation engine uses Arrow’s primitive type traits to dispatch operations:

Sources: llkv-table/src/table.rs:17-20

The dispatch mechanism uses Arrow’s type system to select the appropriate kernel at evaluation time. The macros llkv_for_each_arrow_numeric, llkv_for_each_arrow_boolean, and llkv_for_each_arrow_string provide type-safe iteration over all supported Arrow types.

Aggregate Functions in Scalar Context

The Aggregate variant of ScalarExpr allows aggregate functions to appear in scalar contexts, such as COUNT(*) + 1:

Sources: llkv-expr/src/expr.rs145

The AggregateCall enum includes:

• CountStar: Count all rows
• Count { expr, distinct }: Count non-NULL values
• Sum { expr, distinct }: Sum of values
• Total { expr, distinct }: Sum with NULL-safe 0 default
• Avg { expr, distinct }: Average of values
• Min(expr): Minimum value
• Max(expr): Maximum value
• CountNulls(expr): Count NULL values
• GroupConcat { expr, distinct, separator }: String concatenation

Sources: llkv-expr/src/expr.rs:184-215

Each aggregate operates on a ScalarExpr, allowing nested computations like SUM(col1 + col2) or AVG(-price).

Random Number Generation

The Random variant produces pseudo-random floating-point values:

Sources: llkv-expr/src/expr.rs181

Following PostgreSQL and DuckDB semantics, each evaluation produces a new random value in the range [0.0, 1.0). The generator is seeded automatically and does not expose seed control at the SQL level.\n\n## Struct Field Access\n\nThe GetField variant extracts fields from struct expressions](https://github.com/jzombie/rust-llkv/blob/89777726/0.0, 1.0). The generator is seeded automatically and does not expose seed control at the SQL level.\n\n## Struct Field Access\n\nThe GetField variant extracts fields from struct expressions#LNaN-LNaN)

This enables navigation of nested data structures. For example, accessing user.address.city would be represented as:

The evaluation engine resolves field names against Arrow struct schemas at runtime.

Performance Considerations

The scalar evaluation engine includes several optimizations:

Expression Constant Folding

Constant subexpressions are evaluated once during compilation rather than per-row. For example, col1 + (10 * 20) is simplified to col1 + 200 before evaluation.

Predicate Pushdown

When scalar expressions appear in WHERE clauses, they may be pushed down to the storage layer for early filtering. The PredicateFusionCache in llkv-compute caches compiled predicates to avoid recompilation.

Sources: llkv-table/src/table.rs29

Type Specialization

Arrow kernels are specialized for each numeric type, avoiding generic dispatch overhead in tight loops. This ensures that Int64 + Int64 uses dedicated integer addition instructions rather than polymorphic dispatch.

SIMD Acceleration

The underlying storage layer (simd-r-drive) provides SIMD-optimized operations for bulk data movement and filtering, which complements the vectorized evaluation strategy.

Sources: llkv-storage/pager/MemPager llkv-table/src/table.rs21

sequenceDiagram
    participant SQL as SQL Engine
    participant Planner as TablePlanner
    participant Scanner as ScanRowStream
    participant Compute as Compute Layer
    participant Store as ColumnStore
    
    SQL->>Planner: Execute SELECT with expressions
    Planner->>Planner: Compile ScalarExpr to bytecode
    Planner->>Scanner: Create scan with projections
    
    loop For each batch
        Scanner->>Store: Gather column arrays
        Store-->>Scanner: Arrow arrays
        Scanner->>Compute: Evaluate expressions
        Compute->>Compute: Vectorized operations
        Compute-->>Scanner: Computed arrays
        Scanner-->>SQL: RecordBatch
    end

Integration with Scan Pipeline

Scalar expressions are evaluated during table scans through the ScanProjection system:

Sources: llkv-table/src/table.rs:447-488 llkv-scan/execute/execute_scan

The scan pipeline:

1. Gathers base column arrays from the ColumnStore
2. Passes arrays to the compute layer for expression evaluation
3. Assembles computed results into RecordBatch instances
4. Streams batches to the caller

This design minimizes memory allocation by processing data in fixed-size batches (typically 1024 rows) rather than materializing entire result sets.

Expression Compilation Flow

The complete compilation flow from SQL to executed results:

Sources: llkv-expr/src/expr.rs:1-819 llkv-plan/src/plans.rs:1-1500 llkv-table/src/table.rs:1-681