Opensource internals

How ClickHouse's Sparse Column Stores Only the Rows That Differ

20 min read Jay Hubbert

ColumnSparse keeps a values column plus a sorted offsets array of non-default row positions, and its serializer encodes offsets as run-length groups of default rows.

Real columns are mostly default. A status column is 'active' for 98% of rows and '' for the rest. A retries column is 0 almost always. An amount column that is Nullable is NULL for most rows and non-null for a handful.

Storing all those zeros is paying for bytes you could have described in one sentence. ClickHouse has two answers to this, and they live in different layers:

  • ColumnNullable keeps a separate byte-per-row null map next to the value column. The values are still all there; the null map says which ones to ignore.
  • ColumnSparse keeps only the non-default values plus a sorted array of the row positions where they live. The default values are not stored at all — they are implied.

ColumnSparse is the more aggressive of the two, and it is the more interesting one, because the offsets array is not a list of positions but a run-length encoding of gaps, and the whole thing has to survive being filtered, permuted, replicated and merged.

This article is about ColumnSparse and its serializer, in ClickHouse 26.9 (04eac2ea3).

The layout

The header comment says it in four lines:

cpp 
// src/Columns/ColumnSparse.h:13
/** Column for spare representation.
 *  It stores column with non-default values and column
 *  with their sorted positions in original column. Column with
 *  values contains also one default value at 0 position to make
 *  implementation of execution of functions and sorting more convenient.
 */

and the members:

cpp 
// src/Columns/ColumnSparse.h:268
    /// Contains default value at 0 position.
    /// It's convenient, because it allows to execute, e.g functions or sorting,
    /// for this column without handling different cases.
    WrappedPtr values;

    /// Sorted offsets of non-default values in the full column.
    /// 'offsets[i]' corresponds to 'values[i + 1]'.
    WrappedPtr offsets;
    size_t _size; /// NOLINT

So the invariant is precise: offsets[i] is the row number of the value stored at values[i + 1]. values[0] is always the default value, and is never referenced by an offset.

A worked example. A UInt32 column of 10 rows where only rows 2, 5 and 9 are non-zero:

text 
   row:      0    1    2    3    4    5    6    7    8    9
   value:    0    0   17    0    0   42    0    0    0   99

   values:  [ 0, 17, 42, 99 ]          <- values[0] is the default
   offsets: [ 2,  5,  9 ]             <- offsets[i] -> values[i+1]
   _size:   10

To read row n you binary-search offsets for n:

cpp 
// src/Columns/ColumnSparse.cpp:975
size_t ColumnSparse::getValueIndex(size_t n) const
{
    chassert(n < _size);

    const auto & offsets_data = getOffsetsData();
    const auto * it = std::lower_bound(offsets_data.begin(), offsets_data.end(), n);
    if (it == offsets_data.end() || *it != n)
        return 0;

    return it - offsets_data.begin() + 1;
}

getValueIndex returns 0 for a default row (meaning “use values[0]”) and i+1 otherwise. The header documents the cost:

cpp 
// src/Columns/ColumnSparse.h:186
    /// Return position of element in 'values' columns,
    /// that corresponds to n-th element of full column.
    /// O(log(offsets.size())) complexity,
    size_t getValueIndex(size_t n) const;

So random access to a sparse column is a binary search — O(log k) where k is the number of non-default values — plus one indirection into the values column. For a column with 2% non-default rows in a million-row block, that is 20 comparisons instead of a single array index. That is the price of the encoding, and it is why ColumnSparse is a storage optimization that the query layer tries to peel off before doing real work.

The constructor enforces the invariant

The invariants are checked at construction, not just assumed:

cpp 
// src/Columns/ColumnSparse.cpp:35
ColumnSparse::ColumnSparse(MutableColumnPtr && values_, MutableColumnPtr && offsets_, size_t size_)
    : values(std::move(values_)), offsets(std::move(offsets_)), _size(size_)
{
    const ColumnUInt64 * offsets_concrete = typeid_cast<const ColumnUInt64 *>(offsets.get());

    if (!offsets_concrete)
        throw Exception(ErrorCodes::LOGICAL_ERROR, "'offsets' column must be a ColumnUInt64, got: {}", offsets->getName());

    /// 'values' should contain one extra element: default value at 0 position.
    if (offsets->size() + 1 != values->size())
        throw Exception(ErrorCodes::LOGICAL_ERROR,
            "Values size ({}) is inconsistent with offsets size ({})", values->size(), offsets->size());

    if (_size < offsets->size())
        throw Exception(ErrorCodes::LOGICAL_ERROR,
            "Size of sparse column ({}) cannot be lower than number of non-default values ({})", _size, offsets->size());

    if (!offsets_concrete->empty() && _size <= offsets_concrete->getData().back())
        throw Exception(ErrorCodes::LOGICAL_ERROR,
            "Size of sparse column ({}) should be greater than last position of non-default value ({})",
                _size, offsets_concrete->getData().back());

#ifdef DEBUG_OR_SANITIZER_BUILD
    const auto & offsets_data = getOffsetsData();
    const auto * it = std::adjacent_find(offsets_data.begin(), offsets_data.end(), std::greater_equal<>());
    if (it != offsets_data.end())
        throw Exception(ErrorCodes::LOGICAL_ERROR, "Offsets of ColumnSparse must be strictly sorted");
#endif
}

Note the asymmetry: the size checks run in release builds, but the strictly sorted check is debug-only (#ifdef DEBUG_OR_SANITIZER_BUILD), because it is O(n) and a sortedness violation would already have produced garbage from the binary search.

Inserting

Insertion is where the “values[0] is the default” convention pays off. You insert the value into the values column and then decide whether to keep it:

cpp 
// src/Columns/ColumnSparse.cpp:152
void ColumnSparse::insertSingleValue(const Inserter & inserter)
{
    inserter(*values);

    size_t last_idx = values->size() - 1;
    if (values->isDefaultAt(last_idx))
        values->popBack(1);
    else
        getOffsetsData().push_back(_size);

    ++_size;
}

That is the whole trick in six lines: append the value, and if it turned out to be the default, pop it back and do not record an offset. Otherwise record the row number. The values column therefore only ever contains non-default values (plus the sentinel at index 0), and the offsets array is strictly increasing by construction.

Note that isDefaultAt is the type’s notion of default — for UInt32 it is “equals zero”, for String it is “empty”, for Nullable it is “NULL”:

cpp 
// src/Columns/ColumnVector.h:292
    bool isDefaultAt(size_t n) const override
    {
        if constexpr (is_floating_point<T>)
        {
            /// For floating-point types, use bit_cast to compare raw bit patterns instead of
            /// arithmetic equality. IEEE 754 defines -0.0 == +0.0, so the arithmetic check
            /// would incorrectly treat -0.0 as the default value, losing the sign on
            /// deserialization. Comparing bits directly distinguishes the two: +0.0 is
            /// all-zero bits, while -0.0 has its sign bit set.
            ///
            /// std::conditional_t selects an unsigned integer type of the same size as T,
            /// satisfying the requirement of std::bit_cast that both types have equal size.
            /// Unsigned integers are chosen because their value equals their bit pattern,
            /// making the comparison to 0 unambiguous.
            using Bits = std::conditional_t<sizeof(T) == 2, UInt16,
                         std::conditional_t<sizeof(T) == 4, UInt32, UInt64>>;
            return std::bit_cast<Bits>(data[n]) == 0;
        }
        else
        {
            return data[n] == T{};
        }
    }

That -0.0 handling is a nice detail: for floating-point columns the default check is a bit comparison, not an arithmetic one, so that -0.0 is not mistaken for 0.0 and its sign survives a round trip.

The iterator: amortized O(1) sequential access

The binary search is fine for random access, but a scan over a sparse column should not do a binary search per row. The Iterator class exists for that, and it maintains two cursors — the current row and the current offset:

cpp 
// src/Columns/ColumnSparse.h:206
    /// This class helps to iterate over all values in ColumnSparse.
    class Iterator
    {
    public:
        Iterator(const PaddedPODArray<UInt64> & offsets_, size_t size_, size_t current_offset_, size_t current_row_)
            : offsets(offsets_), offsets_size(offsets.size()), size(size_), current_offset(current_offset_), current_row(current_row_)
        {
        }

        bool ALWAYS_INLINE isDefault() const { return current_offset == offsets_size || current_row != offsets[current_offset]; }
        size_t ALWAYS_INLINE getValueIndex() const { return isDefault() ? 0 : current_offset + 1; }
        size_t ALWAYS_INLINE getCurrentRow() const { return current_row; }
        size_t ALWAYS_INLINE getCurrentOffset() const { return current_offset; }
        size_t ALWAYS_INLINE increaseCurrentRow() const { return ++current_row; }
        size_t ALWAYS_INLINE increaseCurrentOffset() const { return ++current_offset; }

        /// Moves the iterator forward to the given row, which must not be behind the current one.
        /// Amortized constant time when the visited rows are increasing.
        void ALWAYS_INLINE advanceToRow(size_t row)
        {
            while (current_offset < offsets_size && offsets[current_offset] < row)
                ++current_offset;
            current_row = row;
        }

advanceToRow walks the offsets array forward, never backward, so a monotonically increasing scan is O(rows + offsets) in total, not O(rows log offsets). This is the standard “galloping cursor” pattern.

On disk: the offsets become run-length groups

The in-memory representation stores each non-default row’s position explicitly. On disk, that is wasteful: a million rows with 2% non-default values would store 20 000 absolute positions, when what you really want to say is “200 default rows, then a value, then 300 default rows, then a value, …”.

That is what serializeOffsets does:

cpp 
// src/DataTypes/Serializations/SerializationSparse.cpp:70
void serializeOffsets(const IColumn::Offsets & offsets, WriteBuffer & ostr, size_t start, size_t end)
{
    size_t size = offsets.size();
    for (size_t i = 0; i < size; ++i)
    {
        size_t group_size = offsets[i] - start;
        writeVarUInt(group_size, ostr);
        start += group_size + 1;
    }

    size_t group_size = start < end ? end - start : 0;
    group_size |= END_OF_GRANULE_FLAG;
    writeVarUInt(group_size, ostr);
}

Read that carefully. For each non-default row it writes the number of default rows that precede it (offsets[i] - start), and then advances start past that value too (start += group_size + 1). At the end it writes the trailing run of default rows with a special flag bit set.

The flag is bit 62:

cpp 
// src/DataTypes/Serializations/SerializationSparse.cpp:43
{

/// 2^62, because VarInt supports only values < 2^63.
constexpr auto END_OF_GRANULE_FLAG = 1ULL << 62;

Because the offsets are VarInt-encoded, the values are small and the whole offsets stream for a 2%-sparse million-row column is a few kilobytes of VarInts, most of them one or two bytes long.

Decoding it

The decoder has to be resumable, because a read may stop in the middle of a group — the reader asked for limit rows and the group runs past it. The state carries the leftovers:

cpp 
// src/DataTypes/Serializations/SerializationSparse.cpp:48
struct DeserializeStateSparse : public ISerialization::DeserializeBinaryBulkState
{
    /// Number of default values, that remain from previous read.
    size_t num_trailing_defaults = 0;
    /// Do we have non-default value after @num_trailing_defaults?
    bool has_value_after_defaults = false;
    ISerialization::DeserializeBinaryBulkStatePtr nested;

    void reset()
    {
        num_trailing_defaults = 0;
        has_value_after_defaults = false;
    }

and the main loop:

cpp 
// src/DataTypes/Serializations/SerializationSparse.cpp:125
    size_t group_size = 0;
    while (!istr.eof())
    {
        readVarUInt(group_size, istr);

        bool end_of_granule = group_size & END_OF_GRANULE_FLAG;
        group_size &= ~END_OF_GRANULE_FLAG;

        size_t next_total_rows = total_rows + group_size;
        group_size += num_trailing_defaults;

        if (unlikely(next_total_rows >= limit))
        {
            /// If it was not last group in granule,
            /// we have to add current non-default value at further reads.
            state.num_trailing_defaults = next_total_rows - limit;
            state.has_value_after_defaults = !end_of_granule;
            return limit;
        }

        if (unlikely(end_of_granule))
        {
            has_value_after_defaults = false;
            num_trailing_defaults = group_size;
        }
        else
        {
            /// If we add value to column for first time in current read,
            /// start from column's current size, because it can have some defaults after last offset,
            /// otherwise just start from previous offset.
            /// After the first push `first` is false and `offsets` is non-empty, so the
            /// `!offsets.empty()` guard from the original is redundant and dropped here.
            size_t start_of_group = first ? start : offsets.back() + 1;
            offsets.push_back(start_of_group + group_size);
            first = false;

            num_trailing_defaults = 0;
            ++next_total_rows;
        }

        total_rows = next_total_rows;
    }

The two state variables handle the two ways a read can be cut short:

  • num_trailing_defaults — the read stopped in the middle of a run of default rows. Those defaults belong to the next read.
  • has_value_after_defaults — the read stopped exactly at a boundary where a non-default value is pending. The next read has to emit it.

Both are stored in the serialization state, not on the stack, precisely so that a partial read can be resumed later.

The decoder also reserves space for the offsets array using a prior guess:

cpp 
// src/DataTypes/Serializations/SerializationSparse.cpp:109
    /// Just try to guess number of offsets.
    offsets.reserve(offsets.size()
        + static_cast<size_t>(static_cast<double>(limit) * (1.0 - ColumnSparse::DEFAULT_RATIO_FOR_SPARSE_SERIALIZATION)));

using the constant

cpp 
// src/Columns/ColumnSparse.h:29
    static constexpr auto DEFAULT_ROWS_SEARCH_SAMPLE_RATIO = 0.1;
    static constexpr auto DEFAULT_RATIO_FOR_SPARSE_SERIALIZATION = 0.95;

So the guess is “5% of the rows are non-default”.

How the encoding gets chosen

The sparse encoding is not something you ask for per column. It is selected by the part writer based on the fraction of default values in the column, and it is recorded in the part’s metadata so the reader knows what to expect:

cpp 
// src/DataTypes/Serializations/SerializationInfo.cpp:415
ISerialization::KindStack SerializationInfo::chooseKindStack(const Data & data, const Settings & settings)
{
    ISerialization::KindStack kind_stack = {ISerialization::Kind::DEFAULT};
    double ratio = data.num_rows ? std::min(static_cast<double>(data.num_defaults) / static_cast<double>(data.num_rows), 1.0) : 0.0;
    if (ratio > settings.ratio_of_defaults_for_sparse)
        kind_stack.push_back(ISerialization::Kind::SPARSE);
    return kind_stack;
}

The threshold is the MergeTree table setting ratio_of_defaults_for_sparse_serialization, default 0.9375:

cpp 
// src/Storages/MergeTree/MergeTreeSettings.cpp:97
    DECLARE(Float, ratio_of_defaults_for_sparse_serialization, 0.9375f, R"(
Minimal ratio of the number of _default_ values to the number of _all_ values
in a column. Setting this value causes the column to be stored using sparse
serializations.

The kind_stack is a stack of wrappers, not a single flag, because a column can be Sparse inside Replicated inside Sparse, and the order matters:

cpp 
// src/DataTypes/Serializations/SerializationInfo.cpp:266
/// The order in which the kinds wrap each other, innermost first: `ColumnSparse` can sit inside
/// `ColumnReplicated` but not the other way round (see `removeSpecialRepresentations`), and nothing
/// wraps a `ColumnBLOB`. Not the order of the enum, whose values are part of the Native format.

and the reconstruction is a loop over the stack:

cpp 
// src/DataTypes/IDataType.cpp:456
SerializationPtr IDataType::wrapSerializationBasedOnKindStack(SerializationPtr serialization, const ISerialization::KindStack & kind_stack, const SerializationInfoSettings & settings) const
{
    for (auto kind : kind_stack)
    {
        if (settings.canUseSparseSerialization(*this) && kind == ISerialization::Kind::SPARSE)
            serialization = SerializationSparse::create(serialization);
        else if (kind == ISerialization::Kind::DETACHED)
            serialization = SerializationDetached::create(serialization);
        else if (kind == ISerialization::Kind::REPLICATED)
            serialization = SerializationReplicated::create(serialization);
    }

    return serialization;
}

The kind stack is serialized into serialization.json in the part, so a reader knows to expect a sparse column without having to guess:

cpp 
// src/DataTypes/Serializations/SerializationInfo.cpp:235
void SerializationInfo::serializeKindStackBinary(WriteBuffer & out) const
{
    if (kind_stack == ISerialization::KindStack{ISerialization::Kind::DEFAULT})
    {
        writeBinary(static_cast<UInt8>(KindStackBinarySerializationType::DEFAULT), out);
    }
    else if (kind_stack == ISerialization::KindStack{ISerialization::Kind::DEFAULT, ISerialization::Kind::SPARSE})
    {
        writeBinary(static_cast<UInt8>(KindStackBinarySerializationType::SPARSE), out);
    }

The three substreams

A sparse column on disk is three substreams: the offsets, the elements, and (for a nullable nested type) a null map:

cpp 
// src/DataTypes/Serializations/SerializationSparse.cpp:259
void SerializationSparse::enumerateStreams(
    EnumerateStreamsSettings & settings, const StreamCallback & callback, const SubstreamData & data) const
{
    const auto * column_sparse = data.column ? typeid_cast<const ColumnSparse *>(data.column.get()) : nullptr;
    size_t column_size = column_sparse ? column_sparse->size() : 0;

    settings.path.push_back(Substream::SparseOffsets);
    auto offsets_data = SubstreamData(SerializationNumber<UInt64>::create())
                            .withColumn(column_sparse ? column_sparse->getOffsetsPtr() : nullptr)
                            .withSerializationInfo(data.serialization_info);

    settings.path.back().data = offsets_data;
    callback(settings.path);

    if (sparse_null_map)
    {
        const auto * type_nullable = data.type ? &assert_cast<const DataTypeNullable &>(*data.type) : nullptr;
        settings.path.back() = Substream::SparseNullMap;
        settings.path.back().creator = std::make_shared<NullMapSubcolumnCreator>(offsets_data.column, column_size);
        auto null_map_data = SubstreamData(sparse_null_map)
                                 .withType(type_nullable ? std::make_shared<DataTypeUInt8>() : nullptr)
                                 .withColumn(nullptr) /// subcolumn will be created in NullMapSubcolumnCreator based on offsets
                                 .withSerializationInfo(data.serialization_info);

        settings.path.back().data = null_map_data;
        callback(settings.path);
    }

    settings.path.back() = Substream::SparseElements;
    settings.path.back().creator = std::make_shared<SubcolumnCreator>(offsets_data.column, column_size);
    settings.path.back().data = data;

The null map of a sparse nullable column is not stored — it is derived from the offsets, because “the row is NULL” and “the row is default” are the same statement for a nullable column:

cpp 
// src/DataTypes/Serializations/SerializationSparse.cpp:248
ColumnPtr SerializationSparse::NullMapSubcolumnCreator::create(const ColumnPtr & /* prev */) const
{
    auto null_map_col = ColumnUInt8::create();
    auto & null_map_data = null_map_col->getData();
    null_map_data.resize_fill(size, static_cast<UInt8>(1));
    const auto & offsets_data = assert_cast<const ColumnUInt64 &>(*offsets).getData();
    for (UInt64 offset : offsets_data)
        null_map_data[offset] = 0;
    return null_map_col;
}

All ones, then punch a zero at each non-default row. That is the whole null map, reconstructed from the offsets array.

Writing

cpp 
// src/DataTypes/Serializations/SerializationSparse.cpp:311
void SerializationSparse::serializeBinaryBulkWithMultipleStreams(
    const IColumn & column, size_t offset, size_t limit, SerializeBinaryBulkSettings & settings, SerializeBinaryBulkStatePtr & state) const
{
    size_t size = column.size();

    auto offsets_column = DataTypeNumber<IColumn::Offset>().createColumn();
    auto & offsets_data = assert_cast<ColumnVector<IColumn::Offset> &>(*offsets_column).getData();
    column.getIndicesOfNonDefaultRows(offsets_data, offset, limit);

    settings.path.push_back(Substream::SparseOffsets);
    if (auto * stream = settings.getter(settings.path))
    {
        size_t end = limit && offset + limit < size ? offset + limit : size;
        serializeOffsets(offsets_data, *stream, offset, end);
    }

    settings.path.back() = Substream::SparseElements;
    if (!offsets_data.empty())
    {
        if (const auto * column_sparse = typeid_cast<const ColumnSparse *>(&column))
        {
            const auto & values = column_sparse->getValuesColumn();
            size_t begin = column_sparse->getValueIndex(offsets_data[0]);
            size_t end = column_sparse->getValueIndex(offsets_data.back());
            nested->serializeBinaryBulkWithMultipleStreams(values, begin, end - begin + 1, settings, state);
        }
        else
        {
            auto values = column.index(*offsets_column, 0);
            nested->serializeBinaryBulkWithMultipleStreams(*values, 0, values->size(), settings, state);
        }
    }

Note the two cases in the elements branch. If the column is already a ColumnSparse in memory, the values sub-column is contiguous and only the relevant slice is written. If it is a plain column that merely has many defaults, the writer first materializes the non-default values with column.index(*offsets_column, 0).

The query layer wants to peel the sparse wrapper off

Because random access to a sparse column is a binary search, most query operations want the full column. ColumnSparse therefore provides convertToFullColumnIfSparse:

cpp 
// src/Columns/ColumnSparse.cpp:147
ColumnPtr ColumnSparse::convertToFullColumnIfSparse() const
{
    return values->createWithOffsets(getOffsetsData(), *createColumnConst(values, 0), _size, /*shift=*/ 1);
}

createWithOffsets is the generic mechanism: it takes a values column and an offsets array and produces a full column where each value is repeated offsets[i] - offsets[i-1] times.

There is one place where the engine keeps the sparse representation: when a function has exactly one sparse argument and the function is deterministic, it can be executed on the values only, and the result re-wrapped. That saves decompressing the default rows entirely:

cpp 
// src/Functions/IFunction.cpp:795
        if (num_sparse_columns == 1 && num_full_columns == 0 && isCallDeterministicInScopeOfQuery(arguments))
        {
            auto & arg_with_sparse = columns_without_sparse[sparse_column_position];
            ColumnPtr sparse_offsets;
            {
                /// New scope to avoid possible mistakes on dangling reference.
                auto & column_sparse = assert_cast<const ColumnSparse &>(*arg_with_sparse.column);
                sparse_offsets = column_sparse.getOffsetsPtr();
                arg_with_sparse.column = column_sparse.getValuesPtr();
            }

            size_t values_size = arg_with_sparse.column->size();
            for (size_t i = 0; i < columns_without_sparse.size(); ++i)
            {
                if (i == sparse_column_position)
                    continue;

                columns_without_sparse[i].column = columns_without_sparse[i].column->cloneResized(values_size);
            }

            auto res = executeWithoutSparseColumns(columns_without_sparse, result_type, values_size, dry_run);

            if (isColumnConst(*res))
                return res->cloneResized(input_rows_count);

            /// If default of sparse column is changed after execution of function, convert to full column.
            /// If there are any default in non-zero position after execution of function, convert to full column.
            /// Currently there is no easy way to rebuild sparse column with new offsets.
            if (!result_type->canBeInsideSparseColumns() || !res->isDefaultAt(0) || res->getNumberOfDefaultRows() != 1)
            {
                const auto & offsets_data = assert_cast<const ColumnVector<UInt64> &>(*sparse_offsets).getData();
                return res->createWithOffsets(offsets_data, *createColumnConst(res, 0), input_rows_count, /*shift=*/1);
            }

            return ColumnSparse::create(res, sparse_offsets, input_rows_count);
        }

The condition at the end is the interesting part: the result can only stay sparse if (a) the result type is allowed inside a sparse column, (b) the result’s default value is still the default (position 0 is the only default), and (c) there is exactly one default row. If the function changed the default value, or produced extra defaults in the middle, the sparse structure no longer matches and the column is expanded. The comment says so plainly: “Currently there is no easy way to rebuild sparse column with new offsets.”

That is the honest limitation of this design, stated in the source.

The other side of the coin: the null map

ColumnNullable takes the opposite approach: keep everything, add a byte per row saying which rows are NULL.

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.

The comment explains the design choice: a bitmap would be 8× smaller, but columns are stored compressed, and a byte map of mostly zeros compresses just as well as a bitmap while being trivially indexable. The null map is literally a ColumnUInt8:

cpp 
// src/Columns/ColumnNullable.h:16
using NullMap = ColumnUInt8::Container;
using ConstNullMapPtr = const NullMap *;

and it is a separate column, which means it is a separate compression stream, a separate substream on disk, and separately filterable:

cpp 
// src/DataTypes/Serializations/SerializationNullable.cpp:124
    if (!use_default_null_map)
    {
        /// First serialize null map.
        settings.path.push_back(Substream::NullMap);
        if (auto * stream = settings.getter(settings.path))
            SerializationNumber<UInt8>::create()->serializeBinaryBulk(col.getNullMapColumn(), *stream, offset, limit);
        settings.path.pop_back();
    }

The null map is written to its own substream, before the values.

The value column of a Nullable still has one entry per row — the value under a NULL is undefined, but it occupies a slot. insertData shows the convention:

cpp 
// src/Columns/ColumnNullable.cpp:183
void ColumnNullable::insertData(const char * pos, size_t length)
{
    if (pos == nullptr)
    {
        getNestedColumn().insertDefault();
        getNullMapData().push_back(true);
    }
    else
    {
        getNestedColumn().insertData(pos, length);
        getNullMapData().push_back(false);
    }
}

A NULL still pushes a default into the value column, to keep the two arrays the same length. And the two must stay in sync even if the push throws:

cpp 
// src/Columns/ColumnNullable.h:97
    void insertDefault() override
    {
        getNestedColumn().insertDefault();
        /// Keep the nested column and the null map in sync even if appending to the
        /// null map throws (e.g. on a memory limit).
        try
        {
            getNullMapData().push_back(true);
        }
        catch (...)
        {
            getNestedColumn().popBack(1);
            throw;
        }
    }

The null map is also where the “combine two nullable columns” logic lives, and it has a subtlety worth reading:

cpp 
// src/Columns/ColumnNullable.cpp:932
void ColumnNullable::applyNullMapImpl(const NullMap & map, size_t offset)
{
    NullMap & arr = getNullMapData();

    if (offset + map.size() != arr.size())
        throw Exception(
            ErrorCodes::LOGICAL_ERROR,
            "Null map of size {} at offset {} does not match ColumnNullable of size {}",
            map.size(), offset, arr.size());

    /// Any non-zero byte means NULL, so reduce the map before negating it: `negative ^ 2` would
    /// yield 3 and mark a row the map leaves present.
    for (size_t i = 0, size = map.size(); i < size; ++i)
        arr[offset + i] |= negative ^ !!map[i];
}

The null map is a byte map where any non-zero means NULL. When negating, the code has to normalize the incoming map to 0/1 first (!!map[i]), because the bitwise XOR against negative would otherwise produce values like 3 from a 2 — which would still read as “non-zero means NULL” for this map but would corrupt subsequent operations.

Seeing it in SQL

The setting is a MergeTree table setting:

sql 
CREATE TABLE my_sparse_table
(
    `id` UInt64,
    `s` String
)
ENGINE = MergeTree()
ORDER BY id
SETTINGS ratio_of_defaults_for_sparse_serialization = 0.95;

INSERT INTO my_sparse_table
SELECT
    number,
    number % 20 = 0 ? toString(number): ''
FROM
    numbers(10000000);

and you can check what happened:

sql 
-- Which columns got the sparse encoding?
SELECT column, serialization_kind FROM system.parts_columns
WHERE table = 'my_sparse_table';
sql 
-- And how much did it save?
SELECT table, name, data_compressed_bytes, data_uncompressed_bytes FROM system.columns
WHERE table LIKE 'my_%_table';

The documentation in the setting itself shows the effect on a table where 95% of the s column is the empty string: the sparse version stores fewer bytes both compressed and uncompressed.

Trade-offs

What the sparse encoding buys you.

A column that is 95% default costs 5% of what it would otherwise cost, plus a small offsets array. And the offsets array is not 8 bytes per non-default row on disk — it is a VarInt run-length encoding of the gaps, so a column with long runs of defaults costs almost nothing per gap.

Better still, the sparse representation is propagated: a function applied to a sparse column is executed on the values only, so the CPU cost is proportional to the non-default rows too, not just the memory cost.

What it costs you.

Random access becomes a binary search. A scan is fine (the Iterator is amortized O(1)), but a WHERE row_id = 42 on a sparse column is O(log k) plus an indirection, where a plain column would be one array index. That is why the query layer tries to convert sparse columns to full ones as early as possible — convertToFullColumnIfSparse is called all over the MergeTree read path.

The structure is also fragile in one specific way: the invariant that “the only default is at position 0” must hold for the column to stay sparse. A function that changes the default value, or produces additional defaults in the middle of the column, forces a full expansion. The source says so without embarrassment.

Sparse vs Nullable. These are not competitors; they solve different problems. Nullable answers “is this row NULL?” and pays one byte per row plus the value slot. Sparse answers “what are the rows that are not default?” and pays only for those rows — but it only applies to default values, and defaultness is a property of the type, not of the data. A nullable column whose non-null values are all distinct is not sparse at all; it is a Nullable with a null map.

The design decision that makes it work. The offsets array is stored as gaps, not positions. That single choice turns “8 bytes per non-default row” into “one VarInt per run of default rows”, which for real data (long runs of defaults) is a factor of hundreds. Everything else — the resumable decoder state, the END_OF_GRANULE_FLAG, the derived null map — exists to make that choice work across granule boundaries and partial reads.

ClickhousePerformanceInternalsMemoryCompression