A Bayesian Reinforcement Learning Framework for Online Index Tuning

Efficient index tuning is critical to maintain high query performance in database systems with dynamic workloads. Traditional off-line and heuristic-driven tuning methods often incur high overhead due to frequent reconfiguration and fail to adapt to evolving workloads. To overcome these limitations, we address online index selection and formulate it as a sequential decision-making problem under uncertainty. We propose a Bayesian Reinforcement Learning framework that adaptively tunes index configurations based solely on the observed workload history, without requiring prior knowledge of the workload. Our framework leverages Q-learning with Thompson Sampling, a posterior distribution sampling method, to adaptively maintain and refine index configurations over time. The probabilistic mechanism of our approach enables the Q-learning agent to effectively balance exploration and exploitation, allowing it to traverse the vast exponential index configuration space. Our comprehensive experimental evaluation demonstrates that our algorithm excels at online index tuning across a diverse range of workloads on a standard benchmark dataset and outperforms other index tuning algorithms which are based on alternative learning methods.