4 files changed, 64 insertions, 7 deletions

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".