spark-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Petar Zecevic (JIRA)" <>
Subject [jira] [Commented] (SPARK-24020) Sort-merge join inner range optimization
Date Thu, 19 Apr 2018 16:21:01 GMT


Petar Zecevic commented on SPARK-24020:

No, this implementation only applies to equi-joins that have range conditions on different
columns. You can think of it as an equi-join with "sub-band" conditions. Hence the name we
gave it ("sort-merge inner range join").

> Sort-merge join inner range optimization
> ----------------------------------------
>                 Key: SPARK-24020
>                 URL:
>             Project: Spark
>          Issue Type: Improvement
>          Components: SQL
>    Affects Versions: 2.3.0
>            Reporter: Petar Zecevic
>            Priority: Major
> The problem we are solving is the case where you have two big tables partitioned by X
column, but also sorted by Y column (within partitions) and you need to calculate an expensive
function on the joined rows. During a sort-merge join, Spark will do cross-joins of all rows
that have the same X values and calculate the function's value on all of them. If the two
tables have a large number of rows per X, this can result in a huge number of calculations.
> We hereby propose an optimization that would allow you to reduce the number of matching
rows per X using a range condition on Y columns of the two tables. Something like:
> ... WHERE t1.X = t2.X AND t1.Y BETWEEN t2.Y - d AND t2.Y + d
> The way SMJ is currently implemented, these extra conditions have no influence on the
number of rows (per X) being checked because these extra conditions are put in the same block
with the function being calculated.
> Here we propose a change to the sort-merge join so that, when these extra conditions
are specified, a queue is used instead of the ExternalAppendOnlyUnsafeRowArray class. This
queue would then used as a moving window across the values from the right relation as the
left row changes. You could call this a combination of an equi-join and a theta join (we call
it "sort-merge inner range join").
> Potential use-cases for this are joins based on spatial or temporal distance calculations.
> The optimization should be triggered automatically when an equi-join expression is present
AND lower and upper range conditions on a secondary column are specified. If the tables aren't
sorted by both columns, appropriate sorts should be added.
> To limit the impact of this change we also propose adding a new parameter (tentatively
named "spark.sql.join.smj.useInnerRangeOptimization") which could be used to switch off the
optimization entirely.

This message was sent by Atlassian JIRA

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

View raw message