Capstone: A Transactional, Multi-Table Engine

Building a Database Engine: Transactions & Concurrency

Chapter 10 · Capstone: A Transactional, Multi-Table Engine

Every chapter of this course built and verified one real piece in isolation: a write-ahead log, a recovery routine, undo-based rollback, locking, MVCC, foreign keys, two join algorithms, a cost-based planner. None of them were ever combined. This capstone wires as many of them together as genuinely can be combined into one real, disk-backed engine — and finds, as every capstone in this project's own "ambitious learning projects" tier has, that integration surfaces bugs no single chapter's own isolated tests could ever catch.

Step 1–3: Combining the WAL and Undo Logging for the First Time

Chapter 2's WAL and Chapter 4's undo log both wrap write_page() — but never once, anywhere in this course, on the same write. A DurableTransactionalHeapFile does both: logs the new page to the WAL (durability), records the old page in the undo log (atomicity), then applies the write.

Verified directly — a rolled-back write comes back from the dead

A row is written, then a business-logic failure (not a crash) triggers rollback() — the row is correctly, genuinely gone from the real data file. Then, simulating an unrelated later crash, recover() is run. It resurrects the rolled-back row — the WAL still had a record of the original write, and recovery, having no idea it was ever undone, faithfully redoes it. Two mechanisms, each independently correct, produce a genuinely wrong combined result the moment they're used together.

The fix — rollback logs a compensating record too

rollback() now appends the restored page content to the WAL as a new record, with a fresh LSN, instead of only updating the real file in place. Recovery, replaying the whole log in order — the original write, then the compensation — now lands on the same, correct, post-rollback state every time, crash or no crash. This is exactly ARIES's own compensation log record technique, arrived at independently by actually trying to combine two chapters that were each correct on their own.

Step 4: A Real Catalog, Durable and Rollback-Safe

Chapter 7's Catalog never used the WAL at all — it wrote straight to a plain HeapFile. Rebuilding it on top of the fixed, combined write path gives foreign keys real crash durability for the first time.

A genuine, deliberate demonstration — rollback undoes the WHOLE transaction, never just one statement

Two logically independent orders, sharing one transaction: the first is genuinely valid; the second violates a foreign key. Rolling back after the second one fails undoes both — including the first, perfectly valid order. This engine only supports transaction-level rollback, never statement-level rollback. Giving the two orders their own separate transactions resolves it correctly: the valid one commits and survives, the invalid one is rejected and rolled back alone.

Step 5: Real Concurrent Transactions, Protected by Locking

Verified directly — two real threads, one correct final answer

Two real threads concurrently buy the same product, starting from 100 in stock — 30 and 40 units respectively — each holding Chapter 5's own exclusive lock across its entire read-modify-write cycle. Final stock: exactly 30 (100 − 30 − 40). The identical lock manager, wired into the real, disk-backed catalog for the first time.

Step 6–7: A Crash-and-Recover Cycle, and a Second Real Bug

Simulating the exact WAL-only crash from Chapter 2's own Finding 1 — log the write, never apply it — at the Catalog level, across three real tables sharing one WAL.

Verified directly — a shared WAL corrupts data across tables

Recovery restores the missing order correctly — but the recovered orders table also shows garbage rows (implausible ids, enormous customer_id values), and Alice's own real order has vanished entirely. Root cause: customers, products, and orders all shared one WAL, and WAL records only ever store a bare page_num — with three separate heap files sharing one log, page_num=0 for orders and page_num=0 for products are genuinely ambiguous. Recovery replayed every record from every table onto the orders file alone, misinterpreting product and customer bytes as order rows.

The fix — one WAL per table, exactly matching Chapters 2–3's own established pairing

Every table gets its own dedicated WAL file, never a shared one. Recovering orders' own WAL now only ever touches orders' own real records — Alice's order survives untouched, the crashed order is correctly restored, and no other table is ever at risk of corruption from another one's recovery.

Step 8: A Real Multi-Table Query, Planned Automatically

Verified directly — a real query spanning three tables, two foreign keys, and a recovered row

customers joined to orders (planner correctly chose nested_loop for this size), then matched against products — producing a complete, correct report, including the order that was recovered from the simulated crash in Step 7. Every piece — the catalog, the FK constraints, the planner's own cost formula, the join algorithm — working together for the first time.

Step 9: An Honest Closing Note — MVCC Was Never Integrated

Verified directly — a real, committed MVCC transaction leaves zero bytes on disk

A row is written and committed through MVCCStore, exactly as verified working in Chapter 6. Checking its own dedicated directory afterward: no files at all. Not a HeapFile, not a WAL — nothing. A real process restart would lose every row MVCC has ever held, in complete contrast to the WAL-backed catalog just verified surviving a real crash in Steps 6–7. Chapter 6 built and independently verified a genuine, working alternative to locking for isolation — but this course never connected it to the durable storage stack Chapters 1–4 spent so much effort building. Combining row-versioned MVCC with real, persistent storage is a substantial engineering project of its own — an honest, deliberate scope boundary to close this entire project on, not a gap to quietly paper over.

Chapter Attribution

Capstone step	Built in
Records, pages, heap files, B-tree indexes	Storage & Query Fundamentals Chapters 2–6 (Course 1)
Write-ahead logging	Chapter 2 (this course)
Crash recovery / replay	Chapter 3 (this course)
Undo logging & rollback	Chapter 4 (this course)
Locking (shared/exclusive)	Chapter 5 (this course)
MVCC (verified independently, never integrated)	Chapter 6 (this course)
Catalog, foreign keys	Chapter 7 (this course)
Nested-loop & hash join	Chapter 8 (this course)
Cost-based query planner	Chapter 9 (this course)

What This Project Doesn't Cover

No client-server networking protocol — everything runs as a local, in-process library (stated in Storage & Query Fundamentals Chapter 1, held throughout both courses)
No full SQL — a genuine but deliberately small subset (CREATE TABLE/INSERT/SELECT/WHERE, no UPDATE/DELETE at the SQL layer)
No distributed or replicated storage
No predicate pushdown — the planner never filters one side of a join down before joining (Chapter 9's own honest limitation)
No B-tree range scans — only exact-match lookups can use an index (a real limitation traced to btree_search()'s own single-key design)
No MVCC-backed durable storage — a genuine, working alternative concurrency strategy that was never connected to the disk-backed engine (this chapter's own closing finding)
No statement-level rollback — only whole-transaction rollback (demonstrated directly in Step 4)
No garbage collection for old MVCC versions, no vacuum, no free-page reclamation after a rollback-blanked page

Hands-On Exercises

Exercise 1

Simulate a crash affecting two different tables at the same moment — one logged-but-unapplied write to customers, one to products — using the fixed, per-table-WAL catalog. Recover each table from its own WAL and confirm neither table's own recovery affects the other's data at all.

📄 View solution

Exercise 2

Re-run Step 5's own concurrent purchase test, but with the LockManager removed entirely. Confirm the outcome is genuinely wrong — either a silently incorrect final stock count, or an outright crash from two threads racing on the same shared file handle — and explain both possible failure modes.

📄 View solution

Exercise 3

Commit a row through a real MVCCStore, then simulate a process restart by creating a brand-new MVCCStore object. Confirm the committed row is completely gone, and contrast this directly against the disk-backed catalog's own real recovery in Steps 6–7.

📄 View solution

Capstone Quick Reference

Bug 1 found: rollback without a compensating WAL record lets a later crash-recovery resurrect a deliberately undone write — fixed by logging the restored page as a new WAL record
Bug 2 found: a single shared WAL across multiple tables corrupts data during recovery, since page_num alone is ambiguous — fixed with one WAL per table
Genuine scope demonstration: rollback always undoes the whole transaction, never a single failed statement
Verified end to end: real concurrent locking, a real crash-and-recover cycle, and a real multi-table join, all through one integrated system
Honest closing finding: MVCC (Chapter 6) was built and verified as a genuine alternative to locking, but was never connected to durable, disk-backed storage — a real, deliberate scope boundary, not a gap to hide
The project: 20 chapters across two courses — Storage & Query Fundamentals and Transactions & Concurrency — building a real database engine from raw bytes to a working, multi-table, transactional, concurrent, query-planned system