Skip to content

Commit 92da7a4

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 985bbbf commit 92da7a4

7 files changed

Lines changed: 991 additions & 65 deletions

File tree

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 16 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -388,8 +388,13 @@ impl MaterializedCteBinder {
388388
}
389389
return internal_err!("MaterializedCteScanExec {} has no CTE", scan.id());
390390
};
391-
let bound =
392-
(bind && !scan.is_bound()).then(|| scan.bind(Arc::clone(cte.buffer())));
391+
let bound = if bind && !scan.is_bound() {
392+
// The scan reads the batches of the body by position.
393+
scan.check_body_schema(&cte.body().schema())?;
394+
Some(scan.bind(Arc::clone(cte.buffer())))
395+
} else {
396+
None
397+
};
393398
let scan = bound.as_ref().unwrap_or(scan);
394399
let scan = match self.body_statistics(scan.id())? {
395400
Some(statistics) => scan.with_body_statistics(statistics),
@@ -891,12 +896,15 @@ impl DefaultPhysicalPlanner {
891896

892897
LogicalPlan::MaterializedCte(MaterializedCtePlan::Scan(scan)) => {
893898
// Unbound until `bind_materialized_cte_scans` runs on the whole plan.
894-
Arc::new(MaterializedCteScanExec::new(
895-
scan.id.as_u64(),
896-
&scan.name,
897-
Arc::clone(scan.schema.inner()),
898-
session_state.config().target_partitions(),
899-
))
899+
Arc::new(
900+
MaterializedCteScanExec::new(
901+
scan.id.as_u64(),
902+
&scan.name,
903+
Arc::clone(scan.schema.inner()),
904+
session_state.config().target_partitions(),
905+
)
906+
.with_projection(scan.projection.clone()),
907+
)
900908
}
901909

902910
// 1 Child

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

Lines changed: 238 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -24,9 +24,13 @@
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
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

@@ -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)]
8896
pub 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)]
196204
pub 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

205220
impl 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.
262379
impl 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

Comments
 (0)