Skip to content

Commit d48480e

Browse files
adriangbclaude
andauthored
feat: report statistics of materialized CTE scans (apache#26271)
## Which issue does this PR close? - Closes apache#26230. ## Rationale for this change A reference to a `MATERIALIZED` CTE reported unknown statistics. A query could then get a worse plan than the same query with the CTE inlined. ```sql SET datafusion.sql_parser.dialect = 'PostgreSQL'; CREATE TABLE small AS SELECT value AS k FROM generate_series(1, 5); CREATE TABLE huge AS SELECT value AS k FROM generate_series(1, 100000); EXPLAIN WITH c AS MATERIALIZED (SELECT k FROM small) SELECT count(*) FROM huge JOIN c ON huge.k = c.k; ``` Before, the hash table is built on the 100000 rows of `huge`: ``` HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(k@0, k@0)], projection=[] DataSourceExec: partitions=1, partition_sizes=[13] MaterializedCteScanExec: name=c ``` After, it is built on the 5 rows of the CTE: ``` HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(k@0, k@0)], projection=[] MaterializedCteScanExec: name=c DataSourceExec: partitions=1, partition_sizes=[13] ``` ## What changes are included in this PR? The scan is a leaf and the body is a child of `MaterializedCteExec`, so the planner copies the statistics to the scan in `DefaultPhysicalPlanner::optimize_physical_plan`, before the optimizer runs. The optimizer runs one time, as before. The EXPLAIN paths use the same function. Each scan gets the statistics of the body, computed with `StatisticsContext`. A body that reads another CTE gets the statistics of that CTE first. A rewrite of the body does not change its rows, so the statistics stay correct. The statistics of one scan partition are known only when the scan has one partition. The statistics API is not changed. Other plan changes that follow from the statistics: an exact row count of the body can answer `count(*)`, and the body then does not run. One pinned plan in `cte_materialized.slt` has a new join order. The ordering and the hash partitioning of the scans are a follow-up: apache#26424. The scan gets the complete statistics of the body, not only the row count: column min, max, null count, distinct count and byte size. Thus the outer query uses the column statistics of the CTE. For example, a filter above the scan derives its bounds from the column bounds of the body, the same as in the inlined plan. The statistics of one partition are given only when the scan has one partition. Otherwise they are unknown, because scan partitions do not map to body partitions. **Comparison with PostgreSQL and DuckDB.** This is what PostgreSQL and DuckDB do. PostgreSQL gives a CTE scan the row estimate of the CTE plan ([allpaths.c](https://github.com/postgres/postgres/blob/af090508018be5ace443ba6e2814500c10842a4d/src/backend/optimizer/path/allpaths.c#L3105)). DuckDB copies the statistics of the body to each reference ([propagate_cte.cpp](https://github.com/duckdb/duckdb/blob/1b4c3e54ba3625bac56ad184f0ce642a8d2bfbd5/src/optimizer/statistics/operator/propagate_cte.cpp#L34)). ## Are these changes tested? Yes. `cte_materialized.slt`: the join-order plan, the statistics in EXPLAIN, `count(*)` from exact statistics, a chain of two CTEs, a scalar subquery and a view. A unit test for the statistics of a scan. ## Are there any user-facing changes? Plans of queries with `MATERIALIZED` CTEs can change. New public functions: `MaterializedCteScanExec::with_body_statistics` and `MaterializedCteExec::body`. --------- Co-authored-by: Claude Opus 5.5 <[email protected]>
1 parent c6ab9b2 commit d48480e

3 files changed

Lines changed: 392 additions & 70 deletions

File tree

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 118 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -72,8 +72,8 @@ use datafusion_common::display::ToStringifiedPlan;
7272
use datafusion_common::format::ExplainAnalyzeCategories;
7373
use datafusion_common::tree_node::{Transformed, TreeNode, TreeNodeRecursion};
7474
use datafusion_common::{
75-
DFSchema, DFSchemaRef, ScalarValue, exec_err, internal_datafusion_err, internal_err,
76-
not_impl_err, plan_err,
75+
DFSchema, DFSchemaRef, ScalarValue, Statistics, exec_err, internal_datafusion_err,
76+
internal_err, not_impl_err, plan_err,
7777
};
7878
use datafusion_common::{
7979
TableReference, assert_eq_or_internal_err, assert_or_internal_err,
@@ -112,7 +112,7 @@ use datafusion_physical_plan::operator_statistics::StatisticsRegistry;
112112
use datafusion_physical_plan::placeholder_row::PlaceholderRowExec;
113113
use datafusion_physical_plan::recursive_query::RecursiveQueryExec;
114114
use datafusion_physical_plan::scalar_subquery::{ScalarSubqueryExec, ScalarSubqueryLink};
115-
use datafusion_physical_plan::statistics::StatisticsContext;
115+
use datafusion_physical_plan::statistics::{StatisticsArgs, StatisticsContext};
116116
use datafusion_physical_plan::unnest::ListUnnest;
117117
use datafusion_session::{PhysicalOptimizerContext, PhysicalOptimizerRule, Session};
118118

@@ -239,8 +239,6 @@ impl DefaultPhysicalPlanner {
239239
let plan = self
240240
.create_initial_plan(logical_plan, session_state)
241241
.await?;
242-
let plan = bind_materialized_cte_scans(plan)?;
243-
244242
self.optimize_physical_plan(plan, session_state, |_, _| {})
245243
}
246244
}
@@ -318,56 +316,126 @@ fn renumber_materialized_ctes(plan: &LogicalPlan) -> Result<Option<LogicalPlan>>
318316
.map(|t| Some(t.data))
319317
}
320318

321-
/// Point every [`MaterializedCteScanExec`] at the buffer of the
322-
/// [`MaterializedCteExec`] with the same id.
319+
/// Points every [`MaterializedCteScanExec`] at the buffer of the
320+
/// [`MaterializedCteExec`] with the same id, and gives it the statistics of
321+
/// the CTE body.
323322
///
324323
/// [`renumber_materialized_ctes`] makes the ids unique before the physical
325324
/// plan is created.
326325
///
327326
/// A scan that is already bound was planned and bound by a separate planning
328-
/// run, such as the `scan` of a [`ViewTable`], and is left as is. Binding it
329-
/// again would count its partitions twice in the buffer.
327+
/// run, such as the `scan` of a [`ViewTable`], and is not bound again. Binding
328+
/// it again would count its partitions twice in the buffer.
330329
///
331330
/// Scans are planned before the node that owns their CTE, and a scan inside a
332331
/// scalar subquery is planned in a separate subtree, so the binding is done
333-
/// once on the whole initial plan.
332+
/// on the whole initial plan.
334333
///
335334
/// [`ViewTable`]: crate::datasource::ViewTable
335+
struct MaterializedCteBinder {
336+
ctes: HashMap<u64, Arc<dyn ExecutionPlan>>,
337+
/// The statistics of the CTE bodies. `None` while they are computed.
338+
statistics: HashMap<u64, Option<Arc<Statistics>>>,
339+
context: StatisticsContext,
340+
}
341+
342+
impl MaterializedCteBinder {
343+
fn new(plan: &Arc<dyn ExecutionPlan>, session_state: &dyn Session) -> Result<Self> {
344+
let mut ctes = HashMap::new();
345+
plan.apply(|node| {
346+
if let Some(cte) = node.downcast_ref::<MaterializedCteExec>()
347+
&& ctes.insert(cte.buffer().id(), Arc::clone(node)).is_some()
348+
{
349+
return internal_err!(
350+
"Two MaterializedCteExec nodes have the id {}",
351+
cte.buffer().id()
352+
);
353+
}
354+
Ok(TreeNodeRecursion::Continue)
355+
})?;
356+
let context = match session_state.statistics_registry() {
357+
Some(registry) => StatisticsContext::new_with_registry(registry.clone()),
358+
None => StatisticsContext::new(),
359+
};
360+
Ok(Self {
361+
ctes,
362+
statistics: HashMap::new(),
363+
context,
364+
})
365+
}
366+
367+
fn cte(&self, id: u64) -> Option<&MaterializedCteExec> {
368+
self.ctes
369+
.get(&id)
370+
.and_then(|cte| cte.downcast_ref::<MaterializedCteExec>())
371+
}
372+
373+
/// Give every scan in `plan` whose CTE is in `self.ctes` the statistics
374+
/// of the CTE body. If `bind` is true, also bind the scans that are not
375+
/// bound.
376+
fn bind(
377+
&mut self,
378+
plan: Arc<dyn ExecutionPlan>,
379+
bind: bool,
380+
) -> Result<Arc<dyn ExecutionPlan>> {
381+
plan.transform_up(|node| {
382+
let Some(scan) = node.downcast_ref::<MaterializedCteScanExec>() else {
383+
return Ok(Transformed::no(node));
384+
};
385+
let Some(cte) = self.cte(scan.id()) else {
386+
if scan.is_bound() {
387+
return Ok(Transformed::no(node));
388+
}
389+
return internal_err!("MaterializedCteScanExec {} has no CTE", scan.id());
390+
};
391+
let bound =
392+
(bind && !scan.is_bound()).then(|| scan.bind(Arc::clone(cte.buffer())));
393+
let scan = bound.as_ref().unwrap_or(scan);
394+
let scan = match self.body_statistics(scan.id())? {
395+
Some(statistics) => scan.with_body_statistics(statistics),
396+
None => match bound {
397+
Some(bound) => bound,
398+
None => return Ok(Transformed::no(node)),
399+
},
400+
};
401+
Ok(Transformed::yes(Arc::new(scan) as Arc<dyn ExecutionPlan>))
402+
})
403+
.map(|t| t.data)
404+
}
405+
406+
/// The statistics of the body of the CTE `id`, or `None` while they are
407+
/// computed.
408+
///
409+
/// The body can read other CTEs. Its scans get their statistics first,
410+
/// in a copy of the body that is used only here.
411+
fn body_statistics(&mut self, id: u64) -> Result<Option<Arc<Statistics>>> {
412+
if let Some(statistics) = self.statistics.get(&id) {
413+
return Ok(statistics.clone());
414+
}
415+
let Some(cte) = self.cte(id) else {
416+
return Ok(None);
417+
};
418+
let body = Arc::clone(cte.body());
419+
self.statistics.insert(id, None);
420+
let body = self.bind(body, false)?;
421+
let statistics = self
422+
.context
423+
.compute(body.as_ref(), &StatisticsArgs::new())?;
424+
self.statistics.insert(id, Some(Arc::clone(&statistics)));
425+
Ok(Some(statistics))
426+
}
427+
}
428+
429+
/// See [`MaterializedCteBinder`].
336430
fn bind_materialized_cte_scans(
337431
plan: Arc<dyn ExecutionPlan>,
432+
session_state: &dyn Session,
338433
) -> Result<Arc<dyn ExecutionPlan>> {
339-
let mut buffers = HashMap::new();
340-
plan.apply(|node| {
341-
if let Some(cte) = node.downcast_ref::<MaterializedCteExec>()
342-
&& buffers
343-
.insert(cte.buffer().id(), Arc::clone(cte.buffer()))
344-
.is_some()
345-
{
346-
return internal_err!(
347-
"Two MaterializedCteExec nodes have the id {}",
348-
cte.buffer().id()
349-
);
350-
}
351-
Ok(TreeNodeRecursion::Continue)
352-
})?;
353-
if buffers.is_empty() {
434+
let mut binder = MaterializedCteBinder::new(&plan, session_state)?;
435+
if binder.ctes.is_empty() {
354436
return Ok(plan);
355437
}
356-
plan.transform_up(|node| {
357-
let Some(scan) = node.downcast_ref::<MaterializedCteScanExec>() else {
358-
return Ok(Transformed::no(node));
359-
};
360-
if scan.is_bound() {
361-
return Ok(Transformed::no(node));
362-
}
363-
let Some(buffer) = buffers.get(&scan.id()) else {
364-
return internal_err!("MaterializedCteScanExec {} has no CTE", scan.id());
365-
};
366-
Ok(Transformed::yes(
367-
Arc::new(scan.bind(Arc::clone(buffer))) as Arc<dyn ExecutionPlan>
368-
))
369-
})
370-
.map(|t| t.data)
438+
binder.bind(plan, true)
371439
}
372440

373441
#[derive(Debug)]
@@ -3301,7 +3369,15 @@ impl DefaultPhysicalPlanner {
33013369

33023370
/// Optimize a physical plan by applying each physical optimizer,
33033371
/// calling observer(plan, optimizer after each one)
3304-
#[expect(clippy::needless_pass_by_value)]
3372+
///
3373+
/// Before the optimizers run, each [`MaterializedCteScanExec`] is bound
3374+
/// to the buffer of its [`MaterializedCteExec`] and gets the statistics
3375+
/// of the CTE body, as it is before the optimizers run. A rewrite of the
3376+
/// body does not change its rows, so these statistics stay valid, but
3377+
/// they can be less precise than the statistics of the optimized body.
3378+
///
3379+
/// TODO: snapshot the statistics after the body is optimized, see
3380+
/// <https://github.com/apache/datafusion/issues/26424>.
33053381
pub fn optimize_physical_plan<F>(
33063382
&self,
33073383
plan: Arc<dyn ExecutionPlan>,
@@ -3311,6 +3387,7 @@ impl DefaultPhysicalPlanner {
33113387
where
33123388
F: FnMut(&dyn ExecutionPlan, &dyn PhysicalOptimizerRule),
33133389
{
3390+
let plan = bind_materialized_cte_scans(plan, session_state)?;
33143391
let optimizers = session_state.physical_optimizers();
33153392
debug!(
33163393
"Input physical plan:\n{}\n",

0 commit comments

Comments
 (0)