# DDIA Ch. 4: sorting rows changes how big they are

## Concept

A column store keeps each column's values together, and analytic columns tend
to have few distinct values. Like values sitting adjacent compress extremely
well — so the same fact table is far smaller column-oriented than row-oriented.
Then the twist: because a column store may keep rows in *any* order, **sorting
the table** turns the sort columns into long runs, and run-length encoding
shrinks them to almost nothing. You will reorder the exact same 10 million rows
— not change a single value — and watch the file get **1.4× smaller**, with one
column collapsing **30×**.

## Provenance

*Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini,
2025), Chapter 4 — *Storage and Retrieval*, §"Column compression" and §"Sort
order in column storage":

> Often the number of distinct values in a column is small compared to the
> number of rows (for example … billions of sales transactions, but only
> 100,000 distinct products).

The book explains bitmap/run-length encoding on low-cardinality columns, and
that a column store can impose a sort order "as we did with SSTables." Here you
measure both: the compression, and how much a chosen sort order adds.

## Prerequisites

The surprise is about redundancy and adjacency. These help; each line notes
where it shows up.

1. **Column-major layout** — each column's values are stored contiguously, so a
   compressor sees a long run of same-typed, often-repeating values (unlike a
   row store, where a column's values are scattered one-per-row).
2. **Cardinality** — the number of *distinct* values in a column. Low
   cardinality (731 dates, 200 stores) is what makes a column compressible.
3. **Run-length & dictionary/bitmap encoding** — "value V repeated 40,000
   times" stored as a count, not 40,000 copies; a small dictionary of distinct
   values plus compact codes. These are the encodings that exploit #1 and #2.
4. **Sort order as a lever** — a column store can store rows in any order.
   Sorting by a column groups its equal values into runs, which is what turns
   run-length encoding from "helpful" into "nearly free." Rows must be sorted
   *whole* (all columns together) so the k-th entry of every column still
   belongs to the same row.

### Where to learn them

- **RLE / bitmap / dictionary encoding (#2–#3):** DDIA §"Column compression"
  (Figure 4-8, bitmap encoding) is the clearest short version; the Apache
  Parquet "Encodings" docs list RLE/dictionary as used here.
- **Sort order (#4):** DDIA §"Sort order in column storage," and the
  "C-Store / Vertica" idea of storing multiple sort orders (projections).

If only one is new, make it #3 — run-length encoding is why sorting pays off.

## Environment

Deterministic data, so every size below reproduces exactly:

- macOS 26.5.2 (Darwin 25.5.0), arm64
- DuckDB 1.5.5 on Python 3.12.13 (run via `uv`); `sqlite3` from the standard
  library as the row-store baseline — no Docker
- One synthetic fact table, 10,000,000 rows × 5 low-cardinality columns

## Mental model

The fact table has five columns, all low-cardinality:

| column | distinct values |
| --- | --- |
| `date_key` | 731 (two years) |
| `product_sk` | 5,000 (scattered) |
| `store_sk` | 200 |
| `promotion_sk` | ~40, but mostly 0 |
| `quantity` | 10 |

We write it three ways and compare sizes: a **row store** (SQLite, no
compression), a **column store** (Parquet), and the **same column store with
the rows sorted** by `(date_key, store_sk, product_sk)`. Sorting changes no
values — only the order rows are stored in. The whole exercise is one script,
`code/column_compression.py`.

## Setup

```
cd study/ddia/ch04/code
uv run --with duckdb python3 column_compression.py     # ~20 s: builds 10M rows, writes 3 files
```

Do **not** read the output yet — make each prediction first.

## Steps

### Step 1 — column vs row size (calibration)

**Predict.** Same 10M-row table, no schema change. Roughly how much smaller is
the column-oriented (Parquet) file than the uncompressed row store (SQLite)?

**Do.** Run the script; read the size block.

**Observe.**

```
same data, three ways on disk:
    row store    SQLite (uncompressed) =   190.4 MB
    column store Parquet (unsorted)    =    34.4 MB   (5.5x smaller than the row store)
    column store Parquet (sorted)      =    24.3 MB   (1.4x smaller again -- same data, just reordered)
```

**5.5×** smaller as a column store, before any sorting — because each column is a
run of same-typed, low-cardinality values that dictionary/run-length encoding
loves. Note the third line for the next step: sorting made it smaller *again*.

### Step 2 — sorting the rows shrinks the file (the surprise)

**Predict.** The sorted file (24.3 MB) is smaller than the unsorted one
(34.4 MB) — but it is the *exact same 10 million rows with the exact same
values*, only in a different order. How can reordering rows change the file
size? And which columns get smaller? (Most people expect row order to have no
effect on size at all.)

**Do.** Read the per-column block.

**Observe.**

```
per-column compressed size, unsorted -> sorted by (date_key, store_sk, product_sk):
    column           unsorted      sorted   effect of sorting
    date_key          0.66 MB     0.01 MB   59x smaller
    store_sk          9.75 MB     0.32 MB   30x smaller
    product_sk       17.20 MB    17.20 MB   ~unchanged
    promotion_sk      1.74 MB     1.74 MB   ~unchanged
    quantity          4.24 MB     4.24 MB   ~unchanged
```

The whole 10 MB the file shed came from **two columns**. Sorting by `date_key`
first turns it into 731 long runs — run-length encoding crushes it **59×**, to
essentially nothing (0.01 MB). Within each date, sorting by `store_sk` groups
its 200 values into runs too: **30× smaller**. `product_sk` — the last, finest
sort key — is still scattered inside each little group, so it barely changes;
`promotion_sk` and `quantity` weren't sorted on at all, so they don't move.

### Step 3 — why only those columns

**Predict.** You sorted by three columns but only two shrank. Why does
`product_sk` (also a sort key) stay 17.2 MB?

**Observe.** Sorting produces runs only where values actually repeat
*consecutively*. `date_key` and `store_sk` are the leading sort keys, so their
equal values land in long contiguous blocks. `product_sk` is the *tie-breaker*:
within a single (date, store) group there are few rows and 5,000 possible
products, so consecutive `product_sk` values rarely repeat — no runs, no RLE
win. The compression benefit of a sort order lands almost entirely on its
**leading** columns.

## What you should see

- Column store is **~5.5×** smaller than the uncompressed row store (same data).
- Sorting the rows makes it **~1.4× smaller again** — same values, just
  reordered.
- The savings are concentrated in the leading sort columns: `date_key` **~59×**,
  `store_sk` **~30×**; the trailing/​unsorted columns barely move.

## Why

Compression feeds on redundancy that sits close together. A column store already
wins because a column is a long, uniform run of same-typed values — and when the
cardinality is low (731 dates among 10M rows), dictionary and run-length
encoding replace millions of repeats with a handful of codes and counts. That is
the 5.5× in Step 1, and why `date_key` was already tiny (0.66 MB) even unsorted.

Sorting adds a second, larger win, and it is purely about *adjacency*.
Run-length encoding stores "value V, ×N" only when V's copies are consecutive.
Unsorted, a column's equal values are sprinkled throughout the file; sorting the
table gathers them into long contiguous runs. Sort by `date_key` and the column
becomes 731 runs — 0.01 MB. Sort by `store_sk` next and, *within* each date, its
200 values form runs too — 30× smaller. Crucially, the rows are sorted **as
whole rows**: you cannot sort each column independently or the k-th entries
would no longer belong to the same row. So one physical sort order is imposed on
the whole table, and its benefit falls on the leading columns; the tie-breaker
`product_sk` still has no local repetition and does not compress.

**The boundary — you get one sort order, so choose it.** Sorting helps the
columns you sort by (and any column correlated with them), and only the leading
ones dramatically. A high-cardinality, uncorrelated column like `product_sk`
won't compress no matter where you put it in the sort. And a table has a single
physical order per copy — you're spending it. That is both a compression lever
and an indexing decision: the same sort that shrinks `date_key` to nothing also
lets a "last month" query scan a contiguous block (the SSTable-style ordering
the book points back to). Systems like Vertica store several sort orders as
separate *projections* precisely because one order can't be optimal for
everything.

### Go deeper

1. **Change the sort key.** Sort by `(store_sk, date_key, product_sk)` instead
   and re-run. Predict which column now collapses most (the new leading key) and
   whether the total shrinks more or less than sorting by `date_key` first.
2. **Raise the cardinality.** Make `product_sk` range over 5,000,000 values
   instead of 5,000. Predict what happens to the unsorted column size and to the
   total — and why sorting still can't save it.
3. **Bitmap-encode a query.** `promotion_sk` is mostly 0. Predict how a bitmap
   index on it (one bit per row per distinct value) would size, and how
   `WHERE promotion_sk = 7` could then be answered by ANDing bitmaps — the
   Figure 4-8 technique.