# QRLIT: Quantum Reinforcement Learning for Database Index Tuning
## 3 Related Work
### Classical SMARTIX Algorithm  
The SMARTIX experiments presented by the authors of [3] demonstrated a good balance between the disk space utilized by its index configuration and the performance metric it can achieve, which led to the selection of its evolution [20] as the foundation for the development of a quantum version in our work. As the authors of [20] have made the source code publicly available on GitHub [31], our work is built on that code, containing the adaptations required to fit the quantum algorithm and preserving the original characteristics. For the environment, they utilize a scalable database benchmark, TPC-H [26], which offers a set of features. These features allow for the generation of data for a predefined group of database tables and the construction of 22 instances of queries according to 22 query templates. The TPC-H benchmark schema includes eight database tables, each with a distinct set of attributes. When these attributes are added together, the state space contains 45 of these being available for indexing. Each attribute has two possible actions (CREATE or DROP), which generate a state space with a total of 90 actions, each encoded in a natural decimal value in the interval [0, 89]. The reward is defined by a TPC-H performance metric, expressed in queries per hour (QphH) (Equation (17)), which is composed of two other metrics, namely Power and Throughput. The Power metric is designed to measure the computing speed of simple queries (Equation (16)). The Throughput metric measures the capacity to process the maximum number of queries in the shortest time using parallelism mechanisms (Equation (15)). The equations are composed of several elements. The quantity 3600 represents the number of seconds per hour, while the variable \(\text{QI}(\text{i},0)\) denotes the execution time of query i. The variable \(\text{RI}(\text{j},0)\) symbolizes the execution time of the refresh function j, which is responsible for inserting and removing records from the database. The variable S represents the number of query streams executed, SF the scale factor of the database, \(\text{T}_{\text{s}}\) the total time needed to run the throughput test for the S streams, and finally, @Size represents the size of the database. \[\text{Throughput@Size}=\frac{\text{S}\times 22}{\text{T}_{\text{s}}}\times 3600 \times\text{SF} \tag{15}\]  
\[\text{Power@Size}=\frac{3600}{\sqrt[24]{\prod_{i=1}^{22}\text{QI}(\text{i},0 )\times\prod_{i=1}^{2}\text{RI}(\text{j},0)}}\times\text{SF} \tag{16}\]  
\[\text{QphH@Size}=\sqrt[2]{\text{Power@Size}\times\text{Throughput@Size}} \tag{17}\]  
To address the issue of a tabular policy, SMARTIX uses a variant of Q-learning called Q-learning, with linear feature approximation as its reinforcement learning algorithm [32]. This policy is represented by a set of weights, collectively referred to as a feature vector. A feature is defined as an element of the state space or the action space, so the vector has a total of 135 weights with an additional weight corresponding to a bias. To calculate the Q-value, Equation (18) must be used, where \(\theta\) is the weight value and \(\text{f}_{\text{n}}(\text{s})\) is the value of each feature according to the current state of the environment. \[\hat{\text{Q}}(\text{a},\text{s})\leftarrow\theta_{0}+\theta_{1}\text{f}_{1}( \text{s})+\theta_{2}\text{f}_{2}(\text{s})+...+\theta_{n}\text{f}_{n}(\text{ s}) \tag{18}\]  
However, during the learning process, it is crucial to modify the agent's policy. The algorithm uses the temporal difference strategy with gradient descent (Equation (19)). \[\theta_{\text{i}}\leftarrow\theta_{\text{i}}+\alpha(\text{r}+\gamma\text{ max}_{\text{a}}\hat{\text{Q}}_{\theta}(\text{s}^{\prime},\text{a}^{\prime})- \hat{\text{Q}}_{\theta}(\text{s},\text{a}))\frac{\partial\hat{\text{Q}}_{ \theta}(\text{s}^{\prime},\text{a}^{\prime})}{\partial\theta_{\text{i}}} \tag{19}\]  
The SMARTIX algorithm works as follows: first, the feature vector is populated with random values, and the replay memory is set to an empty state.