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.

< 8000 !-- no margin wins, so we check it last and use its value if true. -->

…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!

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

Enable materialized CTEs for PIVOT statements and add tests for it

e49e7c0

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 6D47 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

Mer 8C3E ged

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

Open

2 tasks

kryonix mentioned this pull request May 13, 2025

DRAFT: Make CTE Materialization the Default Instead of Inlining #17459

Draft

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!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Add support for materialized CTEs #7126

Add support for materialized CTEs #7126

Uh oh!

Conversation

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!