Z-order versus sort: count the files touched

Simulate a modelNeeds Python with NumPy

Problem

Sorting a table by one column makes its files' min/max ranges on that column tight, so a filter on it reads almost nothing, and does nothing for any other column. Z-ordering interleaves the bits of several columns, so each file covers a compact box in all of them at once: no column is perfectly clustered, every column is partly clustered. For N files and d columns, a filter on k of them reads about N^(1 − k/d) files.

Simulate 10,000 files over 4 columns. Cluster the rows (a) by sorting on column A and (b) by Z-order on columns A-D (interleave the bits). For each layout, record per-file min/max and count how many files a filter on column A alone must read, then a filter on column D alone. Check how close your counts are to N^(1 − k/d).

The question. How many files does a filter on A, and on D, read under each layout?

Predict

Z-ordered on four columns over 10,000 files, how many files does a filter on A read?

About 1, like a sortAbout 100About 1,000 to 2,000Most of them

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.

z-order-versus-sort-count-the.py46 linesDownload

View the code

z-order-versus-sort-count-the.py

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy"]
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Z-order against sort: count the files.

1 million rows with four uniform columns A–D, clustered into 10,000 files
(a) by sorting on A and (b) by Z-order on A–D (bits interleaved). From each
file's min/max, counts the files a filter on A alone must read, then a filter
on D alone, and compares with N^(1 − k/d).
"""
import argparse, json
import numpy as np

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--files", type=int, default=10_000, help="Files.")
p.add_argument("--rows-per-file", type=int, default=100, help="Rows per file.")
p.add_argument("--queries", type=int, default=50, help="Random point filters per column.")
p.add_argument("--seed", type=int, default=0, 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); n = args.files * args.rows_per_file
cols = rng.integers(0, 2**16, (n, 4)).astype(np.uint64)
def zkey(x):
    z = np.zeros(len(x), dtype=np.uint64)
    for bit in range(16):
        for c in range(4): z |= ((x[:, c] >> np.uint64(bit)) & np.uint64(1)) << np.uint64(bit * 4 + c)
    return z
layouts = {"sort on A": np.argsort(cols[:, 0], kind="stable"), "Z-order on A-D": np.argsort(zkey(cols), kind="stable")}
rows = []
for name, order in layouts.items():
    files = cols[order].reshape(args.files, args.rows_per_file, 4); mn, mx = files.min(axis=1), files.max(axis=1)
    for ci, cname in ((0, "A"), (3, "D")):
        reads = [int(((mn[:, ci] <= v) & (v <= mx[:, ci])).sum()) for v in rng.integers(0, 2**16, args.queries)]
        rows.append({"layout": name, "filter_on": cname, "files_read": float(np.mean(reads)), "files_read_pct": float(np.mean(reads)) / args.files * 100})
summary = {"formula": args.files ** 0.75, "files": args.files}
for r in rows: print(f"{r['layout']:<16} filter on {r['filter_on']}: reads {r['files_read']:8.1f} of {args.files:,} files ({r['files_read_pct']:5.1f}%)")
print(f"N^(1 - 1/4) = {summary['formula']:.0f}")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"summary": summary, "tables": {"filters": 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 z-order-versus-sort-count-the.py
uv run z-order-versus-sort-count-the.py --help     # every knob
```

Knobs
Knob · default	What it changes
--files10,000	Files.
--rows-per-file100	Rows per file.
--queries50	Random point filters per column.
--seed0	Random seed.

Our run

Files read per filter (of 10,000)

Files read per filter (of 10,000)
Layout	Filter on	Files read	Share
sort on A	A	1.16	0.012%
sort on A	D	9,820	98.2%
Z-order on A-D	A	1,710	17.1%
Z-order on A-D	D	1,090	10.9%

Reference runApple M2 · 8 cores · 8 GB

Output · uv run z-order-versus-sort-count-the.py

sort on A        filter on A: reads      1.2 of 10,000 files (  0.0%)
sort on A        filter on D: reads   9817.4 of 10,000 files ( 98.2%)
Z-order on A-D   filter on A: reads   1707.3 of 10,000 files ( 17.1%)
Z-order on A-D   filter on D: reads   1089.7 of 10,000 files ( 10.9%)
N^(1 - 1/4) = 1000

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

What we found

Sorted on A, a filter on A read 1.16 files and a filter on D 9.82K. Z-ordered, a filter on A read 1.71K and on D 1.09K, close to N^0.75 = 1K. The two differ because A's bits sit lowest in each 4-bit group of the interleaving, so the curve clusters it slightly less well than D.

Read it

Z-order is a compromise priced by the formula: a single-column filter reads N^0.75 files instead of N^0 (sorted on it) or N (sorted on something else). It is worth it when filters spread over several columns and none dominates; when one column carries most filters, sort on it.