Skip to content

Commit 4f0729c

Browse files
committed
feat: decide automatically when to materialize a CTE
Add the option `datafusion.optimizer.enable_automatic_cte_materialization`, which is off by default. With the default, each query plans as before. When the option is on, the SQL planner plans each non-recursive CTE that has no directive as a `MaterializedCte` with `automatic = true`, in each dialect. The new optimizer rule `InlineAutomaticCtes` replaces an automatic node with `MaterializedCte::inline` when the CTE has zero or one reference, or when its body is volatile, has an outer reference, or is only projections and filters on one table, or when a `LIMIT` with a fetch is above all references in the chain of one-input nodes from the root of the query. All other automatic CTEs stay materialized and are computed one time. `AS MATERIALIZED` and `AS NOT MATERIALIZED` override the rule. The physical planner inlines an automatic CTE that has an unbounded body, because such a body cannot be buffered and the query worked before. Closes apache#26237.
1 parent 37c5b98 commit 4f0729c

16 files changed

Lines changed: 1740 additions & 39 deletions

File tree

‎datafusion/common/src/config.rs‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1664,6 +1664,28 @@ config_namespace! {
16641664
/// past window functions, if possible
16651665
pub enable_window_limits: bool, default = true
16661666

1667+
/// When set to true, the SQL planner plans each non-recursive CTE that
1668+
/// has no `MATERIALIZED` or `NOT MATERIALIZED` directive as a
1669+
/// materialized CTE, and the optimizer rule `inline_automatic_ctes`
1670+
/// decides which of them stay materialized. A CTE stays materialized,
1671+
/// and is computed one time, when it has more than one reference and
1672+
/// its body is more than projections and filters on one table, and no
1673+
/// `LIMIT` is above all of its references. A CTE
1674+
/// with a volatile body is inlined, unless
1675+
/// `automatic_cte_materialization_keeps_volatile` is true. All other
1676+
/// CTEs are inlined at each reference.
1677+
/// When set to false, a CTE is materialized only with `AS MATERIALIZED`.
1678+
pub enable_automatic_cte_materialization: bool, default = false
1679+
1680+
/// When set to true, together with
1681+
/// `enable_automatic_cte_materialization`, a CTE with a volatile body
1682+
/// and more than one reference stays materialized, so that each
1683+
/// reference reads the same rows. PostgreSQL and DuckDB do the same.
1684+
/// When set to false, such a CTE is inlined at each reference, and
1685+
/// each reference evaluates the volatile expressions again, as with
1686+
/// `enable_automatic_cte_materialization` set to false.
1687+
pub automatic_cte_materialization_keeps_volatile: bool, default = false
1688+
16671689
/// When set to true, the optimizer will replace
16681690
/// Filter(rn<=K) → Window(ROW_NUMBER) → Sort patterns with a
16691691
/// PartitionedTopKExec that maintains per-partition heaps, avoiding

‎datafusion/core/src/optimizer_rule_reference.md‎

Lines changed: 27 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -37,32 +37,33 @@ Rule order matters. The default pipeline may change between releases.
3737

3838
| order | rule | summary |
3939
| ----- | ----------------------------------------- | --------------------------------------------------------------------------------------------------------------------------- |
40-
| 1 | `rewrite_set_comparison` | Rewrites `ANY` and `ALL` set-comparison subqueries into `EXISTS`-based boolean expressions with correct SQL NULL semantics. |
41-
| 2 | `optimize_unions` | Flattens nested unions and removes unions with a single input. |
42-
| 3 | `unions_to_filter` | Merges `UNION DISTINCT` branches that share the same source into a single filtered branch with a disjunctive predicate. |
43-
| 4 | `simplify_expressions` | Constant-folds and simplifies expressions while preserving output names. |
44-
| 5 | `replace_distinct_aggregate` | Rewrites `DISTINCT` and `DISTINCT ON` operators into aggregate-based plans that later rules can optimize further. |
45-
| 6 | `eliminate_join` | Replaces keyless inner joins with a literal `false` filter by an empty relation. |
46-
| 7 | `decorrelate_predicate_subquery` | Converts eligible `IN` and `EXISTS` predicate subqueries into semi or anti joins. |
47-
| 8 | `scalar_subquery_to_join` | Rewrites eligible scalar subqueries into joins and adds schema-preserving projections. |
48-
| 9 | `decorrelate_lateral_join` | Rewrites eligible lateral joins into regular joins. |
49-
| 10 | `extract_equijoin_predicate` | Splits join filters into equijoin keys and residual predicates. |
50-
| 11 | `eliminate_duplicated_expr` | Removes duplicate expressions from projections, aggregates, and similar operators. |
51-
| 12 | `eliminate_filter` | Drops always-true filters and replaces always-false or NULL filters with empty relations. |
52-
| 13 | `eliminate_cross_join` | Uses filter predicates to replace cross joins with inner joins when join keys can be found. |
53-
| 14 | `eliminate_limit` | Removes no-op limits and simplifies trivial limit shapes. |
54-
| 15 | `propagate_empty_relation` | Pushes empty-relation knowledge upward so operators fed by no rows collapse early. |
55-
| 16 | `filter_null_join_keys` | Adds `IS NOT NULL` filters to nullable equijoin keys that can never match. |
56-
| 17 | `eliminate_outer_join` | Rewrites outer joins to inner joins when later filters reject the NULL-extended rows. |
57-
| 18 | `push_down_limit` | Moves literal limits closer to scans and unions and merges adjacent limits. |
58-
| 19 | `push_down_filter` | Moves filters as early as possible through filter-commutative operators. |
59-
| 20 | `eliminate_aggregate_distinct` | Drops the `DISTINCT` modifier from aggregates whose result cannot change, such as `min`, `max` and `bit_or`. |
60-
| 21 | `single_distinct_aggregation_to_group_by` | Rewrites single-column `DISTINCT` aggregations into two-stage `GROUP BY` plans. |
61-
| 22 | `eliminate_group_by_constant` | Removes constant or functionally redundant expressions from `GROUP BY`. |
62-
| 23 | `common_sub_expression_eliminate` | Computes repeated subexpressions once and reuses the result. |
63-
| 24 | `extract_leaf_expressions` | Pulls cheap leaf expressions closer to data sources so later pruning and filter rules can act earlier. |
64-
| 25 | `push_down_leaf_projections` | Pushes the helper projections created by leaf extraction toward leaf inputs. |
65-
| 26 | `optimize_projections` | Prunes unused columns and removes unnecessary logical projections. |
40+
| 1 | `inline_automatic_ctes` | Inlines the automatic materialized CTEs that have at most one reference, or a volatile or cheap body. |
41+
| 2 | `rewrite_set_comparison` | Rewrites `ANY` and `ALL` set-comparison subqueries into `EXISTS`-based boolean expressions with correct SQL NULL semantics. |
42+
| 3 | `optimize_unions` | Flattens nested unions and removes unions with a single input. |
43+
| 4 | `unions_to_filter` | Merges `UNION DISTINCT` branches that share the same source into a single filtered branch with a disjunctive predicate. |
44+
| 5 | `simplify_expressions` | Constant-folds and simplifies expressions while preserving output names. |
45+
| 6 | `replace_distinct_aggregate` | Rewrites `DISTINCT` and `DISTINCT ON` operators into aggregate-based plans that later rules can optimize further. |
46+
| 7 | `eliminate_join` | Replaces keyless inner joins with a literal `false` filter by an empty relation. |
47+
| 8 | `decorrelate_predicate_subquery` | Converts eligible `IN` and `EXISTS` predicate subqueries into semi or anti joins. |
48+
| 9 | `scalar_subquery_to_join` | Rewrites eligible scalar subqueries into joins and adds schema-preserving projections. |
49+
| 10 | `decorrelate_lateral_join` | Rewrites eligible lateral joins into regular joins. |
50+
| 11 | `extract_equijoin_predicate` | Splits join filters into equijoin keys and residual predicates. |
51+
| 12 | `eliminate_duplicated_expr` | Removes duplicate expressions from projections, aggregates, and similar operators. |
52+
| 13 | `eliminate_filter` | Drops always-true filters and replaces always-false or NULL filters with empty relations. |
53+
| 14 | `eliminate_cross_join` | Uses filter predicates to replace cross joins with inner joins when join keys can be found. |
54+
| 15 | `eliminate_limit` | Removes no-op limits and simplifies trivial limit shapes. |
55+
| 16 | `propagate_empty_relation` | Pushes empty-relation knowledge upward so operators fed by no rows collapse early. |
56+
| 17 | `filter_null_join_keys` | Adds `IS NOT NULL` filters to nullable equijoin keys that can never match. |
57+
| 18 | `eliminate_outer_join` | Rewrites outer joins to inner joins when later filters reject the NULL-extended rows. |
58+
| 19 | `push_down_limit` | Moves literal limits closer to scans and unions and merges adjacent limits. |
59+
| 20 | `push_down_filter` | Moves filters as early as possible through filter-commutative operators. |
60+
| 21 | `eliminate_aggregate_distinct` | Drops the `DISTINCT` modifier from aggregates whose result cannot change, such as `min`, `max` and `bit_or`. |
61+
| 22 | `single_distinct_aggregation_to_group_by` | Rewrites single-column `DISTINCT` aggregations into two-stage `GROUP BY` plans. |
62+
| 23 | `eliminate_group_by_constant` | Removes constant or functionally redundant expressions from `GROUP BY`. |
63+
| 24 | `common_sub_expression_eliminate` | Computes repeated subexpressions once and reuses the result. |
64+
| 25 | `extract_leaf_expressions` | Pulls cheap leaf expressions closer to data sources so later pruning and filter rules can act earlier. |
65+
| 26 | `push_down_leaf_projections` | Pushes the helper projections created by leaf extraction toward leaf inputs. |
66+
| 27 | `optimize_projections` | Prunes unused columns and removes unnecessary logical projections. |
6667

6768
### Physical Optimizer Rules
6869

‎datafusion/core/src/physical_planner.rs‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -318,6 +318,47 @@ fn renumber_materialized_ctes(plan: &LogicalPlan) -> Result<Option<LogicalPlan>>
318318
.map(|t| Some(t.data))
319319
}
320320

321+
/// The body of the automatic [`MaterializedCte`] with this id is unbounded, so
322+
/// the CTE must be inlined. This error does not reach the user:
323+
/// `create_initial_plan` handles it.
324+
#[derive(Debug)]
325+
struct UnboundedAutomaticCte(MaterializedCteId);
326+
327+
impl std::fmt::Display for UnboundedAutomaticCte {
328+
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
329+
write!(
330+
f,
331+
"The automatic materialized CTE {} reads an unbounded source",
332+
self.0
333+
)
334+
}
335+
}
336+
337+
impl std::error::Error for UnboundedAutomaticCte {}
338+
339+
/// Replace each occurrence of the [`MaterializedCte`] `id` in `plan` with its
340+
/// continuation, in which each scan is a copy of the body. A copy of the body
341+
/// can hold another materialized CTE, so the CTEs get new ids.
342+
fn inline_materialized_cte(
343+
plan: &LogicalPlan,
344+
id: MaterializedCteId,
345+
) -> Result<LogicalPlan> {
346+
let inlined = plan
347+
.clone()
348+
.transform_up_with_subqueries(|node| match node {
349+
LogicalPlan::MaterializedCte(MaterializedCtePlan::Cte(cte))
350+
if cte.id == id =>
351+
{
352+
Ok(Transformed::yes(cte.inline()?))
353+
}
354+
_ => Ok(Transformed::no(node)),
355+
})?;
356+
if !inlined.transformed {
357+
return internal_err!("The materialized CTE {id} is not in the plan");
358+
}
359+
Ok(renumber_materialized_ctes(&inlined.data)?.unwrap_or(inlined.data))
360+
}
361+
321362
/// Point every [`MaterializedCteScanExec`] at the buffer of the
322363
/// [`MaterializedCteExec`] with the same id.
323364
///
@@ -506,6 +547,38 @@ impl DefaultPhysicalPlanner {
506547
&'a self,
507548
logical_plan: &'a LogicalPlan,
508549
session_state: &'a dyn Session,
550+
) -> BoxFuture<'a, Result<Arc<dyn ExecutionPlan>>> {
551+
Box::pin(async move {
552+
// An automatic materialized CTE with an unbounded body cannot be
553+
// buffered. The query worked before the CTE was materialized, so
554+
// inline the CTE and plan again.
555+
let mut inlined: Option<LogicalPlan> = None;
556+
loop {
557+
let plan = inlined.as_ref().unwrap_or(logical_plan);
558+
let result = self.create_initial_plan_once(plan, session_state).await;
559+
let id = match &result {
560+
Err(e) => match e.find_root() {
561+
DataFusionError::External(e) => {
562+
e.downcast_ref::<UnboundedAutomaticCte>().map(|e| e.0)
563+
}
564+
_ => None,
565+
},
566+
Ok(_) => None,
567+
};
568+
let Some(id) = id else {
569+
return result;
570+
};
571+
inlined = Some(inline_materialized_cte(plan, id)?);
572+
}
573+
})
574+
}
575+
576+
/// Plans `logical_plan` and its uncorrelated scalar subqueries. See
577+
/// [`Self::create_initial_plan`].
578+
fn create_initial_plan_once<'a>(
579+
&'a self,
580+
logical_plan: &'a LogicalPlan,
581+
session_state: &'a dyn Session,
509582
) -> BoxFuture<'a, Result<Arc<dyn ExecutionPlan>>> {
510583
Box::pin(async move {
511584
// When `enable_physical_uncorrelated_scalar_subquery` is disabled, the
@@ -2053,6 +2126,13 @@ impl DefaultPhysicalPlanner {
20532126
// The body is fully buffered before a scan yields a row, so an
20542127
// unbounded body would never produce output.
20552128
if body.boundedness().is_unbounded() {
2129+
// The user did not ask for this CTE to be materialized.
2130+
// `create_initial_plan` inlines it and plans again.
2131+
if cte.is_automatic() {
2132+
return Err(DataFusionError::External(Box::new(
2133+
UnboundedAutomaticCte(cte.id),
2134+
)));
2135+
}
20562136
return plan_err!(
20572137
"MATERIALIZED CTE {} reads an unbounded source, which cannot be materialized",
20582138
cte.name

0 commit comments

Comments
 (0)