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

of the operator trees consumes the least resources. Resources may be central
processing unit (CPU) time, input/output (I/O) cost, memory, or a combi-
nation of these. Therefore, given a partial or full operator tree, being able to
accurately and e ciently evaluate its cost is of fundamental importance. Cost
estimation must be accurate (optimization is only as good as its cost esti-
mates) and ecient (it is in the inner loop of query optimization). The basic
framework for estimating costs is based on the following recursive approach:

1. Collect statistical summaries of stored data.
2. Given an operator in the execution plan and statistical summaries for
each of its subplans, determine:
a. Statistical summaries of the output
b. Estimated cost of executing the operator

The procedure can be applied to an arbitrary tree to derive the costs of
each operator. The estimated cost of a plan is then obtained by combining
the costs of each of its operators. The resources needed to execute a query plan
(and thus the plan cost) are a function of the sizes of the intermediate query
results. Therefore, the cost estimation module heavily depends on cardinality
estimates of subplans generated during optimization. The following example
illustrates how sizes of intermediate results can significantly change the chosen
plan.
Consider the following query template, where @C is a numeric parameter:

SELECT *
FROM R,S
WHERE R.x = S.y and R.a < @C

Figure 2.4 shows the execution plans produced by an optimizer when we
instantiate @C with the values 20, 200, and 2 , 000. Although the three in-
stantiated queries are syntactically very similar, the resulting optimal query
plans are considerably different. For instance, in Figure 2.4a, the optimizer
estimates that the number of tuples in R satisfying R

. a < 20 is very small.

Loop Join
[R.x=S.y]

Merge Join
[R.x=S.y]

Hash Join
[R.x=S.y]

Index Join
[RID]

Table Scan
[S]

Sort
[R.x]

Index Scan
[S]

Table Scan
[R]

Table Scan
[S]

Index Seek
[R.a<20]

RID Lookup
[R]

Table Scan
[R]

(a) R.a < 20. (b) R.a < 200. (c) R.a < 2000.

FIGURE 2.4 Query execution plans for various instances of a template

query.