DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads with safety guarantees

Automating physical database design has remained a long-term interest in\ndatabase research due to substantial performance gains afforded by optimised\nstructures. Despite significant progress, a majority of today's commercial\nsolutions are highly manual, requiring offline invocation by database\nadministrators (DBAs) who are expected to identify and supply representative\ntraining workloads. Unfortunately, the latest advancements like query stores\nprovide only limited support for dynamic environments. This status quo is\nuntenable: identifying representative static workloads is no longer realistic;\nand physical design tools remain susceptible to the query optimiser's cost\nmisestimates (stemming from unrealistic assumptions such as attribute value\nindependence and uniformity of data distribution). We propose a self-driving\napproach to online index selection that eschews the DBA and query optimiser,\nand instead learns the benefits of viable structures through strategic\nexploration and direct performance observation. We view the problem as one of\nsequential decision making under uncertainty, specifically within the bandit\nlearning setting. Multi-armed bandits balance exploration and exploitation to\nprovably guarantee average performance that converges to a fixed policy that is\noptimal with perfect hindsight. Our comprehensive empirical results demonstrate\nup to 75% speed-up on shifting and ad-hoc workloads and 28% speed-up on static\nworkloads compared against a state-of-the-art commercial tuning tool.\n