Database Reference

In-Depth Information

predicate on column
b
. The corresponding index on
V
M
additionally contains

tuples that satisfy 10

20. When bounding the cost of evaluating the

same subplan with the promoted index on
V
M
, the expected fraction of tuples

retrieved from the index does not change since we assume independence, but

we need to add the cost of a compensating filter for predicate
R

≤

R

.

a

<

.

a

<

10.

On the other hand, if the used index is originally
I
2

)
, the total

number of tuples touched in the corresponding index on
V
M
stays the same

(and therefore the fraction of tuples changes) since the leading key column in

the index is precisely
R

=

V
1
(

a

,

b

a
.If
q
uses some index on
V
2
under
C
, we need to add

the cost of a final group-by operator after the subplan that uses
V
M
instead,

because the merged view
V
M
removed the grouping clause on
R

.

a
.

In general, however, there might be no view in
C
that is obtained via

transformations from view
V
, which is used under
C
to evaluate query
q
. The

problem in this case is that we do not know how to replace a subplan that uses

V
under
C
without calling the optimizer. An inexpensive approach to address

this problem is as follows. Each time we consider a new view
V
during tuning,

we optimize
V
with respect to the empty configuration and obtain
C
V
, the

cost to evaluate
V
in the base configuration. The value
C
V
is an upper bound

to the cost of “regenerating” the content of
V
from scratch, and we can use

this value if no other view can be used. There are more expensive procedures

to obtain tighter upper bounds, which duplicate some of the functionality in

the optimizer (e.g., its view-matching component).

.

8.4 Enumeration Strategies

Enumeration strategies for the physical design problem that consider both in-

dexes and materialized views are very similar to those described in Chapter 6

for the case of indexes over base tables only. The main difference is quan-

titative and arises from a much larger search space. In addition to indexes

on base tables, there usually is a combinatorial explosion in the number of

materialized views for a given workload. Moreover, indexes can be defined

over such materialized views, further increasing the number of structures to

consider. For top-down strategies that explore the enumeration space on de-

mand, this is not a big problem. In fact, the technique discussed in Section 6.2

can be adapted with small changes to also handle materialized views. Specif-

ically, we need to additionally consider view merging, reduction, and deletion

as new operations to transform configurations and to use the extensions to

the cost model discussed in the previous section to rank candidate configura-

tions. Bottom-up strategies, in contrast, require the enumeration space to be

generated eagerly (e.g., see
greedy(m,B)
and the knapsack-based strategies in

Section 6.1). In such cases, it is crucial to restrict the enumeration space, or

else the resulting techniques would simply not scale beyond trivial problem

Search WWH ::

Custom Search