Support MergeAppend plans, to allow sorted output from append relations.

This patch eliminates the former need to sort the output of an Append scan
when an ordered scan of an inheritance tree is wanted.  This should be
particularly useful for fast-start cases such as queries with LIMIT.

Original patch by Greg Stark, with further hacking by Hans-Jurgen Schonig,
Robert Haas, and Tom Lane.

1 files changed, 71 insertions, 0 deletions

diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 71e0e75a569..8214acc5713 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -636,6 +636,8 @@ create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals)
  * create_append_path
  *	  Creates a path corresponding to an Append plan, returning the
  *	  pathnode.
+ *
+ * Note that we must handle subpaths = NIL, representing a dummy access path.
  */
 AppendPath *
 create_append_path(RelOptInfo *rel, List *subpaths)
@@ -649,6 +651,13 @@ create_append_path(RelOptInfo *rel, List *subpaths)
 										 * unsorted */
 	pathnode->subpaths = subpaths;
 
+	/*
+	 * 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.
+	 *
+	 * If you change this, see also make_append().
+	 */
 	pathnode->path.startup_cost = 0;
 	pathnode->path.total_cost = 0;
 	foreach(l, subpaths)
@@ -664,6 +673,68 @@ create_append_path(RelOptInfo *rel, List *subpaths)
 }
 
 /*
+ * create_merge_append_path
+ *	  Creates a path corresponding to a MergeAppend plan, returning the
+ *	  pathnode.
+ */
+MergeAppendPath *
+create_merge_append_path(PlannerInfo *root,
+						 RelOptInfo *rel,
+						 List *subpaths,
+						 List *pathkeys)
+{
+	MergeAppendPath *pathnode = makeNode(MergeAppendPath);
+	Cost		input_startup_cost;
+	Cost		input_total_cost;
+	ListCell   *l;
+
+	pathnode->path.pathtype = T_MergeAppend;
+	pathnode->path.parent = rel;
+	pathnode->path.pathkeys = pathkeys;
+	pathnode->subpaths = subpaths;
+
+	/* Add up all the costs of the input paths */
+	input_startup_cost = 0;
+	input_total_cost = 0;
+	foreach(l, subpaths)
+	{
+		Path	   *subpath = (Path *) lfirst(l);
+
+		if (pathkeys_contained_in(pathkeys, subpath->pathkeys))
+		{
+			/* Subpath is adequately ordered, we won't need to sort it */
+			input_startup_cost += subpath->startup_cost;
+			input_total_cost += subpath->total_cost;
+		}
+		else
+		{
+			/* We'll need to insert a Sort node, so include cost for that */
+			Path	sort_path;		/* dummy for result of cost_sort */
+
+			cost_sort(&sort_path,
+					  root,
+					  pathkeys,
+					  subpath->total_cost,
+					  subpath->parent->tuples,
+					  subpath->parent->width,
+					  0.0,
+					  work_mem,
+					  -1.0);
+			input_startup_cost += sort_path.startup_cost;
+			input_total_cost += sort_path.total_cost;
+		}
+	}
+
+	/* Now we can compute total costs of the MergeAppend */
+	cost_merge_append(&pathnode->path, root,
+					  pathkeys, list_length(subpaths),
+					  input_startup_cost, input_total_cost,
+					  rel->tuples);
+
+	return pathnode;
+}
+
+/*
  * create_result_path
  *	  Creates a path representing a Result-and-nothing-else plan.
  *	  This is only used for the case of a query with an empty jointree.