Query optimization by intelligent search.
Hyuck Yoo · Deep Blue (University of Michigan) · 1990
Query optimization is a crucial part in relational database management systems because it can make a significant improvement in the overall performance of these systems. As the need for relational database management systems to handle larger amounts of data and more complex queries increases, it is of paramount importance that an optimal and efficient solution is found to answer a given query. Traditionally, dynamic programming or exhaustive search has been used to guarantee optimality, but these approaches are not effective for complex queries with large search spaces. In this dissertation, we investigate the problem of finding an optimal solution to the query optimization problem without having to search all the possibilities. The savings result from the idea of intelligently predicting future processing costs. Specifically, four query optimization problems are addressed: query optimization by semijoins, join query optimization, multiple query optimization, and query optimization for fragmented databases. For each problem, a new query optimization method is developed in light of the goal of enhancing the search efficiency while preserving optimality. Simulation experiments are carried out to show that substantial improvements can indeed be achieved. Another advantage of our approach is its modularity, in that different query processing strategies can be easily incorporated into the methods and general cost functions can be used for the optimization. Modularity is achieved because the methods developed consist of four well-defined and unrelated modules so that one module can be modified without affecting the others.