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

6 files changed, 57 insertions, 2 deletions

diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index caed683ba92..40ae489c235 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -471,6 +471,8 @@ typedef enum NodeTag
 	T_WithClause,
 	T_InferClause,
 	T_OnConflictClause,
+	T_CTESearchClause,
+	T_CTECycleClause,
 	T_CommonTableExpr,
 	T_RoleSpec,
 	T_TriggerTransition,
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index 068c6ec4401..236832a2ca7 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -1439,9 +1439,8 @@ typedef struct OnConflictClause
 /*
  * CommonTableExpr -
  *	   representation of WITH list element
- *
- * We don't currently support the SEARCH or CYCLE clause.
  */
+
 typedef enum CTEMaterialize
 {
 	CTEMaterializeDefault,		/* no option specified */
@@ -1449,6 +1448,31 @@ typedef enum CTEMaterialize
 	CTEMaterializeNever			/* NOT MATERIALIZED */
 } CTEMaterialize;
 
+typedef struct CTESearchClause
+{
+	NodeTag		type;
+	List	   *search_col_list;
+	bool		search_breadth_first;
+	char	   *search_seq_column;
+	int			location;
+} CTESearchClause;
+
+typedef struct CTECycleClause
+{
+	NodeTag		type;
+	List	   *cycle_col_list;
+	char	   *cycle_mark_column;
+	Node	   *cycle_mark_value;
+	Node	   *cycle_mark_default;
+	char	   *cycle_path_column;
+	int			location;
+	/* These fields are set during parse analysis: */
+	Oid			cycle_mark_type;	/* common type of _value and _default */
+	int			cycle_mark_typmod;
+	Oid			cycle_mark_collation;
+	Oid			cycle_mark_neop;	/* <> operator for type */
+} CTECycleClause;
+
 typedef struct CommonTableExpr
 {
 	NodeTag		type;
@@ -1457,6 +1481,8 @@ typedef struct CommonTableExpr
 	CTEMaterialize ctematerialized; /* is this an optimization fence? */
 	/* SelectStmt/InsertStmt/etc before parse analysis, Query afterwards: */
 	Node	   *ctequery;		/* the CTE's subquery */
+	CTESearchClause *search_clause;
+	CTECycleClause *cycle_clause;
 	int			location;		/* token location, or -1 if unknown */
 	/* These fields are set during parse analysis: */
 	bool		cterecursive;	/* is this CTE actually recursive? */
diff --git a/src/include/parser/analyze.h b/src/include/parser/analyze.h
index fede4be820a..4a3c9686f90 100644
--- a/src/include/parser/analyze.h
+++ b/src/include/parser/analyze.h
@@ -46,4 +46,6 @@ extern void applyLockingClause(Query *qry, Index rtindex,
 extern List *BuildOnConflictExcludedTargetlist(Relation targetrel,
 											   Index exclRelIndex);
 
+extern SortGroupClause *makeSortGroupClauseForSetOp(Oid rescoltype);
+
 #endif							/* ANALYZE_H */
diff --git a/src/include/parser/kwlist.h b/src/include/parser/kwlist.h
index 8c554e1f690..28083aaac9d 100644
--- a/src/include/parser/kwlist.h
+++ b/src/include/parser/kwlist.h
@@ -60,6 +60,7 @@ PG_KEYWORD("binary", BINARY, TYPE_FUNC_NAME_KEYWORD, BARE_LABEL)
 PG_KEYWORD("bit", BIT, COL_NAME_KEYWORD, BARE_LABEL)
 PG_KEYWORD("boolean", BOOLEAN_P, COL_NAME_KEYWORD, BARE_LABEL)
 PG_KEYWORD("both", BOTH, RESERVED_KEYWORD, BARE_LABEL)
+PG_KEYWORD("breadth", BREADTH, UNRESERVED_KEYWORD, BARE_LABEL)
 PG_KEYWORD("by", BY, UNRESERVED_KEYWORD, BARE_LABEL)
 PG_KEYWORD("cache", CACHE, UNRESERVED_KEYWORD, BARE_LABEL)
 PG_KEYWORD("call", CALL, UNRESERVED_KEYWORD, BARE_LABEL)
@@ -128,6 +129,7 @@ PG_KEYWORD("delete", DELETE_P, UNRESERVED_KEYWORD, BARE_LABEL)
 PG_KEYWORD("delimiter", DELIMITER, UNRESERVED_KEYWORD, BARE_LABEL)
 PG_KEYWORD("delimiters", DELIMITERS, UNRESERVED_KEYWORD, BARE_LABEL)
 PG_KEYWORD("depends", DEPENDS, UNRESERVED_KEYWORD, BARE_LABEL)
+PG_KEYWORD("depth", DEPTH, UNRESERVED_KEYWORD, BARE_LABEL)
 PG_KEYWORD("desc", DESC, RESERVED_KEYWORD, BARE_LABEL)
 PG_KEYWORD("detach", DETACH, UNRESERVED_KEYWORD, BARE_LABEL)
 PG_KEYWORD("dictionary", DICTIONARY, UNRESERVED_KEYWORD, BARE_LABEL)
diff --git a/src/include/parser/parse_node.h b/src/include/parser/parse_node.h
index dfc214b06fb..176b9f37c1f 100644
--- a/src/include/parser/parse_node.h
+++ b/src/include/parser/parse_node.h
@@ -78,6 +78,7 @@ typedef enum ParseExprKind
 	EXPR_KIND_CALL_ARGUMENT,	/* procedure argument in CALL */
 	EXPR_KIND_COPY_WHERE,		/* WHERE condition in COPY FROM */
 	EXPR_KIND_GENERATED_COLUMN, /* generation expression for a column */
+	EXPR_KIND_CYCLE_MARK,		/* cycle mark value */
 } ParseExprKind;
 
 
@@ -294,6 +295,7 @@ struct ParseNamespaceColumn
 	Oid			p_varcollid;	/* OID of collation, or InvalidOid */
 	Index		p_varnosyn;		/* rangetable index of syntactic referent */
 	AttrNumber	p_varattnosyn;	/* attribute number of syntactic referent */
+	bool		p_dontexpand;	/* not included in star expansion */
 };
 
 /* Support for parser_errposition_callback function */
diff --git a/src/include/rewrite/rewriteSearchCycle.h b/src/include/rewrite/rewriteSearchCycle.h
new file mode 100644
index 00000000000..257fb7cdab7
--- /dev/null
+++ b/src/include/rewrite/rewriteSearchCycle.h
@@ -0,0 +1,21 @@
+/*-------------------------------------------------------------------------
+ *
+ * rewriteSearchCycle.h
+ *		Support for rewriting SEARCH and CYCLE clauses.
+ *
+ *
+ * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/rewrite/rewriteSearchCycle.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef REWRITESEARCHCYCLE_H
+#define REWRITESEARCHCYCLE_H
+
+#include "nodes/parsenodes.h"
+
+extern CommonTableExpr *rewriteSearchAndCycle(CommonTableExpr *cte);
+
+#endif							/* REWRITESEARCHCYCLE_H */