[Proposal] Make the optimiser aware of partitions ordering

diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index c1602c59cc..20e63b3204 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -80,6 +80,8 @@ static void show_upper_qual(List *qual, const char *qlabel,
 				ExplainState *es);
 static void show_sort_keys(SortState *sortstate, List *ancestors,
 			   ExplainState *es);
+static void show_append_keys(AppendState *mstate, List *ancestors,
+					   ExplainState *es);
 static void show_merge_append_keys(MergeAppendState *mstate, List *ancestors,
 					   ExplainState *es);
 static void show_agg_keys(AggState *astate, List *ancestors,
@@ -1602,6 +1604,10 @@ ExplainNode(PlanState *planstate, List *ancestors,
 			show_sort_keys(castNode(SortState, planstate), ancestors, es);
 			show_sort_info(castNode(SortState, planstate), es);
 			break;
+		case T_Append:
+			show_append_keys(castNode(AppendState, planstate),
+								   ancestors, es);
+			break;
 		case T_MergeAppend:
 			show_merge_append_keys(castNode(MergeAppendState, planstate),
 								   ancestors, es);
@@ -1744,7 +1750,7 @@ ExplainNode(PlanState *planstate, List *ancestors,
 							   ancestors, es);
 			break;
 		case T_MergeAppend:
-			ExplainMemberNodes(((MergeAppend *) plan)->mergeplans,
+			ExplainMemberNodes(((MergeAppend*) plan)->plan.appendplans,
 							   ((MergeAppendState *) planstate)->mergeplans,
 							   ancestors, es);
 			break;
@@ -1935,6 +1941,22 @@ show_sort_keys(SortState *sortstate, List *ancestors, ExplainState *es)
 						 ancestors, es);
 }
 
+/*
+ * Likewise, for an Append node.
+ */
+static void
+show_append_keys(AppendState *mstate, List *ancestors,
+					   ExplainState *es)
+{
+	Append *plan = (Append *) mstate->ps.plan;
+
+	show_sort_group_keys((PlanState *) mstate, "Sort Key",
+						 plan->numCols, plan->sortColIdx,
+						 plan->sortOperators, plan->collations,
+						 plan->nullsFirst,
+						 ancestors, es);
+}
+
 /*
  * Likewise, for a MergeAppend node.
  */
@@ -1942,7 +1964,7 @@ static void
 show_merge_append_keys(MergeAppendState *mstate, List *ancestors,
 					   ExplainState *es)
 {
-	MergeAppend *plan = (MergeAppend *) mstate->ps.plan;
+	Append *plan = (Append *) mstate->ps.plan;
 
 	show_sort_group_keys((PlanState *) mstate, "Sort Key",
 						 plan->numCols, plan->sortColIdx,
diff --git a/src/backend/executor/nodeMergeAppend.c b/src/backend/executor/nodeMergeAppend.c
index 6bf490bd70..601f2547d3 100644
--- a/src/backend/executor/nodeMergeAppend.c
+++ b/src/backend/executor/nodeMergeAppend.c
@@ -64,6 +64,7 @@ MergeAppendState *
 ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
 {
 	MergeAppendState *mergestate = makeNode(MergeAppendState);
+	Append			 *append = &node->plan;
 	PlanState **mergeplanstates;
 	int			nplans;
 	int			i;
@@ -76,12 +77,12 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
 	 * Lock the non-leaf tables in the partition tree controlled by this node.
 	 * It's a no-op for non-partitioned parent tables.
 	 */
-	ExecLockNonLeafAppendTables(node->partitioned_rels, estate);
+	ExecLockNonLeafAppendTables(append->partitioned_rels, estate);
 
 	/*
 	 * Set up empty vector of subplan states
 	 */
-	nplans = list_length(node->mergeplans);
+	nplans = list_length(append->appendplans);
 
 	mergeplanstates = (PlanState **) palloc0(nplans * sizeof(PlanState *));
 
@@ -116,7 +117,7 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
 	 * results into the array "mergeplans".
 	 */
 	i = 0;
-	foreach(lc, node->mergeplans)
+	foreach(lc, append->appendplans)
 	{
 		Plan	   *initNode = (Plan *) lfirst(lc);
 
@@ -133,17 +134,17 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
 	/*
 	 * initialize sort-key information
 	 */
-	mergestate->ms_nkeys = node->numCols;
-	mergestate->ms_sortkeys = palloc0(sizeof(SortSupportData) * node->numCols);
+	mergestate->ms_nkeys = append->numCols;
+	mergestate->ms_sortkeys = palloc0(sizeof(SortSupportData) * append->numCols);
 
-	for (i = 0; i < node->numCols; i++)
+	for (i = 0; i < append->numCols; i++)
 	{
 		SortSupport sortKey = mergestate->ms_sortkeys + i;
 
 		sortKey->ssup_cxt = CurrentMemoryContext;
-		sortKey->ssup_collation = node->collations[i];
-		sortKey->ssup_nulls_first = node->nullsFirst[i];
-		sortKey->ssup_attno = node->sortColIdx[i];
+		sortKey->ssup_collation = append->collations[i];
+		sortKey->ssup_nulls_first = append->nullsFirst[i];
+		sortKey->ssup_attno = append->sortColIdx[i];
 
 		/*
 		 * It isn't feasible to perform abbreviated key conversion, since
@@ -154,7 +155,7 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
 		 */
 		sortKey->abbreviate = false;
 
-		PrepareSortSupportFromOrderingOp(node->sortOperators[i], sortKey);
+		PrepareSortSupportFromOrderingOp(append->sortOperators[i], sortKey);
 	}
 
 	/*
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index f1bed14e2b..23dd6043be 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -224,6 +224,19 @@ _copyModifyTable(const ModifyTable *from)
 	return newnode;
 }
 
+static void
+copyAppendFields(const Append *from, Append *newnode)
+{
+	CopyPlanFields((const Plan *) from, (Plan *) newnode);
+	COPY_NODE_FIELD(partitioned_rels);
+	COPY_NODE_FIELD(appendplans);
+	COPY_SCALAR_FIELD(numCols);
+	COPY_POINTER_FIELD(sortColIdx, from->numCols * sizeof(AttrNumber));
+	COPY_POINTER_FIELD(sortOperators, from->numCols * sizeof(Oid));
+	COPY_POINTER_FIELD(collations, from->numCols * sizeof(Oid));
+	COPY_POINTER_FIELD(nullsFirst, from->numCols * sizeof(bool));
+}
+
 /*
  * _copyAppend
  */
@@ -232,16 +245,7 @@ _copyAppend(const Append *from)
 {
 	Append	   *newnode = makeNode(Append);
 
-	/*
-	 * copy node superclass fields
-	 */
-	CopyPlanFields((const Plan *) from, (Plan *) newnode);
-
-	/*
-	 * copy remainder of node
-	 */
-	COPY_NODE_FIELD(partitioned_rels);
-	COPY_NODE_FIELD(appendplans);
+	copyAppendFields(from, newnode);
 
 	return newnode;
 }
@@ -254,21 +258,7 @@ _copyMergeAppend(const MergeAppend *from)
 {
 	MergeAppend *newnode = makeNode(MergeAppend);
 
-	/*
-	 * copy node superclass fields
-	 */
-	CopyPlanFields((const Plan *) from, (Plan *) newnode);
-
-	/*
-	 * copy remainder of node
-	 */
-	COPY_NODE_FIELD(partitioned_rels);
-	COPY_NODE_FIELD(mergeplans);
-	COPY_SCALAR_FIELD(numCols);
-	COPY_POINTER_FIELD(sortColIdx, from->numCols * sizeof(AttrNumber));
-	COPY_POINTER_FIELD(sortOperators, from->numCols * sizeof(Oid));
-	COPY_POINTER_FIELD(collations, from->numCols * sizeof(Oid));
-	COPY_POINTER_FIELD(nullsFirst, from->numCols * sizeof(bool));
+	copyAppendFields((const Append *)from, (Append *)newnode);
 
 	return newnode;
 }
diff --git a/src/backend/nodes/nodeFuncs.c b/src/backend/nodes/nodeFuncs.c
index e3eb0c5788..ccbf11d72e 100644
--- a/src/backend/nodes/nodeFuncs.c
+++ b/src/backend/nodes/nodeFuncs.c
@@ -3735,7 +3735,7 @@ planstate_tree_walker(PlanState *planstate,
 				return true;
 			break;
 		case T_MergeAppend:
-			if (planstate_walk_members(((MergeAppend *) plan)->mergeplans,
+			if (planstate_walk_members(((MergeAppend *) plan)->plan.appendplans,
 									   ((MergeAppendState *) planstate)->mergeplans,
 									   walker, context))
 				return true;
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index b83d919e40..47f276d9f5 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -386,27 +386,14 @@ _outModifyTable(StringInfo str, const ModifyTable *node)
 }
 
 static void
-_outAppend(StringInfo str, const Append *node)
+_outAppendInfo(StringInfo str, const Append *node)
 {
-	WRITE_NODE_TYPE("APPEND");
+	int i;
 
 	_outPlanInfo(str, (const Plan *) node);
 
 	WRITE_NODE_FIELD(partitioned_rels);
 	WRITE_NODE_FIELD(appendplans);
-}
-
-static void
-_outMergeAppend(StringInfo str, const MergeAppend *node)
-{
-	int			i;
-
-	WRITE_NODE_TYPE("MERGEAPPEND");
-
-	_outPlanInfo(str, (const Plan *) node);
-
-	WRITE_NODE_FIELD(partitioned_rels);
-	WRITE_NODE_FIELD(mergeplans);
 
 	WRITE_INT_FIELD(numCols);
 
@@ -427,6 +414,20 @@ _outMergeAppend(StringInfo str, const MergeAppend *node)
 		appendStringInfo(str, " %s", booltostr(node->nullsFirst[i]));
 }
 
+static void
+_outAppend(StringInfo str, const Append *node)
+{
+	WRITE_NODE_TYPE("APPEND");
+	_outAppendInfo(str, node);
+}
+
+static void
+_outMergeAppend(StringInfo str, const MergeAppend *node)
+{
+	WRITE_NODE_TYPE("MERGEAPPEND");
+	_outAppendInfo(str, (const Append *) &node->plan);
+}
+
 static void
 _outRecursiveUnion(StringInfo str, const RecursiveUnion *node)
 {
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
index fbf8330735..270b60041c 100644
--- a/src/backend/nodes/readfuncs.c
+++ b/src/backend/nodes/readfuncs.c
@@ -1582,18 +1582,31 @@ _readModifyTable(void)
 	READ_DONE();
 }
 
+static void
+ReadCommonAppend(Append* local_node)
+{
+	READ_TEMP_LOCALS();
+
+	ReadCommonPlan(&local_node->plan);
+
+	READ_NODE_FIELD(partitioned_rels);
+	READ_NODE_FIELD(appendplans);
+	READ_INT_FIELD(numCols);
+	READ_ATTRNUMBER_ARRAY(sortColIdx, local_node->numCols);
+	READ_OID_ARRAY(sortOperators, local_node->numCols);
+	READ_OID_ARRAY(collations, local_node->numCols);
+	READ_BOOL_ARRAY(nullsFirst, local_node->numCols);
+}
+
 /*
  * _readAppend
  */
 static Append *
 _readAppend(void)
 {
-	READ_LOCALS(Append);
+	READ_LOCALS_NO_FIELDS(Append);
 
-	ReadCommonPlan(&local_node->plan);
-
-	READ_NODE_FIELD(partitioned_rels);
-	READ_NODE_FIELD(appendplans);
+	ReadCommonAppend(local_node);
 
 	READ_DONE();
 }
@@ -1604,17 +1617,9 @@ _readAppend(void)
 static MergeAppend *
 _readMergeAppend(void)
 {
-	READ_LOCALS(MergeAppend);
-
-	ReadCommonPlan(&local_node->plan);
+	READ_LOCALS_NO_FIELDS(MergeAppend);
 
-	READ_NODE_FIELD(partitioned_rels);
-	READ_NODE_FIELD(mergeplans);
-	READ_INT_FIELD(numCols);
-	READ_ATTRNUMBER_ARRAY(sortColIdx, local_node->numCols);
-	READ_OID_ARRAY(sortOperators, local_node->numCols);
-	READ_OID_ARRAY(collations, local_node->numCols);
-	READ_BOOL_ARRAY(nullsFirst, local_node->numCols);
+	ReadCommonAppend(&local_node->plan);
 
 	READ_DONE();
 }
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index a7866a99e0..f62fc5488a 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -94,6 +94,10 @@ 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 int indexof_path_relation_in_oid_list(Oid oid, Oid* sorted_oids,
+			int array_size);
+static void generate_sorted_append_paths(PlannerInfo *root,
+			RelOptInfo *parent_rel, RelOptInfo **ordered_childs);
 static void generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
 						   List *live_childrels,
 						   List *all_child_pathkeys,
@@ -134,7 +138,7 @@ static void recurse_push_qual(Node *setOp, Query *topquery,
 				  RangeTblEntry *rte, Index rti, Node *qual);
 static void remove_unused_subquery_outputs(Query *subquery, RelOptInfo *rel);
 static void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
-						List *live_childrels);
+						List *live_childrels, RelOptInfo **ordered_partition_rels);
 
 
 /*
@@ -1215,12 +1219,27 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 	int			parentRTindex = rti;
 	List	   *live_childrels = NIL;
 	ListCell   *l;
+	bool is_partitioned = rel->rel_sorted_part_oids != NIL;
+	int		    num_parts = list_length(rel->rel_sorted_part_oids);
+	RelOptInfo	**ordered_partition_rels = palloc0(sizeof(RelOptInfo*) * num_parts);
+	Oid		    *parts_oids = palloc0(sizeof(Oid) * num_parts);
+
+	if (is_partitioned)
+	{
+		ListCell *lc;
+		int i = 0;
+		foreach (lc, rel->rel_sorted_part_oids)
+		{
+			parts_oids[i] = lfirst_oid(lc);
+			i++;
+		}
+	}
 
 	/*
 	 * Generate access paths for each member relation, and remember the
 	 * non-dummy children.
 	 */
-	foreach(l, root->append_rel_list)
+	foreach (l, root->append_rel_list)
 	{
 		AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
 		int			childRTindex;
@@ -1260,10 +1279,21 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 		 * Child is live, so add it to the live_childrels list for use below.
 		 */
 		live_childrels = lappend(live_childrels, childrel);
+
+		if (is_partitioned) {
+				int partindex =
+					indexof_path_relation_in_oid_list(childRTE->relid,
+							parts_oids, num_parts);
+
+				ordered_partition_rels[partindex] = childrel;
+		}
 	}
 
 	/* Add paths to the "append" relation. */
-	add_paths_to_append_rel(root, rel, live_childrels);
+	add_paths_to_append_rel(root, rel, live_childrels, ordered_partition_rels);
+
+	pfree(parts_oids);
+	pfree(ordered_partition_rels);
 }
 
 
@@ -1280,7 +1310,8 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
  */
 static void
 add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
-						List *live_childrels)
+						List *live_childrels,
+						RelOptInfo **ordered_partition_rels)
 {
 	List	   *subpaths = NIL;
 	bool		subpaths_valid = true;
@@ -1292,6 +1323,7 @@ add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 	List	   *partitioned_rels = NIL;
 	RangeTblEntry *rte;
 	bool		build_partitioned_rels = false;
+	bool is_partitioned = rel->rel_sorted_part_oids != NIL;
 
 	/*
 	 * A root partition will already have a PartitionedChildRelInfo, and a
@@ -1431,8 +1463,15 @@ add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 	 * if we have zero or one live subpath due to constraint exclusion.)
 	 */
 	if (subpaths_valid)
-		add_path(rel, (Path *) create_append_path(rel, subpaths, NULL, 0,
-												  partitioned_rels));
+		add_path(rel, (Path *) create_append_path(root, rel, subpaths, NULL, 0,
+												  partitioned_rels, NIL));
+
+	/*
+	 * If possible, build ordered append path matching the PathKeys derived
+	 * from the partition key
+	 */
+	if (is_partitioned)
+		generate_sorted_append_paths(root, rel, ordered_partition_rels);
 
 	/*
 	 * Consider an append of partial unordered, unparameterized partial paths.
@@ -1458,8 +1497,8 @@ add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 		Assert(parallel_workers > 0);
 
 		/* Generate a partial append path. */
-		appendpath = create_append_path(rel, partial_subpaths, NULL,
-										parallel_workers, partitioned_rels);
+		appendpath = create_append_path(root, rel, partial_subpaths, NULL,
+										parallel_workers, partitioned_rels, NIL);
 		add_partial_path(rel, (Path *) appendpath);
 	}
 
@@ -1512,8 +1551,127 @@ add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 
 		if (subpaths_valid)
 			add_path(rel, (Path *)
-					 create_append_path(rel, subpaths, required_outer, 0,
-										partitioned_rels));
+					 create_append_path(root, rel, subpaths, required_outer, 0,
+										partitioned_rels, NIL));
+	}
+}
+
+static int
+indexof_path_relation_in_oid_list(Oid oid, Oid* sorted_oids, int array_size)
+{
+	int i;
+
+	for(i=0; i < array_size; i++)
+	{
+		if(sorted_oids[i] == oid)
+			return i;
+	}
+
+	return -1;
+}
+
+
+static void
+generate_sorted_append_paths(PlannerInfo *root, RelOptInfo *parent_rel, RelOptInfo **ordered_childs)
+{
+	ListCell *lc;
+	int i;
+	List *partitions_asc = NIL;
+	List *partitions_desc = NIL;
+	RangeTblEntry * parent_rte = planner_rt_fetch(parent_rel->relid, root);
+
+	for (i = 0; i < list_length(parent_rel->rel_sorted_part_oids); i++)
+	{
+		partitions_asc = lappend(partitions_asc, ordered_childs[i]);
+		partitions_desc = lcons(ordered_childs[i], partitions_desc);
+	}
+
+	if (parent_rte->relkind != RELKIND_PARTITIONED_TABLE)
+		return;
+
+	foreach(lc, parent_rel->rel_partitioned_pathkeys)
+	{
+		List *pathkeys = (List *) lfirst(lc);
+		PathKey *first = (PathKey *) linitial(pathkeys);
+		List *ordered_partitions = first->pk_strategy == BTLessStrategyNumber ?
+			partitions_asc : partitions_desc;
+		List *startup_subpaths = NIL;
+		List *total_subpaths = NIL;
+		List *sequential_subpaths = NIL;
+		bool startup_neq_total = false;
+		ListCell *lc2;
+
+		if (compare_pathkeys(pathkeys, root->query_pathkeys) == PATHKEYS_DIFFERENT)
+			continue;
+
+		foreach (lc2, ordered_partitions)
+		{
+			RelOptInfo *childrel = lfirst(lc2);
+			Path *cheapest_startup,
+				 *cheapest_total,
+				 *sequential = NULL;
+
+			/* The partition may have been pruned */
+			if (!childrel)
+				continue;
+
+			//Assert(pathkeys_contained_in(pathkeys, root->query_pathkeys));
+
+			cheapest_startup = get_cheapest_path_for_pathkeys(childrel->pathlist,
+					root->query_pathkeys,
+					NULL,
+					STARTUP_COST,
+					false);
+			cheapest_total = get_cheapest_path_for_pathkeys(childrel->pathlist,
+					root->query_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);
+			}
+			/*
+			 * Force a an unordered path, which could be cheaper in corner cases where
+			 * orderedpaths are too expensive.
+			 */
+			sequential = childrel->cheapest_total_path;
+
+			/*
+			 * Notice whether we actually have different paths for the
+			 * "cheapest" and "total" cases; frequently there will be no point
+			 * in two create_merge_append_path() calls.
+			 */
+			if (cheapest_startup != cheapest_total)
+				startup_neq_total = true;
+			startup_subpaths =
+				lappend(startup_subpaths, cheapest_startup);
+			total_subpaths =
+				lappend(total_subpaths, cheapest_total);
+			sequential_subpaths =
+				lappend(sequential_subpaths, sequential);
+
+		}
+		if (startup_subpaths)
+		{
+			add_path(parent_rel, (Path *) create_append_path(root, parent_rel, startup_subpaths,
+						NULL, 0, NIL, root->query_pathkeys));
+		}
+		if (startup_neq_total)
+			add_path(parent_rel, (Path *) create_append_path(root,
+					parent_rel, total_subpaths, NULL, 0, NIL, root->query_pathkeys));
+		if (sequential_subpaths){
+			add_path(parent_rel, (Path *) create_append_path(root,
+					parent_rel, sequential_subpaths, NULL, 0, NIL, root->query_pathkeys));
+		}
 	}
 }
 
@@ -1749,7 +1907,7 @@ set_dummy_rel_pathlist(RelOptInfo *rel)
 	rel->pathlist = NIL;
 	rel->partial_pathlist = NIL;
 
-	add_path(rel, (Path *) create_append_path(rel, NIL, NULL, 0, NIL));
+	add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NULL, 0, NIL, NIL));
 
 	/*
 	 * We set the cheapest path immediately, to ensure that IS_DUMMY_REL()
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 6ee23509c5..9b201ecdda 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -1217,7 +1217,7 @@ mark_dummy_rel(RelOptInfo *rel)
 	rel->partial_pathlist = NIL;
 
 	/* Set up the dummy path */
-	add_path(rel, (Path *) create_append_path(rel, NIL, NULL, 0, NIL));
+	add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NULL, 0, NIL, NIL));
 
 	/* Set or update cheapest_total_path and related fields */
 	set_cheapest(rel);
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 28216629aa..e063128251 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -78,8 +78,8 @@ static List *get_gating_quals(PlannerInfo *root, List *quals);
 static Plan *create_gating_plan(PlannerInfo *root, Path *path, Plan *plan,
 				   List *gating_quals);
 static Plan *create_join_plan(PlannerInfo *root, JoinPath *best_path);
-static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path);
-static Plan *create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path);
+static Plan *create_append_plan(NodeTag node_type, PlannerInfo *root, AppendPath *best_path);
+static Plan *wrap_sort(PlannerInfo *root, Append* parentplan, Path *subpath, List* pathkeys, double limit_tuples);
 static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path);
 static ProjectSet *create_project_set_plan(PlannerInfo *root, ProjectSetPath *best_path);
 static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path,
@@ -203,7 +203,7 @@ 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, List *tlist, List *partitioned_rels);
+static Append *make_append(NodeTag node_type, List *tlist, List *partitioned_rels);
 static RecursiveUnion *make_recursive_union(List *tlist,
 					 Plan *lefttree,
 					 Plan *righttree,
@@ -381,12 +381,9 @@ create_plan_recurse(PlannerInfo *root, Path *best_path, int flags)
 									(JoinPath *) best_path);
 			break;
 		case T_Append:
-			plan = create_append_plan(root,
-									  (AppendPath *) best_path);
-			break;
 		case T_MergeAppend:
-			plan = create_merge_append_plan(root,
-											(MergeAppendPath *) best_path);
+			plan = create_append_plan(best_path->pathtype, root,
+									  (AppendPath *) best_path);
 			break;
 		case T_Result:
 			if (IsA(best_path, ProjectionPath))
@@ -999,13 +996,17 @@ create_join_plan(PlannerInfo *root, JoinPath *best_path)
  *	  Returns a Plan node.
  */
 static Plan *
-create_append_plan(PlannerInfo *root, AppendPath *best_path)
+create_append_plan(NodeTag node_type, PlannerInfo *root, AppendPath *best_path)
 {
-	Append	   *plan;
+	Append	   *node;
+	Plan 	   *plan;
 	List	   *tlist = build_path_tlist(root, &best_path->path);
+	List	   *pathkeys = best_path->path.pathkeys;
 	List	   *subplans = NIL;
 	ListCell   *subpaths;
 
+	double limit_tuples = best_path->limit_tuples;
+
 	/*
 	 * The subpaths list could be empty, if every child was proven empty by
 	 * constraint exclusion.  In that case generate a dummy plan that returns
@@ -1017,9 +1018,6 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path)
 	 */
 	if (best_path->subpaths == NIL)
 	{
-		/* Generate a Result plan with constant-FALSE gating qual */
-		Plan	   *plan;
-
 		plan = (Plan *) make_result(tlist,
 									(Node *) list_make1(makeBoolConst(false,
 																	  false)),
@@ -1030,62 +1028,11 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path)
 		return plan;
 	}
 
-	/* Build the plan for each child */
-	foreach(subpaths, best_path->subpaths)
-	{
-		Path	   *subpath = (Path *) lfirst(subpaths);
-		Plan	   *subplan;
-
-		/* Must insist that all children return the same tlist */
-		subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
-
-		subplans = lappend(subplans, subplan);
-	}
-
-	/*
-	 * XXX ideally, if there's just one child, we'd not bother to generate an
-	 * Append node but just return the single child.  At the moment this does
-	 * not work because the varno of the child scan plan won't match the
-	 * parent-rel Vars it'll be asked to emit.
-	 */
-
-	plan = make_append(subplans, tlist, best_path->partitioned_rels);
-
-	copy_generic_path_info(&plan->plan, (Path *) best_path);
-
-	return (Plan *) plan;
-}
-
-/*
- * create_merge_append_plan
- *	  Create a MergeAppend plan for 'best_path' and (recursively) plans
- *	  for its subpaths.
- *
- *	  Returns a Plan node.
- */
-static Plan *
-create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path)
-{
-	MergeAppend *node = makeNode(MergeAppend);
-	Plan	   *plan = &node->plan;
-	List	   *tlist = build_path_tlist(root, &best_path->path);
-	List	   *pathkeys = best_path->path.pathkeys;
-	List	   *subplans = NIL;
-	ListCell   *subpaths;
-
-	/*
-	 * We don't have the actual creation of the MergeAppend node split out
-	 * into a separate make_xxx function.  This is because we want to run
-	 * prepare_sort_from_pathkeys on it before we do so on the individual
-	 * child plans, to make cross-checking the sort info easier.
-	 */
+	node = make_append(node_type, tlist, best_path->partitioned_rels);
+	plan = &node->plan;
 	copy_generic_path_info(plan, (Path *) best_path);
 	plan->targetlist = tlist;
-	plan->qual = NIL;
-	plan->lefttree = NULL;
-	plan->righttree = NULL;
 
-	/* Compute sort column info, and adjust MergeAppend's tlist as needed */
 	(void) prepare_sort_from_pathkeys(plan, pathkeys,
 									  best_path->path.parent->relids,
 									  NULL,
@@ -1096,70 +1043,18 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path)
 									  &node->collations,
 									  &node->nullsFirst);
 
-	/*
-	 * Now prepare the child plans.  We must apply prepare_sort_from_pathkeys
-	 * even to subplans that don't need an explicit sort, to make sure they
-	 * are returning the same sort key columns the MergeAppend expects.
-	 */
-	foreach(subpaths, best_path->subpaths)
+	/* Build the plan for each child */
+ 	foreach(subpaths, best_path->subpaths)
 	{
 		Path	   *subpath = (Path *) lfirst(subpaths);
-		Plan	   *subplan;
-		int			numsortkeys;
-		AttrNumber *sortColIdx;
-		Oid		   *sortOperators;
-		Oid		   *collations;
-		bool	   *nullsFirst;
-
-		/* Build the child plan */
-		/* Must insist that all children return the same tlist */
-		subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
-
-		/* Compute sort column info, and adjust subplan's tlist as needed */
-		subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
-											 subpath->parent->relids,
-											 node->sortColIdx,
-											 false,
-											 &numsortkeys,
-											 &sortColIdx,
-											 &sortOperators,
-											 &collations,
-											 &nullsFirst);
-
-		/*
-		 * Check that we got the same sort key information.  We just Assert
-		 * that the sortops match, since those depend only on the pathkeys;
-		 * but it seems like a good idea to check the sort column numbers
-		 * explicitly, to ensure the tlists really do match up.
-		 */
-		Assert(numsortkeys == node->numCols);
-		if (memcmp(sortColIdx, node->sortColIdx,
-				   numsortkeys * sizeof(AttrNumber)) != 0)
-			elog(ERROR, "MergeAppend child's targetlist doesn't match MergeAppend");
-		Assert(memcmp(sortOperators, node->sortOperators,
-					  numsortkeys * sizeof(Oid)) == 0);
-		Assert(memcmp(collations, node->collations,
-					  numsortkeys * sizeof(Oid)) == 0);
-		Assert(memcmp(nullsFirst, node->nullsFirst,
-					  numsortkeys * sizeof(bool)) == 0);
-
-		/* Now, insert a Sort node if subplan isn't sufficiently ordered */
-		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;
-		}
 
+		/* TODO: decrease limit tuples for each subpath */
+		Plan *subplan = plan = wrap_sort(root, node, subpath, pathkeys, limit_tuples);
+		if(limit_tuples > 0)
+			limit_tuples = Max(1, limit_tuples - subpath->rows);
 		subplans = lappend(subplans, subplan);
 	}
-
-	node->partitioned_rels = best_path->partitioned_rels;
-	node->mergeplans = subplans;
-
+	node->appendplans = subplans;
 	return (Plan *) node;
 }
 
@@ -1566,7 +1461,7 @@ create_projection_plan(PlannerInfo *root, ProjectionPath *best_path)
 	 * anyway.  Usually create_projection_path will have detected that and set
 	 * dummypp if we don't need a Result; but its decision can't be final,
 	 * because some createplan.c routines change the tlists of their nodes.
-	 * (An example is that create_merge_append_plan might add resjunk sort
+	 * (An example is that create_append_plan might add resjunk sort
 	 * columns to a MergeAppend.)  So we have to recheck here.  If we do
 	 * arrive at a different answer than create_projection_path did, we'll
 	 * have made slightly wrong cost estimates; but label the plan with the
@@ -5274,21 +5169,100 @@ make_foreignscan(List *qptlist,
 }
 
 static Append *
-make_append(List *appendplans, List *tlist, List *partitioned_rels)
+make_append(NodeTag node_type, List *tlist, List *partitioned_rels)
 {
-	Append	   *node = makeNode(Append);
-	Plan	   *plan = &node->plan;
+	Append	   *node;
+	Plan	   *plan;
 
-	plan->targetlist = tlist;
+	if (node_type != T_Append && node_type != T_MergeAppend)
+		elog(ERROR, "create_append_plan can only create Append or MergeAppend plans");
+
+	switch(node_type)
+	{
+		case T_Append:
+			node = makeNode(Append);
+			break;
+		case T_MergeAppend:
+			node = (Append *) makeNode(MergeAppend);
+			break;
+		default:
+			elog(ERROR, "create_append_plan can only create Append or MergeAppend plans");
+	}
+
+	plan = &node->plan;  	plan->targetlist = tlist;
 	plan->qual = NIL;
 	plan->lefttree = NULL;
 	plan->righttree = NULL;
 	node->partitioned_rels = partitioned_rels;
-	node->appendplans = appendplans;
+	node->appendplans = NIL;
+	node->numCols = 0;
+	node->sortColIdx = NULL;
+	node->sortOperators = NULL;
+	node->collations = NULL;
+	node->nullsFirst = NULL;
 
 	return node;
 }
 
+static Plan *
+wrap_sort(PlannerInfo *root, Append* parentplan, Path *subpath, List* pathkeys, double limit_tuples)
+{
+	int			numCols;
+	AttrNumber *sortColIdx;
+	Oid		   *sortOperators;
+	Oid		   *collations;
+	bool	   *nullsFirst;
+	Plan	   *subplan;
+
+	/* Build the child plan */
+	/* Must insist that all children return the same tlist */
+	subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
+
+	if (pathkeys != NIL)
+	{
+		/* Compute sort column info, and adjust subplan's tlist as needed */
+		subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+											 subpath->parent->relids,
+											 parentplan->sortColIdx,
+											 false,
+											 &numCols,
+											 &sortColIdx,
+											 &sortOperators,
+											 &collations,
+											 &nullsFirst);
+
+		/*
+		 * Check that we got the same sort key information.  We just Assert
+		 * that the sortops match, since those depend only on the pathkeys;
+		 * but it seems like a good idea to check the sort column numbers
+		 * explicitly, to ensure the tlists really do match up.
+		 */
+		Assert(numCols == parentplan->numCols);
+		if (memcmp(sortColIdx, parentplan->sortColIdx,
+					numCols * sizeof(AttrNumber)) != 0)
+			elog(ERROR, "MergeAppend child's targetlist doesn't match MergeAppend");
+		Assert(memcmp(sortOperators, parentplan->sortOperators,
+					numCols * sizeof(Oid)) == 0);
+		Assert(memcmp(collations, parentplan->collations,
+					numCols * sizeof(Oid)) == 0);
+		Assert(memcmp(nullsFirst, parentplan->nullsFirst,
+					numCols * sizeof(bool)) == 0);
+
+		/* Now, insert a Sort node if subplan isn't sufficiently ordered */
+		if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
+		{
+			Sort	   *sort = make_sort(subplan, numCols,
+										 sortColIdx, sortOperators,
+										 collations, nullsFirst);
+
+			label_sort_with_costsize(root, sort, limit_tuples);
+			subplan = (Plan *) sort;
+		}
+	}
+
+	return subplan;
+}
+
 static RecursiveUnion *
 make_recursive_union(List *tlist,
 					 Plan *lefttree,
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index f4e0a6ea3d..acf87cc917 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -25,6 +25,7 @@
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
 #include "optimizer/placeholder.h"
+#include "optimizer/plancat.h"
 #include "optimizer/planmain.h"
 
 
@@ -176,6 +177,13 @@ query_planner(PlannerInfo *root, List *tlist,
 	 */
 	(*qp_callback) (root, qp_extra);
 
+	/*
+	 * We consider generating pathkeys for partitioned tables only if the
+	 * query has some ordering
+	 */
+	if (root->query_pathkeys != NIL)
+		generate_pathkeys_for_partitioned_tables(root);
+
 	/*
 	 * Examine any "placeholder" expressions generated during subquery pullup.
 	 * Make sure that the Vars they need are marked as needed at the relevant
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 7f146d670c..175088313b 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -3643,10 +3643,12 @@ create_grouping_paths(PlannerInfo *root,
 				paths = lappend(paths, path);
 			}
 			path = (Path *)
-				create_append_path(grouped_rel,
+				create_append_path(root,
+								   grouped_rel,
 								   paths,
 								   NULL,
 								   0,
+								   NIL,
 								   NIL);
 			path->pathtarget = target;
 		}
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index b0c9e94459..c9280af5c1 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -932,12 +932,12 @@ set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset)
 				 * targetlist or check quals.
 				 */
 				set_dummy_tlist_references(plan, rtoffset);
-				Assert(splan->plan.qual == NIL);
-				foreach(l, splan->partitioned_rels)
+				Assert(splan->plan.plan.qual == NIL);
+				foreach(l, splan->plan.partitioned_rels)
 				{
 					lfirst_int(l) += rtoffset;
 				}
-				foreach(l, splan->mergeplans)
+				foreach(l, splan->plan.appendplans)
 				{
 					lfirst(l) = set_plan_refs(root,
 											  (Plan *) lfirst(l),
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 1103984779..19fc190f7d 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -2589,7 +2589,7 @@ finalize_plan(PlannerInfo *root, Plan *plan,
 			{
 				ListCell   *l;
 
-				foreach(l, ((MergeAppend *) plan)->mergeplans)
+				foreach(l, ((MergeAppend *) plan)->plan.appendplans)
 				{
 					context.paramids =
 						bms_add_members(context.paramids,
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 3e0c3de86d..fc615a4314 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -590,7 +590,7 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	/*
 	 * Append the child results together.
 	 */
-	path = (Path *) create_append_path(result_rel, pathlist, NULL, 0, NIL);
+	path = (Path *) create_append_path(root, result_rel, pathlist, NULL, 0, NIL, NIL);
 
 	/* We have to manually jam the right tlist into the path; ick */
 	path->pathtarget = create_pathtarget(root, tlist);
@@ -702,7 +702,7 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 	/*
 	 * Append the child results together.
 	 */
-	path = (Path *) create_append_path(result_rel, pathlist, NULL, 0, NIL);
+	path = (Path *) create_append_path(root, result_rel, pathlist, NULL, 0, NIL, NIL);
 
 	/* We have to manually jam the right tlist into the path; ick */
 	path->pathtarget = create_pathtarget(root, tlist);
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 26567cb7f6..33906d3d64 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1200,11 +1200,21 @@ create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals,
  * Note that we must handle subpaths = NIL, representing a dummy access path.
  */
 AppendPath *
-create_append_path(RelOptInfo *rel, List *subpaths, Relids required_outer,
-				   int parallel_workers, List *partitioned_rels)
+create_append_path(PlannerInfo *root, RelOptInfo *rel, List *subpaths,
+				   Relids required_outer, int parallel_workers,
+				   List *partitioned_rels, List *pathkeys)
 {
 	AppendPath *pathnode = makeNode(AppendPath);
 	ListCell   *l;
+	double		limit_tuples;
+	Cost		input_startup_cost;
+	Cost		input_total_cost;
+
+	/*
+	 * Just to make sure that nobody is trying to build a parallel sorted
+	 * append path
+	 */
+	Assert(parallel_workers > 0 ? pathkeys == NIL : true);
 
 	pathnode->path.pathtype = T_Append;
 	pathnode->path.parent = rel;
@@ -1214,7 +1224,7 @@ create_append_path(RelOptInfo *rel, List *subpaths, Relids required_outer,
 	pathnode->path.parallel_aware = false;
 	pathnode->path.parallel_safe = rel->consider_parallel;
 	pathnode->path.parallel_workers = parallel_workers;
-	pathnode->path.pathkeys = NIL;	/* result is always considered unsorted */
+	pathnode->path.pathkeys = pathkeys;
 	pathnode->partitioned_rels = list_copy(partitioned_rels);
 	pathnode->subpaths = subpaths;
 
@@ -1229,15 +1239,47 @@ create_append_path(RelOptInfo *rel, List *subpaths, Relids required_outer,
 	pathnode->path.rows = 0;
 	pathnode->path.startup_cost = 0;
 	pathnode->path.total_cost = 0;
+
+	if (root && bms_equal(rel->relids, root->all_baserels))
+		pathnode->limit_tuples = root->limit_tuples;
+	else
+		pathnode->limit_tuples = -1.0;
+
+	limit_tuples = pathnode->limit_tuples;
+
 	foreach(l, subpaths)
 	{
 		Path	   *subpath = (Path *) lfirst(l);
+		input_startup_cost = subpath->startup_cost;
+		input_total_cost = subpath->total_cost;
+
+		if(pathkeys && !pathkeys_contained_in(pathkeys, subpath->pathkeys))
+		{
+			Path		sort_path;		/* dummy for result of cost_sort */
+
+			cost_sort(&sort_path,
+					root,
+					pathkeys,
+					subpath->total_cost,
+					subpath->rows,
+					subpath->pathtarget->width,
+					0.0,
+					work_mem,
+					limit_tuples);
+			input_startup_cost += sort_path.startup_cost;
+			input_total_cost = sort_path.total_cost;
+		}
 
 		pathnode->path.rows += subpath->rows;
 
 		if (l == list_head(subpaths))	/* first node? */
-			pathnode->path.startup_cost = subpath->startup_cost;
-		pathnode->path.total_cost += subpath->total_cost;
+			pathnode->path.startup_cost = input_startup_cost;
+		/* Consider that the number of tuples to be fetched decreases
+		 * for every subsequent partition */
+		if(limit_tuples > 0)
+			limit_tuples = Max(1, limit_tuples - subpath->rows);
+
+		pathnode->path.total_cost += input_total_cost;
 		pathnode->path.parallel_safe = pathnode->path.parallel_safe &&
 			subpath->parallel_safe;
 
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index a1ebd4acc8..b4f7a3d932 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -35,6 +35,7 @@
 #include "nodes/makefuncs.h"
 #include "optimizer/clauses.h"
 #include "optimizer/cost.h"
+#include "optimizer/paths.h"
 #include "optimizer/plancat.h"
 #include "optimizer/predtest.h"
 #include "optimizer/prep.h"
@@ -1258,6 +1259,148 @@ get_relation_constraints(PlannerInfo *root,
 	return result;
 }
 
+/*
+ * Generate pathkeys for Range-based partitions
+ */
+void
+generate_pathkeys_for_partitioned_tables(PlannerInfo *root)
+{
+	int i;
+	for (i = 1; i < root->simple_rel_array_size; i++)
+	{
+		RelOptInfo *rel = root->simple_rel_array[i];
+
+		/* Only base relation can be partitionned */
+		if (rel && has_useful_pathkeys(root, rel))
+		{
+			Index varno = rel->relid;
+			Index parent_varno = varno;
+			RelOptInfo *parent_rel = rel;
+			Relation relation;
+			RangeTblEntry *rte = planner_rt_fetch(varno, root);
+
+			if (rte->relkind != RELKIND_PARTITIONED_TABLE)
+				continue;
+
+			while (parent_rel->reloptkind != RELOPT_BASEREL)
+			{
+				ListCell *lc;
+
+				foreach(lc, root->append_rel_list)
+				{
+					AppendRelInfo *ari = lfirst(lc);
+
+					if (ari->child_relid == parent_rel->relid)
+					{
+						parent_rel = root->simple_rel_array[ari->parent_relid];
+						break;
+					}
+
+					/* Should never happen: we should always be able to climb up the
+					 *  inheritance tree */
+					if(!lc)
+						elog(ERROR, "Unable to find parent table for child ");
+				}
+			}
+			parent_varno = parent_rel->relid;
+
+			/*
+			 * Ignore base rel if it's not a partitionned table. We'll still
+			 * have to open it to verify if it's a range partitionned table
+			 */
+			if (rte->relkind != RELKIND_PARTITIONED_TABLE)
+				continue;
+
+			relation = heap_open(rte->relid, NoLock);
+
+			/*
+			 * Store the child partitions OIDs and build pathkeys for the
+			 * partitioning keys
+			 */
+			if(relation->rd_partkey->strategy == PARTITION_STRATEGY_RANGE)
+			{
+				int j;
+				ListCell *lc;
+				Oid equality_op;
+				EquivalenceClass *ec;
+				List *opfamilies;
+				List *asc_pathkeys = NIL;
+				List *desc_pathkeys = NIL;
+
+				Assert(rel->rel_sorted_part_oids == NIL);
+				Assert(rel->rel_partitioned_pathkeys == NIL);
+
+				for (j = 0; j < relation->rd_partdesc->nparts; j++)
+				{
+					rel->rel_sorted_part_oids =
+						lappend_oid(rel->rel_sorted_part_oids,
+								relation->rd_partdesc->oids[j]);
+				}
+
+				/* Lookup individual vars from the pathtarget */
+				/* FIXME: refactor this in an external function */
+				lc = list_head(relation->rd_partkey->partexprs);
+				for (j=0; j < relation->rd_partkey->partnatts; j++)
+				{
+					AttrNumber attno = relation->rd_partkey->partattrs[j];
+					Expr *expr = NULL;
+
+					/* This is not an attribute, but an expression */
+					if(attno == InvalidAttrNumber)
+					{
+						/* Should never append : we should be able to fetch
+						 * an expression for anything in the partition key */
+						if (!lc)
+							elog(ERROR, "Could not find expression for partition key");
+						expr = lfirst(lc);
+						lc = lnext(lc);
+					}
+					else
+					{
+						expr = (Expr*) makeVar(parent_varno, attno, relation->rd_partkey->parttypid[j],
+									  relation->rd_partkey->parttypmod[j],
+									  relation->rd_partkey->parttypcoll[j],
+									  0);
+					}
+
+					equality_op = get_opfamily_member(relation->rd_partkey->partopfamily[j],
+																		  relation->rd_partkey->partopcintype[j],
+																		  relation->rd_partkey->partopcintype[j],
+																		  BTEqualStrategyNumber);
+					opfamilies = get_mergejoin_opfamilies(equality_op);
+					ec = get_eclass_for_sort_expr(root, expr,
+							NULL, opfamilies,
+							relation->rd_partkey->partopcintype[j],
+							relation->rd_partkey->partcollation[j],
+							0, rel->relids, true);
+					asc_pathkeys = lappend(asc_pathkeys,  make_canonical_pathkey(root,
+							ec,
+							relation->rd_partkey->partopfamily[j],
+							BTLessStrategyNumber, false));
+					desc_pathkeys  = lappend(desc_pathkeys, make_canonical_pathkey(root,
+							ec,
+							relation->rd_partkey->partopfamily[j],
+							BTGreaterStrategyNumber, true));
+				}
+
+				/* FIXME: this is as dirty as it gets */
+				if(list_length(asc_pathkeys) > list_length(root->query_pathkeys))
+				{
+					asc_pathkeys = truncate_useless_pathkeys(root, rel, asc_pathkeys);
+					desc_pathkeys = truncate_useless_pathkeys(root, rel, desc_pathkeys);
+				}
+
+				if(asc_pathkeys)
+					rel->rel_partitioned_pathkeys = lappend(rel->rel_partitioned_pathkeys, asc_pathkeys);
+
+				if(desc_pathkeys)
+					rel->rel_partitioned_pathkeys = lappend(rel->rel_partitioned_pathkeys, desc_pathkeys);
+			}
+			heap_close(relation, NoLock);
+		}
+	}
+}
+
 /*
  * get_relation_statistics
  *		Retrieve extended statistics defined on the table.
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index c7b2695ebb..3a2f9e11de 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -146,6 +146,8 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
 	rel->baserestrict_min_security = UINT_MAX;
 	rel->joininfo = NIL;
 	rel->has_eclass_joins = false;
+	rel->rel_partitioned_pathkeys = NIL;
+	rel->rel_sorted_part_oids = NIL;
 
 	/*
 	 * Pass top parent's relids down the inheritance hierarchy. If the parent
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index a382331f41..283af54e09 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -248,6 +248,17 @@ typedef struct Append
 	/* RT indexes of non-leaf tables in a partition tree */
 	List	   *partitioned_rels;
 	List	   *appendplans;
+	/* remaining fields are just like the sort-key info in struct Sort */
+	/* FIXME: We should either
+	 * 	- define Append as sort + appendplans
+	 * 	- define Append "like" sort and define MergeAppend as Append, only with
+	 * 	a different tag
+	 */
+	int			numCols;		/* number of sort-key columns */
+	AttrNumber *sortColIdx;		/* their indexes in the target list */
+	Oid		   *sortOperators;	/* OIDs of operators to sort them by */
+	Oid		   *collations;		/* OIDs of collations */
+	bool	   *nullsFirst;		/* NULLS FIRST/LAST directions */
 } Append;
 
 /* ----------------
@@ -257,16 +268,7 @@ typedef struct Append
  */
 typedef struct MergeAppend
 {
-	Plan		plan;
-	/* RT indexes of non-leaf tables in a partition tree */
-	List	   *partitioned_rels;
-	List	   *mergeplans;
-	/* remaining fields are just like the sort-key info in struct Sort */
-	int			numCols;		/* number of sort-key columns */
-	AttrNumber *sortColIdx;		/* their indexes in the target list */
-	Oid		   *sortOperators;	/* OIDs of operators to sort them by */
-	Oid		   *collations;		/* OIDs of collations */
-	bool	   *nullsFirst;		/* NULLS FIRST/LAST directions */
+	Append 		plan;
 } MergeAppend;
 
 /* ----------------
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index d50ff55681..73d9851d23 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -567,6 +567,8 @@ typedef struct RelOptInfo
 	PlannerInfo *subroot;		/* if subquery */
 	List	   *subplan_params; /* if subquery */
 	int			rel_parallel_workers;	/* wanted number of parallel workers */
+	List		*rel_sorted_part_oids; /* if range partitioning */
+	List		*rel_partitioned_pathkeys;
 
 	/* Information about foreign tables and foreign joins */
 	Oid			serverid;		/* identifies server for the table or join */
@@ -1178,6 +1180,7 @@ typedef struct AppendPath
 	/* RT indexes of non-leaf tables in a partition tree */
 	List	   *partitioned_rels;
 	List	   *subpaths;		/* list of component Paths */
+	double		limit_tuples;	/* hard limit on output tuples, or -1 */
 } AppendPath;
 
 #define IS_DUMMY_PATH(p) \
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index e372f8862b..1496bdc0dc 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -63,9 +63,13 @@ extern BitmapOrPath *create_bitmap_or_path(PlannerInfo *root,
 					  List *bitmapquals);
 extern TidPath *create_tidscan_path(PlannerInfo *root, RelOptInfo *rel,
 					List *tidquals, Relids required_outer);
-extern AppendPath *create_append_path(RelOptInfo *rel, List *subpaths,
-				   Relids required_outer, int parallel_workers,
-				   List *partitioned_rels);
+extern AppendPath *create_append_path(PlannerInfo *root,
+				   RelOptInfo *rel,
+				   List *subpaths,
+				   Relids required_outer,
+				   int parallel_workers,
+				   List *partitioned_rels,
+				   List *pathkeys);
 extern MergeAppendPath *create_merge_append_path(PlannerInfo *root,
 						 RelOptInfo *rel,
 						 List *subpaths,
diff --git a/src/include/optimizer/plancat.h b/src/include/optimizer/plancat.h
index 71f0faf938..6d96d54b5d 100644
--- a/src/include/optimizer/plancat.h
+++ b/src/include/optimizer/plancat.h
@@ -35,6 +35,8 @@ extern void estimate_rel_size(Relation rel, int32 *attr_widths,
 
 extern int32 get_relation_data_width(Oid relid, int32 *attr_widths);
 
+extern void generate_pathkeys_for_partitioned_tables(PlannerInfo *root);
+
 extern bool relation_excluded_by_constraints(PlannerInfo *root,
 								 RelOptInfo *rel, RangeTblEntry *rte);
 
diff --git a/src/test/regress/expected/inherit.out b/src/test/regress/expected/inherit.out
index c698faff2f..03d9cbb242 100644
--- a/src/test/regress/expected/inherit.out
+++ b/src/test/regress/expected/inherit.out
@@ -1952,13 +1952,13 @@ explain (costs off) select min(a), max(a) from parted_minmax where b = '12345';
  Result
    InitPlan 1 (returns $0)
      ->  Limit
-           ->  Merge Append
+           ->  Append
                  Sort Key: parted_minmax1.a
                  ->  Index Only Scan using parted_minmax1i on parted_minmax1
                        Index Cond: ((a IS NOT NULL) AND (b = '12345'::text))
    InitPlan 2 (returns $1)
      ->  Limit
-           ->  Merge Append
+           ->  Append
                  Sort Key: parted_minmax1_1.a DESC
                  ->  Index Only Scan Backward using parted_minmax1i on parted_minmax1 parted_minmax1_1
                        Index Cond: ((a IS NOT NULL) AND (b = '12345'::text))

diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index c1602c59cc..20e63b3204 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -80,6 +80,8 @@ static void show_upper_qual(List *qual, const char *qlabel,
 				ExplainState *es);
 static void show_sort_keys(SortState *sortstate, List *ancestors,
 			   ExplainState *es);
+static void show_append_keys(AppendState *mstate, List *ancestors,
+					   ExplainState *es);
 static void show_merge_append_keys(MergeAppendState *mstate, List *ancestors,
 					   ExplainState *es);
 static void show_agg_keys(AggState *astate, List *ancestors,
@@ -1602,6 +1604,10 @@ ExplainNode(PlanState *planstate, List *ancestors,
 			show_sort_keys(castNode(SortState, planstate), ancestors, es);
 			show_sort_info(castNode(SortState, planstate), es);
 			break;
+		case T_Append:
+			show_append_keys(castNode(AppendState, planstate),
+								   ancestors, es);
+			break;
 		case T_MergeAppend:
 			show_merge_append_keys(castNode(MergeAppendState, planstate),
 								   ancestors, es);
@@ -1744,7 +1750,7 @@ ExplainNode(PlanState *planstate, List *ancestors,
 							   ancestors, es);
 			break;
 		case T_MergeAppend:
-			ExplainMemberNodes(((MergeAppend *) plan)->mergeplans,
+			ExplainMemberNodes(((MergeAppend*) plan)->plan.appendplans,
 							   ((MergeAppendState *) planstate)->mergeplans,
 							   ancestors, es);
 			break;
@@ -1935,6 +1941,22 @@ show_sort_keys(SortState *sortstate, List *ancestors, ExplainState *es)
 						 ancestors, es);
 }
 
+/*
+ * Likewise, for an Append node.
+ */
+static void
+show_append_keys(AppendState *mstate, List *ancestors,
+					   ExplainState *es)
+{
+	Append *plan = (Append *) mstate->ps.plan;
+
+	show_sort_group_keys((PlanState *) mstate, "Sort Key",
+						 plan->numCols, plan->sortColIdx,
+						 plan->sortOperators, plan->collations,
+						 plan->nullsFirst,
+						 ancestors, es);
+}
+
 /*
  * Likewise, for a MergeAppend node.
  */
@@ -1942,7 +1964,7 @@ static void
 show_merge_append_keys(MergeAppendState *mstate, List *ancestors,
 					   ExplainState *es)
 {
-	MergeAppend *plan = (MergeAppend *) mstate->ps.plan;
+	Append *plan = (Append *) mstate->ps.plan;
 
 	show_sort_group_keys((PlanState *) mstate, "Sort Key",
 						 plan->numCols, plan->sortColIdx,
diff --git a/src/backend/executor/nodeMergeAppend.c b/src/backend/executor/nodeMergeAppend.c
index 6bf490bd70..601f2547d3 100644
--- a/src/backend/executor/nodeMergeAppend.c
+++ b/src/backend/executor/nodeMergeAppend.c
@@ -64,6 +64,7 @@ MergeAppendState *
 ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
 {
 	MergeAppendState *mergestate = makeNode(MergeAppendState);
+	Append			 *append = &node->plan;
 	PlanState **mergeplanstates;
 	int			nplans;
 	int			i;
@@ -76,12 +77,12 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
 	 * Lock the non-leaf tables in the partition tree controlled by this node.
 	 * It's a no-op for non-partitioned parent tables.
 	 */
-	ExecLockNonLeafAppendTables(node->partitioned_rels, estate);
+	ExecLockNonLeafAppendTables(append->partitioned_rels, estate);
 
 	/*
 	 * Set up empty vector of subplan states
 	 */
-	nplans = list_length(node->mergeplans);
+	nplans = list_length(append->appendplans);
 
 	mergeplanstates = (PlanState **) palloc0(nplans * sizeof(PlanState *));
 
@@ -116,7 +117,7 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
 	 * results into the array "mergeplans".
 	 */
 	i = 0;
-	foreach(lc, node->mergeplans)
+	foreach(lc, append->appendplans)
 	{
 		Plan	   *initNode = (Plan *) lfirst(lc);
 
@@ -133,17 +134,17 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
 	/*
 	 * initialize sort-key information
 	 */
-	mergestate->ms_nkeys = node->numCols;
-	mergestate->ms_sortkeys = palloc0(sizeof(SortSupportData) * node->numCols);
+	mergestate->ms_nkeys = append->numCols;
+	mergestate->ms_sortkeys = palloc0(sizeof(SortSupportData) * append->numCols);
 
-	for (i = 0; i < node->numCols; i++)
+	for (i = 0; i < append->numCols; i++)
 	{
 		SortSupport sortKey = mergestate->ms_sortkeys + i;
 
 		sortKey->ssup_cxt = CurrentMemoryContext;
-		sortKey->ssup_collation = node->collations[i];
-		sortKey->ssup_nulls_first = node->nullsFirst[i];
-		sortKey->ssup_attno = node->sortColIdx[i];
+		sortKey->ssup_collation = append->collations[i];
+		sortKey->ssup_nulls_first = append->nullsFirst[i];
+		sortKey->ssup_attno = append->sortColIdx[i];
 
 		/*
 		 * It isn't feasible to perform abbreviated key conversion, since
@@ -154,7 +155,7 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
 		 */
 		sortKey->abbreviate = false;
 
-		PrepareSortSupportFromOrderingOp(node->sortOperators[i], sortKey);
+		PrepareSortSupportFromOrderingOp(append->sortOperators[i], sortKey);
 	}
 
 	/*
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index f1bed14e2b..23dd6043be 100644
--- a/src/backend/nodes/copyfuncs.c
+++ b/src/backend/nodes/copyfuncs.c
@@ -224,6 +224,19 @@ _copyModifyTable(const ModifyTable *from)
 	return newnode;
 }
 
+static void
+copyAppendFields(const Append *from, Append *newnode)
+{
+	CopyPlanFields((const Plan *) from, (Plan *) newnode);
+	COPY_NODE_FIELD(partitioned_rels);
+	COPY_NODE_FIELD(appendplans);
+	COPY_SCALAR_FIELD(numCols);
+	COPY_POINTER_FIELD(sortColIdx, from->numCols * sizeof(AttrNumber));
+	COPY_POINTER_FIELD(sortOperators, from->numCols * sizeof(Oid));
+	COPY_POINTER_FIELD(collations, from->numCols * sizeof(Oid));
+	COPY_POINTER_FIELD(nullsFirst, from->numCols * sizeof(bool));
+}
+
 /*
  * _copyAppend
  */
@@ -232,16 +245,7 @@ _copyAppend(const Append *from)
 {
 	Append	   *newnode = makeNode(Append);
 
-	/*
-	 * copy node superclass fields
-	 */
-	CopyPlanFields((const Plan *) from, (Plan *) newnode);
-
-	/*
-	 * copy remainder of node
-	 */
-	COPY_NODE_FIELD(partitioned_rels);
-	COPY_NODE_FIELD(appendplans);
+	copyAppendFields(from, newnode);
 
 	return newnode;
 }
@@ -254,21 +258,7 @@ _copyMergeAppend(const MergeAppend *from)
 {
 	MergeAppend *newnode = makeNode(MergeAppend);
 
-	/*
-	 * copy node superclass fields
-	 */
-	CopyPlanFields((const Plan *) from, (Plan *) newnode);
-
-	/*
-	 * copy remainder of node
-	 */
-	COPY_NODE_FIELD(partitioned_rels);
-	COPY_NODE_FIELD(mergeplans);
-	COPY_SCALAR_FIELD(numCols);
-	COPY_POINTER_FIELD(sortColIdx, from->numCols * sizeof(AttrNumber));
-	COPY_POINTER_FIELD(sortOperators, from->numCols * sizeof(Oid));
-	COPY_POINTER_FIELD(collations, from->numCols * sizeof(Oid));
-	COPY_POINTER_FIELD(nullsFirst, from->numCols * sizeof(bool));
+	copyAppendFields((const Append *)from, (Append *)newnode);
 
 	return newnode;
 }
diff --git a/src/backend/nodes/nodeFuncs.c b/src/backend/nodes/nodeFuncs.c
index e3eb0c5788..ccbf11d72e 100644
--- a/src/backend/nodes/nodeFuncs.c
+++ b/src/backend/nodes/nodeFuncs.c
@@ -3735,7 +3735,7 @@ planstate_tree_walker(PlanState *planstate,
 				return true;
 			break;
 		case T_MergeAppend:
-			if (planstate_walk_members(((MergeAppend *) plan)->mergeplans,
+			if (planstate_walk_members(((MergeAppend *) plan)->plan.appendplans,
 									   ((MergeAppendState *) planstate)->mergeplans,
 									   walker, context))
 				return true;
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index b83d919e40..47f276d9f5 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -386,27 +386,14 @@ _outModifyTable(StringInfo str, const ModifyTable *node)
 }
 
 static void
-_outAppend(StringInfo str, const Append *node)
+_outAppendInfo(StringInfo str, const Append *node)
 {
-	WRITE_NODE_TYPE("APPEND");
+	int i;
 
 	_outPlanInfo(str, (const Plan *) node);
 
 	WRITE_NODE_FIELD(partitioned_rels);
 	WRITE_NODE_FIELD(appendplans);
-}
-
-static void
-_outMergeAppend(StringInfo str, const MergeAppend *node)
-{
-	int			i;
-
-	WRITE_NODE_TYPE("MERGEAPPEND");
-
-	_outPlanInfo(str, (const Plan *) node);
-
-	WRITE_NODE_FIELD(partitioned_rels);
-	WRITE_NODE_FIELD(mergeplans);
 
 	WRITE_INT_FIELD(numCols);
 
@@ -427,6 +414,20 @@ _outMergeAppend(StringInfo str, const MergeAppend *node)
 		appendStringInfo(str, " %s", booltostr(node->nullsFirst[i]));
 }
 
+static void
+_outAppend(StringInfo str, const Append *node)
+{
+	WRITE_NODE_TYPE("APPEND");
+	_outAppendInfo(str, node);
+}
+
+static void
+_outMergeAppend(StringInfo str, const MergeAppend *node)
+{
+	WRITE_NODE_TYPE("MERGEAPPEND");
+	_outAppendInfo(str, (const Append *) &node->plan);
+}
+
 static void
 _outRecursiveUnion(StringInfo str, const RecursiveUnion *node)
 {
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
index fbf8330735..270b60041c 100644
--- a/src/backend/nodes/readfuncs.c
+++ b/src/backend/nodes/readfuncs.c
@@ -1582,18 +1582,31 @@ _readModifyTable(void)
 	READ_DONE();
 }
 
+static void
+ReadCommonAppend(Append* local_node)
+{
+	READ_TEMP_LOCALS();
+
+	ReadCommonPlan(&local_node->plan);
+
+	READ_NODE_FIELD(partitioned_rels);
+	READ_NODE_FIELD(appendplans);
+	READ_INT_FIELD(numCols);
+	READ_ATTRNUMBER_ARRAY(sortColIdx, local_node->numCols);
+	READ_OID_ARRAY(sortOperators, local_node->numCols);
+	READ_OID_ARRAY(collations, local_node->numCols);
+	READ_BOOL_ARRAY(nullsFirst, local_node->numCols);
+}
+
 /*
  * _readAppend
  */
 static Append *
 _readAppend(void)
 {
-	READ_LOCALS(Append);
+	READ_LOCALS_NO_FIELDS(Append);
 
-	ReadCommonPlan(&local_node->plan);
-
-	READ_NODE_FIELD(partitioned_rels);
-	READ_NODE_FIELD(appendplans);
+	ReadCommonAppend(local_node);
 
 	READ_DONE();
 }
@@ -1604,17 +1617,9 @@ _readAppend(void)
 static MergeAppend *
 _readMergeAppend(void)
 {
-	READ_LOCALS(MergeAppend);
-
-	ReadCommonPlan(&local_node->plan);
+	READ_LOCALS_NO_FIELDS(MergeAppend);
 
-	READ_NODE_FIELD(partitioned_rels);
-	READ_NODE_FIELD(mergeplans);
-	READ_INT_FIELD(numCols);
-	READ_ATTRNUMBER_ARRAY(sortColIdx, local_node->numCols);
-	READ_OID_ARRAY(sortOperators, local_node->numCols);
-	READ_OID_ARRAY(collations, local_node->numCols);
-	READ_BOOL_ARRAY(nullsFirst, local_node->numCols);
+	ReadCommonAppend(&local_node->plan);
 
 	READ_DONE();
 }
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index a7866a99e0..c39b537366 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -20,6 +20,7 @@
 
 #include "access/sysattr.h"
 #include "access/tsmapi.h"
+#include "catalog/partition.h"
 #include "catalog/pg_class.h"
 #include "catalog/pg_operator.h"
 #include "catalog/pg_proc.h"
@@ -94,6 +95,8 @@ 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_sorted_append_paths(PlannerInfo *root,
+			RelOptInfo *parent_rel);
 static void generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
 						   List *live_childrels,
 						   List *all_child_pathkeys,
@@ -1431,8 +1434,19 @@ add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 	 * if we have zero or one live subpath due to constraint exclusion.)
 	 */
 	if (subpaths_valid)
-		add_path(rel, (Path *) create_append_path(rel, subpaths, NULL, 0,
-												  partitioned_rels));
+		add_path(rel, (Path *) create_append_path(root, rel, subpaths, NULL, 0,
+												  partitioned_rels, NIL));
+
+	/*
+	 * If possible, build ordered append path matching the PathKeys derived
+	 * from the partition key.  A native order is possible if it's a ranged
+	 * partitioning and it doesn't have a default partition.
+	 */
+	if (rel->part_scheme &&
+		rel->part_scheme->strategy == PARTITION_STRATEGY_RANGE &&
+		get_default_partition_oid(rte->relid) == InvalidOid
+	)
+		generate_sorted_append_paths(root, rel);
 
 	/*
 	 * Consider an append of partial unordered, unparameterized partial paths.
@@ -1458,8 +1472,8 @@ add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 		Assert(parallel_workers > 0);
 
 		/* Generate a partial append path. */
-		appendpath = create_append_path(rel, partial_subpaths, NULL,
-										parallel_workers, partitioned_rels);
+		appendpath = create_append_path(root, rel, partial_subpaths, NULL,
+										parallel_workers, partitioned_rels, NIL);
 		add_partial_path(rel, (Path *) appendpath);
 	}
 
@@ -1512,8 +1526,112 @@ add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 
 		if (subpaths_valid)
 			add_path(rel, (Path *)
-					 create_append_path(rel, subpaths, required_outer, 0,
-										partitioned_rels));
+					 create_append_path(root, rel, subpaths, required_outer, 0,
+										partitioned_rels, NIL));
+	}
+}
+
+static void
+generate_sorted_append_paths(PlannerInfo *root, RelOptInfo *parent_rel)
+{
+	ListCell *lc;
+	int i;
+	List *partitions_asc = NIL;
+	List *partitions_desc = NIL;
+	RangeTblEntry * parent_rte = planner_rt_fetch(parent_rel->relid, root);
+
+	if (parent_rte->relkind != RELKIND_PARTITIONED_TABLE)
+		return;
+
+	for (i = 0; i < parent_rel->nparts; i++)
+	{
+		partitions_asc = lappend(partitions_asc, parent_rel->part_rels[i]);
+		partitions_desc = lcons(parent_rel->part_rels[i], partitions_desc);
+	}
+
+	foreach(lc, parent_rel->part_pathkeys)
+	{
+		List *pathkeys = (List *) lfirst(lc);
+		PathKey *first = (PathKey *) linitial(pathkeys);
+		List *ordered_partitions = first->pk_strategy == BTLessStrategyNumber ?
+			partitions_asc : partitions_desc;
+		List *startup_subpaths = NIL;
+		List *total_subpaths = NIL;
+		List *sequential_subpaths = NIL;
+		bool startup_neq_total = false;
+		ListCell *lc2;
+
+		if (compare_pathkeys(pathkeys, root->query_pathkeys) == PATHKEYS_DIFFERENT)
+			continue;
+
+		foreach (lc2, ordered_partitions)
+		{
+			RelOptInfo *childrel = lfirst(lc2);
+			Path *cheapest_startup,
+				 *cheapest_total,
+				 *sequential = NULL;
+
+			/* The partition may have been pruned */
+			if (!childrel)
+				continue;
+
+			//Assert(pathkeys_contained_in(pathkeys, root->query_pathkeys));
+
+			cheapest_startup = get_cheapest_path_for_pathkeys(childrel->pathlist,
+					root->query_pathkeys,
+					NULL,
+					STARTUP_COST,
+					false);
+			cheapest_total = get_cheapest_path_for_pathkeys(childrel->pathlist,
+					root->query_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);
+			}
+			/*
+			 * Force a an unordered path, which could be cheaper in corner cases where
+			 * orderedpaths are too expensive.
+			 */
+			sequential = childrel->cheapest_total_path;
+
+			/*
+			 * Notice whether we actually have different paths for the
+			 * "cheapest" and "total" cases; frequently there will be no point
+			 * in two create_merge_append_path() calls.
+			 */
+			if (cheapest_startup != cheapest_total)
+				startup_neq_total = true;
+			startup_subpaths =
+				lappend(startup_subpaths, cheapest_startup);
+			total_subpaths =
+				lappend(total_subpaths, cheapest_total);
+			sequential_subpaths =
+				lappend(sequential_subpaths, sequential);
+
+		}
+		if (startup_subpaths)
+		{
+			add_path(parent_rel, (Path *) create_append_path(root, parent_rel, startup_subpaths,
+						NULL, 0, NIL, root->query_pathkeys));
+		}
+		if (startup_neq_total)
+			add_path(parent_rel, (Path *) create_append_path(root,
+					parent_rel, total_subpaths, NULL, 0, NIL, root->query_pathkeys));
+		if (sequential_subpaths){
+			add_path(parent_rel, (Path *) create_append_path(root,
+					parent_rel, sequential_subpaths, NULL, 0, NIL, root->query_pathkeys));
+		}
 	}
 }
 
@@ -1749,7 +1867,7 @@ set_dummy_rel_pathlist(RelOptInfo *rel)
 	rel->pathlist = NIL;
 	rel->partial_pathlist = NIL;
 
-	add_path(rel, (Path *) create_append_path(rel, NIL, NULL, 0, NIL));
+	add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NULL, 0, NIL, NIL));
 
 	/*
 	 * We set the cheapest path immediately, to ensure that IS_DUMMY_REL()
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 6ee23509c5..9b201ecdda 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -1217,7 +1217,7 @@ mark_dummy_rel(RelOptInfo *rel)
 	rel->partial_pathlist = NIL;
 
 	/* Set up the dummy path */
-	add_path(rel, (Path *) create_append_path(rel, NIL, NULL, 0, NIL));
+	add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NULL, 0, NIL, NIL));
 
 	/* Set or update cheapest_total_path and related fields */
 	set_cheapest(rel);
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 28216629aa..e063128251 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -78,8 +78,8 @@ static List *get_gating_quals(PlannerInfo *root, List *quals);
 static Plan *create_gating_plan(PlannerInfo *root, Path *path, Plan *plan,
 				   List *gating_quals);
 static Plan *create_join_plan(PlannerInfo *root, JoinPath *best_path);
-static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path);
-static Plan *create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path);
+static Plan *create_append_plan(NodeTag node_type, PlannerInfo *root, AppendPath *best_path);
+static Plan *wrap_sort(PlannerInfo *root, Append* parentplan, Path *subpath, List* pathkeys, double limit_tuples);
 static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path);
 static ProjectSet *create_project_set_plan(PlannerInfo *root, ProjectSetPath *best_path);
 static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path,
@@ -203,7 +203,7 @@ 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, List *tlist, List *partitioned_rels);
+static Append *make_append(NodeTag node_type, List *tlist, List *partitioned_rels);
 static RecursiveUnion *make_recursive_union(List *tlist,
 					 Plan *lefttree,
 					 Plan *righttree,
@@ -381,12 +381,9 @@ create_plan_recurse(PlannerInfo *root, Path *best_path, int flags)
 									(JoinPath *) best_path);
 			break;
 		case T_Append:
-			plan = create_append_plan(root,
-									  (AppendPath *) best_path);
-			break;
 		case T_MergeAppend:
-			plan = create_merge_append_plan(root,
-											(MergeAppendPath *) best_path);
+			plan = create_append_plan(best_path->pathtype, root,
+									  (AppendPath *) best_path);
 			break;
 		case T_Result:
 			if (IsA(best_path, ProjectionPath))
@@ -999,13 +996,17 @@ create_join_plan(PlannerInfo *root, JoinPath *best_path)
  *	  Returns a Plan node.
  */
 static Plan *
-create_append_plan(PlannerInfo *root, AppendPath *best_path)
+create_append_plan(NodeTag node_type, PlannerInfo *root, AppendPath *best_path)
 {
-	Append	   *plan;
+	Append	   *node;
+	Plan 	   *plan;
 	List	   *tlist = build_path_tlist(root, &best_path->path);
+	List	   *pathkeys = best_path->path.pathkeys;
 	List	   *subplans = NIL;
 	ListCell   *subpaths;
 
+	double limit_tuples = best_path->limit_tuples;
+
 	/*
 	 * The subpaths list could be empty, if every child was proven empty by
 	 * constraint exclusion.  In that case generate a dummy plan that returns
@@ -1017,9 +1018,6 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path)
 	 */
 	if (best_path->subpaths == NIL)
 	{
-		/* Generate a Result plan with constant-FALSE gating qual */
-		Plan	   *plan;
-
 		plan = (Plan *) make_result(tlist,
 									(Node *) list_make1(makeBoolConst(false,
 																	  false)),
@@ -1030,62 +1028,11 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path)
 		return plan;
 	}
 
-	/* Build the plan for each child */
-	foreach(subpaths, best_path->subpaths)
-	{
-		Path	   *subpath = (Path *) lfirst(subpaths);
-		Plan	   *subplan;
-
-		/* Must insist that all children return the same tlist */
-		subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
-
-		subplans = lappend(subplans, subplan);
-	}
-
-	/*
-	 * XXX ideally, if there's just one child, we'd not bother to generate an
-	 * Append node but just return the single child.  At the moment this does
-	 * not work because the varno of the child scan plan won't match the
-	 * parent-rel Vars it'll be asked to emit.
-	 */
-
-	plan = make_append(subplans, tlist, best_path->partitioned_rels);
-
-	copy_generic_path_info(&plan->plan, (Path *) best_path);
-
-	return (Plan *) plan;
-}
-
-/*
- * create_merge_append_plan
- *	  Create a MergeAppend plan for 'best_path' and (recursively) plans
- *	  for its subpaths.
- *
- *	  Returns a Plan node.
- */
-static Plan *
-create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path)
-{
-	MergeAppend *node = makeNode(MergeAppend);
-	Plan	   *plan = &node->plan;
-	List	   *tlist = build_path_tlist(root, &best_path->path);
-	List	   *pathkeys = best_path->path.pathkeys;
-	List	   *subplans = NIL;
-	ListCell   *subpaths;
-
-	/*
-	 * We don't have the actual creation of the MergeAppend node split out
-	 * into a separate make_xxx function.  This is because we want to run
-	 * prepare_sort_from_pathkeys on it before we do so on the individual
-	 * child plans, to make cross-checking the sort info easier.
-	 */
+	node = make_append(node_type, tlist, best_path->partitioned_rels);
+	plan = &node->plan;
 	copy_generic_path_info(plan, (Path *) best_path);
 	plan->targetlist = tlist;
-	plan->qual = NIL;
-	plan->lefttree = NULL;
-	plan->righttree = NULL;
 
-	/* Compute sort column info, and adjust MergeAppend's tlist as needed */
 	(void) prepare_sort_from_pathkeys(plan, pathkeys,
 									  best_path->path.parent->relids,
 									  NULL,
@@ -1096,70 +1043,18 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path)
 									  &node->collations,
 									  &node->nullsFirst);
 
-	/*
-	 * Now prepare the child plans.  We must apply prepare_sort_from_pathkeys
-	 * even to subplans that don't need an explicit sort, to make sure they
-	 * are returning the same sort key columns the MergeAppend expects.
-	 */
-	foreach(subpaths, best_path->subpaths)
+	/* Build the plan for each child */
+ 	foreach(subpaths, best_path->subpaths)
 	{
 		Path	   *subpath = (Path *) lfirst(subpaths);
-		Plan	   *subplan;
-		int			numsortkeys;
-		AttrNumber *sortColIdx;
-		Oid		   *sortOperators;
-		Oid		   *collations;
-		bool	   *nullsFirst;
-
-		/* Build the child plan */
-		/* Must insist that all children return the same tlist */
-		subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
-
-		/* Compute sort column info, and adjust subplan's tlist as needed */
-		subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
-											 subpath->parent->relids,
-											 node->sortColIdx,
-											 false,
-											 &numsortkeys,
-											 &sortColIdx,
-											 &sortOperators,
-											 &collations,
-											 &nullsFirst);
-
-		/*
-		 * Check that we got the same sort key information.  We just Assert
-		 * that the sortops match, since those depend only on the pathkeys;
-		 * but it seems like a good idea to check the sort column numbers
-		 * explicitly, to ensure the tlists really do match up.
-		 */
-		Assert(numsortkeys == node->numCols);
-		if (memcmp(sortColIdx, node->sortColIdx,
-				   numsortkeys * sizeof(AttrNumber)) != 0)
-			elog(ERROR, "MergeAppend child's targetlist doesn't match MergeAppend");
-		Assert(memcmp(sortOperators, node->sortOperators,
-					  numsortkeys * sizeof(Oid)) == 0);
-		Assert(memcmp(collations, node->collations,
-					  numsortkeys * sizeof(Oid)) == 0);
-		Assert(memcmp(nullsFirst, node->nullsFirst,
-					  numsortkeys * sizeof(bool)) == 0);
-
-		/* Now, insert a Sort node if subplan isn't sufficiently ordered */
-		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;
-		}
 
+		/* TODO: decrease limit tuples for each subpath */
+		Plan *subplan = plan = wrap_sort(root, node, subpath, pathkeys, limit_tuples);
+		if(limit_tuples > 0)
+			limit_tuples = Max(1, limit_tuples - subpath->rows);
 		subplans = lappend(subplans, subplan);
 	}
-
-	node->partitioned_rels = best_path->partitioned_rels;
-	node->mergeplans = subplans;
-
+	node->appendplans = subplans;
 	return (Plan *) node;
 }
 
@@ -1566,7 +1461,7 @@ create_projection_plan(PlannerInfo *root, ProjectionPath *best_path)
 	 * anyway.  Usually create_projection_path will have detected that and set
 	 * dummypp if we don't need a Result; but its decision can't be final,
 	 * because some createplan.c routines change the tlists of their nodes.
-	 * (An example is that create_merge_append_plan might add resjunk sort
+	 * (An example is that create_append_plan might add resjunk sort
 	 * columns to a MergeAppend.)  So we have to recheck here.  If we do
 	 * arrive at a different answer than create_projection_path did, we'll
 	 * have made slightly wrong cost estimates; but label the plan with the
@@ -5274,21 +5169,100 @@ make_foreignscan(List *qptlist,
 }
 
 static Append *
-make_append(List *appendplans, List *tlist, List *partitioned_rels)
+make_append(NodeTag node_type, List *tlist, List *partitioned_rels)
 {
-	Append	   *node = makeNode(Append);
-	Plan	   *plan = &node->plan;
+	Append	   *node;
+	Plan	   *plan;
 
-	plan->targetlist = tlist;
+	if (node_type != T_Append && node_type != T_MergeAppend)
+		elog(ERROR, "create_append_plan can only create Append or MergeAppend plans");
+
+	switch(node_type)
+	{
+		case T_Append:
+			node = makeNode(Append);
+			break;
+		case T_MergeAppend:
+			node = (Append *) makeNode(MergeAppend);
+			break;
+		default:
+			elog(ERROR, "create_append_plan can only create Append or MergeAppend plans");
+	}
+
+	plan = &node->plan;  	plan->targetlist = tlist;
 	plan->qual = NIL;
 	plan->lefttree = NULL;
 	plan->righttree = NULL;
 	node->partitioned_rels = partitioned_rels;
-	node->appendplans = appendplans;
+	node->appendplans = NIL;
+	node->numCols = 0;
+	node->sortColIdx = NULL;
+	node->sortOperators = NULL;
+	node->collations = NULL;
+	node->nullsFirst = NULL;
 
 	return node;
 }
 
+static Plan *
+wrap_sort(PlannerInfo *root, Append* parentplan, Path *subpath, List* pathkeys, double limit_tuples)
+{
+	int			numCols;
+	AttrNumber *sortColIdx;
+	Oid		   *sortOperators;
+	Oid		   *collations;
+	bool	   *nullsFirst;
+	Plan	   *subplan;
+
+	/* Build the child plan */
+	/* Must insist that all children return the same tlist */
+	subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
+
+	if (pathkeys != NIL)
+	{
+		/* Compute sort column info, and adjust subplan's tlist as needed */
+		subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
+											 subpath->parent->relids,
+											 parentplan->sortColIdx,
+											 false,
+											 &numCols,
+											 &sortColIdx,
+											 &sortOperators,
+											 &collations,
+											 &nullsFirst);
+
+		/*
+		 * Check that we got the same sort key information.  We just Assert
+		 * that the sortops match, since those depend only on the pathkeys;
+		 * but it seems like a good idea to check the sort column numbers
+		 * explicitly, to ensure the tlists really do match up.
+		 */
+		Assert(numCols == parentplan->numCols);
+		if (memcmp(sortColIdx, parentplan->sortColIdx,
+					numCols * sizeof(AttrNumber)) != 0)
+			elog(ERROR, "MergeAppend child's targetlist doesn't match MergeAppend");
+		Assert(memcmp(sortOperators, parentplan->sortOperators,
+					numCols * sizeof(Oid)) == 0);
+		Assert(memcmp(collations, parentplan->collations,
+					numCols * sizeof(Oid)) == 0);
+		Assert(memcmp(nullsFirst, parentplan->nullsFirst,
+					numCols * sizeof(bool)) == 0);
+
+		/* Now, insert a Sort node if subplan isn't sufficiently ordered */
+		if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
+		{
+			Sort	   *sort = make_sort(subplan, numCols,
+										 sortColIdx, sortOperators,
+										 collations, nullsFirst);
+
+			label_sort_with_costsize(root, sort, limit_tuples);
+			subplan = (Plan *) sort;
+		}
+	}
+
+	return subplan;
+}
+
 static RecursiveUnion *
 make_recursive_union(List *tlist,
 					 Plan *lefttree,
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index f4e0a6ea3d..acf87cc917 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -25,6 +25,7 @@
 #include "optimizer/pathnode.h"
 #include "optimizer/paths.h"
 #include "optimizer/placeholder.h"
+#include "optimizer/plancat.h"
 #include "optimizer/planmain.h"
 
 
@@ -176,6 +177,13 @@ query_planner(PlannerInfo *root, List *tlist,
 	 */
 	(*qp_callback) (root, qp_extra);
 
+	/*
+	 * We consider generating pathkeys for partitioned tables only if the
+	 * query has some ordering
+	 */
+	if (root->query_pathkeys != NIL)
+		generate_pathkeys_for_partitioned_tables(root);
+
 	/*
 	 * Examine any "placeholder" expressions generated during subquery pullup.
 	 * Make sure that the Vars they need are marked as needed at the relevant
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 7f146d670c..175088313b 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -3643,10 +3643,12 @@ create_grouping_paths(PlannerInfo *root,
 				paths = lappend(paths, path);
 			}
 			path = (Path *)
-				create_append_path(grouped_rel,
+				create_append_path(root,
+								   grouped_rel,
 								   paths,
 								   NULL,
 								   0,
+								   NIL,
 								   NIL);
 			path->pathtarget = target;
 		}
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index b0c9e94459..c9280af5c1 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -932,12 +932,12 @@ set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset)
 				 * targetlist or check quals.
 				 */
 				set_dummy_tlist_references(plan, rtoffset);
-				Assert(splan->plan.qual == NIL);
-				foreach(l, splan->partitioned_rels)
+				Assert(splan->plan.plan.qual == NIL);
+				foreach(l, splan->plan.partitioned_rels)
 				{
 					lfirst_int(l) += rtoffset;
 				}
-				foreach(l, splan->mergeplans)
+				foreach(l, splan->plan.appendplans)
 				{
 					lfirst(l) = set_plan_refs(root,
 											  (Plan *) lfirst(l),
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 1103984779..19fc190f7d 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -2589,7 +2589,7 @@ finalize_plan(PlannerInfo *root, Plan *plan,
 			{
 				ListCell   *l;
 
-				foreach(l, ((MergeAppend *) plan)->mergeplans)
+				foreach(l, ((MergeAppend *) plan)->plan.appendplans)
 				{
 					context.paramids =
 						bms_add_members(context.paramids,
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index 3e0c3de86d..fc615a4314 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -590,7 +590,7 @@ generate_union_path(SetOperationStmt *op, PlannerInfo *root,
 	/*
 	 * Append the child results together.
 	 */
-	path = (Path *) create_append_path(result_rel, pathlist, NULL, 0, NIL);
+	path = (Path *) create_append_path(root, result_rel, pathlist, NULL, 0, NIL, NIL);
 
 	/* We have to manually jam the right tlist into the path; ick */
 	path->pathtarget = create_pathtarget(root, tlist);
@@ -702,7 +702,7 @@ generate_nonunion_path(SetOperationStmt *op, PlannerInfo *root,
 	/*
 	 * Append the child results together.
 	 */
-	path = (Path *) create_append_path(result_rel, pathlist, NULL, 0, NIL);
+	path = (Path *) create_append_path(root, result_rel, pathlist, NULL, 0, NIL, NIL);
 
 	/* We have to manually jam the right tlist into the path; ick */
 	path->pathtarget = create_pathtarget(root, tlist);
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 26567cb7f6..899769eca4 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1200,11 +1200,21 @@ create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals,
  * Note that we must handle subpaths = NIL, representing a dummy access path.
  */
 AppendPath *
-create_append_path(RelOptInfo *rel, List *subpaths, Relids required_outer,
-				   int parallel_workers, List *partitioned_rels)
+create_append_path(PlannerInfo *root, RelOptInfo *rel, List *subpaths,
+				   Relids required_outer, int parallel_workers,
+				   List *partitioned_rels, List *pathkeys)
 {
 	AppendPath *pathnode = makeNode(AppendPath);
 	ListCell   *l;
+	double		limit_tuples;
+	Cost		input_startup_cost;
+	Cost		input_total_cost;
+
+	/*
+	 * Just to make sure that nobody is trying to build a parallel sorted
+	 * append path
+	 */
+	Assert(parallel_workers > 0 ? pathkeys == NIL : true);
 
 	pathnode->path.pathtype = T_Append;
 	pathnode->path.parent = rel;
@@ -1214,7 +1224,7 @@ create_append_path(RelOptInfo *rel, List *subpaths, Relids required_outer,
 	pathnode->path.parallel_aware = false;
 	pathnode->path.parallel_safe = rel->consider_parallel;
 	pathnode->path.parallel_workers = parallel_workers;
-	pathnode->path.pathkeys = NIL;	/* result is always considered unsorted */
+	pathnode->path.pathkeys = pathkeys;
 	pathnode->partitioned_rels = list_copy(partitioned_rels);
 	pathnode->subpaths = subpaths;
 
@@ -1229,15 +1239,49 @@ create_append_path(RelOptInfo *rel, List *subpaths, Relids required_outer,
 	pathnode->path.rows = 0;
 	pathnode->path.startup_cost = 0;
 	pathnode->path.total_cost = 0;
+
+	if (root && bms_equal(rel->relids, root->all_baserels))
+		pathnode->limit_tuples = root->limit_tuples;
+	else
+		pathnode->limit_tuples = -1.0;
+
+	limit_tuples = pathnode->limit_tuples;
+
 	foreach(l, subpaths)
 	{
 		Path	   *subpath = (Path *) lfirst(l);
+		input_startup_cost = subpath->startup_cost;
+		input_total_cost = subpath->total_cost;
+
+		if(pathkeys && !pathkeys_contained_in(pathkeys, subpath->pathkeys))
+		{
+			Path		sort_path;		/* dummy for result of cost_sort */
+
+			cost_sort(&sort_path,
+					root,
+					pathkeys,
+					subpath->total_cost,
+					subpath->rows,
+					subpath->pathtarget->width,
+					0.0,
+					work_mem,
+					limit_tuples);
+			input_startup_cost += sort_path.startup_cost;
+			input_total_cost = sort_path.total_cost;
+		}
 
 		pathnode->path.rows += subpath->rows;
 
 		if (l == list_head(subpaths))	/* first node? */
-			pathnode->path.startup_cost = subpath->startup_cost;
-		pathnode->path.total_cost += subpath->total_cost;
+			pathnode->path.startup_cost = input_startup_cost;
+		/*
+		 * Consider that the number of tuples to be fetched decreases
+		 * for every subsequent partition
+		 */
+		if(limit_tuples > 0)
+			limit_tuples = Max(1, limit_tuples - subpath->rows);
+
+		pathnode->path.total_cost += input_total_cost;
 		pathnode->path.parallel_safe = pathnode->path.parallel_safe &&
 			subpath->parallel_safe;
 
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index cac46bedf9..9bd8fb89f4 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -35,6 +35,7 @@
 #include "nodes/makefuncs.h"
 #include "optimizer/clauses.h"
 #include "optimizer/cost.h"
+#include "optimizer/paths.h"
 #include "optimizer/plancat.h"
 #include "optimizer/predtest.h"
 #include "optimizer/prep.h"
@@ -1269,6 +1270,142 @@ get_relation_constraints(PlannerInfo *root,
 	return result;
 }
 
+/*
+ * Generate pathkeys for Range-based partitions
+ */
+void
+generate_pathkeys_for_partitioned_tables(PlannerInfo *root)
+{
+	int i;
+	for (i = 1; i < root->simple_rel_array_size; i++)
+	{
+		RelOptInfo *rel = root->simple_rel_array[i];
+
+		/* Only base relation can be partitionned */
+		if (rel && has_useful_pathkeys(root, rel))
+		{
+			Index varno = rel->relid;
+			Index parent_varno = varno;
+			RelOptInfo *parent_rel = rel;
+			Relation relation;
+			RangeTblEntry *rte = planner_rt_fetch(varno, root);
+
+			if (rte->relkind != RELKIND_PARTITIONED_TABLE)
+				continue;
+
+			while (parent_rel->reloptkind != RELOPT_BASEREL)
+			{
+				ListCell *lc;
+
+				foreach(lc, root->append_rel_list)
+				{
+					AppendRelInfo *ari = lfirst(lc);
+
+					if (ari->child_relid == parent_rel->relid)
+					{
+						parent_rel = root->simple_rel_array[ari->parent_relid];
+						break;
+					}
+
+					/* Should never happen: we should always be able to climb up the
+					 *  inheritance tree */
+					if(!lc)
+						elog(ERROR, "Unable to find parent table for child ");
+				}
+			}
+			parent_varno = parent_rel->relid;
+
+			/*
+			 * Ignore base rel if it's not a partitionned table. We'll still
+			 * have to open it to verify if it's a range partitionned table
+			 */
+			if (rte->relkind != RELKIND_PARTITIONED_TABLE)
+				continue;
+
+			relation = heap_open(rte->relid, NoLock);
+
+			/*
+			 * If the partitioning has natural data ordering (ie. a range
+			 * strategy and no default partition), build pathkeys
+			 * for the partitioning keys
+			 */
+			if(relation->rd_partkey->strategy == PARTITION_STRATEGY_RANGE &&
+			    get_default_oid_from_partdesc(relation->rd_partdesc) == InvalidOid)
+			{
+				int j;
+				ListCell *lc;
+				Oid equality_op;
+				EquivalenceClass *ec;
+				List *opfamilies;
+				List *asc_pathkeys = NIL;
+				List *desc_pathkeys = NIL;
+
+				Assert(rel->part_pathkeys == NIL);
+
+				/* Lookup individual vars from the pathtarget */
+				/* FIXME: refactor this in an external function */
+				lc = list_head(relation->rd_partkey->partexprs);
+				for (j=0; j < relation->rd_partkey->partnatts; j++)
+				{
+					AttrNumber attno = relation->rd_partkey->partattrs[j];
+					Expr *expr = NULL;
+
+					/* This is not an attribute, but an expression */
+					if(attno == InvalidAttrNumber)
+					{
+						/* Should never append : we should be able to fetch
+						 * an expression for anything in the partition key */
+						if (!lc)
+							elog(ERROR, "Could not find expression for partition key");
+						expr = lfirst(lc);
+						lc = lnext(lc);
+					}
+					else
+					{
+						expr = (Expr*) makeVar(parent_varno, attno, relation->rd_partkey->parttypid[j],
+									  relation->rd_partkey->parttypmod[j],
+									  relation->rd_partkey->parttypcoll[j],
+									  0);
+					}
+
+					equality_op = get_opfamily_member(relation->rd_partkey->partopfamily[j],
+																		  relation->rd_partkey->partopcintype[j],
+																		  relation->rd_partkey->partopcintype[j],
+																		  BTEqualStrategyNumber);
+					opfamilies = get_mergejoin_opfamilies(equality_op);
+					ec = get_eclass_for_sort_expr(root, expr,
+							NULL, opfamilies,
+							relation->rd_partkey->partopcintype[j],
+							relation->rd_partkey->partcollation[j],
+							0, rel->relids, true);
+					asc_pathkeys = lappend(asc_pathkeys,  make_canonical_pathkey(root,
+							ec,
+							relation->rd_partkey->partopfamily[j],
+							BTLessStrategyNumber, false));
+					desc_pathkeys  = lappend(desc_pathkeys, make_canonical_pathkey(root,
+							ec,
+							relation->rd_partkey->partopfamily[j],
+							BTGreaterStrategyNumber, true));
+				}
+
+				/* FIXME: this is as dirty as it gets */
+				if(list_length(asc_pathkeys) > list_length(root->query_pathkeys))
+				{
+					asc_pathkeys = truncate_useless_pathkeys(root, rel, asc_pathkeys);
+					desc_pathkeys = truncate_useless_pathkeys(root, rel, desc_pathkeys);
+				}
+
+				if(asc_pathkeys)
+					rel->part_pathkeys = lappend(rel->part_pathkeys, asc_pathkeys);
+
+				if(desc_pathkeys)
+					rel->part_pathkeys = lappend(rel->part_pathkeys, desc_pathkeys);
+			}
+			heap_close(relation, NoLock);
+		}
+	}
+}
+
 /*
  * get_relation_statistics
  *		Retrieve extended statistics defined on the table.
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 077e89ae43..86ecf70cc2 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -151,6 +151,7 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
 	rel->boundinfo = NULL;
 	rel->part_rels = NULL;
 	rel->partexprs = NULL;
+	rel->part_pathkeys = NIL;
 
 	/*
 	 * Pass top parent's relids down the inheritance hierarchy. If the parent
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index a382331f41..283af54e09 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -248,6 +248,17 @@ typedef struct Append
 	/* RT indexes of non-leaf tables in a partition tree */
 	List	   *partitioned_rels;
 	List	   *appendplans;
+	/* remaining fields are just like the sort-key info in struct Sort */
+	/* FIXME: We should either
+	 * 	- define Append as sort + appendplans
+	 * 	- define Append "like" sort and define MergeAppend as Append, only with
+	 * 	a different tag
+	 */
+	int			numCols;		/* number of sort-key columns */
+	AttrNumber *sortColIdx;		/* their indexes in the target list */
+	Oid		   *sortOperators;	/* OIDs of operators to sort them by */
+	Oid		   *collations;		/* OIDs of collations */
+	bool	   *nullsFirst;		/* NULLS FIRST/LAST directions */
 } Append;
 
 /* ----------------
@@ -257,16 +268,7 @@ typedef struct Append
  */
 typedef struct MergeAppend
 {
-	Plan		plan;
-	/* RT indexes of non-leaf tables in a partition tree */
-	List	   *partitioned_rels;
-	List	   *mergeplans;
-	/* remaining fields are just like the sort-key info in struct Sort */
-	int			numCols;		/* number of sort-key columns */
-	AttrNumber *sortColIdx;		/* their indexes in the target list */
-	Oid		   *sortOperators;	/* OIDs of operators to sort them by */
-	Oid		   *collations;		/* OIDs of collations */
-	bool	   *nullsFirst;		/* NULLS FIRST/LAST directions */
+	Append 		plan;
 } MergeAppend;
 
 /* ----------------
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 48e6012f7f..81c962d91b 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -646,6 +646,8 @@ typedef struct RelOptInfo
 	struct RelOptInfo **part_rels;	/* Array of RelOptInfos of partitions,
 									 * stored in the same order of bounds */
 	List	  **partexprs;		/* Partition key expressions. */
+	List	   *part_pathkeys;	/* Pathkey representing the  partition key if a
+								   natural order exists*/
 } RelOptInfo;
 
 /*
@@ -1232,6 +1234,7 @@ typedef struct AppendPath
 	/* RT indexes of non-leaf tables in a partition tree */
 	List	   *partitioned_rels;
 	List	   *subpaths;		/* list of component Paths */
+	double		limit_tuples;	/* hard limit on output tuples, or -1 */
 } AppendPath;
 
 #define IS_DUMMY_PATH(p) \
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index e372f8862b..1496bdc0dc 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -63,9 +63,13 @@ extern BitmapOrPath *create_bitmap_or_path(PlannerInfo *root,
 					  List *bitmapquals);
 extern TidPath *create_tidscan_path(PlannerInfo *root, RelOptInfo *rel,
 					List *tidquals, Relids required_outer);
-extern AppendPath *create_append_path(RelOptInfo *rel, List *subpaths,
-				   Relids required_outer, int parallel_workers,
-				   List *partitioned_rels);
+extern AppendPath *create_append_path(PlannerInfo *root,
+				   RelOptInfo *rel,
+				   List *subpaths,
+				   Relids required_outer,
+				   int parallel_workers,
+				   List *partitioned_rels,
+				   List *pathkeys);
 extern MergeAppendPath *create_merge_append_path(PlannerInfo *root,
 						 RelOptInfo *rel,
 						 List *subpaths,
diff --git a/src/include/optimizer/plancat.h b/src/include/optimizer/plancat.h
index 71f0faf938..6d96d54b5d 100644
--- a/src/include/optimizer/plancat.h
+++ b/src/include/optimizer/plancat.h
@@ -35,6 +35,8 @@ extern void estimate_rel_size(Relation rel, int32 *attr_widths,
 
 extern int32 get_relation_data_width(Oid relid, int32 *attr_widths);
 
+extern void generate_pathkeys_for_partitioned_tables(PlannerInfo *root);
+
 extern bool relation_excluded_by_constraints(PlannerInfo *root,
 								 RelOptInfo *rel, RangeTblEntry *rte);
 
diff --git a/src/test/regress/expected/inherit.out b/src/test/regress/expected/inherit.out
index c698faff2f..03d9cbb242 100644
--- a/src/test/regress/expected/inherit.out
+++ b/src/test/regress/expected/inherit.out
@@ -1952,13 +1952,13 @@ explain (costs off) select min(a), max(a) from parted_minmax where b = '12345';
  Result
    InitPlan 1 (returns $0)
      ->  Limit
-           ->  Merge Append
+           ->  Append
                  Sort Key: parted_minmax1.a
                  ->  Index Only Scan using parted_minmax1i on parted_minmax1
                        Index Cond: ((a IS NOT NULL) AND (b = '12345'::text))
    InitPlan 2 (returns $1)
      ->  Limit
-           ->  Merge Append
+           ->  Append
                  Sort Key: parted_minmax1_1.a DESC
                  ->  Index Only Scan Backward using parted_minmax1i on parted_minmax1 parted_minmax1_1
                        Index Cond: ((a IS NOT NULL) AND (b = '12345'::text))