Skip to content

Commit e7d9971

Browse files
authored
fix: do not extract common subexpressions from the arguments of an aggregate with a FILTER (apache#26184)
## Which issue does this PR close? - Closes apache#26183. ## Rationale for this change An aggregate with a `FILTER` clause evaluates its arguments only for the rows that pass the filter, so a fallible argument does not fail on a rejected row. When two aggregates have the same argument, `CommonSubexprEliminate` moves that argument into a projection below the aggregate. The projection evaluates it for every row, and the query fails on a row that the filter rejects: ```sql CREATE TABLE t AS SELECT * FROM (VALUES (CAST(-950 AS SMALLINT), 0), (CAST(5 AS SMALLINT), 1)) AS v(x, y); -- Succeeds. SELECT avg(arrow_cast(x, 'UInt64')) FILTER (WHERE y > 0) AS a FROM t; -- Fails: Arrow error: Cast error: Can't cast value -950 to type UInt64 SELECT sum(arrow_cast(x, 'UInt64')) FILTER (WHERE y > 0) AS s, count(arrow_cast(x, 'UInt64')) FILTER (WHERE y > 0) AS c FROM t; ``` The rule already has a model for this: a conditionally evaluated subexpression (a `CASE` branch, the right side of `AND` / `OR`, a lazy function argument) is extracted only if it is also surely evaluated somewhere else. The arguments of a filtered aggregate are conditionally evaluated in the same sense, but the rule did not know that. ## What changes are included in this PR? 1. `ExprCSEController::conditional_children` now reports the arguments and the `ORDER BY` expressions of an `Expr::AggregateFunction` with a `FILTER` as conditionally evaluated. The filter itself stays a normal child, because the aggregate evaluates it for every row. A filter that several aggregates share is still extracted. 2. The same function reports the arguments of an `Expr::WindowFunction` with a `FILTER` as conditionally evaluated. The `PARTITION BY` expressions, the `ORDER BY` expressions and the filter stay normal children. The window executor does not yet evaluate the filter first (apache#24507, apache#24508), so this part has no visible effect today. It keeps the rule correct when that fix merges. 3. `CSEVisitor::f_down` in `datafusion/common/src/cse.rs` now visits the children of a node with conditional children in tree order. Before, it visited all normal children and then all conditional children. `CSERewriter` reads `id_array` in pre-order, so that was correct only when every normal child came before every conditional child in the tree. The children of an aggregate are `args`, `filter`, `order_by`, so the normal child is in the middle. The `CSEController` trait is unchanged. The rule keeps every extraction that is safe: | Query shape | Before | After | |---|---|---| | `sum(f(x)) FILTER (WHERE p), count(f(x)) FILTER (WHERE p)` | `f(x)` and `p` extracted | only `p` extracted | | `sum(f(x)) FILTER (WHERE p), count(f(x))` | `f(x)` extracted | `f(x)` extracted (the second aggregate evaluates it for every row) | | `sum(f(x)) FILTER (WHERE f(x) > 0)` | `f(x)` extracted | `f(x)` extracted (the filter evaluates it for every row) | | `sum(f(x)) FILTER (WHERE p) AS a, sum(f(x)) FILTER (WHERE p) AS b` | one aggregate | one aggregate | The cost is the first row: when an expression occurs only under filtered aggregates, each aggregate now evaluates it, on the rows that pass its filter. An alternative keeps that extraction when every aggregate has the same filter, with a guard such as `CASE WHEN p THEN f(x) END` in the projection. I did not do that here because it is a larger change with its own plan shape, and it can be a follow-up. ## What is the testing strategy for this PR? - Unit tests in `common_subexpr_eliminate.rs`: `test_aggregate_filter_arguments` (the four rows of the table above), `test_aggregate_filter_order_by` and `test_window_filter_arguments`. - `cse.slt`: the reproduction above, with and without `GROUP BY`, the `EXPLAIN` that shows the cast stays in the aggregate, and the case where an unfiltered aggregate shares the argument. - `aggregates_simplify.slt`: one expected plan changes. `SUM(column1 + 1) FILTER (WHERE column1 > 1), SUM(column1 + 1) FILTER (WHERE column1 > 0)` no longer extracts `column1 + 1`. ## Are there any user-facing changes? Queries that failed with an error from a row that an aggregate `FILTER` rejects now succeed. Plans for queries where a subexpression occurs only in the arguments of filtered aggregates no longer have that subexpression in a `__common_expr` projection. There are no API changes.
1 parent 4ab4721 commit e7d9971

4 files changed

Lines changed: 318 additions & 19 deletions

File tree

‎datafusion/common/src/cse.rs‎

Lines changed: 18 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,7 @@ use crate::tree_node::{
2626
TreeNodeVisitor,
2727
};
2828
use indexmap::IndexMap;
29-
use std::collections::HashMap;
29+
use std::collections::{HashMap, HashSet};
3030
use std::hash::{BuildHasher, Hash, Hasher, RandomState};
3131
use std::marker::PhantomData;
3232
use std::sync::Arc;
@@ -176,6 +176,9 @@ pub trait CSEController {
176176

177177
/// Splits the children to normal and conditionally evaluated ones or returns `None`
178178
/// if all are always evaluated.
179+
///
180+
/// The returned references must point to the children of `node` themselves. The two
181+
/// lists can be in any order.
179182
fn conditional_children(node: &Self::Node) -> Option<ChildrenList<&Self::Node>>;
180183

181184
// Returns true if a node is valid. If a node is invalid then it can't be eliminated.
@@ -363,14 +366,21 @@ where
363366
// If we are already in a node that can short-circuit then start new
364367
// traversals on its normal conditional children.
365368
match C::conditional_children(node) {
366-
Some((normal, conditional)) => {
367-
normal
368-
.into_iter()
369-
.try_for_each(|n| n.visit(self).map(|_| ()))?;
370-
self.conditional = true;
371-
conditional
369+
Some((_normal, conditional)) => {
370+
// Visit the children in tree order, whatever order the
371+
// controller lists them in. `CSERewriter` reads `id_array` in
372+
// pre-order, so the indexes that this visitor assigns must
373+
// follow the same order.
374+
let conditional = conditional
372375
.into_iter()
373-
.try_for_each(|n| n.visit(self).map(|_| ()))?;
376+
.map(std::ptr::from_ref)
377+
.collect::<HashSet<_>>();
378+
node.apply_children(|child| {
379+
self.conditional =
380+
conditional.contains(&std::ptr::from_ref(child));
381+
child.visit(self)?;
382+
Ok(TreeNodeRecursion::Continue)
383+
})?;
374384
self.conditional = false;
375385

376386
TreeNodeRecursion::Jump

‎datafusion/optimizer/src/common_subexpr_eliminate.rs‎

Lines changed: 225 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,10 @@ use datafusion_common::alias::AliasGenerator;
3030
use datafusion_common::cse::{CSE, CSEController, FoundCommonNodes};
3131
use datafusion_common::tree_node::{Transformed, TreeNode};
3232
use datafusion_common::{Column, DFSchema, DFSchemaRef, Result, qualified_name};
33-
use datafusion_expr::expr::{Alias, HigherOrderFunction, ScalarFunction};
33+
use datafusion_expr::expr::{
34+
AggregateFunction, AggregateFunctionParams, Alias, HigherOrderFunction,
35+
ScalarFunction, WindowFunction, WindowFunctionParams,
36+
};
3437
use datafusion_expr::logical_plan::{
3538
Aggregate, Filter, LogicalPlan, Projection, Sort, Window,
3639
};
@@ -691,6 +694,62 @@ impl CSEController for ExprCSEController<'_> {
691694
.chain(else_expr.iter().map(|e| e.as_ref()))
692695
.collect(),
693696
)),
697+
698+
// An aggregate function with a `FILTER` clause evaluates the filter for
699+
// every input row, but it evaluates its arguments only for the rows that
700+
// pass the filter. Extracting an argument subexpression into a projection
701+
// below the aggregate would evaluate it for the rejected rows too, which
702+
// can raise an error (for example a failed cast or a division by zero)
703+
// that the filter must prevent. The `ORDER BY` expressions of the
704+
// aggregate are conservatively handled like the arguments.
705+
Expr::AggregateFunction(AggregateFunction {
706+
params:
707+
AggregateFunctionParams {
708+
args,
709+
filter: Some(filter),
710+
order_by,
711+
..
712+
},
713+
..
714+
}) => Some((
715+
vec![filter.as_ref()],
716+
args.iter()
717+
.chain(order_by.iter().map(|sort| &sort.expr))
718+
.collect(),
719+
)),
720+
721+
// The arguments of a window function with a `FILTER` clause are
722+
// conservatively handled like the arguments of a filtered aggregate.
723+
// The window executor does not guarantee the same today:
724+
// `AggregateWindowExpr::get_result_column` evaluates the arguments
725+
// before it applies the filter. This rule must not rely on that order,
726+
// so it does not extract a subexpression that occurs only in such
727+
// arguments. The `PARTITION BY` and `ORDER BY` expressions of the
728+
// window are evaluated for every input row.
729+
Expr::WindowFunction(window_function) => {
730+
let WindowFunction {
731+
params:
732+
WindowFunctionParams {
733+
args,
734+
partition_by,
735+
order_by,
736+
filter: Some(filter),
737+
..
738+
},
739+
..
740+
} = window_function.as_ref()
741+
else {
742+
return None;
743+
};
744+
Some((
745+
partition_by
746+
.iter()
747+
.chain(order_by.iter().map(|sort| &sort.expr))
748+
.chain([filter.as_ref()])
749+
.collect(),
750+
args.iter().collect(),
751+
))
752+
}
694753
_ => None,
695754
}
696755
}
@@ -842,9 +901,9 @@ mod test {
842901
use arrow::datatypes::{DataType, Field, Schema};
843902
use datafusion_expr::logical_plan::{JoinType, table_scan};
844903
use datafusion_expr::{
845-
AccumulatorFactoryFunction, AggregateUDF, ColumnarValue, ScalarFunctionArgs,
846-
ScalarUDF, ScalarUDFImpl, Signature, SimpleAggregateUDF, Volatility,
847-
grouping_set, is_null, not,
904+
AccumulatorFactoryFunction, AggregateUDF, ColumnarValue, ExprFunctionExt,
905+
ScalarFunctionArgs, ScalarUDF, ScalarUDFImpl, Signature, SimpleAggregateUDF,
906+
Volatility, WindowFunctionDefinition, grouping_set, is_null, not,
848907
};
849908
use datafusion_expr::{lit, logical_plan::builder::LogicalPlanBuilder};
850909

@@ -853,7 +912,7 @@ mod test {
853912
use crate::optimizer::OptimizerContext;
854913
use crate::test::udfs::leaf_udf_expr;
855914
use crate::test::*;
856-
use datafusion_expr::test::function_stub::{avg, sum};
915+
use datafusion_expr::test::function_stub::{avg, count, sum, sum_udaf};
857916
use datafusion_functions_window::row_number::row_number_udwf;
858917

859918
macro_rules! assert_optimized_plan_equal {
@@ -946,7 +1005,7 @@ mod test {
9461005
let return_type = DataType::UInt32;
9471006
let accumulator: AccumulatorFactoryFunction = Arc::new(|_| unimplemented!());
9481007
let udf_agg = |inner: Expr| {
949-
Expr::AggregateFunction(datafusion_expr::expr::AggregateFunction::new_udf(
1008+
Expr::AggregateFunction(AggregateFunction::new_udf(
9501009
Arc::new(AggregateUDF::from(SimpleAggregateUDF::new_with_signature(
9511010
"my_agg",
9521011
Signature::exact(vec![DataType::UInt32], Volatility::Stable),
@@ -1948,4 +2007,164 @@ mod test {
19482007
"
19492008
)
19502009
}
2010+
2011+
#[test]
2012+
fn test_aggregate_filter_arguments() -> Result<()> {
2013+
let table_scan = test_table_scan()?;
2014+
2015+
// An aggregate evaluates its arguments only for the rows that pass its
2016+
// `FILTER`. Thus `a + b` must stay in the aggregates. The filter `c > 0` is
2017+
// evaluated for every row and is extracted.
2018+
let filter = col("c").gt(lit(0));
2019+
let plan = LogicalPlanBuilder::from(table_scan.clone())
2020+
.aggregate(
2021+
iter::empty::<Expr>(),
2022+
vec![
2023+
sum(col("a") + col("b")).filter(filter.clone()).build()?,
2024+
count(col("a") + col("b")).filter(filter.clone()).build()?,
2025+
],
2026+
)?
2027+
.build()?;
2028+
2029+
assert_optimized_plan_equal!(
2030+
plan,
2031+
@ "
2032+
Aggregate: groupBy=[[]], aggr=[[sum(test.a + test.b) FILTER (WHERE __common_expr_1 AS test.c > Int32(0)) AS sum(test.a + test.b) FILTER (WHERE test.c > Int32(0)), COUNT(test.a + test.b) FILTER (WHERE __common_expr_1 AS test.c > Int32(0)) AS COUNT(test.a + test.b) FILTER (WHERE test.c > Int32(0))]]
2033+
Projection: test.c > Int32(0) AS __common_expr_1, test.a, test.b, test.c
2034+
TableScan: test
2035+
"
2036+
)?;
2037+
2038+
// `a + b` is surely evaluated by the aggregate without a `FILTER`, so it is
2039+
// extracted.
2040+
let plan = LogicalPlanBuilder::from(table_scan.clone())
2041+
.aggregate(
2042+
iter::empty::<Expr>(),
2043+
vec![
2044+
sum(col("a") + col("b")).filter(filter.clone()).build()?,
2045+
count(col("a") + col("b")),
2046+
],
2047+
)?
2048+
.build()?;
2049+
2050+
assert_optimized_plan_equal!(
2051+
plan,
2052+
@ "
2053+
Aggregate: groupBy=[[]], aggr=[[sum(__common_expr_1 AS test.a + test.b) FILTER (WHERE test.c > Int32(0)), COUNT(__common_expr_1 AS test.a + test.b)]]
2054+
Projection: test.a + test.b AS __common_expr_1, test.a, test.b, test.c
2055+
TableScan: test
2056+
"
2057+
)?;
2058+
2059+
// `a + b` is surely evaluated by the filter, so it is extracted.
2060+
let plan = LogicalPlanBuilder::from(table_scan.clone())
2061+
.aggregate(
2062+
iter::empty::<Expr>(),
2063+
vec![
2064+
sum(col("a") + col("b"))
2065+
.filter((col("a") + col("b")).gt(lit(0)))
2066+
.build()?,
2067+
],
2068+
)?
2069+
.build()?;
2070+
2071+
assert_optimized_plan_equal!(
2072+
plan,
2073+
@ "
2074+
Aggregate: groupBy=[[]], aggr=[[sum(__common_expr_1 AS test.a + test.b) FILTER (WHERE __common_expr_1 AS test.a + test.b > Int32(0)) AS sum(test.a + test.b) FILTER (WHERE test.a + test.b > Int32(0))]]
2075+
Projection: test.a + test.b AS __common_expr_1, test.a, test.b, test.c
2076+
TableScan: test
2077+
"
2078+
)?;
2079+
2080+
// Identical aggregates with a `FILTER` are still deduplicated.
2081+
let plan = LogicalPlanBuilder::from(table_scan)
2082+
.aggregate(
2083+
iter::empty::<Expr>(),
2084+
vec![
2085+
sum(col("a") + col("b"))
2086+
.filter(filter.clone())
2087+
.build()?
2088+
.alias("s1"),
2089+
sum(col("a") + col("b")).filter(filter).build()?.alias("s2"),
2090+
],
2091+
)?
2092+
.build()?;
2093+
2094+
assert_optimized_plan_equal!(
2095+
plan,
2096+
@ "
2097+
Projection: __common_expr_2 AS s1, __common_expr_2 AS s2
2098+
Aggregate: groupBy=[[]], aggr=[[sum(test.a + test.b) FILTER (WHERE __common_expr_1) AS __common_expr_2]]
2099+
Projection: test.c > Int32(0) AS __common_expr_1, test.a, test.b, test.c
2100+
TableScan: test
2101+
"
2102+
)
2103+
}
2104+
2105+
#[test]
2106+
fn test_aggregate_filter_order_by() -> Result<()> {
2107+
let table_scan = test_table_scan()?;
2108+
2109+
// The `ORDER BY` expressions of an aggregate with a `FILTER` are handled
2110+
// like its arguments, so `a + b` is not extracted.
2111+
let filter = col("c").gt(lit(0));
2112+
let order_by = vec![(col("a") + col("b")).sort(true, false)];
2113+
let plan = LogicalPlanBuilder::from(table_scan)
2114+
.aggregate(
2115+
iter::empty::<Expr>(),
2116+
vec![
2117+
sum(col("a"))
2118+
.order_by(order_by.clone())
2119+
.filter(filter.clone())
2120+
.build()?,
2121+
sum(col("b")).order_by(order_by).filter(filter).build()?,
2122+
],
2123+
)?
2124+
.build()?;
2125+
2126+
assert_optimized_plan_equal!(
2127+
plan,
2128+
@ "
2129+
Aggregate: groupBy=[[]], aggr=[[sum(test.a) FILTER (WHERE __common_expr_1 AS test.c > Int32(0)) ORDER BY [test.a + test.b ASC NULLS LAST] AS sum(test.a) FILTER (WHERE test.c > Int32(0)) ORDER BY [test.a + test.b ASC NULLS LAST], sum(test.b) FILTER (WHERE __common_expr_1 AS test.c > Int32(0)) ORDER BY [test.a + test.b ASC NULLS LAST] AS sum(test.b) FILTER (WHERE test.c > Int32(0)) ORDER BY [test.a + test.b ASC NULLS LAST]]]
2130+
Projection: test.c > Int32(0) AS __common_expr_1, test.a, test.b, test.c
2131+
TableScan: test
2132+
"
2133+
)
2134+
}
2135+
2136+
#[test]
2137+
fn test_window_filter_arguments() -> Result<()> {
2138+
let table_scan = test_table_scan()?;
2139+
2140+
// CSE conservatively treats the arguments of a window function with a
2141+
// `FILTER` as conditionally evaluated, although the window executor
2142+
// evaluates them before it applies the filter today. The `PARTITION BY`
2143+
// expressions and the filter are evaluated for every input row.
2144+
let window_sum = |arg: Expr| {
2145+
Expr::from(WindowFunction::new(
2146+
WindowFunctionDefinition::AggregateUDF(sum_udaf()),
2147+
vec![arg],
2148+
))
2149+
.partition_by(vec![col("a") * col("b")])
2150+
.filter(col("c").gt(lit(0)))
2151+
.build()
2152+
};
2153+
let plan = LogicalPlanBuilder::from(table_scan)
2154+
.window(vec![
2155+
window_sum(col("a") + col("b"))?,
2156+
window_sum((col("a") + col("b")) * lit(2))?,
2157+
])?
2158+
.build()?;
2159+
2160+
assert_optimized_plan_equal!(
2161+
plan,
2162+
@ "
2163+
Projection: test.a, test.b, test.c, sum(test.a + test.b) FILTER (WHERE test.c > Int32(0)) PARTITION BY [test.a * test.b] ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING, sum(test.a + test.b * Int32(2)) FILTER (WHERE test.c > Int32(0)) PARTITION BY [test.a * test.b] ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
2164+
WindowAggr: windowExpr=[[sum(test.a + test.b) FILTER (WHERE __common_expr_2 AS test.c > Int32(0)) PARTITION BY [__common_expr_1 AS test.a * test.b] ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING AS sum(test.a + test.b) FILTER (WHERE test.c > Int32(0)) PARTITION BY [test.a * test.b] ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING, sum((test.a + test.b) * Int32(2)) FILTER (WHERE __common_expr_2 AS test.c > Int32(0)) PARTITION BY [__common_expr_1 AS test.a * test.b] ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING AS sum(test.a + test.b * Int32(2)) FILTER (WHERE test.c > Int32(0)) PARTITION BY [test.a * test.b] ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING]]
2165+
Projection: test.a * test.b AS __common_expr_1, test.c > Int32(0) AS __common_expr_2, test.a, test.b, test.c
2166+
TableScan: test
2167+
"
2168+
)
2169+
}
19512170
}

‎datafusion/sqllogictest/test_files/aggregates_simplify.slt‎

Lines changed: 3 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -226,13 +226,11 @@ query TT
226226
EXPLAIN SELECT SUM(column1 + 1) FILTER (WHERE column1 > 1), SUM(column1 + 1) FILTER (WHERE column1 > 0) FROM sum_simplify_t;
227227
----
228228
logical_plan
229-
01)Aggregate: groupBy=[[]], aggr=[[sum(__common_expr_1 AS sum_simplify_t.column1 + Int64(1)) FILTER (WHERE sum_simplify_t.column1 > Int64(1)), sum(__common_expr_1 AS sum_simplify_t.column1 + Int64(1)) FILTER (WHERE sum_simplify_t.column1 > Int64(0))]]
230-
02)--Projection: sum_simplify_t.column1 + Int64(1) AS __common_expr_1, sum_simplify_t.column1
231-
03)----TableScan: sum_simplify_t projection=[column1]
229+
01)Aggregate: groupBy=[[]], aggr=[[sum(sum_simplify_t.column1 + Int64(1)) FILTER (WHERE sum_simplify_t.column1 > Int64(1)), sum(sum_simplify_t.column1 + Int64(1)) FILTER (WHERE sum_simplify_t.column1 > Int64(0))]]
230+
02)--TableScan: sum_simplify_t projection=[column1]
232231
physical_plan
233232
01)AggregateExec: mode=Single, gby=[], aggr=[sum(sum_simplify_t.column1 + Int64(1)) FILTER (WHERE sum_simplify_t.column1 > Int64(1)), sum(sum_simplify_t.column1 + Int64(1)) FILTER (WHERE sum_simplify_t.column1 > Int64(0))]
234-
02)--ProjectionExec: expr=[column1@0 + 1 as __common_expr_1, column1@0 as column1]
235-
03)----DataSourceExec: partitions=1, partition_sizes=[1]
233+
02)--DataSourceExec: partitions=1, partition_sizes=[1]
236234

237235
# volatile aggregate arguments
238236
query B

0 commit comments

Comments
 (0)