Histogram Methods in Query Optimization: The Relation between Accuracy and Optimality

We have solved the following problem using Pattern Classijication Techniques (PCT): Given two histogram methods M I and M2 used in query optimization, ifthe esti-mation accuracy of M1 is greater than that of M2, then M I has a higher probabilio of leading to the optimal Query Evaluation Plan (QEP) than M2. To the best of our knowl-edge. this problem has been open for at least two decades, the difJicul9 of the problem partially being due to the hur-dles involved in the formulation itseg By formulating the problem from a Pattern Recognition (PR) perspective, we use PCT to present a mathematical, rigorous proof of this fact, and show some uniqueness results. We also report em-pirical results demonstrating the power of these theoretical results on well-known histogram estimation methods