Fix generate_useful_gather_paths for parallel unsafe pathkeys

From 065c299bdaa5585b89d174ce649bf973dbf1c34d Mon Sep 17 00:00:00 2001
From: jcoleman <jtc331@gmail.com>
Date: Wed, 25 Nov 2020 15:53:49 -0500
Subject: [PATCH v2 4/5] Remove volatile expr target search

While prepare_sort_from_pathkeys has to be concerned about matching up a
volatile expression to the proper tlist entry, we don't need to do that
here since such a sort will have to be postponed anyway.
---
 src/backend/optimizer/path/equivclass.c | 27 +++++--------------------
 1 file changed, 5 insertions(+), 22 deletions(-)

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index ac2ed7aff1..f36c57ed81 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -819,7 +819,6 @@ find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, Rel
 		EquivalenceMember *em = lfirst(lc_em);
 		Expr	   *em_expr = em->em_expr;
 		PathTarget *target = rel->reltarget;
-		ListCell   *lc_target_expr;
 
 		/*
 		 * We shouldn't be trying to sort by an equivalence class that
@@ -850,30 +849,14 @@ find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, Rel
 		 * As long as the expression isn't volatile then
 		 * prepare_sort_from_pathkeys is able to generate a new target entry,
 		 * so there's no need to verify that one already exists.
+		 *
+		 * While prepare_sort_from_pathkeys has to be concerned about matching
+		 * up a volatile expression to the proper tlist entry, it doesn't seem
+		 * valuable here to expend the work trying to find a match in the
+		 * target's exprs since such a sort will have to be postponed anyway.
 		 */
 		if (!ec->ec_has_volatile)
 			return em->em_expr;
-
-		/*
-		 * If, however, it's volatile, we have to verify that the
-		 * equivalence member's expr is already generated in the
-		 * relation's target (we do strip relabels first from both
-		 * expressions, which is cheap and might allow us to match
-		 * more expressions).
-		 */
-		while (em_expr && IsA(em_expr, RelabelType))
-			em_expr = ((RelabelType *) em_expr)->arg;
-
-		foreach(lc_target_expr, target->exprs)
-		{
-			Expr	   *target_expr = lfirst(lc_target_expr);
-
-			while (target_expr && IsA(target_expr, RelabelType))
-				target_expr = ((RelabelType *) target_expr)->arg;
-
-			if (equal(target_expr, em_expr))
-				return em->em_expr;
-		}
 	}
 
 	/* We didn't find any suitable equivalence class expression */
-- 
2.17.1

From 1dd54123ec95cfc2df66ccf1189bff1df70d15e7 Mon Sep 17 00:00:00 2001
From: jcoleman <jtc331@gmail.com>
Date: Wed, 25 Nov 2020 15:46:00 -0500
Subject: [PATCH v2 3/5] Disallow SRFs in proactive sort

So they can be evaluated at the proper time as determiend by
make_sort_input_target.
---
 src/backend/optimizer/path/equivclass.c        |  8 ++++++++
 src/backend/optimizer/util/tlist.c             |  5 -----
 src/include/optimizer/optimizer.h              |  5 +++++
 src/test/regress/expected/incremental_sort.out | 12 ++++++++++++
 src/test/regress/sql/incremental_sort.sql      |  2 ++
 5 files changed, 27 insertions(+), 5 deletions(-)

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index e47a16827d..ac2ed7aff1 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -838,6 +838,14 @@ find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, Rel
 
 		if (parallel && !is_parallel_safe(root, (Node *) em_expr))
 			continue;
+
+		/*
+		 * Disallow SRFs so that all of them can be evaluated at the correct
+		 * time as determined by make_sort_input_target.
+		 */
+		if (IS_SRF_CALL((Node *) em_expr))
+			continue;
+
 		/*
 		 * As long as the expression isn't volatile then
 		 * prepare_sort_from_pathkeys is able to generate a new target entry,
diff --git a/src/backend/optimizer/util/tlist.c b/src/backend/optimizer/util/tlist.c
index 02a3c6b165..01cea102ea 100644
--- a/src/backend/optimizer/util/tlist.c
+++ b/src/backend/optimizer/util/tlist.c
@@ -21,11 +21,6 @@
 #include "optimizer/tlist.h"
 
 
-/* Test if an expression node represents a SRF call.  Beware multiple eval! */
-#define IS_SRF_CALL(node) \
-	((IsA(node, FuncExpr) && ((FuncExpr *) (node))->funcretset) || \
-	 (IsA(node, OpExpr) && ((OpExpr *) (node))->opretset))
-
 /*
  * Data structures for split_pathtarget_at_srfs().  To preserve the identity
  * of sortgroupref items even if they are textually equal(), what we track is
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h
index 3e4171056e..1e135652b9 100644
--- a/src/include/optimizer/optimizer.h
+++ b/src/include/optimizer/optimizer.h
@@ -24,6 +24,11 @@
 
 #include "nodes/parsenodes.h"
 
+/* Test if an expression node represents a SRF call.  Beware multiple eval! */
+#define IS_SRF_CALL(node) \
+	((IsA(node, FuncExpr) && ((FuncExpr *) (node))->funcretset) || \
+	 (IsA(node, OpExpr) && ((OpExpr *) (node))->opretset))
+
 /*
  * We don't want to include nodes/pathnodes.h here, because non-planner
  * code should generally treat PlannerInfo as an opaque typedef.
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index d316a7c4b9..a8cbfd9f5f 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1620,3 +1620,15 @@ order by 1, 2;
                ->  Function Scan on generate_series
 (7 rows)
 
+-- Disallow pushing down sort when pathkey is an SRF.
+explain (costs off) select unique1 from tenk1 order by unnest('{1,2}'::int[]);
+                               QUERY PLAN                                
+-------------------------------------------------------------------------
+ Sort
+   Sort Key: (unnest('{1,2}'::integer[]))
+   ->  Gather
+         Workers Planned: 2
+         ->  ProjectSet
+               ->  Parallel Index Only Scan using tenk1_unique1 on tenk1
+(6 rows)
+
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index ff3af0fd16..62a037b0cf 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -267,3 +267,5 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
 explain (costs off) select sub.unique1, stringu1 || random()::text
 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
 order by 1, 2;
+-- Disallow pushing down sort when pathkey is an SRF.
+explain (costs off) select unique1 from tenk1 order by unnest('{1,2}'::int[]);
-- 
2.17.1

From 4ff3140640a2cba300dfe4993a16932bf6e96ba9 Mon Sep 17 00:00:00 2001
From: James Coleman <jtc331@gmail.com>
Date: Fri, 20 Nov 2020 20:29:51 -0500
Subject: [PATCH v2 2/5] Enforce parallel safety of pathkeys in
 generate_useful_gather_paths

If, for example, a pathkey expression (e.g., a correlated subquery which
is currently always treated this way) is unsafe for parallel query then
we must not generate a gather merge path with either incremental or full
sort including that pathkey.
---
 src/backend/optimizer/path/allpaths.c         | 13 ++++--
 src/backend/optimizer/path/equivclass.c       |  7 +++-
 src/include/optimizer/paths.h                 |  2 +-
 .../regress/expected/incremental_sort.out     | 40 +++++++++++++++++++
 src/test/regress/sql/incremental_sort.sql     | 11 +++++
 5 files changed, 68 insertions(+), 5 deletions(-)

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 672a20760c..ac21b08801 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2802,6 +2802,9 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
  * This allows us to do incremental sort on top of an index scan under a gather
  * merge node, i.e. parallelized.
  *
+ * If the parallel argument is true then we'll require that pathkey expressions
+ * be parallel safe.
+ *
  * XXX At the moment this can only ever return a list with a single element,
  * because it looks at query_pathkeys only. So we might return the pathkeys
  * directly, but it seems plausible we'll want to consider other orderings
@@ -2809,7 +2812,7 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
  * merge joins.
  */
 static List *
-get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
+get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel, bool parallel)
 {
 	List	   *useful_pathkeys_list = NIL;
 
@@ -2839,8 +2842,12 @@ get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
 			 * meet criteria of EC membership in the current relation, we
 			 * enable not just an incremental sort on the entirety of
 			 * query_pathkeys but also incremental sort below a JOIN.
+			 *
+			 * By passing true for the final argument
+			 * find_em_expr_usable_for_sorting_rel will ensure the chosen
+			 * expression is parallel safe.
 			 */
-			if (!find_em_expr_usable_for_sorting_rel(pathkey_ec, rel))
+			if (!find_em_expr_usable_for_sorting_rel(root, pathkey_ec, rel, true))
 				break;
 
 			npathkeys++;
@@ -2894,7 +2901,7 @@ generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_r
 	generate_gather_paths(root, rel, override_rows);
 
 	/* consider incremental sort for interesting orderings */
-	useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel);
+	useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true);
 
 	/* used for explicit (full) sort paths */
 	cheapest_partial_path = linitial(rel->partial_pathlist);
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index f98fd7b3eb..e47a16827d 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -801,9 +801,12 @@ find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel)
  * Find an equivalence class member expression that can be safely used by a
  * sort node on top of the provided relation. The rules here must match those
  * applied in prepare_sort_from_pathkeys.
+ *
+ * If parallel is set to true, then we'll also enforce that the chosen
+ * expression is parallel safe.
  */
 Expr *
-find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel)
+find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel, bool parallel)
 {
 	ListCell   *lc_em;
 
@@ -833,6 +836,8 @@ find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel)
 		if (!bms_is_subset(em->em_relids, rel->relids))
 			continue;
 
+		if (parallel && !is_parallel_safe(root, (Node *) em_expr))
+			continue;
 		/*
 		 * As long as the expression isn't volatile then
 		 * prepare_sort_from_pathkeys is able to generate a new target entry,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 8a4c6f8b59..afe1b41a4d 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -135,7 +135,7 @@ extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
 												  Relids rel,
 												  bool create_it);
 extern Expr *find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel);
-extern Expr *find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel);
+extern Expr *find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel, bool parallel);
 extern void generate_base_implied_equalities(PlannerInfo *root);
 extern List *generate_join_implied_equalities(PlannerInfo *root,
 											  Relids join_relids,
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 51471ae92d..d316a7c4b9 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1551,6 +1551,46 @@ order by 1, 2;
    ->  Function Scan on generate_series
 (7 rows)
 
+-- Parallel sort but with expression (correlated subquery) that
+-- is prohibited in parallel plans.
+explain (costs off) select distinct
+  unique1,
+  (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000);
+                                   QUERY PLAN                                    
+---------------------------------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: t.unique1, ((SubPlan 1))
+         ->  Gather
+               Workers Planned: 2
+               ->  Nested Loop
+                     ->  Parallel Index Only Scan using tenk1_unique1 on tenk1 t
+                     ->  Function Scan on generate_series
+               SubPlan 1
+                 ->  Index Only Scan using tenk1_unique1 on tenk1
+                       Index Cond: (unique1 = t.unique1)
+(11 rows)
+
+explain (costs off) select
+  unique1,
+  (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000)
+order by 1, 2;
+                                QUERY PLAN                                 
+---------------------------------------------------------------------------
+ Sort
+   Sort Key: t.unique1, ((SubPlan 1))
+   ->  Gather
+         Workers Planned: 2
+         ->  Nested Loop
+               ->  Parallel Index Only Scan using tenk1_unique1 on tenk1 t
+               ->  Function Scan on generate_series
+         SubPlan 1
+           ->  Index Only Scan using tenk1_unique1 on tenk1
+                 Index Cond: (unique1 = t.unique1)
+(10 rows)
+
 -- Parallel sort but with expression not available until the upper rel.
 explain (costs off) select distinct sub.unique1, stringu1 || random()::text
 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index cb48f200ce..ff3af0fd16 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -250,6 +250,17 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
 explain (costs off) select sub.unique1, md5(stringu1)
 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
 order by 1, 2;
+-- Parallel sort but with expression (correlated subquery) that
+-- is prohibited in parallel plans.
+explain (costs off) select distinct
+  unique1,
+  (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000);
+explain (costs off) select
+  unique1,
+  (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000)
+order by 1, 2;
 -- Parallel sort but with expression not available until the upper rel.
 explain (costs off) select distinct sub.unique1, stringu1 || random()::text
 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
-- 
2.17.1

From dd611ec536f7aef74cea6a64dac1a56dc7cc13ff Mon Sep 17 00:00:00 2001
From: jcoleman <jtc331@gmail.com>
Date: Sun, 29 Nov 2020 09:13:02 -0500
Subject: [PATCH v2 5/5] Document find_em_expr_usable_for_sorting_rel in
 prepare_sort_from_pathkeys

---
 src/backend/optimizer/plan/createplan.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 40abe6f9f6..db31ee6c0f 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -5848,6 +5848,9 @@ make_incrementalsort(Plan *lefttree, int numCols, int nPresortedCols,
  *
  * Returns the node which is to be the input to the Sort (either lefttree,
  * or a Result stacked atop lefttree).
+ *
+ * Note: Restrictions on what expressions are safely sortable may also need to
+ * be added to find_em_expr_usable_for_sorting_rel.
  */
 static Plan *
 prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
-- 
2.17.1

From b378e8c2bb76d61da11ce834d55939987ffa1289 Mon Sep 17 00:00:00 2001
From: jcoleman <jtc331@gmail.com>
Date: Fri, 20 Nov 2020 16:19:00 +0000
Subject: [PATCH v2 1/5] generate_useful_gather_paths shouldn't skip unsorted
 subpaths

This appears to be a copy/paste thinko from when we added this function.
Here's the issue: the comment claims that we should skip subpaths that
aren't sorted at all since we can't possibly use a gather merge directly
or with an incremental sort applied first. It's true that we can't do
either of those things unless the subpath is already at least partially
sorted. But subsequently we attempt to construct a gather merge path on
top of a full sort (for the cheapest path), and there's no reason to
limit that to partially sorted paths (indeed in the presence of
incremental sort it seems unlikely that that would be the cheapest path).

We still don't want to build incremental sort paths if the subpath has
no pathkeys, but that will imply presorted_keys = 0, which we already
check.
---
 src/backend/optimizer/path/allpaths.c          |  8 --------
 src/test/regress/expected/incremental_sort.out | 13 +++++++++++++
 src/test/regress/sql/incremental_sort.sql      |  4 ++++
 3 files changed, 17 insertions(+), 8 deletions(-)

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 84a69b064a..672a20760c 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2914,14 +2914,6 @@ generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_r
 			Path	   *subpath = (Path *) lfirst(lc2);
 			GatherMergePath *path;
 
-			/*
-			 * If the path has no ordering at all, then we can't use either
-			 * incremental sort or rely on implicit sorting with a gather
-			 * merge.
-			 */
-			if (subpath->pathkeys == NIL)
-				continue;
-
 			is_sorted = pathkeys_count_contained_in(useful_pathkeys,
 													subpath->pathkeys,
 													&presorted_keys);
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 7cf2eee7c1..51471ae92d 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1468,6 +1468,19 @@ explain (costs off) select * from t union select * from t order by 1,3;
                            ->  Parallel Seq Scan on t t_1
 (13 rows)
 
+-- Full sort, not just incremental sort can be pushed below a gather merge path
+-- by generate_useful_gather_paths.
+explain (costs off) select distinct a,b from t;
+                QUERY PLAN                
+------------------------------------------
+ Unique
+   ->  Gather Merge
+         Workers Planned: 2
+         ->  Sort
+               Sort Key: a, b
+               ->  Parallel Seq Scan on t
+(6 rows)
+
 drop table t;
 -- Sort pushdown can't go below where expressions are part of the rel target.
 -- In particular this is interesting for volatile expressions which have to
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 3ee11c394b..cb48f200ce 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -220,6 +220,10 @@ explain (costs off) select a,b,sum(c) from t group by 1,2 order by 1,2,3 limit 1
 set enable_hashagg to off;
 explain (costs off) select * from t union select * from t order by 1,3;
 
+-- Full sort, not just incremental sort can be pushed below a gather merge path
+-- by generate_useful_gather_paths.
+explain (costs off) select distinct a,b from t;
+
 drop table t;
 
 -- Sort pushdown can't go below where expressions are part of the rel target.
-- 
2.17.1

From 714aacfea72dfa202457923befefa3a401309369 Mon Sep 17 00:00:00 2001
From: jcoleman <jtc331@gmail.com>
Date: Sun, 29 Nov 2020 09:13:02 -0500
Subject: [PATCH v3 5/5] Document find_em_expr_usable_for_sorting_rel in
 prepare_sort_from_pathkeys

---
 src/backend/optimizer/path/equivclass.c | 9 ++++++---
 src/backend/optimizer/plan/createplan.c | 3 +++
 2 files changed, 9 insertions(+), 3 deletions(-)

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index e098b6066b..067c969100 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -798,9 +798,12 @@ find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel)
 }
 
 /*
- * Find an equivalence class member expression that can be safely used by a
- * sort node on top of the provided relation. The rules here must match those
- * applied in prepare_sort_from_pathkeys.
+ * Find an equivalence class member expression that can be safely used to build
+ * a sort node using the provided relation. The applied rules parallel those
+ * applied in prepare_sort_from_pathkeys but are a subset of that function since
+ * here we are concerned with proactive sorts while prepare_sort_from_pathkeys
+ * must deal with sorts that must be delayed until the last stages of query
+ * execution.
  */
 Expr *
 find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel, bool require_parallel_safe)
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 40abe6f9f6..db31ee6c0f 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -5848,6 +5848,9 @@ make_incrementalsort(Plan *lefttree, int numCols, int nPresortedCols,
  *
  * Returns the node which is to be the input to the Sort (either lefttree,
  * or a Result stacked atop lefttree).
+ *
+ * Note: Restrictions on what expressions are safely sortable may also need to
+ * be added to find_em_expr_usable_for_sorting_rel.
  */
 static Plan *
 prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
-- 
2.17.1

From ec3f4dc5f48d4d6ed062aff7d7ca51998642dd85 Mon Sep 17 00:00:00 2001
From: jcoleman <jtc331@gmail.com>
Date: Wed, 25 Nov 2020 15:53:49 -0500
Subject: [PATCH v3 4/5] Remove volatile expr target search

While prepare_sort_from_pathkeys has to be concerned about matching up a
volatile expression to the proper tlist entry, we don't need to do that
here since such a sort will have to be postponed anyway.
---
 src/backend/optimizer/path/equivclass.c | 27 +++++--------------------
 1 file changed, 5 insertions(+), 22 deletions(-)

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 8c3ef98d73..e098b6066b 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -816,7 +816,6 @@ find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, Rel
 		EquivalenceMember *em = lfirst(lc_em);
 		Expr	   *em_expr = em->em_expr;
 		PathTarget *target = rel->reltarget;
-		ListCell   *lc_target_expr;
 
 		/*
 		 * We shouldn't be trying to sort by an equivalence class that
@@ -847,30 +846,14 @@ find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, Rel
 		 * As long as the expression isn't volatile then
 		 * prepare_sort_from_pathkeys is able to generate a new target entry,
 		 * so there's no need to verify that one already exists.
+		 *
+		 * While prepare_sort_from_pathkeys has to be concerned about matching
+		 * up a volatile expression to the proper tlist entry, it doesn't seem
+		 * valuable here to expend the work trying to find a match in the
+		 * target's exprs since such a sort will have to be postponed anyway.
 		 */
 		if (!ec->ec_has_volatile)
 			return em->em_expr;
-
-		/*
-		 * If, however, it's volatile, we have to verify that the
-		 * equivalence member's expr is already generated in the
-		 * relation's target (we do strip relabels first from both
-		 * expressions, which is cheap and might allow us to match
-		 * more expressions).
-		 */
-		while (em_expr && IsA(em_expr, RelabelType))
-			em_expr = ((RelabelType *) em_expr)->arg;
-
-		foreach(lc_target_expr, target->exprs)
-		{
-			Expr	   *target_expr = lfirst(lc_target_expr);
-
-			while (target_expr && IsA(target_expr, RelabelType))
-				target_expr = ((RelabelType *) target_expr)->arg;
-
-			if (equal(target_expr, em_expr))
-				return em->em_expr;
-		}
 	}
 
 	/* We didn't find any suitable equivalence class expression */
-- 
2.17.1

From 3cc9d13869e25b546bf113d57e5015b5ab2c2abf Mon Sep 17 00:00:00 2001
From: jcoleman <jtc331@gmail.com>
Date: Wed, 25 Nov 2020 15:46:00 -0500
Subject: [PATCH v3 3/5] Disallow SRFs in proactive sort

So they can be evaluated at the proper time as determiend by
make_sort_input_target.
---
 src/backend/optimizer/path/equivclass.c        |  8 ++++++++
 src/backend/optimizer/util/tlist.c             |  5 -----
 src/include/optimizer/optimizer.h              |  5 +++++
 src/test/regress/expected/incremental_sort.out | 12 ++++++++++++
 src/test/regress/sql/incremental_sort.sql      |  2 ++
 5 files changed, 27 insertions(+), 5 deletions(-)

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 75cb1750a8..8c3ef98d73 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -835,6 +835,14 @@ find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, Rel
 
 		if (require_parallel_safe && !is_parallel_safe(root, (Node *) em_expr))
 			continue;
+
+		/*
+		 * Disallow SRFs so that all of them can be evaluated at the correct
+		 * time as determined by make_sort_input_target.
+		 */
+		if (IS_SRF_CALL((Node *) em_expr))
+			continue;
+
 		/*
 		 * As long as the expression isn't volatile then
 		 * prepare_sort_from_pathkeys is able to generate a new target entry,
diff --git a/src/backend/optimizer/util/tlist.c b/src/backend/optimizer/util/tlist.c
index 02a3c6b165..01cea102ea 100644
--- a/src/backend/optimizer/util/tlist.c
+++ b/src/backend/optimizer/util/tlist.c
@@ -21,11 +21,6 @@
 #include "optimizer/tlist.h"
 
 
-/* Test if an expression node represents a SRF call.  Beware multiple eval! */
-#define IS_SRF_CALL(node) \
-	((IsA(node, FuncExpr) && ((FuncExpr *) (node))->funcretset) || \
-	 (IsA(node, OpExpr) && ((OpExpr *) (node))->opretset))
-
 /*
  * Data structures for split_pathtarget_at_srfs().  To preserve the identity
  * of sortgroupref items even if they are textually equal(), what we track is
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h
index 3e4171056e..1e135652b9 100644
--- a/src/include/optimizer/optimizer.h
+++ b/src/include/optimizer/optimizer.h
@@ -24,6 +24,11 @@
 
 #include "nodes/parsenodes.h"
 
+/* Test if an expression node represents a SRF call.  Beware multiple eval! */
+#define IS_SRF_CALL(node) \
+	((IsA(node, FuncExpr) && ((FuncExpr *) (node))->funcretset) || \
+	 (IsA(node, OpExpr) && ((OpExpr *) (node))->opretset))
+
 /*
  * We don't want to include nodes/pathnodes.h here, because non-planner
  * code should generally treat PlannerInfo as an opaque typedef.
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index d316a7c4b9..a8cbfd9f5f 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1620,3 +1620,15 @@ order by 1, 2;
                ->  Function Scan on generate_series
 (7 rows)
 
+-- Disallow pushing down sort when pathkey is an SRF.
+explain (costs off) select unique1 from tenk1 order by unnest('{1,2}'::int[]);
+                               QUERY PLAN                                
+-------------------------------------------------------------------------
+ Sort
+   Sort Key: (unnest('{1,2}'::integer[]))
+   ->  Gather
+         Workers Planned: 2
+         ->  ProjectSet
+               ->  Parallel Index Only Scan using tenk1_unique1 on tenk1
+(6 rows)
+
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index ff3af0fd16..62a037b0cf 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -267,3 +267,5 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
 explain (costs off) select sub.unique1, stringu1 || random()::text
 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
 order by 1, 2;
+-- Disallow pushing down sort when pathkey is an SRF.
+explain (costs off) select unique1 from tenk1 order by unnest('{1,2}'::int[]);
-- 
2.17.1

From 57880d51d7af98a68fbec34723fca3bb6ce91e6a Mon Sep 17 00:00:00 2001
From: James Coleman <jtc331@gmail.com>
Date: Fri, 20 Nov 2020 20:29:51 -0500
Subject: [PATCH v3 2/5] Enforce parallel safety of pathkeys in
 generate_useful_gather_paths

If, for example, a pathkey expression (e.g., a correlated subquery which
is currently always treated this way) is unsafe for parallel query then
we must not generate a gather merge path with either incremental or full
sort including that pathkey.
---
 src/backend/optimizer/path/allpaths.c         | 13 ++++--
 src/backend/optimizer/path/equivclass.c       |  4 +-
 src/include/optimizer/paths.h                 |  2 +-
 .../regress/expected/incremental_sort.out     | 40 +++++++++++++++++++
 src/test/regress/sql/incremental_sort.sql     | 11 +++++
 5 files changed, 65 insertions(+), 5 deletions(-)

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 672a20760c..9381ba9af1 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2802,6 +2802,9 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
  * This allows us to do incremental sort on top of an index scan under a gather
  * merge node, i.e. parallelized.
  *
+ * If the parallel argument is true then we'll require that pathkey expressions
+ * be parallel safe.
+ *
  * XXX At the moment this can only ever return a list with a single element,
  * because it looks at query_pathkeys only. So we might return the pathkeys
  * directly, but it seems plausible we'll want to consider other orderings
@@ -2809,7 +2812,7 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
  * merge joins.
  */
 static List *
-get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
+get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel, bool require_parallel_safe)
 {
 	List	   *useful_pathkeys_list = NIL;
 
@@ -2839,8 +2842,12 @@ get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
 			 * meet criteria of EC membership in the current relation, we
 			 * enable not just an incremental sort on the entirety of
 			 * query_pathkeys but also incremental sort below a JOIN.
+			 *
+			 * By passing true for the final argument
+			 * find_em_expr_usable_for_sorting_rel will ensure the chosen
+			 * expression is parallel safe.
 			 */
-			if (!find_em_expr_usable_for_sorting_rel(pathkey_ec, rel))
+			if (!find_em_expr_usable_for_sorting_rel(root, pathkey_ec, rel, require_parallel_safe))
 				break;
 
 			npathkeys++;
@@ -2894,7 +2901,7 @@ generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_r
 	generate_gather_paths(root, rel, override_rows);
 
 	/* consider incremental sort for interesting orderings */
-	useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel);
+	useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true);
 
 	/* used for explicit (full) sort paths */
 	cheapest_partial_path = linitial(rel->partial_pathlist);
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index f98fd7b3eb..75cb1750a8 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -803,7 +803,7 @@ find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel)
  * applied in prepare_sort_from_pathkeys.
  */
 Expr *
-find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel)
+find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel, bool require_parallel_safe)
 {
 	ListCell   *lc_em;
 
@@ -833,6 +833,8 @@ find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel)
 		if (!bms_is_subset(em->em_relids, rel->relids))
 			continue;
 
+		if (require_parallel_safe && !is_parallel_safe(root, (Node *) em_expr))
+			continue;
 		/*
 		 * As long as the expression isn't volatile then
 		 * prepare_sort_from_pathkeys is able to generate a new target entry,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 8a4c6f8b59..fae6bddead 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -135,7 +135,7 @@ extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
 												  Relids rel,
 												  bool create_it);
 extern Expr *find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel);
-extern Expr *find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel);
+extern Expr *find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec, RelOptInfo *rel, bool require_parallel_safe);
 extern void generate_base_implied_equalities(PlannerInfo *root);
 extern List *generate_join_implied_equalities(PlannerInfo *root,
 											  Relids join_relids,
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 51471ae92d..d316a7c4b9 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1551,6 +1551,46 @@ order by 1, 2;
    ->  Function Scan on generate_series
 (7 rows)
 
+-- Parallel sort but with expression (correlated subquery) that
+-- is prohibited in parallel plans.
+explain (costs off) select distinct
+  unique1,
+  (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000);
+                                   QUERY PLAN                                    
+---------------------------------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: t.unique1, ((SubPlan 1))
+         ->  Gather
+               Workers Planned: 2
+               ->  Nested Loop
+                     ->  Parallel Index Only Scan using tenk1_unique1 on tenk1 t
+                     ->  Function Scan on generate_series
+               SubPlan 1
+                 ->  Index Only Scan using tenk1_unique1 on tenk1
+                       Index Cond: (unique1 = t.unique1)
+(11 rows)
+
+explain (costs off) select
+  unique1,
+  (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000)
+order by 1, 2;
+                                QUERY PLAN                                 
+---------------------------------------------------------------------------
+ Sort
+   Sort Key: t.unique1, ((SubPlan 1))
+   ->  Gather
+         Workers Planned: 2
+         ->  Nested Loop
+               ->  Parallel Index Only Scan using tenk1_unique1 on tenk1 t
+               ->  Function Scan on generate_series
+         SubPlan 1
+           ->  Index Only Scan using tenk1_unique1 on tenk1
+                 Index Cond: (unique1 = t.unique1)
+(10 rows)
+
 -- Parallel sort but with expression not available until the upper rel.
 explain (costs off) select distinct sub.unique1, stringu1 || random()::text
 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index cb48f200ce..ff3af0fd16 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -250,6 +250,17 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
 explain (costs off) select sub.unique1, md5(stringu1)
 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
 order by 1, 2;
+-- Parallel sort but with expression (correlated subquery) that
+-- is prohibited in parallel plans.
+explain (costs off) select distinct
+  unique1,
+  (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000);
+explain (costs off) select
+  unique1,
+  (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000)
+order by 1, 2;
 -- Parallel sort but with expression not available until the upper rel.
 explain (costs off) select distinct sub.unique1, stringu1 || random()::text
 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
-- 
2.17.1

From b378e8c2bb76d61da11ce834d55939987ffa1289 Mon Sep 17 00:00:00 2001
From: jcoleman <jtc331@gmail.com>
Date: Fri, 20 Nov 2020 16:19:00 +0000
Subject: [PATCH v3 1/5] generate_useful_gather_paths shouldn't skip unsorted
 subpaths

This appears to be a copy/paste thinko from when we added this function.
Here's the issue: the comment claims that we should skip subpaths that
aren't sorted at all since we can't possibly use a gather merge directly
or with an incremental sort applied first. It's true that we can't do
either of those things unless the subpath is already at least partially
sorted. But subsequently we attempt to construct a gather merge path on
top of a full sort (for the cheapest path), and there's no reason to
limit that to partially sorted paths (indeed in the presence of
incremental sort it seems unlikely that that would be the cheapest path).

We still don't want to build incremental sort paths if the subpath has
no pathkeys, but that will imply presorted_keys = 0, which we already
check.
---
 src/backend/optimizer/path/allpaths.c          |  8 --------
 src/test/regress/expected/incremental_sort.out | 13 +++++++++++++
 src/test/regress/sql/incremental_sort.sql      |  4 ++++
 3 files changed, 17 insertions(+), 8 deletions(-)

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 84a69b064a..672a20760c 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2914,14 +2914,6 @@ generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_r
 			Path	   *subpath = (Path *) lfirst(lc2);
 			GatherMergePath *path;
 
-			/*
-			 * If the path has no ordering at all, then we can't use either
-			 * incremental sort or rely on implicit sorting with a gather
-			 * merge.
-			 */
-			if (subpath->pathkeys == NIL)
-				continue;
-
 			is_sorted = pathkeys_count_contained_in(useful_pathkeys,
 													subpath->pathkeys,
 													&presorted_keys);
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 7cf2eee7c1..51471ae92d 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1468,6 +1468,19 @@ explain (costs off) select * from t union select * from t order by 1,3;
                            ->  Parallel Seq Scan on t t_1
 (13 rows)
 
+-- Full sort, not just incremental sort can be pushed below a gather merge path
+-- by generate_useful_gather_paths.
+explain (costs off) select distinct a,b from t;
+                QUERY PLAN                
+------------------------------------------
+ Unique
+   ->  Gather Merge
+         Workers Planned: 2
+         ->  Sort
+               Sort Key: a, b
+               ->  Parallel Seq Scan on t
+(6 rows)
+
 drop table t;
 -- Sort pushdown can't go below where expressions are part of the rel target.
 -- In particular this is interesting for volatile expressions which have to
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 3ee11c394b..cb48f200ce 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -220,6 +220,10 @@ explain (costs off) select a,b,sum(c) from t group by 1,2 order by 1,2,3 limit 1
 set enable_hashagg to off;
 explain (costs off) select * from t union select * from t order by 1,3;
 
+-- Full sort, not just incremental sort can be pushed below a gather merge path
+-- by generate_useful_gather_paths.
+explain (costs off) select distinct a,b from t;
+
 drop table t;
 
 -- Sort pushdown can't go below where expressions are part of the rel target.
-- 
2.17.1

From 857e653607656d10586e2a0f1b936576513d4277 Mon Sep 17 00:00:00 2001
From: jcoleman <jtc331@gmail.com>
Date: Fri, 20 Nov 2020 16:19:00 +0000
Subject: [PATCH 1/5] Consider unsorted paths in generate_useful_gather_paths

generate_useful_gather_paths used to skip unsorted paths (without any
pathkeys), but that is unnecessary - the later code actually can handle
such paths just fine by adding a Sort node. This is clearly a thinko,
preventing construction of useful plans.

Backpatch to 13, where this code was introduced (for Incremental Sort).

Author: James Coleman
Reviewed-by: Tomas Vondra
Backpatch-through: 13
Discussion: https://postgr.es/m/CAAaqYe8cK3g5CfLC4w7bs=hC0mSksZC=H5M8LSchj5e5OxpTAg@mail.gmail.com
---
 src/backend/optimizer/path/allpaths.c          |  8 --------
 src/test/regress/expected/incremental_sort.out | 13 +++++++++++++
 src/test/regress/sql/incremental_sort.sql      |  4 ++++
 3 files changed, 17 insertions(+), 8 deletions(-)

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 84a69b064a..672a20760c 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2914,14 +2914,6 @@ generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_r
 			Path	   *subpath = (Path *) lfirst(lc2);
 			GatherMergePath *path;
 
-			/*
-			 * If the path has no ordering at all, then we can't use either
-			 * incremental sort or rely on implicit sorting with a gather
-			 * merge.
-			 */
-			if (subpath->pathkeys == NIL)
-				continue;
-
 			is_sorted = pathkeys_count_contained_in(useful_pathkeys,
 													subpath->pathkeys,
 													&presorted_keys);
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 7cf2eee7c1..51471ae92d 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1468,6 +1468,19 @@ explain (costs off) select * from t union select * from t order by 1,3;
                            ->  Parallel Seq Scan on t t_1
 (13 rows)
 
+-- Full sort, not just incremental sort can be pushed below a gather merge path
+-- by generate_useful_gather_paths.
+explain (costs off) select distinct a,b from t;
+                QUERY PLAN                
+------------------------------------------
+ Unique
+   ->  Gather Merge
+         Workers Planned: 2
+         ->  Sort
+               Sort Key: a, b
+               ->  Parallel Seq Scan on t
+(6 rows)
+
 drop table t;
 -- Sort pushdown can't go below where expressions are part of the rel target.
 -- In particular this is interesting for volatile expressions which have to
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 3ee11c394b..cb48f200ce 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -220,6 +220,10 @@ explain (costs off) select a,b,sum(c) from t group by 1,2 order by 1,2,3 limit 1
 set enable_hashagg to off;
 explain (costs off) select * from t union select * from t order by 1,3;
 
+-- Full sort, not just incremental sort can be pushed below a gather merge path
+-- by generate_useful_gather_paths.
+explain (costs off) select distinct a,b from t;
+
 drop table t;
 
 -- Sort pushdown can't go below where expressions are part of the rel target.
-- 
2.26.2

From 8ed86b447c07bdce8fafe95cdfb1e68286443274 Mon Sep 17 00:00:00 2001
From: James Coleman <jtc331@gmail.com>
Date: Fri, 20 Nov 2020 20:29:51 -0500
Subject: [PATCH 2/5] Check parallel safety in generate_useful_gather_paths

Commit ebb7ae839d ensured we ignore pathkeys with volatile expressions
when considering adding a sort below a Gather Merge. Turns out we need
to care about parallel safety of the pathkeys too, otherwise we might
try sorting e.g. on results of a correlated subquery (as demonstrated
by a report from Luis Roberto).

Initial investigation by Tom Lane, patch by James Coleman. Backpatch
to 13, where the code was instroduced (as part of Incremental Sort).

Reported-by: Luis Roberto
Author: James Coleman
Reviewed-by: Tomas Vondra
Backpatch-through: 13
Discussion: https://postgr.es/m/622580997.37108180.1604080457319.JavaMail.zimbra%40siscobra.com.br
Discussion: https://postgr.es/m/CAAaqYe8cK3g5CfLC4w7bs=hC0mSksZC=H5M8LSchj5e5OxpTAg@mail.gmail.com
---
 src/backend/optimizer/path/allpaths.c         | 13 ++++--
 src/backend/optimizer/path/equivclass.c       |  9 ++++-
 src/include/optimizer/paths.h                 |  5 ++-
 .../regress/expected/incremental_sort.out     | 40 +++++++++++++++++++
 src/test/regress/sql/incremental_sort.sql     | 11 +++++
 5 files changed, 73 insertions(+), 5 deletions(-)

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 672a20760c..df8d9309f9 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2802,6 +2802,9 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
  * This allows us to do incremental sort on top of an index scan under a gather
  * merge node, i.e. parallelized.
  *
+ * If the require_parallel_safe is true, we also require the expressions to
+ * be parallel safe (which allows pushing the sort below Gather Merge).
+ *
  * XXX At the moment this can only ever return a list with a single element,
  * because it looks at query_pathkeys only. So we might return the pathkeys
  * directly, but it seems plausible we'll want to consider other orderings
@@ -2809,7 +2812,8 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
  * merge joins.
  */
 static List *
-get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
+get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel,
+								 bool require_parallel_safe)
 {
 	List	   *useful_pathkeys_list = NIL;
 
@@ -2839,8 +2843,11 @@ get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
 			 * meet criteria of EC membership in the current relation, we
 			 * enable not just an incremental sort on the entirety of
 			 * query_pathkeys but also incremental sort below a JOIN.
+			 *
+			 * If requested, ensure the expression is parallel safe too.
 			 */
-			if (!find_em_expr_usable_for_sorting_rel(pathkey_ec, rel))
+			if (!find_em_expr_usable_for_sorting_rel(root, pathkey_ec, rel,
+													 require_parallel_safe))
 				break;
 
 			npathkeys++;
@@ -2894,7 +2901,7 @@ generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_r
 	generate_gather_paths(root, rel, override_rows);
 
 	/* consider incremental sort for interesting orderings */
-	useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel);
+	useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true);
 
 	/* used for explicit (full) sort paths */
 	cheapest_partial_path = linitial(rel->partial_pathlist);
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index f98fd7b3eb..b49ee52cba 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -803,7 +803,8 @@ find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel)
  * applied in prepare_sort_from_pathkeys.
  */
 Expr *
-find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel)
+find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec,
+									RelOptInfo *rel, bool require_parallel_safe)
 {
 	ListCell   *lc_em;
 
@@ -833,6 +834,12 @@ find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel)
 		if (!bms_is_subset(em->em_relids, rel->relids))
 			continue;
 
+		/*
+		 * If requested, reject expressions that are not parallel-safe.
+		 */
+		if (require_parallel_safe && !is_parallel_safe(root, (Node *) em_expr))
+			continue;
+
 		/*
 		 * As long as the expression isn't volatile then
 		 * prepare_sort_from_pathkeys is able to generate a new target entry,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 8a4c6f8b59..bf6c16b804 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -135,7 +135,10 @@ extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
 												  Relids rel,
 												  bool create_it);
 extern Expr *find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel);
-extern Expr *find_em_expr_usable_for_sorting_rel(EquivalenceClass *ec, RelOptInfo *rel);
+extern Expr *find_em_expr_usable_for_sorting_rel(PlannerInfo *root,
+												 EquivalenceClass *ec,
+												 RelOptInfo *rel,
+												 bool require_parallel_safe);
 extern void generate_base_implied_equalities(PlannerInfo *root);
 extern List *generate_join_implied_equalities(PlannerInfo *root,
 											  Relids join_relids,
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 51471ae92d..d316a7c4b9 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1551,6 +1551,46 @@ order by 1, 2;
    ->  Function Scan on generate_series
 (7 rows)
 
+-- Parallel sort but with expression (correlated subquery) that
+-- is prohibited in parallel plans.
+explain (costs off) select distinct
+  unique1,
+  (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000);
+                                   QUERY PLAN                                    
+---------------------------------------------------------------------------------
+ Unique
+   ->  Sort
+         Sort Key: t.unique1, ((SubPlan 1))
+         ->  Gather
+               Workers Planned: 2
+               ->  Nested Loop
+                     ->  Parallel Index Only Scan using tenk1_unique1 on tenk1 t
+                     ->  Function Scan on generate_series
+               SubPlan 1
+                 ->  Index Only Scan using tenk1_unique1 on tenk1
+                       Index Cond: (unique1 = t.unique1)
+(11 rows)
+
+explain (costs off) select
+  unique1,
+  (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000)
+order by 1, 2;
+                                QUERY PLAN                                 
+---------------------------------------------------------------------------
+ Sort
+   Sort Key: t.unique1, ((SubPlan 1))
+   ->  Gather
+         Workers Planned: 2
+         ->  Nested Loop
+               ->  Parallel Index Only Scan using tenk1_unique1 on tenk1 t
+               ->  Function Scan on generate_series
+         SubPlan 1
+           ->  Index Only Scan using tenk1_unique1 on tenk1
+                 Index Cond: (unique1 = t.unique1)
+(10 rows)
+
 -- Parallel sort but with expression not available until the upper rel.
 explain (costs off) select distinct sub.unique1, stringu1 || random()::text
 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index cb48f200ce..ff3af0fd16 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -250,6 +250,17 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
 explain (costs off) select sub.unique1, md5(stringu1)
 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
 order by 1, 2;
+-- Parallel sort but with expression (correlated subquery) that
+-- is prohibited in parallel plans.
+explain (costs off) select distinct
+  unique1,
+  (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000);
+explain (costs off) select
+  unique1,
+  (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
+from tenk1 t, generate_series(1, 1000)
+order by 1, 2;
 -- Parallel sort but with expression not available until the upper rel.
 explain (costs off) select distinct sub.unique1, stringu1 || random()::text
 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
-- 
2.26.2

From 7e9502f88cf177fd4bd12b121b439dcb9cc39cf0 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Wed, 16 Dec 2020 00:18:40 +0100
Subject: [PATCH 3/5] Disallow SRFs when considering sorts below Gather Merge

While we do allow SRFs in ORDER BY, but scan/join processing should not
consider such cases - such sorts should only happen via final Sort atop
a ProjectSet. So make sure we don't try adding such sorts below Gather
Merge, just like we do for expressions that are volatile and/or not
parallel safe.

Backpatch to PostgreSQL 13, where this code was introduced as part of
the Incremental Sort patch.

Author: James Coleman
Reviewed-by: Tomas Vondra
Backpatch-through: 13
Discussion: https://postgr.es/m/CAAaqYe8cK3g5CfLC4w7bs=hC0mSksZC=H5M8LSchj5e5OxpTAg@mail.gmail.com
---
 src/backend/optimizer/path/equivclass.c        |  7 +++++++
 src/backend/optimizer/util/tlist.c             |  5 -----
 src/include/optimizer/optimizer.h              |  5 +++++
 src/test/regress/expected/incremental_sort.out | 12 ++++++++++++
 src/test/regress/sql/incremental_sort.sql      |  2 ++
 5 files changed, 26 insertions(+), 5 deletions(-)

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index b49ee52cba..0b2e212b2b 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -840,6 +840,13 @@ find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec,
 		if (require_parallel_safe && !is_parallel_safe(root, (Node *) em_expr))
 			continue;
 
+		/*
+		 * Disallow SRFs so that all of them can be evaluated at the correct
+		 * time as determined by make_sort_input_target.
+		 */
+		if (IS_SRF_CALL((Node *) em_expr))
+			continue;
+
 		/*
 		 * As long as the expression isn't volatile then
 		 * prepare_sort_from_pathkeys is able to generate a new target entry,
diff --git a/src/backend/optimizer/util/tlist.c b/src/backend/optimizer/util/tlist.c
index 02a3c6b165..01cea102ea 100644
--- a/src/backend/optimizer/util/tlist.c
+++ b/src/backend/optimizer/util/tlist.c
@@ -21,11 +21,6 @@
 #include "optimizer/tlist.h"
 
 
-/* Test if an expression node represents a SRF call.  Beware multiple eval! */
-#define IS_SRF_CALL(node) \
-	((IsA(node, FuncExpr) && ((FuncExpr *) (node))->funcretset) || \
-	 (IsA(node, OpExpr) && ((OpExpr *) (node))->opretset))
-
 /*
  * Data structures for split_pathtarget_at_srfs().  To preserve the identity
  * of sortgroupref items even if they are textually equal(), what we track is
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h
index dea0e7338d..446071c554 100644
--- a/src/include/optimizer/optimizer.h
+++ b/src/include/optimizer/optimizer.h
@@ -24,6 +24,11 @@
 
 #include "nodes/parsenodes.h"
 
+/* Test if an expression node represents a SRF call.  Beware multiple eval! */
+#define IS_SRF_CALL(node) \
+	((IsA(node, FuncExpr) && ((FuncExpr *) (node))->funcretset) || \
+	 (IsA(node, OpExpr) && ((OpExpr *) (node))->opretset))
+
 /*
  * We don't want to include nodes/pathnodes.h here, because non-planner
  * code should generally treat PlannerInfo as an opaque typedef.
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index d316a7c4b9..a8cbfd9f5f 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1620,3 +1620,15 @@ order by 1, 2;
                ->  Function Scan on generate_series
 (7 rows)
 
+-- Disallow pushing down sort when pathkey is an SRF.
+explain (costs off) select unique1 from tenk1 order by unnest('{1,2}'::int[]);
+                               QUERY PLAN                                
+-------------------------------------------------------------------------
+ Sort
+   Sort Key: (unnest('{1,2}'::integer[]))
+   ->  Gather
+         Workers Planned: 2
+         ->  ProjectSet
+               ->  Parallel Index Only Scan using tenk1_unique1 on tenk1
+(6 rows)
+
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index ff3af0fd16..62a037b0cf 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -267,3 +267,5 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
 explain (costs off) select sub.unique1, stringu1 || random()::text
 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
 order by 1, 2;
+-- Disallow pushing down sort when pathkey is an SRF.
+explain (costs off) select unique1 from tenk1 order by unnest('{1,2}'::int[]);
-- 
2.26.2

From 6c468c961a2a6b07833f1ce1dd22cddef32cc3e3 Mon Sep 17 00:00:00 2001
From: jcoleman <jtc331@gmail.com>
Date: Wed, 25 Nov 2020 15:53:49 -0500
Subject: [PATCH 4/5] Don't search for volatile expr in
 find_em_expr_usable_for_sorting_rel

While prepare_sort_from_pathkeys has to be concerned about matching up
a volatile expression to the proper tlist entry, we don't need to do
that in find_em_expr_usable_for_sorting_rel becausee such a sort will
have to be postponed anyway.

Author: James Coleman
Reviewed-by: Tomas Vondra
Backpatch-through: 13
Discussion: https://postgr.es/m/CAAaqYe8cK3g5CfLC4w7bs%3DhC0mSksZC%3DH5M8LSchj5e5OxpTAg%40mail.gmail.com
---
 src/backend/optimizer/path/equivclass.c | 27 +++++--------------------
 1 file changed, 5 insertions(+), 22 deletions(-)

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 0b2e212b2b..70499af2cf 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -817,7 +817,6 @@ find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec,
 		EquivalenceMember *em = lfirst(lc_em);
 		Expr	   *em_expr = em->em_expr;
 		PathTarget *target = rel->reltarget;
-		ListCell   *lc_target_expr;
 
 		/*
 		 * We shouldn't be trying to sort by an equivalence class that
@@ -851,30 +850,14 @@ find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec,
 		 * As long as the expression isn't volatile then
 		 * prepare_sort_from_pathkeys is able to generate a new target entry,
 		 * so there's no need to verify that one already exists.
+		 *
+		 * While prepare_sort_from_pathkeys has to be concerned about matching
+		 * up a volatile expression to the proper tlist entry, it doesn't seem
+		 * valuable here to expend the work trying to find a match in the
+		 * target's exprs since such a sort will have to be postponed anyway.
 		 */
 		if (!ec->ec_has_volatile)
 			return em->em_expr;
-
-		/*
-		 * If, however, it's volatile, we have to verify that the
-		 * equivalence member's expr is already generated in the
-		 * relation's target (we do strip relabels first from both
-		 * expressions, which is cheap and might allow us to match
-		 * more expressions).
-		 */
-		while (em_expr && IsA(em_expr, RelabelType))
-			em_expr = ((RelabelType *) em_expr)->arg;
-
-		foreach(lc_target_expr, target->exprs)
-		{
-			Expr	   *target_expr = lfirst(lc_target_expr);
-
-			while (target_expr && IsA(target_expr, RelabelType))
-				target_expr = ((RelabelType *) target_expr)->arg;
-
-			if (equal(target_expr, em_expr))
-				return em->em_expr;
-		}
 	}
 
 	/* We didn't find any suitable equivalence class expression */
-- 
2.26.2

From 1694a9dfb0f2c61aeb3b63e931edb7a16fb8acac Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Wed, 16 Dec 2020 00:20:53 +0100
Subject: [PATCH 5/5] Improve find_em_expr_usable_for_sorting_rel comment

Clarify the relationship between find_em_expr_usable_for_sorting_rel and
prepare_sort_from_pathkeys, i.e. what restrictions need to be shared
between those two places.

Author: James Coleman
Reviewed-by: Tomas Vondra
Backpatch-through: 13
Discussion: https://postgr.es/m/CAAaqYe8cK3g5CfLC4w7bs%3DhC0mSksZC%3DH5M8LSchj5e5OxpTAg%40mail.gmail.com
---
 src/backend/optimizer/path/equivclass.c | 9 ++++++---
 src/backend/optimizer/plan/createplan.c | 3 +++
 2 files changed, 9 insertions(+), 3 deletions(-)

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 70499af2cf..4466f880ee 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -798,9 +798,12 @@ find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel)
 }
 
 /*
- * Find an equivalence class member expression that can be safely used by a
- * sort node on top of the provided relation. The rules here must match those
- * applied in prepare_sort_from_pathkeys.
+ * Find an equivalence class member expression that can be safely used to build
+ * a sort node using the provided relation. The applied rules parallel those
+ * applied in prepare_sort_from_pathkeys but are a subset of that function since
+ * here we are concerned with proactive sorts while prepare_sort_from_pathkeys
+ * must deal with sorts that must be delayed until the last stages of query
+ * execution.
  */
 Expr *
 find_em_expr_usable_for_sorting_rel(PlannerInfo *root, EquivalenceClass *ec,
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 5ecf9f4065..f7a8dae3c6 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -5850,6 +5850,9 @@ make_incrementalsort(Plan *lefttree, int numCols, int nPresortedCols,
  *
  * Returns the node which is to be the input to the Sort (either lefttree,
  * or a Result stacked atop lefttree).
+ *
+ * Note: Restrictions on what expressions are safely sortable may also need to
+ * be added to find_em_expr_usable_for_sorting_rel.
  */
 static Plan *
 prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
-- 
2.26.2