The Bitmap Index

Why the bitmap index matters

Analytic queries are dominated by filtering. A dashboard asks "how many orders were status = 'shipped' AND region = 'EMEA' AND NOT channel = 'returns'?" — three predicates over three low-cardinality columns, combined with boolean logic. A B-tree index can answer each predicate individually, but combining three B-tree scans means intersecting three sorted lists of row IDs, an operation whose cost scales with the number of matching rows.

The bitmap index changes the representation so that combination is the cheap operation. Each predicate is already a bit-vector; ANDing three vectors of n bits is n/64 machine-word ANDs regardless of how many rows match. The final answer — the set of qualifying rows — is itself a bitmap, and counting the survivors is a population count. On a billion-row fact table this is the difference between a query that touches gigabytes of index entries and one that streams a few megabytes of packed bits through the CPU's ALU.

This is why every serious column-store and analytics engine — Oracle, DB2, Druid, ClickHouse, Apache Lucene/Elasticsearch, Apache Spark, Kylin — leans on bitmaps for filter evaluation.

How it works, step by step

Take a tiny customers table with a region column that has three distinct values: US, EU, ASIA.

row #   region     bitmap[US]  bitmap[EU]  bitmap[ASIA]
  0      US             1           0            0
  1      EU             0           1            0
  2      US             1           0            0
  3      ASIA           0           0            1
  4      EU             0           1            0
  5      US             1           0            0
  6      ASIA           0           0            1
  7      EU             0           1            0

1. One bitmap per distinct value. The column produces exactly c = 3 bitmaps, each n = 8 bits long. In every bitmap, position i answers a yes/no question: "does row i equal this value?"
2. Bitmaps are mutually exclusive and exhaustive. For a single-valued column, exactly one bit is set at each row position across the set of bitmaps. ORing all value bitmaps together yields the all-ones "not null" vector.
3. Predicates become bit-vector lookups. region = 'EU' is simply bitmap[EU] = 01001001 (rows 1, 4, 7).
4. Boolean logic is bitwise. region IN ('EU','ASIA') is bitmap[EU] OR bitmap[ASIA]. region != 'US' is NOT bitmap[US]. Combining columns — region='EU' AND premium=true — is bitmap[region=EU] AND bitmap[premium=true].
5. Materialize or count. The result bitmap's set positions are the qualifying row IDs; iterate them to fetch rows, or POPCNT the words for a COUNT(*) without ever touching the base table.

Because each operation is word-parallel, the asymptotic cost of a full boolean expression over the index is O(n / w) word operations per bitmap involved, where w is the machine word width (64). There is no per-matching-row cost until you actually materialize rows.

Compression: WAH, EWAH, and Roaring

The obvious objection: a column with c distinct values costs c × n bits uncompressed. For 1 billion rows and 100 distinct values, that is 100 billion bits ≈ 12.5 GB — before compression. But real bitmaps are extremely sparse or clustered: for a value appearing in 1% of rows, 99% of the bits are zero, often in long runs. Run-length compression exploits exactly this.

• WAH (Word-Aligned Hybrid). Splits the bit-stream into words. A word is either a literal (31 real bits) or a fill (a run-length of all-0 or all-1 words). Crucially, fills and literals stay word-aligned, so a WAH-compressed AND/OR runs word-at-a-time without decompressing — you skip aligned runs of zeros wholesale. Introduced by Wu, Otoo, and Shoshani (LBNL, FastBit).
• EWAH (Enhanced WAH). Packs a marker word that describes a run of fills followed by a count of literal words, improving skip efficiency and random access. Used by Git (for reachability bitmaps) and by Apache Hive.
• Roaring bitmaps. Partition the 32-bit row-ID space into 2¹⁶ chunks of 65 536 positions. Each chunk is stored in the smallest of three formats: an array container (sorted 16-bit ints) when sparse (< 4096 set bits), a raw bitmap container (8 KB) when dense, or a run container when values form long runs. Roaring picks per-chunk, so it adapts to local density and typically beats WAH on both size and speed. It is the default bitmap format in Lucene, Druid, Spark, ClickHouse, and InfluxDB.

A key property preserved by all three: compressed AND/OR/NOT stay in compressed space. You never expand a billion-bit vector to operate on it — you walk aligned words or containers and emit compressed output. That is what makes bitmap indexes practical at warehouse scale.

Bitmap index vs B-tree index

	Bitmap index	B-tree index
Ideal cardinality	Low (few distinct values)	High (near-unique)
Space	O(c · n) bits, compressed heavily when sparse	O(n) entries, ~O(n log n) bits
Point lookup (one value)	Load one bitmap, O(n / w)	O(log n) tree descent
Multi-predicate AND/OR/NOT	Native — bitwise, O(n / w) per vector	Intersect sorted row-ID lists, cost ∝ matches
COUNT / GROUP BY	POPCNT the result bitmap	Scan matching leaf entries
Range scan (a < x < b)	OR many value bitmaps (or use binned/range-encoded bitmaps)	Native — ordered leaves, one range walk
Single-row INSERT/UPDATE/DELETE	Expensive — may re-encode a compressed run; coarse locking	O(log n) node split/merge, row-level friendly
Concurrency (OLTP)	Poor — DML serializes on bitmap segments	Good — designed for it
Sweet spot	Read-mostly OLAP fact tables, star schemas	OLTP, primary keys, ordered scans

They are complementary, not competitors. A star-schema warehouse typically puts bitmap indexes on the low-cardinality dimension foreign keys of the fact table (enabling bitmap join indexes and star transformations) while keeping B-trees on high-cardinality surrogate keys.

Encoding schemes: equality, range, and binning

The naive "one bitmap per value" is equality encoding and is optimal for equality predicates but weak for ranges (a range needs to OR many bitmaps). Two refinements matter for real workloads:

• Range encoding. Bitmap k stores "value ≤ k" instead of "value = k". A range predicate a < x ≤ b then costs a constant two bitmap operations (B[b] AND NOT B[a]) instead of ORing every bitmap in the interval.
• Binning. For higher-cardinality-but-still-bounded columns, bucket values into bins (e.g. price ranges) and index the bins. Queries that don't align with bin boundaries incur a candidate check ("false positive" verification) against the base data — the classic FastBit strategy for scientific data.
• Bit-sliced / bit-plane encoding. Store each binary digit of the value as its own bitmap (⌈log₂ c⌉ bitmaps total). This supports arithmetic and range aggregation (SUM, range-count) with logarithmically many bitmaps — the basis of "bit-sliced indexing" (BSI) used for top-k and preference queries.

A worked query

Suppose a 1-billion-row events fact table with bitmap indexes on status (4 values) and device (3 values). We want:

SELECT COUNT(*)
FROM events
WHERE status IN ('ok','retry')
  AND device = 'mobile'
  AND status != 'error';

The optimizer rewrites this into pure bitmap algebra:

result = (B[status=ok] OR B[status=retry])
         AND B[device=mobile]
         AND NOT B[status=error]
answer = popcount(result)

Four billion-bit vectors are combined with three bitwise ops and one popcount. Compressed, each vector is a few megabytes; the entire query never reads a single base-table row. Contrast a B-tree plan, which would resolve each predicate to a row-ID set and intersect them, paying per matching row.

Implementation: a minimal bitmap index in Python

class BitmapIndex:
    """Equality-encoded bitmap index over one column.
    Each distinct value maps to a Python int used as an arbitrary-width bit-vector."""

    def __init__(self):
        self.bitmaps = {}   # value -> int (bit i set if row i has this value)
        self.n = 0          # number of rows indexed

    def add(self, value):
        row = self.n
        # set bit `row` in this value's bitmap; create it if new (new distinct value)
        self.bitmaps[value] = self.bitmaps.get(value, 0) | (1 << row)
        self.n += 1

    def eq(self, value):
        return self.bitmaps.get(value, 0)

    def neq(self, value):
        full = (1 << self.n) - 1            # all-ones mask over n rows
        return full & ~self.bitmaps.get(value, 0)

    def any_of(self, values):
        r = 0
        for v in values:
            r |= self.bitmaps.get(v, 0)     # OR
        return r

    @staticmethod
    def count(bits):
        return bin(bits).count('1')         # popcount

# --- usage ---
regions = ['US','EU','US','ASIA','EU','US','ASIA','EU']
idx = BitmapIndex()
for r in regions:
    idx.add(r)

# WHERE region IN ('EU','ASIA') AND region != 'US'
result = idx.any_of(['EU','ASIA']) & idx.neq('US')
print(idx.count(result))          # -> 5   (rows 1,3,4,6,7)
print(f"{result:08b}"[::-1])      # -> 01011011  (bit i = row i)

Python's big integers make every set operation a single &, |, or ~, and bin(bits).count('1') is the popcount. A production engine replaces the arbitrary-width int with word-aligned arrays plus WAH/Roaring compression, and the popcount with the CPU's hardware POPCNT instruction, but the algebra is identical.

The update problem

Bitmap indexes are cheap to read and expensive to write. Changing one row's status from ok to error flips two bits: clear bit i in B[ok], set bit i in B[error]. That is trivial on an uncompressed bitmap — but on a compressed one, flipping a bit that sits inside a long compressed run splits that run, turning one word into up to three and forcing a re-encode of the surrounding segment. And many engines take a coarse lock on the affected bitmap segment during DML, so concurrent updates serialize.

The practical consequences:

• Oracle explicitly recommends bitmap indexes for data-warehouse and decision-support tables and warns against them on tables with heavy concurrent OLTP, where the coarse locking causes contention and deadlocks.
• Analytics engines sidestep updates entirely by treating data as immutable segments: Druid, Lucene, and Parquet-based stores build bitmaps at ingest time per segment and never mutate them; deletes are handled by a separate "deletion bitmap," and updates are append-plus-tombstone, compacted later.
• Deferred / batch maintenance — rebuild or bulk-merge bitmaps offline — is the norm for warehouse ETL, which is bulk-load-then-query anyway.

Common misconceptions and pitfalls

• "Bitmaps are only for boolean columns." False — they work for any discrete column; you just get one bitmap per distinct value. Cardinality, not type, is the deciding factor.
• "High cardinality is fine because compression saves you." Compression shrinks each sparse bitmap, but you still manage c bitmaps and their metadata; when c ≈ n the per-value overhead and lookup dispatch dominate, and a B-tree is better.
• "Bitmap indexes speed up single-row OLTP lookups." They can, but the update cost usually makes them a poor fit for write-heavy transactional tables. Reach for a B-tree there.
• "NULLs don't need a bitmap." They do if you want IS NULL to be fast; some engines maintain an explicit NULL bitmap so the value bitmaps stay exhaustive.
• "Range queries are hopeless on bitmaps." Naive equality encoding is weak on ranges, but range-encoded or bit-sliced bitmaps turn a range into a constant number of operations.
• "A bitmap index and an inverted index are different things." They are duals — the same value→rows mapping stored as a dense vector vs. a sparse list. Engines switch representation based on term density.

A little history

The bitmap index traces to Patrick O'Neil's work on the Model 204 DBMS in the late 1970s and 1980s, which used bit-vectors for set-valued query evaluation. The idea entered mainstream relational databases when Oracle shipped bitmap indexes in Oracle 7.3 (1996) and built the star-transformation optimizer around them. Compression research at Lawrence Berkeley National Laboratory produced WAH and the FastBit library for scientific data in the 2000s. In 2016, Daniel Lemire and collaborators published Roaring bitmaps, which quickly became the de-facto standard container format across the open-source analytics stack — Lucene, Druid, Spark, ClickHouse, and even Git's on-disk reachability bitmaps all rely on the run-length/hybrid ideas pioneered here.