Course 1 ended with a real, working single-table engine: records, pages, a heap table, B-tree indexes, and a small SQL-like query language, all genuinely wired together and verified end to end in its own capstone. What it never once claimed, anywhere, is that any of it survives going wrong partway through. This chapter doesn't add a single line of new engine code — it goes back to Course 1's own finished code and asks it two direct, uncomfortable questions, verifying the answers with real Python rather than assuming them.

ACID, Stated Concretely

Four properties a database is expected to guarantee around any single operation (or group of operations run together as one unit, a transaction):

Course 1's own capstone chapter closed with an honest "What This Course Doesn't Cover" section naming exactly this gap — it just never demonstrated what specifically goes wrong without it. That's this chapter's job.

Finding 1: A Real, Verified Consistency Failure

Course 1's own Database.insert() is a genuine two-step operation: write the row to the heap table, then update every index registered for that table.

Nothing in Course 1 guarantees these two steps happen together. To verify what a real interruption between them actually looks like, this test skips Database.insert() entirely for one row and calls the heap table's own insert() directly — exactly what a process crash between step 1 and step 2 would leave behind.

This isn't a hypothetical worst case dreamed up for the sake of a scary example — it's the exact, ordinary shape every real insert already takes. Any interruption at all between its two steps — a crash, a killed process, even an unhandled exception raised partway through the index-update loop — leaves the database in exactly this state.

Finding 2: The Index Itself Never Touches Disk

A more basic question: does a B-tree index even survive an ordinary, controlled restart — closing the Python process and opening a fresh one pointed at the same files, the way any real application actually re-opens a database?

A query for WHERE id = 1 against db_b still returns the right answer here — but only because Chapter 9's own choose_plan() correctly sees no index registered for that column and safely falls back to a full scan. This particular case is a silent performance loss, not a correctness bug: every index would need to be rebuilt from scratch, by hand, after every single restart, or a real application simply never gets the benefit Course 1's own Chapter 9 built it for in the first place.

Separately, real database durability has a second, deeper layer worth naming honestly even without simulating it directly: Course 1's own HeapFile.write_page() calls self.file.flush() after every write, but never os.fsync(). This is a well-established, uncontroversial fact about how operating systems work, not something that needs a live crash to demonstrate — flush() only pushes data out of Python's own internal buffer and into the operating system's page cache; the OS itself is still free to hold that data in memory for a while before actually committing it to the physical disk. A real power loss between those two points loses data Python already reported as "written." Chapter 2 builds the real mechanism — write-ahead logging — that closes this exact gap.

What Actually Happened, Underneath Both Findings

Both findings trace back to the same root cause: Course 1 built real mechanisms — pages, a heap file, a B-tree, a query planner — but never built any protocol governing what happens when something interrupts a sequence of steps partway through. That protocol is precisely what this course exists to build:

Where This Connects

Hands-On Exercises

Chapter 1 named the gap without closing it: write_page() calls flush() but never os.fsync(), and even if it did, a crash between logging intent and applying it could still leave a table's own pages and indexes disagreeing. A write-ahead log is the real, standard mechanism that turns "I hope this happened" into something verifiable — write down exactly what's about to change, force it to disk, and only then touch the actual data. If a crash happens after the log write, the record survives. If it happens before, nothing was promised yet. There's no third case.

A Real WAL Record Format

Each record is length-prefixed and checksummed, so a reader never has to guess where one record ends and the next begins, or trust bytes it can't verify:

The LSN (log sequence number) is a strictly increasing integer identifying each record — Chapter 3's own recovery routine will need it to know exactly where it left off. This chapter logs the entire new page image, not a small delta — deliberately simple, and it buys something important later: reapplying an already-applied record is harmless, since writing the same complete page twice produces the identical result either time (this matters directly for Exercise 1, below).

The One Non-Negotiable fsync in This Engine

Finding 1: A Logged-but-Unapplied Change Survives a Simulated Crash

A "crash" is simulated the same honest way Chapter 1 did it: call wal.append() directly and never call heap_file.write_page() at all — exactly what a process death immediately after the WAL's own fsync() returns, but before the data write runs, actually looks like.

That distinction — the update didn't happen, but nothing about it was forgotten — is the entire point of this chapter, and precisely what Chapter 3's own recovery routine will use.

Finding 2: A Torn Trailing Record — Two Very Different Failure Modes

A real crash can interrupt the WAL's own append in the middle, too — the OS commits some of a record's bytes but not all of them before the process dies. This test builds one complete record, then writes only the first half of a second record's real bytes, simulating exactly that.

Finding 2b: Why Bounds-Checking Alone Isn't Enough

A truncated file is one kind of corruption. A single flipped bit somewhere inside an otherwise complete, correctly-sized record is another — and a length check alone has nothing to say about it.

Where This Connects

Hands-On Exercises

Chapter 2 built a log that survives a crash. It never actually used that log for anything — the whole point of Chapter 2's own Finding 1 was that the data file stayed wrong even though the WAL was perfectly intact. This chapter closes that loop: read every record the log can prove is real, and reapply it to the data file, on startup, before anything else runs.

The Real Recovery Routine

That's the whole mechanism. It has no idea which of these records were already applied before the crash and which weren't — and, as the next finding shows, it doesn't need to.

Finding 1: A Crashed Write, Actually Restored

Chapter 2's own Finding 1 logged an update, simulated a crash before it was applied, and confirmed the data file stayed untouched while the WAL held a complete, correct record of what was meant to happen. Running recover() against that exact same scenario closes the gap.

Finding 2: Replaying an Already-Applied Record Is Safe

A real crash rarely interrupts a single write in isolation — by the time it happens, some earlier writes in the log have usually already made it all the way to the data file. Chapter 2's own Exercise 1 built exactly this scenario: one page fully written and applied, a second page logged but never applied, both sitting in the same WAL.

Finding 3: Truncating the Log Too Early Can Lose Data Forever

A WAL that's never cleared grows without bound — the obvious next step is to truncate it once recovery has replayed everything, reclaiming the space. The obvious place to put that truncation call is at the start of recovery, right after reading the records out: it feels safe, since the records are already sitting in a local Python list by then.

This looks completely reasonable — the records are already read into memory, so what could truncating the file underneath them possibly break? The test: log three writes, apply none of them, then simulate a second crash during recovery itself — right after the first record has been applied, before the other two.

The Fix: Truncate Last, Only Once Everything Is Confirmed Durable

Finding 2 and Finding 3 depend on each other directly: it's only because replaying an already-applied record is provably safe that "just keep the log around and re-run recovery in full after any interruption" is a correct strategy at all, rather than something that risks corrupting already-correct pages.

Where This Connects

Hands-On Exercises

This course opened with a real, verified bug: a two-step insert — write the row, then update the index — that leaves the table and its own index silently disagreeing if anything interrupts it between the two steps. Chapters 2 and 3 closed the durability half of that story: a crash before a write is applied is now recoverable. But Chapter 1's own original scenario wasn't a crash — it was one step succeeding and the next one failing outright. This chapter closes that half: wrap the whole operation in a transaction, and if any part of it fails, undo everything that already happened.

A Real Undo Log

Where Chapter 2's WAL recorded each page's new content, an undo log records each page's old content — captured the first time, and only the first time, a transaction touches it:

Making the write side of every table transparently participate needs no changes at all to Course 1's own HeapTable — only a thin wrapper implementing the exact same interface, so HeapTable genuinely has no idea it's being run inside a transaction:

Finding 1: Commit Keeps Changes, Rollback Fully Undoes Them

Finding 2: First-Touch Capture Restores the TRUE Original, Not an Intermediate State

A single transaction writes to the same page twice — once with content V1, then again with different content V2.

Finding 3: The Payoff — Genuinely Resolving Chapter 1's Own Bug

Chapter 1's own opening scenario, unmodified: insert a row, then update an index for it. This time, both steps run inside a transaction, and the index update is made to fail on purpose.

Finding 4: Why a Non-Deduped Undo Log Must Replay in Reverse

This chapter's own Transaction class sidesteps a subtle ordering problem entirely, by construction, since it never keeps more than one undo record per page. A log that captures every write — not just the first one per page — doesn't get that guarantee for free.

Where This Connects

Hands-On Exercises

Every chapter so far has run one operation at a time, alone, then checked what a crash or a failure would have done to it. Isolation is a genuinely different question: what happens when two operations run at the same time, for real? This chapter uses real Python threads — not a simulation of concurrency, actual concurrent execution — to reproduce a genuine race condition, fix it with real locks, and then reproduce a genuine deadlock.

A Real Lock Manager: Shared and Exclusive

Shared locks (for reads) can be held by multiple transactions on the same page at once. An exclusive lock (for writes) needs the page completely to itself — no other shared or exclusive holder at all.

Finding 1: A Real, Reproducible Lost Update

Five real threads, each incrementing one shared counter twenty times — read the current value, sleep briefly (to force a genuine interleaving window), write back value + 1. No locking at all.

Finding 2: The Same Test, Correct Every Time With a Real Lock

Finding 3: Shared Locks Overlap, Exclusive Locks Serialize

Four threads each hold a lock on the same page for a fixed 0.15-second duration — once with a shared lock, once with an exclusive lock — measuring real wall-clock time for all four to finish.

Finding 4: A Real, Reproducible Deadlock

Two transactions, each locking one page first, then trying to lock the other's page — the classic circular-wait shape. Transaction A locks page 1, then tries for page 2. Transaction B locks page 2, then tries for page 1.

Finding 5: Wait-for-Graph Detection Catches the Cycle Immediately

A deadlock detector doesn't need to wait for anything to time out — it needs to notice, at the moment a transaction is about to wait, that doing so would close a cycle: "I'm about to wait for you, and you're already waiting for me."

Where This Connects

Hands-On Exercises

Chapter 5 solved isolation with locking: a reader and a writer touching the same page genuinely have to wait for each other. MVCC — multi-version concurrency control — solves the same problem a completely different way: instead of one mutable value per row that everyone fights over, keep every version a row has ever had, tagged with when it was created and when it stopped being current. A reader just picks the version that was current as of the moment its own transaction began, and never has to wait for anyone.

A Real Version Chain, Not One Mutable Value

Reading a row means finding the newest version whose created_ts is at or before the reader's own snapshot, and which hadn't yet been superseded (deleted_ts) as of that same snapshot. Writing never touches an existing version at all — it stages a brand-new one, invisible to everyone else until commit.

A Real Bug Found Building the Very First Test: the Snapshot Boundary

The first, most natural way to compute a transaction's own snapshot at begin() looks completely reasonable: self.txn_snapshot[txn_id] = self._next_ts — "whatever the counter currently reads." It's wrong.

Finding 1: A Stable Snapshot, Verified Against a Real Concurrent Commit

Finding 2: Read-Your-Own-Writes

Finding 3: Real Threads — Neither Side Ever Waits

A long-running reader holds a transaction open for 0.15s, reading the same row twice. A separate thread commits a new value to that row partway through.

Finding 4: An Honest Limitation — Version History Grows Forever

Finding 5: MVCC Alone Doesn't Prevent a Lost Update

Two transactions both begin from the same snapshot, both read 100, one computes +10 and the other computes +20, and both commit.

Where This Connects

Hands-On Exercises

Course 1's own Database class could already hold more than one table — that was never the missing piece. What's missing is any guarantee about how those tables relate to each other: nothing stops an orders row from pointing at a customer_id that doesn't exist anywhere in customers. This chapter builds a real foreign key constraint — checked on every insert, using the exact same B-tree index machinery Course 1 already built for a completely different reason.

A Real Catalog, and a Real Constraint

Finding 1: A Real Foreign Key, Verified Both Ways

Finding 2: Reusing Course 1's Own Index Makes This Fast

Checking whether a value exists in another table means either scanning it in full, or — if an index already exists on the referenced column — a real btree_search() call.

Finding 3: A Real Bug — Referencing a Table That Doesn't Exist Yet

The first, most natural version of create_table() just stores whatever foreign keys it's given, with no check that the referenced table actually exists.

Finding 4: A Real, Working Multi-Table System

A Genuine Structural Discovery: Self-Reference Under Check-Before-Insert

Building an exercise around a self-referencing table (an employees row whose own manager_id points at another row in the same table) surfaced something worth explaining honestly rather than working around quietly.

Reordering to insert first and validate second — physically writing the row, then checking, then rolling it back if invalid — resolves this cleanly, reusing Chapter 4's own real Transaction and TransactionalHeapFile completely unmodified:

Where This Connects

Hands-On Exercises

Chapter 7's own capstone joined customers to orders by hand — build a Python dict once, look each order up in it. That was already a hash join, just not named as one. This chapter builds two real join algorithms properly, verifies they agree with each other exactly, measures a real speed difference at scale, and finds a genuine correctness bug hiding in the "obvious" way to build a hash table.

Two Real Join Algorithms

Finding 1: The Two Algorithms Agree Exactly

Finding 2: A Real, Measured 44× Speedup

Finding 3: A Real, Silent Correctness Bug — Building on the Wrong Side

customers.id is unique — one row per id. orders.customer_id is not — Alice alone has two orders sharing the same key. The most natural first version of a hash join's own build step just assigns a key to a row, without thinking about what happens if that key shows up twice:

The fix is the same one shown in this chapter's own hash_join from the start: hash_table.setdefault(key, []).append(row) instead of a bare assignment. Every key maps to a list of rows, so a collision means "append," never "overwrite."

Finding 4: Once Fixed, Either Side Is Safe to Build On

Where This Connects

Hands-On Exercises

Every chapter so far has left a choice to the caller: use an index or scan (Course 1, Chapter 9), nested-loop or hash join (Chapter 8, this course). A real planner makes that choice automatically, from real, measurable properties of the data — and, as this chapter finds out the hard way, the obvious way to estimate "which is cheaper" doesn't actually match reality until it's calibrated against real measurements.

The Obvious Cost Formula

This predicts hash join wins as soon as n=m=3 (9 > 6). Real measurement says otherwise.

Finding 1: The Naive Formula Is Wrong at Small Scale

The reason: constructing a Python dict, hashing keys into it, and looking them up all carry real, non-trivial constant overhead the pure "count the operations" formula never accounts for. A handful of plain comparisons can genuinely be cheaper than building a hash table at all.

Finding 2: A Corrected, Empirically-Calibrated Formula

Finding 3: A Unified Planner, Measured Against a Naive Baseline

Combining Course 1's own index-vs-scan choice with this chapter's corrected join-strategy choice into one planner, and running it against a baseline that always scans and always uses nested-loop — on 1,500 customers and 3,000 orders.

An Honest Limitation: No Predicate Pushdown

"Find customer 42's own orders" can be answered two ways: join everything, then filter for customer 42 — or filter customers down to just that one row first, then join only that row against orders.

Where This Connects

Hands-On Exercises

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.

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.

Step 5: Real Concurrent Transactions, Protected by Locking

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.

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

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

Chapter Attribution

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