Continuous Physical Database Design - Automated Physical Database Design and Tuning - page 185

plan but avoid expensive optimization calls that would prevent low overhead.
The cost of the plan that we obtain by local changes is therefore an upper
bound of that of the global optimal plan that the optimizer would find under
the new configuration.
Once we obtain the initial, locally optimal configuration, we gradually relax
it to obtain alternative ones that might be more attractive from a cost-benefit
point of view. Specifically, we transform each configuration into another one
that is smaller but less ecient (lines 3-7). Since the alerter needs to be very
fast, we use index deletion and index merging as the only transformations
and perform a greedy search in which we move from one configuration to
the next using the most promising transformation (this technique is a sim-
plification of the top-down approach discussed in Section 6.2). In general,
there are many alternatives to transform a given configuration C . We can
delete each index in C , or we can merge any pair of indexes defined over the
same table. To rank the transformations, we use the penalty of transforming
a configuration C into C by an index deletion or index merge as defined in
Section 6.2.1.4. Penalty values measure the increase in execution cost per unit
of storage that we save in C compared with C . For an AND/OR request tree
T , penalty C ) = (

C C )/(

C )) . At each iteration of lines

3-7, we choose the transformation TR with the smallest penalty value and cre-
ate a new configuration (lines 6-7). After we exit the main loop, in line 8 we
check whether some configuration satisfies all the constraints, and in such a
case we issue an alert. The alert contains the list of all configurations that fit
in the available space (i.e., B min ≤

( C , − size ( C ) − size (

B max ) and are estimated to have
at least P improvement. The DBA can then analyze the alert and proceed
as appropriate (e.g., by explicitly performing a full physical database design
session).
If implemented appropriately, a physical design alerter can diagnose hun-
dreds of queries in the order of seconds, and the overhead imposed to the
query optimizer during normal operation for generating the AND/OR tree is
below 1%.

size ( C ) ≤

10.2 Continuous Physical Design Tuning
Although the alerting mechanism described earlier can identify when a tun-
ing session is necessary, the subsequent physical design tuning process is un-
changed. Therefore, each tuning session assumes that any change in the phys-
ical design is useful, independent of the cost of creating and dropping indexes.
This might not be adequate in general, because indexes that only marginally
improve performance but are expensive to create can cause unacceptable over-
head on a production server. We next discuss an alternative approach to the