FeatherDB Query Engine

The query engine transforms SQL strings into executable query plans and produces results. It features a cost-based optimizer with index selection, join ordering, and prepared statement support with plan caching.

Architecture Overview

                              SQL String
                                  |
                                  v
+-------------------------------------------------------------+
|  Parser (parser.rs)                                          |
|  - Uses sqlparser-rs for SQL parsing                         |
|  - Rich error messages with keyword suggestions              |
|  - Data type conversion to FeatherDB types                   |
+-------------------------------------------------------------+
                                  |
                                  v
+-------------------------------------------------------------+
|  Planner (planner.rs)                                        |
|  - AST to LogicalPlan conversion                             |
|  - Table/column resolution with suggestions                  |
|  - Parameter placeholder support ($1, $2, ?1, ?2)            |
+-------------------------------------------------------------+
                                  |
                                  v
+-------------------------------------------------------------+
|  Optimizer (optimizer.rs)                                    |
|  - Predicate pushdown                                        |
|  - Projection pushdown                                       |
|  - Constant folding                                          |
|  - Index selection (100-1000x speedup)                       |
|  - Join order optimization (greedy algorithm)                |
|  - Cost estimation with table statistics                     |
+-------------------------------------------------------------+
                                  |
                                  v
+-------------------------------------------------------------+
|  Executor (executor.rs)                                      |
|  - Volcano model (pull-based iteration)                      |
|  - Hash join for equi-joins                                  |
|  - Index scan execution                                      |
|  - MVCC visibility checking                                  |
|  - EXPLAIN with cost annotations                             |
+-------------------------------------------------------------+
                                  |
                                  v
                           Query Results

Components

1. Parser (parser.rs)

Wraps sqlparser-rs to parse SQL into AST with enhanced error messages.

Features:

• Parse SQL strings into AST using GenericDialect
• Rich error context with line/column positions
• Keyword typo detection and suggestions (e.g., "SELEKT" suggests "SELECT")
• Data type conversion to FeatherDB's ColumnType

Supported SQL:

-- DDL
CREATE TABLE name (col TYPE [constraints], ...)
DROP TABLE [IF EXISTS] name
CREATE INDEX name ON table (col)

-- DML
SELECT [DISTINCT] cols FROM table [AS alias]
       [JOIN table ON condition]
       [WHERE condition]
       [GROUP BY cols] [HAVING condition]
       [ORDER BY cols [ASC|DESC]]
       [LIMIT n [OFFSET m]]

-- CTEs (Common Table Expressions)
WITH cte_name [(col1, col2, ...)] AS (
  SELECT ...
)
SELECT * FROM cte_name;

-- Subqueries
SELECT * FROM table WHERE col IN (SELECT ...);
SELECT * FROM table WHERE EXISTS (SELECT ...);
SELECT * FROM (SELECT ...) AS derived_table;

INSERT INTO table [(cols)] VALUES (...)
UPDATE table SET col = expr [WHERE condition]
DELETE FROM table [WHERE condition]

-- Query analysis
EXPLAIN [VERBOSE] [ANALYZE] query

Data Types:

SQL Type	FeatherDB Type
BOOLEAN	Boolean
SMALLINT, INT, INTEGER, BIGINT, TINYINT	Integer
FLOAT, REAL, DOUBLE, DECIMAL, NUMERIC	Real
CHAR(n), VARCHAR(n), TEXT	Text { max_len }
BINARY, VARBINARY, BLOB, BYTEA	Blob { max_len }
TIMESTAMP, DATETIME, DATE	Timestamp

2. Planner (planner.rs)

Converts SQL AST to logical query plans with comprehensive error handling.

Logical Plan Types:

enum LogicalPlan {
    // Data access
    Scan { table, alias, projection, filter },
    IndexScan { table, alias, index, range, residual_filter, projection },

    // Subqueries and CTEs
    SubqueryScan { input, alias, schema },
    CTE { name, input, column_aliases },
    ScalarSubquery { input },
    Exists { input },
    InSubquery { expr, subquery },

    // Special join types
    SemiJoin { left, right, condition },
    AntiJoin { left, right, condition },

    // Relational operators
    Filter { input, predicate },
    Project { input, exprs },
    Join { left, right, join_type, condition },
    Aggregate { input, group_by, aggregates },
    Sort { input, order_by },
    Limit { input, limit, offset },
    Distinct { input },

    // DML
    Insert { table, columns, values },
    Update { table, assignments, filter },
    Delete { table, filter },

    // DDL
    CreateTable { table },
    DropTable { name, if_exists },

    // Utility
    EmptyRelation,
    Explain { input, verbose, analyze },
}

Join Types:

• Inner - Standard inner join
• Left - Left outer join
• Right - Right outer join
• Full - Full outer join

Index Range Types:

• point(value) - Equality lookup (fastest)
• between(start, end) - Range with both bounds
• from_inclusive/exclusive(value) - Range >= or >
• to_inclusive/exclusive(value) - Range <= or <
• full() - Full index scan

Error Handling:

• Table not found with suggestions for typos
• Column not found with similar name suggestions
• Ambiguous column references in joins
• Type validation for constraints

3. Optimizer (optimizer.rs)

Applies transformation rules and cost-based optimization.

Optimization Rules:

Rule	Description	Benefit
Predicate Pushdown	Push filters closer to table scans	Reduces rows early
Projection Pushdown	Only read needed columns	Reduces I/O
Constant Folding	Evaluate constant expressions at plan time	Avoids runtime computation
Index Selection	Convert Scan+Filter to IndexScan	100-1000x speedup
Join Order Optimization	Reorder joins by estimated cardinality	10-100x speedup

Index Selection:

The optimizer automatically selects indexes for:

• Equality predicates: WHERE id = 5 -> point lookup
• Range predicates: WHERE age > 18 AND age < 65 -> range scan
• Combined predicates: indexed predicate + residual filter

-- Example: query with index
SELECT * FROM users WHERE id = 5 AND name = 'Alice';
-- Optimizer creates: IndexScan(id=5) + residual_filter(name='Alice')

Cost Estimation:

The CostEstimator provides:

• Cardinality estimation for each plan node
• Cost estimation based on:
  • Sequential scan: 1.0 per row
  • Index scan: 1.5 per row (but fewer rows)
  • Hash join: build cost + probe cost
  • Sort: n log n amortized

Cost Constants:

SEQ_SCAN_COST_PER_ROW: 1.0
INDEX_SCAN_COST_PER_ROW: 1.5
HASH_JOIN_COST_PER_ROW: 0.1
HASH_BUILD_COST_PER_ROW: 1.0
SORT_COST_PER_ROW: 2.0
DEFAULT_SELECTIVITY: 0.1
DEFAULT_RANGE_SELECTIVITY: 0.3
DEFAULT_JOIN_SELECTIVITY: 0.1

Join Order Optimization:

For multi-way joins (3+ tables), uses greedy algorithm:

1. Extract all base relations and predicates
2. Estimate cardinalities using catalog statistics
3. Iteratively join the pair with smallest intermediate result
4. Place smaller table on build side of hash join

4. Executor (executor.rs)

Executes physical operators using the Volcano (iterator) model.

Physical Operators:

Operator	Description
SeqScan	Sequential table scan with optional pushed filter
IndexScan	Index-based lookup (point or range)
SubqueryScan	Execute subquery and expose as table
SemiJoin	Semi-join for EXISTS and IN subqueries
AntiJoin	Anti-join for NOT EXISTS and NOT IN subqueries
Filter	Evaluate predicate on each row
Project	Compute output expressions, expand wildcards
HashJoin	Hash-based equi-join (preferred for equality)
NestedLoopJoin	Fallback for non-equi joins
HashAggregate	Group-by aggregation with hash table
Sort	In-memory quicksort
Limit	Limit/offset row output
Distinct	Remove duplicate rows via hash set

Execution Context:

struct ExecutionContext<'a> {
    catalog: &'a Catalog,
    buffer_pool: &'a Arc<BufferPool>,
    snapshot: &'a Snapshot,      // MVCC visibility
    txn_manager: &'a TransactionManager,
}

Query Results:

enum QueryResult {
    Rows(Vec<Row>),      // SELECT results
    Affected(usize),      // INSERT/UPDATE/DELETE count
    SchemaChanged,        // CREATE/DROP
}

EXPLAIN Support:

-- Show query plan with cost estimates
EXPLAIN SELECT * FROM users WHERE id = 5;

-- Show detailed costs
EXPLAIN VERBOSE SELECT * FROM users WHERE id = 5;

-- Actually execute and show timing
EXPLAIN ANALYZE SELECT * FROM users WHERE id = 5;

Output includes:

• Plan tree structure
• Cost estimates per node
• Row estimates per node
• For ANALYZE: actual execution time and row counts

5. Expressions (expr.rs)

Expression representation and evaluation.

Expression Types:

enum Expr {
    Column { table, name, index },
    Literal(Value),
    Parameter { index },           // For prepared statements
    BinaryOp { left, op, right },
    UnaryOp { op, expr },
    Function { name, args },
    Aggregate { func, arg, distinct },
    Case { operand, when_clauses, else_result },
    Between { expr, low, high, negated },
    InList { expr, list, negated },
    Like { expr, pattern, negated },
    Wildcard,                      // SELECT *
    QualifiedWildcard(table),      // SELECT table.*
}

Binary Operators:

• Arithmetic: +, -, *, /, %
• Comparison: =, !=, <, <=, >, >=
• Logical: AND, OR
• String: || (concatenation)

Unary Operators:

• NOT - Logical negation
• - - Numeric negation
• IS NULL / IS NOT NULL

Aggregate Functions:

• COUNT(*), COUNT(col), COUNT(DISTINCT col)
• SUM(col), AVG(col)
• MIN(col), MAX(col)

Built-in Functions:

String Functions:

• UPPER(text), LOWER(text) - Case conversion
• LENGTH(text), LENGTH(blob) - Get length
• SUBSTR(text, start [, length]) - Extract substring (1-based indexing, SQL standard)
• TRIM(text) - Remove leading and trailing whitespace
• LTRIM(text) - Remove leading whitespace
• RTRIM(text) - Remove trailing whitespace
• REPLACE(text, from, to) - Replace all occurrences

Date/Time Functions:

• DATE(timestamp) - Extract date portion ("YYYY-MM-DD")
• YEAR(timestamp) - Extract year as integer
• MONTH(timestamp) - Extract month as integer (1-12)
• DAY(timestamp) - Extract day as integer (1-31)
• NOW() - Get current timestamp

Numeric Functions:

• ABS(numeric) - Absolute value

Utility Functions:

• COALESCE(val1, val2, ...) - First non-NULL value
• NULLIF(val1, val2) - Return NULL if equal

NULL Handling:

• Most operations propagate NULL
• AND: FALSE AND NULL = FALSE
• OR: TRUE OR NULL = TRUE
• Division by zero returns NULL

6. Prepared Statements (prepared.rs)

Plan caching for repeated queries (5-10x speedup).

PreparedStatement:

struct PreparedStatement {
    sql: String,
    plan: LogicalPlan,        // Cached optimized plan
    param_types: Vec<Option<ColumnType>>,
    param_count: usize,
    id: u64,
}

Parameter Placeholders:

• PostgreSQL style: $1, $2, $3, ...
• Question mark with index: ?1, ?2, ?3, ...

PlanCache:

• LRU cache with configurable max size (default: 1000)
• Automatic eviction of least recently used plans
• Schema-aware invalidation (on DDL)
• Table-specific invalidation

Cache Statistics:

struct CacheStats {
    hits: u64,          // Cache hits
    misses: u64,        // Cache misses
    evictions: u64,     // LRU evictions
    invalidations: u64, // Schema invalidations
}

Usage Example:

use featherdb_query::{PlanCache, PreparedStatement, substitute_plan_params};

// Create cache
let cache = PlanCache::new(1000);

// Prepare statement (parse + plan + optimize once)
let stmt = db.prepare("SELECT * FROM users WHERE id = $1")?;

// Execute multiple times with different parameters
let params = vec![Value::Integer(1)];
let plan = substitute_plan_params(stmt.plan(), &params)?;
let result = Executor::execute(&ctx, &plan)?;

// Cache statistics
println!("Hit ratio: {:.2}%", cache.stats().hit_ratio() * 100.0);

Query Execution Flow

1. Parse:    "SELECT name FROM users WHERE id = $1"
                              |
2. Plan:     Project(name)
                 |__ Filter(id = $1)
                       |__ Scan(users)
                              |
3. Optimize: IndexScan(users, idx_id, point($1), project=[name])
                              |
4. Substitute: IndexScan(users, idx_id, point(42), project=[name])
                              |
5. Execute:  IndexScan iterator -> MVCC visibility check -> project
                              |
6. Results:  Row { name: "Alice" }

Usage Examples

Basic Query Execution

use featherdb_query::{Parser, Planner, Optimizer, Executor, ExecutionContext};

// Parse SQL
let stmt = Parser::parse_one("SELECT * FROM users WHERE age > 21")?;

// Create logical plan
let planner = Planner::new(&catalog);
let plan = planner.plan(&stmt)?;

// Optimize (with index selection and cost-based optimization)
let optimizer = Optimizer::with_catalog(catalog.clone());
let optimized = optimizer.optimize(plan);

// Execute
let ctx = ExecutionContext {
    catalog: &catalog,
    buffer_pool: &buffer_pool,
    snapshot: &snapshot,
    txn_manager: &txn_manager,
};

match Executor::execute(&ctx, &optimized)? {
    QueryResult::Rows(rows) => {
        for row in rows {
            println!("{}: {:?}", row.columns[0], row.values[0]);
        }
    }
    QueryResult::Affected(n) => println!("{} rows affected", n),
    QueryResult::SchemaChanged => println!("Schema updated"),
}

Using Prepared Statements

use featherdb_query::{PlanCache, Parser, Planner, Optimizer};
use featherdb_query::{PreparedStatement, substitute_plan_params, count_plan_params};

// Create plan cache
let cache = PlanCache::new(100);

// Parse and plan with parameters
let sql = "SELECT * FROM users WHERE id = $1 AND status = $2";
let stmt = Parser::parse_one(sql)?;
let plan = planner.plan(&stmt)?;
let optimized = optimizer.optimize(plan);

// Create prepared statement
let param_count = count_plan_params(&optimized);
let prepared = PreparedStatement::new(
    sql.to_string(),
    optimized,
    vec![None; param_count],
    param_count,
    cache.next_id(),
);

// Cache it
cache.insert(sql.to_string(), prepared.clone());

// Execute with parameters
let params = vec![Value::Integer(42), Value::Text("active".into())];
prepared.validate_params(&params)?;
let bound_plan = substitute_plan_params(prepared.plan(), &params)?;
let result = Executor::execute(&ctx, &bound_plan)?;

Using EXPLAIN

// Show query plan
let stmt = Parser::parse_one("EXPLAIN SELECT * FROM users WHERE id = 5")?;
let plan = planner.plan(&stmt)?;
let result = Executor::execute(&ctx, &plan)?;

// Output:
// QUERY PLAN
// ============================================================
// -> Index Lookup using idx_users_id on users
//
// Estimated total cost: 1.50
// Estimated rows: 1

// With verbose costs
let stmt = Parser::parse_one("EXPLAIN VERBOSE SELECT * FROM users")?;
// Shows cost and row estimates for each node

// With actual execution stats
let stmt = Parser::parse_one("EXPLAIN ANALYZE SELECT * FROM users")?;
// Shows actual execution time and row counts

Configuration Options

Optimizer Configuration

// Without catalog (no index selection or join ordering)
let optimizer = Optimizer::new();

// With catalog (enables all optimizations)
let optimizer = Optimizer::with_catalog(catalog.clone());

Plan Cache Configuration

// Custom cache size
let cache = PlanCache::new(500);

// Default size (1000 entries)
let cache = PlanCache::default_size();

// Invalidate on schema changes
cache.invalidate_all();

// Invalidate specific table
cache.invalidate_table("users");

Testing

# Run all query engine tests (using Make)
make test-crate CRATE=featherdb-query

# Or with cargo directly
cargo test -p featherdb-query

# Test specific component
cargo test -p featherdb-query parser
cargo test -p featherdb-query planner
cargo test -p featherdb-query optimizer
cargo test -p featherdb-query executor
cargo test -p featherdb-query prepared
cargo test -p featherdb-query expr

# Run with coverage
make coverage  # or: cargo llvm-cov --workspace

Performance Considerations

1. Index Selection: Ensure indexes exist on frequently filtered columns
2. Predicate Pushdown: Filters are automatically pushed to scans
3. Projection Pruning: Select only needed columns
4. Join Order: Optimizer reorders joins for multi-table queries
5. Prepared Statements: Use for repeated queries (5-10x speedup)
6. Statistics: Keep table statistics updated for accurate cost estimates

Implemented Features

Core Query Processing:

• SQL parsing with rich error messages
• Logical plan generation
• Predicate pushdown optimization
• Projection pushdown optimization
• Constant folding
• Index selection (point and range)
• Join order optimization
• Cost-based estimation with statistics
• Prepared statements with plan caching
• EXPLAIN with cost annotations
• Hash join for equi-joins
• MVCC-aware execution

Advanced SQL:

• Common Table Expressions (WITH clause, column aliasing, chained CTEs)
• Subquery support (scalar, IN, NOT IN, EXISTS, NOT EXISTS, correlated)
• Semi-join and anti-join optimization
• Derived tables (subquery in FROM clause)
• UNION / UNION ALL / INTERSECT / EXCEPT set operations
• CREATE VIEW / DROP VIEW
• CAST, EXTRACT, date interval arithmetic

Functions:

• String: UPPER, LOWER, LENGTH, SUBSTR, TRIM, LTRIM, RTRIM, REPLACE
• Date/time: DATE, YEAR, MONTH, DAY, NOW
• Math: ABS, SQRT, POWER, FLOOR, CEIL, LOG, MOD
• Aggregate: COUNT, SUM, AVG, MIN, MAX
• Window: ROW_NUMBER, RANK, DENSE_RANK, LAG, LEAD
• Utility: COALESCE, NULLIF

Constraints:

• CHECK constraints (parsing and enforcement)
• Foreign key constraints (CASCADE, RESTRICT, SET NULL, NO ACTION)
• UNIQUE constraints
• NOT NULL constraints

Future Improvements

• Parallel query execution
• Lateral joins
• Recursive CTEs
• External sort for large datasets
• Merge join algorithm
• Bitmap index scans
• Adaptive hash aggregate with spill-to-disk