Part 4 of 5 · 2 min read
Bitmap indices for low-cardinality columns
One bit per possible value per row, efficient when only a few distinct values exist.
Bitmap indices for low-cardinality columns
Think of a survey question with only five possible answers. Picture one light switch per possible answer, where exactly one switch per respondent gets flipped on.
In plain words: a bitmap index builds one bit-array per distinct value a column can hold, with one bit per row in that array, set to 1 if that row has that value. This works well for low-cardinality columns, meaning columns with only a small number of distinct possible values, such as a status flag or a boolean. A B+-tree becomes comparatively wasteful here, since its tree structure is built for distinguishing among many distinct values, not a handful.
A worked example. A bitmap index on orders.status, with only three possible values ("placed," "shipped," "delivered"), stores one compact bit-array per status value, each bit marking whether that row currently holds that status.
The key lines.
SELECT * FROM orders WHERE status = 'shipped';
-- a bitmap index on status answers this by reading the 'shipped' bit-array directly
Bitmap index
A bitmap index stores one bit-array per distinct column value, with one bit per row marking whether that row holds that value, well-suited to low-cardinality columns with only a few distinct values.
Example: a row of light switches, one per possible survey answer, with exactly one switch on per respondent, mirrors a bitmap index over that survey column.
Remember this
A Bloom filter answers a membership question cheaply, trading a small, harmless false-positive rate for speed. A bitmap index is a different tool entirely, built for columns with only a handful of distinct values, where a B+-tree would be comparatively wasteful.
Quick notes
- A Bloom filter answers "definitely not present" or "possibly present" for a key, cheaply.
- False positives can happen in a Bloom filter; false negatives cannot, by construction.
- A bitmap index stores one bit-array per distinct column value, one bit per row.
- Bitmap indices suit low-cardinality columns, such as status flags or booleans, better than B+-trees.
- Both structures trade something else away in exchange for being compact and fast for their specific case.