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

Figure 10.2c shows the resulting AND/OR tree for the requests of
Figure 10.2b. As a final step, we normalize the AND/OR tree so that it contains
no empty requests or unary intermediate nodes and strictly interleaves AND
and OR nodes. In our example (see Figure 10.2d), the normalized tree con-
sists of an AND root node whose children are either base requests or simple OR
nodes. Due to the specific nature of execution plans and requests, this is true
in general. In fact, we can prove by structural induction that the normalized
AND/OR request tree for an input query is either (1) a single request, (2) a
simple OR root whose children are requests, or (3) an AND root whose children
are either requests or simple OR nodes. Since requests for different queries are
orthogonal and can be satisfied simultaneously, we can combine the AND/OR
request trees for the current workload by using an AND root node. Normaliz-
ing this combined tree, we obtain, for an arbitrary input workload, an AND/OR
request tree that satisfies the previous property. This normalized tree can be
used to make inferences about the workload in the presence of physical design
changes without issuing additional optimization calls .

10.1.2 Upper Bounds Using AND/OR Trees
The idea of the alerter is to quickly identify whether the current configura-
tion is suboptimal. For doing so, we try a small number of variations in the
physical design and determine whether any of the alternatives can substan-
tially improve the cost of the workload under the current configuration. For
eciency purposes, however, we cannot perform additional optimization calls.
For that reason, a crucial component in the alerter is the ability to calculate,
without making an optimization call, upper bounds on the workload cost for
different configurations. Suppose that we want to calculate the cost of an al-
ternative subplan that uses indexes I to implement

. For that purpose, we
use the cost upper-bound techniques discussed in Section 5.2.2 (let us denote
this cost as Cost I ). If the original cost of the subplan associated with the
request ρ is Cost or i g , we define I = Cost or i g − Cost I . Then, I is a lower
bound on the local cost difference that we would gain by using I to implement
ρ rather than the index used originally by the optimizer. I values need not
be positive; a bad choice of I can result in a subplan that is more expensive
than the current one.
A configuration contains multiple indexes defined over request tables. We
then calculate the difference in cost by implementing a request

ρ

ρ with the

min I ⊆ C I . In general,
the workload is encoded as an AND/OR request tree, and OR nodes rule out
multiple simultaneous requests in a query plan. The difference in cost for an
AND/OR request tree T and a configuration C is defined as

C

best index strategy from a configuration C as =

⎧
⎨

T .ρ
C

if T is a leaf node with request T. ρ

i

T
C

T . child i

= if T is an AND node

⎩

C

T . child i

min i if T is an OR node

C