Skip to content

Commit 2de017a

Browse files
adriangbclaude
andcommitted
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. 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. Co-Authored-By: Claude Opus 5.5 <[email protected]>
1 parent 456f298 commit 2de017a

16 files changed

Lines changed: 1416 additions & 39 deletions

File tree

‎datafusion/common/src/config.rs‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1664,6 +1664,16 @@ 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 not volatile and is more than projections and filters
1673+
/// on one table. All other CTEs are inlined at each reference.
1674+
/// When set to false, a CTE is materialized only with `AS MATERIALIZED`.
1675+
pub enable_automatic_cte_materialization: bool, default = false
1676+
16671677
/// When set to true, the optimizer will replace
16681678
/// Filter(rn<=K) → Window(ROW_NUMBER) → Sort patterns with a
16691679
/// 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: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -308,6 +308,45 @@ fn renumber_materialized_ctes(plan: &LogicalPlan) -> Result<Option<LogicalPlan>>
308308
.map(|t| Some(t.data))
309309
}
310310

311+
/// The body of the automatic [`MaterializedCte`] with this id is unbounded, so
312+
/// the CTE must be inlined. This error does not reach the user:
313+
/// `create_initial_plan` handles it.
314+
#[derive(Debug)]
315+
struct UnboundedAutomaticCte(MaterializedCteId);
316+
317+
impl std::fmt::Display for UnboundedAutomaticCte {
318+
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
319+
write!(
320+
f,
321+
"The automatic materialized CTE {} reads an unbounded source",
322+
self.0
323+
)
324+
}
325+
}
326+
327+
impl std::error::Error for UnboundedAutomaticCte {}
328+
329+
/// Replace each occurrence of the [`MaterializedCte`] `id` in `plan` with its
330+
/// continuation, in which each scan is a copy of the body. A copy of the body
331+
/// can hold another materialized CTE, so the CTEs get new ids.
332+
fn inline_materialized_cte(
333+
plan: &LogicalPlan,
334+
id: MaterializedCteId,
335+
) -> Result<LogicalPlan> {
336+
let inlined = plan
337+
.clone()
338+
.transform_up_with_subqueries(|node| match node {
339+
LogicalPlan::MaterializedCte(cte) if cte.id == id => {
340+
Ok(Transformed::yes(cte.inline()?))
341+
}
342+
_ => Ok(Transformed::no(node)),
343+
})?;
344+
if !inlined.transformed {
345+
return internal_err!("The materialized CTE {id} is not in the plan");
346+
}
347+
Ok(renumber_materialized_ctes(&inlined.data)?.unwrap_or(inlined.data))
348+
}
349+
311350
/// Point every [`MaterializedCteScanExec`] at the buffer of the
312351
/// [`MaterializedCteExec`] with the same id.
313352
///
@@ -496,6 +535,38 @@ impl DefaultPhysicalPlanner {
496535
&'a self,
497536
logical_plan: &'a LogicalPlan,
498537
session_state: &'a dyn Session,
538+
) -> BoxFuture<'a, Result<Arc<dyn ExecutionPlan>>> {
539+
Box::pin(async move {
540+
// An automatic materialized CTE with an unbounded body cannot be
541+
// buffered. The query worked before the CTE was materialized, so
542+
// inline the CTE and plan again.
543+
let mut inlined: Option<LogicalPlan> = None;
544+
loop {
545+
let plan = inlined.as_ref().unwrap_or(logical_plan);
546+
let result = self.create_initial_plan_once(plan, session_state).await;
547+
let id = match &result {
548+
Err(e) => match e.find_root() {
549+
DataFusionError::External(e) => {
550+
e.downcast_ref::<UnboundedAutomaticCte>().map(|e| e.0)
551+
}
552+
_ => None,
553+
},
554+
Ok(_) => None,
555+
};
556+
let Some(id) = id else {
557+
return result;
558+
};
559+
inlined = Some(inline_materialized_cte(plan, id)?);
560+
}
561+
})
562+
}
563+
564+
/// Plans `logical_plan` and its uncorrelated scalar subqueries. See
565+
/// [`Self::create_initial_plan`].
566+
fn create_initial_plan_once<'a>(
567+
&'a self,
568+
logical_plan: &'a LogicalPlan,
569+
session_state: &'a dyn Session,
499570
) -> BoxFuture<'a, Result<Arc<dyn ExecutionPlan>>> {
500571
Box::pin(async move {
501572
// When `enable_physical_uncorrelated_scalar_subquery` is disabled, the
@@ -2043,6 +2114,13 @@ impl DefaultPhysicalPlanner {
20432114
// The body is fully buffered before a scan yields a row, so an
20442115
// unbounded body would never produce output.
20452116
if body.boundedness().is_unbounded() {
2117+
// The user did not ask for this CTE to be materialized.
2118+
// `create_initial_plan` inlines it and plans again.
2119+
if cte.is_automatic() {
2120+
return Err(DataFusionError::External(Box::new(
2121+
UnboundedAutomaticCte(cte.id),
2122+
)));
2123+
}
20462124
return plan_err!(
20472125
"MATERIALIZED CTE {} reads an unbounded source, which cannot be materialized",
20482126
cte.name

0 commit comments

Comments
 (0)