An examination is made of existing rule-based optimizers, showing that they have significant limitations. A new approach to optimization based on the idea of modules is presented. An optimizer is divided into several interconnected modules. Each module has its own set of rewrite rules and can be implemented differently according to how the rules are used. This modular approach avoids the limitations of existing systems and supports flexible optimizer prototyping, efficient optimize-time search, and convenient access to metadata. To illustrate these ideas, a decomposition into modules is given for an example relational query optimizer.>

A description is given of extended relations, a generalization of ordinary relations in which tuple identifiers (tids) can appear as attribute values. The relational algebra is extended to include new operators that manipulate these tids; the resulting algebra is called the tid-algebra. The theorems of the tid-algebra are shown to provide a formal basis for optimizer transformations that involve high-level access structures. Three particular access structures-secondary indices, join indices, and join extensions-are examined in detail.>