On Fri, Jul 27, 2018 at 02:55:26PM +1200, Thomas Munro wrote: > On Thu, Jul 26, 2018 at 7:14 AM, David Fetter <da...@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/donate
>From f2c2b80653056058b7fb799bb8b9d2c0443ddd5f Mon Sep 17 00:00:00 2001 From: David Fetter <da...@fetter.org> Date: Tue, 24 Jul 2018 22:09:55 -0700 Subject: [PATCH] Inlining CTEs v0004 To: pgsql-hack...@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.out index 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.c index 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.c index 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.c index 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.c index 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.c index 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.h index 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.out index 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.out index 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.out index 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