You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/07/27 15:05:13 UTC

(datafusion) 01/01: perf(functions-aggregate): optimize sliding window MIN/MAX using monotonic deques (#23826) (#23827)

This is an automated email from the ASF dual-hosted git repository.

github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-23827-9facaaabd001d0f82ecc6bcd4d09adcc6f731109
in repository https://gitbox.apache.org/repos/asf/datafusion.git

commit 4f1e83b407dc3702822c679d59356cd8b605a71e
Author: Pavan51 <pa...@gmail.com>
AuthorDate: Mon Jul 27 10:04:51 2026 -0500

    perf(functions-aggregate): optimize sliding window MIN/MAX using monotonic deques (#23826) (#23827)
    
    ## Which issue does this PR close?
    
    - Closes #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 <pa...@Lakshmis-MacBook-Air.local>
---
 datafusion/functions-aggregate/Cargo.toml          |   4 +
 .../functions-aggregate/benches/sliding_max.rs     | 113 +++++++
 datafusion/functions-aggregate/src/min_max.rs      | 366 +++++++++++----------
 docs/source/library-user-guide/upgrading/55.0.0.md |  10 +
 4 files changed, 315 insertions(+), 178 deletions(-)

diff --git a/datafusion/functions-aggregate/Cargo.toml b/datafusion/functions-aggregate/Cargo.toml
index c1b992a6d8..e75afc8f0b 100644
--- a/datafusion/functions-aggregate/Cargo.toml
+++ b/datafusion/functions-aggregate/Cargo.toml
@@ -95,5 +95,9 @@ harness = false
 name = "percentile_cont"
 harness = false
 
+[[bench]]
+name = "sliding_max"
+harness = false
+
 [features]
 force_hash_collisions = ["datafusion-common/force_hash_collisions"]
diff --git a/datafusion/functions-aggregate/benches/sliding_max.rs b/datafusion/functions-aggregate/benches/sliding_max.rs
new file mode 100644
index 0000000000..d5de001a1a
--- /dev/null
+++ b/datafusion/functions-aggregate/benches/sliding_max.rs
@@ -0,0 +1,113 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use arrow::array::{ArrayRef, Int64Array, StringArray};
+use arrow::datatypes::DataType;
+use criterion::{BenchmarkId, Criterion, Throughput, criterion_group, criterion_main};
+use datafusion_expr::Accumulator;
+use datafusion_functions_aggregate::min_max::SlidingMaxAccumulator;
+use rand::Rng;
+use rand::SeedableRng;
+use rand::rngs::StdRng;
+use std::sync::Arc;
+
+fn generate_random_i64(size: usize) -> Vec<i64> {
+    let mut rng = StdRng::seed_from_u64(42);
+    (0..size).map(|_| rng.random_range(0..1_000_000)).collect()
+}
+
+fn generate_random_strings(size: usize) -> Vec<String> {
+    let mut rng = StdRng::seed_from_u64(42);
+    (0..size)
+        .map(|_| {
+            let len = rng.random_range(10..40);
+            (0..len)
+                .map(|_| rng.random_range(b'a'..=b'z') as char)
+                .collect()
+        })
+        .collect()
+}
+
+/// Simulates a sliding window by calling update_batch and retract_batch
+/// on SlidingMaxAccumulator, mirroring how the query engine uses it.
+fn bench_sliding_max_for(
+    c: &mut Criterion,
+    label: &str,
+    data_type: &DataType,
+    array: &ArrayRef,
+    data_size: usize,
+    window_size: usize,
+) {
+    let mut group = c.benchmark_group(format!("sliding_window_max_{label}"));
+    group.throughput(Throughput::Elements(data_size as u64));
+
+    group.bench_with_input(
+        BenchmarkId::new("sliding_max", window_size),
+        &window_size,
+        |b, &w| {
+            b.iter(|| {
+                let mut acc = SlidingMaxAccumulator::try_new(data_type).unwrap();
+                // Warm up the window
+                let init_batch = array.slice(0, w);
+                acc.update_batch(&[init_batch]).unwrap();
+
+                // Slide: for each subsequent element, add it and retract one
+                for i in w..data_size {
+                    let new_val = array.slice(i, 1);
+                    let old_val = array.slice(i - w, 1);
+                    acc.update_batch(&[new_val]).unwrap();
+                    acc.retract_batch(&[old_val]).unwrap();
+                    std::hint::black_box(acc.evaluate().unwrap());
+                }
+            });
+        },
+    );
+
+    group.finish();
+}
+
+fn bench_sliding_max(c: &mut Criterion) {
+    let data_size = 50_000;
+
+    let i64_data: Vec<i64> = generate_random_i64(data_size);
+    let str_data: Vec<String> = generate_random_strings(data_size);
+
+    let i64_array: ArrayRef = Arc::new(Int64Array::from(i64_data));
+    let str_array: ArrayRef = Arc::new(StringArray::from(str_data));
+
+    for window_size in [100, 1000, 5000] {
+        bench_sliding_max_for(
+            c,
+            "int64",
+            &DataType::Int64,
+            &i64_array,
+            data_size,
+            window_size,
+        );
+        bench_sliding_max_for(
+            c,
+            "utf8",
+            &DataType::Utf8,
+            &str_array,
+            data_size,
+            window_size,
+        );
+    }
+}
+
+criterion_group!(benches, bench_sliding_max);
+criterion_main!(benches);
diff --git a/datafusion/functions-aggregate/src/min_max.rs b/datafusion/functions-aggregate/src/min_max.rs
index 1a3179170c..b306e7db2f 100644
--- a/datafusion/functions-aggregate/src/min_max.rs
+++ b/datafusion/functions-aggregate/src/min_max.rs
@@ -52,6 +52,7 @@ use datafusion_expr::{
 use datafusion_expr::{GroupsAccumulator, StatisticsArgs};
 use datafusion_macros::user_doc;
 use half::f16;
+use std::collections::VecDeque;
 use std::mem::{size_of, size_of_val};
 use std::ops::Deref;
 
@@ -731,71 +732,47 @@ impl Accumulator for SlidingMinAccumulator {
 
 /// Keep track of the minimum value in a sliding window.
 ///
-/// 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 ascending value order.
 ///
-/// `moving min max` provides one data structure for keeping track of the
-/// minimum value and one for keeping track of the maximum value in a sliding
-/// window.
-///
-/// Each element is stored with the current min/max. One stack to push and another one for pop. If pop stack is empty,
-/// push to this stack all elements popped from first stack while updating their current min/max. Now pop from
-/// the second stack (MovingMin/Max struct works as a queue). To find the minimum element of the queue,
-/// look at the smallest/largest two elements of the individual stacks, then take the minimum of those two values.
-///
-/// The complexity of the operations are
-/// - O(1) for getting the minimum/maximum
-/// - O(1) for push
-/// - amortized O(1) for pop
-///
-/// ```
-/// # use datafusion_functions_aggregate::min_max::MovingMin;
-/// let mut moving_min = MovingMin::<i32>::new();
-/// moving_min.push(2);
-/// moving_min.push(1);
-/// moving_min.push(3);
-///
-/// assert_eq!(moving_min.min(), Some(&1));
-/// assert_eq!(moving_min.pop(), Some(2));
-///
-/// assert_eq!(moving_min.min(), Some(&1));
-/// assert_eq!(moving_min.pop(), Some(1));
-///
-/// assert_eq!(moving_min.min(), Some(&3));
-/// assert_eq!(moving_min.pop(), Some(3));
-///
-/// assert_eq!(moving_min.min(), None);
-/// assert_eq!(moving_min.pop(), None);
-/// ```
+/// Complexity:
+/// - O(1) for getting the minimum
+/// - amortized O(1) for push
+/// - O(1) for pop
 #[derive(Debug)]
-pub struct MovingMin<T> {
-    push_stack: Vec<(T, T)>,
-    pop_stack: Vec<(T, T)>,
+pub(crate) struct MovingMin<T> {
+    deque: VecDeque<(u64, T)>,
+    push_seq: u64,
+    pop_seq: u64,
 }
 
-impl<T: Clone + PartialOrd> Default for MovingMin<T> {
+impl<T: PartialOrd> Default for MovingMin<T> {
     fn default() -> Self {
         Self {
-            push_stack: Vec::new(),
-            pop_stack: Vec::new(),
+            deque: VecDeque::new(),
+            push_seq: 0,
+            pop_seq: 0,
         }
     }
 }
 
-impl<T: Clone + PartialOrd> MovingMin<T> {
-    /// Creates a new `MovingMin` to keep track of the minimum in a sliding
-    /// window.
+impl<T: PartialOrd> MovingMin<T> {
+    /// Creates a new `MovingMin` to keep track of the minimum in a sliding window.
     #[inline]
     pub fn new() -> Self {
         Self::default()
     }
 
-    /// Creates a new `MovingMin` to keep track of the minimum in a sliding
-    /// window with `capacity` allocated slots.
+    /// Creates a new `MovingMin` to keep track of the minimum in a sliding window with
+    /// `capacity` allocated slots.
+    #[cfg(test)]
     #[inline]
     pub fn with_capacity(capacity: usize) -> Self {
         Self {
-            push_stack: Vec::with_capacity(capacity),
-            pop_stack: Vec::with_capacity(capacity),
+            deque: VecDeque::with_capacity(capacity),
+            push_seq: 0,
+            pop_seq: 0,
         }
     }
 
@@ -803,129 +780,113 @@ impl<T: Clone + PartialOrd> MovingMin<T> {
     /// empty.
     #[inline]
     pub fn min(&self) -> Option<&T> {
-        match (self.push_stack.last(), self.pop_stack.last()) {
-            (None, None) => None,
-            (Some((_, min)), None) => Some(min),
-            (None, Some((_, min))) => Some(min),
-            (Some((_, a)), Some((_, b))) => Some(if a < b { a } else { b }),
-        }
+        self.deque.front().map(|(_, val)| val)
+    }
+
+    #[inline]
+    fn check_invariants(&self) {
+        debug_assert!(self.pop_seq <= self.push_seq);
+        debug_assert!(
+            self.deque
+                .front()
+                .is_none_or(|&(front_seq, _)| front_seq >= self.pop_seq)
+        );
     }
 
     /// Pushes a new element into the sliding window.
     #[inline]
     pub fn push(&mut self, val: T) {
-        self.push_stack.push(match self.push_stack.last() {
-            Some((_, min)) => {
-                if val > *min {
-                    (val, min.clone())
-                } else {
-                    (val.clone(), val)
-                }
-            }
-            None => (val.clone(), val),
-        });
+        let seq = self.push_seq;
+        self.push_seq += 1;
+        while self.deque.back().is_some_and(|back_val| back_val.1 >= val) {
+            self.deque.pop_back();
+        }
+        self.deque.push_back((seq, val));
+
+        self.check_invariants();
     }
 
-    /// Removes and returns the last value of the sliding window.
+    /// Removes the oldest value from the sliding window.
+    ///
+    /// If the window is empty, this is a no-op.
     #[inline]
-    pub fn pop(&mut self) -> Option<T> {
-        if self.pop_stack.is_empty() {
-            match self.push_stack.pop() {
-                Some((val, _)) => {
-                    let mut last = (val.clone(), val);
-                    self.pop_stack.push(last.clone());
-                    while let Some((val, _)) = self.push_stack.pop() {
-                        let min = if last.1 < val {
-                            last.1.clone()
-                        } else {
-                            val.clone()
-                        };
-                        last = (val.clone(), min);
-                        self.pop_stack.push(last.clone());
-                    }
-                }
-                None => return None,
-            }
+    pub fn pop(&mut self) {
+        if self.is_empty() {
+            return;
+        }
+        let seq = self.pop_seq;
+        self.pop_seq += 1;
+        if self
+            .deque
+            .front()
+            .is_some_and(|front_val| front_val.0 == seq)
+        {
+            self.deque.pop_front();
         }
-        self.pop_stack.pop().map(|(val, _)| val)
+
+        self.check_invariants();
     }
 
     /// Returns the number of elements stored in the sliding window.
-    #[inline]
+    #[cfg(test)]
     pub fn len(&self) -> usize {
-        self.push_stack.len() + self.pop_stack.len()
+        (self.push_seq - self.pop_seq) as usize
     }
 
     /// Returns `true` if the moving window contains no elements.
     #[inline]
     pub fn is_empty(&self) -> bool {
-        self.len() == 0
+        self.push_seq == self.pop_seq
     }
 
-    /// Heap bytes owned by the two stack buffers plus each stored `T`'s
+    /// Heap bytes owned by the deque plus each stored `T`'s
     /// heap payload as reported by `elem_heap`. Excludes `size_of::<Self>()`.
     #[inline]
     fn heap_size(&self, elem_heap: impl Fn(&T) -> usize) -> usize {
-        moving_stacks_heap_size(&self.push_stack, &self.pop_stack, elem_heap)
+        moving_deque_heap_size(&self.deque, elem_heap)
     }
 }
 
 /// Shared implementation for [`MovingMin::heap_size`] and
-/// [`MovingMax::heap_size`]. Both share the same two-stack layout.
+/// [`MovingMax::heap_size`]. Both share the same deque layout.
 #[inline]
-fn moving_stacks_heap_size<T>(
-    push_stack: &Vec<(T, T)>,
-    pop_stack: &Vec<(T, T)>,
+fn moving_deque_heap_size<T>(
+    deque: &VecDeque<(u64, T)>,
     elem_heap: impl Fn(&T) -> usize,
 ) -> usize {
-    let buffers = (push_stack.capacity() + pop_stack.capacity()) * size_of::<(T, T)>();
-    let elems: usize = push_stack
-        .iter()
-        .chain(pop_stack.iter())
-        .map(|(a, b)| elem_heap(a) + elem_heap(b))
-        .sum();
+    let buffers = deque.capacity() * size_of::<(u64, T)>();
+    let elems: usize = deque.iter().map(|(_, val)| elem_heap(val)).sum();
     buffers + elems
 }
 
 /// Keep track of the maximum value in a sliding window.
 ///
-/// See [`MovingMin`] for more details.
-///
-/// ```
-/// # use datafusion_functions_aggregate::min_max::MovingMax;
-/// let mut moving_max = MovingMax::<i32>::new();
-/// moving_max.push(2);
-/// moving_max.push(3);
-/// moving_max.push(1);
-///
-/// assert_eq!(moving_max.max(), Some(&3));
-/// assert_eq!(moving_max.pop(), Some(2));
-///
-/// assert_eq!(moving_max.max(), Some(&3));
-/// assert_eq!(moving_max.pop(), Some(3));
+/// `MovingMax` keeps track of the maximum value in a sliding window using a
+/// monotonic deque. Each element is stored with its sequence number, and the
+/// deque maintains candidate elements in descending value order.
 ///
-/// assert_eq!(moving_max.max(), Some(&1));
-/// assert_eq!(moving_max.pop(), Some(1));
-///
-/// assert_eq!(moving_max.max(), None);
-/// assert_eq!(moving_max.pop(), None);
-/// ```
+/// Complexity:
+/// - O(1) for getting the maximum
+/// - amortized O(1) for push
+/// - O(1) for pop
 #[derive(Debug)]
-pub struct MovingMax<T> {
-    push_stack: Vec<(T, T)>,
-    pop_stack: Vec<(T, T)>,
+pub(crate) struct MovingMax<T> {
+    deque: VecDeque<(u64, T)>,
+    push_seq: u64,
+    pop_seq: u64,
 }
 
-impl<T: Clone + PartialOrd> Default for MovingMax<T> {
+impl<T: PartialOrd> Default for MovingMax<T> {
     fn default() -> Self {
         Self {
-            push_stack: Vec::new(),
-            pop_stack: Vec::new(),
+            deque: VecDeque::new(),
+            push_seq: 0,
+            pop_seq: 0,
         }
     }
 }
 
-impl<T: Clone + PartialOrd> MovingMax<T> {
+impl<T: PartialOrd> MovingMax<T> {
     /// Creates a new `MovingMax` to keep track of the maximum in a sliding window.
     #[inline]
     pub fn new() -> Self {
@@ -934,81 +895,83 @@ impl<T: Clone + PartialOrd> MovingMax<T> {
 
     /// Creates a new `MovingMax` to keep track of the maximum in a sliding window with
     /// `capacity` allocated slots.
+    #[cfg(test)]
     #[inline]
     pub fn with_capacity(capacity: usize) -> Self {
         Self {
-            push_stack: Vec::with_capacity(capacity),
-            pop_stack: Vec::with_capacity(capacity),
+            deque: VecDeque::with_capacity(capacity),
+            push_seq: 0,
+            pop_seq: 0,
         }
     }
 
     /// Returns the maximum of the sliding window or `None` if the window is empty.
     #[inline]
     pub fn max(&self) -> Option<&T> {
-        match (self.push_stack.last(), self.pop_stack.last()) {
-            (None, None) => None,
-            (Some((_, max)), None) => Some(max),
-            (None, Some((_, max))) => Some(max),
-            (Some((_, a)), Some((_, b))) => Some(if a > b { a } else { b }),
-        }
+        self.deque.front().map(|(_, val)| val)
+    }
+
+    #[inline]
+    fn check_invariants(&self) {
+        debug_assert!(self.pop_seq <= self.push_seq);
+        debug_assert!(
+            self.deque
+                .front()
+                .is_none_or(|&(front_seq, _)| front_seq >= self.pop_seq)
+        );
     }
 
     /// Pushes a new element into the sliding window.
     #[inline]
     pub fn push(&mut self, val: T) {
-        self.push_stack.push(match self.push_stack.last() {
-            Some((_, max)) => {
-                if val < *max {
-                    (val, max.clone())
-                } else {
-                    (val.clone(), val)
-                }
-            }
-            None => (val.clone(), val),
-        });
+        let seq = self.push_seq;
+        self.push_seq += 1;
+        while self.deque.back().is_some_and(|back_val| back_val.1 <= val) {
+            self.deque.pop_back();
+        }
+        self.deque.push_back((seq, val));
+
+        self.check_invariants();
     }
 
-    /// Removes and returns the last value of the sliding window.
+    /// Removes the oldest value from the sliding window.
+    ///
+    /// If the window is empty, this is a no-op.
     #[inline]
-    pub fn pop(&mut self) -> Option<T> {
-        if self.pop_stack.is_empty() {
-            match self.push_stack.pop() {
-                Some((val, _)) => {
-                    let mut last = (val.clone(), val);
-                    self.pop_stack.push(last.clone());
-                    while let Some((val, _)) = self.push_stack.pop() {
-                        let max = if last.1 > val {
-                            last.1.clone()
-                        } else {
-                            val.clone()
-                        };
-                        last = (val.clone(), max);
-                        self.pop_stack.push(last.clone());
-                    }
-                }
-                None => return None,
-            }
+    pub fn pop(&mut self) {
+        if self.is_empty() {
+            return;
+        }
+        let seq = self.pop_seq;
+        self.pop_seq += 1;
+        if self
+            .deque
+            .front()
+            .is_some_and(|front_val| front_val.0 == seq)
+        {
+            self.deque.pop_front();
         }
-        self.pop_stack.pop().map(|(val, _)| val)
+
+        self.check_invariants();
     }
 
     /// Returns the number of elements stored in the sliding window.
-    #[inline]
+    #[cfg(test)]
     pub fn len(&self) -> usize {
-        self.push_stack.len() + self.pop_stack.len()
+        (self.push_seq - self.pop_seq) as usize
     }
 
     /// Returns `true` if the moving window contains no elements.
     #[inline]
     pub fn is_empty(&self) -> bool {
-        self.len() == 0
+        self.push_seq == self.pop_seq
     }
 
-    /// Heap bytes owned by the two stack buffers plus each stored `T`'s
+    /// Heap bytes owned by the deque plus each stored `T`'s
     /// heap payload as reported by `elem_heap`. Excludes `size_of::<Self>()`.
     #[inline]
     fn heap_size(&self, elem_heap: impl Fn(&T) -> usize) -> usize {
-        moving_stacks_heap_size(&self.push_stack, &self.pop_stack, elem_heap)
+        moving_deque_heap_size(&self.deque, elem_heap)
     }
 }
 
@@ -1251,13 +1214,12 @@ mod tests {
     #[test]
     fn moving_min_max_heap_size_i32() {
         // Fixed-width `T` has no per-element heap payload, so `heap_size`
-        // reports exactly the two stack buffers' capacity in bytes.
+        // reports exactly the buffer's capacity in bytes.
         let mut moving_min = MovingMin::<i32>::with_capacity(4);
         let mut moving_max = MovingMax::<i32>::with_capacity(4);
         let elem = |_: &i32| 0;
 
-        // Both stacks are `with_capacity(4)`, so total slots = 8.
-        let buffer_only = 2 * 4 * size_of::<(i32, i32)>();
+        let buffer_only = moving_min.deque.capacity() * size_of::<(u64, i32)>();
         assert_eq!(moving_min.heap_size(elem), buffer_only);
         assert_eq!(moving_max.heap_size(elem), buffer_only);
 
@@ -1272,8 +1234,6 @@ mod tests {
 
     #[test]
     fn moving_min_max_heap_size_counts_elems() {
-        // Each buffered slot is a `(T, T)` pair, so a stored element is
-        // visited twice by `heap_size` — mirrors two independent `Clone`s.
         let mut moving_min = MovingMin::<String>::with_capacity(2);
         let mut moving_max = MovingMax::<String>::with_capacity(2);
         let elem = |s: &String| s.capacity();
@@ -1281,15 +1241,65 @@ mod tests {
         moving_min.push("abcdef".to_string());
         moving_max.push("abcdef".to_string());
 
-        // Both `push_stack` and `pop_stack` allocate `capacity` slots.
-        let buffers = 2 * 2 * size_of::<(String, String)>();
-        // 2 slots per stored element (value + running extremum) times the
-        // per-element heap payload from `elem`.
-        let elems = 2 * 6;
+        let buffers = moving_min.deque.capacity() * size_of::<(u64, String)>();
+        let elems = 6;
         assert_eq!(moving_min.heap_size(elem), buffers + elems);
         assert_eq!(moving_max.heap_size(elem), buffers + elems);
     }
 
+    #[test]
+    fn test_moving_min_max_empty_pop() {
+        let mut moving_min = MovingMin::<i32>::new();
+        moving_min.pop(); // empty pop is a no-op
+        assert_eq!(moving_min.len(), 0);
+        assert!(moving_min.is_empty());
+        // Verify it still works correctly after empty pop
+        moving_min.push(10);
+        moving_min.push(20);
+        assert_eq!(moving_min.min(), Some(&10));
+        moving_min.pop();
+        assert_eq!(moving_min.min(), Some(&20));
+
+        let mut moving_max = MovingMax::<i32>::new();
+        moving_max.pop(); // empty pop is a no-op
+        assert_eq!(moving_max.len(), 0);
+        assert!(moving_max.is_empty());
+        // Verify it still works correctly after empty pop
+        moving_max.push(20);
+        moving_max.push(10);
+        assert_eq!(moving_max.max(), Some(&20));
+        moving_max.pop();
+        assert_eq!(moving_max.max(), Some(&10));
+    }
+
+    #[test]
+    fn test_moving_min_max_duplicate_heavy() {
+        let mut moving_min = MovingMin::<i32>::new();
+        let mut moving_max = MovingMax::<i32>::new();
+
+        // Push duplicates
+        for _ in 0..5 {
+            moving_min.push(5);
+            moving_max.push(5);
+        }
+
+        assert_eq!(moving_min.len(), 5);
+        assert_eq!(moving_max.len(), 5);
+
+        // Ensure min/max query works and we can pop all duplicates correctly
+        for i in (1..=5).rev() {
+            assert_eq!(moving_min.len(), i);
+            assert_eq!(moving_max.len(), i);
+            assert_eq!(moving_min.min(), Some(&5));
+            assert_eq!(moving_max.max(), Some(&5));
+            moving_min.pop();
+            moving_max.pop();
+        }
+
+        assert!(moving_min.is_empty());
+        assert!(moving_max.is_empty());
+    }
+
     #[test]
     fn test_min_max_coerce_types() {
         // the coerced types is same with input types
diff --git a/docs/source/library-user-guide/upgrading/55.0.0.md b/docs/source/library-user-guide/upgrading/55.0.0.md
index df268792d8..6097c8dc71 100644
--- a/docs/source/library-user-guide/upgrading/55.0.0.md
+++ b/docs/source/library-user-guide/upgrading/55.0.0.md
@@ -884,6 +884,16 @@ let stream = csv_format.read_to_delimited_chunks_from_stream(input);
 let plan = deserialize_bytes(&proto_bytes)?;
 ```
 
+### `MovingMin` and `MovingMax` changed to `pub(crate)`
+
+`MovingMin` and `MovingMax` in `datafusion_functions_aggregate::min_max` have been changed from `pub` to `pub(crate)` visibility as they are internal helper data structures for DataFusion's sliding window aggregators.
+
+**Who is affected:**
+
+- Code that directly imported `MovingMin` or `MovingMax` from `datafusion_functions_aggregate`. Standard SQL window functions (`MIN(...) OVER (...)` / `MAX(...) OVER (...)`) are unaffected.
+
+See [PR #23827](https://github.com/apache/datafusion/pull/23827) for details.
+
 ### `MSRV` updated to 1.94.0
 
 The Minimum Supported Rust Version (MSRV) has been updated to [`1.94.0`].


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org