Database Reference
In-Depth Information
5.2.2 Upper Bounds
Some search strategies (discussed in Chapter 6) require approximating a large
number of query costs under different—but similar—configurations. In such
situations, performing a large number of what-if calls quickly becomes pro-
hibitively expensive. These strategies, however, can be adapted to work off
approximations of query costs, as long as such approximations are (tight) up-
per bounds of the true cost of the queries. We now describe how to obtain
an upper bound on the cost of a query under a given configuration without
making an explicit optimization call. The techniques discussed in this section
are also useful in the more advanced strategies that we discuss later in this
chapter.
To begin with a simple example, suppose that we optimized a SELECT query
q under configuration C , and we want to obtain an upper bound on the cost
for q under C
. If the execution plan for q under C does not use
index I , the execution plan for q under C would be unchanged. The reason is
that the optimal plan for q under C is no better than that under C because
C
=
C
−{
I
}
C and is no worse either, because the one under C uses only indexes
that are available in C . Then, a tight upper bound for cost
C )
(
q
,
is cost
(
q
,
C
)
itself.
5.2.2.1
Local Plan Transformations
In general, however, the optimal execution plan for q under C would use
an index I that is not in C . Consider the execution plan P at the left of
Figure 5.4. Index I
=
(
|
,
)
<
R
a
b
c
is used to seek tuples that satisfy a
10
Replace I = R ( a | b , c )
with I ´= R ( a | b )
P ´
P
Project
[ a , c ]
Project
[ a , c ]
Index Join
[RID]
Seek I = R ( a | b , c )
[ a <10]
Seek I ´= R ( a | b )
[ a <10]
RID Lockup
FIGURE 5.4 Estimating execution cost upper bounds. (Used with permis-
sion from Bruno, N. & Chaudhuri, S. In Proceedings of the ACM International
Conference on Management of Data [SIGMOD] , 2005.)
Search WWH ::




Custom Search