BitPacking

Bitpacking is an encoding technique that packs multiple small integers or discrete fields into a compact bit stream. Each value is represented with a fixed number of bits, allowing values that fit within the width to share bits across byte boundaries. The result is a contiguous sequence of bits that can be stored or transmitted more efficiently when the value range is limited.

Fixed-width bitpacking assigns a uniform bit width to all values in a block. Values are concatenated as w-bit fields, and decoding extracts every w bits in order. It is commonly used with delta encoding, where successive differences are stored before packing, and with partitioned bitpacking to handle outliers. Additional compression such as run-length encoding may accompany the scheme to improve performance on certain patterns.

Applications include columnar data stores such as Parquet and ORC, where integer columns are compressed by small fixed widths per block to reduce disk and memory I/O. Bitpacked bitmaps are also used in indexes and other compact representations to enable fast scans with lower memory usage. In practice, bitpacking is often combined with other techniques to balance space savings against encoding and decoding speed.

Considerations include decoding complexity, memory access patterns, and endianness. While bitpacking reduces space, it can incur CPU overhead for packing and unpacking and can complicate random access unless paired with indexing or selective decoding. The choice of bit width depends on the data distribution, the desired granularity of access, and the target hardware capabilities.

Example: encoding four 3-bit values [2, 5, 1, 7] yields 010 101 001 111, which concatenates to 010101001111, a 12-bit stream. Decoding simply reads successive 3-bit chunks to recover the original values.