Tech Report CS-91-38

An Architecture for Query Processing in Persistent Object Stores

Gail Mitchell, Stanley B. Zdonik and Umeshwar Dayal

June 1991

Abstract:

Query optimizers for persistent object systems should be extensible to react to user-supplied abstract types. Although extensible optimizers exist, current architectures support only a single, non-extensible technique for controlling the optimization process. That is, the search strategy used by the optimizer is fixed when the optimizer is built.

We propose an alternative to the current extensible architectures that will support multiple optimizer control strategies and the addition of new control strategies. The optimizer consists of a collection of optimization regions, each of which can transform queries according to a particular control strategy, set of transformations and cost model. A global optimizer control coordinates the movement of a query between these regions. This architecture provides extensibility in the optimizer's repertoire of control strategies through the addition of new regions.

In this paper we describe our approach and demonstrate its utility by following the optimizer as it works on an example query. The optimizer will move the query between three distinct regions, one that works with standard rule-based transformations, one that discovers join relationships in a query, and a third that manipulates a canonical join form. The first region acts similarly to existing rule-based optimizers, by applying algebraic rules to a query expression. The second region extends the optimizer to manipulate nested algebraic query expressions. The third manipulates join orderings in a query expression. The different regions illustrate different kinds of transformations and different strategies for application of those transformations. The optimizer can be extended with additional regions to provide more transformation types and control strategies, a result that cannot be achieved by existing relational or extensible optimizers.

(complete text in pdf or gzipped postscript)