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<br>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:

External or parallel merge sort, which can be used to implement ORDER BY, JOIN and WINDOW function operators.

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) {<br>sorting_queue.add(Cursor(stream));

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

min_element = min_cursor.value()<br>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]<br>cursor_1: [2, 2, 3]<br>cursor_2: [2, 3, 3]<br>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,...