Efficient search in extensible database query optimization: the volcano optimizer generator
William Joseph McKenna · 1993
Novel database applications demand high performance as well as high functionality. Query optimization is an area where significant performance gains can be achieved in these applications. However, query optimization in extensible, scientific, and object-oriented systems lags behind relational query optimization for several reasons. First, optimization tools and subsystems currently available to assist in the construction of optimizers lack sufficient generality and efficiency. Second, optimizers for such systems are quite complex, making both development and modification difficult and time-consuming tasks. Third, optimization strategies for the query languages of these database systems are not yet well understood, partly because of the lack of an experimental vehicle for researching these strategies. This thesis describes the design, implementation, and application of a software tool, the Volcano Optimizer Generator, that greatly alleviates these problems. This system is the realization of an extensible, flexible framework for creating efficient optimizers for new database systems, and our research advances the study of extensible database query optimization in several ways. First, our approach is based on an optimization framework more complete than previous optimization subsystems, and is extensible enough to allow experimentation in all of the following dimensions: new algebraic operators, new algebraic transformation rules, new execution algorithms, improved cost models, physical formats and structures, new state space search strategies, and thoroughness of search. Second, the search engine of the Volcano Optimizer Generator is the first to combine dynamic programming, branch-and-bound pruning, and goal-directed search based on a physical property abstract data type, and it unites efficiency and generality more effectively than the search engines of previous systems. Third, it is the first extensible optimization system to be used to produce a near-production quality query optimizer for an object-oriented system. This optimizer, built for the Open OODB system, an extensible and modular database system being developed at Texas Instruments, is the first working object optimizer based on an optimization framework extensible in all of the above dimensions. Finally, this research demonstrates that optimizer generator technology has become mature enough to substantially assist database implementors in the development of efficient, effective, and extensible query optimizers for non-standard database systems.