Incorporating Other Physical Structures - Automated Physical Database Design and Tuning - page 173

discussed either how to recommend these new structures in isolation or how
to integrate them in a combined search space. This is an important design
point whenever we include a new type of structure into the physical design
problem. We next comment on some general approaches to address this issue.

Iterative approach: A simple iterative approach begins by dividing the
available space among all available types of physical structures (e.g.,
75% of the budget for indexes and the remaining 25% for materialized
views) and then iteratively processing one structure type at a time. This
alternative is the easiest to engineer since it requires independent tuners
for each physical structure (these components can be treated as black
boxes, as we do not need to know the details inside of a specific tuner
to implement another one). The main problem with the approach, how-
ever, is one of interdependence (i.e., physical structures influence one
another). For instance, the choice of a single index might remove the
need of a materialized view. At the same time, indexes can be defined
over materialized views, but only after these have been recommended.
Several studies in the literature show that recommending physical struc-
tures in isolation can be significantly suboptimal. A secondary but im-
portant problem is that of defining a good allocation of resources to
each physical structure.
Combined approach: Since in the worst case all types of structures de-
pend on each other, a combined approach simply defines the search space
as the joint set of all possible structures. In this approach, the search is
conducted directly on the combined space, and heuristics are applied to
limit the candidates being enumerated. While this approach is suitable
to select a few types of physical structures and results in the best quality
of recommendations, it might not scale very well with the addition of
new features. The reason is that the search space grows combinatorially
with respect to the number of new design structures, and also a large
portion of the algorithms might need to be adapted to support such
joint enumeration.
Hybrid approach: Some studies suggest that the degree of dependency
among different physical structures can be better understood and lever-

Index Materialized

View

Partitioning MDC

Index — Strong Weak Weak

Materialized view Strong — Strong Strong

Partitioning Weak Strong — Weak

MDC Weak Strong Weak —

FIGURE 9.5 Dependence analysis for various physical structures.