Skip to content

Commit 5a5632c

Browse files
committed
feat: support WITH ... AS [NOT] MATERIALIZED CTEs
Plan a MATERIALIZED CTE as a MaterializedCte node (body + continuation) and a MaterializedCteScan leaf per reference. The body runs once, is buffered with memory-pool accounting, spills to disk when a reservation fails, and is replayed by every scan. CTEs without the directive are still inlined.
1 parent 0576a0b commit 5a5632c

8 files changed

Lines changed: 1084 additions & 8 deletions

File tree

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -45,6 +45,9 @@ use crate::physical_plan::joins::{
4545
PartitionMode, SortMergeJoinExec,
4646
};
4747
use crate::physical_plan::limit::{GlobalLimitExec, LocalLimitExec};
48+
use crate::physical_plan::materialized_cte::{
49+
MaterializedCteBuffer, MaterializedCteExec, MaterializedCteScanExec,
50+
};
4851
use crate::physical_plan::projection::{ProjectionExec, ProjectionExpr};
4952
use crate::physical_plan::repartition::RepartitionExec;
5053
use crate::physical_plan::sorts::sort::SortExec;
@@ -216,11 +219,45 @@ impl DefaultPhysicalPlanner {
216219
let plan = self
217220
.create_initial_plan(logical_plan, session_state)
218221
.await?;
222+
let plan = bind_materialized_cte_scans(plan)?;
219223

220224
self.optimize_physical_plan(plan, session_state, |_, _| {})
221225
}
222226
}
223227

228+
/// Point every [`MaterializedCteScanExec`] at the buffer of the
229+
/// [`MaterializedCteExec`] with the same id.
230+
///
231+
/// Scans are planned before the node that owns their CTE, and a scan inside a
232+
/// scalar subquery is planned in a separate subtree, so the binding is done
233+
/// once on the whole initial plan.
234+
fn bind_materialized_cte_scans(
235+
plan: Arc<dyn ExecutionPlan>,
236+
) -> Result<Arc<dyn ExecutionPlan>> {
237+
let mut buffers = HashMap::new();
238+
plan.apply(|node| {
239+
if let Some(cte) = node.downcast_ref::<MaterializedCteExec>() {
240+
buffers.insert(cte.buffer().id(), Arc::clone(cte.buffer()));
241+
}
242+
Ok(TreeNodeRecursion::Continue)
243+
})?;
244+
if buffers.is_empty() {
245+
return Ok(plan);
246+
}
247+
plan.transform_up(|node| {
248+
let Some(scan) = node.downcast_ref::<MaterializedCteScanExec>() else {
249+
return Ok(Transformed::no(node));
250+
};
251+
let Some(buffer) = buffers.get(&scan.id()) else {
252+
return internal_err!("MaterializedCteScanExec {} has no CTE", scan.id());
253+
};
254+
Ok(Transformed::yes(
255+
Arc::new(scan.bind(Arc::clone(buffer))) as Arc<dyn ExecutionPlan>
256+
))
257+
})
258+
.map(|t| t.data)
259+
}
260+
224261
#[derive(Debug)]
225262
struct ExecutionPlanChild {
226263
/// Index needed to order children of parent to ensure consistency with original
@@ -1857,6 +1894,33 @@ impl DefaultPhysicalPlanner {
18571894

18581895
// N Children
18591896
LogicalPlan::Union(_) => UnionExec::try_new(children.vec())?,
1897+
LogicalPlan::Extension(Extension { node })
1898+
if node.as_any().is::<datafusion_expr::MaterializedCte>() =>
1899+
{
1900+
let cte = node
1901+
.as_any()
1902+
.downcast_ref::<datafusion_expr::MaterializedCte>()
1903+
.unwrap();
1904+
let [body, continuation] = children.two()?;
1905+
let buffer =
1906+
Arc::new(MaterializedCteBuffer::new(cte.id.as_u64(), &cte.name));
1907+
Arc::new(MaterializedCteExec::new(body, continuation, buffer))
1908+
}
1909+
LogicalPlan::Extension(Extension { node })
1910+
if node.as_any().is::<datafusion_expr::MaterializedCteScan>() =>
1911+
{
1912+
let scan = node
1913+
.as_any()
1914+
.downcast_ref::<datafusion_expr::MaterializedCteScan>()
1915+
.unwrap();
1916+
// Unbound until `bind_materialized_cte_scans` runs on the whole plan.
1917+
Arc::new(MaterializedCteScanExec::new(
1918+
scan.id.as_u64(),
1919+
&scan.name,
1920+
Arc::clone(scan.schema.inner()),
1921+
session_state.config().target_partitions(),
1922+
))
1923+
}
18601924
LogicalPlan::Extension(Extension { node }) => {
18611925
let mut maybe_plan = None;
18621926
let children = children.vec();
Lines changed: 186 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,186 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! Logical nodes for `WITH x AS MATERIALIZED (...)`.
19+
//!
20+
//! A materialized CTE is planned as one [`MaterializedCte`] node, which owns the
21+
//! CTE body and the rest of the query (the "continuation"), and one
22+
//! [`MaterializedCteScan`] leaf for each reference to the CTE inside the
23+
//! continuation. The body is therefore optimized and executed once, and the
24+
//! scans read its buffered output.
25+
//!
26+
//! The scans are leaves, so filters and projections of one reference are not
27+
//! pushed into the shared body. This is the same optimization fence that
28+
//! PostgreSQL applies to `MATERIALIZED` CTEs.
29+
30+
use std::cmp::Ordering;
31+
use std::fmt;
32+
use std::hash::Hash;
33+
use std::sync::atomic::{AtomicU64, Ordering as AtomicOrdering};
34+
35+
use datafusion_common::{DFSchemaRef, Result, assert_eq_or_internal_err};
36+
37+
use crate::{Expr, LogicalPlan, UserDefinedLogicalNodeCore};
38+
39+
/// Identifies one materialized CTE and binds its scans to it.
40+
///
41+
/// CTE names are not unique (two sibling subqueries can each declare `WITH t`),
42+
/// so the planner allocates a process-unique id.
43+
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
44+
pub struct MaterializedCteId(u64);
45+
46+
impl MaterializedCteId {
47+
/// Allocate a new unique id.
48+
pub fn next() -> Self {
49+
static NEXT: AtomicU64 = AtomicU64::new(0);
50+
Self(NEXT.fetch_add(1, AtomicOrdering::Relaxed))
51+
}
52+
53+
/// The numeric value of this id.
54+
pub fn as_u64(self) -> u64 {
55+
self.0
56+
}
57+
}
58+
59+
impl fmt::Display for MaterializedCteId {
60+
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
61+
write!(f, "{}", self.0)
62+
}
63+
}
64+
65+
/// Computes `cte` once and evaluates `continuation`, in which every
66+
/// [`MaterializedCteScan`] with the same `id` reads the buffered output of
67+
/// `cte`. The output of this node is the output of `continuation`.
68+
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
69+
pub struct MaterializedCte {
70+
pub id: MaterializedCteId,
71+
pub name: String,
72+
pub cte: LogicalPlan,
73+
pub continuation: LogicalPlan,
74+
}
75+
76+
impl PartialOrd for MaterializedCte {
77+
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
78+
match self.id.cmp(&other.id) {
79+
Ordering::Equal => self.name.partial_cmp(&other.name),
80+
ord => Some(ord),
81+
}
82+
}
83+
}
84+
85+
impl UserDefinedLogicalNodeCore for MaterializedCte {
86+
fn name(&self) -> &str {
87+
"MaterializedCte"
88+
}
89+
90+
fn inputs(&self) -> Vec<&LogicalPlan> {
91+
vec![&self.cte, &self.continuation]
92+
}
93+
94+
fn schema(&self) -> &DFSchemaRef {
95+
self.continuation.schema()
96+
}
97+
98+
fn expressions(&self) -> Vec<Expr> {
99+
vec![]
100+
}
101+
102+
fn fmt_for_explain(&self, f: &mut fmt::Formatter) -> fmt::Result {
103+
write!(f, "MaterializedCte: name={}", self.name)
104+
}
105+
106+
fn with_exprs_and_inputs(
107+
&self,
108+
exprs: Vec<Expr>,
109+
mut inputs: Vec<LogicalPlan>,
110+
) -> Result<Self> {
111+
assert_eq_or_internal_err!(exprs.len(), 0, "MaterializedCte takes no exprs");
112+
assert_eq_or_internal_err!(inputs.len(), 2, "MaterializedCte takes 2 inputs");
113+
let continuation = inputs.pop().unwrap();
114+
let cte = inputs.pop().unwrap();
115+
Ok(Self {
116+
id: self.id,
117+
name: self.name.clone(),
118+
cte,
119+
continuation,
120+
})
121+
}
122+
123+
fn necessary_children_exprs(
124+
&self,
125+
output_columns: &[usize],
126+
) -> Option<Vec<Vec<usize>>> {
127+
// The scans need every column of the body, since they are leaves whose
128+
// schema is fixed at planning time. The continuation only needs the
129+
// columns the parent asks for.
130+
let all_cte_columns = (0..self.cte.schema().fields().len()).collect();
131+
Some(vec![all_cte_columns, output_columns.to_vec()])
132+
}
133+
}
134+
135+
/// Reads the buffered output of the [`MaterializedCte`] with the same `id`.
136+
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
137+
pub struct MaterializedCteScan {
138+
pub id: MaterializedCteId,
139+
pub name: String,
140+
pub schema: DFSchemaRef,
141+
}
142+
143+
impl PartialOrd for MaterializedCteScan {
144+
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
145+
match self.id.cmp(&other.id) {
146+
Ordering::Equal => self.name.partial_cmp(&other.name),
147+
ord => Some(ord),
148+
}
149+
}
150+
}
151+
152+
impl UserDefinedLogicalNodeCore for MaterializedCteScan {
153+
fn name(&self) -> &str {
154+
"MaterializedCteScan"
155+
}
156+
157+
fn inputs(&self) -> Vec<&LogicalPlan> {
158+
vec![]
159+
}
160+
161+
fn schema(&self) -> &DFSchemaRef {
162+
&self.schema
163+
}
164+
165+
fn expressions(&self) -> Vec<Expr> {
166+
vec![]
167+
}
168+
169+
fn fmt_for_explain(&self, f: &mut fmt::Formatter) -> fmt::Result {
170+
write!(f, "MaterializedCteScan: name={}", self.name)
171+
}
172+
173+
fn with_exprs_and_inputs(
174+
&self,
175+
exprs: Vec<Expr>,
176+
inputs: Vec<LogicalPlan>,
177+
) -> Result<Self> {
178+
assert_eq_or_internal_err!(exprs.len(), 0, "MaterializedCteScan takes no exprs");
179+
assert_eq_or_internal_err!(
180+
inputs.len(),
181+
0,
182+
"MaterializedCteScan takes no inputs"
183+
);
184+
Ok(self.clone())
185+
}
186+
}

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@ pub mod display;
2121
pub mod dml;
2222
mod extension;
2323
pub(crate) mod invariants;
24+
pub mod materialized_cte;
2425
pub use invariants::{InvariantLevel, assert_expected_schema, check_subquery_expr};
2526
mod plan;
2627
mod statement;
@@ -59,3 +60,4 @@ pub use datafusion_common::format::ExplainFormat;
5960
pub use display::display_schema;
6061

6162
pub use extension::{UserDefinedLogicalNode, UserDefinedLogicalNodeCore};
63+
pub use materialized_cte::{MaterializedCte, MaterializedCteId, MaterializedCteScan};

‎datafusion/physical-plan/src/lib.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -86,6 +86,7 @@ pub mod filter;
8686
pub mod filter_pushdown;
8787
pub mod joins;
8888
pub mod limit;
89+
pub mod materialized_cte;
8990
pub mod memory;
9091
pub mod metrics;
9192
pub mod operator_statistics;

0 commit comments

Comments
 (0)