LiteSelect: A Lightweight Adaptive Learning Algorithm for Online Index Selection

Using appropriately selected indexes can dramatically improve the performance of query workloads in database systems. Typically, the access patterns of the workloads in real-world applications change frequently. This poses the challenge of automatically adapting the indexes to the changing workload. An effective approach to solve this problem is an online index selection process, which does not assume prior knowledge of the workload pattern but adapts the index configuration based on the history of the workload. In this paper, we address the Online Index Selection problem. Our study on recent learning-based solutions shows that their methods incur significant tuning overhead, making them unsuitable for online-tuning in real-world systems. To address this limitation, we model online index selection as a problem of sequential decision making under uncertainty, and we design a lightweight adaptive learning algorithm called LiteSelect. At the core of LiteSelect is an exponential smoothing method which takes a sequence of observations to estimate index benefits for future queries with unknown distribution. LiteSelect enjoys a fast convergence rate and has low memory cost. We further design optimizations for LiteSelect to control the online tuning overhead and to enhance the solution quality. Our extensive experiments demonstrate that LiteSelect effectively performs online index tuning on different kinds of workloads under widely used benchmarks and greatly outperforms index tuning algorithms using sophisticated learning methods.