spark-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Herman van Hovell tot Westerflier (JIRA)" <>
Subject [jira] [Created] (SPARK-8682) Range Join for Spark SQL
Date Sat, 27 Jun 2015 21:54:04 GMT
Herman van Hovell tot Westerflier created SPARK-8682:

             Summary: Range Join for Spark SQL
                 Key: SPARK-8682
             Project: Spark
          Issue Type: Improvement
          Components: SQL
            Reporter: Herman van Hovell tot Westerflier

Currently Spark SQL uses a Broadcast Nested Loop join (or a filtered Cartesian Join) when
it has to execute the following range query:
FROM   tableA A
       JOIN tableB B
        ON A.start <= B.end
         AND A.end > B.start
This is horribly inefficient. The performance of this query can be greatly improved, when
one of the tables can be broadcasted, by creating a range index. A range index is basically
a sorted map containing the rows of the smaller table, indexed by both the high and low keys.
using this structure the complexity of the query would go from O(N * M) to O(N * 2 * LOG(M)),
N = number of records in the larger table, M = number of records in the smaller (indexed)

I have created a prototype for this. According to the [Spark SQL: Relational Data Processing
in Spark|] paper similar
work (page 11, section 7.2) has already been done by the ADAM project (cannot locate the code

So before charging ahead, by creating a PR, I would like to know first if this is worth the
effort. Any comments and/or feedback are greatly appreciated.

This message was sent by Atlassian JIRA

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message