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 4.1.3.3).

•
getCost(
ρ
:request,
{

I
j
}
:indexes)
: Approximates the cost of the

best locally transformed plan implementing

ρ

when

{

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
,

C

)

C

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

=

(

C
0
,

C
1
,... ,

C
n
)

C

is

cost

n

cost

(

W

, 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
)

(

W

, C)

, C))
. An online algo-

rithm that solves this problem must progressively determine
C
=
(

cost

(

W

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
)
=

0

otherwise

Search WWH ::

Custom Search