@@ -42,13 +42,15 @@ use datafusion_common::{
4242use datafusion_expr:: expr:: Alias ;
4343use datafusion_expr:: utils:: passthrough_field_index;
4444use 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
4949use crate :: optimize_projections:: required_indices:: RequiredIndices ;
5050use 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