Skip to content

Commit 80096e0

Browse files
committed
perf: don't re-inline CSE'd expensive expressions in projection pushdown
Extend the projection-pushdown guard so it also declines to merge a projection into a file scan when the merge would duplicate a non-trivial expression (e.g. `power(a, 2)`, `a + b`, `c2 >= 2`) that CSE extracted into a shared intermediate projection. Without this the expression is re-inlined at every reference site and re-evaluated per row, undoing the deduplication. "Non-trivial" is decided by expression placement (`KeepInPlace`) — the same signal `try_collapse_projection_chain` uses — so leaf-pushable expressions (columns, `get_field`, `input_file_name`) still merge. References are counted with multiplicity (reused from the volatile guard), so an expression is blocked only when referenced more than once; volatile (correctness, apache#23220) and non-trivial (performance) share the same threshold.
1 parent a631cc0 commit 80096e0

2 files changed

Lines changed: 139 additions & 37 deletions

File tree

  • datafusion

‎datafusion/datasource/src/file_scan_config/mod.rs‎

Lines changed: 137 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -625,23 +625,29 @@ fn project_output_partitioning(
625625
}
626626
}
627627

628-
/// Returns `true` if merging `outer` into `inner` would duplicate a volatile
629-
/// expression; the caller should then decline the merge.
628+
/// Returns `true` if merging `outer` into `inner` would duplicate a volatile or
629+
/// non-trivial expression that CSE deduplicated; the caller should then decline
630+
/// the merge.
630631
///
631-
/// `inner` is the scan's current projection and `outer` the projection being
632-
/// pushed into it; merging substitutes each `inner` expression into every
633-
/// `outer` reference to it. If a volatile `inner` expression (e.g. `random()`,
634-
/// `uuid()`) is referenced more than once, that single value gets inlined at
635-
/// each site and re-evaluated independently, so references meant to share a
636-
/// "locked-in" value diverge. This is the volatility guard the physical
637-
/// `ProjectionPushdown` and `FilterPushdown` rules already apply (see
638-
/// `datafusion_physical_expr_common::physical_expr::is_volatile`).
632+
/// Merging substitutes each `inner` expression into every `outer` reference to
633+
/// it. Since the logical optimizer extracts a repeated expression into a single
634+
/// `inner` entry referenced by column, re-inlining it at more than one
635+
/// reference site undoes that deduplication. An `inner` expression referenced
636+
/// more than once is therefore blocked when it is either:
639637
///
640-
/// References are counted with multiplicity by walking each `outer` expression
641-
/// (as `try_collapse_projection_chain` does), so a self-duplicating expression
642-
/// such as `r + r` counts as two references. A volatile expression referenced
643-
/// exactly once has nothing to duplicate and is left to merge.
644-
fn would_duplicate_volatile_exprs(
638+
/// - **volatile** (e.g. `random()`) — evaluating it independently at each site
639+
/// makes references that should share one "locked-in" value diverge (the
640+
/// correctness guard the physical `ProjectionPushdown` and `FilterPushdown`
641+
/// rules also apply via
642+
/// `datafusion_physical_expr_common::physical_expr::is_volatile`); or
643+
/// - **not cheap to recompute** — its placement is not push-to-leaves
644+
/// (`KeepInPlace`: arithmetic, casts, most scalar functions). Leaf-pushable
645+
/// expressions (columns, `get_field`, `input_file_name`) still merge. This
646+
/// matches `try_collapse_projection_chain`.
647+
///
648+
/// References are counted with multiplicity, so `r + r` counts as two; an
649+
/// expression referenced exactly once has nothing to duplicate.
650+
fn would_duplicate_costly_exprs(
645651
inner: &ProjectionExprs,
646652
outer: &ProjectionExprs,
647653
) -> bool {
@@ -664,10 +670,10 @@ fn would_duplicate_volatile_exprs(
664670
.expect("infallible closure should not fail");
665671
}
666672

667-
ref_counts
668-
.iter()
669-
.enumerate()
670-
.any(|(idx, &count)| count > 1 && is_volatile(&inner_exprs[idx].expr))
673+
ref_counts.iter().enumerate().any(|(idx, &count)| {
674+
let expr = &inner_exprs[idx].expr;
675+
count > 1 && (is_volatile(expr) || !expr.placement().should_push_to_leaves())
676+
})
671677
}
672678

673679
impl DataSource for FileScanConfig {
@@ -957,11 +963,13 @@ impl DataSource for FileScanConfig {
957963
projection: &ProjectionExprs,
958964
) -> Result<Option<Arc<dyn DataSource>>> {
959965
// Don't merge a projection into the scan if it would inline a volatile
960-
// expression that the outer projection references, which would turn a
961-
// single "locked-in" value (e.g. `random()` aliased in a subquery) into
962-
// multiple independent evaluations. See #23220.
966+
// or expensive expression referenced more than once. For a volatile
967+
// expression (e.g. `random()` aliased in a subquery) this would turn a
968+
// single "locked-in" value into multiple independent evaluations (see
969+
// #23220); for an expensive scalar function it would undo CSE and
970+
// re-evaluate the expression at every reference site.
963971
if let Some(inner) = self.file_source.projection()
964-
&& would_duplicate_volatile_exprs(inner, projection)
972+
&& would_duplicate_costly_exprs(inner, projection)
965973
{
966974
return Ok(None);
967975
}
@@ -3395,6 +3403,45 @@ mod tests {
33953403
))
33963404
}
33973405

3406+
/// Helper: create a deterministic but expensive scalar-function
3407+
/// expression, e.g. `abs(<arg>)`.
3408+
fn make_udf_expr(args: Vec<Arc<dyn PhysicalExpr>>) -> Arc<dyn PhysicalExpr> {
3409+
use datafusion_common::config::ConfigOptions;
3410+
use datafusion_expr::ScalarUDF;
3411+
use datafusion_functions::math::abs::AbsFunc;
3412+
use datafusion_physical_expr::ScalarFunctionExpr;
3413+
3414+
Arc::new(ScalarFunctionExpr::new(
3415+
"abs",
3416+
Arc::new(ScalarUDF::from(AbsFunc::new())),
3417+
args,
3418+
Arc::new(Field::new("abs", DataType::Int32, false)),
3419+
Arc::new(ConfigOptions::default()),
3420+
))
3421+
}
3422+
3423+
/// Helper: create a cheap, leaf-pushable scalar function — struct field
3424+
/// access `get_field(s, 'x')`, whose placement is `MoveTowardsLeafNodes`
3425+
/// when the base is a column and the key is a literal.
3426+
fn make_leaf_pushable_expr() -> Arc<dyn PhysicalExpr> {
3427+
use datafusion_common::config::ConfigOptions;
3428+
use datafusion_expr::ScalarUDF;
3429+
use datafusion_functions::core::getfield::GetFieldFunc;
3430+
use datafusion_physical_expr::ScalarFunctionExpr;
3431+
use datafusion_physical_expr::expressions::Literal;
3432+
3433+
Arc::new(ScalarFunctionExpr::new(
3434+
"get_field",
3435+
Arc::new(ScalarUDF::from(GetFieldFunc::new())),
3436+
vec![
3437+
Arc::new(Column::new("s", 0)),
3438+
Arc::new(Literal::new(ScalarValue::Utf8(Some("x".to_string())))),
3439+
],
3440+
Arc::new(Field::new("x", DataType::Int32, true)),
3441+
Arc::new(ConfigOptions::default()),
3442+
))
3443+
}
3444+
33983445
/// Column-only inner projections always merge safely, even when
33993446
/// the outer projection references them multiple times.
34003447
#[test]
@@ -3411,16 +3458,16 @@ mod tests {
34113458
(Arc::new(Column::new("a", 0)), "y"),
34123459
]);
34133460

3414-
assert!(!would_duplicate_volatile_exprs(&inner, &outer));
3461+
assert!(!would_duplicate_costly_exprs(&inner, &outer));
34153462
}
34163463

3417-
/// Deterministic computed expressions (arithmetic) referenced multiple
3418-
/// times are allowed to merge — only volatile expressions are protected.
3464+
/// A non-trivial computed expression (arithmetic, `KeepInPlace`) referenced
3465+
/// multiple times blocks the merge — recomputing it per site is wasteful.
34193466
#[test]
3420-
fn test_would_duplicate_allows_deterministic_computed_multi_ref() {
3467+
fn test_would_duplicate_blocks_computed_multi_ref() {
34213468
let col_a: Arc<dyn PhysicalExpr> = Arc::new(Column::new("a", 0));
34223469
let col_b: Arc<dyn PhysicalExpr> = Arc::new(Column::new("b", 1));
3423-
// Inner: [a + b, b] (index 0 is deterministic computed)
3470+
// Inner: [a + b, b] (index 0 is a non-trivial computed expression)
34243471
let inner = make_projection(vec![
34253472
(
34263473
Arc::new(BinaryExpr::new(
@@ -3439,8 +3486,7 @@ mod tests {
34393486
(Arc::new(Column::new("sum", 0)), "y"),
34403487
]);
34413488

3442-
// Deterministic arithmetic → allow merge even though duplicated
3443-
assert!(!would_duplicate_volatile_exprs(&inner, &outer));
3489+
assert!(would_duplicate_costly_exprs(&inner, &outer));
34443490
}
34453491

34463492
/// A volatile expression the outer projection does not reference is
@@ -3455,7 +3501,7 @@ mod tests {
34553501
// Outer references only index 1 (the column), not the volatile expr
34563502
let outer = make_projection(vec![(Arc::new(Column::new("a", 1)), "a")]);
34573503

3458-
assert!(!would_duplicate_volatile_exprs(&inner, &outer));
3504+
assert!(!would_duplicate_costly_exprs(&inner, &outer));
34593505
}
34603506

34613507
/// A volatile expression referenced multiple times must block merge:
@@ -3472,7 +3518,7 @@ mod tests {
34723518
(Arc::new(Column::new("r", 0)), "y"),
34733519
]);
34743520

3475-
assert!(would_duplicate_volatile_exprs(&inner, &outer));
3521+
assert!(would_duplicate_costly_exprs(&inner, &outer));
34763522
}
34773523

34783524
/// A volatile expression referenced exactly once has nothing to duplicate,
@@ -3490,7 +3536,7 @@ mod tests {
34903536
(Arc::new(Column::new("a", 1)), "a"),
34913537
]);
34923538

3493-
assert!(!would_duplicate_volatile_exprs(&inner, &outer));
3539+
assert!(!would_duplicate_costly_exprs(&inner, &outer));
34943540
}
34953541

34963542
/// References are counted with multiplicity, so a single outer expression
@@ -3510,7 +3556,7 @@ mod tests {
35103556
"x",
35113557
)]);
35123558

3513-
assert!(would_duplicate_volatile_exprs(&inner, &outer));
3559+
assert!(would_duplicate_costly_exprs(&inner, &outer));
35143560
}
35153561

35163562
/// A volatile expression buried inside a larger expression (e.g.
@@ -3533,14 +3579,69 @@ mod tests {
35333579
(Arc::new(Column::new("expr", 0)), "y"),
35343580
]);
35353581

3536-
assert!(would_duplicate_volatile_exprs(&inner, &outer));
3582+
assert!(would_duplicate_costly_exprs(&inner, &outer));
35373583
}
35383584

35393585
/// Empty projections should not block merging.
35403586
#[test]
35413587
fn test_would_duplicate_empty_projections() {
35423588
let inner = make_projection(vec![]);
35433589
let outer = make_projection(vec![]);
3544-
assert!(!would_duplicate_volatile_exprs(&inner, &outer));
3590+
assert!(!would_duplicate_costly_exprs(&inner, &outer));
3591+
}
3592+
3593+
/// An expensive (scalar-function) expression referenced more than once
3594+
/// must block the merge to preserve CSE.
3595+
#[test]
3596+
fn test_would_duplicate_blocks_multi_ref_expensive() {
3597+
let col_a: Arc<dyn PhysicalExpr> = Arc::new(Column::new("a", 0));
3598+
// Inner: [abs(a)]
3599+
let inner = make_projection(vec![(make_udf_expr(vec![col_a]), "abs_a")]);
3600+
3601+
// Outer references index 0 twice
3602+
let outer = make_projection(vec![
3603+
(Arc::new(Column::new("abs_a", 0)), "x"),
3604+
(Arc::new(Column::new("abs_a", 0)), "y"),
3605+
]);
3606+
3607+
assert!(would_duplicate_costly_exprs(&inner, &outer));
3608+
}
3609+
3610+
/// An expensive expression referenced only once has nothing to duplicate,
3611+
/// so the merge is allowed.
3612+
#[test]
3613+
fn test_would_duplicate_allows_single_ref_expensive() {
3614+
let col_a: Arc<dyn PhysicalExpr> = Arc::new(Column::new("a", 0));
3615+
// Inner: [abs(a), a]
3616+
let inner = make_projection(vec![
3617+
(make_udf_expr(vec![Arc::clone(&col_a)]), "abs_a"),
3618+
(Arc::clone(&col_a), "a"),
3619+
]);
3620+
3621+
// Outer references each inner column once
3622+
let outer = make_projection(vec![
3623+
(Arc::new(Column::new("abs_a", 0)), "out"),
3624+
(Arc::new(Column::new("a", 1)), "a"),
3625+
]);
3626+
3627+
assert!(!would_duplicate_costly_exprs(&inner, &outer));
3628+
}
3629+
3630+
/// A cheap, leaf-pushable scalar function (placement
3631+
/// `MoveTowardsLeafNodes`, e.g. `get_field` / `input_file_name`) still
3632+
/// merges even when referenced multiple times — it is meant to be pushed
3633+
/// into the scan, so blocking would defeat that optimization.
3634+
#[test]
3635+
fn test_would_duplicate_allows_leaf_pushable_scalar_function() {
3636+
// Inner: [input_file_name()]
3637+
let inner = make_projection(vec![(make_leaf_pushable_expr(), "f")]);
3638+
3639+
// Outer references index 0 twice
3640+
let outer = make_projection(vec![
3641+
(Arc::new(Column::new("f", 0)), "x"),
3642+
(Arc::new(Column::new("f", 0)), "y"),
3643+
]);
3644+
3645+
assert!(!would_duplicate_costly_exprs(&inner, &outer));
35453646
}
35463647
}

‎datafusion/sqllogictest/test_files/window.slt‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6085,7 +6085,8 @@ physical_plan
60856085
03)----BoundedWindowAggExec: wdw=[sum(test.c2) FILTER (WHERE test.c2 >= Int64(2)) ORDER BY [test.c1 ASC NULLS LAST, test.c2 ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "sum(test.c2) FILTER (WHERE test.c2 >= Int64(2)) ORDER BY [test.c1 ASC NULLS LAST, test.c2 ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": nullable Int64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, sum(test.c2) FILTER (WHERE test.c2 >= Int64(2) AND test.c2 < Int64(4) AND test.c1 > Int64(0)) ORDER BY [test.c1 ASC NULLS LAST, test.c2 ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "sum(test.c2) FILTER (WHERE test.c2 >= Int64(2) AND test.c2 < Int64(4) AND test.c1 > Int64(0)) ORDER BY [test.c1 ASC NULLS LAST, test.c2 ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": nullable Int64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, count(test.c2) FILTER (WHERE test.c2 >= Int64(2)) ORDER BY [test.c1 ASC NULLS LAST, test.c2 ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "count(test.c2) FILTER (WHERE test.c2 >= Int64(2)) ORDER BY [test.c1 ASC NULLS LAST, test.c2 ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": Int64 }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, array_agg(test.c2) FILTER (WHERE test.c2 >= Int64(2)) ORDER BY [test.c1 ASC NULLS LAST, test.c2 ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "array_agg(test.c2) FILTER (WHERE test.c2 >= Int64(2)) ORDER BY [test.c1 ASC NULLS LAST, test.c2 ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": nullable List(Int64) }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, array_agg(test.c2) FILTER (WHERE test.c2 >= Int64(2) AND test.c2 < Int64(4) AND test.c1 > Int64(0)) ORDER BY [test.c1 ASC NULLS LAST, test.c2 ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "array_agg(test.c2) FILTER (WHERE test.c2 >= Int64(2) AND test.c2 < Int64(4) AND test.c1 > Int64(0)) ORDER BY [test.c1 ASC NULLS LAST, test.c2 ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": nullable List(Int64) }, frame: ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
60866086
04)------SortPreservingMergeExec: [c1@2 ASC NULLS LAST, c2@3 ASC NULLS LAST], fetch=5
60876087
05)--------SortExec: TopK(fetch=5), expr=[c1@2 ASC NULLS LAST, c2@3 ASC NULLS LAST], preserve_partitioning=[true]
6088-
06)----------DataSourceExec: file_groups={2 groups: [[WORKSPACE_ROOT/datafusion/core/tests/data/partitioned_csv/partition-0.csv, WORKSPACE_ROOT/datafusion/core/tests/data/partitioned_csv/partition-1.csv], [WORKSPACE_ROOT/datafusion/core/tests/data/partitioned_csv/partition-2.csv, WORKSPACE_ROOT/datafusion/core/tests/data/partitioned_csv/partition-3.csv]]}, projection=[c2@1 >= 2 as __common_expr_1, c2@1 >= 2 AND c2@1 < 4 AND c1@0 > 0 as __common_expr_2, c1, c2], file_type=csv, has_header=false
6088+
06)----------ProjectionExec: expr=[__common_expr_3@0 as __common_expr_1, __common_expr_3@0 AND c2@2 < 4 AND c1@1 > 0 as __common_expr_2, c1@1 as c1, c2@2 as c2]
6089+
07)------------DataSourceExec: file_groups={2 groups: [[WORKSPACE_ROOT/datafusion/core/tests/data/partitioned_csv/partition-0.csv, WORKSPACE_ROOT/datafusion/core/tests/data/partitioned_csv/partition-1.csv], [WORKSPACE_ROOT/datafusion/core/tests/data/partitioned_csv/partition-2.csv, WORKSPACE_ROOT/datafusion/core/tests/data/partitioned_csv/partition-3.csv]]}, projection=[c2@1 >= 2 as __common_expr_3, c1, c2], file_type=csv, has_header=false
60896090

60906091
# FILTER filters out some rows
60916092
query IIIII??

0 commit comments

Comments
 (0)