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
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 .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