Debabrota Basu
email: debabrota.basu@u.nus.edu

Qian Lin

Hoang Weidong Chen

Tam Vo

Zihong Yuan

Pierre Senellart

Stéphane Bressan

Hoang Tam Vo

Regularized Cost-Model Oblivious Database Tuning with Reinforcement Learning

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

In a recent SIGMOD blog entry [START_REF] Lohman | Is query optimization a "solved" problem?[END_REF], Guy Lohman asked "Is query optimization a 'solved' problem?". He argued that current query optimizers and their cost models can be critically wrong. Instead of relying on wrong cost models, Stillger et al. have proposed LEO-DB2, a learning optimizer [START_REF] Stillger | LEO -DB2's LEarning Optimizer[END_REF]; its enhanced performance with respect to classical query optimizers strengthens the claim of discrepancies introduced by the predetermined cost models. Stillger et al. have proposed LEO-DB2, a learning optimizer [START_REF] Stillger | LEO -DB2's LEarning Optimizer[END_REF]; its enhanced performance with respect to classical query optimizers strengthens the claim of discrepancies introduced by the predetermined cost models This is our perspective in this article: we propose a learning approach to performance tuning of database applications. By performance tuning, we mean selection of an optimal physical database configuration in view of the workload. In general, configurations differ in the indexes, materialized views, partitions, replicas, and other parameters. While most existing tuning systems and literature [START_REF] Bruno | An online approach to physical design tuning[END_REF][START_REF] Schnaitter | On-line index selection for shifting workloads[END_REF][START_REF] Schnaitter | Semi-automatic index tuning: Keeping dbas in the loop[END_REF] rely on a predefined cost model, the objective of this work is to validate the opportunity for a tuning strategy to do without.

To achieve this, we propose a formulation of database tuning as a reinforcement learning problem (see Section 3). The execution of queries and updates is modelled as a Markov decision process whose states are database configurations, whose actions are configuration changes, and whose rewards are functions of the cost of configuration change and query/update evaluation. This formulation does not rely on a preexisting cost model, rather it learns it.

We present a solution to the reinforcement learning formulation that tackles the curse of dimensionality (Section 4). To do this, we reduce the search space by exploiting the quasi-metric properties of the configuration change cost, and we approximate the cumulative cost with a linear model. We formally prove that, assuming such a linear approximation is sound, our approach converges to an optimal policy for estimating the cost.

We then tackle in Section 5 the problem of overfitting: to avoid instability while learning the cost model, we add a regularization term in learning the cost model. We formally derive a bound on the total regret of the regularized estimation, that is logarithmic in the time step (i.e., in the size of the workload).

We instantiate our approach to the use case of index tuning (Section 6), developing in particular optimizations specific to this use case to reduce the search space. The approaches of Sections 4 and 5 provide us with two algorithms COREIL and rCOREIL to solve the index tuning problem.

We use this case to demonstrate the validity of a cost-model oblivious database tuning with reinforcement learning, through experimental evaluation on a TPC-C workload [START_REF] Raab | TPC-C -the standard benchmark for online transaction processing (OLTP)[END_REF] (see Section 7). We compare the performance with the Work Function Index Tuning (WFIT) algorithm [START_REF] Schnaitter | Semi-automatic index tuning: Keeping dbas in the loop[END_REF]. Results show that our approach is competitive yet does not need knowledge of a cost model. While the comparison of WFIT with COREIL establishes reinforcement learning as an effective approach to automatize the index tuning problem, performance of rCOREIL with respect to COREIL demonstrates that the learning performance is significantly enhanced by a crisp estimation of the cost model.

Related work is discussed in Section 2.

This article extends a conference publication [START_REF] Basu | Costmodel oblivious database tuning with reinforcement learning[END_REF]. In addition to minor edits and precisions added throughout the paper, the following material is novel: the discussion of related work on reinforcement learning (Section 2.2); the result of convergence to an optimal policy (Proposition 2) and its proof; the introduction of regularization (Section 5), including bounds on regrets (Theorem 1 and Section 6.4), the experimental comparison between regularized and non-regularized versions of our approach (Section 7.4) and the study of the quality of their cost estimators (Section 7.5).

We now review the related work in two areas of relevance: self-tuning databases, and the use of reinforcement learning for data management applications.

Automated Database Configuration

Table 1 provides a brief classification of related research in automated database configuration, in terms of various dimensions: the offline or online nature of the algorithm (see further), and the physical design aspects being considered by these works (index selection, vertical partitioning, or mixed design together with horizontal partitioning and replication). Stand-alone: [START_REF] Bruno | Constrained physical design tuning[END_REF][START_REF] Bruno | Configuration-parametric query optimization for physical design tuning[END_REF][START_REF] Papadomanolakis | Efficient use of the query optimizer for automated physical design[END_REF] Parallel DBs: [START_REF] Agrawal | Integrating vertical and horizontal partitioning into automated physical database design[END_REF][START_REF] Rao | Automating physical database design in a parallel database[END_REF] Online [START_REF] Bruno | An online approach to physical design tuning[END_REF][START_REF] Luhring | Autonomous management of soft indexes[END_REF][START_REF] Malik | Adaptive physical design for curated archives[END_REF][START_REF] Schnaitter | Semi-automatic index tuning: Keeping dbas in the loop[END_REF] [3, [START_REF] Li | Self-managing online partitioner for databases (smopd): A vertical database partitioning system with a fully automatic online approach[END_REF][START_REF] Rösch | A storage advisor for hybrid-store databases[END_REF] Offline Algorithms Traditionally, automated database configuration is conducted in an offline manner. In that approach, database administrators (DBAs) identify representative workloads from the trace of historical database queries and updates. That task can be done either manually or with the help of sophisticated tools provided by database vendors. Based on these representative workloads, new database configurations are realized: for example, new beneficial indexes to be created [START_REF] Agrawal | Automated selection of materialized views and indexes in sql databases[END_REF][START_REF] Lefevre | Exploiting opportunistic physical design in large-scale data analytics[END_REF][START_REF] Zilio | Recommending materialized views and indexes with IBM DB2 design advisor[END_REF], smart vertical partitioning for reducing I/O costs [START_REF] Hammer | A heuristic approach to attribute partitioning[END_REF][START_REF] Lightstone | Automated design of multidimensional clustering tables for relational databases[END_REF][START_REF] Rasin | An automatic physical design tool for clustered columnstores[END_REF], or possibly a combination of index selection, partitioning and replication for both stand-alone databases [START_REF] Bruno | Constrained physical design tuning[END_REF][START_REF] Bruno | Configuration-parametric query optimization for physical design tuning[END_REF][START_REF] Papadomanolakis | Efficient use of the query optimizer for automated physical design[END_REF] and parallel databases [START_REF] Agrawal | Integrating vertical and horizontal partitioning into automated physical database design[END_REF][START_REF] Rao | Automating physical database design in a parallel database[END_REF].

Online Algorithms Given the increasing complication and agility of database applications, coupled with the introduction of modern database environments such as database-as-a-service, the aforementioned manual task of DBAs, though it can be done at regular times in an offline fashion, becomes even more tedious and problematic. Therefore, it is desirable to design more automated solutions to the database design problem that are able to continuously monitor changes in the workload and react in a timely manner by adapting the database configuration to the new workload. In fact, the problem of online index selection has been well-studied in the past [START_REF] Bruno | An online approach to physical design tuning[END_REF][START_REF] Bruno | Interactive physical design tuning[END_REF][START_REF] Luhring | Autonomous management of soft indexes[END_REF][START_REF] Malik | Adaptive physical design for curated archives[END_REF][START_REF] Schnaitter | Semi-automatic index tuning: Keeping dbas in the loop[END_REF]. Generally, these techniques adopt the same working model in which the system continuously tracks the incoming queries for identifying candidate indexes, profiles the benefit of the indexes, and realizes the ones that are most useful for query execution. Specifically, an online approach to physical design tuning (index selection) was proposed in [START_REF] Bruno | An online approach to physical design tuning[END_REF]. The essence of the algorithm is to progressively choose the optimal plan at each step by using a case-by-case analysis on the potential benefits that we may lose by not implementing relevant candidate indexes. That is, each new database configuration is selected only when a physical change, i.e., creating or deleting an index, would be helpful in improving system performance. Similarly, a framework for continuous online physical tuning was proposed in [START_REF] Schnaitter | On-line index selection for shifting workloads[END_REF] where effective indexes are created and deleted in response to the shifting workload. Furthermore, the framework is able to self-regulate its performance by providing explicit mechanism for controlling the overhead of profiling the benefit of indexes.

One of the key components of an index selection algorithm is profiling indexes' benefit, i.e., how to evaluate the cost of executing a query workload with the new indexes as well as the cost of configuration transition, i.e., creating and deleting indexes. To realize this function, most of the aforementioned online algorithms exploit a what-if optimizer [START_REF] Chaudhuri | Autoadmin: What-if index analysis utility[END_REF] which returns such estimated costs. For examples, the what-if optimizer of DB2 was used in [START_REF] Schnaitter | Semi-automatic index tuning: Keeping dbas in the loop[END_REF], and the what-if optimizer of SQL Server was employed in [START_REF] Bruno | An online approach to physical design tuning[END_REF], while the classical optimizer of PostgreSQL was extended to support what-if analysis in [START_REF] Schnaitter | On-line index selection for shifting workloads[END_REF]. However, it is well-known that invoking the optimizer for estimating the cost of each query under different configurations is expensive [START_REF] Papadomanolakis | Efficient use of the query optimizer for automated physical design[END_REF]. In this work, we propose an algorithm that does not require the use of a what-if optimizer while being able to adaptively provide a better database configuration in the end, as reported in our experimental results.

More recently, as column-oriented databases have attracted a great deal of attention in both academia and industry, online algorithms for automated vertical partitioning becomes critical for such an emerging breed of database systems [START_REF] Alagiannis | H2o: A hands-free adaptive store[END_REF][START_REF] Li | Self-managing online partitioner for databases (smopd): A vertical database partitioning system with a fully automatic online approach[END_REF][START_REF] Rösch | A storage advisor for hybrid-store databases[END_REF]. Specifically, a storage advisor for SAP's HANA in-memory database system was proposed in [START_REF] Rösch | A storage advisor for hybrid-store databases[END_REF] in order to take advantage of both columnar and row-oriented storage layouts. At the core of that storage advisor is a cost model which is used to estimate and compare query execution times for different stores. Similarly, a continuous layout adaptation has been recently been introduced in [START_REF] Alagiannis | H2o: A hands-free adaptive store[END_REF] with the aim to support multiple storage layouts in a single engine which is able to adapt to changing data access patterns. The adaptive store monitors the access patterns of incoming queries through a dynamic window of N queries and devises cost models for evaluating the workload and layout transformation cost. Furthermore, in order to efficiently find a near optimal data layout for a given workload, the hybrid store exploits proper heuristic techniques to prune the immense search space of alternative data layouts. On the contrary, the algorithm introduced in [START_REF] Li | Self-managing online partitioner for databases (smopd): A vertical database partitioning system with a fully automatic online approach[END_REF] uses data mining techniques for vertical partitioning in database systems. The technique is based on closed item sets mining from a query set and system statistic information at run-time, and hence is able to automatically detect changing workloads and perform a re-partitioning action without the need of interaction from DBAs.

Recently, [START_REF] Bouchakri | Advances in Databases and Information Systems[END_REF] and [START_REF] Azefack | Dynamic index selection in data warehouses[END_REF] have aimed at solving the problem of online index selection for large join queries and data warehouses. Since both approaches use a predefined cost model, similarly to [START_REF] Schnaitter | Semi-automatic index tuning: Keeping dbas in the loop[END_REF], it renders them susceptible to erroneous estimations of the cost model. In our work, we are removing the effects of errors made by the cost model by learning it. This gives our approach more robustness and flexibility than cost-model-dependent ones. Moreover, [START_REF] Bouchakri | Advances in Databases and Information Systems[END_REF] uses genetic algorithms to optimize the selection of multi-table indexes incrementally. But genetic algorithms generally performs worse than reinforcement learning [START_REF] Rieser | A comparison of genetic algorithms and reinforcement learning for optimising sustainable forest management[END_REF] in this kind of dynamic optimization tasks due to its more exploratory nature. In addition, reinforcement learning agents have a more real-time behaviour than genetic behaviour. In [START_REF] Azefack | Dynamic index selection in data warehouses[END_REF], authors use a heuristics approach where they incrementally look for frequent itemsets in a query workload. With the knowledge base acquired from there updates, indexes are generated for the frequent itemsets while eliminating the ones generated for infrequent itemsets. Due to such greedy behaviour, higher variance and instability is expected than for reinforcement learning approaches where a trade-off between exploration and exploitation is reached through learning.

Discussion Compared to the state-of-the-art in online automated database design, our proposed overall approach is more general and has the potential to be applied for various problems such as index selection, horizontal/vertical partitioning design, and in combination with replication as well; we note however that we experiment solely with index tuning in this article. More importantly, as our proposed online algorithm is able to learn the estimated cost of queries gradually through subsequent iterations, it does not need the what-if optimizer for estimating query cost. Therefore, our proposed algorithm is applicable to a wider range of database management systems which may not implement a what-if optimizer or expose its interface to users.

Reinforcement Learning in Data Management

Reinforcement learning [START_REF] Sutton | Reinforcement Learning[END_REF] is about determining the best thing to do next under an evolving knowledge of the world, in order to reach a goal. This goal is commonly represented as maximization of the cumulative reward obtained while performing some actions. Here each action leads to an individual reward and to a new state, usually in a stochastic manner. Markov decision processes (MDPs) [START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF] are a common model for reinforcement learning scenarios. In this model each action leads to a new state and to a given reward according to a probability distribution that must be learned. This implies an inherent trade-off between exploration (trying out new actions leading to new states and to potentially high rewards) and exploitation (performing actions already known to yield high rewards), a compromise explored in depth in, e.g., the stateless model of multi-armed bandits [START_REF] Audibert | Exploration-exploitation tradeoff using variance estimates in multi-armed bandits[END_REF]. Despite being well-adapted to the modelling of uncertain environments, the use of MDPs in data management applications has been limited so far. The use of MDP for modelling data cleaning tasks has been raised in [START_REF] Benedikt | Data cleaning for decision support[END_REF]. In that paper, the authors discussed the absence of a straightforward technique to do that because of the huge state space. More generally, the following reasons may explain the difficulties in using reinforcement learning in data management applications:

(i) As in [START_REF] Benedikt | Data cleaning for decision support[END_REF], the state space is typically huge, representing all possible partial knowledge of the world. This can be phrased as the curse of dimensionality. (ii) States have complex structures, namely that of the data, or, in our case, of the database configuration. (iii) Rewards may be delayed, obtained after a long sequence of state transitions. This is for example the case in focused Web crawling, which is a datacentric application domain. Still multi-armed bandits have been successfully applied [START_REF] Gouriten | Scalable, generic, and adaptive systems for focused crawling[END_REF] to this problem. (iv) Because of data uncertainty, there may be only partial observability of the current state. That changes the problem to a partially observable Markov decision process [START_REF] White | Markov decision processes[END_REF].

The last two issues are fortunately not prevalent in the online tuning problem discussed here. This lets us formulate online tuning problem as an MDP and focus on a solution to the first two problems.

Problem Definition

Let R be a logical database schema. We can consider R to be the set of its possible database instances. Let S be the set of corresponding physical database configurations of instances of R. For a given database instance, two configurations s and s may differ in the indexes, materialized views, partitions, replicas, and other parameters. For a given instance, two configurations will be logically equivalent if they yield the same results for all queries and updates. The cost of changing configuration from s ∈ S to s ∈ S is denoted by the function δ(s, s ). The function δ(s, s ) is not necessarily symmetric, i.e., we may have δ(s, s ) = δ(s , s). This property emerges as the cost of changing configuration from s to s and the reverse may not be the same. On the other hand, it is a non-negative function and also verifies the identity of indiscernibles: formally, δ(s, s ) 0 and the equality holds if and only if s = s . Physically this means that there is no free configuration change. As it is always cheaper to do a direct configuration change, we get ∀s, s , s ∈ S δ(s, s ) δ(s, s ) + δ(s , s ). This is simply the triangle inequality. As δ exhibits the aforementioned properties, it is a quasi-metric on S.

Let Q be a workload, defined as a schedule of queries and updates. For brevity, we refer to both of them as queries. To simplify, we consider the schedule to be sequential and the issue of concurrency control orthogonal to the current presentation. Thus, query q t represents the t th query in the schedule, which is executed at time t.

We model a query q t as a random variable, whose generating distribution may not be known a priori. It means that q t is only observable at time t. The cost of executing query q ∈ Q on configuration s ∈ S is denoted by the function cost(s, q). For a given query, the cost function is always positive as the system have to pay some cost to execute a query.

Let s 0 be the initial configuration of the database. At any time t the configuration is changed from s t-1 to s t with the following events in order:

1. Arrival of query q t . We call qt the observation of q t at time t. Thus, the system has to pay the sum of the cost of configuration change and that of query execution during each transition. Now, we define per-stage cost as

C(s t-1 , s t , qt ) := δ(s t-1 , s t ) + cost(s t , qt ).
We can phrase in other words the stochastic decision process of choosing the configuration changes as a Markov decision process (MDP) [START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF] where states are database configurations, actions are configuration changes, and penalties (negative rewards) are the per-stage cost of the action. Note that in contrast to the general framework of MDPs, transitions from one state to another on an action are deterministic. Indeed, in this process there is no uncertainty associated with the new configuration when a configuration change is decided. On the other hand, penalties are stochastic, as they depend on the query which is a random variable. In the absence of a reliable cost model, the cost of a query in a configuration is not known in advance. This makes penalties uncertain.

Ideally, the problem would be to find the sequence of configurations that minimizes the sum of future per-stage costs. We assume an infinite horizon [START_REF] Sutton | Reinforcement Learning[END_REF], which means an action will affect all the future states and actions of the system. But it makes the cumulative sum of future per-stage costs infinite. One practical way to circumvent this problem is to introduce a discount factor γ ∈ [0, 1). Mathematically, it makes the cumulative sum of per-stage costs convergent. Physically, it gives more importance to immediate costs than to costs distant in the future, which is a practical intuition. Now, the problem translates into finding the sequence of configurations that minimize a discounted cumulative cost defined with γ. Under Markov assumption, a sequence of configuration changes is represented by a function, called policy π : S × Q → S. Given the current configuration s t-1 and a query qt , a policy π determines the next configuration

s t := π(s t-1 , qt ).
We define the cost-to-go function V π for a policy π as:

V π (s) := E ∞ t=1 γ t-1 C(s t-1 , s t , qt ) such that s 0 = s s t = π(s t-1 , qt ), t 1 (1)
where 0 < γ < 1 is the discount factor. The value of V π (s) represents the expected cumulative cost for the following policy π from the current configuration s.

Let U be the set of all policies for a given database schema. Our problem can now be formally phrased as to minimize the expected cumulative cost, i.e., to find an optimal policy π * such that

π * := arg min π∈U V π (s 0 )
where the initial state s 0 is given.

Adaptive Database Tuning

Algorithm Framework

In order to find the optimal policy π * , we start from an arbitrary policy π, compute an estimation of its cost-to-go function, and incrementally attempt to improve it using the current estimate of the cost-to-go function V for each s ∈ S. This strategy is known as policy iteration [START_REF] Sutton | Reinforcement Learning[END_REF] in the reinforcement learning literature.

Traditionally, policy iteration functions as follows. Assuming the probability distribution of q t is known in advance, we improve the cost-to-go function V πt of the policy π t at iteration t using

V πt (s) = min s ∈S δ(s, s ) + E [cost(s , q)] + γV πt-1 (s ) (2)
We obtain the updated policy as arg min πt∈U V πt (s). The algorithm terminates when there is no change in the policy. The proof of optimality and convergence of policy iteration can be found in [START_REF] Powell | Approximate Dynamic Programming: Solving the Curses of Dimensionality[END_REF].

Unfortunately, policy iteration suffers from several problems. First, there may not be any proper model available beforehand for the cost function cost(s, q). Second, the curse of dimensionality [START_REF] Powell | Approximate Dynamic Programming: Solving the Curses of Dimensionality[END_REF] makes the direct computation of V hard. Third, the probability distribution of queries is not assumed to be known a priori, making it impossible to compute the expected cost of query execution E [cost(s , q)].

Algorithm 1 Algorithm Framework

1: Initialization: an arbitrary policy π0 and a cost model C0 2: Repeat till convergence 3:

V π t-1 ← approximate using a linear projection over φ(s)

4:

C t-1 ← approximate using a linear projection over η(s, qt) 5:

πt ← arg min s∈S C t-1 + γV π t-1 (s)

6: End

Instead, we apply the basic framework shown in Algorithm 1. The initial policy π 0 and cost model C 0 can be initialized arbitrarily or using some intelligent heuristics. In line 5 of Algorithm 1, we have tried to overcome the issues at the root of the curse of dimensionality by juxtaposing the original problem with approximated per-stage cost and cost-to-go function. Firstly, we map a configuration to a vector of associated feature φ(s). Then, we approximate the cost-to-go function by a linear model θ T φ(s) with parameter θ. It is extracted from a reduced subspace S of configuration space S that makes the search for optimal policy computationally cheaper. Finally, we learn the per-stage cost C(s, s , q) by a linear model ζ T η(s, q) with parameter ζ. This method does not need any prior knowledge of the cost model, rather it learns the model iteratively. Thus, we have resolved shortcomings of policy iteration and the need of predefined cost model for the performance tuning problem in our algorithm. These methods are depicted and analysed in the following sections.

Reducing the Search Space

In order to reduce the size of search space in line 5 of Algorithm 1, we filter the configurations that satisfy certain necessary conditions deduced from an optimal policy. Proposition 1. Let s be any configuration and q be any observed query. Let π * be an optimal policy. If π * (s, q) = s , then cost(s, q) -cost(s , q) 0. Furthermore, if δ(s, s ) > 0, i.e., if the configurations certainly change after a query, then cost(s, q) -cost(s , q) > 0.

Proof. Since π * (s, q) = s , we have

δ(s, s ) + cost(s , q) + γV (s ) cost(s, q) + γV (s) = cost(s, q) + γE min s (δ(s, s ) + cost(s , q) + γV (s )) cost(s, q) + γδ(s, s ) + γV (s ),
where the second inequality is obtained by exploiting triangle inequality δ(s, s ) δ(s, s ) + δ(s , s ), as δ is a quasi-metric on S.

This infers that cost(s, q) -cost(s , q) (1 -γ)δ(s, s ) 0.

The assertion follows.

By Proposition 1, if π * is an optimal policy and s = π * (s, q) = s, then cost(s, q) > cost(s , q). Thus, we can define a reduced subspace as

S s,q = {s ∈ S | cost(s, q) > cost(s , q)}.
Hence, at each time t, we can solve

π t = arg min s∈S s t-1 , qt δ(s t-1 , s) + cost(s, qt ) + γV πt-1 (s) . (3)
Next, we design an algorithm that converges to an optimal policy through searching in the reduced set S s,q .

Modified Policy Iteration with Cost Model Learning

We calculate the optimal policy using the least square policy iteration (LSPI) [START_REF] Lagoudakis | Least-squares policy iteration[END_REF]. If for any policy π, there exists a vector θ such that we can approximate V π (s) = θ T φ(s) for any configuration s, then LSPI converges to the optimal policy. This mathematical guarantee makes LSPI a useful tool to solve the MDP as defined in Section 3. But the LSPI algorithm needs a predefined cost model to update the policy and evaluate the cost-to-go function. It is not obvious that any form of cost model would be available and as mentioned in Section 1, pre-defined cost models may be critically wrong. This motivates us to develop another form of the algorithm, where the cost model can be equivalently obtained through learning.

Assume that there exists a feature mapping η such that cost(s, q) ≈ ζ T η(s, q) for some vector ζ. Changing the configuration from s to s can be considered as executing a special query q(s, s ). Therefore we approximate δ(s, s ) = cost(s, q(s, s )) ≈ ζ T η(s, q(s, s )).

The vector ζ can be updated iteratively using the well-known recursive least squares estimation (RLSE) [START_REF] Young | Recursive least squares estimation[END_REF] as shown in Algorithm 2, where η t = η(s t-1 , qt ) and ˆ t = (ζ t-1 ) T η t -cost(s t-1 , qt ) is the prediction error. Combining RLSE with LSPI, we get our cost-model oblivious algorithm as shown in Algorithm 3.

Algorithm 2 Recursive least squares estimation.

1: procedure RLSE(ˆ t , B t-1 , ζ t-1 , η t ) 2: γ t ← 1 + (η t ) T B t-1 η t 3: B t ← B t-1 -1 γ t (B t-1 η t (η t ) T B t-1 )
4:

ζ t ← ζ t-1 -1 γ t B t-1 η t ˆ t 5: return B t , ζ t .
6: end procedure

In Algorithm 3, the vector θ determines the current policy. We can make a decision by solving the equation in line 6. The values of δ(s t-1 , s) and cost(s, qt ) are obtained from the approximation of the cost model. The vector θ t is used to approximate the cost-to-go function following the current policy. If θ t converges, then we update the current policy (line 14-16).

Instead of using any heuristics we initialize policy π 0 as initial configuration s 0 and the cost-model C 0 as 0, as shown in the lines 1-3 of Algorithm 3. Proposition 2. If for any policy π, there exists a vector θ such that V π (s) = θ T φ(s) for any configuration s, Algorithm 3 will converge to an optimal policy. Proof. Let V : S → R be a set of bounded, real-valued functions. Then V is a Banach space with the norm v = v ∞ = sup |v(s)| for any v ∈ V. Let qt be the just received query. 6:

st ← arg min

s∈S s t-1 , qt (ζ t-1 ) T η(st-1, q(st-1, s)) + (ζ t-1 ) T η(s, qt) + γθ T φ(s) 7:
Change the configuration to st.

8:

Execute query qt. 9:

Ĉt ← δ(st-1, st) + cost(st, qt). 10:

ˆ t ← (ζ t-1 ) T η(st-1, qt) -cost(st-1, qt) 11: B t ← B t-1 - B t-1 φ(s t-1 )(φ(s t-1 )-γφ(s t )) T B t-1
1+(φ(s t-1 )-γφ(s t )) T B t-1 φ(s t-1 ) . 12:

θ t ← θ t-1 + ( Ĉt -(φ(s t-1 )-γφ(s t ) T θ t-1 )B t-1 φ(s t-1 ) 1+(φ(s t-1 )-γφ(s t )) T B t-1 φ(s t-1 )
.

13:

(B t , ζ t ) ← RLSE(ˆ t , B t-1 , ζ t-1 , η t ) 14: if (θ t ) converges then 15: θ ← θ t . 16:
end if 17: end for If we redefine our problem in the reduced search space, we get:

arg min π∈U E ∞ t=1 γ t-1 (δ(s t-1 , s t ) + cost(s t , q))
such that : s t = π(s t-1 , q), s t ∈ S st-1,q , for t 1

(4)
Then Algorithm 3 is analogous to LSPI over the reduced search space. For this new problem given by Equation ( 4), Algorithm 3 converges to a unique cost-to-go function Ṽ ∈ V. We need to show that V * = Ṽ . That means we need to prove the cost-to-go function estimate by Algorithm 3 is the optimal one. Let us define the process of updating policy as a mapping M : V → V. Now based on Equation (2), it can be expressed as

Mv(s) = E min s ∈Ss,q (δ(s, s ) + cost(s , q) + γv(s )) .
For a particular configuration s and query q, let a * s,q (v) = arg min s ∈Ss,q (δ(s, s ) + cost(s , q) + γv(s )) .

Assume that Mv(s) Mu(s). Then

0 Mv(s) -Mu(s) = E δ(s, a * s,q (v)) + cost(a * s,q (v), q) + γv(a * s,q (v)) -E δ(s, a * s,q (u)) + cost(a * s,q (u), q) + γu(a * s,q (u)) E δ(s, a * s,q (u)) + cost(a * s,q (u), q) + γv(a * s,q (u)) -E δ(s, a * s,q (u)) + cost(a * s,q (u), q) + γu(a * s,q (u)) = γE v(a * s,q (u)) -u(a * s,q (u)) γE [ v -u ] = γ v -u .
Thus we can conclude, |Mv(s) -Mu(s)| γ|v(s) -u(s)| for all configuration s ∈ S. From the definition of our norm, we can write

sup s∈S |Mv(s) -Mu(s)| = Mv -Mu γ v -u .
This means that if 0 γ < 1, M is a contraction mapping. By [28, Proposition 3.10.2], there exists a unique v * such that Mv * = v * , such that for an arbitrary v 0 , the sequence v n generated by v n+1 = Mv n converges to v * . By the property of convergence of LSPI [START_REF] Lagoudakis | Least-squares policy iteration[END_REF], v * = Ṽ . From Proposition 1, the optimal cost-togo function V * also satisfies MV * = V * . Hence V * = Ṽ and the property of convergence of LSPI is preserved in Algorithm 3.

Adaptive Database Tuning with Regularized Cost-Model Learning

In the results that we will present in Section 7.3, we will observe a higher variance of Algorithm 3 for index tuning than that of the state-of-art WFIT algorithm [START_REF] Schnaitter | Semi-automatic index tuning: Keeping dbas in the loop[END_REF]. This high variance is caused mainly due to the absence of the cost model. As Algorithm 3 decides the policy depending on the estimated cost model, any error in the cost model causes instability in its outcome.

The process of cost-model estimation by accumulating information of incoming queries is analogous to approximating a function online from its incoming samples. Here, the function is the per-stage cost model C : S × S × Q → R. Here, Q is the extended set of queries given by Q ∪ {q(s, s ) | s, s ∈ S}. We obtain this Q by considering configuration updates as special queries, as explained in Section 4.3. Now, the per-stage cost function can be defined as

C(s t-1 , s t , qt ) = cost(s t-1 , q(s t-1 , s t )) + cost(s t , qt )
This equation shows that if we consider changing the configuration from s to s as executing a special query q(s, s ), approximating the function cost : S × Q → R in turn approximates the per-stage cost.

As explained in the previous section, we approximate cost online using linear projection to the feature space of the observed state and query. At each step we obtain some vector ζ such that cost(s, q) ≈ ζ T η(s, q). Here, η(s, q) is the feature vector corresponding to state s and query q. In order to obtain the optimal approximation, we initialize with an arbitrary ζ and then recursively improve our estimate of ζ using recursive least squares estimation (RLSE) algorithm [START_REF] Young | Recursive least squares estimation[END_REF]. But the issues with RLSE are: i. It tries to minimize the square error per step

ˆ 2 t = (ζ t-1 ) T η t -cost(s t-1 , qt ) 2
which is highly sensitive to outliers. If RLSE faces some query or configuration update which is very different from the previously observed queries, the estimation of ζ can change drastically. ii. The algorithm becomes unstable if the components of η(s, q) are highly correlated. This may happen when the algorithm passes through a series of related queries.

As the reinforcement learning algorithm uses the estimated cost model to decide policies and to evaluate them, error or instability in the estimated cost model at any step affects its performance. Specifically, large deviations arise in the estimated cost model due to the queries which are far from the previously learned distribution. This costs the learning algorithm some time to adapt. It also affects the policy and evaluation of the present state and action. We thus propose to use a regularized cost-model estimator instead of RLSE, which is less sensitive to outliers and relatively stable, so as to improve the performance of Algorithm 3 and decrease its variance.

Regularized Cost-Model Estimator

In order to avoid the effect of outliers, we can penalize high variance of ζ by adding a regularization term with the squared prediction error of RLSE. Thus at time step t, the new estimator will try to find

ζ t = arg min ζ P t given ˆ t , B t-1 , ζ t-1 , η t (5)
such that:

P t := ˆ 2 t + λ ζ t-1 2 2 = ζ t-1 , η t -cost(s t-1 , qt ) 2 + λ ζ t-1 , ζ t-1 .
Here, λ > 0 is the regularization parameter. Square of L 2 -norm, ζ 2 2 , is the regularization function. η t := η(s t-1 , qt ) is the feature vector of state s t-1 and query qt . We call this squared error the loss function L t defined at time t for a given choice of ζ t . Thus,

L t (ζ t ) := ζ t , η t -cost(s t-1 , qt ) 2 .
The dual of this problem can be considered as picking up such an ζ t inside an ndimensional Euclidean ball B n λ of radius s(λ) that minimizes the error ˆ 2 t . From an optimization point of view, we choose

ζ t inside B n λ := ζ | ζ 2 2
s(λ) and ζ ∈ R n rather than searching for it in the whole space R n . This estimator penalizes any drastic change in the cost model due to some outlier query. If some query tries to pull ζ t out of B n λ , this estimator regularizes ζ t at the boundary. It also induces sparsity in the components of estimating vector ζ that eliminates the instability due to highly correlated queries.

Algorithm 4 Regularized cost-model estimation.

1: Initialize ζ 0 = 0 and R 0 = εI. 2: for t=1,2,3,. . . do 3:

ˆ t ← (ζ t-1 ) T η t -cost(st-1, qt) 4: γ t ← λ + (η t ) T R t-1 η t 5: R t ← R t-1 -1 γ t (R t-1 η t (η t ) T R t-1 ) 6: ζ t ← ζ t-1 -1 γ t R t-1 η t ˆ t 7: return R t , ζ t 8: end for
The online penalized cost-model estimation algorithm obtained from this formulation is shown in Algorithm 4. Generally, the optimal values of ε and λ are decided using a cross-validation procedure. In Section 6.4, we are going to derive the optimal value of ε and a probable estimation for λ for the index tuning problem. This will decide optimal values of the hyper-parameters for a given set of workload with theoretical performance bounds.

Performance Bound

We can depict this online cost-model estimation task as a simple game between a decision maker and an adversary [START_REF] Rockafellar | Convex analysis[END_REF]. In database tuning, the decision maker is our cost-model estimating algorithm and the adversary is the workload providing an uncertain sequence of queries. Then, we can formulate the game as Algorithm 5.

Algorithm 5 Cost-model Estimation Game. We can define the regret of this game after time step T as,

Reg T := T t=1 L t (ζ t ) - T t=1 L t (ζ OPT ) (6)
where ζ OPT is the solution picked up by an offline expert that minimizes the cumulative loss after time step T . Reg T is the difference between cumulative sum of errors up to time T obtained using Algorithm 4 and the optimal offline algorithm. This regret term captures deviation of the cost-model estimated by the Algorithm 5 from the computable optimal cost model.

As the loss function L(ζ) is the square of the error between estimated and actual values of cost at time t, it is a convex function over the set of ζ. According to the analysis given in [START_REF] Rockafellar | Convex analysis[END_REF], we can canonically describe our estimation model as a scheme to develop a Legendre potential function Φ(ζ OPT ) with time t for the given workload, where the initial value of potential is given by:

Φ 0 (ζ OPT ) := ζ OPT 2
and its value at time t is updated as

Φ t (ζ OPT ) := Φ t-1 (ζ OPT ) + 1 λ L t (ζ t ).
Now, we can re-write Equation ( 5) as:

ζ t = arg min ζ∈B n λ D Φ0 (ζ OPT , ζ t-1 ) + 1 λ (∇L t-1 (ζ t-1 )) T ζ t-1 (7)
Here, D Φ0 (ζ OPT , ζ t-1 ) is the Bregman divergence [START_REF] Nielsen | Matrix information geometry[END_REF] between ζ OPT and ζ t-1 along the potential field Φ 0 (ζ OPT ). This term in Equation [START_REF] Benedikt | Data cleaning for decision support[END_REF] inclines Algorithm 4 to choose such a ζ which is nearest to optimal ζ OPT on the ζ 2 manifold. Also, ∇L t-1 (ζ t-1 ) T ζ t-1 is the change of the loss function in the direction of ζ t-1 . Minimization of this term is equivalent to selection of such a ζ t that minimizes the corresponding loss. Thus, the ζ t picked up by the Algorithm is the one that minimizes a linear combination of these two terms weighted by λ. From this formulation we can obtain the following lemma for the regret bound.

Lemma 1. After time step T , the upper bound of the regret of Algorithm 4 can be given by

Reg T λ ζ OPT 2 + 1 λ T t=1 ˆ t 2 (η t ) T R t η t . (8)
Proof. Applying Theorem 1 of [START_REF] Warmuth | Continuous and discrete-time nonlinear gradient descent: Relative loss bounds and convergence[END_REF] on Equation ( 7) we get the inequalities,

Reg T λ D Φ0 (ζ OPT , ζ 0 ) -D Φ T (ζ OPT , ζ T +1 ) + T t=1 D Φt (ζ t , ζ t+1 ) λ D Φ0 (ζ OPT , ζ 0 ) + T t=1 D Φt (ζ t , ζ t+1 ) .
From the definition of the Legendre potential we get:

Φ t (ζ) = Φ t-1 (ζ) + 1 λ L t (ζ) = ζ 2 + T t=1 ζ, η t -cost(s t-1 , qt ) 2 = ζ T I + 1 λ T t=1 η t (η t ) T ζ -ζ T 1 λ T t=1 cost(s t-1 , qt )η t + T t=1 cost(s t-1 , qt ) 2 = ζ T (R T ) -1 ζ -ζ T b T + C T where b T = T t=1 c t η t and C T = T t=1 cost(s t-1 , qt )) 2 .
Thus, the dual of the potential can be given by

Φ * t (ζ) = ζ T R T ζ -2ζ T R T b T + (b T ) T R T b T Now,
from the definition of Φ 0 and properties of Bregman divergence,

D Φ0 (ζ OPT , ζ 0 ) = D ζ OPT 2 (ζ OPT , ζ 0 ) = ζ OPT 2 and D Φt (ζ t , ζ t+1 ) = D Φ * t ∇Φ t (ζ t+1 ), ∇Φ t (ζ t ) = D Φ * t 0, ∇Φ t (ζ t ) = D Φ * t 0, 1 λ ∇L t (ζ t ) = 1 λ 2 ∇L t (ζ t ) T R t ∇L t (ζ t ) = 1 λ 2 ζ, η t -cost(s t-1 , qt ) 2 (η t ) T R t η t = 1 λ 2 ˆ t 2 (η t ) T R t η t .
By replacing these results in the aforementioned inequality we get:

Reg T λ ζ OPT 2 + 1 λ T t=1 ˆ t 2 (η t ) T R t η t . Lemma 2. If R 0 ∈ R n×n and invertible, (η t ) T R t η t = 1 - det(R t ) det(R t-1 ) ∀t = 1, 2, . . . , T (9)
Proof. From [START_REF] Lai | Least squares estimates in stochastic regression models with applications to identification and control of dynamic systems[END_REF], we get if there exists an invertible matrix B ∈ R n×n such that A = B + xx T , where x ∈ R n , then

x T A -1 x = 1 - det(B) det(A) (10)
As, per Algorithm 4, R 0 = εI, it is invertible. Since (R t ) -1 = (R t-1 ) -1 + η t (η t ) T , by the Sherman-Morrison formula, all R t 's are invertible for t 0. Thus, simply replacing A by (R t ) -1 and B by (R t-1 ) -1 in Equation ( 10), we obtain

(η t ) T R t η t = 1 - det((R t-1 ) -1 ) det((R t ) -1 ) = 1 - det(R t ) det(R t-1 ) since, det((R t ) -1 ) = 1 det(R t ) .
Using Lemmas 1 and 2, we finally derive the regret bound for the regularized cost-model estimator in the following theorem.

Theorem 1. If we consider the error as a bounded function such that 0 ˆ t 2

E max and η t ∞ δ, Reg T λ ζ OPT 2 + E max λ nln 1 + εδ 2 T n -(n -1)ln(ε) (11)
where R 0 = εI.

Proof. Let us assume the squared error has an upper bound E max for a given workload. Under this assumption, we get from Equations ( 8) and ( 9),

Reg T λ ζ OPT 2 + E max λ T t=1 1 - det(R t ) det(R t-1 ) λ ζ OPT 2 - E max λ T t=1 ln det(R t ) det(R t-1 ) = λ ζ OPT 2 + E max λ ln det(R 0 ) det(R T ) = λ ζ OPT 2 + E max λ ln(ε) -ln(det(R T )) = λ ζ OPT 2 + E max λ ln(ε) + ln det 1 ε I + T t=1 η t (η t ) T = λ ζ OPT 2 + E max λ n k=1 ln (1 + ελ k ) -(n -1) ln(ε) . Because det 1 ε I + T t=1 η t (η t ) T = ε -n det I + ε T t=1 η t (η t ) T = ε -n n k=1 (1 + ελ k )
where λ 1 , . . . , λ n are eigenvalues of the matrix T t=1 η t (η t ) T . As the eigenvalues of T t=1 η t (η t ) T are equal to the eigenvalues of its Gram matrix G ij = (η i ) T η j , we can write

n k=1 λ k = T race(G) = T t=1 (η t ) T η t δ 2 T
where η t ∞ δ, that is, the maximum value of any component of η is bounded by δ. In the above inequality, the equality holds if and only if λ 1 = λ 2 = . . . = λ n = δ 2 T n . By applying this condition, we get the regret bound as

Reg T λ ζ OPT 2 + E max λ nln 1 + εδ 2 T n -(n -1)ln(ε) .
This theorem shows that our estimation of the cost model using Algorithm 4 is always upper bounded by a constant value depending on the optimal solution added with a term that increases with time logarithmically. This shows that the regret, which is the cumulative deviation of the cost model computed by Algorithm 4 with respect to the optimal one, increases very slowly with time. That means the error of estimation in each and every time step is considerably small.

Case Study: Index Tuning

In this section we present COREIL (for Cost-model Oblivious REInforcement Learning algorithm) and its regularized version, rCOREIL. COREIL and rCOR-EIL instantiate Algorithm 3 taking as cost-model estimators Algorithms 2 and 4 respectively. Both of them tune the configurations differing in their secondary indexes and handle the configuration changes corresponding to the creation and deletion of indexes. COREIL uses reinforcement learning approach to solve the index tuning problem on-the fly. It projects index tuning as an MDP and applies Algorithm 3 to solve it. On the other hand, rCOREIL uses the regularized cost-model estimator, described in Section 5.1; rCOREIL's regularized estimator affords it to leverage the fact that if we serve the learning algorithm with a better cost-model to evaluate its policy better, it will perform better. In this section, we also define the feature mappings φ and η for both COREIL and rCOREIL. They are used to approximate the cost-to-go function V and the cost function respectively. At the end of this section we prove tighter performance bounds for Algorithm 4 in case of index tuning. We also derive optimal values of the parameters λ and ε for a given workload.

Reducing the Search Space

Let I be the set of indexes that can be created. Each configuration s ∈ S is an element of the power set 2 I . For example, 7 attributes in a schema of R yield a total of 13699 indexes and a total of 2 13699 possible configurations. Such a large search space invalidates a naive brute-force search for the optimal policy. For any query q, let r(q) be a function that returns a set of recommended indexes. This function may be already provided by the database system (e.g., as with IBM DB2), or it can be implemented externally [START_REF] Agrawal | Automated selection of materialized views and indexes in sql databases[END_REF]. Let d(q) ⊆ I be the set of indexes being modified (update, insertion or deletion) by q. We can define the reduced search space as

S s,q = {s ∈ S | (s -d(q)) ⊆ s ⊆ (s ∪ r(q))}. ( 12
)
Deleting indexes in d(q) will reduce the index maintenance overhead and creating indexes in r(q) will reduce the query execution cost. Note that the definition of S s,q here is a subset of the one defined in Section 4.2 which deals with the general configurations.

Note that for tree-structured indexes (e.g., B + -tree), we could further consider the prefix closure of indexes for optimization. For any configuration s ∈ 2 I , define the prefix closure of s as s = {i ∈ I | i is a prefix of an index j for some j ∈ s}.

(

) 13
Thus in Equation ( 12), we use r(q) to replace r(q) for better approximation.

The intuition is that in case of i / ∈ s but i ⊆ s we can leverage the prefix index to answer the query.

Defining the Feature Mapping φ

Let V be the cost-to-go function following a policy. As mentioned earlier, Algorithm 3 relies on a proper feature mapping φ that approximates the cost-to-go function as V (s) ≈ θ T φ(s) for some vector θ. The challenge lies in how to define φ under the scenario of index tuning. Both in COREIL and rCOREIL, we define it as

φ s (s) := 1, if s ⊆ s -1, otherwise
for each s, s ∈ S. Let φ = (φ s ) s ∈S . Note that φ ∅ is an intercept term since φ ∅ (s) = 1 for all s ∈ S. The following proposition shows the effectiveness of φ for capturing the values of the cost-to-go function V . Proposition 3. There exists a unique θ = (θ s ) s ∈S which approximates the value function as

V (s) = s ∈S θ s φ s (s) = θ T φ(s). ( 14
)
Proof. Suppose S = {s 1 , s 2 , . . . , s |S| }. Note that we use superscripts to denote the ordering of elements in S. Let V = (V (s)) T s∈S and M be a |S| × |S| matrix such that

M i,j = φ s j (s i ).
Let θ be a |S|-dimension column vector such that M θ = V . If M is invertible then θ = M -1 V and thus Equation ( 14) holds. We now show that M is invertible. Let ψ be a |S| × |S| matrix such that

ψ i,j = M i,j + 1.
We claim that ψ is invertible and its inverse is the matrix τ such that

τ i,j = (-1) |s i |-|s j | ψ i,j .
To see this, consider

(τ ψ) i,j = 1 k |S| (-1) |s i |-|s k | ψ i,k ψ k,j = sj ⊆s k ⊆si (-1) |s i |-|s k | .
Therefore (τ ψ) i,j = 1 if and only if i = j. By the Sherman-Morrison formula, M is also invertible.

However, for any configuration s, θ(s) is a |2 I |-dimensional vector. In order to reduce the dimensionality, the cost-to-go function can be approximated by V (s) ≈ s ∈S,|s | N θ s φ s (s) for some integer N . Here we assume that the collaborative benefit among indexes could be negligible if the number of indexes exceeds N . In particular when N = 1, we have

V (s) ≈ θ 0 + i∈I θ i φ i (s). ( 15
)
where we ignore all the collaborative benefits among indexes in a configuration. This is reasonable since any index in a database management system is often of individual contribution for answering queries [START_REF] Ramakrishnan | Database management systems[END_REF]. Therefore, we derive φ from Equation ( 15) as φ(s) = (1, (φ i (s)) T i∈I ) T . By using this feature mapping φ, both COREIL and rCOREIL approximate the cost-to-go function V (s) ≈ θ T φ(s) for some vector θ.

Defining the Feature Mapping η

A good feature mapping for approximating functions δ and cost must take into account both the benefit from the current configuration and the maintenance overhead of the configuration.

To capture the difference between the index set recommended by the database system and that of the current configuration, we define a function β(s, q) = (1, (β i (s, q)) T i∈I ) T , where

β i (s, q) :=      0, i / ∈ r(q) 1,
i ∈ r(q) and i ∈ s -1, i ∈ r(q) and i / ∈ s.

If the execution of query q cannot benefit from index i then β i (s, q) always equals zero; otherwise, β i (s, q) equals 1 or -1 depending on whether s contains i or not. For tree-structured indexes, we could further consider the prefix closure of indexes as defined in Equation ( 13) for optimization.

On the other hand, to capture whether a query (update, insertion or deletion) modifies any index in the current configuration, we define a function α(s, q) = (α i (s, q)) i∈I where α i (s, q) = 1, if i ∈ s and q modify i 0, otherwise.

Note that if q is a selection query, α trivially returns 0.

By combining β and α, we get the feature mapping η = (β T , α T ) T used in both of the algorithms. It can be used to approximate the functions δ and cost as described in Section 4.3.

Performance Bounds for Regularized COREIL

rCOREIL applies Algorithm 4 for cost-model estimation, while COREIL uses RLSE for this. If we follow Algorithm 3, on line 13 rCOREIL calls the regularized cost-model estimator with arguments ˆ t , R t-1 , ζ t-1 , η t instead of RLSE. Following Theorem 1 and the construction of the feature map in Section 6.3, Proposition 4 gives a tighter regret bound for the cost-model estimation of rCOREIL.

Proposition 4. If we consider the error as a bounded function such that 0 ˆ t 2 E max :

Reg rCOREIL T λ ζ OP T 2 + E max λ [2nlnT -nlnn] (16)
and the optimal value for ε is given by:

ε * = n 2 -n T .
Proof. From Section 6.3, η t ∞ 1. Equation ( 11) transforms into

Reg rCOREIL T λ ζ OP T 2 + E max λ nln 1 + T n -(n -1)ln(ε) .
Now, we determine the optimal value of ε by minimizing the RHS of above inequality as this will impose tighter limit on the bound. Thus,

∂(RHS) ∂ε ε * =0 = 0.
By solving this, we get ε * = n 2 -n T . Substituting this value in the previous inequality gives us the regret bound for regularized COREIL algorithm as Similarly, we can also find out the optimal value of λ that will make the upper bound tightest.

Reg rCOREIL T λ ζ OP T 2 + E max λ [2nln(T ) -nln(n)] .
Corollary 1. If the value of optimal solution ζ OP T can be predicted beforehand, the optimal value of λ is given by

λ * = E max ζ OP T 2 [2nln(T ) -nln(n)]
where the stopping time T is given.

Proof. As an optimal λ will minimize the RHS of Equation ( 16), we get it by setting the partial derivative of the RHS with respect to λ as zero. This simply gives us,

λ * = Emax ζ OP T 2 [2nln(T ) -nln(n)].
Substituting the optimal value of λ in Equation ( 16) for a given T and ζ OP T , we get

Reg rCOREIL T ζ OP T 2 + E max [2nln(T ) -nln(n)] .
For large n and comparatively smaller T , [2nln(T ) -nln(n)] is a negative number that makes the plausible error in cost-model estimation much smaller than even the magnitude of the optimal ζ vector. This shows the guarantee on the quality of the cost-model estimated by rCOREIL once the parameters are properly set.

Performance Evaluation

In this section, we present an empirical evaluation of COREIL and rCOREIL through two sets of experiments. In the first set of experiments, we implement a prototype of COREIL in Java. We compare its performance with that of the state-of-the-art WFIT algorithm [START_REF] Schnaitter | Semi-automatic index tuning: Keeping dbas in the loop[END_REF] (briefly described in Section 7.2). In the results, we can see that COREIL shows competitive performance with WFIT but has higher variance. This validates the efficiency of the reinforcement learning approach to solve the index tuning problem on the fly. This shows that, even without any assumption of a pre-determined cost model, it is possible to perform at the level of the state-of-the-art.

In the second set of experiments, we evaluate the performance of rCOREIL with respect to COREIL. The results show enhancements in performance by rCOREIL as reasoned in Section 5. This validates the claim in Section 5 that the higher variance of COREIL is due to suboptimal use of the RLSE algorithm. It also establishes the fact that if we serve the learning algorithm with an enhanced estimation of cost-model, it improves the performance substantially. In these experiments, we also check the sensitivity of rCOREIL with respect to the parameter λ and cross-validate the optimal value for the given workload.

Dataset and Workload

The dataset and workload is conforming to the TPC-C specification [START_REF] Raab | TPC-C -the standard benchmark for online transaction processing (OLTP)[END_REF] and generated by the OLTP-Bench tool [START_REF] Difallah | Oltp-bench: An extensible testbed for benchmarking relational databases[END_REF]. The 5 types of transactions in TPC-C are distributed as NewOrder 45%, Payment 43%, OrderStatus 4%, Delivery 4% and StockLevel 4%. Each of these transactions are associated with 3 ∼ 5 SQL statements (query/update). The scale factor used throughout the experiments is 2. We do not leverage any repetition or periodicity of the workload in our approach; still for robustness there may be up to 10% of repetition of queries. Note that [START_REF] Schnaitter | Semi-automatic index tuning: Keeping dbas in the loop[END_REF] additionally uses the dataset NREF in its experiments. However, this dataset and workload are not publicly available.

WFIT: Brief Description

WFIT is proposed in [START_REF] Schnaitter | Semi-automatic index tuning: Keeping dbas in the loop[END_REF] as a method of semi-automatic index tuning. This algorithm keeps the database administrator "in the loop" by generating recommendations. These recommendations are generated through a feedback loop originating from the administrator's preferences. This process is based on the Work Function Algorithm [START_REF] Borodin | Online Computation and Competitive Analysis[END_REF]. In order to determine the change of configuration, WFIT considers all the queries observed in the past. Then it solves a deterministic problem of minimizing the total processing cost. However, while doing so, it assumes the existence of a pre-determined cost model served by the database system or administrator. Due to use of a pre-defined cost model for all the datasets and workloads it faces the problems discussed in the Introduction. Results documented in the following sections will show the importance of a reinforcement learning approach to make the process generic and cost-model oblivious.

COREIL: Experiments and Results

Experimental Set-up We conduct all the experiments on a server running IBM DB2 10.5. The server is equipped with Intel i7-2600 Quad-Core @ 3.40 GHz and 4 GB RAM. We measure wall-clock times for execution of all components. Specially, for execution of workload queries or index creating/dropping, we measure the response time of processing corresponding SQL statement in DB2. Additionally, WFIT uses the what-if optimizer of DB2 to evaluate the cost. In this setup, each query is executed only once and all the queries were generated from one execution history.

Efficiency Figure 1 shows the total cost of processing TPC-C queries for online index tuning of COREIL and WFIT. Total cost consists of the overhead of corresponding tuning algorithm, cost of configuration change and that of query execution. Results show that, after convergence, COREIL has lower processing cost most of the time. But COREIL converges slower than WFIT, which is expected since it does not rely on the what-if optimizer to guide the index creations. 4 With respect to the whole execution set, the average processing cost of COREIL (451 ms) is competitive to that of WFIT (452 ms). However, if we calculate the average processing cost of the 500 th query forwards, the average performance of COREIL (357 ms) outperforms that of WFIT (423 ms). To obtain further insight from these data, we study the distribution of the processing time per query, as shown in Figure 2. As can be seen, although COREIL exhibits larger variance in the processing cost, its median is significantly lower that that 0 500 1,000 1,500 2,000 2,500 3,000 of WFIT. All these results confirms that COREIL has better efficiency than WFIT under a long term execution. Figures 3 and4 show analysis of the overhead of corresponding tuning algorithm and cost of configuration change respectively. By comparing Figure 1 with Figure 3, we can see that the overhead of the tuning algorithm dominates the total cost and the overhead of COREIL is significantly lower than that of WFIT. In addition, WFIT tends to make costlier configuration changes than COREIL, which is reflected in a higher time for configuration change. This would be discussed further in the micro-analysis. Note that both methods converge rather quickly and no configuration change happens beyond the 700th query.

A possible reason for the comparatively smaller overhead of COREIL with respect to WFIT, in addition to not relying on a possibly costly what-if optimizer, is the MDP structure. In MDPs, all the history of the system is assumed to be summarized in the present state and the cost-function. Thus, COREIL has to do less book-keeping than WFIT.

Effectiveness To verify the effectiveness of indexes created by the tuning algorithms, we extract the cost of query execution from the total cost. Figure 5 (note the logarithmic y-axis) indicates that the set of indexes created by COREIL shows competitive effectiveness with that created by WFIT, though WFIT is more effective in general and exhibits less variance after convergence. Again, this is to be expected since COREIL does not have access to any cost model for the queries. As previously noted, the total running time is lower for COREIL than COREIL λ300 λ350 λ400 λ450 λ500

1,700 WFIT, as overhead rather than query execution dominates running time for both systems.

We have also performed a micro-analysis to check whether the indexes created by the algorithms are reasonable. We observe that WFIT creates more indexes with longer compound attributes, whereas COREIL is more parsimonious in creating indexes. For instance, WFIT creates a 14-attribute index as shown below.

[S_W_ID, S_I_ID, S_DIST_10, S_DIST_09, S_DIST_08, S_DIST_07, S_DIST_06, S_DIST_05, S_DIST_04, S_DIST_03, S_DIST_02, S_DIST_01, S_DATA, S_QUANTITY] The reason of WFIT creating such a complex index is probably due to multiple queries with the following pattern.

SELECT S_QUANTITY, S_DATA, S_DIST_01, S_DIST_02, S_DIST_03, S_DIST_04, S_DIST_05, S_DIST_06, S_DIST_07, S_DIST_08, S_DIST_09, S_DIST_10 FROM STOCK WHERE S_I_ID = 69082 AND S_W_ID = 1;

In contrast, COREIL tends to create shorter compound-attribute indexes. For example, COREIL created an index [S_I_ID, S_W_ID] which is definitely beneficial to answer the query above and is competitive in performance compared with the one created by WFIT.

rCOREIL: Experiments and Results

Experimental Set-up We run COREIL and rCOREIL, with a set of λ values 300, 350, 400, 450, and 500. The previous set of experiments have already established competitive performance of COREIL with WFIT. In this set we evaluate the basic idea of rCOREIL: providing regularized estimation of costmodel enhances the performance of COREIL and also stabilizes it. We conduct all the experiments on a server running IBM DB2 10.5 with scale factor and time measure, mentioned in the previous set of experiments. But here the server is installed on a 64 bit Windows virtual box with dual-core 2-GB hard disk. It operates in an Ubuntu machine with Intel i7-2600 Quad-Core @ 3.40 GHz and 4 GB RAM. This eventually makes both version of algorithms slower in comparison to the previous physical machine installation.

Efficiency As the offline optimal outcome for this workload is unavailable beforehand, we set an expected range of λ as [300, 600] depending on the other parameters like the number of queries and the size of state space. Figure 6 shows efficiency of COREIL and rCOREIL with different values of λ. As promised by Algorithm 4, variations of rCOREIL are always showing lesser median and variance of total cost. We can also observe from the boxplot, the efficiency is maximum as well as the variance is minimum for λ = 400. As efficiency is the final measure that controls runtime performance of the algorithm, we have considered this as optimal value of λ for further analysis. This process is analogous to cross-validation of parameter λ, where the proved bounds help us to set a range 0 500 1,000 1,500 2,000 2,500 3,000 of values for searching it instead of going through an arbitrary large range of values. Though here we are validating depending upon the result obtained from the whole run of 3,000 queries in the workload, the optimal λ would typically be set, in a realistic scenario, after running first 500 queries of the workload with different parameter values and then choosing the optimal one. Figure 7 shows that rCOREIL with λ = 400 outperforms COREIL. With respect to the whole execution set, the average processing cost of rCOREIL is 1758 ms which is significantly less than that of COREIL (1975 ms). Also the standard deviation of rCOREIL is 90ms which is half of that of COREIL, 180ms. This enhanced performance and low variance establishes the claim that if we serve the learning algorithm with a better estimation of cost-model it will improve. Figures 8 and9 show analysis of the overhead of corresponding tuning algorithms and cost of configuration change respectively. In this set of experiments also, we can see that the overhead of the tuning algorithms dominates their total cost. Here, the overhead of rCOREIL for each query is on an average 207ms lower than that of COREIL. This is more than 10% improvement over the average overhead of COREIL. In addition, rCOREIL (mean: 644ms) also makes cheaper configuration changes than COREIL (mean: 858ms). rCOREIL also converges faster than COREIL as the last configuration update made by rCOREIL occurs at the 335 th query but the last two updates for COREIL occur at the 358 th and 1940 th queries respectively. If we look closely, the 358 th and 1940 th queries in this particular experiment are: In reaction to this, COREIL creates indexes [ORDER_LINE.OL_D_ID,ORDER_LINE. OL_W_ID] and [STOCK.S_W_ID, STOCK.S_QUANTITY] respectively. It turns out that such indexes are not of much use for most other queries (only 6 out of 3000 queries benefit of one of these indexes). COREIL makes configuration updates to tune the indexes for such queries, while the regularized cost model of rCOREIL does not make configuration updates due to rare and complex events, because it regularizes any big change due to such an outlier. Instead, rCOREIL has a slightly higher the overhead to find out the optimal indexes. For example, in the window consisting of 10 queries after the 359 th query average overhead of rCOREIL increases from 1724ms to 1748ms. Effectiveness Like Section 7.3, here also we extract the cost of query execution to verify the effectiveness of indexes created by the tuning algorithms. Figure 10 indicates that the set of indexes created by rCOREIL are significantly more effective than those created by COREIL. We can see the average query execution time of rCOREIL is less than that of COREIL almost by a factor of 10.

SELECT COUNT(DISTINCT (S_I_ID)) AS STOCK_COUNT

At a micro-analysis level, we observe rCOREIL creates only one index with two combined attributes, all other indexes being single-attribute. On the other hand, COREIL creates only one index with a single attribute whereas all other indexes have two attributes. This observation shows that though COREIL creates parsimonious and efficient indexes, rCOREIL shows even better specificity and effectiveness in doing so.

Analysis of Cost Estimator

In order to examine the quality of the three cost estimators used by WFIT, COR-EIL, and rCOREIL to predict the actual cost of query executions or configuration updates, we observe the actual execution time, the estimated cost, and that returned by the what-if optimizer during every run of experiments for COREIL and rCOREIL, respectively. The scatter plot of Figure 11 shows that the what-if cost has significantly less correlation (0.013) with the actual execution time than COREIL (0.1539) Again, the scatter plot of Figure 12 shows the regularized cost estimated by rCOREIL has significantly higher positive correlation (0.1558) than that predicted by the what-if optimizer. This proves that the execution time estimated by COREIL and rCOREIL are significantly more reliable than the ones estimated by what-if optimizer. It can also been observed that rCOREIL provides better estimations: visually, there are many more points at the middle of Figure 12 (left) with positive inclination.

Finally, Figure 13 shows that the regularized cost model estimator of rCOREIL gives a more stable estimation of the cost model than that of COREIL, as the cost model estimated by COREIL (averaged over 20 queries) shows higher variance and also sensitivity to changes in types of queries.

Conclusion

We have presented a cost-model oblivious solution to the problem of performance tuning. We first formalized the problem as a Markov decision process. Then we devised and presented a solution, which addresses both issues of the curse of dimensionality and of over-fitting. We instantiated the problem to the case of index tuning. For this case, we implemented and evaluated the COREIL and rCOREIL algorithms, with and without regularization, respectively. Experiments show competitive performance with respect to the state-of-the-art WFIT algorithm, despite our approach being cost-model oblivious. We also show that as our costmodel estimation becomes crisp and stable the performance of learner improves significantly. Beyond the material presented in this paper, we continue studying the universality and robustness of the COREIL and rCOREIL approaches.

Specially for rCOREIL, it is an interesting problem to determine the optimal regularization parameter on the go or to adapt it with the dynamics of workload. Though now this process causes us only a one-time up-front cost, following the flavour of our approach we would like to perform it online. One possible method is to run COREIL for the first 500 queries and to calculate the costs for different set of regularization parameter values simultaneously for that period. Following that, we can choose the parameter value that causes minimum average estimation of the cost function.

We are now running further empirical performance evaluation tests with other datasets such as TPC-E, TPC-H and dedicated benchmarks for online index tuning [START_REF] Schnaitter | A benchmark for online index selection[END_REF]. For completeness from an engineering perspective, we are considering concurrent access, which was ignored in the algorithm and experiments presented in this paper for the sake of simplicity. We are also going to look at the favourable case of predictable workload such as periodic transactions. Furthermore, we are extending the solution to other aspects of database configuration, including partitioning and replication. For each of these aspects, we need to devise specific and non-trivial heuristics that help curb the combinatorial explosion of the configuration space as well as specific intelligent initialization techniques.

Finally, note that a critical assumption in our approach is that queries arrive sequentially and that nothing is known ahead of time about the workload. Both assumptions do not held in a number of realistic settings: queries can be submitted concurrently to the database, and a workload may often be predictable (such as when it consists of similar transactions, repeated on different data items). We leave for further work the adaptation of rCOREIL to such settings.

Algorithm 3

 3 Least squares policy iteration with RLSE. 1: Initialize the configuration s0. 2: Initialize θ 0 = θ = 0 and B 0 = I. 3: Initialize ζ 0 = 0 and B 0 = εI. 4: for t=1,2,3,. . . do 5:

Fig. 1 .

 1 Fig. 1. Evolution of the efficiency (total time per query) of the two systems from the beginning of the workload (smoothed by averaging over a moving window of size 20)

Fig. 2 .

 2 Fig.2. Box chart of the efficiency (total time per query) of the two systems. We show in both cases the 9th and 91th percentiles (whiskers), first and third quartiles (box) and median (horizontal rule).

Fig. 3 .

 3 Fig. 3. Evolution of the overhead (time of the optimization itself) of the two systems from the beginning of the workload (smoothed by averaging over a moving window of size 20)

Fig. 4 .

 4 Fig. 4. Evolution of the time taken by configuration change (index creation and destruction) of the two systems from the beginning of the workload; no configuration change happens past query #700. All values except the vertical lines shown in the figure are zero.

Fig. 5 .

 5 Fig. 5. Evolution of the effectiveness (query execution time in the DBMS alone) of the two systems from the beginning of the workload (smoothed by averaging over a moving window of size 20); logarithmic y-axis

Fig. 7 .

 7 Fig. 7. Evolution of the efficiency (total time per query) of COREIL and rCOREIL with λ = 400 from the beginning of the workload (smoothed by averaging over a moving window of size 20)

Fig. 9 .

 9 Fig. 9. Evolution of the time taken by configuration change (index creation and destruction) of COREIL and rCOREIL with λ = 400 from the beginning of the workload; no configuration change happens past query #2000. All values except the vertical lines shown in the figure are zero.

Fig. 10 .

 10 Fig. 10. Evolution of the effectiveness (query execution time in the DBMS alone) of COREIL and rCOREIL with λ = 400 from the beginning of the workload (smoothed by averaging over a moving window of size 20); logarithmic y-axis

Fig. 11 .

 11 Fig. 11. Scatter plot of the estimated cost by COREIL and the what-if optimizer vs execution time. Left shows correlation between cost estimated by COREIL and actual execution time (in ms). Right shows (on a log y-axis) correlation between the cost estimated by the what-if optimizer and the actual execution time (in ms) in the same run.

Fig. 12 .

 12 Fig. 12. Scatter plot of the estimated cost by rCOREIL and the what-if optimizer vs execution time. Left shows correlation between cost estimated by rCOREIL and actual execution time (in ms). Right shows (on a log y-axis) correlation between the cost estimated by the what-if optimizer and the actual execution time (in ms) in the same run.

Fig. 13 .

 13 Fig. 13. Evolution of the estimated costs of COREIL and rCOREIL with λ = 400 from the beginning of the workload (smoothed by averaging over a moving window of size 20); logarithmic y-axis

Table 1 .

 1 Automated physical database design

		Index selection	Vert. partitioning	Mixed
	Offline	[1, 20, 45]	[17, 22, 33]

  2. Choice of the configuration s t ∈ S based on q1 , q2 , . . . , qt and s t-1 . 3. Change of configuration from s t-1 to s t . If no configuration change occurs at time t, then s t = s t-1 . 4. Execution of query qt under the configuration s t .

  Box chart of the efficiency (total time per query) of COREIL and its improved version with different values of λ. We show in both cases the 9th and 91st percentile (whiskers), first and third quartiles (box) and median (horizontal rule).

		2,100
	Time (ms)	1,900 2,000
		1,800
	Fig. 6.

  Evolution of the overhead (time of the optimization itself) of COREIL and rCOREIL with λ = 400 from the beginning of the workload (smoothed by averaging over a moving window of size 20)

		2,400	COREIL rCOREIL
		2,200
	Time (ms)	2,000
		1,800
		1,600
		Query #
	Fig. 8.

By convergence we mean the first stable patch in Figure1after the series of high spikes, around the

th query. The convergence point is qualitatively chosen by observing characteristics of the curve.

Acknowledgement

We thank Prof. Haibo Chen for valuable feedback on this work. This research is funded by the National Research Foundation Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme with the SP2 project of the Energy and Environmental Sustainability Solutions for Megacities -E2S2 programme.