The Zipf ceiling on data-parallel speedup

Simulate a modelNeeds Python with NumPy

Problem

Data parallelism splits rows by key across workers, so a stage finishes when its largest partition does. If the largest partition holds a fraction f of all the work, the speedup can never exceed 1/f, no matter how many cores you buy. This is Amdahl's law with the hot key playing the role of the serial fraction. Key frequencies in real data are roughly Zipfian: a few keys are very common and most are rare. For a Zipf distribution with exponent 1, the top key's share is 1/H_n, where H_n ≈ ln n + 0.577 for n distinct keys.

Turn "the largest partition is your serial fraction" into a number. Generate Zipf-distributed keys, hash them to partitions, and compute the best possible speedup (total work ÷ largest partition).

You will measure, for 1,000 to 1,000,000 distinct keys and 20 million rows, the top key's share, the largest partition's share and the speedup cap they imply. The chart also holds runs for two other Zipf exponents and for 10,000 partitions.

The question. With a million Zipf-distributed keys, what is the best possible speedup, and does adding partitions raise it?

Predict

With a million Zipf keys, going from 1,000 to 10,000 partitions: what happens to the speedup cap?

It rises about tenfoldIt rises a littleIt does not move

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.

zipf-ceiling-on-speedup.py46 linesDownload

View the code

zipf-ceiling-on-speedup.py

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy"]
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""The Zipf ceiling on data-parallel speedup.

Zipf-distributed keys hashed to partitions; the best possible speedup is
total work divided by the largest partition.
"""
import argparse, json
import numpy as np

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--key-counts", type=lambda s: [int(v) for v in s.split(",")], default=[1_000, 10_000, 100_000, 1_000_000],
               help="Distinct keys to try, comma-separated.")
p.add_argument("--rows", type=int, default=20_000_000, help="Rows generated per key count.")
p.add_argument("--parts", type=int, default=1000, help="Partitions the keys are hashed to.")
p.add_argument("--s", type=float, default=1.0, help="Zipf exponent: below 1 is flatter, above 1 is steeper.")
p.add_argument("--seed", type=int, default=1, help="Random seed.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()
rng = np.random.default_rng(args.seed)


def ceiling(n_keys, rows, parts, s):
    w = 1.0 / np.arange(1, n_keys + 1) ** s       # Zipf weights
    w /= w.sum()
    keys = rng.choice(n_keys, size=rows, p=w)
    part = np.bincount(keys % parts, minlength=parts)   # rows per partition
    return {"n_keys": n_keys, "top_key_share_pct": float(w[0] * 100), "one_over_f": float(1 / w[0]),
            "largest_partition_pct": float(part.max() / rows * 100), "speedup_cap": float(rows / part.max())}


rows = []
for n in args.key_counts:
    r = ceiling(n, args.rows, args.parts, args.s)
    rows.append(r)
    print(f"n_keys={n:>10,}  top key share={r['top_key_share_pct']:.3f}%  1/f={r['one_over_f']:.1f}  "
          f"largest partition={r['largest_partition_pct']:.3f}%  speedup cap={r['speedup_cap']:.1f}")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"ceiling": 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 zipf-ceiling-on-speedup.py
uv run zipf-ceiling-on-speedup.py --help     # every knob
```

Knobs
Knob · default	What it changes
--key-counts1000, 10,000, 100,000, 1,000,000	Distinct keys to try, comma-separated.
--rows20,000,000	Rows generated per key count.
--parts1000	Partitions the keys are hashed to.
--s1	Zipf exponent: below 1 is flatter, above 1 is steeper.
--seed1	Random seed.

Our run

Best possible speedup, by number of keysApple M2 · 8 cores · 8 GB

s = 0.7s = 1.0s = 1.3

Partitions

Data table

Best possible speedup, by number of keys
Distinct keys	series	Speedup cap
1K	s = 0.7	23.7
10K	s = 0.7	48.6
100K	s = 0.7	94.6
1M	s = 0.7	175
1K	s = 1.0	7.48
10K	s = 1.0	9.77
100K	s = 1.0	12
1M	s = 1.0	14.3
1K	s = 1.3	3.51
10K	s = 1.3	3.72
100K	s = 1.3	3.82
1M	s = 1.3	3.88

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

Output · uv run zipf-ceiling-on-speedup.py --s 1.0 --parts 1000

n_keys=     1,000  top key share=13.359%  1/f=7.5  largest partition=13.363%  speedup cap=7.5
n_keys=    10,000  top key share=10.217%  1/f=9.8  largest partition=10.239%  speedup cap=9.8
n_keys=   100,000  top key share=8.271%  1/f=12.1  largest partition=8.313%  speedup cap=12.0
n_keys= 1,000,000  top key share=6.948%  1/f=14.4  largest partition=6.995%  speedup cap=14.3

What we found

At a million keys the top key held 6.95% of the rows and the cap was 14.3, as expected. With 10,000 partitions instead of 1,000 it was 14.4: the cap does not move, because the hot key lands in one partition whatever their number. More partitions only remove the small extra imbalance from other keys sharing the hot key's partition.

A flatter distribution (s = 0.7) raised the cap to 175 at a million keys. A steeper one (s = 1.3) held it at 3.88, barely above the 3.51 it had at a thousand keys.

Read it

Repeat with parts=10_000 and see that the cap does not move. Change s to 0.7 and 1.3 to see the boundary conditions: a flatter curve gives a higher ceiling, a steeper one a ceiling that stops growing with the number of keys. Both are precomputed: use the Partitions toggle and compare the three lines.

The largest partition is your serial fraction, and under Zipf-1 it caps speedup near ln(distinct keys). Skew is usually treated as an operational annoyance; here it is a term in the speedup formula. The only way past the cap is to split the hot key itself, which is the next lab.