[jira] [Updated] (SPARK-8682) Range Join for Spark SQL

["Herman van Hovell tot Westerflier (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/SPARK-8682?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Herman van Hovell tot Westerflier updated SPARK-8682:
-----------------------------------------------------
    Description: 
Currently Spark SQL uses a Broadcast Nested Loop join (or a filtered Cartesian Join) when it has to execute the following range query:
{noformat}
SELECT A.*,
       B.*
FROM   tableA A
       JOIN tableB B
        ON A.start <= B.end
         AND A.end > B.start
{noformat}
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) table.

I have created a pull request for this. According to the [Spark SQL: Relational Data Processing in Spark|http://people.csail.mit.edu/matei/papers/2015/sigmod_spark_sql.pdf] paper similar work (page 11, section 7.2) has already been done by the ADAM project (cannot locate the code though). 

Any comments and/or feedback are greatly appreciated.

  was:
Currently Spark SQL uses a Broadcast Nested Loop join (or a filtered Cartesian Join) when it has to execute the following range query:
{noformat}
SELECT A.*,
       B.*
FROM   tableA A
       JOIN tableB B
        ON A.start <= B.end
         AND A.end > B.start
{noformat}
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) table.

I have created a prototype for this. According to the [Spark SQL: Relational Data Processing in Spark|http://people.csail.mit.edu/matei/papers/2015/sigmod_spark_sql.pdf] paper similar work (page 11, section 7.2) has already been done by the ADAM project (cannot locate the code though). 

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.


> Range Join for Spark SQL
> ------------------------
>
>                 Key: SPARK-8682
>                 URL: https://issues.apache.org/jira/browse/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:
> {noformat}
> SELECT A.*,
>        B.*
> FROM   tableA A
>        JOIN tableB B
>         ON A.start <= B.end
>          AND A.end > B.start
> {noformat}
> 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) table.
> I have created a pull request for this. According to the [Spark SQL: Relational Data Processing in Spark|http://people.csail.mit.edu/matei/papers/2015/sigmod_spark_sql.pdf] paper similar work (page 11, section 7.2) has already been done by the ADAM project (cannot locate the code though). 
> Any comments and/or feedback are greatly appreciated.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org