SQL Database Engine

Overview

A relational database engine written from scratch in Python: a hand-written SQL parser, a cost-based planner, B+tree storage on slotted 4KB pages, a write-ahead log with real crash recovery, and MVCC snapshot-isolation transactions. The core uses only the standard library.

Databases are the best systems-programming curriculum there is: parsing, query optimization, on-disk data structures, caching, logging protocols, and concurrency control, all forced to cooperate.

sqlmill owns each layer end to end, including the parts tutorials usually skip: crash recovery that survives a SIGKILL mid-page-write, and transaction semantics precise enough to state which anomalies are and are not possible.

Key features

• SQL: a hand-written lexer and recursive-descent parser covering DDL, indexes, INNER and LEFT joins, GROUP BY with aggregates and HAVING, transactions, EXPLAIN, and VACUUM. Syntax errors report line, column, and a caret under the offending token.
• Planner: predicate pushdown, index selection with a row-count cost model, left-deep join-order search, and a hash join vs nested loop choice.
• Storage: slotted heap pages, a from-scratch B+tree with variable-length keys and split, borrow, and merge rebalancing, an LRU buffer pool, and per-page CRC32 checksums.
• Durability: write-ahead logging with full-page after-images batched atomically per safe point, fsync on commit, checkpointing, and torn pages detected by checksum and repaired from the log.
• Transactions: MVCC snapshot isolation with first-committer-wins conflict detection and VACUUM garbage collection. Readers never block writers.

Verification

• 85 tests covering the parser, planner, B+tree property tests, buffer pool eviction, WAL recovery including torn pages, MVCC, and the differential suite.
• Crash campaign: 300 rounds passed (seed 2026, 105s); each round SIGKILLs a workload subprocess at a random moment, and 135 rounds also corrupted half of a written page before recovery. 8,504 committed transactions were verified durable; uncommitted work never survived.
• Differential suite: 300 seeded generated queries run against both sqlmill and stdlib sqlite3, compared modulo row order. 300 of 300 match.
• Benchmarks: about 1,000 inserts/s with an fsync per commit vs about 2,800/s with fsync off; indexed point lookups stay around 0.2 to 0.3 ms while full scans grow linearly, about 390x slower at 50k rows.

Tech stack

• Python 3.12
• Standard library only
• B+tree storage
• Write-ahead log
• MVCC
• pytest

Challenges

• Torn multi-page operations in the WAL: the first crash campaign failed around round 200 because page images were logged individually and a SIGKILL left exactly one of a heap-chain append's images in the replayable prefix. Logging the whole dirty set of each safe point as a single length-and-CRC-framed batch record fixed it.
• Unique indexes vs MVCC versions: an UPDATE that keeps the key creates a second version with the same key, so the RID is appended to every index key and UNIQUE is enforced logically at insert time.
• Rebalancing with variable-length keys: count-based split and merge rules break for keys from 9 to 400 bytes, so the tree uses serialized-size thresholds throughout.
• Negative integers broke the order-preserving key encoding on Python's arbitrary-precision ints, caught by a property test over the full 64-bit range.

What I learned

• Full-page-image redo plus MVCC-as-undo is a legitimately simple recovery scheme, but only if checkpoints quiesce transactions and rollback physically undoes before the durable horizon advances.
• Atomicity boundaries have to match at every layer; the batch-record bug was invisible to every deterministic test and appeared only under randomized SIGKILL timing.
• Appending the RID to secondary-index keys makes non-unique indexes, version chains, and range scans fall out of one unique-key B+tree.
• Build the crash harness first: it found the only serious correctness bug in the project within 200 rounds.