bitunpack extracts one bit at a time; the win scales with bit width, up to ~14% where unpacking dominates

[ChronicallyJD]

bitunpack extracts values one bit at a time. It is the largest single frame in a CPU profile of both scan shapes, and a word-at-a-time rewrite is byte-identical and dramatically cheaper in isolation.

Found by profiling with bench/run_profile.sh (#499).

The measurement

Self time, cpu-clock with DWARF unwinding, 8M rows, PG 18.4, serial:

shape	bitunpack	PgColumnarDecodeChunk
filtered aggregate over a skippable range	21.0%	4.2%
row-returning projection	19.2%	7.4%

The decode machinery around it is 4 to 7%. The time is in the inner unpacking loop.

Why

src/columnar_encoding.c:168. The inner loop runs once per bit, and each iteration does a byte load, two shifts, a mask, a test and an or:

for (i = 0; i < n; i++)
{
    uint64  v = 0;
    int     b;

    COLUMNAR_DECODE_INTERRUPT(i);
    for (b = 0; b < width; b++)
    {
        if ((in[(bitpos + b) >> 3] >> ((bitpos + b) & 7)) & 1)
            v |= (uint64) 1 << b;
    }
    out[i] = v;
    bitpos += width;
}

So cost scales with n * width. A 32-bit-wide column pays 32 dependent operations per value to reconstruct something a single shifted load could produce.

The alternative, measured

One unaligned 64-bit load, one shift, one mask, per value:

uint64  w;
memcpy(&w, in + (bitpos >> 3), 8);
out[i] = (w >> (bitpos & 7)) & mask;

1,000,000 values per run, mean of five, gcc -O2. Every value compared against the current implementation on random input before timing, because a faster wrong answer is not a result:

width	current	word-at-a-time	speedup	identical
1	3.7 ms	0.6 ms	6.2x	yes
7	26.2 ms	0.5 ms	49.6x	yes
8	31.3 ms	0.6 ms	48.7x	yes
13	51.2 ms	0.6 ms	90.2x	yes
17	66.2 ms	0.6 ms	106.2x	yes
32	120.5 ms	0.7 ms	177.1x	yes
57	210.0 ms	0.6 ms	335.3x	yes
64	235.7 ms	236.1 ms	1.00x	yes

The current implementation scales linearly with width, as the loop shape predicts. The replacement is flat, because the work no longer depends on width.

What this is worth at query level, which is much less

The microbenchmark speedups are not query speedups, and it would be easy to read them that way. bitunpack is about 20% of these queries, so Amdahl caps the whole thing:

bitunpack speedup	overall query
10x	1.22x
50x	1.24x
335x	1.25x

The ceiling is 1.25x even if bitunpack became free, and essentially all of it is reached by 10x. That is worth having on the hottest read path, and it is not the 300x the table above might suggest. It also means an elaborate SIMD kernel buys nothing over the simple version: the curve is flat past 10x.

Three things that need care

Endianness. The packing is LSB-first, so memcpy into a uint64 and shifting is correct only on a little-endian host. A big-endian build needs a byteswap after the load. This is the one that would produce silently wrong data rather than a crash, on a platform nobody here tests.

Bounds. A 64-bit load at bitpos >> 3 touches up to 8 bytes, so any value whose start byte is within 8 of the encoded body must keep using the existing per-bit path. The version measured above does exactly that, which is also why it is byte-identical: the tail is literally the old code.

width > 57. With a bit offset of up to 7, a single 8-byte load covers at most 57 bits. Wider values need a second load, which I did not implement; width 64 falls through to the safe path, hence the 1.00x row. Whether wide columns are common enough to justify the second word is a question for whoever takes this.

COLUMNAR_DECODE_INTERRUPT(i) must survive the rewrite. It is per-value and the stride makes it nearly free, but a decode of one vector is otherwise uninterruptible for chunk_group_row_limit values, which is user-settable and unbounded.

Not proposing to take this

Filing it with the numbers rather than a patch, since the endianness question is a portability decision rather than a coding one. Happy to implement if you want it, including the big-endian path.

[ChronicallyJD]

Amending my own framing: "~20% of every scan" is not supported, and the win scales with width

jdatcmd took this and could not reproduce the reach I claimed. He is right, and
the title is the part that is wrong.

What I actually measured: 21.0% and 19.2% self time, on two shapes of one
8M-row fixture, cpu-clock with DWARF unwinding. The body says "both scan
shapes"; the title says "every scan". Two shapes of one fixture is not every
scan, and the title is what people will quote.

What he measured, A/B on the bench, same cluster and data, .so the only
difference, restarted between arms, medians of three:

shape	main	#501
sum(a), bigint, width ~1	155.2 ms	154.4 ms	no change
WHERE b = 7, int, width 10	128.7 ms	111.2 ms	13.6% faster
per-row materialisation	277.0 ms	272.9 ms	~1.5%

And no measurable difference on real ClickBench queries, because those either
prune to nothing or are not dominated by unpacking.

The mechanism explains both results and I should have derived it when I filed
this. The per-bit loop runs width iterations per value; the word path runs
one. So the saving scales with width, and at width 1 there is nothing to save —
his first version was 1.7% slower there, because a per-value "does the nine-byte
window fit" test cost more than the loop it replaced.

So: the mechanism in this issue is right, the ceiling I gave is right, and the
reach is not. The number to carry forward is "up to ~14% on a query dominated by
wide bit-packed unpacking, nothing at width 1", not a fifth off any scan.

Retitling to say so. Leaving the original numbers visible rather than editing them
away — they are true of the fixture they were taken on, and the error was the
scope, not the measurement.

And perf does work on jd-tests, which unblocks verifying this independently

You reported cpu-clock producing a file with no samples. It samples here:

$ perf record -q -e cpu-clock -F 99 -g -o /tmp/pt.data -- <workload>
$ perf report -i /tmp/pt.data --stdio
# Samples: 360  of event 'cpu-clock'

perf_event_paranoid is -1 and perf stat -e cpu-clock also works, so the box
is not the problem — something in the invocation is. -F 99 and an explicit -o
are the two things I would check first; a default -F can land on a frequency the
PMU-less VM will not honour, and that is the shape that yields an empty file
rather than an error.

Worth resolving, because "the self-time figures are yours and I have labelled them
that way" is the right call while it stands, and it should not have to stand.

[jdatcmd]

Fixed on main by #514 (44411fe), closing with the measurement rather than by assumption.

What landed: bitunpack reads one unaligned 64-bit word per value instead of running its inner loop once per bit, with a per-bit tail where the nine-byte window would read past the encoded body.

What it is worth, A/B on the bench, same cluster, same data, only the .so differing, postmaster restarted between arms, medians of 3, answers identical:

shape	before	after
count(*) WHERE b = 7 — int, width 10	128.7 ms	111.2 ms	13.6% faster
sum(a) — bigint delta-packed to ~1 bit	155.2 ms	154.4 ms	no change
per-row materialisation	277.0 ms	272.9 ms	~1.5%

And on ClickBench, no measurable difference at all. This is a primitive-level win that appears where unpacking dominates; it should not be quoted as a workload number.

The retitle was right, and the profile confirms the mechanism rather than just the outcome — cpu-clock, 5K samples per shape, distinct capture files:

width ~1   sum(a)            bitunpack: not in the top 5 frames
width 10   count WHERE b=7   bitunpack: 17.22%  (second-largest frame)

The share tracks width, which is what the mechanism predicts: the old loop ran width iterations per value and the new one runs one, so the saving is the width.

Byte-identical is proven, not asserted. ref_bitunpack keeps the pre-change per-bit loop verbatim as an oracle, and the encoding selftest compares them value by value at every width 1–64 at every sub-byte offset — with one count per width now derived rather than listed, because the fixed list was what made that coverage complete and trimming it would have narrowed the oracle silently.

Gated on five majors, ALL VERSIONS PASSED, encode_invariants and native_encoding PASS on each and in no skip list.