[jira] [Resolved] (SPARK-58201) Optimize sliding window MIN/MAX aggregate functions using monotonic deque

["Peter Toth (Jira)" <ji...@apache.org>]

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

Peter Toth resolved SPARK-58201.
--------------------------------
    Fix Version/s: 5.0.0
       Resolution: Fixed

Issue resolved by pull request 57346
[https://github.com/apache/spark/pull/57346]

> Optimize sliding window MIN/MAX aggregate functions using monotonic deque
> -------------------------------------------------------------------------
>
>                 Key: SPARK-58201
>                 URL: https://issues.apache.org/jira/browse/SPARK-58201
>             Project: Spark
>          Issue Type: Improvement
>          Components: SQL
>    Affects Versions: 4.3.0
>            Reporter: Pavan
>            Assignee: Pavan
>            Priority: Major
>              Labels: pull-request-available
>             Fix For: 5.0.0
>
>
> Currently, sliding window aggregates in Spark are executed using:
>  # *Naive Sliding Window* ({{{}SlidingWindowFunctionFrame{}}}): Re-scans all rows in the sliding window buffer on every row, resulting in O(N⋅W) time complexity.
>  # *Segment Tree* ({{{}SegmentTreeWindowFunctionFrame{}}}): Built over partition blocks, offering O(Nlog⁡W) complexity but with significant block-caching and tree-construction overhead.
> While the Segment Tree is an improvement over Naive for large windows, it has three major deficiencies:
>  * {*}Logarithmic Complexity Overhead{*}: As the window size W grows, the query overhead increases logarithmically (O(log⁡W)).
>  * {*}Pareto Loss Zone at Small Windows{*}: At small window sizes (e.g. W=11), the Segment Tree's setup, block allocation, and pointer-chasing traversal overhead make it significantly slower than even the Naive baseline (running at *~0.5X* the speed of Naive).
>  * {*}High Heap Allocation & GC Pressure{*}: The Segment Tree divides rows into blocks and builds a tree structure over the partition data. To build and store leaf and branch nodes, it allocates a large number of node objects and tree arrays on the JVM heap. This leads to high heap allocation and garbage collection (GC) pressure, even for primitive types.
> By implementing a monotonic deque, we achieve true linear *O(N) time complexity* (amortized O(1) operations per row regardless of window size) and a minimal memory footprint.
> As a result:
>  * At standard window scales (W=1001), Monotonic Deque is *~3X - 4X faster* than Segment Tree, and *~30X - 37X* faster than the Naive baseline.
>  * At large window scales (W=100,001), Monotonic Deque achieves *6X+ speedup* over Segment Tree. Because of its O(1) amortized complexity vs the Segment Tree's O(log⁡W), the speedup factor scales logarithmically with the window size, diverging even further in favor of Monotonic Deque as W grows.
>  * At small window scales (W=11), Monotonic Deque completely resolves the Segment Tree's deoptimization, outperforming Naive and running up to *3X+ faster* than Segment Tree.
> ----



--
This message was sent by Atlassian Jira
(v8.20.10#820010)

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