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

Alerter ( T :AND/OR request tree,
B min , B max :storage constraints,
P :minimum percentage improvement)

1 R =∅ ;

2 Obtain locally optimal configuration C

T
C / cost current > P )

while (size(C)> B min and 100% ·

3

if (size(C)< B max )

4

5 R = R ∪ C

6 Pick transformation TR that minimizes penalty(C, TR(C))

7 C = TR(C)

8 if ( R =∅ ) ALERT ( R )

FIGURE 10.4 Alerting main algorithm. (Used with permission from
Bruno, N. & Chaudhuri, S. In Proceedings of the International Conference
on Very Large Databases [VLDB] , 2006.)

C is therefore a lower bound on the difference in the workload
cost between C and the original configuration (

The value

C values are lower bounds
on such difference, since we obtain feasible—but perhaps suboptimal—plans
that the optimizer would find for C ).

10.1.3 Alerting Technique
Recall from Figure 10.1 that during normal operation, the DBMS gathers
relevant information about the execution plans that are processed. This in-
formation is consolidated in the form of an AND/OR request tree. When a
prespecified triggering event happens, the alerter main algorithm is launched
(see Figure 10.4). The inputs to the alerter are the AND/OR request tree, space
bounds B min and B max that are acceptable for a new configuration, and the
minimum percentage improvement P that we consider important enough to
issue an alert.
The alerter eciently searches a space of configurations for one (or some)
that fits in the available space and is as ecient as possible. Similarly to the
approaches in Section 6.2, we start with an optimal configuration and relax
it into smaller and less ecient ones. We first obtain in line 2 the locally
optimal configuration C as the union of the indexes that implement the best
strategy for each request in the AND/OR request tree. Note that the best we
can do by following this approach is to obtain a locally optimal execution
plan. That is, we replace the physical subplans associated to each request in
the original plan with alternatives that are as ecient as possible. We would
not be able to, say, obtain a plan with a different join order or other complex
transformation that optimizers apply during plan generation. In that sense,
we are giving up some opportunities to obtain the globally optimal execution