Database Internals: Indexes, Transactions and Query Plans
Look inside a database: how pages, B-trees and LSM trees store data, how the planner uses indexes, and how MVCC, locks and the write-ahead log keep transactions correct.
Advanced · Computer Science · about 18 hours · 5 modules · certificate on completion
Taught by Ngo Thi Huừngé, Konstantinì Papadopouloùs, AI Learning Companions.
About this course
A database is a carefully engineered program, and knowing how it works is what lets you design schemas and indexes that stay fast, read a query plan with confidence, and choose the isolation level your code really needs. This advanced course opens one up. You'll see how data is laid out in pages and slotted records and cached in the buffer pool, and how B+trees and log-structured merge trees trade read speed against write speed. You'll design composite, covering, partial and expression indexes, learn how a cost-based planner chooses between scans and joins, and read EXPLAIN output in SQLite and PostgreSQL. Then you'll study transactions: the anomalies weak isolation allows, how real databases implement isolation levels, MVCC, locks and deadlocks, and the write-ahead log that makes commits durable and recovery possible.
The labs run on your laptop with Python and SQLite: you'll parse an SQLite file's pages byte by byte, build an LSM tree with Bloom filters and compaction, fix slow queries by reading their plans, simulate MVCC to watch snapshot isolation allow write skew, and build a write-ahead log that survives torn writes. Walkthroughs in psql show the same ideas in PostgreSQL: ctids and pages, EXPLAIN (ANALYZE, BUFFERS), isolation levels in two sessions, row locks and a deadlock. The capstone has you diagnose and tune a slow help-desk database and fix a race in its code. The course goes deeper than SQL for Data Analysis with DataGrip, which teaches querying, and pairs with Distributed Systems: Replication, Consensus and Consistency, which covers what happens across many database nodes.
What you'll learn
- Explain how pages, slotted records, heap files and buffer pools store and cache data
- Compare B+trees and LSM trees, and build an LSM tree with Bloom filters and compaction
- Design composite, covering, partial and expression indexes for real queries
- Read EXPLAIN and EXPLAIN ANALYZE plans in SQLite and PostgreSQL, and fix slow queries
- Predict the anomalies each isolation level allows, and explain MVCC, locks and deadlocks
- Explain write-ahead logging and crash recovery, and build a log that survives torn writes
Skills you'll gain
Storage engines, B-trees and LSM trees, Index design, Query planning, EXPLAIN ANALYZE, Transaction isolation, MVCC, Locking and deadlocks, Write-ahead logging, Crash recovery
Tools
SQLite, PostgreSQL, psql, Python, pytest, Docker
Before you start
SQL for Data Analysis with DataGrip, or confident SQL (joins, GROUP BY, subqueries), and confident Python; System Design Fundamentals: Scale, Caching and Load Balancing helps. Install Python 3.10 or newer with pytest; the SQLite labs use Python's own sqlite3 (SQLite 3.36 or newer for the plan wording shown). For the PostgreSQL walkthroughs, install Docker or PostgreSQL 16.
Modules
Storage: pages, records and files
See how a database lays data out on disk: fixed-size pages, slotted pages that hold records, heap files and clustered tables, and the buffer pool that caches pages in memory. Then open an SQLite file and read its pages yourself.
- Pages and the buffer pool (12 min)
- Slotted pages, heap files and clustered tables (13 min)
- Inside an SQLite file (12 min)
- Hands-on lab: Read the pages of an SQLite database
B-trees, LSM trees and other index structures
Compare the structures storage engines are built on: B+trees that update pages in place, log-structured merge trees that buffer writes and merge sorted files in the background, and the hash, GIN, GiST and BRIN indexes for other kinds of query.
- B-trees and B+trees (14 min)
- Log-structured merge trees (14 min)
- Hash, GIN, GiST and BRIN indexes (12 min)
- Hands-on lab: Build a small LSM tree
Indexes and query planning
Design indexes for real queries (composite, covering, partial and expression indexes), learn how a cost-based planner chooses scans and joins from statistics, and read EXPLAIN output in SQLite and PostgreSQL.
- Composite, covering and partial indexes (14 min)
- How the planner chooses a plan (13 min)
- Reading EXPLAIN and EXPLAIN ANALYZE (14 min)
- Hands-on lab: Fix slow queries by reading their plans
Transactions, isolation and MVCC
Define what a transaction guarantees, name the anomalies weaker isolation allows, compare the isolation levels real databases implement, and see how multi-version concurrency control gives readers consistent snapshots without blocking writers.
- ACID and the anomalies (13 min)
- Isolation levels in real databases (14 min)
- Multi-version concurrency control (14 min)
- Hands-on lab: Simulate MVCC, then see real snapshots in SQLite
Locking, deadlocks and recovery
Use locks where MVCC isn't enough, see how deadlocks form and how databases detect or avoid them, and learn how the write-ahead log makes commits durable and lets a database recover from a crash.
- Locks and two-phase locking (13 min)
- Deadlocks (12 min)
- Write-ahead logging and crash recovery (14 min)
- Hands-on lab: Deadlocks and a write-ahead log
Project: Diagnose and tune a slow help-desk database
A help-desk application keeps its users, tickets and comments in SQLite. Agents say it's slow, and that two of them sometimes end up working on the same ticket. make_db.py builds a copy of the database (5,000 users, 80,000 tickets, 160,000 comments); workload.py runs the eight slowest endpoints, printing each one's median time and plan, then times a batch of inserts; workload.py --race reproduces the double assignment. Diagnose each endpoint from its plan. Design the smallest set of indexes that fixes them (composite, covering, partial or on an expression, as each needs), rewrite the queries no index can fix (a function on a column, a deep OFFSET), and find out what SQLite needs before a LIKE can use an index. Measure what your indexes cost the write benchmark. Fix the race so that two agents can never take the same ticket, and prove it with a concurrent test. Finally, plan the move to PostgreSQL: the same schema and indexes, the EXPLAIN (ANALYZE, BUFFERS) checks you would run, and what changes for isolation, locking (FOR UPDATE SKIP LOCKED for the ticket queue) and VACUUM. Write it up in report_template.md.
Part of
The products this course names are trademarks of their owners, who haven't made or endorsed it.