apache/spark — pull request #3173 by Ishiihara (2014-11-09 05:31:27+00:00)
Title: [SPARK-2213][SQL] Sort Merge Join 

This PR adds MergeJoin operator to Spark SQL. The semantics of MergeJoin operator is similar to Hive's Sort merge bucket join.

MergeJoin operator relies on SortBasedShuffle to create partitions that sorted by the join key. In each partition, we merge the two child iterators. The tricky part in merge step is handling duplicate join keys. To handle duplicate keys, we use a buffer to store all matching elements in right iterator for a certain join key. The buffer is used for generating join tuples when the join key of the next left element is the same as the current join key.

MergeJoin reduces extra memory consumption, in the current implementation, MergeJoin only needs memory that can hold elements of the key that has the most duplicates in right iterator.

For query optimization, we may resolve to MergeJoin when both relations are large and neither of the two can fit in memory. Currently, this heuristic is not added to optimizer. I would appreciate if you can add comments on how to resolve to MergeJoin in optimizer.

Currently, MergeJoin only supports inner join. However, it can be extended to support outer join. Will handle outer join in separate PRs.