Skip to content

Commit 5fada42

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 0a9f1dc commit 5fada42

2 files changed

Lines changed: 226 additions & 36 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 & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,7 @@ use datafusion_expr::{
4343
};
4444

4545
use crate::optimizer::ApplyOrder;
46+
use crate::projection_inliner::{DuplicationCost, ProjectionInliner};
4647
use crate::simplify_expressions::{reorder_predicates, simplify_predicates};
4748
use crate::utils::{
4849
ColumnReference, has_all_column_refs, is_restrict_null_predicate, schema_columns,
@@ -1388,28 +1389,36 @@ fn rewrite_projection(
13881389
predicates: Vec<Expr>,
13891390
mut projection: Projection,
13901391
) -> Result<(Transformed<LogicalPlan>, Vec<Expr>)> {
1391-
// Partition projection expressions into non-pushable vs pushable.
1392-
// Non-pushable expressions are volatile (must not be duplicated) or
1393-
// MoveTowardsLeafNodes (cheap expressions like get_field where re-inlining
1394-
// into a filter causes optimizer instability — ExtractLeafExpressions will
1395-
// undo the push-down, creating an infinite loop that runs until the
1396-
// iteration limit is hit).
1397-
let (non_pushable_map, pushable_map) = projection
1398-
.schema
1399-
.iter()
1400-
.zip(projection.expr.iter())
1401-
.map(|((qualifier, field), expr)| {
1402-
(qualified_name(qualifier, field.name()), unalias(expr))
1403-
})
1404-
.partition(|(_, value)| {
1405-
value.is_volatile()
1406-
|| value.placement() == ExpressionPlacement::MoveTowardsLeafNodes
1407-
});
1408-
1392+
let inliner = ProjectionInliner::new(&projection);
1393+
1394+
// A predicate is kept above the projection when it references:
1395+
// - a volatile definition. The projection still computes it, so a second
1396+
// evaluation below would see a different value.
1397+
// - an expensive definition that the predicates reference more than one
1398+
// time. Pushing would evaluate it more than one time, and
1399+
// `CommonSubexprEliminate` would create a projection for it again below
1400+
// the filter, so the two rules would never converge (issue #25329). A
1401+
// single reference is pushed: if the columns above still use the
1402+
// definition, that is the usual cost of a filter push-down.
1403+
// - a `MoveTowardsLeafNodes` definition (a cheap expression like
1404+
// `get_field`). Re-inlining such an expression into a filter causes
1405+
// optimizer instability: `ExtractLeafExpressions` undoes the push-down,
1406+
// which creates a loop that runs until the iteration limit is hit.
1407+
let no_other_consumers: [&Expr; 0] = [];
1408+
let pinned = inliner.pinned_for_known_consumers(
1409+
&predicates,
1410+
no_other_consumers,
1411+
DuplicationCost::Cheap,
1412+
);
14091413
let mut push_predicates = vec![];
14101414
let mut keep_predicates = vec![];
14111415
for expr in predicates {
1412-
if contain(&expr, &non_pushable_map) {
1416+
let references_leaf_expr = expr.column_refs().into_iter().any(|col| {
1417+
inliner.definition(col).is_some_and(|definition| {
1418+
definition.placement() == ExpressionPlacement::MoveTowardsLeafNodes
1419+
})
1420+
});
1421+
if references_leaf_expr || inliner.references_pinned(&expr, &pinned) {
14131422
keep_predicates.push(expr);
14141423
} else {
14151424
push_predicates.push(expr);
@@ -1420,7 +1429,7 @@ fn rewrite_projection(
14201429
// re-write all filters based on this projection
14211430
// E.g. in `Filter: b\n Projection: a > 1 as b`, we can swap them, but the filter must be "a > 1"
14221431
projection.input = Arc::new(LogicalPlan::Filter(Filter::new(
1423-
replace_cols_by_name(expr, &pushable_map)?,
1432+
inliner.substitute(expr)?,
14241433
projection.input,
14251434
)));
14261435

@@ -1489,14 +1498,6 @@ fn unalias(expr: &Expr) -> &Expr {
14891498
}
14901499
}
14911500

1492-
/// check whether the expression uses the columns in `check_map`.
1493-
fn contain<T>(e: &Expr, check_map: &HashMap<String, T>) -> bool {
1494-
e.exists(|expr| {
1495-
Ok(matches!(expr, Expr::Column(c) if check_map.contains_key(&c.flat_name())))
1496-
})
1497-
.unwrap()
1498-
}
1499-
15001501
fn with_filters(predicates: Vec<Expr>, plan: LogicalPlan) -> LogicalPlan {
15011502
if let Some(predicate) = conjunction(predicates) {
15021503
LogicalPlan::Filter(Filter::new(predicate, Arc::new(plan)))
@@ -1537,7 +1538,7 @@ mod tests {
15371538
use crate::assert_optimized_plan_eq_snapshot;
15381539
use crate::optimizer::Optimizer;
15391540
use crate::simplify_expressions::SimplifyExpressions;
1540-
use crate::test::udfs::leaf_udf_expr;
1541+
use crate::test::udfs::{PlacementTestUDF, get_field_like, leaf_udf_expr};
15411542
use crate::test::*;
15421543
use datafusion_expr::test::function_stub::sum;
15431544
use insta::assert_snapshot;
@@ -4546,6 +4547,90 @@ mod tests {
45464547
)
45474548
}
45484549

4550+
fn keep_in_place_udf(arg: Expr) -> Expr {
4551+
ScalarUDF::new_from_impl(
4552+
PlacementTestUDF::new().with_placement(ExpressionPlacement::KeepInPlace),
4553+
)
4554+
.call(vec![arg])
4555+
}
4556+
4557+
/// Issue #25329: `CommonSubexprEliminate` computes `c1` one time for
4558+
/// predicates that reference it twice. Pushing the predicates would compute
4559+
/// it twice, and CSE would then create the projection again below the
4560+
/// filter, so the two rules never converge.
4561+
#[test]
4562+
fn filter_with_repeated_expensive_reference_not_pushed_through_projection()
4563+
-> Result<()> {
4564+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
4565+
.project(vec![keep_in_place_udf(col("a")).alias("c1"), col("b")])?
4566+
.filter(
4567+
col("c1")
4568+
.is_not_null()
4569+
.and(get_field_like(col("c1"), "x").is_null())
4570+
.and(col("b").gt(lit(1))),
4571+
)?
4572+
.build()?;
4573+
4574+
assert_optimized_plan_equal!(
4575+
plan,
4576+
@r#"
4577+
Filter: c1 IS NOT NULL AND get_field_like(c1, Utf8("x")) IS NULL
4578+
Projection: keep_in_place_udf(test.a) AS c1, test.b
4579+
TableScan: test, full_filters=[test.b > Int32(1)]
4580+
"#
4581+
)
4582+
}
4583+
4584+
/// A single reference to an expensive definition is pushed, like any
4585+
/// other computed column of a projection.
4586+
#[test]
4587+
fn filter_with_single_expensive_reference_pushed_through_projection() -> Result<()> {
4588+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
4589+
.project(vec![keep_in_place_udf(col("a")).alias("c1"), col("b")])?
4590+
.filter(col("c1").is_not_null())?
4591+
.build()?;
4592+
4593+
assert_optimized_plan_equal!(
4594+
plan,
4595+
@r"
4596+
Projection: keep_in_place_udf(test.a) AS c1, test.b
4597+
TableScan: test, full_filters=[keep_in_place_udf(test.a) IS NOT NULL]
4598+
"
4599+
)
4600+
}
4601+
4602+
/// The shape of draft https://github.com/apache/datafusion/pull/25388:
4603+
/// a filter over a projection that reads an expensive column of the
4604+
/// projection below it. The narrow policy pushes `c1 IS NOT NULL`,
4605+
/// because the predicates reference `c1` one time. `c2 IS NULL` stays
4606+
/// above, because `c2` is a `MoveTowardsLeafNodes` definition.
4607+
#[test]
4608+
fn filter_not_pushed_through_nested_computed_projection() -> Result<()> {
4609+
let inner = LogicalPlanBuilder::from(test_table_scan()?)
4610+
.project(vec![keep_in_place_udf(col("a")).alias("c1"), col("b")])?
4611+
.build()?;
4612+
let outer = LogicalPlanBuilder::from(inner)
4613+
.project(vec![
4614+
get_field_like(col("c1"), "x").alias("c2"),
4615+
col("c1"),
4616+
col("b"),
4617+
])?
4618+
.build()?;
4619+
let plan = LogicalPlanBuilder::from(outer)
4620+
.filter(col("c1").is_not_null().and(col("c2").is_null()))?
4621+
.build()?;
4622+
4623+
assert_optimized_plan_equal!(
4624+
plan,
4625+
@r#"
4626+
Filter: c2 IS NULL
4627+
Projection: get_field_like(c1, Utf8("x")) AS c2, c1, test.b
4628+
Projection: keep_in_place_udf(test.a) AS c1, test.b
4629+
TableScan: test, full_filters=[keep_in_place_udf(test.a) IS NOT NULL]
4630+
"#
4631+
)
4632+
}
4633+
45494634
#[test]
45504635
fn filter_not_pushed_down_through_table_scan_with_fetch() -> Result<()> {
45514636
let scan = test_table_scan()?;

0 commit comments

Comments
 (0)