Name
Abstract | ||
|---|---|---|
Many database applications deploy hundreds or thousands of indexes to speed up query execution. Despite a plethora of prior work on index selection, designing and deploying indexes remains a difficult 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 performance 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 transitional design performance into the overall problem of physical database design. We call our approach Incremental Database Design. As the first step in this direction, we study the problem of ordering index deployment. The benefits of a good index deployment order are twofold: (1) a prompt query runtime improvement and (2) a reduced total time to deploy the design. Finding an effective 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 ordering 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 significant improvements over a greedy solution with minimal computational 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2247596.2247630 | EDBT |
Keywords | Field | DocType |
index selection,online index deployment,index deployment,good index deployment order,deploying index,complex index interaction,on-line index selection,local search algorithm,effective deployment order,optimizing index deployment order,exact search technique,constraint programming,mathematical model,database design,search space,indexation | Data mining,Software deployment,Computer science,Constraint programming,Database design,Integer programming,Database administrator,Local search (optimization),Online analytical processing,Database,Scalability | Conference |
Citations | PageRank | References |
2 | 0.37 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hideaki Kimura | 1 | 573 | 37.97 |
| Carleton Coffrin | 2 | 204 | 20.20 |
| Alexander Rasin | 3 | 2950 | 209.48 |
| Stanley B. Zdonik | 4 | 9186 | 1660.15 |