Tree-IS: Efficient Index Selection and Optimization Model for Dynamic Workloads.
TL;DR
A network-optimized Monte Carlo tree search (NMCTS)-based index selection model, called tree-based index selection (Tree-IS), is proposed by using the sampling-based reinforcement learning algorithm Monte Carlo tree search (MCTS), achieving the rapid identification of optimal index sets and a significant improvement in query efficiency.
Abstract
Index selection is a crucial component in database query optimization. Traditional database index selection is inefficient when handling large-scale and complex structured query language (SQL) queries, and existing methods often overlook index maintenance costs and the necessity of updates. To address these issues, a network-optimized Monte Carlo tree search (NMCTS)-based index selection model, called tree-based index selection (Tree-IS), is proposed by using the sampling-based reinforcement learning algorithm Monte Carlo tree search (MCTS). This model compresses the action space through workload-driven query template extraction and candidate index (CI) generation techniques. It integrates a novel query state representor and an execution-plan-based index value model (IVM), accurately characterizing the database environment while providing reliable action criteria for index search. On this basis, Tree-IS further leverages a state abstraction network (SAN), a policy network, and a value network (VN) to optimize the search logic of MCTS, achieving the rapid identification of optimal index sets and a significant improvement in query efficiency. Extensive experiments are conducted on popular datasets, including join order benchmark (JOB), transaction processing performance council benchmark holistic (TPC-H), and transaction processing performance council benchmark decision support (TPC-DS), to evaluate the proposed method across multiple metrics. The results demonstrate that the quality of indices selected by the Tree-IS model is significantly superior to that of existing methods.