Skip to content

Commit d5eb246

Browse files
tohuya6Omega359
authored andcommitted
fix: evaluate struct-returning UDFs once across repeated field accesses (apache#23691)
## Which issue does this PR close? - Closes apache#23655. ## Rationale for this change `SELECT f(c)['a'], f(c)['b']`, where `f` is a struct-returning UDF, evaluates `f(c)` twice in the physical `ProjectionExec` — once per `get_field` — although the two calls are identical. `CommonSubexprEliminate` already hoists the shared `f(c)` into a `__common_expr_N` column so it runs once. [`PushDownLeafProjections`](https://github.com/apache/datafusion/blob/main/datafusion/optimizer/src/extract_leaf_expressions.rs) then undoes that, one pass at a time: - After CSE, each field access reads its base from the hoist column, so `get_field`'s placement flips to `MoveTowardsLeafNodes` and the pass extracts it. - Merging the extraction into the hoist projection inlines that column's definition back into every access (via `build_projection_replace_map`), re-duplicating the `KeepInPlace` UDF. - `optimize_projections` drops the now-unused hoist column, and the two passes oscillate pass after pass — settling on a double evaluation. This is the instability the `is_ignored` note in `common_subexpr_eliminate` already warns about. ## What changes are included in this PR? Adds a guard `merge_would_duplicate_kept_expr` and calls it from `split_and_push_projection`, which now bails out — leaving the projection untouched — when merging the extractions into the input projection would inline a `KeepInPlace` definition that more than one extraction pair references. This mirrors the existing `optimize_projections` merge guard (apache#8296): a compute-once expression referenced more than once is kept in place instead of duplicated. With the guard, CSE's hoist survives, `optimize_projections` keeps it, and the pipeline converges to a single evaluation: Before: ```text Projection: get_field(f(c), 'a'), get_field(f(c), 'b') -- f(c) twice TableScan ``` After: ```text Projection: get_field(__common_expr_1, 'a'), get_field(__common_expr_1, 'b') Projection: f(c) AS __common_expr_1 -- f(c) once TableScan ``` ## Are these changes tested? Yes. - `test_struct_returning_udf_evaluated_once` (in `extract_leaf_expressions.rs`) runs the four interacting rules — CSE → extraction → pushdown → projection pruning — and asserts no field access wraps a fresh UDF call, plus an `insta` snapshot of the single-eval plan. It runs with the default pass budget, so any residual oscillation would surface as a double evaluation. - `get_field_like` — a small test UDF added to `test/udfs.rs` — reproduces `GetFieldFunc`'s conditional placement (`MoveTowardsLeafNodes` only when the base is pushable and the keys are literals). This lets the optimizer crate model struct-field access without depending on `datafusion-functions`, which it intentionally does not. `cargo fmt --all` and `cargo clippy --all-targets --all-features -- -D warnings` are clean. ## Are there any user-facing changes? Yes, but only in the sense that a redundantly-evaluated path becomes single-evaluation. No API or query-result changes: affected plans evaluate a struct-returning UDF once instead of once per field access, a saving that scales with the number of distinct field accesses on the same UDF. --------- Co-authored-by: tohuya6 <[email protected]>
1 parent b163e82 commit d5eb246

2 files changed

Lines changed: 233 additions & 2 deletions

File tree

‎datafusion/optimizer/src/extract_leaf_expressions.rs‎

Lines changed: 169 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -837,6 +837,66 @@ fn passthrough_column(expr: &Expr) -> Option<&Column> {
837837
}
838838
}
839839

840+
/// Returns `true` if merging the extracted `pairs` (and the pass-through
841+
/// `columns_needed`) into `child` would inline a `KeepInPlace` definition into
842+
/// more than one reference site — e.g. a struct-returning UDF `f(c)` behind both
843+
/// `f(c)['a']` and `f(c)['b']`, or behind `f(c)['a']` and a bare `f(c)`.
844+
///
845+
/// `CommonSubexprEliminate` hoists such an expression into a shared column so it
846+
/// runs once; [`build_extraction_projection_impl`] then resolves that column
847+
/// back to its definition and re-duplicates it. Mirrors the
848+
/// `optimize_projections` merge guard (#8296): a compute-once expression used
849+
/// more than once stays in place.
850+
fn merge_would_duplicate_kept_expr(
851+
pairs: &[(Expr, String)],
852+
columns_needed: &IndexSet<Column>,
853+
child: &Projection,
854+
) -> bool {
855+
// Columns whose `KeepInPlace` definition must stay put; inlining one would
856+
// duplicate a compute-once expression. Plain columns, pushable exprs, and
857+
// literals are all cheap to duplicate, so only `KeepInPlace` counts.
858+
let kept_columns: std::collections::HashSet<String> = child
859+
.schema
860+
.iter()
861+
.zip(child.expr.iter())
862+
.filter_map(|((qualifier, field), expr)| {
863+
if matches!(expr.placement(), ExpressionPlacement::KeepInPlace) {
864+
Some(Column::from((qualifier, field)).flat_name())
865+
} else {
866+
None
867+
}
868+
})
869+
.collect();
870+
if kept_columns.is_empty() {
871+
return false;
872+
}
873+
874+
// Count every site that references a kept column. A pair that references the
875+
// same kept column twice still inlines one copy, so count each pair at most
876+
// once per column.
877+
let mut usage: HashMap<String, usize> = HashMap::new();
878+
for (expr, _alias) in pairs {
879+
let mut seen: std::collections::HashSet<String> =
880+
std::collections::HashSet::new();
881+
for col in expr.column_refs() {
882+
let name = col.flat_name();
883+
if kept_columns.contains(&name) && seen.insert(name.clone()) {
884+
*usage.entry(name).or_insert(0) += 1;
885+
}
886+
}
887+
}
888+
// Pass-through / pre-existing-alias inputs are additional reference sites:
889+
// a bare `f(c)` alongside `f(c)['a']` also pins the compute-once column, so
890+
// counting only `pairs` under-counted and re-duplicated it (#23655).
891+
for col in columns_needed {
892+
let name = col.flat_name();
893+
if kept_columns.contains(&name) {
894+
*usage.entry(name).or_insert(0) += 1;
895+
}
896+
}
897+
usage.values().any(|&count| count > 1)
898+
}
899+
840900
/// Splits a projection into extractable pieces, pushes them towards leaf
841901
/// nodes, and adds a recovery projection if needed.
842902
///
@@ -990,6 +1050,14 @@ fn split_and_push_projection(
9901050
return Ok(None);
9911051
}
9921052

1053+
// Merging here would re-inline an expression `CommonSubexprEliminate` hoisted
1054+
// to run once, undoing it (issue #23655); leave the projection in place.
1055+
if let LogicalPlan::Projection(child) = input.as_ref()
1056+
&& merge_would_duplicate_kept_expr(&extraction_pairs, columns_needed, child)
1057+
{
1058+
return Ok(None);
1059+
}
1060+
9931061
// ── Phase 2: Push down ──────────────────────────────────────────────
9941062
let proj_input = Arc::clone(&proj.input);
9951063
let pushed = push_extraction_pairs(
@@ -1346,8 +1414,9 @@ fn try_push_into_inputs(
13461414
mod tests {
13471415

13481416
use super::*;
1417+
use crate::common_subexpr_eliminate::CommonSubexprEliminate;
13491418
use crate::optimize_projections::OptimizeProjections;
1350-
use crate::test::udfs::PlacementTestUDF;
1419+
use crate::test::udfs::{PlacementTestUDF, get_field_like};
13511420
use crate::test::*;
13521421
use crate::{Optimizer, OptimizerContext};
13531422
use datafusion_expr::expr::ScalarFunction;
@@ -3431,6 +3500,105 @@ mod tests {
34313500
alias_generator.next(EXTRACTED_EXPR_PREFIX),
34323501
"__datafusion_extracted_8"
34333502
);
3503+
3504+
Ok(())
3505+
}
3506+
3507+
/// Regression test for issue #23655: `f(c)['a'], f(c)['b']` on a
3508+
/// struct-returning UDF must evaluate `f(c)` once, not once per field access.
3509+
///
3510+
/// `keep_in_place_udf` / `get_field_like` model `f(c)` and `f(c)[key]` — the
3511+
/// crate can't depend on the real `get_field` (see [`get_field_like`]).
3512+
/// Without the guard, `PushDownLeafProjections` re-inlines the shared UDF that
3513+
/// `CommonSubexprEliminate` hoisted and the passes oscillate to a double
3514+
/// evaluation.
3515+
#[test]
3516+
fn test_struct_returning_udf_evaluated_once() -> Result<()> {
3517+
let udf = ScalarUDF::new_from_impl(
3518+
PlacementTestUDF::new().with_placement(ExpressionPlacement::KeepInPlace),
3519+
);
3520+
let f_c = udf.call(vec![col("c")]);
3521+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
3522+
.project(vec![
3523+
get_field_like(f_c.clone(), "a"),
3524+
get_field_like(f_c, "b"),
3525+
])?
3526+
.build()?;
3527+
3528+
// The full four-rule interaction, default pass budget so any oscillation
3529+
// would surface here as a double evaluation.
3530+
let ctx = OptimizerContext::new();
3531+
let optimizer = Optimizer::with_rules(vec![
3532+
Arc::new(CommonSubexprEliminate::new()),
3533+
Arc::new(ExtractLeafExpressions::new()),
3534+
Arc::new(PushDownLeafProjections::new()),
3535+
Arc::new(OptimizeProjections::new()),
3536+
]);
3537+
let optimized = optimizer.optimize(plan, &ctx, |_, _| {})?;
3538+
3539+
// Every field access reads the UDF back through `__common_expr_1`; none
3540+
// wraps a fresh `keep_in_place_udf(...)` call. Asserted explicitly so a
3541+
// careless snapshot re-accept can't quietly restore the double evaluation.
3542+
let formatted = format!("{optimized}");
3543+
assert_eq!(
3544+
formatted
3545+
.matches("get_field_like(keep_in_place_udf")
3546+
.count(),
3547+
0,
3548+
"struct-returning UDF must not be re-evaluated inside a field access; got:\n{formatted}"
3549+
);
3550+
3551+
insta::assert_snapshot!(formatted, @r#"
3552+
Projection: get_field_like(__common_expr_1 AS keep_in_place_udf(test.c), Utf8("a")), get_field_like(__common_expr_1 AS keep_in_place_udf(test.c), Utf8("b"))
3553+
Projection: keep_in_place_udf(test.c) AS __common_expr_1
3554+
TableScan: test projection=[c]
3555+
"#);
3556+
3557+
Ok(())
3558+
}
3559+
3560+
#[test]
3561+
fn test_struct_returning_udf_evaluated_once_with_bare_reference() -> Result<()> {
3562+
// Regression for the `SELECT f(c)['a'], f(c)` shape: the struct UDF is
3563+
// referenced once through a field access and once as a bare value. The
3564+
// bare reference is tracked in `columns_needed`, not `extraction_pairs`,
3565+
// so a guard that counted only pairs would re-inline `f(c)` and evaluate
3566+
// it twice (#23655).
3567+
let udf = ScalarUDF::new_from_impl(
3568+
PlacementTestUDF::new().with_placement(ExpressionPlacement::KeepInPlace),
3569+
);
3570+
let f_c = udf.call(vec![col("c")]);
3571+
let plan = LogicalPlanBuilder::from(test_table_scan()?)
3572+
.project(vec![get_field_like(f_c.clone(), "a"), f_c])?
3573+
.build()?;
3574+
3575+
let ctx = OptimizerContext::new();
3576+
let optimizer = Optimizer::with_rules(vec![
3577+
Arc::new(CommonSubexprEliminate::new()),
3578+
Arc::new(ExtractLeafExpressions::new()),
3579+
Arc::new(PushDownLeafProjections::new()),
3580+
Arc::new(OptimizeProjections::new()),
3581+
]);
3582+
let optimized = optimizer.optimize(plan, &ctx, |_, _| {})?;
3583+
3584+
// The field access must read the UDF back through `__common_expr_1`, not
3585+
// wrap a fresh `keep_in_place_udf(...)` call. Asserted explicitly so a
3586+
// careless snapshot re-accept can't quietly restore the double evaluation.
3587+
let formatted = format!("{optimized}");
3588+
assert_eq!(
3589+
formatted
3590+
.matches("get_field_like(keep_in_place_udf")
3591+
.count(),
3592+
0,
3593+
"struct-returning UDF must not be re-evaluated inside a field access; got:\n{formatted}"
3594+
);
3595+
3596+
insta::assert_snapshot!(formatted, @r#"
3597+
Projection: get_field_like(__common_expr_1 AS keep_in_place_udf(test.c), Utf8("a")), __common_expr_1 AS keep_in_place_udf(test.c)
3598+
Projection: keep_in_place_udf(test.c) AS __common_expr_1
3599+
TableScan: test projection=[c]
3600+
"#);
3601+
34343602
Ok(())
34353603
}
34363604
}

‎datafusion/optimizer/src/test/udfs.rs‎

Lines changed: 64 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,7 @@ use arrow::datatypes::DataType;
1919
use datafusion_common::Result;
2020
use datafusion_expr::{
2121
ColumnarValue, Expr, ExpressionPlacement, ScalarFunctionArgs, ScalarUDF,
22-
ScalarUDFImpl, Signature, TypeSignature, Volatility,
22+
ScalarUDFImpl, Signature, TypeSignature, Volatility, lit,
2323
};
2424

2525
/// A configurable test UDF for optimizer tests.
@@ -103,3 +103,66 @@ pub fn leaf_udf_expr(arg: Expr) -> Expr {
103103
);
104104
udf.call(vec![arg])
105105
}
106+
107+
/// A `get_field`-like test UDF for modeling struct-field access (`f(c)['a']`),
108+
/// so tests need not depend on `datafusion-functions` (which this crate avoids —
109+
/// see its `Cargo.toml`).
110+
///
111+
/// Placement mirrors `GetFieldFunc`: `MoveTowardsLeafNodes` when the base is
112+
/// pushable and the keys are literals, else `KeepInPlace`. That flip drives the
113+
/// issue #23655 pushdown interaction: the access is `KeepInPlace` until
114+
/// `CommonSubexprEliminate` hoists the UDF into a column, then becomes pushable.
115+
#[derive(Debug, PartialEq, Eq, Hash)]
116+
pub struct GetFieldLikeUDF {
117+
signature: Signature,
118+
}
119+
120+
impl Default for GetFieldLikeUDF {
121+
fn default() -> Self {
122+
Self::new()
123+
}
124+
}
125+
126+
impl GetFieldLikeUDF {
127+
pub fn new() -> Self {
128+
Self {
129+
signature: Signature::new(TypeSignature::Any(2), Volatility::Immutable),
130+
}
131+
}
132+
}
133+
134+
impl ScalarUDFImpl for GetFieldLikeUDF {
135+
fn name(&self) -> &str {
136+
"get_field_like"
137+
}
138+
fn signature(&self) -> &Signature {
139+
&self.signature
140+
}
141+
fn return_type(&self, _arg_types: &[DataType]) -> Result<DataType> {
142+
Ok(DataType::UInt32)
143+
}
144+
fn invoke_with_args(&self, _args: ScalarFunctionArgs) -> Result<ColumnarValue> {
145+
panic!("GetFieldLikeUDF: not intended for execution")
146+
}
147+
fn placement(&self, args: &[ExpressionPlacement]) -> ExpressionPlacement {
148+
// Mirror `GetFieldFunc`: cheap to push down only when the base is a
149+
// column (or already pushable) and every field key is a literal.
150+
match args.first() {
151+
Some(
152+
ExpressionPlacement::Column | ExpressionPlacement::MoveTowardsLeafNodes,
153+
) if args[1..]
154+
.iter()
155+
.all(|p| matches!(p, ExpressionPlacement::Literal)) =>
156+
{
157+
ExpressionPlacement::MoveTowardsLeafNodes
158+
}
159+
_ => ExpressionPlacement::KeepInPlace,
160+
}
161+
}
162+
}
163+
164+
/// Create a `get_field_like(base, key)` expression that models `base[key]`.
165+
pub fn get_field_like(base: Expr, key: &str) -> Expr {
166+
let udf = ScalarUDF::new_from_impl(GetFieldLikeUDF::new());
167+
udf.call(vec![base, lit(key)])
168+
}

0 commit comments

Comments
 (0)