perf(functions-aggregate): optimize sliding window MIN/MAX using monotonic deques (#23826) by pavan51 · Pull Request #23827 · apache/datafusion

pavan51 · 2026-07-23T01:11:04Z

Which issue does this PR close?

Closes Optimize sliding window MIN/MAX aggregations using monotonic deques #23826

What changes are included in this PR?

This PR optimizes sliding window MIN/MAX aggregate functions using a Sequence-Numbered Monotonic Deque instead of a Two-Stack Queue.

Revised Design:

We store (sequence_number, value) pairs in a single VecDeque, kept in strictly monotonic order.
push(val): Evicts dominated elements from the back, then pushes the new value with the current push_seq and increments push_seq.
pop(): Increments pop_seq. If the front elements sequence number equals the old pop_seq, it is expired and popped.
Benefits: No secondary FIFO queue (lower memory) and no clone() overhead.

Are these changes tested?

Yes, existing tests pass. Added tests for empty-window pop() and duplicate-heavy scenarios.

Are there any user-facing changes?

API Change: MovingMin and MovingMax were changed to pub(crate) visibility, and their pop() methods now return () instead of returning a value.
Performance is significantly improved (2x-3.5x throughput).

codecov-commenter · 2026-07-23T15:36:19Z

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 80.65%. Comparing base (88365dd) to head (edf19f0).
⚠️ Report is 7 commits behind head on main.

Additional details and impacted files

@@           Coverage Diff           @@
##             main   #23827   +/-   ##
=======================================
  Coverage   80.65%   80.65%           
=======================================
  Files        1093     1093           
  Lines      371619   371663   +44     
  Branches   371619   371663   +44     
=======================================
+ Hits       299730   299776   +46     
+ Misses      53993    53989    -4     
- Partials    17896    17898    +2

☔ View full report in Codecov by Harness.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
📦 JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.

neilconway

Thanks for the contribution @pavan51 ! I think this is directionally a good idea and a clear improvement over the previous implementation.

The PR fails some linter checks; can you fix those, please?

pavan51 · 2026-07-24T08:05:01Z

Thanks for the contribution @pavan51 ! I think this is directionally a good idea and a clear improvement over the previous implementation.

The PR fails some linter checks; can you fix those, please?

Fixed. I've resolved all the clippy::unnecessary_map_or warnings.

pavan51 · 2026-07-24T08:29:10Z

@neilconway Thanks for the detailed review and excellent feedback. I've addressed all the comments.

The sliding_min_max.rs benchmark now only tests the production MovingMax implementation directly. To establish the performance delta, I ran the benchmark against both the main branch (old two-stack implementation) and this new branch (monotonic deque sequence number).

Here are the results:

Key Metrics (Old vs New)

1. 64-bit Integers (`Int64`)

Window Size 1000
- Throughput (New): ~50 Million elements / sec
- Throughput (Old): ~28 Million elements / sec
- Delta: Old code is ~48% slower (New code is nearly 2x faster)
- Time: Old code takes +91% longer to process the same batch.

2. Timestamps (`TimestampNanosecond`)

Window Size 1000
- Throughput (New): ~52 Million elements / sec
- Throughput (Old): ~26 Million elements / sec
- Delta: Old code is ~50% slower (New code is exactly 2x faster)
- Time: Old code takes +100% longer to process the same batch.

3. Decimals (`Decimal128`)

Window Size 1000
- Throughput (New): ~50 Million elements / sec
- Throughput (Old): ~25 Million elements / sec
- Delta: Old code is ~50% slower (New code is exactly 2x faster)
- Time: Old code takes +100% longer to process the same batch.

4. Strings (`Utf8`)

Window Size 1000
- Throughput (New): ~16 Million elements / sec
- Throughput (Old): ~4.6 Million elements / sec
- Delta: Old code is ~71% slower (New code is 3.5x faster)
- Time: Old code takes +245% longer to process the same batch.

Thanks again for the review! Please let me know if anything else is needed.

neilconway

Thanks for the work on this!

Can you update the PR description to describe the revised design? Also if possible, can we make the PR description more concise?

neilconway · 2026-07-24T14:18:28Z

+    pop_seq: u64,
 }

 impl<T: Clone + PartialOrd> Default for MovingMin<T> {


I don't think we need Clone anymore.

neilconway · 2026-07-24T14:25:03Z

+        while self.deque.back().is_some_and(|back_val| back_val.1 > val) {
+            self.deque.pop_back();
+        }


I think >= would be correct and a bit more efficient for duplicate-heavy inputs?

neilconway · 2026-07-24T14:26:03Z

+                            if i >= w {
+                                q.pop();
+                            }
+                            let _res = q.max();


std::hint::black_box(q.max()); is safer I think.

neilconway · 2026-07-24T14:27:21Z

+            group.throughput(Throughput::Elements(data_size as u64));
+
+            group.bench_with_input(
+                BenchmarkId::new("monotonic_deque", window_size),


A name like "sliding_max" is probably more descriptive.

neilconway · 2026-07-24T14:34:08Z


    /// Pushes a new element into the sliding window.
    #[inline]
    pub fn push(&mut self, val: T) {


What do you think of adding some debug_asserts to check that invariants on the data structure hold after push() and pop()? For example:

pop_seq <= push_seq

if let Some((front_seq, _)) = self.deque.front() { front_seq >= pop_seq }

github-actions · 2026-07-24T14:49:27Z

Thank you for opening this pull request!

Reviewer note: cargo-semver-checks reported the current version number is not SemVer-compatible with the changes in this pull request (compared against the base branch).

Details

     Cloning apache/main
    Building datafusion-functions-aggregate v54.1.0 (current)
       Built [  36.944s] (current)
     Parsing datafusion-functions-aggregate v54.1.0 (current)
      Parsed [   0.046s] (current)
    Building datafusion-functions-aggregate v54.1.0 (baseline)
       Built [  30.876s] (baseline)
     Parsing datafusion-functions-aggregate v54.1.0 (baseline)
      Parsed [   0.046s] (baseline)
    Checking datafusion-functions-aggregate v54.1.0 -> v54.1.0 (no change; assume patch)
     Checked [   0.227s] 223 checks: 222 pass, 1 fail, 0 warn, 30 skip

--- failure struct_missing: pub struct removed or renamed ---

Description:
A publicly-visible struct cannot be imported by its prior path. A `pub use` may have been removed, or the struct itself may have been renamed or removed entirely.
        ref: https://doc.rust-lang.org/cargo/reference/semver.html#item-remove
       impl: https://github.com/obi1kenobi/cargo-semver-checks/tree/v0.49.0/src/lints/struct_missing.ron

Failed in:
  struct datafusion_functions_aggregate::min_max::MovingMin, previously in file /home/runner/work/datafusion/datafusion/target/semver-checks/git-apache_main/96930e9da4aa5f9bd3751786ae50f8102ff1a527/datafusion/functions-aggregate/src/min_max.rs:770
  struct datafusion_functions_aggregate::min_max::MovingMax, previously in file /home/runner/work/datafusion/datafusion/target/semver-checks/git-apache_main/96930e9da4aa5f9bd3751786ae50f8102ff1a527/datafusion/functions-aggregate/src/min_max.rs:914

     Summary semver requires new major version: 1 major and 0 minor checks failed
    Finished [  69.605s] datafusion-functions-aggregate

neilconway

Thanks for the update!

I notice that MovingMin and MovingMax are pub; I think we should probably make them pub(crate). We should also mention the API change in the PR, since even if we don't change the visibility of these types, we're already making a breaking API change.

For clarity, can we name the benchmark file sliding_max.rs? Since we don't actually benchmark sliding min.

neilconway · 2026-07-25T23:40:05Z

    }

-    /// Removes and returns the last value of the sliding window.
+    /// Removes the oldest value from the sliding window.


Can we add a comment on the behavior for empty windows?

neilconway · 2026-07-25T23:41:03Z

+                    debug_assert!(prev.1 < curr.1);
+                    prev = curr;
+                }
+            }


I don't think an assertion that is this expensive is warranted, even for debug-only builds -- I'd just omit it.

…tonic deques

…d benchmarks

…dback

… readability

…tonic deques

…nt empty window pop behavior

Criterion benchmarks are compiled as a separate crate, so pub(crate) makes them inaccessible. Using #[doc(hidden)] achieves the same intent (hiding from public API docs) while still allowing the bench crate to import the struct.

…Min/Max pub(crate) - Benchmark now tests the production SlidingMaxAccumulator API via update_batch/retract_batch, which is how the query engine uses it. This fully satisfies the reviewer's preference for benchmarking the production implementation directly. - MovingMin and MovingMax can now be properly pub(crate) -- no hacks needed since the benchmark no longer imports them directly. - Remove unused with_capacity methods. - Remove doc tests that would fail to compile against pub(crate) items (their logic is covered by the unit tests in the test module).

…in CI

pavan51 · 2026-07-26T05:54:39Z

@neilconway All comments have been addressed, could you please take a look.

getChan

make sense to me.
please remove the temporary markdown files.

pavan51 · 2026-07-26T07:51:03Z

make sense to me.
please remove the temporary markdown files.

@getChan Thank you for

make sense to me. please remove the temporary markdown files.

@getChan Thanks for the review! Done, I have removed the temporary markdown files from the PR.

neilconway

A few last nits and then I'll merge this 😊

Can you add a quick note to the v55 migration guide describing the breaking API change?

neilconway · 2026-07-26T13:30:35Z

+        self.push_seq == self.pop_seq
    }

    /// Heap bytes owned by the two stack buffers plus each stored `T`'s


Update this comment.

neilconway · 2026-07-26T13:32:47Z

-/// The implementation is taken from <https://github.com/spebern/moving_min_max/blob/master/src/lib.rs>
+/// `MovingMin` keeps track of the minimum value in a sliding window using a
+/// monotonic deque. Each element is stored with its sequence number, and the
+/// deque maintains candidate elements in strictly increasing value order.


"Strictly increasing" is a bit misleading, since we only require PartialOrd. "in ascending order" instead?

…cending ordering and deque heap size

…n guide

pavan51 · 2026-07-26T16:27:13Z

@neilconway Thanks for the review. Requested updates have been addressed and pushed, including the entry in the v55 upgrade guide.

…tonic deques (apache#23826) (apache#23827) ## Which issue does this PR close? - Closes apache#23826 ### What changes are included in this PR? This PR optimizes sliding window `MIN`/`MAX` aggregate functions using a **Sequence-Numbered Monotonic Deque** instead of a Two-Stack Queue. **Revised Design:** - We store `(sequence_number, value)` pairs in a single `VecDeque`, kept in strictly monotonic order. - **`push(val)`**: Evicts dominated elements from the back, then pushes the new value with the current `push_seq` and increments `push_seq`. - **`pop()`**: Increments `pop_seq`. If the front elements sequence number equals the old `pop_seq`, it is expired and popped. - **Benefits**: No secondary FIFO queue (lower memory) and no `clone()` overhead. ### Are these changes tested? Yes, existing tests pass. Added tests for empty-window `pop()` and duplicate-heavy scenarios. ### Are there any user-facing changes? **API Change**: `MovingMin` and `MovingMax` were changed to `pub(crate)` visibility, and their `pop()` methods now return `()` instead of returning a value. Performance is significantly improved (2x-3.5x throughput). --------- Co-authored-by: Pavan <[email protected]>

github-actions Bot added the functions Changes to functions implementation label Jul 23, 2026

pavan51 closed this Jul 23, 2026

pavan51 reopened this Jul 23, 2026

neilconway reviewed Jul 23, 2026

View reviewed changes

pavan51 force-pushed the sliding-window-min-max-monotonic-deque branch from 82168be to 31cf348 Compare July 24, 2026 07:08

pavan51 requested a review from neilconway July 24, 2026 08:30

neilconway reviewed Jul 24, 2026

View reviewed changes

github-actions Bot added the auto detected api change Auto detected API change label Jul 24, 2026

neilconway reviewed Jul 25, 2026

View reviewed changes

Pavan added 17 commits July 25, 2026 23:44

perf(functions-aggregate): optimize sliding window min/max using mono…

1d35f52

…tonic deques

test(functions-aggregate): add sliding window min/max benchmark

40d3971

test(functions-aggregate): add comprehensive ScalarValue and 5M scale…

8c7eaed

…d benchmarks

style(functions-aggregate): apply rustfmt

460128b

fix(functions-aggregate): resolve clippy unnecessary_map_or warnings

0b21f98

Optimize MovingMin/MovingMax with Sequence Numbers and resolve PR fee…

0c1ce96

…dback

style(functions-aggregate): use std::collections::VecDeque import for…

db99753

… readability

Fix clippy warnings in sliding_min_max.rs benchmark

99c4115

fix(functions-aggregate): resolve PR feedback for sliding window mono…

c6d0876

…tonic deques

style: apply rustfmt

7013b0e

Address review comments: rename benchmark and make structs pub(crate)

2689ad6

Address review comments: remove expensive debug assertions and docume…

f901afd

…nt empty window pop behavior

fix: mark MovingMin/MovingMax::len as cfg(test) to silence dead_code …

4f5fc4d

…in CI

fix(clippy): pass DataType and ArrayRef by reference in benchmark

b2c7b97

style: apply rustfmt to benchmark file

0cee76d

pavan51 force-pushed the sliding-window-min-max-monotonic-deque branch from f266712 to 0cee76d Compare July 26, 2026 04:51

test: restore with_capacity for MovingMin and MovingMax tests

942514f

pavan51 requested a review from neilconway July 26, 2026 05:55

getChan reviewed Jul 26, 2026

View reviewed changes

chore: remove temporary PR description files

2785a07

pavan51 requested a review from getChan July 26, 2026 07:51

getChan approved these changes Jul 26, 2026

View reviewed changes

neilconway reviewed Jul 26, 2026

View reviewed changes

neilconway added the api change Changes the API exposed to users of the crate label Jul 26, 2026

Pavan added 2 commits July 26, 2026 10:30

doc: update MovingMin/MovingMax doc comments to reflect ascending/des…

2c45917

…cending ordering and deque heap size

docs: add MovingMin and MovingMax pub(crate) entry to 55.0.0 migratio…

edf19f0

…n guide

github-actions Bot added the documentation Improvements or additions to documentation label Jul 26, 2026

pavan51 requested a review from neilconway July 26, 2026 16:27

neilconway approved these changes Jul 27, 2026

View reviewed changes

neilconway added this pull request to the merge queue Jul 27, 2026

github-merge-queue Bot removed this pull request from the merge queue due to no response for status checks Jul 27, 2026

neilconway added this pull request to the merge queue Jul 27, 2026

Merged via the queue into apache:main with commit 8d2ffc9 Jul 27, 2026
39 checks passed

nuno-faria added the v55.0.0 label Oct 3, 2026

Conversation

pavan51 commented Jul 23, 2026 • edited by neilconway Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Which issue does this PR close?

What changes are included in this PR?

Are these changes tested?

Are there any user-facing changes?

Uh oh!

codecov-commenter commented Jul 23, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

neilconway left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

pavan51 commented Jul 24, 2026

Uh oh!

pavan51 commented Jul 24, 2026

Key Metrics (Old vs New)

1. 64-bit Integers (Int64)

2. Timestamps (TimestampNanosecond)

3. Decimals (Decimal128)

4. Strings (Utf8)

Thanks again for the review! Please let me know if anything else is needed.

Uh oh!

neilconway left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

github-actions Bot commented Jul 24, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

neilconway left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

pavan51 commented Jul 26, 2026

Uh oh!

getChan left a comment

Choose a reason for hiding this comment

Uh oh!

pavan51 commented Jul 26, 2026

Uh oh!

neilconway left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

pavan51 commented Jul 26, 2026

Uh oh!

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

pavan51 commented Jul 23, 2026 •

edited by neilconway

Loading

codecov-commenter commented Jul 23, 2026 •

edited

Loading

1. 64-bit Integers (`Int64`)

2. Timestamps (`TimestampNanosecond`)

3. Decimals (`Decimal128`)

4. Strings (`Utf8`)

github-actions Bot commented Jul 24, 2026 •

edited

Loading