[
https://issues.apache.org/jira/browse/SPARK-58201?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
ASF GitHub Bot updated SPARK-58201:
-----------------------------------
Labels: pull-request-available (was: )
> 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
> Priority: Major
> Labels: pull-request-available
>
> 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(NlogW) 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(logW)).
> * {*}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(logW), 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: [email protected]
For additional commands, e-mail: [email protected]
