SEARCH and CYCLE clauses

This adds the SQL standard feature that adds the SEARCH and CYCLE
clauses to recursive queries to be able to do produce breadth- or
depth-first search orders and detect cycles.  These clauses can be
rewritten into queries using existing syntax, and that is what this
patch does in the rewriter.

Reviewed-by: Vik Fearing <vik@postgresfriends.org>
Reviewed-by: Pavel Stehule <pavel.stehule@gmail.com>
Discussion: https://www.postgresql.org/message-id/flat/db80ceee-6f97-9b4a-8ee8-3ba0c58e5be2@2ndquadrant.com

8 files changed, 354 insertions, 29 deletions

diff --git a/src/backend/parser/analyze.c b/src/backend/parser/analyze.c
index 65483892252..0f3a70c49a8 100644
--- a/src/backend/parser/analyze.c
+++ b/src/backend/parser/analyze.c
@@ -1810,6 +1810,33 @@ transformSetOperationStmt(ParseState *pstate, SelectStmt *stmt)
 }
 
 /*
+ * Make a SortGroupClause node for a SetOperationStmt's groupClauses
+ */
+SortGroupClause *
+makeSortGroupClauseForSetOp(Oid rescoltype)
+{
+	SortGroupClause *grpcl = makeNode(SortGroupClause);
+	Oid			sortop;
+	Oid			eqop;
+	bool		hashable;
+
+	/* determine the eqop and optional sortop */
+	get_sort_group_operators(rescoltype,
+							 false, true, false,
+							 &sortop, &eqop, NULL,
+							 &hashable);
+
+	/* we don't have a tlist yet, so can't assign sortgrouprefs */
+	grpcl->tleSortGroupRef = 0;
+	grpcl->eqop = eqop;
+	grpcl->sortop = sortop;
+	grpcl->nulls_first = false; /* OK with or without sortop */
+	grpcl->hashable = hashable;
+
+	return grpcl;
+}
+
+/*
  * transformSetOperationTree
  *		Recursively transform leaves and internal nodes of a set-op tree
  *
@@ -2109,31 +2136,15 @@ transformSetOperationTree(ParseState *pstate, SelectStmt *stmt,
 			 */
 			if (op->op != SETOP_UNION || !op->all)
 			{
-				SortGroupClause *grpcl = makeNode(SortGroupClause);
-				Oid			sortop;
-				Oid			eqop;
-				bool		hashable;
 				ParseCallbackState pcbstate;
 
 				setup_parser_errposition_callback(&pcbstate, pstate,
 												  bestlocation);
 
-				/* determine the eqop and optional sortop */
-				get_sort_group_operators(rescoltype,
-										 false, true, false,
-										 &sortop, &eqop, NULL,
-										 &hashable);
+				op->groupClauses = lappend(op->groupClauses,
+										   makeSortGroupClauseForSetOp(rescoltype));
 
 				cancel_parser_errposition_callback(&pcbstate);
-
-				/* we don't have a tlist yet, so can't assign sortgrouprefs */
-				grpcl->tleSortGroupRef = 0;
-				grpcl->eqop = eqop;
-				grpcl->sortop = sortop;
-				grpcl->nulls_first = false; /* OK with or without sortop */
-				grpcl->hashable = hashable;
-
-				op->groupClauses = lappend(op->groupClauses, grpcl);
 			}
 
 			/*
diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y
index b2f447bf9a2..dd72a9fc3c4 100644
--- a/src/backend/parser/gram.y
+++ b/src/backend/parser/gram.y
@@ -494,6 +494,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query);
 %type <list>	row explicit_row implicit_row type_list array_expr_list
 %type <node>	case_expr case_arg when_clause case_default
 %type <list>	when_clause_list
+%type <node>	opt_search_clause opt_cycle_clause
 %type <ival>	sub_type opt_materialized
 %type <value>	NumericOnly
 %type <list>	NumericOnly_list
@@ -625,7 +626,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query);
 	ASSERTION ASSIGNMENT ASYMMETRIC AT ATTACH ATTRIBUTE AUTHORIZATION
 
 	BACKWARD BEFORE BEGIN_P BETWEEN BIGINT BINARY BIT
-	BOOLEAN_P BOTH BY
+	BOOLEAN_P BOTH BREADTH BY
 
 	CACHE CALL CALLED CASCADE CASCADED CASE CAST CATALOG_P CHAIN CHAR_P
 	CHARACTER CHARACTERISTICS CHECK CHECKPOINT CLASS CLOSE
@@ -637,7 +638,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query);
 	CURRENT_TIME CURRENT_TIMESTAMP CURRENT_USER CURSOR CYCLE
 
 	DATA_P DATABASE DAY_P DEALLOCATE DEC DECIMAL_P DECLARE DEFAULT DEFAULTS
-	DEFERRABLE DEFERRED DEFINER DELETE_P DELIMITER DELIMITERS DEPENDS DESC
+	DEFERRABLE DEFERRED DEFINER DELETE_P DELIMITER DELIMITERS DEPENDS DEPTH DESC
 	DETACH DICTIONARY DISABLE_P DISCARD DISTINCT DO DOCUMENT_P DOMAIN_P
 	DOUBLE_P DROP
 
@@ -11353,8 +11354,6 @@ simple_select:
  * WITH [ RECURSIVE ] <query name> [ (<column>,...) ]
  *		AS (query) [ SEARCH or CYCLE clause ]
  *
- * We don't currently support the SEARCH or CYCLE clause.
- *
  * Recognizing WITH_LA here allows a CTE to be named TIME or ORDINALITY.
  */
 with_clause:
@@ -11386,13 +11385,15 @@ cte_list:
 		| cte_list ',' common_table_expr		{ $$ = lappend($1, $3); }
 		;
 
-common_table_expr:  name opt_name_list AS opt_materialized '(' PreparableStmt ')'
+common_table_expr:  name opt_name_list AS opt_materialized '(' PreparableStmt ')' opt_search_clause opt_cycle_clause
 			{
 				CommonTableExpr *n = makeNode(CommonTableExpr);
 				n->ctename = $1;
 				n->aliascolnames = $2;
 				n->ctematerialized = $4;
 				n->ctequery = $6;
+				n->search_clause = castNode(CTESearchClause, $8);
+				n->cycle_clause = castNode(CTECycleClause, $9);
 				n->location = @1;
 				$$ = (Node *) n;
 			}
@@ -11404,6 +11405,49 @@ opt_materialized:
 		| /*EMPTY*/								{ $$ = CTEMaterializeDefault; }
 		;
 
+opt_search_clause:
+		SEARCH DEPTH FIRST_P BY columnList SET ColId
+			{
+				CTESearchClause *n = makeNode(CTESearchClause);
+				n->search_col_list = $5;
+				n->search_breadth_first = false;
+				n->search_seq_column = $7;
+				n->location = @1;
+				$$ = (Node *) n;
+			}
+		| SEARCH BREADTH FIRST_P BY columnList SET ColId
+			{
+				CTESearchClause *n = makeNode(CTESearchClause);
+				n->search_col_list = $5;
+				n->search_breadth_first = true;
+				n->search_seq_column = $7;
+				n->location = @1;
+				$$ = (Node *) n;
+			}
+		| /*EMPTY*/
+			{
+				$$ = NULL;
+			}
+		;
+
+opt_cycle_clause:
+		CYCLE columnList SET ColId TO AexprConst DEFAULT AexprConst USING ColId
+			{
+				CTECycleClause *n = makeNode(CTECycleClause);
+				n->cycle_col_list = $2;
+				n->cycle_mark_column = $4;
+				n->cycle_mark_value = $6;
+				n->cycle_mark_default = $8;
+				n->cycle_path_column = $10;
+				n->location = @1;
+				$$ = (Node *) n;
+			}
+		| /*EMPTY*/
+			{
+				$$ = NULL;
+			}
+		;
+
 opt_with_clause:
 		with_clause								{ $$ = $1; }
 		| /*EMPTY*/								{ $$ = NULL; }
@@ -15222,6 +15266,7 @@ unreserved_keyword:
 			| BACKWARD
 			| BEFORE
 			| BEGIN_P
+			| BREADTH
 			| BY
 			| CACHE
 			| CALL
@@ -15266,6 +15311,7 @@ unreserved_keyword:
 			| DELIMITER
 			| DELIMITERS
 			| DEPENDS
+			| DEPTH
 			| DETACH
 			| DICTIONARY
 			| DISABLE_P
@@ -15733,6 +15779,7 @@ bare_label_keyword:
 			| BIT
 			| BOOLEAN_P
 			| BOTH
+			| BREADTH
 			| BY
 			| CACHE
 			| CALL
@@ -15797,6 +15844,7 @@ bare_label_keyword:
 			| DELIMITER
 			| DELIMITERS
 			| DEPENDS
+			| DEPTH
 			| DESC
 			| DETACH
 			| DICTIONARY
diff --git a/src/backend/parser/parse_agg.c b/src/backend/parser/parse_agg.c
index 588f005dd93..fd08b9eeff0 100644
--- a/src/backend/parser/parse_agg.c
+++ b/src/backend/parser/parse_agg.c
@@ -545,6 +545,10 @@ check_agglevels_and_constraints(ParseState *pstate, Node *expr)
 
 			break;
 
+		case EXPR_KIND_CYCLE_MARK:
+			errkind = true;
+			break;
+
 			/*
 			 * There is intentionally no default: case here, so that the
 			 * compiler will warn if we add a new ParseExprKind without
@@ -933,6 +937,9 @@ transformWindowFuncCall(ParseState *pstate, WindowFunc *wfunc,
 		case EXPR_KIND_GENERATED_COLUMN:
 			err = _("window functions are not allowed in column generation expressions");
 			break;
+		case EXPR_KIND_CYCLE_MARK:
+			errkind = true;
+			break;
 
 			/*
 			 * There is intentionally no default: case here, so that the
diff --git a/src/backend/parser/parse_cte.c b/src/backend/parser/parse_cte.c
index 4e0029c58c9..f4f7041ead0 100644
--- a/src/backend/parser/parse_cte.c
+++ b/src/backend/parser/parse_cte.c
@@ -18,9 +18,13 @@
 #include "catalog/pg_type.h"
 #include "nodes/nodeFuncs.h"
 #include "parser/analyze.h"
+#include "parser/parse_coerce.h"
+#include "parser/parse_collate.h"
 #include "parser/parse_cte.h"
+#include "parser/parse_expr.h"
 #include "utils/builtins.h"
 #include "utils/lsyscache.h"
+#include "utils/typcache.h"
 
 
 /* Enumeration of contexts in which a self-reference is disallowed */
@@ -334,6 +338,195 @@ analyzeCTE(ParseState *pstate, CommonTableExpr *cte)
 		if (lctyp != NULL || lctypmod != NULL || lccoll != NULL)	/* shouldn't happen */
 			elog(ERROR, "wrong number of output columns in WITH");
 	}
+
+	if (cte->search_clause || cte->cycle_clause)
+	{
+		Query	   *ctequery;
+		SetOperationStmt *sos;
+
+		if (!cte->cterecursive)
+			ereport(ERROR,
+					(errcode(ERRCODE_SYNTAX_ERROR),
+					 errmsg("WITH query is not recursive"),
+					 parser_errposition(pstate, cte->location)));
+
+		/*
+		 * SQL requires a WITH list element (CTE) to be "expandable" in order
+		 * to allow a search or cycle clause.  That is a stronger requirement
+		 * than just being recursive.  It basically means the query expression
+		 * looks like
+		 *
+		 *     non-recursive query UNION [ALL] recursive query
+		 *
+		 * and that the recursive query is not itself a set operation.
+		 *
+		 * As of this writing, most of these criteria are already satisfied by
+		 * all recursive CTEs allowed by PostgreSQL.  In the future, if
+		 * further variants recursive CTEs are accepted, there might be
+		 * further checks required here to determine what is "expandable".
+		 */
+
+		ctequery = castNode(Query, cte->ctequery);
+		Assert(ctequery->setOperations);
+		sos = castNode(SetOperationStmt, ctequery->setOperations);
+
+		/*
+		 * This left side check is not required for expandability, but
+		 * rewriteSearchAndCycle() doesn't currently have support for it, so
+		 * we catch it here.
+		 */
+		if (!IsA(sos->larg, RangeTblRef))
+			ereport(ERROR,
+					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+					 errmsg("with a SEARCH or CYCLE clause, the left side of the UNION must be a SELECT")));
+
+		if (!IsA(sos->rarg, RangeTblRef))
+			ereport(ERROR,
+					(errcode(ERRCODE_SYNTAX_ERROR),
+					 errmsg("with a SEARCH or CYCLE clause, the right side of the UNION must be a SELECT")));
+	}
+
+	if (cte->search_clause)
+	{
+		ListCell   *lc;
+		List	   *seen = NIL;
+
+		foreach(lc, cte->search_clause->search_col_list)
+		{
+			Value	   *colname = lfirst(lc);
+
+			if (!list_member(cte->ctecolnames, colname))
+				ereport(ERROR,
+						(errcode(ERRCODE_SYNTAX_ERROR),
+						 errmsg("search column \"%s\" not in WITH query column list",
+								strVal(colname)),
+						 parser_errposition(pstate, cte->search_clause->location)));
+
+			if (list_member(seen, colname))
+				ereport(ERROR,
+						(errcode(ERRCODE_DUPLICATE_COLUMN),
+						 errmsg("search column \"%s\" specified more than once",
+								strVal(colname)),
+						 parser_errposition(pstate, cte->search_clause->location)));
+			seen = lappend(seen, colname);
+		}
+
+		if (list_member(cte->ctecolnames, makeString(cte->search_clause->search_seq_column)))
+			ereport(ERROR,
+					errcode(ERRCODE_SYNTAX_ERROR),
+					errmsg("search sequence column name \"%s\" already used in WITH query column list",
+						   cte->search_clause->search_seq_column),
+					parser_errposition(pstate, cte->search_clause->location));
+	}
+
+	if (cte->cycle_clause)
+	{
+		ListCell   *lc;
+		List	   *seen = NIL;
+		TypeCacheEntry *typentry;
+		Oid			op;
+
+		foreach(lc, cte->cycle_clause->cycle_col_list)
+		{
+			Value	   *colname = lfirst(lc);
+
+			if (!list_member(cte->ctecolnames, colname))
+				ereport(ERROR,
+						(errcode(ERRCODE_SYNTAX_ERROR),
+						 errmsg("cycle column \"%s\" not in WITH query column list",
+								strVal(colname)),
+						 parser_errposition(pstate, cte->cycle_clause->location)));
+
+			if (list_member(seen, colname))
+				ereport(ERROR,
+						(errcode(ERRCODE_DUPLICATE_COLUMN),
+						 errmsg("cycle column \"%s\" specified more than once",
+								strVal(colname)),
+						 parser_errposition(pstate, cte->cycle_clause->location)));
+			seen = lappend(seen, colname);
+		}
+
+		if (list_member(cte->ctecolnames, makeString(cte->cycle_clause->cycle_mark_column)))
+			ereport(ERROR,
+					errcode(ERRCODE_SYNTAX_ERROR),
+					errmsg("cycle mark column name \"%s\" already used in WITH query column list",
+						   cte->cycle_clause->cycle_mark_column),
+					parser_errposition(pstate, cte->cycle_clause->location));
+
+		cte->cycle_clause->cycle_mark_value = transformExpr(pstate, cte->cycle_clause->cycle_mark_value,
+															EXPR_KIND_CYCLE_MARK);
+		cte->cycle_clause->cycle_mark_default = transformExpr(pstate, cte->cycle_clause->cycle_mark_default,
+															  EXPR_KIND_CYCLE_MARK);
+
+		if (list_member(cte->ctecolnames, makeString(cte->cycle_clause->cycle_path_column)))
+			ereport(ERROR,
+					errcode(ERRCODE_SYNTAX_ERROR),
+					errmsg("cycle path column name \"%s\" already used in WITH query column list",
+						   cte->cycle_clause->cycle_path_column),
+					parser_errposition(pstate, cte->cycle_clause->location));
+
+		if (strcmp(cte->cycle_clause->cycle_mark_column,
+				   cte->cycle_clause->cycle_path_column) == 0)
+			ereport(ERROR,
+					errcode(ERRCODE_SYNTAX_ERROR),
+					errmsg("cycle mark column name and cycle path column name are the same"),
+					parser_errposition(pstate, cte->cycle_clause->location));
+
+		cte->cycle_clause->cycle_mark_type = select_common_type(pstate,
+																list_make2(cte->cycle_clause->cycle_mark_value,
+																		   cte->cycle_clause->cycle_mark_default),
+																"CYCLE", NULL);
+		cte->cycle_clause->cycle_mark_value = coerce_to_common_type(pstate,
+																	cte->cycle_clause->cycle_mark_value,
+																	cte->cycle_clause->cycle_mark_type,
+																	"CYCLE/SET/TO");
+		cte->cycle_clause->cycle_mark_default = coerce_to_common_type(pstate,
+																	  cte->cycle_clause->cycle_mark_default,
+																	  cte->cycle_clause->cycle_mark_type,
+																	  "CYCLE/SET/DEFAULT");
+
+		cte->cycle_clause->cycle_mark_typmod = select_common_typmod(pstate,
+																	list_make2(cte->cycle_clause->cycle_mark_value,
+																			   cte->cycle_clause->cycle_mark_default),
+																	cte->cycle_clause->cycle_mark_type);
+
+		cte->cycle_clause->cycle_mark_collation = select_common_collation(pstate,
+																		  list_make2(cte->cycle_clause->cycle_mark_value,
+																					 cte->cycle_clause->cycle_mark_default),
+																		  true);
+
+		typentry = lookup_type_cache(cte->cycle_clause->cycle_mark_type, TYPECACHE_EQ_OPR);
+		if (!typentry->eq_opr)
+			ereport(ERROR,
+					errcode(ERRCODE_UNDEFINED_FUNCTION),
+					errmsg("could not identify an equality operator for type %s",
+						   format_type_be(cte->cycle_clause->cycle_mark_type)));
+		op = get_negator(typentry->eq_opr);
+		if (!op)
+			ereport(ERROR,
+					errcode(ERRCODE_UNDEFINED_FUNCTION),
+					errmsg("could not identify an inequality operator for type %s",
+						   format_type_be(cte->cycle_clause->cycle_mark_type)));
+
+		cte->cycle_clause->cycle_mark_neop = op;
+	}
+
+	if (cte->search_clause && cte->cycle_clause)
+	{
+		if (strcmp(cte->search_clause->search_seq_column,
+				   cte->cycle_clause->cycle_mark_column) == 0)
+			ereport(ERROR,
+					errcode(ERRCODE_SYNTAX_ERROR),
+					errmsg("search sequence column name and cycle mark column name are the same"),
+					parser_errposition(pstate, cte->search_clause->location));
+
+		if (strcmp(cte->search_clause->search_seq_column,
+				   cte->cycle_clause->cycle_path_column) == 0)
+			ereport(ERROR,
+					errcode(ERRCODE_SYNTAX_ERROR),
+					errmsg("search_sequence column name and cycle path column name are the same"),
+					parser_errposition(pstate, cte->search_clause->location));
+	}
 }
 
 /*
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 379355f9bff..6c87783b2c7 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -507,6 +507,7 @@ transformColumnRef(ParseState *pstate, ColumnRef *cref)
 		case EXPR_KIND_CALL_ARGUMENT:
 		case EXPR_KIND_COPY_WHERE:
 		case EXPR_KIND_GENERATED_COLUMN:
+		case EXPR_KIND_CYCLE_MARK:
 			/* okay */
 			break;
 
@@ -1723,6 +1724,7 @@ transformSubLink(ParseState *pstate, SubLink *sublink)
 		case EXPR_KIND_RETURNING:
 		case EXPR_KIND_VALUES:
 		case EXPR_KIND_VALUES_SINGLE:
+		case EXPR_KIND_CYCLE_MARK:
 			/* okay */
 			break;
 		case EXPR_KIND_CHECK_CONSTRAINT:
@@ -3044,6 +3046,8 @@ ParseExprKindName(ParseExprKind exprKind)
 			return "WHERE";
 		case EXPR_KIND_GENERATED_COLUMN:
 			return "GENERATED AS";
+		case EXPR_KIND_CYCLE_MARK:
+			return "CYCLE";
 
 			/*
 			 * There is intentionally no default: case here, so that the
diff --git a/src/backend/parser/parse_func.c b/src/backend/parser/parse_func.c
index 07d0013e84b..37cebc7d829 100644
--- a/src/backend/parser/parse_func.c
+++ b/src/backend/parser/parse_func.c
@@ -2527,6 +2527,9 @@ check_srf_call_placement(ParseState *pstate, Node *last_srf, int location)
 		case EXPR_KIND_GENERATED_COLUMN:
 			err = _("set-returning functions are not allowed in column generation expressions");
 			break;
+		case EXPR_KIND_CYCLE_MARK:
+			errkind = true;
+			break;
 
 			/*
 			 * There is intentionally no default: case here, so that the
diff --git a/src/backend/parser/parse_relation.c b/src/backend/parser/parse_relation.c
index e490043cf55..43db4e9af8b 100644
--- a/src/backend/parser/parse_relation.c
+++ b/src/backend/parser/parse_relation.c
@@ -2235,6 +2235,8 @@ addRangeTableEntryForCTE(ParseState *pstate,
 	int			numaliases;
 	int			varattno;
 	ListCell   *lc;
+	int			n_dontexpand_columns = 0;
+	ParseNamespaceItem *psi;
 
 	Assert(pstate != NULL);
 
@@ -2267,9 +2269,9 @@ addRangeTableEntryForCTE(ParseState *pstate,
 					 parser_errposition(pstate, rv->location)));
 	}
 
-	rte->coltypes = cte->ctecoltypes;
-	rte->coltypmods = cte->ctecoltypmods;
-	rte->colcollations = cte->ctecolcollations;
+	rte->coltypes = list_copy(cte->ctecoltypes);
+	rte->coltypmods = list_copy(cte->ctecoltypmods);
+	rte->colcollations = list_copy(cte->ctecolcollations);
 
 	rte->alias = alias;
 	if (alias)
@@ -2294,6 +2296,34 @@ addRangeTableEntryForCTE(ParseState *pstate,
 
 	rte->eref = eref;
 
+	if (cte->search_clause)
+	{
+		rte->eref->colnames = lappend(rte->eref->colnames, makeString(cte->search_clause->search_seq_column));
+		if (cte->search_clause->search_breadth_first)
+			rte->coltypes = lappend_oid(rte->coltypes, RECORDOID);
+		else
+			rte->coltypes = lappend_oid(rte->coltypes, RECORDARRAYOID);
+		rte->coltypmods = lappend_int(rte->coltypmods, -1);
+		rte->colcollations = lappend_oid(rte->colcollations, InvalidOid);
+
+		n_dontexpand_columns += 1;
+	}
+
+	if (cte->cycle_clause)
+	{
+		rte->eref->colnames = lappend(rte->eref->colnames, makeString(cte->cycle_clause->cycle_mark_column));
+		rte->coltypes = lappend_oid(rte->coltypes, cte->cycle_clause->cycle_mark_type);
+		rte->coltypmods = lappend_int(rte->coltypmods, cte->cycle_clause->cycle_mark_typmod);
+		rte->colcollations = lappend_oid(rte->colcollations, cte->cycle_clause->cycle_mark_collation);
+
+		rte->eref->colnames = lappend(rte->eref->colnames, makeString(cte->cycle_clause->cycle_path_column));
+		rte->coltypes = lappend_oid(rte->coltypes, RECORDARRAYOID);
+		rte->coltypmods = lappend_int(rte->coltypmods, -1);
+		rte->colcollations = lappend_oid(rte->colcollations, InvalidOid);
+
+		n_dontexpand_columns += 2;
+	}
+
 	/*
 	 * Set flags and access permissions.
 	 *
@@ -2321,9 +2351,19 @@ addRangeTableEntryForCTE(ParseState *pstate,
 	 * Build a ParseNamespaceItem, but don't add it to the pstate's namespace
 	 * list --- caller must do that if appropriate.
 	 */
-	return buildNSItemFromLists(rte, list_length(pstate->p_rtable),
+	psi = buildNSItemFromLists(rte, list_length(pstate->p_rtable),
 								rte->coltypes, rte->coltypmods,
 								rte->colcollations);
+
+	/*
+	 * The columns added by search and cycle clauses are not included in star
+	 * expansion in queries contained in the CTE.
+	 */
+	if (rte->ctelevelsup > 0)
+		for (int i = 0; i < n_dontexpand_columns; i++)
+			psi->p_nscolumns[list_length(psi->p_rte->eref->colnames) - 1 - i].p_dontexpand = true;
+
+	return psi;
 }
 
 /*
@@ -3008,7 +3048,11 @@ expandNSItemVars(ParseNamespaceItem *nsitem,
 		const char *colname = strVal(colnameval);
 		ParseNamespaceColumn *nscol = nsitem->p_nscolumns + colindex;
 
-		if (colname[0])
+		if (nscol->p_dontexpand)
+		{
+			/* skip */
+		}
+		else if (colname[0])
 		{
 			Var		   *var;
 
diff --git a/src/backend/parser/parse_target.c b/src/backend/parser/parse_target.c
index 7eaa076771a..51ecc16c42e 100644
--- a/src/backend/parser/parse_target.c
+++ b/src/backend/parser/parse_target.c
@@ -399,8 +399,23 @@ markTargetListOrigin(ParseState *pstate, TargetEntry *tle,
 			{
 				CommonTableExpr *cte = GetCTEForRTE(pstate, rte, netlevelsup);
 				TargetEntry *ste;
+				List	   *tl = GetCTETargetList(cte);
+				int			extra_cols = 0;
+
+				/*
+				 * RTE for CTE will already have the search and cycle columns
+				 * added, but the subquery won't, so skip looking those up.
+				 */
+				if (cte->search_clause)
+					extra_cols += 1;
+				if (cte->cycle_clause)
+					extra_cols += 2;
+				if (extra_cols &&
+					attnum > list_length(tl) &&
+					attnum <= list_length(tl) + extra_cols)
+					break;
 
-				ste = get_tle_by_resno(GetCTETargetList(cte), attnum);
+				ste = get_tle_by_resno(tl, attnum);
 				if (ste == NULL || ste->resjunk)
 					elog(ERROR, "CTE %s does not have attribute %d",
 						 rte->eref->aliasname, attnum);