Physical database designtuning
Reaching the holy grail of performanceguarantees
Renata Borovica-Gajic
Work supported by:Physical design (PD) tuning is hard

[VLDBJ’18, ICDE’15, DBTest’12]

Setting: TPC-H, SF10, DBMS-X, Tuning tool 5GB space for indexes

100

Tuned
With indexes
Original
Without indexes

400

1010.1

Q1
Q2
Q3
Q4
Q5
Q6
Q7
Q8
Q9
Q10
Q11
Q12
Q13
Q14
Q16
Q18
Q19
Q21
Q22

Normalized exec. time(log scale)

1000

TPC-H Query

And results can be unpredictable[VLDBJ’18] Smooth Scan: Robust Access Path Selection without Cardinality Estimation.
R. Borovica-Gajic, S. Idreos, A. Ailamaki, M. Zukowski and C. Fraser.

2

Cause for sub-optimal plans
Cardinality errors
Estimated: … Actual:
3.2M
192K
Nestedloop join
Estimated: Actual:
Table
108K
6K
lookup
Index
Table
scan
scan
LineitemPart

Cost model…

Estimated: Actual:
305K
298K
Table
lookup
Index
scan
PartPart

Lineitem

Order of magnitude more tuples

Wrong decision of cost model

Optimizer’s mistakes -> hurt predictability

3Physical design tuning under looking glass

DBAWorkloads
ad hocEstimates
unreliableRepresentative
Workload“What if”

Recommended
Physical design

PhysicalDesign
Tool

Estimatedbenefit

Broken pipeline….

DBMSQueryOptimizer

4

Status quo: untenable for modern applications

Properties:• Ever growing data
• Ad hoc data exploration• Multi-tenancy

Challenges:• Complex optimization problems• Analytical models failLearning algorithms to the rescue
Photos credit: Bloomberg, Stock market°, Atlas experiment, CERN*, Strato Data Centre, cloudˆ6

Embarking the (M) learning train…

8

Multi-armed bandits (MAB) for PD tuning••••Pull an arm (slot machine) observe a reward (win/lose)
Explore vs exploit
Find a sequence of arms to maximize reward
Many variants, but C2UCB most interesting

Optimism in the face of uncertainty

9Index tuning with MAB (C2UCB)[ICDE’21]

Observe
Workload

DBA

MAB“What if” DBMS
Try arms (index)
Query
Estimated
Recommended Observe reward benefit Optimizerindexes• UCB guarantees to converge to optimal policy• C (contextual) learns benefit of arms without pulling them
• C (combinatorial) pulls a set of arms per round given constraints[ICDE’21] DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads withsafety guarantees. M. Perera, B. Oetomo, B. Rubinstein, and R. Borovica-Gajic.

Safety guarantees with fast convergence11

MAB under looking glass…
SELECT A.C1 FROM A
WHERE A.C2 = 5 AND
A.C3 = 6(5)Returning
Query(1) New
Query[ICDE’21]Arms
IX1(Learns) 10sec gain, 20sec
creation time, 30MB size

IX2(3) Identify Arms

(2) Query details &Execution time before
tunning

Bandit tuner(6) Creation time, Execution time
w/ Index

IX6IX7(4) Materialize IX6Automated tuning with provable guarantees[ICDE’21] DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads withsafety guarantees. M. Perera, B. Oetomo, B. Rubinstein, and R. Borovica-Gajic.

12

MAB to the rescue
Normalized execution time

Setting: TPC-H, SF10, DBMS-X, Multi-armed bandits (MAB) for index tuning
1.2

MAB
Series1_ Without indexes

10.8
0.6
0.4
0.2
0Q22Q21
Q20Q19Q18Q17Q16Q15Q13Q12Q11Q10Q9Q8Q7Q6Q5Q4Q3Q2Q1

TPCH Query

3x Speed up vs. previous 22x slowdown

13MAB in action[ICDE’21]

Setting: TPCH, TPCH skew, TPC DS, SSB (10GB); IMDb(6GB) datasets
static (repetitive) vs random (ad hoc) queries, MAB vs PDTool, 25 rounds
4035302520151050

STATICNo Index
PD Tool
MAB

SSB

TPC-H TPC-H TPC-DS IMDb
Skew

Thousands

Total Workload Time (sec)

Total Workload Time (sec)Thousands

454035302520151050SSBAD HOC

TPC-H TPC-H TPC-DS IMDb
SkewWorkload

MAB robust against complex unpredictable workloads
and skew

15

MAB in action: Zoom in TPC-DS [ICDE’21]

Setting: TPC-DS, static vs ad hoc queries, MAB vs PDTool, 25 rounds
4000

AD HOC
NoIndex

3500

PDTool

3000

MAB

2500
2000
1500
1000
500
05000

Total Time Per Round (sec)

Total Time Per Round (sec)

STATIC
4500
4000
3500
3000
2500
2000
1500
1000
500
005101520

Round Number

250510152025

Round Number

Lightweight, yet efficient16Choosing a right tool for the job is key

Why not (general) RL[ICDE’21]

PDToolDDQN

MAB
DDQN_SC (NoDBA)*Total Time Per Round(sec)

Setting: TPC-H Skew 10GB, 100 rounds static
1000900
80070060050040030020010000204060

Round Number80100*NoDBA: [ArXiv’18] The case for automatic database administration using deep
reinforcement learning. A. Sharma, F. M. Schuhknecht, and J. Dittrich

Faster convergence, less variance with MAB

18

X

MAB for Index Tuning: An Example
Physical Design

SELECT A.C1 FROM A
WHERE A.C2 = 5 AND
A.C3 = 6(5)ReturningQuery(1) NewQueryArms
IX1(Learns) 10sec gain, 20sec
creation time, 30MB size

IX2(3) Identify Arms

(2) Query details &Execution time before
tunning

Bandit tuner(6) Creation time, Execution time w/Index

MV1MV2(4) Materialize IX6Design too complex, too large action space19

HMAB - Hierarchical Bandit Architecture[VLDB’22]
L1 Bandits
Bandit for
Table A
Bandit for
Table B

L2Bandit

Physical Design
Configuration

Bandit forMVs

Smallerbandits
forfasterconvergence[VLDB’22] HMAB: Self-Driving Hierarchy of Bandits for Integrated Physical Database Design
Tuning. M. Knowledge
Perera, B. Oetomo, B. Rubinstein,and via
R. Borovica-Gajic.
sharing
central bandit

20

HMAB with contexts[VLDB’22]

21

HMAB in Action[VLDB’22]

20

NoIndex
PDToolHMAB

NoIndex
PDToolHMAB

0NoIndex
PDToolHMAB

10TPC-H

TPC-H
Skew

TPC-DS

IMDb

800
600

2914.41

4002000

NoIndex
PDTool
HMAB

30~

NoIndex
PDToolHMAB

40

Random1000

NoIndex
PDToolHMAB

StaticNoIndex
PDTool
HMAB

50

Total Workload Time (min)Thousands

NoIndex
PDTool
HMAB

Total Workload Time (sec)

Setting: TPCH, TPCH skew, TPC DS, IMDb datasets; static (repetitive) vs random (adhoc) queries, MAB vs PDTool, 25 rounds, tuning indices and materialised views

TPC-H

TPC-H TPC-DSSkewIMDb

Up to 96% speed-up, and 67% on average

22Index Only Tuning[VLDB’22][ICDE’21]
DBA Bandits[VLDB’20]
Magic Mirror

Outperforming baselines over a single DS as well

[ICDE’21] DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads with safety guarantees[VLDB’20] Magic mirror in my hand, which is the best in the land? an experimental evaluation of24index selection algorithms. J. Kossmann, S. Halfpap, M. Jankrift, and R. Schlosser.

Dealing with complexity (HTAP)No DBA? No regret! …
[TKDE’23]
Setting: CH-BenCHmark under static workloads, MAB vs. PDTool, 25 rounds
12000
10000
8000
6000
4000
2000
NoIndexMAB

PDToolNoIndexMAB

PDToolNoIndex
MAB

0
PDToolTotal Workload Time (sec)

14000

0:1

1:1

2:1

3:1

4:1

5:1

Transactional to Analytical Ratio (TAR)

MAB with focused updates to support HTAP[TKDE’23] No DBA? No regret! Multi-armed bandits for index tuning of analytical and HTAP
workloads with provable guarantees. M. Perera, B. Oetomo, B. Rubinstein, R. Borovica-Gajic. 25

But isn’t exploration too expensive?

Cutting to the chase with warm bandits

Time per round (sec)

Setting: TPC-H benchmark 10GB, 5 queries, 25 rounds static[ICDM’21]

100

cold start
warm start

95
90
85
80
75

15

9

13

17

21

25

Round
[ICDM’21] Cutting to the Chase with Warm-Start Contextual Bandits. B. Oetomo, M. Perera,
B. Rubinstein, and R. Borovica-Gajic.
26(Inexpensive) warm up reduces exploration costSummary• (H)MAB is a lightweight MAB solution for (integrated)
physical database design tuning• HMAB is the first learned solution to work in the
combined space of indices and views• (H)MAB successfully tackles tuning challenges: optimizer
misestimates, unpredictable and HTAP workloads• Up to 40% and 70% average improvement for integrated
view and index tuning under static and random settingscompared against a SOTA commercial tuning tool29

Critical view on learning-based algorithms

This is great, but……

(Relatively) slow uptake by commercial vendors...

30

Properties for future DBMS adoption• Small computational overhead— Pre-training important, yet often ignored— Resources plus time invested• Ability to adapt and generalize— See the past, adjust to unpredictable future— Train on development port to product environment— Transfer learning critical• Safety guarantees required— Prove it does the right thing— Explain the output (decisions made)Lightweight, yet (provably) accurate is key31

Numerous opportunities for innovation• ML within the DB Engine– Physical database design– Learned vs traditional data structures– Configuration tuning– Resource management– Query optimization• Innovation in ML domain– Hierarchical MABs (infinite arms)– Pretraining for faster convergence (warm start)– Lightweight transfer learning

Plus, the entire field DBs for ML!

32

Where to go from here
“It is not the strongest species that survive, nor the most intelligent, but the ones
most responsive to change.” Charles Darwin

Queries[SIGMOD’12][CACM’15][ICDE’21][ICDM’21][VLDB’23][TKDE’23]

Data[ICDE’15][VLDBJ’18][ADC’20][SIGMOD’23][ICDE’24][VLDB’24]

Hardware[VLDB’16][ADMS’17][CACM’19]

Learn
AdaptRefine

Fast response

DBMS System

Learning DBMSs for efficient data analysis

33

Questions?
Website: https://renata.borovica-gajic.com/
Email: renata.borovica@unimelb.edu.au

Looking for PhD students!

Malinga
PereraBastianOetomo*This work is supported by the Australian Research Council
Discovery Project DP220102269, and Discovery Early
Career Researcher Award DE230100366.

Ben
Rubinstein

THANK YOU!

34

Backup slides

35

Rewards that guide MAB

36

MABs don’t need to try all arms

37

MAB with context

38

HTAP: positive + negative rewards

39

HTAP: Focused updates40

HMAB with contexts

41Materialised View Only Tuning
Exec. Time Per Round (sec)

Setting: TPC-H, static, MAB vs ICDE’21* baselines, 25 rounds, tuning
materialised views
400

PDToolHMABTopValueTopUValue

350
300
250
200
150
100
50051015

Round Number

2025*[ICDE’21] An Autonomous Materialized View Management System with Deep Reinforcement Learning.
42Y. Han, G. Li, H. Yuan, and J. Sun.