LLKV Query Expression AST

Work in Progress

llkv-expr defines the expression Abstract Syntax Tree (AST) used across the LLKV database stack. It provides type-aware, Arrow-native expression structures that decouple logical expressions from concrete evaluation strategies.

This crate intentionally ships without an evaluator or execution engine; it focuses on representation. Downstream crates like llkv-table and llkv-executor consume these ASTs for compilation and evaluation.

Purpose and Scope

• Define a shared expression language for logical predicates (Expr) and scalar operations (ScalarExpr).
• Support generic field identifiers (Expr<F>) so callers can use FieldId, String, or custom types as needed.
• Enable modular testing and independent evolution of planner and executor layers.
• Serve as the foundation for expression compilation into stack-based evaluation programs used by the table layer.

Expression Types

Logical Expressions (Expr)

The following is a non-exhaustive list of supported expressions.

Logical expressions include boolean operations and predicates:

• Boolean composition: And, Or, Not
• Comparisons: Compare operations with standard relational operators
• Null checks: IsNull predicates
• Set membership: InList for testing values against a set
• Subquery evaluation: Exists for correlated subqueries
• Literal booleans for constant folding

Scalar Expressions (ScalarExpr)

Scalar expressions represent arithmetic and data manipulation:

• Column references and literal values
• Binary arithmetic operations (addition, subtraction, multiplication, division, modulo)
• Type casts and coercion
• Aggregate function calls (COUNT, SUM, AVG, MIN, MAX)
• Null coalescing (Coalesce) and conditional logic (Case)
• Subquery evaluation for scalar results
• Struct field access (GetField)

Integration with Other Crates

Planner (llkv-plan)

• llkv-plan uses llkv-expr to construct logical query plans.
• SelectFilter and other plan structures embed Expr<String> for predicates, ensuring the planner remains decoupled from execution details.
• Correlation helpers in the planner manage placeholder assignment for correlated subqueries, which are represented as ScalarExpr::ScalarSubquery.

Executor (llkv-executor)

• llkv-executor evaluates expressions by collecting aggregates, compiling filter programs, and streaming results.
• The executor applies MVCC visibility filters and evaluates HAVING clauses using the Expr and ScalarExpr structures.

Table Layer (llkv-table)

• llkv-table compiles Expr<FieldId> into stack-based EvalProgram structures for efficient vectorized evaluation.
• Provides domain analysis and affine transformation extraction to optimize range scans and index selection.

Design Principles

• Generic field identifiers: expressions work with any F type (e.g., u32, &'static str, FieldId), enabling flexibility across layers.
• Zero-copy where possible: expressions use borrowed references to avoid unnecessary allocations during AST construction.
• Decoupling: the crate avoids embedding evaluation logic so compilation strategies can be optimized independently in consuming crates.
• Arrow-native: expressions map naturally to Arrow data types and columnar operations, supporting efficient vectorized execution.

License

Licensed under the Apache-2.0 License.