Pavan created SPARK-58201:
-----------------------------
Summary: 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
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]
