Encoding by hand: dictionary, RLE and delta

Measure your machineNeeds Python with NumPy

Problem

Columnar encodings exploit what a column's values have in common. Dictionary encoding replaces each value with a small code (⌈log₂ k⌉ bits for k distinct values); run-length encoding stores a value once per run, so it depends on order; delta encoding stores differences, which are small for sorted or slowly changing numbers. General-purpose compression finds some of the same structure without knowing the type.

Take a country column (200 distinct values of 12 bytes, 10 million rows) and a sorted timestamp column. Compute by hand: the number of distinct values k and the bits per value; the size after dictionary encoding against the raw size; the run count after sorting the table by that column (RLE size); and the delta sizes for the timestamp column. Then compress the raw column with gzip and compare.

The question. How much does each encoding save, and what does sorting do to RLE?

Predict

Unsorted, how many runs does RLE find in the 10 million country values (200 distinct)?

About 200, one per valueThousands to a million1 to 5 millionOver 5 million: almost one per row

Run it

1Install uv once. It fetches Python and the lab's packages for you.
Terminal
```
curl -LsSf https://astral.sh/uv/install.sh | sh
```

2Get the script. It is the whole lab: read it, then download it.

encoding-by-hand-dictionary-rle-and.py47 linesDownload

View the code

encoding-by-hand-dictionary-rle-and.py

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy"]
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Encoding by hand: dictionary, RLE and delta.

A 10-million-value country column (200 distinct values, 12 bytes each) and a
sorted timestamp column. Computes the distinct count and bits per value, the
dictionary-encoded size against the raw size, the run count (RLE) before and
after sorting, delta sizes for the timestamps, and gzip of the raw bytes.
"""
import argparse, gzip, json, math
import numpy as np

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--n", type=int, default=10_000_000, help="Values.")
p.add_argument("--distinct", type=int, default=200, help="Distinct countries.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()

rng = np.random.default_rng(0)
names = np.array([f"country-{i:04d}"[:12].ljust(12) for i in range(args.distinct)], dtype="S12")
codes = rng.zipf(1.3, args.n) % args.distinct; col = names[codes]
raw = col.nbytes; k = len(np.unique(col)); bits = math.ceil(math.log2(k))
dict_size = args.n * bits / 8 + k * 12
runs = lambda a: int((a[1:] != a[:-1]).sum()) + 1
r_unsorted, r_sorted = runs(codes), runs(np.sort(codes))
rle_size = lambda r: r * (bits / 8 + 4)                                    # value code + 4-byte run length
ts = np.sort(rng.integers(1_700_000_000_000_000, 1_700_000_000_000_000 + 86_400_000_000, args.n))   # one day of microseconds
deltas = np.diff(ts); dbits = int(deltas.max()).bit_length()
gz = len(gzip.compress(col[:1_000_000].tobytes(), 6)) * (args.n / 1_000_000)
rows = [{"encoding": "raw strings", "mb": raw / 1e6, "ratio": 1.0},
        {"encoding": f"dictionary ({k} values, {bits} bits each)", "mb": dict_size / 1e6, "ratio": raw / dict_size},
        {"encoding": f"RLE, unsorted ({r_unsorted:,} runs)", "mb": rle_size(r_unsorted) / 1e6, "ratio": raw / rle_size(r_unsorted)},
        {"encoding": f"RLE, sorted ({r_sorted:,} runs)", "mb": rle_size(r_sorted) / 1e6, "ratio": raw / rle_size(r_sorted)},
        {"encoding": "gzip of the raw bytes", "mb": gz / 1e6, "ratio": raw / gz}]
ts_rows = [{"encoding": "raw int64 timestamps", "mb": ts.nbytes / 1e6, "ratio": 1.0},
           {"encoding": f"delta, {dbits} bits per value", "mb": args.n * dbits / 8 / 1e6, "ratio": ts.nbytes / (args.n * dbits / 8)}]
summary = {"distinct": k, "bits": bits, "runs_unsorted": r_unsorted, "runs_sorted": r_sorted, "delta_bits": dbits}
for r in rows + ts_rows: print(f"{r['encoding']:<40} {r['mb']:9.2f} MB  ({r['ratio']:7.1f}x)")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"summary": summary, "tables": {"country": rows, "timestamps": ts_rows}}, f)

3Run it in the folder you saved it to, with the defaults first. Then change a knob from the table below and run it again.
Terminal
```
uv run encoding-by-hand-dictionary-rle-and.py
uv run encoding-by-hand-dictionary-rle-and.py --help     # every knob
```

Knobs
Knob · default	What it changes
--n10,000,000	Values.
--distinct200	Distinct countries.

Our run

Country column

Country column
Encoding	MB	Ratio
raw strings	120	1×
dictionary (200 values, 8 bits each)	10	12×
RLE, unsorted (9,136,902 runs)	45.7	2.63×
RLE, sorted (200 runs)	0.001	120,000×
gzip of the raw bytes	12.7	9.47×

Timestamp column

Timestamp column
Encoding	MB	Ratio
raw int64 timestamps	80	1×
delta, 18 bits per value	22.5	3.56×

Reference runApple M2 · 8 cores · 8 GB

Output · uv run encoding-by-hand-dictionary-rle-and.py

raw strings                                 120.00 MB  (    1.0x)
dictionary (200 values, 8 bits each)         10.00 MB  (   12.0x)
RLE, unsorted (9,136,902 runs)               45.68 MB  (    2.6x)
RLE, sorted (200 runs)                        0.00 MB  (120000.0x)
gzip of the raw bytes                        12.67 MB  (    9.5x)
raw int64 timestamps                         80.00 MB  (    1.0x)
delta, 18 bits per value                     22.50 MB  (    3.6x)

macOS 26.6.2 · Python 3.13.3 · numpy 2.5.4 · run 2026-10-25

What we found

The country column had 200 distinct values, so 8 bits per value: dictionary encoding took it from 120 MB to 10 MB (12×), as computed. Unsorted, RLE found 9.14M runs and saved little; sorted by the column, 200 runs, one per value, and the column became almost nothing. gzip of the raw bytes reached 9.47×, less than the dictionary. The sorted timestamps' deltas needed 18 bits each instead of 64: 3.56×.

Read it

Encodings are arithmetic you can do before writing a file: count distinct values, count runs in the intended sort order, look at the size of deltas. They also show why sort order is part of the schema of a columnar table: it decides whether RLE and delta have anything to work with.