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

With the increasing complexity and variability of database applications and their hosting platforms (e.g., multi-tenant cloud environments), automated physical design tuning, particularly automated index selection, has re-emerged as a contemporary challenge for database management systems. Most database vendors offer automated tools for physical design tuning within their product suites [1, 2, 3]. Such tools form an integral part of broader efforts toward fully automated database management systems which aim to: a) decrease database administration costs and thus total costs of ownership [4, 5]; b) help non-experts use database systems; and c) facilitate hosting of databases on dynamic environments such as cloud-based services [6, 7, 8, 9]. Most physical design tools take an off-line approach, where the representative training workload is provided by the database administrator (DBA) [10]. Where online solutions are provided [11, 12, 13, 14, 8, 15], questions remain: How often should the tools be invoked? And more importantly, is the quality of proposed designs in any way guaranteed? How can tools generalise beyond queries seen to dynamic ad-hoc workloads, where queries are unpredictable and non-stationary?

Modern analytics workloads are dynamic in nature with ad-hoc queries common [16] e.g., data exploration workloads adapt to past query responses [17, 18]. Such ad-hoc workloads hinder automated tuning since: a) inputting representative information to design tools is infeasible under time-evolving workloads; and b) reacting too quickly to changes may result in undesirable performance variability, where indices are continuously dropped and created. Any proposed robust automated physical design solution must address such challenges  [11].

To compare alternative physical design structures, automated design tools use a cost model employed by the query optimiser, typically exposed through a “what-if” interface [19], as the sole source of truth. However such cost models make inappropriate assumptions about data characteristics [20, 21]: commercial DBMSs often assume uniform data distributions and attribute value independence. As a result, estimated benefits of proposed designs may diverge significantly from actual workload performance [22, 23, 24, 9, 8]. Even with more complex data distribution statistics such as single- and multi-column histograms, the issue remains for complex workloads, as demonstrated in our experiments (Section V).

In this paper, we demonstrate that even in ad-hoc environments where queries are unpredictable, there are opportunities for index optimisation. We argue that the problem of online index selection under ad-hoc, analytical workloads can be efficiently formulated within the multi-armed bandit (MAB) learning setting—a tractable form of Markov decision process. MABs take arms or actions (selecting indices) to maximise cumulative rewards, trading off exploration of untried actions with exploitation of actions that maximise rewards observed so far (see Figure 1). MABs permit learning from observations of actual performance, and need not rely on potentially misspecified cost models. Unlike initial efforts with applying learning for physical design, e.g., more general forms of reinforcement learning [25], bandits offer regret bounds that guarantee the fitness of dynamically-proposed indices [26].

The key contributions of the paper are summarised next:

• •

  We model index tuning as a multi-armed bandit, proposing design choices that lead to a practical, competitive solution;

• •

  Our proposed design achieves a worst-case safety guarantee against any optimal fixed policy, as a consequence of a corrected regret analysis of the C²UCB bandit; and

• •

  Our comprehensive experiments demonstrate MAB’s superiority over a state-of-the-art commercial physical design tool, with up to 75% speed-ups under dynamic, analytical workloads.

The goal of the online database index selection problem is to choose a set of indices (henceforth referred to as a configuration) that minimises the total running time of a workload sequence within a given memory allowance. Neither the workload sequence, nor system run times, are known in advance.

We adopt the problem definition of [13]. Let the workload $W=(w_{1},w_{2},\ldots,w_{T})$ be a sequence of mini-workloads (e.g., a sequence of single queries), $I$ the set of secondary indices, $C_{mem}(s)$ represent the memory space required to materialise a configuration $s\subseteq I$, and $\mathcal{S}=\left\{s\subseteq I\left|\,C_{mem}(s)\leq M\right\}\right.\subseteq 2^{I}$ be the class of index configurations feasible within our total memory allowance $M$. Our goal is to propose a configuration sequence $S=(s_{0},s_{1},\ldots,s_{T})$, with $s_{t}\in\mathcal{S}$ as the configuration in round $t$ and $s_{0}=\emptyset$ as the starting configuration, which minimises the total workload time $C_{tot}(W,S)$ defined as:

Here $C_{rec}(t)$ refers to the recommendation time in round $t$ (defined as running time of the recommendation tool) and $C_{cre}(s_{t-1},s_{t})$ refers to the incremental index creation time in transitioning from configuration $s_{t-1}$ to $s_{t}$. Finally, $C_{exc}(w_{t},s_{t})$ denotes the execution time of mini-workload $w_{t}$ under the configuration $s_{t}$, namely the sum of response times of individual queries.

At round $t$, the system:

1. 1.

   Chooses a set of indices $s_{t}\in\mathcal{S}$ in preparation for upcoming workload $w_{t}$, without direct access to $w_{t}$.

   $s_{t}$ only depends on observation of historical workloads ($w_{1},\ldots,w_{t-1}$), corresponding sets of chosen indices, and resulting performance;

2. 2.

   Materialises the indices in $s_{t}$ which do not exist yet, that is, all indices in the set difference $s_{t}\backslash s_{t-1}$; and

3. 3.

   Receives workload $w_{t}$, executes all the queries therein, and measures elapsed time of each individual query and each operator in the corresponding query plan.

In this paper, we argue that online index selection can be successfully addressed using multi-armed bandits (MABs) from statistical machine learning, where different arms correspond to chosen indices. We first present necessary background on MABs, outlining the essential properties that we exploit in our work (i.e., bandit context and combinatorial arms) to converge to a highly performant index configuration.

We use the following notation. We denote non-scalar values with boldface: lowercase for vectors and uppercase for matrices. We also write $[k]=\{1,2,\ldots,k\}$ for $k\in\mathbb{N}$, and denote the transpose of a matrix or a vector with a prime.

The contextual combinatorial bandit setting under semi-bandit feedback involves repeated selections from $k$ possible actions, over rounds $t=1,2,\ldots$, in which the MAB:

1. 1.

   Observes a context feature vector (possibly random or adversarially chosen) of each action or arm $i\in[k]$, denoted as $\bm{X}_{t}=\{\bm{x}_{t}(i)\}_{i\in[k]}$, for $\bm{x}_{t}(i)\in\mathbb{R}^{d}$, along with their costs, $c_{i}$;

2. 2.

   Selects or pulls a set of arms (often referred to as super arm) $s_{t}\in\mathcal{S}_{t}$, where we restrict the class of possible super arms $\mathcal{S}_{t}\subseteq\mathcal{S}^{\prime}_{t}=\left\{s\subseteq[k]\left|\,\sum_{i\in s}c_{i}\leq C\right.\right\}\subseteq 2^{[k]}$; and

3. 3.

   For each $i_{t}\in s_{t}$, observes random scores $r_{t}(i_{t})$ drawn from fixed but unknown arm distribution which depends solely on the arm $i_{t}$ and its context $\bm{x}_{t}(i_{t})$, whose true expected values are contained in the unknown variable $\bm{r}^{\star}_{t}=\{\mathbb{E}[r_{t}(i)]\}_{i\in[k]}$

A MAB’s goal is to maximise the cumulative expected reward $\sum_{t}\mathbb{E}[R_{t}(s_{t})]=\sum_{t}g(\bm{r}^{\star}_{t},\bm{X}_{t},s_{t})$ for a known function $g$. This function $g$ need not be a simple summation of all the scores. The core challenge in this problem is that the expected scores for all arms $i\in[k]$ are unknown. Refinement of a bandit learner’s approximation for arm $i$ is generally only possible by including arm $i$ in the super arm, as the score for arm $i$ is not observable when $i$ is not played. This suggests solutions that balance exploration and exploitation. Even though at first glance it may seem that each arm needs to be explored at least once, placing practical limits on large numbers of arms, there is a remedy to this as will be discussed shortly.

The C²UCB algorithm. Used to solve the contextual combinatorial bandit problem, the C²UCB Algorithm [26] models the arms’ scores as linearly dependent on their contexts: $r_{t}(i)={\bm{\theta}}^{\prime}\bm{x}_{t}(i)+\varepsilon_{t}(i)$ for unknown zero-mean (subgaussian) random variable $\varepsilon_{t}$, unknown but fixed parameter $\bm{\theta}\in\mathbb{R}^{d}$, and known context $\bm{x}_{t}(i)$. It is crucial to notice that this implies that all learned knowledge is contained in estimates of $\bm{\theta}$, which is shared between all arms, obviating the need to explore each arm. Estimation of $\bm{\theta}$ can be achieved using ridge regression,¹¹1A standard linear regression with $L_{2}$ regularisation on the $\bm{\theta}$ coefficients, leading to well-posed optimisation. Equivalent to max a posteriori Bayesian linear regression with a Gaussian prior. with $|s_{t}|$ new data points $\{(\bm{x}_{t}(i),r_{t}(i))\}_{i\in s_{t}}$ available at round $t$, further accelerating the convergence rate of the estimator $\hat{\bm{\theta}}$, over observing only one example as might be naïvely assumed.

Point estimates on the expected scores can be made with $\bar{r}_{t}(i)=\hat{\bm{\theta}}_{t}^{\prime}\bm{x}_{t}(i)$, where $\hat{\bm{\theta}}_{t}$ are trained coefficients of a ridge regression on arm $i$’s observed rewards against contexts. However, this quantity is oblivious to the variance in the score estimation. Intuitively, to balance out the exploration and exploitation, it is desirable to add an exploration boost to the arms whose score we are less sure of (i.e., greater estimate variance). This suggests that the upper confidence bound (UCB) should be used, in place of the expected value, and which can be calculated [27] as:

where $\alpha_{t}$ is the exploration boost factor, and $\bm{V}_{t-1}$ is the positive-definite $d\times d$ scatter matrix of contexts for the chosen arms up to and including round $t-1$. The first term of $\hat{r}_{t}(i)$ corresponds to arm $i$’s immediate reward, whereas its second term corresponds to its exploration boost, as its value is larger when the arm is sensitive to the context elements we are less confident of (i.e., the underexplored context dimension). Hence, by using $\hat{r}_{t}(i)$ in place of $\bar{r}_{t}(i)$, arms with contexts lying in the underexplored regions of context space are more likely to be chosen, as higher scores yield higher $g$, assuming that $g$ is monotonic increasing in the arm rewards.

Ideally, the super arm $s_{t}\in\mathcal{S}_{t}$ is chosen such that $g(\hat{\bm{r}}_{t},\bm{X}_{t},s_{t})$ is maximised. However, it is sometimes computationally expensive to find such super arms. In such cases, it is often good enough to obtain a solution via some approximation algorithm where $g(\hat{\bm{r}}_{t},\bm{X}_{t},s_{t})$ is near maximum. With this criterion in mind, we now define an $\alpha$-approximation oracle.

Note that knapsack-constrained submodular programs are efficiently solved by the greedy algorithm (iteratively select a remaining cost-feasible arm with highest available score) with $\alpha=1-1/e$. C²UCB is detailed in Algorithm 1.

The performance of a bandit algorithm is usually measured by its cumulative regret, defined as the total expected difference between the reward of the chosen super arm $\mathbb{E}[R_{t}(s_{t})]$ and an optimal super arm $\max_{s\in\mathcal{S}_{t}}\mathbb{E}[R_{t}(s)]$ over $T$ rounds. However, such a metric is unfair to C²UCB since its performance depends on the oracle’s performance. This suggests to measure C²UCB’s performance with a new metric using the oracle’s performance guarantee as its measuring stick, defined as follows.

When $g$ is assumed to be monotonic and Lipschitz continuous, [26] claimed that C²UCB enjoys $\tilde{O}(\sqrt{T})$ $\alpha$-regret.²²2The notation $\tilde{O}(\bm{\cdot})$ is equivalent to $O(\bm{\cdot})$ while ignoring logarithmic factors. We have corrected an error in the original proof, as seen in our technical note [28], confirming the $\tilde{O}(\sqrt{T})$ $\alpha$-regret. This expression is sub-linear in $T$, implying that the per-round average cumulative regret approaches zero after sufficiently many rounds. Consequently, online index selection based on C²UCB comes endowed with a safety guarantee on worst-case performance: selections become at least as good as an $\alpha$-optimal policy (with perfect access to true scores); and potentially much better than any fixed policy.

Performant bandit learning for online index tuning demands arms covering important actions and no more, rewards that are observable and for which regret bounds are meaningful, and contexts and oracle that are efficiently computable and predictive of rewards. Each workload query is monitored for characteristics such as running time, query predicates, payload, etc. (Figure 1). These observations feed into generation of relevant arms and their contexts. The learner selects a desired configuration which is materialised. After query return, the system identifies benefits of the materialised indices, which are then shaped into the reward signal for learning.

Dynamic arms from workload predicates. Instead of enumerating all column combinations, relevant arms (indices) may be generated based on queries: combinations and permutations of query predicates (including join predicates), with and without inclusion of payload attributes from the selection clause. Such workload-based arm generation drastically reduces the action space, and exploits natural skewness of real-life workloads that focus on small subsets of attributes over full tables [18, 17]. Workload-based arm generation is only viable due to dynamic arm addition (reflecting a dynamic action space) and is allowed by the bandit setting: we may define the set of feasible arms for each round at the start of the round.

Context engineering. Effective contexts are predictive of rewards, efficiently computable, and promote generalisation to previously unseen workloads and arms. We form our context in two parts (see Figure 1).

Context Part 1: Indexed column prefix. We encode one context component per column. However unlike a bag-of-words or one-hot representation appropriate for text, similarity of arms depends on having similar column prefixes; common index columns is insufficient. This reflects a novel bandit learning aspect of the problem. A context component has value $10^{-j}$ where $j$ is the corresponding column’s position in the index, provided that the column is included in the index and is a workload predicate column. The value is set to 0 otherwise, including if its presence only covers the payload.

Context Part 2: Derived statistical information. We represent statistical and derived information about the arms and workload, details available from the optimiser during query execution, and sufficient statistics for unbiased estimates. This statistical information includes: a Boolean indicating a covering index, the estimated size of the index divided by the database size (if not materialised already, 0 otherwise), and usage information of the index from previous rounds. This is shown in Figure 1 under D1, D2 and D3, respectively.

Reward shaping. As the goal of physical design tuning tools is to minimise end-to-end workload time, we incorporate index creation time and query execution time into the reward for a workload. We omit index recommendation time, as it is independent of arm selection. However, we measure and report recommendation time of the MAB algorithm in our experiments. Recall that MAB depends only on observed execution statistics from implemented configurations and generalisation of the learned knowledge to unseen arms thereafter.

The implementation of the reward signal for an arm includes the execution time as a gain $G_{t}(i,w_{t},s_{t})$ for a workload $w_{t}$ by each arm $i$ under configuration $s_{t}$. By defining $\mathcal{U}(s,q)$ as the list of indices used by the query optimiser for query $q$ for a given configuration $s$, the gain by index $i$ for a query $q$ is defined by:

where $\tau(i)$ is the table which $i$ belongs to and $C_{tab}(\tau(i),q,\emptyset)$ represents the full table scan time for table $\tau(i)$ and query $q$.³³3Due to the reactive nature of multi-armed bandits, we mostly observe a full table scan time for each table $\tau(i)$ and query $q$. When we do not observe this, we estimate it with the maximum secondary index scan/seek time. The gain for a workload is related to the gain for individual query by:

By this definition, gain $G_{t}(i,w_{t},s_{t})$ will be $0$ if $i$ is not used by the optimiser in the current round $t$ and can be negative if the index creation leads to a performance regression. Creation time of $i$ is taken as a negative reward, only if $i$ is materialised in round $t$, and is $0$ otherwise:

Minimising the end-to-end workload time, or rather, maximising the end-to-end workload time gained, is the goal of the bandit. As defined earlier, the total workload time $C_{tot}$ is the sum of execution, recommendation and creation times accumulated over rounds. As such, minimising each round’s summand is an equivalent problem. Modifying the execution time to the time gain while ignoring the recommendation time yields per-round super arm reward of:

Selection of the execution plan depends on the query optimiser, and as noted, the query optimiser may resolve to a sub-optimal query plan. As we show, the bandit is nonetheless resilient as it can quickly recover from any such performance regressions. Observed execution times encapsulate real-world effects e.g., the interaction between queries, application properties, run-time parameters, etc. Since the end-to-end workload time includes the index creation and query execution times, we are indirectly optimising for both efficiency and the quality of recommendations.

A greedy oracle for super-arm selection. Recall that C²UCB leverages a near-optimal oracle to select a super arm, based on individual arm scores [26]. As a sum of individual arm rewards, our super-arm reward has a (sub)modular objective function and (as easily proven) exhibits monotonicity and Lipschitz continuity. Approximate solutions to maximise submodular (diminishing returns) objective functions can be obtained with greedy oracles that are efficient and near-optimal [29]. Our implementation uses such an oracle combined with filtering to encourage diversity. Initially, arms with negative scores are pruned. Then arm selection and filtering steps alternate, until the memory budget is reached. In the selection step, an arm is selected greedily based on individual scores. The filtering step filters out arms that are no longer viable under the remaining memory budget, or those that are already covered by the selected arms based on prefix matching. If a covering index is selected for a query, all other arms generated for that query will be filtered out. Note that filtering is a temporary process that only impacts the current round.

Bandit learning algorithm. Algorithm 2 shows the MAB algorithm which summarises workload information using templates; these track frequency, average selectivity, first seen and last seen times of the queries which help to generate the best set of arms per round (i.e., QoI). The context is updated after each round based on the workload and selected set of arms. The bandit then selects a set of arms for this round. The set of arms chosen form a configuration to be materialised within the database. Once the new configuration is in place, a new set of queries will be executed. To support shifting workloads, where users’ interests change over time, the learner can forget learned knowledge depending on the workload shift intensity (i.e., number of newly introduced query templates).

We evaluate our MAB framework across a range of widely used industrial benchmarks, comparing it to a state-of-the-art physical design tool shipped with a commercial database product referred to as the Physical Design Tool (PDTool). This is a mature product, proven to outperform other physical design tools available on the market.

Automated physical design tuning. Most commercial DBMS vendors nowadays offer physical design tools in their products [1, 2, 3]. These tools rely heavily on the query optimiser to compare benefits of different design structures without materialisation [19]. Such an approach is ineffective when base data statistics are unavailable, skewed, or change dynamically [10]. In these dynamic environments, the problem of physical design is aggravated: a) deciding when to call a tuning process is not straightforward; and b) deciding what is a representative training workload is a challenge.

Online physical design tuning. Several research groups have recognised these problems and have offered lightweight solutions to physical design tuning [14, 13, 12, 11]. While such solutions are more flexible and need not know the workload in advance, they are typically limited in terms of applicability to new unknown workloads (generalisation beyond past), and do not come with theoretical guarantees that extend to actual runtime conditions. Moreover, by giving the optimiser a central role, the tools remain susceptible to its mistakes [9]. [8] extends [1] with the use of additional components, in a narrowed scope of index selection to mimic an online tool. This takes corrective actions against the optimiser mistakes through a validation process.

Adaptive and learning indices. Another dimension of online physical design tuning is database cracking and adaptive indexing that smooth the creation cost of indices by piggybacking on query execution [37, 38]. Recent efforts have gone a step further and proposed replacing data structures with learned models that are smaller in size and faster to query [39, 40, 41]. Such approaches are complementary to our efforts: once the data structures (or models) are materialised inside a DBMS, the MAB framework can be used to automate the decision making as to which data structure should be used to speed-up query analysis.

Learning approaches to optimisation and tuning. Recent years have witnessed new machine learning approaches to automate decision-making processes within databases. For instance, reinforcement learning approaches have been used for query optimisation and join ordering [42, 43, 44, 45]. In [9], simpler approaches like regression have mitigated the optimiser’s cost misestimates as a path toward more robust index selection. While [9] shows promising results when avoiding query regressions, according to the authors, when it starts without any knowledge on tuning database (AdaptiveDB), it only provides a marginal workload execution cost improvement (and sometimes deterioration) over the traditional optimiser. Furthermore, this classifier incurs up to 10% recommendation time, impacting recommendation cost in all cases, especially where recommendation cost already dominates the cost for PDTool (TPC-DS, IMDb). When it comes to tuning, the closest approaches employ variants of RL for index selection or partitioning [25, 46, 35] or configuration tuning [5]. [35] describes RL-based index selection, which depends solely on the recommendation tool for query-level recommendations and is affected by decision combinatorial explosion, both issues addressed in our work. Unlike its more general counterpart (RL), MABs have advantages of faster convergences as demonstrated in Section V-C, simple implementation, and theoretical guarantees.

This paper scratches the surface of the numerous opportunities for applying bandit learners to performance tuning of databases. In the following, we discuss a rich research vision for the area.

Real-world use and integration. Even though we use synthetic benchmarks, they are comprehensive in summarising fundamental properties and known pain points of real-life workloads (complexity, data skewness, numerous joins, etc.). Therefore our findings and results generalise to real-life use cases as well. Furthermore, MAB only requires execution statistics to function and can be easily integrated with any existing DBMS.

Multi-tenant and HTAP environments. A crucial advantage of the MAB setting is theoretical guarantees on the fitness of proposed indices to observed run-time conditions. This is critical for production systems in the cloud and multi-tenant environments [9, 7, 8], where analytical modelling is impossible due to unpredictable changes in run-time conditions. Similar requirements hold for hybrid OLTP/OLAP processing environments (HTAP) where the presence of transactions hinders the usefulness of indices, making analytical modelling next to impossible. The MAB approach on the contrary eschews the optimiser and modelling completely, choosing indices based on observed query performance and is thus equally applicable to these challenging environments.

Beyond index choices. Despite focusing solely on the task of index selection in this paper, the MAB framework is equally applicable to other physical design choices, such as materialised views selection, statistics collection, or even selection of design structures that are a mix of traditional and approximate data structures, such as learned models [39] or other fine-grained design primitives [41].

Complementing the recommendation tool. Even though the MAB solution was presented as an alternative to the recommendation tool (PDTool), it can work in concert with existing recommendation systems. MAB can be used as a validator that starts with the PDTool’s recommendations and performs further run-time optimisations based on observed performance, in a similar vein to [8].

Cold-start problem. Under the current setup, MAB starts without any secondary indices or knowledge about their benefits, forming a cold-start problem and leading to higher creation costs. While MAB is already superior against PDTool even with the creation cost burden (see Section V-B3), even faster convergence and better creation costs can be provided by pre-training models in hypothetical rounds [47] (using what-if) or workload forecasting [15] to improve context quality.

Opportunities for bandit learning. The increased search space of possible design choices calls for advancements to bandits algorithms and theory, where unbounded/infinite numbers of arms will be increasingly important. Similarly, various flavours of physical design might ask for novel bandits that adopt the notion of heterogeneous arms (indices, views, or statistics), or hierarchical models where individual choices at lower levels (e.g., the choice of indices or materialised views) influence decisions at a higher level (e.g., index merging due to memory constraints).

This paper develops a multi-armed bandit learning framework for online index selection. Benefits include eschewing the DBA and the (error-prone) query optimiser by learning the benefits of indices through strategic exploration and observation. We justify our choice of MAB over general reinforcement learning for online index tuning, comparing MAB against DDQN, a popular RL algorithm based on deep neural networks, demonstrating significantly faster convergence of the MAB. Furthermore, our extensive experimental evaluation demonstrates advantages of MAB over an existing commercial physical design tool (up to 75% speed up, and 23% on average), and exemplifies robustness to data skew and unpredictable ad-hoc workloads.