Hash join vs merge join

A few months ago, I came across this article by a certain Justin Jaffray, where he makes the case that merge join has virtually disappeared from modern execution engines, and explores the reasons why. Simply put, his argument is as follows: merge join requires sorted data, and data in modern workflows increasingly comes from outside sources (e.g. data lakes) that the execution engine doesn’t control; therefore, it is rarely sorted.

While I totally agree with his assessment, reading that triggered a spark of curiosity: what do we miss by giving up on merge join? How does it compare with hash join? That was enough of an excuse to craft another benchmark. 😇

Choosing the right hash map🔗

Implementing a hash join is straightforward: choose one side (typically the smallest) and index it with a hash table: map each join key to the corresponding row index; that’s your “build” side. Then scan the other side—the “probe” side—and, for each row, look up the join key in the hash table.

The problem is that std::unordered_map is notoriously slow: in a typical implementation, each bucket would be realized as a linked list, which is bad both in terms of memory allocation and data locality. By contrast, serious execution engines use some form of “flat” hash map (a.k.a. “Swiss table”), where all the data is stored in a contiguous buffer, using linear probing to handle collisions (or one of its refinements, like cuckoo hashing). Consequently, we use Abseil’s flat_hash_map as a more realistic alternative for our benchmark.

Benchmark🔗

We dust up the join benchmark that we already used in previous articles, and put it to work with hash join. We try both std::unordered_map and absl::flat_hash_map.

Here are the results. The X axis represents the “skew factor” of the data, i.e. the inverse probability for a match (remember that this affects branch prediction). The Y axis is the throughput (higher is better).

As expected, Abseil beats the standard library thanks to its optimized implementation. But in all cases, both merge joins (naïve and branchless) are faster than Abseil.

Interestingly enough, as we saw in a previous article, the branchless implementation beats the naïve implementation when data is not too skewed, but the trend is reversed for high skew factors. That’s understandable: when the data is skewed, probabilities are biased, therefore branches become more and more predictable, eliminating one of the handicaps of the naïve version.

Conclusion🔗

Merge join beats hash join hands down. That remains true even when comparing a naïve merge join implementation to a reasonably optimized hash join. Of course, the data must be already sorted; including a pre-sorting step in merge join would completely tip the scales. Therefore, one can say merge join remains an invaluable niche algorithm: to be used only when the data is already sorted according to the join key, but unlocking greater performance when that precondition is satisfied.