CSE Roadmap

Specialist tier · about 2 hours · 5 parts

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.