When Is a Columnar Scan Bandwidth-Bound? A Decode-Throughput Law and Its Cross-Hardware Validation Madhulatha Mandarapu∗
Sandeep Kunkunuru†
arXiv:2606.22423v1 [cs.DB] 21 Jun 2026
VaidhyaMegha Private Limited, India https://samyama.ai/ June 2026
Abstract A columnar scan that decompresses, filters, and aggregates should be limited only by memory bandwidth—the roofline floor T ≥ BytesRead/β—yet real kernels are often compute-bound and leave bandwidth idle. We give a predictive answer to when a scan is bandwidth-bound. Across encodings, predicate selectivities, and two different machines, we find that a decoder’s value throughput Tdec (values decoded per second) is essentially independent of the bit-width b: it is set by the decode layout/strategy, not by how many bits each value occupies. Consequently the achieved bandwidth fraction obeys a one-parameter law, f = min 1, Tdec b/(8β) , with the compute-to-bandwidth ridge at b⋆ = 8β/Tdec . Fitting one Tdec per strategy reproduces measured bandwidth fractions with median error 0.027 on x86/AVX2 and 0.003 on a held-out Apple M4/NEON machine, and the ridge b⋆ shifts correctly with each machine’s bandwidth. Inserting FastLanes’ reported decode throughput into the law reproduces its “decode is free at three bits” headline as the large-Tdec limit, unifying our decoder and hand-tuned production code in one curve. We add two crossovers, validated on both machines: branch-free predicate evaluation beats branchy in a mid-selectivity band (the σ(1 − σ) misprediction parabola), and zone-map skipping is clustering-gated rather than selectivity-gated. We release the micro-benchmark, the correctness oracle, and a one-command reproduction. This is a baseline and model, not a faster kernel: our portable C decoders reach ∼ 2 values/cycle, far below hand-tuned SOTA; the law holds because it is parameterized by the measured Tdec .
1
Introduction
Analytical query engines spend much of their time scanning compressed columns. The folklore goal is to make such scans bandwidth-bound: limited by how fast bytes stream from DRAM, not by decode or predicate instructions. The roofline model [Williams et al., 2009] makes this precise—a kernel of operational intensity I (useful work per byte) attains min(π, βI), and is bandwidth-bound iff I is below the ridge π/β. Modern columnar systems [Boncz et al., 2005, Lang et al., 2016, Kuschewski et al., 2023, Afroozeh and Boncz, 2023] push decode below this ridge with SIMD-friendly layouts. But the field lacks a simple, predictive answer to the operational question a practitioner actually asks: given my encoding, my selectivity, and my hardware, what fraction of memory bandwidth will this scan achieve, and at what bit-width does decode stop being free? ∗ †
[email protected] [email protected]
1
The phenomena are individually known. Selectivity-dependent scan throughput and zone-map skipping are measured by Data Blocks [Lang et al., 2016] and, recently and thoroughly, by Zeng et al. [2023]; branch-free vs branchy SIMD scans are studied by Polychroniou and Ross [2015]. What is missing is a closed-form model that ties them to the roofline and transfers across hardware. This paper supplies one. Contributions. • A bandwidth-fraction law (§3). The empirical observation that decode value-throughput Tdec is bit-width-independent yields f = min(1, Tdec b/(8β)) with ridge b⋆ = 8β/Tdec . One parameter per decode strategy. • Cross-hardware validation (§5). Median fit error 0.027 on x86/AVX2 and 0.003 on held-out Apple M4/NEON; the ridge moves correctly with β. The law reproduces FastLanes’ “decode is free” result as its Tdec → ∞ limit. • Two crossovers (§6). The branch-free/branchy mid-selectivity band (predicted within ±1 selectivity decade) and the result that zone-map skipping is clustering-gated, sharpening the “low-selectivity only” folklore. • An open, reproducible harness with a correctness oracle and negative controls; one command regenerates every number. What this is not. We do not beat FastLanes or BtrBlocks. Our portable-C decoders reach ∼ 2 values/cycle, well below FastLanes’ hand-tuned ∼ 40; we model the regime they operate in. The law is parameterized by the measured Tdec , so the science does not depend on matching SOTA absolute speed (§8).
2
Problem and Model
A scan reads a compressed column, decodes each value, evaluates a predicate, and aggregates. Let β be sustainable memory bandwidth (bytes/s) and b the bits per (encoded) value. Reading a column of N values costs BytesRead = N b/8, so the roofline floor is T ≥ N b/(8β) and the achieved bandwidth fraction is BytesRead/T achieved read GB/s = ∈ (0, 1]. (1) f = β β Write Tdec for the decoder’s value throughput (values/s) in the compute-bound regime, i.e. the rate at which the kernel can produce decoded values when bandwidth is not the bottleneck. Then the achieved read bandwidth is Tdec · b/8 bytes/s until it saturates β:
f = min 1,
Tdec b , 8β
b⋆ =
8β (the compute→bandwidth ridge). Tdec
(2)
Equation (2) is the roofline written in scan-native units. Its predictive content is the empirical claim, validated in §5, that Tdec is independent of b: a decoder processes a near-constant number of values per second regardless of how many bits each value takes, so the bytes it pulls—and thus f —grow linearly in b until the ridge b⋆ .
2
3
Method: encodings, kernels, harness
We implement three decode strategies over 32-bit integer columns: (i) scalar row-major bitunpacking (a serial variable-shift extractor; the compute-bound baseline); (ii) a FastLanes-style transposed layout [Afroozeh and Boncz, 2023] that stores 1024-value blocks across 32 lanes so that all lanes share one shift+mask and the inner loop auto-vectorizes; and (iii) byte-aligned widths (b ∈ {8, 16, 32}) that coincide with plain integer arrays. Predicates are equality counts and a materializing select; we also implement RLE and per-block zone maps (min/max skipping). The fused kernels decode, filter, and aggregate in one pass. β is measured per machine as STREAM-Triad [McCalpin, 1995] and an empirical sequentialread maximum (buffers ≫ LLC); we report f against the empirical read maximum (tighter than theoretical peak). A correctness oracle checks encode/decode round-trips for all widths 1−32 in both layouts, scan counts against brute force, and three negative controls (byte-aligned = generic decode; random data ⇒ no zone skipping; sub-LLC throughput > β). All code, seeds, and a one-command reproduction are released.
4
Experimental Setup
Two single-thread hardware points: x86 (Intel Core i9-9980HK, AVX2, DDR4; βscan ≈ 14–16 GB/s) and M4 (Apple M4, NEON, unified memory; βscan ≈ 70, βtriad ≈ 93 GB/s). N = 67,108,864 values, median of 7 repeats, -O3 -march=native. M4 is treated as a held-out generalization point: Apple silicon does not expose reliable turbo control or hard core-pinning, so we use it to test whether the law’s form transfers, not as a precision gate.
5
Results: the law
Figure 1 plots measured f versus b with the law overlaid. For every strategy the measured valuethroughput Tdec is flat across bit-width, and f rises linearly until it plateaus at the ridge b⋆ = 8β/Tdec . Fitting one Tdec per (machine, strategy) gives the parameters in Table 1. machine
strategy
x86 x86 x86 M4 M4 M4
scalar (row-major) FastLanes (transposed) byte-aligned scalar (row-major) FastLanes (transposed) byte-aligned
Tdec (Gval/s)
b⋆ (bits)
median |f − fˆ|
0.27 3.91 5.74 2.06 8.36 9.04
426 29 20 273 67 62
0.0005 0.089 0.040 0.0002 0.022 0.008
Table 1: One Tdec per strategy fits the bandwidth fraction. Overall median |f − fˆ|: 0.027 on x86 (training) and 0.003 on M4 (held-out). The ridge b⋆ moves with the machine: M4’s ∼ 4× bandwidth pushes it from b ≈ 29 to b ≈ 67. Reproducing SOTA as a limit. FastLanes reports ∼ 140 Gval/s scalar-auto-vectorized decode and the headline that 3-bit unpacking already saturates RAM bandwidth (∼ 52 GB/s) [Afroozeh and Boncz, 2023]. Plugging Tdec = 140 into Eq. (2) gives b⋆ ≈ 1 bit and f ≈ 1 even at b = 3—exactly
3
Figure 1: Bandwidth fraction f vs bit-width b (solid = measured, dashed = law min(1, Tdec b/8β)). Left: x86/AVX2. Right: Apple M4/NEON (held-out). Scalar row-major is compute-bound at all real widths; the transposed and byte-aligned strategies cross into bandwidth-bound at b⋆ = 8β/Tdec . their “decode is free” result. The same law that describes our portable decoder (Tdec ≈ 4–9, ridge at b ≈ 20–67) predicts the SOTA regime by changing one number.
6
Results: the two crossovers
Branch (Fig. 2 left). On a decode-free materializing select, branchy evaluation time traces the textbook σ(1 − σ) misprediction parabola (peak at σ = 0.5) while branch-free (predicated) is flat. Branch-free wins in a mid-selectivity band; fitting A + B σ(1 − σ) against the constant predicated cost predicts the band edges within ±1 selectivity decade on both machines (x86: model (0.026, 0.974) vs measured [0.05, 0.90]; M4: (0.008, 0.992) vs [0.001, 0.99]). Caveat: at -O3 the compiler auto-branchlesses a count aggregate, collapsing the distinction—the crossover is real only for data-dependent (materializing / position-list) scans. Clustering (Fig. 2 right). Zone-map skipping is clustering-gated, not selectivity-gated. On a sorted column the scan reads only the block(s) overlapping the predicate value (∼ 1/8192 of bytes here), so skipping wins at every selectivity; on random data zone maps skip nothing (bytes read ≈ full) except at σ below one match per block. This sharpens the common “zone maps help only at low selectivity” [Zeng et al., 2023]: the lever is whether the predicate value is confined to few blocks.
4
Figure 2: Left: branchy select time is the σ(1 − σ) misprediction parabola; predicated is flat (x86). Right: on sorted/clustered data zone maps read a tiny fraction of bytes; on random data they do not (x86).
7
Related Work
Vectorized, bandwidth-aware scans originate with MonetDB/X100 [Boncz et al., 2005]; Data Blocks [Lang et al., 2016], BtrBlocks [Kuschewski et al., 2023], and FastLanes [Afroozeh and Boncz, 2023] push decode toward the roofline with SIMD-friendly encodings. Polychroniou and Ross [2015], Polychroniou et al. [2015] study branch-free SIMD scans; Zeng et al. [2023] empirically vary selectivity, encoding, and zone-map effectiveness; Manegold et al. [2002] model memory-access cost (latency, pre-roofline); Kersten et al. [2018] compare compiled vs vectorized execution qualitatively. Our delta is the closed-form bandwidth-fraction law f = min(1, Tdec b/8β), the ridge b⋆ = 8β/Tdec , its cross-hardware validation, and the reproduction of SOTA as the large-Tdec limit. We claim none of the phenomena—selectivity dependence, the branch crossover, zone-map skipping—only the predictive model that unifies them.
8
Limitations and Honest Negatives
(1) Absolute throughput. Our portable-C decoders reach ∼ 2 values/cycle, ∼ 5% of FastLanes’ hand-tuned ∼ 40; we did not reimplement the full 1024-bit interleaving and instruction scheduling. The law is parameterized by the measured Tdec , so this does not affect the fit, but the absolute ridge b⋆ we report is specific to our decoders (and the law predicts how b⋆ moves for a faster one). (2) Single-thread. We model per-core bandwidth; the many-core shared-controller (aggregate) wall is out of scope. (3) Counting vs materializing. The branch crossover requires a data-dependent kernel; for count aggregates the compiler removes the branch. (4) Integer columns. Strings/nested types (where SOTA decode is hardest) are future work; we expect the law to hold with their Tdec . (5) Measurement. Apple-silicon lacks turbo/pinning control, so M4 is a generalization point, not a precision gate; we report medians.
9
Conclusion
A columnar scan’s bandwidth fraction is captured by one number per decode strategy: its bit-widthindependent value throughput Tdec , via f = min(1, Tdec b/8β) with ridge b⋆ = 8β/Tdec . The law fits
5
across two ISAs, predicts where decode stops being free, and reproduces hand-tuned SOTA as a limit. With the branch and clustering crossovers and an open harness, it gives practitioners a direct answer to “will this scan be bandwidth-bound, and at what bit-width?” Artifact.
Code, data, and one-command reproduction: https://github.com/samyama-ai/bandwidth-bound-sc
References Azim Afroozeh and Peter Boncz. The FastLanes compression layout: Decoding >100 billion integers per second with scalar code. Proceedings of the VLDB Endowment, 16(9):2132–2144, 2023. Peter A. Boncz, Marcin Zukowski, and Niels Nes. MonetDB/X100: Hyper-pipelining query execution. In CIDR, pages 225–237, 2005. Timo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo, and Peter Boncz. Everything you always wanted to know about compiled and vectorized queries but were afraid to ask. Proceedings of the VLDB Endowment, 11(13):2209–2222, 2018. Maximilian Kuschewski, David Sauerwein, Adnan Alhomssi, and Viktor Leis. BtrBlocks: Efficient columnar compression for data lakes. Proceedings of the ACM on Management of Data, 1(2):1–26, 2023. Harald Lang, Tobias Mühlbauer, Florian Funke, Peter A. Boncz, Thomas Neumann, and Alfons Kemper. Data blocks: Hybrid OLTP and OLAP on compressed storage using both vectorization and compilation. In SIGMOD, pages 311–326, 2016. Stefan Manegold, Peter A. Boncz, and Martin L. Kersten. Generic database cost models for hierarchical memory systems. In VLDB, pages 191–202, 2002. John D. McCalpin. Memory bandwidth and machine balance in current high performance computers. IEEE TCCA Newsletter, pages 19–25, 1995. Orestis Polychroniou and Kenneth A. Ross. Efficient lightweight compression alongside fast scans. In DaMoN, pages 1–6, 2015. Orestis Polychroniou, Arun Raghavan, and Kenneth A. Ross. Rethinking SIMD vectorization for in-memory databases. In SIGMOD, pages 1493–1508, 2015. Samuel Williams, Andrew Waterman, and David Patterson. Roofline: an insightful visual performance model for multicore architectures. In Communications of the ACM, volume 52, pages 65–76. ACM, 2009. Xinyu Zeng, Yulong Hui, Jiahong Shen, Andrew Pavlo, Wes McKinney, and Huanchen Zhang. An empirical evaluation of columnar storage formats. Proceedings of the VLDB Endowment, 17(2):148–161, 2023.
6