Volume 16, No. 2
HMAB: Self-Driving Hierarchy of Bandits for Integrated Physical Database Design Tuning
Effective physical database design tuning requires selection of sev- eral physical design structures (PDS), such as indices and materi- alised views, whose combination influences overall system perfor- mance in a non-linear manner. While the simplicity of combining the results of iterative searches for individual PDSs may be appeal- ing, such a greedy approach may yield vastly suboptimal results compared to an integrated search. We propose a new self-driving approach (HMAB) based on hierarchical multi-armed bandit learn- ers, which can work in an integrated space of multiple PDS while avoiding the full cost of combinatorial search. HMAB eschews the optimiser cost misestimates by direct performance observa- tions through a strategic exploration, while carefully leveraging its knowledge to prune the less useful exploration paths. As an added advantage, HMAB comes with a provable guarantee on its expected performance. To the best of our knowledge, this is the first learned system to tune both indices and materialised views in an integrated manner. We find that our solution enjoys superior empirical performance relative to state-of-the-art commercial phys- ical database design tools that search over the integrated space of materialised views and indices. Specifically, HMAB achieves up to 96% performance gain over a state-of-the-art commercial physical database design tool when running industrial benchmarks.