### Database Systems Research Paper Reading List

This lecture curriculum is of CMU DB Intro Course by Andy Pavlo.
You can find more details on the course [here](https://15445.courses.cs.cmu.edu/fall2024/) 

| Lecture # | Lecture Name | Research Papers (Unique Links) |
|-----------|--------------|--------------------------------|
| **00** | Course Overview & Logistics | • [A Relational Model of Data for Large Shared Data Banks](https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf)<br>• [Architecture of a Database System](https://dsf.berkeley.edu/papers/fntdb07-architecture.pdf)<br>• [What Goes Around Comes Around](https://people.cs.umass.edu/~yanlei/courses/CS691LL-f06/papers/SH05.pdf)<br>• [Reflections on the Future of Database Systems](https://dl.acm.org/doi/10.1145/142414.142423) |
| **01** | Relational Model & Algebra | • [A Relational Model of Data for Large Shared Data Banks](https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf)<br>• [Relational Algebra and Relational Calculus](https://dl.acm.org/doi/10.1145/362384.362685)<br>• [Derivability, Redundancy, and Consistency of Relations](https://dl.acm.org/doi/10.1145/362384.362685)<br>• [The Transaction Concept: Virtues and Limitations](https://dl.acm.org/doi/10.1109/TR.1983.5221735)<br>• [A Critique of the SQL Database Language](https://dl.acm.org/doi/10.1145/1046933.1046940)<br>• [The Third Manifesto](https://www.dcs.warwick.ac.uk/~hugh/TTM/DTATRM.pdf)<br>• [Foundations of Databases](https://webdam.inria.fr/Alice/)<br>• [Access Path Selection in a Relational Database Management System](https://dsf.berkeley.edu/papers/fntdb07-opt4.pdf) |
| **02** | Modern SQL | • [SQL:1999, Formerly Known as SQL3](https://dl.acm.org/doi/10.1145/846150.846151)<br>• [Advanced SQL:1999](https://dl.acm.org/doi/10.5555/940308)<br>• [SQL:2011 - Under the Covers](https://ieeexplore.ieee.org/document/6171608)<br>• [Pivoted Knowledge](https://dl.acm.org/doi/10.1145/1247480.1247646)<br>• [A Decomposition Storage Model](https://dl.acm.org/doi/10.1145/971701.50214)<br>• [SQL:1999, SQL:2003, SQL:2006](https://www.iso.org/standard/45498.html)<br>• [Temporal Support in SQL:2011](https://dl.acm.org/doi/10.1145/2695667)<br>• [Efficiently Compiling Efficient Query Plans](https://dl.acm.org/doi/10.14778/2002938.2002940)<br>• [Spark SQL: Relational Data Processing in Spark](https://people.csail.mit.edu/matei/papers/2015/sigmod_spark_sql.pdf)<br>• [CockroachDB: The Resilient Geo-Distributed SQL Database](https://www.cockroachlabs.com/blog/paper-reading-cockroachdb/) |
| **03** | Database Storage I | • [The Design and Implementation of Modern Column-Oriented Database Systems](https://dl.acm.org/doi/10.1561/1900000024)<br>• [C-Store: A Column-oriented DBMS](https://dl.acm.org/doi/10.5555/1083592.1083658)<br>• [Design Tradeoffs for SSD Performance](https://www.usenix.org/legacy/event/usenix08/tech/full_papers/agrawal/agrawal.pdf)<br>• [A Five-Minute Rule for Modern Storage Media](https://dl.acm.org/doi/10.1145/1594204.1594207)<br>• [Database Architecture Optimized for Memory Access](https://dl.acm.org/doi/10.1145/304182.304211)<br>• [ARIES: A Transaction Recovery Method](https://cs.stanford.edu/people/chrismre/cs345/rl/aries.pdf)<br>• [The Design and Implementation of a Log-Structured File System](https://people.eecs.berkeley.edu/~brewer/cs262/LFS.pdf)<br>• [LevelDB Documentation](https://github.com/google/leveldb)<br>• [LMDB: Memory-Mapped Key-Value Storage](https://github.com/LMDB/lmdb) |
| **04** | Database Storage II | • [ARIES: Fine-Granularity Locking and Partial Rollbacks](https://dl.acm.org/doi/10.1145/128765.128770)<br>• [The Log-Structured Merge-Tree (LSM-Tree)](https://dl.acm.org/doi/10.1007/s002360050048)<br>• [WiscKey: Separating Keys from Values in SSD-Conscious Storage](https://www.usenix.org/system/files/conference/fast16/fast16-papers-lu.pdf)<br>• [A Comparison of Approaches to Large-Scale Data Analysis](https://dl.acm.org/doi/10.1145/1559845.1559865)<br>• [Efficiently Compiling Efficient Query Plans](https://dl.acm.org/doi/10.14778/2002938.2002940)<br>• [The 5 Minute Rule for Trading Memory for Disk Accesses](https://www.hpl.hp.com/techreports/tandem/TR-86.1.pdf)<br>• [The DBMIN Storage Manager](https://dl.acm.org/doi/10.1145/971697.602294)<br>• [LeanStore: In-Memory Data Management](https://dl.acm.org/doi/10.1145/3183713.3196896)<br>• [The Bw-Tree: A B-tree for New Hardware Platforms](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/bw-tree-icde2013-final.pdf) |
| **05** | Storage Models & Compression | • [Column-Stores vs. Row-Stores](https://dl.acm.org/doi/10.1145/1376616.1376712)<br>• [Integrating Compression and Execution in Column-Oriented Databases](https://dl.acm.org/doi/10.1145/1142473.1142548)<br>• [Data Blocks: Hybrid OLTP and OLAP](https://dl.acm.org/doi/10.1145/3183713.3196937)<br>• [MonetDB/X100: Hyper-Pipelining Query Execution](https://dl.acm.org/doi/10.5555/1083592.1083600)<br>• [Database Cracking: Fancy Scan, not Poor Man's Sort!](https://dl.acm.org/doi/10.14778/3229863.3229867)<br>• [ZStandard: Fast and Efficient Compression](https://github.com/facebook/zstd)<br>• [Amazon Redshift and Simpler Data Warehouses](https://dl.acm.org/doi/10.1145/2723372.2742795) |
| **06** | Memory Management | • [Buffer Management in Database Systems](https://dl.acm.org/doi/10.1145/1270.1271)<br>• [The Five-Minute Rule Ten Years Later](https://dl.acm.org/doi/10.1145/271074.271094)<br>• [Managing Non-Volatile Memory](https://dl.acm.org/doi/10.1145/2463676.2465270)<br>• [Main Memory Hash Join Algorithms](https://dl.acm.org/doi/10.1145/1989323.1989328)<br>• [Memory Management for High-Performance Applications](https://people.cs.umass.edu/~emery/pubs/berger-pldi00.pdf)<br>• [C-ARF: Clock-Based Adaptive Replacement Filter](https://ieeexplore.ieee.org/document/5447811)<br>• [Optimizing In-Memory Databases for AI Workloads](https://arxiv.org/pdf/1901.08255) |
| **07** | Hash Tables | • [Extendible Hashing—A Fast Access Method](https://dl.acm.org/doi/10.1145/320083.320092)<br>• [Linear Hashing: A New Tool for File Addressing](https://dl.acm.org/doi/10.5555/1286831.1286848)<br>• [Dynamic Hash Tables](https://dl.acm.org/doi/10.1145/62084.62087)<br>• [Cache-Conscious Collision Resolution](https://dl.acm.org/doi/10.1145/1106014.1106034)<br>• [Cuckoo Hashing](https://dl.acm.org/doi/10.1007/3-540-48058-0_9)<br>• [Hopscotch Hashing](https://dl.acm.org/doi/10.1007/978-3-540-87779-0_24)<br>• [Robin Hood Hashing](https://cs.uwaterloo.ca/research/tr/1985/CS-85-12.pdf) |
| **08** | Indexes & Filters I | • [Ubiquitous B-Tree](https://dl.acm.org/doi/10.1145/356770.356776)<br>• [R-Trees: A Dynamic Index Structure](https://dl.acm.org/doi/10.1145/971697.602266)<br>• [The R*-Tree: Efficient and Robust Access](https://dl.acm.org/doi/10.1145/93597.98741)<br>• [Bloom Filters in Probabilistic Verification](https://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf)<br>• [Cache-Conscious Indexing](https://dl.acm.org/doi/10.5555/645925.671362)<br>• [Cuckoo Filter: Practically Better Than Bloom](https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) |
| **09** | Indexes & Filters II | • [The Adaptive Radix Tree (ART)](https://db.in.tum.de/~leis/papers/ART.pdf)<br>• [FAST: Fast Architecture Sensitive Tree Search](https://dl.acm.org/doi/10.1145/1807167.1807206)<br>• [Bitmap Index Design and Evaluation](https://dl.acm.org/doi/10.1145/253262.253268)<br>• [Less is More: Lightweight Filter Design](https://arxiv.org/abs/2203.00482)<br>• [The Bw-Tree: A B-tree for New Hardware](https://www.microsoft.com/en-us/research/publication/the-bw-tree-a-b-tree-for-new-hardware/)<br>• [The Log-Structured Merge-Tree (LSM-Tree)](https://www.cs.umb.edu/~poneil/lsmtree.pdf)<br>• [TiDB: A Raft-Based HTAP Database](https://dl.acm.org/doi/10.14778/3407790.3407853) |
| **10** | Index Concurrency Control | • [Optimistic Methods for Concurrency Control](https://dl.acm.org/doi/10.1145/319628.319650)<br>• [Generalized Isolation Level Definitions](https://dl.acm.org/doi/10.1109/ICDE.2000.839452)<br>• [Granularity of Locks and Degrees of Consistency](https://dl.acm.org/doi/10.5555/1241882.1241895)<br>• [A Case for Fractured Mirrors](https://dl.acm.org/doi/10.5555/1287369.1287455)<br>• [Implementing Data Cubes Efficiently](https://dl.acm.org/doi/10.1145/235968.233333)<br>• [Efficient Locking for B-Trees](https://www.csd.uoc.gr/~hy460/pdf/p650-lehman.pdf)<br>• [MassTree: A Cache-Conscious Concurrent B+-Tree](https://pdos.csail.mit.edu/papers/masstree:eurosys12.pdf) |
| **11** | Sorting & Aggregation Algorithms | • [AlphaSort: A RISC Machine Sort](https://dl.acm.org/doi/10.1145/191843.191970)<br>• [Efficient External Sorting](https://dl.acm.org/doi/10.1145/170036.170058)<br>• [Implementing Sorting in Database Systems](https://dl.acm.org/doi/10.1145/1132863.1132865)<br>• [Efficient Aggregation for Graph Summarization](https://dl.acm.org/doi/10.1145/1376616.1376683)<br>• [Scalable Progressive Analytics](https://dl.acm.org/doi/10.14778/2536336.2536356)<br>• [HyperLogLog in Practice](https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf) |
| **12** | Joins Algorithms | • [Hash Joins and Hash Teams in SQL Server](https://dl.acm.org/doi/10.1109/ICDE.2011.5767868)<br>• [Main-Memory Hash Joins on Multi-Core CPUs](https://dl.acm.org/doi/10.1109/ICDE.2013.6544839)<br>• [Sort vs. Hash Revisited](https://dl.acm.org/doi/10.14778/1687627.1687645)<br>• [A Comparison of Adaptive Radix Trees and Hash Tables](https://dl.acm.org/doi/10.1109/ICDE.2019.00028)<br>• [Improving Hash Joins on Intel Xeon Phi](https://dl.acm.org/doi/10.14778/2831360.2831362)<br>• [Grace Hash Join: A Hybrid Hash Join](https://dsf.berkeley.edu/cs286/papers/gracehash-vldb1984.pdf)<br>• [The Radix-Clustered Join Algorithm](https://www.cidrdb.org/cidr1999/P21.pdf) |
| **13** | Query Execution I | • [Volcano - An Extensible Query Evaluation System](https://dl.acm.org/doi/10.1109/69.273032)<br>• [Morsel-Driven Parallelism](https://dl.acm.org/doi/10.1145/2588555.2610507)<br>• [Vectorwise: Beyond Column Stores](https://dl.acm.org/doi/10.1109/DEBull.2012.19)<br>• [Adaptive Execution of Compiled Queries](https://dl.acm.org/doi/10.1109/ICDE.2018.00025)<br>• [Everything About Compiled and Vectorized Queries](https://dl.acm.org/doi/10.14778/3275366.3284966)<br>• [Morsel-Driven Parallelism (NUMA-Aware)](https://dl.acm.org/doi/10.14778/2732977.2732983) |
| **14** | Query Execution II | • [How to Architect a Query Compiler](https://dl.acm.org/doi/10.1145/3183713.3196935)<br>• [Relaxed Operator Fusion](https://dl.acm.org/doi/10.14778/3137628.3137633)<br>• [Adaptive Query Processing: Technology in Evolution](https://dl.acm.org/doi/10.1109/MC.2007.147)<br>• [Dremel: Interactive Analysis of Web-Scale Datasets](https://dl.acm.org/doi/10.14778/1920841.1920886)<br>• [ClickHouse: High-Performance Column-Oriented DB](https://clickhouse.com/docs/en/development/architecture)<br>• [Vectorized Execution for Query Engines](https://dl.acm.org/doi/10.1145/3299869.3319881) |
| **15** | Query Planning & Optimization | • [Access Path Selection in a Relational DBMS](https://dl.acm.org/doi/10.1145/582095.582099)<br>• [The Volcano Optimizer Generator](https://dl.acm.org/doi/10.1109/ICDE.1993.344061)<br>• [The Cascades Framework](https://dl.acm.org/doi/10.5555/671310)<br>• [An Overview of Query Optimization](https://dl.acm.org/doi/10.1145/275487.275492)<br>• [Orca: A Modular Query Optimizer](https://dl.acm.org/doi/10.1145/2619228.2619231)<br>• [Eddy: Continuously Adaptive Query Processing](https://dsf.berkeley.edu/cs286/papers/eddy-sigmod2000.pdf) |
| **16** | Concurrency Control Theory | • [A Critique of ANSI SQL Isolation Levels](https://dl.acm.org/doi/10.1145/223784.223785)<br>• [Concurrency Control in Distributed Databases](https://dl.acm.org/doi/10.1145/356842.356846)<br>• [A Majority Consensus Approach](https://dl.acm.org/doi/10.1145/800152.804484)<br>• [Serializable Isolation for Snapshot Databases](https://dl.acm.org/doi/10.1145/1376616.1376690)<br>• [Granularity of Locks and Degrees of Consistency](https://dsf.berkeley.edu/cs286/papers/graymvcc-cacm1976.pdf) |
| **17** | Two-Phase Locking Concurrency Control | • [An Algorithm for Concurrency Control in Distributed DB](https://dl.acm.org/doi/10.1145/2845.2847)<br>• [Distributed Deadlock Detection](https://dl.acm.org/doi/10.1145/45267.45288)<br>• [Hierarchical Locking in B-tree Indexes](https://dl.acm.org/doi/10.5555/646484.694342)<br>• [Strict 2PL: A High-Performance Locking Protocol](https://dl.acm.org/doi/10.1145/319628.319651)<br>• [Locking in Databases: A Survey](https://dl.acm.org/doi/10.1109/MIS.2002.1039831) |
| **18** | Timestamp Ordering Concurrency Control | • [Distributed Timestamp Order Concurrency Control](https://dl.acm.org/doi/10.1145/3007165.3007176)<br>• [Timestamp-Based Protocols for Distributed DB](https://ieeexplore.ieee.org/document/379681)<br>• [Timestamp-Based Concurrency Control for Heterogeneous DB](https://ieeexplore.ieee.org/document/1385504)<br>• [Timestamp-Based Two-Phase Locking](https://dl.acm.org/doi/10.1109/IDEAS.2004.1319800)<br>• [An Implementation of Causal Ordering](https://dl.acm.org/doi/10.1109/71.80124)<br>• [Silo: Speeding Up In-Memory Databases with Hardware Transactions](https://dl.acm.org/doi/10.1145/2517349.2522712) |
| **19** | Multi-Version Concurrency Control | • [High-Performance Concurrency Control for Main-Memory DB](https://dl.acm.org/doi/10.14778/2556549.2556562)<br>• [Serializable Snapshot Isolation in PostgreSQL](https://dl.acm.org/doi/10.14778/2168651.2168659)<br>• [An Empirical Evaluation of MVCC](https://dl.acm.org/doi/10.14778/3137628.3137641)<br>• [Cicada: Dependably Fast Multi-Core Transactions](https://dl.acm.org/doi/10.1145/3035918.3064015)<br>• [Hyder: A Transactional Record Manager for Shared Flash](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/hyder-sigmod2013.pdf) |
| **20** | Database Logging | • [Lightweight Locking for Main Memory DB](https://dl.acm.org/doi/10.14778/2095686.2095689)<br>• [Scalable Logging with Non-Volatile Memory](https://dl.acm.org/doi/10.14778/2732240.2732246)<br>• [Fast Databases with Fast Durability](https://dl.acm.org/doi/10.5555/2685048.2685065)<br>• [The End of a Myth: Distributed Transactions Can Scale](https://dl.acm.org/doi/10.14778/3137628.3137659)<br>• [Scalable Atomic Visibility with RAMP Transactions](https://dl.acm.org/doi/10.1145/2588555.2588562)<br>• [Kafka: A Distributed Messaging System](https://www.kafka.apache.org/) |
| **21** | Database Recovery | • [Recovering With Limited Overlap](https://dl.acm.org/doi/10.1145/7474.7477)<br>• [Crash Recovery in a Distributed System](https://dl.acm.org/doi/10.5555/1313611.1313615)<br>• [Constant Time Recovery in Azure SQL](https://dl.acm.org/doi/10.14778/3352063.3352090)<br>• [NVM Write Allocation](https://dl.acm.org/doi/10.1145/3117811.3132479)<br>• [Fast Recovery in In-Memory Databases](https://dl.acm.org/doi/10.1145/2882903.2882942)<br>• [Non-Volatile Memory DBMS](https://dl.acm.org/doi/10.14778/2733004.2733006) |
| **22** | Introduction to Distributed Databases | • [The Case for Determinism in DB Systems](https://dl.acm.org/doi/10.14778/1920841.1920855)<br>• [Bigtable: A Distributed Storage System](https://dl.acm.org/doi/10.5555/1267308.1267323)<br>• [Dynamo: Amazon’s Highly Available Key-Value Store](https://dl.acm.org/doi/10.1145/1294261.1294281)<br>• [CAP Twelve Years Later](https://ieeexplore.ieee.org/document/6133253)<br>• [Spanner: Google’s Globally-Distributed DB](https://static.googleusercontent.com/media/research.google.com/en//archive/spanner-osdi2012.pdf) |
| **23** | Distributed OLTP Database Systems | • [Calvin: Fast Distributed Transactions](https://dl.acm.org/doi/10.1145/2213836.2213838)<br>• [Amazon Aurora: Cloud-Native Relational DB](https://dl.acm.org/doi/10.1145/3035918.3056101)<br>• [F1: A Distributed SQL Database](https://dl.acm.org/doi/10.14778/2536222.2536232)<br>• [Orleans: Distributed Virtual Actors](https://www.microsoft.com/en-us/research/publication/orleans-distributed-virtual-actors-for-programmability-and-scalability/)<br>• [SLOG: Serializable, Low-Latency Geo-Replicated Transactions](https://dl.acm.org/doi/10.14778/3407790.3407855) |
| **24** | Distributed OLAP Database Systems | • [Presto: SQL on Everything](https://dl.acm.org/doi/10.1145/3299869.3314040)<br>• [Spark SQL: Relational Data Processing](https://dl.acm.org/doi/10.1145/2723372.2742797)<br>• [SnowFlake: A Query Workspace](https://dl.acm.org/doi/10.14778/2944415.2944420)<br>• [Apache Druid: Real-Time Analytics DB](https://arxiv.org/pdf/2003.08236) |
| **25** | Final Review + Systems Potpourri | • [What's Really New with NewSQL?](https://dl.acm.org/doi/10.1145/2940745)<br>• [The Predictive Database](https://dl.acm.org/doi/10.14778/2824032.2824093)<br>• [The End of an Architectural Era](https://dl.acm.org/doi/10.1109/VLDB.2007.4304066)<br>• [Retrospection on DB System Performance](https://dl.acm.org/doi/10.1145/2588555.2611185)<br>• [Research for Practice: Prediction-Serving Systems](https://dl.acm.org/doi/10.1145/3051024)<br>• [The Case for Learned Index Structures](https://arxiv.org/pdf/1712.01208)<br>• [Designing Data-Intensive Applications](https://dataintensive.net/) |
