# Architecture of OsirisDB
This document outlines the high-level architecture and design decisions behind the `OsirisDB` lexer and parser.
## Core Design Philosophy
- **Zero External Dependencies**: The parser is written entirely in standard Rust without external parser generators (like LALRPOP or Nom).
- **Separation of Concerns**: Lexer, AST, and Parser are cleanly separated into three independent modules.
- **Zero-Copy Lexing**: The lexer utilizes lifetimes to refer back to parts of the original SQL input string where possible, minimizing heap allocations.
- **Extensible via Traits**: Instead of housing all parser functions inside a single giant `Parser` struct implementation, the parser functions are organized into traits implemented for `Parser<'a>`.
---
## 1. Lexer (Lexical Analyzer)
The Lexer (`src/lexer/`) translates raw query strings (SQL) into a flat sequence of tokens.
### Key Components
1. **`Span`**: Records the byte offsets (`start..end`) and human-readable line and column positions.
2. **`TokenKind`**: A comprehensive enum representing keywords, literal types, operators, and punctuation.
3. **`Token`**: Combines a `TokenKind` and its source `Span`.
4. **`Lexer<'a>`**: Performs the tokenization process using `Peekable<CharIndices<'a>>`.
### Keyword Resolution
To avoid scanning keywords character-by-character inside the parser, the lexer reads generic identifiers and resolves them against a static keyword matcher:
```rust
// src/lexer/lookup_keyword.rs
pub fn lookup_keyword(word: &str) -> TokenKind {
match word.to_uppercase().as_str() {
"SELECT" => TokenKind::Select,
"FROM" => TokenKind::From,
// ...
_ => TokenKind::Ident,
}
}
```
---
## 2. Abstract Syntax Tree (AST)
The AST (`src/ast/`) defines strongly typed Rust data structures representing the logical components of an SQL query.
### Module Layout
- **`common/`**: Universal types like `DataType` (int, varchar, etc.), `ObjectName` (qualified names), and `Value` (literals).
- **`ddl/`**: Statements modifying database structure (`CreateTableStmt`, `CreateIndexStmt`, `DropTableStmt`).
- **`dml/`**: Data manipulation statements (`InsertStmt`, `UpdateStmt`, `DeleteStmt`).
- **`query/`**: Representation of queries (`SelectStmt`, joins, CTEs, window definitions).
- **`expression/`**: Highly recursive operator tree representing expressions (`Expr`).
### Recursive Expressions
SQL expressions (like `(a + b) > 5`) are modeled using a recursive `Expr` enum:
```rust
pub enum Expr {
Literal(Value),
Column { table: Option<String>, name: Symbol },
BinOp { op: BinOpKind, lhs: Box<Expr>, rhs: Box<Expr> },
// ...
}
```
---
## 3. Parser (Syntactic Analyzer)
The parser (`src/parser/`) converts the stream of tokens generated by the Lexer into AST nodes. It combines **Recursive Descent** for structured SQL statements with **Pratt Parsing** for operator expressions.
### Lookahead Shell
The core `Parser<'a>` maintains a two-token lookahead state:
```rust
pub struct Parser<'a> {
pub source: &'a str,
pub lexer: Lexer<'a>,
pub current: Token,
pub peek: Token,
}
```
### Pratt Expression Parsing
Expressions in SQL require correct operator precedence (e.g. `*` binds tighter than `+`). Pratt parsing uses "binding powers" associated with tokens to resolve nesting:
```rust
fn parse_expr_bp(&mut self, min_bp: u8) -> Result<Expr, ParserError> {
let mut lhs = self.parse_prefix()?;
while let Some((left_bp, right_bp)) = infix_binding_power(self.current_token()) {
if left_bp < min_bp {
break;
}
lhs = self.parse_infix(lhs, right_bp)?;
}
Ok(lhs)
}
```
### Trait Extension Pattern
To keep files small and readable, the parsing logic is split into multiple traits:
```rust
// src/parser/select.rs
pub trait SelectParser {
fn parse_select(&mut self) -> Result<SelectStmt, ParserError>;
}
impl<'a> SelectParser for Parser<'a> {
fn parse_select(&mut self) -> Result<SelectStmt, ParserError> {
// ...
}
}
```
This makes it extremely easy for contributors to add features without causing merge conflicts in `parser.rs`.
---
## 4. Binder
The **Binder** resolves database identifiers, namespace bindings, and type mappings against the database catalog (schema).
### Key Responsibilities
1. **Name Resolution**: Map user-specified names (like table names `users` or qualified column names `public.users.age`) to internal unique catalog IDs (e.g. `TableId`, `ColumnId`).
2. **Catalog Verification**: Ensure that referenced schemas, tables, columns, indexes, and views actually exist in the database catalog.
3. **Type Resolution**: Infer the types of expressions, operators, and parameters. For instance, binding `age + 2` requires verifying that `age` is of a numeric type and that the return type of the expression is compatible.
4. **Function Resolution**: Match function names (such as `COUNT`, `SUBSTRING`) to registered function signatures and handle implicit casting.
### Proposed Rust Interface
The Binder consumes the raw Abstract Syntax Tree (AST) generated by the parser and produces a strongly-typed **Bound AST** (e.g. `BoundStatement` and `BoundExpr`):
```rust
pub struct Binder<'a> {
pub catalog: &'a Catalog,
pub context: BinderContext,
}
impl<'a> Binder<'a> {
pub fn bind_statement(&mut self, stmt: Statement) -> Result<BoundStatement, BinderError> {
match stmt {
Statement::Select(select) => Ok(BoundStatement::Select(self.bind_select(select)?)),
// ... other statements
}
}
}
```
---
## 5. Semantic Analyzer
The **Semantic Analyzer** performs advanced semantic checks on the Bound AST to validate structural and semantic constraints that syntactic analysis alone cannot catch.
### Key Responsibilities
1. **Aggregate Validation**: Ensure aggregate functions (like `SUM()`, `AVG()`) are not nested and that non-aggregated columns in a `SELECT` statement with aggregates are correctly listed in the `GROUP BY` clause.
2. **Window Function Context**: Verify window functions (e.g. `ROW_NUMBER() OVER (...)`) are restricted to valid syntactic positions (only in `SELECT` lists and `ORDER BY` clauses).
3. **Constraint Integrity**: Verify defaults, checks, and foreign keys are semantically valid and do not reference invalid symbols.
4. **Privileges & Authorization**: Check user permissions to verify that the active user/role has sufficient access privileges to perform the requested operation on the target resources.
### Proposed Rust Interface
We can implement a visitor pattern over the bound statement hierarchy to run semantic checks:
```rust
pub trait BoundVisitor {
fn visit_bound_select(&mut self, select: &BoundSelect) -> Result<(), SemanticError>;
fn visit_bound_expr(&mut self, expr: &BoundExpr) -> Result<(), SemanticError>;
}
```
---
## 6. Logical Planner
The **Logical Planner** translates the bound, annotated AST into a relational algebra execution tree known as a **Logical Plan**.
### Key Responsibilities
1. **Relational Operator Construction**: Maps SQL features to logical operators (e.g. `SELECT` maps to `LogicalProjection`, `WHERE` to `LogicalFilter`, `JOIN` to `LogicalJoin`, and `LIMIT` to `LogicalLimit`).
2. **Abstraction Layer**: Represents _what_ the query wants to do, completely independent of how data is stored, indexed, or retrieved physically.
### Proposed Rust Interface
The Logical Plan is represented as a tree of logical operators:
```rust
pub enum LogicalPlan {
Scan(LogicalScan),
Filter(LogicalFilter),
Projection(LogicalProjection),
Join(LogicalJoin),
Aggregate(LogicalAggregate),
Limit(LogicalLimit),
// ...
}
pub struct LogicalScan {
pub table_id: TableId,
pub projection: Vec<ColumnId>,
}
```
---
## 7. Optimizer
The **Optimizer** receives a logical plan and transforms it into a semantically equivalent but significantly more efficient version.
### Key Responsibilities
1. **Rule-Based Optimization (RBO)**: Apply deterministic optimization heuristics:
- **Predicate Pushdown**: Move filter operations as close to the physical data source as possible.
- **Projection Pruning**: Eliminate unused columns from scan/projection nodes early.
- **Constant Folding**: Evaluate deterministic expressions (like `WHERE age > 10 + 8`) into static values (`WHERE age > 18`) at compile time.
2. **Cost-Based Optimization (CBO)**: Select the best execution plan based on statistical data (cardinalities, page counts, histograms):
- **Join Reordering**: Reorder join sequences to minimize intermediate result sizes.
- **Access Path Selection**: Evaluate costs of table scans vs index scans.
### Proposed Rust Interface
```rust
pub trait OptimizerRule {
fn optimize(&self, plan: LogicalPlan) -> Result<LogicalPlan, OptimizerError>;
}
pub struct Optimizer {
pub rules: Vec<Box<dyn OptimizerRule>>,
}
```
---
## 8. Physical Planner
The **Physical Planner** maps the optimized logical plan to a **Physical Plan** by choosing concrete algorithms for each logical node.
### Key Responsibilities
1. **Algorithm Assignment**: Choose physical algorithm implementations:
- Map `LogicalJoin` to `HashJoin`, `NestedLoopJoin`, or `SortMergeJoin`.
- Map `LogicalScan` to `SeqScan` (Sequential Page Scan) or `IndexScan` (B+ Tree traversal).
- Map `LogicalAggregate` to `HashAggregate` or `SortAggregate`.
2. **Physical Constraints & Sorting**: Insert operators to enforce ordering, grouping, or hashing requirements (e.g. adding a `PhysicalSort` before a merge join if the inputs are not pre-sorted).
### Proposed Rust Interface
```rust
pub enum PhysicalPlan {
SeqScan(PhysicalSeqScan),
IndexScan(PhysicalIndexScan),
HashJoin(PhysicalHashJoin),
NestedLoopJoin(PhysicalNestedLoopJoin),
HashAggregate(PhysicalHashAggregate),
Projection(PhysicalProjection),
Filter(PhysicalFilter),
Sort(PhysicalSort),
}
```
---
## 9. Executor
The **Executor** evaluates the physical execution plan and returns the resulting records.
### Key Responsibilities
1. **Tuple Processing Models**:
- **Volcano/Iterator Model (Pull-Based)**: Each operator pulls one row at a time via `next()` calls from its child. Very memory-efficient but has high function call overhead in languages like Rust due to dynamic dispatch.
- **Vectorized Engine (Batch-Based)**: Operators pull chunks of rows (e.g., batches of 1024 tuples) at a time. Dramatically reduces invocation overhead and maximizes CPU cache friendliness and SIMD instruction potential.
2. **Resource Management**: Manage internal thread pools for parallel operators and disk spill buffers for memory-intensive operations.
### Proposed Rust Interface
For a Volcano iterator-style execution:
```rust
pub trait PhysicalExecutor: Send + Sync {
fn init(&mut self) -> Result<(), ExecutionError>;
fn next(&mut self) -> Result<Option<RowBatch>, ExecutionError>;
fn close(&mut self) -> Result<(), ExecutionError>;
}
```
---
## 10. Storage Engine
The **Storage Engine** is the underlying database kernel managing low-level table and index files on disk (or in-memory).
### Key Responsibilities
1. **Buffer Pool Manager**: Caches database pages (usually 4KB or 8KB frames) in memory, coordinating disk read/write calls and evicting pages using policies like Clock or LRU.
2. **Page & Index Layouts**: Handles the binary representation of heap pages, slotted page layouts for variable-length rows, and B+ Trees for secondary indexes.
3. **Write-Ahead Logging (WAL)**: Ensures transaction Durability (ACID) by logging transaction modifications to disk sequentially before dirty pages are flushed.
4. **Concurrency Control (MVCC)**: Implements Multi-Version Concurrency Control (or Locking protocols) to provide snapshot isolation and transactional consistency.
### Proposed Rust Interface
```rust
pub struct BufferPoolManager {
pub disk_manager: DiskManager,
pub pool: Vec<BufferFrame>,
}
impl BufferPoolManager {
pub fn fetch_page(&mut self, page_id: PageId) -> Result<&BufferFrame, StorageError> { ... }
pub fn flush_page(&mut self, page_id: PageId) -> Result<(), StorageError> { ... }
}
```