Re: BUG #17320: A SEGV in optimizer

At Mon, 06 Dec 2021 06:42:57 +0000, PG Bug reporting form <noreply@postgresql.org> wrote in 
> The following bug has been logged on the website:
> 
> Bug reference:      17320
> Logged by:          Zhiyong Wu
> Email address:      253540651@qq.com
> PostgreSQL version: 14.1
> Operating system:   Linux version 5.13.0-1-MANJARO (builduser@LEGION)
> Description:        
> 
> PoC:
> WITH RECURSIVE x ( x ) AS ( SELECT 4 UNION ( WITH x AS ( SELECT 5 UNION (
> WITH TIMESTAMP AS ( SELECT 2 UNION ( WITH x ( x ) AS ( SELECT 1 UNION ( WITH
> x AS ( SELECT 6 FROM ( VALUES ( ROW ( 1 , 2 ) ) , ( ROW ( 1 , 4 ) ) ) x ( x
> ) UNION ( WITH x AS ( SELECT 7 ) SELECT * FROM x ) ) SELECT * FROM x UNION
> SELECT * FROM x ) ) SELECT * FROM x ) ) SELECT * FROM ( SELECT * FROM x
> WHERE x = x ) x ) ) SELECT * FROM x ) ) SEARCH BREADTH FIRST BY x SET NCHAR
> SELECT * FROM x WHERE x BETWEEN 0 AND 1000000 ;
>  COPY x FROM STDIN WHERE x IN ( x ( 1 , 5 ) ) ;
>  CREATE OR REPLACE TEMP VIEW x AS SELECT x , x ( x ) OVER ( ORDER BY x ROWS
> BETWEEN 1 PRECEDING AND 1 FOLLOWING EXCLUDE NO OTHERS ) AS x FROM x ( 1 , 10
> ) x ;
>  EXECUTE x ( '-9223372036854775800' ) ;
..
>     #0 0xda215c in bms_add_members
> /root/postgres/bld/../src/backend/nodes/bitmapset.c:806:9
>     #1 0xf25518 in add_vars_to_targetlist
> /root/postgres/bld/../src/backend/optimizer/plan/initsplan.c:259:30
>     #2 0xf250c7 in build_base_rel_tlists

I had the following assertion failure from the original query by
master head.

> TRAP: FailedAssertion("attno >= rel->min_attr && attno <= rel->max_attr", File: "initsplan.c", Line: 249, PID:
25862)

max_attr is 1 and attno is 2 here.  I could reduce the query like this.

WITH RECURSIVE x ( x ) AS
 (SELECT 1
  UNION
  (WITH x AS
    (WITH TIMESTAMP AS (SELECT 2)
     SELECT * FROM x)
   SELECT * FROM x)
 ) SEARCH BREADTH FIRST BY x SET NCHAR
SELECT * FROM x;

If I tried to execute the following query, I got the follwoing
error. This looks like rooted from the same mistake.

WITH RECURSIVE x ( x ) AS
 (SELECT 1
  UNION
  (WITH x AS (SELECT * FROM x)
   SELECT * FROM x)
 ) SEARCH BREADTH FIRST BY x SET NCHAR
SELECT * FROM x;

> ERROR:  could not find attribute 2 in subquery targetlist

The outmost query tries to access nchar that the second level query
doesn't have. The implicit column is not surfaced through the
upper-level CTEs.

By the way, if I executed the following query, I get the following
another assertion failure.

WITH RECURSIVE x ( x ) AS
 (SELECT 1
  UNION
  (WITH y AS (SELECT * FROM x)
   SELECT * FROM y)
 ) SEARCH BREADTH FIRST BY x SET NCHAR
SELECT * FROM x;

> TRAP: FailedAssertion("cte_rtindex > 0", File: "rewriteSearchCycle.c", Line: 398, PID: 31288)

This looks a bit different but rooted from the same issue.

The most simple way to avoid such assertion failures or internal erors
is to reject indirecto references to CTEs that have SEARCH or CYCLE
clause.  I'm not sure it's worth the trouble somehow allowing such
references.

I'm not confident that it is the right fix, but the attached catches
the original problem query and the above reduced queries as syntax
error.

regards.

-- 
Kyotaro Horiguchi
NTT Open Source Software Center
From de9457a23ac343b25e60c7451fea5d59e701da0f Mon Sep 17 00:00:00 2001
From: Kyotaro Horiguchi <horikyota.ntt@gmail.com>
Date: Tue, 7 Dec 2021 16:13:13 +0900
Subject: [PATCH] Reject indirect reference to CTEs with SEARCH or CYCLE clause

SEARCH and CYCLE clauses adds an implicit column to the recursively
referencing quireies then expects the column in the result from the
immediate recursive query and we don't expect another level of CTE is
inserted in-between. Reject indirect recursive references to CTEs that
have SEARCH or CYCLE clause.
---
 src/backend/parser/parse_relation.c | 13 +++++++++++++
 src/test/regress/expected/with.out  |  9 +++++++++
 src/test/regress/sql/with.sql       |  9 +++++++++
 3 files changed, 31 insertions(+)

diff --git a/src/backend/parser/parse_relation.c b/src/backend/parser/parse_relation.c
index c5c3f26ecf..2cc497e0e7 100644
--- a/src/backend/parser/parse_relation.c
+++ b/src/backend/parser/parse_relation.c
@@ -263,6 +263,7 @@ scanNameSpaceForCTE(ParseState *pstate, const char *refname,
                     Index *ctelevelsup)
 {
     Index        levelsup;
+    CommonTableExpr *nearest_cte = NULL;
 
     for (levelsup = 0;
          pstate != NULL;
@@ -270,12 +271,24 @@ scanNameSpaceForCTE(ParseState *pstate, const char *refname,
     {
         ListCell   *lc;
 
+        if (!nearest_cte && pstate->p_parent_cte)
+            nearest_cte = pstate->p_parent_cte;
+
         foreach(lc, pstate->p_ctenamespace)
         {
             CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
 
             if (strcmp(cte->ctename, refname) == 0)
             {
+                /*
+                 * SEARCH and CYCLE clauses adds a hidden column which is not
+                 * revealed to the upper levels.
+                 */
+                if (nearest_cte && nearest_cte != cte &&
+                    (cte->search_clause || cte->cycle_clause))
+                    ereport(ERROR,
+                            (errcode(ERRCODE_SYNTAX_ERROR),
+                             errmsg("indirectly referenced recursive CTE \"%s\" cannot have SEARCH or CYCLE clause",
refname)));
                 *ctelevelsup = levelsup;
                 return cte;
             }
diff --git a/src/test/regress/expected/with.out b/src/test/regress/expected/with.out
index 75e61460d9..a06a0a37ae 100644
--- a/src/test/regress/expected/with.out
+++ b/src/test/regress/expected/with.out
@@ -846,6 +846,15 @@ with recursive search_graph(f, t, label) as (
 ) search depth first by f, t set seq
 select * from search_graph order by seq;
 ERROR:  with a SEARCH or CYCLE clause, the right side of the UNION must be a SELECT
+with recursive search_graph(f, t, label) as (
+    select * from graph0 g
+    union all
+    (with x as
+        (select * from search_graph g)
+        select * from x)
+) search depth first by f, t set seq
+select * from search_graph order by seq;
+ERROR:  indirectly referenced recursive CTE "search_graph" cannot have SEARCH or CYCLE clause
 -- test ruleutils and view expansion
 create temp view v_search as
 with recursive search_graph(f, t, label) as (
diff --git a/src/test/regress/sql/with.sql b/src/test/regress/sql/with.sql
index 46668a903e..987ed4d11b 100644
--- a/src/test/regress/sql/with.sql
+++ b/src/test/regress/sql/with.sql
@@ -464,6 +464,15 @@ with recursive search_graph(f, t, label) as (
 ) search depth first by f, t set seq
 select * from search_graph order by seq;
 
+with recursive search_graph(f, t, label) as (
+    select * from graph0 g
+    union all
+    (with x as
+        (select * from search_graph g)
+        select * from x)
+) search depth first by f, t set seq
+select * from search_graph order by seq;
+
 -- test ruleutils and view expansion
 create temp view v_search as
 with recursive search_graph(f, t, label) as (
-- 
2.27.0