Run-Length Encoding

RLE compresses sequences of repeated values:

Original: A A A A B B C C C C C
RLE:      (A,4) (B,2) (C,5)

Storage: 11 bytes → 6 bytes (3 pairs of 2 bytes).

Best when:

• Values cluster (sorted, time-series, low cardinality).
• Long runs.

Useless when values change frequently.

Implementation:

Variants:

• Bit-packed RLE: tiny ints + tiny counts in compact words.
• Run-aware operations: SUM = sum(value * count) without expanding runs.

Modern column stores combine RLE with other encodings:

• DELTA + RLE: store differences, RLE the deltas.
• DICT + RLE: dict-encode strings to ints, RLE the ints.

When data is sorted by primary key + this column has low cardinality, RLE compresses 10-100x.

Decoding cost matters: queries must decode (or operate on encoded form). Skip-decode tricks:

• For point queries: scan run lengths until you reach target index. O(runs) not O(values).
• For aggregates: operate on (value, count) pairs directly.

Example, COUNT WHERE col = X:

• Iterate runs.
• For each (value, count): if value == X, add count to result.
• Never materialize the values array.