Database Reference
In-Depth Information
10000000000
Query 5
Query 1-5
Query 1-22
100000000
1000000
10000
100
1
FIGURE 3.2
Number of possible relevant indexes for different query work-
loads.
indexes that, if present, would be considered by the query optimizer. Clearly,
reasoning with such a large number of indexes is a very dicult task!
3.1.3 Formal Complexity Argument
We now show that in general the physical design problem is NP-complete. We
provide a reduction from the 0-1 knapsack problem. The 0-1 knapsack problem
takes as inputs an integer capacity
C
and a set of objects
O
o
n
}
,
where each
o
i
has volume
c
i
and is associated with a benefit
b
i
. The output
={
o
1
,... ,
is a subset of
O
whose combined volume fits in
C
(i.e.,
c
i
≤
C
) and sum of
benefit values is maximized (i.e.
maximize
b
i
).
Consider an arbitrary knapsack problem with capacity
B
and objects
O
=
{
o
n
}
. We construct a physical design problem instance as follows. First,
we associate each
o
i
with a table
T
i
. Table
T
i
contains
n
i
tuples and
m
i
columns
(the first of such columns is called
col
). Values
m
i
and
n
i
are chosen such that
the following properties are satisfied. First, a nonclustered index on column
col
fits in exactly
c
i
pages (since the number of pages is determined by the
number of tuples
n
i
, this property essentially fixes the number of tuples of
T
i
). Second, table
T
i
fits in
b
i
+
o
1
,... ,
1 pages. Note that the number of tuples in
T
i
is fixed, so this property determines how many additional columns
m
i
to
create. Of course, the number of pages in the nonclustered index cannot be
larger than the number of pages in the full table
T
i
, so a third constraint is
that
b
i
+
c
i
. Note that
b
i
and
c
i
are given in the knapsack problem and
might not satisfy the inequality. However, in such a case, we can always scale
1
≥
Search WWH ::
Custom Search