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