Optimizing Index Deployment Order for Evolving OLAP

Many database applications deploy hundreds or thousands of in-dexes to speed up query execution. Despite a plethora of prior work on index selection, designing and deploying indexes remains a dif-ficult task for database administrators. First, real-world businesses often require online index deployment, and the traditional off-line approach to index selection ignores intermediate workload perfor-mance during index deployment. Second, recent work on on-line index selection does not address effects of complex interactions that manifest during index deployment. In this paper, we propose a new approach that incorporates tran-sitional design performance into the overall problem of physical database design. We call our approach Incremental Database De-sign. As the first step in this direction, we study the problem of ordering index deployment. The benefits of a good index deploy-ment order are twofold: (1) a prompt query runtime improvement and (2) a reduced total time to deploy the design. Finding an effec-tive deployment order is difficult due to complex index interaction and a factorial number of possible solutions. We formulate a mathematical model to represent the index order-ing problem and demonstrate that Constraint Programming (CP) is a more efficient solution compared to other methods such as mixed integer programming and A * search. In addition to exact search techniques, we also study local search algorithms that make signif-icant improvements over a greedy solution with minimal computa-tional overhead. Our empirical analysis using the TPC-H dataset shows that our pruning techniques can reduce the size of the search space by many orders of magnitude. Using the TPC-DS dataset, we verify that our local search algorithm is a highly scalable and stable method for quickly finding the best known solutions. 1