Characterizing the Search Space - Automated Physical Database Design and Tuning - page 64

Logical subplan
π c,d (σ a=10 (T))

Physical plans
Project (Filter(...))

Tag logical subplan
with index request

Access Path Generation Module

Available Indexes

Instrumentation Original Optimizer

FIGURE 4.2 Instrumenting the query optimizer. (Used with permission
from Bruno, N. & Chaudhuri, M. In Proceedings of the ACM of Data [SIG-
MOD] , 1993.)

rooted at the operator over which the index request was issued. Specifically,
an index request is an expression of the form N × ( T , E , R , P , O , A ) , where:

• N is the number of times the subplan would be executed. It is greater

than one when the subplan corresponds to the inner relation of an index-
based join or is part of a correlated subquery (to simplify the notation,
we omit this prefix when N = 1).

• T is the table over which the index request is issued.

• , where c i is a column from T

in a equality-based sargable predicate (e.g., a=10 ), and car d i is the
estimated cardinality of the predicate.

E is a set of tuples, E ={ ( c i , car d i ) }

• ={ (

c i , car d i ) }

, where c i is a column from T in
a range-based sargable predicate (e.g., 5<a<10 ), and car d i is the
estimated cardinality of the predicate.

R is a set of tuples, R

• , where C i is a subset of columns

from T corresponding to a nonsargable predicate (e.g., a*b<10 ),
and car d i is the estimated cardinality of the predicate.

P is a set of tuples P ={ ( C i , car d i ) }

• O is a sequence of columns for which an order has been requested.

• A is the set of additional columns from T required upward in the exe-

cution plan.

Figure 4.3 illustrates this procedure for some fragments of the following
query:

SELECT R.a
FROM R, S, T
WHERE R.x = S.y AND R.w = T.z
AND R.a = 5 AND R.b < 8
AND T.c = 8 AND T.d + T.e = 100