K-way merge

Overview

In general, the k-way merge algorithm allows merging K sorted streams into a single sorted stream. This is one of the most fundamental algorithms, so it is well studied, and there are a lot of data structures that can be used.

The problem of merging multiple sorted streams can appear in a lot of different tasks:

1. External or parallel merge sort, which can be used to implement ORDER BY, JOIN and WINDOW function operators.
2. Merging data parts on disk in LSM tree or MergeTree engines.

For this task the Wikipedia article suggests:

The heap is more commonly used, although a tournament tree is faster in practice. A heap uses approximately 2*log(k) comparisons in each step because it handles the tree from the root down to the bottom and needs to compare both children of each node. Meanwhile, a tournament tree only needs log(k) comparisons because it starts on the bottom of the tree and works up to the root, only making a single comparison in each layer. The tournament tree should therefore be the preferred implementation.

My main motivation for this blog post is to show that in practice, on real data, you should almost never use a tournament tree/loser tree, and should use other data structures instead. I also researched a lot of data structures that can be used for this task, prepared a k-way-merge benchmark and have a concrete data structure that you should use instead, depending on your usage scenario. At the end, I will show some optimizations that are also used in practice and that can improve performance even more. Let’s go.

K-way merge basics

Let’s define K - the number of sorted streams that we want to merge, and N - the total number of elements that can be extracted from all K streams. In the rest of the article I will use cursors that point to streams, I will also assume that we try to sort elements in ascending order.

In practice, K is usually a small number, like the number of threads/streams that we use for merging, for example 32, 64, 128 or 256. In a scenario when you need to merge a lot of streams, most of the time multiple runs are used, where K stays small in each run.

In this article I focus on the number of comparisons, because in practice this is the most important metric. For example, in ClickHouse, where you compare long strings and rows from multiple columns, most of the time during a merge is spent on comparisons, so our goal will be to find a data structure that performs as few comparisons as possible.

The basic implementation of k-way merge can be described in pseudocode like this:

for (stream in streams) {
    sorting_queue.add(Cursor(stream));
}

while (!sorting_queue.isEmpty()) {
    /// sorting queue current() points to the min cursor
    min_cursor = sorting_queue.current();

    min_element = min_cursor.value()
    processElement(min_element)

    sorting_queue.next();
}

How sorting_queue maintains access to the min cursor and recalculates the current min cursor depends on the implementation. In a simple scenario, during the sorting_queue.next() call, the queue can iterate over all cursors and find the min cursor linearly, which would result in O(N * K) comparisons. Generally, though, some data structure with a logarithmic number of comparisons can be used, for example a heap/tournament tree/self-balanced tree, and then the running time will be O(N * log(K)).

Before diving deeper, please read about the Heap data structure and about the Tournament Tree data structure.

The main difference between a heap and a tournament tree is the number of comparisons. For a heap, to recalculate the min element (replace top), you need 2 * log(K) comparisons in the worst case, while a tournament tree performs only log(K) comparisons. But a heap gives a very important property that a tournament tree does not have: we can identify the next minimum cursor in O(1) comparisons. This is not unique to the heap; other sorting data structures have this property as well. Additionally, a heap will perform 2 * log(K) comparisons only in the worst case and can stop earlier, which matters a lot on real data, as I will show later.

Consider this special scenario: we have 4 cursors with low cardinality data:

cursor_0: [1, 1, 1, 2]
cursor_1: [2, 2, 3]
cursor_2: [2, 3, 3]
cursor_3: [3, 4, 4]

cursor_0 stays the minimum for its whole run of ones. If we know that cursor_0 is the min and cursor_1 is the next min cursor, we can compare elements from cursor_0 with cursor_1 and stop immediately, without any heap rebalance, because cursor_0 will still be the min cursor. A tournament tree does not know anything about the next min cursor, so it replays all matches on the path from the cursor_0 leaf to the root, performing 2 comparisons instead of the 1 performed by the heap.

In fact, tournament tree is an optimal data structure in a scenario where all elements are unique and are spread uniformly across cursors, but in practice the thing is that most of the time you have a lot of non-unique elements in your data, and depending on the cardinality of your data, you potentially want to know the next minimum cursor in your sorting queue.

The reader could ask: what if we try to somehow store or recalculate information about the next min cursor in a tournament tree/loser tree? I tried several approaches. For example:

1. Store the min and the next min in each node of the tournament tree. Recalculation becomes much more complex, with additional comparisons, but in the end the additional comparisons were never amortized.
2. When we know the min cursor, we know that the next min cursor is on our winner path, so we can compare log(K) elements on our winner path to find the next min cursor, but in the end the additional comparisons were never amortized.

For a tournament tree/loser tree I am not sure if it is possible to have O(1) comparisons for next min cursor access while keeping log(K) comparisons per element in the worst case.

From the comparisons point of view only, there are 2 good alternatives that can be used instead of a tournament tree, that will perform close to log(K) comparisons per element in the worst case and will allow O(1) comparisons for next min cursor access. When K <= 256, I suggest using a sorted array where each index is 1 byte, and if K > 256, I suggest using an in memory B-tree. As I will show later, there is a good in memory B-tree implementation in the Abseil library, so you don’t need to roll your own implementation.

In terms of comparisons, a sorted array performs exactly log(K) comparisons, because recalculation of the min cursor position is just a binary search over cursors. A B-tree performs log(K) * P comparisons, where 1 <= P < 2; check Best case and worst case heights if you are interested in precise numbers. In practice, the B-tree performed much fewer comparisons than other self balanced binary trees.

The problem with a sorted array is that you need to move on average half of the array during each min element recalculation, but if the number of elements is small (<= 256), this is very fast, because we can use a single byte to index a cursor. This is faster compared to the B-tree implementation, where you have a more complex code pipeline, indirections and potentially more cache misses. The sorted array implementation is small and simple; if you are interested, check SortedArray.h from my benchmark.

Additionally, there is a third option. If you want to have exactly log(K) comparisons, you can build an array on top of an Implicit Treap or any other self balanced binary tree. This will allow you to implement an array with element access in O(log(K)) and with the ability to insert into any array position in O(log(K)). During a binary search we need to perform log(K) lookups, and if each lookup is O(log(K)) operations, we will have O(log(K)^2) operations per min cursor recalculation instead of the O(K) operations per sorted array min cursor recalculation, and we will have exactly log(K) comparisons. So, overall, asymptotically this data structure is better than a sorted array, but in practice the implementation is quite complex, and there are a lot of indirections and cache misses. This makes sense in some scenarios, but in my benchmarks it seems that the B-tree is almost as good as the array in terms of comparisons when K > 256.

In production scenarios on real data, as I will show later, a heap is very competitive in terms of comparisons with a sorted array or a B-tree, and you need to change heap usage only if you understand that the time that you spend in comparisons significantly dominates the time spent on data structure internals.

Benchmark

I prepared a benchmark where I compared a lot of data structures for the k-way merge algorithm. The benchmark measures the number of comparisons per element instead of time. As I said before, in practice this is the most important metric: in databases you compare long strings and rows from multiple columns, and use comparators with virtual calls, so most of the merge time is spent inside comparisons. The comparisons count is also deterministic: it does not depend on hardware, compiler or optimization level, only on the algorithm, the data and the seed.

The benchmark works in two modes: generated random data and real data from a ClickHouse generated file.

In generated random data mode, the benchmark has 3 parameters:

1. N - number of elements.
2. K - number of cursors (sorted streams).
3. C - cardinality. Values are generated using a uniform integer distribution in [0, C), so cardinality controls the amount of duplicates: 1 - all values are equal, N - all values are almost surely unique.

Values are split into cursors in generation order (random layout): every cursor covers the whole value range.

In file mode, the benchmark takes K and a file with a UInt64 column exported from ClickHouse. The column is split into K contiguous ranges in file order, so cursor value ranges intersect the same way as in the original data.

In both modes, every cursor is sorted locally before the merge.

Elements are compared as (value, cursor_index) pairs, so comparisons form a total order and the merge is stable.

Results on real data: rank encoded columns of the ClickBench hits dataset (100 million rows), split into K = 256 cursors in table order, each cursor sorted locally and merged. Metric: average number of comparisons per element; lower is better, and the best result is in bold.

Results on random data:

As we can see, on real and random data the loser tree is not a good choice. The only scenario when you would want to use a loser tree is when you know your data distribution and you know that the cardinality of your data is very high. Also, on real data we can see that the heap is almost as good as the sorted array or the B-tree in terms of comparisons, but in terms of data structure operations the heap is much better, so I suggest using a heap if you are not sure whether comparisons will dominate merge time in your particular scenario.

Additionally, for the benchmark I first rolled a custom in memory B-tree implementation, but then I decided to check the Abseil B-tree implementation and got the same number of comparisons, so for practical usage I suggest using the Abseil B-tree.

Please check the full benchmark on GitHub: k-way-merge-benchmark.

Additional optimizations

Total order of cursors

When you have very low cardinality data, some data structures can perform more comparisons than needed to understand that your elements are actually the same. To avoid that, you can compare (element, cursor_index), where cursor_index is a unique integer that you attach to each cursor. That way you will have a total order of elements and potentially perform fewer comparisons.

Batch processing

With data structures that allow getting the next min cursor in O(1) comparisons, we can compare as many elements as we want from the min cursor with the next min cursor, and then extract them from the min cursor in a batch. This is very useful when you want to process elements in batches, reduce the amount of virtual function calls, etc.

We introduced this batch processing optimization in ClickHouse in this pull request.

For example, for sorting the low cardinality column Age:

SELECT DISTINCT Age FROM hits_100m_obfuscated;

┌─Age─┐
│   0 │
│  50 │
│  31 │
│  55 │
│  22 │
│  28 │
└─────┘

We got the following results. Before:

SELECT WatchID FROM hits_100m_obfuscated ORDER BY Age FORMAT Null;
0 rows in set. Elapsed: 4.154 sec. Processed 100.00 million rows, 900.00 MB (24.07 million rows/s., 216.64 MB/s.)

After:

SELECT WatchID FROM hits_100m_obfuscated ORDER BY Age FORMAT Null;
0 rows in set. Elapsed: 0.482 sec. Processed 100.00 million rows, 900.00 MB (207.47 million rows/s., 1.87 GB/s.)

In practice you can even play with the lookahead index; for example, you can compare the i-th element from the min cursor with the next min cursor’s first element. Additionally, you can compare the last element from the min cursor with the first element from the next min cursor, and if it is less, extract all elements from the min cursor at once. This optimization is used in ClickHouse and is important when you merge multiple sorted streams.

Summary

When choosing a data structure for k-way merge in production, I suggest the following order:

1. By default, use a heap. On real data it is almost as good as a sorted array or a B-tree in terms of comparisons, and its data structure operations are the cheapest.
2. If you measured that during merge of your data comparisons dominate the time spent on data structure operations, switch depending on K: if K <= 256, use a hand rolled sorted array with the batch optimization; if K > 256, use an in memory B-tree with the batch optimization.
3. Use a tournament tree/loser tree only if you know that the cardinality of your data is always very high and the data is spread uniformly across cursors; on sorted or clustered streams, adaptive structures will have a significant advantage. But even then, the win over a sorted array or a B-tree will be very small.

Even for such a well studied fundamental algorithm as k-way merge, there are a bunch of practical optimizations that can be applied to it. It is important to always measure performance on real data and in your scenarios, trying different data structures and algorithms.