77use std:: sync:: Arc ;
88
99use crate :: PhysicalExpr ;
10- use arrow:: array:: { ArrayRef , BooleanArray } ;
11- use arrow:: record_batch:: RecordBatch ;
12- use datafusion_common:: { Result , ScalarValue } ;
10+ use arrow:: array:: { Array , ArrayRef , BooleanArray , NullArray , new_null_array} ;
11+ use arrow:: compute:: FilterBuilder ;
12+ use arrow:: datatypes:: { DataType , Field , Fields , Schema , SchemaRef } ;
13+ use arrow:: record_batch:: { RecordBatch , RecordBatchOptions } ;
14+ use datafusion_common:: cast:: as_boolean_array;
15+ use datafusion_common:: { Result , ScalarValue , internal_err} ;
1316use datafusion_physical_expr:: expressions:: Literal ;
17+ use datafusion_physical_expr:: utils:: collect_columns;
18+ use datafusion_physical_expr_common:: utils:: scatter;
19+ use itertools:: Itertools ;
1420
1521/// Largest literal array, in bytes, that an [`AggregateArgument`] keeps for
1622/// later batches.
@@ -35,16 +41,42 @@ const MAX_KEPT_LITERAL_ARRAY_BYTES: usize = 1024 * 1024;
3541/// [`ColumnarValue::Scalar`]: datafusion_expr::ColumnarValue::Scalar
3642pub ( in crate :: aggregates) struct AggregateArgument {
3743 expr : Arc < dyn PhysicalExpr > ,
44+ /// The argument's type in the input schema, also used for rejected rows.
45+ data_type : DataType ,
3846 /// Set when `expr` is a [`Literal`].
3947 literal : Option < LiteralArray > ,
4048}
4149
4250impl AggregateArgument {
43- pub ( in crate :: aggregates) fn new ( expr : Arc < dyn PhysicalExpr > ) -> Self {
51+ pub ( in crate :: aggregates) fn try_new (
52+ expr : Arc < dyn PhysicalExpr > ,
53+ input_schema : & Schema ,
54+ ) -> Result < Self > {
55+ let data_type = expr. data_type ( input_schema) ?;
4456 let literal = expr
4557 . downcast_ref :: < Literal > ( )
4658 . map ( |literal| LiteralArray :: new ( literal. value ( ) . clone ( ) ) ) ;
47- Self { expr, literal }
59+ Ok ( Self {
60+ expr,
61+ data_type,
62+ literal,
63+ } )
64+ }
65+
66+ /// Keeps the expression and its type without retaining a literal array.
67+ pub ( in crate :: aggregates) fn empty_like ( & self ) -> Self {
68+ Self {
69+ expr : Arc :: clone ( & self . expr ) ,
70+ data_type : self . data_type . clone ( ) ,
71+ literal : self
72+ . literal
73+ . as_ref ( )
74+ . map ( |literal| LiteralArray :: new ( literal. value . clone ( ) ) ) ,
75+ }
76+ }
77+
78+ pub ( in crate :: aggregates) fn null_array ( & self , num_rows : usize ) -> ArrayRef {
79+ new_null_array ( & self . data_type , num_rows)
4880 }
4981
5082 pub ( in crate :: aggregates) fn expr ( & self ) -> & Arc < dyn PhysicalExpr > {
@@ -68,6 +100,10 @@ impl AggregateArgument {
68100 /// Evaluates the argument for the rows of `batch` where `selection` is
69101 /// true, returning one value per row of `batch`.
70102 ///
103+ /// `selected` holds those rows, as returned by [`AggregateFilter::select`].
104+ /// Like [`PhysicalExpr::evaluate_selection`], the argument is evaluated
105+ /// only against them, so rejected rows cannot raise errors.
106+ ///
71107 /// Rows where `selection` is not true may hold any value, because the
72108 /// selection is also passed to [`GroupsAccumulator::convert_to_state`],
73109 /// which ignores them.
@@ -77,16 +113,160 @@ impl AggregateArgument {
77113 & mut self ,
78114 batch : & RecordBatch ,
79115 selection : & BooleanArray ,
116+ selected : & RecordBatch ,
80117 ) -> Result < ArrayRef > {
118+ let num_rows = batch. num_rows ( ) ;
119+ if selected. num_rows ( ) == num_rows {
120+ return self . evaluate ( batch) ;
121+ }
122+ if selected. num_rows ( ) == 0 {
123+ // A fallible expression may fail even for an empty batch, so it
124+ // is not evaluated.
125+ return Ok ( self . null_array ( num_rows) ) ;
126+ }
81127 match & mut self . literal {
82- Some ( literal) if selection. has_true ( ) => {
83- literal. array_of_size ( batch. num_rows ( ) )
84- }
85- _ => self
86- . expr
87- . evaluate_selection ( batch, selection) ?
88- . into_array_of_size ( batch. num_rows ( ) ) ,
128+ Some ( literal) => literal. array_of_size ( num_rows) ,
129+ None => scatter ( selection, self . evaluate ( selected) ?. as_ref ( ) ) ,
130+ }
131+ }
132+ }
133+
134+ /// The `FILTER` clause of one aggregate function, such as `x > 0` in
135+ /// `SUM(y) FILTER (WHERE x > 0)`.
136+ ///
137+ /// The arguments of the aggregate are evaluated only for the rows the filter
138+ /// selects, so those rows are copied out of each input batch first: evaluating
139+ /// the arguments for every row could raise errors for rejected rows, such as
140+ /// division by zero in `SUM(1 / x) FILTER (WHERE x <> 0)`.
141+ ///
142+ /// Only the input columns that the arguments read are copied. A query may have
143+ /// many filtered aggregates over a wide input, and copying every column for
144+ /// every aggregate would dominate the cost of the aggregation.
145+ pub ( in crate :: aggregates) struct AggregateFilter {
146+ predicate : Arc < dyn PhysicalExpr > ,
147+ /// Sorted indices of the input columns that the arguments read.
148+ argument_columns : Vec < usize > ,
149+ /// The input schema last passed to [`Self::select`], and the schema of the
150+ /// batches it returns for that input.
151+ selected_schema : Option < ( SchemaRef , SchemaRef ) > ,
152+ }
153+
154+ impl AggregateFilter {
155+ pub ( in crate :: aggregates) fn new (
156+ predicate : Arc < dyn PhysicalExpr > ,
157+ arguments : & [ AggregateArgument ] ,
158+ ) -> Self {
159+ let argument_columns = arguments
160+ . iter ( )
161+ . flat_map ( |argument| collect_columns ( argument. expr ( ) ) )
162+ . map ( |column| column. index ( ) )
163+ . sorted_unstable ( )
164+ . dedup ( )
165+ . collect ( ) ;
166+ Self {
167+ predicate,
168+ argument_columns,
169+ selected_schema : None ,
170+ }
171+ }
172+
173+ pub ( in crate :: aggregates) fn predicate ( & self ) -> & Arc < dyn PhysicalExpr > {
174+ & self . predicate
175+ }
176+
177+ /// Evaluates the filter predicate for every row of `batch`.
178+ pub ( in crate :: aggregates) fn evaluate (
179+ & self ,
180+ batch : & RecordBatch ,
181+ ) -> Result < BooleanArray > {
182+ let selection = self
183+ . predicate
184+ . evaluate ( batch) ?
185+ . into_array ( batch. num_rows ( ) ) ?;
186+ Ok ( as_boolean_array ( & selection) ?. clone ( ) )
187+ }
188+
189+ /// Returns the rows of `batch` where `selection` is true, for evaluating
190+ /// the arguments of the aggregate.
191+ ///
192+ /// Only the columns that the arguments read are copied. The other columns
193+ /// are replaced by [`NullArray`]s, which hold no data, so the column
194+ /// indices in the arguments remain valid. If every row is selected, the
195+ /// input batch is shared without changing its schema or columns.
196+ pub ( in crate :: aggregates) fn select (
197+ & mut self ,
198+ batch : & RecordBatch ,
199+ selection : & BooleanArray ,
200+ ) -> Result < RecordBatch > {
201+ // Nulls reject their rows, but `has_false` does not count them.
202+ if selection. null_count ( ) == 0 && !selection. has_false ( ) {
203+ return Ok ( batch. clone ( ) ) ;
204+ }
205+ let schema = batch. schema_ref ( ) ;
206+ // As in `filter_record_batch`, optimizing the filter pays off only
207+ // when it is applied to several arrays.
208+ let optimize = match self . argument_columns . as_slice ( ) {
209+ [ ] => false ,
210+ [ index] => schema. fields ( ) . get ( * index) . is_some_and ( |field| {
211+ FilterBuilder :: is_optimize_beneficial ( field. data_type ( ) )
212+ } ) ,
213+ _ => true ,
214+ } ;
215+ let mut builder = FilterBuilder :: new ( selection) ;
216+ if optimize {
217+ builder = builder. optimize ( ) ;
218+ }
219+ let predicate = builder. build ( ) ;
220+
221+ let num_rows = predicate. count ( ) ;
222+ // Every column the arguments do not read shares one placeholder.
223+ let placeholder: ArrayRef = Arc :: new ( NullArray :: new ( num_rows) ) ;
224+ let mut columns = vec ! [ placeholder; batch. num_columns( ) ] ;
225+ for & index in & self . argument_columns {
226+ let Some ( column) = batch. columns ( ) . get ( index) else {
227+ return internal_err ! (
228+ "Aggregate argument references column {index}, but the input has {} columns" ,
229+ batch. num_columns( )
230+ ) ;
231+ } ;
232+ columns[ index] = predicate. filter ( column. as_ref ( ) ) ?;
233+ }
234+
235+ let options = RecordBatchOptions :: new ( ) . with_row_count ( Some ( num_rows) ) ;
236+ Ok ( RecordBatch :: try_new_with_options (
237+ self . selected_schema ( schema) ,
238+ columns,
239+ & options,
240+ ) ?)
241+ }
242+
243+ /// Returns `schema` with the fields of columns that the arguments do not
244+ /// read changed to [`DataType::Null`].
245+ fn selected_schema ( & mut self , schema : & SchemaRef ) -> SchemaRef {
246+ if let Some ( ( input, selected) ) = & self . selected_schema
247+ && input == schema
248+ {
249+ return Arc :: clone ( selected) ;
89250 }
251+
252+ // Schema::project would remove fields and change the column indices
253+ // used by the existing argument expressions.
254+ let fields = schema
255+ . fields ( )
256+ . iter ( )
257+ . enumerate ( )
258+ . map ( |( index, field) | {
259+ if self . argument_columns . binary_search ( & index) . is_ok ( ) {
260+ Arc :: clone ( field)
261+ } else {
262+ Arc :: new ( Field :: new ( field. name ( ) , DataType :: Null , true ) )
263+ }
264+ } )
265+ . collect :: < Fields > ( ) ;
266+ let selected =
267+ Arc :: new ( Schema :: new_with_metadata ( fields, schema. metadata ( ) . clone ( ) ) ) ;
268+ self . selected_schema = Some ( ( Arc :: clone ( schema) , Arc :: clone ( & selected) ) ) ;
269+ selected
90270 }
91271}
92272
@@ -122,9 +302,11 @@ impl LiteralArray {
122302mod tests {
123303 use super :: * ;
124304
125- use arrow:: array:: { AsArray , Int32Array } ;
126- use arrow:: datatypes:: { DataType , Field , Int32Type , Schema } ;
127- use datafusion_physical_expr:: expressions:: { col, lit} ;
305+ use arrow:: array:: { AsArray , Int32Array , StringArray } ;
306+ use arrow:: compute:: filter_record_batch;
307+ use arrow:: datatypes:: Int32Type ;
308+ use datafusion_expr:: Operator ;
309+ use datafusion_physical_expr:: expressions:: { binary, col, lit} ;
128310
129311 fn batch ( num_rows : usize ) -> RecordBatch {
130312 let schema = Arc :: new ( Schema :: new ( vec ! [ Field :: new( "a" , DataType :: Int32 , true ) ] ) ) ;
@@ -138,7 +320,7 @@ mod tests {
138320
139321 #[ test]
140322 fn literal_array_is_reused_across_batches ( ) -> Result < ( ) > {
141- let mut argument = AggregateArgument :: new ( lit ( 1i32 ) ) ;
323+ let mut argument = AggregateArgument :: try_new ( lit ( 1i32 ) , batch ( 0 ) . schema_ref ( ) ) ? ;
142324
143325 let first = argument. evaluate ( & batch ( 4 ) ) ?;
144326 let smaller = argument. evaluate ( & batch ( 3 ) ) ?;
@@ -163,7 +345,8 @@ mod tests {
163345
164346 #[ test]
165347 fn large_literal_array_is_not_kept ( ) -> Result < ( ) > {
166- let mut argument = AggregateArgument :: new ( lit ( "x" . repeat ( 1024 ) ) ) ;
348+ let mut argument =
349+ AggregateArgument :: try_new ( lit ( "x" . repeat ( 1024 ) ) , batch ( 0 ) . schema_ref ( ) ) ?;
167350
168351 let first = argument. evaluate ( & batch ( 2048 ) ) ?;
169352 let second = argument. evaluate ( & batch ( 2048 ) ) ?;
@@ -178,7 +361,7 @@ mod tests {
178361 #[ test]
179362 fn non_literal_is_evaluated_for_every_batch ( ) -> Result < ( ) > {
180363 let schema = batch ( 0 ) . schema ( ) ;
181- let mut argument = AggregateArgument :: new ( col ( "a" , & schema) ?) ;
364+ let mut argument = AggregateArgument :: try_new ( col ( "a" , & schema) ?, & schema ) ? ;
182365
183366 let first = argument. evaluate ( & batch ( 3 ) ) ?;
184367 assert_eq ! (
@@ -194,28 +377,71 @@ mod tests {
194377 }
195378
196379 #[ test]
197- fn literal_selection_matches_evaluate_selection ( ) -> Result < ( ) > {
198- let batch = batch ( 3 ) ;
199- let expr = lit ( 7i32 ) ;
200- let mut argument = AggregateArgument :: new ( Arc :: clone ( & expr) ) ;
201-
202- for selection in [
203- BooleanArray :: from ( vec ! [ true , true , true ] ) ,
204- BooleanArray :: from ( vec ! [ false , true , false ] ) ,
205- BooleanArray :: from ( vec ! [ Some ( false ) , None , Some ( true ) ] ) ,
206- BooleanArray :: from ( vec ! [ false , false , false ] ) ,
207- BooleanArray :: from ( vec ! [ None , Some ( false ) , None ] ) ,
208- ] {
209- let expected = expr
210- . evaluate_selection ( & batch, & selection) ?
211- . into_array ( batch. num_rows ( ) ) ?;
212- let actual = argument. evaluate_selection ( & batch, & selection) ?;
213- assert_eq ! (
214- actual. as_ref( ) ,
215- expected. as_ref( ) ,
216- "selection {selection:?}"
217- ) ;
380+ fn filter_selects_only_argument_columns ( ) -> Result < ( ) > {
381+ let schema = Arc :: new ( Schema :: new ( vec ! [
382+ Field :: new( "a" , DataType :: Int32 , true ) ,
383+ Field :: new( "b" , DataType :: Utf8 , true ) ,
384+ Field :: new( "c" , DataType :: Int32 , false ) ,
385+ ] ) ) ;
386+ let batch = RecordBatch :: try_new (
387+ Arc :: clone ( & schema) ,
388+ vec ! [
389+ Arc :: new( Int32Array :: from( vec![ 1 , 2 , 3 , 4 ] ) ) ,
390+ Arc :: new( StringArray :: from( vec![ "w" , "x" , "y" , "z" ] ) ) ,
391+ Arc :: new( Int32Array :: from( vec![ 10 , 20 , 30 , 40 ] ) ) ,
392+ ] ,
393+ ) ?;
394+ let selection =
395+ BooleanArray :: from ( vec ! [ Some ( true ) , Some ( false ) , None , Some ( true ) ] ) ;
396+ let expected = filter_record_batch ( & batch, & selection) ?;
397+
398+ // `c + a` reads columns 0 and 2, so column 1 is not copied.
399+ let expr = binary (
400+ col ( "c" , & schema) ?,
401+ Operator :: Plus ,
402+ col ( "a" , & schema) ?,
403+ & schema,
404+ ) ?;
405+ let mut argument = AggregateArgument :: try_new ( expr, & schema) ?;
406+ let mut filter = AggregateFilter :: new ( lit ( true ) , std:: slice:: from_ref ( & argument) ) ;
407+ let selected = filter. select ( & batch, & selection) ?;
408+ assert_eq ! ( selected. num_rows( ) , 2 ) ;
409+ assert_eq ! ( selected. column( 0 ) , expected. column( 0 ) ) ;
410+ assert_eq ! ( selected. column( 2 ) , expected. column( 2 ) ) ;
411+ assert_eq ! ( selected. column( 1 ) . data_type( ) , & DataType :: Null ) ;
412+ assert_eq ! ( selected. column( 1 ) . len( ) , 2 ) ;
413+ assert_eq ! ( selected. schema( ) . field( 1 ) . name( ) , "b" ) ;
414+ assert_eq ! (
415+ argument. evaluate( & selected) ?. as_ref( ) ,
416+ argument. evaluate( & expected) ?. as_ref( )
417+ ) ;
418+
419+ // The schema of the selected rows is reused for later batches.
420+ let next =
421+ filter. select ( & batch, & BooleanArray :: from ( vec ! [ true , true , false , true ] ) ) ?;
422+ assert_eq ! ( next. num_rows( ) , 3 ) ;
423+ assert ! ( Arc :: ptr_eq( selected. schema_ref( ) , next. schema_ref( ) ) ) ;
424+
425+ // Selecting every row shares the original arrays and schema.
426+ let all = filter. select ( & batch, & BooleanArray :: from ( vec ! [ true ; 4 ] ) ) ?;
427+ assert ! ( Arc :: ptr_eq( batch. schema_ref( ) , all. schema_ref( ) ) ) ;
428+ for ( input, selected) in batch. columns ( ) . iter ( ) . zip ( all. columns ( ) ) {
429+ assert ! ( Arc :: ptr_eq( input, selected) ) ;
218430 }
431+
432+ // `COUNT(*)` reads no columns.
433+ let mut filter = AggregateFilter :: new (
434+ lit ( true ) ,
435+ & [ AggregateArgument :: try_new ( lit ( 1 ) , & schema) ?] ,
436+ ) ;
437+ let selected = filter. select ( & batch, & selection) ?;
438+ assert_eq ! ( selected. num_rows( ) , 2 ) ;
439+ assert ! (
440+ selected
441+ . columns( )
442+ . iter( )
443+ . all( |column| column. data_type( ) == & DataType :: Null )
444+ ) ;
219445 Ok ( ( ) )
220446 }
221447}
0 commit comments