Handling Materialized Views - Automated Physical Database Design and Tuning - page 151

over the same table or view. As discussed in Section 4.3, the search space for
workload W is therefore defined as closure

( W ) = VC k , where k is the smallest

integer that satisfies VC k = VC k + 1 .

8.2.5.1 Discussion: Why Merge and Reduce?

We now explain why the merge and reduction operators in fact cover the set
of relevant indexes over views for the physical design problem in the context
of typical query optimizers.
Consider a subquery q 1 that exactly matches a view V 1 (i.e., q 1 and V 1 are
semantically equivalent). Then, q 1 can be matched and answered by either V 1
or some generalization V of V 1 (e.g., V is obtained by adding to V 1 additional
grouping columns or relaxing its selection predicates). By definition, V is
larger than V 1 and therefore less effective in answering subquery q 1 .Why
should we then consider V in our search space, since it is both larger and
less ecient for q 1 than the original V 1 ? The only reasonable answer is that
q 1 is not the only query in the workload. Instead, there might be some other
subquery q 2 (which is matched perfectly by V 2 ), for which V can also be
used. In this scenario, having V instead of the original V 1 and V 2 might be
beneficial, since the size of V might be smaller than the combined sizes of
V 1 and V 2 (albeit being less ecient for answering q 1 and q 2 ). We should
then consider V in our search space, noting that V must be a generalization
of both V 1 and V 2 . Now, the merging of V 1 ⊕

V 2 seems the most appropriate
choice for V , since it results in the most specific view that generalizes both V 1
and V 2 (other generalizations are both larger and less ecient than V 1 ⊕ V 2 ).

The merge operation covers all the “interesting” views that can be used to
answer expressions originally matched by the input set of views.
Let us now consider subexpressions. In fact, a view V R that is not a gen-
eralization of a query q can still be used to rewrite and answer q . It would
also make sense, then, to consider in our search space such subexpressions
of q that can be used to speed up its processing. In general, the “reduc-
tions” that we look for are somewhat dependent on the view-matching engine
itself. View-matching engines typically restrict the space of transformations
and matching rules for eciency purposes. Usually, the only subqueries that
can be matched and compensated with a restricted view contain fewer joins.
But this is how the reduction operator is defined (i.e., eliminating joins from
the original view). ∗ Thus, the reduction operator in its generality covers all
the “interesting” views that can be used to rewrite queries originally matched

∗ In general, if the view-matching engine is capable of additional functionality (e.g., taking the
union of several horizontal fragments of a single template expression to answer a given sub-
query), we should certainly extend the primitive operators accordingly (e.g., considering range
partitioning over a column as a primitive operator).