Carleton University
Technical Report TR-00-08
October 2000
Resolving Open Problems in Query Optimization Using Pattern Classification Techniques
Abstract
We have solved the following problem using Pattern Classification Techniques (PCT): Given two histogram methods M1 and M2 used in query optimization, if the estimation accuracy of M1 is greater than thet of M2, then M1 has a higher probability of leading the optimal Query Evaluation Plan (QEP) than M2. To the best of our knowledge, this problem ahs 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 (PR) perspective, we use PCT to present a mathematical, rigorous proof of this fact, and show some uniqueness results. We also report emperical results demonstrating the power of these theoretical results on well known histogram estimation methods.