Skip to content

Commit a442b87

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 5009f42 commit a442b87

3 files changed

Lines changed: 315 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)]
@@ -3320,7 +3388,11 @@ impl DefaultPhysicalPlanner {
33203388

33213389
/// Optimize a physical plan by applying each physical optimizer,
33223390
/// calling observer(plan, optimizer after each one)
3323-
#[expect(clippy::needless_pass_by_value)]
3391+
///
3392+
/// Before the optimizers run, each [`MaterializedCteScanExec`] is bound
3393+
/// to the buffer of its [`MaterializedCteExec`] and gets the statistics
3394+
/// of the CTE body. A rewrite of the body does not change its rows, so
3395+
/// these statistics stay correct.
33243396
pub fn optimize_physical_plan<F>(
33253397
&self,
33263398
plan: Arc<dyn ExecutionPlan>,
@@ -3330,6 +3402,7 @@ impl DefaultPhysicalPlanner {
33303402
where
33313403
F: FnMut(&dyn ExecutionPlan, &dyn PhysicalOptimizerRule),
33323404
{
3405+
let plan = bind_materialized_cte_scans(plan, session_state)?;
33333406
let optimizers = session_state.physical_optimizers();
33343407
debug!(
33353408
"Input physical plan:\n{}\n",

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

Lines changed: 78 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -39,6 +39,10 @@
3939
//! files until it can. An in-memory batch that is larger than the batches on
4040
//! disk is written in pieces, so that the move does not raise the memory that
4141
//! each reader needs.
42+
//!
43+
//! A scan is a leaf, and the body is not its child, so a scan cannot compute
44+
//! the statistics of the body. The planner copies them to the scan with
45+
//! [`MaterializedCteScanExec::with_body_statistics`].
4246
4347
use std::fmt;
4448
use std::pin::Pin;
@@ -513,6 +517,11 @@ impl MaterializedCteExec {
513517
pub fn buffer(&self) -> &Arc<MaterializedCteBuffer> {
514518
&self.buffer
515519
}
520+
521+
/// The plan of the CTE body.
522+
pub fn body(&self) -> &Arc<dyn ExecutionPlan> {
523+
&self.body
524+
}
516525
}
517526

518527
impl DisplayAs for MaterializedCteExec {
@@ -663,6 +672,8 @@ pub struct MaterializedCteScanExec {
663672
id: u64,
664673
name: String,
665674
schema: SchemaRef,
675+
/// The statistics of all partitions of the body.
676+
statistics: Option<Arc<Statistics>>,
666677
buffer: Option<Arc<MaterializedCteBuffer>>,
667678
metrics: ExecutionPlanMetricsSet,
668679
cache: Arc<PlanProperties>,
@@ -687,6 +698,7 @@ impl MaterializedCteScanExec {
687698
id,
688699
name: name.into(),
689700
schema,
701+
statistics: None,
690702
buffer: None,
691703
metrics: ExecutionPlanMetricsSet::new(),
692704
cache: Arc::new(cache),
@@ -703,12 +715,30 @@ impl MaterializedCteScanExec {
703715
id: self.id,
704716
name: self.name.clone(),
705717
schema: Arc::clone(&self.schema),
718+
statistics: self.statistics.clone(),
706719
buffer: Some(buffer),
707720
metrics: ExecutionPlanMetricsSet::new(),
708721
cache: Arc::clone(&self.cache),
709722
}
710723
}
711724

725+
/// Copy this scan, with the statistics of all partitions of the CTE
726+
/// body.
727+
///
728+
/// The scan returns every row of the body, so the statistics stay
729+
/// correct when the body is rewritten to a plan that gives the same rows.
730+
pub fn with_body_statistics(&self, statistics: Arc<Statistics>) -> Self {
731+
Self {
732+
id: self.id,
733+
name: self.name.clone(),
734+
schema: Arc::clone(&self.schema),
735+
statistics: Some(statistics),
736+
buffer: self.buffer.clone(),
737+
metrics: ExecutionPlanMetricsSet::new(),
738+
cache: Arc::clone(&self.cache),
739+
}
740+
}
741+
712742
/// The id of the [`MaterializedCteBuffer`] this scan reads.
713743
pub fn id(&self) -> u64 {
714744
self.id
@@ -801,19 +831,25 @@ impl ExecutionPlan for MaterializedCteScanExec {
801831
Some(self.metrics.clone_inner())
802832
}
803833

804-
/// The statistics are unknown: a leaf cannot ask the body for its
805-
/// statistics through [`StatisticsArgs`].
834+
/// Returns the statistics that the planner copied from the CTE body.
835+
/// See [`Self::with_body_statistics`].
806836
///
807-
/// This is a known limitation, and it can make a plan worse than the
808-
/// plan of the inlined CTE. For example, `JoinSelection` does not know
809-
/// that a scan is small, and can put the other, larger input of a hash
810-
/// join on the build side.
837+
/// The statistics of one partition are known only when the scan has one
838+
/// partition.
811839
fn statistics_from_inputs(
812840
&self,
813841
_input_stats: &[Arc<Statistics>],
814-
_args: &StatisticsArgs,
842+
args: &StatisticsArgs,
815843
) -> Result<Arc<Statistics>> {
816-
Ok(Arc::new(Statistics::new_unknown(&self.schema)))
844+
match &self.statistics {
845+
Some(statistics)
846+
if args.partition().is_none()
847+
|| self.cache.partitioning.partition_count() == 1 =>
848+
{
849+
Ok(Arc::clone(statistics))
850+
}
851+
_ => Ok(Arc::new(Statistics::new_unknown(&self.schema))),
852+
}
817853
}
818854
}
819855

@@ -823,12 +859,46 @@ mod tests {
823859
use crate::common::collect;
824860
use crate::empty::EmptyExec;
825861
use crate::filter_pushdown::PushedDown;
862+
use crate::statistics::StatisticsContext;
826863
use crate::test::TestMemoryExec;
827864
use arrow::array::{Array, Int32Array};
828865
use arrow::datatypes::{DataType, Field, Schema};
866+
use datafusion_common::stats::Precision;
829867
use datafusion_execution::runtime_env::RuntimeEnvBuilder;
830868
use datafusion_physical_expr::expressions::{col, lit};
831869

870+
#[test]
871+
fn scan_reports_body_statistics() -> Result<()> {
872+
let schema = Arc::new(Schema::new(vec![Field::new("a", DataType::Int32, false)]));
873+
let batch = RecordBatch::try_new(
874+
Arc::clone(&schema),
875+
vec![Arc::new(Int32Array::from(vec![3, 1, 2]))],
876+
)?;
877+
let body = TestMemoryExec::try_new_exec(
878+
&[vec![batch.clone()], vec![batch]],
879+
Arc::clone(&schema),
880+
None,
881+
)?;
882+
let context = StatisticsContext::new();
883+
let body_statistics = context.compute(body.as_ref(), &StatisticsArgs::new())?;
884+
assert_eq!(body_statistics.num_rows, Precision::Exact(6));
885+
886+
let buffer = Arc::new(MaterializedCteBuffer::new(0, "c"));
887+
let scan = MaterializedCteScanExec::new(0, "c", schema, 4).bind(buffer);
888+
let statistics = context.compute(&scan, &StatisticsArgs::new())?;
889+
assert_eq!(statistics.num_rows, Precision::Absent);
890+
891+
let scan = scan.with_body_statistics(body_statistics);
892+
assert!(scan.is_bound());
893+
let statistics = context.compute(&scan, &StatisticsArgs::new())?;
894+
assert_eq!(statistics.num_rows, Precision::Exact(6));
895+
// The 4 scan partitions do not map to the 2 body partitions.
896+
let args = StatisticsArgs::new().with_partition(Some(0));
897+
let statistics = context.compute(&scan, &args)?;
898+
assert_eq!(statistics.num_rows, Precision::Absent);
899+
Ok(())
900+
}
901+
832902
#[test]
833903
fn parent_filters_go_to_the_continuation_only() -> Result<()> {
834904
let schema = Arc::new(Schema::new(vec![Field::new("a", DataType::Int32, true)]));

0 commit comments

Comments
 (0)