Database Reference
In-Depth Information
physical design problem. Specifically, we present algorithms that are always-
on and continuously modify the current physical design, reacting to changes in
the workload. The techniques have low overhead and take into account both
storage constraints and the cost to create temporary indexes. To simplify the
presentation, in the rest of this section we abstract the functionality related to
access path requests and local transformations using the following functions:
getRequests(q:query) : Gets the AND/OR request tree for q encoding
the requirements of each index strategy (see Section 10.1.1).
getBestIndex( ρ :request) : Gets the index that results in the cheapest
alternative implementing ρ (see Section
getCost( ρ :request, {
I j } :indexes) : Approximates the cost of the
best locally transformed plan implementing
I j }
are available
(see Section 5.2.2).
We next introduce the continuous physical design tuning problem. A con-
figuration is defined as the set of indexes available at some point in time. For
a configuration C , we denote the cost of creating an index I as b I (note that
b I depends on the indexes in C ). Let a workload W =
q 1 ,
q 2 ,... ,
q n )
be a se-
quence of queries and updates. As usual, we define cost
as the estimated
cost of q i when optimized under configuration C .A configuration schedule
q i ,
is a sequence of configurations
, such that q i is executed
when the DBMS is in configuration C i . The cost of W under
C 0 ,
C 1 ,... ,
C n )
, C) =
q i ,
C i ) + transition(
C i 1 ,
C i )
i = 1
= I ( C 1 C 0 ) b C I . Therefore, cost
where transition
is the sum of
each query cost in W under the corresponding configuration, plus the total cost
to transition between configurations in C . The optimal configuration schedule
C is the one with minimum cost, so C = minarg C (
C 0 ,
C 1 )
, C)
, C)) . An online algo-
rithm that solves this problem must progressively determine C = (
C 0 ,... ,
C n )
without seeing the complete workload W = (
q n ) . Specifically, to deter-
mine each C i we have knowledge only about the prefix (
q 1 ,... ,
q 1 ,... ,
q i ) .
10.2.1 Single-Index Scenario
To simplify the presentation, we first address the case of a single-index I .In
this scenario, a configuration C is denoted as either 1 (when the given index I
is present) or 0 (when it is absent). We only create I can from C =0, so we de-
note I 's creation cost simply as b I . The transition cost between configurations
is given by
b I
if C 0 = 0 and C 1 = 1
transition (
C 0 ,
C 1 ) =
Search WWH ::

Custom Search