Opensource internals

ClickHouse's Merge Join Walks Two Sorted Streams and Skips Whole Runs

19 min read Jay Hubbert

ClickHouse's merge join sorts both sides, then advances two cursors in lockstep, using a fused compare-and-run-search to skip entire equal-key runs instead of comparing rows one at a time.

TL;DR: A merge join needs no hash table and no right side in memory — it needs both sides sorted. ClickHouse sorts them, then walks two cursors in lockstep. The interesting part is not the comparison but the skipping: one fused virtual call reports both the order of two rows and how far the run of lesser rows extends, so a whole group of equal keys is consumed in one step.

The hash join is the default because it is fast when the right side fits in memory. But it has a hard ceiling: the entire right table, every column of it, has to be resident. When it does not fit, the alternatives are a spilling hash join or a merge join — and the merge join is the one that streams.

A merge join’s contract is simple: if both inputs are sorted by the join key, the join is a linear walk. Two cursors, each pointing at the current row; compare the keys; whichever side is smaller can be skipped entirely. The result is a streaming join with O(1) memory beyond the two blocks in flight.

That contract has a price — the inputs have to be sorted — and the whole implementation is about paying that price as cheaply as possible, and about the awkward fact that a merge join can only be parallelised if you first shuffle.

sql 
SELECT l.id, r.payload
FROM left_table AS l
FULL JOIN right_table AS r ON l.id = r.id
SETTINGS join_algorithm = 'full_sorting_merge';

The shape of the execution, with the two cursors walking towards each other:

text 
   LEFT input (sorted by id)              RIGHT input (sorted by id)
   +----------------------+               +----------------------+
   | 1  2  3  4  5  6  7  |               |  2  4  4  6  8  9  |
   +----------------------+               +----------------------+
     ^cursor                                 ^cursor
     |                                        |
     |  compareTrackAt: "how far does the run of lesser rows go?"     |
     +----------------> 2 <--------------------+
                       |
                       v  equal key: the two runs are cross-joined
            left rows [2]  x  right rows [2]
            left rows [4]  x  right rows [4, 4]

   result (index maps, then gathered):
   +------------------------------------------+
   | (1, defaults) (2, r2) (4, r4a) (4, r4b)  |
   | (5, defaults) (6, r6) (7, defaults) ...   |
   +------------------------------------------+

The join object is a dummy

The first surprise is that the object representing the join in the query plan does nothing at all:

cpp 
// src/Interpreters/FullSortingMergeJoin.h:20
/// Dummy class, actual joining is done by MergeTransform
class FullSortingMergeJoin : public IJoin
{
public:
    explicit FullSortingMergeJoin(std::shared_ptr<TableJoin> table_join_, SharedHeader & right_sample_block_,
                                  int null_direction_ = 1, bool is_parallel_ = false)
        : table_join(table_join_)
        , right_sample_block(right_sample_block_)
        , null_direction(null_direction_)
        , is_parallel(is_parallel_)
    {

It cannot even accept data:

cpp 
// src/Interpreters/FullSortingMergeJoin.h:61
    bool addBlockToJoin(const Block & /* block */, size_t /* num_rows */, JoinBuildContext /* context */) override
    {
        throw Exception(ErrorCodes::LOGICAL_ERROR, "FullSortingMergeJoin::addBlockToJoin should not be called");
    }

All it carries is the shape of the join and one interesting bit of state: the pipeline shape. A hash join is “fill the right side first, then probe”; a merge join needs both sides running at once, so it declares a Y-shaped pipeline:

cpp 
// src/Interpreters/FullSortingMergeJoin.h:176
    /// Left and right streams have the same priority and are processed simultaneously
    JoinPipelineType pipelineType() const override { return JoinPipelineType::YShaped; }

The real engine is MergeJoinTransform, a merging processor with two input ports. Before it can run, the planner has to make both inputs sorted.

The planner sorts both sides

When the physical join step is built and the algorithm is a merge join, the planner inserts a full sort on each side:

cpp 
// src/Processors/QueryPlan/JoinStepLogical.cpp:1697
    auto add_sorting = [&] (QueryPlan::Node *& node, const Names & key_names, JoinTableSide join_table_side)
    {
        SortDescription sort_description;
        sort_description.reserve(key_names.size());
        for (const auto & key_name : key_names)
            sort_description.emplace_back(key_name);

        auto sorting_step = std::make_unique<SortingStep>(
            node->step->getOutputHeader(), std::move(sort_description), 0 /*limit*/, sort_settings, true /*is_sorting_for_merge_join*/);
        sorting_step->setStepDescription(fmt::format("Sort {} before JOIN", join_table_side), max_step_description_length);
        node = &nodes.emplace_back(QueryPlan::Node{std::move(sorting_step), {node}});
    };

Two SortingSteps, one per side, both flagged is_sorting_for_merge_join. That flag matters later: it tells the optimisers that this sort exists only to feed the merge join, so it must not be treated as an ordering the user asked for.

If a side comes out of the sort with more than one stream, the pipeline builder merges them back into one sorted stream, because the merge join takes exactly one input per side:

cpp 
// src/QueryPipeline/QueryPipelineBuilder.cpp:390
    else if (left->getNumStreams() != 1 || right->getNumStreams() != 1)
    {
        /// `MergeJoinTransform` below takes exactly one input per side. The streams are already sorted by the
        /// join keys, so a sorted merge on those keys preserves the order it requires.
        auto merge_to_single_sorted_stream = [&](std::unique_ptr<QueryPipelineBuilder> & pipeline, const Names & key_names)
        {
            if (pipeline->getNumStreams() <= 1)
                return;

            SortDescription sort_description;
            sort_description.reserve(key_names.size());
            for (const auto & key_name : key_names)
                sort_description.emplace_back(key_name);

            auto transform = std::make_shared<MergingSortedTransform>(
                pipeline->getSharedHeader(),
                pipeline->getNumStreams(),
                sort_description,
                max_block_size,
                /*max_block_size_bytes=*/ 0,
                /*max_dynamic_subcolumns=*/ std::nullopt,
                SortingQueueStrategy::Default);

Before sorting: filter with a set

There is an optimisation that runs before the sort, and it is the one that makes merge joins practical on skewed data. If one side is small, build a hash set of its keys and filter the other side with it:

cpp 
// src/Processors/QueryPlan/JoinStepLogical.cpp:1743
    if (join_settings.max_rows_in_set_to_optimize_join > 0 && join_type_allows_filtering && has_non_const_keys)
    {
        auto * left_set = add_create_set(left_node, join_clause.key_names_left, JoinTableSide::Left);
        auto * right_set = add_create_set(right_node, join_clause.key_names_right, JoinTableSide::Right);

        if (isInnerOrLeft(join_kind))
            right_set->setFiltering(left_set->getSet());

        if (isInnerOrRight(join_kind))
            left_set->setFiltering(right_set->getSet());
    }

The set is built while the stream is being read — the CreatingSetsOnTheFly transform inserts into it as blocks arrive — and the other side is filtered against it once it is complete. If the set turns out to be too big, the whole thing is abandoned and the join proceeds unfiltered:

cpp 
// src/Processors/Transforms/CreateSetAndFilterOnTheFlyTransform.cpp:114
    if (chunk.getNumRows())
    {
        Columns key_columns = getColumnsByIndices(chunk, key_column_indices);
        bool limit_exceeded = !set->insertFromColumns(key_columns);
        if (limit_exceeded)
        {
            auto prev_state = set->state.exchange(SetWithState::State::Suspended);
            /// Print log only after first state switch
            if (prev_state == SetWithState::State::Creating)
            {
                LOG_DEBUG(log, "{}: set limit exceeded, give up building set, after reading {} rows and using {}",
                    getDescription(), set->getTotalRowCount(), formatReadableSizeWithBinarySuffix(set->getTotalByteCount()));
            }

The filter side checks the state before filtering, and only filters if the set actually reached the “finished” state:

cpp 
// src/Processors/Transforms/CreateSetAndFilterOnTheFlyTransform.cpp:178
    bool can_filter = set && set->state == SetWithState::State::Finished;
    if (!can_filter)
        stat.consumed_rows_before_set += chunk.getNumRows();

    if (can_filter && chunk.getNumRows())
    {
        auto key_columns = getColumnsByIndices(key_sample_block, chunk, key_column_indices);
        ColumnPtr mask_col = set->execute(key_columns, false);

This is a “semi-join reduction” and it is the difference between sorting and comparing a hundred million rows and sorting and comparing a hundred thousand. The setting that controls it is off by default:

cpp 
// src/Core/Settings.cpp:4537
    DECLARE(UInt64, max_rows_in_set_to_optimize_join, 0, R"(
Maximal size of the set to filter joined tables by each other's row sets before joining.

Possible values:

- 0 — Disable.
- Any positive integer.
)", 0, \
        {"24.1", 100000, 0, "Disable join optimization as it prevents from read in order optimization"}) \

It was disabled by default in 24.1 because the set has to be built before the filter can run, which blocks the “read in order” optimisation — a MergeTree table read in primary-key order can no longer stream into the join.

The cursor

Each side of the join is a FullMergeJoinCursor: a chunk, a position, and the key columns pre-processed. The pre-processing matters — LowCardinality is expanded and Nullable is split into a null map plus a nested column, so the comparison loop never has to deal with either:

cpp 
// src/Processors/Transforms/MergeJoinTransform.cpp:470
    const auto & all_columns = current_chunk.getColumns();
    for (size_t i : key_indices)
    {
        auto column = all_columns.at(i);
        column = column->convertToFullColumnIfLowCardinality();
        ColumnPtr null_map = nullptr;
        if (const auto * column_nullable = checkAndGetColumn<ColumnNullable>(column.get()))
        {
            null_map = column_nullable->getNullMapColumnPtr();
            column = column_nullable->getNestedColumnPtr();
        }
        null_maps.push_back(std::move(null_map));
        sort_columns.push_back(std::move(column));
    }

The fused comparison

Here is the mechanism the whole join is built around. A merge join does not just need to know which row is smaller; it needs to know how many consecutive rows on the smaller side are also smaller. If the left side has a thousand rows with key 5 and the right side’s current key is 7, all thousand left rows are smaller, and the join can consume all thousand at once.

The naive implementation compares two rows, and then separately searches for the end of the run — two passes over the same data. ClickHouse fuses them into one virtual call, and the contract is spelled out on the column interface:

cpp 
// src/Columns/IColumn.h:547
    /** Compares (*this)[n] and rhs[m] like compareAt, additionally reporting how far the run of
      * lesser values on the lesser side extends. Returns 0 if the values are equal; -N if rows
      * [n, n + N) of *this are all less than rhs[m]; +N if rows [m, m + N) of rhs are all less
      * than (*this)[n]. N >= 1 and the runs are maximal.
      *
      * PRECONDITION: the tail of the lesser column (starting at n, respectively m) is sorted
      * ascending consistently with compareAt under the same nan_direction_hint; the run end is
      * found by galloping (findEqualRangeEndAssumeSorted), which relies on it.
      *
      * The main reason for the function is to fuse the comparison and the run search into one
      * virtual call. IColumnHelper implements it for all concrete columns with devirtualized
      * compareAt probes; ColumnVector, ColumnDecimal and ColumnFixedString specialize it to probe
      * raw data with the per-call setup (data pointers, the Decimal scale dispatch) hoisted out
      * of the run search.
      */
    [[nodiscard]] virtual Int64 compareTrackAt(size_t n, size_t m, const IColumn & rhs, int nan_direction_hint) const = 0;

The run search itself is a galloping search, preceded by a short linear probe — because short runs are the common case and a binary search on a run of length two is pure overhead:

cpp 
// src/Columns/findEqualRangeEndAssumeSorted.h:94
/** Returns the end (exclusive) of the run of values equal to the value at `begin`, within the sorted
  * range `[begin, end)`. The predicate `equals(i)` must report whether the value at row `i` equals the
  * value at `begin`.
  *
  * The search first does a short linear probe, which is cheap for the common case of short,
  * high-cardinality runs. If the run extends past that probe, it switches to galloping (an exponential
  * probe) followed by a binary search, so for a long run it issues only O(log run) calls to `equals`
  * instead of O(run).
  *

And the shared tail is deliberately ALWAYS_INLINE, with a measured reason:

cpp 
// src/Columns/findEqualRangeEndAssumeSorted.h:116
/** Shared tail of compareTrackAt (see IColumn::compareTrackAt): given `compare_result` for lhs[n] vs
  * rhs[m], find the end of the run of lesser rows on the lesser side by galloping. The predicate
  * is_less(row) must report lhs[row] < rhs[m], and is_greater(row) must report lhs[n] > rhs[row];
  * the sorted-tail precondition of compareTrackAt applies to the probed side.
  *
  * ALWAYS_INLINE: the merge joins call compareTrackAt once per loop iteration; leaving this as a
  * separate call behind the virtual one costs ~10% on interleaved short-run keys.
  */

Ten percent, for one ALWAYS_INLINE. That is the kind of number that tells you the loop is the bottleneck.

The merge loop uses it like this:

cpp 
// src/Processors/Transforms/MergeJoinTransform.cpp:660
        while (left_cursor.isValid() && right_cursor.isValid())
        {
            lpos = left_cursor.getRow();
            rpos = right_cursor.getRow();

            /// Compare the first key column once: a nonzero result decides the whole tuple
            /// comparison and carries the run of lesser rows that can be skipped at once.
            FirstKeyCompare first_key = trackCursorsFirstKey(left_cursor, right_cursor, null_direction_hint);
            cmp = first_key.cmp != 0 ? first_key.cmp : compareCursors(left_cursor, lpos, right_cursor, rpos, null_direction_hint, /*from_key=*/ 1);

Note the structure: the first key column is compared with compareTrackAt, which both decides the order and measures the run. Only if the first columns are equal does the code walk the remaining key columns — and then it starts at column 1, because column 0 has already been compared.

Equal runs

When the keys are equal, the join has to emit the cross product of the two equal ranges (for an ALL join). The end of an equal range is found with a per-column search:

cpp 
// src/Processors/Transforms/MergeJoinTransform.cpp:222
size_t ALWAYS_INLINE nextDistinct(FullMergeJoinCursor & impl)
{
    chassert(impl.isValid());
    const size_t start_pos = impl.getRow();

    /// Find the end of the run of rows that share the same (multi-column) key, starting at start_pos.
    const size_t run_end = impl.key_runs.findRunEnd(
        start_pos,
        impl.rows,
        [&](size_t i, size_t from, size_t bound)
        {
            const auto * nm = getNullMapData(impl.null_maps[i]);
            const bool ref_is_null = nm && (*nm)[from] != 0;

            size_t column_run_end = bound;
            if (nm)
                column_run_end
                    = findEqualRangeEndAssumeSorted(from, column_run_end, 16, [&](size_t row) { return ((*nm)[row] != 0) == ref_is_null; });

            if (!ref_is_null)
                column_run_end = impl.sort_columns[i]->getEqualRangeEndAssumeSorted(from, column_run_end, 1);

            return column_run_end;
        });
    impl.pos = run_end;
    return run_end - start_pos;
}

key_runs is a SortedKeyRuns, which remembers the run found for each key prefix, so a multi-column key search does not restart from column 0 every time:

cpp 
// src/Columns/findEqualRangeEndAssumeSorted.h:168
/** Same result as `findKeyRangeEndAssumeSorted`, for callers that search the runs of one range one after another.
  * Remembers the last run found for each key prefix: a search from a row inside it ends at the same row, so a column
  * is searched again only when the search leaves its prefix's run. Call `reset` when the columns change, or when `end`
  * changes and the next search may start before the previous `end`.
  */
class SortedKeyRuns

The output is an index map, not a copy

The join does not copy rows as it goes. It computes, for each side, an array of row indices into the current block, and the result block is built at the end by gathering through those indices:

cpp 
// src/Processors/Transforms/MergeJoinTransform.cpp:195
ColumnPtr indexColumn(const ColumnPtr & column, const DataTypePtr & type, const PaddedPODArray<UInt64> & indices)
{
    auto new_col = column->cloneEmpty();
    new_col->reserve(indices.size());
    for (size_t idx : indices)
    {
        /// Rows where a default should be inserted have index == size. Fill them through the
        /// data type: types whose default is not all-zero (e.g. Enum, whose default is the
        /// first member) must not get a raw zero. Every non-joined-row fill in this file goes
        /// through the data type for the same reason.
        if (idx < column->size())
            new_col->insertFrom(*column, idx);
        else
            type->insertDefaultInto(*new_col);
    }
    return new_col;
}

An index equal to the column’s size means “this row did not match”; the default is filled in. Note that the index map doubles as the filter: for an INNER join, the unmatched left rows simply never appear in the map.

For an ALL join the index maps are built as a cross product of the two equal ranges:

cpp 
// src/Processors/Transforms/MergeJoinTransform.cpp:676
                bool all_fit_in_block = !max_block_size || std::max(left_map.size(), right_map.size()) + lnum * rnum <= max_block_size;
                bool have_all_ranges = left_cursor.isValid() && right_cursor.isValid();
                if (all_fit_in_block && have_all_ranges)
                {
                    /// fast path if all joined rows fit in one block
                    for (size_t i = 0; i < rnum; ++i)
                    {
                        addRange(left_map, lpos, left_cursor.getRow());
                        addMany(right_map, rpos + i, lnum);
                    }
                }

lnum * rnum is the size of the cross product. If it does not fit in one block, the join switches to the “accumulate and cross” mode, where the equal ranges are buffered in AllJoinState and the product is walked incrementally:

cpp 
// src/Processors/Transforms/MergeJoinTransform.cpp:790
    if (all_join_state)
    {
        chassert(cursors.size() == 2);
        /// Accumulate blocks with same key in all_join_state
        for (size_t i = 0; i < 2; ++i)
        {
            if (cursors[i].isValid() && all_join_state->keys[i].equals(cursors[i]))
            {
                size_t pos = cursors[i].getRow();
                size_t num = nextDistinct(cursors[i]);
                stat.matched_rows.side(i) += num;
                all_join_state->addRange(i, cursors[i].getCurrent().clone(), pos, num);
            }
        }

The ANY case has to remember the previous block

An ANY join emits one row per matching key — but the match may be in the next block of the other side. When the left cursor runs out, the join has to remember the key it was on and the right row it matched, so the next call can complete the match:

cpp 
// src/Processors/Transforms/MergeJoinTransform.h:67
/// Remembers previous key if it was joined in previous block
class AnyJoinState : boost::noncopyable
{
public:
    void set(size_t source_num, const FullMergeJoinCursor & cursor);
    void setValue(Chunk value_);

    void reset(size_t source_num);

    bool empty() const;

    /// current keys
    JoinKeyRow keys[2];

    /// for LEFT/RIGHT join use previously joined row from other table.
    Chunk value;

JoinKeyRow is a materialised copy of the key columns of one row — one row of one-row columns — because the block it came from may be gone by the time the state is checked.

ASOF

ASOF is the odd one out: it is not an equality join but an inequality join — “the closest row on the right whose ASOF column is at most mine”. The merge join implements it by walking the right side and remembering the last row that satisfied the inequality:

cpp 
// src/Processors/Transforms/MergeJoinTransform.cpp:845
std::optional<MergeJoinAlgorithm::Status> MergeJoinAlgorithm::handleAsofJoinState()
{
    if (strictness != JoinStrictness::Asof)
        return {};

    if (!cursors[1].fullyCompleted())
        return {};

The right side has to be complete before an ASOF match can be decided, because the closest match might be further down the right stream. So the ASOF path buffers the whole right side’s relevant state — it is the one strictness that cannot be fully streaming.

Parallelism: sharding by hash

A single merge join is single-threaded: two cursors, one thread. To use several threads, the join has to be sharded, and the only way to shard a merge join is to shuffle the rows by a hash of the join key so that equal keys end up in the same shard on both sides:

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoinByShards.cpp:518
/// Shard a `parallel_full_sorting_merge` join into independent per-shard merge joins by the hash of the
/// join keys.
///
/// Unlike `optimizeJoinByShards` above (which shards by primary-key ranges and only works when both sides
/// read from MergeTree in order), this works on any unsorted input: each side's pre-join full
/// `SortingStep` is switched to scatter the rows by the hash of the join keys into independent partitions
/// and sort each partition (one sorted stream per shard), and the join is executed shard-by-shard

The rewrite is guarded by a surprising number of conditions, and the comments explain why each one exists. The first is that only the parallel variant may be sharded — because the sharded result is unordered, and silently changing the ordering of a query that asked for full_sorting_merge would be wrong:

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoinByShards.cpp:548
            /// Only shard when `parallel_full_sorting_merge` was the algorithm actually selected. Both
            /// algorithms build the same `FullSortingMergeJoin`, so `join_algorithm` membership is not
            /// enough: with `full_sorting_merge,parallel_full_sorting_merge` the priority list selects plain
            /// `full_sorting_merge` and the parallel variant is an unreached fallback, so the sharded
            /// (unordered) rewrite must not fire. `FullSortingMergeJoin::isParallel` carries the selected
            /// algorithm over from `chooseJoinAlgorithm`.

The second is ASOF, whose trailing key is an inequality key, so rows with equal equality keys but different ASOF values would land in different shards and the closest match could be missed.

The third is the deadlock. This is the most interesting comment in the file:

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoinByShards.cpp:572
                /// An already-sorted side (`FinishSorting`: a MergeTree read in order, or any input
                /// recognized as pre-sorted) must NOT be scattered, tempting as an order-preserving scatter
                /// is. It can deadlock: a `ScatterByPartitionTransform` does not consume new input until all
                /// partition chunks of the previous one are pushed, while its consumers (per-partition
                /// `MergingSortedTransform`s, per-shard `MergeJoinTransform`s) wait for a chunk of one
                /// specific input each. Two such scatters then form a circular wait - A blocked pushing to
                /// shard `i` whose merge waits on B, B blocked pushing to shard `j` whose merge waits on A
                /// (seen as `Logical error: Pipeline stuck` in the AST fuzzer). The full-sort path is immune
                /// while every shard lane is demanded: a sleeping lane never starts draining its input.

A ScatterByPartitionTransform will not read the next chunk until it has pushed all partitions of the current one; the consumers wait for one specific partition each; two such scatters deadlock on each other. The Full sort path is immune because every shard lane is demanded at once.

And the fourth is the hash/equality consistency of the key type. Float64 breaks it: -0.0 == +0.0 but they hash differently, and NaN == NaN in ClickHouse’s comparison but not in a hash:

cpp 
// src/Processors/QueryPlan/Optimizations/optimizeJoinByShards.cpp:599
                    /// Do not shard when a join key is (or contains) a type whose hash-based shard selection
                    /// is not consistent with the merge-join `compareAt` - floating-point (`-0.0` == `+0.0`,
                    /// NaN == NaN), `JSON`/`Object`, or `Dynamic` - so equal keys could land in different
                    /// shards and the match would be lost (see `keyTypeBreaksHashSharding`). If a key
                    /// column cannot be found to check its type, be conservative and skip sharding as well.

This is a real class of bug that only shows up in parallel merge joins: single-threaded, the comparison is exact; sharded, the hash decides.

The other way to parallelise: primary-key ranges

The most recent addition (enabled by default in 26.10) shards the join by primary key range instead of by hash, which needs no shuffle at all:

cpp 
// src/Core/Settings.cpp:3142
    DECLARE(Bool, query_plan_join_shard_by_pk_ranges, true, R"(
Execute a JOIN of two MergeTree tables as independent joins over primary-key ranges when the join keys contain a prefix of the primary key of both tables. Both tables are split into the same ranges by the values of that prefix (the same way `FINAL` splits parts into non-intersecting layers), so equal keys land in the same range, and each range is joined on its own thread.

For `full_sorting_merge` and `parallel_full_sorting_merge`, this replaces a single-threaded merge join over both tables with one streaming merge join per range, running in parallel, which is typically several times faster and uses several times less memory.

The trick is that the ranges are cut by the same key prefix on both sides, so a key can only match inside its own range — and each range’s join is a plain, independent merge join. No hash, no shuffle, no deadlock.

Trade-offs

What the merge join buys:

  • O(1) memory. Only the two current blocks are in flight. A join over a right table that does not fit in memory is possible.
  • No hash table, no hash collisions, no hashed fallback.
  • The comparison work is amortised over runs. One compareTrackAt call can consume thousands of rows.

What it costs:

  • Both sides must be sorted. The sort is the dominant cost unless the data is already ordered — and a sort is O(n log n) with a memory cost of its own, which can exceed the memory a hash join would have used.
  • It is single-threaded by construction. Parallelism needs either a shuffle (hash sharding) or a range split (primary-key ranges), and both have sharp edges: the float/NaN key hazard, the scatter deadlock, and the unordered output.
  • The join keys must have compatible types. String and Nullable(String) cannot be merged, and the check happens at plan time.
  • ASOF is not streaming. The right side must be complete before a match can be decided.
  • The set-based pre-filter is off by default, because it breaks the read -in-order optimisation.

Wrapping up

The one thing to remember: a merge join is a sorted join. The algorithm is trivial — two cursors, compare, advance — and all the engineering is in the skipping (compareTrackAt), in the sort that has to come first, and in the sharding that has to happen afterwards.

The part people get wrong: the merge join does not need the right side in memory, but it does need it sorted, and sorting is not free. A merge join on unsorted data is usually slower than a hash join, not faster.

What to go do about it: if you have a large join that is spilling or failing on memory, look at whether the tables are ordered by the join key. If they are, full_sorting_merge with query_plan_join_shard_by_pk_ranges gives you a parallel, streaming join with no shuffle. If they are not, and the right side is small enough to filter with a set, turn on max_rows_in_set_to_optimize_join and measure — the set is built while the stream is read, so it costs a hash table, not a second pass.

ClickhousePerformanceInternalsJoinsMerge join