Index selection for databases: a hardness study and a principled heuristic solution

@article{citeulike:2601614, abstract = {We study the index selection problem: Given a workload consisting of SQL statements on a database, and a user-specified storage constraint, recommend a set of indexes that have the maximum benefit for the given workload. We present a formal statement for this problem and show that it is computationally "hard" to solve or even approximate it. We develop a new algorithm for the problem which is based on treating the problem as a knapsack problem. The novelty of our approach lies in an LP (linear programming) based method that assigns benefits to individual indexes. For a slightly modified algorithm, that does more work, we prove that we can give instance specific guarantees about the quality of our solution. We conduct an extensive experimental evaluation of this new heuristic and compare it with previous solutions. Our results demonstrate that our solution is more scalable while achieving comparable quality.}, author = {Chaudhuri, S. and Datar, M. and Narasayya, V. }, booktitle = {Knowledge and Data Engineering, IEEE Transactions on}, citeulike-article-id = {2601614}, doi = {http://dx.doi.org/10.1109/TKDE.2004.75}, journal = {IEEE Transactions on Knowledge and Data Engineering,}, number = {11}, pages = {1313--1323}, posted-at = {2008-03-27 11:51:43}, priority = {2}, title = {Index selection for databases: a hardness study and a principled heuristic solution}, url = {http://dx.doi.org/10.1109/TKDE.2004.75}, volume = {16}, year = {2004} }

TY - JOUR ID - citeulike:2601614 L3 - citeulike-article-id:2601614 TI - Index selection for databases: a hardness study and a principled heuristic solution T2 - Knowledge and Data Engineering, IEEE Transactions on JF - IEEE Transactions on Knowledge and Data Engineering, VL - 16 IS - 11 SP - 1313 EP - 1323 N2 - We study the index selection problem: Given a workload consisting of SQL statements on a database, and a user-specified storage constraint, recommend a set of indexes that have the maximum benefit for the given workload. We present a formal statement for this problem and show that it is computationally "hard" to solve or even approximate it. We develop a new algorithm for the problem which is based on treating the problem as a knapsack problem. The novelty of our approach lies in an LP (linear programming) based method that assigns benefits to individual indexes. For a slightly modified algorithm, that does more work, we prove that we can give instance specific guarantees about the quality of our solution. We conduct an extensive experimental evaluation of this new heuristic and compare it with previous solutions. Our results demonstrate that our solution is more scalable while achieving comparable quality. AU - Chaudhuri, S AU - Datar, M AU - Narasayya, V PY - 2004/// UR - http://dx.doi.org/10.1109/TKDE.2004.75 ER -