Bitmap Index Low-Level Design: Bit Vectors, Compression, Multi-Column Queries, and Cardinality Trade-offs

What Is a Bitmap Index?

A bitmap index represents the presence or absence of a column value for each row using a bit vector: a sequence of bits, one per row in the table, where bit i is 1 if row i has the indexed value and 0 otherwise. One bit vector is stored per distinct value of the indexed column. For a table with 10 million rows and a “status” column with 4 distinct values (active, inactive, pending, deleted), the bitmap index consists of 4 bit vectors, each 10 million bits (1.25 MB) long.

Bitmap indexes shine in OLAP workloads where queries filter on multiple low-cardinality columns simultaneously — the exact pattern that makes B-tree indexes expensive.

Equality and Range Queries

Equality query (status = 'active'): fetch the bitmap for value “active”, iterate set bits to get the matching row IDs. This is a single bitmap lookup and a bit scan — extremely fast.

Range query (age BETWEEN 30 AND 40): fetch bitmaps for values 30, 31, …, 40 and bitwise-OR them together. The result is a single bitmap of rows where age is in [30, 40]. For a column with 100 distinct values, this requires ORing 11 bitmaps — still faster than a B-tree range scan that must traverse index pages and follow heap pointers.

Multi-Column AND with Bitwise Logic

This is where bitmap indexes truly excel. A query like:

SELECT * FROM orders WHERE status = 'shipped' AND country = 'US' AND product_type = 'electronics'

With a bitmap index on each column, the engine:

1. Fetches the “shipped” bitmap
2. Fetches the “US” bitmap
3. Fetches the “electronics” bitmap
4. Bitwise-ANDs all three bitmaps
5. Iterates set bits in the result to get matching row IDs

Each AND operation processes 64 bits at a time using a single CPU instruction. For 10 million rows, that's ~156,250 64-bit AND operations — a few microseconds of CPU time. No B-tree page traversal, no random I/O for index lookups, no row-by-row comparison.

WAH Compression

Uncompressed bitmap indexes for low-cardinality columns are sparse: most bits are 0. Run-length encoding exploits this sparsity. WAH (Word-Aligned Hybrid) compresses bitmaps using 32-bit or 64-bit words:

• Literal word — a word with the high bit = 0, storing 31 bits of raw bitmap data
• Fill word — a word with the high bit = 1; the next bit indicates fill value (all 0s or all 1s), and the remaining 30 bits encode the run length in words

The key property of WAH: bitwise AND, OR, and NOT can be computed directly on compressed words without decompression. Fill words of the same type can be combined by adding run lengths; literal words are AND/OR'd directly. This gives the same result as decompressing and operating on raw bitmaps, at a fraction of the I/O cost.

Real-world compression ratios for low-cardinality columns range from 10× to 100×. Oracle's bitmap index compression uses a similar scheme; Apache Druid uses Roaring Bitmaps (a more modern variant with better performance on dense bitmaps).

Cardinality and When to Use Bitmap Indexes

Bitmap indexes are optimal for low-cardinality columns — columns with a small number of distinct values relative to the number of rows. “Low” is typically defined as fewer than 1000 distinct values, but the practical threshold depends on workload.

For high-cardinality columns (e.g., user_id, email, phone number), a bitmap index would have one bit vector per distinct value — for 10 million unique users, that's 10 million bitmaps, each with only a single bit set. The overhead is enormous. Use a B-tree for high-cardinality equality lookups and hash indexes for exact equality on primary keys.

Columnar databases like Apache Druid, ClickHouse, and Redshift use bitmap indexes pervasively because their workloads are predominantly OLAP queries with multi-column low-cardinality filters.

Update Overhead and Concurrency

When a row is inserted, the bit at its row position must be set in the bitmap for each of its column values. When a row is deleted, the corresponding bits must be cleared across all bitmaps. When a column value is updated (status changes from “pending” to “active”), one bit is cleared in the “pending” bitmap and set in the “active” bitmap.

Bitmap index updates are expensive under concurrent write workloads because multiple transactions may attempt to modify the same compressed WAH word simultaneously, requiring locking at the word or page level. This is why bitmap indexes are generally avoided in OLTP systems with high write concurrency and preferred in read-heavy OLAP or data warehouse environments where updates are batched.

SQL Data Model

-- Bitmap index storage (one row per distinct column value)
CREATE TABLE BitmapIndex (
    id              BIGSERIAL PRIMARY KEY,
    table_name      VARCHAR(255) NOT NULL,
    column_name     VARCHAR(255) NOT NULL,
    value           TEXT NOT NULL,              -- the indexed column value
    bitmap          BYTEA NOT NULL,             -- WAH-compressed bit vector
    set_bit_count   BIGINT NOT NULL,            -- number of matching rows
    updated_at      TIMESTAMPTZ NOT NULL DEFAULT now(),
    UNIQUE (table_name, column_name, value)
);

-- Bitmap index statistics and metadata
CREATE TABLE BitmapIndexStats (
    index_id            BIGINT PRIMARY KEY REFERENCES BitmapIndex(id),
    cardinality         INT NOT NULL,           -- number of distinct values for this column
    compression_ratio   NUMERIC(8,2) NOT NULL,  -- uncompressed / compressed size
    last_rebuilt_at     TIMESTAMPTZ NOT NULL DEFAULT now()
);

CREATE INDEX idx_bitmapindex_table_col ON BitmapIndex(table_name, column_name);

Python Implementation Sketch

from __future__ import annotations
import array, math
from typing import Iterator

class BitmapIndex:
    """Simple bitmap index for a single low-cardinality column."""

    def __init__(self):
        self._bitmaps: dict[str, bytearray] = {}
        self._row_count = 0

    def build(self, column_values: list) -> None:
        """Build bitmap index from a list of column values (one per row)."""
        self._row_count = len(column_values)
        n_bytes = math.ceil(self._row_count / 8)
        # Initialize bitmaps for all distinct values
        distinct = set(column_values)
        self._bitmaps = {str(v): bytearray(n_bytes) for v in distinct}
        for row_id, value in enumerate(column_values):
            key = str(value)
            byte_idx = row_id // 8
            bit_idx = row_id % 8
            self._bitmaps[key][byte_idx] |= (1 < list[int]:
        """Return sorted list of row IDs where column equals value."""
        bm = self._bitmaps.get(str(value))
        if bm is None:
            return []
        return list(self._iter_set_bits(bm))

    def query_range(self, low, high) -> list[int]:
        """Return row IDs where low <= value <= high (for numeric columns)."""
        result_bm = bytearray(len(next(iter(self._bitmaps.values()), bytearray())))
        for value_str, bm in self._bitmaps.items():
            try:
                v = float(value_str)
                if low <= v  list[int]:
        """AND two bitmap indexes: find rows matching both column values."""
        # In practice: AND specific bitmaps, not entire indexes
        return []

    def bitwise_or(self, bm_a: bytearray, bm_b: bytearray) -> bytearray:
        result = bytearray(max(len(bm_a), len(bm_b)))
        for i in range(len(bm_a)):
            result[i] = bm_a[i] | (bm_b[i] if i  bytearray:
        result = bytearray(min(len(bm_a), len(bm_b)))
        for i in range(len(result)):
            result[i] = bm_a[i] & bm_b[i]
        return result

    def multi_column_and(self, filters: dict[str, "BitmapIndex"]) -> list[int]:
        """AND filters across multiple columns. filters = {value: BitmapIndex}."""
        bitmaps = [bi._bitmaps.get(v, bytearray()) for v, bi in filters.items()]
        if not bitmaps or not all(bitmaps):
            return []
        result = bitmaps[0]
        for bm in bitmaps[1:]:
            result = self.bitwise_and_bm(result, bm)
        return list(self._iter_set_bits(result))

    def compress_wah(self, bitmap: bytearray) -> bytearray:
        """Compress a bitmap using simplified WAH (Word-Aligned Hybrid) encoding."""
        compressed = bytearray()
        i = 0
        while i < len(bitmap):
            word = bitmap[i]
            if word == 0x00 or word == 0xFF:
                # Count run length
                fill_byte = word
                run_len = 1
                while i + run_len < len(bitmap) and bitmap[i + run_len] == fill_byte:
                    run_len += 1
                fill_bit = 1 if fill_byte == 0xFF else 0
                # Encode as: [fill=1][fill_value][run_length in 6 bits]
                header = 0x80 | (fill_bit < Iterator[int]:
        for byte_idx, byte in enumerate(bitmap):
            if byte == 0:
                continue
            for bit_idx in range(8):
                if byte & (1 << bit_idx):
                    yield byte_idx * 8 + bit_idx

Frequently Asked Questions

{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “At what cardinality threshold should I choose a bitmap index over a B-tree?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The traditional rule of thumb is to use bitmap indexes for columns with fewer than 100-1000 distinct values (low cardinality) and B-trees for higher cardinality. The real threshold depends on query patterns and workload. Bitmap indexes are superior when queries combine multiple low-cardinality predicates (multi-column AND/OR), because the bitwise operations are far cheaper than B-tree index intersection. If queries access one column in isolation with high selectivity, a B-tree is faster. Columnar databases like Druid and Redshift use bitmap indexes up to much higher cardinalities because their scan-oriented execution benefits from bitmap operations more than OLTP row-oriented engines.”
}
},
{
“@type”: “Question”,
“name”: “What is the compression ratio achievable with WAH?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “WAH compression ratio depends on column cardinality and data distribution. For a column with 4 distinct values in a table of 10 million rows, each bitmap has on average 2.5 million set bits and 7.5 million zero bits. Runs of zeros compress to a few WAH fill words each. Typical WAH compression ratios for low-cardinality columns range from 10x to 100x. The Roaring Bitmap format (used in Apache Druid) achieves better ratios on mixed-density bitmaps by using three internal container types: array (for sparse), bitset (for dense), and run-length-encoded containers.”
}
},
{
“@type”: “Question”,
“name”: “How efficient are multi-column bitmap AND/OR queries?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Multi-column bitmap AND/OR operations process 64 bits per CPU instruction (using 64-bit integer AND/OR). For a table with 10 million rows, each bitmap is ~1.25 MB uncompressed. ANDing two bitmaps requires ~156,000 64-bit AND operations, which takes microseconds on modern CPUs. This is dramatically faster than a B-tree index intersection that must merge sorted posting lists with random I/O. On compressed (WAH) bitmaps, the operation is even faster because runs of zeros are processed in a single instruction that skips millions of rows.”
}
},
{
“@type”: “Question”,
“name”: “Why is update overhead high for bitmap indexes in OLTP?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Every INSERT requires setting bits in bitmaps for each indexed column. Every DELETE requires clearing bits. Every UPDATE that changes a column value requires clearing one bit and setting another. On compressed bitmaps, inserting or modifying a bit in the middle of a run requires decompressing the affected section, modifying it, and recompressing — potentially touching many compressed words. Under concurrent writes, multiple transactions may contend on the same bitmap page or word, requiring fine-grained locking. Oracle addresses this with bitmap index locking at the key value level, but contention on popular values remains a bottleneck. For OLTP, B-trees have much better update throughput.”
}
}
]
}

{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “Why are bitmap indexes best suited for low-cardinality columns?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “A bitmap index creates one bit vector per distinct value; low-cardinality columns (e.g., status with 3 values) create only 3 bit vectors; high-cardinality columns (e.g., user_id with millions of values) create millions of bit vectors, each nearly all-zeros, wasting storage.”
}
},
{
“@type”: “Question”,
“name”: “How does WAH compression work for bitmap indexes?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “WAH divides the bit vector into 32-bit words; a sequence of identical words is encoded as a run-length fill word (type bit + count); non-repeating words are stored as verbatim literal words; bitwise AND/OR operations can be performed on compressed WAH representations without full decompression.”
}
},
{
“@type”: “Question”,
“name”: “How does a multi-column bitmap AND query work?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Each column's bitmap for the queried value is fetched separately; the bitmaps are ANDed together bitwise; set bits in the result correspond to row IDs satisfying all column conditions simultaneously, avoiding row-by-row predicate evaluation.”
}
},
{
“@type”: “Question”,
“name”: “How are bitmap indexes updated on INSERT?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “For each indexed column, the new row's value determines which bitmap to update; a single bit at the new row's position is set to 1 in that bitmap; this is fast for batch inserts but can be slow for frequent single-row inserts due to bitmap reconstruction.”
}
}
]
}

See also: Meta Interview Guide 2026: Facebook, Instagram, WhatsApp Engineering

See also: Netflix Interview Guide 2026: Streaming Architecture, Recommendation Systems, and Engineering Excellence

See also: Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture