Position List Word Aligned Hybrid: Optimizing Space andPerformance for Compressed Bitmaps
François Deliège

Torben Bach Pedersen

Department of Computer Science
Aalborg University, Denmark

Department of Computer Science
Aalborg University, Denmark

fdeliege@gmail.com

tbp@cs.aau.dk

ABSTRACT

then, various approaches have been studied to improve bitmap indexes for high-cardinality attributes. A deeper review of bitmap
index extensions, compression techniques, and technologies usedin commercial DBMSes is presented in [15].
The binning technique partitions the values of the index attributes
into ranges [13, 17]. Each bitmap captures a range of values rather
than a single value. Binning techniques prove to be useful when
the attribute values can be partitioned into sets. In [8], a binningtechnique using partitioning based on query patterns, their frequencies, and the data distribution is presented and further improves theindex performance. Bit-slicing techniques rely on an ordered listof bitmaps [11]. If every value of an attribute can be represented
using n bits, then the indexed attribute is represented with an ordered list of n bitmaps, where for example, the first bitmap represents the first bits of the values of the indexed attribute. Dedicatedarithmetic has been developed to operate directly on the bitmaps inorder to, for example, perform ranges queries [12]. The AttributeValue-Decomposition (AVD) is another bit-slicing technique designed to encode both range-encoded and equality-encoded bitmap
indexes [5]. Both lossy and lossless bitmap compression schemes
have been applied to bitmap indexes. The Approximate Encoding,(AE), is an example of lossy bitmap compression scheme [4]. An
AE compressed bitmap index returns false-positives but is guarantied not to return false-negatives. The accuracy of an AE compressed bitmap index ranges from 90% to 100%.
The Byte-aligned Bitmap Compression (BBC) [3] and the Word
Aligned Hybrid (WAH) [16] are both lossless compression schemes
based on run-length encoding. In run-length encoding, continuous
sequences of bits are represented by one bit of the same value andthe length of the sequence. The WAH compression scheme is currently regarded the most CPU efficient scheme, and is faster than,e.g., BBC. The performance gain is due to the enforced alignment
with the CPU word size. This yields more CPU friendly bitwise
operations between bitmaps. However, WAH suffers from a significant storage overhead, an average of 60% storage overhead over
BBC was reported [16]. More recently, for attributes with cardinalities up to 10,000, hybrid techniques based on combined Huffman
run-length encoding have shown their superiority from a size pointof view [14]. However, both storage and performance of such compressed bitmap indexes decrease for bigger cardinalities and performing bitwise operations (OR/AND) on such bitmaps is very expensive since the bitmaps must first be de-compressed and later recompressed. General-purpose data compression algorithms, suchas PFOR and PFOR-DELTA [19], often offer very efficient decompression but are not well-suited for bitmap compression as theynecessitate a preliminary decompression to operate on the values.
This paper improves upon existing work by offering a lossless
bitmap compression technique that outperforms WAH, currently

Compressed bitmap indexes are increasingly used for efficiently
querying very large and complex databases. The Word Aligned
Hybrid (WAH) bitmap compression scheme is commonly recognized as the most efficient compression scheme in terms of CPU
efficiency. However, WAH compressed bitmaps use a lot of storage space. This paper presents the Position List Word Aligned
Hybrid (PLWAH) compression scheme that improves significantly
over WAH compression by better utilizing the available bits andnew CPU instructions. For typical bit distributions, PLWAH compressed bitmaps are often half the size of WAH bitmaps and, at thesame time, offer an even better CPU efficiency. The results are verified by theoretical estimates and extensive experiments on large
amounts of both synthetic and real-world data.

1.

INTRODUCTION

Compressed bitmap indexes are increasingly used to support efficient querying of large and complex databases. Example applications areas include very large scientific databases and multimedia applications, where the datasets typically consist of feature setswith high dimensionality. The present work was motivated by theneed to perform (one- or multi-dimensional) range queries in large
multimedia databases for music (Music Warehouses). Here, musicsnippets are analyzed on various cultural, acoustical, editorial, andphysical aspects, and the extracted features are high-dimensional,
and range over very wide intervals. However, the exact same characteristics apply to a wide range of applications within multimedia and scientific databases. While bitmap indexes are commonly
accepted as an efficient solution for performing search on lowcardinality attributes, their sizes increase dramatically for highcardinality attributes. Therefore, the central challenge is to develop
an efficient compression technique for sparse bitmaps and that has
a low overhead for low-cardinality attributes.
The first use of a bitmap index in a DBMS dates back to 1987 [10].
The index was made from uncompressed bitmaps and suffered fromtremendous storage requirements proportional to the cardinality of
the indexed attribute, causing it to become too large to fit in memory and leading to a deterioration of the performance [18]. Since

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
EDBT 2010, March 22–26, 2010, Lausanne, Switzerland
Copyright 2010 ACM 978-1-60558-945-9/10/0003 ...$10.00.

228seen as the leading bitmap compression scheme for high-cardinality
attributes, from both a storage and a performance perspective. Other
extensions to the bitmap index (bit-slicing, etc.) will thus also benefit from the proposed compression scheme to represent their underlying bitmaps.
Specifically, the paper presents Position List Word Aligned Hybrid (PLWAH), a new bitmap compression scheme. PLWAH isbased on the observation that many of the bits used for the runlength counter in the WAH compression scheme are in fact neverused, since runs never become long enough to need all the bits. Instead, these bits are used to hold a “position list” of the set/unset
bits that follow a 0/1 run. This enables a significantly more efficientstorage use than WAH. In fact, PLWAH compressed bitmaps areoften only half the size of WAH compressed ones, and at the sametime, PLWAH is faster than WAH, thus PLWAH provides “the bestof both worlds.” PLWAH guarantees a maximum bitmap size inwords that is at most the number of set bits. Furthermore, PLWAH
has a very low overhead on non-compressible bitmaps (1/64 or 1/32
depending on word length).
Additional contributions include the removal of the active wordand bitmap length that significantly reduce the size of compressed
bitmap indexes composed of very short compressed bitmaps, the reduction of the conditional branches required to decompress a word,
and the creation of an adaptive counter that allows extremely sparse
bitmaps to be compressed efficiently without necessitating longer
words that increase the size of the bitmaps.
This paper shows that for uniformly distributed bitmaps, the hardest bitmaps to compress for compression schemes based on run
length encoding, PLWAH uses half the space of WAH. On clustered
bitmaps, PLWAH also uses less storage than WAH. These results
are shown in a detailed theoretical analysis of the two schemes. The
paper also presents algorithms that perform efficient bitwise operations on PLWAH compressed bitmaps and analyzes their complexity. Again, the analysis shows PLWAH to be faster than WAH.
The theoretical results are verified by extensive experimentation on
both synthetic and real-world (music) data. The experiments confirm that PLWAH uses significantly less storage than WAH, while
also outperforming WAH in terms of query speed. While developed in the specific context of Music Warehouses, the presented
compression scheme is applicable to any kind of bitmaps indexes,
thus making the contribution generally applicable.
The paper is structured as follows. Section 2 describes PLWAH
compression scheme. In Section 3, we establish the upper andlower bounds of the compression ratio, provide size estimates forboth uniformly distributed and clustered bitmaps, and discuss theimpact of the size of the position list. The algorithms for performing bitwise operations on the compressed bitmaps are presented in
Section 4, along with an analysis of the time complexity of thepresented procedures. In Section 5, the theoretical size and timecomplexity estimates are verified through extensive experiments on
both synthetic and real data sets. Finally, in Section 6, we conclude
and present future research directions.

2.

Uncompressed bitmap:
000 … 000 1 000 … 000 1 000 … 000 1 00
50 x 080 x 040 x 0

2x0

Uncompressed bitmap organizedin groups of 31 bits:
0000000000 0000000000 0000000000 0
0000000000 0000000001 0000000000 0
0000000000 0000000000 0000000000 0
0000000000 0000000000 0000000000 0
0000000100 0000000000 0000000000 0
0000000000 0000000100 0000000000 0
31 bits

11 bits

Merging consecutive homogenous groups:
0000000000 0000000000 0000000000 0
0000000000 0000000001 0000000000 0
0000000000 0000000000 0000000000 0
0000000000 0000000000 0000000000 0
0000000100 0000000000 0000000000 0
0000000000 0000000100 0000000000 0

2 groups
mergedEncoding 32 bits fill words:
1 0 0000000000 0000000000 0000000001
0 0000000000 0000000001 0000000000 0
1 0 0000000000 0000000000 0000000010
0 0000000100 0000000000 0000000000 0
0 0000000000 0000000100 0000000000 0

0 Fill word, counter = 1
Literal word
0 Fill word, counter = 2
Literal word
Literal word

Encoding sparse 32 bits literal words:
1 0 1010000000 0000000000 0000000001
1 0 0100000000 0000000000 0000000010
0 0000000000 0000000100 0000000000 0

0 Fill word, cnt = 1, pos = 20
0 Fill word, cnt = 2, pos = 8
Literal word

Figure 1: Example of PLWAH32 compression

We thus have six 31 bit long groups.
Step 2. Identical adjacent homogeneous groups, i.e., groups composed of either 31 set bits or 31 unset bits, are marked as candidates for a merge. In our example, the first group is a candidate
for a merge since it is exclusively composed of homogeneous bits.
Similarly, in the third and fourth groups, all bits are unset, so thetwo groups are candidates for a merge. The second, fifth, and sixthgroups are not homogeneous and therefore are not candidates.
Step 3. An additional bit is appended to the groups at the position of
their Most Significant bit (MSB). A set bit represents a group composed of homogeneous bits. Those 32 bit long words starting with
their MSB set are referred to as fill words. Fill words can be of two
types, zero fill words and one fill words; they are distinguished bytheir second MSB. Candidate groups for a merge are transformed
into fill words. The last 25 Least Significant Bits (LSBs) are used
to represent the number of merged groups each fill word contains.
In our example, the first group becomes a fill word. Similarly, thethird and fourth groups become a fill word with its counter is set
to two; this corresponds to the number of merged groups. An extra unset bit is added as MSB to heterogeneous groups. Encodedwords having their MSB unset are referred to as literal words. In
our example, the second, the fifth, and the sixth word are transformed into literal words; each starts with an unset bit. The firstand second words are fill words, their MSBs are set.
Step 4. Literal words immediately following and “nearly identical”1 to a fill word are identified. The positions of the heterogeneous bits are calculated and are placed in the preceding fill word.
The unused bits located between the fill word type bit and thecounter bits are used for this purpose. In our example, 25 bits are

PLWAH COMPRESSION

The PLWAH compression is composed of four steps; they are
explained with an example to ensure clarity. Assume an uncompressed bitmap composed of 175 bits and a 32-bit CPU architecture. The PLWAH compression steps are detailed below and areillustrated in Figure 1.
Step 1. The uncompressed bitmap is divided into groups of equal
size, corresponding to the word length of the CPU architecture minus one. In our example, the first four groups have a size of 31 bits.
The last group is appended with 11 zeros to reach a size of 31 bits.

1

The maximum number of bits differing between a literal word
and a fill word to be considered as “nearly identical” will later be
defined by a threshold parameter.

229

Literal word

composed of a long sequence of unset bits and ending with a set bit,
00000000...00001, is an example of a bitmap were the maximum
compression can be reached. Such bitmap can be represented with
only one fill
All compression schemes have an overhead when representing
incompressible bitmaps. For WAH and PLWAH, this overhead isone bit per word, so the compression ratio is w/(w − 1). A bitmap
containing no homogeneous groups will not have any fill words andwill be incompressible. The bitmap 01010101010101...0101010
is an example of an incompressible bitmap for both the WAH and
PLWAH compression schemes.
The upper and lower bounds of the PLWAH compression ratio
are respectively: (2w−2−s log2 w + 1)(w − 1)/w and (w − 1)/w.
As long as the upper bound is not reached, the worst PLWAH compression ratio is bounded by the WAH compression ratio.
The WAH and PLWAH compression ratio for different bitmap
distributions that fall within the compression limits are describedin Sections 3.2, 3.3, and 3.5. The (rare) bitmap distributions notwithin these boundaries, e.g., bitmaps that would cause counter
overflows, are discussed in Section 3.6.

total length w bits
bitmap of w-1 bits

Fill wordposition s...

position 1

counterlog 2 w − 1  bits
Figure 2: Structure of PLWAH literal and fill words

used for the counter, and 2 bits are used for the representing theword type. We thus have 5 bits remaining, namely the 3rd to the
7th MSB. A heterogeneous bit requires 5 bits to ensure all the possible bit positions in a literal word can be captured. In the example,
the second and fourth words are literal words with only one bit different from their preceding fill word; they can be piggybacked. The
position of the heterogeneous bit is placed in the position list of thefill word and the literal word is removed from the bitmap. The
last word is treated as any other word; in the example, it cannot be
piggybacked into its predecessor and is left as it is.
As mentioned above, the PLWAH compressed words are of two
kinds: fill words and literal words; their structures are presented in
Figure 2. A literal word is identified by an unset MSB, followedby an uncompressed group. Fill words are identified by a set MSB,
followed by a type bit to distinguish zero fills from one fills. The
remaining bits are used for the optional storage of the list of positions of the heterogeneous bits in the tailing group, and for storinga counter that captures the total number of groups the current fillword represents.
The position list can be empty in three cases: first, if the following word is a fill word of a different type; second, if the following
word is a literal but is not “nearly identical” to the current fill word;
and third, if the multiple fill words have to be repeated because thecounter has reached its maximum value. An “empty” element in theposition list is represented with all its value set to zero. The empty
position list is represented with all position values set to zero.

3.

3.2

In a uniformly distributed bitmaps, the probability of having a
set bit is independent from the bit position. Such bitmaps can becharacterized by their bit density d. The bit density is the fraction of bits that are set compared to the total number of bits. On a
uniformly distributed bitmap of density d, the probability of having exactly k or less bit set in a sequence of w bits is given by
the binomial distribution Pu (k, w, d) = Ckw dk (1 − d)w−k , wherew!
is the binomial coefficient and represents the total
Ckw = k!(w−k)!
number of combinations, that k bits can be picked out of a set ofw bits. The probability of having no bit set in a w − 1 bit long
word is Pu (0, w − 1, d) = (1 − d)w−1 . The probability of having all bits set is: Pu (w − 1, w − 1, d) = dw−1 . The probabilityof having two successive w − 1 bit long words filled with unset
bits is: Pu (0, 2w − 2, d) = Pu (0, w − 1, d)Pu (0, w − 1, d) =(1 − d)2(w−1) . Similarly, the probability of having two w − 1 bit
long words filled with set bits is: d2(w−1) .
The number of words W in a compressed bitmap is W = M −G, where M is the total number of groups, and G is the number ofpairs of blocks that can be collapsed [16]. For the WAH scheme,
GWAH is the number of pairs of adjacent blocks containing only unset bits plus the number of adjacent blocks containing only set bits.
The total number of adjacent blocks is M − 1, and the expectedvalue of GWAH is GWAH = (M − 1)Pcol , where Pcol is the probability of collapsing two adjacent blocks. The expected total numberof words using WAH is:

PLWAH SIZE ESTIMATES

In this section, we compare the space complexity of the WAH
and PLWAH compression schemes.
Let w be the number of bits in the CPU word, so that w = 32 on
a 32-bit CPU and w = 64 on a 64-bit CPU. Given an uncompressed
bitmap as input, we described in Section 2 that the PLWAH compression scheme divides the uncompressed bitmap into groups of(w − 1) bits, referred to as literal groups. For a bitmap with N bits,
there are bN/(w − 1)c such groups plus an optional incomplete
word of size N mod(w − 1). Unset bits are appended to the incomplete word so that the bitmap is divided into M = dN/(w − 1)egroups each containing (w − 1) bits. The total length in bits of theuncompressed bitmap with its tailing unset bits is L = M (w − 1).
A literal word is created by prepending an unset bit to a group.
When all groups of a bitmap are represented with literal words, thebitmap is said to be in its uncompressed form.

3.1

Compression of sparse and uniformly distributed bitmaps

W WAH = M − GWAHh
= M − (M − 1) Pu 0, 2(w − 1), di+ Pu 2(w − 1), 2(w − 1), dhi= M 1 − (1 − d)2(w−1) − d2(w−1)

Compression upper and lower bounds

The maximum compression is obtained when all words are fillwords. This happens when all groups but the last are homogeneousand identical, and the last group can be represented using the listof positions of the preceding fill word. The upper bound is thus
determined by the maximum number of groups a fill word can contain, plus one for the last literal group. Let s be the maximum
number of heterogeneous bits a fill word can store in its list of positions. The size of the list is s log2 w and the size of the counteris w − 2 − s log2 w.
 A single fill word can thus represent up to
2w−2−s log2 w + 1 groups of length w − 1. A very sparse bitmap(1)+ (1 − d)2(w−1) + d2(w−1)
Let L be the total length in bits of the uncompressed bitmap as
defined in Section 3.1. On a sparse bitmap, i.e., d → 0, by applying
a binomial decomposition, we have 1−(1−d)2(w−1) −d2(w−1) →2(w−1)d. As explained in [16], considering large values of L (andthereby M ) and small values of d, the expected number of words

230

2

can be approximated as follows:hi
W WAH ≈ M 1 − (1 − 2(w − 1)d) = 2Ld = 2h

1words per bit set(2)

where h denotes the number of set bits. Using the definition of bit
density, h = dL, the number of words in a sparse bitmap can be
expressed in terms of set bits as shown in Equation 2. In such asparse bitmap, all literal words contain only a single bit that is set,and each literal word is separated from the next by a fill word ofzeros. On the average, two words are thus used for each bit that isset.
We now calculate the expected total number of words using the
PLWAH compression scheme. The probabilityof having 0 to s set
PsP(k,w − 1, d). The
bits in a w − 1 bit long group is:u
k=0
probability of having a w − 1 bit long group with w − 1 unset
bits followed byP
a w − 1 bit long group with 0 to s set bits is:Pu (0, w − 1, d) sk=0 Pu (k, w − 1, d). Similarly, the probabilityof having a w − 1 bit long group with all its bits setPfollowed by agroup with 0 to s unset bits is: Pu (w − 1, w − 1, d) sk=0 Pu (w −1 − k, w − 1, d). The expected total number of words is:

0.25

0.0001

3.3

(3)

s
h
X
= M − (M − 1) (1 − d)w−1
Ckw−1 dk (1 − d)w−1−k
k=0

+d

w−1

s
X

Ckw−1 dw−1−k (1 − d)ki

k=0

For small values of d and large values of M , we can use a binomial decomposition. The expected number of words can then be
approximated as follows.
hi
W PLWAH ≈ M 1 − (1 − d)2(w−1) − (w − 1)d(1 − d)2w−3hi≈ M (w − 1) 2d − d(1 − (2w − 3)d)W PLWAH≈1hbit density

0.01

0.1

Compression of clustered bitmaps

For sparse bitmaps with d << 1, an upper bound for the number ofwords per set bit is to consider that almost all homogeneous groups
are composed of unset bits. Furthermore, for p = dq/(1 − d) → 0
we can use a binomial decomposition; this is always true for d <<1 as q <= 1. Therefore, as stated in [16], for large values of M ,the expected number of compressed words is as follows.
h2w−3 iW WAH ≈ M 1 − (1 − d) 1 − dq/(1 − d)hi
≈ M 1 − (1 − d) 1 − (2w − 3)dq/(1 − d)
(7)
h
i
Ld
=
1 + (2w − 3)qw−1(4)
Looking at the expected number of words relative to the expected
number of set bits, we have:
and

0.001

+ (1 − d)(1 − p)2w−3 + d(1 − q)2w−3≈ Ld = h

W WAH
≈2
h

WAH128

We now study the compression of a bitmap constructed by a random walk modeled by the following Markov process. A bit has
a probability p to be set if its preceding bit is unset, and a probability q to be unset if its preceding bit is set. The bit density is:d = (1 − d)p + d(1 − q) = p/(p + q). The clustered bitmap
can thus be fully described by the density d and its clustering factor
f = 1/q.
Let Pc (k, w, d, f |b0 ) denote the probability of having k set bits
in a block of w bits when the bit preceding the block is b0 , theclustering factor is f and the bit density is d. It is straightforward
to calculate Pc (0, w, d, f |0) = (1 − p)w = (1 − d/f (1 − d))w .
Thus, the probability to have two consecutive groups exclusively
composed of set bits or unset bits is respectively d(1 − q)2(w−1)−1
and (1 − d)(1 − p)2(w−1)−1 . The expected number of compressedwords in a WAH bitmap can thus be expressed as follows.
h
W WAH = M − (M − 1) (1 − d)Pc (0, 2w − 3, d, f |0)i+ dPc (2w − 3, 2w − 3, d, f |1)hi (6)= M 1 − (1 − d)(1 − p)2w−3 − d(1 − q)2w−3

ik=0

LWAH64

LWAH128

have reached their maximum size as explained by the lower boundof the compression ratio established in Section 3.1.

k=0

Pu (w − 1 − k, w − 1, d)

WAH32

WAH64

Figure 3: Word count estimates on uniformly distributed bitmapsshX= M − (M − 1) Pu (0, w − 1, d)
Pu (k, w − 1, d)+ Pu (w − 1, w − 1, d)

LWAH320.125

W PLWAH

s
X

0.5

(5)

The compressed size of a sparse bitmap is thus directly proportional to the number of bits set. In such a sparse bitmap, all words
are fill words of unset bits with one position set in the position listof the fill word. The compression ratio of PLWAH is asymptotically, within the limits of compressibility detailed in Section 3.1,
twice the compression ratio of WAH for a uniformly distributed
bitmap as the bit density goes to zero.
Figure 3 shows the expected number of words per set bit for
WAH and PLWAH depending on the bit density. The behavior of
the curves for low densities is explained by the previous approximations detailed in Equation 5. The error due to the approximation in
Equation 5 is less than a 1% for bit densities d < 0.001. For higher
densities, the number of words per set bit drops linearly to the bit
density: if the density is too high to have fill words, the bitmaps
are filled with literal words, they have become incompressible andFor bitmaps with a moderate clustering factor, f < 5, we have
W WAH ≈ 2h/f . Similarly, the expected number of words on a
PLWAH bitmap is as follows.
W PLWAH= M − (M − 1)shX× (1 − d)(1 − p)w−2
Pc (k, w − 1, d, f |0)

(8)

k=0

+ d(1 − q)w−2

s
X
k=0

231

Pc (w − 1 − k, w − 1, d, f |1)i1words per bit set

Unlike when k = 0, for 1 < k < w − 1, a recursive calculation is needed to calculate Pc (k, w, d, f |0). Nonetheless, on aclustered bitmap, a lower bound for Pc (k, w, d, f |0) is the probability to have k set bits forming an uninterrupted sequence of set
bits. The probability of having a group full of unset bits followed
by a groupwith k set bits in sequence is: (1 − d)p(1 − q)k−1 (1 −p)2w−4−k (w − k − 1)q + (1 − p) . Therefore, an upper boundfor the expected number of words in an PLWAH bitmap is to consider only uninterrupted sequences of set bits. The upper bound for
d << 1 can be expressed as follows.

0.5

0.25

PLWAH32 f=2, s=1
PLWAH32 f=3, s=1
PLWAH32 f=4, s=1

0.125
0.0001

0.001

0.01

0.1

bit density

1(a) Clustered bitmap on 32 bit long words

dW PLWAH e

1words per bit set= M − (M − 1)h× (1 − d)(1 − p)2w−3 + d(1 − q)2w−3+

WAH32 f=2
WAH32 f=3
WAH32 f=4s X
(1 − d)p(1 − q)k−1 (1 − p)2w−4−k
k=1

0.5

0.25

WAH64 f=2
WAH64 f=3
WAH32 f=4

(9)



× (w − k − 1)q + (1 − p)

PLWAH64 f=2, s=1
PLWAH64 f=3, s=1
PLWAH64 f=4, s=1

0.125
0.0001s X+dq(1 − p)k−1 (1 − q)2w−4−k

0.001

0.01

bit density

0.11(b) Clustered bitmap on 64 bit long words

k=1

Figure 4: Word count estimates on clustered bitmapsi× (w − k − 1)p + (1 − q)

3.4

The size of the position list in fill words

The size of the position list depends on the number of bits available in a fill word. A fill word contains two bits, a position list,
and a counter. Increasing the size of the position list causes thetotal number of bits assigned to the counter to decrease. There is
therefore a trade-off between the maximum number of groups thatcan be represented in a fill word, and the maximum number of heterogeneous bits in group that can be stored within its preceding fillword.
Each heterogeneous bit requires dlog2 we bits to be stored in
the position list. Let l be the number of bits taken by the position list and r the number of bits taken by the counter. The total
number of bits in a fill word is : w = 2 + l + r. The maximum
number of heterogeneous bits that can be stored in a fill word is:
w−2−rc.
s = b dlogl we c = b dlog
2
2 we
In Equation 3, the cumulative distribution increases for increassP
ing s. Similarly, all the terms in thein Equation 9 are positive.
Thus, for both uniformly distributed and clustered bitmaps, WPLWAH
decreases when increasing s. Therefore, maximizing s minimizes
WPLWAH .
Figure 5 shows the effect of varying s for uniformly distributedand clustered bitmaps. There is very little benefit of increasing s
on sparse uniformly distributed bitmaps as the probability of having multiple heterogeneous bits in a single group drops for low bit
densities. However, bitmaps whose bit density is between the twolinear zones contain fill words and literal words with a few set bits.
For those bitmaps, increasing the value of s increases the probability of a fill word to be able to carry its following literal word. Thus,
as s increases, the number of words per set bit decreases.
On a clustered bitmap, however, increasing s increases the compression ratio, such that WPLWAH = 0.5∗WWAH , i.e., all literal words
with heterogeneous bits can be stored in their preceding fill word.
The length of an uncompressed bitmap in a bitmap index corresponds to the number of indexed elements. For s = 1, on a 32-bit
CPU, PLWAH can represent 31 ∗ 225 > 1, 000, 000, 000 elements
in a single fill word. For s = 5, on a 64-bit CPU, PLWAH canrepresent 63 ∗ 232 > 270, 000, 000, 000 elements in a single fillword. Almost any imaginable database application will thus only
require a single fill word to capture homogeneous bit sequences.

Furthermore, we can make the same assumption used in Equation 7; on a sparse bitmap with d << 1, almost all homogeneousgroups are composed of unset bits. For s = 1, the expected numberof words a PLWAH bitmap can be approximated as follows.
hs=1
WPLWAH ≈ M 1 − (1 − d)(1 − p)2w−3
i− (1 − d)p(1 − p)2w−5 (w − 2)q + (1 − p)


f <5
1 h
≈ Ld(2q − q 2 ) = 2 −f f(10)
Equation 10 represents the size in words of a PLWAH bitmap where
the maximum number of sparse bit positions a fill word can contain is constrained to one. The number of sparse bits that can be“piggybacked” into a fill word depends on w and the length of thecounter as explained in Section 3.1.
Figure 4 presents the average number of compressed words per
set bit required by the WAH and PLWAH depending on the bit density for different values of the clustering factor. As established in
Equation 10, the number of words in a PLWAH bitmap decreases
as q decreases, i.e., as the clustering factor increases. We also observe that PLWAH compression always requires less words per set
bit than WAH compression. In Figure 4(a), the ratio between thenumber of words in a sparse WAH bitmap and the corresponding
PLWAH bitmap ranges from 1.32 to 1.13 for clustering factors
varying from 2 to 4. The compression ratio on 32 bit and 64 bit
word are identical. At higher bit densities, the bitmaps become incompressible and adopt a linear behavior. Finally, for very sparse
bitmaps, the word length has little impact on the number of WAH
and PLWAH words per set bit as shown by comparing the graphsfrom Figures 4(a) and 4(b). However, as the bitmaps get denser,
they become incompressible and the number of words per set bitis thus inversely proportional to the word length. As the density
approaches 1, the number of words becomes proportional to thenumber of unset bits, while the number of words per set bit tends to
0. For example, an uncompressed bitmaps of 1,000,000 bits withall bits set would be compressed to one word. Therefore, the ratioof words / bit set is: 1 / 1,000,000, which is close to 0.

232

2

necessary to index a clustered attribute is given by rewriting Equation 7 as follows.

words per bit set

1

sizeWAH
2w−3 Lwc ≈
1 − (1 − 1/c) 1 − q/c(1 − 1/c)
w−1
f <5 2h
≈
words
f

0.5
WAH64
PLWAH64 s=1
PLWAH64 s=5

0.25

0.125
0.00010.001

bit density

0.01

0.1

Using Equation 9, the total expected size of a corresponding bitmap
index compressed with PLWAH is as follows.

s=1,f <5
1 hw
sizePLWAH≈ L(2q − q 2 ) = 2 −
words
(16)
f
f

(a) Uniformly distributed bitmap on 64 bit long words

words per bit set

2

1

The bit density in each bitmap of a bitmap index of a uniformly
distributed attribute is inversely proportional to the attribute cardinality. Thus, for high-cardinality attributes, the bit density is low
for each bitmap of the bitmap index. The total size is proportional
to the number of set bits. Similarly, for a high-cardinality attribute
following a clustered distribution, the bitmaps of the bitmap index are sparse. The total size is proportional to the number of set
bits divided by the clustering factor, i.e., a clustered attribute takeless storage space. For example, an attribute following a distribution with a clustering factor f = 2 takes half the storage of a
uniformly distributed bitmap when compressed with PLWAH on
64 bit long words and a position list of size 5. Additionally, equations 13, 14, 15, and 16 show that for both WAH and PLWAH, andfor all attribute distributions, the total size of the bitmap is proportional to the size of the alignment, i.e., the CPU word length. For
example, a bitmap index of a uniformly distributed attribute compressed using PLWAH with 32 bit alignment takes half the spaceof a WAH compressed one with 32 bit alignment, which in turn isthe same size as a PLWAH compressed one with 64 bit alignment,
which again is half the size of PAWAH compressed one with 64 bitalignment.

0.5
WAH64
PLWAH64 s=1
PLWAH64 s=2
PLWAH64 s=5

0.25

0.125
0.0001

0.001

0.01

0.1

bit density(b) Clustered bitmap on 64 bit long words, f = 2

Figure 5: Word count estimates on clustered bitmaps

3.5

Compression of high-cardinality attributes

In this section, we discuss the compression of a attribute whose
random value follows a uniform distribution, and the compressionof a clustered attribute whose probabilities to change from one
value to another depends on a Markov process as described in Section 3.3.
Let c be the cardinality of the random attribute. The attribute
can thus be represented with c bitmaps. Since all the values havean equal probability of appearing, each bitmap is uniformly distributed with bit density: d = 1/c. For indexing attributes withhigh-cardinality the total estimated size in bits of the c WAH compressed bitmaps can be approximated as follows.
sizeWAH ≈ Lwc/(w − 1)hi
2(w−1)× 1 − 1 − 1/c− 1/c2(w−1)

3.6
(11)

sizePLWAH≈ Lwc/(w − 1)(12)h2(w−1)
2w−3 i1
× 1 − 1 − 1/c− (w − 1) 1 − 1/ccWhen c is large, (1/c)2w−2 → 0 and (1 − 1/c)2w−2 → (1 −(2w − 2)/c). The total size of the c WAH compressed bitmaps
that compose the bitmap index for a uniformly distributed random
attribute has the following asymptotic formula.
(13)

Similarly, the total estimated size of the c PLWAH compressed
bitmaps is as follows.
sizePLWAH = Lw bits = L words

Adaptive Counter

A potential problem with the PLWAH compression technique for
32 bit words occurs when the number of elements significantly exceeds 109 . In this case, the very long runs cannot be represented
with a single fill word, as not enough bits are available to represent the counter value. Instead, for a run with a length of 1011 , a
chain of approximately 100 fill words is needed. This issue could
be resolved by using 64 bit words, but this would double the size ofeach word in the index (and the total index size), in order to solvea problem that only occurs very infrequently.
Instead, in such scenario, we propose to use an adaptive counterthat basically uses 32 bit words when this is enough, and thenadapts to 64 bit words when necessary, meaning that the longer
words are only used for very long runs. This is achieved withoutchanging the basic encoding scheme. A very long run is encodedwith an empty position list in the (first) 32 bit (fill) word. The next
word is also a fill word, and the total length of the run (using a
50 bit counter) will be encoded in two parts: the 25 LSBs of thelength are put into the first word’s counter part, while the 25 MSBs
of the length are put into the second word’s counter part. For the(extremely rare) case of 0-run followed immediately by a 1-run (orvice versa), a literal word is inserted in the middle.
Figure 6 proposes an example of PLWAH bitmap using the adaptive counter. The counter value is 224−1 + 217−1+25 = 223 + 231
and the position of the set bit in the following word is 4. In its
uncompressed form, the bitmap is thus composed of (223 + 231 ) ∗32 + 3 unset bits followed by a set bit.

Similarly, the total estimated size in bits of the c PLWAH compressed bitmap is approximated as follows.

sizeWAH = 2Lw bits = 2L words

(15)

(14)

The same reasoning holds for a clustered attribute where theprobabilities are allowed to depend on another value. One such example is a simple uniform c-state Markov process: from any state,
the Markov process has the same transition probability q to otherstates, and it selects one of the c − 1 states with an equal probability. The total expected size in bits of the WAH compressed bitmaps

233

EmptyPosition List

Algorithm 2: Appends a fill word to a compressed bitmap

25 LSB of counter

Word 1

1 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Word 2

1 0 0 0 1 0 0

0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

AppendFill(bitmap C, word f ill, int count)last is the last word of the bitmap
1: if last is same type as f ill and last position list is empty then2:
count is added to the counter of last
3: else4:
Append f ill to bitmap

25 MSB of counter

Figure 6: Example of PLWAH adaptive counter

4.

BITWISE OPERATIONS

Logical bitwise operations are crucial operations for swiftly carrying out range queries and queries with multiple predicates using
bitmap indexes. For this reason, we next examine the complexityof performing bitwise logical operations on PLWAH compressed
bitmaps. In this section, we show that the time for completing an arbitrary logical operation between two PLWAH compressed bitmaps
is proportional to the total size of the two compressed bitmaps,
while when the two operands are in their uncompressed form andassuming all the bitmaps have the same size, the time required isconstant. Finally, we show that the time to perform a logical operation between a decompressed bitmap and a PLWAH compressed
one is proportional to the size of the compressed bitmap.

4.1

Algorithm 3: Appends a literal word to a compressed bitmap
AppendLit(Compressed bitmap C, literal word L)
last is the last word of C
1: if L = 0 then2:
AppendF ill(C, 0, 1)
3: else if last is counter and has empty position list then4:
if last is a zero fill then5:
if L is sparse then
. popcount CPU
6:
Generate position list for a zero fill . bitscan CPU
7:
Place position list into last
8:
else
9:
Append L to C
10:
else if L is sparse then
. popcount CPU
11:
Generate position list for a one fill
. bitscan CPU
12:
Place position list into last
13:
else
14:
Append L to C
15: else
16:
Append L to C

Operations on 2 compressed bitmaps

A bitwise operation on two compressed bitmaps is performedby sequentially scanning each input bitmap, compressed word bycompressed word. The complexity of bitwise AND/OR operations
are quite similar, but ANDs are somewhat faster since the resulting bitmap has less set bits than the operands (as opposed to ORs,
where the opposite is true). Thus, for simplicity, we focus on the
logical OR operation on two compressed bitmaps (the hardest of
the two). However, the methods are very easily adapted to logical ANDs. Details on the OR implementation are found in Algorithm 4. Additionally, three auxiliary procedures are shown: ReadWord, AppendFill, and AppendLit.
The ReadWord procedure (Algorithm 1) is called each time acompressed word has to be decompressed. The decompression requires very few CPU cycles and has only one branch2 . If the word isa fill word, it loads the corresponding fill group, adjusts the counter,and transforms the position list into a bitmap. Both the load of thedata corresponding to the fill word type and the transformation froma position list to a bitmap are done by multiplication and bit shiftoperations and do not require any branching. If the word is a literal
word, the data is loaded by masking out the word’s MSB.

branches. It performs two interesting operations, namely the countof the number of set bits and the transformation of a bitmap into a
position list. Both operations can be efficiently performed using the
new instructions at hand on recent CPU architectures. Counting thenumber of set bits can be performed directly using the population
count instruction, part of the SSE4a instruction set available, forexample, on the AMD “10h” [1] and the Intel “Core i7” [7] processor families. For older architectures, the most efficient alternativeis probably to count the number of times the LSB of the bitmap
can be removed before obtaining a bitmap with all bits unset. In
practice, one can limit the count to a threshold corresponding to
the maximum size the position list can reach. Generating the listof the positions of the set bits in a bitmap is performed by locating
the position of the LSB, removing the LSB, and repeating the process until all bits are unset. Many techniques to find the position of
the LSB in a word exist in the literature [9]. However, the bit scan
forward instruction, available for 32 and 64-bit words on modern
CPU architectures, e.g., “Pentium 4”, “AMD K8”, and above, is by
far the fastest approach of tackling the task.
The CCOR, procedure (Algorithm 4) performs a bitwise OR on
two compressed bitmaps. Its total execution time is dominated by
the number of iterations through the main loop. Each loop iteration consumes a fill word or a literal word from either one or both
bitmap operands. Let Wx and Wy , respectively, be the numberof words of each operand, and let Mx and My denote the numberof words in their decompressed form, i.e., the number of groups. If
each iteration consumes a word from both operands, min(Wx ; Wy )iterations will be required. If each iteration consumes only one
word from either operand, Wx + Wy iterations may be required.
Since each iteration produces at least one group and the result contains at most min(Mx , My ) groups, the main loop requires at mostmin(Mx , My ) iterations3 . The number of iterations through the

Algorithm 1: Reads a compressed word and updates the run
ReadWord ( Compressed word W )1: if W is a fill word then2:data ← ((W >> 62)&1) ∗ all_ones3:
nW ords ← W &counter_mask
4:
isF ill ← true
5:
isSparse ← (W &position_mask)! = 0
6:sparse ← bitmap constructed from the position list
7: else8:
data ← W &f irst_bit_unset. MSB of W is unset
9:nW ords ← 1
10:
isF ill ← f alse
11:
isSparse ← f alse
The AppendFill procedure (Algorithm 2) generates a fill wordcorresponding to the provided fill word type and counter. It has one
conditional branch.
Finally, the AppendLit procedure (Algorithm 3) transforms a literal group into a PLWAH encoded word. It has up to 4 conditional3

Our implementation allows to perform bitwise operations using
bitmaps of different uncompressed sizes. In the case of an OR, theremaining part of the longest bitmap is appended to the result.

2

Reducing branching is important for keeping the CPU instruction
cache full and avoiding stalls.

234

Algorithm 4: Performs a bitwise OR on 2 compressed bitmaps

is as follows.
TCC = Ta + Tl + Tf + Td

CCOR(Compressed bitmap X, Compressed bitmap Y )xrun holds the current run of X
yrun holds the current run of Y
Z is the resulting compressed bitmap
1: Allocate memory for Z
2: while xrun.it < size(X) and yrun.it < size(Y ) do3:
if xrun.nW ords = 0 then Readword(X, xrun.it)
4:
if yrun.nW ords = 0 then Readword(Y, yrun.it)
5:
if xrun.isF ill and yrun.isF ill then6:nW ords ← min(xrun.nW ords, yrun.nW ords)
7:
AppendF ill(Z, xrun.data|yrun.data, nW ords)
8:
decrease xrun.nW ords by nW ords
9:decrease yrun.nW ords by nW ords
10:
else
11:
AppendLit(Z, xrun.data|yrun.data). If bitmaps position lists are empty, ignore the remaining
12:
if (xrun.nW ords = 0 and xrun.isSparse) or(yrun.nW ords = 0 and yrun.isSparse) then13:
if xrun.nW ords = 0 and xrun.isSparse then
14:
Load xrun sparse data
15:
if yrun.nW ords = 0 and yrun.isSparse then16:
Load yrun sparse data
17:
if xrun.nW ords > 0 and yrun.nW ords > 0 then
18:
AppendLit(Z, xrun.data|yrun.data)
19:
Decrement xrun.nW ord
20:
Decrement yrun.nW ord
21:
if xrun.nW ords = 0 and xrun.isSparse then
22:
Load xrun sparse data
23:
else if yrun.nW ords = 0 and yrun.isSparsethen
24:
Load yrun sparse data25:
if xrun.nW ords = 0 then Increment xrun.it
26:
if yrun.nW ords = 0 then Increment yrun.it
27: Append the remaining of the longest bitmap to Z
28: Return Z< (Ca + Cl + Cf + Cd ) (Wx + Wy )(18)

The complexity of performing an OR operation on two compressed
bitmap is O(Wx + Wy ).

4.2

In-place operations

The most time expensive operations to perform a logical OR between two compressed bitmaps are in decreasing order: the memory allocation, the addition of a literal word, the addition of a fill
word, and the decompression of a word. If an OR operation is executed on many bitmaps, the memory management dominates the total execution time. However, logical bitmap operations such as OR
or AND are frequently used on a large number of sparse bitmaps
in order, for example, to answer range queries or combine predicates. A common approach to reduce the memory management
cost is to use an “in-place” operator that recycles the memory allocated for one of the operands to store the result, thus eliminating
expensive memory allocation. For example, instead of allocating
memory for z, and performing z = x OR y, the “in-place OR”
does x = x OR y.
The PLWAH in-place OR takes one uncompressed and a compressed bitmap as operand. Using an uncompressed operand ensures that there is never more input than output words, so that noresult word is overwriting a future input word. The uncompressed
bitmap can thus be used both as input and output. In addition to
avoiding repeated allocation of new memory for the intermediate
results, it also removes the need to compress temporary results. The
time complexity is thus mainly dependent on the time for initiallyallocating memory for the storage of the uncompressed bitmap andto perform I decompressions. The in-place OR operation is performed by the UCOR function whose details are supplied in Algorithm 5. UCOR is composed of a main loop that iterates througheach word of the compressed operand.
Algorithm 5: Performs a bitwise OR on an uncompressed bitmap
and a compressed bitmap

loop I satisfies the following conditions:

UCOR(Uncompressed bitmap U , Compressed bitmap C)
1: for all words in C do
2:
if run.data = 0 then3:
move forward of run.nW ords words in U
4:
else
5:
while nW ords do
6:
nW ords ← nW ords − 1
7:
Next word in U ← |run.data . “|” is a bitwiseOR8:
if run.isSparse then9:
Next word in U ← |run.sparse . “|” is a bitwise OR

min(Wx ; Wy ) < I < min ((Wx + Wy ), min(Mx , My )) (17)When the operands are two sparse bitmaps, each word is a fill wordwith a non-empty position list. In that case, each operation only
consumes one word from one of the operands. Therefore, it takes
Wx + Wy iterations to complete the bitwise OR, as each loop iteration executes AppendFill and AppendLit once. Compared to a
WAH bitmap where each set bit requires on average two words,
half the number of loop iterations are thus required. In the caseof WAH bitmaps, every two iterations, the AppendFill procedure
is called followed by, in the next iteration, a call to the AppendLit
procedure. Thus, the total number of calls to the AppendFill andAppendLit procedures to perform an OR operation on two PLWAH
bitmaps and two WAH bitmaps are equal.
The time complexity for performing a logical OR on two compressed bitmaps, TCC , mainly depends on four terms: the time toperform one memory allocation Ta , the time to perform I decompressions Td , the time to perform I AppendFill Tf , and the time toperform I AppendLit Tl . Let Cd , Cf , and Cl respectively be thetime to invoke each of these operations. As established in Equation 17, (Wx + Wy ) is an upper bound for I. In common memory
management libraries, the time for memory allocation and initialization is less than proportional to the size of the memory allocated [6]. Let Ca be the time to allocate one word, we thus have
Ta < Ca (Wx +Wy ). An upper bound for the total time complexity

Let x and y, respectively, be the uncompressed and compressed
operand bitmaps. The number of words in x is Mx , the numberof compressed words in y is Wy . Let I be the number of iterationin the main loop, each iteration of the loop treats one compressed
word, therefore there are I = Wy iterations. The time to allocate
memory for storing x, Tx , is at least proportional to Mx . Thus,
Ta < Ca Mx . Let Ci be the time to process one iteration, the timeto process the whole loop is proportional to Ci I. An upper boundfor the total time spent to perform an in-place OR TU C , is therefore:
TU C = Ca Mx + Ci Wy(19)

The UCOR has three conditional branches including one conditional branch for decompressing a word. In comparison, the inplace OR algorithm has a total of two conditional branches per

235

180

compressed word, but the number of compressed words in a WAH
bitmap is always higher than the number of words found in the corresponding PLWAH bitmap. As explained in Section 3, the numberof words in a PLWAH bitmap tends to be half the number of words
in a WAH bitmap. Executing the UCOR thus represents a net performance gain for sparse bitmaps.
Equations 18 and 19 show that the fastest procedure depends
on the size of the uncompressed bitmap and the size of the compressed bitmap, i.e., the compression ratio. Let r be the number oflogical bitwise OR operations performed to answer a range query.
The total time to perform the logical OR operations on compressed
bitmaps to answer a range query is as follows.

size ( MB)

160
140

WAH32

WAH64

120

PLWAH32

PLWAH64

100
80
60
40
20
0
100

1000

attribute cardinality

10000

100000(a) Size of bitmap index for a uniformly distributed attribute90
80

TU C,r ≈ Ca Mx + r(Ci Wy )

70

(20)

size ( MB)

TCC,r ≈ r (Ca + Cl + Cf + Cd ) (Wx + Wy )The in-place benefits from a lower number of iterations in its main
loop. In addition, the complexity of the main loop is significantly
reduced compared to the OR operation on two compressed bitmaps.
However, the in-place OR procedure suffers from a higher startup
cost due to the initial memory allocation corresponding to the sizeof an uncompressed bitmap. Since, in a bitmap index, the size ofthe uncompressed bitmap is proportional to the size of the dataset,the fastest procedure to perform a range query depends on the sizeof the dataset and the range of the query.

40

20

WAH32

WAH64

10

PLWAH32

PLWAH64

0
100

1000

attribute cardinality

10000

100000(b) Size of bitmap index for a clustered attribute, f = 2
45
40
35

EXPERIMENTS

In this section, we present the timing results from a Dell Dimension 9300 equipped with a Intel “Core 2 6700 2.66GHz” CPUrunning FreeBSD 7.1 64-bit OS which relies on the “jemalloc” [6]memory allocation library. All the presented experiments are performed within a PostgreSQL 8.3 DBMS. The implementation is in
C and runs as a loadable module for PostgreSQL, thus making thecode usable by a wide audience.
The experiments are conducted on both synthetic and real data
sets. The generated data is composed of a set of (key, attribute)pairs. The attribute follows either a uniform distribution, or a clustered distribution as presented in Section 3.5. For each, a comparative study of the influence of the distribution parameters on
the size and performance of the WAH and PLWAH indexes is conducted. The present study shows that PLWAH compression is superior to WAH compression. Furthermore, PLWAH performs “inplace OR” operations faster than WAH. For long range queries,
the speedup is up to 20%. As the performance-wise superiority of
WAH over BBC is already shown in previous work [16], we only
compare PLWAH with WAH. The indexes are implicitly cached inmemory by Postgresql as previous research has demonstrated thatcompressed bitmap indexes were CPU bounded [16].
Finally, experiments are conducted on a real data set composedof 15,000,000 music segments. Each music segment is describedusing 15 attributes, each with a granularity of 100,000. The index
keys are composed of the attribute identifier and the attribute value
and are in turn indexed using the B-tree index available in PostgreSQL. The index thus has 15 × 100, 000 entries and compressed
bitmaps. Each compressed bitmap is less than 2KB in size andthus fits in L1 cache and benefits from CPU optimizations related
to cache locality.

5.1

50

30

size ( MB)

5.

60

30
25
20
15
10

WAH32

WAH64

5

PLWAH32

PLWAH64

0
100

1000

attribute cardinality 10000

100000(c) Size of bitmap index for a clustered attribute, f = 4

Figure 7: Size comparison between WAH and PLWAH bitmap indexes(indexed elements: 10,000,000)

in accordance with the estimates in Equations 13 and 14. Hence,the curves of PLWAH64 and WAH32 overlap (the WAH32 curve isactually hidden below the PLWAH64 curve).
The size of bitmap indexes on clustered attributes are shownfor different clustering factors in Figures 7(b) and 7(c). Again,
PLWAH outperforms WAH on compression ratio. PLWAH64 provides significant benefits due to its longer position list. For shortposition lists, a higher clustering factor decreases the probability
for PLWAH to “piggyback” the next literal word in the current fillword.
The histograms of the music data set vary greatly from value tovalue. Low values tend to be very frequent, e.g., 30% of the elements have 0 as value for the first extracted feature. For frequentvalues, the four compression schemes converge; the bitmaps are
too dense to be compressed and the bitmaps are mainly composedof literal words. For less frequent values, the bitmaps can be compressed. As illustrated in Figures 8(a) and 8(b), PLWAH32 tends
to be half the size of WAH32, PLWAH64 half the size of WAH64
and very similar to the size of WAH32. A comparison of the total
index size between each compression scheme for the reviewed data
distribution is presented in Table 1. All the bitmap indexes have asize proportional to the number of values.
Finally, evidences of the influence of the position list size areuncovered in Figures 9(a) and 9(b). For uniformly distributed attributes, the probabilities of having multiple set bits in a single literal word are very low and the position list tends to contain only
one set bit position. The gain of increasing the size of the posi-

Bitmap index size

The sizes of the bitmap indexes for the various data distributions
discussed earlier are presented in Figure 7. Figure 7(a) confirmsthat for uniformly distributed high-cardinality attributes, the size of
PLWAH tends to be half the size of WAH for a given word length,

236

350

180

300

160
140
size ( MB)# elements

250
200
150

120
100
80
60

100

WAH64
PLWAH64 s=1
PLWAH64 s = 5

40
50

20
0

0

10000

10010

10020

10030

10040 10050 10060
Attribute value

10070

10080

10090

10100

100

(a) Histogram for values from 10,000 to 10,100 of the first music feature attribute
1400

PLWAH64

WAH64

PLWAH32

40
size ( MB)

50

1000
Size (B)attribute cardinality

10000

100000

60

WAH32

1200

800
600

30
20

400

WAH64
PLWAH64 s=1
PLWAH64 s = 3
PLWAH64 s = 5

10

200
0

0

10000

10010

10020

10030

10040 10050 10060
Attribute value

10070

10080

10090

10100

100

tion list is thus marginal. The position list size proves to have an
important impact on the compression ratio for clustered attributes.
Indeed, for clustered attributes, the probability of having more than
one set bit in a literal word increase with the clustering factor. Extending the position list allows more literal words to be encodedwithin their preceding fill word.

In the following, we study the performance of the OR operator
for answering range queries. A similar study can be conducted using other bitwise operators, however, (1) OR operations are more
complicated to handle for the compression scheme as the bitmaps
become denser, this is not always the case, e.g., with the AND operator; (2) long series of OR operations are often required to perform
range queries, while the number of AND operations, for example
required to treat a multi-dimensional range query, tends to be muchsmaller. Range queries are generated by choosing a range of a given
size randomly within the interval [0; 100, 000].
The total CPU time of performing range queries depending on
the range is presented next. In the following experiments, the bitmaps
are aggregated sequentially since this is the most revealing for thebasic performance difference between the compression schemas.
Other aggregation schemes are of course possible, for example, theaggregation could be performed by arranging the operation as abalanced tree. However, such schemes require more intermediate
memory allocation, etc., something which blurs the basic performance difference between compression schemes. For a balanced
tree-based scheme, there would be log r operations of complexity O(r), thus leading to an overall O(r log r) complexity. Even in
more complex scenarios, involving series of different logical operation on the bitmaps, the optimal ordering of the operations involved
WAH64
177 MB
88 MB
60 MB
47 MB
1617 MB

PLWAH32
43 MB
36 MB
28 MB
24 MB
565 MB

10000

100000in the aggregation can be easily calculated, as discussed in [2]. The
complexity of performing a single operation and the aggregation
scheme are thus orthogonal, so our choice of sequential aggregation does not distort the results.
The performance of range queries on short random intervals comprised of 10 values is shown in Figures 10(a) and 10(b). Here, since
the number of operation is small, the aggregation scheme has little
influence on the query performance. When the attribute cardinality increases, i.e., the density decreases, the compression ratio increases, and the number of words per bitmap decreases. Hence,
the CPU time required to process a constant number of bitmaps
decreases. For both algorithms, the query time is very similar
for PLWAH32 versus WAH32, and for PLWAH64 versus WAH64.
However, for the UCOR algorithm, the 64 bit compression schemes
perform up to 20% faster than their 32 bit counterparts.
The query performance for different range lengths using a sequential aggregation scheme is studied in the following. In a bitmap
index, each possible value of the indexed attribute is represented
with a bitmap; exactly one bit is set at any given position acrossall the bitmaps. Thus, when performing an OR operation, the number of set bits in the resulting bitmap is the total number of set
bits in each operand bitmap. On a uniformly distributed attribute,the bit density per bitmap is constant and since all bitmaps havethe same uncompressed length, the expected number of set bits ineach bitmap h is constant. Each OR operation thus increases thenumber of set bits approximately by h. After i OR operations,the result has ih set bits. Therefore, as explained by Equations 13
and 14, on very sparse bitmaps the length of the resulting WAH
and PLWAH bitmaps after i OR operations are, respectively, 2ih
and ih words long. Since, on sparse PLWAH bitmaps, each loop
iteration produces one fill word with a non-empty position list, thetotal number of iteration to produce the ith result is ih. Similarly,
on WAH bitmaps, each loop iteration produces one word, thus,
in total, 2ih iterations are required to produce the ith result. To
answera range query, r − 1P
OR operations are performed, thus
Pr
r
ih
=
hr(r
−
1)/2
and
i
i ih = hr(r − 1) loop iterations
are run. The complexity of performing a range query using the
CCOR procedures on two compressed bitmaps is thus quadratic in
the range while aggregating the bitmaps in a sequential fashion.

Performance study

PLWAH64
86 MB
48 MB
37 MB
31 MB
926 MB

attribute cardinality

Figure 9: Size comparison between PLWAH bitmap indexes with different
position list sizes (indexed elements: 10,000,000)

Figure 8: Bitmap sizes of the first music feature attribute

Data set
Uniform
Clustered, f = 2
Clustered, f = 3
Clustered, f = 4
15 music att.

1000(b) Size of bitmap index for a clustered attribute, f = 3(b) Size of bitmaps corresponding to values 10,000 to 10,100 of the first music feature
attribute

5.2

1000

(a) Size of bitmap index for a uniformly distributed attribute

WAH32
86 MB
46 MB
33 MB
27 MB
926 MB

Table 1: The size of the bitmap indexes for a common attribute cardinalityof 100,000

237

18

100

WAH32
WAH64
PLWAH32
PLWAH64 s =516

CPU time in ms

14

CPU time (ms)10

PLWAH64
1

WAH64

12

WAH32 inplace
WAH64 inplace
PLWAH32 inplace
PLWAH64 inplace

10
8
6

PLWAH32

4

WAH32

2
0

0.1
100

1000

10000

0

100000

20

40

range

60

80

100

attribute cardinality(a) Total query time using CCOR(a) CPU time to perform CCOR on 10 bitmaps
1225
PLWAH64

10WAH64
PLWAH32

15

CPU time (ms)CPU time (ms)

20

WAH32

10

8
6
WAH32 inplace
WAH64 inplace
PLWAH32 inplace
PLWAH64 inplace

4
2

5

0
0

0
100

1000

attribute cardinality

10000

200

400

100000

range

600

800

1000

(b) Total query time using UCOR(b) CPU time to perform UCOR on 10 bitmaps
1.3

Figure 10: Performance impact of the attribute cardinality (10,000,000
elements, uniformly distributed attribute)
Performance gain

1.25

However, as discussed earlier, this simple aggregation scheme allows a straightforward comparison the WAH and PLWAH.
The CCOR procedure offers good response time for queries on
short ranges as show in Figure 11(a). Experiments show no significant performance drop for ranges covering less than 20 attributevalues. In fact, PLWAH32 and WAH32 performance are so similarthat their performance curves overlap. For larger ranges, the performance of both WAH and PLWAH drops. For those large ranges,
the WAH performance tends to be slightly better than the PLWAH
due to the more complex AppendLit procedure present in PLWAH.
However, these observations for larger range queries are not relevant, as for both algorithms, the “in-place OR” procedures prove to
be much faster.
As illustrated in Figure 11(b), large range queries are very wellhandled by the UCOR procedure whose time complexity is linear in
the size of the range. However, the UCOR procedure suffers from ahigh start-up cost mainly due to the initial memory allocation. For
short range queries, the CCOR procedure is thus preferred. The
maximum size of the position list does not change the complexity of the decompression or the management of a sparse literal; forclarity purposes, Figure 11(b) only shows PLWAH64 with a position list of size 5, and PLWAH32 with a position list of size 1. Boththe WAH and PLWAH complexities depend on the size of the compressed operand bitmap. The small additional complexity of thedecompression and the accounting of sparse literal words do nothandicap the performance of PLWAH. On the contrary, PLWAH is
more efficient for executing the UCOR procedure as only half thenumber of loop iterations are required. As shown in Figure 11(c),the ratios between the CPU time of WAH and PLWAH increase up
to 20% as the range increases. The chaotic start is due to the highinfluence of the initial memory allocation. Better memory management, planned as future work, would further improve the ratio.
Figures 12(a) and 12(b) show similar results on the music data
set. The noteworthy higher starting cost of the in-place OR operator on the music data set is due to the larger number of elements: the uncompressed bitmaps are 50% longer due to the 50%
increase in the number of elements. However, the flatter slope after
the startup overhead is due to the smaller size of the compressed
bitmaps; bitmaps of uniformly distributed attributes are the hardest

1.2
1.15
1.1
WAH32 / PLWAH32
WAH64 / PLWAH64

1.05
1
0

200

400

Range

600

800

1000

(c) Query time ratio WAH / PLWAH

Figure 11: Performance on uniformly distributed attribute (elements:
10,000,000, cardinality: 100,000)

to compress, hence better compression ratios are obtained on themusic data. For the same reason, a flatter slope is also noticeable
for the OR on compressed bitmaps.
Finally, the impact of the position list size on the performance of
the CCOR operator is shown in Figure 13. The computation of theposition list is directly proportional to its size. As the size of theposition list increases, a small overhead can be observed for longrange queries for which better performance is achieved using the
UCOR algorithm. For short range queries, no significant overhead
is observed. The decompression time is independent of the size ofthe position list. Hence, the performance of the UCOR operation is
not directly influenced by of the size of the position list.
In summary, the experiments confirm the analytical estimates inEquations 13 and 14: a uniformly distributed attribute indexed with
PLWAH bitmaps takes half the size it would require using WAH.
Furthermore, we have measured the performance impact of threefactors, namely the attribute cardinality, the range, and the size ofthe position list. For long range queries PLWAH shows a significant
performance improvement. For short range queries, PLWAH and
WAH efficiencies are equivalent.

6.

CONCLUSIONS AND FUTURE WORKIn this paper, we present PLWAH, a bitmap compression schemethat compresses sparse bitmaps better and answers queries on longranges faster than WAH, which was so far recognized as the mostefficient bitmap compression scheme for high-cardinality attributes.
The results are verified through detailed analytical and experimental approaches. The storage gain essentially varies depending on

238

9
PLWAH64

8

WAH64

CPU time (ms)7

PLWAH32

6

WAH32
5
4
3
2
1
0
0

20

40

Range

60

80

100

(a) Total CPU time using CCOR on the music attributes
8

CPU time (ms)76

LWAH64 in-place
WAH64 in-place
LWAH32 in-place

5

WAH32 in-place
4
0

200

400

Range

600

800

1000

(b) Total CPU time using UCOR on the music attributes

Figure 12: Performance comparison between the WAH and PLWAH OR
operators on the music attributes
18
16
14
CPU time (ms)

12
10

WAH64
PLWAH64 s=1
PLWAH64 s =5

8
6
4
2
0
0

10

20

30

40

50
range

60

70

80

90

100

Figure 13: Performance impact of the size of the position list on a
uniformly distributed attributethe following parameters: the size of the data set, the attribute distribution, the attribute cardinality, and the word length.
For uniformly distributed high-cardinality attributes, we both proveand observe that the compression ratio is twice as good as for WAH.
For real data, the size of PLWAH compressed bitmaps varies between 57% and 61% of the size of WAH compressed bitmaps. In
terms of performance, PLWAH and WAH are comparable for shortrange queries. However, for long range queries, PLWAH is up 20%
faster than WAH, depending on the data distribution.
Future work encompasses studying the performance impact of
PLWAH used with complementary bitmap indexing strategies, andcollecting empirical storage and performance results from different data sets and CPU instruction sets. Furthermore, the current
implementation would benefit from making use of multi-core CPUarchitecture and dividing long bitmaps into chunks to ensure they
fit into the L1 cache. Additionally, new techniques, e.g., posting
list and batched updates, need to be developed in order to improvethe update performance of the index. Promising research directions
include the development of a dedicated bitmap materialization engine that would build aggregated bitmaps based on query patterns
and frequencies, and data distribution. The index would then beable to select the most efficient aggregation path, the required bitwise operations, and the type of bitwise algorithm to use.

7.

REFERENCES[1] Advanced Micro Devices. Software Optimization Guide for
AMD Family 10h Processors, November 2008.

239[2] S. Amer-Yahia and T. Johnson. Optimizing queries oncompressed bitmaps. In Proc. of Int. Conf. on Very Large
Data Bases (VLDB), pages 329–338, 2000.
[3] G. Antoshenkov and M. Ziauddin. Query processing andoptimization in ORACLE RDB. VLDB Journal,5(4):229–237, 1996.
[4] T. Apaydin, G. Canahuate, H. Ferhatosmanoglu, and A. S.
Tosun. Approximate Encoding for direct access and query
processing over compressed bitmaps. In Proc. of Int. Conf.
on Very Large Data Bases (VLDB), pages 846–857, 2006.
[5] C.-Y. Chan and Y. E. Ioannidis. Bitmap index design andevaluation. SIGMOD Rec., 27(2):355–366, 1998.
[6] J. Evans. A Scalable Concurrent malloc Implementation for
FreeBSD. FreeBSD, April 2006.
[7] Intel. Intel SSE4 Programming Reference, July 2007.
[8] N. Koudas. Space efficient bitmap indexing. In Proc. of ACM
Conf. on Information and Knowledge Management (CIKM),
2000.
[9] C. E. Leiserson, H. Prokop, and K. H. Randall. Using deBruijn sequences to index a 1 in a computer word, 1998.
Available at http://supertech.csail.mit.edu/papers.html.
[10] P. O’Neil. Model 204 architecture and performance. In Proc.
of Workshop in High Performance Transaction Systems,
1987.
[11] P. O’Neil and D. Quass. Improved query performance withvariant indexes. In Proc. of ACM Int. Conf. on Managementof Data (SIGMOD), pages 38–49, May 1997.
[12] D. Rinfret, P. O’Neil, and E. O’Neil. Bit-sliced index
arithmetic. SIGMOD Rec., 30(2):47–57, 2001.
[13] D. Rotem, K. Stockinger, and K. Wu. Optimizing candidate
check costs for bitmap indices. In Proc. of ACM Conf. on
Information and Knowledge Management (CIKM), 2005.
[14] M. Stabno and R. Wrembel. RLH: Bitmap compression
technique based on run-length and Huffman encoding. To
appear in Information Systems, 2009.
[15] K. Stockinger and K. Wu. Data Warehouses and OLAP:
Concepts, Architectures and Solutions, chapter Bitmap
Indices for Data Warehouses, pages 157–178. 2007.
[16] K. Wu, E. J. Otoo, and A. Shoshani. Optimizing bitmap
indices with efficient compression. ACM Trans. Database
Syst., 31(1):1–38, 2006.
[17] K. Wu and P. Yu. Range-based bitmap indexing for highcardinality attributes with skew. In Proc. of Int. Computer
Software and Applications Conf. (COMPSAC), pages 61 –67, 1998.
[18] M.-C. Wu and A. P. Buchmann. Encoded bitmap indexing
for Data Warehouses. In Proc. of the Int. Conf. on Data
Engineering, (ICDE), pages 220–230, 1998.
[19] M. Zukowski, S. Heman, N. Nes, and P. Boncz. Super-scalar
RAM-CPU cache compression. In Proc. of the Int. Conf. on
Data Engineering, (ICDE), pages 59–71, 2006.

Acknowledgments
This project is funded by the Danish Research Council for Technology and Production Sciences, through the framework project “Intelligent Sound”, grant no. 26-04-0092.