One outlier sets the width

Measure your machineNeeds Python with NumPy

Problem

Frame-of-reference bit packing stores a block of integers as offsets from the block's minimum, each in just enough bits for the largest offset. The width is a property of the whole block, so a single outlier widens every value in it. Patched frame of reference (PFOR) keeps the width that fits most values and stores the few that do not fit as exceptions: a position and the full value, in a separate patch list.

Compute by hand what an outlier costs, and what a patch list returns. The block is 128 values in a range of 256; the outlier is 2³¹.

The question. How many bits does the block take with no outlier, with one, and with PFOR?

Predict

One outlier in a block of 128 eight-bit values: how many times more bits does the block take?

Barely more1.5 to 3×3 to 5×More than 5×

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.

one-outlier-sets-the-width.py35 linesDownload

View the code

one-outlier-sets-the-width.py

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy"]
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""One outlier sets the width.

Frame-of-reference bit packing of a 128-value block: the width is set by
max - min. Without an outlier, with one, and with the outlier moved to a
patch list (PFOR).
"""
import argparse, json
import numpy as np

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--block", type=int, default=128, help="Values per block.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()
rng = np.random.default_rng(0)
block = rng.integers(1_000_000, 1_000_256, args.block)
bits = lambda x: int(x).bit_length()
w_plain = bits(block.max() - block.min())
block2 = block.copy(); block2[17] = 2**31
w_out = bits(block2.max() - block2.min())
pos_bits = bits(args.block - 1)
rows = [{"encoding": "no outlier", "bits": args.block * w_plain, "width": w_plain},
        {"encoding": "one outlier", "bits": args.block * w_out, "width": w_out},
        {"encoding": "PFOR: width 8 + one patch", "bits": args.block * w_plain + pos_bits + 32, "width": w_plain}]
for r in rows: print(f"{r['encoding']:<28} width {r['width']:2d} bits   {r['bits']:,} bits per block")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"encodings": rows, "summary": [{"outlier_x": rows[1]["bits"] / rows[0]["bits"], "pfor_x": rows[2]["bits"] / rows[0]["bits"]}]}}, 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 one-outlier-sets-the-width.py
uv run one-outlier-sets-the-width.py --help     # every knob
```

Knobs
Knob · default	What it changes
--block128	Values per block.

Our run

One block of 128 values

One block of 128 values
Encoding	Width (bits)	Bits per block
no outlier	8	1.02K
one outlier	31	3.97K
PFOR: width 8 + one patch	8	1.06K

Reference runApple M2 · 8 cores · 8 GB

Output · uv run one-outlier-sets-the-width.py

no outlier                   width  8 bits   1,024 bits per block
one outlier                  width 31 bits   3,968 bits per block
PFOR: width 8 + one patch    width  8 bits   1,063 bits per block

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

What we found

Exactly as computed: 1.02K bits without the outlier, 3.97K with it (3.88× worse), and 1.06K with PFOR, within 1.04× of the clean block.

Read it

One value in 128 sets the width of all 128 values, and a patch list gives almost all of it back. The same pattern recurs across encodings: any scheme that chooses one parameter per block (width, dictionary, delta base) is set by its worst value, and an exception path keeps the rare value from setting the cost of the common ones.