Query Optimization in Relational Database Systems - Automated Physical Database Design and Tuning - page 34

QGM, a box represents a query block and labeled arcs between boxes represent
table references across blocks. Each box contains information on the predicate
structure and on the data stream order.
In the query rewrite phase of optimization, heuristic but sound rules are
used to transform a QGM into another equivalent QGM. Rules are modeled
as pairs of arbitrary functions. The first one checks the QGM for condition
for applicability, and the second one enforces the transformation. A forward
chaining rule engine governs the rules. Rules may be grouped in rule classes,
and it is possible to tune the order of evaluation of rule classes to focus the
search. Since any application of a rule results in a valid QGM, any set of rule
applications guarantees query equivalence. The query rewrite phase does not
have cost information available. This forces this module either to retain alter-
natives obtained through rule application or to use the rules in a heuristic way.
The second phase of query optimization is called plan optimization. In this
phase, given a QGM, an execution plan is chosen. In Starburst, the phys-
ical operators (called LOLEPOPs) may be combined in a variety of ways
to implement higher-level operators. Such combinations are expressed in a
grammar-production-like language. The realization of a higher-level operation
is expressed by its derivation in terms of the physical operators. In comput-
ing such derivations, comparable plans that represent the same physical and
logical properties but have higher costs are pruned. Each plan has a rela-
tional description that corresponds to the algebraic expression it represents,
an estimated cost, and physical properties (e.g., order). These properties are
propagated as plans and are built bottom-up. Thus, with each physical op-
erator, a function is associated that shows the effect of the physical operator
on each of the aforementioned properties. The join enumerator in Starburst
is similar to System-R's bottom-up enumeration scheme described in the pre-
vious section.
2.3.3 Volcano/Cascades
The Volcano/Cascades optimization framework was developed in the mid-
nineties and used as the foundation for both academic and industrial query
optimizers (e.g., Tandem's NonStop SQL and Microsoft SQL Server optimiz-
ers are based on this architecture). These optimizers work by manipulating
operators , which are the building blocks of operator trees and are used to
describe both the input declarative queries and the output execution plans.
Consider the following simple SQL query:
SELECT *
FROM R, S, T
WHERE R.x = S.x AND S.y = T.y
Figure 2.7a shows a tree of logical operators that specify, in an almost
one-to-one correspondence, the relational algebra representation of the query
above. In turn, Figure 2.7c shows a tree of physical operators that corresponds