Late materialization crossover

Measure your machineNeeds Python with NumPy

Problem

A column engine can apply a filter in two ways. Early materialization copies the matching values out in one sequential pass over the column. Late materialization first builds a list of matching positions and later fetches values from other columns by position: less data moved when few rows match, but each fetch is a scattered read. The cost of the scattered reads grows with the number of positions, so past some selectivity the sequential pass wins. Where that point is depends on the machine.

In Python with NumPy, make a 100-million-element array. For selectivities from 0.001 to 0.9, compare (a) arr[mask] (a sequential pass) with (b) arr[np.flatnonzero(mask)] (build a position list, then gather). Plot time against s.

The question. At what selectivity does the position list stop paying off on this machine?

Predict

On this machine, at what selectivity does the position list clearly lose to the boolean mask?

Below 5%5 to 20%20 to 50%Only near 90%

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.

late-materialization-crossover.py45 linesDownload

View the code

late-materialization-crossover.py

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

A 100-million-element array and a random mask at selectivities 0.01 to 0.9.
Compares (a) arr[mask], a sequential pass over everything, with (b)
arr[np.flatnonzero(mask)], building a position list and gathering from it,
and finds the selectivity where the gather starts to lose.
"""
import argparse, json, time
import numpy as np

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--n", type=int, default=100_000_000, help="Array length.")
p.add_argument("--selectivities", default="0.001,0.01,0.05,0.1,0.2,0.5,0.9", help="Selectivities.")
p.add_argument("--repeats", type=int, default=3, help="Runs per point (best is kept).")
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); arr = rng.random(args.n); u = rng.random(args.n)
def best(fn):
    ts = []
    for _ in range(args.repeats):
        t = time.perf_counter(); fn(); ts.append(time.perf_counter() - t)
    return min(ts) * 1000
rows = []
for s in map(float, args.selectivities.split(",")):
    mask = u < s
    early = best(lambda: arr[mask]); pos = np.flatnonzero(mask)
    late = best(lambda: arr[pos]); late_total = best(lambda: arr[np.flatnonzero(mask)])
    rows.append({"selectivity": s, "mask_ms": early, "gather_ms": late, "positions_plus_gather_ms": late_total})
cross = next((r["selectivity"] for r in rows if r["positions_plus_gather_ms"] > r["mask_ms"]), None)
summary = {"crossover": cross}
for r in rows: print(f"s = {r['selectivity']:<5g}  arr[mask] {r['mask_ms']:7.1f} ms   positions + gather {r['positions_plus_gather_ms']:7.1f} ms   (gather alone {r['gather_ms']:7.1f} ms)")
print(f"positions + gather loses from s = {cross}")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"summary": summary, "tables": {"selectivities": 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 late-materialization-crossover.py
uv run late-materialization-crossover.py --help     # every knob
```

Knobs
Knob · default	What it changes
--n100,000,000	Array length.
--selectivities0.001, 0.01, 0.05, 0.1, 0.2, 0.5, 0.9	Selectivities.
--repeats3	Runs per point (best is kept).
--seed0	Random seed.

Our run

Mask against position listApple M2 · 8 cores · 8 GB

arr[mask]positions + gather

Data table

Mask against position list
Selectivity	arr[mask]	positions + gather
0.001	26.6	20.6
0.01	58.3	34.8
0.05	95.7	95.5
0.1	170	161
0.2	291	83.8
0.5	504	135
0.9	181	202

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

Times (ms)

Times (ms)
s	arr[mask]	Positions + gather	Gather alone
0.001	26.6	20.6	0.385
0.01	58.3	34.8	5.23
0.05	95.7	95.5	13.9
0.1	170	161	15.1
0.2	291	83.8	17.8
0.5	504	135	47.8
0.9	181	202	65.2

Output · uv run late-materialization-crossover.py

s = 0.001  arr[mask]    26.6 ms   positions + gather    20.6 ms   (gather alone     0.4 ms)
s = 0.01   arr[mask]    58.3 ms   positions + gather    34.8 ms   (gather alone     5.2 ms)
s = 0.05   arr[mask]    95.7 ms   positions + gather    95.5 ms   (gather alone    13.9 ms)
s = 0.1    arr[mask]   169.8 ms   positions + gather   160.9 ms   (gather alone    15.1 ms)
s = 0.2    arr[mask]   291.4 ms   positions + gather    83.8 ms   (gather alone    17.8 ms)
s = 0.5    arr[mask]   504.0 ms   positions + gather   135.0 ms   (gather alone    47.8 ms)
s = 0.9    arr[mask]   181.0 ms   positions + gather   202.1 ms   (gather alone    65.2 ms)
positions + gather loses from s = 0.9

What we found

The position list won at low selectivity (34.8 against 58.3 ms at s = 0.01) and, surprisingly, again in the middle (135 against 504 ms at s = 0.5); it lost clearly only at s = 0.9. The boolean mask was slowest at 50%, the selectivity at which its per-element branch is least predictable, and recovered at 90%. So on this machine there is no single crossover: the mask's cost is not proportional to the work, because branch prediction, not memory, dominates it in the middle.

Read it

The textbook picture (gather wins when few rows match, a sequential pass wins when many do) holds at the ends. Between them, implementation details decide, and they differ by engine and CPU. That is the point of measuring your own crossover instead of carrying someone else's threshold.