Search papers, labs, and topics across Lattice.
This paper investigates the conditions under which a columnar scan operation becomes bandwidth-bound, revealing that the decode throughput is primarily determined by the decode layout and strategy rather than the bit-width of the values processed. The authors establish a predictive model that accurately describes the achieved bandwidth fraction across various hardware platforms, achieving a median error of just 0.027 on x86/AVX2 and 0.003 on Apple M4/NEON. Additionally, they validate two key crossovers in performance, demonstrating that branch-free predicate evaluation outperforms branchy methods in specific selectivity ranges and that zone-map skipping is influenced by clustering rather than selectivity.
Decode throughput is independent of bit-width and governed by layout strategy, challenging conventional wisdom about bandwidth limitations in columnar scans.
A columnar scan that decompresses, filters, and aggregates should be limited only by memory bandwidth (the roofline floor T >= BytesRead/beta), 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 very different machines, a decoder's value throughput T_dec (values decoded per second) is essentially independent of bit-width b: it is set by the decode layout/strategy, not by how many bits each value occupies. Hence the achieved bandwidth fraction obeys a one-parameter law, f = min(1, T_dec * b / (8*beta)), with the compute-to-bandwidth ridge at b* = 8*beta/T_dec. Fitting one T_dec 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-T_dec limit, unifying our portable decoder and hand-tuned state of the art in one curve. We add two crossovers, validated on both machines: branch-free predicate evaluation beats branchy in a mid-selectivity band (the sigma(1-sigma) 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 a model, not a faster kernel: our portable C decoders reach ~2 values/cycle, far below hand-tuned SOTA, and the law holds precisely because it is parameterized by the measured T_dec.
