Tracking Issue: Implement Blocked BitPacked Encoding #10167

This is a tracking issue for implementing per-block bit widths in the BitPacked encoding. This is not a new encoding, but rather an evolution of the existing BitPacked encoding. The evolution will be supported with editions.

Motivation

Our current BitPacked encoding uses one bit width for an entire array. This works well for arrays whose values have a similar magnitude throughout, but less so for arrays with high-variance magnitude values.

For example, consider a 3072-row array spread over three 1024-row chunks:

chunk 0 values: 0 .. 7          (fits in 3 bits)
chunk 1 values: 0 .. 1_000_000  (fits in 20 bits)
chunk 2 values: 0 .. 15         (fits in 4 bits)

With the current BitPacked, every chunk is packed at the widest width needed (20 bits), or the compressor picks a narrower width and stores the wider values as patches:

chunk 0: 20 bits x 1024 = 2560 bytes
chunk 1: 20 bits x 1024 = 2560 bytes
chunk 2: 20 bits x 1024 = 2560 bytes
total:                    7680 bytes

With per-chunk bit widths, each chunk is packed at its own width ([3, 20, 4]):

chunk 0:  3 bits x 1024 =  384 bytes
chunk 1: 20 bits x 1024 = 2560 bytes
chunk 2:  4 bits x 1024 =  512 bytes
total:                    3456 bytes (+ 32 bytes of chunk offsets)

Patches do not help here: they cost an index and a value per exception, so they only pay off when exceptions are rare, not when a whole chunk is wider than the others.

Per-chunk widths give each 1024-element chunk its own bit width. 1024 is the FastLanes chunk size, so each chunk still unpacks with the existing FastLanes kernels. The only change is where the chunk starts and which width it unpacks at.

This pairs naturally with blocked FoR (#10127). Once each chunk has its own reference, its values are small, and the chunk can then be packed at its own width.

Design

Array

Change the in-memory BitPackedArray in the following ways:

• Add a non-nullable unsigned block_offsets child that holds the byte boundaries of the packed blocks, including the trailing end boundary.
• Remove the scalar bit_width. A block's width is derived from its boundaries as (block_offsets[i + 1] - block_offsets[i] / 128)

Block offsets and block width

A FastLanes block always holds 1024 values, and the last chunk is padded up to 1024. A block packed at width w therefore takes:

1024 values * w bits / 8 = 128 * w bytes

Suppose we have an array with 3 blocks. They are packed to widths of [3, 20, 4]. Then:

chunk 0: 128 * 3 = 384 bytes
chunk 1: 128 * 20 = 2560 bytes
chunk 2: 128 * 4 = 512 bytes

The block_offsets child is a prefix sum of the chunk byte sizes. For this example:

block_offsets = [0, 384, 2944, 3456]

Within the packed buffer, we can index to the beginning of each block with these offsets.

Encoding

The encoder chooses a width for each 1024-element block independently, accounting for exceptions (patches) as well.

Wire format

fastlanes.bitpacked is the existing format, unchanged. It is written whenever every chunk has the same width. The offsets child is omitted on write and rebuilt from the scalar width on read, so existing files read exactly as before, and default writes stay byte-identical.

fastlanes.bitpacked.v2 is a new format for arrays whose chunk widths differ. It stores the offsets child (num_chunks + 1 boundaries) and no scalar width, and its metadata contains only bounded array and patch information. The offsets child is serialized like any other child, so the compressor can compress it.

Maintaining v1 serde

When we read v1, we translate the bitwidth into a SequenceArray block offsets child. We detect whether a BitPackedArray can be serialized as v1 by whether the block offsets child is a SequenceArray.

Compressor

BitPackingScheme gains a per-chunk mode. Scheme::refine selects it when fastlanes.bitpacked_v2 is allowed, and falls back to the global-width mode (v1) otherwise.

Steps

• Move serde logic from blanket vtable impl to explicit arrayplugin
• Transition from single bit_width field to mutually exclusive bit_width (for global bw) and block_offsets child (for blocked bws)
• Implement blocked encoding
• Implement blocked decoding
• Support serde for bitpacked.v2
• Support blocked encoding in as new BitPacked compressor mode
• Support blocked encode/decode on GPU
• Extend compute kernels to work with blocked bws
• Support fused FoR unpacking
• Refine compression estimates
• Use blocked BP when enabled in FoRScheme

Unresolved questions

1. How should we account for patches in the blocked encoding? Cost model will be different with blocked layout.
2. Is it better to maintain an optional bit_width in array data that marks whether the array is v1 compatible (and then keep the compute kernel fast paths) than to have the differentiator be whether the SequenceArray block offsets child? We can make this and the presence of the block offsets child complements. ANSWER: use mutually exclusive fields.