Tech Report CS-94-04

The Framework for EPOQ - an Extensible Object- Oriented Query Optimizer

Solveig Bj{\o}rnestad

March 1994

Abstract:

This report describes the design and implementation of a framework for EPOQ - the architecture for an extensible, object-oriented query optimizer. Extensibility in this context is related to the types of objects that can be queried, the types of queries that can be optimized, and the optimization strategies that can be applied. For object-oriented data base systems different optimization strategies may be used on different data types, and the architecture makes this possible through the combination of several optimization regions that can apply different strategies. This work was initiated to implement the overall design described in [Mitch93] where the emphasis is made on the overall architecture, and the description is on a relatively high abstraction level. How this could be realized was not emphasized. In this paper focus is made on the detailed design decisions that were made to ensure that the overall goals were met. The architecture is intended to be extensible to make it possible to build flexible optimizers that can be adaptable to new types of objects and experimentation with new optimization strategies. A second goal has been to design a reusable framework for building query optimizers. To achieve this, focus has been put on designing the architecture as a set of interacting components that can be specialized whenever a new type of optimization strategy has to be implemented. Until the framework has actually been used to build example optimizers, it is hard to tell whether this goal has been achieved. The report can also be used as a manual for implementation of optimizers based on this architecture. Currently this work is continued at Brown and hopefully we will gain more insight in how such a framework should be organized.

(complete text in pdf or gzipped postscript)