Skip to content

Commit bafd6d2

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 1b581b0 commit bafd6d2

7 files changed

Lines changed: 983 additions & 62 deletions

File tree

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 16 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -330,7 +330,10 @@ fn bind_materialized_cte_scans(
330330
plan.apply(|node| {
331331
if let Some(cte) = node.downcast_ref::<MaterializedCteExec>()
332332
&& buffers
333-
.insert(cte.buffer().id(), Arc::clone(cte.buffer()))
333+
.insert(
334+
cte.buffer().id(),
335+
(Arc::clone(cte.buffer()), cte.children()[0].schema()),
336+
)
334337
.is_some()
335338
{
336339
return internal_err!(
@@ -350,9 +353,11 @@ fn bind_materialized_cte_scans(
350353
if scan.is_bound() {
351354
return Ok(Transformed::no(node));
352355
}
353-
let Some(buffer) = buffers.get(&scan.id()) else {
356+
let Some((buffer, body_schema)) = buffers.get(&scan.id()) else {
354357
return internal_err!("MaterializedCteScanExec {} has no CTE", scan.id());
355358
};
359+
// The scan reads the batches of the body by position.
360+
scan.check_body_schema(body_schema)?;
356361
Ok(Transformed::yes(
357362
Arc::new(scan.bind(Arc::clone(buffer))) as Arc<dyn ExecutionPlan>
358363
))
@@ -813,12 +818,15 @@ impl DefaultPhysicalPlanner {
813818

814819
LogicalPlan::MaterializedCteScan(scan) => {
815820
// Unbound until `bind_materialized_cte_scans` runs on the whole plan.
816-
Arc::new(MaterializedCteScanExec::new(
817-
scan.id.as_u64(),
818-
&scan.name,
819-
Arc::clone(scan.schema.inner()),
820-
session_state.config().target_partitions(),
821-
))
821+
Arc::new(
822+
MaterializedCteScanExec::new(
823+
scan.id.as_u64(),
824+
&scan.name,
825+
Arc::clone(scan.schema.inner()),
826+
session_state.config().target_partitions(),
827+
)
828+
.with_projection(scan.projection.clone()),
829+
)
822830
}
823831

824832
// 1 Child

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

Lines changed: 233 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -24,9 +24,13 @@
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
3135
use std::cmp::Ordering;
3236
use std::fmt;
@@ -35,7 +39,9 @@ use std::sync::Arc;
3539
use std::sync::atomic::{AtomicU64, Ordering as AtomicOrdering};
3640

3741
use 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

4046
use 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)]
7987
pub 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)]
187195
pub 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

196211
impl 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.
249366
impl 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

Comments
 (0)