v0-0001-Consider-explicit-sort-of-the-MergeAppend-subpath.patch

From 98306f0e14c12b6dee92ef5977d85fc1dd324898 Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <lepihov@gmail.com>
Date: Thu, 24 Apr 2025 14:03:02 +0200
Subject: [PATCH v0] Consider explicit sort of the MergeAppend subpaths.

Expand the optimiser search scope a little: fetching optimal subpath matching
pathkeys of the planning MergeAppend, consider the extra case of
overall-optimal path plus explicit Sort node at the top.

It may provide a more effective plan in both full and fractional scan cases:
1. The Sort node may be pushed down to subpaths under a parallel or
async Append.
2. The case is when a minor set of subpaths doesn't have a proper index, and it
is profitable to sort them instead of switching to plain Append.

In general, analysing the regression tests changed by this code, I see that
the cost model prefers a series of small sortings instead of a single massive
one.

Overhead:
It seems multiple subpaths may be encountered, as well as many pathkeys.
So, to be as careful as possible here, only cost estimation is performed.
---
 .../postgres_fdw/expected/postgres_fdw.out    |   6 +-
 src/backend/optimizer/path/allpaths.c         |  35 ++---
 src/backend/optimizer/path/pathkeys.c         | 112 ++++++++++++++
 src/include/optimizer/paths.h                 |  10 ++
 .../regress/expected/collate.icu.utf8.out     |   9 +-
 src/test/regress/expected/inherit.out         |  19 ++-
 src/test/regress/expected/partition_join.out  | 139 +++++++++++-------
 src/test/regress/expected/partition_prune.out |  16 +-
 src/test/regress/expected/union.out           |   6 +-
 src/test/regress/sql/inherit.sql              |   4 +-
 10 files changed, 255 insertions(+), 101 deletions(-)

diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index d1acee5a5fa..11b42f18cb6 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -10277,13 +10277,15 @@ SELECT t1.a, t2.b FROM fprt1 t1 INNER JOIN fprt2 t2 ON (t1.a = t2.b) WHERE t1.a
    ->  Nested Loop
          Join Filter: (t1.a = t2.b)
          ->  Append
-               ->  Foreign Scan on ftprt1_p1 t1_1
+               ->  Sort
+                     Sort Key: t1_1.a
+                     ->  Foreign Scan on ftprt1_p1 t1_1
                ->  Foreign Scan on ftprt1_p2 t1_2
          ->  Materialize
                ->  Append
                      ->  Foreign Scan on ftprt2_p1 t2_1
                      ->  Foreign Scan on ftprt2_p2 t2_2
-(10 rows)
+(12 rows)
 
 SELECT t1.a, t2.b FROM fprt1 t1 INNER JOIN fprt2 t2 ON (t1.a = t2.b) WHERE t1.a % 25 = 0 ORDER BY 1,2 FOR UPDATE OF t1;
   a  |  b  
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 905250b3325..f48f5b94c0a 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -1855,29 +1855,13 @@ generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel,
 
 			/* Locate the right paths, if they are available. */
 			cheapest_startup =
-				get_cheapest_path_for_pathkeys(childrel->pathlist,
-											   pathkeys,
-											   NULL,
-											   STARTUP_COST,
-											   false);
+				get_cheapest_path_for_pathkeys_ext(root, childrel, pathkeys,
+												   NULL, STARTUP_COST, false);
 			cheapest_total =
-				get_cheapest_path_for_pathkeys(childrel->pathlist,
-											   pathkeys,
-											   NULL,
-											   TOTAL_COST,
-											   false);
+				get_cheapest_path_for_pathkeys_ext(root, childrel, pathkeys,
+												   NULL, TOTAL_COST, false);
 
-			/*
-			 * If we can't find any paths with the right order just use the
-			 * cheapest-total path; we'll have to sort it later.
-			 */
-			if (cheapest_startup == NULL || cheapest_total == NULL)
-			{
-				cheapest_startup = cheapest_total =
-					childrel->cheapest_total_path;
-				/* Assert we do have an unparameterized path for this child */
-				Assert(cheapest_total->param_info == NULL);
-			}
+			Assert(cheapest_total->param_info == NULL);
 
 			/*
 			 * When building a fractional path, determine a cheapest
@@ -1894,10 +1878,11 @@ generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel,
 				double		path_fraction = (1.0 / root->tuple_fraction);
 
 				cheapest_fractional =
-					get_cheapest_fractional_path_for_pathkeys(childrel->pathlist,
-															  pathkeys,
-															  NULL,
-															  path_fraction);
+					get_cheapest_fractional_path_for_pathkeys_ext(root,
+																  childrel,
+																  pathkeys,
+																  NULL,
+																  path_fraction);
 
 				/*
 				 * If we found no path with matching pathkeys, use the
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 8b04d40d36d..4a5e37b493c 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -19,11 +19,13 @@
 
 #include "access/stratnum.h"
 #include "catalog/pg_opfamily.h"
+#include "miscadmin.h"
 #include "nodes/nodeFuncs.h"
 #include "optimizer/cost.h"
 #include "optimizer/optimizer.h"
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
+#include "optimizer/planner.h"
 #include "partitioning/partbounds.h"
 #include "rewrite/rewriteManip.h"
 #include "utils/lsyscache.h"
@@ -648,6 +650,72 @@ get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
 	return matched_path;
 }
 
+/*
+ * get_cheapest_path_for_pathkeys_ext
+ *	  Calls get_cheapest_path_for_pathkeys to obtain cheapest path that
+ *	  satisfies defined criterias and сonsiders one more option: choose
+ *	  overall-optimal path (according the criterion) and explicitly sort its
+ *	  output to satisfy the pathkeys.
+ *
+ *	  Caller is responsible to insert corresponding sort path at the top of
+ *	  returned path if it will be chosen to be used.
+ *
+ *	  Return NULL if no such path.
+ */
+Path *
+get_cheapest_path_for_pathkeys_ext(PlannerInfo *root, RelOptInfo *rel,
+								   List *pathkeys, Relids required_outer,
+								   CostSelector cost_criterion,
+								   bool require_parallel_safe)
+{
+	Path	sort_path;
+	Path   *base_path;
+	Path   *path;
+
+	path = get_cheapest_path_for_pathkeys(rel->pathlist, pathkeys,
+										  required_outer, cost_criterion,
+										  require_parallel_safe);
+
+
+	if (path == NULL)
+		/*
+		 * Current pathlist doesn't fit the pathkeys. No need to check extra
+		 * sort path ways.
+		 */
+		return rel->cheapest_total_path;
+
+	switch (cost_criterion)
+	{
+		case STARTUP_COST:
+			base_path = rel->cheapest_startup_path;
+			break;
+		case TOTAL_COST:
+			base_path = rel->cheapest_total_path;
+			break;
+		default:
+			/* In case of new criteries */
+			elog(ERROR, "unrecognized cost criterion: %d", cost_criterion);
+			break;
+	}
+
+	/* Stop here if the path doesn't satisfy necessary conditions */
+	if ((require_parallel_safe && !base_path->parallel_safe) ||
+		!bms_is_subset(PATH_REQ_OUTER(base_path), required_outer))
+		return path;
+
+	/* Consider the most startup-optimal path with extra sort */
+	if (base_path && path != base_path)
+	{
+		cost_sort(&sort_path, root, pathkeys, base_path->disabled_nodes,
+				  base_path->total_cost, base_path->rows,
+				  base_path->pathtarget->width, 0.0, work_mem, -1.0);
+
+		if (compare_path_costs(&sort_path, path, cost_criterion) < 0)
+			return base_path;
+	}
+	return path;
+}
+
 /*
  * get_cheapest_fractional_path_for_pathkeys
  *	  Find the cheapest path (for retrieving a specified fraction of all
@@ -690,6 +758,50 @@ get_cheapest_fractional_path_for_pathkeys(List *paths,
 	return matched_path;
 }
 
+/*
+ * get_cheapest_fractional_path_for_pathkeys_ext
+ *	  obtain cheapest fractional path that satisfies defined criterias excluding
+ *	  pathkeys and explicitly sort its output to satisfy the pathkeys.
+ *
+ *	  Caller is responsible to insert corresponding sort path at the top of
+ *	  returned path if it will be chosen to be used.
+ *
+ *	  Return NULL if no such path.
+ */
+Path *
+get_cheapest_fractional_path_for_pathkeys_ext(PlannerInfo *root,
+											  RelOptInfo *rel,
+											  List *pathkeys,
+											  Relids required_outer,
+											  double fraction)
+{
+	Path	sort_path;
+	Path   *base_path;
+	Path   *path;
+
+	path = get_cheapest_fractional_path_for_pathkeys(rel->pathlist, pathkeys,
+													 required_outer, fraction);
+
+
+	base_path = get_cheapest_fractional_path(rel, root->tuple_fraction);
+
+	/* Stop here if the path doesn't satisfy necessary conditions */
+	if (!base_path || !bms_is_subset(PATH_REQ_OUTER(base_path), required_outer))
+		return path;
+
+	if (path != base_path)
+	{
+		cost_sort(&sort_path, root, pathkeys, base_path->disabled_nodes,
+				  base_path->total_cost, base_path->rows,
+				  base_path->pathtarget->width, 0.0, work_mem, -1.0);
+
+		if (!path ||
+			compare_fractional_path_costs(&sort_path, path, fraction) <= 0)
+			return base_path;
+	}
+
+	return path;
+}
 
 /*
  * get_cheapest_parallel_safe_total_inner
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index a48c9721797..4bdc85afca9 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -224,10 +224,20 @@ extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
 											Relids required_outer,
 											CostSelector cost_criterion,
 											bool require_parallel_safe);
+extern Path *get_cheapest_path_for_pathkeys_ext(PlannerInfo *root,
+												RelOptInfo *rel, List *pathkeys,
+												Relids required_outer,
+												CostSelector cost_criterion,
+												bool require_parallel_safe);
 extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
 													   List *pathkeys,
 													   Relids required_outer,
 													   double fraction);
+extern Path *get_cheapest_fractional_path_for_pathkeys_ext(PlannerInfo *root,
+														   RelOptInfo *rel,
+														   List *pathkeys,
+														   Relids required_outer,
+														   double fraction);
 extern Path *get_cheapest_parallel_safe_total_inner(List *paths);
 extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index,
 								  ScanDirection scandir);
diff --git a/src/test/regress/expected/collate.icu.utf8.out b/src/test/regress/expected/collate.icu.utf8.out
index 69805d4b9ec..48d47bb7455 100644
--- a/src/test/regress/expected/collate.icu.utf8.out
+++ b/src/test/regress/expected/collate.icu.utf8.out
@@ -2412,16 +2412,19 @@ EXPLAIN (COSTS OFF)
 SELECT c collate "C", count(c) FROM pagg_tab3 GROUP BY c collate "C" ORDER BY 1;
                        QUERY PLAN                       
 --------------------------------------------------------
- Sort
+ Merge Append
    Sort Key: ((pagg_tab3.c)::text) COLLATE "C"
-   ->  Append
+   ->  Sort
+         Sort Key: ((pagg_tab3.c)::text) COLLATE "C"
          ->  HashAggregate
                Group Key: (pagg_tab3.c)::text
                ->  Seq Scan on pagg_tab3_p2 pagg_tab3
+   ->  Sort
+         Sort Key: ((pagg_tab3_1.c)::text) COLLATE "C"
          ->  HashAggregate
                Group Key: (pagg_tab3_1.c)::text
                ->  Seq Scan on pagg_tab3_p1 pagg_tab3_1
-(9 rows)
+(12 rows)
 
 SELECT c collate "C", count(c) FROM pagg_tab3 GROUP BY c collate "C" ORDER BY 1;
  c | count 
diff --git a/src/test/regress/expected/inherit.out b/src/test/regress/expected/inherit.out
index f9b0c415cfd..71036dc938f 100644
--- a/src/test/regress/expected/inherit.out
+++ b/src/test/regress/expected/inherit.out
@@ -1665,11 +1665,13 @@ insert into matest2 (name) values ('Test 3');
 insert into matest2 (name) values ('Test 4');
 insert into matest3 (name) values ('Test 5');
 insert into matest3 (name) values ('Test 6');
-set enable_indexscan = off;  -- force use of seqscan/sort, so no merge
+set enable_indexscan = off;  -- force use of seqscan/sort
+set enable_sort = off; -- since merge append may employ sort in children we need to disable sort
 explain (verbose, costs off) select * from matest0 order by 1-id;
                          QUERY PLAN                         
 ------------------------------------------------------------
  Sort
+   Disabled: true
    Output: matest0.id, matest0.name, ((1 - matest0.id))
    Sort Key: ((1 - matest0.id))
    ->  Result
@@ -1683,7 +1685,7 @@ explain (verbose, costs off) select * from matest0 order by 1-id;
                      Output: matest0_3.id, matest0_3.name
                ->  Seq Scan on public.matest3 matest0_4
                      Output: matest0_4.id, matest0_4.name
-(14 rows)
+(15 rows)
 
 select * from matest0 order by 1-id;
  id |  name  
@@ -1719,6 +1721,7 @@ select min(1-id) from matest0;
 (1 row)
 
 reset enable_indexscan;
+reset enable_sort;
 set enable_seqscan = off;  -- plan with fewest seqscans should be merge
 set enable_parallel_append = off; -- Don't let parallel-append interfere
 explain (verbose, costs off) select * from matest0 order by 1-id;
@@ -1844,16 +1847,20 @@ order by t1.b limit 10;
          Merge Cond: (t1.b = t2.b)
          ->  Merge Append
                Sort Key: t1.b
-               ->  Index Scan using matest0i on matest0 t1_1
+               ->  Sort
+                     Sort Key: t1_1.b
+                     ->  Seq Scan on matest0 t1_1
                ->  Index Scan using matest1i on matest1 t1_2
          ->  Materialize
                ->  Merge Append
                      Sort Key: t2.b
-                     ->  Index Scan using matest0i on matest0 t2_1
-                           Filter: (c = d)
+                     ->  Sort
+                           Sort Key: t2_1.b
+                           ->  Seq Scan on matest0 t2_1
+                                 Filter: (c = d)
                      ->  Index Scan using matest1i on matest1 t2_2
                            Filter: (c = d)
-(14 rows)
+(18 rows)
 
 reset enable_nestloop;
 drop table matest0 cascade;
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out
index 6101c8c7cf1..d41979367c9 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -65,31 +65,34 @@ SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1, prt2 t2 WHERE t1.a = t2.b AND t1.b =
 -- inner join with partially-redundant join clauses
 EXPLAIN (COSTS OFF)
 SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1, prt2 t2 WHERE t1.a = t2.a AND t1.a = t2.b ORDER BY t1.a, t2.b;
-                          QUERY PLAN                           
----------------------------------------------------------------
- Sort
+                       QUERY PLAN                        
+---------------------------------------------------------
+ Merge Append
    Sort Key: t1.a
-   ->  Append
-         ->  Merge Join
-               Merge Cond: (t1_1.a = t2_1.a)
-               ->  Index Scan using iprt1_p1_a on prt1_p1 t1_1
-               ->  Sort
-                     Sort Key: t2_1.b
-                     ->  Seq Scan on prt2_p1 t2_1
-                           Filter: (a = b)
+   ->  Merge Join
+         Merge Cond: (t1_1.a = t2_1.a)
+         ->  Index Scan using iprt1_p1_a on prt1_p1 t1_1
+         ->  Sort
+               Sort Key: t2_1.b
+               ->  Seq Scan on prt2_p1 t2_1
+                     Filter: (a = b)
+   ->  Sort
+         Sort Key: t1_2.a
          ->  Hash Join
                Hash Cond: (t1_2.a = t2_2.a)
                ->  Seq Scan on prt1_p2 t1_2
                ->  Hash
                      ->  Seq Scan on prt2_p2 t2_2
                            Filter: (a = b)
+   ->  Sort
+         Sort Key: t1_3.a
          ->  Hash Join
                Hash Cond: (t1_3.a = t2_3.a)
                ->  Seq Scan on prt1_p3 t1_3
                ->  Hash
                      ->  Seq Scan on prt2_p3 t2_3
                            Filter: (a = b)
-(22 rows)
+(25 rows)
 
 SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1, prt2 t2 WHERE t1.a = t2.a AND t1.a = t2.b ORDER BY t1.a, t2.b;
  a  |  c   | b  |  c   
@@ -1383,28 +1386,32 @@ SELECT t1.a, t1.c, t2.b, t2.c, t3.a + t3.b, t3.c FROM (prt1 t1 LEFT JOIN prt2 t2
 -- This should generate a partitionwise join, but currently fails to
 EXPLAIN (COSTS OFF)
 SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT * FROM prt2 WHERE b > 250) t2 ON t1.a = t2.b WHERE t1.b = 0 ORDER BY t1.a, t2.b;
-                        QUERY PLAN                         
------------------------------------------------------------
- Incremental Sort
+                           QUERY PLAN                            
+-----------------------------------------------------------------
+ Sort
    Sort Key: prt1.a, prt2.b
-   Presorted Key: prt1.a
-   ->  Merge Left Join
-         Merge Cond: (prt1.a = prt2.b)
-         ->  Sort
-               Sort Key: prt1.a
-               ->  Append
-                     ->  Seq Scan on prt1_p1 prt1_1
-                           Filter: ((a < 450) AND (b = 0))
-                     ->  Seq Scan on prt1_p2 prt1_2
-                           Filter: ((a < 450) AND (b = 0))
-         ->  Sort
-               Sort Key: prt2.b
-               ->  Append
+   ->  Merge Right Join
+         Merge Cond: (prt2.b = prt1.a)
+         ->  Append
+               ->  Sort
+                     Sort Key: prt2_1.b
                      ->  Seq Scan on prt2_p2 prt2_1
                            Filter: (b > 250)
+               ->  Sort
+                     Sort Key: prt2_2.b
                      ->  Seq Scan on prt2_p3 prt2_2
                            Filter: (b > 250)
-(19 rows)
+         ->  Materialize
+               ->  Append
+                     ->  Sort
+                           Sort Key: prt1_1.a
+                           ->  Seq Scan on prt1_p1 prt1_1
+                                 Filter: ((a < 450) AND (b = 0))
+                     ->  Sort
+                           Sort Key: prt1_2.a
+                           ->  Seq Scan on prt1_p2 prt1_2
+                                 Filter: ((a < 450) AND (b = 0))
+(23 rows)
 
 SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT * FROM prt2 WHERE b > 250) t2 ON t1.a = t2.b WHERE t1.b = 0 ORDER BY t1.a, t2.b;
   a  |  b  
@@ -1424,25 +1431,33 @@ SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT *
 -- partitionwise join does not apply
 EXPLAIN (COSTS OFF)
 SELECT t1.a, t2.b FROM prt1 t1, prt2 t2 WHERE t1::text = t2::text AND t1.a = t2.b ORDER BY t1.a;
-                                       QUERY PLAN                                        
------------------------------------------------------------------------------------------
+                            QUERY PLAN                            
+------------------------------------------------------------------
  Merge Join
-   Merge Cond: ((t1.a = t2.b) AND (((((t1.*)::prt1))::text) = ((((t2.*)::prt2))::text)))
-   ->  Sort
-         Sort Key: t1.a, ((((t1.*)::prt1))::text)
-         ->  Result
-               ->  Append
-                     ->  Seq Scan on prt1_p1 t1_1
-                     ->  Seq Scan on prt1_p2 t1_2
-                     ->  Seq Scan on prt1_p3 t1_3
-   ->  Sort
-         Sort Key: t2.b, ((((t2.*)::prt2))::text)
-         ->  Result
-               ->  Append
+   Merge Cond: (t1.a = t2.b)
+   Join Filter: ((((t2.*)::prt2))::text = (((t1.*)::prt1))::text)
+   ->  Append
+         ->  Sort
+               Sort Key: t1_1.a
+               ->  Seq Scan on prt1_p1 t1_1
+         ->  Sort
+               Sort Key: t1_2.a
+               ->  Seq Scan on prt1_p2 t1_2
+         ->  Sort
+               Sort Key: t1_3.a
+               ->  Seq Scan on prt1_p3 t1_3
+   ->  Materialize
+         ->  Append
+               ->  Sort
+                     Sort Key: t2_1.b
                      ->  Seq Scan on prt2_p1 t2_1
+               ->  Sort
+                     Sort Key: t2_2.b
                      ->  Seq Scan on prt2_p2 t2_2
+               ->  Sort
+                     Sort Key: t2_3.b
                      ->  Seq Scan on prt2_p3 t2_3
-(16 rows)
+(24 rows)
 
 SELECT t1.a, t2.b FROM prt1 t1, prt2 t2 WHERE t1::text = t2::text AND t1.a = t2.b ORDER BY t1.a;
  a  | b  
@@ -4508,9 +4523,10 @@ EXPLAIN (COSTS OFF)
 SELECT t1.a, t1.c, t2.a, t2.c, t3.a, t3.c FROM plt1_adv t1 LEFT JOIN plt2_adv t2 ON (t1.a = t2.a AND t1.c = t2.c) LEFT JOIN plt1_adv t3 ON (t1.a = t3.a AND t1.c = t3.c) WHERE t1.b < 10 ORDER BY t1.a;
                                    QUERY PLAN                                   
 --------------------------------------------------------------------------------
- Sort
+ Merge Append
    Sort Key: t1.a
-   ->  Append
+   ->  Sort
+         Sort Key: t1_1.a
          ->  Hash Right Join
                Hash Cond: ((t3_1.a = t1_1.a) AND (t3_1.c = t1_1.c))
                ->  Seq Scan on plt1_adv_p1 t3_1
@@ -4521,6 +4537,8 @@ SELECT t1.a, t1.c, t2.a, t2.c, t3.a, t3.c FROM plt1_adv t1 LEFT JOIN plt2_adv t2
                            ->  Hash
                                  ->  Seq Scan on plt1_adv_p1 t1_1
                                        Filter: (b < 10)
+   ->  Sort
+         Sort Key: t1_2.a
          ->  Hash Right Join
                Hash Cond: ((t3_2.a = t1_2.a) AND (t3_2.c = t1_2.c))
                ->  Seq Scan on plt1_adv_p2 t3_2
@@ -4531,6 +4549,8 @@ SELECT t1.a, t1.c, t2.a, t2.c, t3.a, t3.c FROM plt1_adv t1 LEFT JOIN plt2_adv t2
                            ->  Hash
                                  ->  Seq Scan on plt1_adv_p2 t1_2
                                        Filter: (b < 10)
+   ->  Sort
+         Sort Key: t1_3.a
          ->  Hash Right Join
                Hash Cond: ((t3_3.a = t1_3.a) AND (t3_3.c = t1_3.c))
                ->  Seq Scan on plt1_adv_p3 t3_3
@@ -4541,15 +4561,19 @@ SELECT t1.a, t1.c, t2.a, t2.c, t3.a, t3.c FROM plt1_adv t1 LEFT JOIN plt2_adv t2
                            ->  Hash
                                  ->  Seq Scan on plt1_adv_p3 t1_3
                                        Filter: (b < 10)
-         ->  Nested Loop Left Join
-               Join Filter: ((t1_4.a = t3_4.a) AND (t1_4.c = t3_4.c))
-               ->  Nested Loop Left Join
-                     Join Filter: ((t1_4.a = t2_4.a) AND (t1_4.c = t2_4.c))
+   ->  Nested Loop Left Join
+         Join Filter: ((t1_4.a = t3_4.a) AND (t1_4.c = t3_4.c))
+         ->  Merge Left Join
+               Merge Cond: ((t1_4.a = t2_4.a) AND (t1_4.c = t2_4.c))
+               ->  Sort
+                     Sort Key: t1_4.a, t1_4.c
                      ->  Seq Scan on plt1_adv_extra t1_4
                            Filter: (b < 10)
+               ->  Sort
+                     Sort Key: t2_4.a, t2_4.c
                      ->  Seq Scan on plt2_adv_extra t2_4
-               ->  Seq Scan on plt1_adv_extra t3_4
-(41 rows)
+         ->  Seq Scan on plt1_adv_extra t3_4
+(50 rows)
 
 SELECT t1.a, t1.c, t2.a, t2.c, t3.a, t3.c FROM plt1_adv t1 LEFT JOIN plt2_adv t2 ON (t1.a = t2.a AND t1.c = t2.c) LEFT JOIN plt1_adv t3 ON (t1.a = t3.a AND t1.c = t3.c) WHERE t1.b < 10 ORDER BY t1.a;
  a  |  c   | a |  c   | a |  c   
@@ -5037,21 +5061,26 @@ EXPLAIN (COSTS OFF)
 SELECT t1.*, t2.* FROM alpha t1 INNER JOIN beta t2 ON (t1.a = t2.a AND t1.b = t2.b) WHERE t1.b >= 125 AND t1.b < 225 ORDER BY t1.a, t1.b;
                              QUERY PLAN                             
 --------------------------------------------------------------------
- Sort
+ Merge Append
    Sort Key: t1.a, t1.b
-   ->  Append
+   ->  Sort
+         Sort Key: t1_1.a, t1_1.b
          ->  Hash Join
                Hash Cond: ((t1_1.a = t2_1.a) AND (t1_1.b = t2_1.b))
                ->  Seq Scan on alpha_neg_p1 t1_1
                      Filter: ((b >= 125) AND (b < 225))
                ->  Hash
                      ->  Seq Scan on beta_neg_p1 t2_1
+   ->  Sort
+         Sort Key: t1_2.a, t1_2.b
          ->  Hash Join
                Hash Cond: ((t2_2.a = t1_2.a) AND (t2_2.b = t1_2.b))
                ->  Seq Scan on beta_neg_p2 t2_2
                ->  Hash
                      ->  Seq Scan on alpha_neg_p2 t1_2
                            Filter: ((b >= 125) AND (b < 225))
+   ->  Sort
+         Sort Key: t1_4.a, t1_4.b
          ->  Hash Join
                Hash Cond: ((t2_4.a = t1_4.a) AND (t2_4.b = t1_4.b))
                ->  Append
@@ -5066,7 +5095,7 @@ SELECT t1.*, t2.* FROM alpha t1 INNER JOIN beta t2 ON (t1.a = t2.a AND t1.b = t2
                                  Filter: ((b >= 125) AND (b < 225))
                            ->  Seq Scan on alpha_pos_p3 t1_6
                                  Filter: ((b >= 125) AND (b < 225))
-(29 rows)
+(34 rows)
 
 SELECT t1.*, t2.* FROM alpha t1 INNER JOIN beta t2 ON (t1.a = t2.a AND t1.b = t2.b) WHERE t1.b >= 125 AND t1.b < 225 ORDER BY t1.a, t1.b;
  a  |  b  |  c   | a  |  b  |  c   
diff --git a/src/test/regress/expected/partition_prune.out b/src/test/regress/expected/partition_prune.out
index 0bf35260b46..b25aa73e946 100644
--- a/src/test/regress/expected/partition_prune.out
+++ b/src/test/regress/expected/partition_prune.out
@@ -4763,9 +4763,10 @@ select min(a) over (partition by a order by a) from part_abc where a >= stable_o
                Window: w1 AS (PARTITION BY part_abc.a ORDER BY part_abc.a)
                ->  Append
                      Subplans Removed: 1
-                     ->  Index Scan using part_abc_2_a_idx on part_abc_2 part_abc_1
-                           Index Cond: (a >= (stable_one() + 1))
-                           Filter: (d <= stable_one())
+                     ->  Sort
+                           Sort Key: part_abc_1.a
+                           ->  Seq Scan on part_abc_2 part_abc_1
+                                 Filter: ((d <= stable_one()) AND (a >= (stable_one() + 1)))
                      ->  Merge Append
                            Sort Key: part_abc_3.a
                            Subplans Removed: 1
@@ -4780,9 +4781,10 @@ select min(a) over (partition by a order by a) from part_abc where a >= stable_o
                Window: w1 AS (PARTITION BY part_abc_5.a ORDER BY part_abc_5.a)
                ->  Append
                      Subplans Removed: 1
-                     ->  Index Scan using part_abc_2_a_idx on part_abc_2 part_abc_6
-                           Index Cond: (a >= (stable_one() + 1))
-                           Filter: (d >= stable_one())
+                     ->  Sort
+                           Sort Key: part_abc_6.a
+                           ->  Seq Scan on part_abc_2 part_abc_6
+                                 Filter: ((d >= stable_one()) AND (a >= (stable_one() + 1)))
                      ->  Merge Append
                            Sort Key: a
                            Subplans Removed: 1
@@ -4792,7 +4794,7 @@ select min(a) over (partition by a order by a) from part_abc where a >= stable_o
                            ->  Index Scan using part_abc_3_3_a_idx on part_abc_3_3 part_abc_9
                                  Index Cond: (a >= (stable_one() + 1))
                                  Filter: (d >= stable_one())
-(35 rows)
+(37 rows)
 
 drop view part_abc_view;
 drop table part_abc;
diff --git a/src/test/regress/expected/union.out b/src/test/regress/expected/union.out
index 96962817ed4..0ccadea910c 100644
--- a/src/test/regress/expected/union.out
+++ b/src/test/regress/expected/union.out
@@ -1207,12 +1207,14 @@ select event_id
 ----------------------------------------------------------
  Merge Append
    Sort Key: events.event_id
-   ->  Index Scan using events_pkey on events
+   ->  Sort
+         Sort Key: events.event_id
+         ->  Seq Scan on events
    ->  Sort
          Sort Key: events_1.event_id
          ->  Seq Scan on events_child events_1
    ->  Index Scan using other_events_pkey on other_events
-(7 rows)
+(9 rows)
 
 drop table events_child, events, other_events;
 reset enable_indexonlyscan;
diff --git a/src/test/regress/sql/inherit.sql b/src/test/regress/sql/inherit.sql
index 699e8ac09c8..c58beebbd1e 100644
--- a/src/test/regress/sql/inherit.sql
+++ b/src/test/regress/sql/inherit.sql
@@ -641,12 +641,14 @@ insert into matest2 (name) values ('Test 4');
 insert into matest3 (name) values ('Test 5');
 insert into matest3 (name) values ('Test 6');
 
-set enable_indexscan = off;  -- force use of seqscan/sort, so no merge
+set enable_indexscan = off;  -- force use of seqscan/sort
+set enable_sort = off; -- since merge append may employ sort in children we need to disable sort
 explain (verbose, costs off) select * from matest0 order by 1-id;
 select * from matest0 order by 1-id;
 explain (verbose, costs off) select min(1-id) from matest0;
 select min(1-id) from matest0;
 reset enable_indexscan;
+reset enable_sort;
 
 set enable_seqscan = off;  -- plan with fewest seqscans should be merge
 set enable_parallel_append = off; -- Don't let parallel-append interfere
-- 
2.39.5