Opensource internals

How ClickHouse Compresses Columns: Delta, Gorilla and the CODEC Pipeline

21 min read Jay Hubbert

ClickHouse's column codecs are bit-level transforms chained under a generic compressor: Delta stores differences, DoubleDelta stores second differences, Gorilla stores XORs, and CODEC(...) nests them.

TL;DR: A CODEC(...) clause is a pipeline, not a single algorithm. ClickHouse stores a column as a chain: Delta turns values into differences, DoubleDelta turns differences into second differences, Gorilla stores XORs of successive values, and a generic compressor like ZSTD squeezes the result. Each link is described by one method byte, so the reader knows how to undo it.

Compression in a columnar database is not one algorithm but two different problems, and ClickHouse splits them explicitly.

The first problem is entropy: the bytes have patterns a general-purpose compressor can exploit — repeated strings, correlated fields, common prefixes. This is what LZ4 and ZSTD are for, and it is a general-purpose job.

The second problem is structure: the column has a shape that a general-purpose compressor cannot see. A timestamp column that increases by exactly 1000 every row has almost zero entropy, but the bytes of the timestamps look like random noise to ZSTD, because the relationship between adjacent values is not visible in any single byte. A Delta preprocessor restores that structure, and then ZSTD does its job.

So ClickHouse’s codecs come in two flavours — preprocessors that change the representation, and compressors that reduce the entropy — and a column can use several of them in sequence:

sql 
CREATE TABLE events
(
    `timestamp` DateTime CODEC(Delta, ZSTD(1)),
    `user_id`   UInt32   CODEC(T64, ZSTD(1)),
    `value`     Float64  CODEC(Gorilla, ZSTD(1)),
    `payload`   String   CODEC(ZSTD(3))
)
ENGINE = MergeTree
ORDER BY timestamp;

Delta, ZSTD(1) means: first turn the timestamps into differences, then compress the differences with ZSTD level 1. This article is about how that pipeline is built, what each stage actually does to the bits, and why the framing around it is what it is.

The block format

Before the codecs, the frame. Every compressed block on disk is:

text 
  +----------------+-----------------+-------------------+---------------+
  | checksum (16B) | method (1 byte) | compressed size   | uncompressed  |
  |   CityHash128  |                 | (4 bytes, LE)    | size (4B, LE) |
  +----------------+-----------------+-------------------+---------------+
  |                         compressed payload                     |
  +--------------------------------------------------------------+

The checksum covers the method byte, the sizes, and the payload — everything after itself. And the header size is a compile-time constant:

cpp 
// src/Compression/CompressionInfo.h:16
/** one byte for method, 4 bytes for compressed size, 4 bytes for uncompressed size */
constexpr uint8_t COMPRESSED_BLOCK_HEADER_SIZE = 9;

The method byte identifies the codec, and the values are frozen forever:

cpp 
// src/Compression/CompressionInfo.h:43
enum class CompressionMethodByte : uint8_t
{
    NONE            = 0x02,
    LZ4             = 0x82,
    ZSTD            = 0x90,
    Multiple        = 0x91,
    Delta           = 0x92,
    T64             = 0x93,
    DoubleDelta     = 0x94,
    Gorilla         = 0x95,
    AES_128_GCM_SIV = 0x96,
    AES_256_GCM_SIV = 0x97,
    FPC             = 0x98,
    /// DeflateQpl      = 0x99, /// Removed, don't reuse for another codec
    GCD             = 0x9a,
    /// ZSTD_QPL        = 0x9b, /// Removed, don't reuse for another codec
    ALP             = 0x9c,
    SZ3             = 0x9d,
    Quantized       = 0x9e,
    ZXC             = 0x9f,
    PCO             = 0xa0,
};

The removed entries are interesting: 0x99 and 0x9b were codecs that no longer exist, and rather than reuse the numbers, ClickHouse burns them. A codec byte is a permanent, on-disk identifier; reusing one would mean old data silently decoding as the wrong thing.

The header itself is written by one function:

cpp 
// src/Compression/ICompressionCodec.cpp:63
UInt32 ICompressionCodec::writeHeader(char * dest, UInt32 body_size, UInt32 uncompressed_size) const
{
    const UInt32 block_size = getHeaderSize() + body_size;
    dest[0] = getMethodByte();
    unalignedStoreLittleEndian<UInt32>(&dest[1], block_size);
    unalignedStoreLittleEndian<UInt32>(&dest[5], uncompressed_size);
    return block_size;
}

Note that the compressed size in the header includes the header itself (getHeaderSize() + body_size), which is what lets a reader skip a block without decompressing it.

The “don’t bother” rule

Compression is not always a win. Random data compresses to slightly more than its original size, and the block would be both bigger and slower to read. ClickHouse’s writer has an escape hatch for exactly this:

cpp 
// src/Compression/CompressedWriteBuffer.cpp:53
    UInt32 compressed_size = codec->compress(working_buffer.begin(), decompressed_size, compressed_ptr);

    /// The block is stored as is if compression saves less than 1/8 of its size.
    if (uncompressed_codec && static_cast<UInt64>(compressed_size) * 8 > static_cast<UInt64>(decompressed_size) * 7)
        compressed_size = uncompressed_codec->compress(working_buffer.begin(), decompressed_size, compressed_ptr);

The uncompressed_codec is a NONE codec, and the rule is a 12.5% threshold: if compression did not save at least 1/8 of the block, the block is stored uncompressed. That is not a micro-optimisation — for a column of random UUIDs it is the difference between a part that grows and one that does not.

The checksum is computed over the compressed bytes, and written before them:

cpp 
// src/Compression/CompressedWriteBuffer.cpp:59
    CityHash_v1_0_2::uint128 checksum = CityHash_v1_0_2::CityHash128(compressed_ptr, compressed_size);

    writeBinaryLittleEndian(checksum.low64, out);
    writeBinaryLittleEndian(checksum.high64, out);

    if (compress_in_place)
        out.position() += compressed_size;
    else
        out.write(compressed_buffer.data(), compressed_size);

And on the read side, the checksum failure handler does something rather charming: it tries every single-bit flip of the block to find the culprit.

cpp 
// src/Compression/CompressedReadBufferBase.cpp:87
    if (size < (1ULL << 20))
    {
        /// We need to copy data from ReadBuffer to flip bits as ReadBuffer should be immutable
        PODArray<char> tmp_buffer(data, data + size);
        char * tmp_data = tmp_buffer.data();

        /// Check if the difference caused by single bit flip in data.
        for (size_t bit_pos = 0; bit_pos < size * 8; ++bit_pos)
        {
            flip_bit(tmp_data, bit_pos);

            auto checksum_of_data_with_flipped_bit = CityHash_v1_0_2::CityHash128(tmp_data, size);
            if (expected_checksum == checksum_of_data_with_flipped_bit)
            {

If exactly one bit flip explains the mismatch, the error message says which byte and which bit, and blames the hardware (“bad RAM on network interface controller … or disk bit rot”). It is a 1 MB block, so at most 8 million hash computations — expensive, but this is the path where a user is already losing data and needs to know whether their disk is dying.

Delta: store the differences

The simplest useful preprocessor. Delta(4) on a UInt32 column stores a[i] - a[i-1] instead of a[i].

cpp 
// src/Compression/CompressionCodecDelta.cpp:81
template <typename T>
void compressDataForType(const char * source, UInt32 source_size, char * dest)
{
    if (source_size % sizeof(T) != 0)
        throw Exception(ErrorCodes::CANNOT_COMPRESS, "Cannot compress with Delta codec, data size {} is not aligned to {}", source_size, sizeof(T));

    T prev_src = 0;
    const char * const source_end = source + source_size;
    while (source < source_end)
    {
        T curr_src = unalignedLoadLittleEndian<T>(source);
        unalignedStoreLittleEndian<T>(dest, curr_src - prev_src);
        prev_src = curr_src;

        source += sizeof(T);
        dest += sizeof(T);
    }
}

For a timestamp column increasing by one second, every stored value is 1, and the four bytes of every value are 01 00 00 00. ZSTD turns that into almost nothing. This is the classic “delta encoding” of time series, and it is why CODEC(Delta, ...) is the default suggestion for DateTime columns.

Decompressing deltas is a prefix sum, and prefix sums vectorise

Delta decoding is an inclusive prefix sum: a[i] = sum(deltas[0..i]). And a prefix sum is exactly the kind of thing that SIMD does well — if you restructure it. The naive scalar loop is limited to one element per cycle by the loop-carried accumulator. ClickHouse’s version computes the prefix sum within a 16-byte register with log2(lanes) shift-and-add steps, then adds the running total of previous registers:

cpp 
// src/Compression/CompressionCodecDelta.cpp:100
/** Delta decoding is an inclusive prefix sum of the deltas, and the scalar loop is limited by the
  * loop-carried accumulator to at most one element per cycle. Instead, process the data in 16-byte
  * registers: log2(lanes) shift-and-add steps compute the prefix sum within a register, then the
  * running total of all previous registers is added to every lane, and the last lane becomes the
  * running total for the next register.
  *
  * The kernel is written with generic clang vectors; the shuffles compile to single instructions
  * on the SSE2 (x86_64) and NEON (AArch64) baselines, so no arch-specific code or runtime dispatch
  * is needed. Lanes are loaded in native byte order, so the fast path also requires a little-endian
  * build to match the little-endian on-disk format; others fall back to the scalar loop below.
  */

The kernel:

cpp 
// src/Compression/CompressionCodecDelta.cpp:131
template <typename T>
T decompressBlocks(const char * source, char * dest, size_t blocks)
{
    constexpr size_t lanes = 16 / sizeof(T);
    constexpr auto index = std::make_index_sequence<lanes>{};

    DeltaVec<T> sum{};
    for (size_t i = 0; i < blocks; ++i)
    {
        DeltaVec<T> x;
        memcpy(&x, source + i * 16, 16);
        if constexpr (lanes >= 2)
            x += shiftLanesIn<1>(x, index);
        if constexpr (lanes >= 4)
            x += shiftLanesIn<2>(x, index);
        if constexpr (lanes >= 8)
            x += shiftLanesIn<4>(x, index);
        if constexpr (lanes >= 16)
            x += shiftLanesIn<8>(x, index);
        /// Update the running total from the local prefix sum, so that the broadcast stays off
        /// the loop-carried dependency chain (which is then a single addition).
        const DeltaVec<T> carry = broadcastLastLane(x, index);
        x += sum;
        sum += carry;
        memcpy(dest + i * 16, &x, 16);
    }
    return sum[0];
}

The trick is the ordering of the last two lines. A naive “add the carry to every lane” would put the carry on the critical path: the carry depends on the current block, and the next block’s carry depends on this one. Instead, the running total is updated from the local prefix sum (carry = broadcastLastLane(x), the last lane of the block’s own prefix sum), so the loop-carried dependency is a single addition of two vectors, and the broadcast — which is a shuffle — sits off that chain.

The whole thing is guarded by a portability check:

cpp 
// src/Compression/CompressionCodecDelta.cpp:111
#if (((defined(__x86_64__) || defined(__i386__)) && defined(__SSE2__)) || (defined(__aarch64__) && defined(__ARM_NEON))) \
    && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
#define DELTA_CODEC_SIMD_DECOMPRESS

Note the __ORDER_LITTLE_ENDIAN__ condition: the vector lanes are loaded in native byte order, so the fast path only works where native order is the on-disk order. On a big-endian build the code falls back to the scalar loop, which explicitly byte-swaps:

cpp 
// src/Compression/CompressionCodecDelta.cpp:181
    while (source < source_end)
    {
        accumulator += unalignedLoadLittleEndian<T>(source);
        unalignedStoreLittleEndian<T>(dest, accumulator);
        source += sizeof(T);
        dest += sizeof(T);
    }

Delta is not a compressor by itself — it is a preprocessor, and the class says so:

cpp 
// src/Compression/CompressionCodecDelta.cpp:33
    bool isCompression() const override { return false; }
    bool isGenericCompression() const override { return false; }
    bool isDeltaCompression() const override { return true; }

so Delta alone on a column would make it bigger (it adds a 2-byte header and stores bytes_to_skip bytes of alignment padding). It only pays off when something follows it.

DoubleDelta: store the differences of the differences

If Delta works because consecutive values are close, DoubleDelta works because the deltas are close — a sequence with a constant stride has a constant second difference, which is zero.

The bit-level encoding is the interesting part. Instead of storing the second differences as fixed-width integers, they are stored with a variable-length prefix:

cpp 
// src/Compression/CompressionCodecDoubleDelta.cpp:44
 * Given input sequence a: [a0, a1, ... an]:
 *
 * First, write number of items (sizeof(int32)*8 bits):                n
 * Then write first item as is (sizeof(a[0])*8 bits):                  a[0]
 * Second item is written as delta (sizeof(a[0])*8 bits):              a[1] - a[0]
 * Loop over remaining items and calculate double delta:
 *   double_delta = a[i] - 2 * a[i - 1] + a[i - 2]
 *   Write it in compact binary form with `BitWriter`
 *   if double_delta == 0:
 *      write 1bit:                                                    0
 *   else if -63 < double_delta < 64:
 *      write 2 bit prefix:                                            10
 *      write sign bit (1 if signed):                                  x
 *      write 7-1 bits of abs(double_delta - 1):                       xxxxxx
 *   else if -255 < double_delta < 256:
 *      write 3 bit prefix:                                            110
 *      write sign bit (1 if signed):                                  x
 *      write 9-1 bits of abs(double_delta - 1):                       xxxxxxxx
 *   else if -2047 < double_delta < 2048:
 *      write 4 bit prefix:                                            1110
 *      write sign bit (1 if signed):                                  x
 *      write 12-1 bits of abs(double_delta - 1):                      xxxxxxxxxxx
 *   else if double_delta fits into 32-bit int:
 *      write 5 bit prefix:                                            11110
 *      write sign bit (1 if signed):                                  x
 *      write 32-1 bits of abs(double_delta - 1):                      xxxxxxxxxxx...
 *   else
 *      write 5 bit prefix:                                            11111
 *      write sign bit (1 if signed):                                  x
 *      write 64-1 bits of abs(double_delta - 1):                      xxxxxxxxxxx...

The prefix is a unary-ish code: 0 means zero (one bit!), 10 means a 7-bit magnitude, 110 a 9-bit one, 1110 a 12-bit one, 11110 a 32-bit one, 11111 a 64-bit one. The prefix lengths are increasing but the code is a prefix code, so a decoder can dispatch on the first 5 bits with a lookup table:

cpp 
// src/Compression/CompressionCodecDoubleDelta.cpp:185
// delta size prefix and data lengths based on few high bits peeked from binary stream
const WriteSpec WRITE_SPEC_LUT[32] = {
    // 0b0 - 1-bit prefix, no data to read
    /* 00000 */ {1, 0b0, 0},

The table has 32 entries because the decoder peeks the top 5 bits:

cpp 
// src/Compression/CompressionCodecDoubleDelta.cpp:455
        static_assert(sizeof(WRITE_SPEC_LUT)/sizeof(WRITE_SPEC_LUT[0]) == 32); // 5-bit prefix lookup table
        const auto write_spec = WRITE_SPEC_LUT[reader.peekByte() >> (8 - 5)]; // only 5 high bits of peeked byte value

The -1 in abs(double_delta - 1) is a classic trick: zero is already encoded by the 0 prefix, so the magnitude can be shifted down by one and still represent 1 in one bit less.

The writer side:

cpp 
// src/Compression/CompressionCodecDoubleDelta.cpp:341
        if (double_delta == 0)
        {
            writer.writeBits(1, 0);
        }
        else
        {
            const SignedDeltaType signed_dd = static_cast<SignedDeltaType>(double_delta);
            const auto sign = signed_dd < 0;

            // -1 shrinks dd down to fit into number of bits, and there can't be 0, so it is OK.
            const auto abs_value =
                signed_dd == std::numeric_limits<SignedDeltaType>::min()
                    ? (static_cast<UnsignedDeltaType>(-1) >> 1)
                    : static_cast<UnsignedDeltaType>(std::abs(signed_dd) - 1);
            const auto write_spec = getDeltaWriteSpec(signed_dd);

            writer.writeBits(write_spec.prefix_bits, write_spec.prefix);
            writer.writeBits(1, sign);
            writer.writeBits(write_spec.data_bits - 1, abs_value);
        }

and the BitWriter that packs it — note the unsigned __int128 accumulator, which holds 128 bits so the inner loop rarely has to flush:

cpp 
// src/IO/BitHelpers.h:151
class BitWriter
{
    char * dest_begin;
    char * dest_end;
    char * dest_current;

    using BufferType = unsigned __int128;
    BufferType bits_buffer = 0;

    UInt8 bits_count = 0;

    static constexpr UInt8 BIT_BUFFER_SIZE = sizeof(bits_buffer) * 8;

The decompressor has a fast path too: it reads a 64-bit word at a time and decodes as many deltas as fit, only falling back to the bit reader for the tail:

cpp 
// src/Compression/CompressionCodecDoubleDelta.cpp:415
    /// Read up to two words per delta; leave the final bytes to `BitReader`.
    while (items_read < items_count && source_end - source >= 16)
    {
        const UInt64 word = unalignedLoadBigEndian<UInt64>(source);
        const auto write_spec = WRITE_SPEC_LUT[(word << bit_offset) >> (64 - 5)];

Note unalignedLoadBigEndian here, even though the data is little-endian: the bits are read as a bit stream, and the byte order of the word is irrelevant as long as it is consistent — but big-endian load makes the “top 5 bits” arithmetic work out.

Gorilla: XOR of successive values

For floating-point gauges — CPU usage, queue depth, temperature — the values change slowly and the bit pattern of the change is small. Gorilla stores a[i] ^ a[i-1] and describes each XOR with its leading and trailing zero counts:

cpp 
// src/Compression/CompressionCodecGorilla.cpp:31
 * Loop over remaining items and calculate xor_diff:
 *   xor_diff = a[i] ^ a[i - 1] (e.g. 00000011'10110100)
 *   Write it in compact binary form with `BitWriter`
 *   if xor_diff == 0:
 *       write 1 bit:                                                  0
 *   else:
 *       calculate leading zero bits (lzb)
 *       and trailing zero bits (tzb) of xor_diff,
 *       compare to lzb and tzb of previous xor_diff
 *       (X = sizeof(a[i]) * 8, e.g. X = 16, lzb = 6, tzb = 2)
 *       if lzb >= prev_lzb && tzb >= prev_tzb:
 *           (e.g. prev_lzb=4, prev_tzb=1)
 *           write 2 bit prefix:                                       0b10
 *           write xor_diff >> prev_tzb (X - prev_lzb - prev_tzb bits):0b00111011010
 *           (where X = sizeof(a[i]) * 8, e.g. 16)
 *       else:
 *           write 2 bit prefix:                                       0b11
 *           write 5 bits of lzb:                                      0b00110
 *           write 6 bits of (X - lzb - tzb)=(16-6-2)=8:               0b001000
 *           write (X - lzb - tzb) non-zero bits of xor_diff:          0b11101101
 *           prev_lzb = lzb
 *           prev_tzb = tzb

The clever part is the 0b10 case: if the new XOR has at least as many leading zeros and at least as many trailing zeros as the previous one, the previous window still contains the new value, so only the payload has to be written — 2 bits of prefix plus the significant bits. A slowly drifting float usually stays in this case, and each sample then costs a handful of bits.

The writer:

cpp 
// src/Compression/CompressionCodecGorilla.cpp:236
    while (source < source_end)
    {
        const T curr_value = unalignedLoadLittleEndian<T>(source);
        source += sizeof(curr_value);

        const auto xored_data = curr_value ^ prev_value;
        const BinaryValueInfo curr_xored_info = getBinaryValueInfo(xored_data);

        if (xored_data == 0)
        {
            writer.writeBits(1, 0);
        }
        else if (prev_xored_info.data_bits != 0
                && prev_xored_info.leading_zero_bits <= curr_xored_info.leading_zero_bits
                && prev_xored_info.trailing_zero_bits <= curr_xored_info.trailing_zero_bits)
        {
            writer.writeBits(2, 0b10);
            writer.writeBits(prev_xored_info.data_bits, xored_data >> prev_xored_info.trailing_zero_bits);
        }
        else
        {
            writer.writeBits(2, 0b11);
            writer.writeBits(LEADING_ZEROES_BIT_LENGTH, curr_xored_info.leading_zero_bits);
            writer.writeBits(DATA_BIT_LENGTH, curr_xored_info.data_bits);
            writer.writeBits(curr_xored_info.data_bits, xored_data >> curr_xored_info.trailing_zero_bits);
            prev_xored_info = curr_xored_info;
        }

        prev_value = curr_value;
    }

The widths of the “leading zero count” and “data length” fields depend on the type width, which is why they are computed from a table:

cpp 
// src/Compression/CompressionCodecGorilla.cpp:148
constexpr UInt8 getBitLengthOfLength(UInt8 data_bytes_size)
{
    // 1-byte value is 8 bits, and we need 4 bits to represent 8 : 1000,
    // 2-byte         16 bits        =>    5
    // 4-byte         32 bits        =>    6
    // 8-byte         64 bits        =>    7
    const UInt8 bit_lengths[] = {0, 4, 5, 0, 6, 0, 0, 0, 7};

And the decoder is careful about corrupted input — the widths it reads are checked against the type’s bit size before they are used to shift:

cpp 
// src/Compression/CompressionCodecGorilla.cpp:323
                /// The encoder derives both widths from a non-zero XOR, so there is at least one data
                /// bit and the leading zero bits and the data bits together fit into the value.
                if (curr_xored_info.data_bits == 0
                    || UInt32{curr_xored_info.leading_zero_bits} + UInt32{curr_xored_info.data_bits} > sizeof(T) * 8) [[unlikely]]
                    throw Exception(ErrorCodes::CANNOT_DECOMPRESS,
                        "Cannot decompress Gorilla-encoded data: corrupted input data. "
                        "It has {} leading zero bits and {} data bits, which is not a valid split of {} bits",

That is a real hardening measure: without it, a corrupted data_bits field of 255 would shift by 255 bits and produce garbage — or undefined behaviour.

The pipeline: CODEC(Delta, ZSTD(1))

A chain of codecs is stored as a Multiple codec, whose payload is a list of method bytes followed by the nested payload:

text 
  +--------+---------------+------------------------+
  | count  | method bytes  |  stage 0 payload       |
  | (1B)   | (count bytes) |  ...                   |
  +--------+---------------+------------------------+

The compression side runs the chain in order, alternating between two scratch buffers:

cpp 
// src/Compression/CompressionCodecMultiple.cpp:132
UInt32
CompressionCodecMultiple::compressBody(size_t completed_stages, const char * input, UInt32 input_size, UInt32 dest_size, char * dest) const
{
    const auto chain = getCodecs();
    chassert(completed_stages <= chain.size());

    dest[0] = static_cast<UInt8>(chain.size());
    for (size_t idx = 0; idx < chain.size(); ++idx)
        dest[1 + idx] = chain[idx]->getMethodByte();

    const size_t payload_offset = 1 + chain.size();
    char * const payload = dest + payload_offset;

    /// Stage outputs alternate between two buffers. The last stage writes into `dest` when its reserve fits there.
    std::array<PODArray<char>, 2> buffers;
    for (size_t idx = completed_stages; idx < chain.size(); ++idx)
    {
        const auto & codec = chain[idx];
        const UInt32 reserve = getCheckedReserveSize(codec, input_size, idx, chain.size());
        const bool is_last_stage = idx + 1 == chain.size();
        const bool in_place = is_last_stage && payload_offset + reserve <= dest_size;

        char * output = payload;
        if (!in_place)
        {
            buffers[idx % 2].resize_exact(reserve);
            output = buffers[idx % 2].data();
        }

        input_size = codec->compress(input, input_size, output);
        input = output;
    }

The two-buffer alternation is the minimum needed for a pipeline: stage n reads from one buffer and writes to the other, and they swap. The last stage writes directly into the destination if there is room, avoiding a final memcpy — and if there is not, the result is copied back:

cpp 
// src/Compression/CompressionCodecMultiple.cpp:165
    const size_t written_size = payload_offset + input_size;

    /// The result is in a buffer after no stage was left to run or a last stage whose reserve did not fit. If so, memcpy it to `dest`.
    if (input != payload)
    {
        if (written_size > dest_size)
            throw Exception(
                ErrorCodes::CANNOT_COMPRESS,
                "Compressed data of size {} does not fit the reserved buffer of size {}",
                written_size,
                dest_size);
        memcpy(payload, input, input_size);
    }

Decompression runs the chain backwards — the last stage written is the first stage undone — and the comment in the source lays out the buffer choreography:

cpp 
// src/Compression/CompressionCodecMultiple.cpp:197
    /// source --memcpy--> compressed_buf --decode--> uncompressed_buf --swap--> compressed_buf --decode--> ... --decode--> uncompressed_buf --memcpy--> dest
    /// Buffers get the codec's padding, the caller's `source` and `dest` have none.
    /// A first stage that needs no padding decodes `source` directly, skipping the first memcpy.
    /// A last stage that needs no padding decodes into `dest` directly, skipping the last one.
    PODArray<char> compressed_buf;
    PODArray<char> uncompressed_buf;

and the loop:

cpp 
// src/Compression/CompressionCodecMultiple.cpp:204
    for (int idx = compression_methods_size - 1; idx >= 0; --idx)
    {
        UInt8 compression_method = source[idx + 1];
        const auto codec = CompressionCodecFactory::instance().get(compression_method);
        auto additional_size_at_the_end_of_buffer = codec->getAdditionalSizeAtTheEndOfBuffer();
        const bool is_first_stage = idx == compression_methods_size - 1;
        const bool is_last_stage = idx == 0;

The additional_size_at_the_end_of_buffer is a per-codec quirk: LZ4, for example, needs a few extra bytes at the end of its output buffer to read past. The chain handles it by padding the intermediate buffers and skipping the copy at the ends when padding is not needed.

And the chain length is limited by the format:

cpp 
// src/Compression/CompressionCodecMultiple.cpp:91
    /// doCompressData stores the number of codecs in one byte, and doDecompressData reads it back
    /// from there, so a longer chain would write a part that cannot be read.
    if (chain.size() > std::numeric_limits<UInt8>::max())
        throw Exception(ErrorCodes::CANNOT_COMPRESS,
            "Too many codecs in the codec chain: {}. The number of codecs is stored in one byte, "
            "so at most {} are supported.",
            chain.size(), static_cast<size_t>(std::numeric_limits<UInt8>::max()));

255 codecs, because the count is a byte.

Adaptive: picking the codec per block

One more mechanism is worth mentioning, because it shows how the framing enables a trick. The CODEC(Default) setting does not pick one codec for the whole column; it picks one per block, from a pool that depends on the column’s type:

cpp 
// src/Compression/CompressionCodecAdaptive.h:32
/// Adaptive codec picks the smallest-output codec per block from a default codec + type-appropriate pool and delegates to it.
/// On disk, each block carries the winner's method byte and reader decodes it with no knowledge of "adaptive".
/// The wrapper itself never appears on disk.
class CompressionCodecAdaptive final : public ICompressionCodec

The pool is NONE, the deployment default, plus type-appropriate candidates:

cpp 
// src/Compression/CompressionCodecAdaptive.cpp:49
/// Candidate codecs for the adaptive pool. Each one is also tried followed by the deployment default if it's a general-purpose compressor.
constexpr auto CANDIDATES = std::to_array<CandidateGroup>({
    /// T64 defaults to the byte flavour (over bit). Good: same size + faster [de]compression.
    {"T64", T64_TYPES},
    {"ALP(AUTO)", ALP_TYPES},
});

So for an integer column the pool is NONE, LZ4, T64, T64+LZ4; for a float column it is NONE, LZ4, ALP, ALP+LZ4. Each block is compressed with every candidate and the smallest output wins — and because the winner’s method byte is written into the block header, the reader needs no knowledge of “adaptive” at all. The wrapper never appears on disk.

That is a nice payoff of the framing design: because the method byte is per-block rather than per-column, the choice of codec can be made per block, at the cost of compressing the block more than once.

Trade-offs

What the pipeline buys:

  • Structure-aware compression. Delta + ZSTD on a timestamp column routinely beats ZSTD alone by a wide margin, because the differences are nearly constant and the generic compressor gets to see that.
  • A per-block fallback. The 1/8 rule means a column of incompressible data costs 0 bytes of overhead rather than a few percent.
  • Self-describing blocks. Every block carries its own method byte and sizes, so a file can mix codecs, and a reader can skip a block it does not understand.
  • Corruption is detected, and diagnosed. A 128-bit CityHash over the block catches silent bit rot, and the error path can name the exact bit.

What it costs:

  • Preprocessors are not compressors. Delta alone makes a column bigger. Using it without a compressor is a mistake the API allows.
  • The chain is not free. Each stage is a full pass over the data, with a buffer ping-pong between stages. CODEC(Delta, ZSTD(1)) reads the column twice.
  • The chain is positional. The method bytes appear before the payload, in the chain’s order, but the payload is nested — stage 0’s output is stage 1’s input. A reader must decode from the inside out, and the code has to juggle two scratch buffers to do it.
  • Type-specific codecs need the type. Gorilla needs to know the width (1, 2, 4 or 8 bytes), and T64 and ALP need the column type. That is fine inside a MergeTree part, where the type is known, but it makes the codec non-portable — you cannot apply Gorilla to a column whose type you do not know.
  • Adaptive costs one compression pass per candidate. Picking the smallest output requires trying them all.
  • The format is frozen. Method bytes are permanent, removed codecs burn their numbers, and the on-disk layout of every codec is covered by compatibility tests:
cpp 
// src/Compression/CompressionCodecDoubleDelta.cpp:117
 * Please also see unit tests for:
 *   * Examples on what output `BitWriter` produces on predefined input.
 *   * Compatibility tests solidifying encoded binary output on set of predefined sequences.

That last point is the real constraint. Once a codec’s bytes are on disk in somebody’s cluster, the exact bit layout — the prefix widths, the order of the fields, the endianness — is forever. The WRITE_SPEC_LUT table, the getBitLengthOfLength table, the abs(value - 1) trick: none of it can change, ever, without a format version bump.

ClickhouseInternalsCompressionCodecs