What we read, and how it fits together

Starts from all single-column indexes and repeatedly drops the one whose removal hurts least. Presented in 1985, published in 1987.

Index selection in relational databases — Whang, Foundations of Data Organization 1985

Introduced the what-if optimiser call: per-query candidate selection, Greedy(m, k) enumeration, and multi-column indexes built up one column at a time.

An efficient, cost-driven index selection tool for Microsoft SQL Server — Chaudhuri & Narasayya, VLDB 1997

Lets the optimiser plan each query with virtual indexes, credits the gain to the indexes used, solves a knapsack by benefit per byte, then tries random swaps.

DB2 Advisor: An Optimizer Smart Enough to Recommend Its Own Indexes — Valentin et al., ICDE 2000

Extends AutoAdmin to choose indexes and materialised views together, the basis of SQL Server's tuning advisor.

Automated Selection of Materialized Views and Indexes for SQL Databases — Agrawal, Chaudhuri & Narasayya, VLDB 2000

White-box models that predict how an OLTP system responds to resource changes such as a larger buffer pool.

Continuous resource monitoring for self-predicting DBMS — Narayanan, Thereska & Ailamaki, MASCOTS 2005

Online index tuning that profiles candidate indexes as queries arrive and adjusts the physical design continuously.

COLT: continuous on-line tuning — Schnaitter et al., SIGMOD (demo) 2006

Treats the workload as a sequence and picks when to apply each design change, merging per-step recommendations greedily.

Automatic physical design tuning: workload as a sequence — Agrawal, Chu & Narasayya, SIGMOD 2006

Keeps adjusting indexes in response to the running workload, using execution statistics to pick candidates.

An Online Approach to Physical Design Tuning — Bruno & Chaudhuri, ICDE 2007

Predicts the latency of analytical queries running concurrently from their buffer-access behaviour.

Performance prediction for concurrent database workloads — Duggan et al., SIGMOD 2011

Formulates index selection as a binary integer program over cached plan costs and hands it to a solver; quality depends on how far the solver gets.

CoPhy: A Scalable, Portable, and Interactive Index Advisor for Large Workloads — Dash, Polyzotis & Ailamaki, PVLDB 2011

Models how analytical queries in a batch interfere with each other, then simulates the batch to predict its completion time.

Predicting completion times of batch query workloads using interaction-aware models and simulation — Ahmad et al., EDBT 2011

Clusters transaction types and predicts disk I/O, CPU and lock contention for what-if workload changes; tied to MySQL.

Performance and resource modeling in highly-concurrent OLTP workloads — Mozafari et al., SIGMOD 2013

Explains performance anomalies to a DBA with predicates over system metrics and causal models.

DBSherlock: A Performance Diagnostic Tool for Transactional Databases — Yoon, Niu & Mozafari, SIGMOD 2016

Groups queries by template, creates hypothetical indexes with HypoPG and keeps those the planner says reduce cost.

Dexter: the automatic indexer for Postgres — Andrew Kane, Open source 2017

Recommends knob settings by mapping a new workload onto past ones and running Bayesian optimisation.

Automatic Database Management System Tuning Through Large-scale Machine Learning — Van Aken et al., SIGMOD 2017

The paper that named the field: a DBMS designed from the start to forecast its workload and apply tuning actions without a DBA.

Self-Driving Database Management Systems — Pavlo et al., CIDR 2017

Templatises queries, clusters templates by arrival-rate history, and forecasts each cluster with linear regression, an LSTM and kernel regression (the HYBRID model catches rare spikes).

Query-based Workload Forecasting for Self-Driving Database Management Systems — Ma et al., SIGMOD 2018

Runs index tuning as a cloud service, validating every change against production performance and reverting regressions.

Automatically Indexing Millions of Databases in Microsoft Azure SQL Database — Das et al., SIGMOD 2019

A vision for a query optimiser trained end to end with deep reinforcement learning instead of hand-written cost models.

Towards a Hands-Free Query Optimizer through Deep Learning — Marcus & Papaemmanouil, CIDR 2019

A neural network shaped like the query plan, with one small network per operator, predicts query latency.

Plan-Structured Deep Neural Network Models for Query Performance Prediction — Marcus & Papaemmanouil, PVLDB 2019

Featurises the incoming queries and tunes knobs with deep reinforcement learning.

QTune: A Query-Aware Database Tuning System with Deep Reinforcement Learning — Li et al., PVLDB 2019

SQL Server's tuning advisor as an anytime algorithm: it returns the best configuration found within a time limit.

Anytime Algorithm of Database Tuning Advisor for Microsoft SQL Server — Chaudhuri & Narasayya, Microsoft Research 2020

Encodes concurrently running operators and their interactions as a graph and learns to predict latency from it.

Query Performance Prediction for Concurrent Queries using Graph Embedding — Zhou et al., PVLDB 2020

Re-implements eight index selection algorithms on one platform and compares their quality, runtime and what-if calls on TPC-H, TPC-DS and JOB.

Magic Mirror in My Hand, Which is the Best in the Land? An Experimental Evaluation of Index Selection Algorithms — Kossmann et al., PVLDB 2020

A component framework: a workload predictor feeds tuners for each feature (indexes, knobs, ...), and an organiser decides which tuning to apply and when.

Self-driving database systems: a conceptual approach — Kossmann & Schlosser, DAPD 2020

The conference version of the MAB tuner: C²UCB over workload-generated index arms, learning from observed runtimes.

DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads with safety guarantees — Perera et al., ICDE 2021

Brings QB5000, ModelBot2 and PilotBot0 together into one pipeline; the backbone of our workload-driven optimisation section.

Self-Driving Database Management Systems: Forecasting, Modeling, and Planning — Lin Ma, PhD thesis, CMU 2021

Splits the DBMS into small operating units, trains a model per unit from runner data, and combines them to predict the cost and impact of any candidate action.

MB2: Decomposed Behavior Modeling for Self-Driving Database Management Systems — Ma et al., SIGMOD 2021

Implementation lessons from NoisePage and the six levels of DBMS autonomy, from manual (0) to fully self-driving (5).

Make Your Database System Dream of Electric Sheep: Towards Self-Driving Operation — Pavlo et al., PVLDB 2021

Plans a sequence of actions over a receding horizon with Monte Carlo tree search, using forecasts and behaviour models, and applies the first action each time.

Self-Driving Database Management Systems: Forecasting, Modeling, and Planning — Lin Ma, PhD thesis, CMU 2021

Tunes transaction code, physical design and parameters together with reinforcement learning and Monte Carlo tree search.

UDO: Universal Database Optimization using Reinforcement Learning — Wang, Trummer & Basu, PVLDB 2021

When what-if calls are rationed, spends them with Monte Carlo tree search over configurations instead of greedy enumeration.

Budget-aware Index Tuning with Reinforcement Learning — Wu et al., SIGMOD 2022

Correction: The 2023 report credited this paper to “Yuhao Zhang and Tim Kraska”. It is by Wentao Wu, Chi Wang, Tarique Siddiqui, Junxiong Wang, Vivek Narasayya, Surajit Chaudhuri and Philip A. Bernstein (Microsoft Research and Cornell).

Extends DBA bandits to HTAP workloads with a corrected regret proof and focused updates; beats a commercial tuning tool on dynamic and random workloads.

No DBA? No regret! Multi-armed bandits for index tuning of analytical and HTAP workloads with provable guarantees — Perera, Oetomo, Rubinstein & Borovica-Gajic, IEEE TKDE 2023

Correction: The 2023 report credited this paper to “Tim Kraska et al.” (SIGMOD 2022). It is by R. Malinga Perera, Bastian Oetomo, Benjamin Rubinstein and Renata Borovica-Gajic (University of Melbourne), IEEE TKDE 2023.