Database Reference
In-Depth Information
used to indicate whether a bit position in a bitmap is used or not. Such an
existence bitmap may also be used to indicate whether a particular record has
been deleted without recreating the whole bitmap index. This mapping mech-
anism is robust to changes and can be applied to all bitmap indexes of a table.
In most scientific applications, data records are stored in densely packed
arrays
35
,
49
,
59
; therefore, a more straightforward mapping between the RIDs
and positions in bitmaps can be used. Furthermore, most scientific data con-
tain only fixed-sized data values, such as integers and floating-point values,
and are stored in multidimensional arrays. In these cases, the array index is a
durable mapping between bit positions and data records. Usually such RIDs
are not stored explicitly.
The bitmap indexes are particularly useful for query-intensive applications,
such as data warehousing and on-line analytical processing (OLAP).
66
,
112
One of the key reasons is that queries can be answered with bitwise logi-
cal operations on the bitmaps. In the example shown in Figure 6.15, a query
“
A
b
2
).
Since most computer hardware support such bitwise logical operations e-
ciently, the queries can be answered eciently in general. Another key reason
is that answers from different bitmap indexes can be easily combined. This
is because the answers from each bitmap index are a bitmap, and combin-
ing the different answers simply requires additional bitwise logical operations.
Because combining answers from different indexes eciently is such an impor-
tant consideration, a number of DBMS that do not support bitmap indexes,
such as PostgreSQL and MS SQL server, even convert intermediate solutions
to bitmaps to combine them more effectively.
Because results from different indexes can be eciently combined, a bitmap
index is built for one column only, and composite bitmap indexes for multiple
columns are rarely used. This simplifies the decisions on what indexes to build
because one does not need to consider composite indexes. This also simplifies
the query optimization because there are fewer indexes to consider.
The biggest weakness of the basic bitmap index is that its size grows linearly
with the number of distinct values of the column being indexed. Next, we
review three sets of strategies to control the index sizes and improve the
query response time, namely, compression, encoding, and binning.
<
2” can be answered by performing bitwise OR on
b
1
and
b
2
(
b
1
|
6.6.2 Compression
Each individual bitmap in a bitmap index can be compressed with a data
compression method.
60
Any lossless compression may be used. However, the
specialized bitmap compression methods typically offer faster bitwise logical
operations and consequently faster query response time.
3
,
45
The most widely
used bitmap compression method is byte-aligned bitmap code (BBC).
4
,
5
More
recently, another bitmap compression method called word-aligned hybrid
(WAH) code was shown to perform bitwise logical operations more than 10
times faster than BBC.
107
,
109
