Database Reference

In-Depth Information

set of candidate indexes for query
Q
, obtained by any of the techniques of

Section 4.1. Let
C
i

(

i

≥

0

)

be a family of candidate indexes defined as follows:

C
0
=

cand

(

Q

)

Q

∈

W

C
i
+
1
=

∪

C
i

{

I
1
⊕

I
2
for each
I
1
,

I
2
∈

C
i
}∪

{

I
1
⊗

I
2
for each
I
1
,

I
2
∈

C
i
}∪

K
)
for each
I

K
⊆

{
ρ(

I

,

=

R

(

K

,

S

)
∈

C
i
,

K

}∪

{
(

I

)
for each
I

∈

C
i
}

That is,
C
i
+
1
is obtained by considering all possible merges, splits, reductions,

and promotions of indexes in
C
i
. We define
closure

=
C
k
, where
k
is the

smallest integer that satisfies
C
k
=
C
k
+
1
. In words, the closure of a workload
W

is the set of all indexes that either are in the candidate set of a query in
W
or

can be derived from these candidates through a series of merging, splitting,

reduction, and promotion operations. Our goal is then to obtain a subset of

this closure that fits in the available storage and is as ecient as possible for

a given representative workload. Thus, the physical design problem can be

stated as follows:

(

W

)

Physical design problem:
Given a workload
W
={
Q
1
,... ,
Q
n
}
, where each

Q
i
is a
SQL
query or update, and a storage bound
B
, obtain the index configu-

ration
C
={
I
1
,... ,
I
k
}
such that:

1.
C

⊆
closure(

W

)

2.
I
∈
C
size(

B

3.
q
i
∈
W
cost(
q
i
,
C
)
is minimized, where
cost(
q
,
C
)
is the optimizer estimated cost

of query
q
under configuration
C

I

)
≤

)
just specifies all possible indexes

that can be considered as part of the final configuration, but in general it is

not feasible to evaluate each subset of
closure(

Note that the definition of
closure(

W

)
except for
extremely
simple

cases. In Chapter 6 we introduce different approaches to effectively traverse

the search space of a physical design problem instance and to obtain good

configurations in reasonable amounts of time.

W

4.4

Summary

•

The search space for the physical design problem can be defined as

the closure of an initial set of query-specific candidates under suitable

transformations.

Search WWH ::

Custom Search