Skip to content

Commit 34eb6dc

Browse files
authored
perf: filter only aggregate argument columns (#27119)
## Which issue does this PR close? - Closes #27114. ## Rationale for this change Each aggregate with `FILTER` currently filters every input column before evaluating its arguments. Queries with several filtered aggregates repeatedly copy columns that each aggregate does not read. This change filters only the columns needed by that aggregate, while preserving evaluation after filtering so rejected rows cannot cause errors such as division by zero. ## What changes are included in this PR? - Record the input columns used by each aggregate's arguments, including its `ORDER BY` expressions. Unread columns use data-free `NullArray` placeholders to keep column indices valid. - Apply this to ungrouped aggregation, compacting grouped hash aggregation, and skip-partial state conversion. Skip-partial conversion shares one selected batch across all arguments. - Add SQL regressions for multiple aggregates, ordering, NULL and empty selections, fallible arguments, multiple partitions, and multi-argument skip-partial conversion. Physical-plan tests verify that unused columns are not copied and that skip-partial execution is exercised. For the issue's 20M-row reproducer with 15 filtered aggregates, local medians of 21 warm runs after three warm-ups were: | Query | main (`70f2ed01b`) | This change | Speedup | |---|---:|---:|---:| | No `GROUP BY` | 68 ms | 37 ms | 1.84x | | `GROUP BY quantity % 8` | 95 ms | 56 ms | 1.70x | Both builds used `release-nonlto`; all results matched. The corresponding `CASE WHEN` controls measured 46/47 ms and 80/86 ms. Other local builds were running concurrently, so these timings include scheduling noise. ## What is the testing strategy for this PR? - `cargo fmt --all` and `cargo clippy --profile ci --all-targets --all-features -- -D warnings` passed. - Ran 10 representative cases from the existing `aggregate_filter` Criterion benchmark against main, covering column/literal arguments, selection rates, group cardinality, and unfiltered controls. An initial 5.8% slowdown in an unfiltered control did not consistently reproduce in three alternating-order repetitions (fix/main ratios 0.998, 0.943, and 1.019). ## Are there any user-facing changes? Lower copying overhead for aggregate `FILTER` queries. SQL behavior and public APIs are unchanged.
1 parent 01f4796 commit 34eb6dc

6 files changed

Lines changed: 906 additions & 119 deletions

File tree

‎datafusion/physical-plan/src/aggregates/aggregate_argument.rs‎

Lines changed: 265 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -7,10 +7,16 @@
77
use std::sync::Arc;
88

99
use 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};
1316
use 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
3642
pub(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

4250
impl 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 {
122302
mod 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

Comments
 (0)