# 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>`.
---
## High-Level Architecture
```mermaid
flowchart TD
subgraph Frontend["Query Frontend (Implemented)"]
SQL["SQL Input String"] -->|Char Indices / Bytes| Lexer["Lexer (src/lexer)"]
Lexer -->|Token Stream + Spans| Parser["Parser (src/parser)"]
Parser -->|Pratt Parsing / Recursive Descent| AST["Abstract Syntax Tree (src/ast)"]
end
subgraph Intermediate["Query Compilation (Planned Roadmap)"]
AST -->|AST Nodes| Binder["Binder"]
Binder -->|Bound AST / Schema Resolved| Sem["Semantic Analyzer"]
Sem -->|Type-Checked & Validated AST| LP["Logical Planner"]
LP -->|Initial Logical Plan| Opt["Optimizer"]
Opt -->|Optimized Logical Plan| PP["Physical Planner"]
end
subgraph Backend["Query Execution & Storage (Planned Roadmap)"]
PP -->|Physical Plan| Exec["Executor"]
Exec -->|Get / Put Pages & Rows| Storage["Storage Engine"]
end
style Frontend fill:#d4edda,stroke:#28a745,stroke-width:2px;
style Intermediate fill:#fff3cd,stroke:#ffc107,stroke-width:2px;
style Backend fill:#f8d7da,stroke:#dc3545,stroke-width:2px;
```
### Query Execution Lifecycle
The system is designed around a classic 11-stage query compilation and execution pipeline:
| **1. SQL Input** | Input | Raw query string submitted by the user or client application. |
| **2. Lexer** | [`src/lexer/`](src/lexer/) (Implemented) | Zero-copy lexical analyzer. Splits input characters into distinct tokens with precise `Span` locations. |
| **3. Parser** | [`src/parser/`](src/parser/) (Implemented) | Hand-written recursive descent and Pratt parser. Converts tokens into structured syntax elements. |
| **4. AST** | [`src/ast/`](src/ast/) (Implemented) | Strongly-typed Abstract Syntax Tree representing the statements (DDL/DML/Queries) and expressions. |
| **5. Binder** | [`src/binder/`](src/binder/) (Implemented) | Resolves identifiers (tables, columns, views) against the catalog schema, matches functions, and produces a bound AST. |
| **6. Semantic Analyzer**| Planned | Validates semantic rules (e.g. correct usage of window and aggregate functions, type safety, user privileges). |
| **7. Logical Planner** | Planned | Translates the bound AST into a tree of relational algebra operators (e.g. Scan, Filter, Project, Join, Limit). |
| **8. Optimizer** | Planned | Rewrites logical plans using rule-based transformations (predicate pushdown) and cost-based plan searches. |
| **9. Physical Planner**| Planned | Translates the logical plan into a tree of concrete physical execution operators (e.g. HashJoin, IndexScan, SeqScan). |
| **10. Executor** | [`src/executor/`](src/executor/) (Implemented) | Receives bound statements and applies them to the catalog and storage. Currently executes database DDL statements. |
| **11. Storage Engine**| [`src/storage/`](src/storage/) (Implemented) | Manages on-disk layout, directories, and files. Currently supports directory creation and drop operations for databases and schemas. |
---
## 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> { ... }
}
```