merge_append_2010_09_29.patch

diff --git a/src/backend/executor/nodeAppend.c b/src/backend/executor/nodeAppend.c
index 4f3d899..94359bb 100644
--- a/src/backend/executor/nodeAppend.c
+++ b/src/backend/executor/nodeAppend.c
@@ -59,9 +59,25 @@
 
 #include "executor/execdebug.h"
 #include "executor/nodeAppend.h"
+#include "utils/lsyscache.h"
+#include "access/nbtree.h"
+
+/* It gets quite confusing having a heap array (indexed by integers) which
+ * contains integers which index into the slots array. These typedefs try to
+ * clear it up but without making simple inline accessing functions they don't
+ * actually produce any warnings on mistakes */
+
+typedef int SlotNumber;
+typedef int HeapPosition;
+
+#define WHICHPLAN_PLANS_UNINITIALIZED (-1)
 
 static bool exec_append_initialize_next(AppendState *appendstate);
 
+static int heap_compare_slots(AppendState *node, SlotNumber slot1, SlotNumber slot2);
+
+static void heap_siftup_slot(AppendState *node);
+static void heap_insert_slot(AppendState *node, SlotNumber new_slot);
 
 /* ----------------------------------------------------------------
  *		exec_append_initialize_next
@@ -142,6 +158,7 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
 	appendstate->ps.state = estate;
 	appendstate->appendplans = appendplanstates;
 	appendstate->as_nplans = nplans;
+	appendstate->as_is_ordered = node->isOrdered;
 
 	/*
 	 * Miscellaneous initialization
@@ -175,11 +192,53 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
 	ExecAssignResultTypeFromTL(&appendstate->ps);
 	appendstate->ps.ps_ProjInfo = NULL;
 
-	/*
-	 * initialize to scan first subplan
-	 */
-	appendstate->as_whichplan = 0;
-	exec_append_initialize_next(appendstate);
+	if (!appendstate->as_is_ordered)
+	{
+		/*
+		 * initialize to scan first subplan
+		 */
+		appendstate->as_whichplan = 0;
+		exec_append_initialize_next(appendstate);
+	}
+	else
+	{
+		/* set up scan keys and initialize *all* the subnodes */
+		int i;
+
+		appendstate->as_nkeys = node->numCols;
+		appendstate->as_scankeys = palloc(sizeof(ScanKeyData) *  node->numCols);
+		appendstate->as_slots = palloc(sizeof(TupleTableSlot *) * nplans);
+		appendstate->as_heap = palloc(sizeof(int) * nplans);
+		appendstate->as_heap_size = 0;
+
+		for (i=0; i < nplans; i++)
+		{
+			appendstate->as_whichplan = i;
+			exec_append_initialize_next(appendstate);
+		}
+
+		appendstate->as_whichplan = WHICHPLAN_PLANS_UNINITIALIZED;
+
+		for (i = 0; i < node->numCols; i++)
+		{
+			Oid sortFunction;
+			bool reverse;
+
+			get_compare_function_for_ordering_op(node->sortOperators[i],
+												 &sortFunction, &reverse);
+
+			ScanKeyInit(&appendstate->as_scankeys[i],
+						node->sortColIdx[i],
+						InvalidStrategy,
+						sortFunction,
+						(Datum)0);
+
+			if (reverse)
+				appendstate->as_scankeys[i].sk_flags |= SK_BT_DESC;
+			if (node->nullsFirst[i])
+				appendstate->as_scankeys[i].sk_flags |= SK_BT_NULLS_FIRST;
+		}
+	}
 
 	return appendstate;
 }
@@ -193,45 +252,169 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
 TupleTableSlot *
 ExecAppend(AppendState *node)
 {
-	for (;;)
+	if (!node->as_is_ordered)
 	{
-		PlanState  *subnode;
-		TupleTableSlot *result;
+		for (;;)
+		{
+			PlanState  *subnode;
+			TupleTableSlot *result;
 
-		/*
-		 * figure out which subplan we are currently processing
-		 */
-		subnode = node->appendplans[node->as_whichplan];
+			/*
+			 * figure out which subplan we are currently processing
+			 */
+			subnode = node->appendplans[node->as_whichplan];
 
-		/*
-		 * get a tuple from the subplan
-		 */
-		result = ExecProcNode(subnode);
+			/*
+			 * get a tuple from the subplan
+			 */
+			result = ExecProcNode(subnode);
+
+			if (!TupIsNull(result))
+			{
+				/*
+				 * If the subplan gave us something then return it as-is. We do
+				 * NOT make use of the result slot that was set up in
+				 * ExecInitAppend; there's no need for it.
+				 */
+				return result;
+			}
 
-		if (!TupIsNull(result))
-		{
 			/*
-			 * If the subplan gave us something then return it as-is. We do
-			 * NOT make use of the result slot that was set up in
-			 * ExecInitAppend; there's no need for it.
+			 * Go on to the "next" subplan in the appropriate direction. If no
+			 * more subplans, return the empty slot set up for us by
+			 * ExecInitAppend.
 			 */
-			return result;
+			if (ScanDirectionIsForward(node->ps.state->es_direction))
+				node->as_whichplan++;
+			else
+				node->as_whichplan--;
+			if (!exec_append_initialize_next(node))
+				return ExecClearTuple(node->ps.ps_ResultTupleSlot);
+
+			/* Else loop back and try to get a tuple from the new subplan */
 		}
+	}
+	else
+	{
+		TupleTableSlot *result;
+		SlotNumber i;
 
-		/*
-		 * Go on to the "next" subplan in the appropriate direction. If no
-		 * more subplans, return the empty slot set up for us by
-		 * ExecInitAppend.
-		 */
-		if (ScanDirectionIsForward(node->ps.state->es_direction))
-			node->as_whichplan++;
-		else
-			node->as_whichplan--;
-		if (!exec_append_initialize_next(node))
-			return ExecClearTuple(node->ps.ps_ResultTupleSlot);
-
-		/* Else loop back and try to get a tuple from the new subplan */
+		if (node->as_whichplan == WHICHPLAN_PLANS_UNINITIALIZED)
+		{
+			for (i = 0; i < node->as_nplans; i++)
+			{
+				node->as_slots[i] = ExecProcNode(node->appendplans[i]);
+				if (!TupIsNull(node->as_slots[i]))
+					heap_insert_slot(node, i);
+			}
+                }
+                else
+                {
+                	i = node->as_whichplan;
+                	node->as_slots[i] = ExecProcNode(node->appendplans[i]);
+                	if (TupIsNull(node->as_slots[i]))
+                		;
+			else if (node->as_heap_size <= 0 || heap_compare_slots(node, node->as_heap[0], i) >= 0)
+				return node->as_slots[i];
+			else 
+				heap_insert_slot(node, i);
+                }
+
+                if (node->as_heap_size > 0)
+                {
+                	i = node->as_heap[0];
+                	node->as_whichplan = i;
+                	heap_siftup_slot(node);
+                	result = node->as_slots[i];
+		} else {
+			result = ExecClearTuple(node->ps.ps_ResultTupleSlot);
+		}
+
+		return result;
+	}
+}
+
+static void
+heap_insert_slot(AppendState *node, SlotNumber new_slot)
+{
+	HeapPosition j;
+	SlotNumber *heap;
+
+	Assert(!TupIsNull(node->as_slots[new_slot]));
+
+	j = node->as_heap_size++;
+	heap = node->as_heap;
+
+	while (j > 0)
+	{
+		int i = (j-1)/2;
+		if (heap_compare_slots(node, new_slot, node->as_heap[i]) >= 0)
+			break;
+		heap[j] = heap[i];
+		j = i;
+	}
+	heap[j] = new_slot;
+}
+
+static void
+heap_siftup_slot(AppendState *node)
+{
+	HeapPosition i=0, j, n;
+
+	if (--node->as_heap_size <= 0)
+		return;
+	n = node->as_heap_size;
+
+	for (;;)
+	{
+		j = 2 * i + 1;
+		if (j >= n)
+			break;
+		if (j+1 < n && heap_compare_slots(node, node->as_heap[j], node->as_heap[j+1]) > 0)
+			j++;
+		if (heap_compare_slots(node, node->as_heap[n], node->as_heap[j]) <= 0)
+			break;
+		node->as_heap[i] = node->as_heap[j];
+		i = j;
+	}
+	node->as_heap[i] = node->as_heap[n];
+}
+
+static int
+heap_compare_slots(AppendState *node, SlotNumber slot1, SlotNumber slot2)
+{
+	int nkey;
+	TupleTableSlot *s1, *s2;
+
+	Assert(slot1 < node->as_nplans);
+	Assert(slot2 < node->as_nplans);
+
+	s1 = node->as_slots[slot1];
+	s2 = node->as_slots[slot2];
+	Assert(!TupIsNull(s1));
+	Assert(!TupIsNull(s2));
+
+	for (nkey = 0; nkey < node->as_nkeys; nkey++)
+	{
+		ScanKey scankey = node->as_scankeys + nkey;
+		AttrNumber attno = scankey->sk_attno;
+		Datum d1, d2;
+		bool  n1, n2;
+		int compare;
+
+		d1 = slot_getattr(s1, attno, &n1);
+		d2 = slot_getattr(s2, attno, &n2);
+
+		if (n1 && !n2)
+			return (scankey->sk_flags & SK_BT_NULLS_FIRST) ? -1 :  1;
+		if (!n1 && n2)
+			return (scankey->sk_flags & SK_BT_NULLS_FIRST) ?  1 : -1;
+
+		compare = FunctionCall2(&scankey->sk_func, d1, d2);
+		if (compare != 0)
+			return (scankey->sk_flags & SK_BT_DESC) ? -compare : compare;
 	}
+	return 0;
 }
 
 /* ----------------------------------------------------------------
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index b7cf0b8..b8d5a80 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -51,7 +51,8 @@ static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 					   RangeTblEntry *rte);
 static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 						Index rti, RangeTblEntry *rte);
-static void set_dummy_rel_pathlist(RelOptInfo *rel);
+static List *accumulate_append_subpath(List *subpaths, Path *path);
+static void set_dummy_rel_pathlist(PlannerInfo *root, RelOptInfo *rel);
 static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 					  Index rti, RangeTblEntry *rte);
 static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel,
@@ -222,7 +223,7 @@ set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
 	if (rel->reloptkind == RELOPT_BASEREL &&
 		relation_excluded_by_constraints(root, rel, rte))
 	{
-		set_dummy_rel_pathlist(rel);
+		set_dummy_rel_pathlist(root, rel);
 		return;
 	}
 
@@ -283,12 +284,13 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 						Index rti, RangeTblEntry *rte)
 {
 	int			parentRTindex = rti;
-	List	   *subpaths = NIL;
+	List	   *best_subpaths = NIL;	/* list of paths */
+	List	   *all_pathkeys = NIL;		/* union of all pathkeys in sub paths */
 	double		parent_rows;
 	double		parent_size;
 	double	   *parent_attrsizes;
 	int			nattrs;
-	ListCell   *l;
+	ListCell   *l, *ll, *lll;
 
 	/*
 	 * Initialize to compute size estimates for whole append relation.
@@ -366,7 +368,7 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 			 * Restriction reduces to constant FALSE or constant NULL after
 			 * substitution, so this child need not be scanned.
 			 */
-			set_dummy_rel_pathlist(childrel);
+			set_dummy_rel_pathlist(root, childrel);
 			continue;
 		}
 		childquals = make_ands_implicit((Expr *) childqual);
@@ -381,7 +383,7 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 			 * appendrel.  Mark it with a dummy cheapest-path though, in case
 			 * best_appendrel_indexscan() looks at it later.
 			 */
-			set_dummy_rel_pathlist(childrel);
+			set_dummy_rel_pathlist(root, childrel);
 			continue;
 		}
 
@@ -394,14 +396,22 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 								   appinfo);
 
 		/*
-		 * We have to make child entries in the EquivalenceClass data
-		 * structures as well.
+		 * If the parent has useful pathkeys, we can obtain the data for each
+		 * child in sorted order and then perform a final merge pass in the
+		 * Append node.  In order to construct a suitable sort or index scan
+		 * on a given child, the EquivalenceClass data structures for the
+		 * parent will need suitably-adjusted EquivalenceMember entries for
+		 * that child.  We will also need these child entries if we're trying
+		 * to "push down" an inner index-scan to each child rel.  However, a
+		 * separate test for that case isn't necessary here, because we only
+		 * care about pushing down eclass joins, and if there is such a join
+		 * then there will be useful pathkeys, because we could also handle the
+		 * same join as a merge join.
 		 */
-		if (rel->has_eclass_joins)
-		{
+		if (has_useful_pathkeys(root, rel))
 			add_child_rel_equivalences(root, appinfo, rel, childrel);
+		if (rel->has_eclass_joins)
 			childrel->has_eclass_joins = true;
-		}
 
 		/*
 		 * Note: we could compute appropriate attr_needed data for the child's
@@ -413,21 +423,34 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 
 		/*
 		 * Compute the child's access paths, and add the cheapest one to the
-		 * Append path we are constructing for the parent.
-		 *
-		 * It's possible that the child is itself an appendrel, in which case
-		 * we can "cut out the middleman" and just add its child paths to our
-		 * own list.  (We don't try to do this earlier because we need to
-		 * apply both levels of transformation to the quals.)
+ 		 * list of cheap paths (best_paths) and the pathkeys of all the paths
+ 		 * to the union, all_pathkeys.
 		 */
 		set_rel_pathlist(root, childrel, childRTindex, childRTE);
 
 		childpath = childrel->cheapest_total_path;
-		if (IsA(childpath, AppendPath))
-			subpaths = list_concat(subpaths,
-							list_copy(((AppendPath *) childpath)->subpaths));
-		else
-			subpaths = lappend(subpaths, childpath);
+ 		best_subpaths = accumulate_append_subpath(best_subpaths, childpath);
+
+		/* gather up all the pathkeys of all sub-paths
+		 * FIXME -- this is O(n^2)!
+		 */
+		foreach(ll, childrel->pathlist)
+		{
+			ListCell *lll;
+			Path *childpath = (Path *) lfirst(ll);
+			bool found = false;
+			
+			foreach (lll, all_pathkeys)
+			{
+				List *existing_pathkeys = (List *)lfirst(lll);
+ 
+				if (compare_pathkeys(existing_pathkeys,
+									 childpath->pathkeys) == PATHKEYS_EQUAL)
+					found = true;
+			}
+			if (!found)
+				all_pathkeys = lappend(all_pathkeys, childpath->pathkeys);
+		}
 
 		/*
 		 * Accumulate size information from each child.
@@ -483,14 +506,89 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
 	pfree(parent_attrsizes);
 
 	/*
-	 * Finally, build Append path and install it as the only access path for
-	 * the parent rel.	(Note: this is correct even if we have zero or one
-	 * live subpath due to constraint exclusion.)
+	 * First, build unordered Append path for the parent rel.	(Note: this is
+	 * correct even if we have zero or one live subpath due to constraint
+	 * exclusion.)
 	 */
-	add_path(rel, (Path *) create_append_path(rel, subpaths));
+	add_path(rel, (Path *) create_append_path(root, rel, best_subpaths, NIL));
 
-	/* Select cheapest path (pretty easy in this case...) */
-	set_cheapest(rel);
+	/*
+	 * Next, attempt to add ordered append paths based on the collected list
+	 * of child pathkeys.
+	 */
+	foreach (ll, all_pathkeys)
+	{
+		List *pathkeys = (List *)lfirst(ll);
+		List *startup_subpaths = NIL; /* subpaths for minimal startup cost append path */
+		List *total_subpaths = NIL;   /* subpaths for minimal total cost append path */
+
+		/* populate both subpaths lists based on this pathkeys list */
+		foreach(lll, root->append_rel_list)
+		{
+			AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lll);
+			RelOptInfo *childrel;
+			Path	   *cheapest_startup,
+					   *cheapest_total;
+
+			/* append_rel_list contains all append rels; ignore others */
+			if (appinfo->parent_relid != parentRTindex)
+				continue;
+
+			childrel = find_base_rel(root, appinfo->child_relid);
+			Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
+
+			/* First the cheapest startup cost */
+			cheapest_startup =
+				get_cheapest_path_for_pathkeys(childrel->pathlist, 
+											   pathkeys,
+											   TOTAL_COST);
+			cheapest_total =
+				get_cheapest_path_for_pathkeys(childrel->pathlist, 
+											   pathkeys,
+											   STARTUP_COST);
+
+			/*
+			 * If we can't find any plans with the right order just add the
+			 * cheapest total plan to both paths; we'll have to sort it.
+			 */
+			if (cheapest_startup == NULL)
+			{
+				Assert(cheapest_total == NULL);
+				cheapest_startup = childrel->cheapest_total_path;
+				cheapest_total = childrel->cheapest_total_path;
+			}
+
+			/* Accumulate paths. */
+	 		total_subpaths =
+				accumulate_append_subpath(total_subpaths, cheapest_startup);
+	 		startup_subpaths =
+				accumulate_append_subpath(startup_subpaths, cheapest_total);
+		}
+
+		add_path(rel, (Path *) create_append_path(root, rel, startup_subpaths, pathkeys));
+		add_path(rel, (Path *) create_append_path(root, rel, total_subpaths, pathkeys));
+	}
+
+	/* Select cheapest path */
+  	set_cheapest(rel);
+}
+
+/*
+ * It's possible that the child is itself an appendrel, in which case
+ * we can "cut out the middleman" and just add its child paths to our
+ * own list.  (We don't try to do this earlier because we need to
+ * apply both levels of transformation to the quals.)
+ */
+static List *
+accumulate_append_subpath(List *subpaths, Path *path)
+{
+	if (IsA(path, AppendPath))
+	{
+		AppendPath *apath = (AppendPath *) path;
+		return list_concat(subpaths, list_copy(apath->subpaths));
+	}
+	else
+		return lappend(subpaths, path);
 }
 
 /*
@@ -501,13 +599,13 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
  * AppendPath with no members (see also IS_DUMMY_PATH macro).
  */
 static void
-set_dummy_rel_pathlist(RelOptInfo *rel)
+set_dummy_rel_pathlist(PlannerInfo *root, RelOptInfo *rel)
 {
 	/* Set dummy size estimates --- we leave attr_widths[] as zeroes */
 	rel->rows = 0;
 	rel->width = 0;
 
-	add_path(rel, (Path *) create_append_path(rel, NIL));
+	add_path(rel, (Path *) create_append_path(root, rel, NIL, NIL));
 
 	/* Select cheapest path (pretty easy in this case...) */
 	set_cheapest(rel);
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index a20ed5f..e44e960 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -1611,8 +1611,8 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
  *	  Search for EC members that reference (only) the parent_rel, and
  *	  add transformed members referencing the child_rel.
  *
- * We only need to do this for ECs that could generate join conditions,
- * since the child members are only used for creating inner-indexscan paths.
+ * Note that this function won't be called at all unless we have at least some
+ * reason to believe that the EC members it generates will be useful.
  *
  * parent_rel and child_rel could be derived from appinfo, but since the
  * caller has already computed them, we might as well just pass them in.
@@ -1631,10 +1631,14 @@ add_child_rel_equivalences(PlannerInfo *root,
 		ListCell   *lc2;
 
 		/*
-		 * Won't generate joinclauses if const or single-member (the latter
-		 * test covers the volatile case too)
+		 * If this EC contains a constant, then it's not useful for sorting
+		 * or driving an inner index-scan, so we skip generating child EMs.
+		 *
+		 * If this EC contains a volatile expression, then generating child
+		 * EMs would be downright dangerous.  We rely on a volatile EC having
+		 * only one EM.
 		 */
-		if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
+		if (cur_ec->ec_has_const || cur_ec->ec_has_volatile)
 			continue;
 
 		/* No point in searching if parent rel not mentioned in eclass */
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index ab3b9cd..a333b87 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -955,7 +955,7 @@ best_appendrel_indexscan(PlannerInfo *root, RelOptInfo *rel,
 		return NULL;
 
 	/* Form and return the completed Append path. */
-	return (Path *) create_append_path(rel, append_paths);
+	return (Path *) create_append_path(root, rel, append_paths, NIL);
 }
 
 /*
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 197c49d..d9a2c7d 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -945,7 +945,7 @@ mark_dummy_rel(RelOptInfo *rel)
 	rel->pathlist = NIL;
 
 	/* Set up the dummy path */
-	add_path(rel, (Path *) create_append_path(rel, NIL));
+	add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL));
 
 	/* Set or update cheapest_total_path */
 	set_cheapest(rel);
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index fa7b29f..23efbad 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -24,6 +24,7 @@
 #include "nodes/nodeFuncs.h"
 #include "optimizer/clauses.h"
 #include "optimizer/cost.h"
+#include "optimizer/paths.h"
 #include "optimizer/plancat.h"
 #include "optimizer/planmain.h"
 #include "optimizer/predtest.h"
@@ -609,11 +610,19 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path)
 	foreach(subpaths, best_path->subpaths)
 	{
 		Path	   *subpath = (Path *) lfirst(subpaths);
+		Plan	   *subplan;
 
-		subplans = lappend(subplans, create_plan_recurse(root, subpath));
+		subplan = create_plan_recurse(root, subpath);
+		if (!pathkeys_contained_in(best_path->path.pathkeys, subpath->pathkeys))
+			subplan = (Plan *)make_sort_from_pathkeys(root,
+													  subplan,
+													  best_path->path.pathkeys,
+													  -1.0);
+
+		subplans = lappend(subplans, subplan);
 	}
 
-	plan = make_append(subplans, tlist);
+	plan = make_append(root, subplans, tlist, best_path->path.pathkeys);
 
 	return (Plan *) plan;
 }
@@ -2784,7 +2793,8 @@ make_worktablescan(List *qptlist,
 }
 
 Append *
-make_append(List *appendplans, List *tlist)
+make_append(PlannerInfo *root, List *appendplans,
+				   List *tlist, List *pathkeys)
 {
 	Append	   *node = makeNode(Append);
 	Plan	   *plan = &node->plan;
@@ -2792,9 +2802,11 @@ make_append(List *appendplans, List *tlist)
 	ListCell   *subnode;
 
 	/*
-	 * Compute cost as sum of subplan costs.  We charge nothing extra for the
-	 * Append itself, which perhaps is too optimistic, but since it doesn't do
-	 * any selection or projection, it is a pretty cheap node.
+	 * Compute cost as sum of subplan costs. We charge nothing extra for a
+	 * plain Append itself, which perhaps is too optimistic, but since it
+	 * doesn't do any selection or projection, it is a pretty cheap node. In
+	 * the case of an ordered append we construct an equivalent bounded Sort
+	 * node and steal the cost calculations from it.
 	 */
 	plan->startup_cost = 0;
 	plan->total_cost = 0;
@@ -2804,8 +2816,10 @@ make_append(List *appendplans, List *tlist)
 	{
 		Plan	   *subplan = (Plan *) lfirst(subnode);
 
-		if (subnode == list_head(appendplans))	/* first node? */
-			plan->startup_cost = subplan->startup_cost;
+ 		/* If it's ordered then the startup cost is the sum of the startup
+ 		 * costs, otherwise it's the startup cost of just the first plan */
+ 		if (pathkeys || subnode == list_head(appendplans))
+ 			plan->startup_cost += subplan->startup_cost;
 		plan->total_cost += subplan->total_cost;
 		plan->plan_rows += subplan->plan_rows;
 		total_size += subplan->plan_width * subplan->plan_rows;
@@ -2821,6 +2835,30 @@ make_append(List *appendplans, List *tlist)
 	plan->righttree = NULL;
 	node->appendplans = appendplans;
 
+	if (!pathkeys)
+		node->isOrdered = false;
+	else 
+	{
+		/* generate a throwaway sort node to find the sort functions */
+		Sort *tmp = make_sort_from_pathkeys(root, (Plan*)node, pathkeys, list_length(appendplans));
+		
+		node->isOrdered = true;
+		
+		node->numCols 		= tmp->numCols;
+		node->sortColIdx 	= tmp->sortColIdx;
+		node->sortOperators = tmp->sortOperators;
+		node->nullsFirst 	= tmp->nullsFirst;
+
+		/* a limited sort is the same kind of work (bounded heap sort) as an
+		 * ordered append with the bound set to the number of plans, so we just
+		 * use that to calculate the total cost. The startup cost is just the
+		 * sum of the startup costs of the nodes plus a bit to build the heap
+		 * (similar to processing that many rows in the bounded sort case).
+		 */
+		plan->total_cost = tmp->plan.total_cost - (enable_sort ? 0 : disable_cost);
+		plan->startup_cost += plan->total_cost / plan->plan_rows * list_length(appendplans);
+	}
+
 	return node;
 }
 
@@ -3182,7 +3220,12 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
 			{
 				EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
 
-				if (em->em_is_const || em->em_is_child)
+				/*
+				 * We shouldn't be trying to sort by an equivalence class that
+				 * contains a constant, so no need to consider such cases any
+				 * further.
+				 */
+				if (em->em_is_const)
 					continue;
 
 				tle = tlist_member((Node *) em->em_expr, tlist);
@@ -3218,8 +3261,14 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
 					List	   *exprvars;
 					ListCell   *k;
 
-					if (em->em_is_const || em->em_is_child)
+					/*
+					 * We shouldn't be trying to sort by an equivalence class
+					 * that contains a constant, so no need to consider such
+					 * cases any further.
+					 */
+					if (em->em_is_const)
 						continue;
+
 					sortexpr = em->em_expr;
 					exprvars = pull_var_clause((Node *) sortexpr,
 											   PVC_INCLUDE_PLACEHOLDERS);
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index f904258..b7039b1 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -449,7 +449,7 @@ generate_union_plan(SetOperationStmt *op, PlannerInfo *root,
 	/*
 	 * Append the child results together.
 	 */
-	plan = (Plan *) make_append(planlist, tlist);
+	plan = (Plan *) make_append(root, planlist, tlist, NIL);
 
 	/*
 	 * For UNION ALL, we just need the Append plan.  For UNION, need to add
@@ -540,7 +540,7 @@ generate_nonunion_plan(SetOperationStmt *op, PlannerInfo *root,
 	/*
 	 * Append the child results together.
 	 */
-	plan = (Plan *) make_append(planlist, tlist);
+	plan = (Plan *) make_append(root, planlist, tlist, NIL);
 
 	/* Identify the grouping semantics */
 	groupList = generate_setop_grouplist(op, tlist);
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index f8aa745..d80e52c 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -635,31 +635,74 @@ create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals)
 /*
  * create_append_path
  *	  Creates a path corresponding to an Append plan, returning the
- *	  pathnode.
+ *	  pathnode. 
+ *
+ *    Note that we must support create_append_path(null, rel, nil, nil) which
+ *    is used to create dummy plans.
  */
 AppendPath *
-create_append_path(RelOptInfo *rel, List *subpaths)
+create_append_path(PlannerInfo *root, RelOptInfo *rel, List *subpaths, List *pathkeys)
 {
 	AppendPath *pathnode = makeNode(AppendPath);
 	ListCell   *l;
+	Cost total_cost=0, startup_cost=0;
+	Cost this_total_cost, this_startup_cost;
+	int npaths = 0;
 
 	pathnode->path.pathtype = T_Append;
 	pathnode->path.parent = rel;
-	pathnode->path.pathkeys = NIL;		/* result is always considered
-										 * unsorted */
+	pathnode->path.pathkeys = pathkeys;
 	pathnode->subpaths = subpaths;
 
-	pathnode->path.startup_cost = 0;
-	pathnode->path.total_cost = 0;
 	foreach(l, subpaths)
 	{
 		Path	   *subpath = (Path *) lfirst(l);
 
-		if (l == list_head(subpaths))	/* first node? */
-			pathnode->path.startup_cost = subpath->startup_cost;
-		pathnode->path.total_cost += subpath->total_cost;
+		if (pathkeys_contained_in(pathkeys, subpath->pathkeys))  
+		{
+			this_startup_cost = subpath->startup_cost;
+			this_total_cost   = subpath->total_cost;
+		}
+		else
+		{
+			Path sort_path; /* dummy for result of cost_sort */
+			cost_sort(&sort_path,
+					  root,
+					  pathkeys,
+					  subpath->total_cost, 
+					  subpath->parent->tuples, 
+					  subpath->parent->width, 
+					  -1.0);
+			this_total_cost   = sort_path.total_cost;
+			this_startup_cost = sort_path.startup_cost;
+		}
+
+		npaths++;
+		total_cost += this_total_cost;
+		/* If it's unsorted the startup cost is just the first subpath's
+		 * startup cost, otherwise it's the sum of all startup costs */
+		if (pathkeys != NIL || l == list_head(subpaths))
+			startup_cost += this_startup_cost;
+	}
+
+	/* The cost of merging using a heapsort */
+	if (pathkeys != NIL)
+	{
+		Path sort_path;
+		cost_sort(&sort_path,
+				  root,
+				  pathkeys,
+				  total_cost,
+				  rel->rows,
+				  rel->width, 
+				  npaths);
+		total_cost = sort_path.total_cost - (enable_sort ? 0 : disable_cost);
+		startup_cost += total_cost / rel->rows * npaths;
 	}
 
+	pathnode->path.total_cost = total_cost;
+	pathnode->path.startup_cost = startup_cost;
+	
 	return pathnode;
 }
 
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 8a1f2ee..b274efc 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1047,6 +1047,13 @@ typedef struct AppendState
 	PlanState **appendplans;	/* array of PlanStates for my inputs */
 	int			as_nplans;
 	int			as_whichplan;
+
+	bool		as_is_ordered;
+	int			as_nkeys;
+	ScanKey		as_scankeys;		/* array of length as_nkeys */
+	TupleTableSlot **as_slots;		/* array of length as_nplans */
+	int			*as_heap;	/* array of length as_nplans */
+	int			as_heap_size;	/* how many slots are present in the heap */
 } AppendState;
 
 /* ----------------
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index f2f99f4..060d6a3 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -180,6 +180,14 @@ typedef struct Append
 {
 	Plan		plan;
 	List	   *appendplans;
+	bool		isOrdered;
+
+	/* used only if the append is an ordered append */
+
+	int		numCols;	/* number of sort-key columns */
+	AttrNumber *sortColIdx;		/* their indexes in the target list */
+	Oid	   *sortOperators;	/* OIDs of operators to sort them by */
+	bool	   *nullsFirst;		/* NULLS FIRST/LAST directions */
 } Append;
 
 /* ----------------
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 91f4c5c..11dd2ec 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -542,10 +542,11 @@ typedef struct EquivalenceClass
  *
  * em_is_child signifies that this element was built by transposing a member
  * for an inheritance parent relation to represent the corresponding expression
- * on an inheritance child.  The element should be ignored for all purposes
- * except constructing inner-indexscan paths for the child relation.  (Other
- * types of join are driven from transposed joininfo-list entries.)  Note
- * that the EC's ec_relids field does NOT include the child relation.
+ * on an inheritance child.  These elements are used for constructing
+ * inner-indexscan paths for the child relation (other types of join are
+ * driven from transposed joininfo-list entries) and for constructing sort
+ * ordered Append output.  Note that the EC's ec_relids field does NOT include
+ * the child relation.
  *
  * em_datatype is usually the same as exprType(em_expr), but can be
  * different when dealing with a binary-compatible opfamily; in particular
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 5e0ebe0..e5219d9 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -46,7 +46,10 @@ extern BitmapOrPath *create_bitmap_or_path(PlannerInfo *root,
 					  List *bitmapquals);
 extern TidPath *create_tidscan_path(PlannerInfo *root, RelOptInfo *rel,
 					List *tidquals);
-extern AppendPath *create_append_path(RelOptInfo *rel, List *subpaths);
+extern AppendPath *create_append_path(PlannerInfo *root,
+									  RelOptInfo *rel, 
+									  List *subpaths,
+									  List *pathkeys);
 extern ResultPath *create_result_path(List *quals);
 extern MaterialPath *create_material_path(RelOptInfo *rel, Path *subpath);
 extern UniquePath *create_unique_path(PlannerInfo *root, RelOptInfo *rel,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 5bb0e09..e11b1fd 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -43,7 +43,8 @@ extern Node *fix_indexqual_operand(Node *node, IndexOptInfo *index);
 extern SubqueryScan *make_subqueryscan(List *qptlist, List *qpqual,
 				  Index scanrelid, Plan *subplan,
 				  List *subrtable, List *subrowmark);
-extern Append *make_append(List *appendplans, List *tlist);
+extern Append *make_append(PlannerInfo *root, List *appendplans,
+					 List *tlist, List *pathkeys);
 extern RecursiveUnion *make_recursive_union(List *tlist,
 					 Plan *lefttree, Plan *righttree, int wtParam,
 					 List *distinctList, long numGroups);