Much work is done by a DBMS before a query optimizer ever gets a logical algebra query tree. For example, the query must be parsed, checked to make sure that it's legal and its referenced views must be resolved. If the data model is SQL, the DBMS must deal with nested subqueries.
Some of these functions are best left to the parser. But other functions could be handled by the optimizer itself or by a pre-optimization phase. For example, we could either give nested queries to the optimizer without modification -- moving the problem to the optimizer -- which could then evaluate the nested and unnested versions of the query and chose the cheapest, or we could develop a rewrite or tenderization phase which would be run after the parser, but before the optimizer.
[Pirahesh 92], discuss a "novel" phase of query optimization intended to precede the optimization proper, that they call query rewrite. It is rule-based, like many optimizers, but heuristic in the sense that it does not consider calculated (i.e. estimated) costs during the rewrite process. (The consequent of a rule is always assumed to be the best, as opposed to at some point comparing its cost to the cost of the antecedent.)
Query rewrite is able to merge views into the original query, transform quantified (nested) subqueries into single query blocks with additional joins, and add keys to certain intermediate tables to allow duplicate elimination to occur early, reducing cardinalities of non-unique tables.
One motivation for putting the rewrite rules in a pre-optimization phase instead of in the optimizer proper, is to prevent rule or search space explosion or other difficulties in applying the rewrite rules during optimization.
| 4. Related Work: |
<System R>
<Bottom Up>
<Join Order Heuristics>
<Query Blocks>
<Rules>
<Top Down>
<Volcano>
<Phases>
<Specialized Techniques>
<Unique Rules>
4.1: Left-Deep |
|---|
| 
Page 15
|