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 -- 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.
This book takes the engine across two complete parts and eight units:
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
By the last page, the engine answers a SQL query it parsed from text,
against rows it stored on disk, through an index it built and a cache it
manages itself -- and every number in the book came from actually running
that code.
Reference machine: g++ 13.3.0, Ubuntu 24.04, C++20, stdlib + POSIX only.
Every benchmark ships with the exact command that produced it, so you can
run it yourself and get the same structural numbers.
A companion volume, "Build a SQL Database Engine in C++, Book 2: Parts III
& IV," continues the engine into durability (crash recovery via a
write-ahead log), concurrency, and performance -- available separately, and
as a discounted bundle with this book.
