mergeappend_to_append_conversion_v15.patch

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 910a738c20..755ef43caa 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1847,6 +1847,7 @@ _outAppendPath(StringInfo str, const AppendPath *node)
 	WRITE_NODE_FIELD(partitioned_rels);
 	WRITE_NODE_FIELD(subpaths);
 	WRITE_INT_FIELD(first_partial_path);
+	WRITE_FLOAT_FIELD(limit_tuples, "%.0f");
 }
 
 static void
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index da0d778721..27699a59d1 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -96,15 +96,16 @@ static void set_append_rel_size(PlannerInfo *root, RelOptInfo *rel,
 					Index rti, RangeTblEntry *rte);
 static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 						Index rti, RangeTblEntry *rte);
-static void generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
-						   List *live_childrels,
-						   List *all_child_pathkeys,
-						   List *partitioned_rels);
+static void generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel,
+							 List *live_childrels,
+							 List *all_child_pathkeys,
+							 List *partitioned_rels);
 static Path *get_cheapest_parameterized_child_path(PlannerInfo *root,
 									  RelOptInfo *rel,
 									  Relids required_outer);
 static void accumulate_append_subpath(Path *path,
 						  List **subpaths, List **special_subpaths);
+static Path *get_singleton_append_subpath(Path *path);
 static void set_dummy_rel_pathlist(RelOptInfo *rel);
 static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 					  Index rti, RangeTblEntry *rte);
@@ -1551,7 +1552,7 @@ add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 	 */
 	if (subpaths_valid)
 		add_path(rel, (Path *) create_append_path(root, rel, subpaths, NIL,
-												  NULL, 0, false,
+												  NIL, NULL, 0, false,
 												  partitioned_rels, -1));
 
 	/*
@@ -1593,7 +1594,7 @@ add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 
 		/* Generate a partial append path. */
 		appendpath = create_append_path(root, rel, NIL, partial_subpaths,
-										NULL, parallel_workers,
+										NIL, NULL, parallel_workers,
 										enable_parallel_append,
 										partitioned_rels, -1);
 
@@ -1643,19 +1644,19 @@ add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 
 		appendpath = create_append_path(root, rel, pa_nonpartial_subpaths,
 										pa_partial_subpaths,
-										NULL, parallel_workers, true,
+										NIL, NULL, parallel_workers, true,
 										partitioned_rels, partial_rows);
 		add_partial_path(rel, (Path *) appendpath);
 	}
 
 	/*
-	 * Also build unparameterized MergeAppend paths based on the collected
+	 * Also build unparameterized ordered append paths based on the collected
 	 * list of child pathkeys.
 	 */
 	if (subpaths_valid)
-		generate_mergeappend_paths(root, rel, live_childrels,
-								   all_child_pathkeys,
-								   partitioned_rels);
+		generate_orderedappend_paths(root, rel, live_childrels,
+									 all_child_pathkeys,
+									 partitioned_rels);
 
 	/*
 	 * Build Append paths for each parameterization seen among the child rels.
@@ -1705,7 +1706,7 @@ add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 		if (subpaths_valid)
 			add_path(rel, (Path *)
 					 create_append_path(root, rel, subpaths, NIL,
-										required_outer, 0, false,
+										NIL, required_outer, 0, false,
 										partitioned_rels, -1));
 	}
 
@@ -1734,44 +1735,82 @@ add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 				continue;
 
 			appendpath = create_append_path(root, rel, NIL, list_make1(path),
-											NULL, path->parallel_workers,
-											true,
-											partitioned_rels, partial_rows);
+											NIL, NULL, path->parallel_workers,
+											true, partitioned_rels,
+											partial_rows);
 			add_partial_path(rel, (Path *) appendpath);
 		}
 	}
 }
 
 /*
- * generate_mergeappend_paths
- *		Generate MergeAppend paths for an append relation
+ * generate_orderedappend_paths
+ *		Generate ordered append paths for an append relation.
  *
- * Generate a path for each ordering (pathkey list) appearing in
+ * Generally we generate MergeAppend paths here, but there are some special
+ * cases where we can generate simple Append paths when we're able to
+ * determine that the list of subpaths provide tuples in the required order.
+ *
+ * We generate a path for each ordering (pathkey list) appearing in
  * all_child_pathkeys.
  *
  * We consider both cheapest-startup and cheapest-total cases, ie, for each
  * interesting ordering, collect all the cheapest startup subpaths and all the
- * cheapest total paths, and build a MergeAppend path for each case.
- *
- * We don't currently generate any parameterized MergeAppend paths.  While
- * it would not take much more code here to do so, it's very unclear that it
- * is worth the planning cycles to investigate such paths: there's little
- * use for an ordered path on the inside of a nestloop.  In fact, it's likely
- * that the current coding of add_path would reject such paths out of hand,
- * because add_path gives no credit for sort ordering of parameterized paths,
- * and a parameterized MergeAppend is going to be more expensive than the
+ * cheapest total paths, and build a suitable path for each case.
+ *
+ * We don't currently generate any parameterized paths here.  While it would
+ * not take much more code to do so, it's very unclear that it is worth the
+ * planning cycles to investigate such paths: there's little use for an
+ * ordered path on the inside of a nestloop.  In fact, it's likely that the
+ * current coding of add_path would reject such paths out of hand, because
+ * add_path gives no credit for sort ordering of parameterized paths, and a
+ * parameterized MergeAppend is going to be more expensive than the
  * corresponding parameterized Append path.  If we ever try harder to support
  * parameterized mergejoin plans, it might be worth adding support for
- * parameterized MergeAppends to feed such joins.  (See notes in
+ * parameterized paths here to feed such joins.  (See notes in
  * optimizer/README for why that might not ever happen, though.)
  */
 static void
-generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
-						   List *live_childrels,
-						   List *all_child_pathkeys,
-						   List *partitioned_rels)
+generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel,
+							 List *live_childrels,
+							 List *all_child_pathkeys,
+							 List *partitioned_rels)
 {
 	ListCell   *lcp;
+	List	   *partition_pathkeys = NIL;
+	List	   *partition_pathkeys_desc = NIL;
+	bool		partition_pathkeys_partial = true;
+	bool		partition_pathkeys_desc_partial = true;
+
+	/*
+	 * Some partitioned table setups may allow us to use an Append node
+	 * instead of a MergeAppend.  This is possible in cases such as RANGE
+	 * partitioned tables where it's guaranteed that an earlier partition must
+	 * contain rows which come earlier in the sort order.
+	 */
+	if (rel->part_scheme != NULL && IS_SIMPLE_REL(rel) &&
+		partitions_are_ordered(root, rel))
+	{
+		partition_pathkeys = build_partition_pathkeys(root, rel,
+													  ForwardScanDirection,
+													  &partition_pathkeys_partial);
+
+		partition_pathkeys_desc = build_partition_pathkeys(root, rel,
+														   BackwardScanDirection,
+														   &partition_pathkeys_desc_partial);
+
+		/*
+		 * You might think we should truncate_useless_pathkeys here, but
+		 * allowing partition keys which are a subset of the query's pathkeys
+		 * can often be useful.  For example, a RANGE partitioned table on (a,
+		 * b), and a query with an ORDER BY a, b, c.  We can still allow an
+		 * Append scan in this case.  Imagine each partition has a btree index
+		 * on (a, b, c), scanning those indexes still provides tuples in the
+		 * correct order and using an Append in place of a MergeAppend is
+		 * still valid since lower-order  (a, b) tuples will still come before
+		 * higher-order ones over all partitions.
+		 */
+	}
 
 	foreach(lcp, all_child_pathkeys)
 	{
@@ -1780,6 +1819,29 @@ generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
 		List	   *total_subpaths = NIL;
 		bool		startup_neq_total = false;
 		ListCell   *lcr;
+		bool		partition_order;
+		bool		partition_order_desc;
+
+		/*
+		 * Determine if these pathkeys are contained in the partition pathkeys
+		 * for both ascending and decending partition order.  If the
+		 * partitioned pathkeys happened to be contained in pathkeys then this
+		 * is fine too, providing that the partition pathkeys are complete and
+		 * not just a prefix of the partition order.  In this case an Append
+		 * scan cannot produce any out of order tuples.
+		 */
+		partition_order = pathkeys_contained_in(pathkeys,
+												partition_pathkeys) ||
+			(!partition_pathkeys_partial &&
+			 pathkeys_contained_in(partition_pathkeys, pathkeys));
+
+		partition_order_desc = !partition_order &&
+			(pathkeys_contained_in(pathkeys,
+								   partition_pathkeys_desc) ||
+			 (!partition_pathkeys_desc_partial &&
+			  pathkeys_contained_in(partition_pathkeys_desc,
+									pathkeys)));
+
 
 		/* Select the child paths for this ordering... */
 		foreach(lcr, live_childrels)
@@ -1822,26 +1884,86 @@ generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
 			if (cheapest_startup != cheapest_total)
 				startup_neq_total = true;
 
-			accumulate_append_subpath(cheapest_startup,
-									  &startup_subpaths, NULL);
-			accumulate_append_subpath(cheapest_total,
-									  &total_subpaths, NULL);
+			/*
+			 * Build an Append path when in partition order.  If in reverse
+			 * partition order we build a reverse list of subpaths so that we
+			 * scan them in the opposite order.
+			 */
+			if (partition_order)
+			{
+				/*
+				 * Attempt to flatten subpaths that are themselves Appends or
+				 * MergeAppends.  We can do this providing the Append or
+				 * MergeAppend has just a single subpath.  If there are
+				 * multiple subpaths then we can't make guarantees about the
+				 * order tuples in those subpaths, so we must leave the
+				 * Append/MergeAppend in place.
+				 */
+				cheapest_startup = get_singleton_append_subpath(cheapest_startup);
+				cheapest_total = get_singleton_append_subpath(cheapest_total);
+
+				startup_subpaths = lappend(startup_subpaths, cheapest_startup);
+				total_subpaths = lappend(total_subpaths, cheapest_total);
+			}
+			else if (partition_order_desc)
+			{
+				cheapest_startup = get_singleton_append_subpath(cheapest_startup);
+				cheapest_total = get_singleton_append_subpath(cheapest_total);
+
+				startup_subpaths = lcons(cheapest_startup, startup_subpaths);
+				total_subpaths = lcons(cheapest_total, total_subpaths);
+			}
+			else
+			{
+				accumulate_append_subpath(cheapest_startup,
+										  &startup_subpaths, NULL);
+				accumulate_append_subpath(cheapest_total,
+										  &total_subpaths, NULL);
+			}
 		}
 
-		/* ... and build the MergeAppend paths */
-		add_path(rel, (Path *) create_merge_append_path(root,
-														rel,
-														startup_subpaths,
-														pathkeys,
-														NULL,
-														partitioned_rels));
-		if (startup_neq_total)
+		/* Build simple Append paths if in partition asc/desc order */
+		if (partition_order || partition_order_desc)
+		{
+			add_path(rel, (Path *) create_append_path(root,
+													  rel,
+													  startup_subpaths,
+													  NIL,
+													  pathkeys,
+													  NULL,
+													  0,
+													  false,
+													  partitioned_rels,
+													  -1));
+			if (startup_neq_total)
+				add_path(rel, (Path *) create_append_path(root,
+														  rel,
+														  total_subpaths,
+														  NIL,
+														  pathkeys,
+														  NULL,
+														  0,
+														  false,
+														  partitioned_rels,
+														  -1));
+		}
+		else
+		{
+			/* else just build the MergeAppend paths */
 			add_path(rel, (Path *) create_merge_append_path(root,
 															rel,
-															total_subpaths,
+															startup_subpaths,
 															pathkeys,
 															NULL,
 															partitioned_rels));
+			if (startup_neq_total)
+				add_path(rel, (Path *) create_merge_append_path(root,
+																rel,
+																total_subpaths,
+																pathkeys,
+																NULL,
+																partitioned_rels));
+		}
 	}
 }
 
@@ -1982,6 +2104,34 @@ accumulate_append_subpath(Path *path, List **subpaths, List **special_subpaths)
 	*subpaths = lappend(*subpaths, path);
 }
 
+/*
+ * get_singleton_append_subpath
+ *		Returns the singleton subpath of an Append/MergeAppend or
+ *		return 'path' if it's not a single sub-path Append/MergeAppend.
+ */
+static Path *
+get_singleton_append_subpath(Path *path)
+{
+	if (IsA(path, AppendPath))
+	{
+		AppendPath *apath = (AppendPath *) path;
+
+		Assert(!apath->path.parallel_aware);
+
+		if (list_length(apath->subpaths) == 1)
+			return (Path *) linitial(apath->subpaths);
+	}
+	else if (IsA(path, MergeAppendPath))
+	{
+		MergeAppendPath *mpath = (MergeAppendPath *) path;
+
+		if (list_length(mpath->subpaths) == 1)
+			return (Path *) linitial(mpath->subpaths);
+	}
+
+	return path;
+}
+
 /*
  * set_dummy_rel_pathlist
  *	  Build a dummy path for a relation that's been excluded by constraints
@@ -2005,7 +2155,7 @@ set_dummy_rel_pathlist(RelOptInfo *rel)
 	rel->partial_pathlist = NIL;
 
 	/* Set up the dummy path */
-	add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL,
+	add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL, NIL,
 											  rel->lateral_relids,
 											  0, false, NIL, -1));
 
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 4b9be13f08..f3f9c421a3 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1872,7 +1872,7 @@ append_nonpartial_cost(List *subpaths, int numpaths, int parallel_workers)
  *	  Determines and returns the cost of an Append node.
  */
 void
-cost_append(AppendPath *apath)
+cost_append(PlannerInfo *root, AppendPath *apath)
 {
 	ListCell   *l;
 
@@ -1884,21 +1884,72 @@ cost_append(AppendPath *apath)
 
 	if (!apath->path.parallel_aware)
 	{
-		Path	   *subpath = (Path *) linitial(apath->subpaths);
+		List	   *pathkeys = apath->path.pathkeys;
 
-		/*
-		 * Startup cost of non-parallel-aware Append is the startup cost of
-		 * first subpath.
-		 */
-		apath->path.startup_cost = subpath->startup_cost;
+		if (pathkeys == NIL)
+		{
+			Path	   *subpath = (Path *) linitial(apath->subpaths);
 
-		/* Compute rows and costs as sums of subplan rows and costs. */
-		foreach(l, apath->subpaths)
+			/*
+			 * When there are no pathkeys the startup cost of
+			 * non-parallel-aware Append is the startup cost of the first
+			 * subpath.
+			 */
+			apath->path.startup_cost = subpath->startup_cost;
+
+			foreach(l, apath->subpaths)
+			{
+				Path	   *subpath = (Path *) lfirst(l);
+
+				apath->path.rows += subpath->rows;
+				apath->path.total_cost += subpath->total_cost;
+			}
+		}
+		else
 		{
-			Path	   *subpath = (Path *) lfirst(l);
+			/*
+			 * Otherwise we make the Append's startup cost the sum of the
+			 * startup cost of all the subpaths.  It may appear like we should
+			 * just be doing the same as above and take the startup cost of
+			 * just the initial subpath, however, it is possible that when a
+			 * LIMIT clause exists in the query that we could end up favoring
+			 * these ordered Append paths too much.  Imagine a scenario where
+			 * the initial subpath is already ordered and is estimated to
+			 * contain just 10 rows and the 2nd subpath requires a sort and is
+			 * estimated to have 10 million rows, if the query has LIMIT 11
+			 * then we could end up performing an expensive sort for just a
+			 * single row without having considered the startup cost for the
+			 * 2nd subpath.  Such a scenario could end up favoring a MergeJoin
+			 * plan instead of a Hash Join plan.
+			 */
+			foreach(l, apath->subpaths)
+			{
+				Path	   *subpath = (Path *) lfirst(l);
+				Path		sort_path;	/* dummy for result of cost_sort */
+
+				if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
+				{
+					/*
+					 * We'll need to insert a Sort node, so include cost for
+					 * that.
+					 */
+					cost_sort(&sort_path,
+							  root,
+							  pathkeys,
+							  subpath->total_cost,
+							  subpath->parent->tuples,
+							  subpath->pathtarget->width,
+							  0.0,
+							  work_mem,
+							  apath->limit_tuples);
+
+					subpath = &sort_path;
+				}
 
-			apath->path.rows += subpath->rows;
-			apath->path.total_cost += subpath->total_cost;
+				apath->path.rows += subpath->rows;
+				apath->path.startup_cost += subpath->startup_cost;
+				apath->path.total_cost += subpath->total_cost;
+			}
 		}
 	}
 	else						/* parallel-aware */
@@ -1906,6 +1957,8 @@ cost_append(AppendPath *apath)
 		int			i = 0;
 		double		parallel_divisor = get_parallel_divisor(&apath->path);
 
+		Assert(apath->path.pathkeys == NIL);
+
 		/* Calculate startup cost. */
 		foreach(l, apath->subpaths)
 		{
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 9604a54b77..7044899dc1 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -1264,7 +1264,7 @@ mark_dummy_rel(RelOptInfo *rel)
 	rel->partial_pathlist = NIL;
 
 	/* Set up the dummy path */
-	add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL,
+	add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL, NIL,
 											  rel->lateral_relids,
 											  0, false, NIL, -1));
 
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 56d839bb31..e5580966f6 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -24,6 +24,8 @@
 #include "optimizer/optimizer.h"
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
+#include "partitioning/partbounds.h"
+#include "partitioning/partprune.h"
 #include "utils/lsyscache.h"
 
 
@@ -546,6 +548,77 @@ build_index_pathkeys(PlannerInfo *root,
 	return retval;
 }
 
+/*
+ * build_partition_pathkeys
+ *	  Build a pathkeys list that describes the ordering induced by the
+ *	  partitions of 'partrel'.  (Callers must ensure that this partitioned
+ *	  table guarantees that lower order tuples never will be found in a
+ *	  later partition.).  Sets *partialkeys to false if pathkeys were only
+ *	  built for a prefix of the partition key, otherwise sets it to true.
+ */
+List *
+build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
+						 ScanDirection scandir, bool *partialkeys)
+{
+	PartitionScheme partscheme;
+	List	   *retval = NIL;
+	int			i;
+
+	Assert(partitions_are_ordered(root, partrel));
+
+	partscheme = partrel->part_scheme;
+
+	for (i = 0; i < partscheme->partnatts; i++)
+	{
+		PathKey    *cpathkey;
+		Expr	   *keyCol = linitial(partrel->partexprs[i]);
+
+		/*
+		 * OK, try to make a canonical pathkey for this part key.  Note we're
+		 * underneath any outer joins, so nullable_relids should be NULL.
+		 */
+		cpathkey = make_pathkey_from_sortinfo(root,
+											  keyCol,
+											  NULL,
+											  partscheme->partopfamily[i],
+											  partscheme->partopcintype[i],
+											  partscheme->partcollation[i],
+											  ScanDirectionIsBackward(scandir),
+											  ScanDirectionIsBackward(scandir),
+											  0,
+											  partrel->relids,
+											  false);
+
+		/*
+		 * When unable to create the pathkey we'll just need to return
+		 * whatever ones we have so far.
+		 */
+		if (cpathkey == NULL)
+		{
+			/*
+			 * Boolean partition keys might be redundant even if they do not
+			 * appear in an EquivalenceClass, because of our special treatment
+			 * of boolean equality conditions --- see the comment for
+			 * partkey_is_bool_constant_for_query().  If that applies, we can
+			 * continue to examine lower-order partition keys.  Otherwise, we
+			 * must abort and return any partial matches we've found so far.
+			 */
+			if (partkey_is_bool_constant_for_query(partrel, i))
+				continue;
+
+			*partialkeys = true;
+			return retval;
+		}
+
+		/* Add it to list, unless it's redundant. */
+		if (!pathkey_is_redundant(cpathkey, retval))
+			retval = lappend(retval, cpathkey);
+	}
+
+	*partialkeys = false;
+	return retval;
+}
+
 /*
  * build_expression_pathkey
  *	  Build a pathkeys list that describes an ordering by a single expression
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 979c3c212f..49f02ee1e6 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -205,8 +205,6 @@ static NamedTuplestoreScan *make_namedtuplestorescan(List *qptlist, List *qpqual
 						 Index scanrelid, char *enrname);
 static WorkTableScan *make_worktablescan(List *qptlist, List *qpqual,
 				   Index scanrelid, int wtParam);
-static Append *make_append(List *appendplans, int first_partial_plan,
-			List *tlist, PartitionPruneInfo *partpruneinfo);
 static RecursiveUnion *make_recursive_union(List *tlist,
 					 Plan *lefttree,
 					 Plan *righttree,
@@ -1058,12 +1056,20 @@ create_join_plan(PlannerInfo *root, JoinPath *best_path)
 static Plan *
 create_append_plan(PlannerInfo *root, AppendPath *best_path)
 {
-	Append	   *plan;
+	Append	   *node = makeNode(Append);
+	Plan	   *plan = &node->plan;
 	List	   *tlist = build_path_tlist(root, &best_path->path);
+	List	   *pathkeys = best_path->path.pathkeys;
 	List	   *subplans = NIL;
 	ListCell   *subpaths;
 	RelOptInfo *rel = best_path->path.parent;
 	PartitionPruneInfo *partpruneinfo = NULL;
+	AttrNumber *nodeSortColIdx;
+
+	plan->targetlist = tlist;
+	plan->qual = NIL;
+	plan->lefttree = NULL;
+	plan->righttree = NULL;
 
 	/*
 	 * The subpaths list could be empty, if every child was proven empty by
@@ -1089,6 +1095,28 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path)
 		return plan;
 	}
 
+	if (pathkeys != NIL)
+	{
+		int			nodenumsortkeys;
+		Oid		   *nodeSortOperators;
+		Oid		   *nodeCollations;
+		bool	   *nodeNullsFirst;
+
+		/*
+		 * Compute sort column info, and adjust the Append's tlist as needed.
+		 * We only need the 'nodeSortColIdx' from all of the output params.
+		 */
+		(void) prepare_sort_from_pathkeys(plan, pathkeys,
+										  best_path->path.parent->relids,
+										  NULL,
+										  true,
+										  &nodenumsortkeys,
+										  &nodeSortColIdx,
+										  &nodeSortOperators,
+										  &nodeCollations,
+										  &nodeNullsFirst);
+	}
+
 	/* Build the plan for each child */
 	foreach(subpaths, best_path->subpaths)
 	{
@@ -1098,6 +1126,39 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path)
 		/* Must insist that all children return the same tlist */
 		subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
 
+		/*
+		 * Now, for appends with pathkeys, insert a Sort node if subplan isn't
+		 * sufficiently ordered.
+		 */
+		if (pathkeys != NIL)
+		{
+			int			numsortkeys;
+			AttrNumber *sortColIdx;
+			Oid		   *sortOperators;
+			Oid		   *collations;
+			bool	   *nullsFirst;
+
+			/* Compute sort column info, and adjust subplan's tlist as needed */
+			subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+												 subpath->parent->relids,
+												 nodeSortColIdx,
+												 false,
+												 &numsortkeys,
+												 &sortColIdx,
+												 &sortOperators,
+												 &collations,
+												 &nullsFirst);
+
+			if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
+			{
+				Sort	   *sort = make_sort(subplan, numsortkeys,
+											 sortColIdx, sortOperators,
+											 collations, nullsFirst);
+
+				label_sort_with_costsize(root, sort, best_path->limit_tuples);
+				subplan = (Plan *) sort;
+			}
+		}
 		subplans = lappend(subplans, subplan);
 	}
 
@@ -1140,10 +1201,11 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path)
 	 * won't match the parent-rel Vars it'll be asked to emit.
 	 */
 
-	plan = make_append(subplans, best_path->first_partial_path,
-					   tlist, partpruneinfo);
+	node->appendplans = subplans;
+	node->first_partial_plan = best_path->first_partial_path;
+	node->part_prune_info = partpruneinfo;
 
-	copy_generic_path_info(&plan->plan, (Path *) best_path);
+	copy_generic_path_info(plan, (Path *) best_path);
 
 	return (Plan *) plan;
 }
@@ -5300,23 +5362,6 @@ make_foreignscan(List *qptlist,
 	return node;
 }
 
-static Append *
-make_append(List *appendplans, int first_partial_plan,
-			List *tlist, PartitionPruneInfo *partpruneinfo)
-{
-	Append	   *node = makeNode(Append);
-	Plan	   *plan = &node->plan;
-
-	plan->targetlist = tlist;
-	plan->qual = NIL;
-	plan->lefttree = NULL;
-	plan->righttree = NULL;
-	node->appendplans = appendplans;
-	node->first_partial_plan = first_partial_plan;
-	node->part_prune_info = partpruneinfo;
-	return node;
-}
-
 static RecursiveUnion *
 make_recursive_union(List *tlist,
 					 Plan *lefttree,
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index e408e77d6f..02f805129f 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -1597,7 +1597,8 @@ inheritance_planner(PlannerInfo *root)
 
 		/* Make a dummy path, cf set_dummy_rel_pathlist() */
 		dummy_path = (Path *) create_append_path(NULL, final_rel, NIL, NIL,
-												 NULL, 0, false, NIL, -1);
+												 NIL, NULL, 0, false, NIL,
+												 -1);
 
 		/* These lists must be nonempty to make a valid ModifyTable node */
 		subpaths = list_make1(dummy_path);
@@ -3878,6 +3879,7 @@ create_degenerate_grouping_paths(PlannerInfo *root, RelOptInfo *input_rel,
 							   grouped_rel,
 							   paths,
 							   NIL,
+							   NIL,
 							   NULL,
 							   0,
 							   false,
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index eb815c2f12..65d77a5402 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -616,7 +616,7 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 	/*
 	 * Append the child results together.
 	 */
-	path = (Path *) create_append_path(root, result_rel, pathlist, NIL,
+	path = (Path *) create_append_path(root, result_rel, pathlist, NIL, NIL,
 									   NULL, 0, false, NIL, -1);
 
 	/*
@@ -671,7 +671,7 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
 		Assert(parallel_workers > 0);
 
 		ppath = (Path *)
-			create_append_path(root, result_rel, NIL, partial_pathlist,
+			create_append_path(root, result_rel, NIL, partial_pathlist, NIL,
 							   NULL, parallel_workers, enable_parallel_append,
 							   NIL, -1);
 		ppath = (Path *)
@@ -782,7 +782,7 @@ generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
 	/*
 	 * Append the child results together.
 	 */
-	path = (Path *) create_append_path(root, result_rel, pathlist, NIL,
+	path = (Path *) create_append_path(root, result_rel, pathlist, NIL, NIL,
 									   NULL, 0, false, NIL, -1);
 
 	/* Identify the grouping semantics */
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 56de8fc370..5e3309955f 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1208,7 +1208,7 @@ AppendPath *
 create_append_path(PlannerInfo *root,
 				   RelOptInfo *rel,
 				   List *subpaths, List *partial_subpaths,
-				   Relids required_outer,
+				   List *pathkeys, Relids required_outer,
 				   int parallel_workers, bool parallel_aware,
 				   List *partitioned_rels, double rows)
 {
@@ -1242,6 +1242,7 @@ create_append_path(PlannerInfo *root,
 	pathnode->path.parallel_aware = parallel_aware;
 	pathnode->path.parallel_safe = rel->consider_parallel;
 	pathnode->path.parallel_workers = parallel_workers;
+	pathnode->path.pathkeys = pathkeys;
 	pathnode->partitioned_rels = list_copy(partitioned_rels);
 
 	/*
@@ -1251,10 +1252,14 @@ create_append_path(PlannerInfo *root,
 	 * costs.  There may be some paths that require to do startup work by a
 	 * single worker.  In such case, it's better for workers to choose the
 	 * expensive ones first, whereas the leader should choose the cheapest
-	 * startup plan.
+	 * startup plan.  Note: We mustn't fiddle with the order of subpaths when
+	 * the Append has valid pathkeys.  The order they're listed in is critical
+	 * to keeping the pathkeys valid.
 	 */
 	if (pathnode->path.parallel_aware)
 	{
+		Assert(pathkeys == NIL);
+
 		subpaths = list_qsort(subpaths, append_total_cost_compare);
 		partial_subpaths = list_qsort(partial_subpaths,
 									  append_startup_cost_compare);
@@ -1262,6 +1267,15 @@ create_append_path(PlannerInfo *root,
 	pathnode->first_partial_path = list_length(subpaths);
 	pathnode->subpaths = list_concat(subpaths, partial_subpaths);
 
+	/*
+	 * Apply query-wide LIMIT if known and path is for sole base relation.
+	 * (Handling this at this low level is a bit klugy.)
+	 */
+	if (root != NULL && bms_equal(rel->relids, root->all_baserels))
+		pathnode->limit_tuples = root->limit_tuples;
+	else
+		pathnode->limit_tuples = -1.0;
+
 	foreach(l, pathnode->subpaths)
 	{
 		Path	   *subpath = (Path *) lfirst(l);
@@ -1291,10 +1305,7 @@ create_append_path(PlannerInfo *root,
 		pathnode->path.pathkeys = child->pathkeys;
 	}
 	else
-	{
-		pathnode->path.pathkeys = NIL;	/* unsorted if more than 1 subpath */
-		cost_append(pathnode);
-	}
+		cost_append(root, pathnode);
 
 	/* If the caller provided a row estimate, override the computed value. */
 	if (rows >= 0)
@@ -3736,7 +3747,7 @@ reparameterize_path(PlannerInfo *root, Path *path,
 				}
 				return (Path *)
 					create_append_path(root, rel, childpaths, partialpaths,
-									   required_outer,
+									   NIL, required_outer,
 									   apath->path.parallel_workers,
 									   apath->path.parallel_aware,
 									   apath->partitioned_rels,
diff --git a/src/backend/partitioning/partbounds.c b/src/backend/partitioning/partbounds.c
index bdd0d23854..630e619786 100644
--- a/src/backend/partitioning/partbounds.c
+++ b/src/backend/partitioning/partbounds.c
@@ -1680,6 +1680,8 @@ qsort_partition_hbound_cmp(const void *a, const void *b)
  * qsort_partition_list_value_cmp
  *
  * Compare two list partition bound datums.
+ *
+ * Note: If changing this, see build_partition_pathkeys()
  */
 static int32
 qsort_partition_list_value_cmp(const void *a, const void *b, void *arg)
@@ -1697,6 +1699,8 @@ qsort_partition_list_value_cmp(const void *a, const void *b, void *arg)
  * qsort_partition_rbound_cmp
  *
  * Used when sorting range bounds across all range partitions.
+ *
+ * Note: If changing this, see build_partition_pathkeys()
  */
 static int32
 qsort_partition_rbound_cmp(const void *a, const void *b, void *arg)
diff --git a/src/backend/partitioning/partprune.c b/src/backend/partitioning/partprune.c
index af3f91133e..4f971a323c 100644
--- a/src/backend/partitioning/partprune.c
+++ b/src/backend/partitioning/partprune.c
@@ -109,7 +109,9 @@ typedef struct PruneStepResult
 	bool		scan_null;		/* Scan the partition for NULL values? */
 } PruneStepResult;
 
-
+static bool matches_boolean_partition_clause(RestrictInfo *rinfo,
+								 int partkeycol,
+								 RelOptInfo *partrel);
 static List *make_partitionedrel_pruneinfo(PlannerInfo *root,
 							  RelOptInfo *parentrel,
 							  int *relid_subplan_map,
@@ -176,6 +178,138 @@ static bool partkey_datum_from_expr(PartitionPruneContext *context,
 						Expr *expr, int stateidx,
 						Datum *value, bool *isnull);
 
+/*
+ * partkey_is_bool_constant_for_query
+ *
+ * If a partition key column is constrained to have a constant value by the
+ * query's WHERE conditions, then it's irrelevant for sort-order
+ * considerations.  Restriction clauses like WHERE partkeycol = constant, get
+ * turned into an EquivalenceClass containing a constant, which is recognized
+ * as redundant by build_partition_pathkeys().  But if the partition column is
+ * a boolean variable (or expression), then we are not going to see WHERE
+ * partkeycol = constant, because expression preprocessing will have
+ * simplified that to "WHERE partkeycol" or "WHERE NOT partkeycol".  So we are
+ * not going to have a matching EquivalenceClass (unless the query also
+ * contains "ORDER BY partkeycol").  To allow such cases to work the same as
+ * they would for non-boolean values, this function is provided to detect
+ * whether the specified partkey column matches a boolean restriction clause.
+ */
+bool
+partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
+{
+	PartitionScheme partscheme;
+	ListCell   *lc;
+
+	partscheme = partrel->part_scheme;
+
+	/* If the partkey isn't boolean, we can't possibly get a match */
+	if (!IsBooleanOpfamily(partscheme->partopfamily[partkeycol]))
+		return false;
+
+	/* Check each restriction clause for partrel */
+	foreach(lc, partrel->baserestrictinfo)
+	{
+		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+
+		/* Skip pseudoconstant quals */
+		if (rinfo->pseudoconstant)
+			continue;
+
+		/* See if we can match the clause's expression to the partkey column */
+		if (matches_boolean_partition_clause(rinfo, partkeycol, partrel))
+			return true;
+	}
+
+	return false;
+}
+
+/*
+ * matches_boolean_partition_clause
+ *		Determine if rinfo matches partrel's 'partkeycol' partition key
+ *		column.
+ */
+static bool
+matches_boolean_partition_clause(RestrictInfo *rinfo, int partkeycol,
+								 RelOptInfo *partrel)
+{
+	Node	   *clause = (Node *) rinfo->clause;
+	Expr	   *partexpr = (Expr *) linitial(partrel->partexprs[partkeycol]);
+
+	/* Direct match? */
+	if (equal(partexpr, clause))
+		return true;
+	/* NOT clause? */
+	else if (is_notclause(clause))
+	{
+		Node	   *arg = (Node *) get_notclausearg((Expr *) clause);
+
+		if (equal(partexpr, arg))
+			return true;
+	}
+
+	return false;
+}
+
+/*
+ * partitions_are_ordered
+ *		For the partitioned table given in 'partrel', returns true if the
+ *		partitioned table guarantees that tuples which sort earlier according
+ *		to the partition bound are stored in a partition that comes earlier in
+ *		the relation's PartitionDesc.  Otherwise return false.
+ *
+ * This assumes nothing about the order of tuples inside the actual
+ * partitions.
+ */
+bool
+partitions_are_ordered(PlannerInfo *root, RelOptInfo *partrel)
+{
+	PartitionBoundInfo boundinfo = partrel->boundinfo;
+
+	Assert(boundinfo != NULL);
+
+	switch (boundinfo->strategy)
+	{
+			/*
+			 * RANGE type partitions guarantee that the partitions can be
+			 * scanned in the order that they're defined in the PartitionDesc
+			 * to provide non-overlapping ranges of tuples.  We must disallow
+			 * when a DEFAULT partition exists as this could contain tuples
+			 * from either below or above the defined range, or contain tuples
+			 * belonging to gaps in the defined range.
+			 */
+		case PARTITION_STRATEGY_RANGE:
+			if (partition_bound_has_default(boundinfo))
+				return false;
+			break;
+
+			/*
+			 * LIST partitions can also guarantee ordering, but we'd need to
+			 * ensure that partitions don't allow interleaved values.  We
+			 * could likely check for this looking at each partition, in
+			 * order, and checking which Datums are accepted.  If we find a
+			 * Datum in a partition that's greater than one previously already
+			 * seen, then values could become out of order and we'd have to
+			 * disable the optimization.  For now, let's just keep it simple
+			 * and just accept LIST partitions without a DEFAULT partition
+			 * which only accept a single Datum per partition.  This is cheap
+			 * as it does not require any per-partition processing.  Maybe
+			 * we'd like to handle more complex cases in the future.
+			 */
+		case PARTITION_STRATEGY_LIST:
+			if (partition_bound_has_default(boundinfo))
+				return false;
+
+			if (boundinfo->ndatums + partition_bound_accepts_nulls(boundinfo)
+				!= partrel->nparts)
+				return false;
+			break;
+
+		default:
+			return false;
+	}
+
+	return true;
+}
 
 /*
  * make_partition_pruneinfo
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 253e0b7e48..0bab42e853 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1361,6 +1361,7 @@ typedef struct AppendPath
 
 	/* Index of first partial path in subpaths */
 	int			first_partial_path;
+	double		limit_tuples;	/* hard limit on output tuples, or -1 */
 } AppendPath;
 
 #define IS_DUMMY_APPEND(p) \
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index ac6de0f6be..9da3f19c6e 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -103,7 +103,7 @@ extern void cost_sort(Path *path, PlannerInfo *root,
 		  List *pathkeys, Cost input_cost, double tuples, int width,
 		  Cost comparison_cost, int sort_mem,
 		  double limit_tuples);
-extern void cost_append(AppendPath *path);
+extern void cost_append(PlannerInfo *root, AppendPath *path);
 extern void cost_merge_append(Path *path, PlannerInfo *root,
 				  List *pathkeys, int n_streams,
 				  Cost input_startup_cost, Cost input_total_cost,
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 574bb85b50..1bcd0e4235 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -64,7 +64,7 @@ extern BitmapOrPath *create_bitmap_or_path(PlannerInfo *root,
 extern TidPath *create_tidscan_path(PlannerInfo *root, RelOptInfo *rel,
 					List *tidquals, Relids required_outer);
 extern AppendPath *create_append_path(PlannerInfo *root, RelOptInfo *rel,
-				   List *subpaths, List *partial_subpaths,
+				   List *subpaths, List *partial_subpaths, List *pathkeys,
 				   Relids required_outer,
 				   int parallel_workers, bool parallel_aware,
 				   List *partitioned_rels, double rows);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 36d12bc376..0e858097c8 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -194,6 +194,8 @@ extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
 extern Path *get_cheapest_parallel_safe_total_inner(List *paths);
 extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index,
 					 ScanDirection scandir);
+extern List *build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
+						 ScanDirection scandir, bool *partialkeys);
 extern List *build_expression_pathkey(PlannerInfo *root, Expr *expr,
 						 Relids nullable_relids, Oid opno,
 						 Relids rel, bool create_it);
diff --git a/src/include/partitioning/partprune.h b/src/include/partitioning/partprune.h
index 2f75717ffb..09a9884d7c 100644
--- a/src/include/partitioning/partprune.h
+++ b/src/include/partitioning/partprune.h
@@ -74,6 +74,10 @@ typedef struct PartitionPruneContext
 #define PruneCxtStateIdx(partnatts, step_id, keyno) \
 	((partnatts) * (step_id) + (keyno))
 
+extern bool partkey_is_bool_constant_for_query(struct RelOptInfo *partrel,
+								   int partkeycol);
+extern bool partitions_are_ordered(struct PlannerInfo *root,
+					   struct RelOptInfo *partrel);
 extern PartitionPruneInfo *make_partition_pruneinfo(struct PlannerInfo *root,
 						 struct RelOptInfo *parentrel,
 						 List *subpaths,
diff --git a/src/test/regress/expected/inherit.out b/src/test/regress/expected/inherit.out
index 7518148df0..a94f44a652 100644
--- a/src/test/regress/expected/inherit.out
+++ b/src/test/regress/expected/inherit.out
@@ -2037,7 +2037,237 @@ explain (costs off) select * from mcrparted where a = 20 and c > 20; -- scans mc
          Filter: ((c > 20) AND (a = 20))
 (9 rows)
 
+-- Test code that uses Append nodes in place of MergeAppend when the
+-- partitions guarantee earlier partitions means lower sort order of the
+-- tuples contained within.
+create index mcrparted_a_abs_c_idx on mcrparted (a, abs(b), c);
+-- check MergeAppend is used when a default partition exists
+explain (costs off) select * from mcrparted order by a, abs(b), c;
+                            QUERY PLAN                             
+-------------------------------------------------------------------
+ Merge Append
+   Sort Key: mcrparted0.a, (abs(mcrparted0.b)), mcrparted0.c
+   ->  Index Scan using mcrparted0_a_abs_c_idx on mcrparted0
+   ->  Index Scan using mcrparted1_a_abs_c_idx on mcrparted1
+   ->  Index Scan using mcrparted2_a_abs_c_idx on mcrparted2
+   ->  Index Scan using mcrparted3_a_abs_c_idx on mcrparted3
+   ->  Index Scan using mcrparted4_a_abs_c_idx on mcrparted4
+   ->  Index Scan using mcrparted5_a_abs_c_idx on mcrparted5
+   ->  Index Scan using mcrparted_def_a_abs_c_idx on mcrparted_def
+(9 rows)
+
+drop table mcrparted_def;
+-- check Append is used for RANGE partitioned table with no default and no subpartitions
+explain (costs off) select * from mcrparted order by a, abs(b), c;
+                         QUERY PLAN                          
+-------------------------------------------------------------
+ Append
+   ->  Index Scan using mcrparted0_a_abs_c_idx on mcrparted0
+   ->  Index Scan using mcrparted1_a_abs_c_idx on mcrparted1
+   ->  Index Scan using mcrparted2_a_abs_c_idx on mcrparted2
+   ->  Index Scan using mcrparted3_a_abs_c_idx on mcrparted3
+   ->  Index Scan using mcrparted4_a_abs_c_idx on mcrparted4
+   ->  Index Scan using mcrparted5_a_abs_c_idx on mcrparted5
+(7 rows)
+
+-- check Append is used with subpaths in reverse order with backwards index scans.
+explain (costs off) select * from mcrparted order by a desc, abs(b) desc, c desc;
+                              QUERY PLAN                              
+----------------------------------------------------------------------
+ Append
+   ->  Index Scan Backward using mcrparted5_a_abs_c_idx on mcrparted5
+   ->  Index Scan Backward using mcrparted4_a_abs_c_idx on mcrparted4
+   ->  Index Scan Backward using mcrparted3_a_abs_c_idx on mcrparted3
+   ->  Index Scan Backward using mcrparted2_a_abs_c_idx on mcrparted2
+   ->  Index Scan Backward using mcrparted1_a_abs_c_idx on mcrparted1
+   ->  Index Scan Backward using mcrparted0_a_abs_c_idx on mcrparted0
+(7 rows)
+
+-- check that Append plan is used containing a MergeAppend for sub-partitions
+-- that are unordered.
+drop table mcrparted5;
+create table mcrparted5 partition of mcrparted for values from (20, 20, 20) to (maxvalue, maxvalue, maxvalue) partition by list (a);
+create table mcrparted5a partition of mcrparted5 for values in(20);
+create table mcrparted5_def partition of mcrparted5 default;
+explain (costs off) select * from mcrparted order by a, abs(b), c;
+                                QUERY PLAN                                 
+---------------------------------------------------------------------------
+ Append
+   ->  Index Scan using mcrparted0_a_abs_c_idx on mcrparted0
+   ->  Index Scan using mcrparted1_a_abs_c_idx on mcrparted1
+   ->  Index Scan using mcrparted2_a_abs_c_idx on mcrparted2
+   ->  Index Scan using mcrparted3_a_abs_c_idx on mcrparted3
+   ->  Index Scan using mcrparted4_a_abs_c_idx on mcrparted4
+   ->  Merge Append
+         Sort Key: mcrparted5a.a, (abs(mcrparted5a.b)), mcrparted5a.c
+         ->  Index Scan using mcrparted5a_a_abs_c_idx on mcrparted5a
+         ->  Index Scan using mcrparted5_def_a_abs_c_idx on mcrparted5_def
+(10 rows)
+
+drop table mcrparted5_def;
+-- check that an Append plan is used and the sub-partitions are flattened
+-- into the main Append when the sub-partition is unordered but contains
+-- just a single sub-partition.
+explain (costs off) select a, abs(b) from mcrparted order by a, abs(b), c;
+                          QUERY PLAN                           
+---------------------------------------------------------------
+ Append
+   ->  Index Scan using mcrparted0_a_abs_c_idx on mcrparted0
+   ->  Index Scan using mcrparted1_a_abs_c_idx on mcrparted1
+   ->  Index Scan using mcrparted2_a_abs_c_idx on mcrparted2
+   ->  Index Scan using mcrparted3_a_abs_c_idx on mcrparted3
+   ->  Index Scan using mcrparted4_a_abs_c_idx on mcrparted4
+   ->  Index Scan using mcrparted5a_a_abs_c_idx on mcrparted5a
+(7 rows)
+
+-- check that Append is used when the sub-partitioned tables are pruned during planning.
+explain (costs off) select * from mcrparted where a < 20 order by a, abs(b), c;
+                         QUERY PLAN                          
+-------------------------------------------------------------
+ Append
+   ->  Index Scan using mcrparted0_a_abs_c_idx on mcrparted0
+         Index Cond: (a < 20)
+   ->  Index Scan using mcrparted1_a_abs_c_idx on mcrparted1
+         Index Cond: (a < 20)
+   ->  Index Scan using mcrparted2_a_abs_c_idx on mcrparted2
+         Index Cond: (a < 20)
+   ->  Index Scan using mcrparted3_a_abs_c_idx on mcrparted3
+         Index Cond: (a < 20)
+(9 rows)
+
+create table mclparted (a int) partition by list(a);
+create table mclparted1 partition of mclparted for values in(1);
+create table mclparted2 partition of mclparted for values in(2);
+create index on mclparted (a);
+-- Ensure an Append is used to for a list partition with an order by.
+explain (costs off) select * from mclparted order by a;
+                         QUERY PLAN                         
+------------------------------------------------------------
+ Append
+   ->  Index Only Scan using mclparted1_a_idx on mclparted1
+   ->  Index Only Scan using mclparted2_a_idx on mclparted2
+(3 rows)
+
+-- Ensure a MergeAppend is used when a partition exists with interleaved
+-- datums in the partition bound.
+create table mclparted3_5 partition of mclparted for values in(3,5);
+create table mclparted4 partition of mclparted for values in(4);
+explain (costs off) select * from mclparted order by a;
+                           QUERY PLAN                           
+----------------------------------------------------------------
+ Merge Append
+   Sort Key: mclparted1.a
+   ->  Index Only Scan using mclparted1_a_idx on mclparted1
+   ->  Index Only Scan using mclparted2_a_idx on mclparted2
+   ->  Index Only Scan using mclparted3_5_a_idx on mclparted3_5
+   ->  Index Only Scan using mclparted4_a_idx on mclparted4
+(6 rows)
+
+drop table mclparted;
+-- Ensure subplans which don't have a path with the correct pathkeys get
+-- sorted correctly.
+drop index mcrparted_a_abs_c_idx;
+create index on mcrparted1 (a, abs(b), c);
+create index on mcrparted2 (a, abs(b), c);
+create index on mcrparted3 (a, abs(b), c);
+create index on mcrparted4 (a, abs(b), c);
+explain (costs off) select * from mcrparted where a < 20 order by a, abs(b), c limit 1;
+                               QUERY PLAN                                
+-------------------------------------------------------------------------
+ Limit
+   ->  Append
+         ->  Sort
+               Sort Key: mcrparted0.a, (abs(mcrparted0.b)), mcrparted0.c
+               ->  Seq Scan on mcrparted0
+                     Filter: (a < 20)
+         ->  Index Scan using mcrparted1_a_abs_c_idx on mcrparted1
+               Index Cond: (a < 20)
+         ->  Index Scan using mcrparted2_a_abs_c_idx on mcrparted2
+               Index Cond: (a < 20)
+         ->  Index Scan using mcrparted3_a_abs_c_idx on mcrparted3
+               Index Cond: (a < 20)
+(12 rows)
+
+set enable_bitmapscan = 0;
+-- Ensure Append node can be used when the partition is ordered by some
+-- pathkeys which were deemed redundant.
+explain (costs off) select * from mcrparted where a = 10 order by a, abs(b), c;
+                         QUERY PLAN                          
+-------------------------------------------------------------
+ Append
+   ->  Index Scan using mcrparted1_a_abs_c_idx on mcrparted1
+         Index Cond: (a = 10)
+   ->  Index Scan using mcrparted2_a_abs_c_idx on mcrparted2
+         Index Cond: (a = 10)
+(5 rows)
+
+reset enable_bitmapscan;
 drop table mcrparted;
+-- Ensure LIST partitions allow an Append to be used instead of a MergeAppend
+create table bool_lp (b bool) partition by list(b);
+create table bool_lp_true partition of bool_lp for values in(true);
+create table bool_lp_false partition of bool_lp for values in(false);
+create index on bool_lp (b);
+explain (costs off) select * from bool_lp order by b;
+                            QUERY PLAN                            
+------------------------------------------------------------------
+ Append
+   ->  Index Only Scan using bool_lp_false_b_idx on bool_lp_false
+   ->  Index Only Scan using bool_lp_true_b_idx on bool_lp_true
+(3 rows)
+
+drop table bool_lp;
+-- Ensure const bool quals can be properly detected as redundant
+create table bool_rp (b bool, a int) partition by range(b,a);
+create table bool_rp_false_1k partition of bool_rp for values from (false,0) to (false,1000);
+create table bool_rp_true_1k partition of bool_rp for values from (true,0) to (true,1000);
+create table bool_rp_false_2k partition of bool_rp for values from (false,1000) to (false,2000);
+create table bool_rp_true_2k partition of bool_rp for values from (true,1000) to (true,2000);
+create index on bool_rp (b,a);
+explain (costs off) select * from bool_rp where b = true order by b,a;
+                               QUERY PLAN                               
+------------------------------------------------------------------------
+ Append
+   ->  Index Only Scan using bool_rp_true_1k_b_a_idx on bool_rp_true_1k
+         Index Cond: (b = true)
+   ->  Index Only Scan using bool_rp_true_2k_b_a_idx on bool_rp_true_2k
+         Index Cond: (b = true)
+(5 rows)
+
+explain (costs off) select * from bool_rp where b = false order by b,a;
+                                QUERY PLAN                                
+--------------------------------------------------------------------------
+ Append
+   ->  Index Only Scan using bool_rp_false_1k_b_a_idx on bool_rp_false_1k
+         Index Cond: (b = false)
+   ->  Index Only Scan using bool_rp_false_2k_b_a_idx on bool_rp_false_2k
+         Index Cond: (b = false)
+(5 rows)
+
+drop table bool_rp;
+-- Ensure an Append scan is chosen when the partition order is a subset of
+-- the required order.
+create table range_parted (a int, b int, c int) partition by range(a, b);
+create table range_parted1 partition of range_parted for values from (0,0) to (10,10);
+create table range_parted2 partition of range_parted for values from (10,10) to (20,20);
+create index on range_parted (a,b,c);
+explain (costs off) select * from range_parted order by a,b,c;
+                              QUERY PLAN                              
+----------------------------------------------------------------------
+ Append
+   ->  Index Only Scan using range_parted1_a_b_c_idx on range_parted1
+   ->  Index Only Scan using range_parted2_a_b_c_idx on range_parted2
+(3 rows)
+
+explain (costs off) select * from range_parted order by a desc,b desc,c desc;
+                                  QUERY PLAN                                   
+-------------------------------------------------------------------------------
+ Append
+   ->  Index Only Scan Backward using range_parted2_a_b_c_idx on range_parted2
+   ->  Index Only Scan Backward using range_parted1_a_b_c_idx on range_parted1
+(3 rows)
+
+drop table range_parted;
 -- check that partitioned table Appends cope with being referenced in
 -- subplans
 create table parted_minmax (a int, b varchar(16)) partition by range (a);
diff --git a/src/test/regress/expected/partition_prune.out b/src/test/regress/expected/partition_prune.out
index 50ca03b9e3..837a57e817 100644
--- a/src/test/regress/expected/partition_prune.out
+++ b/src/test/regress/expected/partition_prune.out
@@ -3024,14 +3024,14 @@ drop table boolp;
 --
 set enable_seqscan = off;
 set enable_sort = off;
-create table ma_test (a int) partition by range (a);
+create table ma_test (a int, b int) partition by range (a);
 create table ma_test_p1 partition of ma_test for values from (0) to (10);
 create table ma_test_p2 partition of ma_test for values from (10) to (20);
 create table ma_test_p3 partition of ma_test for values from (20) to (30);
-insert into ma_test select x from generate_series(0,29) t(x);
-create index on ma_test (a);
+insert into ma_test select x,x from generate_series(0,29) t(x);
+create index on ma_test (b);
 analyze ma_test;
-prepare mt_q1 (int) as select * from ma_test where a >= $1 and a % 10 = 5 order by a;
+prepare mt_q1 (int) as select a from ma_test where a >= $1 and a % 10 = 5 order by b;
 -- Execute query 5 times to allow choose_custom_plan
 -- to start considering a generic plan.
 execute mt_q1(0);
@@ -3078,17 +3078,15 @@ explain (analyze, costs off, summary off, timing off) execute mt_q1(15);
                                   QUERY PLAN                                   
 -------------------------------------------------------------------------------
  Merge Append (actual rows=2 loops=1)
-   Sort Key: ma_test_p2.a
+   Sort Key: ma_test_p2.b
    Subplans Removed: 1
-   ->  Index Scan using ma_test_p2_a_idx on ma_test_p2 (actual rows=1 loops=1)
-         Index Cond: (a >= $1)
-         Filter: ((a % 10) = 5)
-         Rows Removed by Filter: 4
-   ->  Index Scan using ma_test_p3_a_idx on ma_test_p3 (actual rows=1 loops=1)
-         Index Cond: (a >= $1)
-         Filter: ((a % 10) = 5)
+   ->  Index Scan using ma_test_p2_b_idx on ma_test_p2 (actual rows=1 loops=1)
+         Filter: ((a >= $1) AND ((a % 10) = 5))
          Rows Removed by Filter: 9
-(11 rows)
+   ->  Index Scan using ma_test_p3_b_idx on ma_test_p3 (actual rows=1 loops=1)
+         Filter: ((a >= $1) AND ((a % 10) = 5))
+         Rows Removed by Filter: 9
+(9 rows)
 
 execute mt_q1(15);
  a  
@@ -3101,13 +3099,12 @@ explain (analyze, costs off, summary off, timing off) execute mt_q1(25);
                                   QUERY PLAN                                   
 -------------------------------------------------------------------------------
  Merge Append (actual rows=1 loops=1)
-   Sort Key: ma_test_p3.a
+   Sort Key: ma_test_p3.b
    Subplans Removed: 2
-   ->  Index Scan using ma_test_p3_a_idx on ma_test_p3 (actual rows=1 loops=1)
-         Index Cond: (a >= $1)
-         Filter: ((a % 10) = 5)
-         Rows Removed by Filter: 4
-(7 rows)
+   ->  Index Scan using ma_test_p3_b_idx on ma_test_p3 (actual rows=1 loops=1)
+         Filter: ((a >= $1) AND ((a % 10) = 5))
+         Rows Removed by Filter: 9
+(6 rows)
 
 execute mt_q1(25);
  a  
@@ -3120,12 +3117,11 @@ explain (analyze, costs off, summary off, timing off) execute mt_q1(35);
                                QUERY PLAN                               
 ------------------------------------------------------------------------
  Merge Append (actual rows=0 loops=1)
-   Sort Key: ma_test_p1.a
+   Sort Key: ma_test_p1.b
    Subplans Removed: 2
-   ->  Index Scan using ma_test_p1_a_idx on ma_test_p1 (never executed)
-         Index Cond: (a >= $1)
-         Filter: ((a % 10) = 5)
-(6 rows)
+   ->  Index Scan using ma_test_p1_b_idx on ma_test_p1 (never executed)
+         Filter: ((a >= $1) AND ((a % 10) = 5))
+(5 rows)
 
 execute mt_q1(35);
  a 
@@ -3134,23 +3130,23 @@ execute mt_q1(35);
 
 deallocate mt_q1;
 -- ensure initplan params properly prune partitions
-explain (analyze, costs off, summary off, timing off) select * from ma_test where a >= (select min(a) from ma_test_p2) order by a;
+explain (analyze, costs off, summary off, timing off) select * from ma_test where a >= (select min(b) from ma_test_p2) order by b;
                                                  QUERY PLAN                                                 
 ------------------------------------------------------------------------------------------------------------
  Merge Append (actual rows=20 loops=1)
-   Sort Key: ma_test_p1.a
+   Sort Key: ma_test_p1.b
    InitPlan 2 (returns $1)
      ->  Result (actual rows=1 loops=1)
            InitPlan 1 (returns $0)
              ->  Limit (actual rows=1 loops=1)
-                   ->  Index Scan using ma_test_p2_a_idx on ma_test_p2 ma_test_p2_1 (actual rows=1 loops=1)
-                         Index Cond: (a IS NOT NULL)
-   ->  Index Scan using ma_test_p1_a_idx on ma_test_p1 (never executed)
-         Index Cond: (a >= $1)
-   ->  Index Scan using ma_test_p2_a_idx on ma_test_p2 (actual rows=10 loops=1)
-         Index Cond: (a >= $1)
-   ->  Index Scan using ma_test_p3_a_idx on ma_test_p3 (actual rows=10 loops=1)
-         Index Cond: (a >= $1)
+                   ->  Index Scan using ma_test_p2_b_idx on ma_test_p2 ma_test_p2_1 (actual rows=1 loops=1)
+                         Index Cond: (b IS NOT NULL)
+   ->  Index Scan using ma_test_p1_b_idx on ma_test_p1 (never executed)
+         Filter: (a >= $1)
+   ->  Index Scan using ma_test_p2_b_idx on ma_test_p2 (actual rows=10 loops=1)
+         Filter: (a >= $1)
+   ->  Index Scan using ma_test_p3_b_idx on ma_test_p3 (actual rows=10 loops=1)
+         Filter: (a >= $1)
 (14 rows)
 
 reset enable_seqscan;
diff --git a/src/test/regress/sql/inherit.sql b/src/test/regress/sql/inherit.sql
index 5480fe7db4..89a0f8c229 100644
--- a/src/test/regress/sql/inherit.sql
+++ b/src/test/regress/sql/inherit.sql
@@ -715,8 +715,111 @@ explain (costs off) select * from mcrparted where abs(b) = 5;	-- scans all parti
 explain (costs off) select * from mcrparted where a > -1;	-- scans all partitions
 explain (costs off) select * from mcrparted where a = 20 and abs(b) = 10 and c > 10;	-- scans mcrparted4
 explain (costs off) select * from mcrparted where a = 20 and c > 20; -- scans mcrparted3, mcrparte4, mcrparte5, mcrparted_def
+
+-- Test code that uses Append nodes in place of MergeAppend when the
+-- partitions guarantee earlier partitions means lower sort order of the
+-- tuples contained within.
+create index mcrparted_a_abs_c_idx on mcrparted (a, abs(b), c);
+
+-- check MergeAppend is used when a default partition exists
+explain (costs off) select * from mcrparted order by a, abs(b), c;
+
+drop table mcrparted_def;
+
+-- check Append is used for RANGE partitioned table with no default and no subpartitions
+explain (costs off) select * from mcrparted order by a, abs(b), c;
+
+-- check Append is used with subpaths in reverse order with backwards index scans.
+explain (costs off) select * from mcrparted order by a desc, abs(b) desc, c desc;
+
+-- check that Append plan is used containing a MergeAppend for sub-partitions
+-- that are unordered.
+drop table mcrparted5;
+create table mcrparted5 partition of mcrparted for values from (20, 20, 20) to (maxvalue, maxvalue, maxvalue) partition by list (a);
+create table mcrparted5a partition of mcrparted5 for values in(20);
+create table mcrparted5_def partition of mcrparted5 default;
+
+explain (costs off) select * from mcrparted order by a, abs(b), c;
+
+drop table mcrparted5_def;
+
+-- check that an Append plan is used and the sub-partitions are flattened
+-- into the main Append when the sub-partition is unordered but contains
+-- just a single sub-partition.
+explain (costs off) select a, abs(b) from mcrparted order by a, abs(b), c;
+
+-- check that Append is used when the sub-partitioned tables are pruned during planning.
+explain (costs off) select * from mcrparted where a < 20 order by a, abs(b), c;
+
+create table mclparted (a int) partition by list(a);
+create table mclparted1 partition of mclparted for values in(1);
+create table mclparted2 partition of mclparted for values in(2);
+create index on mclparted (a);
+
+-- Ensure an Append is used to for a list partition with an order by.
+explain (costs off) select * from mclparted order by a;
+
+-- Ensure a MergeAppend is used when a partition exists with interleaved
+-- datums in the partition bound.
+create table mclparted3_5 partition of mclparted for values in(3,5);
+create table mclparted4 partition of mclparted for values in(4);
+
+explain (costs off) select * from mclparted order by a;
+
+drop table mclparted;
+
+-- Ensure subplans which don't have a path with the correct pathkeys get
+-- sorted correctly.
+drop index mcrparted_a_abs_c_idx;
+create index on mcrparted1 (a, abs(b), c);
+create index on mcrparted2 (a, abs(b), c);
+create index on mcrparted3 (a, abs(b), c);
+create index on mcrparted4 (a, abs(b), c);
+
+explain (costs off) select * from mcrparted where a < 20 order by a, abs(b), c limit 1;
+
+set enable_bitmapscan = 0;
+-- Ensure Append node can be used when the partition is ordered by some
+-- pathkeys which were deemed redundant.
+explain (costs off) select * from mcrparted where a = 10 order by a, abs(b), c;
+reset enable_bitmapscan;
+
 drop table mcrparted;
 
+-- Ensure LIST partitions allow an Append to be used instead of a MergeAppend
+create table bool_lp (b bool) partition by list(b);
+create table bool_lp_true partition of bool_lp for values in(true);
+create table bool_lp_false partition of bool_lp for values in(false);
+create index on bool_lp (b);
+
+explain (costs off) select * from bool_lp order by b;
+
+drop table bool_lp;
+
+-- Ensure const bool quals can be properly detected as redundant
+create table bool_rp (b bool, a int) partition by range(b,a);
+create table bool_rp_false_1k partition of bool_rp for values from (false,0) to (false,1000);
+create table bool_rp_true_1k partition of bool_rp for values from (true,0) to (true,1000);
+create table bool_rp_false_2k partition of bool_rp for values from (false,1000) to (false,2000);
+create table bool_rp_true_2k partition of bool_rp for values from (true,1000) to (true,2000);
+create index on bool_rp (b,a);
+explain (costs off) select * from bool_rp where b = true order by b,a;
+explain (costs off) select * from bool_rp where b = false order by b,a;
+
+drop table bool_rp;
+
+-- Ensure an Append scan is chosen when the partition order is a subset of
+-- the required order.
+create table range_parted (a int, b int, c int) partition by range(a, b);
+create table range_parted1 partition of range_parted for values from (0,0) to (10,10);
+create table range_parted2 partition of range_parted for values from (10,10) to (20,20);
+create index on range_parted (a,b,c);
+
+explain (costs off) select * from range_parted order by a,b,c;
+explain (costs off) select * from range_parted order by a desc,b desc,c desc;
+
+drop table range_parted;
+
 -- check that partitioned table Appends cope with being referenced in
 -- subplans
 create table parted_minmax (a int, b varchar(16)) partition by range (a);
diff --git a/src/test/regress/sql/partition_prune.sql b/src/test/regress/sql/partition_prune.sql
index a5514c7506..227dab630d 100644
--- a/src/test/regress/sql/partition_prune.sql
+++ b/src/test/regress/sql/partition_prune.sql
@@ -768,15 +768,15 @@ drop table boolp;
 --
 set enable_seqscan = off;
 set enable_sort = off;
-create table ma_test (a int) partition by range (a);
+create table ma_test (a int, b int) partition by range (a);
 create table ma_test_p1 partition of ma_test for values from (0) to (10);
 create table ma_test_p2 partition of ma_test for values from (10) to (20);
 create table ma_test_p3 partition of ma_test for values from (20) to (30);
-insert into ma_test select x from generate_series(0,29) t(x);
-create index on ma_test (a);
+insert into ma_test select x,x from generate_series(0,29) t(x);
+create index on ma_test (b);
 
 analyze ma_test;
-prepare mt_q1 (int) as select * from ma_test where a >= $1 and a % 10 = 5 order by a;
+prepare mt_q1 (int) as select a from ma_test where a >= $1 and a % 10 = 5 order by b;
 
 -- Execute query 5 times to allow choose_custom_plan
 -- to start considering a generic plan.
@@ -797,7 +797,7 @@ execute mt_q1(35);
 deallocate mt_q1;
 
 -- ensure initplan params properly prune partitions
-explain (analyze, costs off, summary off, timing off) select * from ma_test where a >= (select min(a) from ma_test_p2) order by a;
+explain (analyze, costs off, summary off, timing off) select * from ma_test where a >= (select min(b) from ma_test_p2) order by b;
 
 reset enable_seqscan;
 reset enable_sort;