A Bit Per Row Per Value
A bitmap index represents each distinct value of a column as a bit array, one bit per row. The bit is set when that row has that value. A column with three values like a small status set becomes three bitmaps, each as long as the table.
Why It Is Powerful
Combining filters becomes bitwise math:
- Filtering on value A and value B is a bitwise AND of their bitmaps.
- Filtering on A or B is a bitwise OR.
- The result bitmap marks exactly the matching rows.
This makes ad hoc queries that combine many conditions, common in analytics and data warehouses, extremely fast, since AND and OR over bitmaps are cheap and the bitmaps compress well.
The Cardinality Catch
Bitmap indexes shine on low cardinality columns, those with few distinct values like gender, status, or country. On high cardinality columns like a unique id, you would create millions of sparse bitmaps, wasting space. They also suit read heavy stores, because updating many bitmaps on each write is costly, which is why they are rare in busy transactional systems.
Key idea
A bitmap index stores one bit array per distinct value, so combining filters is fast bitwise AND and OR, ideal for low cardinality columns in read heavy analytics but poor for high cardinality or write heavy workloads.