pavan51 opened a new issue, #23826:
URL: https://github.com/apache/datafusion/issues/23826
### Is your feature request related to a problem or challenge?
Currently, DataFusion's sliding window `MIN` and `MAX` aggregations
(`SlidingMinAccumulator` and `SlidingMaxAccumulator`) are implemented using a
"two-stack queue" approach.
While this gives an amortized $O(1)$ time complexity for the overall
query, it has a worst-case $O(W)$ time complexity for a single operation (where
$W$ is the window size). This occurs when the pop-stack is empty and the entire
push-stack must be reversed. At
large window sizes, this stack reversal causes execution threads to
experience significant tail-latency "jitter" and stalls, which degrades overall
system predictability and performance.
Additionally, the current implementation clones the underlying
`ScalarValue` multiple times, adding overhead.
### Describe the solution you'd like
Replace the two-stack implementation with a **Monotonic Deque**
(double-ended queue) for `MovingMin` and `MovingMax`.
A Monotonic Deque maintains the elements in monotonically increasing (or
decreasing) order. This approach provides:
1. **Strict $O(1)$ worst-case time complexity** per row, completely
eliminating the $O(W)$ stack-reversal stalls.
2. **Fewer Clones**: Only the candidate minimums/maximums are kept in
the deque, rather than the entire window of `ScalarValue`s, significantly
reducing memory and cloning overhead.
### Describe alternatives you've considered
Using tree-based structures (like `BTreeMap`), but those are $O(\log W)$
which is strictly worse than the Monotonic Deque's $O(1)$ amortized and
worst-case bounds.
### Additional context
Extensive benchmarking with 5,000,000 records across various
`ScalarValue` types (Int64, Float64, Timestamp, Decimal128, Utf8) shows that a
Monotonic Deque implementation yields:
- **1.1x to 1.9x better total throughput** compared to the two-stack
approach.
- **50x to 500x better worst-case tail latency** (jitter), ensuring
query execution threads no longer stall when processing large sliding windows.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
