Papers
The papers that shaped how databases are built, and the ones we keep coming back to in our sessions. Each comes with a note on why it is worth your time.
How we read papers
Research papers are dense. Nobody reads them in one go. Try three passes.
- Pass 1
Skim
Read the title, abstract, introduction, headings, and conclusion. What problem does it solve?
- Pass 2
Understand
Read it properly. Study the figures, note what you don't follow, and skip the proofs for now.
- Pass 3
Rebuild
Could you explain it to someone else, or sketch an implementation? That is what our sessions are for.
Showing 19 of 19 papers, oldest first
- FoundationsStart here1970
A Relational Model of Data for Large Shared Data Banks
E. F. Codd · Communications of the ACM
Where the relational model began. Short, readable, and still the foundation of every SQL database.
Summary and key ideas→ - Storage & IndexingStart here1972
Organization and Maintenance of Large Ordered Indices
R. Bayer, E. McCreight · Acta Informatica
The original B-tree paper. The index structure behind nearly every database.
Summary and key ideas→ - Query ProcessingStart here1979
Access Path Selection in a Relational Database Management System
P. G. Selinger et al. · SIGMOD
The birth of cost-based query optimisation, from System R.
Summary and key ideas→ - Storage & Indexing1992
The Design and Implementation of a Log-Structured File System
M. Rosenblum, J. K. Ousterhout · ACM Transactions on Computer Systems
Treating the disk as an append-only log. An idea that shaped storage design for decades.
Summary and key ideas→ - Transactions & Recovery1992
ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging
C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, P. Schwarz · ACM Transactions on Database Systems
The definitive write-ahead logging and crash recovery algorithm. Dense, but worth every page.
Summary and key ideas→ - Query Processing1994
Volcano — An Extensible and Parallel Query Evaluation System
G. Graefe · IEEE Transactions on Knowledge and Data Engineering
The iterator model that most query engines still use today.
Summary and key ideas→ - Transactions & Recovery1995
A Critique of ANSI SQL Isolation Levels
H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O'Neil, P. O'Neil · SIGMOD
What isolation levels really guarantee, and the anomalies the standard missed.
Summary and key ideas→ - Storage & Indexing1996
The Log-Structured Merge-Tree (LSM-Tree)
P. O'Neil, E. Cheng, D. Gawlick, E. O'Neil · Acta Informatica
The write-optimised structure behind RocksDB, Cassandra, and many modern storage engines.
Summary and key ideas→ - Foundations2005
What Goes Around Comes Around
M. Stonebraker, J. M. Hellerstein · Readings in Database Systems
Decades of data model history, and why the same ideas keep coming back.
Summary and key ideas→ - Storage & Indexing2005
C-Store: A Column-oriented DBMS
M. Stonebraker et al. · VLDB
Why storing data by column changes everything for analytics workloads.
Summary and key ideas→ - Query Processing2005
MonetDB/X100: Hyper-Pipelining Query Execution
P. Boncz, M. Zukowski, N. Nes · CIDR
Vectorised execution: processing batches instead of single tuples to use modern CPUs well.
Summary and key ideas→ - Distributed Systems2006
Bigtable: A Distributed Storage System for Structured Data
F. Chang et al. · OSDI
How Google stored structured data at planet scale, and a blueprint for many NoSQL systems.
Summary and key ideas→ - FoundationsStart here2007
Architecture of a Database System
J. M. Hellerstein, M. Stonebraker, J. Hamilton · Foundations and Trends in Databases
A guided tour of every major component inside a DBMS. The best map before diving into any one part.
Summary and key ideas→ - Distributed Systems2007
Dynamo: Amazon's Highly Available Key-value Store
G. DeCandia et al. · SOSP
Consistent hashing, quorums, and choosing availability over consistency.
Summary and key ideas→ - Transactions & Recovery2008
OLTP Through the Looking Glass, and What We Found There
S. Harizopoulos, D. J. Abadi, S. Madden, M. Stonebraker · SIGMOD
Where does the time actually go in a transaction? A surprising breakdown of overheads.
Summary and key ideas→ - Query Processing2011
Efficiently Compiling Efficient Query Plans for Modern Hardware
T. Neumann · VLDB
Compiling queries to machine code, the alternative to vectorisation.
Summary and key ideas→ - Distributed Systems2012
Spanner: Google's Globally-Distributed Database
J. C. Corbett et al. · OSDI
Global transactions made possible by carefully bounded clock uncertainty.
Summary and key ideas→ - Distributed Systems2014
In Search of an Understandable Consensus Algorithm
D. Ongaro, J. Ousterhout · USENIX ATC
Raft, the consensus algorithm designed to be understood. A great first distributed systems paper.
Summary and key ideas→ - I/O & HardwareStart here2022
Are You Sure You Want to Use MMAP in Your Database Management System?
A. Crotty, V. Leis, A. Pavlo · CIDR
Why letting the OS manage your pages is tempting, and why it usually goes wrong.
Summary and key ideas→