spark-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Nattavut Sutyanyong (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (SPARK-18688) Interpolated time series join
Date Thu, 08 Dec 2016 18:19:58 GMT

    [ https://issues.apache.org/jira/browse/SPARK-18688?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15732969#comment-15732969
] 

Nattavut Sutyanyong commented on SPARK-18688:
---------------------------------------------

It looks like this "interpolation" join is best implemented using Sort-merge join with a twist
of caching the prior unmatched value to return instead of a null value in the case of left
outer join.

For example:
{code}
T1    T2
==    ==
t0    t0
t1
t2
      t3
t4
{code}

The result of {{T1 Left Outer Join T2 ON T1 INTERPOLATE T2}} would be
{code}
t0    t0
t1    t0
t2    t0
t4    t3
{code}

The join could be processed in these steps below:

[Step 0]
Initial state: prev[T1] <- null, cur[T1] <- null, prev[T2] <- null, cur[T2] <-
null
Action: move T1 and T2 to their first rows

[Step 1]
State: prev[T1] <- null, cur[T1] <- t0, prev[T1] <- null, cur[T2] <- t0
Condition: cur[T1] == cur[T2]
Result: Produce (cur[T1], cur[T2]): (t0, t0)
Action: Move T1 forward, T2 stays put because cur[T2] >= cur[T1]

[Step 2]
State: prev[T1] <- t0, cur[T1] <- t1, prev[T2] <- null, cur[T2] <- t0
Condition: cur[T1] > cur[T2]
Result: None
Action: Move T2 forward, T1 stays put because cur[T1] > cur[T2]

[Step 3]
State: prev[T1] <- t0, cur[T1] <- t1, prev[T2] <- t0, cur[T2] <- t3
Condition: cur[T1] < cur[T2]
Result: Produce (cur[T1], prev[T2]): (t1, t0)
Action: Move T1 forward, T2 stays put because cur[T2] >= cur[T1]

[Step 4]
State: prev[T1] <- t1, cur[T1] <- t2, prev[T2] <- t0, cur[T2] <- t3
Condition: cur[T1] < cur[T2]
Result: Produce (cur[T1], prev[T2]): (t2, t0)
Action: Move T1 forward, T2 stays put because cur[T2] >= cur[T1]

[Step 5]
State: prev[T1] <- t2, cur[T1] <- t4, prev[T2] <- t0, cur[T2] <- t3
Condition: cur[T1] > cur[T2]
Result: None
Action: Move T2 forward, T1 stays put because cur[T1] > cur[T2]

[Step 6]
State: prev[T1] <- t2, cur[T1] <- t4, prev[T2] <- t3, cur[T2] <- EOF
Condition: T2 reaches EOF
Result: Produce [cur[T1], prev[T2]): (t4, t3)
Action: Move T1 forward

[Step 7]
State: prev[T1] <- t4, cur[T1] <- EOF, prev[T2] <- t3, cur[T2] <- EOF
Condition: Both tables reach EOF
Result: End of the processing

Note that the buffer prev[T1] is not needed in LOJ. It would be needed for FOJ to keep the
value for padding the unmatched rows from T2.

> Interpolated time series join
> -----------------------------
>
>                 Key: SPARK-18688
>                 URL: https://issues.apache.org/jira/browse/SPARK-18688
>             Project: Spark
>          Issue Type: Improvement
>          Components: SQL
>    Affects Versions: 2.0.2
>            Reporter: Jarno Seppanen
>
> Time series joins are very common in analytics tasks. A simple example would be joining
the newest value of number of followers from data frame F with sessions from data frame S.
Currently, a cross join is needed for such joins in Spark, making them practically impossible.
> Example syntax:
> {noformat}
> SELECT l.account_id, l.time AS login_time, f.num_followers
> FROM account_login l
> LEFT JOIN follower_count_changed f
>   ON (f.account_id = l.account_id
>       AND l.time INTERPOLATE PREVIOUS VALUE f.time)
> {noformat}
> In essence, I'd like to have support for efficiently running joins like INTERPOLATE PREVIOUS
VALUE joins in Vertica [1].
> Thanks for your consideration,
> Jarno
> [1] https://my.vertica.com/docs/7.1.x/HTML/index.htm#Authoring/SQLReferenceManual/LanguageElements/Predicates/INTERPOLATE.htm



--
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


Mime
View raw message