You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@spark.apache.org by "zhengruifeng (JIRA)" <ji...@apache.org> on 2017/12/20 08:41:00 UTC

[jira] [Commented] (SPARK-10496) Efficient DataFrame cumulative sum

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

zhengruifeng commented on SPARK-10496:
--------------------------------------

According to the prefix scan (https://en.wikipedia.org/wiki/Prefix_sum), I think it needs the random access.
The wiki said: "If the input sequence has n steps, then the recursion continues to a depth of O(log n), which is also the bound on the parallel running time of this algorithm. The number of steps of the algorithm is O(n), and it can be implemented on a *parallel random access machine* with O(n/log n) processors without any asymptotic slowdown by assigning multiple indices to each processor in rounds of the algorithm for which there are more elements than processors.[3]"

So I think the prefix scan may be not suitable for Spark, and the impl should be like current impl of {{zipWithIndex}}:
If there is only on partition, it do not need to trigger a spark job;
If there are more partitions, it needs to trigger a spark job.

I will update the PR to represent my idea.

> Efficient DataFrame cumulative sum
> ----------------------------------
>
>                 Key: SPARK-10496
>                 URL: https://issues.apache.org/jira/browse/SPARK-10496
>             Project: Spark
>          Issue Type: Improvement
>          Components: SQL
>            Reporter: Joseph K. Bradley
>            Priority: Minor
>
> Goal: Given a DataFrame with a numeric column X, create a new column Y which is the cumulative sum of X.
> This can be done with window functions, but it is not efficient for a large number of rows.  It could be done more efficiently using a prefix sum/scan.



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

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