MiniDB

THE PROBLEM

Understand how a relational database really works by building the whole stack: storage, indexing, SQL, query optimization, concurrency control and recovery from crashes.

HOW IT WORKS

• Storage: slotted-page heap files, a disk-backed B+ tree (split, merge, borrow, bulk load) and an LRU-K buffer pool.
• Query path: SQL is parsed with sql-parser-cst, then goes through my own binder, a cost-based planner (ANALYZE statistics, EXPLAIN) and Volcano-style plus vectorized executors.
• Transactions: strict two-phase locking with a wait-for-graph deadlock detector, and write-ahead logging with ARIES-style analysis, redo and undo recovery plus checkpoints.

THE PIPELINE

ENGINEERING EVIDENCE

• 133 tests in 26 suites pass. They include a crash matrix that simulates failures between a WAL flush and a page flush, a 1,000-operation SQL fuzz test against a reference model, and deadlock tests. crash_matrix.test.ts ↗
• A 683-line disk-backed B+ tree with split, merge, borrow and bulk-load, and its root persisted through the catalog. BPlusTree.ts ↗
• The buffer pool flushes the log up to a page's LSN before writing the page (write-ahead logging), and recovery runs analysis, redo and undo passes. CrashRecovery.ts ↗
• Lock manager with shared and exclusive modes, FIFO queues and upgrades. The deadlock detector aborts the youngest transaction in a cycle. LockManager.ts ↗
• Benchmarks are scripts, not screenshots. The vectorized executor reached about 1.2 to 2.2× over the Volcano one, not the 10× I aimed for, and the benchmark doc explains why. BENCHMARKS.md ↗

DECISIONS & INVESTIGATIONS

• Vectorized executor missed its 5-10x goal: measured about 1.0-2.3xINCONCLUSIVE

  Six runs of the documented script gave about 1.5-2.3x at 10k rows, 1.1-1.4x at 50k and 1.0-1.3x at 100k, so the gap is small and noisy; the documented 1.19x at 100k is inside that range.

• ARIES-style recovery without CLRs, with LSN equal to the byte offset in the WALPARTIAL

  benchmarks/crash_recovery.ts (10,000 committed inserts, 500 uncommitted deletes, crash, recover twice) ends with 10,000 rows, and three crash-matrix tests plus two CrashRecovery unit tests pass.

• Crash with 10,000 committed inserts and 500 uncommitted deletes recovers to exactly 10,000 rowsADOPTED

  The benchmark printed 'Expected Rows: 10000 | Actual Rows: 10000' after two recoveries, as documented.

• BufferPool flushes the log up to a page's pageLSN before writing that dirty page (steal / no-force)ADOPTED

  A test ('enforces WAL rule on eviction') sets pageLsn 42 on a dirty page, evicts it, and asserts the log manager was flushed to 42.

• Row-level strict 2PL with a wait-for-graph detector that aborts the youngest transactionADOPTED

  Unit tests cover 2- and 3-transaction cycles and assert the youngest is aborted; an integration test asserts t2 (the younger) is the victim.

NEXT STEPS

Each one comes from a gap listed above. It says what fixing the gap would take; it is not a promise.

• Make aborting a transaction undo its changes.
• Fix recovery so a second crash straight after recovery does not lose committed rows.
• Stop the planner choosing an index for range predicates the index scan cannot run.
• Put the catalog file under the write-ahead log.

STACK

• TypeScript
• Node.js
• Jest
• sql-parser-cst