EFFICIENCY IN THE COLUMBIA DATABASE QUERY OPTIMIZER By YONGWEN XU A thesis submitted in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE in COMPUTER SCIENCE Portland State University 1998 I ABSTRACT An abstract of the thesis of Yongwen Xu for the Master of Science in Computer Science presented February 12,1998. Title: Efficiency in the Columbia Database Query Optimizer Query optimization is an area where database systems can achieve significant performance gains. Modern database applications demand optimizers with high extensibility and efficiency. Although more than one decade’s efforts have been contributed to these areas, the state of the art in optimizer research is still not adequate for the demands of business.
The goal of our Columbia project is to provide efficient and extensible tools for query optimization, particularly for complex queries and new data models. Efficiency is the main focus of this thesis. This thesis describes the design and implementation of the Columbia Query Optimizer, which obtains significant performance improvement while extensibility is not sacrificed. Based on the top-down optimization algorithm of the Cascades Optimizer Framework, Columbia simplifies the design of top-down optimizers by carefully reengineering the search space structure and search algorithms.
Two pruning techniques are implemented which can achieve significantly better performance improvement. Usability is also improved in Columbia by adding a friendly user interface and extensive tracing support. Experiments on the Columbia optimizer were done using the relational data model. Results will be demonstrated in efficiency II improvement by comparing Columbia to other top-down optimizers, such as Cascades.
III THESIS APPROVAL The abstract and thesis of Yongwen Xu for the Master of Science in Computer Science were presented February 12, 1998, and accepted by the thesis committee and the department. COMMITTEE APPROVALS: Leonard Shapiro, Chair Jingke Li John Rueter Representative of the Office of Graduate Studies DEPARTMENT APPROVAL: Richard Hamlet, Chair Department of Computer Science IV Acknowledgments Many people helped in the work of this thesis. I am grateful to all of them. Many thanks to my advisor, Professor Leonard Shapiro.
I owe him a great deal for his help and guidance from the beginning of the research to the end of the thesis. Thanks for his friendly supervision, visionary instructions and extreme patience. Thanks to Keith Billings for sharing his work in Model D and the helpful discussions about models and search algorithms in Columbia and Cascades. Thanks to Professor Jingke Li for providing an experimental platform for the performance analysis of our work.
Beth Phelps and Cynthia Beretta-Loepp in the Computer Science department office provided essential support for our efforts. Thanks to Professor David Maier and graduate student Quan Wang at Oregon Graduate Institute for suggestions and helpful discussions regarding the design and development of Columbia, pruning techniques, and optimization of object-oriented data models. The work of this thesis also benefits from discussions on top-down optimization efforts in industry. Goetz Graefe and Cesar Galindo-Legaria told us about Microsoft’s new transformation-based optimizer.
They are very useful for the design of the Columbia optimizer. Last but not least, thanks to my wife, Wen Huang, for her long-lasting understanding and support during the entire project. She also provided valuable comments for this thesis as well as sharing her knowledge on TPC-D queries and Microsoft SQL Server optimizer. This research is supported by NSF IRI-9119446, DARPA (BAAB07=91-C- Q513) subcontract from Oregon Graduate Institute to Portland State University.
i Table of Contents Chapter 1 .1 Motivation for This Research .2 Overview of This Thesis. Logical Operators and Query Tree. Physical Operators and Execution Plan. The Search Space.1 The System R and Starburst Optimizer .2 The Exodus and Volcano Optimizer Generators.3 The Cascades Optimizer Framework.
Structure of the Columbia Optimizer.1 Overview of the Columbia Optimizer .1 The Optimizer Input. The Optimizer Output.3 The External Dependence of Optimizer .2 The Search Engine.1 The Search Space .1 Search Space Structure - Class SSP.2 Duplicate Multi-expression Detection in the Search Space.3 Tasks -- Searching Algorithm.1 O_GROUP - Task to Optimize a Group .2 E_GROUP - Task to expand the group .3 O_EXPR - Task to optimize a multi-expression .4 APPLY_RULE - Task to Apply a Rule to a Multi-Expression.5 O_INPUTS - Task to optimize inputs and derive cost of an expression 70 4.1 Lower Bound Group Pruning.2 Global Epsilon Pruning .4 Usability in the Columbia Optimizer .2 Tracing of the optimizer. Result and Performance.1 Performance on Chain and Star Queries. Comparison with Cascades.3 Epsilon Pruning Technique Analysis.
Conclusions and Future works. Cost Model Text File Example. A Simple Rule Set for Join Queries. A Final Search Space Example in Tracing File.
An OPEN Task Stack Sample in Tracing File.105 iii List of Tables Table 1. Complexity of Join of n Relations [Bil97]. Grammar of the Query Tree. Data Member Definition of class M_EXPR in Columbia.
Data Member Definition of class EXPR_LIST in Cascades .50 iv List of Figures Figure 1. Logically equivalent query trees and plans. Equivalent expressions in groups [ABC]. Equivalent multi-expressions in group [ABC].
Initial Search Space of a given query. Two types of Rules. Interface of Columbia Optimizer. An Example of Query Text File and Query Expression Tree.
Two Optimal Plans for one Query with different Catalogs. Main components in the Columbia Search Engine. Pseudo-code for the Use of lookup2(). Pseudo-code for calculating lower bound of a group.
Finite State Machine for BINDERY::advance(). Main Loop of Optimization in Columbia. Relationship between Tasks. Algorithm for O_GROUP.
Algorithm for E_GROUP. Algorithm for O_EXPR. Algorithm for APPLY_RULE.70 Figure 22 Pseudo-code of O_INPUTS::perform(). Search space during optimization ( [AC] is Cartesian product ).
Algorithm of Lower Bound Pruning. A situation when lower bound pruning happens. A Dialog to allow user to change parameters of the optimizer. A picture of the optimizer application.
Optimization time for chain and star queries. Number of multi-expressions generated in chain and star queries. Memory usage for chain and star queries. Optimization time for chain queries.
Optimization time for star queries.Effectiveness of Epsilon pruning. Errors to optimal plan of Epsilon pruning.1 Motivation for This Research In spite of the fact that query optimization has been a subject of research for more than 15 years [SAC+79], query optimizers are still among the largest and most complex modules of database systems, making their development and modification into difficult and time-consuming tasks. The situation is further complicated by the needs of modern database applications [ZdM90], such as Decision Support Systems (DSS) and On-Line Analytical Processing (OLAP), large data warehouses, complex objects (e., multimedia databases, WWW and GIS), and the need to handle new evaluation techniques (e., parallel and distributed evaluations). These new application areas in turn demand new database technologies, such as new query languages and new query processing techniques, which are quite different from those in traditional transaction processing applications.
Over the past several years, several generations of commercial and research query optimizers have been developed, making contributions to the extensibility and efficiency of optimizers. The first efforts at extensible optimizer technology (we call it the first generation.), begun about ten years ago, realized the need for new data models, query classes, languages and evaluation techniques. These projects include Exodus [GrD87] and Starburst [HCL90]. Their goal was to make optimizers more modular and easier to extend.
The techniques they used include layering of components, rule-based 1 transformations, etc. Those efforts had some shortcomings, such as the complexity of making extensions, search performance, and a bias toward record-oriented data models. The second generation of extensible optimizer tools, such as the Volcano optimizer generator [GrM93], added more sophisticated search techniques, more use of physical properties to guide search, and better control over search strategy, to achieve better search performance. Although these optimizers are somewhat flexible, it is still hard and complex to make extensions.
The third generation of query optimizer frameworks, such as Cascades [Gra95], OPT++ [KaD96], EROC [MBH96] and METU [ONK95], use object- oriented design to simplify the task of implementing, extending and modifying an optimizer, while maintaining efficiency and making search strategies more flexible. This latest generation of optimizers is reaching a level of sophistication that satisfies the requirements and demands of modern commercial database systems. This is demonstrated by industry’s implementation of these optimizers, such as Cascades by Microsoft [Gra96] and Tandem [Cel96], EROC by NCR [MBH96]. These three generations of query optimizers can be categorized into two kinds of search strategies, Starburst style bottom-up dynamic programming optimizers and Cascades style top-down branch and bound rule-driven cost based optimizers.
Bottom- up optimization is widely used in current traditional commercial database systems because it is believed to be efficient, at least in traditional applications. But bottom-up optimization is inherently less extensible than top-down optimization since it requires the decomposition of the original problem into sub problems. Also, to achieve 2 acceptable performance for large queries, heuristics are required in bottom-up optimization. Although previous implementations of top-down optimizers showed they have been difficult to tune for competitive performance as bottom-up optimization, we believe that top-down optimizers have advantages in efficiency as well as extensibility.
The remainder of this thesis describes our attempt to develop an alternative top-down optimizer, Columbia, to demonstrate that high efficiency could be achieved in a top-down approach. Based on the top-down optimization of the Cascades Optimizer Framework, Columbia extensively exploits the object-oriented features of C++ and carefully engineers and simplifies the top-down optimization to achieve efficiency while maintaining extensibility. It defines a few key abstract classes with virtual methods. The search strategy is implemented entirely in terms of these abstract classes.
The search strategy invokes the virtual methods of these abstract classes to perform the search and the cost-based pruning of the search space. Hence, it is easy to extend the optimizer to manipulate complex data models, adding new operators and transformation rules by deriving new classes from the abstract classes and rewriting the virtual methods. Since the main focus of this thesis is optimization efficiency in the relational data model, we do not discuss extensibility of the optimizer here and leave extending the optimizer to manipulate other data model as future works. To minimize the usage of CPU and memory, several engineering techniques are used to obtain efficiency in Columbia.
They include a fast hash function to eliminate duplicate expressions, separation of logical and physical expressions in a 3 group, small and compact data structures, efficient algorithms to optimize groups and inputs, and an efficient way to handle enforcers. An important technique Columbia provides is group pruning, which significantly prunes the search space without compromising plan quality. The optimizer computes the cost for high-level physical plans before some lower-level plans are generated. These early costs serve as upper bounds for subsequent optimization.
We will show that in many cases these upper bounds can be used to avoid generating entire groups of expressions, hence, pruning significant amounts of possible query plans in the search space. Besides group pruning, Columbia also implements another pruning technique: global epsilon pruning. This technique significantly prunes the search space by generating acceptable close-to-optimal solutions. An optimization goal is finished when a solution is found to be close enough to the optimal solution, hence a significant amount of expressions need not be considered.
An analysis of this pruning technique is discussed. The effectiveness and error in the optimization are shown.2 Overview of This Thesis The remainder of this thesis is organized as follows. Chapter 2 describes the terminology and fundamental concepts used in this thesis. Related work is presented in Chapter 3, in which we survey the commercial and research contributions in this area, from traditional to new generations, from bottom-up to top-down optimizers.
We will focus on performance analysis. 4 In Chapter 4, the overall structure and design of the Columbia system is described, including search space, rules and optimizing tasks. Two pruning techniques are discussed. Usability improvement is also discussed in this chapter.