Introduction
Physical database design, particularly the selection of optimal indexes, remains a critical yet challenging task for database administrators (DBAs). While the right set of indexes can accelerate query performance by orders of magnitude, poor choices lead to excessive storage consumption and degraded performance in write-heavy workloads. Traditional tuning tools often fall into the "optimizer trap," relying on internal cost models that may be inaccurate due to stale statistics or oversimplified assumptions. Furthermore, in modern Hybrid Transactional and Analytical Processing (HTAP) environments, the trade-off between analytical query speed and transactional throughput is increasingly difficult to manage manually.
This paper proposes a "self-driving" index tuning approach that replaces manual intervention and flawed cost models with a Multi-Armed Bandit (MAB) framework. By learning directly from observed query execution times, the system provides provable performance guarantees and significantly outperforms existing commercial and deep learning-based solutions.
Methodology: The $C^2UCB$ Framework
The authors frame index selection as a Contextual Combinatorial Bandit problem. In this model, each potential index is treated as an "arm" that can be "pulled" (materialized). The system must balance exploration—testing new indexes to gather performance data—with exploitation—utilizing indexes known to provide high rewards.
The core of the system is the $C^2UCB$ (Contextual Combinatorial Upper Confidence Bound) algorithm. Unlike Deep Reinforcement Learning (DRL) approaches that attempt to model the entire database state, the MAB approach focuses on the relationship between query context and index performance. This simplification allows for faster convergence and stronger theoretical "regret bounds," ensuring the system's performance mathematically converges toward an optimal policy.
Focused Updates and Context Engineering
A key innovation introduced is the concept of Focused Updates. Standard bandit models typically observe a single scalar reward (e.g., total time saved). However, the authors decompose this reward into specific components: data scan gains, index maintenance costs, and "unclaimed" gains. This structured reward signal allows the model to attribute performance changes to specific indexes more accurately, leading to much faster learning.
Additionally, the researchers developed a specialized context encoding for indexes. Since the order of columns in a multi-column index is crucial for its utility (prefix-matching), they employed a value-based encoding scheme ($10^{-j}$ for a column at position $j$). This ensures the bandit can effectively differentiate between similar index structures that have different performance characteristics.
Experimental Evaluation
The proposed system was evaluated against industry-standard benchmarks, including TPC-H, TPC-DS, SSB, and the Join Order Benchmark (JOB). For HTAP scenarios, the CH-BenCHmark and a modified TPC-H Skew workload were used to simulate concurrent analytical and transactional operations.
Performance Results
- Comparison with Commercial Tools: Against a state-of-the-art commercial tuning tool (PDTool), the MAB approach achieved up to a 75% speed-up in dynamic analytical workloads. In HTAP environments, it delivered a 59% speed-up by more effectively identifying and dropping indexes that hindered transactional performance.
- Comparison with Deep RL: The MAB framework outperformed a highly-tuned Double Deep Q-Network (DDQN) agent by 58%. The bandit approach demonstrated significantly higher stability and faster convergence, avoiding the performance volatility often seen in DRL training.
- Resource Efficiency: In several HTAP tests, the MAB-driven system identified configurations that were not only faster but also used up to 83% less memory than those recommended by traditional tools.
Conclusion and Future Work
By shifting from cost-estimation models to a learning-based MAB framework, this research demonstrates that "self-driving" index tuning is both feasible and highly effective. The system's ability to learn from actual performance data makes it resilient to the inaccuracies that plague traditional optimizers.
Future research directions include extending the framework to support index merging—the automated combination of multiple narrow indexes into wider, multi-purpose structures. Additionally, the authors aim to address the "cold-start" problem by pre-training the bandit using synthetic rounds before deployment in live environments. Beyond indexing, this MAB-based approach holds promise for optimizing other physical design elements, such as materialized views and data partitioning.
Summary updated