Evolution of Index Selection: From Traditional Greedy Approaches to IA2

Table of Links

Abstract and 1. Introduction

1. Related Works

   2.1 Traditional Index Selection Approaches

   2.2 RL-based Index Selection Approaches

2. Index Selection Problem

3. Methodology

   4.1 Formulation of the DRL Problem

   4.2 Instance-Aware Deep Reinforcement Learning for Efficient Index Selection

4. System Framework of IA2

   5.1 Preprocessing Phase

   5.2 RL Training and Application Phase

5. Experiments

   6.1 Experimental Setting

   6.2 Experimental Results

   6.3 End-to-End Performance Comparison

   6.4 Key Insights

6. Conclusion and Future Work, and References

2 Related Works

This section outlines the landscape of existing research on index selection approaches, with a particular focus on traditional index advising methods and reinforcement learning (RL)-based strategies for index advising. Our discussion aims to contextualize the innovations our work introduces in the field.

2.1 Traditional Index Selection Approaches

Traditional index selection methods, despite their evolution over decades, often struggle with the intricate interdependencies between indexes and the dynamic nature of workloads and tend to struggle to deal with the explosion of index candidates’ choices. Early two-stage greedy-based approaches by Chaudhuri et al. [1] and Valentin et al. [14] made significant strides but failed to consider critical interactions among different indexes, key for optimizing database performance. Similarly, while ILP formulations [9] and Cophy [2] brought mathematical precision to modeling the Index Selection Problem (ISP) as a Binary Integer Problem, they too overlooked the complex interplay between indexes and the multifaceted access patterns in contemporary databases.

\ Among traditional index selection algorithms, Extend [11] represents a significant contribution, characterized by its novel recursive strategy that complements its additive approach to building index configurations. This method stands out by not preemptively excluding index candidates and effectively managing index interactions, addressing the limitations of existing approaches for large database instances. Unlike reductive methods, which often lead to prohibitive runtimes or suboptimal solutions by limiting the set of index candidates early in the process, Extend prioritizes both efficiency and solution quality. This approach reflects a broader trend in index advising, seeking to balance the demands of complex analytical workloads with the practical necessities of runtime and scalability.

\

:::info Authors:

(1) Taiyi Wang, University of Cambridge, Cambridge, United Kingdom (Taiyi.Wang@cl.cam.ac.uk);

(2) Eiko Yoneki, University of Cambridge, Cambridge, United Kingdom (eiko.yoneki@cl.cam.ac.uk).

:::

:::info This paper is available on arxiv under CC BY-NC-SA 4.0 Deed (Attribution-Noncommercial-Sharelike 4.0 International) license.

:::

\