Skip to content

Commit e6eba50

Browse files
adriangbclaude
andcommitted
fix(optimizer): do not push a filter that duplicates an expensive projection column
`PushDownFilter` inlined every non-volatile definition of a projection into the pushed predicates. When the predicates reference an expensive definition more than one time, for example a column that `CommonSubexprEliminate` made for a struct-returning UDF, the push-down evaluates that expression more than one time. `CommonSubexprEliminate` then makes the projection again below the filter, so the two rules never converge. Route the rewrite through `ProjectionInliner` and delete the local `contain` helper and the placement partition. A predicate stays above the projection when it references a volatile definition, a `MoveTowardsLeafNodes` definition (as before), or an expensive definition that the predicates reference more than one time. A predicate with one reference is still pushed. Part of apache#25329 Co-Authored-By: Claude Fable 5.1 <[email protected]>
1 parent 7d09b99 commit e6eba50

2 files changed

Lines changed: 226 additions & 39 deletions

File tree

‎datafusion/optimizer/src/projection_inliner.rs‎

Lines changed: 112 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -32,14 +32,17 @@
3232
//! column that [`CommonSubexprEliminate`] created on purpose, so that an
3333
//! expensive expression is computed one time only.
3434
//!
35-
//! [`ProjectionInliner`] is the one place that makes this decision.
35+
//! [`ProjectionInliner`] is the one place that makes this decision. Rules call
36+
//! it instead of doing the substitution themselves.
3637
//!
3738
//! [`CommonSubexprEliminate`]: crate::common_subexpr_eliminate::CommonSubexprEliminate
3839
3940
use std::collections::{HashMap, HashSet};
4041

41-
use datafusion_common::Column;
42-
use datafusion_common::tree_node::{TreeNode, TreeNodeRecursion};
42+
use datafusion_common::tree_node::{
43+
Transformed, TransformedResult, TreeNode, TreeNodeRecursion,
44+
};
45+
use datafusion_common::{Column, Result};
4346
use datafusion_expr::{Expr, ExpressionPlacement, Projection};
4447

4548
/// The cost of one more evaluation of an expression.
@@ -128,9 +131,9 @@ impl PinnedDefinitions {
128131
}
129132
}
130133

131-
/// Decides if the column references of expressions over the output of a
132-
/// projection can be replaced with their definitions, without evaluating a
133-
/// definition too many times.
134+
/// Rewrites expressions over the output of a projection into expressions over
135+
/// its input, and decides if that is possible without evaluating a definition
136+
/// too many times.
134137
///
135138
/// The rule is: after the rewrite, a definition that is evaluated more than
136139
/// one time must have a [`DuplicationCost`] of at most the `max_cost` that the
@@ -207,6 +210,32 @@ impl<'a> ProjectionInliner<'a> {
207210
inlined: impl IntoIterator<Item = &'i Expr>,
208211
others: impl IntoIterator<Item = &'o Expr>,
209212
max_cost: DuplicationCost,
213+
) -> PinnedDefinitions {
214+
self.pinned_impl(inlined, others, max_cost, false)
215+
}
216+
217+
/// Returns [`Self::pinned`], and also pins every
218+
/// [`DuplicationCost::Forbidden`] definition that `inlined` references.
219+
///
220+
/// Use this when the projection can stay in the plan for consumers that
221+
/// the caller can not see. A copy of a forbidden definition would then
222+
/// be evaluated independently of the original, and change the query
223+
/// result.
224+
pub(crate) fn pinned_for_known_consumers<'i, 'o>(
225+
&self,
226+
inlined: impl IntoIterator<Item = &'i Expr>,
227+
others: impl IntoIterator<Item = &'o Expr>,
228+
max_cost: DuplicationCost,
229+
) -> PinnedDefinitions {
230+
self.pinned_impl(inlined, others, max_cost, true)
231+
}
232+
233+
fn pinned_impl<'i, 'o>(
234+
&self,
235+
inlined: impl IntoIterator<Item = &'i Expr>,
236+
others: impl IntoIterator<Item = &'o Expr>,
237+
max_cost: DuplicationCost,
238+
pin_forbidden: bool,
210239
) -> PinnedDefinitions {
211240
debug_assert!(
212241
max_cost < DuplicationCost::Forbidden,
@@ -220,14 +249,51 @@ impl<'a> ProjectionInliner<'a> {
220249
let pinned = inlined_references
221250
.into_iter()
222251
.filter(|(idx, count)| {
252+
let cost = self.definitions[*idx].1;
223253
let evaluations = count + usize::from(other_references.contains_key(idx));
224-
evaluations > 1 && self.definitions[*idx].1 > max_cost
254+
(pin_forbidden && cost == DuplicationCost::Forbidden)
255+
|| (evaluations > 1 && cost > max_cost)
225256
})
226257
.map(|(idx, _)| idx)
227258
.collect();
228259
PinnedDefinitions(pinned)
229260
}
230261

262+
/// Returns `true` if `expr` references a definition in `pinned`.
263+
pub(crate) fn references_pinned(
264+
&self,
265+
expr: &Expr,
266+
pinned: &PinnedDefinitions,
267+
) -> bool {
268+
!pinned.is_empty()
269+
&& expr
270+
.exists(|e| {
271+
Ok(matches!(e, Expr::Column(col)
272+
if self.index_of(col).is_some_and(|idx| pinned.0.contains(&idx))))
273+
})
274+
.expect("exists closure is infallible")
275+
}
276+
277+
/// Returns the definition of `column`, without its top-level alias.
278+
pub(crate) fn definition(&self, column: &Column) -> Option<&'a Expr> {
279+
self.index_of(column).map(|idx| self.definitions[idx].0)
280+
}
281+
282+
/// Replaces each column reference in `expr` with its definition, without a
283+
/// cost check. Callers must check [`Self::pinned`] first.
284+
pub(crate) fn substitute(&self, expr: Expr) -> Result<Expr> {
285+
expr.transform_up(|e| {
286+
if let Expr::Column(col) = &e
287+
&& let Some(definition) = self.definition(col)
288+
{
289+
Ok(Transformed::yes(definition.clone()))
290+
} else {
291+
Ok(Transformed::no(e))
292+
}
293+
})
294+
.data()
295+
}
296+
231297
/// Counts the references to each definition in `exprs`.
232298
fn count_references<'e>(
233299
&self,
@@ -388,5 +454,44 @@ mod tests {
388454
.is_empty()
389455
);
390456
assert!(!inliner.pinned([&col("r")], [&col("r")], max).is_empty());
457+
// Without all the consumers, a single reference is pinned as well.
458+
assert!(
459+
!inliner
460+
.pinned_for_known_consumers([&col("r")], no_others, max)
461+
.is_empty()
462+
);
463+
}
464+
465+
#[test]
466+
fn substitute_and_references_pinned() -> Result<()> {
467+
let p = projection(vec![
468+
col("a"),
469+
expensive(col("c")).alias("exp"),
470+
(col("b") + lit(1)).alias("cheap"),
471+
]);
472+
let inliner = ProjectionInliner::new(&p);
473+
let no_others: [&Expr; 0] = [];
474+
475+
let twice = col("exp")
476+
.is_not_null()
477+
.and(get_field_like(col("exp"), "x"));
478+
let other = col("cheap").gt(col("a"));
479+
let pinned = inliner.pinned_for_known_consumers(
480+
[&twice, &other],
481+
no_others,
482+
DuplicationCost::Cheap,
483+
);
484+
assert!(inliner.references_pinned(&twice, &pinned));
485+
assert!(!inliner.references_pinned(&other, &pinned));
486+
487+
assert_eq!(
488+
inliner.definition(&Column::from_name("exp")),
489+
Some(&expensive(col("test.c")))
490+
);
491+
assert_eq!(
492+
inliner.substitute(other)?,
493+
(col("test.b") + lit(1)).gt(col("test.a"))
494+
);
495+
Ok(())
391496
}
392497
}

‎datafusion/optimizer/src/push_down_filter.rs‎

Lines changed: 114 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -56,6 +56,7 @@ use datafusion_expr::{
5656

5757
use crate::extract_leaf_expressions::is_pure_extraction_projection;
5858
use crate::optimizer::ApplyOrder;
59+
use crate::projection_inliner::{DuplicationCost, ProjectionInliner};
5960
use crate::simplify_expressions::{reorder_predicates, simplify_predicates};
6061
use crate::utils::{
6162
ColumnReference, has_all_column_refs, is_restrict_null_predicate, schema_columns,
@@ -1544,33 +1545,36 @@ fn rewrite_projection(
15441545
));
15451546
}
15461547

1547-
// Partition projection expressions into non-pushable vs pushable.
1548-
// Non-pushable expressions are volatile (must not be duplicated) or
1549-
// MoveTowardsLeafNodes (cheap expressions like get_field where re-inlining
1550-
// into a filter causes optimizer instability — ExtractLeafExpressions will
1551-
// undo the push-down, creating an infinite loop that runs until the
1552-
// iteration limit is hit).
1553-
//
1554-
// Keyed by the output column rather than its flat name, for the reason
1555-
// given on `replace_cols_by_column`. `EliminateGroupByConstant` can leave a
1556-
// projection that outputs both `t.a` and `CAST(t.a AS ...)` under that one
1557-
// name.
1558-
let (non_pushable_map, pushable_map): (HashMap<_, _>, HashMap<_, _>) = projection
1559-
.schema
1560-
.iter()
1561-
.zip(projection.expr.iter())
1562-
.map(|((qualifier, field), expr)| {
1563-
(Column::new(qualifier.cloned(), field.name()), unalias(expr))
1564-
})
1565-
.partition(|(_, value)| {
1566-
value.is_volatile()
1567-
|| value.placement() == ExpressionPlacement::MoveTowardsLeafNodes
1568-
});
1569-
1548+
let inliner = ProjectionInliner::new(&projection);
1549+
1550+
// A predicate is kept above the projection when it references:
1551+
// - a volatile definition. The projection still computes it, so a second
1552+
// evaluation below would see a different value.
1553+
// - an expensive definition that the predicates reference more than one
1554+
// time. Pushing would evaluate it more than one time, and
1555+
// `CommonSubexprEliminate` would create a projection for it again below
1556+
// the filter, so the two rules would never converge (issue #25329). A
1557+
// single reference is pushed: if the columns above still use the
1558+
// definition, that is the usual cost of a filter push-down.
1559+
// - a `MoveTowardsLeafNodes` definition (a cheap expression like
1560+
// `get_field`). Re-inlining such an expression into a filter causes
1561+
// optimizer instability: `ExtractLeafExpressions` undoes the push-down,
1562+
// which creates a loop that runs until the iteration limit is hit.
1563+
let no_other_consumers: [&Expr; 0] = [];
1564+
let pinned = inliner.pinned_for_known_consumers(
1565+
&predicates,
1566+
no_other_consumers,
1567+
DuplicationCost::Cheap,
1568+
);
15701569
let mut push_predicates = vec![];
15711570
let mut keep_predicates = vec![];
15721571
for expr in predicates {
1573-
if contains_column(&expr, &non_pushable_map) {
1572+
let references_leaf_expr = expr.column_refs().into_iter().any(|col| {
1573+
inliner.definition(col).is_some_and(|definition| {
1574+
definition.placement() == ExpressionPlacement::MoveTowardsLeafNodes
1575+
})
1576+
});
1577+
if references_leaf_expr || inliner.references_pinned(&expr, &pinned) {
15741578
keep_predicates.push(expr);
15751579
} else {
15761580
push_predicates.push(expr);
@@ -1581,7 +1585,7 @@ fn rewrite_projection(
15811585
// re-write all filters based on this projection
15821586
// E.g. in `Filter: b\n Projection: a > 1 as b`, we can swap them, but the filter must be "a > 1"
15831587
projection.input = Arc::new(LogicalPlan::Filter(Filter::new(
1584-
replace_cols_by_column(expr, &pushable_map)?,
1588+
inliner.substitute(expr)?,
15851589
projection.input,
15861590
)));
15871591

@@ -1672,12 +1676,6 @@ fn unalias(expr: &Expr) -> &Expr {
16721676
}
16731677
}
16741678

1675-
/// check whether the expression uses the columns in `check_map`.
1676-
fn contains_column<T>(e: &Expr, check_map: &HashMap<Column, T>) -> bool {
1677-
e.exists(|expr| Ok(matches!(expr, Expr::Column(c) if check_map.contains_key(c))))
1678-
.unwrap()
1679-
}
1680-
16811679
fn with_filters(predicates: Vec<Expr>, plan: LogicalPlan) -> LogicalPlan {
16821680
if let Some(predicate) = conjunction(predicates) {
16831681
LogicalPlan::Filter(Filter::new(predicate, Arc::new(plan)))
@@ -1767,7 +1765,7 @@ mod tests {
17671765
use crate::assert_optimized_plan_eq_snapshot;
17681766
use crate::optimizer::Optimizer;
17691767
use crate::simplify_expressions::SimplifyExpressions;
1770-
use crate::test::udfs::leaf_udf_expr;
1768+
use crate::test::udfs::{PlacementTestUDF, get_field_like, leaf_udf_expr};
17711769
use crate::test::*;
17721770
use datafusion_expr::test::function_stub::{count, sum};
17731771
use insta::assert_snapshot;
@@ -4959,6 +4957,90 @@ mod tests {
49594957
)
49604958
}
49614959

4960+
fn keep_in_place_udf(arg: Expr) -> Expr {
4961+
ScalarUDF::new_from_impl(
4962+
PlacementTestUDF::new().with_placement(ExpressionPlacement::KeepInPlace),
4963+
)
4964+
.call(vec![arg])
4965+
}
4966+
4967+
/// Issue #25329: `CommonSubexprEliminate` computes `c1` one time for
4968+
/// predicates that reference it twice. Pushing the predicates would compute
4969+
/// it twice, and CSE would then create the projection again below the
4970+
/// filter, so the two rules never converge.
4971+
#[test]
4972+
fn filter_with_repeated_expensive_reference_not_pushed_through_projection()
4973+
-> Result<()> {
4974+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
4975+
.project(vec![keep_in_place_udf(col("a")).alias("c1"), col("b")])?
4976+
.filter(
4977+
col("c1")
4978+
.is_not_null()
4979+
.and(get_field_like(col("c1"), "x").is_null())
4980+
.and(col("b").gt(lit(1))),
4981+
)?
4982+
.build()?;
4983+
4984+
assert_optimized_plan_equal!(
4985+
plan,
4986+
@r#"
4987+
Filter: c1 IS NOT NULL AND get_field_like(c1, Utf8("x")) IS NULL
4988+
Projection: keep_in_place_udf(test.a) AS c1, test.b
4989+
TableScan: test, full_filters=[test.b > Int32(1)]
4990+
"#
4991+
)
4992+
}
4993+
4994+
/// A single reference to an expensive definition is pushed, like any
4995+
/// other computed column of a projection.
4996+
#[test]
4997+
fn filter_with_single_expensive_reference_pushed_through_projection() -> Result<()> {
4998+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
4999+
.project(vec![keep_in_place_udf(col("a")).alias("c1"), col("b")])?
5000+
.filter(col("c1").is_not_null())?
5001+
.build()?;
5002+
5003+
assert_optimized_plan_equal!(
5004+
plan,
5005+
@r"
5006+
Projection: keep_in_place_udf(test.a) AS c1, test.b
5007+
TableScan: test, full_filters=[keep_in_place_udf(test.a) IS NOT NULL]
5008+
"
5009+
)
5010+
}
5011+
5012+
/// The shape of draft https://github.com/apache/datafusion/pull/25388:
5013+
/// a filter over a projection that reads an expensive column of the
5014+
/// projection below it. The narrow policy pushes `c1 IS NOT NULL`,
5015+
/// because the predicates reference `c1` one time. `c2 IS NULL` stays
5016+
/// above, because `c2` is a `MoveTowardsLeafNodes` definition.
5017+
#[test]
5018+
fn filter_not_pushed_through_nested_computed_projection() -> Result<()> {
5019+
let inner = LogicalPlanBuilder::from(test_table_scan()?)
5020+
.project(vec![keep_in_place_udf(col("a")).alias("c1"), col("b")])?
5021+
.build()?;
5022+
let outer = LogicalPlanBuilder::from(inner)
5023+
.project(vec![
5024+
get_field_like(col("c1"), "x").alias("c2"),
5025+
col("c1"),
5026+
col("b"),
5027+
])?
5028+
.build()?;
5029+
let plan = LogicalPlanBuilder::from(outer)
5030+
.filter(col("c1").is_not_null().and(col("c2").is_null()))?
5031+
.build()?;
5032+
5033+
assert_optimized_plan_equal!(
5034+
plan,
5035+
@r#"
5036+
Filter: c2 IS NULL
5037+
Projection: get_field_like(c1, Utf8("x")) AS c2, c1, test.b
5038+
Projection: keep_in_place_udf(test.a) AS c1, test.b
5039+
TableScan: test, full_filters=[keep_in_place_udf(test.a) IS NOT NULL]
5040+
"#
5041+
)
5042+
}
5043+
49625044
#[test]
49635045
fn filter_not_pushed_down_through_table_scan_with_fetch() -> Result<()> {
49645046
let scan = test_table_scan()?;

0 commit comments

Comments
 (0)