Bit-Packed Encoding for Small Integers

1. The Core Idea: Stop Wasting Bits

Database systems and programming languages typically store integers in fixed-size types like a 32-bit or 64-bit integer. This is convenient, but often wasteful. If you have a column storing human ages, the maximum value might be around 120. To store the number 120, you only need 7 bits ($2^7=128$), yet a 32-bit integer uses 32 bits, wasting the 25 leading zero-bits.

Bit-packed encoding, or bit packing, eliminates this waste. It determines the minimum number of bits required to store the largest value in a chunk of data and then stores every value in that chunk using exactly that many bits.

2. Why and How Bit Packing Works

The fundamental motivation for bit packing is to reduce the data size, which in turn minimizes I/O and allows more data to fit into CPU caches. To get a formal introduction from a database systems perspective, let's watch a segment from a CMU lecture.

As the video explains, the process for a block of data is:

1. Find the maximum value in the block.
2. Calculate the required bit-width: $width=\lceil {\log }_2(\text{max\_value}+1)\rceil$. For example, if the max value is 100, you need $\lceil {\log }_2(101)\rceil =7$ bits.
3. Pack all integers in the block using this fixed width, storing them contiguously in a byte array.

The "mostly encoding" trick mentioned is an important optimization for data with rare large values, but for our core implementation, we will assume all values fit within the calculated bit-width.

3. The Mechanics of Implementation

Implementing bit packing requires careful manipulation of bits using bitwise operators. Since you're proficient in C++, you'll be familiar with shifting (<<, >>), masking (&), and ORing (|). The main challenge is managing the bit-stream as it crosses byte boundaries.

A fantastic, detailed video walks through building a bit packer from scratch. Although the code is in JavaScript, the underlying logic of bit manipulation is universal and directly applicable to a C++ implementation.

The core algorithm demonstrated in the video involves maintaining two pointers:

• byte_index: The current byte we are writing to in our output buffer.
• bit_offset: The next available bit within the current byte (e.g., from 7 down to 0).

When packing a new value, the algorithm must:

1. Determine if the new value's bits fit in the remaining space of the current byte.
2. If yes (the simple case), shift the value into position and OR it with the current byte.
3. If no (the complex case), fill the rest of the current byte with the top bits of the value, advance to the next byte, and then write the remaining bits of the value. This may repeat if the value spans multiple byte boundaries.

4. Bit Ordering and a C++ Perspective

Before writing code, a crucial design decision is the bit ordering. Do you pack bits starting from the Most Significant Bit (MSB) of a byte, or the Least Significant Bit (LSB)?

• MSB-first: New values are packed from left to right in the byte. This corresponds naturally to big-endian byte order.
• LSB-first: New values are packed from right to left. This corresponds naturally to little-endian byte order, which is used by most modern CPUs (like x86 and ARM).

The following blog post provides an expert-level discussion on this topic and is essential reading for anyone implementing bit-level I/O.

A Simple C++ Example: Packing Bools

To see this in a C++ context, let's look at a simplified version of bit packing: packing boolean values, where each value takes exactly 1 bit.

The first "manual version" is a great starting point for our general-purpose packer. It uses a shiftCounter (our bit_offset) and an OutByte variable to accumulate 8 bits before writing to the output array.

C++ Pseudocode for General Bit Packing

Now, let's synthesize these ideas into a C++ function that can pack integers of a given bit_width. This implementation will use an LSB-first strategy, which is common.

#include <vector>
#include <cstdint>
#include <cmath>

// A simplified bit packer for unsigned integers.
// Assumes all values fit within bit_width.
void bit_pack(const std::vector<uint32_t>& values, int bit_width, std::vector<uint8_t>& packed_output) {
    if (values.empty()) return;

    // Calculate the required output size in bytes.
    uint64_t total_bits = (uint64_t)values.size() * bit_width;
    size_t packed_size_bytes = (total_bits + 7) / 8;
    packed_output.assign(packed_size_bytes, 0);

    uint64_t bit_buffer = 0; // A 64-bit buffer to hold bits before they are flushed to bytes.
    int bits_in_buffer = 0;

    for (uint32_t value : values) {
        // Add the new value's bits to our buffer.
        // We cast value to uint64_t to ensure the left shift doesn't overflow if bits_in_buffer is large.
        bit_buffer |= ((uint64_t)value << bits_in_buffer);
        bits_in_buffer += bit_width;

        // Flush full bytes from the buffer to the output vector.
        while (bits_in_buffer >= 8) {
            packed_output.push_back(bit_buffer & 0xFF); // Write the lowest 8 bits.
            bit_buffer >>= 8;                           // Shift them out of the buffer.
            bits_in_buffer -= 8;
        }
    }

    // Flush any remaining bits.
    if (bits_in_buffer > 0) {
        packed_output.push_back(bit_buffer & 0xFF);
    }

    // The logic above writes bytes in reverse order of how they appear in the stream.
    // For a real implementation, you would write to an index in packed_output instead.
    // This simplified version using push_back is for clarity of the bit manipulation logic.
}

This implementation uses a bit_buffer (a 64-bit integer) to simplify the logic. Instead of managing byte boundaries manually for each value, we accumulate bits into this larger buffer and then flush completed bytes from it. This is a common and efficient pattern.

Conclusion

You have now learned the principles and implementation details of bit-packed encoding, a fundamental compression technique for columnar databases.

Key Takeaways:

• Bit packing is ideal for columns of small integers that do not have long consecutive runs (unlike RLE).
• It saves space by storing each number using the minimum number of bits required for the largest value in a block.
• The implementation relies on careful bitwise manipulation (shifting, masking, and ORing) to tightly pack values into a byte stream.
• A key design choice is bit-ordering (LSB-first vs. MSB-first), which has implications for endianness and implementation simplicity.
• Using a larger bit buffer (e.g., a uint64_t) can simplify the code by decoupling the process of adding bits from the process of writing full bytes to the output.

Preview of the Next Lesson

We have now covered several powerful compression techniques that are applied at the column level (RLE, Dictionary Encoding, Bit Packing). But how are these compressed columns physically arranged on disk? In our next lesson, you will learn how to describe the PAX hybrid storage model as a compromise between row and column stores, which organizes data within a page to get the benefits of both worlds.