Database Reference
In-Depth Information
6.1.3 Integer Programming Approach
The technique presented in Section 6.1.2.1 calculates more accurate bene-
fit values by solving several linear programs. These benefit values are sub-
sequently fed to the knapsack heuristic. We can alternatively cast the full
physical design problem as an integer programming instance and use existing
solvers to obtain the desired configuration. Note that this approach is not
strictly bottom-up, but we include it in this section since it generalizes some
ideas and techniques discussed earlier.
For that purpose, suppose that the indexes in the enumeration space are
ES
={
I
1
,... ,
I
n
}
, and the queries in the workload are
W
={
q
1
,... ,
q
m
}
.Now
assume that the set of atomic configurations for
W
and
ES
are
{
C
p
}
.
Recall that a configuration
C
is atomic for a query
q
if
q
uses all indexes
in
C
(see Section 5.2.1 for more details). We then calculate the benefit of
each query
q
i
(1
C
1
,...
≤
i
≤
m
) under atomic configurations
C
k
, denoted as
b
ik
, where
C
0
is the base configuration (using
the notation in the previous section, we have that
=
cost
(
q
i
,
C
0
)
−
cost
(
q
i
,
C
k
)
C
k
)
=
q
i
b
ik
).
Let
y
j
be a decision variable that is 1 if index
I
j
is part of the final con-
figuration, and 0 otherwise. Additionally, let
x
ik
be a decision variable that is
1 if query
q
i
uses all indexes in
C
k
when optimized under the final configura-
tion, and 0 otherwise. Then, the corresponding integer program is defined as
follows:
β(
p
m
maximize
b
ik
·
x
ik
i
=
1
k
=
1
subject to
p
x
ik
≤
1
∀
i
(6.1)
i
=
1
x
ik
≤
∀
,
∀
,
k
:
I
j
∈
y
j
i
j
C
k
(6.2)
n
size
(
I
j
)
·
y
j
≤
B
(6.3)
j
=
1
Constraints 6.1 guarantee that a query uses a single atomic configuration,
and Constraints 6.2 guarantee that all the indexes in such atomic configuration
are defined in the final configuration. Constraint 6.3 expresses the storage
limit. Finally, the optimizing function sums the benefits of all queries over all
possible atomic configurations. A single atomic configuration is used for each
query (Constraints 6.1), all indexes in such atomic configuration are present
in the final configuration (Constraints 6.2), and the final configuration fits
in the available storage (Constraint 6.3). Note that we require an additional
Search WWH ::
Custom Search