apache/spark — pull request #2939 by kozanitis (2014-10-25 03:03:19+00:00)
Title: Add range join support to spark-sql

This PR enables spark-sql to join two tables based on the interval overlapping between their columns. This is a very useful feature to add as you can see here: https://issues.apache.org/jira/browse/HIVE-556

Syntax:
select * from table1 RANGEJOIN table2 on OVERLAPS( (t1Attribute1, t1Attribute2), (t2Attribute1, t2Attribute2))

Example:
Table1 (id : String, start1: Int, end1: Int) = ( ("i1", 10,20), ("i2", 50, 60) )
Table2(start2: Int, end2: Int) = ( (15,70), (80, 90) )
select * from Table1 RANGEJOIN Table2 on OVERLAPS( (start1, end1), (start2, end2) ) produces the following entries:
("i1", 10, 20, 15, 70), ("i2", 50, 60, 15, 70)

Method:
Assuming rdd1 corresponds to the smaller table and rdd2 to the bigger one, I create an interval tree from all regions of rdd1 which I broadcast to all nodes and I query the tree with all entries of rdd2.

Note that the interval tree uses metadata only, not all contents of rdd1. I keep track of the correspondence between the contents of interval tree and rdd1 through a collection of keys that I zipped with rdd1.