2424//! as cases of [`MaterializedCtePlan`]. The body is therefore optimized and executed once, and
2525//! the scans read its buffered output.
2626//!
27- //! The scans are leaves, so filters and projections of one reference are not
28- //! pushed into the shared body. This is the same optimization fence that
29- //! PostgreSQL applies to `MATERIALIZED` CTEs.
27+ //! The scans are leaves, so the filters of one reference are not pushed into
28+ //! the shared body. This is the same optimization fence that PostgreSQL
29+ //! applies to `MATERIALIZED` CTEs.
30+ //!
31+ //! A scan can read a subset of the columns of the body (see
32+ //! [`MaterializedCteScan::projection`]). The optimizer removes from the body
33+ //! the columns that no scan reads.
3034
3135use std:: cmp:: Ordering ;
3236use std:: fmt;
@@ -35,7 +39,9 @@ use std::sync::Arc;
3539use std:: sync:: atomic:: { AtomicU64 , Ordering as AtomicOrdering } ;
3640
3741use datafusion_common:: tree_node:: TreeNodeRecursion ;
38- use datafusion_common:: { DFSchemaRef , Result } ;
42+ use datafusion_common:: {
43+ DFSchema , DFSchemaRef , Result , internal_datafusion_err, internal_err,
44+ } ;
3945
4046use crate :: LogicalPlan ;
4147
@@ -81,8 +87,10 @@ pub enum MaterializedCtePlan {
8187/// The node has two inputs with different roles, in this order:
8288///
8389/// 1. `cte`: the body of the CTE. It is shared by all the scans, so a rule
84- /// must not change its schema, and must not push into it a filter, limit
85- /// or projection that belongs to one scan only.
90+ /// must not push into it a filter, limit or projection that belongs to one
91+ /// scan only. A rule that changes its schema must also change the
92+ /// [`projection`](MaterializedCteScan::projection) of every scan, because a
93+ /// scan reads the columns of the body by position.
8694/// 2. `continuation`: the query that declared the CTE.
8795#[ derive( Debug , Clone , PartialEq , Eq , Hash ) ]
8896pub struct MaterializedCte {
@@ -100,7 +108,8 @@ impl MaterializedCte {
100108 /// Create a new node.
101109 ///
102110 /// Returns an error if a scan of this CTE in `continuation` (also in a
103- /// subquery expression) does not have the column names and types of `cte`.
111+ /// subquery expression) does not have the names and types of the columns
112+ /// of `cte` that it reads.
104113 pub fn try_new (
105114 id : MaterializedCteId ,
106115 name : impl Into < String > ,
@@ -109,8 +118,7 @@ impl MaterializedCte {
109118 ) -> Result < Self > {
110119 let name = name. into ( ) ;
111120 for scan in MaterializedCteScan :: find_in ( & continuation, id) ? {
112- scan. schema
113- . has_equivalent_names_and_types ( cte. schema ( ) )
121+ scan. check_body_schema ( cte. schema ( ) )
114122 . map_err ( |e| {
115123 e. context ( format ! (
116124 "A scan of the materialized CTE {name} does not have the schema of the CTE"
@@ -190,20 +198,28 @@ impl PartialOrd for MaterializedCte {
190198
191199/// Reads the buffered output of the [`MaterializedCte`] with the same `id`.
192200///
193- /// This is a leaf. Its schema is the schema of the CTE body and is fixed when
194- /// the scan is created .
201+ /// This is a leaf. It outputs all the columns of the CTE body, or the columns
202+ /// that `projection` selects .
195203#[ derive( Debug , Clone , PartialEq , Eq , Hash ) ]
196204pub struct MaterializedCteScan {
197205 /// The id of the [`MaterializedCte`] that this scan reads
198206 pub id : MaterializedCteId ,
199207 /// Name of the CTE, used for display and error messages only
200208 pub name : String ,
201- /// The schema of the CTE body
209+ /// The schema of this scan: the columns of the CTE body that
210+ /// `projection` selects
202211 pub schema : DFSchemaRef ,
212+ /// The indexes of the columns of the CTE body that this scan outputs, in
213+ /// output order. `None` means all the columns, in the order of the body.
214+ ///
215+ /// The indexes refer to the schema of the body of the [`MaterializedCte`]
216+ /// with the same id, and the scan reads the buffered batches by position.
217+ pub projection : Option < Vec < usize > > ,
203218}
204219
205220impl MaterializedCteScan {
206- /// Create a scan of the CTE `id`, whose body has the schema `schema`.
221+ /// Create a scan of all the columns of the CTE `id`, whose body has the
222+ /// schema `schema`.
207223 pub fn new (
208224 id : MaterializedCteId ,
209225 name : impl Into < String > ,
@@ -213,6 +229,7 @@ impl MaterializedCteScan {
213229 id,
214230 name : name. into ( ) ,
215231 schema,
232+ projection : None ,
216233 }
217234 }
218235
@@ -231,6 +248,90 @@ impl MaterializedCteScan {
231248 & self . schema
232249 }
233250
251+ /// The indexes of the columns of the CTE body that this scan outputs.
252+ /// `None` means all the columns.
253+ pub fn projection ( & self ) -> Option < & [ usize ] > {
254+ self . projection . as_deref ( )
255+ }
256+
257+ /// Return a scan that outputs only the columns `indices` of this scan.
258+ ///
259+ /// The indexes refer to the schema of this scan, not to the schema of the
260+ /// CTE body.
261+ pub fn with_projection ( & self , indices : & [ usize ] ) -> Result < Self > {
262+ let len = self . schema . fields ( ) . len ( ) ;
263+ if let Some ( index) = indices. iter ( ) . find ( |index| * * index >= len) {
264+ return internal_err ! (
265+ "Column {index} is not in the scan of the materialized CTE {}, which has {len} columns" ,
266+ self . name
267+ ) ;
268+ }
269+ if indices. iter ( ) . copied ( ) . eq ( 0 ..len) {
270+ return Ok ( self . clone ( ) ) ;
271+ }
272+ let projection = match & self . projection {
273+ Some ( projection) => indices. iter ( ) . map ( |index| projection[ * index] ) . collect ( ) ,
274+ None => indices. to_vec ( ) ,
275+ } ;
276+ Ok ( Self {
277+ id : self . id ,
278+ name : self . name . clone ( ) ,
279+ schema : Arc :: new ( project_schema ( & self . schema , indices) ?) ,
280+ projection : Some ( projection) ,
281+ } )
282+ }
283+
284+ /// Return a scan with the same output, for a CTE body that keeps only its
285+ /// columns `kept`, in this order.
286+ ///
287+ /// Returns an error if this scan reads a column that is not in `kept`.
288+ pub fn with_body_columns ( & self , kept : & [ usize ] ) -> Result < Self > {
289+ let old: Vec < usize > = match & self . projection {
290+ Some ( projection) => projection. clone ( ) ,
291+ // The scan reads all the columns, so `kept` must be all of them.
292+ None => ( 0 ..self . schema . fields ( ) . len ( ) ) . collect ( ) ,
293+ } ;
294+ let projection = old
295+ . iter ( )
296+ . map ( |index| {
297+ kept. iter ( ) . position ( |k| k == index) . ok_or_else ( || {
298+ internal_datafusion_err ! (
299+ "A scan of the materialized CTE {} reads the column {index}, which was removed from the CTE" ,
300+ self . name
301+ )
302+ } )
303+ } )
304+ . collect :: < Result < Vec < _ > > > ( ) ?;
305+ // A scan that reads all the columns in order has no projection.
306+ let projection =
307+ ( !projection. iter ( ) . copied ( ) . eq ( 0 ..kept. len ( ) ) ) . then_some ( projection) ;
308+ Ok ( Self {
309+ id : self . id ,
310+ name : self . name . clone ( ) ,
311+ schema : Arc :: clone ( & self . schema ) ,
312+ projection,
313+ } )
314+ }
315+
316+ /// Check that this scan has the names and types of the columns that it
317+ /// reads from a CTE body with the schema `body`.
318+ pub fn check_body_schema ( & self , body : & DFSchema ) -> Result < ( ) > {
319+ match & self . projection {
320+ None => self . schema . has_equivalent_names_and_types ( body) ,
321+ Some ( projection) => {
322+ let len = body. fields ( ) . len ( ) ;
323+ if let Some ( index) = projection. iter ( ) . find ( |index| * * index >= len) {
324+ return internal_err ! (
325+ "A scan of the materialized CTE {} reads the column {index}, but the CTE has {len} columns" ,
326+ self . name
327+ ) ;
328+ }
329+ self . schema
330+ . has_equivalent_names_and_types ( & project_schema ( body, projection) ?)
331+ }
332+ }
333+ }
334+
234335 /// Return a copy of each scan of the CTE `id` in `plan`, also in subquery
235336 /// expressions.
236337 ///
@@ -257,8 +358,24 @@ impl MaterializedCteScan {
257358 }
258359}
259360
361+ /// The columns `indices` of `schema`, with their qualifiers.
362+ fn project_schema ( schema : & DFSchema , indices : & [ usize ] ) -> Result < DFSchema > {
363+ let fields = indices
364+ . iter ( )
365+ . map ( |index| {
366+ let ( qualifier, field) = schema. qualified_field ( * index) ;
367+ ( qualifier. cloned ( ) , Arc :: clone ( field) )
368+ } )
369+ . collect ( ) ;
370+ let dependencies = schema
371+ . functional_dependencies ( )
372+ . project_functional_dependencies ( indices, indices. len ( ) ) ;
373+ DFSchema :: new_with_metadata ( fields, schema. metadata ( ) . clone ( ) ) ?
374+ . with_functional_dependencies ( dependencies)
375+ }
376+
260377/// Orders by `id` and `name`. Scans with the same `id` and `name` but a
261- /// different `schema` are not comparable.
378+ /// different `schema` or `projection` are not comparable.
262379impl PartialOrd for MaterializedCteScan {
263380 fn partial_cmp ( & self , other : & Self ) -> Option < Ordering > {
264381 match self
@@ -375,6 +492,113 @@ mod tests {
375492 Ok ( ( ) )
376493 }
377494
495+ fn wide_schema ( ) -> DFSchemaRef {
496+ let schema = Schema :: new ( vec ! [
497+ Field :: new( "a" , DataType :: Int32 , true ) ,
498+ Field :: new( "b" , DataType :: Utf8 , true ) ,
499+ Field :: new( "c" , DataType :: Float64 , true ) ,
500+ Field :: new( "d" , DataType :: Boolean , true ) ,
501+ ] ) ;
502+ Arc :: new ( DFSchema :: try_from_qualified_schema ( "c" , & schema) . unwrap ( ) )
503+ }
504+
505+ fn names ( scan : & MaterializedCteScan ) -> Vec < String > {
506+ scan. schema ( )
507+ . columns ( )
508+ . iter ( )
509+ . map ( |c| c. flat_name ( ) )
510+ . collect ( )
511+ }
512+
513+ #[ test]
514+ fn scan_projection_refers_to_the_body ( ) -> Result < ( ) > {
515+ let id = MaterializedCteId :: next ( ) ;
516+ let body = wide_schema ( ) ;
517+ let all = MaterializedCteScan :: new ( id, "c" , Arc :: clone ( & body) ) ;
518+ assert_eq ! ( all. projection( ) , None ) ;
519+ all. check_body_schema ( & body) ?;
520+
521+ // All the columns in order is not a projection.
522+ assert_eq ! ( all. with_projection( & [ 0 , 1 , 2 , 3 ] ) ?, all) ;
523+ assert ! ( all. with_projection( & [ 4 ] ) . is_err( ) ) ;
524+
525+ let bcd = all. with_projection ( & [ 1 , 2 , 3 ] ) ?;
526+ assert_eq ! ( bcd. projection( ) , Some ( [ 1 , 2 , 3 ] . as_slice( ) ) ) ;
527+ assert_eq ! ( names( & bcd) , [ "c.b" , "c.c" , "c.d" ] ) ;
528+ bcd. check_body_schema ( & body) ?;
529+
530+ // The indexes of a second projection refer to the output of the scan.
531+ let bd = bcd. with_projection ( & [ 0 , 2 ] ) ?;
532+ assert_eq ! ( bd. projection( ) , Some ( [ 1 , 3 ] . as_slice( ) ) ) ;
533+ assert_eq ! ( names( & bd) , [ "c.b" , "c.d" ] ) ;
534+ bd. check_body_schema ( & body) ?;
535+
536+ let none = bd. with_projection ( & [ ] ) ?;
537+ assert_eq ! ( none. projection( ) , Some ( [ ] . as_slice( ) ) ) ;
538+ assert ! ( none. schema( ) . fields( ) . is_empty( ) ) ;
539+ none. check_body_schema ( & body) ?;
540+
541+ // The body keeps `b`, `c` and `d`: the output of the scans is the
542+ // same, and the indexes change.
543+ let kept = [ 1 , 2 , 3 ] ;
544+ let new_body = project_schema ( & body, & kept) ?;
545+ let new_bd = bd. with_body_columns ( & kept) ?;
546+ assert_eq ! ( new_bd. projection( ) , Some ( [ 0 , 2 ] . as_slice( ) ) ) ;
547+ assert_eq ! ( new_bd. schema( ) , bd. schema( ) ) ;
548+ new_bd. check_body_schema ( & new_body) ?;
549+ assert ! ( bd. check_body_schema( & new_body) . is_err( ) ) ;
550+
551+ let new_bcd = bcd. with_body_columns ( & kept) ?;
552+ assert_eq ! ( new_bcd. projection( ) , None ) ;
553+ new_bcd. check_body_schema ( & new_body) ?;
554+
555+ let new_none = none. with_body_columns ( & kept) ?;
556+ assert_eq ! ( new_none. projection( ) , Some ( [ ] . as_slice( ) ) ) ;
557+
558+ // A scan cannot lose a column that it reads.
559+ assert ! ( all. with_body_columns( & kept) . is_err( ) ) ;
560+ assert ! ( bd. with_body_columns( & [ 1 , 2 ] ) . is_err( ) ) ;
561+ Ok ( ( ) )
562+ }
563+
564+ #[ test]
565+ fn try_new_checks_the_projection_of_the_scans ( ) -> Result < ( ) > {
566+ let id = MaterializedCteId :: next ( ) ;
567+ let body = Arc :: new ( LogicalPlan :: EmptyRelation ( EmptyRelation {
568+ produce_one_row : false ,
569+ schema : wide_schema ( ) ,
570+ } ) ) ;
571+ let scan = MaterializedCteScan :: new ( id, "c" , wide_schema ( ) ) ;
572+ let narrow = scan. with_projection ( & [ 1 , 3 ] ) ?;
573+ let plan =
574+ LogicalPlan :: MaterializedCte ( MaterializedCtePlan :: Scan ( narrow. clone ( ) ) ) ;
575+ assert_eq ! (
576+ plan. display_indent( ) . to_string( ) ,
577+ "MaterializedCteScan: name=c projection=[b, d]"
578+ ) ;
579+ MaterializedCte :: try_new ( id, "c" , Arc :: clone ( & body) , Arc :: new ( plan) ) ?;
580+
581+ // The projection does not select the columns of the scan schema.
582+ let wrong = MaterializedCteScan {
583+ projection : Some ( vec ! [ 0 , 1 ] ) ,
584+ ..narrow. clone ( )
585+ } ;
586+ let plan = Arc :: new ( LogicalPlan :: MaterializedCte ( MaterializedCtePlan :: Scan (
587+ wrong,
588+ ) ) ) ;
589+ assert ! ( MaterializedCte :: try_new( id, "c" , Arc :: clone( & body) , plan) . is_err( ) ) ;
590+
591+ let out_of_range = MaterializedCteScan {
592+ projection : Some ( vec ! [ 1 , 9 ] ) ,
593+ ..narrow
594+ } ;
595+ let plan = Arc :: new ( LogicalPlan :: MaterializedCte ( MaterializedCtePlan :: Scan (
596+ out_of_range,
597+ ) ) ) ;
598+ assert ! ( MaterializedCte :: try_new( id, "c" , body, plan) . is_err( ) ) ;
599+ Ok ( ( ) )
600+ }
601+
378602 #[ test]
379603 fn find_in_looks_in_subqueries_and_stops_at_the_same_cte ( ) -> Result < ( ) > {
380604 let id = MaterializedCteId :: next ( ) ;
0 commit comments