Add support for materialized CTEs #7126

kryonix · 2023-04-18T07:06:31Z

This pr adds support for materialized CTE expressions as an alternative to inlining, as I briefly mentioned in #404.

Inlining CTEs can be great, but it can also multiply the work. Take this query for example:

WITH t(x) AS
  (SELECT t FROM generate_series(1,10) AS _(t))
SELECT t1.x, t2.x FROM t AS t1, t AS t2;

Inlining duplicates the definition of t for each reference.
This results in the following query:

SELECT t1.x, t2.x FROM (SELECT t FROM generate_series(1,10) AS _(t)) AS t1(x),
                       (SELECT t FROM generate_series(1,10) AS _(t)) AS t2(x);

Now, if t is an expensive query, there may be a problem.

With this pr, CTEs can be annotated as being MATERIALIZED.
Such CTEs first fully materialize their result, which can then be read:

WITH t(x) AS MATERIALIZED
  (SELECT t FROM generate_series(1,10) AS _(t))
SELECT t1.x, t2.x FROM t AS t1, t AS t2;

Instead of copying t for each reference, t is calculated exactly once. Since the result is cached, no work is done multiple times.

kryonix · 2023-04-18T07:11:54Z

~~This pr is currently a draft, as there are two remaining issues:~~

~~First, something during binding seems to be broken, as the following fails:~~

SELECT x FROM (WITH t(y, z) AS MATERIALIZED (SELECT 1, 2) SELECT * FROM t) AS _(x, y);

Error: INTERNAL Error: Failed to bind column reference "x" [0.0] (bindings: [9.0])

Edit: This is fixed.

~~Second, pipeline construction of two (or more) materialized recursive CTEs fails:~~

WITH RECURSIVE t(x) AS MATERIALIZED
(
  SELECT 1
    UNION ALL
  SELECT x+1
  FROM   t
  WHERE  x < 4
)
,
u(x) AS
(
  SELECT *
  FROM   t
    UNION ALL
  SELECT u.x + t.x
  FROM   u, t
  WHERE  u.x < 32
)
SELECT *
FROM   u;

Error: INTERNAL Error: Assertion triggered in file "/duckdb/src/parallel/executor.cpp" on line 156: event_map_entry != event_map.end()

Edit: This is fixed.

Mytherin

Thanks for the PR! Looks good - very cool feature! I have left some comments inline. One note is that we have been working to remove C-style pointers (see #7080) - this might cause a few merge conflicts on your end.

SELECT x FROM (WITH t(y, z) AS MATERIALIZED (SELECT 1, 2) SELECT * FROM t) AS _(x, y);

Error: INTERNAL Error: Failed to bind column reference "x" [0.0] (bindings: [9.0])

This is the column binding resolver that complains. Essentially "x" is bound as the first column to table binding 0, but table binding 0 is not accessible from that part of the plan.

Second, pipeline construction of two (or more) materialized recursive CTEs fails:

I'm not sure about what causes this exactly - I would guess that something goes wrong in the order in which BuildPipelines is executed so that the layered situation is not resolved correctly, or perhaps the incorrect pipeline is passed on to the child.

Perhaps it would also be interesting to add a benchmark where the benefits of the materialized CTEs are visible?

src/execution/physical_plan/plan_recursive_cte.cpp

src/include/duckdb/execution/operator/set/physical_cte.hpp

src/include/duckdb/execution/physical_plan_generator.hpp

src/include/duckdb/parallel/pipeline.hpp

src/planner/binder/query_node/bind_cte_node.cpp

kryonix · 2023-04-21T07:59:19Z

The binder issue seems to be resolved now.

Thank you for the comments. I will address them.

Thanks for the PR! Looks good - very cool feature! I have left some comments inline. One note is that we have been working to remove C-style pointers (see #7080) - this might cause a few merge conflicts on your end.

I think I will just rebase onto master and do the rewritings before I take this pr out of its draft status. Should be a clean solution.

…ations

…ator

…perations

kryonix · 2023-05-25T06:02:50Z

I think all remaining issues are now resolved.

kryonix · 2023-05-25T15:16:38Z

NVM I guess. ALTERNATIVE_VERIFY still has some issues 👀

Some test cases can (and should!) be re-enabled when decorrelation of materialized CTEs is implemented.

…erify mode

kryonix · 2023-06-07T14:02:49Z

If you find the time, @Mytherin, I think this pr is ready for review now.

Mytherin

Thanks for the fixes! Looks great to me now. One minor comment otherwise this is good to go. Could you also merge with feature so the CI can rerun? I believe the CI failures should be fixed then.

Mytherin · 2023-06-15T12:19:50Z

src/parser/transform/statement/transform_update.cpp

+		TransformCTE(*PGPointerCast<duckdb_libpgquery::PGWithClause>(stmt.withClause), result->cte_map,
+		             materialized_ctes);
+		if (!materialized_ctes.empty()) {
+			throw NotImplementedException("Materialized CTEs are not implemented for delete.");


Should this be update - also could you perhaps expand on the reason for this?

You are right, the message is wrong. I will fix that.

There is an AST 'mismatch' currently. Materialized CTEs are represented as a QueryNode, whereasINSERT/UPDATE/DELETE are SQLStatements. This means, that it is easy to represent the materialized CTEs as a bunch of stacked QueryNodes (this happens in Transformer::TransformMaterializedCTE). It is not that easy for INSERT/UPDATE/DELETE, however. While there should not be a principle problem implementing that, my current plan is to tackle that in a separate pr.

Mytherin · 2023-06-15T12:21:12Z

test/sql/cte/materialized/dml_materialized_cte.test

+statement ok
+PRAGMA enable_verification
+
+require noalternativeverify


Is this necessary here?

Alternative verify would lead to non-MATERIALIZED CTEs here. Therefore, the tests would be unexpectedly successful.

Mytherin · 2023-06-20T19:26:41Z

Thanks!

@neumannt

Until now, DuckDB's default behavior for CTEs was to inline them, which means that the CTE is replaced with its definition in the main query. However, inlining can not only lead to performance issues, especially when the CTE is used multiple times in the main query, but also to incorrect results in some cases. With the introduction of the `WITH ... AS [NOT] MATERIALIZED` syntax in #7126, users can specify that a CTE should be materialized, meaning that it will be computed once and stored in memory for the duration of the main query. This can improve performance and ensure correct results when the CTE is used multiple times. This PR is a continuation of that work. While we still want to be able to inline CTEs in some cases, it should not be the default behavior anymore. More importantly, this should not be the responsibility of the `Binder`, but rather an `Optimizer` decision. For CTEs with `MATERIALIZED` or `NOT MATERIALIZED` specified, nothing changes. If a CTE is marked as `MATERIALIZED`, it will be materialized, and if it is marked as `NOT MATERIALIZED`, it will be inlined—regardless of the possibly questionable performance or correctness implications. For CTEs without a `MATERIALIZED` or `NOT MATERIALIZED` clause, the `Optimizer` will decide whether to inline or materialize the CTE. The rules for this decision are currently a work in progress. --- **Performance** @neumannt released a solution of the Advent of Code 2024 using SQL: https://github.com/neumannt/aoc24 All solutions rely heavily on CTEs, but do not use explicit MATERIALIZATION hints. I use his queries as a benchmark—using the full AoC input: | DAY | Speedup with this PR vs. DuckDB main | |-----|---------------------------------------| | 1 | 2.3x | | 2 | 1.7x | | 3 | 1.6x | | 4 | 2.7x | | 5 | 99.3x | | 6 | 1810x (now ~18 sec, main ~9h) | | 7 | 11.8x | | 8 | 1.2x | | 9 |156.2x | | 10 | 1.7x | | 11 | 1.2x | | 12 | 2.3x | | 13 | 3.2x | | 14 | 308x (now ~1.5s, main ~8 min) | | 15 | > 10x (now ~2 min, main timeout) | | 16 | TBD | | 17 | Not supported | | 18 | > 73x (now ~8.5 sec, main timeout) | | 19 | 2.2x | | 20 | 28x (now ~8 sec, main ~3 min 50s) | | 21 | 24.2x | | 22 | Not supported | | 23 | 188x (now ~260ms, main ~48 sec) | | 24 | Not supported | | 25 | > 2245x (now ~250ms, main timeout) | I think these numbers speak for themselves. All queries experienced a speedup, and the most problematic queries are now fast enough to run in a reasonable time frame. Speedups range from 1.2x to over 2000x, which—I think—is a significant improvement. --- `logical_operator_deep_copy` is a new visitor that allows us to _"deep copy"_ a logical operator tree. While we can already get a 1:1 copy of a logical operator using `Copy`, we can not use that copy to immediately replace a CTE reference in the main query. This is because the copy has the same `table_index`es as the original tree, which breaks some sanity checks. To fix this, we traverse the tree and assign new `table_index`es to each operator. --- TODO: - [x] Improve the rules for inlining vs. materializing CTEs - [x] Fix the unit tests for `WITH RECURSIVE` queries, that are currently failing because they relied on the inlining behavior - [x] Clean up some rough edges in the code - [x] Add more tests for the new `Optimizer` behavior --- Fix: #17456 Fix: #12875 Fix: #15416 Fix: #16891 Fix: #9940 Fix: #14244

Mytherin reviewed Apr 20, 2023

View reviewed changes

kryonix force-pushed the master branch from 3ad8d2b to c2b2046 Compare May 2, 2023 08:58

kryonix added 26 commits May 9, 2023 10:43

Add parsing for MATERIALIZED CTEs

616cda7

Add new CTENode for materialized CTEs to parser

bf320c0

Fix transformation of materialized CTEs for recursive CTEs

f52e6ab

Add bound_cte_node to bind materialized CTEs

91bb6c9

Add binding of materialized CTEs

bc21a41

Add LOGICAL_CTE operator and type

985bcba

Add logical plan generation for materialized CTEs

03e8141

Fix comment in BaseTableRef binder

7fe664e

Add physical operator types CTE and CTE_SCAN

ae31209

Add cte_dependencies to Pipeline class to keep track of CTE_SCAN oper…

3083685

…ations

Add materialized_ctes and materialized_cte_ids to physical plan gener…

f15f8d5

…ator

Add PhysicalCTE operator

2fe6b7f

Add physical plan generation for LogicalCTE node

29c9f09

Adapt physical plan generation of LogicalCTERef for materialized CTEs

e616374

Adapt BuildPipelines of physical_column_data_scan for materialized CTEs

93b5a8f

Move materialized CTE handling to Transformer

3eb9ab3

Improve TransformSelectInternal and add CTE materialization for set o…

306ece7

…perations

Throw exception when materialized CTE is used in DELETE statement

4ad74ac

Throw exception when materialized CTE is used in INSERT statement

f94f3fb

Throw exception when materialized CTE is used in UPDATE statement

948ace5

Throw exception when materialized CTE is used in PIVOT statement

70580cd

Fix toString method of CTENode

dbeebc5

Remove unused assertion from LogicalCTERef physical plan generator

3566cfc

Improve EXPLAIN output of CTE, RECURSIVE_CTE and COLUMN_DATA_SCAN

ed0fe93

Add test cases for materialized CTEs

9ffc9ca

Add check for unplanned subqueries to logical planning of BoundCTENode

3ffb90b

kryonix requested a review from Mytherin May 25, 2023 15:01

kryonix added 5 commits May 25, 2023 18:04

Fix alternative verify for materialized CTEs

8a2140f

Some test cases can (and should!) be re-enabled when decorrelation of materialized CTEs is implemented.

Fix two more alternative verify errors

0ca6480

Fix code coverage

f4ae191

Throw binder error when trying to flatten correlated materialized CTE

aade34e

Fix uncovered_files.csv

29de1ac

kryonix force-pushed the master branch from d23026b to dbfe96d Compare May 28, 2023 19:11

Fix more alternative verify issues

410ed0c

kryonix force-pushed the master branch from dbfe96d to 410ed0c Compare May 29, 2023 06:59

kryonix added 6 commits May 30, 2023 08:05

Merge remote-tracking branch 'origin/feature'

bf2e318

Add tests for materialized CTEs and DML statements

f461ead

Merge remote-tracking branch 'origin/feature'

59aab9e

Fix materialized cte DML tests

e56c993

Add noalternativeverify to materialized dml CTEs

fa0a0a6

Only skip tests with require alternativeverify, when in alternative v…

eafdf1a

…erify mode

Mytherin reviewed Jun 15, 2023

View reviewed changes

kryonix and others added 4 commits June 15, 2023 16:17

Fix materialized CTE exception in transform_update.cpp

3cdb739

Merge remote-tracking branch 'origin/feature'

1819e80

Merge remote-tracking branch 'origin/feature'

58e0f46

Fix uncovered files

08a181e

Mytherin merged commit 09fd4e3 into duckdb:feature Jun 20, 2023

szarnyasg mentioned this pull request Sep 5, 2023

Document WITH RECURSIVE ... [[NOT] MATERIALIZED] duckdb/duckdb-web#1089

Merged

kryonix mentioned this pull request Feb 27, 2024

Add support for materialized CTEs in INSERT/UPDATE/DELETE statements #10878

Merged

kryonix mentioned this pull request Dec 29, 2024

CTE does implicit and unexpected cross join when referencing columns that aren't in the table in the from clause #15416

Closed

2 tasks

kryonix mentioned this pull request May 13, 2025

Make CTE Materialization the Default Instead of Inlining #17459

Merged

4 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Add support for materialized CTEs #7126

Add support for materialized CTEs #7126

Uh oh!

kryonix commented Apr 18, 2023

Uh oh!

kryonix commented Apr 18, 2023 •

edited

Loading

Uh oh!

Mytherin left a comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

kryonix commented Apr 21, 2023 •

edited

Loading

Uh oh!

kryonix commented May 25, 2023

Uh oh!

kryonix commented May 25, 2023

Uh oh!

kryonix commented Jun 7, 2023

Uh oh!

Mytherin left a comment

Uh oh!

Mytherin Jun 15, 2023

Uh oh!

kryonix Jun 15, 2023

Uh oh!

Mytherin Jun 15, 2023

Uh oh!

kryonix Jun 15, 2023 •

edited

Loading

Uh oh!

Mytherin commented Jun 20, 2023

Uh oh!

Uh oh!

Add support for materialized CTEs #7126

Add support for materialized CTEs #7126

Uh oh!

Conversation

kryonix commented Apr 18, 2023

Uh oh!

kryonix commented Apr 18, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Mytherin left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

kryonix commented Apr 21, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

kryonix commented May 25, 2023

Uh oh!

kryonix commented May 25, 2023

Uh oh!

kryonix commented Jun 7, 2023

Uh oh!

Mytherin left a comment

Choose a reason for hiding this comment

Uh oh!

Mytherin Jun 15, 2023

Choose a reason for hiding this comment

Uh oh!

kryonix Jun 15, 2023

Choose a reason for hiding this comment

Uh oh!

Mytherin Jun 15, 2023

Choose a reason for hiding this comment

Uh oh!

kryonix Jun 15, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Mytherin commented Jun 20, 2023

Uh oh!

Uh oh!

kryonix commented Apr 18, 2023 •

edited

Loading

kryonix commented Apr 21, 2023 •

edited

Loading

kryonix Jun 15, 2023 •

edited

Loading