Skip to content
Self-Driving DB LabCOMP90050 · G40

COMP90050 · Group 40 · 2023 Winter term

How databases learn to tune themselves.

In 2023 our group surveyed self-driving databases — systems that forecast their own workload and choose their own indexes. This lab rebuilds the survey as something you can run: five index advisors from 1985 to 2023 compete on a live SQLite database inside your browser.

Open the advisor arena Browse the survey map Watch the tour
index advisors, 1985–2023
5index advisors, 1985–2023
references in our report
21references in our report
datasets, incl. the INFO20003 Louvre
2datasets, incl. the INFO20003 Louvre
servers needed
0servers needed
sqlite 3.49 · wasm · round 4 of 25
sqlite> EXPLAIN QUERY PLAN
 ...> SELECT COUNT(*), SUM(l_quantity)
 ...> FROM lineitem WHERE l_partkey = 742;
`--SCAN lineitem                    1.62 ms

-- MAB · C²UCB picks arm lineitem(l_partkey, l_quantity)
-- θᵀx = 4.81 + α√(xᵀV⁻¹x) = 0.37
sqlite> CREATE INDEX ix_lineitem__l_partkey__l_quantity
 ...> ON lineitem (l_partkey, l_quantity);   18.4 ms

`--SEARCH lineitem USING COVERING INDEX
     ix_lineitem__l_partkey__l_quantity (l_partkey=?)  0.03 ms
Illustration of one arena round. Real runs print their own plans and timings.

The coursework

A survey, a talk, and now a lab

COMP90050 asked groups of four to survey a hot topic in databases — not an annotated bibliography, but a categorisation and critique of the main approaches — in a 10–16 page report and a 25-minute talk. Group 40 chose self-driving databases and split the work in two: index selection, and workload-driven optimisation.

What the brief asked

Find the key papers, group them into families, explain how each extends the last, compare their strengths and limits, and reflect on the process. At least two papers had to be from 2021 or later.

What we argued in 2023

Index selection moved from heuristics to constraint programming to machine learning; learned tuners recommend far faster than commercial tools, but results are hard to compare because every paper benchmarks differently.

What the lab adds

The algorithms the survey described, implemented and racing on one engine with one stopwatch — so the comparison we said was missing can finally be run, by anyone, in a browser tab.

  1. Group formed and topic submitted (Self-driving databases)
  2. Report draft completed
  3. Group presentation delivered
  4. Report due

Explainer

From level 0 to self-driving, in seven steps

Scroll through the survey's argument. The diagram follows along.

Level 0

A database that does nothing on its own

Every index, memory setting and partition is chosen by a database administrator, usually after something has already gone slow. Pavlo et al. call this level 0: manual. Most production systems in 2023 still lived here for physical design.

  1. 5Self-drivingThe system is fully autonomous.
  2. 4DirectedThe system is semi-autonomous.
  3. 3LocalSelf-contained components act on their own.
  4. 2MixedThe system acts, and alerts the user when a decision is needed.
  5. 1AssistantThe system recommends promising actions to the user.
  6. 0ManualThe system has no autonomy.

Levels 1–2

Advisors that recommend, people who decide

Tools such as AutoAdmin (1997) and DB2 Advisor (2000) ask the optimiser what if an index existed, then recommend a set. A DBA still picks the workload to tune for and when to apply the change — levels 1 and 2 on the autonomy ladder.

  1. 5Self-drivingThe system is fully autonomous.
  2. 4DirectedThe system is semi-autonomous.
  3. 3LocalSelf-contained components act on their own.
  4. 2MixedThe system acts, and alerts the user when a decision is needed.
  5. 1AssistantThe system recommends promising actions to the user.
  6. 0ManualThe system has no autonomy.

Levels 3–5

Components that act, then a system that drives

A self-driving DBMS removes the human from the loop: it anticipates the workload, chooses actions, applies them at the right moment and learns from what happened. Level 5 is fully autonomous; our survey asked how far index selection and workload-driven optimisation had got.

  1. 5Self-drivingThe system is fully autonomous.
  2. 4DirectedThe system is semi-autonomous.
  3. 3LocalSelf-contained components act on their own.
  4. 2MixedThe system acts, and alerts the user when a decision is needed.
  5. 1AssistantThe system recommends promising actions to the user.
  6. 0ManualThe system has no autonomy.

Predictor

First, guess what is coming

Kossmann and Schlosser split a self-driving system into a predictor, tuners and an organiser. The predictor forecasts the workload: QueryBot 5000 turns queries into templates, clusters templates that rise and fall together, and forecasts each cluster. You can run that pipeline on the forecasting page.

  1. incoming queries
  2. Workload predictortemplatise → cluster → forecast arrival ratesQB5000 · LR, LSTM, kernel regression
  3. Tunerswhat to changeindex advisors · knob tuners · MB2
  4. Organiserwhen and in what orderreceding-horizon planning · PilotBot0
  5. DBMS↺ observed runtimes feed back (the bandit's reward)

Tuners

Then decide what to change

Tuners turn the forecast into candidate actions — build this index, resize that buffer — and behaviour models such as ModelBot2 estimate what each action would cost and save. Index advisors are tuners; so are knob tuners such as OtterTune.

  1. incoming queries
  2. Workload predictortemplatise → cluster → forecast arrival ratesQB5000 · LR, LSTM, kernel regression
  3. Tunerswhat to changeindex advisors · knob tuners · MB2
  4. Organiserwhen and in what orderreceding-horizon planning · PilotBot0
  5. DBMS↺ observed runtimes feed back (the bandit's reward)

Organiser

And when to change it

Building an index takes time and storage, so the organiser schedules actions ahead of demand. PilotBot0 plans over a receding horizon with Monte Carlo tree search. Online tuners close the loop the other way: the multi-armed bandit learns only from runtimes it actually observed.

  1. incoming queries
  2. Workload predictortemplatise → cluster → forecast arrival ratesQB5000 · LR, LSTM, kernel regression
  3. Tunerswhat to changeindex advisors · knob tuners · MB2
  4. Organiserwhen and in what orderreceding-horizon planning · PilotBot0
  5. DBMS↺ observed runtimes feed back (the bandit's reward)

Index selection

Enumerate, select, explore

Whatever the era, index advisors follow the same three steps: enumerate candidate indexes from the workload, prune them to the promising ones, then explore configurations under a storage budget. The numbers on the right are AutoAdmin running on this lab's own twelve-query workload.

  1. 01Enumerate42

    syntactically relevant indexes from the workload's predicates

  2. 02Select17

    candidates that win for at least one query on their own

  3. 03Explore8

    indexes kept by Greedy(2, k) under the budget, after 2,778 what-if calls

Forty years of index selection

Heuristics, then solvers, then learners

Our report followed Kossmann et al.'s timeline: greedy heuristics first, then integer programming, then machine learning. Five of them run in the arena; the About page lists where each port departs from its paper.

  1. 1985in the arena

    DROP

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

    Whang · Foundations of Data Organization

  2. 1997in the arena

    AutoAdmin

    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.

    Chaudhuri & Narasayya · VLDB

  3. 2000in the arena

    DB2 Advisor

    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.

    Valentin et al. · ICDE

  4. 2011in the arena

    CoPhy

    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.

    Dash, Polyzotis & Ailamaki · PVLDB

  5. 2017Open source

    Dexter

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

    Andrew Kane · Open source

  6. 2018Forecasting

    QueryBot 5000

    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).

    Ma et al. · SIGMOD

  7. 2021in the arena

    DBA bandits

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

    Perera et al. · ICDE

  8. 2022Reinforcement learning

    Budget-aware MCTS

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

    Wu et al. · SIGMOD

Key result we reported

Bandits beat a commercial tuner, mostly

The report's Table 2 reproduced Perera et al.'s comparison of a multi-armed bandit (MAB) with a commercial physical design tool (PDTool) on TPC-H and TPC-DS. The bandit never spent more than 1.7 minutes recommending (the tool needed up to 310) and finished 5 of 6 workloads sooner, taking up to 61% less time on TPC-DS random. The commercial tool still won static TPC-H, the setting offline tools are designed for.

TPC-H

StaticMAB +24%

TPC-H Static: total workload time, PDTool vs MAB (minutes)
RowQuery executionIndex creationRecommendationTotal
PDTool46.4 min2.5 min0.6 min49.4 min
MAB55.6 min5.7 min0.1 min61.4 min

DynamicMAB -6%

TPC-H Dynamic: total workload time, PDTool vs MAB (minutes)
RowQuery executionIndex creationRecommendationTotal
PDTool26.4 min9.4 min1.6 min37.3 min
MAB25.1 min9.7 min0.1 min35.0 min

RandomMAB -18%

TPC-H Random: total workload time, PDTool vs MAB (minutes)
RowQuery executionIndex creationRecommendationTotal
PDTool84.1 min14.7 min7.5 min106 min
MAB80.4 min7.1 min0.1 min87.6 min

TPC-DS

StaticMAB -28%

TPC-DS Static: total workload time, PDTool vs MAB (minutes)
RowQuery executionIndex creationRecommendationTotal
PDTool303 min1.4 min44.9 min349 min
MAB242 min5.9 min1.5 min250 min

DynamicMAB -15%

TPC-DS Dynamic: total workload time, PDTool vs MAB (minutes)
RowQuery executionIndex creationRecommendationTotal
PDTool187 min6.1 min11.1 min204 min
MAB156 min16.5 min1.7 min174 min

RandomMAB -61%

TPC-DS Random: total workload time, PDTool vs MAB (minutes)
RowQuery executionIndex creationRecommendationTotal
PDTool324 min8.2 min310 min642 min
MAB227 min19.8 min1.4 min248 min

Minutes, from Perera et al., IEEE TKDE 2023, as tabulated in our report. The report attributed this paper to Kraska et al.; the survey map lists the correction.

Explore

Five ways in

Advisor arenaRace DROP, AutoAdmin, DB2 Advisor, CoPhy and a C²UCB bandit on a live SQLite database.Open BenchmarkRepeated seeded runs with 95% intervals, paired comparisons, the bandit's regret, a drift sweep and a BYOK LLM advisor.Open Forecasting labQB5000's templatise–cluster–forecast pipeline, feeding an index tuner ahead of demand.Open SQL consoleQuery the synthetic TPC-H data, add indexes, and read SQLite's plan next to the what-if estimate.Open Survey mapEvery system we covered, filterable by technique, component, venue and year, with corrected citations.Open

Database journey

One Louvre database, from design to self-tuning

In 2020 Sunchuangyu (Rin) Huang designed this database for an individual INFO20003 assignment. In 2023, COMP90050 taught what a database does with a design once it runs. The arena now loads the INFO20003 file byte for byte and lets the survey's index advisors, and your own LLM if you bring a key, tune it.

  1. 2020Semester 1

    INFO20003 Database Systems

    Design the database

    A ticketing and visitor database for the Louvre, designed from a written brief: who buys what, which entrance and wing a ticket passes, audio guides, timed exhibition slots.

    • Conceptual ER model (Chen)
    • Crow's foot physical model
    • Relational schema
    • SQL

  2. 2023Winter term

    COMP90050 Advanced Database Systems

    Make it run well, on its own

    What happens after design: how rows are stored, how indexes and the optimiser decide a query's cost, and how a self-driving database chooses its own indexes.

    • Storage
    • Indexing
    • Query optimisation
    • Self-driving index selection
Tune the Louvre in the arena Benchmark itThe 2020 design: Louvre Ops DB Its ER diagrams

Shared file: louvre.db · 19 tables · about 66,000 synthetic rows · SHA-256 b762146e2601… · why the arena drops its indexes (DR-004)

About this project

COMP90050 Advanced Database Systems

The University of Melbourne · 2023 Winter term · Group 40

Team, stack and academic-integrity note

  • Sunchuangyu (Rin) Huang

    Index selection

  • Runqiu Fei

    Index selection

  • Xiaoyi Liu

    Workload-driven optimisation

  • Qingxuan Yang

    Workload-driven optimisation