Awesome Database Learning
A list of learning materials to understand databases internals, including but not limited to:
- papers
- blogs
- courses
- talks
Please submit a pull request if there is any material that you think should be included in this collection.
Table of Contents
Recommended Courses, Books and Talks
Courses
Books
Talks
Blogs
SQL & Relation Algebra
Courses:
Query Optimizer
Courses:
Blogs:
Planner Models
Blogs:
Papers:
- 1979, Access Path Selection in a Relational Database Management System, SIGMOD
- 1979, Query Processing in Main Memory Database Management Systems, VLDB
- 1987, Query Optimization by Simulated Annealing, SIGMOD
- 1988, Grammar-like Functional Rules for Representing Query Optimization Alternatives, SIGMOD
- 1993, The Volcano Optimizer Generator- Extensibility and Efficient Search, ICDE
- 1995, The Cascades Framework for Query Optimization, IEEE Data engineering Bulltin
- 1998, An Overview of Query Optimization in Relational Systems, PODS
- 2001, LEO – DB2’s LEarning Optimizer, VLDB
- 2004, Robust Query Processing through Progressive Optimization, SIGMOD
- 2014, Orca: A Modular Query Optimizer Architecture for Big Data, SIGMOD
- 2016, Parallelizing Query Optimization on Shared-Nothing Architectures, VLDB
- 2016, The MemSQL Query Optimizer: A modern optimizer for real-time analytics in a distributed database, VLDB
Subquery Optimization
Blogs:
Papers:
Join Order Optimization
Papers:
Functional Dependency & Physical Properties
Thesis:
Papers:
Cost Model
Papers:
Statistics
Papers:
- 1984, Accurate Estimation of the Number of Tuples Satisfying a Condition, SIGMOD
- 1993, Optimal Histograms for Limiting Worst-Case Error Propagation in the Size of Join Results, ACM Trans. on Database Systems
- 1993, Universality of Serial Histograms, VLDB
- 1995, Balancing Histogram Optimality and Practicality for Query Result Size Estimation, SIGMOD
- 1996, Improved Histograms for Selectivity Estimation of Range Predicates, SIGMOD
- 1997, SEEKing the truth about ad hoc join costs, VLDB
- 2000, Towards Estimation Error Guarantees for Distinct Values, SIGMOD/PODS
- 2001, Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports, VLDB
- 2003, The History of Histograms, VLDB
- 2005, An Improved Data Stream Summary: The Count-Min Sketch and its Applications, Journal of Algorithms
- 2007, New Estimation Algorithms for Streaming Data: Count-min Can Do More
- 2009, Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors, VLDB
- 2010, Histograms Reloaded: The Merits of Bucket Diversity, SIGMOD
- 2014, Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA, SIGMOD
- 2017, Adaptive Statistics in Oracle 12c, VLDB
- 2019, Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities, SIGMOD
- 2019, Deep Unsupervised Cardinality Estimation, VLDB
- 2020, NeuroCard: One Cardinality Estimator for All Tables, VLDB
Books:
Query Execution
Courses:
Execution Framework
Papers:
Vectorization vs Compilization
Blogs:
Papers:
- 2005, MonetDB/X100: Hyper-Pipelining Query Execution, CIDR
- 2011, Efficiently Compiling Efficient Query Plans for Modern Hardware, VLDB
- 2017, Relaxed Operator Fusion for In-Memory Databases: Making Compilation, Vectorization, and Prefetching Work Together At Last, VLDB
- 2018, Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask, VLDB
- 2018, Adaptive Execution of Compiled Queries, ICDE
Join
Papers:
Hash Table
Courses:
Blogs:
Bloom Filter
Papers:
DDL
Relational Model
Blogs:
Codd's Rules
Blogs:
Relational Data Model
Blogs:
Relational Algebra
Blogs:
ER to Relational Model
Blogs:
SQL - Overview
Blogs:
Transaction
Isolation Levels
Blogs:
Papers:
Concurrency Control
Courses:
Papers:
- 1976, The Notions of Consistency and Predicate Locks in a Database System, Communications of the ACM
- 1981, Concurrency Control in Distributed Database Systems, ACM Computing Surveys
- 1981, On Optimistic Methods for Concurrency Control, ACM Transactions on Database Systems
- 1983, Multiversion Concurrency Control - Theory and Algorithms, ACM Transactions on Database Systems
- 2012, Serializable Snapshot Isolation in PostgreSQL, VLDB
- 2012, Calvin: Fast Distributed Transactions for Partitioned Database Systems, SIGMOD
- 2014, MaaT: effective and scalable coordination of distributed transactions in the cloud, VLDB
- 2014, Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores, VLDB
- 2014, An Evaluation of the Advantages and Disadvantages of Deterministic Database Systems, VLDB
- 2015, Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems, SIGMOD
- 2017, An Empirical Evaluation of In-Memory Multi-Version Concurrency Control, VLDB
- 2017, An Evaluation of Distributed Concurrency Control, VLDB
- 2019, Scalable Garbage Collection for In-Memory MVCC Systems, VLDB
Network
Courses:
Papers:
Storage
NoSQL Systems
Papers:
- 2006, Bigtable: A Distributed Storage System for Structured Data, OSDI
- 2007, Dynamo: Amazon’s Highly Available Key-value Store, SOSP
- 2008, PNUTS: Yahoo!’s Hosted Data Serving Platform, VLDB
- 2010, Cassandra - A Decentralized Structured Storage System, SOSP
- 2019, PNUTS to Sherpa: Lessons from Yahoo!’s Cloud Database , VLDB
Buffer Management
Courses:
Papers:
- 1987, The 5 Minute Rule for Trading Memory for Disc Accesses and the 5 Byte Rule for Trading Memory for CPU Time, SIGMOD
- 2008, The Five Minute Rule 20 Years Later and How Flash Memory Changes the Rules, ACM Queue
- 2018, Managing Non-Volatile Memory in Database Systems, SIGMOD
- 2018, LeanStore: In-Memory Data Management Beyond Main Memory, ICDE
- 2020, Umbra: A Disk-Based System with In-Memory Performance, CIDR
Disk IO
Blogs:
- On Disk IO, Part 1: Flavors of IO, thanks to Alex
- On Disk IO, Part 2: More Flavours of IO, thanks to Alex
- On Disk IO, Part 3: LSM Trees, thanks to Alex
- On Disk IO, Part 4: B-Trees and RUM Conjecture, thanks to Alex
- On Disk IO, Part 5: Access Patterns in LSM Trees, thanks to Alex
- Ensuring data reaches disk(LWN)
- Read, write & space amplification - pick 2, thanks to Mark Callaghan
Papers:
B-Tree
Blogs:
Courses:
Papers:
LSM-Tree
Papers:
Learned Indexes Structures
Papers:
- 2018, The Case for Learned Index Structures
- 2019, Learning Multi-dimensional Indexes
- 2020, XIndex: A Scalable Learned Index for Multicore Data Storage
- 2020, RadixSpline: A Single-Pass Learned Index, Source Code, aiDM@SIGMOD
- 2020, The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds, Source Code, VLDB
- 2020, From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees
Serializing & RPC
Data Partitioning
Blogs:
Papers:
Replication & Consistency
Blogs:
Papers:
Consensus
Technical report:
- University of Cambridge Distributed consensus revised, a great paper about Consenssus especially Paxos and Paxos-Related algorithms, by Heidi Howard
Papers:
Scheduling
Blogs:
Papers:
Benchmark & Testing
Blogs:
Papers:
HTAP
Papers:
TLA+
Talks:
一份用于理解数据库内部原理的精选学习资料合集——包括论文、教科书、大学课程、演讲和博客文章——内容涵盖从查询优化到存储、并发控制和分布式共识的方方面面。