Skip to content

Commit d4c2a32

Browse files
authored
perf: reuse projection schema in OptimizeProjections instead of recomputing it (#24281)
## Which issue does this close? Closes #24264. Answers #24284 in the process. ## Rationale for this change `rewrite_projection_given_requirements`, the core of `OptimizeProjections`, prunes a projection's expressions to the subset actually required and then rebuilds it with `Projection::try_new`. `try_new` recomputes the output schema via `projection_schema`, calling `Expr::to_field` for every retained expression; column resolution is a linear scan over the input schema, so this is `O(exprs * schema_width)` per projection, per pass. The retained expressions are a subset of the ones the projection already has, so the answer is usually already sitting in `proj.schema`. Reusing it is only safe if that schema is still what the expressions derive. `OptimizeProjections` recomputing every schema was quietly fixing up the cases where it is not, so this PR first makes those cases explicit. ## What changes are included in this PR? A stored projection schema can go stale in three ways. Each is handled where it happens: **1. A rule rewrites the projection's own expressions.** - `LogicalPlan::map_expressions` now derives the projection schema again when the expressions were rewritten, and keeps it otherwise. This covers in-tree rules such as `SimplifyExpressions` (constant folding can turn a nullable function call into a non-null literal) and downstream rules registered with `add_optimizer_rule`, which previously relied on the next `OptimizeProjections` pass to fix the schema up. This is the root cause #24284 points at. - `CommonSubexprEliminate` builds its projection itself, so it derives the schema there when it changed something (`common_subexpr_eliminate.rs`). Splitting a CASE guard such as `WHEN x IS NOT NULL THEN x` into two common subexpressions means the rewritten CASE can no longer be proven non-null, while the stored schema still said non-null. This is the sqlite sqllogictest failure the previous revision hit (`slt_good_1.slt:33179`); a minimal version is now in `cse.slt`. **2. The projection contains a subquery.** A subquery is optimized on its own, so the field it produces can change after the outer projection's schema was derived. `OptimizeProjections` recomputes the schema for these. **3. Rewriting the input changes a field the projection reads**, for example an aggregate rebuilt after constant folding made a group column non-null. After the input is rewritten, `OptimizeProjections` compares the `k` fields the projection reads before and after (`read_fields_unchanged`). If any differ, it recomputes. **Otherwise it reuses the schema.** `project_schema_by_indices` selects the already-computed fields at the retained indices and builds with `Projection::try_new_with_schema`; when nothing is pruned, the existing `Arc` is reused as-is. Functional dependencies are projected through the kept indices; they can be weaker than recomputed ones, never stronger. The checks cost `O(k)` with no name lookups, so the common case goes from `O(exprs * width)` to `O(k)`. ## Benchmarks The existing `sql_planner` cases barely exercise this: their projections are narrow or plain columns, so recomputing the schema is cheap there. #26841 adds `optimizer_wide_projection_stack_{all,half}`: four nested projections of 200 computed expressions each over a 200-column table, as produced by layered views. Locally (Apple M4 Pro), with that benchmark applied to both sides: | case | main | this PR | |---|---|---| | `optimizer_wide_projection_stack_all` | 11.28 ms | 6.24 ms (-45%) | | `optimizer_wide_projection_stack_half` | 5.57 ms | 3.81 ms (-32%) | On a downstream production query with a ~60-column projection, `OptimizeProjections` went from 18.1 ms to 9.2 ms (-49%). ## Are these changes tested? To check that nothing else can go stale, I temporarily logged every reused schema that differs from `projection_schema` and ran all 542 sqllogictest files. Before (2) and (3) it logged 13 cases (12 scalar subqueries, 1 aggregate); with them it logs none. So for everything the test suite covers, the reused fields are exactly what `try_new` would compute, and final plans are unchanged. Tests, each verified to fail without its fix: - `projection_schema_follows_rule_rewrite` (a downstream-style rule using `map_expressions`), `projection_schema_kept_without_rule_rewrite` (unchanged expressions keep the same schema `Arc`), `projection_schema_follows_rewritten_exprs` (CSE unit test) and the `cse.slt` coalesce case for (1) - `projection_schema_follows_subquery` for (2) - `projection_schema_follows_rewritten_input` for (3) - `project_schema_by_indices_matches_recompute`: the sliced schema matches `projection_schema` on fields, qualifiers, metadata and functional dependencies, and the identity subset reuses the same `Arc` No existing test or snapshot needed updating. Local runs on current `main`: `datafusion-optimizer` 958 + 29 + 5, `datafusion-expr`, and all 542 sqllogictest files. ## Are there any user-facing changes? Optimized plans are unchanged. `LogicalPlan::map_expressions` now returns a projection with a freshly derived schema when it rewrote the projection's expressions, so custom rules no longer need to rebuild it with `Projection::try_new` themselves. API change: because the schema is derived from the new expressions, a rewrite that renames outputs (e.g. `unalias`) now changes the returned `schema()`, and a rewrite whose new expressions reference columns of an input installed only afterwards now fails inside `map_expressions` on a `Projection`. The 56.0.0 upgrade guide describes both and the migration.
1 parent 867bf3c commit d4c2a32

5 files changed

Lines changed: 505 additions & 21 deletions

File tree

‎datafusion/expr/src/logical_plan/tree_node.rs‎

Lines changed: 22 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -544,6 +544,9 @@ impl LogicalPlan {
544544
/// # Notes
545545
/// * Similar to [`TreeNode::map_children`] but for this node's expressions.
546546
/// * Visits only the top level expressions (Does not recurse into each expression)
547+
/// * A `Projection` whose expressions were rewritten gets its schema derived
548+
/// again from the new expressions, so the new expressions must resolve
549+
/// against the current input.
547550
pub fn map_expressions<F: FnMut(Expr) -> Result<Transformed<Expr>>>(
548551
self,
549552
mut f: F,
@@ -553,13 +556,25 @@ impl LogicalPlan {
553556
expr,
554557
input,
555558
schema,
556-
}) => expr.map_elements(f)?.update_data(|expr| {
557-
LogicalPlan::Projection(Projection {
558-
expr,
559-
input,
560-
schema,
561-
})
562-
}),
559+
}) => {
560+
let expr = expr.map_elements(f)?;
561+
if expr.transformed {
562+
// A projection's output fields are derived from its
563+
// expressions, so rewritten expressions need a freshly
564+
// derived schema.
565+
expr.map_data(|expr| {
566+
Projection::try_new(expr, input).map(LogicalPlan::Projection)
567+
})?
568+
} else {
569+
expr.update_data(|expr| {
570+
LogicalPlan::Projection(Projection {
571+
expr,
572+
input,
573+
schema,
574+
})
575+
})
576+
}
577+
}
563578
LogicalPlan::Values(Values { schema, values }) => values
564579
.map_elements(f)?
565580
.update_data(|values| LogicalPlan::Values(Values { schema, values })),

‎datafusion/optimizer/src/common_subexpr_eliminate.rs‎

Lines changed: 45 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -76,11 +76,22 @@ impl CommonSubexprEliminate {
7676
..
7777
} = projection;
7878
let input = Arc::unwrap_or_clone(input);
79-
self.try_unary_plan(expr, input, config)?
80-
.map_data(|(new_expr, new_input)| {
81-
Projection::try_new_with_schema(new_expr, Arc::new(new_input), schema)
82-
.map(LogicalPlan::Projection)
83-
})
79+
let rewritten = self.try_unary_plan(expr, input, config)?;
80+
let transformed = rewritten.transformed;
81+
rewritten.map_data(|(new_expr, new_input)| {
82+
let new_input = Arc::new(new_input);
83+
// The rewritten expressions keep their names, but their fields can
84+
// differ: a CASE whose `WHEN x IS NOT NULL THEN x` guard is split
85+
// into two common subexpressions can no longer be proven non-null.
86+
// Derive the schema from the new expressions so it matches what
87+
// the physical planner will compute from them.
88+
if transformed {
89+
Projection::try_new(new_expr, new_input)
90+
} else {
91+
Projection::try_new_with_schema(new_expr, new_input, schema)
92+
}
93+
.map(LogicalPlan::Projection)
94+
})
8495
}
8596

8697
fn try_optimize_sort(
@@ -889,11 +900,11 @@ mod test {
889900
use std::iter;
890901

891902
use arrow::datatypes::{DataType, Field, Schema};
892-
use datafusion_expr::logical_plan::{JoinType, table_scan};
903+
use datafusion_expr::logical_plan::{JoinType, projection_schema, table_scan};
893904
use datafusion_expr::{
894905
AccumulatorFactoryFunction, AggregateUDF, ColumnarValue, ExprFunctionExt,
895906
ScalarFunctionArgs, ScalarUDF, ScalarUDFImpl, Signature, SimpleAggregateUDF,
896-
Volatility, WindowFunctionDefinition, grouping_set, is_null, not,
907+
Volatility, WindowFunctionDefinition, grouping_set, is_null, not, when,
897908
};
898909
use datafusion_expr::{lit, logical_plan::builder::LogicalPlanBuilder};
899910

@@ -2157,4 +2168,31 @@ mod test {
21572168
"
21582169
)
21592170
}
2171+
2172+
/// A projection rewritten by CSE carries the schema its new expressions
2173+
/// derive, not the one derived before the rewrite.
2174+
#[test]
2175+
fn projection_schema_follows_rewritten_exprs() -> Result<()> {
2176+
let schema = Schema::new(vec![Field::new("a", DataType::Int32, true)]);
2177+
let table_scan = table_scan(Some("t"), &schema, None)?.build()?;
2178+
let a = || col("a") + lit(1);
2179+
let expr = when(a().is_not_null(), a())
2180+
.when(a().is_not_null(), a())
2181+
.otherwise(lit(0))?;
2182+
let plan = LogicalPlanBuilder::from(table_scan)
2183+
.project(vec![expr])?
2184+
.build()?;
2185+
// Before the rewrite the guard proves the CASE non-null.
2186+
assert!(!plan.schema().field(0).is_nullable());
2187+
2188+
let optimized = CommonSubexprEliminate::new()
2189+
.rewrite(plan, &OptimizerContext::new())?
2190+
.data;
2191+
let LogicalPlan::Projection(projection) = &optimized else {
2192+
panic!("expected a projection, got {optimized}");
2193+
};
2194+
let derived = projection_schema(&projection.input, &projection.expr)?;
2195+
assert_eq!(projection.schema.as_ref(), derived.as_ref());
2196+
Ok(())
2197+
}
21602198
}

0 commit comments

Comments
 (0)