# No DBA? No regret! Multi-armed bandits for index tuning of analytical and HTAP workloads with provable guarantees

arXiv: https://arxiv.org/abs/2108.10130 · HTML: https://mlsanity.com/paper/2108.10130/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 82 references that are in the map.
- First posted on arXiv 23 Aug 2021.

## Builds on (most cited first, 11 of 11)

- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Learned Cardinalities: Estimating Correlated Joins with Deep Learning](https://mlsanity.com/paper/1809.00677/) (2018)
- [Bao: Learning to Steer Query Optimizers](https://mlsanity.com/paper/2004.03814/) (2020)
- [FITing-Tree: A Data-aware Index Structure](https://mlsanity.com/paper/1801.10207/) (2018)
- [SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning](https://mlsanity.com/paper/1901.05152/) (2019)
- [A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration](https://mlsanity.com/paper/2101.01507/) (2021)
- [The Case for Automatic Database Administration using Deep Reinforcement Learning](https://mlsanity.com/paper/1801.05643/) (2018)
- [Towards a Hands-Free Query Optimizer through Deep Learning](https://mlsanity.com/paper/1809.10212/) (2018)
- [Cuttlefish: A Lightweight Primitive for Adaptive Query Processing](https://mlsanity.com/paper/1802.09180/) (2018)
- [A Note on Bounding Regret of the C2UCB Contextual Combinatorial Bandit](https://mlsanity.com/paper/1902.07500/) (2019)

## Built on by (most cited first, 4 of 4)

- [ML-Powered Index Tuning: An Overview of Recent Progress and Open Challenges](https://mlsanity.com/paper/2308.13641/) (2023)
- [Baihe: SysML Framework for AI-driven Databases](https://mlsanity.com/paper/2112.14460/) (2021)
- [Can Uncertainty Quantification Improve Learned Index Benefit Estimation?](https://mlsanity.com/paper/2410.17748/) (2024)
- [GrASP: A Generalizable Address-based Semantic Prefetcher for Scalable Transactional and Analytical Workloads](https://mlsanity.com/paper/2510.11011/) (2025)

## Abstract (arXiv)

Automating physical database design has remained a long-term interest in database research due to substantial performance gains afforded by optimised structures. Despite significant progress, a majority of today's commercial solutions are highly manual, requiring offline invocation by database administrators (DBAs) who are expected to identify and supply representative training workloads. Even the latest advancements like query stores provide only limited support for dynamic environments. This status quo is untenable: identifying representative static workloads is no longer realistic; and physical design tools remain susceptible to the query optimiser's cost misestimates. Furthermore, modern application environments such as hybrid transactional and analytical processing (HTAP) systems render analytical modelling next to impossible. We propose a self-driving approach to online index selection that eschews the DBA and query optimiser, and instead learns the benefits of viable structures through strategic exploration and direct performance observation. We view the problem as one of sequential decision making under uncertainty, specifically within the bandit learning setting. Multi-armed bandits balance exploration and exploitation to provably guarantee average performance that converges to policies that are optimal with perfect hindsight. Our comprehensive empirical evaluation against a state-of-the-art commercial tuning tool demonstrates up to 75% speed-up on shifting and ad-hoc workloads and up to 28% speed-up on static workloads in analytical processing environments. In HTAP environments, our solution provides up to 59% speed-up on shifting and 51% speed-up on static workloads. Furthermore, our bandit framework outperforms deep reinforcement learning (RL) in terms of convergence speed and performance volatility (providing up to 58% speed-up).