ClickHouse's LowCardinality Column Shares One Dictionary Across Millions of Rows

TL;DR: LowCardinality(T) stores a dictionary of distinct values once and keeps a 1–8 byte index per row. The dictionary is shared across every block, granule and part, so twelve distinct values cost one byte per row instead of ten. It pays off below ~10 000 distinct values and hurts above ~100 000.

Every column-oriented database eventually meets the same data: a column of country codes, of status strings, of user agents, of enum-like labels. A hundred thousand rows, twelve distinct values, repeated over and over.

Storing the value in every row is absurd. Storing the position of the value in every row is not.

ClickHouse’s answer is a column type called LowCardinality(T), and the implementation is one of the more interesting pieces of the whole storage engine, because it has to solve three separate problems at once:

how to represent the dictionary and the index in memory,
how to make the same dictionary serve many different blocks, granules and parts, so the dictionary is stored once and not once per block,
how to serialize that arrangement on disk so a reader can rebuild it — including the case where the dictionary had to change halfway through.

Let’s take all three. Source quoted from ClickHouse 26.9 (04eac2ea3).

The shape of the thing

The header comment of ColumnLowCardinality states the design in four lines:

cpp
// src/Columns/ColumnLowCardinality.h:17
/**
 * How data is stored (in a nutshell):
 * we have a dictionary @e reverse_index in ColumnUnique that holds pairs (DataType, UIntXX) and a column
 * with UIntXX holding actual data indices.
 * To obtain the value's index, call #getOrFindIndex.
 * To operate on the data (so called indices column), call #getIndexes.
 *
 * @note The indices column always contains the default value (empty std::string_view) with the first index.
 */

The class holds exactly two members:

cpp
// src/Columns/ColumnLowCardinality.h:398
    Dictionary dictionary;
    ColumnIndex idx;

Dictionary is a thin wrapper around a ColumnUnique plus a shared flag:

cpp
// src/Columns/ColumnLowCardinality.h:366
private:
    class Dictionary
    {
    public:
        Dictionary(const Dictionary & other) = default;
        explicit Dictionary(MutableColumnPtr && column_unique, bool is_shared);
        explicit Dictionary(ColumnPtr column_unique, bool is_shared);

        const WrappedPtr & getColumnUniquePtr() const { return column_unique; }
        WrappedPtr & getColumnUniquePtr() { return column_unique; }

        const IColumnUnique & getColumnUnique() const { return static_cast<const IColumnUnique &>(*column_unique); }
        IColumnUnique & getColumnUnique() { return static_cast<IColumnUnique &>(*column_unique); }

        /// Dictionary may be shared for several mutable columns.
        /// Immutable columns may have the same column unique, which isn't necessarily shared dictionary.
        void setShared(const ColumnPtr & column_unique_);
        bool isShared() const { return shared; }

        /// Create new dictionary with only keys that are mentioned in indexes.
        void compact(MutableColumnPtr & indexes);
        /// Create nullable dictionary with only keys that are mentioned in indexes.
        void compactToNullable(MutableColumnPtr & indexes);

        static MutableColumnPtr compact(const IColumnUnique & column_unique, MutableColumnPtr & indexes);
        static MutableColumnPtr compactToNullable(const IColumnUnique & column_unique, MutableColumnPtr & indexes);

    private:
        WrappedPtr column_unique;
        bool shared = false;
    };

So a LowCardinality column is:

text

                 +---------------------------+
   row 0  -----> | dictionary[ idx[0] ]      |  idx is a ColumnVector<UInt8|UInt16|UInt32|UInt64>
   row 1  -----> | dictionary[ idx[1] ]      |  dictionary is a ColumnUnique<ColumnString> (etc.)
   row 2  -----> | dictionary[ idx[2] ]      |
   ...           +---------------------------+

The values are in the dictionary; the rows are indices. Getting row n is two loads: getIndexes().getUInt(n), then a lookup in the dictionary.

That second load is a random access into a (hopefully tiny) array — and the whole point is that the dictionary array is tiny enough to stay in L1/L2 while the index array streams past it.

The index column grows its own type

The index column is not fixed-width. It starts as UInt8 and widens to UInt16, UInt32, UInt64 as the dictionary outgrows the range. The widening logic lives in ColumnIndex:

cpp
// src/Columns/ColumnIndex.cpp:135
void ColumnIndex::expandType()
{
    auto expand = [&](auto type)
    {
        using CurIndexType = decltype(type);
        constexpr auto next_size = NumberTraits::nextSize(sizeof(CurIndexType));
        if (next_size == sizeof(CurIndexType))
            throw Exception(ErrorCodes::LOGICAL_ERROR, "Can't expand indexes type for ColumnLowCardinality from type: {}",
                            demangle(typeid(CurIndexType).name()));

        using NewIndexType = typename NumberTraits::Construct<false, false, next_size>::Type;
        convertIndexes<NewIndexType>();
    };

    callForType(std::move(expand), size_of_type);
}

and the bound that decides when to widen:

cpp
// src/Columns/ColumnIndex.cpp:152
size_t ColumnIndex::getMaxIndexForCurrentType() const
{
    chassert(size_of_type == 1 || size_of_type == 2 || size_of_type == 4 || size_of_type == 8);
    /// Shifting by 64 is undefined, and this is called per inserted value, so no `callForType` here.
    if (size_of_type == sizeof(UInt64))
        return std::numeric_limits<UInt64>::max();
    return (1ULL << (8 * size_of_type)) - 1;
}

The per-value insert path is where the widening happens, and note the comment about avoiding a typeid_cast on the hot path:

cpp
// src/Columns/ColumnIndex.cpp:198
void ColumnIndex::insertIndex(size_t index)
{
    while (index > getMaxIndexForCurrentType())
        expandType();

    auto insert = [&]<typename CurIndexType>(CurIndexType /*type_value*/)
    {
        /// `size_of_type` tracks the type of `indexes` and `expandType` keeps the two in sync, so
        /// this is `static_cast` in release. `getIndexesData` would run a `typeid_cast` instead, and
        /// this is the per-value path.
        assert_cast<ColumnVector<CurIndexType> *>(indexes.get())->getData().push_back(static_cast<CurIndexType>(index));
    };

    callForType(std::move(insert), size_of_type);

    /// Same invariant, so re-deriving it from `indexes` is a debug-only check here.
    chassert(size_of_type == getSizeOfIndexType(*indexes, size_of_type));
}

callForType is a hand-rolled dispatch over the four possible widths — no virtual call, no switch on a runtime type id, just four instantiations of a lambda. This is the pattern used throughout ClickHouse’s hot column code: the virtual IColumn interface is for the cold, structural paths; the per-row paths are devirtualized by dispatching on the concrete type once and then running a monomorphic loop.

Reading an index back has the same shape, and is marked ALWAYS_INLINE because it is called from the tightest loops in the engine:

cpp
// src/Columns/ColumnLowCardinality.h:326
    ALWAYS_INLINE size_t getIndexAt(size_t row) const
    {
        const IColumn * indexes = &getIndexes();

        switch (idx.getSizeOfIndexType())
        {
            case sizeof(UInt8): return assert_cast<const ColumnUInt8 *>(indexes)->getElement(row);
            case sizeof(UInt16): return assert_cast<const ColumnUInt16 *>(indexes)->getElement(row);
            case sizeof(UInt32): return assert_cast<const ColumnUInt32 *>(indexes)->getElement(row);
            case sizeof(UInt64): return assert_cast<const ColumnUInt64 *>(indexes)->getElement(row);
            default: throwUnexpectedLowCardinalityIndexType(idx.getSizeOfIndexType());
        }
    }

The dictionary: ColumnUnique and its reverse index

ColumnUnique is the dictionary. It is not a column type you can select; the comment says so:

cpp
// src/Columns/ColumnUnique.h:36
/** Stores another column with unique values
  * and also an index that allows to find position by value.
  *
  * This column is not used on it's own but only as implementation detail of ColumnLowCardinality.
  */
template <typename ColumnType>
class ColumnUnique final : public COWHelper<IColumnUnique, ColumnUnique<ColumnType>>

Its members are the values plus the lookup structure:

cpp
// src/Columns/ColumnUnique.h:203
private:
    IColumn::WrappedPtr column_holder;
    bool is_nullable;
    size_t size_of_value_if_fixed = 0;

    ReverseIndex<UInt64, ColumnType> reverse_index;

    /// For DataTypeNullable, stores null map.
    IColumn::WrappedPtr nested_null_mask;
    IColumn::WrappedPtr nested_column_nullable;

Two reserved slots

The first row of the dictionary is special: it is the default value of the type. If the dictionary is nullable, row 0 is the NULL and row 1 is the default value of the inner type:

cpp
// src/Columns/ColumnUnique.h:74
    size_t getDefaultValueIndex() const override { return 0; }
    size_t getNullValueIndex() const override;
    size_t getNestedTypeDefaultValueIndex() const override { return is_nullable ? 1 : 0; }
    bool canContainNulls() const override { return is_nullable; }

and

cpp
// src/Columns/ColumnUnique.h:370
template <typename ColumnType>
size_t ColumnUnique<ColumnType>::getNullValueIndex() const
{
    if (!is_nullable)
        throw Exception(ErrorCodes::LOGICAL_ERROR, "ColumnUnique can't contain null values.");

    return 0;
}

The count of reserved slots is therefore one or two:

cpp
// src/Columns/ColumnUnique.h:238
    static size_t numSpecialValues(bool is_nullable) { return is_nullable ? 2 : 1; }
    size_t numSpecialValues() const { return numSpecialValues(is_nullable); }

Those reserved slots are not in the reverse index, which is why the insert path has to special-case them by hand:

cpp
// src/Columns/ColumnUnique.h:513
template <typename ColumnType>
size_t ColumnUnique<ColumnType>::uniqueInsertData(const char * pos, size_t length)
{
    /// The reserved prefix slots are not in the reverse index, so the default value is matched here.
    /// Comparing the first byte first keeps the `memcmp` call out of this path for the values that
    /// are not the default, which is all of them in a typical dictionary.
    const size_t default_index = getNestedTypeDefaultValueIndex();
    const std::string_view default_value = getRawColumnPtr()->getDataAt(default_index);
    if (default_value.size() == length && (length == 0 || (default_value[0] == pos[0] && default_value == std::string_view(pos, length))))
        return default_index;

    auto insertion_point = reverse_index.insert({pos, length});

    updateNullMask();

    return insertion_point;
}

The comment is a nice piece of micro-optimisation reasoning: comparing the first byte before the whole value keeps the expensive memcmp off the path for the (overwhelmingly common) case where the value is not the default.

The reverse index stores row numbers, not values

ReverseIndex is the interesting part. A naive dictionary would be a HashMap<value, index> — the values stored twice, once in the column and once as hash-table keys. ReverseIndex inverts that: the hash table stores the row number in the dictionary column, and comparisons dereference back into the column:

cpp
// src/Columns/ReverseIndex.h:94
    /// Special case when we want to compare with something not in index_column.
    /// When we compare something inside column default keyEquals checks only that row numbers are equal.
    bool keyEquals(std::string_view object, size_t hash_ [[maybe_unused]], const State & state) const
    {
        auto index = key;
        if constexpr (has_base_index)
            index -= state.base_index;

        if constexpr (string_hash)
            return hash_ == (*state.saved_hash_column)[index] && object == state.index_column->getDataAt(index);
        else
            return object == state.index_column->getDataAt(index);
    }

The hash table therefore holds 8-byte integers, and the dictionary column holds the only copy of the data. For a LowCardinality(String) with 1000 distinct values, that is the difference between a hash table with 1000 string keys (plus their hashes, plus their lengths) and a hash table with 1000 UInt64s.

For string columns the hash is expensive, so it is precomputed once and kept in a parallel ColumnUInt64:

cpp
// src/Columns/ReverseIndex.h:43
template <typename ColumnType>
struct ReverseIndexHashTableState<ColumnType, /* with_saved_hash = */ true, /* has_base_index */ false>
{
    constexpr static bool with_saved_hash = true;
    constexpr static bool has_base_index = false;

    ColumnType * index_column;
    typename ColumnVector<UInt64>::Container * saved_hash_column;
};

and the hash function for a stored row reads the precomputed hash rather than re-hashing the string:

cpp
// src/Columns/ReverseIndex.h:108
    size_t getHash(const Hash & hash) const
    {
        auto index = key;

        /// Hack. HashTable is Hash itself.
        const auto & state = static_cast<const State &>(static_cast<const HashTable &>(hash));

        if constexpr (has_base_index)
            index -= state.base_index;

        if constexpr (string_hash)
            return (*state.saved_hash_column)[index];
        else
        {
            using ValueType = typename ColumnType::ValueType;
            ValueType value = unalignedLoad<ValueType>(state.index_column->getDataAt(index).data());
            return DefaultHash<ValueType>()(value);
        }
    }

The index is built lazily, and the hash table is filled in one pass

The reverse index is not built at construction time; it is built on the first insert, and the build is a single pass over the dictionary:

cpp
// src/Columns/ReverseIndex.h:435
template <typename IndexType, typename ColumnType>
void ReverseIndex<IndexType, ColumnType>::buildIndex()
{
    if (index)
        return;

    if (!column)
        throw Exception(ErrorCodes::LOGICAL_ERROR, "ReverseIndex can't build index because index column wasn't set.");

    auto size = column->size();
    index = std::make_unique<IndexMapType>(size);

    if constexpr (use_saved_hash)
        saved_hash = calcHashes();

    auto & state = index->getState();
    state.index_column = column;
    state.base_index = base_index;
    if constexpr (use_saved_hash)
        state.saved_hash_column = &saved_hash->getData();

    using IteratorType = typename IndexMapType::iterator;
    IteratorType iterator;
    bool inserted = false;

    for (auto row : collections::range(num_prefix_rows_to_skip, size))
    {
        UInt64 hash = 0;
        if constexpr (use_saved_hash)
            hash = saved_hash->getElement(row);
        else
            hash = getHash(column->getDataAt(row));

        index->reverseIndexEmplace(row + base_index, iterator, inserted, hash, column->getDataAt(row));

        if (!inserted)
            throw Exception(ErrorCodes::LOGICAL_ERROR, "Duplicating keys found in ReverseIndex.");
    }
}

Note num_prefix_rows_to_skip: the reserved NULL/default slots are skipped, because they are matched by hand in uniqueInsertData.

The insert path is the mirror image, and it is written to be branch-light for the two different column kinds:

cpp
// src/Columns/ReverseIndex.h:490
template <typename IndexType, typename ColumnType>
UInt64 ReverseIndex<IndexType, ColumnType>::insert(std::string_view data)
{
    if (!index)
        buildIndex();

    using IteratorType = typename IndexMapType::iterator;
    IteratorType iterator;
    bool inserted = false;

    auto hash = getHash(data);
    UInt64 num_rows = size();

    if constexpr (use_saved_hash)
    {
        auto & column_data = saved_hash->getData();
        if (column_data.size() <= num_rows)
            column_data.resize(num_rows + 1);
        column_data[num_rows] = hash;
    }
    else
        column->insertData(data.data(), data.size());

    index->reverseIndexEmplace(num_rows + base_index, iterator, inserted, hash, data);

    if constexpr (use_saved_hash)
    {
        if (inserted)
            column->insertData(data.data(), data.size());
    }
    else
    {
        if (!inserted)
            column->popBack(1);
    }

    return iterator->getValue();
}

For strings the hash is appended optimistically and the value is appended only if the key was new. For fixed-size values the value is appended optimistically and popped back if the key turned out to be a duplicate. Each kind pushes and pops the cheaper thing.

Float NaNs are canonicalized

A LowCardinality(Float64) dictionary must not contain two NaNs, because NaN == NaN is false but all NaNs must compare equal in the dictionary semantics. So NaN is normalized at insert time:

cpp
// src/Columns/ColumnUnique.h:389
template <typename ColumnType>
size_t ColumnUnique<ColumnType>::uniqueInsert(const Field & x)
{
    if (x.isNull())
        return getNullValueIndex();

    // NaN can contain different sign or mantissa bits, but we need to consider all NaNs equal.
    if constexpr (is_float_vector_v<ColumnType>)
    {
        if (isNaN(x.safeGet<typename ColumnType::ValueType>()))
        {
            auto nan = NaNOrZero<typename ColumnType::ValueType>();
            return uniqueInsertData(reinterpret_cast<char *>(&nan), sizeof(nan));
        }
    }

Here is where the design pays off. A LowCardinality column can point at a dictionary owned by another column. The shared flag on Dictionary records this, and byteSize() deliberately does not count a shared dictionary:

cpp
// src/Columns/ColumnLowCardinality.h:200
    /// Don't count the dictionary size as it can be shared between different blocks.
    size_t byteSize() const override { return idx.getIndexes()->byteSize() + (isSharedDictionary() ? 0 : getDictionary().byteSize()); }

    size_t byteSizeAt(size_t n) const override { return getDictionary().byteSizeAt(getIndexes().getUInt(n)); }
    size_t allocatedBytes() const override { return idx.getIndexes()->allocatedBytes() + getDictionary().allocatedBytes(); }

Note the asymmetry: byteSize() (the logical size, used for statistics and for system.parts_columns) excludes the shared dictionary, but allocatedBytes() (the physical size, used for memory accounting) includes it. That distinction is what makes the accounting correct when a part has a hundred blocks all pointing at one dictionary.

Sharing also propagates through every operation that produces a new column from an old one — cut, filter, permute, index, replicate all hand the same dictionary pointer to the result:

cpp
// src/Columns/ColumnLowCardinality.h:130
    ColumnPtr filter(const Filter & filt, ssize_t result_size_hint) const override
    {
        return ColumnLowCardinality::create(
            dictionary.getColumnUniquePtr(), getIndexes().filter(filt, result_size_hint), isSharedDictionary());
    }

But a shared dictionary is immutable

The moment you want to mutate a column whose dictionary is shared with somebody else, the dictionary has to be un-shared. This happens in compactIfSharedDictionary(), which is called at the top of every mutating insert:

cpp
// src/Columns/ColumnLowCardinality.cpp:146
void ColumnLowCardinality::insert(const Field & x)
{
    compactIfSharedDictionary();
    idx.insertIndex(getDictionary().uniqueInsert(x));
}

bool ColumnLowCardinality::tryInsert(const Field & x)
{
    compactIfSharedDictionary();

    size_t index = 0;
    if (!dictionary.getColumnUnique().tryUniqueInsert(x, index))
        return false;

    idx.insertIndex(index);
    return true;
}

cpp
// src/Columns/ColumnLowCardinality.cpp:894
void ColumnLowCardinality::compactIfSharedDictionary()
{
    if (dictionary.isShared())
        compactInplace();
}

Compaction rebuilds a private dictionary containing only the keys that are actually referenced by this column’s indexes, and remaps the indexes accordingly:

cpp
// src/Columns/ColumnLowCardinality.cpp:1002
MutableColumnPtr ColumnLowCardinality::Dictionary::compact(const IColumnUnique & unique, MutableColumnPtr & indexes)
{
    auto new_column_unique = unique.cloneEmpty();
    auto & new_unique = static_cast<IColumnUnique &>(*new_column_unique);

    auto unique_indexes = mapUniqueIndex(*indexes);
    auto sub_keys = unique.getNestedColumn()->index(*unique_indexes, 0);
    auto new_indexes = new_unique.uniqueInsertRangeFrom(*sub_keys, 0, sub_keys->size());

    indexes = IColumn::mutate(new_indexes->index(*indexes, 0));
    return new_column_unique;
}

mapUniqueIndex is the piece that does the renumbering. It is a counting-sort-like trick that works in O(n) with a flat array, and it has an overflow path for when the dictionary is shared and the indexes do not fit the “max index < number of rows” assumption:

cpp
// src/Columns/ColumnLowCardinality.cpp:79
template <typename T>
MutableColumnPtr mapUniqueIndexImpl(PaddedPODArray<T> & index)
{
    if (index.empty())
        return ColumnVector<T>::create();

    auto size = index.size();

    T max_val = index[0];
    for (size_t i = 1; i < size; ++i)
        max_val = std::max(max_val, index[i]);

    /// May happen when dictionary is shared.
    if (max_val > size)
        return mapUniqueIndexImplRef(index);

    auto map_size = static_cast<UInt64>(max_val) + 1;
    PaddedPODArray<T> map(map_size, 0);
    T zero_pos_value = index[0];
    index[0] = 0;
    T cur_pos = 0;
    for (size_t i = 1; i < size; ++i)
    {
        T val = index[i];
        if (val != zero_pos_value && map[val] == 0)
        {
            ++cur_pos;
            map[val] = cur_pos;
        }

        index[i] = map[val];
    }

The “overflow” case (max_val > size) means the column references dictionary entries that belong to a bigger dictionary — exactly what happens when the dictionary is shared. Then a hash map is used instead of a flat array:

cpp
// src/Columns/ColumnLowCardinality.cpp:53
template <typename T>
MutableColumnPtr mapUniqueIndexImplRef(PaddedPODArray<T> & index)
{
    PaddedPODArray<T> copy(index.cbegin(), index.cend());

    HashMap<T, T> hash_map;
    for (auto val : index)
        hash_map.insert({val, static_cast<T>(hash_map.size())});

    auto res_col = ColumnVector<T>::create();
    auto & data = res_col->getData();

    data.resize(hash_map.size());
    for (const auto & val : hash_map)
        data[val.getMapped()] = val.getKey();

    for (auto & ind : index)
        ind = hash_map[ind];

    for (size_t i = 0; i < index.size(); ++i)
        if (data[index[i]] != copy[i])
            throw Exception(ErrorCodes::LOGICAL_ERROR, "Expected {}, but got {}", toString(data[index[i]]), toString(copy[i]));

    return res_col;
}

That last loop is a self-check: after the renumbering, the new index must still resolve to the same value. Cheap insurance against an off-by-one in a data structure that is otherwise very hard to test.

Inserting from a column with the same dictionary

Once dictionaries are shared, a very common operation becomes trivial: copying a row from another LowCardinality column that happens to use the same dictionary is just a copy of an index.

cpp
// src/Columns/ColumnLowCardinality.cpp:180
    size_t position = low_cardinality_src->getIndexes().getUInt(n);

    if (&low_cardinality_src->getDictionary() == &getDictionary())
    {
        /// Dictionary is shared with src column. Insert only index.
        idx.insertIndex(position);
    }
    else
    {
        compactIfSharedDictionary();
        const auto & nested = *low_cardinality_src->getDictionary().getNestedColumn();
        idx.insertIndex(getDictionary().uniqueInsertFrom(nested, position));
    }

The test is a pointer comparison of the dictionary addresses. If they are the same object, the index is valid as-is; otherwise the value has to be re-inserted into this column’s dictionary and the resulting index used.

On disk: one dictionary per part, versioned per granule

Now the hard part. In a MergeTree part, a LowCardinality column is written as two streams: DictionaryKeys and DictionaryIndexes.

The keys stream holds the dictionary; the indexes stream holds, per granule, a header and then the index data. The dictionary is not rewritten per granule — it accumulates until it hits a size limit, at which point it is flushed and a new one starts.

The version byte

The keys stream starts with a version:

cpp
// src/DataTypes/Serializations/SerializationLowCardinality.cpp:102
struct KeysSerializationVersion
{
    enum Value
    {
        /// Version is written at the start of <name.dict.bin>.
        /// Dictionary is written as number N and N keys after them.
        /// Dictionary can be shared for continuous range of granules, so some marks may point to the same position.
        /// Shared dictionary is stored in state and is read once.
        SharedDictionariesWithAdditionalKeys = 1,
    };

    Value value;

    static void checkVersion(UInt64 version)
    {
        if (version != SharedDictionariesWithAdditionalKeys)
            throw Exception(ErrorCodes::INCORRECT_DATA, "Invalid version for SerializationLowCardinality key column.");
    }

    explicit KeysSerializationVersion(UInt64 version) : value(static_cast<Value>(version)) { checkVersion(version); }
};

The single legal version is called SharedDictionariesWithAdditionalKeys, and the comment tells you the whole story in three lines: the dictionary is written as a count followed by that many keys, it can be shared across a continuous range of granules, and the shared dictionary is kept in the serialization state and read once.

The per-granule header

Every granule’s index data begins with a header that encodes the index width plus three flags:

cpp
// src/DataTypes/Serializations/SerializationLowCardinality.cpp:124
/// Version is stored at the start of each granule. It's used to store indexes type and flags.
struct IndexesSerializationType
{
    using SerializationType = UInt64;
    /// Need to read dictionary if it wasn't.
    static constexpr SerializationType NeedGlobalDictionaryBit = 1u << 8u;
    /// Need to read additional keys. Additional keys are stored before indexes as value N and N keys after them.
    static constexpr SerializationType HasAdditionalKeysBit = 1u << 9u;
    /// Need to update dictionary. It means that previous granule has different dictionary.
    static constexpr SerializationType NeedUpdateDictionary = 1u << 10u;

    enum Type
    {
        TUInt8 = 0,
        TUInt16,
        TUInt32,
        TUInt64,
    };

    Type type;
    bool has_additional_keys;
    bool need_global_dictionary;
    bool need_update_dictionary;

    static constexpr SerializationType resetFlags(SerializationType type)
    {
        return type & (~(HasAdditionalKeysBit | NeedGlobalDictionaryBit | NeedUpdateDictionary));
    }

The three flags are the entire state machine:

NeedGlobalDictionaryBit — “there is a dictionary in the keys stream that I have not read yet”.
HasAdditionalKeysBit — “this granule carries keys that did not fit in the shared dictionary; they are stored inline, before the index data”.
NeedUpdateDictionary — “the dictionary changed since the previous granule”.

Serialization and deserialization are symmetric and trivial:

cpp
// src/DataTypes/Serializations/SerializationLowCardinality.cpp:162
    void serialize(WriteBuffer & buffer) const
    {
        SerializationType val = type;
        if (has_additional_keys)
            val |= HasAdditionalKeysBit;
        if (need_global_dictionary)
            val |= NeedGlobalDictionaryBit;
        if (need_update_dictionary)
            val |= NeedUpdateDictionary;
        writeBinaryLittleEndian(val, buffer);
    }

    void deserialize(ReadBuffer & buffer, const ISerialization::DeserializeBinaryBulkSettings & settings)
    {
        SerializationType val = 0;
        readBinaryLittleEndian(val, buffer);

        checkType(val);
        has_additional_keys = (val & HasAdditionalKeysBit) != 0;
        need_global_dictionary = (val & NeedGlobalDictionaryBit) != 0;
        need_update_dictionary = (val & NeedUpdateDictionary) != 0;
        type = static_cast<Type>(resetFlags(val));

        if (settings.native_format)
        {
            if (need_global_dictionary)
                throw Exception(ErrorCodes::INCORRECT_DATA,
                                "LowCardinality indexes serialization type for Native format "
                                "cannot use global dictionary");
        }
    }

The low four bits carry the index width; bits 8, 9, 10 are the flags. Bits 4–7 are unused — a hole left for future flags.

Writing: the dictionary accumulates, then overflows

The writer keeps the accumulating dictionary in the serialization state:

cpp
// src/DataTypes/Serializations/SerializationLowCardinality.cpp:232
struct SerializeStateLowCardinality : public ISerialization::SerializeBinaryBulkState
{
    KeysSerializationVersion key_version;
    MutableColumnUniquePtr shared_dictionary;

    explicit SerializeStateLowCardinality(UInt64 key_version_) : key_version(key_version_) {}
};

The write path is where the interesting decisions live:

cpp
// src/DataTypes/Serializations/SerializationLowCardinality.cpp:561
    const ColumnLowCardinality & low_cardinality_column = typeid_cast<const ColumnLowCardinality &>(column);

    auto * low_cardinality_state = checkAndGetState<SerializeStateLowCardinality>(state);
    auto & global_dictionary = low_cardinality_state->shared_dictionary;
    KeysSerializationVersion::checkVersion(low_cardinality_state->key_version.value);

    size_t max_limit = column.size() - offset;
    limit = limit ? std::min(limit, max_limit) : max_limit;

    /// Do not write anything for empty column. (May happen while writing empty arrays.)
    if (limit == 0)
        return;

    bool need_update_dictionary = global_dictionary == nullptr;
    if (need_update_dictionary)
        global_dictionary = DataTypeLowCardinality::createColumnUnique(*dictionary_type);

    auto sub_column = low_cardinality_column.cutAndCompact(offset, limit);
    ColumnPtr positions = sub_column->getIndexesPtr();
    ColumnPtr keys = sub_column->getDictionary().getNestedColumn();

    if (settings.low_cardinality_max_dictionary_size)
    {
        /// Insert used_keys into global dictionary and update sub_index.
        auto indexes_with_overflow = global_dictionary->uniqueInsertRangeWithOverflow(*keys, 0, keys->size(),
                                                                                      settings.low_cardinality_max_dictionary_size);

        if (global_dictionary->size() > settings.low_cardinality_max_dictionary_size)
            throw Exception(ErrorCodes::LOGICAL_ERROR, "Got dictionary with size {} but max dictionary size is {}",
                            global_dictionary->size(), settings.low_cardinality_max_dictionary_size);

        positions = indexes_with_overflow.indexes->index(*positions, 0);
        keys = std::move(indexes_with_overflow.overflowed_keys);

        if (global_dictionary->size() < settings.low_cardinality_max_dictionary_size && !keys->empty())
            throw Exception(ErrorCodes::LOGICAL_ERROR, "Has additional keys, but dict size is {} which is less "
                            "then max dictionary size ({})", global_dictionary->size(),
                            settings.low_cardinality_max_dictionary_size);
    }

cutAndCompact is the first step: it takes the slice of the column being written and produces a private dictionary containing only the keys that slice actually uses. That is what keeps the accumulated dictionary small — without it, every granule would re-insert the whole dictionary.

Then the keys are merged into the global dictionary, and anything that does not fit within low_cardinality_max_dictionary_size becomes “overflowed keys” — keys carried inline by that granule.

The flush happens when the accumulated dictionary reaches the limit:

cpp
// src/DataTypes/Serializations/SerializationLowCardinality.cpp:602
    bool need_additional_keys = !keys->empty();
    bool need_dictionary = settings.low_cardinality_max_dictionary_size != 0;
    bool need_write_dictionary = !settings.low_cardinality_use_single_dictionary_for_part
                                 && global_dictionary->size() >= settings.low_cardinality_max_dictionary_size;

    IndexesSerializationType index_version(*positions, need_additional_keys, need_dictionary, need_update_dictionary);
    index_version.serialize(*indexes_stream);

    if (need_write_dictionary)
    {
        const auto & nested_column = global_dictionary->getNestedNotNullableColumn();
        UInt64 num_keys = nested_column->size();
        writeBinaryLittleEndian(num_keys, *keys_stream);
        dict_inner_serialization->serializeBinaryBulk(*nested_column, *keys_stream, 0, num_keys);
        low_cardinality_state->shared_dictionary = nullptr;
    }

    if (need_additional_keys)
    {
        UInt64 num_keys = keys->size();
        writeBinaryLittleEndian(num_keys, *indexes_stream);
        dict_inner_serialization->serializeBinaryBulk(*keys, *indexes_stream, 0, num_keys);
    }

    UInt64 num_rows = positions->size();
    writeBinaryLittleEndian(num_rows, *indexes_stream);
    auto index_serialization = index_version.getDataType()->getDefaultSerialization();
    index_serialization->serializeBinaryBulk(*positions, *indexes_stream, 0, num_rows);

The default limit is 8192 keys:

cpp
// src/Core/Settings.cpp:5045
    DECLARE(UInt64, low_cardinality_max_dictionary_size, 8192, R"(
Sets a maximum size in rows of a shared global dictionary for the [LowCardinality](/reference/data-types/lowcardinality) data type that can be written to a storage file system. This setting prevents issues with RAM in case of unlimited dictionary growth. All the data that can't be encoded due to maximum dictionary size limitation ClickHouse writes in an ordinary method.

Possible values:

- Any positive integer.
)", 0) \

So: with an 8192-key limit, a part whose column has 100 distinct values writes the dictionary once; a part with 100 000 distinct values writes the dictionary roughly every 8192 keys and starts a new one.

Note that need_update_dictionary is global_dictionary == nullptr — i.e. “this granule starts a new dictionary”. And the dictionary is flushed after the header was written, so the header says “read the dictionary” and the dictionary follows in the keys stream.

Reading: the reader has to reconstruct the same state

The read side keeps the shared dictionary in the deserialize state, along with a flag that survives granule skips:

cpp
// src/DataTypes/Serializations/SerializationLowCardinality.cpp:240
struct DeserializeStateLowCardinality : public ISerialization::DeserializeBinaryBulkState
{
    KeysSerializationVersion key_version;
    ColumnUniquePtr global_dictionary;

    IndexesSerializationType index_type{};
    ColumnPtr additional_keys;
    ColumnPtr null_map;
    UInt64 num_pending_rows = 0;

    /// If dictionary should be updated.
    /// Can happen is some granules was skipped while reading from MergeTree.
    /// We should store this flag in State because
    ///   in case of long block of empty arrays we may not need read dictionary at first reading.
    bool need_update_dictionary = false;

    /// True if this part has a single dictionary for the entire column. The prefix
    /// reader first checks `has_uniform_marks_callback` as a cheap prefilter, then
    /// verifies it by reading the first dictionary and checking that `DictionaryKeys`
    /// reached EOF. When true, non-continuous reads (granule skips) do not invalidate
    /// the cached dictionary, and the dictionary can be shared across all threads via `clone`.
    bool single_dictionary_for_part = false;

    explicit DeserializeStateLowCardinality(UInt64 key_version_) : key_version(key_version_) {}

    ISerialization::DeserializeBinaryBulkStatePtr cloneImpl(ISerialization::DeserializeBinaryBulkStateCloneContext &) const override
    {
        return std::make_shared<DeserializeStateLowCardinality>(*this);
    }
};

The need_update_dictionary comment is the interesting one: when reading is not continuous (i.e. some granules were skipped), the reader cannot assume that the dictionary it holds is the one the next granule refers to, so it must force a re-read. That flag lives in the state, not on the stack, precisely because a skipped granule may be discovered long after the state was created.

The main read loop:

cpp
// src/DataTypes/Serializations/SerializationLowCardinality.cpp:752
    if (!settings.continuous_reading)
    {
        low_cardinality_state->num_pending_rows = 0;

        /// Some granules were skipped; the next granule header may signal a dictionary
        /// update. For multi-dict parts this forces a re-read at the next boundary.
        low_cardinality_state->need_update_dictionary = true;
    }

    while (limit)
    {
        if (low_cardinality_state->num_pending_rows == 0)
        {
            if (indexes_stream->eof())
                break;

            auto & index_type = low_cardinality_state->index_type;
            auto & global_dictionary = low_cardinality_state->global_dictionary;

            index_type.deserialize(*indexes_stream, settings);

            bool need_update_dictionary =
                !global_dictionary || index_type.need_update_dictionary || low_cardinality_state->need_update_dictionary;
            if (index_type.need_global_dictionary && need_update_dictionary)
            {
                /// For single-dict parts the in-memory dictionary is valid for the entire part,
                /// so skip re-reading it even if the stream was seeked back to the beginning.
                if (!low_cardinality_state->single_dictionary_for_part || !global_dictionary)
                    read_dictionary();
                low_cardinality_state->need_update_dictionary = false;
            }

            if (low_cardinality_state->index_type.has_additional_keys)
                read_additional_keys();
            else
                low_cardinality_state->additional_keys = nullptr;

            readBinaryLittleEndian(low_cardinality_state->num_pending_rows, *indexes_stream);
        }

        size_t num_rows_to_read = std::min<UInt64>(limit, low_cardinality_state->num_pending_rows);
        read_indexes(num_rows_to_read);
        limit -= num_rows_to_read;
        low_cardinality_state->num_pending_rows -= num_rows_to_read;
    }

num_pending_rows is what makes a granule’s worth of rows readable in chunks: the header is read once, then the reader consumes num_pending_rows rows from the index stream, and only when that counter hits zero does it look for the next header.

The single-dictionary-for-part fast path

There is a special case worth highlighting: a part where the column has exactly one dictionary for the whole part. The prefix reader detects it by reading the first dictionary and checking whether the DictionaryKeys stream reached EOF:

cpp
// src/DataTypes/Serializations/SerializationLowCardinality.cpp:348
    if (might_have_single_dictionary && !stream->eof())
    {
        /// For `Wide` parts that might have a single dictionary, the stream is
        /// now positioned right at the dictionary data (after the version).
        /// Read the first dictionary and check EOF afterwards. If this proves
        /// that there are no more dictionaries, all threads sharing this prefix
        /// state via `DeserializationPrefixesCache` get the dictionary through
        /// a `shared_ptr` clone instead of each reading it independently.

and

cpp
// src/DataTypes/Serializations/SerializationLowCardinality.cpp:377
        if (stream->eof())
        {
            new_state->single_dictionary_for_part = true;
            new_state->global_dictionary = std::move(global_dictionary);
        }
        else
        {
            /// The mark heuristic can be fooled by several dictionaries written
            /// inside one mark interval. Reset the `DictionaryKeys` stream back
            /// to the normal post-prefix position and let data deserialization
            /// read dictionary updates from the stream.
            if (!settings.seek_to_start_callback)
                throw Exception(ErrorCodes::LOGICAL_ERROR, "Cannot reset LowCardinality dictionary stream without seek_to_start_callback");

            settings.seek_to_start_callback(dictionary_keys_path);

            UInt64 repeated_keys_version = 0;
            readBinaryLittleEndian(repeated_keys_version, *stream);
            if (repeated_keys_version != keys_version)
                throw Exception(ErrorCodes::INCORRECT_DATA, "Inconsistent version while resetting LowCardinality dictionary stream");
        }

This is a heuristic with a verification step. The cheap check (has_uniform_marks_callback) says “all marks point at the same position in the keys stream, so maybe there is only one dictionary”. The expensive check (actually reading the dictionary and seeing EOF) confirms it. If the heuristic lied, the stream is rewound and the normal path takes over.

That’s a pattern you will see repeatedly in ClickHouse’s MergeTree reader: cheap prefilter, expensive confirmation, safe fallback.

When the fast path holds, cloneImpl copies the state (including the dictionary pointer) so every thread reading the part gets the same dictionary without re-reading it.

The overflow path on the read side

When a granule carries inline “additional keys”, the reader has to merge two dictionaries: the global one and the granule-local one. mapIndexWithAdditionalKeys does that with two flat maps — one for the global dictionary’s keys and one for the overflow keys:

cpp
// src/DataTypes/Serializations/SerializationLowCardinality.cpp:515
    /// Update column and return map with old indexes.
    /// Let N is the number of distinct values which are less than max_size;
    ///     old_column - column before function call;
    ///     new_column - column after function call:
    /// * if old_column[i] < max_size, than
    ///       dictionary_map[new_column[i]] = old_column[i]
    /// * else
    ///       additional_keys_map[new_column[i]] = old_column[i] - dict_size + N
    IndexMapsWithAdditionalKeys mapIndexWithAdditionalKeys(IColumn & column, size_t dict_size)

and then the keys are stitched back together:

cpp
// src/DataTypes/Serializations/SerializationLowCardinality.cpp:726
        else
        {
            auto maps = mapIndexWithAdditionalKeys(*indexes_column, global_dictionary->size());

            auto used_keys = IColumn::mutate(global_dictionary->getNestedColumn()->index(*maps.dictionary_map, 0));

            if (!maps.additional_keys_map->empty())
            {
                if (additional_keys == nullptr)
                    throw Exception(ErrorCodes::INCORRECT_DATA, "No additional keys found.");

                auto used_add_keys = additional_keys->index(*maps.additional_keys_map, 0);

                if (dictionary_type->isNullable())
                {
                    ColumnPtr null_map = ColumnUInt8::create(used_add_keys->size(), static_cast<UInt8>(0));
                    used_add_keys = ColumnNullable::create(used_add_keys, null_map);
                }

                used_keys->insertRangeFrom(*used_add_keys, 0, used_add_keys->size());
            }

            low_cardinality_column.insertRangeFromDictionaryEncodedColumn(*used_keys, *indexes_column);
        }

The final call re-inserts the merged keys into the destination column’s own dictionary and remaps the indexes one last time.

The whole thing in SQL

sql
CREATE TABLE events
(
    `ts`      DateTime,
    `user_id` UInt64,
    `kind`    LowCardinality(String),   -- 12 distinct values in 100M rows
    `country` LowCardinality(FixedString(2))
)
ENGINE = MergeTree
ORDER BY (ts, user_id);

sql
-- The dictionary is shared across every block of the part, so the per-column
-- cost is one byte per row (UInt8 index) plus the dictionary once.
SELECT kind, count() FROM events GROUP BY kind;

The type-level guarantee is that LowCardinality is only worth it while the dictionary stays small; the documentation says so plainly:

text

// src/DataTypes/DataTypeLowCardinality.cpp:198
The efficiency of using `LowCardinality` data type depends on data diversity. If a dictionary contains less than 10,000 distinct values, then ClickHouse mostly shows higher efficiency of data reading and storing. If a dictionary contains more than 100,000 distinct values, then ClickHouse can perform worse in comparison with using ordinary data types.

Trade-offs

What the hack buys you.

A LowCardinality(String) column with 12 distinct values costs one byte per row plus a few hundred bytes of dictionary, instead of ~10 bytes per row of strings. It also means the scan is a byte scan, not a string scan: filters, GROUP BY, and ORDER BY all operate on UInt8 indexes, and the dictionary is touched only for the rows that survive the filter.

What it costs you.

Every value access is two dependent loads: read the index, then read the dictionary entry. That is a pointer chase a plain String column does not have — although for a plain string column you also pay a pointer chase into the character arena, so the two are more comparable than they look.

The dictionary is a global per part, and the index stream has to carry a per-granule header with three flags and a row count, plus the possibility of inline overflow keys. A plain column has none of that. For a column with 100 000+ distinct values you have bought complexity and lost compression.

The sharing is also asymmetric: byteSize() excludes a shared dictionary while allocatedBytes() includes it. That is correct but subtle, and it means the two numbers in system.parts_columns can disagree in a way that looks like a bug until you know why.

The design decision that makes it work. The dictionary is not stored per block, and not per granule; it is stored per part, capped at 8192 keys, and flushed when it overflows. Everything else — the three header bits, the need_update_dictionary flag, the single_dictionary_for_part heuristic — exists to make that one decision survive partial reads, granule skips and multi-threaded readers.

Wrapping up

The one thing to remember: LowCardinality moves the repetition out of the rows and into a shared dictionary, and the whole design is about making that dictionary shared — across blocks, granules, parts, and threads.

The rule of thumb: below ~10 000 distinct values, use it. Above ~100 000, don’t. In between, measure.

What to go do about it: count the distinct values in your “status” or “country” columns (uniqExact), then wrap them. One byte per row instead of ten is not a rounding error on a hundred-million-row table.