ClickHouse Hashes Map Keys into Buckets So a One-Key Read Touches One Stream

TL;DR: Map(K, V) is not a hash table. It is an Array(Tuple(K, V)) — one flat list of key-value pairs plus an offsets array saying which pairs belong to which row. Since 26.3 that flat list can be split into hash buckets on disk: the key is SipHash’ed, hash % buckets picks a bucket, and each bucket becomes its own substream. A query that asks for m['k'] is rewritten to a subcolumn that reads exactly one bucket.

The obvious way to store a map is as a hash table: key → value, one lookup in constant time. ClickHouse does not do that, and the reason is instructive. A columnar database’s job is to answer range questions efficiently — read 10 000 consecutive rows and aggregate them — and a hash table is the wrong shape for that: it scatters the values of one row across memory.

So ClickHouse stores a map the boring way: a flat, row-major list of pairs. And that flat list is what makes the next trick possible.

The in-memory shape

The type says it outright:

cpp
// src/DataTypes/DataTypeMap.h:9
/** Map data type.
  * Map is implemented as two arrays of keys and values.
  * Serialization of type 'Map(K, V)' is similar to serialization.
  * of 'Array(Tuple(keys K, values V))' or in other words of 'Nested(keys K, valuev V)'.
  */

and the column agrees:

cpp
// src/Columns/ColumnMap.h:11
/** Column, that stores a nested Array(Tuple(key, value)) column.
 */

ColumnMap holds exactly one thing — a nested ColumnArray whose data is a ColumnTuple of two columns:

cpp
// src/Columns/ColumnMap.h:36
    WrappedPtr nested;
    StatisticsPtr statistics;

and the factory makes that structure explicit:

cpp
// src/Columns/ColumnMap.cpp:24
ColumnMap::Ptr ColumnMap::create(const ColumnPtr & keys, const ColumnPtr & values, const ColumnPtr & offsets, const StatisticsPtr & statistics_)
{
    auto nested_column = ColumnArray::create(ColumnTuple::create(Columns{keys, values}), offsets);
    return ColumnMap::create(nested_column, statistics_);
}

So a Map(String, UInt64) column with three rows is physically:

text
   ColumnMap
     └── nested : ColumnArray            (3 rows)
           ├── offsets : ColumnUInt64     [0, 2, 3, 5]   <- prefix sums
           └── data    : ColumnTuple
                 ├── keys   : ColumnString  ['a','b','c','d','e']
                 └── values : ColumnUInt64  [1,2,3,4,5]

row 0 owns pairs 0..1, row 1 owns pair 2, row 2 owns pairs 3..4. The offsets array is a ColumnVector<UInt64> — ClickHouse’s standard array offsets type:

cpp
// src/Columns/ColumnArray.h:67
    /** On the index i there is an offset to the beginning of the i + 1 -th element. */
    using ColumnOffsets = ColumnVector<Offset>;

Reading a row is two array lookups and a range scan:

cpp
// src/Columns/ColumnMap.cpp:74
void ColumnMap::get(size_t n, Field & res) const
{
    const auto & offsets = getNestedColumn().getOffsets();
    size_t offset = offsets[n - 1];
    size_t size = offsets[n] - offsets[n - 1];

    res = Map();
    auto & map = res.safeGet<Map>();
    map.reserve(size);

    for (size_t i = 0; i < size; ++i)
        map.push_back(getNestedData()[offset + i]);
}

Note the consequence, which surprises people: m['k'] is a linear scan of one row’s pairs. ClickHouse does not maintain a per-row index. The docs say so plainly: “the runtime of the operation is linear in the size of the map”.

The constructor enforces the invariants that make this shape safe: the nested column must be an array of tuples, the tuple must have exactly two elements (keys and values), and neither may be a ColumnConst (src/Columns/ColumnMap.cpp:38).

The column carries its own statistics

Here is the first genuinely surprising thing. ColumnMap has a second field next to nested — a small statistics object:

cpp
// src/Columns/ColumnMap.h:16
    /// Statistics about the average number of key-value pairs per map row.
    struct Statistics
    {
        Statistics() = default;
        Statistics(Float64 avg_, UInt64 count_) : avg(avg_), count(count_) {}

        /// Incrementally updates the running weighted average with statistics from another batch.
        void merge(const Statistics & other);

Two numbers: the running average number of pairs per row, and how many rows contributed to it.

Why does a column need to know its own density? Because the number of buckets to split into depends on it, and the number of buckets has to be decided when the part is written, not when it is read.

The statistics are trivially derivable from the offsets:

cpp
// src/Columns/ColumnMap.cpp:476
ColumnMap::Statistics ColumnMap::calculateStatisticsForRange(size_t start, size_t end) const
{
    const auto & offsets = getNestedColumn().getOffsets();
    size_t total_maps_size = offsets[ssize_t(end) - 1] - offsets[ssize_t(start) - 1];
    return Statistics(start == end ? 0 : static_cast<Float64>(total_maps_size) / static_cast<Float64>(end - start), end - start);
}

and they merge across parts with a weighted average, so a merged part knows the density of everything that went into it:

cpp
// src/Columns/ColumnMap.cpp:449
void ColumnMap::Statistics::merge(const Statistics & other)
{
    if (other.count == 0)
        return;

    avg = avg + (other.avg - avg) * static_cast<Float64>(other.count) / static_cast<Float64>(count + other.count);
    count += other.count;
}

and getOrCalculateStatistics() computes them lazily if nobody has (src/Columns/ColumnMap.cpp:483).

The bucketed serialization

The settings arrived in 26.3:

cpp
// src/Storages/MergeTree/MergeTreeSettings.cpp:429
    DECLARE(MergeTreeMapSerializationVersion, map_serialization_version, "basic", R"(
Controls the serialization method used for `Map` columns.

Possible values:

- basic — Use the standard serialization for `Map`.
- with_buckets — Split keys into buckets during serialization. Using buckets improves reading individual keys from the Map.

with three tuning knobs: max_buckets_in_map (default 32, hard maximum 256), map_buckets_strategy (default sqrt) and map_buckets_coefficient (default 1.0). A fourth setting, map_buckets_min_avg_size (default 32), disables bucketing entirely for maps with fewer than 32 keys per row.

Choosing the number of buckets

cpp
// src/DataTypes/Serializations/SerializationMap.cpp:988
size_t SerializationMap::calculateNumberOfBuckets(const ColumnMap::StatisticsPtr & statistics, size_t max_buckets, MergeTreeMapBucketsStrategy strategy, double coefficient, size_t min_avg_size)
{
    /// If a minimum average map size threshold is set and the average map size is below it,
    /// use a single bucket to avoid bucketing overhead for small maps.
    if (min_avg_size > 0 && statistics->avg < static_cast<Float64>(min_avg_size))
        return 1;

    UInt64 result = 0;
    switch (strategy)
    {
        /// Always use max_buckets_in_map regardless of the average map size.
        case MergeTreeMapBucketsStrategy::CONSTANT:
            result = max_buckets;
            break;
        /// Use round(coefficient * sqrt(avg_map_size)), good for sublinear growth of buckets.
        case MergeTreeMapBucketsStrategy::SQRT:
            result = static_cast<UInt64>(round(coefficient * sqrt(statistics->avg)));
            break;
        /// Use round(coefficient * avg_map_size), buckets grow proportionally to the average map size.
        case MergeTreeMapBucketsStrategy::LINEAR:
            result = static_cast<UInt64>(round(coefficient * statistics->avg));
            break;
    }
    return std::min(std::max(result, static_cast<UInt64>(1)), static_cast<UInt64>(max_buckets));
}

The sqrt strategy is the interesting default. If a row averages 100 keys, sqrt(100) = 10 buckets — so each bucket holds about 10 keys, and a one-key read touches roughly 1/10th of the column. If a row averages 10 000 keys, sqrt(10000) = 100, but the cap is 32, so you get 32 buckets of ~312 keys each. The cap is what keeps the number of substreams (and therefore the per-part file count and the merge cost) bounded.

Assigning a key to a bucket

One SipHash, one modulo:

cpp
// src/DataTypes/Serializations/SerializationMap.cpp:971
template <typename KeyColumn>
size_t getBucketForKeyImpl(const KeyColumn & key_column, size_t row, size_t buckets)
{
    if (buckets == 0)
        throw Exception(ErrorCodes::LOGICAL_ERROR, "Number of buckets cannot be zero");

    SipHash hash;
    key_column.updateHashWithValue(row, hash);
    return hash.get64() % buckets;
}

The hash is over the value of the key, so it works for any key type — String, Int64, UUID, DateTime. It is computed identically on the write path and on the read path, which is the only reason a reader can find the bucket without reading the column.

The write path

splitMapToBuckets walks the flat pair list and appends each pair to its bucket:

cpp
// src/DataTypes/Serializations/SerializationMap.cpp:1071
    for (size_t i = start; i != end; ++i)
    {
        size_t offset_start = src_offsets[ssize_t(i) - 1];
        size_t offset_end = src_offsets[ssize_t(i)];
        for (size_t j = offset_start; j != offset_end; ++j)
        {
            size_t bucket = getBucketForKeyImpl(src_keys, j, num_buckets);
            dst_keys[bucket]->insertFrom(src_keys, j);
            dst_values[bucket]->insertFrom(src_values, j);
            bucket_index_col.getData().push_back(static_cast<typename IndexColumn::ValueType>(bucket));
        }

        for (size_t bucket = 0; bucket < num_buckets; ++bucket)
            dst_offsets[bucket]->push_back(dst_keys[bucket]->size());
    }

Three things to notice:

Each bucket gets its own offsets array, so each bucket is itself a valid Map column — it just holds a subset of each row’s pairs.
The bucket_index_col records, for every pair in the original order, which bucket it went to. This is the “bucket indexes” substream, added in 26.8 to preserve the original key order.
The inner loop calls insertFrom on a concrete column type. The dispatch is a three-level macro (key type → value type → index type, DISPATCH_MAP_COLUMN_TYPE in src/DataTypes/Serializations/SerializationMap.cpp:1022) that resolves to a fully devirtualised splitMapToBucketsTyped for the common types.

The buckets are then serialized independently, one substream each:

cpp
// src/DataTypes/Serializations/SerializationMap.cpp:1366
        auto bucket_index_column = map_state->bucket_index_type->createColumn();
        auto map_buckets = splitMapToBuckets(column, offset, end, map_state->buckets, *bucket_index_column);
        for (size_t bucket = 0; bucket < map_state->buckets; ++bucket)
        {
            settings.path.push_back(SubstreamType::Bucket);
            settings.path.back().bucket = bucket;
            nested_serialization->serializeBinaryBulkWithMultipleStreams(extractNestedColumn(*map_buckets[bucket]), 0, map_buckets[bucket]->size(), settings, map_state->bucket_nested_states[bucket]);
            settings.path.pop_back();
        }

and a small “buckets info” stream records how many buckets there are, so the reader knows what to expect:

cpp
// src/DataTypes/Serializations/SerializationMap.cpp:782
    /// Determine the number of buckets from column statistics and write it to the stream.
    UInt64 buckets = 1;
    ColumnMap::StatisticsPtr statistics = assert_cast<const ColumnMap &>(column).getOrCalculateStatistics();
    buckets = calculateNumberOfBuckets(statistics, settings.max_buckets_in_map, settings.map_buckets_strategy, settings.map_buckets_coefficient, settings.map_buckets_min_avg_size);
    writeBinaryLittleEndian(buckets, *stream);
    map_state->buckets = buckets;

The bucket count is written in the prefix of the part, so it is known before any data is read.

The read path

Reading one key is a two-step affair. First the analyzer rewrites m['key'] into a subcolumn reference:

cpp
// src/Analyzer/Passes/FunctionToSubcolumnsPass.cpp:401
void optimizeFunctionArrayElementForMap(QueryTreeNodePtr & node, FunctionNode & function_node, ColumnContext & ctx)
{
    /// Replace `m['key']` (which is internally `arrayElement(m, 'key')`) with the subcolumn `m.key_<serialized_key>`.

The key has to be a compile-time constant — a dynamic key cannot become a fixed subcolumn:

cpp
// src/Analyzer/Passes/FunctionToSubcolumnsPass.cpp:410
    /// The key must be a compile-time constant — dynamic key lookups cannot be rewritten to a fixed subcolumn.
    const auto * second_argument_constant_node = function_arguments_nodes[1]->as<ConstantNode>();
    if (!second_argument_constant_node)
        return;

and the subcolumn name is the text serialization of the key:

cpp
// src/Analyzer/Passes/FunctionToSubcolumnsPass.cpp:434
    /// Serialize the key to its text representation to construct the subcolumn name,
    /// e.g. the string key "foo" becomes the subcolumn suffix "key_foo".
    WriteBufferFromOwnString buf;
    key_type->getDefaultSerialization()->serializeText(*tmp_key_column, 0, buf, FormatSettings());
    String subcolumn_name = String(DataTypeMap::KEY_SUBCOLUMN_PREFIX) + buf.str();

Second, the serialization for that subcolumn computes the bucket and reads only that one:

cpp
// src/DataTypes/Serializations/SerializationMapKeyValue.cpp:131
    /// Read the bucket count and determine which bucket the requested key belongs to.
    auto buckets_info_state = SerializationMap::deserializeBucketsInfoStatePrefix(settings, cache);
    const auto * buckets_info_state_concrete = checkAndGetState<SerializationMap::DeserializeBinaryBulkStateBucketsInfo>(buckets_info_state);
    map_key_value_state->bucket = SerializationMap::getBucketForKey(key, 0, buckets_info_state_concrete->buckets);

    /// Only initialize the nested state for the single bucket containing our key.
    settings.path.push_back(SubstreamType::Bucket);
    settings.path.back().bucket = map_key_value_state->bucket;
    map_nested_serialization->deserializeBinaryBulkStatePrefix(settings, map_key_value_state->nested_state, cache);
    settings.path.pop_back();

and the stream enumeration follows suit — only one bucket’s substreams are even named:

cpp
// src/DataTypes/Serializations/SerializationMapKeyValue.cpp:90
    /// Only enumerate the single bucket that contains the requested key.
    settings.path.push_back(SubstreamType::Bucket);
    settings.path.back().bucket = map_key_value_state->bucket;
    map_nested_serialization->enumerateStreams(settings, callback, next_data);
    settings.path.pop_back();

This is where the win is. In a MergeTree part, substreams are separate compressed files with their own marks. If only one bucket’s substreams are enumerated, only one bucket’s files are opened and read. The other 31 buckets are not “skipped” — they are never touched.

Finally, the value is extracted from the bucket’s map:

cpp
// src/DataTypes/Serializations/SerializationMapKeyValue.cpp:181
    /// Extract the value for the requested key from the deserialized Map data.
    extractKeyValueFromMap(*nested_column, *key, column, nested_column->size() - num_read_rows, nested_column->size());

which is a scan of the bucket’s pairs, not the whole column: phase 1 finds the position of the key in each row, phase 2 extracts the values at those positions (src/DataTypes/DataTypeMapHelpers.cpp:561).

Reassembling the whole map

When the query wants the entire map, all buckets are read and stitched back together. Since 26.8 the bucket_indexes substream makes that stitch order-preserving:

cpp
// src/DataTypes/Serializations/SerializationMap.cpp:1211
        for (size_t j = 0; j < total_size; ++j)
        {
            size_t bucket_idx = bucket_index_data[bucket_index_offset++];
            if (bucket_idx >= map_buckets.size())
                throw Exception(ErrorCodes::INCORRECT_DATA, "Bucket index {} is out of range, total buckets: {}", bucket_idx, map_buckets.size());
            size_t pos = bucket_positions[bucket_idx]++;
            map_keys_column.insertFrom(*map_keys_buckets[bucket_idx], pos);
            map_values_column.insertFrom(*map_values_buckets[bucket_idx], pos);
        }

Before 26.8 there was no such stream, and a full read reassembled the map in bucket order — the original key order was simply not recoverable, because it was never stored.

A note on the offsets

One more detail of the nested layout that leaks into every reader. In memory the array offsets are a prefix sum; on disk, a substream can carry either absolute offsets or per-row sizes — the difference of two consecutive offsets (src/DataTypes/Serializations/SerializationArray.cpp:168). Sizes compress better (they are small and often equal) and let a reader decode any row without knowing the offsets before it. The in-memory column always uses offsets, and the conversion is arrayOffsetsToSizes in one direction and insertArraySizesToOffsets in the other.

The SQL

sql
CREATE TABLE events
(
    id    UInt64,
    props Map(String, UInt64)
)
ENGINE = MergeTree
ORDER BY id
SETTINGS
    map_serialization_version = 'with_buckets',
    max_buckets_in_map = 32,
    map_buckets_strategy = 'sqrt';

sql
-- reads one bucket per part, not the whole column
SELECT id FROM events WHERE props['user_id'] = 42;

-- reads everything, and pays for the reassembly
SELECT props FROM events;

With map_buckets_min_avg_size = 32 (the default), a table whose maps average fewer than 32 keys per row stays on the simple format whatever the other settings say.

Trade-offs

What bucketing buys: a one-key lookup reads 1/buckets of the column instead of all of it. With the default sqrt strategy and 32 buckets, that is a ~30x reduction in bytes read for a large map, at the cost of one extra hash per pair on the write path.

What it costs:

Insert overhead. Every pair is hashed and appended to a per-bucket column. The docs put it at 1.5–2.5x slower inserts.
Full scans are ~2x slower. Reading the whole map means reading all buckets and reassembling them, pair by pair.
The bucket count is per part. Two parts of the same table can have different bucket counts, because the count is derived from that part’s statistics. Merging recomputes it from the merged statistics.
Mixed formats. map_serialization_version_for_zero_level_parts lets you keep freshly inserted parts in basic format and only bucket them after a merge — which is the recommended setup, because inserts are the path where the overhead is most visible.
The float-zero trap. A key whose bits hash differently from its value (a float 0.0 versus an integer 0) lands in a different bucket, so the reader falls back to reading the whole map:

cpp
// src/DataTypes/DataTypeMap.cpp:214
    /// The bucket of a key is the hash of its bits. The two zeros are equal, but their bits differ,
    /// so the other zero may be in another bucket. A key with a float zero at any depth, e.g. in a `Tuple`
    /// or in a path of a `JSON`, reads the whole Map.
    bool read_whole_map = map_serialization.getMapSerializationVersion() == MergeTreeMapSerializationVersion::WITH_BUCKETS
        && anyFieldSatisfies((*key_column)[0], isFloatZeroField);

Wrapping up

The one thing to remember: the Map column is a flat list of pairs with an offsets array. Everything clever about it — the statistics, the buckets — is about making one lookup cheap without giving up the flat layout that makes everything else fast.

The part people get wrong: bucketing is off by default (map_serialization_version = "basic"). A table with big maps and key-lookups in the WHERE clause is leaving a 4–49x speedup on the table until you turn it on.

What to go do about it: measure your average map size first (SELECT avg(length(props)) FROM events). Under 32 keys per row, bucketing will not help and the default threshold keeps it off. Over that, turn on with_buckets for merged parts and compare PREWHERE queries that touch a single key against the same query on a basic part.