Course contents
On this page
Learning path: build a database engine
The concepts, prerequisites, and implementation milestones behind the course.
The destination is a small database engine whose behavior you can explain and test. Begin with one running program on one machine. Add storage, query execution, and transaction machinery before extending the design across machines.
The course outline supplies the reading order and Previous/Next navigation. This guide explains the dependencies and sources behind that order. It is our synthesis, not a university-endorsed curriculum.
What is ready to read
The new opening sequence teaches rows, keys, SQL reads and writes, joins, transaction boundaries, an in-memory scan, byte encoding, and saving a file. Three additional bridges introduce pages, the reason for a search tree, and the need for a consistent report. These pages use original examples and worked answers.
The ticket, index, and MVCC pilots link to those foundations. The remaining 45 chapters now also have focused core explanations, worked values, diagrams, and prediction answers. Each links to its original detailed chapter as an extended reference. You can follow the core sequence before exploring those specialist sections. Encountering an unexplained term is still a reason to improve the course, not evidence that you should already know it.
Follow the dependencies
- Describe the behavior
A product row → a query → a purchase that succeeds or fails together.
- Build the local mechanisms
A scan in memory → encoded records → file pages → buffered pages → indexed access → query execution.
- Keep the promises under failure
Interrupted writes → recovery → overlapping transactions → isolation and version visibility.
- Make the engine dependable
Failure tests, restore procedures, diagnostics, bounded resource use, and compatible upgrades. Replication comes after the local guarantees are clear.
Know what each stage should let you do
| Stage | A useful check before moving on | Implementation milestone |
|---|---|---|
| What a database promises | Predict a query result and explain a partially completed purchase | State the supported operations and constraints |
| A tiny engine in memory | Trace a present key and a missing key through a scan | Read records from an in-memory collection |
| Rows become bytes | Decode a record and detect a truncated one | Save and reopen a declared record format |
| Data exceeds memory | Explain the difference between a page and its frame | Load pages into a bounded buffer pool |
| Finding rows efficiently | Trace a boundary key and explain insertion costs | Implement and validate one index |
| Executing queries | Trace rows through a plan and explain its result | Execute a small, explicit SQL subset |
| Surviving interruption | State which acknowledged changes must survive | Recover under a documented failure model |
| Overlapping transactions | Explain an anomaly and the rule that prevents it | Check concurrent histories against the chosen isolation promise |
| Making the engine operable | Restore data and explain an observed bottleneck | Exercise recovery, limits, diagnostics, and compatibility |
| Engines across machines | Explain why a lost reply does not prove a failed request | Build a replicated component and test partial failures |
Implementation work happens locally, outside this reading site. Early Python traces make operations visible; they do not commit the eventual engine to Python. C++ is a direct route into CMU’s supplied projects, but requires preparation in ownership, memory, I/O, debugging, and synchronization. Choose that implementation route deliberately rather than treating those skills as “basic programming.”
Bridges into the three pilots
| Destination | Learn first | Question that motivates it |
|---|---|---|
| One ticket, two buyers | Reading and changing rows, then transactions | What if both requests act on the same earlier stock count? |
| B+ tree lookup | Pages and frames, then sorted search and insertion | How can a page guide a search without moving an entire sorted collection on every insert? |
| Versioned reads | Transactions, then two reads in one report | How can reads of committed values still produce an inconsistent report? |
Sources with different jobs
Roadmap.sh’s SQL map, PostgreSQL map, and Backend map help check coverage. Their full tool lists are not prerequisites for building our first engine. In particular, database administration and engine implementation have different learning goals.
| Material | Use it for |
|---|---|
| Harvard CS50 SQL | A first explanation of queries, relationships, schema design, and updates |
| MIT 6.006 notes, Spring 2020 | Selected data structures, searching, sorting, hashing, and cost analysis |
| Wisconsin OSTEP | Processes, memory, concurrency, files, and persistence, introduced when needed |
| Berkeley CS186 | Relational engine explanations and exercises; some course media may require university access |
| CMU 15-445, Spring 2026 | Storage, indexes, execution, transactions, and recovery; a principal implementation reference |
| MIT 6.5840, Spring 2026 | The later distributed-systems branch, after local systems and concurrency foundations |
| SQLite atomic commit and testing | Production examples of persistence assumptions, crash testing, and malformed-input testing |
| PostgreSQL administration and Google SRE workbook | What operators need from a reliable engine and service |
External courses are supporting materials, not a requirement to finish several university degrees before beginning. This site should provide the explanation needed for each core page. Link to the original materials for further study rather than copying their documents or publicizing university assignment solutions. CMU asks that its project solutions remain private.
How we will judge the explanations
A page should show the problem, work through actual values, explain the mechanism, then change one condition so you can predict the result. Diagrams should reveal structure or changing state. Necessary definitions belong before their first use; a glossary is a reference, not a substitute for teaching.
Later lessons should ask you to recall earlier ideas. For instance, learning about B+ tree splits should reuse your understanding of page capacity. The IES learning guide supports connecting concrete and abstract representations, combining graphics with explanations, worked examples, retrieval, and spaced review. Applying these ideas still requires feedback from a real reader.
A teaching engine and a production engine
Passing component exercises is evidence of learning. Production use needs evidence about the actual implementation, its supported platforms, and its stated failure assumptions.
That includes interrupted and failed I/O, exhausted memory, malformed files and queries, overlapping operations, repeatable recovery, verified restores, and storage-format upgrades. Compare supported query results with a reference engine while accounting for dialect differences and unspecified ordering. Measure performance with a named workload and correctness settings.
CMU’s concurrency assignment explicitly leaves persistent undo logs outside that project’s requirements. It is a useful reminder that a successful educational component is not a complete durability implementation. No lesson count or reading certificate can replace that engineering work.