SQL Query Engine

A from-scratch SQL query engine implemented in Python, featuring a hand-written recursive-descent parser, B+ Tree storage engine, rule-based query planner with index selection, and a volcano-model executor. Built to demonstrate deep understanding of database internals.

---

Architecture

SQL String
    │
    ▼
┌─────────────────────────────────────────────────────────────┐
│  Lexer  (src/lexer/lexer.py)                                │
│  Tokenizes SQL into a stream of typed tokens                │
└────────────────────────┬────────────────────────────────────┘
                         │ Token stream
                         ▼
┌─────────────────────────────────────────────────────────────┐
│  Parser  (src/parser/parser.py)                             │
│  Recursive-descent parser → Abstract Syntax Tree (AST)     │
│  Supports: SELECT, INSERT, UPDATE, DELETE, CREATE, DROP,    │
│            SHOW, EXPLAIN, CREATE INDEX                      │
└────────────────────────┬────────────────────────────────────┘
                         │ AST
                         ▼
┌─────────────────────────────────────────────────────────────┐
│  Planner  (src/planner/planner.py)                          │
│  Rule-based query optimizer                                 │
│  ├── Semantic analysis (table/column resolution)            │
│  ├── Index selection (B+ Tree index vs. full scan)          │
│  ├── Predicate pushdown                                     │
│  ├── Join algorithm selection (Hash Join vs. Nested Loop)   │
│  └── Physical plan tree construction                        │
└────────────────────────┬────────────────────────────────────┘
                         │ Physical Plan
                         ▼
┌─────────────────────────────────────────────────────────────┐
│  Executor  (src/executor/executor.py)                       │
│  Volcano/iterator model — pull-based execution              │
│  Operators: SeqScan, IndexScan, Filter, Project,            │
│             HashJoin, NestedLoopJoin, Sort, Limit,          │
│             Aggregate, Insert, Update, Delete               │
└────────────────────────┬────────────────────────────────────┘
                         │ QueryResult
                         ▼
┌─────────────────────────────────────────────────────────────┐
│  Storage  (src/storage/)                                    │
│  ├── B+ Tree  (btree.py)   — ordered index structure        │
│  └── Table    (table.py)   — heap + index management        │
└─────────────────────────────────────────────────────────────┘

---

Key Technical Concepts

B+ Tree Storage Engine

The storage layer is built on a B+ Tree (not a simple hash map), which is the same index structure used by PostgreSQL, MySQL InnoDB, and SQLite. Key properties:

• All key-value pairs are stored in leaf nodes only
• Internal nodes contain only routing keys for navigation
• Leaf nodes are linked in a chain for O(log n + k) range scans
• Supports point lookups, range scans, and ordered iteration
• Minimum degree t configurable (default t=3, giving nodes with 2–5 keys)

tree = BTree(t=4)
tree.insert(42, {"name": "Alice", "age": 30})
tree.search(42)           # O(log n) point lookup
tree.range_scan(10, 50)   # O(log n + k) range scan
tree.scan_all()           # O(n) full ordered scan

Query Planner & Optimizer

The planner applies rule-based optimizations before execution:

Rule	Description
Index Selection	Replaces SeqScan + Filter with IndexScan when a B+ Tree index exists on the filtered column
Predicate Pushdown	Moves filter predicates as close to the data source as possible
Join Algorithm Selection	Uses HashJoin for equi-joins (O(n+m)), falls back to NestedLoopJoin for non-equi joins
Cardinality Estimation	Estimates output row counts to guide operator selection

Volcano Execution Model

The executor implements the classic iterator/volcano model where each operator exposes a next() interface. Results flow upward through the operator tree on demand, enabling:

• Pipelining: rows flow through operators without full materialization
• Short-circuit evaluation: LIMIT stops execution early
• Composability: operators compose arbitrarily

---

Supported SQL

Data Definition Language (DDL)

-- Create a table with a primary key
CREATE TABLE employees (
    id   INT  PRIMARY KEY,
    name TEXT,
    dept TEXT,
    salary INT
);

-- Create a B+ Tree index on a column
CREATE INDEX idx_dept ON employees (dept);

-- Drop a table
DROP TABLE employees;
DROP TABLE IF EXISTS employees;

-- Inspect schema
SHOW TABLES;
SHOW COLUMNS FROM employees;

Data Manipulation Language (DML)

-- Insert single or multiple rows
INSERT INTO employees (id, name, dept, salary)
VALUES (1, 'Alice', 'Engineering', 120000);

INSERT INTO employees (id, name, dept, salary) VALUES
    (2, 'Bob',     'Marketing',   85000),
    (3, 'Charlie', 'Engineering', 135000);

-- Select with filtering, ordering, and limiting
SELECT name, salary
FROM employees
WHERE dept = 'Engineering'
  AND salary > 100000
ORDER BY salary DESC
LIMIT 5;

-- Aggregation with GROUP BY
SELECT dept, COUNT(*), AVG(salary), MAX(salary)
FROM employees
GROUP BY dept
HAVING AVG(salary) > 90000;

-- JOIN two tables
SELECT e.name, d.budget
FROM employees AS e
INNER JOIN departments AS d ON e.dept = d.name
WHERE e.salary > 100000;

-- Update rows
UPDATE employees SET salary = 130000 WHERE id = 1;

-- Delete rows
DELETE FROM employees WHERE dept = 'Marketing';

Supported Expressions

Category	Examples
Comparison	=, <>, !=, <, <=, >, >=
Logical	AND, OR, NOT
Arithmetic	+, -, *, /, %
Pattern matching	LIKE 'A%', NOT LIKE '%test%'
Range	BETWEEN 10 AND 20, NOT BETWEEN
Membership	IN (1, 2, 3), NOT IN (...)
Null checks	IS NULL, IS NOT NULL
Aggregates	COUNT(*), SUM(col), AVG(col), MIN(col), MAX(col)
Scalar functions	UPPER(), LOWER(), LENGTH(), ABS(), COALESCE(), CONCAT(), ROUND(), NOW()
Aliases	SELECT name AS full_name

EXPLAIN

Use EXPLAIN to inspect the physical query plan chosen by the planner:

EXPLAIN SELECT * FROM employees WHERE dept = 'Engineering';

Output (with index on dept):

Project(*)
  IndexScan(employees, dept='Engineering', est_rows=3)

Output (without index):

Project(*)
  Filter(predicate=(users.dept = 'Engineering'))
    SeqScan(employees, est_rows=8)

---

Getting Started

Prerequisites

• Python 3.10 or higher
• No external dependencies required for the core engine

Installation

git clone https://github.com/Nitaiz123/sql-query-engine.git
cd sql-query-engine
pip install -r requirements.txt   # only needed for tests

Interactive REPL

python3 cli.py

╔══════════════════════════════════════════════════════╗
║          SQL Query Engine  v1.0.0                    ║
║  B+ Tree Storage · Volcano Executor · Rule Planner   ║
║  Type .help for commands, .quit to exit              ║
╚══════════════════════════════════════════════════════╝

sql> CREATE TABLE users (id INT PRIMARY KEY, name TEXT, age INT);
Query OK, 0 row(s) affected
  (0.12 ms)

sql> INSERT INTO users (id, name, age) VALUES (1, 'Alice', 30), (2, 'Bob', 25);
Query OK, 2 row(s) affected
  (0.08 ms)

sql> SELECT * FROM users WHERE age > 20 ORDER BY name;
+----+-------+-----+
| id | name  | age |
+----+-------+-----+
| 1  | Alice | 30  |
| 2  | Bob   | 25  |
+----+-------+-----+
2 row(s) in set
  (0.31 ms)

Built-in Demo

python3 cli.py --demo

Programmatic Usage

from src.engine import Engine

engine = Engine()

# DDL
engine.execute("""
    CREATE TABLE products (
        id    INT  PRIMARY KEY,
        name  TEXT,
        price INT,
        stock INT
    )
""")
engine.execute("CREATE INDEX idx_price ON products (price)")

# DML
engine.execute("INSERT INTO products (id, name, price, stock) VALUES (1, 'Widget', 999, 50)")
engine.execute("INSERT INTO products (id, name, price, stock) VALUES (2, 'Gadget', 1499, 30)")

# Query
result = engine.execute("SELECT * FROM products WHERE price < 1200 ORDER BY price ASC")
print(result.pretty_print())

# Aggregation
result = engine.execute("SELECT COUNT(*), AVG(price) FROM products")
print(result.rows)  # [{'COUNT(*)': 2, 'AVG(price)': 1249.0}]

Running Tests

python3 -m pytest tests/ -v
python3 -m pytest tests/ -v --cov=src --cov-report=term-missing

---

Project Structure

sql-query-engine/
├── src/
│   ├── engine.py              # Top-level Engine class
│   ├── lexer/
│   │   └── lexer.py           # SQL tokenizer
│   ├── parser/
│   │   ├── ast.py             # AST node definitions
│   │   └── parser.py          # Recursive-descent parser
│   ├── planner/
│   │   └── planner.py         # Query planner & physical plan nodes
│   ├── executor/
│   │   └── executor.py        # Volcano-model executor
│   ├── storage/
│   │   ├── btree.py           # B+ Tree implementation
│   │   └── table.py           # Table heap + index management
│   └── catalog/
│       └── catalog.py         # Schema registry
├── tests/
│   └── test_engine.py         # 44 integration + unit tests
├── cli.py                     # Interactive REPL
├── requirements.txt
└── README.md

---

Performance Characteristics

Operation	Complexity	Notes
Point lookup (no index)	O(n)	Full table scan
Point lookup (with index)	O(log n)	B+ Tree traversal
Range scan (with index)	O(log n + k)	Leaf chain traversal
Insert	O(log n)	B+ Tree insert with splits
Hash Join	O(n + m)	Build + probe phase
Nested Loop Join	O(n × m)	Fallback for non-equi joins
Sort	O(n log n)	In-memory sort

---

License

MIT — see LICENSE