Skip to content

Commit afb1ae2

Browse files
Berkay Şahinmustafasrepo
andauthored
Support min max aggregates in window functions with sliding windows (#4675)
* MIN, MAX Aggregate Functions with custom window frames The functions are run with only float64 columns now as in the test case. Support for all types will be implemented. * All ScalarValue types are supported now. * moving_min_max crate dependency is eliminated * use optimized accumulators when retract is not used * Where the algorithm was taken from added as a comment * Change design to use sliding implementation when absolutely necessary * add fuzzy tests for moving min max, remove unsafe block * remove duplicated code * doc comments for example codes * cargo test error correction * revert unnecessary changes Co-authored-by: Mustafa Akur <[email protected]>
1 parent 77991a3 commit afb1ae2

13 files changed

Lines changed: 756 additions & 71 deletions

File tree

‎datafusion/core/src/physical_plan/windows/mod.rs‎

Lines changed: 22 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,9 @@ use datafusion_expr::{
3333
window_function::{signature_for_built_in, BuiltInWindowFunction, WindowFunction},
3434
WindowFrame,
3535
};
36-
use datafusion_physical_expr::window::BuiltInWindowFunctionExpr;
36+
use datafusion_physical_expr::window::{
37+
BuiltInWindowFunctionExpr, SlidingAggregateWindowExpr,
38+
};
3739
use std::convert::TryInto;
3840
use std::sync::Arc;
3941

@@ -55,12 +57,25 @@ pub fn create_window_expr(
5557
input_schema: &Schema,
5658
) -> Result<Arc<dyn WindowExpr>> {
5759
Ok(match fun {
58-
WindowFunction::AggregateFunction(fun) => Arc::new(AggregateWindowExpr::new(
59-
aggregates::create_aggregate_expr(fun, false, args, input_schema, name)?,
60-
partition_by,
61-
order_by,
62-
window_frame,
63-
)),
60+
WindowFunction::AggregateFunction(fun) => {
61+
let aggregate =
62+
aggregates::create_aggregate_expr(fun, false, args, input_schema, name)?;
63+
if !window_frame.start_bound.is_unbounded() {
64+
Arc::new(SlidingAggregateWindowExpr::new(
65+
aggregate,
66+
partition_by,
67+
order_by,
68+
window_frame,
69+
))
70+
} else {
71+
Arc::new(AggregateWindowExpr::new(
72+
aggregate,
73+
partition_by,
74+
order_by,
75+
window_frame,
76+
))
77+
}
78+
}
6479
WindowFunction::BuiltInWindowFunction(fun) => Arc::new(BuiltInWindowExpr::new(
6580
create_built_in_window_expr(fun, args, input_schema, name)?,
6681
partition_by,

‎datafusion/core/tests/sql/aggregates.rs‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -679,6 +679,60 @@ async fn aggregate_grouped_min() -> Result<()> {
679679
Ok(())
680680
}
681681

682+
#[tokio::test]
683+
async fn aggregate_min_max_w_custom_window_frames() -> Result<()> {
684+
let ctx = SessionContext::new();
685+
register_aggregate_csv(&ctx).await?;
686+
let sql =
687+
"SELECT
688+
MIN(c12) OVER (ORDER BY C12 RANGE BETWEEN 0.3 PRECEDING AND 0.2 FOLLOWING) as min1,
689+
MAX(c12) OVER (ORDER BY C11 RANGE BETWEEN 0.1 PRECEDING AND 0.2 FOLLOWING) as max1
690+
FROM aggregate_test_100
691+
ORDER BY C9
692+
LIMIT 5";
693+
let actual = execute_to_batches(&ctx, sql).await;
694+
let expected = vec![
695+
"+---------------------+--------------------+",
696+
"| min1 | max1 |",
697+
"+---------------------+--------------------+",
698+
"| 0.01479305307777301 | 0.9965400387585364 |",
699+
"| 0.01479305307777301 | 0.9800193410444061 |",
700+
"| 0.01479305307777301 | 0.9706712283358269 |",
701+
"| 0.2667177795079635 | 0.9965400387585364 |",
702+
"| 0.3600766362333053 | 0.9706712283358269 |",
703+
"+---------------------+--------------------+",
704+
];
705+
assert_batches_eq!(expected, &actual);
706+
Ok(())
707+
}
708+
709+
#[tokio::test]
710+
async fn aggregate_min_max_w_custom_window_frames_unbounded_start() -> Result<()> {
711+
let ctx = SessionContext::new();
712+
register_aggregate_csv(&ctx).await?;
713+
let sql =
714+
"SELECT
715+
MIN(c12) OVER (ORDER BY C12 RANGE BETWEEN UNBOUNDED PRECEDING AND 0.2 FOLLOWING) as min1,
716+
MAX(c12) OVER (ORDER BY C11 RANGE BETWEEN UNBOUNDED PRECEDING AND 0.2 FOLLOWING) as max1
717+
FROM aggregate_test_100
718+
ORDER BY C9
719+
LIMIT 5";
720+
let actual = execute_to_batches(&ctx, sql).await;
721+
let expected = vec![
722+
"+---------------------+--------------------+",
723+
"| min1 | max1 |",
724+
"+---------------------+--------------------+",
725+
"| 0.01479305307777301 | 0.9965400387585364 |",
726+
"| 0.01479305307777301 | 0.9800193410444061 |",
727+
"| 0.01479305307777301 | 0.9800193410444061 |",
728+
"| 0.01479305307777301 | 0.9965400387585364 |",
729+
"| 0.01479305307777301 | 0.9800193410444061 |",
730+
"+---------------------+--------------------+",
731+
];
732+
assert_batches_eq!(expected, &actual);
733+
Ok(())
734+
}
735+
682736
#[tokio::test]
683737
async fn aggregate_avg_add() -> Result<()> {
684738
let results = execute_with_partition(

‎datafusion/expr/src/window_frame.rs‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -147,6 +147,16 @@ pub enum WindowFrameBound {
147147
Following(ScalarValue),
148148
}
149149

150+
impl WindowFrameBound {
151+
pub fn is_unbounded(&self) -> bool {
152+
match self {
153+
WindowFrameBound::Preceding(elem) => elem.is_null(),
154+
WindowFrameBound::CurrentRow => false,
155+
WindowFrameBound::Following(elem) => elem.is_null(),
156+
}
157+
}
158+
}
159+
150160
impl TryFrom<ast::WindowFrameBound> for WindowFrameBound {
151161
type Error = DataFusionError;
152162

‎datafusion/physical-expr/src/aggregate/average.rs‎

Lines changed: 4 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -21,7 +21,9 @@ use std::any::Any;
2121
use std::convert::TryFrom;
2222
use std::sync::Arc;
2323

24-
use crate::aggregate::row_accumulator::RowAccumulator;
24+
use crate::aggregate::row_accumulator::{
25+
is_row_accumulator_support_dtype, RowAccumulator,
26+
};
2527
use crate::aggregate::sum;
2628
use crate::expressions::format_state_name;
2729
use crate::{AggregateExpr, PhysicalExpr};
@@ -105,19 +107,7 @@ impl AggregateExpr for Avg {
105107
}
106108

107109
fn row_accumulator_supported(&self) -> bool {
108-
matches!(
109-
self.data_type,
110-
DataType::UInt8
111-
| DataType::UInt16
112-
| DataType::UInt32
113-
| DataType::UInt64
114-
| DataType::Int8
115-
| DataType::Int16
116-
| DataType::Int32
117-
| DataType::Int64
118-
| DataType::Float32
119-
| DataType::Float64
120-
)
110+
is_row_accumulator_support_dtype(&self.data_type)
121111
}
122112

123113
fn create_row_accumulator(

‎datafusion/physical-expr/src/aggregate/count.rs‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -104,6 +104,10 @@ impl AggregateExpr for Count {
104104
) -> Result<Box<dyn RowAccumulator>> {
105105
Ok(Box::new(CountRowAccumulator::new(start_index)))
106106
}
107+
108+
fn create_sliding_accumulator(&self) -> Result<Box<dyn Accumulator>> {
109+
Ok(Box::new(CountAccumulator::new()))
110+
}
107111
}
108112

109113
#[derive(Debug)]

‎datafusion/physical-expr/src/aggregate/min_max.rs‎

Lines changed: 132 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -39,12 +39,16 @@ use datafusion_common::ScalarValue;
3939
use datafusion_common::{downcast_value, DataFusionError, Result};
4040
use datafusion_expr::Accumulator;
4141

42-
use crate::aggregate::row_accumulator::RowAccumulator;
42+
use crate::aggregate::row_accumulator::{
43+
is_row_accumulator_support_dtype, RowAccumulator,
44+
};
4345
use crate::expressions::format_state_name;
4446
use arrow::array::Array;
4547
use arrow::array::Decimal128Array;
4648
use datafusion_row::accessor::RowAccessor;
4749

50+
use super::moving_min_max;
51+
4852
// Min/max aggregation can take Dictionary encode input but always produces unpacked
4953
// (aka non Dictionary) output. We need to adjust the output data type to reflect this.
5054
// The reason min/max aggregate produces unpacked output because there is only one
@@ -117,19 +121,7 @@ impl AggregateExpr for Max {
117121
}
118122

119123
fn row_accumulator_supported(&self) -> bool {
120-
matches!(
121-
self.data_type,
122-
DataType::UInt8
123-
| DataType::UInt16
124-
| DataType::UInt32
125-
| DataType::UInt64
126-
| DataType::Int8
127-
| DataType::Int16
128-
| DataType::Int32
129-
| DataType::Int64
130-
| DataType::Float32
131-
| DataType::Float64
132-
)
124+
is_row_accumulator_support_dtype(&self.data_type)
133125
}
134126

135127
fn create_row_accumulator(
@@ -141,6 +133,10 @@ impl AggregateExpr for Max {
141133
self.data_type.clone(),
142134
)))
143135
}
136+
137+
fn create_sliding_accumulator(&self) -> Result<Box<dyn Accumulator>> {
138+
Ok(Box::new(SlidingMaxAccumulator::try_new(&self.data_type)?))
139+
}
144140
}
145141

146142
// Statically-typed version of min/max(array) -> ScalarValue for string types.
@@ -577,6 +573,62 @@ impl Accumulator for MaxAccumulator {
577573
}
578574
}
579575

576+
/// An accumulator to compute the maximum value
577+
#[derive(Debug)]
578+
pub struct SlidingMaxAccumulator {
579+
max: ScalarValue,
580+
moving_max: moving_min_max::MovingMax<ScalarValue>,
581+
}
582+
583+
impl SlidingMaxAccumulator {
584+
/// new max accumulator
585+
pub fn try_new(datatype: &DataType) -> Result<Self> {
586+
Ok(Self {
587+
max: ScalarValue::try_from(datatype)?,
588+
moving_max: moving_min_max::MovingMax::<ScalarValue>::new(),
589+
})
590+
}
591+
}
592+
593+
impl Accumulator for SlidingMaxAccumulator {
594+
fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> {
595+
for idx in 0..values[0].len() {
596+
let val = ScalarValue::try_from_array(&values[0], idx)?;
597+
self.moving_max.push(val);
598+
}
599+
if let Some(res) = self.moving_max.max() {
600+
self.max = res.clone();
601+
}
602+
Ok(())
603+
}
604+
605+
fn retract_batch(&mut self, values: &[ArrayRef]) -> Result<()> {
606+
for _idx in 0..values[0].len() {
607+
(self.moving_max).pop();
608+
}
609+
if let Some(res) = self.moving_max.max() {
610+
self.max = res.clone();
611+
}
612+
Ok(())
613+
}
614+
615+
fn merge_batch(&mut self, states: &[ArrayRef]) -> Result<()> {
616+
self.update_batch(states)
617+
}
618+
619+
fn state(&self) -> Result<Vec<ScalarValue>> {
620+
Ok(vec![self.max.clone()])
621+
}
622+
623+
fn evaluate(&self) -> Result<ScalarValue> {
624+
Ok(self.max.clone())
625+
}
626+
627+
fn size(&self) -> usize {
628+
std::mem::size_of_val(self) - std::mem::size_of_val(&self.max) + self.max.size()
629+
}
630+
}
631+
580632
#[derive(Debug)]
581633
struct MaxRowAccumulator {
582634
index: usize,
@@ -679,19 +731,7 @@ impl AggregateExpr for Min {
679731
}
680732

681733
fn row_accumulator_supported(&self) -> bool {
682-
matches!(
683-
self.data_type,
684-
DataType::UInt8
685-
| DataType::UInt16
686-
| DataType::UInt32
687-
| DataType::UInt64
688-
| DataType::Int8
689-
| DataType::Int16
690-
| DataType::Int32
691-
| DataType::Int64
692-
| DataType::Float32
693-
| DataType::Float64
694-
)
734+
is_row_accumulator_support_dtype(&self.data_type)
695735
}
696736

697737
fn create_row_accumulator(
@@ -703,6 +743,10 @@ impl AggregateExpr for Min {
703743
self.data_type.clone(),
704744
)))
705745
}
746+
747+
fn create_sliding_accumulator(&self) -> Result<Box<dyn Accumulator>> {
748+
Ok(Box::new(SlidingMinAccumulator::try_new(&self.data_type)?))
749+
}
706750
}
707751

708752
/// An accumulator to compute the minimum value
@@ -745,6 +789,67 @@ impl Accumulator for MinAccumulator {
745789
}
746790
}
747791

792+
/// An accumulator to compute the minimum value
793+
#[derive(Debug)]
794+
pub struct SlidingMinAccumulator {
795+
min: ScalarValue,
796+
moving_min: moving_min_max::MovingMin<ScalarValue>,
797+
}
798+
799+
impl SlidingMinAccumulator {
800+
/// new min accumulator
801+
pub fn try_new(datatype: &DataType) -> Result<Self> {
802+
Ok(Self {
803+
min: ScalarValue::try_from(datatype)?,
804+
moving_min: moving_min_max::MovingMin::<ScalarValue>::new(),
805+
})
806+
}
807+
}
808+
809+
impl Accumulator for SlidingMinAccumulator {
810+
fn state(&self) -> Result<Vec<ScalarValue>> {
811+
Ok(vec![self.min.clone()])
812+
}
813+
814+
fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> {
815+
for idx in 0..values[0].len() {
816+
let val = ScalarValue::try_from_array(&values[0], idx)?;
817+
if !val.is_null() {
818+
self.moving_min.push(val);
819+
}
820+
}
821+
if let Some(res) = self.moving_min.min() {
822+
self.min = res.clone();
823+
}
824+
Ok(())
825+
}
826+
827+
fn retract_batch(&mut self, values: &[ArrayRef]) -> Result<()> {
828+
for idx in 0..values[0].len() {
829+
let val = ScalarValue::try_from_array(&values[0], idx)?;
830+
if !val.is_null() {
831+
(self.moving_min).pop();
832+
}
833+
}
834+
if let Some(res) = self.moving_min.min() {
835+
self.min = res.clone();
836+
}
837+
Ok(())
838+
}
839+
840+
fn merge_batch(&mut self, states: &[ArrayRef]) -> Result<()> {
841+
self.update_batch(states)
842+
}
843+
844+
fn evaluate(&self) -> Result<ScalarValue> {
845+
Ok(self.min.clone())
846+
}
847+
848+
fn size(&self) -> usize {
849+
std::mem::size_of_val(self) - std::mem::size_of_val(&self.min) + self.min.size()
850+
}
851+
}
852+
748853
#[derive(Debug)]
749854
struct MinRowAccumulator {
750855
index: usize,

‎datafusion/physical-expr/src/aggregate/mod.rs‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,7 @@ pub(crate) mod median;
4141
pub(crate) mod min_max;
4242
pub mod build_in;
4343
mod hyperloglog;
44+
pub mod moving_min_max;
4445
pub mod row_accumulator;
4546
pub(crate) mod stats;
4647
pub(crate) mod stddev;
@@ -101,4 +102,12 @@ pub trait AggregateExpr: Send + Sync + Debug {
101102
self
102103
)))
103104
}
105+
106+
/// Creates accumulator implementation that supports retract
107+
fn create_sliding_accumulator(&self) -> Result<Box<dyn Accumulator>> {
108+
Err(DataFusionError::NotImplemented(format!(
109+
"Retractable Accumulator hasn't been implemented for {:?} yet",
110+
self
111+
)))
112+
}
104113
}

0 commit comments

Comments
 (0)