G. Graefe and W. McKenna.
Extensibility and search efficiency in the VOLCANO optimizer generator.
In Proceedings IEEE CS Intl. Conference No. 9 on Data Engineering, Vienna, April 1993.
Presented by: Dalal
This paper talks about the Volcano project which provides tools for query and request processing, particularly for Object Oriented and Scientific database systems. It focuses mainly on the Optimizer generator for the project and the Optimizer generator paradigm.
The paper emphasises the importance of extensibility and performance in databse projects and prototypes and it identifies factors like Optimization and parallelization as the main parameters which are crucial for the wider use of extensible database technology. The designers talk about the motivation for the new Optimizer Generator , Volcano and the advantages it offers over the earlier EXODUS prototype.
The main concepts and functionality pesent in the Volcano Optimizer Generator are discussed next. The design decisions which contribute to the above mentioned functionality and efficiency are also discussed. The authors then discuss in detail the Optimizer Generator Paradigm. The way it works is that, when the databse is operational and a query is entered, the query is passed to the optimizer, which generates an optimized plan for it. Then the various components that the optimizer implementor defines when implementing a new database query optimizer like the set of operators, transformation rules, set of algorithms, implementation rules, cost functions etc. are discussed.
The talk then focusses on the Search Engine and its algorithm which are the central components of any query optimizer. The Volcano optimizer provides a search engine to be used in all created optimizers and thus the database implementor is freed of much work. The search algorithm for the Volcano generator uses dynamic programming.
A comparision is then made with the EXODUS optimizer generator which uses the authors first attempt to design and implement an extensibe query optimization system or tool. The various drawbacks of the EXODUS system are cited and also how the Volcano system has overcome these problems. A detailed comparision of the systems based on the functionality and extensibility. A detailed analysis (with graph) of the search efficiency and effectiveness of the mechanisms built into the EXODUS and Volcano Search Engines is provided. The results show that the Volcano optimizer generator is more extensible, effective, and efficient than the EXODUS prototype.
The details of other query optimizers like the optimizer for the Starburst relational database system is provided and its limitations vis-a-vis the Volcano system are cited.
The paper concludes with the retieration of the important topics discussed earlier like the motivation for the tool, various features and the design details.