CSE Roadmap

Specialist tier · about 2 hours · 6 parts

Part 3 of 6 · 2 min read

Compressing a column

Think of bitmap encoding like a seating chart. For each ticket type, a separate chart marks a checkmark in every seat that type occupies. That replaces writing the ticket type next to every seat.

In plain words: A column's values are often highly repetitive, especially one with far fewer distinct values than there are rows, such as a product identifier repeated across many sales. Bitmap encoding turns such a column into one bitmap per distinct value, with a 1 in every row position that holds that value and a 0 everywhere else. When a bitmap is mostly zeros, run-length encoding compresses it further by storing only the lengths of alternating runs of zeros and ones, rather than every individual bit. Because every column's bitmaps share the same row ordering, a query filtering on two columns can combine their bitmaps directly with a bitwise AND, and a query matching several values in one column can combine their bitmaps with a bitwise OR, both very cheap operations.

A worked example. The bookstore's book_id column has far fewer distinct titles than sales rows. A bitmap for book_id = 42 has a 1 in every row where that book was sold and 0 elsewhere; run-length encoding might store that bitmap as "5 zeros, 2 ones, 9 zeros" instead of 16 individual bits.

The key lines. No new SQL; this is a storage encoding, not a query.

book_id = 42 bitmap:        0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0
Run-length encoded:         5, 2, 9

Bitmap encoding, run-length encoding

Bitmap encoding represents a column with n distinct values as n separate bitmaps, one bit per row, with a 1 marking that row's value. Run-length encoding compresses a bitmap, or any repetitive sequence, by storing the lengths of consecutive runs of the same value rather than every individual value.

Example: the book_id = 42 bitmap above run-length-encodes to just three numbers, 5, 2, 9, instead of sixteen separate bits.