Rule-based query optimization in extensible database systems
Goetz Graefe · Minds at UW (University of Wisconsin) · 1987
This thesis presents the problems of query optimization in extensible database systems and proposes a solution. It describes the design and an initial evaluation of the query optimizer generator developed for the EXODUS extensible database system. The goal of the EXODUS system is to provide software tools and libraries to structure and to ease the task of implementing or extending a database system for a new data model. Our basic model of optimization is to map a query tree, which consists of operators at the nodes and stored data at the leaves, to an access plan, which is a tree with implementation methods at the nodes and scans at the leaves. The optimizer generator translates algebraic equivalence rules into an executable optimizer. The equivalence rules are specific to the data model. The generated optimizer reorders query trees and selects implementation methods according to cost functions associated with the methods. The search strategy of the optimizer avoids exhaustive search by learning from past experience. We report on two operational optimizers. Experiments with a restricted relational system show that the generated optimizer produces access plans of almost the same anticipated execution cost as those produced by exhaustive search, with the search time cut to a small fraction. Another set of experiments shows that a generated optimizer is able to handle large queries. An optimizer currently under development for a new query evaluation method shows the power and flexibility of the approach. Other researchers have decided to use the optimizer generator for their database implementation work. Independently from the EXODUS project, the optimizer generator proved to be a valuable tool for exploring the trade-offs between left-deep execution trees and general execution trees in relational database systems. Our experiments show that for bushy trees, the higher optimization cost and the cost for creating and reading temporary files can be more than compensated by the reduction in processing cost.