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.

7 files changed, 96 insertions, 7 deletions

diff --git a/src/include/executor/nodeMergeAppend.h b/src/include/executor/nodeMergeAppend.h
new file mode 100644
index 0000000000..7e7e494b71
--- /dev/null
+++ b/src/include/executor/nodeMergeAppend.h
@@ -0,0 +1,24 @@
+/*-------------------------------------------------------------------------
+ *
+ * nodeMergeAppend.h
+ *
+ *
+ *
+ * Portions Copyright (c) 1996-2010, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/executor/nodeMergeAppend.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef NODEMERGEAPPEND_H
+#define NODEMERGEAPPEND_H
+
+#include "nodes/execnodes.h"
+
+extern MergeAppendState *ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags);
+extern TupleTableSlot *ExecMergeAppend(MergeAppendState *node);
+extern void ExecEndMergeAppend(MergeAppendState *node);
+extern void ExecReScanMergeAppend(MergeAppendState *node);
+
+#endif   /* NODEMERGEAPPEND_H */
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 8a1f2ee047..78188a3954 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1050,6 +1050,33 @@ typedef struct AppendState
 } AppendState;
 
 /* ----------------
+ *	 MergeAppendState information
+ *
+ *		nplans			how many plans are in the array
+ *		nkeys			number of sort key columns
+ *		scankeys		sort keys in ScanKey representation
+ *		slots			current output tuple of each subplan
+ *		heap			heap of active tuples (represented as array indexes)
+ *		heap_size		number of active heap entries
+ *		initialized		true if we have fetched first tuple from each subplan
+ *		last_slot		last subplan fetched from (which must be re-called)
+ * ----------------
+ */
+typedef struct MergeAppendState
+{
+	PlanState	ps;				/* its first field is NodeTag */
+	PlanState **mergeplans;		/* array of PlanStates for my inputs */
+	int			ms_nplans;
+	int			ms_nkeys;
+	ScanKey		ms_scankeys;	/* array of length ms_nkeys */
+	TupleTableSlot **ms_slots;	/* array of length ms_nplans */
+	int			*ms_heap;		/* array of length ms_nplans */
+	int			ms_heap_size;	/* current active length of ms_heap[] */
+	bool		ms_initialized;	/* are subplans started? */
+	int			ms_last_slot;	/* last subplan slot we returned from */
+} MergeAppendState;
+
+/* ----------------
  *	 RecursiveUnionState information
  *
  *		RecursiveUnionState is used for performing a recursive union.
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 0d33a2ed5f..15dabe31ce 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -45,6 +45,7 @@ typedef enum NodeTag
 	T_Result,
 	T_ModifyTable,
 	T_Append,
+	T_MergeAppend,
 	T_RecursiveUnion,
 	T_BitmapAnd,
 	T_BitmapOr,
@@ -87,6 +88,7 @@ typedef enum NodeTag
 	T_ResultState,
 	T_ModifyTableState,
 	T_AppendState,
+	T_MergeAppendState,
 	T_RecursiveUnionState,
 	T_BitmapAndState,
 	T_BitmapOrState,
@@ -215,6 +217,7 @@ typedef enum NodeTag
 	T_HashPath,
 	T_TidPath,
 	T_AppendPath,
+	T_MergeAppendPath,
 	T_ResultPath,
 	T_MaterialPath,
 	T_UniquePath,
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index f2f99f4a2b..81038f6ad1 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -183,6 +183,22 @@ typedef struct Append
 } Append;
 
 /* ----------------
+ *	 MergeAppend node -
+ *		Merge the results of pre-sorted sub-plans to preserve the ordering.
+ * ----------------
+ */
+typedef struct MergeAppend
+{
+	Plan		plan;
+	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 */
+	bool	   *nullsFirst;		/* NULLS FIRST/LAST directions */
+} MergeAppend;
+
+/* ----------------
  *	RecursiveUnion node -
  *		Generate a recursive union of two subplans.
  *
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 91f4c5c1c4..6e3d0f3518 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -256,9 +256,9 @@ typedef struct PlannerInfo
  * the entire append relation.	The member RTEs are otherrels.	The parent
  * is present in the query join tree but the members are not.  The member
  * RTEs and otherrels are used to plan the scans of the individual tables or
- * subqueries of the append set; then the parent baserel is given an Append
- * plan comprising the best plans for the individual member rels.  (See
- * comments for AppendRelInfo for more information.)
+ * subqueries of the append set; then the parent baserel is given Append
+ * and/or MergeAppend paths comprising the best paths for the individual
+ * member rels.  (See comments for AppendRelInfo for more information.)
  *
  * At one time we also made otherrels to represent join RTEs, for use in
  * handling join alias Vars.  Currently this is not needed because all join
@@ -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
+ * MergeAppend paths for the whole inheritance tree.  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
@@ -756,6 +757,16 @@ typedef struct AppendPath
 	(IsA((p), AppendPath) && ((AppendPath *) (p))->subpaths == NIL)
 
 /*
+ * MergeAppendPath represents a MergeAppend plan, ie, the merging of sorted
+ * results from several member plans to produce similarly-sorted output.
+ */
+typedef struct MergeAppendPath
+{
+	Path		path;
+	List	   *subpaths;		/* list of component Paths */
+} MergeAppendPath;
+
+/*
  * ResultPath represents use of a Result plan node to compute a variable-free
  * targetlist with no underlying tables (a "SELECT expressions" query).
  * The query could have a WHERE clause, too, represented by "quals".
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 5a4b33f2b1..e1dcd6df14 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -86,6 +86,10 @@ extern void cost_sort(Path *path, PlannerInfo *root,
 		  List *pathkeys, Cost input_cost, double tuples, int width,
 		  Cost comparison_cost, int sort_mem,
 		  double limit_tuples);
+extern void cost_merge_append(Path *path, PlannerInfo *root,
+				  List *pathkeys, int n_streams,
+				  Cost input_startup_cost, Cost input_total_cost,
+				  double tuples);
 extern void cost_material(Path *path,
 			  Cost input_startup_cost, Cost input_total_cost,
 			  double tuples, int width);
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 5e0ebe046b..53ebe5756b 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -47,6 +47,10 @@ extern BitmapOrPath *create_bitmap_or_path(PlannerInfo *root,
 extern TidPath *create_tidscan_path(PlannerInfo *root, RelOptInfo *rel,
 					List *tidquals);
 extern AppendPath *create_append_path(RelOptInfo *rel, List *subpaths);
+extern MergeAppendPath *create_merge_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,