Bitmap Index
A bitmap index stores one bit vector per distinct value, enabling instant AND and OR combinations of low-cardinality predicates at the cost of terrible write concurrency.
Definition
A bitmap index represents each distinct value of a column as a bit vector over all rows. Query predicates become bitwise operations whose cost scales with row count divided by word size, independent of selectivity. Fast combines of many low-cardinality filters make it an analytics classic; a single row update locks or rewrites whole bitmap extents.
Context and scope
Used in analytical engines and data warehouses for status, category, and flag columns. In query engines without persistent bitmap indexes, bitmap scans build them on the fly from B-tree results.
Common misconceptions
- Bitmap indexes suit any column — they shine on low-cardinality columns; high cardinality explodes vector count and storage
- Bitmaps only help equality — range predicates decompose into OR-ed bitmaps and remain fast, unlike B-tree range scans
- OLTP databases should adopt them — concurrent row updates serialize on bitmap extents, which is fatal for transactional workloads
Anti-patterns
- Deploying bitmap indexes on transactional tables with frequent updates and suffering lock storms
- Building bitmap indexes on near-unique columns and storing more metadata than data
- Ignoring compression — plain bitmaps are sparse; encoded variants such as Roaring are the practical form
Related concepts
Related examples
Authoritative source
What it is
Instead of mapping values to row locations, each value owns a bit per row: set means the row has that value. Combining filters is bitwise AND or OR over vectors, which CPUs do on thousands of rows per instruction. That is why many-flag filters compose almost for free.
How it works
Each predicate evaluates to a bitmap; intersections and unions collapse the filters before a single fetch of surviving rows. Compression formats such as Roaring chunk dense and sparse regions to keep vectors small. Writes, however, invalidate extents of bits, so engines either lock ranges or rebuild pieces, making updates expensive.
When to use it
Read-mostly analytical schemas with status, segment, and boolean columns that always filter together. PostgreSQL offers the on-the-fly variant: bitmap AND and OR scan nodes built from B-tree index results.
Pitfalls
Cardinality is the budget: distinct values near row count produce a vector per row, worse than a scan. Update-heavy tables are the anti-case. Freshly updated rows may fall out of on-the-fly bitmap scans until visibility maps settle.