Histogram methods in query optimization: the relation between accuracy and optimality

We have solved the following problem using pattern classification techniques (PCT): given two histogram methods, M/sub 1/ and M/sub 2/, used in query optimization, if the estimation accuracy of M/sub 1/ is greater than that of M/sub 2/, then M/sub 1/ has a higher probability of leading to the optimal query evaluation plan (QEP) than M/sub 2/. To the best of our knowledge, this problem has been open for at least two decades, the difficulty of the problem partially being due to the hurdles involved in the formulation itself. By formulating the problem from a pattern recognition perspective, we use PCT to present a rigorous mathematical proof of this fact, and show some uniqueness results. We also report empirical results demonstrating the power of these theoretical results on well-known histogram estimation methods.