The index selection problem with configurations and memory limitation: A scatter search approach

Within the physical designing process of relational databases, the Index Selection Problem aims at finding the subset of indexes to build for accessing the stored information. More precisely, given a database workload, each query must be served by at most one predefined set of indexes (named configuration) to maximize the net gain in terms of time. This gain is made up of the time gain obtained to serve the queries through the configurations minus the fixed time needed to create and maintain those configurations. The clustering of indexes into configurations and the limited amount of memory available to store the indexes characterize our variant of the problem. At the same time, established approaches in the literature have only considered those two aspects separately. We model this setting as a generalization of the Uncapacitated Facility Location Problem with budget constraint and propose an Integer Linear Programming formulation for it. Then, to find near-optimal solutions in a reasonable computational time, we develop a Scatter Search meta-heuristic exploiting the specific facility location features of the problem. We test our algorithm over a broad set of benchmark instances and compare it with an exact solver and an efficient state-of-the-art heuristic method.