Bitmap Index Encoding
A bitmap index stores one bit per row per distinct value, making equality predicates on low-cardinality columns a bitwise AND that is faster than a B-tree lookup and compresses well.
Definition
A bitmap index represents each distinct value of a column as a bitmap where bit i is set if row i has that value, so that an equality predicate is a bitmap lookup and a compound predicate is a bitwise AND of bitmaps, making it extremely fast for low-cardinality, read-heavy, ad-hoc query workloads.
Context and scope
Applied in analytical databases, data warehouse fact tables on gender, status, and flag columns, and any read-heavy store with low-cardinality predicates.
Common misconceptions
- Bitmap indexes are always smaller than B-trees — for high-cardinality columns the bitmap per value is sparse and huge; they win on low cardinality
- Bitmap indexes do not support updates — they support updates; the cost is that an update touches the bitmap and the compression, making them read-heavy
Anti-patterns
- Building a bitmap index on a high-cardinality column and watching storage explode
- Updating a compressed bitmap index in an OLTP workload and paying the decompress-modify-recompress cost per write
Related concepts
Authoritative source
What it is
A bitmap index represents each distinct value of a column as a bitmap where bit i is set if row i has that value, so that an equality predicate is a bitmap lookup and a compound predicate is a bitwise AND of bitmaps, making it extremely fast for low-cardinality, read-heavy, ad-hoc query workloads. Applied in analytical databases, data warehouse fact tables on gender, status, and flag columns, and any read-heavy store with low-cardinality predicates. The data model and the access patterns are co-designed: a schema that is correct in the relational sense can be catastrophic for the queries the workload actually issues.
How it works
Indexing decisions follow the query shapes, not the column importance: a covering index turns a table scan into an index-only scan, but every index adds write amplification and storage cost. Partitioning aligns with the access dimension so a query touches one partition, not all. Transaction scope is minimized to hold locks briefly; long transactions are the root of contention and deadlock.
When to apply and pitfalls
Apply when data volume or query latency has a concrete business cost. The common pitfall is indexing for the current workload and ignoring the access patterns that growth will introduce — the index that helps today can serialize writes tomorrow. Another is treating the database as a black box, missing that the optimizer’s plan choice depends on statistics that drift as data changes.