Skip to content

Commit 19fa23e

Browse files
committed
feat: report statistics of materialized CTE scans
A `MaterializedCteScanExec` is a leaf, and the CTE body is a child of `MaterializedCteExec`, so the scan reported unknown statistics. `JoinSelection` could then build a hash table on a large table and not on a small CTE. `optimize_physical_plan` now binds the scans and gives each scan the statistics of the CTE body, before the optimizer runs. A body that reads another CTE gets the statistics of that CTE first. A rewrite of the body does not change its rows, so these statistics stay correct. The EXPLAIN paths use the same function, so they show the same plan. Closes apache#26230.
1 parent 484183d commit 19fa23e

3 files changed

Lines changed: 380 additions & 70 deletions

File tree

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 114 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,
@@ -111,7 +111,7 @@ use datafusion_physical_plan::operator_statistics::StatisticsRegistry;
111111
use datafusion_physical_plan::placeholder_row::PlaceholderRowExec;
112112
use datafusion_physical_plan::recursive_query::RecursiveQueryExec;
113113
use datafusion_physical_plan::scalar_subquery::{ScalarSubqueryExec, ScalarSubqueryLink};
114-
use datafusion_physical_plan::statistics::StatisticsContext;
114+
use datafusion_physical_plan::statistics::{StatisticsArgs, StatisticsContext};
115115
use datafusion_physical_plan::unnest::ListUnnest;
116116
use datafusion_session::{PhysicalOptimizerContext, PhysicalOptimizerRule, Session};
117117

@@ -238,8 +238,6 @@ impl DefaultPhysicalPlanner {
238238
let plan = self
239239
.create_initial_plan(logical_plan, session_state)
240240
.await?;
241-
let plan = bind_materialized_cte_scans(plan)?;
242-
243241
self.optimize_physical_plan(plan, session_state, |_, _| {})
244242
}
245243
}
@@ -335,56 +333,126 @@ fn renumber_materialized_ctes(plan: &LogicalPlan) -> Result<Option<LogicalPlan>>
335333
.map(|t| Some(t.data))
336334
}
337335

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

390458
#[derive(Debug)]
@@ -3340,7 +3408,11 @@ impl DefaultPhysicalPlanner {
33403408

33413409
/// Optimize a physical plan by applying each physical optimizer,
33423410
/// calling observer(plan, optimizer after each one)
3343-
#[expect(clippy::needless_pass_by_value)]
3411+
///
3412+
/// Before the optimizers run, each [`MaterializedCteScanExec`] is bound
3413+
/// to the buffer of its [`MaterializedCteExec`] and gets the statistics
3414+
/// of the CTE body. A rewrite of the body does not change its rows, so
3415+
/// these statistics stay correct.
33443416
pub fn optimize_physical_plan<F>(
33453417
&self,
33463418
plan: Arc<dyn ExecutionPlan>,
@@ -3350,6 +3422,7 @@ impl DefaultPhysicalPlanner {
33503422
where
33513423
F: FnMut(&dyn ExecutionPlan, &dyn PhysicalOptimizerRule),
33523424
{
3425+
let plan = bind_materialized_cte_scans(plan, session_state)?;
33533426
let optimizers = session_state.physical_optimizers();
33543427
debug!(
33553428
"Input physical plan:\n{}\n",

0 commit comments

Comments
 (0)