Database internals, in reading order
The relational model through to the cloud warehouse.
11 papers, in the order to read them. A paper that needs another one first is listed under it.
- 1A Relational Model of Data for Large Shared Data Banks
data as relations, independent of how it is stored
- 2Organization and Maintenance of Large Ordered Indices
a balanced tree with a page-sized node
- 3System R: Relational Approach to Database Management
the first relational system that worked, and SQL with it
Read first: A Relational Model of Data for Large Shared Data Banks
- 4Access Path Selection in a Relational Database Management System
cost-based optimisation, and dynamic programming over join orders
Read first: System R: Relational Approach to Database Management
- 5ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging
analysis, redo, undo, and repeating history before undoing it
- 6Volcano - An Extensible and Parallel Query Evaluation System
the iterator model, and parallelism as one more operator
- 7C-Store: A Column-oriented DBMS
store columns, compress them, and read only what the query touches
- 8MonetDB/X100: Hyper-Pipelining Query Execution
vectors of tuples per call, so the CPU pipeline stays full
Read first: Volcano - An Extensible and Parallel Query Evaluation System
- 9Bigtable: A Distributed Storage System for Structured Data
a sparse, sorted, multidimensional map over a distributed file system
Read first: The Google File System (not on this list)
- 10Spanner: Google's Globally-Distributed Database
TrueTime, and externally consistent transactions across continents
Read first: Bigtable: A Distributed Storage System for Structured Data, The Part-Time Parliament (not on this list)
- 11The Snowflake Elastic Data Warehouse
storage and compute separated, and elasticity as a product
Read first: C-Store: A Column-oriented DBMS