2 files changed, 636 insertions, 51 deletions

diff --git a/src/backend/executor/execPartition.c b/src/backend/executor/execPartition.c
index ac94f9f3374..57a24d48783 100644
--- a/src/backend/executor/execPartition.c
+++ b/src/backend/executor/execPartition.c
@@ -40,6 +40,10 @@ static char *ExecBuildSlotPartitionKeyDescription(Relation rel,
 									 bool *isnull,
 									 int maxfieldlen);
 static List *adjust_partition_tlist(List *tlist, TupleConversionMap *map);
+static void find_subplans_for_params_recurse(PartitionPruneState *prunestate,
+								 PartitionPruningData *pprune,
+								 bool allparams,
+								 Bitmapset **validsubplans);
 
 
 /*
@@ -1293,3 +1297,418 @@ adjust_partition_tlist(List *tlist, TupleConversionMap *map)
 
 	return new_tlist;
 }
+
+/*-------------------------------------------------------------------------
+ * Run-Time Partition Pruning Support.
+ *
+ * The following series of functions exist to support the removal of unneeded
+ * subnodes for queries against partitioned tables.  The supporting functions
+ * here are designed to work with any node type which supports an arbitrary
+ * number of subnodes, e.g. Append, MergeAppend.
+ *
+ * Normally this pruning work is performed by the query planner's partition
+ * pruning code, however, the planner is limited to only being able to prune
+ * away unneeded partitions using quals which compare the partition key to a
+ * value which is known to be Const during planning.  To allow the same
+ * pruning to be performed for values which are only determined during
+ * execution, we must make an additional pruning attempt during execution.
+ *
+ * Here we support pruning using both external and exec Params.  The main
+ * difference between these that we need to concern ourselves with is the
+ * time when the values of the Params are known.  External Param values are
+ * known at any time of execution, including executor startup, but exec Param
+ * values are only known when the executor is running.
+ *
+ * For external Params we may be able to prune away unneeded partitions
+ * during executor startup.  This has the added benefit of not having to
+ * initialize the unneeded subnodes at all.  This is useful as it can save
+ * quite a bit of effort during executor startup.
+ *
+ * For exec Params, we must delay pruning until the executor is running.
+ *
+ * Functions:
+ *
+ * ExecSetupPartitionPruneState:
+ *		This must be called by nodes before any partition pruning is
+ *		attempted.  Normally executor startup is a good time. This function
+ *		creates the PartitionPruneState details which are required by each
+ *		of the two pruning functions, details include information about
+ *		how to map the partition index details which are returned by the
+ *		planner's partition prune function into subnode indexes.
+ *
+ * ExecFindInitialMatchingSubPlans:
+ *		Returns indexes of matching subnodes utilizing only external Params
+ *		to eliminate subnodes.  The function must only be called during
+ *		executor startup for the given node before the subnodes themselves
+ *		are initialized.  Subnodes which are found not to match by this
+ *		function must not be included in the node's list of subnodes as this
+ *		function performs a remap of the partition index to subplan index map
+ *		and the newly created map provides indexes only for subnodes which
+ *		remain after calling this function.
+ *
+ * ExecFindMatchingSubPlans:
+ *		Returns indexes of matching subnodes utilizing all Params to eliminate
+ *		subnodes which can't possibly contain matching tuples.  This function
+ *		can only be called while the executor is running.
+ *-------------------------------------------------------------------------
+ */
+
+/*
+ * ExecSetupPartitionPruneState
+ *		Setup the required data structure which is required for calling
+ *		ExecFindInitialMatchingSubPlans and ExecFindMatchingSubPlans.
+ *
+ * 'partitionpruneinfo' is a List of PartitionPruneInfos as generated by
+ * make_partition_pruneinfo.  Here we build a PartitionPruneContext for each
+ * item in the List.  These contexts can be re-used each time we re-evaulate
+ * which partitions match the pruning steps provided in each
+ * PartitionPruneInfo.
+ */
+PartitionPruneState *
+ExecSetupPartitionPruneState(PlanState *planstate, List *partitionpruneinfo)
+{
+	PartitionPruningData *prunedata;
+	PartitionPruneState *prunestate;
+	ListCell   *lc;
+	int			i;
+
+	Assert(partitionpruneinfo != NIL);
+
+	prunestate = (PartitionPruneState *) palloc(sizeof(PartitionPruneState));
+	prunedata = (PartitionPruningData *)
+		palloc(sizeof(PartitionPruningData) * list_length(partitionpruneinfo));
+
+	/*
+	 * The first item in the array contains the details for the query's target
+	 * partition, so record that as the root of the partition hierarchy.
+	 */
+	prunestate->partprunedata = prunedata;
+	prunestate->num_partprunedata = list_length(partitionpruneinfo);
+	prunestate->extparams = NULL;
+	prunestate->execparams = NULL;
+
+	/*
+	 * Create a sub memory context which we'll use when making calls to the
+	 * query planner's function to determine which partitions will match.  The
+	 * planner is not too careful about freeing memory, so we'll ensure we
+	 * call the function in this context to avoid any memory leaking in the
+	 * executor's memory context.
+	 */
+	prunestate->prune_context =
+		AllocSetContextCreate(CurrentMemoryContext,
+							  "Partition Prune",
+							  ALLOCSET_DEFAULT_SIZES);
+
+	i = 0;
+	foreach(lc, partitionpruneinfo)
+	{
+		PartitionPruneInfo *pinfo = (PartitionPruneInfo *) lfirst(lc);
+		PartitionPruningData *pprune = &prunedata[i];
+		PartitionPruneContext *context = &pprune->context;
+		PartitionDesc partdesc;
+		Relation	rel;
+		PartitionKey partkey;
+		int			partnatts;
+
+		pprune->present_parts = bms_copy(pinfo->present_parts);
+		pprune->subnode_map = palloc(sizeof(int) * pinfo->nparts);
+
+		/*
+		 * We must make a copy of this rather than pointing directly to the
+		 * plan's version as we may end up making modifications to it later.
+		 */
+		memcpy(pprune->subnode_map, pinfo->subnode_map,
+			   sizeof(int) * pinfo->nparts);
+
+		/* We can use the subpart_map verbatim, since we never modify it */
+		pprune->subpart_map = pinfo->subpart_map;
+
+		/*
+		 * Grab some info from the table's relcache; lock was already obtained
+		 * by ExecLockNonLeafAppendTables.
+		 */
+		rel = relation_open(pinfo->reloid, NoLock);
+
+		partkey = RelationGetPartitionKey(rel);
+		partdesc = RelationGetPartitionDesc(rel);
+
+		context->strategy = partkey->strategy;
+		context->partnatts = partnatts = partkey->partnatts;
+		context->partopfamily = partkey->partopfamily;
+		context->partopcintype = partkey->partopcintype;
+		context->partcollation = partkey->partcollation;
+		context->partsupfunc = partkey->partsupfunc;
+		context->nparts = pinfo->nparts;
+		context->boundinfo = partition_bounds_copy(partdesc->boundinfo, partkey);
+		context->planstate = planstate;
+		context->safeparams = NULL; /* empty for now */
+
+		pprune->pruning_steps = pinfo->pruning_steps;
+		pprune->extparams = bms_copy(pinfo->extparams);
+		pprune->allparams = bms_union(pinfo->extparams, pinfo->execparams);
+
+		/*
+		 * Accumulate the paramids which match the partitioned keys of all
+		 * partitioned tables.
+		 */
+		prunestate->extparams = bms_add_members(prunestate->extparams,
+												pinfo->extparams);
+
+		prunestate->execparams = bms_add_members(prunestate->execparams,
+												 pinfo->execparams);
+
+		relation_close(rel, NoLock);
+
+		i++;
+	}
+
+	/*
+	 * Cache the union of the paramids of both types.  This saves having to
+	 * recalculate it everytime we need to know what they are.
+	 */
+	prunestate->allparams = bms_union(prunestate->extparams,
+									  prunestate->execparams);
+
+	return prunestate;
+}
+
+/*
+ * ExecFindInitialMatchingSubPlans
+ *		Determine which subset of subplan nodes we need to initialize based
+ *		on the details stored in 'prunestate'.  Here we only determine the
+ *		matching partitions using values known during plan startup, which is
+ *		only external Params.  Exec Params will be unknown at this time.  We
+ *		must delay pruning using exec Params until the actual executor run.
+ *
+ * It is expected that callers of this function do so only once during their
+ * init plan.  The caller must only initialize the subnodes which are returned
+ * by this function. The remaining subnodes should be discarded.  Once this
+ * function has been called, future calls to ExecFindMatchingSubPlans will
+ * return its matching subnode indexes assuming that the caller discarded
+ * the original non-matching subnodes.
+ *
+ * This function must only be called if 'prunestate' has any extparams.
+ *
+ * 'nsubnodes' must be passed as the total number of unpruned subnodes.
+ */
+Bitmapset *
+ExecFindInitialMatchingSubPlans(PartitionPruneState *prunestate, int nsubnodes)
+{
+	PartitionPruningData *pprune;
+	MemoryContext oldcontext;
+	Bitmapset  *result = NULL;
+
+	/*
+	 * Ensure there's actually external params, or we've not been called
+	 * already.
+	 */
+	Assert(!bms_is_empty(prunestate->extparams));
+
+	pprune = prunestate->partprunedata;
+
+	/*
+	 * Switch to a temp context to avoid leaking memory in the executor's
+	 * memory context.
+	 */
+	oldcontext = MemoryContextSwitchTo(prunestate->prune_context);
+
+	/* Determine which subnodes match the external params */
+	find_subplans_for_params_recurse(prunestate, pprune, false, &result);
+
+	MemoryContextSwitchTo(oldcontext);
+
+	/* Move to the correct memory context */
+	result = bms_copy(result);
+
+	MemoryContextReset(prunestate->prune_context);
+
+	/*
+	 * Record that partition pruning has been performed for external params.
+	 * This partly also serves to ensure we never call this function twice
+	 * with the same input and also so that ExecFindMatchingSubPlans is aware
+	 * that pruning has already been performed for external Params.
+	 */
+	bms_free(prunestate->extparams);
+	prunestate->extparams = NULL;
+
+	/*
+	 * If any subnodes were pruned, we must re-sequence the subnode indexes so
+	 * that ExecFindMatchingSubPlans properly returns the indexes from the
+	 * subnodes which will remain after execution of this function.
+	 */
+	if (bms_num_members(result) < nsubnodes)
+	{
+		int		   *new_subnode_indexes;
+		int			i;
+		int			newidx;
+
+		/*
+		 * First we must build an array which we can use to adjust the
+		 * existing subnode_map so that it contains the new subnode indexes.
+		 */
+		new_subnode_indexes = (int *) palloc(sizeof(int) * nsubnodes);
+		newidx = 0;
+		for (i = 0; i < nsubnodes; i++)
+		{
+			if (bms_is_member(i, result))
+				new_subnode_indexes[i] = newidx++;
+			else
+				new_subnode_indexes[i] = -1;	/* Newly pruned */
+		}
+
+		/*
+		 * Now we can re-sequence each PartitionPruneInfo's subnode_map so
+		 * that they point to the new index of the subnode.
+		 */
+		for (i = 0; i < prunestate->num_partprunedata; i++)
+		{
+			int			nparts;
+			int			j;
+
+			pprune = &prunestate->partprunedata[i];
+			nparts = pprune->context.nparts;
+
+			/*
+			 * We also need to reset the present_parts field so that it only
+			 * contains partition indexes that we actually still have subnodes
+			 * for.  It seems easier to build a fresh one, rather than trying
+			 * to update the existing one.
+			 */
+			bms_free(pprune->present_parts);
+			pprune->present_parts = NULL;
+
+			for (j = 0; j < nparts; j++)
+			{
+				int			oldidx = pprune->subnode_map[j];
+
+				/*
+				 * If this partition existed as a subnode then change the old
+				 * subnode index to the new subnode index.  The new index may
+				 * become -1 if the partition was pruned above, or it may just
+				 * come earlier in the subnode list due to some subnodes being
+				 * removed earlier in the list.
+				 */
+				if (oldidx >= 0)
+				{
+					pprune->subnode_map[j] = new_subnode_indexes[oldidx];
+
+					if (new_subnode_indexes[oldidx] >= 0)
+						pprune->present_parts =
+							bms_add_member(pprune->present_parts, j);
+				}
+			}
+		}
+
+		pfree(new_subnode_indexes);
+	}
+
+	return result;
+}
+
+/*
+ * ExecFindMatchingSubPlans
+ *		Determine which subplans match the the pruning steps detailed in
+ *		'pprune' for the current Param values.
+ *
+ * Here we utilize both external and exec Params for pruning.
+ */
+Bitmapset *
+ExecFindMatchingSubPlans(PartitionPruneState *prunestate)
+{
+	PartitionPruningData *pprune;
+	MemoryContext oldcontext;
+	Bitmapset  *result = NULL;
+
+	pprune = prunestate->partprunedata;
+
+	/*
+	 * Switch to a temp context to avoid leaking memory in the executor's
+	 * memory context.
+	 */
+	oldcontext = MemoryContextSwitchTo(prunestate->prune_context);
+
+	find_subplans_for_params_recurse(prunestate, pprune, true, &result);
+
+	MemoryContextSwitchTo(oldcontext);
+
+	/* Move to the correct memory context */
+	result = bms_copy(result);
+
+	MemoryContextReset(prunestate->prune_context);
+
+	return result;
+}
+
+/*
+ * find_subplans_for_params_recurse
+ *		Recursive worker function for ExecFindMatchingSubPlans and
+ *		ExecFindInitialMatchingSubPlans
+ */
+static void
+find_subplans_for_params_recurse(PartitionPruneState *prunestate,
+								 PartitionPruningData *pprune,
+								 bool allparams,
+								 Bitmapset **validsubplans)
+{
+	PartitionPruneContext *context = &pprune->context;
+	Bitmapset  *partset;
+	Bitmapset  *pruneparams;
+	int			i;
+
+	/* Guard against stack overflow due to overly deep partition hierarchy. */
+	check_stack_depth();
+
+	/*
+	 * Use only external params unless we've been asked to also use exec
+	 * params too.
+	 */
+	if (allparams)
+		pruneparams = pprune->allparams;
+	else
+		pruneparams = pprune->extparams;
+
+	/*
+	 * We only need to determine the matching partitions if there are any
+	 * params matching the partition key at this level.  If there are no
+	 * matching params, then we can simply return all subnodes which belong to
+	 * this parent partition.  The planner should have already determined
+	 * these to be the minimum possible set.  We must still recursively visit
+	 * any subpartitioned tables as we may find their partition keys match
+	 * some Params at their level.
+	 */
+	if (!bms_is_empty(pruneparams))
+	{
+		context->safeparams = pruneparams;
+		partset = get_matching_partitions(context,
+										  pprune->pruning_steps);
+	}
+	else
+		partset = pprune->present_parts;
+
+	/* Translate partset into subnode indexes */
+	i = -1;
+	while ((i = bms_next_member(partset, i)) >= 0)
+	{
+		if (pprune->subnode_map[i] >= 0)
+			*validsubplans = bms_add_member(*validsubplans,
+											pprune->subnode_map[i]);
+		else
+		{
+			int			partidx = pprune->subpart_map[i];
+
+			if (partidx != -1)
+				find_subplans_for_params_recurse(prunestate,
+												 &prunestate->partprunedata[partidx],
+												 allparams, validsubplans);
+			else
+			{
+				/*
+				 * This could only happen if clauses used in planning where
+				 * more restrictive than those used here, or if the maps are
+				 * somehow corrupt.
+				 */
+				elog(ERROR, "partition missing from subplans");
+			}
+		}
+	}
+}
diff --git a/src/backend/executor/nodeAppend.c b/src/backend/executor/nodeAppend.c
index dcbf4d68aa4..b135b61324e 100644
--- a/src/backend/executor/nodeAppend.c
+++ b/src/backend/executor/nodeAppend.c
@@ -58,6 +58,7 @@
 #include "postgres.h"
 
 #include "executor/execdebug.h"
+#include "executor/execPartition.h"
 #include "executor/nodeAppend.h"
 #include "miscadmin.h"
 
@@ -77,11 +78,13 @@ struct ParallelAppendState
 };
 
 #define INVALID_SUBPLAN_INDEX		-1
+#define NO_MATCHING_SUBPLANS		-2
 
 static TupleTableSlot *ExecAppend(PlanState *pstate);
 static bool choose_next_subplan_locally(AppendState *node);
 static bool choose_next_subplan_for_leader(AppendState *node);
 static bool choose_next_subplan_for_worker(AppendState *node);
+static void mark_invalid_subplans_as_finished(AppendState *node);
 
 /* ----------------------------------------------------------------
  *		ExecInitAppend
@@ -99,8 +102,10 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
 {
 	AppendState *appendstate = makeNode(AppendState);
 	PlanState **appendplanstates;
+	Bitmapset  *validsubplans;
 	int			nplans;
-	int			i;
+	int			i,
+				j;
 	ListCell   *lc;
 
 	/* check for unsupported flags */
@@ -113,54 +118,116 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
 	ExecLockNonLeafAppendTables(node->partitioned_rels, estate);
 
 	/*
-	 * Set up empty vector of subplan states
-	 */
-	nplans = list_length(node->appendplans);
-
-	appendplanstates = (PlanState **) palloc0(nplans * sizeof(PlanState *));
-
-	/*
 	 * create new AppendState for our append node
 	 */
 	appendstate->ps.plan = (Plan *) node;
 	appendstate->ps.state = estate;
 	appendstate->ps.ExecProcNode = ExecAppend;
-	appendstate->appendplans = appendplanstates;
-	appendstate->as_nplans = nplans;
+
+	/* Let choose_next_subplan_* function handle setting the first subplan */
+	appendstate->as_whichplan = INVALID_SUBPLAN_INDEX;
+
+	/* If run-time partition pruning is enabled, then set that up now */
+	if (node->part_prune_infos != NIL)
+	{
+		PartitionPruneState *prunestate;
+
+		ExecAssignExprContext(estate, &appendstate->ps);
+
+		prunestate = ExecSetupPartitionPruneState(&appendstate->ps,
+												  node->part_prune_infos);
+
+		/*
+		 * When there are external params matching the partition key we may be
+		 * able to prune away Append subplans now.
+		 */
+		if (!bms_is_empty(prunestate->extparams))
+		{
+			/* Determine which subplans match the external params */
+			validsubplans = ExecFindInitialMatchingSubPlans(prunestate,
+															list_length(node->appendplans));
+
+			/*
+			 * If no subplans match the given parameters then we must handle
+			 * this case in a special way.  The problem here is that code in
+			 * explain.c requires an Append to have at least one subplan in
+			 * order for it to properly determine the Vars in that subplan's
+			 * targetlist.  We sidestep this issue by just initializing the
+			 * first subplan and setting as_whichplan to NO_MATCHING_SUBPLANS
+			 * to indicate that we don't need to scan any subnodes.
+			 */
+			if (bms_is_empty(validsubplans))
+			{
+				appendstate->as_whichplan = NO_MATCHING_SUBPLANS;
+
+				/* Mark the first as valid so that it's initialized below */
+				validsubplans = bms_make_singleton(0);
+			}
+
+			nplans = bms_num_members(validsubplans);
+		}
+		else
+		{
+			/* We'll need to initialize all subplans */
+			nplans = list_length(node->appendplans);
+			validsubplans = bms_add_range(NULL, 0, nplans - 1);
+		}
+
+		/*
+		 * If there's no exec params then no further pruning can be done, we
+		 * can just set the valid subplans to all remaining subplans.
+		 */
+		if (bms_is_empty(prunestate->execparams))
+			appendstate->as_valid_subplans = bms_add_range(NULL, 0, nplans - 1);
+
+		appendstate->as_prune_state = prunestate;
+
+	}
+	else
+	{
+		nplans = list_length(node->appendplans);
+
+		/*
+		 * When run-time partition pruning is not enabled we can just mark all
+		 * subplans as valid, they must also all be initialized.
+		 */
+		appendstate->as_valid_subplans = validsubplans =
+			bms_add_range(NULL, 0, nplans - 1);
+		appendstate->as_prune_state = NULL;
+	}
 
 	/*
 	 * Initialize result tuple type and slot.
 	 */
 	ExecInitResultTupleSlotTL(estate, &appendstate->ps);
 
+	appendplanstates = (PlanState **) palloc(nplans *
+											 sizeof(PlanState *));
+
 	/*
-	 * call ExecInitNode on each of the plans to be executed and save the
-	 * results into the array "appendplans".
+	 * call ExecInitNode on each of the valid plans to be executed and save
+	 * the results into the appendplanstates array.
 	 */
-	i = 0;
+	j = i = 0;
 	foreach(lc, node->appendplans)
 	{
-		Plan	   *initNode = (Plan *) lfirst(lc);
+		if (bms_is_member(i, validsubplans))
+		{
+			Plan	   *initNode = (Plan *) lfirst(lc);
 
-		appendplanstates[i] = ExecInitNode(initNode, estate, eflags);
+			appendplanstates[j++] = ExecInitNode(initNode, estate, eflags);
+		}
 		i++;
 	}
 
+	appendstate->appendplans = appendplanstates;
+	appendstate->as_nplans = nplans;
+
 	/*
 	 * Miscellaneous initialization
-	 *
-	 * Append plans don't have expression contexts because they never call
-	 * ExecQual or ExecProject.
 	 */
-	appendstate->ps.ps_ProjInfo = NULL;
 
-	/*
-	 * Parallel-aware append plans must choose the first subplan to execute by
-	 * looking at shared memory, but non-parallel-aware append plans can
-	 * always start with the first subplan.
-	 */
-	appendstate->as_whichplan =
-		appendstate->ps.plan->parallel_aware ? INVALID_SUBPLAN_INDEX : 0;
+	appendstate->ps.ps_ProjInfo = NULL;
 
 	/* For parallel query, this will be overridden later. */
 	appendstate->choose_next_subplan = choose_next_subplan_locally;
@@ -179,10 +246,20 @@ ExecAppend(PlanState *pstate)
 {
 	AppendState *node = castNode(AppendState, pstate);
 
-	/* If no subplan has been chosen, we must choose one before proceeding. */
-	if (node->as_whichplan == INVALID_SUBPLAN_INDEX &&
-		!node->choose_next_subplan(node))
-		return ExecClearTuple(node->ps.ps_ResultTupleSlot);
+	if (node->as_whichplan < 0)
+	{
+		/*
+		 * If no subplan has been chosen, we must choose one before
+		 * proceeding.
+		 */
+		if (node->as_whichplan == INVALID_SUBPLAN_INDEX &&
+			!node->choose_next_subplan(node))
+			return ExecClearTuple(node->ps.ps_ResultTupleSlot);
+
+		/* Nothing to do if there are no matching subplans */
+		else if (node->as_whichplan == NO_MATCHING_SUBPLANS)
+			return ExecClearTuple(node->ps.ps_ResultTupleSlot);
+	}
 
 	for (;;)
 	{
@@ -251,6 +328,19 @@ ExecReScanAppend(AppendState *node)
 {
 	int			i;
 
+	/*
+	 * If any of the parameters being used for partition pruning have changed,
+	 * then we'd better unset the valid subplans so that they are reselected
+	 * for the new parameter values.
+	 */
+	if (node->as_prune_state &&
+		bms_overlap(node->ps.chgParam,
+					node->as_prune_state->execparams))
+	{
+		bms_free(node->as_valid_subplans);
+		node->as_valid_subplans = NULL;
+	}
+
 	for (i = 0; i < node->as_nplans; i++)
 	{
 		PlanState  *subnode = node->appendplans[i];
@@ -270,8 +360,8 @@ ExecReScanAppend(AppendState *node)
 			ExecReScan(subnode);
 	}
 
-	node->as_whichplan =
-		node->ps.plan->parallel_aware ? INVALID_SUBPLAN_INDEX : 0;
+	/* Let choose_next_subplan_* function handle setting the first subplan */
+	node->as_whichplan = INVALID_SUBPLAN_INDEX;
 }
 
 /* ----------------------------------------------------------------
@@ -360,29 +450,39 @@ static bool
 choose_next_subplan_locally(AppendState *node)
 {
 	int			whichplan = node->as_whichplan;
+	int			nextplan;
 
-	if (ScanDirectionIsForward(node->ps.state->es_direction))
+	/* We should never be called when there are no subplans */
+	Assert(whichplan != NO_MATCHING_SUBPLANS);
+
+	/*
+	 * If first call then have the bms member function choose the first valid
+	 * subplan by initializing whichplan to -1.  If there happen to be no
+	 * valid subplans then the bms member function will handle that by
+	 * returning a negative number which will allow us to exit returning a
+	 * false value.
+	 */
+	if (whichplan == INVALID_SUBPLAN_INDEX)
 	{
-		/*
-		 * We won't normally see INVALID_SUBPLAN_INDEX in this case, but we
-		 * might if a plan intended to be run in parallel ends up being run
-		 * serially.
-		 */
-		if (whichplan == INVALID_SUBPLAN_INDEX)
-			node->as_whichplan = 0;
-		else
-		{
-			if (whichplan >= node->as_nplans - 1)
-				return false;
-			node->as_whichplan++;
-		}
+		if (node->as_valid_subplans == NULL)
+			node->as_valid_subplans =
+				ExecFindMatchingSubPlans(node->as_prune_state);
+
+		whichplan = -1;
 	}
+
+	/* Ensure whichplan is within the expected range */
+	Assert(whichplan >= -1 && whichplan <= node->as_nplans);
+
+	if (ScanDirectionIsForward(node->ps.state->es_direction))
+		nextplan = bms_next_member(node->as_valid_subplans, whichplan);
 	else
-	{
-		if (whichplan <= 0)
-			return false;
-		node->as_whichplan--;
-	}
+		nextplan = bms_prev_member(node->as_valid_subplans, whichplan);
+
+	if (nextplan < 0)
+		return false;
+
+	node->as_whichplan = nextplan;
 
 	return true;
 }
@@ -404,6 +504,9 @@ choose_next_subplan_for_leader(AppendState *node)
 	/* Backward scan is not supported by parallel-aware plans */
 	Assert(ScanDirectionIsForward(node->ps.state->es_direction));
 
+	/* We should never be called when there are no subplans */
+	Assert(node->as_whichplan != NO_MATCHING_SUBPLANS);
+
 	LWLockAcquire(&pstate->pa_lock, LW_EXCLUSIVE);
 
 	if (node->as_whichplan != INVALID_SUBPLAN_INDEX)
@@ -415,6 +518,23 @@ choose_next_subplan_for_leader(AppendState *node)
 	{
 		/* Start with last subplan. */
 		node->as_whichplan = node->as_nplans - 1;
+
+		/*
+		 * If we've yet to determine the valid subplans for these parameters
+		 * then do so now.  If run-time pruning is disabled then the valid
+		 * subplans will always be set to all subplans.
+		 */
+		if (node->as_valid_subplans == NULL)
+		{
+			node->as_valid_subplans =
+				ExecFindMatchingSubPlans(node->as_prune_state);
+
+			/*
+			 * Mark each invalid plan as finished to allow the loop below to
+			 * select the first valid subplan.
+			 */
+			mark_invalid_subplans_as_finished(node);
+		}
 	}
 
 	/* Loop until we find a subplan to execute. */
@@ -461,12 +581,27 @@ choose_next_subplan_for_worker(AppendState *node)
 	/* Backward scan is not supported by parallel-aware plans */
 	Assert(ScanDirectionIsForward(node->ps.state->es_direction));
 
+	/* We should never be called when there are no subplans */
+	Assert(node->as_whichplan != NO_MATCHING_SUBPLANS);
+
 	LWLockAcquire(&pstate->pa_lock, LW_EXCLUSIVE);
 
 	/* Mark just-completed subplan as finished. */
 	if (node->as_whichplan != INVALID_SUBPLAN_INDEX)
 		node->as_pstate->pa_finished[node->as_whichplan] = true;
 
+	/*
+	 * If we've yet to determine the valid subplans for these parameters then
+	 * do so now.  If run-time pruning is disabled then the valid subplans
+	 * will always be set to all subplans.
+	 */
+	else if (node->as_valid_subplans == NULL)
+	{
+		node->as_valid_subplans =
+			ExecFindMatchingSubPlans(node->as_prune_state);
+		mark_invalid_subplans_as_finished(node);
+	}
+
 	/* If all the plans are already done, we have nothing to do */
 	if (pstate->pa_next_plan == INVALID_SUBPLAN_INDEX)
 	{
@@ -532,3 +667,34 @@ choose_next_subplan_for_worker(AppendState *node)
 
 	return true;
 }
+
+/*
+ * mark_invalid_subplans_as_finished
+ *		Marks the ParallelAppendState's pa_finished as true for each invalid
+ *		subplan.
+ *
+ * This function should only be called for parallel Append with run-time
+ * pruning enabled.
+ */
+static void
+mark_invalid_subplans_as_finished(AppendState *node)
+{
+	int			i;
+
+	/* Only valid to call this while in parallel Append mode */
+	Assert(node->as_pstate);
+
+	/* Shouldn't have been called when run-time pruning is not enabled */
+	Assert(node->as_prune_state);
+
+	/* Nothing to do if all plans are valid */
+	if (bms_num_members(node->as_valid_subplans) == node->as_nplans)
+		return;
+
+	/* Mark all non-valid plans as finished */
+	for (i = 0; i < node->as_nplans; i++)
+	{
+		if (!bms_is_member(i, node->as_valid_subplans))
+			node->as_pstate->pa_finished[i] = true;
+	}
+}