Skip to content

Commit 8ce9f60

Browse files
adriangbclaude
andauthored
fix: PushDownLeafProjections yields when the extraction cannot move (apache#26085)
## Which issue does this PR close? - Part of apache#25459. This is a follow-up to apache#25455 (apache#14540). ## Rationale for this change `PushDownLeafProjections` and `OptimizeProjections` undo each other in every optimizer pass for a common plan shape: a projection of a struct field (or another `MoveTowardsLeafNodes` expression) directly over a node that the extraction cannot go through, such as a `TableScan` or an `Aggregate`. ```text Projection: leaf_udf(test.a) TableScan: test ``` In each pass, `push_down_leaf_projections` splits this into a recovery projection over an in-place extraction projection: ```text Projection: __datafusion_extracted_1 AS leaf_udf(test.a) Projection: leaf_udf(test.a) AS __datafusion_extracted_1, test.a TableScan: test ``` Then `optimize_projections` merges the two back into the original plan. The loop stops only because the plan at the end of a pass is the same as at the end of the previous pass. The final plan is correct, but each pass does the work of both rules again. The test that apache#25455 added found this shape. That test records which rules change the plan in each pass. On `main` it prints, for the plan above: ```text pass 0: push_down_leaf_projections, optimize_projections pass 1: push_down_leaf_projections, optimize_projections ``` With this PR: ```text pass 0: optimize_projections ``` ### Which rule yields `PushDownLeafProjections` yields. The split has no use when the extraction projection cannot move: a plain `Projection(get_field(...))` directly over a Parquet scan already reaches `DataSourceExec projection=[..., get_field(s@1, value) ...]`. The existing `EXPLAIN` checks in `projection_pushdown.slt` show this and do not change. If `OptimizeProjections` yielded instead, the plan would keep a projection node that does no work. ## What changes are included in this PR? In `split_and_push_projection` (`extract_leaf_expressions.rs`), the rule still builds the in-place extraction projection, because a mixed projection over a `Filter` must become a pure extraction projection before it can go through the filter. The rule now immediately tries to push that extraction projection into its input. If it cannot move, the rule returns the original projection unchanged. The early return for a projection without new extractions stays: it also ends the recursion of that push attempt. - The decision is recorded in the module documentation of `extract_leaf_expressions.rs` and `optimize_projections`, and as a second entry in the "Rule Precedence" section of `docs/source/library-user-guide/query-optimizer.md`. ## What is the testing strategy for this PR? - `filter_and_extraction_projection_reach_fixed_point` in `push_down_filter.rs` now checks that no rule at all changes the plan in the last optimizer pass (before, it checked only `PushDownFilter` and `PushDownLeafProjections`). It also covers a projection over a scan with no filter. Without the fix it fails with `[["push_down_leaf_projections","optimize_projections"],["push_down_leaf_projections","optimize_projections"]]`. - Six stage snapshots in `extract_leaf_expressions.rs` change. In each one, only the "After Pushdown" stage changes, to "(same as after extraction)". The "Optimized" plan is the same in all six. - One line in `unnest.slt` changes (logical plan line 03). A nested alias is now kept: `get_field(__unnest_placeholder(...,depth=1) AS UNNEST(recursive_unnest_table.column3), Utf8("c1"))`. The split and merge used to remove that alias as a side effect. The physical plan is the same. This is the same display-only nested alias that apache#25455 showed for `length(...)`. Commands run: - `cargo test --profile ci -p datafusion-optimizer --lib`: 932 passed. - `cargo test --profile ci -p datafusion-sqllogictest --test sqllogictests`: 526 of 526 files pass. - `cargo fmt --all` and `cargo clippy --profile ci -p datafusion-optimizer --all-targets -- -D warnings`: clean. ## Are there any user-facing changes? No. Final plans and results do not change, except for the alias display in the `unnest` plan above. Planning does less work for queries that read struct fields. 🤖 Generated with [Claude Code](https://claude.com/claude-code) --------- Co-authored-by: Claude Opus 5.5 <[email protected]>
1 parent 5026ac4 commit 8ce9f60

5 files changed

Lines changed: 83 additions & 49 deletions

File tree

‎datafusion/optimizer/src/extract_leaf_expressions.rs‎

Lines changed: 46 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -53,7 +53,19 @@
5353
//! that runs before the extraction projection exists, so row group pruning and
5454
//! source level filtering still happen.
5555
//!
56+
//! # Yields to [`OptimizeProjections`]
57+
//!
58+
//! When the extraction projection cannot move below the input of a projection
59+
//! (for example a `TableScan` or an `Aggregate`), [`PushDownLeafProjections`]
60+
//! leaves the projection unchanged. Splitting it in place would give a
61+
//! recovery projection over an extraction projection on the same input, and
62+
//! `OptimizeProjections` merges those two back into the original projection.
63+
//! The two rules would then undo each other on every optimizer pass. The split
64+
//! has no use there: the source absorbs the leaf expressions of the original
65+
//! projection just as well.
66+
//!
5667
//! [`PushDownFilter`]: crate::push_down_filter::PushDownFilter
68+
//! [`OptimizeProjections`]: crate::optimize_projections::OptimizeProjections
5769
5870
use indexmap::{IndexMap, IndexSet};
5971
use std::collections::{BTreeSet, HashMap};
@@ -1150,18 +1162,33 @@ fn split_and_push_projection(
11501162
// Only pre-existing __datafusion_extracted aliases and columns, no new
11511163
// extractions from routing_extract. The original projection is
11521164
// already an extraction projection that couldn't be pushed
1153-
// further. Return None.
1165+
// further. Return None. This return also ends the recursion
1166+
// of the `try_push_input` call below, which comes back here
1167+
// with a pure extraction projection.
11541168
return Ok(None);
11551169
}
1156-
// Build extraction projection in-place (couldn't push down)
1170+
// Build the extraction projection in place, then push it. It is a
1171+
// pure extraction projection, which can go through nodes that the
1172+
// original projection cannot.
11571173
let input_arc = Arc::clone(input);
1158-
let extraction = build_extraction_projection_impl(
1174+
let extraction = LogicalPlan::Projection(build_extraction_projection_impl(
11591175
&extraction_pairs,
11601176
columns_needed,
11611177
&input_arc,
11621178
input_schema.as_ref(),
1163-
)?;
1164-
LogicalPlan::Projection(extraction)
1179+
)?);
1180+
match try_push_input(&extraction, alias_generator)? {
1181+
Some(pushed) => pushed,
1182+
// The extraction projection cannot move below `input`. Leave
1183+
// the original projection unchanged: the split would put the
1184+
// extraction projection on the same input, and
1185+
// `OptimizeProjections` merges the recovery and extraction
1186+
// projections back into the original projection. The rules
1187+
// would then undo each other in every optimizer pass. The
1188+
// source absorbs the leaf expressions of the original
1189+
// projection just as well.
1190+
None => return Ok(None),
1191+
}
11651192
}
11661193
};
11671194

@@ -1730,13 +1757,10 @@ mod tests {
17301757
(same as original)
17311758
17321759
## After Pushdown
1733-
Projection: __datafusion_extracted_1 AS leaf_udf(test.user,Utf8("name"))
1734-
Projection: leaf_udf(test.user, Utf8("name")) AS __datafusion_extracted_1, test.user
1735-
TableScan: test projection=[user]
1760+
(same as after extraction)
17361761
17371762
## Optimized
1738-
Projection: leaf_udf(test.user, Utf8("name"))
1739-
TableScan: test projection=[user]
1763+
(same as after pushdown)
17401764
"#)
17411765
}
17421766

@@ -1760,13 +1784,10 @@ mod tests {
17601784
(same as original)
17611785
17621786
## After Pushdown
1763-
Projection: __datafusion_extracted_1 IS NOT NULL AS has_name
1764-
Projection: leaf_udf(test.user, Utf8("name")) AS __datafusion_extracted_1, test.user
1765-
TableScan: test projection=[user]
1787+
(same as after extraction)
17661788
17671789
## Optimized
1768-
Projection: leaf_udf(test.user, Utf8("name")) IS NOT NULL AS has_name
1769-
TableScan: test projection=[user]
1790+
(same as after pushdown)
17701791
"#)
17711792
}
17721793

@@ -1965,13 +1986,10 @@ mod tests {
19651986
(same as original)
19661987
19671988
## After Pushdown
1968-
Projection: __datafusion_extracted_1 AS username
1969-
Projection: leaf_udf(test.user, Utf8("name")) AS __datafusion_extracted_1, test.user
1970-
TableScan: test projection=[user]
1989+
(same as after extraction)
19711990
19721991
## Optimized
1973-
Projection: leaf_udf(test.user, Utf8("name")) AS username
1974-
TableScan: test projection=[user]
1992+
(same as after pushdown)
19751993
"#)
19761994
}
19771995

@@ -2031,13 +2049,10 @@ mod tests {
20312049
(same as original)
20322050
20332051
## After Pushdown
2034-
Projection: __datafusion_extracted_1 AS leaf_udf(test.user,Utf8("name")), __datafusion_extracted_1 AS name2
2035-
Projection: leaf_udf(test.user, Utf8("name")) AS __datafusion_extracted_1, test.user
2036-
TableScan: test projection=[user]
2052+
(same as after extraction)
20372053
20382054
## Optimized
2039-
Projection: leaf_udf(test.user, Utf8("name")), leaf_udf(test.user, Utf8("name")) AS name2
2040-
TableScan: test projection=[user]
2055+
(same as after pushdown)
20412056
"#)
20422057
}
20432058

@@ -2245,13 +2260,10 @@ mod tests {
22452260
(same as original)
22462261
22472262
## After Pushdown
2248-
Projection: __datafusion_extracted_1 AS leaf_udf(test.user,Utf8("name"))
2249-
Projection: leaf_udf(test.user, Utf8("name")) AS __datafusion_extracted_1, test.user
2250-
TableScan: test projection=[user]
2263+
(same as after extraction)
22512264
22522265
## Optimized
2253-
Projection: leaf_udf(test.user, Utf8("name"))
2254-
TableScan: test projection=[user]
2266+
(same as after pushdown)
22552267
"#)
22562268
}
22572269

@@ -2405,8 +2417,8 @@ mod tests {
24052417
}
24062418

24072419
/// Projection containing a MoveTowardsLeafNodes sub-expression above an
2408-
/// Aggregate. Aggregate blocks pushdown, so the (None, true) recovery
2409-
/// fallback path fires: in-place extraction + recovery projection.
2420+
/// Aggregate. The Aggregate blocks pushdown, so the extraction cannot move
2421+
/// and the original projection is kept unchanged.
24102422
#[test]
24112423
fn test_projection_with_leaf_expr_above_aggregate() -> Result<()> {
24122424
use datafusion_expr::test::function_stub::count;
@@ -2432,15 +2444,10 @@ mod tests {
24322444
(same as original)
24332445
24342446
## After Pushdown
2435-
Projection: __datafusion_extracted_1 IS NOT NULL AS has_name, COUNT(Int32(1))
2436-
Projection: leaf_udf(test.user, Utf8("name")) AS __datafusion_extracted_1, test.user, COUNT(Int32(1))
2437-
Aggregate: groupBy=[[test.user]], aggr=[[COUNT(Int32(1))]]
2438-
TableScan: test projection=[user]
2447+
(same as after extraction)
24392448
24402449
## Optimized
2441-
Projection: leaf_udf(test.user, Utf8("name")) IS NOT NULL AS has_name, COUNT(Int32(1))
2442-
Aggregate: groupBy=[[test.user]], aggr=[[COUNT(Int32(1))]]
2443-
TableScan: test projection=[user]
2450+
(same as after pushdown)
24442451
"#)
24452452
}
24462453

‎datafusion/optimizer/src/optimize_projections/mod.rs‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,17 @@
1616
// under the License.
1717

1818
//! [`OptimizeProjections`] identifies and eliminates unused columns
19+
//!
20+
//! # Precedence over `PushDownLeafProjections`
21+
//!
22+
//! `OptimizeProjections` merges adjacent projections, including a recovery
23+
//! projection over an extraction projection that
24+
//! [`PushDownLeafProjections`] creates. To keep the two rules from undoing each
25+
//! other, `PushDownLeafProjections` only creates that pair when the extraction
26+
//! projection moves below the input. See the module documentation of
27+
//! [`extract_leaf_expressions`](crate::extract_leaf_expressions).
28+
//!
29+
//! [`PushDownLeafProjections`]: crate::extract_leaf_expressions::PushDownLeafProjections
1930
2031
mod required_indices;
2132

‎datafusion/optimizer/src/push_down_filter.rs‎

Lines changed: 23 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1751,7 +1751,7 @@ mod tests {
17511751
use crate::simplify_expressions::SimplifyExpressions;
17521752
use crate::test::udfs::leaf_udf_expr;
17531753
use crate::test::*;
1754-
use datafusion_expr::test::function_stub::sum;
1754+
use datafusion_expr::test::function_stub::{count, sum};
17551755
use insta::assert_snapshot;
17561756

17571757
use super::*;
@@ -4864,9 +4864,11 @@ mod tests {
48644864

48654865
/// `PushDownFilter` and `PushDownLeafProjections` must not undo each other
48664866
/// for a filter next to a pure extraction projection
4867-
/// (<https://github.com/apache/datafusion/issues/14540>). Neither rule may
4868-
/// change the plan in the last optimizer pass. The source does not absorb
4869-
/// filters, so the `Filter` node stays in the plan.
4867+
/// (<https://github.com/apache/datafusion/issues/14540>). The source does
4868+
/// not absorb filters, so the `Filter` node stays in the plan. Also,
4869+
/// `PushDownLeafProjections` must not split a projection that
4870+
/// `OptimizeProjections` merges back. No rule may change the plan in the
4871+
/// last optimizer pass.
48704872
#[test]
48714873
fn filter_and_extraction_projection_reach_fixed_point() -> Result<()> {
48724874
let scan = || {
@@ -4887,13 +4889,26 @@ mod tests {
48874889
.project(vec![leaf_udf_expr(col("a")), col("b")])?
48884890
.build()?;
48894891

4890-
for plan in [simple, two_filters] {
4892+
// No filter: the extraction projection cannot move below the scan.
4893+
let no_filter = LogicalPlanBuilder::from(test_table_scan()?)
4894+
.project(vec![leaf_udf_expr(col("a"))])?
4895+
.build()?;
4896+
4897+
// Leaf expression above an Aggregate: the Aggregate blocks movement.
4898+
let above_aggregate = LogicalPlanBuilder::from(test_table_scan_with_struct()?)
4899+
.aggregate(vec![col("user")], vec![count(lit(1))])?
4900+
.project(vec![
4901+
leaf_udf_expr(col("user")).is_not_null().alias("has_name"),
4902+
col("COUNT(Int32(1))"),
4903+
])?
4904+
.build()?;
4905+
4906+
for plan in [simple, two_filters, no_filter, above_aggregate] {
48914907
let passes = rules_that_changed_plan_per_pass(plan)?;
48924908
let last = passes.last().unwrap();
48934909
assert!(
4894-
!last.iter().any(|rule| rule == "push_down_filter"
4895-
|| rule == "push_down_leaf_projections"),
4896-
"pushdown rules changed the plan in the last pass: {passes:?}"
4910+
last.is_empty(),
4911+
"rules changed the plan in the last pass: {passes:?}"
48974912
);
48984913
}
48994914
Ok(())

‎datafusion/sqllogictest/test_files/unnest.slt‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -668,7 +668,7 @@ explain select unnest(unnest(unnest(column3)['c1'])), column3 from recursive_unn
668668
logical_plan
669669
01)Projection: __unnest_placeholder(UNNEST(recursive_unnest_table.column3)[c1],depth=2) AS UNNEST(UNNEST(UNNEST(recursive_unnest_table.column3)[c1])), recursive_unnest_table.column3
670670
02)--Unnest: lists[__unnest_placeholder(UNNEST(recursive_unnest_table.column3)[c1])|depth=2] structs[]
671-
03)----Projection: get_field(__unnest_placeholder(recursive_unnest_table.column3,depth=1), Utf8("c1")) AS __unnest_placeholder(UNNEST(recursive_unnest_table.column3)[c1]), recursive_unnest_table.column3
671+
03)----Projection: get_field(__unnest_placeholder(recursive_unnest_table.column3,depth=1) AS UNNEST(recursive_unnest_table.column3), Utf8("c1")) AS __unnest_placeholder(UNNEST(recursive_unnest_table.column3)[c1]), recursive_unnest_table.column3
672672
04)------Unnest: lists[__unnest_placeholder(recursive_unnest_table.column3)|depth=1] structs[]
673673
05)--------Projection: recursive_unnest_table.column3 AS __unnest_placeholder(recursive_unnest_table.column3), recursive_unnest_table.column3
674674
06)----------TableScan: recursive_unnest_table projection=[column3]

‎docs/source/library-user-guide/query-optimizer.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -168,9 +168,10 @@ Two rules can want the opposite order for the same pair of adjacent plan nodes.
168168

169169
Do not let two rules compete. Give one rule precedence, make the competing rule yield, and record the decision in the module documentation of both rules.
170170

171-
There is one such decision today:
171+
There are two such decisions today:
172172

173173
- `PushDownFilter` yields to a _pure extraction projection_. A pure extraction projection is a projection whose expressions are only `__datafusion_extracted_N` aliases and pass-through columns. `ExtractLeafExpressions` creates it, and `PushDownLeafProjections` moves it towards the leaves. `PushDownFilter` does not move a filter below such a projection, so the projection stays next to the scan. A Parquet scan then merges the projection into the file projection and reads only the struct leaf. The filter loses nothing, because `PushDownFilter` records the predicate in `TableScan::filters` in the pass that runs before the extraction projection exists. See [issue #14540](https://github.com/apache/datafusion/issues/14540).
174+
- `PushDownLeafProjections` yields to `OptimizeProjections`. When the extraction projection cannot move below the input of a projection, for example a `TableScan` or an `Aggregate`, `PushDownLeafProjections` leaves the projection unchanged. A split in place would give a recovery projection over an extraction projection on the same input, which `OptimizeProjections` merges back. The source absorbs the leaf expressions of the original projection just as well. See [PR #26085](https://github.com/apache/datafusion/pull/26085).
174175

175176
### Expression Naming
176177

0 commit comments

Comments
 (0)