Skip to content

Commit e2a2838

Browse files
adriangbclaude
andcommitted
feat: prune unused columns from the body of a materialized CTE
The body of a `MaterializedCte` kept all its columns, because each `MaterializedCteScan` was a leaf with the full schema of the body. A `MaterializedCteScan` now has a `projection`: the indexes of the columns of the body that it outputs. `OptimizeProjections` narrows each scan to the columns that its parent needs, as it does for a `TableScan`. At the `MaterializedCte` node it optimizes the continuation first, computes the union of the columns of all the scans of the CTE (also in subquery expressions and in the bodies of other CTEs), projects the body to this union, and gives each scan the new positions of its columns. `MaterializedCteScanExec` applies the projection to the shared buffered batches. The physical planner checks that each scan agrees with the schema of its body when it binds the scan. Closes apache#26240. Co-Authored-By: Claude Opus 5.5 <[email protected]>
1 parent cec3126 commit e2a2838

3 files changed

Lines changed: 300 additions & 128 deletions

File tree

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

Lines changed: 217 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -42,13 +42,15 @@ use datafusion_common::{
4242
use datafusion_expr::expr::Alias;
4343
use datafusion_expr::utils::passthrough_field_index;
4444
use datafusion_expr::{
45-
Aggregate, Distinct, EmptyRelation, Expr, Projection, TableScanBuilder, Unnest,
46-
Window, logical_plan::LogicalPlan,
45+
Aggregate, Distinct, EmptyRelation, Expr, MaterializedCte, MaterializedCteScan,
46+
Projection, TableScanBuilder, Unnest, Window, logical_plan::LogicalPlan,
4747
};
4848

4949
use crate::optimize_projections::required_indices::RequiredIndices;
5050
use crate::utils::NamePreserver;
51-
use datafusion_common::tree_node::{Transformed, TreeNode, TreeNodeContainer};
51+
use datafusion_common::tree_node::{
52+
Transformed, TreeNode, TreeNodeContainer, TreeNodeRecursion,
53+
};
5254

5355
/// Optimizer rule to prune unnecessary columns from intermediate schemas
5456
/// inside the [`LogicalPlan`]. This rule:
@@ -291,6 +293,20 @@ fn optimize_projections(
291293
return Transformed::yes(LogicalPlan::TableScan(new_scan))
292294
.transform_data(|plan| optimize_subqueries(plan, config));
293295
}
296+
LogicalPlan::MaterializedCte(MaterializedCtePlan::Scan(scan)) => {
297+
// Read only the necessary columns of the CTE body. The node that
298+
// owns the CTE then removes from the body the columns that no
299+
// scan reads.
300+
let new_scan = scan.with_projection(indices.indices())?;
301+
let transformed = new_scan.projection != scan.projection;
302+
return Ok(Transformed::new_transformed(
303+
LogicalPlan::MaterializedCte(MaterializedCtePlan::Scan(new_scan)),
304+
transformed,
305+
));
306+
}
307+
LogicalPlan::MaterializedCte(MaterializedCtePlan::Cte(cte)) => {
308+
return optimize_materialized_cte(cte, config, indices);
309+
}
294310
// Other node types are handled below
295311
_ => {}
296312
}
@@ -376,18 +392,8 @@ fn optimize_projections(
376392
.collect()
377393
}
378394
}
379-
LogicalPlan::MaterializedCte(MaterializedCtePlan::Cte(cte)) => {
380-
// The scans are leaves whose schema is the schema of the body, so
381-
// the body keeps every column. The output is the output of the
382-
// continuation, so the continuation needs what the parent needs.
383-
vec![
384-
RequiredIndices::new_for_all_exprs(&cte.cte),
385-
RequiredIndices::new_from_indices(indices.into_inner()),
386-
]
387-
}
388395
LogicalPlan::EmptyRelation(_)
389396
| LogicalPlan::Values(_)
390-
| LogicalPlan::MaterializedCte(MaterializedCtePlan::Scan(_))
391397
| LogicalPlan::DescribeTable(_) => {
392398
// These operators have no inputs, so stop the optimization process.
393399
return Ok(Transformed::no(plan));
@@ -452,7 +458,8 @@ fn optimize_projections(
452458
LogicalPlan::Projection(_)
453459
| LogicalPlan::Aggregate(_)
454460
| LogicalPlan::Window(_)
455-
| LogicalPlan::TableScan(_) => {
461+
| LogicalPlan::TableScan(_)
462+
| LogicalPlan::MaterializedCte(_) => {
456463
return internal_err!(
457464
"OptimizeProjection: should have handled in the match statement above"
458465
);
@@ -520,6 +527,104 @@ fn optimize_projections(
520527
}
521528
}
522529

530+
/// Removes unnecessary columns from a [`MaterializedCte`]: from its
531+
/// continuation, and then from its body.
532+
///
533+
/// The columns that the body must keep are not known from the parent of the
534+
/// node. They are the columns that the scans of the CTE read, and the scans
535+
/// are leaves of the continuation, of a subquery expression in it, or of the
536+
/// body of another CTE in it. Thus the continuation is optimized first, which
537+
/// narrows each scan to the columns that its parent needs. The body is then
538+
/// projected to the union of the columns of all the scans, and each scan gets
539+
/// the new positions of its columns. The output schema of a scan does not
540+
/// change in this second step.
541+
fn optimize_materialized_cte(
542+
cte: MaterializedCte,
543+
config: &dyn OptimizerConfig,
544+
indices: RequiredIndices,
545+
) -> Result<Transformed<LogicalPlan>> {
546+
let MaterializedCte {
547+
id,
548+
name,
549+
cte: body,
550+
continuation,
551+
} = cte;
552+
// The output is the output of the continuation, so the continuation
553+
// needs what the parent needs.
554+
let continuation =
555+
optimize_projections(Arc::unwrap_or_clone(continuation), config, indices)?;
556+
let mut transformed = continuation.transformed;
557+
let mut continuation = continuation.data;
558+
let mut body = Arc::unwrap_or_clone(body);
559+
560+
let body_len = body.schema().fields().len();
561+
let scans = MaterializedCteScan::find_in(&continuation, id)?;
562+
let mut is_read = vec![false; body_len];
563+
for scan in &scans {
564+
match scan.projection() {
565+
None => is_read.fill(true),
566+
Some(projection) => {
567+
for index in projection {
568+
let Some(is_read) = is_read.get_mut(*index) else {
569+
return internal_err!(
570+
"A scan of the materialized CTE {name} reads the column {index}, but the CTE has {body_len} columns"
571+
);
572+
};
573+
*is_read = true;
574+
}
575+
}
576+
}
577+
}
578+
// A reference such as `SELECT count(*) FROM c` reads no column. Keep one
579+
// column then, so that the body is never a projection without columns.
580+
if !is_read.contains(&true)
581+
&& let Some(first) = is_read.first_mut()
582+
{
583+
*first = true;
584+
}
585+
let kept: Vec<usize> = (0..body_len).filter(|index| is_read[*index]).collect();
586+
// A CTE that nothing reads is not planned, so its body is left as it is.
587+
if !scans.is_empty() && kept.len() < body_len {
588+
let exprs = RequiredIndices::new_from_indices(kept.clone())
589+
.get_required_exprs(body.schema());
590+
body = Projection::try_new(exprs, Arc::new(body)).map(LogicalPlan::Projection)?;
591+
continuation = continuation
592+
.transform_down_with_subqueries(|node| match node {
593+
// A nested occurrence of the same CTE has its own body and
594+
// owns the scans below it.
595+
LogicalPlan::MaterializedCte(MaterializedCtePlan::Cte(ref nested))
596+
if nested.id == id =>
597+
{
598+
Ok(Transformed::new(node, false, TreeNodeRecursion::Jump))
599+
}
600+
LogicalPlan::MaterializedCte(MaterializedCtePlan::Scan(scan))
601+
if scan.id == id =>
602+
{
603+
Ok(Transformed::yes(LogicalPlan::MaterializedCte(
604+
MaterializedCtePlan::Scan(scan.with_body_columns(&kept)?),
605+
)))
606+
}
607+
_ => Ok(Transformed::no(node)),
608+
})?
609+
.data;
610+
transformed = true;
611+
}
612+
613+
// All the columns that the body has now are necessary.
614+
let body_indices = RequiredIndices::new_for_all_exprs(&body);
615+
let body = optimize_projections(body, config, body_indices)?;
616+
transformed |= body.transformed;
617+
Ok(Transformed::new_transformed(
618+
LogicalPlan::MaterializedCte(MaterializedCtePlan::Cte(MaterializedCte::try_new(
619+
id,
620+
name,
621+
Arc::new(body.data),
622+
Arc::new(continuation),
623+
)?)),
624+
transformed,
625+
))
626+
}
627+
523628
/// Optimizes uncorrelated subquery plans embedded in expressions of the given
524629
/// plan node (e.g., `Expr::ScalarSubquery`). `map_children` only visits direct
525630
/// plan inputs, so subqueries must be handled separately.
@@ -940,8 +1045,9 @@ mod tests {
9401045
};
9411046
use datafusion_expr::ExprFunctionExt;
9421047
use datafusion_expr::{
943-
BinaryExpr, Expr, Extension, Like, LogicalPlan, Operator, Projection,
944-
UserDefinedLogicalNodeCore, WindowFunctionDefinition, binary_expr,
1048+
BinaryExpr, Expr, Extension, Like, LogicalPlan, MaterializedCte,
1049+
MaterializedCteId, MaterializedCtePlan, MaterializedCteScan, Operator,
1050+
Projection, UserDefinedLogicalNodeCore, WindowFunctionDefinition, binary_expr,
9451051
build_join_schema,
9461052
builder::table_scan_with_filters,
9471053
col,
@@ -2549,6 +2655,101 @@ mod tests {
25492655
)
25502656
}
25512657

2658+
/// `WITH w AS MATERIALIZED (test), x AS MATERIALIZED (SELECT a, b FROM w)
2659+
/// SELECT a FROM x UNION ALL SELECT c FROM w`
2660+
fn nested_materialized_ctes() -> Result<LogicalPlan> {
2661+
let w = MaterializedCteId::next();
2662+
let x = MaterializedCteId::next();
2663+
let body_w = test_table_scan()?;
2664+
let scan_w = LogicalPlan::MaterializedCte(MaterializedCtePlan::Scan(
2665+
MaterializedCteScan::new(w, "w", Arc::clone(body_w.schema())),
2666+
));
2667+
let body_x = LogicalPlanBuilder::from(scan_w.clone())
2668+
.project(vec![col("a"), col("b")])?
2669+
.build()?;
2670+
let scan_x = LogicalPlan::MaterializedCte(MaterializedCtePlan::Scan(
2671+
MaterializedCteScan::new(x, "x", Arc::clone(body_x.schema())),
2672+
));
2673+
let continuation = LogicalPlanBuilder::from(scan_x)
2674+
.project(vec![col("a")])?
2675+
.union(
2676+
LogicalPlanBuilder::from(scan_w)
2677+
.project(vec![col("c")])?
2678+
.build()?,
2679+
)?
2680+
.build()?;
2681+
let inner = LogicalPlan::MaterializedCte(MaterializedCtePlan::Cte(
2682+
MaterializedCte::try_new(x, "x", Arc::new(body_x), Arc::new(continuation))?,
2683+
));
2684+
Ok(LogicalPlan::MaterializedCte(MaterializedCtePlan::Cte(
2685+
MaterializedCte::try_new(w, "w", Arc::new(body_w), Arc::new(inner))?,
2686+
)))
2687+
}
2688+
2689+
/// The body of `w` keeps the columns that its scan in the body of `x` and
2690+
/// its scan in the main query read. The body of `x` keeps `a` only, so
2691+
/// `w` does not keep `b`.
2692+
#[test]
2693+
fn materialized_cte_body_keeps_the_columns_that_the_scans_read() -> Result<()> {
2694+
let plan = nested_materialized_ctes()?;
2695+
assert_optimized_plan_equal!(
2696+
plan,
2697+
@r"
2698+
MaterializedCte: name=w
2699+
TableScan: test projection=[a, c]
2700+
MaterializedCte: name=x
2701+
MaterializedCteScan: name=w projection=[a]
2702+
Union
2703+
MaterializedCteScan: name=x
2704+
MaterializedCteScan: name=w projection=[c]
2705+
"
2706+
)
2707+
}
2708+
2709+
#[test]
2710+
fn materialized_cte_pruning_is_idempotent() -> Result<()> {
2711+
let once = optimize(nested_materialized_ctes()?)?;
2712+
let twice = optimize(once.clone())?;
2713+
assert_eq!(once, twice);
2714+
// The checks of `try_new` pass for the pruned plan.
2715+
let LogicalPlan::MaterializedCte(MaterializedCtePlan::Cte(cte)) = &twice else {
2716+
panic!("expected a MaterializedCte, got {twice}");
2717+
};
2718+
MaterializedCte::try_new(
2719+
cte.id(),
2720+
cte.name(),
2721+
Arc::clone(cte.body()),
2722+
Arc::clone(cte.continuation()),
2723+
)?;
2724+
Ok(())
2725+
}
2726+
2727+
/// A scan that needs no column keeps the row count: the body keeps its
2728+
/// first column.
2729+
#[test]
2730+
fn materialized_cte_scan_without_columns() -> Result<()> {
2731+
let id = MaterializedCteId::next();
2732+
let body = test_table_scan()?;
2733+
let scan = LogicalPlan::MaterializedCte(MaterializedCtePlan::Scan(
2734+
MaterializedCteScan::new(id, "w", Arc::clone(body.schema())),
2735+
));
2736+
let continuation = LogicalPlanBuilder::from(scan)
2737+
.aggregate(Vec::<Expr>::new(), vec![count(lit(1))])?
2738+
.build()?;
2739+
let plan = LogicalPlan::MaterializedCte(MaterializedCtePlan::Cte(
2740+
MaterializedCte::try_new(id, "w", Arc::new(body), Arc::new(continuation))?,
2741+
));
2742+
assert_optimized_plan_equal!(
2743+
plan,
2744+
@r"
2745+
MaterializedCte: name=w
2746+
TableScan: test projection=[a]
2747+
Aggregate: groupBy=[[]], aggr=[[count(Int32(1))]]
2748+
MaterializedCteScan: name=w projection=[]
2749+
"
2750+
)
2751+
}
2752+
25522753
fn observe(_plan: &LogicalPlan, _rule: &dyn OptimizerRule) {}
25532754

25542755
fn optimize(plan: LogicalPlan) -> Result<LogicalPlan> {

0 commit comments

Comments
 (0)