How ClickHouse Stores a Column: PODArray, the Typed Array, and the Padding Trick

Underneath every ClickHouse data type there is exactly one data structure: a flat array of trivially-copyable elements. UInt64 is an array of UInt64. String is a flat character buffer plus an array of offsets. Nullable(UInt32) is an array of UInt32 plus an array of UInt8. There is no node, no pointer chasing, no per-row allocation.

That design is what makes ClickHouse fast, and it comes with a set of non-obvious constraints that shape everything above it:

The array must not be std::vector, because std::vector value-initializes and ClickHouse does not want to pay for zeroing bytes it is about to overwrite.
The array must be able to grow without copying more than amortized O(1) times — but the growth policy has to be chosen, not inherited.
SIMD code needs to be allowed to read and write past the end of the data.
Code that computes “the size of element i” from “the offset of element i” wants a -1 index that is guaranteed to be zero.

This article is about PODArray and ColumnVector, the layer where all of that comes together. Source is from ClickHouse 26.9 (04eac2ea3).

The container

PODArray is documented at the top of its own header:

cpp
// src/Common/PODArray.h:33
/** A dynamic array for POD types.
  * Designed for a small number of large arrays (rather than a lot of small ones).
  * To be more precise - for use in ColumnVector.
  * It differs from std::vector in that it does not initialize the elements.
  *
  * Made noncopyable so that there are no accidental copies. You can copy the data using `assign` method.
  *
  * Only part of the std::vector interface is supported.
  *
  * The default constructor creates an empty object that does not allocate memory.
  * Then the memory is allocated at least initial_bytes bytes.
  *
  * If you insert elements with push_back, without making a `reserve`, then PODArray is about 2.5 times faster than std::vector.
  *
  * The template parameter `pad_right` - always allocate at the end of the array as many unused bytes.
  * Can be used to make optimistic reading, writing, copying with unaligned SIMD instructions.
  *
  * The template parameter `pad_left` - always allocate memory before 0th element of the array (rounded up to the whole number of elements)
  *  and zero initialize -1th element. It allows to use -1th element that will have value 0.
  * This gives performance benefits when converting an array of offsets to array of sizes.

That comment is the whole design brief. Let the pieces land one at a time.

Noncopyable

cpp
// src/Common/PODArray.h:99
template <size_t ELEMENT_SIZE, size_t initial_bytes, typename TAllocator, size_t pad_right_, size_t pad_left_>
class PODArrayBase : private boost::noncopyable, private TAllocator    /// empty base optimization
{

The boost::noncopyable private base is not decoration. A Column in ClickHouse is copy-on-write: ColumnPtr is an immutable, refcounted pointer, and mutation happens by cloning first. If the underlying array were copyable, someone would eventually copy one by accident and silently double a column’s memory. Making the array noncopyable pushes every copy through the explicit assign path, where the intent is visible.

The private TAllocator is the other half of that line: the allocator is a base class, not a member, so the array’s object size does not grow with the allocator’s state. The comment in the header explains why:

cpp
// src/Common/PODArray.h:58
  * Why Allocator is not passed through constructor, as it is done in C++ standard library?
  * Because sometimes we have many small objects, that share same allocator with same parameters,
  *  and we must avoid larger object size due to storing the same parameters in each object.
  *  This is required for states of aggregate functions.

Three pointers, not a size and a capacity

The array is three raw pointers:

cpp
// src/Common/PODArray.h:119
    char * c_start          = null;    /// Does not include pad_left.
    char * c_end            = null;
    char * c_end_of_storage = null;    /// Does not include pad_right.

and the accessors are arithmetic on them:

cpp
// src/Common/PODArray.h:227
public:
    bool empty() const { return c_end == c_start; }
    size_t size() const { return (c_end - c_start) / ELEMENT_SIZE; }
    size_t capacity() const { return (c_end_of_storage - c_start) / ELEMENT_SIZE; }

    /// This method is safe to use only for information about memory usage.
    size_t allocated_bytes() const { return c_end_of_storage - c_start + pad_right + pad_left; } /// NOLINT

    void clear() { c_end = c_start; }

size() is a subtraction and a division by a compile-time constant, which the compiler turns into a shift. There is no size_ field to keep in sync, which means there is no possibility of size_ disagreeing with the data.

The empty array points at static memory

A default-constructed PODArray must not allocate. But its c_start must still be a valid pointer, because data() may be called on it, and the padding trick needs memory before the first element. The solution is a static buffer:

cpp
// src/Common/PODArray.h:66
static constexpr size_t empty_pod_array_size = 1024;
alignas(std::max_align_t) extern const char empty_pod_array[empty_pod_array_size];

cpp
// src/Common/PODArray.cpp:34
/// Used for left padding of PODArray when empty
alignas(std::max_align_t) const char empty_pod_array[empty_pod_array_size]{};

1024 bytes, zero-initialized, max_align_t-aligned, and:

cpp
// src/Common/PODArray.h:107
    /// Empty array will point to this static memory as padding and begin/end.
    static constexpr char * null = const_cast<char *>(empty_pod_array) + pad_left;

So an empty array’s c_start points 64 bytes into a static zeroed buffer, which means c_start - 1 is a valid zero byte. The empty array is not a special case in any of the arithmetic; it is a zero-length window into a shared static buffer.

That is also why the static_assert on the left padding exists:

cpp
// src/Common/PODArray.h:110
protected:
    static_assert(pad_left <= empty_pod_array_size && "Left Padding exceeds empty_pod_array_size. Is the element size too large?");
    static_assert(pad_left % ELEMENT_SIZE == 0, "pad_left must be multiple of element alignment");

The padding trick

The two padding parameters are the most unusual part of the design.

cpp
// src/Common/PODArray.h:103
    /// Round padding up to an whole number of elements to simplify arithmetic.
    static constexpr size_t pad_right = integerRoundUp(pad_right_, ELEMENT_SIZE);
    /// pad_left is also rounded up to 16 bytes to maintain alignment of allocated memory.
    static constexpr size_t pad_left = integerRoundUp(pad_left_, std::lcm(ELEMENT_SIZE, 16));

And the standard instantiation for columns uses 64 bytes on each side:

cpp
// src/Common/PODArray_fwd.h:24
/** For columns. Padding is enough to read and write xmm-register at the address of the last element. */
template <typename T, size_t initial_bytes = 4096, typename TAllocator = Allocator<false>>
using PaddedPODArray = PODArray<T, initial_bytes, TAllocator, PADDING_FOR_SIMD - 1, PADDING_FOR_SIMD>;

with

cpp
// src/Core/Defines.h:28
static constexpr auto PADDING_FOR_SIMD = 64;

So 63 bytes of right padding and 64 bytes of left padding, for every array in every column of every block. That sounds wasteful until you see what it buys.

Left padding: the `-1` element

Look at how the allocation sets it up:

cpp
// src/Common/PODArray.h:128
    template <typename ... TAllocatorParams>
    void alloc(size_t bytes, TAllocatorParams &&... allocator_params)
    {
        char * allocated = reinterpret_cast<char *>(TAllocator::alloc(bytes, std::forward<TAllocatorParams>(allocator_params)...));

        c_start = allocated + pad_left;
        c_end = c_start;
        c_end_of_storage = allocated + bytes - pad_right;

        if (pad_left)
            memset(c_start - ELEMENT_SIZE, 0, ELEMENT_SIZE);
    }

One memset of exactly one element, immediately before the first element. The element at index -1 is guaranteed to be zero.

And the subscript operator is signed to allow it:

cpp
// src/Common/PODArray.h:393
    /// The index is signed to access -1th element without pointer overflow.
    T & operator[] (ssize_t n)
    {
        /// <= size, because taking address of one element past memory range is Ok in C++ (expression like &arr[arr.size()] is perfectly valid).
        chassert((n >= (static_cast<ssize_t>(pad_left_) ? -1 : 0)) && (n <= static_cast<ssize_t>(this->size())));
        return t_start()[n];
    }

The -1 is only legal when there is left padding — the assertion encodes the precondition. Without left padding, n = -1 would be a genuine out-of-bounds read.

Now, who uses it? ColumnString:

cpp
// src/Columns/ColumnString.h:43
    size_t ALWAYS_INLINE offsetAt(ssize_t i) const { return offsets[i - 1]; }

    /// Size of i-th element
    size_t ALWAYS_INLINE sizeAt(ssize_t i) const
    {
        chassert(offsets[i] >= offsets[i - 1]);
        return offsets[i] - offsets[i - 1];
    }

offsetAt(0) reads offsets[-1], which is the zeroed element. So the offsets array of a ColumnString is a classic “one past the end” offset array where the first offset is implicitly 0, and sizeAt(i) is the difference of two adjacent offsets.

The alternative would be to store offsets as “start of element i” with an explicit offsets[0] = 0 and a separate offsets[size] sentinel, and then sizeAt(i) = offsets[i+1] - offsets[i] — which needs one more slot and would require the array to have size()+1 entries, breaking the invariant that offsets.size() == column.size().

The source even flags the trick where it is used:

cpp
// src/Columns/ColumnString.cpp:59
    const size_t src_offset = src_concrete.offsets[position - 1];
    const size_t src_buf_size
        = src_concrete.offsets[position] - src_concrete.offsets[position - 1]; /// -1th index is Ok, see PaddedPODArray.

The same trick appears in ColumnArray:

cpp
// src/Columns/ColumnArray.h:242
    size_t ALWAYS_INLINE offsetAt(ssize_t i) const { return getOffsets()[i - 1]; }
    size_t ALWAYS_INLINE sizeAt(ssize_t i) const { return getOffsets()[i] - getOffsets()[i - 1]; }

Right padding: SIMD may write past the end

Right padding exists because ClickHouse’s SIMD filters do not write exactly the number of surviving elements. They write in whole vector-width chunks and then fix up the count:

cpp
// src/Columns/ColumnVector.cpp:944
/// Writes the rows of the block at `data_pos` selected by `mask` to `res` and returns their number. Mixed blocks are compressed
/// with a table-driven byte shuffle. Up to `COMPRESS_MAX_OVERWRITE` bytes past the returned count may be written.
/// `res` may alias `data_pos` if it is not ahead of it (filtering in place): each store ends within the rows already loaded.

and the amount of possible overwrite is a compile-time constant:

cpp
// src/Columns/ColumnVector.cpp:912
/// One shuffle handles 8 rows of 1-byte elements (a 256-entry table of 16 bytes would be too large for 16 rows),
/// otherwise the rows of a 16-byte vector (32-byte for `COMPRESS_DWORDS`).
template <size_t ELEMENT_WIDTH>
constexpr size_t COMPRESS_ROWS = ELEMENT_WIDTH == 1 ? 8 : (COMPRESS_DWORDS<ELEMENT_WIDTH> ? 32 : 16) / ELEMENT_WIDTH;

/// One shuffle stores a whole vector of `COMPRESS_ROWS` elements from the current count, which can be past all selected rows.
template <size_t ELEMENT_WIDTH>
constexpr size_t COMPRESS_MAX_OVERWRITE = COMPRESS_ROWS<ELEMENT_WIDTH> * ELEMENT_WIDTH;

The padding requirement is then a static assertion:

cpp
// src/Columns/ColumnVector.cpp:1000
/// Filters whole blocks of `SIMD_ELEMENTS` rows into `res_data`.
template <typename T, typename Container, size_t SIMD_ELEMENTS>
void doFilterAlignedShuffle(const UInt8 *& filt_pos, const UInt8 *& filt_end_aligned, const T *& data_pos, Container & res_data)
{
    /// The writes of `compressBlock` past the selected rows land in the right padding, so an exact `result_size_hint` is kept.
    static_assert(Container::pad_right >= COMPRESS_MAX_OVERWRITE<sizeof(T)>);

This is the payoff of the padding design: the SIMD filter can be written without a single branch for the tail, because the buffer is guaranteed to have room for the overrun. The static_assert ties the guarantee to the code that depends on it, so the two cannot drift apart.

The same trick shows up in the small-string copy helper:

cpp
// src/Common/PODArray.h:509
    /// Works under assumption, that it's possible to read up to 15 excessive bytes after `from_end` and this PODArray is padded.
    template <typename It1, typename It2, typename ... TAllocatorParams>
    void insertSmallAllowReadWriteOverflow15(It1 from_begin, It2 from_end, TAllocatorParams &&... allocator_params)
    {
        static_assert(pad_right_ >= PADDING_FOR_SIMD - 1);
        static_assert(sizeof(T) == sizeof(*from_begin));
        insertPrepare(from_begin, from_end, std::forward<TAllocatorParams>(allocator_params)...);
        size_t bytes_to_copy = PODArrayDetails::byte_size(from_end - from_begin, sizeof(T));
        memcpySmallAllowReadWriteOverflow15(this->c_end, reinterpret_cast<const void *>(&*from_begin), bytes_to_copy);
        this->c_end += bytes_to_copy;
    }

which copies 16 bytes at a time regardless of the actual size:

cpp
// src/Common/memcpySmall.h:41
    inline void memcpySmallAllowReadWriteOverflow15Impl(char * __restrict dst, const char * __restrict src, ssize_t n)
    {
        __msan_unpoison_overflow_15(src, n);
        while (n > 0)
        {
            _mm_storeu_si128(reinterpret_cast<__m128i *>(dst),
                _mm_loadu_si128(reinterpret_cast<const __m128i *>(src)));

            dst += 16;
            src += 16;
            n -= 16;

            /// Avoid clang loop-idiom optimization, which transforms _mm_storeu_si128 to built-in memcpy
            __asm__ __volatile__("" : : : "memory");
        }
    }

Note the n -= 16 in a loop that runs until n <= 0: for a 5-byte copy it runs once and advances 16 bytes past the end. That is legal only because of the padding, and the static_assert above enforces it. The __msan_unpoison_overflow_15 call tells MemorySanitizer that the 15-byte overread is intentional, so sanitizers do not flag it.

The growth policy

There are three different growth behaviours in PODArray, and choosing between them is a deliberate decision at each call site.

`reserve`: round up to a power of two

cpp
// src/Common/PODArray.h:237
    template <typename ... TAllocatorParams>
    ALWAYS_INLINE void reserve(size_t n, TAllocatorParams &&... allocator_params)
    {
        if (n > capacity())
            reallocPowerOfTwoElements(n, std::forward<TAllocatorParams>(allocator_params)...);
    }

which rounds the element count up to a power of two:

cpp
// src/Common/PODArray.h:200
    template <typename ... TAllocatorParams>
    NO_INLINE void reallocPowerOfTwoElements(size_t n, TAllocatorParams &&... allocator_params)
    {
        realloc(roundUpToPowerOfTwoOrZero(PODArrayDetails::minimum_memory_for_elements(n, ELEMENT_SIZE, pad_left, pad_right)), std::forward<TAllocatorParams>(allocator_params)...);
    }

The rounding helper is a one-liner:

cpp
// src/Common/BitHelpers.h:15
inline size_t roundUpToPowerOfTwoOrZero(size_t n)
{
    // if MSB is set, return n, to avoid return zero
    if (unlikely(n >= 0x8000000000000000ULL))
        return n;
    else if (n <= 1)
        return n;

and the comment explains the clzll/clzl choice, which is a nice example of a portability trap being closed with a comment rather than a bug report:

cpp
// src/Common/BitHelpers.h:23
    /// `clzll`, not `clzl`: the argument is a 64-bit `size_t`, as the hardcoded 64 and the
    /// `0x8000000000000000ULL` above both assume, but `unsigned long` - what `clzl` takes - is
    /// only 64-bit wide on LP64 platforms. On an LLP64 one it is 32, and the argument would be
    /// truncated. `clzll` is at least 64 bits everywhere.

`reserve_exact`: exactly what was asked for

cpp
// src/Common/PODArray.h:244
    template <typename ... TAllocatorParams>
    void reserve_exact(size_t n, TAllocatorParams &&... allocator_params) /// NOLINT
    {
        if (n > capacity())
            realloc(PODArrayDetails::minimum_memory_for_elements(n, ELEMENT_SIZE, pad_left, pad_right), std::forward<TAllocatorParams>(allocator_params)...);
    }

This is the one that surprises people. ColumnVector::reserve uses reserve_exact, not reserve:

cpp
// src/Columns/ColumnVector.h:182
    void reserve(size_t n) override
    {
        data.reserve_exact(n);
    }

    size_t capacity() const override
    {
        return data.capacity();
    }

    void shrinkToFit() override
    {
        data.shrink_to_fit();
    }

Why would a column reserve exactly? Because a column’s final size is usually known in advance. When ClickHouse reads a MergeTree granule it knows how many rows the granule has; when it deserializes a Block from the wire it knows the row count. Rounding up to a power of two would waste up to 50% of the memory on every column in every block — and a block with 50 columns of 65 536 rows each would waste tens of megabytes.

The shrinkToFit override exists for the case where the size was not known in advance: after the block is fully built, the over-allocation is returned.

The same policy shows up in ColumnString:

cpp
// src/Columns/ColumnString.cpp:636
void ColumnString::reserve(size_t n)
{
    offsets.reserve_exact(n);
}

and in ColumnFixedString, which reserves in characters:

cpp
// src/Columns/ColumnFixedString.h:197
    void reserve(size_t size) override
    {
        chars.reserve_exact(n * size);
    }

`push_back`: double the allocation

The third policy is the incremental one:

cpp
// src/Common/PODArray.h:442
    template <typename U, typename ... TAllocatorParams>
    void push_back(U && x, TAllocatorParams &&... allocator_params) /// NOLINT
    {
        if (unlikely(this->c_end + sizeof(T) > this->c_end_of_storage))
            this->reserveForNextSize(std::forward<TAllocatorParams>(allocator_params)...);
        new (reinterpret_cast<void*>(t_end())) T(std::forward<U>(x));
        this->c_end += sizeof(T);
    }

and the growth itself:

cpp
// src/Common/PODArray.h:185
    template <typename ... TAllocatorParams>
    NO_INLINE void reserveForNextSize(TAllocatorParams &&... allocator_params)
    {
        if (empty())
        {
            // The allocated memory should be multiplication of ELEMENT_SIZE to hold the element, otherwise,
            // memory issue such as corruption could appear in edge case.
            realloc(std::max(integerRoundUp(initial_bytes, ELEMENT_SIZE),
                             PODArrayDetails::minimum_memory_for_elements(1, ELEMENT_SIZE, pad_left, pad_right)),
                    std::forward<TAllocatorParams>(allocator_params)...);
        }
        else
            realloc(allocated_bytes() * 2, std::forward<TAllocatorParams>(allocator_params)...);
    }

Three details worth noting:

The growth is allocated_bytes() * 2 — doubling the bytes, including the padding. So the element capacity grows by slightly more than 2× when the element is small relative to the 127 bytes of padding.
The first allocation is initial_bytes (4096 for column arrays), not one element. So a column that gets a handful of rows still allocates 4 KB — but only once, and initial_bytes is the minimum, so it is paid once per column, not per row.
reserveForNextSize is NO_INLINE. The comment above it explains why:

cpp
// src/Common/PODArray.h:183
    /// NO_INLINE functions for slow paths of otherwise fast small inlinable functions.

The realloc path is cold; inlining it into push_back would bloat every caller.

The “shrink if less than half used” trick

One more policy lives in ColumnAggregateFunction, and it is a good illustration of the trade-off. When you filter a column, you know approximately how many rows will survive, so you can reserve exactly. But if the filter is much more selective than the hint, you are left with a huge buffer holding a few elements:

cpp
// src/Columns/ColumnAggregateFunction.cpp:335
    auto res = createView();
    auto & res_data = res->data;

    if (result_size_hint)
        res_data.reserve_exact(result_size_hint > 0 ? result_size_hint : size);

    for (size_t i = 0; i < size; ++i)
        if (filter[i])
            res_data.push_back(data[i]);

    /// To save RAM in case of too strong filtering.
    if (res_data.size() * 2 < res_data.capacity())
        res_data = Container(res_data.cbegin(), res_data.cend());

The check size * 2 < capacity means “if less than half the buffer is used, copy it into a tight one”. The copy costs O(size) and is worth it when it frees more than half the buffer.

ColumnVector::filter does the same thing, but with a SIMD path that reserves based on the hint:

cpp
// src/Columns/ColumnVector.cpp:1046
    auto res = this->create();
    Container & res_data = res->getData();

    if (result_size_hint)
        res_data.reserve_exact(result_size_hint > 0 ? result_size_hint : size);

`ColumnVector`: the typed array

With the container settled, ColumnVector is a thin wrapper:

cpp
// src/Columns/ColumnVector.h:39
public:
    using ValueType = T;
    using Container = PaddedPODArray<ValueType>;

private:
    ColumnVector() = default;
    explicit ColumnVector(const size_t n) : data(n) {}
    ColumnVector(const size_t n, const ValueType x) : data(n, x) {}
    ColumnVector(const ColumnVector & src) : data(src.data.begin(), src.data.end()) {}
    ColumnVector(Container::const_iterator begin, Container::const_iterator end) : data(begin, end) { }

Note that the copy constructor of ColumnVector copies the data explicitly, element by element, rather than memcpy’ing the whole buffer. That looks wasteful, and it is — but ColumnVector is copy-on-write at the IColumn level, so the copy constructor is only reached when someone genuinely wants a copy, and the element-by-element copy lets the compiler vectorize it. PaddedPODArray is noncopyable, so this constructor is the only way to copy one, and it is not accidental.

The interesting part is what ColumnVector exposes to code that wants to avoid virtual dispatch:

cpp
// src/Columns/ColumnVector.h:335
    /** More efficient methods of manipulation - to manipulate with data directly. */
    Container & getData()
    {
        return data;
    }

    const Container & getData() const
    {
        return data;
    }

    const T & getElement(size_t n) const
    {
        return data[n];
    }

    T & getElement(size_t n)
    {
        return data[n];
    }

protected:
    Container data;

getData() hands out the raw PaddedPODArray, so a caller that has already established that the column is a ColumnVector<UInt64> can read data.data()[i] directly with no virtual call, no bounds check, and no per-element function call.

This is the pattern that ClickHouse uses throughout: the IColumn interface is for structural operations (filter, permute, serialize), and the concrete class exposes its guts for the data operations. A typical aggregation function does one checkAndGetColumn<ColumnVector<UInt64>>() and then runs a monomorphic loop over getData().

`insertRangeFrom`: memcpy, not a loop

cpp
// src/Columns/ColumnVector.cpp:746
template <typename T>
#if !defined(DEBUG_OR_SANITIZER_BUILD)
void ColumnVector<T>::insertRangeFrom(const IColumn & src, size_t start, size_t length)
#else
void ColumnVector<T>::doInsertRangeFrom(const IColumn & src, size_t start, size_t length)
#endif
{
    const ColumnVector & src_vec = assert_cast<const ColumnVector &>(src);

    if (start > src_vec.data.size() || length > src_vec.data.size() - start)
        throwInsertRangeFromOutOfBound("ColumnVector<T>", start, length, src_vec.data.size());

    size_t old_size = data.size();
    data.resize(old_size + length);
    memcpy(data.data() + old_size, &src_vec.data[start], length * sizeof(data[0]));
}

Two things here. First, data.resize(...) — and PODArray::resize does not initialize:

cpp
// src/Common/PODArray.h:251
    template <typename ... TAllocatorParams>
    void resize(size_t n, TAllocatorParams &&... allocator_params)
    {
        reserve(n, std::forward<TAllocatorParams>(allocator_params)...);
        resize_assume_reserved(n);
    }

cpp
// src/Common/PODArray.h:271
    void resize_assume_reserved(const size_t n) /// NOLINT
    {
        c_end = c_start + PODArrayDetails::byte_size(n, ELEMENT_SIZE);
    }

So resize just moves c_end. No zeroing, no element construction. The memcpy then fills the region. Compare with resize_fill:

cpp
// src/Common/PODArray.h:419
    /// Same as resize, but zeroes new elements.
    void resize_fill(size_t n) /// NOLINT
    {
        size_t old_size = this->size();
        if (n > old_size)
        {
            this->reserve(n);
            memset(this->c_end, 0, PODArrayDetails::byte_size(n - old_size, sizeof(T)));
        }
        this->c_end = this->c_start + PODArrayDetails::byte_size(n, sizeof(T));
    }

ColumnVector uses resize_fill where the values matter:

cpp
// src/Columns/ColumnVector.h:70
    void insertManyFrom(const IColumn & src, size_t position, size_t length) override
    {
        ValueType v = assert_cast<const Self &>(src).getData()[position];
        data.resize_fill(data.size() + length, v);
    }

Second, insertRangeFrom does not call push_back in a loop. It does one resize and one memcpy. That is only possible because the destination is a flat array of the same element type — the whole reason for the ColumnVector design.

`insertRawUninitialized`: writing into the column’s memory directly

There is an even more aggressive version of this, used by the Parquet reader and the hash-join builder. The column grows by n elements and hands back a pointer to the new region, so the caller can decompress straight into it:

cpp
// src/Columns/ColumnVector.cpp:1528
template <typename T>
std::span<char> ColumnVector<T>::insertRawUninitialized(size_t count)
{
    size_t start = data.size();
    data.resize(start + count);
    return {reinterpret_cast<char *>(data.data() + start), count * sizeof(T)};
}

The interface says what it is for:

cpp
// src/Columns/IColumn.h:928
    /// Appends n elements with unspecified values and returns a span pointing to their memory range.
    /// Can be used to decompress or deserialize data directly into the column.
    /// Supported only for simple column types like ColumnVector and ColumnFixedString.
    [[nodiscard]] virtual std::span<char> insertRawUninitialized(size_t count);

This is the “external buffer” trick in modern ClickHouse form: instead of decompressing into a temporary buffer and then copying into the column, the decoder writes into the column. One copy instead of two.

The Nullable case does it for both halves at once:

cpp
// src/Interpreters/HashJoin/gatherJoinOutputColumns.cpp:407
            const std::span<char> null_span = dst.getNullMapColumn().insertRawUninitialized(count);
            const std::span<char> value_span = dst.getNestedColumn().insertRawUninitialized(count);

`ColumnString`: offsets plus a flat character buffer

ColumnString is the same idea, extended to variable-length data. Two arrays:

cpp
// src/Columns/ColumnString.h:34
private:
    friend class COWHelper<IColumnHelper<ColumnString>, ColumnString>;

    /// Maps i'th position to offset to i+1'th element. Last offset maps to the end of all chars (is the size of all chars).
    Offsets offsets;

    /// Bytes of strings, placed contiguously. Note that strings are not zero-terminated and could contain zero bytes in the middle.
    Chars chars;

Note the comment on chars: strings are not zero-terminated. The length comes entirely from the offsets. And the offsets array holds size()+1 entries conceptually — the last one is the end of the character buffer — but because of the -1 trick, the stored array has only size() entries and the implicit offsets[-1] == 0 provides the first one.

The layout for three strings:

text

   offsets:  [ 0,  5,  6, 11 ]        (implicit offsets[-1] = 0)
   chars:    [ 'H','e','l','l','o', ',', 'W','o','r','l','d' ]

   string 0 = chars[offsets[-1] .. offsets[0]) = chars[0..5)  = "Hello"
   string 1 = chars[offsets[0]  .. offsets[1]) = chars[5..6)  = ","
   string 2 = chars[offsets[1]  .. offsets[2]) = chars[6..11) = "World"

Reading a row is two array reads and a subtraction:

cpp
// src/Columns/ColumnString.h:118
    std::string_view getDataAt(size_t n) const override
    {
        chassert(n < size());
        return std::string_view(reinterpret_cast<const char *>(&chars[offsetAt(n)]), sizeAt(n));
    }

No pointer to chase, no per-string allocation, no length prefix in the character buffer. The whole column is two contiguous allocations.

Bulk insertion

Copying a range of strings is one memcpy per string plus one pass over the offsets:

cpp
// src/Columns/ColumnString.cpp:58
    const ColumnString & src_concrete = assert_cast<const ColumnString &>(src);
    const size_t src_offset = src_concrete.offsets[position - 1];
    const size_t src_buf_size
        = src_concrete.offsets[position] - src_concrete.offsets[position - 1]; /// -1th index is Ok, see PaddedPODArray.

    const size_t old_rows = offsets.size();
    const size_t new_rows = old_rows + length;
    /// Reserve offsets before changing chars to keep the column consistent if allocation fails.
    offsets.reserve(new_rows);

    const size_t old_size = chars.size();
    const size_t new_size = old_size + src_buf_size * length;
    chars.resize(new_size);

    const UInt8 * src_buf = &src_concrete.chars[src_offset];

    offsets.resize_assume_reserved(new_rows);

    for (size_t current_offset = old_size; current_offset < new_size; current_offset += src_buf_size)
        memcpySmallAllowReadWriteOverflow15(&chars[current_offset], src_buf, src_buf_size);

    for (size_t i = 0, current_offset = old_size + src_buf_size; i < length; ++i, current_offset += src_buf_size)
        offsets[old_rows + i] = current_offset;

Note the ordering, and the comment explaining it: offsets.reserve happens before chars is modified, so that if the allocation fails the column is still consistent. And chars.resize does not initialize — the memcpySmallAllowReadWriteOverflow15 calls fill it.

Note also that the offsets are written after the characters. That ordering means the offsets array is never in a state where it points past the end of the character buffer, even transiently.

`ColumnFixedString`: the inline variant

FixedString(N) is the degenerate case where every value has the same length, so no offsets array is needed at all — just a flat character buffer of N * size bytes:

cpp
// src/Columns/ColumnFixedString.h:26
private:
    /// Bytes of strings, laid in succession. The strings are stored without a trailing zero byte.
    /** NOTE It is required that the offset and type of chars in the object be the same as that of `data in ColumnUInt8`.
      * Used in `packFixed` function (AggregationCommon.h)
      */
    Chars chars;
    /// The size of the rows.
    const size_t n;

The comment is a constraint on the representation: ColumnFixedString’s buffer must have exactly the same layout as a ColumnUInt8’s, so that generic code can reinterpret one as the other. That is what lets ColumnFixedSizeHelper do this:

cpp
// src/Columns/ColumnFixedSizeHelper.h:31
    template <size_t ELEMENT_SIZE>
    const char * getRawDataBegin() const
    {
        return reinterpret_cast<const PODArrayBase<ELEMENT_SIZE, 4096, Allocator<false>, PADDING_FOR_SIMD - 1, PADDING_FOR_SIMD> *>(
                   reinterpret_cast<const char *>(this) + sizeof(*this))
            ->raw_data();
    }

The class exists so that this downcast is technically legal:

cpp
// src/Columns/ColumnFixedSizeHelper.h:11
/** Allows to access internal array of fixed-size column without cast to concrete type.
  * We will inherit ColumnVector and ColumnFixedString from this class instead of IColumn.
  * Assumes data layout of ColumnVector, ColumnFixedString and PODArray.
  *
  * Why it is needed?
  *
  * There are some algorithms that specialize on the size of data type but doesn't care about concrete type.
  * The same specialization may work for UInt64, Int64, Float64, FixedString(8), if it only does byte moving and hashing.
  * To avoid code bloat and compile time increase, we can use single template instantiation for these cases
  *  and just static_cast pointer to some single column type (e. g. ColumnUInt64) assuming that all types have identical memory layout.
  *
  * But this static_cast (downcast to unrelated type) is illegal according to the C++ standard and UBSan warns about it.
  * To allow functional tests to work under UBSan we have to separate some base class that will present the memory layout in explicit way,
  *  and we will do static_cast to this class.
  */

That is a lovely piece of engineering commentary: the constraint is documented, the workaround is a dedicated base class, and the reason is UBSan.

The n is fixed at construction and the buffer is sized in n-byte units:

cpp
// src/Columns/ColumnFixedString.h:55
    size_t size() const override
    {
        return chars.size() / n;
    }

with the trailing-zero-byte question resolved by the serializer rather than the column: the in-memory buffer holds exactly n bytes per row with no terminator, and shorter strings are zero-padded on the way in:

cpp
// src/Columns/ColumnFixedString.cpp:117
void ColumnFixedString::insertData(const char * pos, size_t length)
{
    if (length > n)
        throw Exception(ErrorCodes::TOO_LARGE_STRING_SIZE, "Too large string for FixedString column");

    size_t old_size = chars.size();
    chars.resize(old_size + n);
    memcpy(chars.data() + old_size, pos, length);
    memset(chars.data() + old_size + length, 0, n - length);
}

`ColumnNullable`: the null map as a separate column

Nullable(T) is a T column plus a ColumnUInt8 of the same length. The comment gives the reasoning:

cpp
// src/Columns/ColumnNullable.h:19
/// Class that specifies nullable columns. A nullable column represents
/// a column, which may have any type, provided with the possibility of
/// storing NULL values. For this purpose, a ColumNullable object stores
/// an ordinary column along with a special column, namely a byte map,
/// whose type is ColumnUInt8. The latter column indicates whether the
/// value of a given row is a NULL or not. Such a design is preferred
/// over a bitmap because columns are usually stored on disk as compressed
/// files. In this regard, using a bitmap instead of a byte map would
/// greatly complicate the implementation with little to no benefits.

That is the whole design decision: a bitmap would be 8× smaller in RAM, but columns are stored compressed, and a byte map of mostly zeros compresses just as well as a bitmap while remaining a perfectly ordinary column that can be filtered, compressed and serialized by the generic machinery.

The two members are independent columns, each with its own lifecycle:

cpp
// src/Columns/ColumnNullable.h:263
private:
    WrappedPtr nested_column;
    WrappedPtr null_map;

and reading a row is a lookup in each:

cpp
// src/Columns/ColumnNullable.h:55
    size_t size() const final { return assert_cast<const ColumnUInt8 &>(*null_map).size(); }
    bool isNullAt(size_t n) const final { return assert_cast<const ColumnUInt8 &>(*null_map).getData()[n] != 0;}

Note that size() is defined by the null map, not the nested column. The null map is the authoritative row count.

There is a subtle point about what lives in the nested column under a NULL. The convention is that the value is undefined — it is present, but meaningless. The code makes that explicit in the one place where it matters:

cpp
// src/Columns/ColumnNullable.cpp:995
    if (isNullAt(0))
    {
        /// Value in main column, when null map is 1 is implementation defined. So, take any value.
        new_values = nested_column->createWithOffsets(offsets, *createColumnConstWithDefaultValue(nested_column), total_rows, shift);

So “nullable” is implemented as “a value column plus a parallel byte column”, and the value column is not branch-free — reading a nullable value always requires a branch on the null map.

Trade-offs

What the flat-array design buys you.

Every column is one or two contiguous allocations. Scans are sequential memory reads that the prefetcher handles perfectly. There is no per-row indirection, so a SELECT sum(x) FROM t on a UInt64 column is a linear sweep over memory at memory bandwidth.

The offsets+chars layout for strings means a string column is also a linear sweep: the character buffer is contiguous, and the offsets are a separate dense UInt64 array. This is also why ClickHouse’s string compression works so well — the LZ4 compressor sees a long run of human-readable bytes.

What it costs you.

The PaddedPODArray pays 127 bytes of padding per array. For a column of UInt8 with 1000 rows that is 12% overhead. For a column with a million rows it is nothing. The design assumes large columns, which is exactly what the header comment says: “Designed for a small number of large arrays (rather than a lot of small ones).”

The -1 element trick means offsets and offsets[-1] are both live data, and the invariant that offsets[-1] == 0 is maintained by a single memset at allocation time. It is checked nowhere. If a future change ever wrote to c_start - ELEMENT_SIZE, every string in the column would silently shift.

The reserve_exact policy for columns is a bet that the row count is known in advance. When it is not, the array over-allocates by up to 2×, and the ColumnAggregateFunction shrink trick exists to clean that up after the fact. The right fix is to know the size; the fallback is a copy.

The design decision that makes it work. PODArray refuses to initialize its elements, and then makes up for it with padding that guarantees the absence of initialization bugs: 63 bytes on the right so that SIMD can overrun, 64 bytes on the left with a zeroed element at index -1 so that offset arithmetic needs no special case. The result is a container where the fastest code paths — memcpy ranges, SIMD filters, unaligned vector copies — are also the simplest code paths, because the padding has already paid for the slack they need.

The container

Noncopyable

Three pointers, not a size and a capacity

The empty array points at static memory

The padding trick

Left padding: the -1 element

Right padding: SIMD may write past the end

The growth policy

reserve: round up to a power of two

reserve_exact: exactly what was asked for

push_back: double the allocation

The “shrink if less than half used” trick

ColumnVector: the typed array

insertRangeFrom: memcpy, not a loop

insertRawUninitialized: writing into the column’s memory directly

ColumnString: offsets plus a flat character buffer