2424//! the continuation. 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
@@ -72,8 +78,10 @@ impl fmt::Display for MaterializedCteId {
7278/// The node has two inputs with different roles, in this order:
7379///
7480/// 1. `cte`: the body of the CTE. It is shared by all the scans, so a rule
75- /// must not change its schema, and must not push into it a filter, limit
76- /// or projection that belongs to one scan only.
81+ /// must not push into it a filter, limit or projection that belongs to one
82+ /// scan only. A rule that changes its schema must also change the
83+ /// [`projection`](MaterializedCteScan::projection) of every scan, because a
84+ /// scan reads the columns of the body by position.
7785/// 2. `continuation`: the query that declared the CTE.
7886#[ derive( Debug , Clone , PartialEq , Eq , Hash ) ]
7987pub struct MaterializedCte {
@@ -91,7 +99,8 @@ impl MaterializedCte {
9199 /// Create a new node.
92100 ///
93101 /// Returns an error if a scan of this CTE in `continuation` (also in a
94- /// subquery expression) does not have the column names and types of `cte`.
102+ /// subquery expression) does not have the names and types of the columns
103+ /// of `cte` that it reads.
95104 pub fn try_new (
96105 id : MaterializedCteId ,
97106 name : impl Into < String > ,
@@ -100,8 +109,7 @@ impl MaterializedCte {
100109 ) -> Result < Self > {
101110 let name = name. into ( ) ;
102111 for scan in MaterializedCteScan :: find_in ( & continuation, id) ? {
103- scan. schema
104- . has_equivalent_names_and_types ( cte. schema ( ) )
112+ scan. check_body_schema ( cte. schema ( ) )
105113 . map_err ( |e| {
106114 e. context ( format ! (
107115 "A scan of the materialized CTE {name} does not have the schema of the CTE"
@@ -181,20 +189,28 @@ impl PartialOrd for MaterializedCte {
181189
182190/// Reads the buffered output of the [`MaterializedCte`] with the same `id`.
183191///
184- /// This is a leaf. Its schema is the schema of the CTE body and is fixed when
185- /// the scan is created .
192+ /// This is a leaf. It outputs all the columns of the CTE body, or the columns
193+ /// that `projection` selects .
186194#[ derive( Debug , Clone , PartialEq , Eq , Hash ) ]
187195pub struct MaterializedCteScan {
188196 /// The id of the [`MaterializedCte`] that this scan reads
189197 pub id : MaterializedCteId ,
190198 /// Name of the CTE, used for display and error messages only
191199 pub name : String ,
192- /// The schema of the CTE body
200+ /// The schema of this scan: the columns of the CTE body that
201+ /// `projection` selects
193202 pub schema : DFSchemaRef ,
203+ /// The indexes of the columns of the CTE body that this scan outputs, in
204+ /// output order. `None` means all the columns, in the order of the body.
205+ ///
206+ /// The indexes refer to the schema of the body of the [`MaterializedCte`]
207+ /// with the same id, and the scan reads the buffered batches by position.
208+ pub projection : Option < Vec < usize > > ,
194209}
195210
196211impl MaterializedCteScan {
197- /// Create a scan of the CTE `id`, whose body has the schema `schema`.
212+ /// Create a scan of all the columns of the CTE `id`, whose body has the
213+ /// schema `schema`.
198214 pub fn new (
199215 id : MaterializedCteId ,
200216 name : impl Into < String > ,
@@ -204,6 +220,7 @@ impl MaterializedCteScan {
204220 id,
205221 name : name. into ( ) ,
206222 schema,
223+ projection : None ,
207224 }
208225 }
209226
@@ -222,6 +239,90 @@ impl MaterializedCteScan {
222239 & self . schema
223240 }
224241
242+ /// The indexes of the columns of the CTE body that this scan outputs.
243+ /// `None` means all the columns.
244+ pub fn projection ( & self ) -> Option < & [ usize ] > {
245+ self . projection . as_deref ( )
246+ }
247+
248+ /// Return a scan that outputs only the columns `indices` of this scan.
249+ ///
250+ /// The indexes refer to the schema of this scan, not to the schema of the
251+ /// CTE body.
252+ pub fn with_projection ( & self , indices : & [ usize ] ) -> Result < Self > {
253+ let len = self . schema . fields ( ) . len ( ) ;
254+ if let Some ( index) = indices. iter ( ) . find ( |index| * * index >= len) {
255+ return internal_err ! (
256+ "Column {index} is not in the scan of the materialized CTE {}, which has {len} columns" ,
257+ self . name
258+ ) ;
259+ }
260+ if indices. iter ( ) . copied ( ) . eq ( 0 ..len) {
261+ return Ok ( self . clone ( ) ) ;
262+ }
263+ let projection = match & self . projection {
264+ Some ( projection) => indices. iter ( ) . map ( |index| projection[ * index] ) . collect ( ) ,
265+ None => indices. to_vec ( ) ,
266+ } ;
267+ Ok ( Self {
268+ id : self . id ,
269+ name : self . name . clone ( ) ,
270+ schema : Arc :: new ( project_schema ( & self . schema , indices) ?) ,
271+ projection : Some ( projection) ,
272+ } )
273+ }
274+
275+ /// Return a scan with the same output, for a CTE body that keeps only its
276+ /// columns `kept`, in this order.
277+ ///
278+ /// Returns an error if this scan reads a column that is not in `kept`.
279+ pub fn with_body_columns ( & self , kept : & [ usize ] ) -> Result < Self > {
280+ let old: Vec < usize > = match & self . projection {
281+ Some ( projection) => projection. clone ( ) ,
282+ // The scan reads all the columns, so `kept` must be all of them.
283+ None => ( 0 ..self . schema . fields ( ) . len ( ) ) . collect ( ) ,
284+ } ;
285+ let projection = old
286+ . iter ( )
287+ . map ( |index| {
288+ kept. iter ( ) . position ( |k| k == index) . ok_or_else ( || {
289+ internal_datafusion_err ! (
290+ "A scan of the materialized CTE {} reads the column {index}, which was removed from the CTE" ,
291+ self . name
292+ )
293+ } )
294+ } )
295+ . collect :: < Result < Vec < _ > > > ( ) ?;
296+ // A scan that reads all the columns in order has no projection.
297+ let projection =
298+ ( !projection. iter ( ) . copied ( ) . eq ( 0 ..kept. len ( ) ) ) . then_some ( projection) ;
299+ Ok ( Self {
300+ id : self . id ,
301+ name : self . name . clone ( ) ,
302+ schema : Arc :: clone ( & self . schema ) ,
303+ projection,
304+ } )
305+ }
306+
307+ /// Check that this scan has the names and types of the columns that it
308+ /// reads from a CTE body with the schema `body`.
309+ pub fn check_body_schema ( & self , body : & DFSchema ) -> Result < ( ) > {
310+ match & self . projection {
311+ None => self . schema . has_equivalent_names_and_types ( body) ,
312+ Some ( projection) => {
313+ let len = body. fields ( ) . len ( ) ;
314+ if let Some ( index) = projection. iter ( ) . find ( |index| * * index >= len) {
315+ return internal_err ! (
316+ "A scan of the materialized CTE {} reads the column {index}, but the CTE has {len} columns" ,
317+ self . name
318+ ) ;
319+ }
320+ self . schema
321+ . has_equivalent_names_and_types ( & project_schema ( body, projection) ?)
322+ }
323+ }
324+ }
325+
225326 /// Return a copy of each scan of the CTE `id` in `plan`, also in subquery
226327 /// expressions.
227328 ///
@@ -244,8 +345,24 @@ impl MaterializedCteScan {
244345 }
245346}
246347
348+ /// The columns `indices` of `schema`, with their qualifiers.
349+ fn project_schema ( schema : & DFSchema , indices : & [ usize ] ) -> Result < DFSchema > {
350+ let fields = indices
351+ . iter ( )
352+ . map ( |index| {
353+ let ( qualifier, field) = schema. qualified_field ( * index) ;
354+ ( qualifier. cloned ( ) , Arc :: clone ( field) )
355+ } )
356+ . collect ( ) ;
357+ let dependencies = schema
358+ . functional_dependencies ( )
359+ . project_functional_dependencies ( indices, indices. len ( ) ) ;
360+ DFSchema :: new_with_metadata ( fields, schema. metadata ( ) . clone ( ) ) ?
361+ . with_functional_dependencies ( dependencies)
362+ }
363+
247364/// Orders by `id` and `name`. Scans with the same `id` and `name` but a
248- /// different `schema` are not comparable.
365+ /// different `schema` or `projection` are not comparable.
249366impl PartialOrd for MaterializedCteScan {
250367 fn partial_cmp ( & self , other : & Self ) -> Option < Ordering > {
251368 match self
@@ -362,6 +479,108 @@ mod tests {
362479 Ok ( ( ) )
363480 }
364481
482+ fn wide_schema ( ) -> DFSchemaRef {
483+ let schema = Schema :: new ( vec ! [
484+ Field :: new( "a" , DataType :: Int32 , true ) ,
485+ Field :: new( "b" , DataType :: Utf8 , true ) ,
486+ Field :: new( "c" , DataType :: Float64 , true ) ,
487+ Field :: new( "d" , DataType :: Boolean , true ) ,
488+ ] ) ;
489+ Arc :: new ( DFSchema :: try_from_qualified_schema ( "c" , & schema) . unwrap ( ) )
490+ }
491+
492+ fn names ( scan : & MaterializedCteScan ) -> Vec < String > {
493+ scan. schema ( )
494+ . columns ( )
495+ . iter ( )
496+ . map ( |c| c. flat_name ( ) )
497+ . collect ( )
498+ }
499+
500+ #[ test]
501+ fn scan_projection_refers_to_the_body ( ) -> Result < ( ) > {
502+ let id = MaterializedCteId :: next ( ) ;
503+ let body = wide_schema ( ) ;
504+ let all = MaterializedCteScan :: new ( id, "c" , Arc :: clone ( & body) ) ;
505+ assert_eq ! ( all. projection( ) , None ) ;
506+ all. check_body_schema ( & body) ?;
507+
508+ // All the columns in order is not a projection.
509+ assert_eq ! ( all. with_projection( & [ 0 , 1 , 2 , 3 ] ) ?, all) ;
510+ assert ! ( all. with_projection( & [ 4 ] ) . is_err( ) ) ;
511+
512+ let bcd = all. with_projection ( & [ 1 , 2 , 3 ] ) ?;
513+ assert_eq ! ( bcd. projection( ) , Some ( [ 1 , 2 , 3 ] . as_slice( ) ) ) ;
514+ assert_eq ! ( names( & bcd) , [ "c.b" , "c.c" , "c.d" ] ) ;
515+ bcd. check_body_schema ( & body) ?;
516+
517+ // The indexes of a second projection refer to the output of the scan.
518+ let bd = bcd. with_projection ( & [ 0 , 2 ] ) ?;
519+ assert_eq ! ( bd. projection( ) , Some ( [ 1 , 3 ] . as_slice( ) ) ) ;
520+ assert_eq ! ( names( & bd) , [ "c.b" , "c.d" ] ) ;
521+ bd. check_body_schema ( & body) ?;
522+
523+ let none = bd. with_projection ( & [ ] ) ?;
524+ assert_eq ! ( none. projection( ) , Some ( [ ] . as_slice( ) ) ) ;
525+ assert ! ( none. schema( ) . fields( ) . is_empty( ) ) ;
526+ none. check_body_schema ( & body) ?;
527+
528+ // The body keeps `b`, `c` and `d`: the output of the scans is the
529+ // same, and the indexes change.
530+ let kept = [ 1 , 2 , 3 ] ;
531+ let new_body = project_schema ( & body, & kept) ?;
532+ let new_bd = bd. with_body_columns ( & kept) ?;
533+ assert_eq ! ( new_bd. projection( ) , Some ( [ 0 , 2 ] . as_slice( ) ) ) ;
534+ assert_eq ! ( new_bd. schema( ) , bd. schema( ) ) ;
535+ new_bd. check_body_schema ( & new_body) ?;
536+ assert ! ( bd. check_body_schema( & new_body) . is_err( ) ) ;
537+
538+ let new_bcd = bcd. with_body_columns ( & kept) ?;
539+ assert_eq ! ( new_bcd. projection( ) , None ) ;
540+ new_bcd. check_body_schema ( & new_body) ?;
541+
542+ let new_none = none. with_body_columns ( & kept) ?;
543+ assert_eq ! ( new_none. projection( ) , Some ( [ ] . as_slice( ) ) ) ;
544+
545+ // A scan cannot lose a column that it reads.
546+ assert ! ( all. with_body_columns( & kept) . is_err( ) ) ;
547+ assert ! ( bd. with_body_columns( & [ 1 , 2 ] ) . is_err( ) ) ;
548+ Ok ( ( ) )
549+ }
550+
551+ #[ test]
552+ fn try_new_checks_the_projection_of_the_scans ( ) -> Result < ( ) > {
553+ let id = MaterializedCteId :: next ( ) ;
554+ let body = Arc :: new ( LogicalPlan :: EmptyRelation ( EmptyRelation {
555+ produce_one_row : false ,
556+ schema : wide_schema ( ) ,
557+ } ) ) ;
558+ let scan = MaterializedCteScan :: new ( id, "c" , wide_schema ( ) ) ;
559+ let narrow = scan. with_projection ( & [ 1 , 3 ] ) ?;
560+ let plan = LogicalPlan :: MaterializedCteScan ( narrow. clone ( ) ) ;
561+ assert_eq ! (
562+ plan. display_indent( ) . to_string( ) ,
563+ "MaterializedCteScan: name=c projection=[b, d]"
564+ ) ;
565+ MaterializedCte :: try_new ( id, "c" , Arc :: clone ( & body) , Arc :: new ( plan) ) ?;
566+
567+ // The projection does not select the columns of the scan schema.
568+ let wrong = MaterializedCteScan {
569+ projection : Some ( vec ! [ 0 , 1 ] ) ,
570+ ..narrow. clone ( )
571+ } ;
572+ let plan = Arc :: new ( LogicalPlan :: MaterializedCteScan ( wrong) ) ;
573+ assert ! ( MaterializedCte :: try_new( id, "c" , Arc :: clone( & body) , plan) . is_err( ) ) ;
574+
575+ let out_of_range = MaterializedCteScan {
576+ projection : Some ( vec ! [ 1 , 9 ] ) ,
577+ ..narrow
578+ } ;
579+ let plan = Arc :: new ( LogicalPlan :: MaterializedCteScan ( out_of_range) ) ;
580+ assert ! ( MaterializedCte :: try_new( id, "c" , body, plan) . is_err( ) ) ;
581+ Ok ( ( ) )
582+ }
583+
365584 #[ test]
366585 fn find_in_looks_in_subqueries_and_stops_at_the_same_cte ( ) -> Result < ( ) > {
367586 let id = MaterializedCteId :: next ( ) ;
0 commit comments