Optimal Indexing Using Near-Minimal Space

We consider the index selection problem. Given either a fixed query workload or an unknown probability distribution on possible future queries, and a bound B on how much space is available to build indices, we seek to build a collection of indices for which the average query response time is minimized. We give strong negative and positive peformance bounds. Let m be the number of queries in the workload. We show how to obtain with high probability a collection of indices using space O(B ln m) for which the average query cost is opt_B the optimal performance possible for indices using at most B total space. Moreover, this space relaxation is necessary: unless N P ⊆ n^{o(log log n)}, no polynomial time algorithm can guarantee average query cost less than M^1-∈ opt_B using space αB, for any constant α, where M is the size of the dataset. We quantify the error in performance introduced by running the algorithm on a sample drawn from a query distribution.