Database Reference
In-Depth Information
. This execution plan seeks
I
1
for tuples satisfying
c
=4, filters tu-
ples satisfying
a
I
1
=
(
c
,
a
,
b
)
2, looks up the remaining columns from the primary
index, and performs a final sort to satisfy the required order. Analogously, Fig-
ure 5.6c shows the execution subplan for index
I
2
=
+
b
=
(
,
,
,
)
. This subplan
scans index
I
2
and filters all predicates simultaneously but does not explicitly
sort the output since it is already ordered in the right way.
Configurations generally contain multiple indexes over the table of a given
request. In principle, we could use more than one index to obtain a physical
subplan that implements a request (e.g., by using index intersections) or even
could consider hash-based alternatives to replace index joins for which no suit-
able index exists anymore. These alternatives effectively trade the accuracy
of the estimation and the eciency/complexity to obtain the subplan.
d
c
b
a
5.3 Index Usage Model (INUM)
The approach described in the previous section returns upper bounds on the
cost of a query under a given configuration. It does so by means of local
transformations to subplans that correspond to index strategies. It is impor-
tant to note that the upper bounds are obtained without considering changes
to the internal subplan, which is configuration independent. Sometimes, the
resulting upper bounds are very accurate, as we discuss next.
Consider a restricted query optimizer that handles only hash-based join
alternatives. We will show that in this scenario, the optimal plan under any
configuration must follow the same join order. Suppose we optimize a query
q
under a configuration
C
1
and obtain plan
P
1
. Figure 5.7 shows an example of a
three-way join query
q
, where each single-table index strategy is depicted with
a triangle. Let us denote
IP
1
as the internal subplan of
P
1
. Now suppose that
IP
2
IP
1
P
1
P
2
T
1
T
2
R
1
S
1
S
2
R
2
FIGURE 5.7
Replacing index strategies in different inner subplans.
Search WWH ::
Custom Search