Select Operators

RookDB — Selection Operator Documentation

Feature: WHERE Clause Execution (Selection Operator σ) Modules: backend/query/where_builder.rs · backend/executor/selection.rs · frontend/data_cmd.rs Language: Rust

Overview
End-to-End Flow
Module Breakdown
API Design & Function Contracts
Data Structures
Tuple & Storage Format
Algorithms Used
Optimizations
Changes to Existing System
Backend Functions Added
Benchmark Analysis
External APIs Used
New Files Introduced
Database Structure Changes
Future Work

1. Overview

The Selection Operator (σ)

In relational algebra, the selection operator (σ) filters a set of tuples against a Boolean predicate, retaining only those tuples for which the predicate evaluates to TRUE. In SQL this is expressed as the WHERE clause:

SELECT * FROM employees WHERE salary > 50000 AND department = 'Engineering';

The predicate salary > 50000 AND department = 'Engineering' is what the selection operator evaluates. Tuples that satisfy it pass through; all others are discarded.

Role of the WHERE Clause

The WHERE clause is the primary tuple-filtering mechanism in RookDB. It:

Reduces the set of tuples that need to be processed by subsequent pipeline stages.
Implements SQL NULL semantics (Three-Valued Logic), meaning a NULL comparison does not produce FALSE — it produces UNKNOWN, which is treated as non-matching.
Supports a rich predicate language: comparisons, range checks (BETWEEN), set membership (IN), pattern matching (LIKE), NULL checks (IS NULL / IS NOT NULL), and arithmetic inside comparison operands.

Two-Stage Execution Pipeline

The implementation is structured as two tightly coupled but cleanly separated stages:

SQL String
    │
    ▼
┌─────────────────────────────┐
│   Predicate Builder         │   backend/query/where_builder.rs
│   SQL → Predicate AST       │
└────────────┬────────────────┘
             │  Predicate (internal tree)
             ▼
┌─────────────────────────────┐
│   Selection Executor        │   backend/executor/selection.rs
│   Predicate → Evaluation    │
└────────────┬────────────────┘
             │  TriValue (True / False / Unknown)
             ▼
      Matching Tuples

Stage 1 — Predicate Builder: Parses the raw SQL string using the sqlparser crate, extracts the WHERE clause from the parse tree, and converts it into RookDB's internal Predicate / Expr AST. This stage is purely structural: it translates syntax into typed internal nodes without touching any actual row data.

Note: The Abstract Syntax Tree (AST) generated by the sqlparser library is not used directly during execution. It serves only as an intermediate representation. The WHERE clause is extracted from this AST and converted into RookDB’s internal Predicate structure, which is the actual representation consumed by the execution engine.

Stage 2 — Selection Executor: Accepts the internal Predicate tree together with the table schema and a raw tuple byte slice. It resolves column names to physical schema indices, evaluates the predicate per tuple, and returns a TriValue (True / False / Unknown) indicating whether the tuple matches.

This separation means the predicate is built once from SQL and the executor is instantiated once per query; the hot evaluation loop has no SQL-parsing overhead.

2. End-to-End Flow

The following is the complete, step-by-step execution trace for a query such as:

SELECT * WHERE id > 4

Step 1 — User Selects "Select Tuples" from CLI

The interactive menu in frontend/menu.rs presents option 7. Select tuples. The user selects it.

=============================
Choose an option:
...
8. Select tuples
...
=============================
Enter your choice: 8

This dispatches to data_cmd::show_tuples_cmd(&current_db).

Step 2 — CLI Prompts for Table Name and SQL

Enter table name: employees
Enter SQL (single SELECT with WHERE): SELECT * WHERE id > 4

The table name and the raw SQL string are read separately. Critically, the table name is NOT parsed from the SQL — it is entered as a separate input. The SQL string is used solely to extract the WHERE clause.

Step 3 — SQL Parsing via `sqlparser`

Inside build_predicate_from_sql(sql) in where_builder.rs:

let mut ast = Parser::parse_sql(&GenericDialect {}, sql)
    .map_err(|e| format!("Parse error: {}", e))?;

The sqlparser crate (with GenericDialect) tokenises and parses SELECT * WHERE id > 4 into an Abstract Syntax Tree (AST). The result is a Vec<Statement> containing exactly one Statement::Query.

Step 4 — WHERE Clause Extraction

extract_where_clause(statement) traverses the AST:

Statement::Query
  └── body: SetExpr::Select
        └── selection: Some(SqlExpr::BinaryOp { id > 4 })

It returns the raw SqlExpr node representing the WHERE condition.

Step 5 — SQL AST → Internal Predicate Tree

convert_predicate(sql_expr) recursively maps each sqlparser AST node to RookDB's internal Predicate and Expr types:

SqlExpr::BinaryOp { left: id, op: Gt, right: 4 }
    │
    ▼
Predicate::Compare(
    Expr::Column(ColumnReference { name: "id", index: None }),
    ComparisonOp::GreaterThan,
    Expr::Constant(Constant::Int(4))
)

At this point, column_index is None — column name resolution happens later in the executor.

Step 6 — Schema Lookup

Back in show_tuples_cmd, the in-memory catalog is queried for the table schema:

let table_schema = catalog
    .databases.get(&db)     // find database
    .tables.get(table)      // find table → Vec<Column>

This provides the list of column names and their DataTypes needed for column resolution and type checking.

Step 7 — Executor Initialisation

SelectionExecutor::new(predicate, table_schema) is called. This performs three planning-time operations:

Normalisation — normalize_predicate() folds constant expressions, rewrites BETWEEN to AND, canonicalises comparison direction (column on left), and pre-compiles LIKE patterns to regex.
Column Resolution — resolve_columns() walks the predicate tree, matches every ColumnReference by name against the schema, fills in the column_index, and type-checks both sides of every comparison.
Bytecode Compilation — compile_predicate() lowers the resolved predicate tree into a flat Vec<Instruction> (described in detail in §7).

The executor is now ready; all subsequent tuple evaluations cost only the dispatch loop — no SQL parsing, no column name lookups, no regex compilation.

Step 8 — Raw Tuple Collection

All data pages are read from the .dat file (page 0 is the table header and is skipped). For each page, item descriptors in the page header are used to locate each tuple's byte range:

for page_num in 1..total_pages {
    let offset = u32::from_le_bytes(...);   // start of tuple in page
    let length = u32::from_le_bytes(...);   // byte length of tuple
    let tuple_bytes = page.data[offset..offset+length].to_vec();
    raw_tuples.push(tuple_bytes);
}

Step 9 — Predicate Filtering

filter_tuples(&executor, &raw_tuples) iterates every raw tuple byte slice and calls executor.evaluate_tuple(tuple), which runs the bytecode dispatch loop (see §7):

Tuple 1 → evaluate_tuple(&bytes) → TriValue::False   → rejected
Tuple 2 → evaluate_tuple(&bytes) → TriValue::Unknown → rejected
Tuple 5 → evaluate_tuple(&bytes) → TriValue::True    → kept

Only tuples that return TriValue::True are included in matching.

Step 10 — Output

Each matched tuple is deserialised with deserialize_nullable_row and printed:

=== Tuples in 'mydb.employees' ===
Total pages: 3

id (INT) | name (VARCHAR(10))
Tuple 1: id=5 name='Alice'
Tuple 2: id=7 name='Bob'

=== End of tuples ===

3. Module Breakdown

A. Predicate Builder — `backend/query/where_builder.rs`

This module is the SQL-to-AST adapter. It has no knowledge of tuples, schemas, or disk layout — its sole job is to convert a SQL string into a Predicate tree.

`build_predicate_from_sql`

pub fn build_predicate_from_sql(sql: &str) -> Result<Predicate, String>

Input: A raw SQL string, e.g. "SELECT * WHERE salary > 50000".
Output: Ok(Predicate) on success; Err(String) with a human-readable error on failure.
Logic:
1. Calls Parser::parse_sql with GenericDialect. Returns error if the SQL is syntactically invalid.
2. Asserts exactly one statement is present. More than one statement returns an error.
3. Calls extract_where_clause to pull the WHERE expression from the AST.
4. Calls convert_predicate to translate that expression into the internal tree.

This is the only public function in the module — all others are internal helpers.

`extract_where_clause`

fn extract_where_clause(statement: Statement) -> Result<SqlExpr, String>

Input: A parsed sqlparser::ast::Statement.
Output: The SqlExpr representing the WHERE condition, or an error if the statement is not a SELECT query or has no WHERE clause.
Logic: Pattern-matches on Statement::Query → SetExpr::Select → selection. The selection field is Option<SqlExpr> in the sqlparser AST; None means there was no WHERE clause, which is an error (we always require a predicate for the selection operator).

`convert_predicate`

fn convert_predicate(expr: SqlExpr) -> Result<Predicate, String>

Input: A sqlparser SqlExpr node known to represent a predicate (a value expected to be Boolean).
Output: The equivalent internal Predicate node.
Logic: Matches on each supported SqlExpr variant:

SQL AST Node	Internal Predicate
`BinaryOp { And }`	`Predicate::And(left, right)`
`BinaryOp { Or }`	`Predicate::Or(left, right)`
`BinaryOp { Eq / NotEq / Lt / LtEq / Gt / GtEq }`	`Predicate::Compare(expr, op, expr)`
`UnaryOp { Not }`	`Predicate::Not(inner)`
`IsNull(expr)`	`Predicate::IsNull(expr)`
`IsNotNull(expr)`	`Predicate::IsNotNull(expr)`
`Between { expr, low, high, negated }`	`Predicate::Between(...)`, wrapped in `Not` if negated
`InList { expr, list, negated }`	`Predicate::In(expr, items)`, wrapped in `Not` if negated
`Like { expr, pattern, negated }`	`Predicate::Like(expr, pattern, None)`, wrapped in `Not` if negated
`Nested(inner)`	Transparent unwrap — recursion into inner
`Subquery`, `Exists`, `Function`, `Case`, `Cast`	`Err(...)` — explicitly unsupported
Anything else	`Err(...)` — fallback error

Note that Predicate::Like is created with regex_opt = None; the regex is compiled during normalize_predicate in the executor, not here.

`convert_expr`

fn convert_expr(expr: SqlExpr) -> Result<Expr, String>

Input: A SqlExpr node known to represent a value expression (not a boolean predicate).
Output: The equivalent internal Expr node.
Logic:

SQL AST Node	Internal Expr
`Identifier(ident)`	`Expr::Column(ColumnReference::new(ident.value))`
`CompoundIdentifier(parts)`	`Expr::Column(...)` using the last part (strips table qualifier)
`Value(Number)`	`Expr::Constant(Constant::Int(n))` or `Constant::Float(f)`
`Value(SingleQuotedString / DoubleQuotedString)`	`Expr::Constant(Constant::Text(s))`
`Value(Null)`	`Expr::Constant(Constant::Null)`
`Value(Boolean(b))`	`Expr::Constant(Constant::Int(1 or 0))`
`BinaryOp { Plus }`	`Expr::Add(left, right)`
`BinaryOp { Minus }`	`Expr::Sub(left, right)`
`BinaryOp { Multiply }`	`Expr::Mul(left, right)`
`BinaryOp { Divide }`	`Expr::Div(left, right)`
`Nested(inner)`	Transparent unwrap
`Subquery`, `Function`, `Case`, `Cast`, `Exists`	`Err(...)`

Example

Consider the SQL expression:

salary + bonus

SQL AST (simplified):

BinaryOp {
    left: Identifier("salary"),
    op: Plus,
    right: Identifier("bonus")
}

After convert_expr:

Expr::Add(
    Expr::Column(ColumnReference::new("salary")),
    Expr::Column(ColumnReference::new("bonus"))
)

B. Selection Executor — `backend/executor/selection.rs`

This module is the predicate evaluation engine. It accepts a Predicate tree and a Table schema, performs all planning-time work in the constructor, and provides an evaluation function that processes raw tuple byte slices.

Execution Workflow in `SelectionExecutor::new`

Predicate (from builder)
    │
    ├── normalize_predicate()     ← constant folding, BETWEEN expansion, LIKE regex compile
    │
    ├── resolve_columns()         ← column name → schema index, type compatibility check
    │
    └── compile_predicate()       ← Predicate → flat instruction list
                                     (populates used_columns, in_sets, like_patterns)

After construction, the SelectionExecutor holds:

schema: Table — column names and types
column_types: Vec<SqlDataType> — types pre-extracted for quick access
bytecode: Vec<Instruction> — the compiled instruction stream
in_sets: Vec<InSet> — constant-pool objects for IN predicates
like_patterns: Vec<LikePattern> — constant-pool objects for LIKE predicates

Per-Tuple Evaluation in `evaluate_tuple`

For each raw tuple &[u8], the executor runs the bytecode dispatch loop:

A fixed [VMValue; 128] array on the call frame acts as the evaluation stack
A program counter pc steps through self.bytecode
Each instruction pops its operands, computes a result, and pushes it
Column access instructions (PushColumn) call extract_column, which decodes only the requested column from the raw bytes — the rest of the row is never touched
After execution, exactly one VMValue::Bool(TriValue) remains on the stack — this is the predicate result

Predicate Evaluation Strategy

The predicate tree is compiled to a flat instruction list at plan time
Evaluation is iterative at runtime — no recursion inside evaluate_tuple

Separation of concerns:

Planning time (once per query): normalize → resolve → compile
- Works on the Predicate tree
Runtime (once per tuple):
- Flat dispatch loop
- Stack-based execution
- Predictable and efficient

Example

Consider the predicate:

WHERE id > 5 AND age < 30

Internal representation:

And(
    Compare(id > 5),
    Compare(age < 30)
)

Compiled bytecode (simplified):

PushColumn(id)
PushConstant(5)
CmpGreaterThan

PushColumn(age)
PushConstant(30)
CmpLessThan

And

4. API Design & Function Contracts

Predicate Builder

`build_predicate_from_sql`

Property	Details
Signature	`pub fn build_predicate_from_sql(sql: &str) -> Result<Predicate, String>`
Input	A raw SQL string containing a `SELECT ... WHERE ...` statement
Output	`Ok(Predicate)` — internal predicate tree; `Err(String)` — parse or translation error
Side Effects	None
Calls	`Parser::parse_sql`, `extract_where_clause`, `convert_predicate`

Selection Executor

`SelectionExecutor::new`

Property	Details
Signature	`pub fn new(predicate: Predicate, schema: Table) -> Result<Self, String>`
Input	A `Predicate` tree (from `build_predicate_from_sql`) and an owned `Table` schema
Output	`Ok(SelectionExecutor)` ready for evaluation; `Err(String)` on invalid column names or type mismatches
Planning Cost	O(n) in predicate tree size — runs once per query
Side Effects	None — no I/O, no disk access

`SelectionExecutor::evaluate_tuple`

Property	Details
Signature	`pub fn evaluate_tuple(&self, tuple: &[u8]) -> Result<TriValue, String>`
Input	A raw tuple as a byte slice in RookDB's nullable row format
Output	`Ok(TriValue::True)` if the tuple matches; `Ok(TriValue::False)` if it doesn't; `Ok(TriValue::Unknown)` if any NULL comparison was inconclusive; `Err` on internal format errors
Runtime Cost	O(k) where k = number of instructions in bytecode (typically proportional to predicate complexity)
Stack Usage	Fixed 128-slot `VMValue` array on the call frame — no heap allocation

`filter_tuples`

Property	Details
Signature	`pub fn filter_tuples(executor: &SelectionExecutor, tuples: &[Vec<u8>]) -> Result<Vec<Vec<u8>>, String>`
Input	An initialised executor and a slice of raw tuple byte vectors
Output	A new `Vec` containing only tuples for which `evaluate_tuple` returned `TriValue::True`
Use in CLI	Called directly from `data_cmd::show_tuples_cmd` after all raw tuples are collected from disk

Additional Filter Variants

Function	Purpose
`filter_tuples_detailed`	Splits results into three buckets: matched / rejected / unknown — useful for debugging
`count_matching_tuples`	Counts matches without materialising them — saves memory for COUNT queries
`filter_tuples_streaming`	Evaluates one tuple at a time, invokes a callback for matches — no intermediate buffer
`filter_iter`	Lazy iterator adapter — wraps any tuple iterator and filters on the fly

3VL Combinators (module-level free functions)

Function	Signature	Semantics
`apply_and`	`(TriValue, TriValue) -> TriValue`	False dominates; True only when both True; else Unknown
`apply_or`	`(TriValue, TriValue) -> TriValue`	True dominates; False only when both False; else Unknown

5. Data Structures

`Predicate`

pub enum Predicate {
    Compare(Box<Expr>, ComparisonOp, Box<Expr>),  // e  op  e
    IsNull(Box<Expr>),                             // e IS NULL
    IsNotNull(Box<Expr>),                          // e IS NOT NULL
    Not(Box<Predicate>),                           // NOT p
    And(Box<Predicate>, Box<Predicate>),           // p AND p
    Or(Box<Predicate>, Box<Predicate>),            // p OR  p
    Between(Box<Expr>, Box<Expr>, Box<Expr>),      // e BETWEEN low AND high
    In(Box<Expr>, Vec<Expr>),                      // e IN (e1, e2, ...)
    Like(Box<Expr>, String, Option<Regex>),        // e LIKE 'pattern'
    Exists(Box<Predicate>),                        // logical wrapper (not correlated)
}

Why a tree? A tree naturally mirrors the recursive structure of SQL predicates. AND / OR / NOT nodes form internal nodes; Compare, IsNull, In, Between, Like are leaves. This makes traversal (for normalisation, resolution, and compilation) straightforward recursive descent.

Why Box? Rust requires known sizes for enum variants. Since Predicate is recursive, child predicates must be heap-allocated (Box) to break the infinite-size cycle.

BETWEEN at planning time only: Between is normalised into an And of two Compare nodes before compilation. It will never appear in the bytecode.

Exists note: The variant exists in the AST for structural completeness, but it is not a correlated subquery — it simply wraps another predicate. The executor does not emit a distinct opcode for it.

`Expr`

pub enum Expr {
    Column(ColumnReference),        // column reference by name
    Constant(Constant),             // literal value
    Add(Box<Expr>, Box<Expr>),      // e + e
    Sub(Box<Expr>, Box<Expr>),      // e - e
    Mul(Box<Expr>, Box<Expr>),      // e * e
    Div(Box<Expr>, Box<Expr>),      // e / e
}

Expr represents a value (as opposed to Predicate, which represents a truth value). Both sides of a Compare node are Expr nodes. Arithmetic is supported inside expressions, so predicates like salary + bonus > 60000 are valid.

During normalize_expr, any Expr whose operands are both Constant is folded to a single Constant at planning time, so 2 + 3 becomes Constant::Int(5) before any tuple is evaluated.

`ColumnReference`

pub struct ColumnReference {
    pub column_name: String,        // e.g. "salary"
    pub column_index: Option<usize>, // None before resolution, Some(idx) after
}

A ColumnReference starts with column_index = None (as produced by the builder). During SelectionExecutor's resolve_columns pass, the executor matches column_name against the Table's column list and sets column_index to the logical schema position of that column. The index is then used in PushColumn(idx) instructions to efficiently decode only that column from the raw tuple bytes.

`Constant`

pub enum Constant {
    Int(i32),
    Float(f64),
    Date(String),   // stored as ISO-8601 string, parsed at evaluation time
    Text(String),
    Null,
}

Constant represents literal values that appear directly in the SQL predicate. At compile time, Constant values are converted to DataValue (the storage layer's native value type) via constant_to_data_value. Constant::Null converts to None and is emitted as a PushNull instruction.

Three-Valued Logic — `TriValue`

pub enum TriValue {
    True,
    False,
    Unknown,  // the NULL case
}

SQL does not use two-valued (TRUE/FALSE) Boolean logic. Any comparison that involves a NULL operand yields UNKNOWN, not FALSE. The WHERE clause filters out tuples for which the predicate is FALSE or UNKNOWN — only TRUE passes.

The 3VL truth tables implemented in RookDB:

AND

Left \ Right	True	False	Unknown
True	True	False	Unknown
False	False	False	False
Unknown	Unknown	False	Unknown

Left \ Right	True	False	Unknown
True	True	True	True
False	True	False	Unknown
Unknown	True	Unknown	Unknown

NOT

Input	Result
True	False
False	True
Unknown	Unknown

`ComparisonOp`

pub enum ComparisonOp {
    Equals, LessThan, GreaterThan,
    LessOrEqual, GreaterOrEqual, NotEquals,
}

A mapping from SQL comparison operators to an internal enum, used in Predicate::Compare nodes.

`Instruction` (VM Bytecode)

pub enum Instruction {
    PushColumn(usize),          // push column[idx] from raw tuple (lazy decode)
    PushConstant(DataValue),    // push a pre-converted literal value
    PushNull,                   // push SQL NULL
    Add, Sub, Mul, Div,         // arithmetic (pops 2 Data, pushes 1 Data)
    CmpEquals, CmpNotEquals,    // comparison (pops 2 Data, pushes 1 Bool)
    CmpLessThan, CmpLessOrEqual,
    CmpGreaterThan, CmpGreaterOrEqual,
    And, Or, Not,               // 3VL logical (pop Bools, push Bool)
    IsNull, IsNotNull,          // (pop Data, push Bool)
    In(usize),                  // pool index into SelectionExecutor::in_sets
    Like(usize),                // pool index into SelectionExecutor::like_patterns
    JumpIfFalse(usize),         // short-circuit AND: skip to pc=offset if top is False
    JumpIfTrue(usize),          // short-circuit OR: skip to pc=offset if top is True
}

Size discipline: In and Like store a pool index (usize) rather than the actual InSet or LikePattern objects. This keeps every instruction variant ≤ 16 bytes, so the entire bytecode vector fits tightly in CPU cache during the dispatch loop.

`VMValue`

pub enum VMValue<'a> {
    Data(Option<Cow<'a, DataValue>>),  // a nullable SQL value
    Bool(TriValue),                    // a predicate truth value
}

The stack holds VMValue entries. Data carries a value that can be NULL (None) or a (possibly borrowed) DataValue. Bool carries a TriValue. The distinction allows the executor to catch type errors at runtime (e.g. an arithmetic instruction applied to a Bool).

`InSet`

pub struct InSet {
    pub values: Vec<DataValue>,  // non-null items in the IN list
    pub has_null: bool,          // true if the list contained at least one NULL
}

Pre-built at compile time. During evaluation, the In instruction does a linear scan of values. If the scan misses and has_null is true, the result is UNKNOWN (not FALSE) — correct 3VL behaviour for x IN (1, NULL) when x != 1.

`LikePattern`

pub enum LikePattern {
    StartsWith(String),   // pattern% (no underscore wildcards)
    EndsWith(String),     // %pattern
    Contains(String),     // %pattern%
    Regex(Regex),         // general case — compiled once at plan time
}

Pattern compilation happens in compile_like_pattern. Simple patterns are detected and stored as string-only variants (StartsWith etc.), bypassing the regex engine entirely. Only patterns with _ wildcards or complex % placement fall through to the compiled Regex variant.

6. Tuple & Storage Format

Physical Row Layout

Every serialised tuple written by serialize_nullable_row follows this exact layout:

┌────────────────────────────────────────────────────────────────────────┐
│ Header (4 bytes)                                                       │
│   [0..2]  u16  num_cols       — number of logical columns              │
│   [2..4]  u16  num_varlen     — number of variable-length columns      │
├────────────────────────────────────────────────────────────────────────┤
│ Null Bitmap  — ceil(num_cols / 8) bytes                                │
│   One bit per logical column (bit=1 → column is NULL)                  │
├────────────────────────────────────────────────────────────────────────┤
│ Var-Len Offset Table — num_varlen × 2 bytes                            │
│   Each entry is a u16 absolute byte offset into the payload region.    │
│   0x0000 is a NULL sentinel (no payload for that column).              │
├────────────────────────────────────────────────────────────────────────┤
│ Fixed-Length Data   — packed in physical column order, alignment-padded│
├────────────────────────────────────────────────────────────────────────┤
│ Var-Length Payloads — packed in physical order, no length prefix       │
│   Boundaries inferred from the offset table above.                     │
└────────────────────────────────────────────────────────────────────────┘

Logical vs. Physical Column Order

The schema has a logical order (the order columns were declared by the user). Internally, columns are reordered so that all fixed-length columns come first (the fixed region), followed by all variable-length columns (the var-len region). PhysicalSchema::from_logical computes this mapping, and physical.logical_to_physical[i] gives the physical slot for logical column i.

Null Representation

A column is NULL if and only if its bit in the null bitmap is 1. The bitmap is consulted first in extract_column:

if bitmap.is_null(target_idx) {
    return Ok(None);  // early exit — no payload to read
}

For variable-length NULL columns, the offset table stores 0x0000 as a sentinel. The extraction code tracks seen_non_null (not the raw slot index r) to correctly skip null slots when computing a column's payload range — a critical correctness fix for schemas where earlier var-len columns may be NULL.

Fixed-Length Column Access

O(1): the layout pre-computes fixed_col_offsets[rank], so the column's bytes in the fixed region are accessed directly without scanning:

let col_start = layout.fixed_data_start + layout.fixed_col_offsets[rank];
let col_size  = ty.fixed_size().unwrap();
DataValue::from_bytes(ty, &tuple[col_start..col_start + col_size])

Variable-Length Column Access

The offset table is scanned to find the start and end offsets of the target column's payload. The end is either the next non-null var-len column's start offset, or total_row_size if the target is the last non-null var-len column.

Lazy / Minimal Decoding

extract_column decodes only one column per call. The rest of the tuple bytes are never touched. Lazy column extraction is achieved implicitly through the bytecode execution model. Only columns referenced by PushColumn instructions are accessed at runtime. The used_columns set exists but is not used as a runtime gate.

7. Algorithms Used

A. Predicate Normalisation

normalize_predicate is a recursive pre-pass over the predicate tree performed once before compilation. It applies:

Constant Folding in Expressions: normalize_expr evaluates any Expr whose operands are both Constant at planning time. For example, 2 + 3 → Constant::Int(5). NULL propagation is also folded: any arithmetic on NULL yields NULL.
Canonical Form for Comparisons: If a Compare node has Constant on the left and Column on the right (e.g. 4 < id), the operands are swapped and the operator is flipped (< → >) so that Column is always on the left (id > 4). This simplifies reasoning about the comparison.
BETWEEN Expansion: Predicate::Between(e, low, high) is rewritten as:
```
Predicate::And(
    Predicate::Compare(e, >=, low),
    Predicate::Compare(e, <=, high)
)
```
After this, BETWEEN never appears again in the tree.
LIKE Regex Compilation: LIKE patterns are initially compiled into a general regex during normalization. Optimized pattern variants (e.g., StartsWith, EndsWith, Contains) are selected later during bytecode compilation (compile_like_pattern), not during normalization.

B. Column Resolution

resolve_columns is also a recursive tree walk. For every Expr::Column, it searches the schema's column list for a matching name and stores the index in ColumnReference::column_index. It simultaneously validates type compatibility for both sides of every comparison:

Numeric vs. numeric (INT, SMALLINT, BIGINT, REAL, DOUBLE PRECISION)
Text vs. text (VARCHAR, CHAR, CHARACTER)
Date vs. date

If the types are incompatible, resolve_columns returns Err and the executor is not created.

C. Bytecode Compilation

compile_predicate is a recursive traversal that emits instructions into a Vec<Instruction> (the bytecode).

Expression compilation (compile_expr):

Expr::Column(ref) → PushColumn(idx)
Expr::Constant(c) → PushConstant(dv) or PushNull
Expr::Add(l, r) → compile_expr(l) + compile_expr(r) + Add
(similarly for Sub, Mul, Div)

The result follows postfix (Reverse Polish) order — left operand pushed first, then right, then operator.

Predicate compilation (compile_predicate):

Compare(l, op, r) → compile_expr(l), compile_expr(r), CmpXxx
IsNull(e) → compile_expr(e), IsNull
Not(p) → compile_predicate(p), Not
In(e, list) → compile_expr(e), build InSet, push to pool, In(pool_idx)
Like(e, pat, re) → compile_expr(e), build LikePattern, push to pool, Like(pool_idx)

Short-Circuit AND:

compile(left)
JumpIfFalse(target)    ← placeholder PC 0; back-patched after right is emitted
compile(right)
And                    ← target points here

If left is False, JumpIfFalse skips the right-side instructions and And entirely. The False value stays on the stack to serve as the final result. If left is True or Unknown, fall through to evaluate right, then And combines both.

Short-Circuit OR:

compile(left)
JumpIfTrue(target)     ← placeholder; back-patched
compile(right)
Or                     ← target points here

Symmetric: if left is True, skip right evaluation entirely.

Back-patching: the jump target is emitted as 0 (placeholder), then the actual instruction index is written back once we know where And/Or lands.

D. Stack-Machine Execution (`evaluate_tuple`)

The dispatch loop:

pc = 0
stack = [VMValue; 128]  ← on the call frame
sp = 0

while pc < bytecode.len():
    match bytecode[pc]:
        PushColumn(idx) → extract_column(types, tuple, idx) → push Data(val)
        PushConstant(dv) → push Data(Some(Borrowed(dv)))
        PushNull         → push Data(None)

        Add / Sub / Mul / Div:
            right = pop() as Data
            left  = pop() as Data
            result = compute_arithmetic(op, left, right)
            push Data(result)

        CmpXxx:
            right = pop() as Data
            left  = pop() as Data
            tri = compare_nullable(left, right)   ← None operand → Unknown
            push Bool(tri)

        And:
            right = pop() as Bool
            left  = pop() as Bool
            push Bool(apply_and(left, right))

        Or:
            right = pop() as Bool
            left  = pop() as Bool
            push Bool(apply_or(left, right))

        Not:
            val = pop() as Bool
            push Bool(not(val))

        JumpIfFalse(offset):
            top = pop()
            if top == Bool(False): push(top); pc = offset; continue
            else: push(top); pc++; continue

        JumpIfTrue(offset):
            top = pop()
            if top == Bool(True): push(top); pc = offset; continue
            else: push(top); pc++; continue

    pc++

assert sp == 1
return stack[0] as Bool

E. Three-Valued Logic Implementation

The 3VL combinators are pure functions with no branches beyond simple pattern matching:

// AND: False dominates; True only when both True; else Unknown
pub fn apply_and(left: TriValue, right: TriValue) -> TriValue {
    match (left, right) {
        (TriValue::False, _) | (_, TriValue::False) => TriValue::False,
        (TriValue::True, TriValue::True)             => TriValue::True,
        _                                            => TriValue::Unknown,
    }
}

// OR: True dominates; False only when both False; else Unknown
pub fn apply_or(left: TriValue, right: TriValue) -> TriValue {
    match (left, right) {
        (TriValue::True, _) | (_, TriValue::True)   => TriValue::True,
        (TriValue::False, TriValue::False)           => TriValue::False,
        _                                            => TriValue::Unknown,
    }
}

NULL comparisons propagate to UNKNOWN via compare_nullable:

// Any NULL operand → None (UNKNOWN); otherwise Some(Ordering)
match compare_nullable(left.as_deref(), right.as_deref()) {
    Ok(Some(ordering)) => map_ordering_to_cmp_result(ordering, op),
    Ok(None)           => TriValue::Unknown,
    Err(e)             => return Err(e),
}

F. Arithmetic Evaluation (`compute_arithmetic`)

Arithmetic follows PostgreSQL semantics:

Int / Int → Int (truncating division toward zero; 5 / 2 = 2)
Int / Float → Float (the narrower type is widened before the operation)
Division by zero → Err("Division by zero")
Either operand NULL → None (NULL propagation)
Integer overflow uses saturating arithmetic (saturating_add, saturating_sub, saturating_mul)

Cross-type widening is handled by recursive re-dispatch after promoting the narrower operand.

8. Optimizations

1. Short-Circuit Evaluation (AND / OR)

What: For A AND B, if evaluating A yields False, evaluation of B is skipped entirely. For A OR B, if A is True, B is skipped.

How: At compile time, JumpIfFalse and JumpIfTrue instructions are inserted between the left and right sub-expressions. The jump target skips the right-side bytecode and lands at the combining And / Or instruction.

Benefit: In the common case where a complex predicate has an early-failing short-circuit arm, a large portion of the instruction stream is never executed per tuple. For large tables this can reduce evaluation cost significantly.

2. No Recursion at Runtime

What: The hot evaluation path (evaluate_tuple) is a flat while pc < bytecode.len() dispatch loop with no function calls (except extract_column for column access).

How: All recursive structure in the predicate tree is linearised at compile time into the flat bytecode stream.

Benefit: No stack frame allocation per recursive call. CPU branch predictor can learn the while loop pattern. No risk of stack overflow on deeply nested predicates (the VM stack is bounded at 128 slots and caught at runtime).

3. Lazy Column Extraction

What: extract_column decodes one column at a time, only when the PushColumn instruction for that column is executed.

How: The raw tuple bytes are a &[u8] slice. extract_column reads only the null bitmap bit and the relevant offset/data bytes for the requested column — the rest of the row bytes are never read.

Benefit: For predicates that reference only one or two columns of a wide table, the vast majority of each tuple's bytes are never touched. This reduces memory bandwidth and avoids the overhead of full-row deserialisation on the hot path.

4. Zero-Copy Constant Access

What: Constants pushed onto the VM stack are Cow::Borrowed(&DataValue) references into the PushConstant instruction itself, not clones.

How: Instruction::PushConstant(DataValue) owns the value. evaluate_tuple pushes VMValue::Data(Some(Cow::Borrowed(dv))), borrowing from the instruction.

Benefit: No heap allocation for constants on the critical path. For queries with many constant comparisons (e.g. IN lists converted to individual comparisons), this avoids repeated clone() calls.

5. Constant Folding at Plan Time

What: Arithmetic expressions over two constants are evaluated once during normalize_expr and replaced by a single Constant node.

How: normalize_expr pattern-matches on (Constant, Constant) operand pairs and reduces them immediately.

Benefit: 2 + 3 in a predicate never generates three instructions (PushConstant, PushConstant, Add) — it generates one (PushConstant(5)). For predicates with compile-time-known arithmetic this eliminates dead computation across every tuple.

6. Canonical Comparison Order

What: Comparisons are normalised so the column reference is always on the left and the constant always on the right (e.g. 4 < id becomes id > 4).

How: normalize_predicate checks if the left operand is Constant and right is Column; if so, swaps them and flips the operator.

Benefit: Simplifies runtime reasoning and avoids any asymmetric handling in the comparison instruction.

7. Pre-Compiled LIKE Patterns

What: LIKE patterns are compiled to a LikePattern (a specific string-match variant or a Regex) exactly once at plan time.

How: compile_like_pattern first checks whether the pattern is a simple prefix/suffix/contains (no _ wildcard, single %). If so, it stores a cheap string variant. Otherwise it stores the pre-compiled Regex.

Benefit: No regex compilation per tuple. Simple patterns (prefix%, %suffix, %contains%) use direct Rust str::starts_with/ends_with/contains calls — far cheaper than a regex match.

8. IN Set as Constant Pool

What: InSet objects (the pre-built value lists for IN predicates) live in a separate pool vector on the executor, not inline in the instruction.

How: Instruction::In(usize) holds only a pool index. The actual InSet is in SelectionExecutor::in_sets[idx].

Benefit: Every Instruction variant stays ≤ 16 bytes. The bytecode vector is dense and cache-friendly. The InSet / LikePattern objects, which can be large, do not bloat the instruction stream.

9. Fixed-Size VM Stack

What: The evaluation stack is a [VMValue; 128] array on the call frame — not a Vec<VMValue>.

How: evaluate_tuple declares let mut stack: [VMValue; 128] = ... as a local. Stack overflow (more than 128 simultaneous values) returns Err rather than heap-allocating.

Benefit: No heap allocation for the stack per tuple evaluation. The array is allocated once on function entry and lives entirely on the CPU stack.

9. Changes to Existing System

New Module: `backend/query/`

Added src/backend/query/mod.rs and src/backend/query/where_builder.rs.
Publicly exports build_predicate_from_sql via pub use where_builder::build_predicate_from_sql.
Declared as a submodule in backend/mod.rs (or equivalent).

New Module: `backend/executor/selection.rs`

Added the entire selection executor as a new file.
Declares all public types (Predicate, Expr, ColumnReference, Constant, TriValue, ComparisonOp, SelectionExecutor) along with the filter utility functions.
Uses existing crate types: DataValue, DataType, Table, PhysicalSchema, RowLayout, NullBitmap, compare_nullable, OrderedF64.

10. Backend Functions Added

Predicate Builder (`backend/query/where_builder.rs`)

Function	Visibility	Purpose
`build_predicate_from_sql`	`pub`	Parse SQL string → internal Predicate tree
`extract_where_clause`	private	Pull the WHERE `SqlExpr` from a parsed `Statement`
`convert_predicate`	private	Recursively map `SqlExpr` (predicate) → `Predicate`
`convert_expr`	private	Recursively map `SqlExpr` (value) → `Expr`
`convert_value`	private	Map `sqlparser::Value` → internal `Constant`
`map_operator`	private	Map `BinaryOperator` → `ComparisonOp`

Selection Executor (`backend/executor/selection.rs`)

Planning

Function	Purpose
`SelectionExecutor::new`	Main constructor: normalise + resolve + compile
`normalize_predicate`	Constant folding, BETWEEN expansion, LIKE pre-compile
`normalize_expr`	Constant folding for expression sub-trees
`resolve_columns`	Bind column names → schema indices, type-check
`resolve_expr`	Column binding for expression sub-trees
`infer_expr_type`	Determine result `DataType` of an expression
`compile_predicate`	Lower predicate AST → bytecode instructions
`compile_expr`	Lower expression AST → push/arithmetic instructions
`compile_like_pattern`	Choose optimal `LikePattern` variant for a LIKE pattern

Runtime

Function	Purpose
`SelectionExecutor::evaluate_tuple`	Run bytecode against a raw tuple; return `TriValue`
`extract_column`	Decode one column from raw tuple bytes (lazy)
`compute_arithmetic`	Apply Add/Sub/Mul/Div to two nullable `DataValue` operands
`is_numeric` / `is_textual` / `is_null_literal`	Type-check helpers

3VL

Function	Purpose
`apply_and`	`TriValue` AND under SQL 3VL rules
`apply_or`	`TriValue` OR under SQL 3VL rules

Filter Utilities

Function	Purpose
`filter_tuples`	Batch filter: returns matching tuples as `Vec<Vec<u8>>`
`filter_tuples_detailed`	Batch filter with match/reject/unknown buckets
`count_matching_tuples`	Count matches without materialising them
`filter_tuples_streaming`	Streaming filter with callback — no intermediate buffer
`filter_iter`	Lazy iterator adapter that filters on the fly

Execution Flow (`data_cmd::show_tuples_cmd`)

User selects option 7
        │
        ▼
Prompt: "Enter table name: "
        │
        ▼
Prompt: "Enter SQL (single SELECT with WHERE): "
        │
        ▼
build_predicate_from_sql(sql.trim())
        │ Ok(predicate) / Err(e) → print error, abort
        ▼
Lookup table schema in in-memory catalog
        │ Err → "Database not found" / "Table not found"
        ▼
SelectionExecutor::new(predicate, table_schema.clone())
        │ Err(e) → print error, abort
        ▼
Read all pages (1..total_pages) → collect raw_tuples: Vec<Vec<u8>>
        │
        ▼
filter_tuples(&executor, &raw_tuples)
        │ Ok(matching) / Err → print error, abort
        ▼
Print header + each matching tuple via deserialize_nullable_row
        │
        ▼
Print "=== End of tuples ==="

Design Decisions

Table name entered separately from SQL. The CLI prompts for the table name independently before asking for the SQL string. The table is never parsed from the SQL. This is a deliberate simplification:

It avoids implementing a full FROM clause parser.
The selection operator does not need to know which table the data comes from — it operates purely on raw tuple bytes + schema.
The SQL string is used solely to obtain the WHERE clause.

Only the WHERE clause is processed from the SQL. extract_where_clause discards everything except select.selection. The projection list (SELECT *), ordering, limits, and joins are all ignored.

Responsibility split is clean:

Component	Responsibility
CLI (`data_cmd.rs`)	User I/O, page reading, result printing
Predicate Builder (`where_builder.rs`)	SQL string → `Predicate` tree
Selection Executor (`selection.rs`)	Schema binding, predicate compilation, tuple evaluation

12. Benchmark Analysis

12.1 Overview

This section presents a comprehensive performance evaluation of the selection engine implemented in RookDB (selection.rs) in comparison with PostgreSQL, a widely used and highly optimized production-grade database system.

The evaluation focuses on two fundamental aspects of query execution:

Compute Performance — the cost of evaluating predicates (logical and arithmetic operations).
Data Movement Performance — the cost of accessing, extracting, and materializing data from memory.

The results reveal a clear architectural tradeoff between computation efficiency and memory handling efficiency.

12.2 Executive Summary

Evaluation Area	Better Performing System
Predicate Evaluation (Compute)	PostgreSQL
Data Movement & Materialization (Wide Tables)	RookDB

PostgreSQL demonstrates superior performance in compute-intensive tasks due to its compiled execution model and highly optimized operators. In contrast, RookDB performs significantly better in memory-intensive workloads by minimizing unnecessary data access and movement.

12.3 Compute Performance (Predicate Evaluation)

This section evaluates the time required to process logical conditions such as comparisons, boolean operations, and arithmetic expressions.

Operation	RookDB (ns/t)	PostgreSQL (ns/t)	Winner	Relative Speed
Full Scan	181	62	PostgreSQL	~3× faster
Filter (`id > 500`)	508	68	PostgreSQL	~7× faster
AND Condition	550	60	PostgreSQL	~9× faster
Short-Circuit AND	426	45	PostgreSQL	~9× faster
String Match	427	65	PostgreSQL	~6× faster
Arithmetic	463	70	PostgreSQL	~6× faster
Worst Case	888	90	PostgreSQL	~10× faster

Explanation

The metric ns/t (nanoseconds per tuple) represents the average time taken to process one row.
Lower values indicate better performance.

Analysis

PostgreSQL uses a compiled execution model, meaning queries are translated into efficient low-level machine instructions.
RookDB uses a bytecode-based virtual machine, where each instruction is interpreted at runtime.

This introduces overhead due to:

Instruction decoding
Dispatch loops
Stack operations

As a result, RookDB is slower in compute-heavy workloads.

12.4 Data Movement and Materialization (Wide Tables)

This section evaluates performance when processing wide tables (21 columns), where memory access and data handling dominate execution time.

Mode	RookDB (ns/t)	PostgreSQL (ns/t)	Winner	Relative Speed
Full Scan	188	85	PostgreSQL	~2× faster
Compute Only	849	82	PostgreSQL	~10× faster
Streaming	747	1293	RookDB	~1.7× faster
Materialized Output	743	1666	RookDB	~2.2× faster

Explanation

Materialization: Creating output rows after filtering.
Streaming: Processing rows one-by-one without storing all results.

Analysis

In wide-table scenarios:

PostgreSQL overhead:

Sequentially accessing columns (tuple deforming)
Reconstructing full rows in memory
Copying data during output generation

RookDB optimizations:

Lazy column extraction: Only required columns are accessed
Zero-copy memory access: Avoids unnecessary data duplication
Minimal deserialization: Works directly on raw bytes

Key Result

RookDB achieves up to 2.2× better performance in materialization-heavy workloads.

12.5 Large-Scale Performance (1,000,000 Rows)

This section evaluates how both systems perform when the dataset size increases significantly.

Test	RookDB (ns/t)	PostgreSQL (ns/t)	Winner	Relative Speed
Full Scan	170	64	PostgreSQL	~2.6× faster
Filter	377	72	PostgreSQL	~5× faster
Materialization	383	564	RookDB	~1.4× faster
Streaming	375	515	RookDB	~1.3× faster

Explanation

This test checks scalability, i.e., how performance changes as data size increases.

Analysis

Both systems show stable and near-linear scalability, meaning performance degrades predictably as data grows.
PostgreSQL continues to dominate compute-heavy operations.
RookDB maintains an advantage in:
- Memory-intensive workloads
- Streaming and materialization tasks

Important Observation

RookDB’s consistent performance indicates:

Efficient cache usage
Predictable execution behavior
Low memory overhead

12.6 Final Assessment

Performance Category	Winner
Compute Performance	PostgreSQL
Data Movement Efficiency	RookDB
Memory Efficiency	RookDB

12.7 Key Insight

The benchmark highlights a fundamental principle in database system design:

The cost of data movement can dominate the total query execution time, especially for wide tables.

PostgreSQL excels due to its optimized computation engine.
RookDB excels due to its efficient memory access and reduced data movement.

12.8 Concluding Remark

The evaluation demonstrates a clear architectural tradeoff:

PostgreSQL is optimized for computation.
RookDB is optimized for memory efficiency and data access.

In modern data-intensive systems, where datasets are large and wide, minimizing data movement can lead to significant performance improvements.

13. External APIs Used

13.1 Overview

This section documents every external API from the storage-layer modules that selection.rs calls directly. These APIs are used in extract_column and execution logic, and collectively support column extraction, NULL handling, comparisons, and row layout interpretation.

13.2 API Summary Table

API Name	Purpose	Where Used
`compare_nullable`	NULL-aware, type-safe value comparison	`evaluate_tuple` comparison instruction arms
`DataValue::from_bytes`	Deserialize raw bytes into typed `DataValue`	`extract_column` fixed-length and variable-length paths
`NullBitmap::from_bytes`	Parse row null bitmap	`extract_column` bitmap initialization
`NullBitmap::is_null`	O(1) NULL test for target column	Early-exit branch in `extract_column`
`PhysicalSchema::from_logical`	Build logical-to-physical schema mapping	`extract_column` layout preparation
`RowLayout::compute`	Compute row offsets and layout metadata	`extract_column` layout preparation
`RowLayout::min_row_size`	Validate minimum structural row length	`extract_column` sanity check
`DataType::fixed_size`	Get byte width of fixed-length types	Fixed-length extraction in `extract_column`
`DataType::is_fixed_length`	Select fixed-length vs var-len decode strategy	Branch selection in `extract_column`

13.3 Detailed API Descriptions

`compare_nullable`

Property	Details
Module / Crate	`crate::types` (`types` sub-crate)
Signature	`fn compare_nullable(left: Option<&DataValue>, right: Option<&DataValue>) -> Result<Option<Ordering>, ...>`
Input	Two optional references to `DataValue`. `None` represents SQL NULL.
Output	`Ok(Some(Ordering))` when both operands are non-null and comparable; `Ok(None)` when either operand is NULL (yields UNKNOWN under 3VL); `Err` on type mismatch.
Purpose	Provides a type-aware, NULL-safe comparison that maps directly to SQL's 3VL NULL semantics — a NULL operand does not produce FALSE, it produces UNKNOWN.
Where Used	Called inside the `CmpEquals` / `CmpNotEquals` / `CmpLessThan` / `CmpLessOrEqual` / `CmpGreaterThan` / `CmpGreaterOrEqual` dispatch arms of `evaluate_tuple`. The returned `Option<Ordering>` is mapped to `TriValue::True`, `TriValue::False`, or `TriValue::Unknown`.

// Usage inside evaluate_tuple (CmpXxx arm)
let tri = match compare_nullable(left.as_deref(), right.as_deref()) {
    Ok(Some(ordering)) => { /* map ordering + op → True/False */ }
    Ok(None)           => TriValue::Unknown,   // NULL involved
    Err(e)             => return Err(e.to_string()),
};

`DataValue::from_bytes`

Property	Details
Module / Crate	`crate::types::DataValue`
Signature	`fn from_bytes(ty: &SqlDataType, bytes: &[u8]) -> Result<DataValue, String>`
Input	A `SqlDataType` describing how to interpret the bytes; a byte slice containing exactly the column's payload.
Output	`Ok(DataValue)` — the deserialised value in its native Rust representation; `Err(String)` on malformed data.
Purpose	Deserialises a single column's raw bytes into a typed `DataValue` that the VM can operate on. Only called for the one column actually requested — not for the whole row.
Where Used	Called in `extract_column` for both fixed-length and variable-length columns, immediately after the correct byte range within the tuple has been located.

// Fixed-length path
let value = DataValue::from_bytes(ty, &tuple[col_start..col_start + col_size])?;

// Variable-length path
let value = DataValue::from_bytes(ty, payload)?;

`NullBitmap::from_bytes`

Property	Details
Module / Crate	`crate::types::null_bitmap::NullBitmap`
Signature	`fn from_bytes(num_cols: usize, bytes: &[u8]) -> Result<NullBitmap, String>`
Input	The total number of logical columns; a byte slice covering exactly the null-bitmap region of the tuple (`ceil(num_cols / 8)` bytes).
Output	`Ok(NullBitmap)` — a wrapper that provides bit-level access to the packed bitmap; `Err` if the slice is too short.
Purpose	Parses the null bitmap embedded in every serialised tuple. The bitmap records, one bit per logical column, whether that column is NULL. This must be checked before attempting any payload access.
Where Used	Called at the start of `extract_column`, immediately after the 4-byte header is read.

let bm_start = RowLayout::bitmap_offset();
let bitmap = NullBitmap::from_bytes(
    types.len(),
    &tuple[bm_start..bm_start + layout.null_bitmap_size],
)?;

`NullBitmap::is_null`

Property	Details
Module / Crate	`crate::types::null_bitmap::NullBitmap`
Signature	`fn is_null(&self, col_idx: usize) -> bool`
Input	The logical index of the column to test (0-based).
Output	`true` if the column is NULL (its bit is set); `false` otherwise.
Purpose	Provides O(1) bit-level NULL check for a specific column without reading any data payload. This is the earliest possible exit point in `extract_column` — if the column is NULL, the function returns `Ok(None)` immediately without touching the fixed data or var-len regions.
Where Used	Called in `extract_column` immediately after parsing the bitmap.

if bitmap.is_null(target_idx) {
    return Ok(None);   // Column is NULL — no payload to decode
}

`PhysicalSchema::from_logical`

Property	Details
Module / Crate	`crate::types::row_layout::PhysicalSchema`
Signature	`fn from_logical(types: &[SqlDataType]) -> PhysicalSchema`
Input	The ordered slice of `SqlDataType` values representing the logical column schema (declaration order).
Output	A `PhysicalSchema` struct containing: `logical_to_physical` mapping (logical idx → physical slot), `num_fixed()` (count of fixed-length columns), `num_varlen()` (count of variable-length columns), and associated physical ordering metadata.
Purpose	Computes the column reordering that the storage layer applies at serialisation time — fixed-length columns are packed first, variable-length columns after. Without this mapping, `extract_column` would not know where to find a given logical column in the physical byte layout.
Where Used	Called once per `extract_column` invocation to establish the physical layout before locating the target column.

let physical = PhysicalSchema::from_logical(types);
// physical.logical_to_physical[target_idx] → physical slot index
// physical.num_fixed()                      → where var-len region begins

`RowLayout::compute`

Property	Details
Module / Crate	`crate::types::row_layout::RowLayout`
Signature	`fn compute(physical: &PhysicalSchema) -> RowLayout`
Input	A `PhysicalSchema` (produced by `PhysicalSchema::from_logical`).
Output	A `RowLayout` struct containing pre-computed byte offsets: `null_bitmap_size`, `fixed_data_start`, `fixed_col_offsets` (per fixed column), `varlen_table_offset()`, and `min_row_size()`.
Purpose	Pre-computes all structural offsets for the row format so that individual column access is O(1) for fixed-length columns (direct index into `fixed_col_offsets`). Without this, every column access would require scanning the schema to sum up preceding column sizes.
Where Used	Called once per `extract_column` invocation, immediately after `PhysicalSchema::from_logical`.

let layout = RowLayout::compute(&physical);
// layout.fixed_data_start           → byte offset where fixed data begins
// layout.fixed_col_offsets[rank]    → byte offset of fixed column 'rank' within fixed region
// layout.null_bitmap_size           → size of null bitmap in bytes

`RowLayout::min_row_size`

Property	Details
Module / Crate	`crate::types::row_layout::RowLayout`
Signature	`fn min_row_size(&self) -> usize`
Input	`&self` — the computed `RowLayout`.
Output	The minimum number of bytes a valid tuple with this schema must occupy (header + bitmap + offset table + fixed data; does not include var-len payloads).
Purpose	Used as a sanity check against the actual tuple byte length before attempting any interpretation. Rejects clearly malformed or truncated tuples early, before any pointer arithmetic into the byte slice.
Where Used	Called in `extract_column` right after `RowLayout::compute`, before any column-specific access.

if total_row_size < layout.min_row_size() {
    return Err(format!(
        "Row ({} bytes) shorter than minimum layout size ({} bytes)",
        total_row_size, layout.min_row_size()
    ));
}

`DataType::fixed_size`

Property	Details
Module / Crate	`crate::types::DataType` (`SqlDataType` alias)
Signature	`fn fixed_size(&self) -> Option<u32>`
Input	`&self` — a `SqlDataType` variant.
Output	`Some(n)` where `n` is the number of bytes this type always occupies (e.g. `INT` → `Some(4)`, `BIGINT` → `Some(8)`, `DATE` → `Some(4)`); `None` for variable-length types like `VARCHAR`.
Purpose	Determines the byte length to read for a fixed-length column. Combined with `fixed_col_offsets`, this gives the exact byte slice `[col_start .. col_start + col_size]` to pass to `DataValue::from_bytes`.
Where Used	Called in `extract_column`'s fixed-length column access path after confirming the column is fixed-length.

let col_size = ty.fixed_size()
    .expect("fixed-length type must have fixed_size") as usize;
let value = DataValue::from_bytes(ty, &tuple[col_start..col_start + col_size])?;

`DataType::is_fixed_length`

Property	Details
Module / Crate	`crate::types::DataType` (`SqlDataType` alias)
Signature	`fn is_fixed_length(&self) -> bool`
Input	`&self` — a `SqlDataType` variant.
Output	`true` for fixed-size types (INT, SMALLINT, BIGINT, REAL, DOUBLE PRECISION, DATE, CHAR(n — fixed)); `false` for variable-size types (VARCHAR, TEXT).
Purpose	Acts as the branch condition in `extract_column` to choose between the O(1) fixed-length path (direct offset lookup) and the var-len path (offset table scan). This single call directs the entire subsequent decoding strategy.
Where Used	Called in `extract_column` immediately after the NULL check, before any payload location logic.

if ty.is_fixed_length() {
    // O(1) fixed path: use pre-computed fixed_col_offsets
    let rank     = phys_idx;
    let col_start = layout.fixed_data_start + layout.fixed_col_offsets[rank];
    ...
}
// else: variable-length path — scan offset table

13.4 API Interaction Flow

The nine APIs collectively form the column extraction pipeline inside extract_column:

extract_column(types, tuple, target_idx)

1. NULL Check (Early Exit Optimization)

RowLayout::bitmap_offset()

Purpose: Computes the byte offset at which the null bitmap begins in the serialized tuple.
Input: None (associated function).
Output: A byte offset (usize) for bitmap access.
Where Used: Called at the beginning of extract_column to locate the bitmap slice.

NullBitmap::from_bytes(num_cols, bytes)

Purpose: Parses the packed null bitmap into a NullBitmap structure.
Input: num_cols: usize, bytes: &[u8] (bitmap slice of length ceil(num_cols / 8)).
Output: Result<NullBitmap, String>.
Where Used: Invoked immediately after bitmap offset computation in extract_column.

NullBitmap::is_null(target_idx)

Purpose: Performs a constant-time null test for the target logical column.
Input: target_idx: usize.
Output: bool (true if the target column is NULL).
Where Used: Evaluated directly after bitmap parsing to determine early termination.

If the column is NULL:

extract_column returns Ok(None).
No fixed-length or variable-length payload decoding is performed.

2. Layout Initialization (Storage Interpretation)

PhysicalSchema::from_logical(types)

Purpose: Converts logical schema order into physical storage order.
Input: types: &[SqlDataType].
Output: PhysicalSchema (including logical-to-physical mapping and fixed/varlen partitioning).
Where Used: Executed in extract_column before computing row offsets.

RowLayout::compute(&physical)

Purpose: Pre-computes structural offsets required for safe column access.
Input: physical: &PhysicalSchema.
Output: RowLayout (bitmap size, fixed-data start, fixed offsets, varlen table offset).
Where Used: Called once per extraction path setup in extract_column.

RowLayout::min_row_size()

Purpose: Validates tuple structural sufficiency before payload access.
Input: &RowLayout.
Output: usize minimum valid row length.
Where Used: Compared against tuple.len() to reject truncated or malformed rows.

3. Column Extraction (Core Logic)

DataType::is_fixed_length()

Purpose: Selects the decoding strategy for the target column.
Input: &SqlDataType for the target column.
Output: bool (true for fixed-length, false for variable-length).
Where Used: Branch condition in extract_column before payload location logic.

Fixed-length path (O(1)):

DataType::fixed_size()

Purpose: Returns the byte width for fixed-length column types.
Input: &SqlDataType.
Output: Option<u32> (Some(size) for fixed types, None otherwise).
Where Used: Computes exact slice bounds for direct fixed-region reads.

DataValue::from_bytes(ty, slice)

Purpose: Deserializes fixed-length payload bytes into a typed value.
Input: ty: &SqlDataType, slice: &[u8] (fixed-width payload).
Output: Result<DataValue, String>.
Where Used: Fixed-length branch after offset computation.

Variable-length path:

Offset table scan

Purpose: Derives payload start and end offsets from the varlen offset table.
Input: Varlen table entries (u16 offsets), null-state context, and tuple length.
Output: Payload boundary interval (start..end).
Where Used: Variable-length branch in extract_column before deserialization.

DataValue::from_bytes(ty, payload)

Purpose: Deserializes variable-length payload bytes into a typed value.
Input: ty: &SqlDataType, payload: &[u8].
Output: Result<DataValue, String>.
Where Used: Final decode step in the variable-length branch.

4. Final Output

Purpose: Return the decoded non-null value to the execution engine.
Input: Decoded DataValue from either extraction branch.
Output: Ok(Some(DataValue)) from extract_column.
Where Used: Consumed by PushColumn in evaluate_tuple as a VMValue::Data operand.

5. Comparison API (Post-Extraction)

compare_nullable(left, right)

Purpose: Performs null-aware, type-safe comparison for VM comparison opcodes and enforces SQL three-valued semantics.
Input: left: Option<&DataValue>, right: Option<&DataValue> (None denotes SQL NULL).
Output: Result<Option<Ordering>, _> where:
- Ok(Some(Ordering)) indicates both operands are non-null and comparable.
- Ok(None) indicates at least one operand is NULL (mapped to TriValue::Unknown).
- Err(_) indicates an invalid comparison (for example, incompatible types).
Role in 3-Valued Logic: The VM maps Ok(None) to TriValue::Unknown; Ok(Some(...)) is mapped to TriValue::True or TriValue::False according to the comparison opcode (CmpEquals, CmpLessThan, etc.).
Where Used: Invoked in SelectionExecutor::evaluate_tuple within comparison instruction handlers, after both operands are extracted and loaded.

14. New Files Introduced

File	Location	Purpose
`where_builder.rs`	`backend/query/`	Converts SQL WHERE clause into internal Predicate tree
`selection.rs`	`backend/executor/`	Executes predicate evaluation using bytecode-based engine

15. Database Structure Changes

No changes were made to the underlying storage layer, page format, or database file structure.
All functionality introduced for the selection operator operates purely at the query and execution layers.

15. Future Work

This section outlines potential enhancements to improve the functionality and performance of the current selection engine implementation .

17.1 Extend SQL Support (`FROM` Clause & Table Inference)

Current Limitation: The system does not parse the FROM clause. The table name is provided separately via the CLI.

Improvement:

Implement full SQL parsing including FROM clause handling
Support table name extraction and optional aliases

Benefit:

Aligns the system with standard SQL behavior
Removes manual table input dependency
Enables future extensions such as joins

17.2 Index-Based Filtering

Current Limitation: All queries perform a full table scan.

Improvement:

Introduce indexing mechanisms (e.g., B+ tree or hash index)
Use indexes to directly locate matching tuples

Benefit:

Reduces search complexity
Improves query performance on large datasets

17.3 Parallel Tuple Evaluation

Current Behavior: Tuples are processed sequentially.

Improvement:

Enable parallel processing of tuples across multiple threads

Benefit:

Improves scalability for large datasets
Utilizes multi-core processing effectively

Table of Contents
1. Overview
2. End-to-End Flow
3. Module Breakdown
4. API Design & Function Contracts
- Predicate Builder
- Selection Executor
5. Data Structures
6. Tuple & Storage Format
7. Algorithms Used
8. Optimizations
9. Changes to Existing System
- New Module: backend/query/
- New Module: backend/executor/selection.rs
10. Backend Functions Added
12. Benchmark Analysis
13. External APIs Used
14. New Files Introduced
15. Database Structure Changes
15. Future Work

RookDB — Selection Operator Documentation

Table of Contents​

1. Overview​

The Selection Operator (σ)​

Role of the WHERE Clause​

Two-Stage Execution Pipeline​

2. End-to-End Flow​

Step 1 — User Selects "Select Tuples" from CLI​

Step 2 — CLI Prompts for Table Name and SQL​

Step 3 — SQL Parsing via sqlparser​

Step 4 — WHERE Clause Extraction​

Step 5 — SQL AST → Internal Predicate Tree​

Step 6 — Schema Lookup​

Step 7 — Executor Initialisation​

Step 8 — Raw Tuple Collection​

Step 9 — Predicate Filtering​

Step 10 — Output​

3. Module Breakdown​

A. Predicate Builder — backend/query/where_builder.rs​

build_predicate_from_sql​

extract_where_clause​

convert_predicate​

convert_expr​

Example​

B. Selection Executor — backend/executor/selection.rs​

Execution Workflow in SelectionExecutor::new​

Per-Tuple Evaluation in evaluate_tuple​

Predicate Evaluation Strategy​

Example​

4. API Design & Function Contracts​

Predicate Builder​

build_predicate_from_sql​

Selection Executor​

SelectionExecutor::new​

SelectionExecutor::evaluate_tuple​

filter_tuples​

Additional Filter Variants​

3VL Combinators (module-level free functions)​

5. Data Structures​

Predicate​

Expr​

ColumnReference​

Constant​

Three-Valued Logic — TriValue​

ComparisonOp​

Instruction (VM Bytecode)​

VMValue​

InSet​

LikePattern​

6. Tuple & Storage Format​

Physical Row Layout​

Logical vs. Physical Column Order​

Null Representation​

Fixed-Length Column Access​

Variable-Length Column Access​

Lazy / Minimal Decoding​

7. Algorithms Used​

A. Predicate Normalisation​

B. Column Resolution​

C. Bytecode Compilation​

D. Stack-Machine Execution (evaluate_tuple)​

E. Three-Valued Logic Implementation​

F. Arithmetic Evaluation (compute_arithmetic)​

8. Optimizations​

1. Short-Circuit Evaluation (AND / OR)​

2. No Recursion at Runtime​

3. Lazy Column Extraction​

4. Zero-Copy Constant Access​

5. Constant Folding at Plan Time​

6. Canonical Comparison Order​

7. Pre-Compiled LIKE Patterns​

8. IN Set as Constant Pool​

9. Fixed-Size VM Stack​

9. Changes to Existing System​

New Module: backend/query/​

New Module: backend/executor/selection.rs​

10. Backend Functions Added​

Predicate Builder (backend/query/where_builder.rs)​

Selection Executor (backend/executor/selection.rs)​

Planning​

Table of Contents

1. Overview

The Selection Operator (σ)

Role of the WHERE Clause

Two-Stage Execution Pipeline

2. End-to-End Flow

Step 1 — User Selects "Select Tuples" from CLI

Step 2 — CLI Prompts for Table Name and SQL

Step 3 — SQL Parsing via `sqlparser`

Step 4 — WHERE Clause Extraction

Step 5 — SQL AST → Internal Predicate Tree

Step 6 — Schema Lookup

Step 7 — Executor Initialisation

Step 8 — Raw Tuple Collection

Step 9 — Predicate Filtering

Step 10 — Output

3. Module Breakdown

A. Predicate Builder — `backend/query/where_builder.rs`

`build_predicate_from_sql`

`extract_where_clause`

`convert_predicate`

`convert_expr`

Example

B. Selection Executor — `backend/executor/selection.rs`

Execution Workflow in `SelectionExecutor::new`

Per-Tuple Evaluation in `evaluate_tuple`

Predicate Evaluation Strategy

Example

4. API Design & Function Contracts

Predicate Builder

`build_predicate_from_sql`

Selection Executor

`SelectionExecutor::new`

`SelectionExecutor::evaluate_tuple`

`filter_tuples`

Additional Filter Variants

3VL Combinators (module-level free functions)

5. Data Structures

`Predicate`

`Expr`

`ColumnReference`

`Constant`

Three-Valued Logic — `TriValue`

`ComparisonOp`

`Instruction` (VM Bytecode)

`VMValue`

`InSet`

`LikePattern`

6. Tuple & Storage Format

Physical Row Layout

Logical vs. Physical Column Order

Null Representation

Fixed-Length Column Access

Variable-Length Column Access

Lazy / Minimal Decoding

7. Algorithms Used

A. Predicate Normalisation

B. Column Resolution

C. Bytecode Compilation

D. Stack-Machine Execution (`evaluate_tuple`)

E. Three-Valued Logic Implementation

F. Arithmetic Evaluation (`compute_arithmetic`)

8. Optimizations

1. Short-Circuit Evaluation (AND / OR)

2. No Recursion at Runtime

3. Lazy Column Extraction

4. Zero-Copy Constant Access

5. Constant Folding at Plan Time

6. Canonical Comparison Order

7. Pre-Compiled LIKE Patterns

8. IN Set as Constant Pool

9. Fixed-Size VM Stack

9. Changes to Existing System

New Module: `backend/query/`

New Module: `backend/executor/selection.rs`

10. Backend Functions Added

Predicate Builder (`backend/query/where_builder.rs`)

Selection Executor (`backend/executor/selection.rs`)

Planning

Runtime