Build a working SQL database engine in C++20 -- from an empty directory to
a query processor that runs real SQL against data on disk and survives a
crash at any write -- through a single relentless method: nothing is
asserted; everything is demonstrated.
Every data structure in this book is built, compiled, and run. Every
performance claim is a table printed by a benchmark whose source code is on
the page in front of you. Every design decision is followed by the
measurement that justifies it -- and, where the design has a cost, by the
measurement that exposes that cost too. And once per unit, something fails
in front of you: a real bug, reproduced deterministically, diagnosed from
the evidence, fixed, and locked shut with a regression test.
This is not a survey of database theory. It is a lab manual. You will not
find hand-waving about how B+Trees are "generally logarithmic" -- you will
find the fan-out arithmetic, the page-count math, and a benchmark that
walks a tree of a million keys and prints the real number.
THE COMPLETE BOOK: fourteen units in four parts.
PART I -- STORAGE
1. Slotted Pages & the Pager -- self-describing 4 KiB pages, records with
stable slot ids, a pager with a free list
2. B+Tree: Insert & Search -- logarithmic lookup, proven against a
million-key tree
3. B+Tree: Delete & Range Scans -- rebalancing, merges, ordered range
queries
4. The Buffer Pool -- a real cache with clock eviction, measured 2.5x
faster with identical logical work
PART II -- FROM BYTES TO A QUERY
5. The Record Layer -- typed rows: a schema-aware codec and a table heap,
reached by key through the index
6. The Catalog -- persistent schemas and named tables: the engine's
self-knowledge
7. The Front End -- a SQL tokenizer and recursive-descent parser, with
compiler-quality caret-pointed errors
8. The Executor -- the milestone: a real executor that runs CREATE TABLE,
INSERT, and SELECT end to end, against a database of hundreds of
thousands of rows
PART III -- MAKING IT FAST & REAL
9. Joins -- the executor rebuilt as a pipeline of operators, JOIN ... ON
with aliases and qualified columns, and two join algorithms raced:
at 100,000 rows a side the hash join is 1,293x faster than the
nested loop, measured
10. Aggregation -- COUNT, SUM, AVG, MIN and MAX with SQL's NULL rules,
GROUP BY and HAVING through a hash table, ORDER BY and LIMIT; the
top 10 of a million rows costs one pass over them, and a GROUP BY's
cost per row, measured, grows tenfold from 10 groups to a million
11. Indexes & the Planner -- ranges of the key, CREATE INDEX on a B+Tree
that keeps duplicate keys, and a planner that chooses scans, indexes
and join algorithms by costs measured on its own machine; an index
loses, measured, past 55% of a cached table and 16% of one that is
not, and Unit 10's questions, replanned, run up to 12,000x faster
12. Vectorized Execution -- rows read where they lie in the buffer pool,
and every operator rebuilt to move them 1,024 at a time as columns: a
scanned row, measured, from 116 ns to 11, Unit 9's pipeline twelve
times faster, and an index's break-even moved from half a table to a
sixth
PART IV -- DURABILITY & CAPSTONE
13. Write-Ahead Log & Crash Recovery -- every page through a log of
checksummed page images, every statement a transaction, BEGIN, COMMIT
and ROLLBACK; the engine crashed at each of the 804 writes and syncs
of a workload, as a dying process and as a power cut, and by 300
kill -9s -- and every time it held exactly what it had acknowledged
14. Capstone -- the engine becomes a program; 20,000 generated statements
run in labdb and in PostgreSQL with not one different answer, and
eight bugs planted to test that comparison, all eight caught; then the
same work beside SQLite, in one process: faster on ten of thirteen
questions, and a file nearly three times the size, explained page by page
By the last page, the engine answers SQL it parsed from text, against rows
it stored on disk, through indexes it built, a cache it manages and a log
that brings it back after a crash -- and its answers are PostgreSQL's. Every
number in the book came from actually running that code.
Reference machines: g++ 13.3.0, Ubuntu 24.04, C++20, stdlib + POSIX only
(Unit 14 also uses PostgreSQL and SQLite, when installed, as the references
it compares against). Every benchmark ships with the exact command that
produced it, so you can run it yourself and get the same structural numbers.
Concurrency and MVCC are not in this book -- labdb is single-threaded by
design, and the book says so plainly rather than promising a chapter it has
no intention of writing in a hurry.
Development Methodology
This book was created through a process that combines careful human planning, content direction, and advanced AI technology, followed by thorough refinement and review to ensure a high-quality final work.
Source Code:
https://github.com/Hatem-M-lab/labdb
