Database Reference
In-Depth Information
there exist greedy algorithms that approximate the exact solution in a
short amount of time.
5.2 Reducing the Overhead of What-If
Optimization Calls
The what-if abstraction described in the previous section makes it possible to
design complex search algorithms that rely on such a fast mode of evaluating
workloads under arbitrary configurations. However, the overhead of a what-if
optimization call is essentially that of a regular optimization call. For relatively
complex queries, this overhead can still be significant. In fact, in some cases
over 90% of the search time is spent issuing what-if optimization calls. In the
rest of this chapter we introduce techniques to reduce the overhead of what-if
optimization calls without significantly compromising the quality of results.
5.2.1 Atomic Configurations
An interesting approach to reduce the number of optimization calls is based
on the notion of atomic configurations . A configuration C is atomic for a query
q if there is a possible execution plan from q that uses all indexes in C (in
turn, a configuration is atomic for a workload W if it is atomic for at least
one query in W ). An interesting consequence of this definition is that if a
configuration is not atomic for a query q , we can derive the cost of q for this
configuration accurately from costs of atomic configurations only, thus saving
what-if optimization calls.
Assume that C is a nonatomic configuration and q is a SELECT query. Since
C is not atomic, there is no plan that uses all indexes in C . Therefore, op-
timizing q under C would result in a plan that uses all and only indexes in
some C
C (i.e., some atomic configuration C ). A well-behaved optimizer
will choose the plan using indexes in the atomic configuration C that has the
minimal cost. Therefore, we can derive the cost of q under C as follows:
C )
(
,
) =
(
,
cost
q
C
min C C atomic ( C ) cost
q
For an UPDATE query, the analysis is more complex. The cost of an UPDATE
query for a nonatomic configuration C can be divided in three components:
(1) the cost of the inner SELECT query, (2) the cost of updating the indexes
that are used in the inner SELECT query, and (3) the cost for updating the
remaining indexes. Similar to the case of a SELECT query, we can derive the
minimum costs over all atomic configurations of q that are subsets of C to
account for components (1) and (2). Note that the costs for updating indexes
in component (3) are independent of each other and also of the chosen plan.
Search WWH ::




Custom Search