Skip to content

Commit 27e81e9

Browse files
authored
fix: do not duplicate volatile expressions when extracting leaf expressions (apache#24720)
## Which issue does this PR close? - Closes apache#24678. ## Rationale for this change A column alias denotes one value per row, and `WHERE p` may only return rows for which `p` held for that row. Today the leaf-expression extraction passes break both: ```sql SELECT s, s['a'] AS field FROM (SELECT named_struct('a', random()) AS s FROM generate_series(1, 3)); ``` | `s['a']` | `field` | |---|---| | 0.5159112071865757 | 0.4514238291986653 | | 0.0029104680074608646 | 0.28979983332288195 | | 0.48542729227457915 | 0.04499392663566881 | `field` is defined as `s['a']` but differs from it on every row, because the plan is ``` Projection: named_struct(Utf8("a"), random()) AS s, random() AS field ``` The `Filter` form is worse — it returns rows that fail their own predicate: ```sql SELECT bool_and(s['a'] > 0.5) FROM (SELECT s FROM (SELECT named_struct('a', random()) AS s FROM generate_series(1, 1000)) WHERE s['a'] > 0.5); -- false; the predicate tested a different draw than the one in the returned `s` ``` Setting `datafusion.optimizer.enable_leaf_expression_pushdown = false` returns the correct answer in both cases, so the rewrite alone changes the meaning of the query. **Root cause.** `build_extraction_projection_impl` merges an extraction into the input projection by resolving column references through `build_projection_replace_map`, i.e. by inlining each referenced column's *defining* expression. Inlining a volatile definition produces a second, independent evaluation. There was no volatility check in the file. This is the same invariant `FileScanConfig::try_swapping_with_projection` already enforces for the physical projection-pushdown path via `would_duplicate_costly_exprs` (apache#23220) — the logical extraction path was missing it. ## What changes are included in this PR? - `volatile_output_columns()` — a projection's output columns whose definition is volatile. - `would_duplicate_volatile()` — true when an extraction references one of them. - The guard is applied at the three places that can merge into an input projection: `extract_from_plan` (pass 1: Filter/Sort/Limit/Aggregate/Join), `split_and_push_projection` (pass 2), and `try_push_into_inputs` (multi-input/Union routing). Each already had a "leave the plan alone" return path. The guard is targeted rather than blanket: for `ORDER BY s['a']` the extraction still happens, stacked above the volatile projection instead of merged into it, so the optimization is kept and the result is correct. ### Relationship to apache#23691 @fornwall wondered on the issue whether apache#23691 already covers this. I checked out that branch and ran both shapes against it: `SELECT s, s['a']` is incidentally fixed there, but `WHERE s['a'] > 0.5` still duplicates `random()` and still returns rows failing the predicate. apache#23691 guards `KeepInPlace` *compute cost* in `split_and_push_projection` only; volatility is a separate concern (one duplication is already wrong, regardless of cost or placement) and pass 1 is a different code path. The two changes look independent to me and I believe they compose, but I'd appreciate a second opinion on that from whoever reviews apache#23691. ## Are these changes tested? Yes. - `datafusion/sqllogictest/test_files/projection_pushdown.slt` — a new section beside the existing apache#23220 volatile section: two `EXPLAIN`s pinning `random()` to a single occurrence, and two deterministic `bool_and(...)` correctness queries. All four fail on `main` and pass here. - Two rule-level snapshot tests in `extract_leaf_expressions.rs` covering the pass-2 projection merge and the pass-1 `Filter` extraction, using a new test-only `PlacementTestUDF::with_volatility()`. `cargo test -p datafusion-optimizer` (796), `cargo test -p datafusion --lib --tests` (2049) and the full 504-file sqllogictest suite all pass; `cargo fmt --all` and `cargo clippy --all-targets --all-features -- -D warnings` are clean. ## Are there any user-facing changes? Queries that were silently returning wrong results now return correct ones. No API change. In the affected shapes the extraction is skipped, which can cost a small amount of column pruning — only when the referenced column is defined by a volatile expression. --- <sub>Per the ASF generative-tooling policy and DataFusion's AI-assisted contribution guidance: this patch was prepared with AI assistance. The core idea is the one described above — the merge path inlines a referenced column's defining expression, which duplicates a volatile definition — and the open question about how this composes with apache#23691 is flagged deliberately rather than glossed over.</sub>
1 parent 17115f3 commit 27e81e9

3 files changed

Lines changed: 240 additions & 4 deletions

File tree

‎datafusion/optimizer/src/extract_leaf_expressions.rs‎

Lines changed: 154 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -57,6 +57,58 @@ fn has_extractable_expr(exprs: &[Expr]) -> bool {
5757
})
5858
}
5959

60+
/// Returns the flat names of `plan`'s output columns whose defining expression
61+
/// is volatile (e.g. `random()`).
62+
///
63+
/// Only a [`LogicalPlan::Projection`] can define such a column: anywhere else
64+
/// the value has already been materialized by the projection that produced it,
65+
/// so referencing the column again does not re-evaluate anything.
66+
fn volatile_output_columns(plan: &LogicalPlan) -> BTreeSet<String> {
67+
let LogicalPlan::Projection(projection) = plan else {
68+
return BTreeSet::new();
69+
};
70+
projection
71+
.schema
72+
.iter()
73+
.zip(projection.expr.iter())
74+
.filter(|(_, expr)| expr.is_volatile())
75+
.map(|((qualifier, field), _)| Column::from((qualifier, field)).flat_name())
76+
.collect()
77+
}
78+
79+
/// Returns `true` if building an extraction projection for `exprs` on top of
80+
/// `input` would duplicate a volatile computation.
81+
///
82+
/// When `input` is already a projection, [`build_extraction_projection_impl`]
83+
/// *merges* into it: every column reference in an extracted expression is
84+
/// replaced by that column's defining expression (see
85+
/// [`build_projection_replace_map`]). Inlining a volatile definition makes the
86+
/// merged projection evaluate it a second, independent time, so the extracted
87+
/// value no longer matches the column it was derived from:
88+
///
89+
/// ```text
90+
/// Projection: s, get_field(s, 'a') AS field
91+
/// Projection: named_struct('a', random()) AS s
92+
/// ```
93+
///
94+
/// would merge into a single projection computing `random()` twice, and
95+
/// `field` would then differ from `s['a']` on every row. Callers skip the
96+
/// extraction instead.
97+
fn would_duplicate_volatile<'a>(
98+
exprs: impl IntoIterator<Item = &'a Expr>,
99+
input: &LogicalPlan,
100+
) -> bool {
101+
let volatile = volatile_output_columns(input);
102+
if volatile.is_empty() {
103+
return false;
104+
}
105+
exprs.into_iter().any(|expr| {
106+
expr.column_refs()
107+
.iter()
108+
.any(|col| volatile.contains(&col.flat_name()))
109+
})
110+
}
111+
60112
/// Extracts `MoveTowardsLeafNodes` sub-expressions from non-projection nodes
61113
/// into **extraction projections** (pass 1 of 2).
62114
///
@@ -195,7 +247,18 @@ fn extract_from_plan(
195247
}
196248

197249
// Fast pre-check: skip all allocations if no extractable expressions exist
198-
if !has_extractable_expr(&plan.expressions()) {
250+
let node_exprs = plan.expressions();
251+
if !has_extractable_expr(&node_exprs) {
252+
return Ok(Transformed::no(plan));
253+
}
254+
255+
// The extraction projection is merged into an input that is already a
256+
// projection, which inlines the referenced columns' definitions. Skip the
257+
// extraction when that would duplicate a volatile computation.
258+
if inputs
259+
.iter()
260+
.any(|input| would_duplicate_volatile(node_exprs.iter(), input))
261+
{
199262
return Ok(Transformed::no(plan));
200263
}
201264

@@ -917,6 +980,16 @@ fn split_and_push_projection(
917980
return Ok(None);
918981
}
919982

983+
// Pushing into an input that is already a projection merges into it and
984+
// inlines the referenced columns' definitions. Leave the projection alone
985+
// when that would duplicate a volatile computation.
986+
if would_duplicate_volatile(
987+
extraction_pairs.iter().map(|(expr, _)| expr),
988+
input.as_ref(),
989+
) {
990+
return Ok(None);
991+
}
992+
920993
// ── Phase 2: Push down ──────────────────────────────────────────────
921994
let proj_input = Arc::clone(&proj.input);
922995
let pushed = push_extraction_pairs(
@@ -1215,6 +1288,15 @@ fn try_push_into_inputs(
12151288
if per_input[idx].pairs.is_empty() {
12161289
new_inputs.push(input.clone());
12171290
} else {
1291+
// Merging into an input projection inlines the referenced columns'
1292+
// definitions; bail out when that would duplicate a volatile
1293+
// computation.
1294+
if would_duplicate_volatile(
1295+
per_input[idx].pairs.iter().map(|(expr, _)| expr),
1296+
input,
1297+
) {
1298+
return Ok(None);
1299+
}
12181300
let input_arc = Arc::new(input.clone());
12191301
let target_schema = Arc::clone(input.schema());
12201302
let proj = build_extraction_projection_impl(
@@ -1270,7 +1352,7 @@ mod tests {
12701352
use crate::{Optimizer, OptimizerContext};
12711353
use datafusion_expr::expr::ScalarFunction;
12721354
use datafusion_expr::{
1273-
ScalarUDF, col, lit, logical_plan::builder::LogicalPlanBuilder,
1355+
ScalarUDF, Volatility, col, lit, logical_plan::builder::LogicalPlanBuilder,
12741356
};
12751357

12761358
fn leaf_udf(expr: Expr, name: &str) -> Expr {
@@ -1283,6 +1365,19 @@ mod tests {
12831365
))
12841366
}
12851367

1368+
/// A stand-in for `random()`: a volatile expression that must be evaluated
1369+
/// exactly once per row.
1370+
fn volatile_udf(expr: Expr) -> Expr {
1371+
Expr::ScalarFunction(ScalarFunction::new_udf(
1372+
Arc::new(ScalarUDF::new_from_impl(
1373+
PlacementTestUDF::new()
1374+
.with_placement(ExpressionPlacement::KeepInPlace)
1375+
.with_volatility(Volatility::Volatile),
1376+
)),
1377+
vec![expr],
1378+
))
1379+
}
1380+
12861381
// =========================================================================
12871382
// Combined optimization stage formatter
12881383
// =========================================================================
@@ -1960,6 +2055,63 @@ mod tests {
19602055
"#)
19612056
}
19622057

2058+
/// Merging an extraction into an input projection inlines the definition of
2059+
/// every column the extraction references. When that definition is volatile
2060+
/// the inlined copy is an independent evaluation, so the extraction must be
2061+
/// skipped and the plan left alone.
2062+
#[test]
2063+
fn test_no_merge_into_volatile_projection() -> Result<()> {
2064+
let table_scan = test_table_scan()?;
2065+
let plan = LogicalPlanBuilder::from(table_scan)
2066+
.project(vec![volatile_udf(col("a")).alias("v")])?
2067+
.project(vec![col("v"), leaf_udf(col("v"), "x")])?
2068+
.build()?;
2069+
2070+
assert_stages!(plan, @r#"
2071+
## Original Plan
2072+
Projection: v, leaf_udf(v, Utf8("x"))
2073+
Projection: keep_in_place_udf(test.a) AS v
2074+
TableScan: test projection=[a]
2075+
2076+
## After Extraction
2077+
(same as original)
2078+
2079+
## After Pushdown
2080+
(same as after extraction)
2081+
2082+
## Optimized
2083+
(same as after pushdown)
2084+
"#)
2085+
}
2086+
2087+
/// Same guard for pass 1: extracting out of a `Filter` whose input
2088+
/// projection defines the referenced column volatilely would make the
2089+
/// predicate test a second, independent evaluation.
2090+
#[test]
2091+
fn test_no_extraction_from_filter_over_volatile_projection() -> Result<()> {
2092+
let table_scan = test_table_scan()?;
2093+
let plan = LogicalPlanBuilder::from(table_scan)
2094+
.project(vec![volatile_udf(col("a")).alias("v")])?
2095+
.filter(leaf_udf(col("v"), "x").eq(lit(1u32)))?
2096+
.build()?;
2097+
2098+
assert_stages!(plan, @r#"
2099+
## Original Plan
2100+
Filter: leaf_udf(v, Utf8("x")) = UInt32(1)
2101+
Projection: keep_in_place_udf(test.a) AS v
2102+
TableScan: test projection=[a]
2103+
2104+
## After Extraction
2105+
(same as original)
2106+
2107+
## After Pushdown
2108+
(same as after extraction)
2109+
2110+
## Optimized
2111+
(same as after pushdown)
2112+
"#)
2113+
}
2114+
19632115
/// Projections with aliased columns (nothing to extract) return unchanged.
19642116
#[test]
19652117
fn test_projection_early_return_no_extraction() -> Result<()> {

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

Lines changed: 9 additions & 2 deletions
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,
22+
ScalarUDFImpl, Signature, TypeSignature, Volatility,
2323
};
2424

2525
/// A configurable test UDF for optimizer tests.
@@ -44,7 +44,7 @@ impl PlacementTestUDF {
4444
// The actual types don't matter since this UDF is not intended for execution.
4545
signature: Signature::new(
4646
TypeSignature::OneOf(vec![TypeSignature::Any(1), TypeSignature::Any(2)]),
47-
datafusion_expr::Volatility::Immutable,
47+
Volatility::Immutable,
4848
),
4949
placement: ExpressionPlacement::MoveTowardsLeafNodes,
5050
id: 0,
@@ -64,6 +64,13 @@ impl PlacementTestUDF {
6464
self.id = id;
6565
self
6666
}
67+
68+
/// Set the volatility of the UDF, so that rules which must not duplicate a
69+
/// volatile computation (e.g. `random()`) can be exercised.
70+
pub fn with_volatility(mut self, volatility: Volatility) -> Self {
71+
self.signature.volatility = volatility;
72+
self
73+
}
6774
}
6875

6976
impl ScalarUDFImpl for PlacementTestUDF {

‎datafusion/sqllogictest/test_files/projection_pushdown.slt‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2144,6 +2144,83 @@ true
21442144
true
21452145
true
21462146

2147+
#####################
2148+
# Section: leaf expression extraction does not duplicate volatile expressions
2149+
#
2150+
# Regression test for #24678. `extract_leaf_expressions` / `push_down_leaf_projections`
2151+
# build an extraction projection by *merging* into the input projection, which
2152+
# inlines the definition of every column the extracted expression references.
2153+
# When that definition is volatile the inlined copy is an independent
2154+
# evaluation, so `random()` is drawn twice and the extracted value no longer
2155+
# matches the struct it was derived from.
2156+
#
2157+
# Before the fix the plan below read
2158+
# Projection: named_struct(Utf8("a"), random()) AS s, random() AS field
2159+
# and `field` differed from `s['a']` on every row. This is the same invariant
2160+
# `FileScanConfig::try_swapping_with_projection` already enforces for the
2161+
# physical pushdown path (#23220).
2162+
#####################
2163+
2164+
statement ok
2165+
set datafusion.explain.logical_plan_only = true;
2166+
2167+
# `random()` must appear once; `field` reads the struct materialized below it.
2168+
query TT
2169+
EXPLAIN SELECT s, s['a'] AS field
2170+
FROM (SELECT named_struct('a', random()) AS s FROM generate_series(1, 3));
2171+
----
2172+
logical_plan
2173+
01)Projection: s, get_field(s, Utf8("a")) AS field
2174+
02)--Projection: named_struct(Utf8("a"), random()) AS s
2175+
03)----TableScan: generate_series() projection=[]
2176+
2177+
# Same for an extraction out of a Filter: the predicate must test the struct
2178+
# that is returned, not a second draw.
2179+
query TT
2180+
EXPLAIN SELECT s
2181+
FROM (SELECT named_struct('a', random()) AS s FROM generate_series(1, 3))
2182+
WHERE s['a'] > 0.5;
2183+
----
2184+
logical_plan
2185+
01)Filter: get_field(s, Utf8("a")) > Float64(0.5)
2186+
02)--Projection: named_struct(Utf8("a"), random()) AS s
2187+
03)----TableScan: generate_series() projection=[]
2188+
2189+
statement ok
2190+
set datafusion.explain.logical_plan_only = false;
2191+
2192+
# Every row's `field` is the `a` field of that row's own struct.
2193+
query B
2194+
SELECT bool_and(field = s['a'])
2195+
FROM (
2196+
SELECT s, s['a'] AS field
2197+
FROM (SELECT named_struct('a', random()) AS s FROM generate_series(1, 1000))
2198+
);
2199+
----
2200+
true
2201+
2202+
# Same invariant when the extraction is routed into one side of a join.
2203+
query B
2204+
SELECT bool_and(field = s['a'])
2205+
FROM (
2206+
SELECT l.s, l.s['a'] AS field
2207+
FROM (SELECT named_struct('a', random()) AS s FROM generate_series(1, 1000)) AS l
2208+
INNER JOIN (SELECT 1 AS k) AS r ON true
2209+
);
2210+
----
2211+
true
2212+
2213+
# Every surviving row satisfies the predicate it was filtered on.
2214+
query B
2215+
SELECT bool_and(s['a'] > 0.5)
2216+
FROM (
2217+
SELECT s
2218+
FROM (SELECT named_struct('a', random()) AS s FROM generate_series(1, 1000))
2219+
WHERE s['a'] > 0.5
2220+
);
2221+
----
2222+
true
2223+
21472224
#####################
21482225
# Section: expensive expressions are not re-inlined by projection pushdown
21492226
#

0 commit comments

Comments
 (0)