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


• Query Optimizer
  
  
  • Planner Models
  
  
  • Subquery Optimization
  
  
  • Join Order Optimization
  
  
  • Functional Dependency & Physical Properties
  
  
  • Cost Model
  
  
  • Statistics
  
  
  
  


• Query Execution
  
  
  • Execution Framework
  
  
  • Vectorization vs Compilization
  
  
  • Join
  
  
  • Hash Table
  
  
  • Bloom Filter
  
  
  
  


• DDL


• Relational Model
  
  
  • Codd's Rules
  
  
  • Relational Data Model
  
  
  • Relational Algebra
  
  
  • ER to Relational Model
  
  
  • SQL - Overview
  
  
  
  


• Transaction
  
  
  • Isolation Levels
  
  
  • Concurrency Control
  
  
  
  


• Network


• Storage
  
  
  • NoSQL Systems
  
  
  • Buffer Management
  
  
  • Disk IO
  
  
  • B-Tree
  
  
  • LSM-Tree
  
  
  • Learned Indexes Structures
  
  
  
  


• Serializing & RPC


• Data Partitioning


• Replication & Consistency


• Consensus


• Scheduling


• Benchmark & Testing


• HTAP


• TLA+

Recommended Courses, Books and Talks
Courses

• CMU Database Systems (15-445/645), thanks to Andy Pavlo


• CMU Advanced Database Systems (15-721), thanks to Andy Pavlo


• UC Berkeley Introduction to Database Systems


• Stanford Database System Implementation


• Cornell Introduction to Database Systems by Prof. Trummer


• Let's Build a Simple Database, thanks to cstack

Books

• Stanford Database Systems: The Complete Book


• Designing Data-Intensive Applications, 中文翻译


• Database Internals


• Foundations of Databases


• Readings in Database Systems, 5th Edition


• Database Design and Implementation: Second Edition (Data-Centric Systems and Applications)


• Principles of Distributed Database Systems, 4th ed


• Inside SQLite


• Architecture of a Database System


• Relational Database Index Design and the Optimizers


• Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control

Talks

• Data Structures and Algorithms for Big Databases


• A Journey From A Quick HackTo A High-Reliability Database Engine

Blogs

• How does a relational database work


• The Internals of PostgreSQL


• Books propose

SQL & Relation Algebra

Courses:

• 
  

  CMU Database Systems (15-445/645), thanks to Andy Pavlo

  
  
  
  
  • Course Introduction and the Relational Model
  
  
  • Advanced SQL
  
  
  
  


• 
  

  UC Berkeley Introduction to Database Systems

  
  
  
  
  • Introduction + SQL I
  
  
  • SQL II
  
  
  • Relational Algebra
  
  
  
  

Query Optimizer

Courses:

• CMU Database Systems (15-445/645), thanks to Andy Pavlo
  
  
  • Query Planning & Optimization I
  
  
  • Query Planning & Optimization II
  
  
  
  

Blogs:

• 数据库内核杂谈, thanks to 顾仲贤
  
  
  • 数据库内核杂谈（七）：数据库优化器（上）
  
  
  • 数据库内核杂谈（八）：数据库优化器（下）
  
  
  
  


• SQL优化器原理 - 查询优化器综述, thanks to 勿烦

Planner Models

Blogs:

• 数据库内核杂谈, thanks to 顾仲贤
  
  
  • 数据库内核杂谈（九）：开源优化器 ORCA
  
  
  
  


• SQL 查询优化原理与 Volcano Optimizer 介绍, thanks to 张茄子


• Cascades Optimizer, thanks to hellocode

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:

• SQL 子查询的优化, thanks to Eric Fu


• Calcite 子查询处理 - I (RemoveSubQuery), thanks to 一只无情的小猫咪


• Calcite 子查询处理 - II (Decorrelate), thanks to 一只无情的小猫咪

Papers:

• 2001, Orthogonal Optimization of Subqueries and Aggregation, SIGMOD


• 2009, Enhanced subquery optimizations in Oracle, VLDB


• 2015, Unnesting Arbitrary Queries, BTW

Join Order Optimization

Papers:

• 2006, Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products, VLDB


• 2015, How Good Are Query Optimizers, Really?, VLDB


• 2018, Adaptive Optimization of Very Large Join Queries, SIGMOD

Functional Dependency & Physical Properties

Thesis:

• 2000, Exploiting Functional Dependence in Query Optimization

Papers:

• 1996, Fundamental Techniques for Order Optimization, SIGMOD


• 2004, An Efficient Framework for Order Optimization, ICDE


• 2010, Incorporating Partitioning and Parallel Plans into the SCOPE Optimizer, ICDE

Cost Model

Papers:

• 1996, Modelling Costs for a MM-DBMS, in Real-Time Databases


• 2014, Approximation Schemes for Many-Objective Query Optimization, SIGMOD


• 2015, Multi-Objective Parametric Query Optimization, VLDB

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:
- Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches

Query Execution

Courses:

• CMU Database Systems (15-445/645), thanks to Andy Pavlo
  
  
  • Query Execution I
  
  
  • Query Execution II
  
  
  
  

Execution Framework

Papers:

• 1994, Volcano-An Extensible and Parallel Query Evaluation System, IEEE Transactions on Knowledge and Data EngineeringFebruary


• 2014, Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age, SIGMOD

Vectorization vs Compilization

Blogs:

• Overhead of a Generalized Query Execution Engine, from The Pivotal Engineering Journal, thanks to the Pivotal Engineering team

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:

• 2013, Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited, VLDB


• 2017, Looking Ahead Makes Query Plans Robust, VLDB

Hash Table

Courses:

• CMU Database Systems (15-445/645), thanks to Andy Pavlo
  
  
  • Hash Tables
  
  
  
  

Blogs:

• Fibonacci Hashing: The Optimization that the World Forgot (or: a Better Alternative to Integer Modulo), thanks to Malte Skarupke


• All hash table sizes you will ever need, thanks to Database Architects - Thomas Neumann

Bloom Filter

Papers:
- 2018, SuRF: Practical Range Query Filtering with Fast Succinct Tries, SIGMOD

DDL

• 2013, Online, Asynchronous Schema Change in F1, VLDB

Relational Model

Blogs:

• What is a Relational Database?, thanks to Caleb Curry


• What is a Relational Database?,thank to JAMES GALLAGHER

Codd's Rules

Blogs:

• Codd’s Rules for Relational Database Systems, thanks to Kevin Kline

Relational Data Model

Blogs:

• Relational model, thanks to Wikipedia

Relational Algebra

Blogs:

• Introduction of Relational Algebra in DBMS, thanks to GeeksforGeeks

ER to Relational Model

Blogs:

• ER Model to Relational Model, thanks to tutorialspoint

SQL - Overview

Blogs:

• An Overview of SQL Text Functions, thanks to Zahin Rahman

Transaction
Isolation Levels

Blogs:

• 一致性模型, thanks to siddontang

Papers:

• 1995, A Critique of ANSI SQL Isolation Levels, SIGMOD


• 2000, Generalized Isolation Level Definitions, Proceedings of 16th International Conference on Data Engineering

Concurrency Control

Courses:

• 
  

  CMU Database Systems (15-445/645), thanks to Andy Pavlo

  
  
  
  
  • Concurrency Control Theory
  
  
  • Two-Phase Locking Concurrency Control
  
  
  • Timestamp Ordering Concurrency Control
  
  
  • Multi-Version Concurrency Control
  
  
  
  


• 
  

  CMU Advanced Database Systems (15-721), thanks to Andy Pavlo

  
  
  
  
  • Multi-Version Concurrency Control (Design Decisions)
  
  
  • Multi-Version Concurrency Control (Protocols)
  
  
  • Multi-Version Concurrency Control (Garbage Collection)
  
  
  
  

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:

• CMU Advanced Database Systems (15-721), thanks to Andy Pavlo
  
  
  • Networking Protocols
  
  
  
  

Papers:

• 2016, The End of Slow Networks: It's Time for a Redesign, VLDB


• 2016, Accelerating Relational Databases by Leveraging Remote Memory and RDMA, SIGMOD


• 2017, Don't Hold My Data Hostage: A Case for Client Protocol Redesign, VLDB

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:

• CMU Database Systems (15-445/645), thanks to Andy Pavlo
  
  
  • Buffer Pools
  
  
  
  

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:

• 2016, Design Tradeoffs of Data Access Methods, SIGMOD


• 2016, Designing Access Methods: The RUM Conjecture, EDBT

B-Tree

Blogs:

• B树、B+树索引算法原理（上） thanks to codedump


• B树、B+树索引算法原理（下）

Courses:

• 
  

  CMU Database Systems (15-445/645), thanks to Andy Pavlo

  
  
  
  
  • Trees Indexes I
  
  
  • Trees Indexes II
  
  
  
  


• 
  

  CMU Advanced Database Systems (15-721), thanks to Andy Pavlo

  
  
  
  
  • OLTP Indexes (B+Tree Data Structures)
  
  
  
  

Papers:

• 1979, The Ubiquitous B-Tree

LSM-Tree

Papers:

• 1996, The Log-Structured Merge-Tree (LSM-Tree),


• 2014, A Comparison of Fractal Trees to Log-Structured Merge (LSM) Trees


• 2017, WiscKey: Separating Keys from Values in SSD-conscious Storage, TOS


• 2019, LSM-based Storage Techniques: A Survey

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, [email protected]


• 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

• Protocol Buffers Developer Guide


• gRPC Documntation

Data Partitioning

Blogs:

• TiDB Internal (I) - Data Storage


• Partitioning Behavior of DynamoDB, thanks to Parth Modi

Papers:

• 2007, Dynamo: Amazon’s Highly Available Key-value Store, SOSP

Replication & Consistency

Blogs:

• Tick or Tock? Keeping Time and Order in Distributed Databases, thanks to Liu Tang

Papers:

• 2012, Consistency Tradeoffs in Modern Distributed Database System Design


• 2020, Strong and Efficient Consistency with Consistency-Aware Durability , FAST 2020

Consensus

Technical report:

• University of Cambridge Distributed consensus revised, a great paper about Consenssus especially Paxos and Paxos-Related algorithms, by Heidi Howard

Papers:

• 2014, Ark: A Real-World Consensus Implementation, CoRR

Scheduling

Blogs:

• Building a Large-scale Distributed Storage System Based on Raft, by Ed Huang

Papers:

• 2016, Automated Demand-driven Resource Scaling in Relational Database-as-a-Service, SIGMOD


• 2019, Autoscaling Tiered Cloud Storage in Anna, VLDB


• 2020, Adaptive HTAP through Elastic Resource Scheduling, SIGMOD


• 2020, MorphoSys: Automatic Physical Design Metamorphosis for Distributed Database Systems, VLDB

Benchmark & Testing

Blogs:

• Use go-ycsb to benchmark different databases (1), thanks to siddontang


• Chaos Tools and Techniques for Testing the TiDB Distributed NewSQL Database, thanks to Liu Tang


• Creating Custom Sysbench Scripts, thanks to Matthew Boehm

Papers:

• 2010, Benchmarking Cloud Serving Systems with YCSB, SOCC

HTAP

Papers:

• 2020, TiDB: A Raft-based HTAP Database, VLDB


• 2020, F1 Lightning: HTAP as a Service, VLDB

TLA+

Talks:
- The TLA+ Video Course