EDBT 2012 Accepted Paper
The Brown Data Management Research Group has the following paper in EDBT 2012:
- Optimizing Index Deployment Order for Evolving OLAP
Hideaki Kimura, Carleton Coffrin, Alexander Rasin, Stanley Zdonik
Many database applications need hundreds or thousands of indexes to speed up query execution, making performance tuning a difficult task for database administrators. The well-known problem of index selection is to automatically design an optimal set of indexes on behalf of DBAs. This paper brings a new perspective to the problem with a scalable and extensible solution. We study the problem of optimizing the order of index creation to achieve prompt query runtime improvements and also reduce the index deployment time. We found that traditional approaches, such as A* search and MIP, are not suitable for this problem. Instead, we demonstrate that Constraint Programming is an efficient and flexible solution for this problem and its future extension. Our experimental results show that our pruning techniques can reduce the size of the search space by many orders of magnitude, and we verify that our local search algorithm based on CP is a highly scalable and stable method for quickly finding the best known solutions.