Database Reference
In-Depth Information
offer the best space-time trade-off.
21
However, practitioners have stayed away
from two-component encodings; existing commercial implementations either
use one-component equality encoding (the basic bitmap index) or the binary
encoding. This discrepancy between the theoretical analysis and the current
best practice is because the analysis has failed to account for compression,
which is a necessary part of a practical bitmap index implementation.
A multilevel index is composed of a hierarchy of nested bins on a column.
Since a level in such an index is a complete index on its own, a query may
be answered with one or a combination of different levels of a multilevel in-
dex. Therefore, this type of composite index offers a different type of trade-off
than the multicomponent index.
86
,
108
We will give more detailed information
about the multilevel indexes in the next subsection after we explain the basic
concept of binning.
Because of the simplicity of WAH compression, it is possible to thoroughly
analyze the performance of WAH-compressed indexes.
110
This analysis con-
firms the merit of the basic equality encoding and the binary encoding. Among
the multilevel encodings, the new analysis reveals that two levels are best
for a variety of parameter choices. More specifically, it identifies three two-
level encoded indexes that have the same theoretical optimality as the WAH-
compressed basic index, but can answer queries faster on average. Figure 6.17
12
BN
E1
EE
RE
IE
10
8
6
4
2
0
0
2
4
6
8
10
×10
7
Number of Hits
Figure 6.17
(See color insert following page 224.) The query response time
of five different bitmap encoding methods with WAH compression (BN: bi-
nary encoding, E1: the basic one-component equality encoding, EE: two-level
equality-equality encoding, RE: two-level range-equality encoding, IE: two-
level interval-equality encoding).
