Having seen the basic algorithms for executing
physical-qucry-plan
operators in
Chapter 6, we shall now take up the architecture of the query compiler and its
optimizer. As we noted in Fig. 6.2, there are three broad steps that the query
processor must take:
1. The query, written in a language like SQL, is parsed, that is, turned into
a parse tree representing the structure of the query in a useful way.
2. The parse tree is transformed into an expression tree of relational algebra
(or a similar
notation),
which we term a logical query plan.
3. The logical query plan must be turned into a physical query
plan,
which
indicates not only the operations performed, but the order in which they
are performed, the algorithm used to perform each step, and the ways in
which stored data is obtained and data is passed from one
operation
to
another.
The first step, parsing, is the subject of Section 7.1. The result of this
step is a parse tree for
the
query. The other two steps involve a number of
choices. In picking a logical query plan, we have opportunities to apply many
different
algebraic operations, with
the
goal
of
producing
the
best logical query
plan. Section 7.2 discusses the algebraic laws for relational algebra in the ab-
stract. Then, Section 7.3 discusses the conversion of parse trees to initial logical
query plans and shows how the algebraic laws from Section 7.2 can be used in
strategies to improve the initial logical plan.
When producing a physical query plan from a logical
plan,
we must
evaluate
the predicted cost of each possible option. Cost estimation is a science of its
own, which we discuss in Section 7.4. We show how to use cost estimates to
evaluate plans in Section 7.5, and the special problems that come up when
we order the joins of several relations are the subject of Section 7.6. Finally,
Section 7.7 covers additional issues and strategies for selecting the physical
query
plan:
algorithm choice
and
pipelining versus materialization.
329
