From: David Fetter <david@fetter.org>
To: Thomas Munro <thomas.munro@enterprisedb.com>
Cc: Andrew Gierth <andrew@tao11.riddles.org.uk>
Cc: Pg Hackers <pgsql-hackers@postgresql.org>
Subject: Re: Early WIP/PoC for inlining CTEs
Date: Fri, 27 Jul 2018 10:10:58 +0200
Message-ID: <20180727081058.GN17411@fetter.org> (raw)
In-Reply-To: <CAEepm=0MKV3MnR4Dn5RkXsK+RnmHEFitqiG4PcBhXtBK4JOoWw@mail.gmail.com>
References: <87sh48ffhb.fsf@news-spur.riddles.org.uk>
<20180725054236.GB17411@fetter.org>
<87bmavfjhy.fsf@news-spur.riddles.org.uk>
<20180725191447.GE17411@fetter.org>
<CAEepm=0MKV3MnR4Dn5RkXsK+RnmHEFitqiG4PcBhXtBK4JOoWw@mail.gmail.com>
On Fri, Jul 27, 2018 at 02:55:26PM +1200, Thomas Munro wrote:
> On Thu, Jul 26, 2018 at 7:14 AM, David Fetter <david@fetter.org> wrote:
> > Please find attached the next version, which passes 'make check'.
>
> ... but not 'make check-world' (contrib/postgres_fdw's EXPLAIN is different).
Please find attached a patch that does.
It doesn't always pass make installcheck-world, but I need to sleep
rather than investigate that at the moment.
Best,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778
Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donateAttachments:
[text/x-diff] 0001-Inlining-CTEs-v0004.patch (18.2K, ../20180727081058.GN17411@fetter.org/2-0001-Inlining-CTEs-v0004.patch)
download | inline diff:
From f2c2b80653056058b7fb799bb8b9d2c0443ddd5f Mon Sep 17 00:00:00 2001
From: David Fetter <david@fetter.org>
Date: Tue, 24 Jul 2018 22:09:55 -0700
Subject: [PATCH] Inlining CTEs v0004
To: pgsql-hackers@postgresql.org
---
.../postgres_fdw/expected/postgres_fdw.out | 22 +--
src/backend/nodes/copyfuncs.c | 1 +
src/backend/nodes/equalfuncs.c | 1 +
src/backend/nodes/outfuncs.c | 1 +
src/backend/nodes/readfuncs.c | 1 +
src/backend/optimizer/plan/subselect.c | 152 ++++++++++++++++++
src/include/nodes/parsenodes.h | 1 +
src/test/regress/expected/rowsecurity.out | 92 +++++------
src/test/regress/expected/rowtypes.out | 13 +-
src/test/regress/expected/rules.out | 6 +-
10 files changed, 209 insertions(+), 81 deletions(-)
diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.outindex f5498c62bd..8bf011df46 100644--- a/contrib/postgres_fdw/expected/postgres_fdw.out+++ b/contrib/postgres_fdw/expected/postgres_fdw.out@@ -1889,21 +1889,15 @@ SELECT t1.c1, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c3, t
-- join in CTE
EXPLAIN (VERBOSE, COSTS OFF)
WITH t (c1_1, c1_3, c2_1) AS (SELECT t1.c1, t1.c3, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1)) SELECT c1_1, c2_1 FROM t ORDER BY c1_3, c1_1 OFFSET 100 LIMIT 10;
- QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------+ QUERY PLAN +------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit
- Output: t.c1_1, t.c2_1, t.c1_3- CTE t- -> Foreign Scan- Output: t1.c1, t1.c3, t2.c1- Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)- Remote SQL: SELECT r1."C 1", r1.c3, r2."C 1" FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1"))))- -> Sort- Output: t.c1_1, t.c2_1, t.c1_3- Sort Key: t.c1_3, t.c1_1- -> CTE Scan on t- Output: t.c1_1, t.c2_1, t.c1_3-(12 rows)+ Output: t1.c1, t2.c1, t1.c3+ -> Foreign Scan+ Output: t1.c1, t2.c1, t1.c3+ Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)+ Remote SQL: SELECT r2."C 1", r3."C 1", r2.c3 FROM ("S 1"."T 1" r2 INNER JOIN "S 1"."T 1" r3 ON (((r2."C 1" = r3."C 1")))) ORDER BY r2.c3 ASC NULLS LAST, r2."C 1" ASC NULLS LAST+(6 rows)
WITH t (c1_1, c1_3, c2_1) AS (SELECT t1.c1, t1.c3, t2.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1)) SELECT c1_1, c2_1 FROM t ORDER BY c1_3, c1_1 OFFSET 100 LIMIT 10;
c1_1 | c2_1
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.cindex 17b650b8cb..8ba2fc1aed 100644--- a/src/backend/nodes/copyfuncs.c+++ b/src/backend/nodes/copyfuncs.c@@ -2530,6 +2530,7 @@ _copyCommonTableExpr(const CommonTableExpr *from)
COPY_NODE_FIELD(ctequery);
COPY_LOCATION_FIELD(location);
COPY_SCALAR_FIELD(cterecursive);
+ COPY_SCALAR_FIELD(ctematerialized);
COPY_SCALAR_FIELD(cterefcount);
COPY_NODE_FIELD(ctecolnames);
COPY_NODE_FIELD(ctecoltypes);
diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.cindex 378f2facb8..2a04506d0d 100644--- a/src/backend/nodes/equalfuncs.c+++ b/src/backend/nodes/equalfuncs.c@@ -2793,6 +2793,7 @@ _equalCommonTableExpr(const CommonTableExpr *a, const CommonTableExpr *b)
COMPARE_NODE_FIELD(ctequery);
COMPARE_LOCATION_FIELD(location);
COMPARE_SCALAR_FIELD(cterecursive);
+ COMPARE_SCALAR_FIELD(ctematerialized);
COMPARE_SCALAR_FIELD(cterefcount);
COMPARE_NODE_FIELD(ctecolnames);
COMPARE_NODE_FIELD(ctecoltypes);
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.cindex a6454ce28b..0ea6b7125a 100644--- a/src/backend/nodes/outfuncs.c+++ b/src/backend/nodes/outfuncs.c@@ -3080,6 +3080,7 @@ _outCommonTableExpr(StringInfo str, const CommonTableExpr *node)
WRITE_NODE_FIELD(ctequery);
WRITE_LOCATION_FIELD(location);
WRITE_BOOL_FIELD(cterecursive);
+ WRITE_BOOL_FIELD(ctematerialized);
WRITE_INT_FIELD(cterefcount);
WRITE_NODE_FIELD(ctecolnames);
WRITE_NODE_FIELD(ctecoltypes);
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.cindex 9a01eb6b63..01db3c1c85 100644--- a/src/backend/nodes/readfuncs.c+++ b/src/backend/nodes/readfuncs.c@@ -409,6 +409,7 @@ _readCommonTableExpr(void)
READ_NODE_FIELD(ctequery);
READ_LOCATION_FIELD(location);
READ_BOOL_FIELD(cterecursive);
+ READ_BOOL_FIELD(ctematerialized);
READ_INT_FIELD(cterefcount);
READ_NODE_FIELD(ctecolnames);
READ_NODE_FIELD(ctecoltypes);
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.cindex 83008d7661..5aa242ff26 100644--- a/src/backend/optimizer/plan/subselect.c+++ b/src/backend/optimizer/plan/subselect.c@@ -1146,6 +1146,141 @@ hash_ok_operator(OpExpr *expr)
}
+struct inline_cte_walker_ctx+{+ const char *ctename;+ int levelsup;+ int refcount;+ Query *ctequery;+ CommonTableExpr *cte;+};++static bool inline_cte_walker(Node *node, void *ctxp)+{+ struct inline_cte_walker_ctx *ctx = ctxp;++ if (!node)+ return false;++ if (IsA(node, Query))+ {+ /*+ * This one is a bit tricky. It's our job to handle the recursion here,+ * but we do some of the lifting normally handled by query_tree_walker+ * in order to get the sequence of operations right.+ *+ * First, if the Query we're looking at is the one containing our CTE+ * definition, then we don't need to recurse into our own CTE or CTEs+ * that are earlier in the list than ours (since cteList has been+ * sorted for us into dependency order). We could check whether a+ * nested query is hiding ours, but that seems too much of an edge case+ * to be worth optimizing (the levelsup check will ensure we don't+ * replace any CTEs improperly). So we scan the cteList ourselves+ * rather than having query_tree_walker do it.+ *+ * Second, we want to walk the rangetable _before_ replacing any+ * RTE_CTE nodes, in order to avoid re-walking the subquery we just+ * inlined. (range_table_walker, if told to visit the RTE nodes at all,+ * visits them before their content.) So we have range_table_walker+ * ignore the RTE nodes themselves and only walk their contents.+ *+ * Third, we scan the rangetable for RTE_CTE nodes to replace.+ *+ * Fourth, we use query_tree_walker to find and walk the rest of the+ * query, telling it to ignore the rangetable and CTEs.+ *+ * Note that ctx->levelsup is -1 on entry the first time, since we need+ * the incremented value to be 0 when scanning the content of the query+ * containing the definition.+ */+ Query *query = castNode(Query, node);+ ListCell *lc;+ bool do_replace = ctx->levelsup >= 0;++ ctx->levelsup++;++ foreach (lc, query->cteList)+ {+ CommonTableExpr *cte = lfirst_node(CommonTableExpr, lc);++ if (!do_replace && strcmp(cte->ctename, ctx->ctename) == 0)+ do_replace = true;+ else if (do_replace)+ inline_cte_walker(cte->ctequery, ctxp);+ }++ range_table_walker(query->rtable, inline_cte_walker, ctxp, 0);++ foreach (lc, query->rtable)+ {+ RangeTblEntry *rte = lfirst_node(RangeTblEntry, lc);++ if (rte->rtekind == RTE_CTE &&+ strcmp(rte->ctename, ctx->ctename) == 0 &&+ rte->ctelevelsup == ctx->levelsup)+ {+ Query *newquery = ctx->ctequery;++ /*+ * We need to do some work here that view rewrite does not, and+ * in turn we do not do some work that view rewrite does.+ *+ * Firstly, views can't have outer references but CTEs can+ * (especially in the case of CTEs referencing other CTEs), so+ * we need to fix up all levelsup attributes inside the CTE+ * query.+ *+ * Secondly, views (and explicit subqueries) currently have+ * different behaviour w.r.t. SELECT FOR UPDATE than CTEs do. A+ * FOR UPDATE clause is treated as extending into views and+ * subqueries, but not into CTEs. We preserve this distinction+ * by not trying to push rowmarks into the new subquery.+ *+ * We avoid copyObject if possible because subquery processing+ * copies the query too.+ */+ if (ctx->levelsup > 0)+ {+ newquery = copyObject(newquery);+ IncrementVarSublevelsUp((Node *) newquery, ctx->levelsup, 1);+ }++ /*+ * Here's where we do the actual substitution.+ */+ rte->rtekind = RTE_SUBQUERY;+ rte->subquery = newquery;+ rte->security_barrier = false;++ ctx->refcount--;+ }+ }++ query_tree_walker(query, inline_cte_walker, ctxp,+ QTW_IGNORE_RANGE_TABLE | QTW_IGNORE_CTE_SUBQUERIES);++ ctx->levelsup--;++ return false;+ }++ return expression_tree_walker(node, inline_cte_walker, ctxp);+}++static void inline_cte(PlannerInfo *root, CommonTableExpr *cte)+{+ struct inline_cte_walker_ctx ctx;+ ctx.ctequery = castNode(Query, cte->ctequery);+ ctx.ctename = cte->ctename;+ ctx.refcount = cte->cterefcount;+ ctx.levelsup = -1;+ ctx.cte = cte;+ inline_cte_walker((Node *) root->parse, &ctx);+ /* we must replace all references */+ Assert(ctx.refcount == 0);+}++
/*
* SS_process_ctes: process a query's WITH list
*
@@ -1183,6 +1318,23 @@ SS_process_ctes(PlannerInfo *root)
continue;
}
+ /*+ * Consider inlining the CTE rather than planning it separately.+ */+ if (cmdType == CMD_SELECT &&+ !cte->ctematerialized &&+ !cte->cterecursive &&+ !((cte->cterefcount > 1) && contain_volatile_functions(cte->ctequery)) &&+ (castNode(Query, cte->ctequery)->rowMarks == NIL)+ )+ {+ inline_cte(root, cte);++ /* Make a dummy entry in cte_plan_ids */+ root->cte_plan_ids = lappend_int(root->cte_plan_ids, -1);+ continue;+ }+
/*
* Copy the source Query node. Probably not necessary, but let's keep
* this similar to make_subplan.
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.hindex 7855cff30d..047d3de71c 100644--- a/src/include/nodes/parsenodes.h+++ b/src/include/nodes/parsenodes.h@@ -1397,6 +1397,7 @@ typedef struct CommonTableExpr
int location; /* token location, or -1 if unknown */
/* These fields are set during parse analysis: */
bool cterecursive; /* is this CTE actually recursive? */
+ bool ctematerialized; /* is this an optimization fence? */
int cterefcount; /* number of RTEs referencing this CTE
* (excluding internal self-references) */
List *ctecolnames; /* list of output column names */
diff --git a/src/test/regress/expected/rowsecurity.out b/src/test/regress/expected/rowsecurity.outindex bc16ca4c43..0d8d382830 100644--- a/src/test/regress/expected/rowsecurity.out+++ b/src/test/regress/expected/rowsecurity.out@@ -2181,29 +2181,25 @@ EXPLAIN (COSTS OFF) EXECUTE plancache_test;
PREPARE plancache_test2 AS WITH q AS (SELECT * FROM z1 WHERE f_leak(b)) SELECT * FROM q,z2;
EXPLAIN (COSTS OFF) EXECUTE plancache_test2;
- QUERY PLAN --------------------------------------------------+ QUERY PLAN +-----------------------------------------------------
Nested Loop
- CTE q- -> Seq Scan on z1- Filter: (((a % 2) = 0) AND f_leak(b))- -> CTE Scan on q+ -> Seq Scan on z2
-> Materialize
- -> Seq Scan on z2-(7 rows)+ -> Seq Scan on z1+ Filter: (((a % 2) = 0) AND f_leak(b))+(5 rows)
PREPARE plancache_test3 AS WITH q AS (SELECT * FROM z2) SELECT * FROM q,z1 WHERE f_leak(z1.b);
EXPLAIN (COSTS OFF) EXECUTE plancache_test3;
QUERY PLAN
-----------------------------------------------------
Nested Loop
- CTE q- -> Seq Scan on z2- -> CTE Scan on q+ -> Seq Scan on z2
-> Materialize
-> Seq Scan on z1
Filter: (((a % 2) = 0) AND f_leak(b))
-(7 rows)+(5 rows)
SET ROLE regress_rls_group1;
SELECT * FROM z1 WHERE f_leak(b);
@@ -2230,28 +2226,24 @@ EXPLAIN (COSTS OFF) EXECUTE plancache_test;
(2 rows)
EXPLAIN (COSTS OFF) EXECUTE plancache_test2;
- QUERY PLAN --------------------------------------------------+ QUERY PLAN +-----------------------------------------------------
Nested Loop
- CTE q- -> Seq Scan on z1- Filter: (((a % 2) = 0) AND f_leak(b))- -> CTE Scan on q+ -> Seq Scan on z2
-> Materialize
- -> Seq Scan on z2-(7 rows)+ -> Seq Scan on z1+ Filter: (((a % 2) = 0) AND f_leak(b))+(5 rows)
EXPLAIN (COSTS OFF) EXECUTE plancache_test3;
QUERY PLAN
-----------------------------------------------------
Nested Loop
- CTE q- -> Seq Scan on z2- -> CTE Scan on q+ -> Seq Scan on z2
-> Materialize
-> Seq Scan on z1
Filter: (((a % 2) = 0) AND f_leak(b))
-(7 rows)+(5 rows)
SET SESSION AUTHORIZATION regress_rls_carol;
SELECT * FROM z1 WHERE f_leak(b);
@@ -2278,28 +2270,24 @@ EXPLAIN (COSTS OFF) EXECUTE plancache_test;
(2 rows)
EXPLAIN (COSTS OFF) EXECUTE plancache_test2;
- QUERY PLAN --------------------------------------------------+ QUERY PLAN +-----------------------------------------------------
Nested Loop
- CTE q- -> Seq Scan on z1- Filter: (((a % 2) = 1) AND f_leak(b))- -> CTE Scan on q+ -> Seq Scan on z2
-> Materialize
- -> Seq Scan on z2-(7 rows)+ -> Seq Scan on z1+ Filter: (((a % 2) = 1) AND f_leak(b))+(5 rows)
EXPLAIN (COSTS OFF) EXECUTE plancache_test3;
QUERY PLAN
-----------------------------------------------------
Nested Loop
- CTE q- -> Seq Scan on z2- -> CTE Scan on q+ -> Seq Scan on z2
-> Materialize
-> Seq Scan on z1
Filter: (((a % 2) = 1) AND f_leak(b))
-(7 rows)+(5 rows)
SET ROLE regress_rls_group2;
SELECT * FROM z1 WHERE f_leak(b);
@@ -2326,28 +2314,24 @@ EXPLAIN (COSTS OFF) EXECUTE plancache_test;
(2 rows)
EXPLAIN (COSTS OFF) EXECUTE plancache_test2;
- QUERY PLAN --------------------------------------------------+ QUERY PLAN +-----------------------------------------------------
Nested Loop
- CTE q- -> Seq Scan on z1- Filter: (((a % 2) = 1) AND f_leak(b))- -> CTE Scan on q+ -> Seq Scan on z2
-> Materialize
- -> Seq Scan on z2-(7 rows)+ -> Seq Scan on z1+ Filter: (((a % 2) = 1) AND f_leak(b))+(5 rows)
EXPLAIN (COSTS OFF) EXECUTE plancache_test3;
QUERY PLAN
-----------------------------------------------------
Nested Loop
- CTE q- -> Seq Scan on z2- -> CTE Scan on q+ -> Seq Scan on z2
-> Materialize
-> Seq Scan on z1
Filter: (((a % 2) = 1) AND f_leak(b))
-(7 rows)+(5 rows)
--
-- Views should follow policy for view owner.
@@ -2854,13 +2838,11 @@ NOTICE: f_leak => 98f13708210194c475687be6106a3b84
(11 rows)
EXPLAIN (COSTS OFF) WITH cte1 AS (SELECT * FROM t1 WHERE f_leak(b)) SELECT * FROM cte1;
- QUERY PLAN --------------------------------------------------- CTE Scan on cte1- CTE cte1- -> Seq Scan on t1- Filter: (((a % 2) = 0) AND f_leak(b))-(4 rows)+ QUERY PLAN +-----------------------------------------+ Seq Scan on t1+ Filter: (((a % 2) = 0) AND f_leak(b))+(2 rows)
WITH cte1 AS (UPDATE t1 SET a = a + 1 RETURNING *) SELECT * FROM cte1; --fail
ERROR: new row violates row-level security policy for table "t1"
diff --git a/src/test/regress/expected/rowtypes.out b/src/test/regress/expected/rowtypes.outindex 30053d07df..c0df2f6333 100644--- a/src/test/regress/expected/rowtypes.out+++ b/src/test/regress/expected/rowtypes.out@@ -1041,14 +1041,11 @@ with r(a,b) as
(values (1,row(1,2)), (1,row(null,null)), (1,null),
(null,row(1,2)), (null,row(null,null)), (null,null) )
select r, r is null as isnull, r is not null as isnotnull from r;
- QUERY PLAN ------------------------------------------------------------ CTE Scan on r- Output: r.*, (r.* IS NULL), (r.* IS NOT NULL)- CTE r- -> Values Scan on "*VALUES*"- Output: "*VALUES*".column1, "*VALUES*".column2-(5 rows)+ QUERY PLAN +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ Values Scan on "*VALUES*"+ Output: ROW("*VALUES*".column1, "*VALUES*".column2), (("*VALUES*".column1 IS NULL) AND ("*VALUES*".column2 IS NOT DISTINCT FROM NULL)), (("*VALUES*".column1 IS NOT NULL) AND ("*VALUES*".column2 IS DISTINCT FROM NULL))+(2 rows)
with r(a,b) as
(values (1,row(1,2)), (1,row(null,null)), (1,null),
diff --git a/src/test/regress/expected/rules.out b/src/test/regress/expected/rules.outindex 744d501e31..882469b79f 100644--- a/src/test/regress/expected/rules.out+++ b/src/test/regress/expected/rules.out@@ -3135,10 +3135,8 @@ RETURNING *;
Conflict Resolution: UPDATE
Conflict Arbiter Indexes: hat_data_unique_idx
Conflict Filter: ((excluded.hat_color <> 'forbidden'::bpchar) AND (hat_data.* <> excluded.*))
- CTE data- -> Values Scan on "*VALUES*"- -> CTE Scan on data-(7 rows)+ -> Values Scan on "*VALUES*"+(5 rows)
SELECT * FROM hat_data WHERE hat_name IN ('h8', 'h9', 'h7') ORDER BY hat_name;
hat_name | hat_color
--
2.17.1
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: david@fetter.org, thomas.munro@enterprisedb.com, andrew@tao11.riddles.org.uk
Subject: Re: Early WIP/PoC for inlining CTEs
In-Reply-To: <20180727081058.GN17411@fetter.org>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox