An Integer Linear Programming Approach to Database Design

Existing index selection tools rely on heuristics to efficiently search within the large space of alternative solutions and to minimize the overhead of using the query optimizer for cost estimation. Index selection heuristics, despite being practical, are hard to analyze and formally compute how close they get to the optimal solution. In this paper we propose a model for index selection based on integer linear programming (ILP). The ILP formulation enables a wealth of combinatorial optimization techniques for providing quality guarantees, approximate solutions and even for computing optimal solutions. We present a system architecture for ILP-based index selection, in the context of commercial database systems. Our ILP-based approach offers higher solution quality, efficiency and scalability without sacrificing any of the precision offered by existing index selection tools.