On Modeling Adaptive Index Management as Adversarial Search

The initial DB Cracking algorithm has spawned variations, offering distinct techniques and advantages concerning robustness and convergence. However, it is essential to consider the selection of the optimal list of attributes for indexing based on workloads and cost-based refinement of the indices. We propose a DB Cracking-based index management conceptualized as a two-player game to address these requirements. While leveraging the advantages of the underlying DB Cracking method, this model adapts index attribute selection and the degree of index refinement to any query workload. Furthermore, we introduce a new variant, Statistical DB Cracking, to complement the two-player model. Notably, an extensive experimental study validates the superiority of our model in terms of robustness and cost-effectiveness for index management compared to the direct DB Cracking algorithms.