UpBit: Scalable In-Memory Updatable Bitmap Indexing

ABSTRACT
Bitmap indexes are widely used in both scientific and commercial
databases. They bring fast read performance for specific types
of queries, such as equality and selective range queries. A major
drawback of bitmap indexes, however, is that supporting updates
is particularly costly. Bitmap indexes are kept compressed to minimize
storage footprint; as a result, updating a bitmap index requires
the expensive step of decoding and then encoding a bitvector. Today,
more and more applications need support for both reads and
writes, blurring the boundaries between analytical processing and
transaction processing. This requires new system designs and access
methods that support general updates and, at the same time,
offer competitive read performance.
In this paper, we propose scalable in-memory Updatable Bitmap
indexing (UpBit), which offers efficient updates, without hurting
read performance. UpBit relies on two design points. First, in addition
to the main bitvector for each domain value, UpBit maintains
an update bitvector, to keep track of updated values. Effectively, every
update can now be directed to a highly-compressible, easy-toupdate
bitvector. While update bitvectors double the amount of uncompressed
data, they are sparse, and as a result their compressed
size is small. Second, we introduce fence pointers in all update
bitvectors which allow for efficient retrieval of a value at an arbitrary
position. Using both synthetic and real-life data, we demonstrate
that UpBit significantly outperforms state-of-the-art bitmap
indexes for workloads that contain both reads and writes. In particular,
compared to update-optimized bitmap index designs UpBit is
15-29 faster in terms of update time and 2:7 faster in terms of
read performance. In addition, compared to read-optimized bitmap
index designs UpBit achieves efficient and scalable updates (51-
115 lower update latency), while allowing for comparable read
performance, having up to 8% overhead.