Redesign the plancache mechanism for more flexibility and efficiency.

Rewrite plancache.c so that a "cached plan" (which is rather a misnomer
at this point) can support generation of custom, parameter-value-dependent
plans, and can make an intelligent choice between using custom plans and
the traditional generic-plan approach.  The specific choice algorithm
implemented here can probably be improved in future, but this commit is
all about getting the mechanism in place, not the policy.

In addition, restructure the API to greatly reduce the amount of extraneous
data copying needed.  The main compromise needed to make that possible was
to split the initial creation of a CachedPlanSource into two steps.  It's
worth noting in particular that SPI_saveplan is now deprecated in favor of
SPI_keepplan, which accomplishes the same end result with zero data
copying, and no need to then spend even more cycles throwing away the
original SPIPlan.  The risk of long-term memory leaks while manipulating
SPIPlans has also been greatly reduced.  Most of this improvement is based
on use of the recently-added MemoryContextSetParent primitive.

1 files changed, 998 insertions, 523 deletions

diff --git a/src/backend/utils/cache/plancache.c b/src/backend/utils/cache/plancache.c
index 68b6783e196..62fdf2877db 100644
--- a/src/backend/utils/cache/plancache.c
+++ b/src/backend/utils/cache/plancache.c
@@ -3,19 +3,23 @@
  * plancache.c
  *	  Plan cache management.
  *
- * We can store a cached plan in either fully-planned format, or just
- * parsed-and-rewritten if the caller wishes to postpone planning until
- * actual parameter values are available.  CachedPlanSource has the same
- * contents either way, but CachedPlan contains a list of PlannedStmts
- * and bare utility statements in the first case, or a list of Query nodes
- * in the second case.
+ * The plan cache manager has two principal responsibilities: deciding when
+ * to use a generic plan versus a custom (parameter-value-specific) plan,
+ * and tracking whether cached plans need to be invalidated because of schema
+ * changes in the objects they depend on.
  *
- * The plan cache manager itself is principally responsible for tracking
- * whether cached plans should be invalidated because of schema changes in
- * the objects they depend on.	When (and if) the next demand for a cached
- * plan occurs, the query will be replanned.  Note that this could result
- * in an error, for example if a column referenced by the query is no
- * longer present.	The creator of a cached plan can specify whether it
+ * The logic for choosing generic or custom plans is in choose_custom_plan,
+ * which see for comments.
+ *
+ * Cache invalidation is driven off sinval events.  Any CachedPlanSource
+ * that matches the event is marked invalid, as is its generic CachedPlan
+ * if it has one.  When (and if) the next demand for a cached plan occurs,
+ * parse analysis and rewrite is repeated to build a new valid query tree,
+ * and then planning is performed as normal.
+ *
+ * Note that if the sinval was a result of user DDL actions, parse analysis
+ * could throw an error, for example if a column referenced by the query is
+ * no longer present.  The creator of a cached plan can specify whether it
  * is allowable for the query to change output tupdesc on replan (this
  * could happen with "SELECT *" for example) --- if so, it's up to the
  * caller to notice changes and cope with them.
@@ -41,6 +45,8 @@
  */
 #include "postgres.h"
 
+#include <limits.h>
+
 #include "access/transam.h"
 #include "catalog/namespace.h"
 #include "executor/executor.h"
@@ -58,15 +64,28 @@
 #include "utils/syscache.h"
 
 
-static List *cached_plans_list = NIL;
-
-static void StoreCachedPlan(CachedPlanSource *plansource, List *stmt_list,
-				MemoryContext plan_context);
+/*
+ * This is the head of the backend's list of "saved" CachedPlanSources (i.e.,
+ * those that are in long-lived storage and are examined for sinval events).
+ * We thread the structs manually instead of using List cells so that we can
+ * guarantee to save a CachedPlanSource without error.
+ */
+static CachedPlanSource *first_saved_plan = NULL;
+
+static void ReleaseGenericPlan(CachedPlanSource *plansource);
+static List *RevalidateCachedQuery(CachedPlanSource *plansource);
+static bool CheckCachedPlan(CachedPlanSource *plansource);
+static CachedPlan *BuildCachedPlan(CachedPlanSource *plansource, List *qlist,
+								   ParamListInfo boundParams);
+static bool choose_custom_plan(CachedPlanSource *plansource,
+							   ParamListInfo boundParams);
+static double cached_plan_cost(CachedPlan *plan);
 static void AcquireExecutorLocks(List *stmt_list, bool acquire);
 static void AcquirePlannerLocks(List *stmt_list, bool acquire);
 static void ScanQueryForLocks(Query *parsetree, bool acquire);
 static bool ScanQueryWalker(Node *node, bool *acquire);
 static bool plan_list_is_transient(List *stmt_list);
+static TupleDesc PlanCacheComputeResultDesc(List *stmt_list);
 static void PlanCacheRelCallback(Datum arg, Oid relid);
 static void PlanCacheFuncCallback(Datum arg, int cacheid, uint32 hashvalue);
 static void PlanCacheSysCallback(Datum arg, int cacheid, uint32 hashvalue);
@@ -90,32 +109,33 @@ InitPlanCache(void)
 /*
  * CreateCachedPlan: initially create a plan cache entry.
  *
- * The caller must already have successfully parsed/planned the query;
- * about all that we do here is copy it into permanent storage.
+ * Creation of a cached plan is divided into two steps, CreateCachedPlan and
+ * CompleteCachedPlan.  CreateCachedPlan should be called after running the
+ * query through raw_parser, but before doing parse analysis and rewrite;
+ * CompleteCachedPlan is called after that.  The reason for this arrangement
+ * is that it can save one round of copying of the raw parse tree, since
+ * the parser will normally scribble on the raw parse tree.  Callers would
+ * otherwise need to make an extra copy of the parse tree to ensure they
+ * still had a clean copy to present at plan cache creation time.
+ *
+ * All arguments presented to CreateCachedPlan are copied into a memory
+ * context created as a child of the call-time CurrentMemoryContext, which
+ * should be a reasonably short-lived working context that will go away in
+ * event of an error.  This ensures that the cached plan data structure will
+ * likewise disappear if an error occurs before we have fully constructed it.
+ * Once constructed, the cached plan can be made longer-lived, if needed,
+ * by calling SaveCachedPlan.
  *
  * raw_parse_tree: output of raw_parser()
- * query_string: original query text (as of PG 8.4, must not be NULL)
+ * query_string: original query text
  * commandTag: compile-time-constant tag for query, or NULL if empty query
- * param_types: array of fixed parameter type OIDs, or NULL if none
- * num_params: number of fixed parameters
- * cursor_options: options bitmask that was/will be passed to planner
- * stmt_list: list of PlannedStmts/utility stmts, or list of Query trees
- * fully_planned: are we caching planner or rewriter output?
- * fixed_result: TRUE to disallow changes in result tupdesc
  */
 CachedPlanSource *
 CreateCachedPlan(Node *raw_parse_tree,
 				 const char *query_string,
-				 const char *commandTag,
-				 Oid *param_types,
-				 int num_params,
-				 int cursor_options,
-				 List *stmt_list,
-				 bool fully_planned,
-				 bool fixed_result)
+				 const char *commandTag)
 {
 	CachedPlanSource *plansource;
-	OverrideSearchPath *search_path;
 	MemoryContext source_context;
 	MemoryContext oldcxt;
 
@@ -123,61 +143,50 @@ CreateCachedPlan(Node *raw_parse_tree,
 
 	/*
 	 * Make a dedicated memory context for the CachedPlanSource and its
-	 * subsidiary data.  We expect it can be pretty small.
+	 * permanent subsidiary data.  It's probably not going to be large, but
+	 * just in case, use the default maxsize parameter.  Initially it's a
+	 * child of the caller's context (which we assume to be transient), so
+	 * that it will be cleaned up on error.
 	 */
-	source_context = AllocSetContextCreate(CacheMemoryContext,
+	source_context = AllocSetContextCreate(CurrentMemoryContext,
 										   "CachedPlanSource",
 										   ALLOCSET_SMALL_MINSIZE,
 										   ALLOCSET_SMALL_INITSIZE,
-										   ALLOCSET_SMALL_MAXSIZE);
-
-	/*
-	 * Fetch current search_path into new context, but do any recalculation
-	 * work required in caller's context.
-	 */
-	search_path = GetOverrideSearchPath(source_context);
+										   ALLOCSET_DEFAULT_MAXSIZE);
 
 	/*
 	 * Create and fill the CachedPlanSource struct within the new context.
+	 * Most fields are just left empty for the moment.
 	 */
 	oldcxt = MemoryContextSwitchTo(source_context);
-	plansource = (CachedPlanSource *) palloc(sizeof(CachedPlanSource));
+
+	plansource = (CachedPlanSource *) palloc0(sizeof(CachedPlanSource));
+	plansource->magic = CACHEDPLANSOURCE_MAGIC;
 	plansource->raw_parse_tree = copyObject(raw_parse_tree);
 	plansource->query_string = pstrdup(query_string);
-	plansource->commandTag = commandTag;		/* no copying needed */
-	if (num_params > 0)
-	{
-		plansource->param_types = (Oid *) palloc(num_params * sizeof(Oid));
-		memcpy(plansource->param_types, param_types, num_params * sizeof(Oid));
-	}
-	else
-		plansource->param_types = NULL;
-	plansource->num_params = num_params;
-	/* these can be set later with CachedPlanSetParserHook: */
+	plansource->commandTag = commandTag;
+	plansource->param_types = NULL;
+	plansource->num_params = 0;
 	plansource->parserSetup = NULL;
 	plansource->parserSetupArg = NULL;
-	plansource->cursor_options = cursor_options;
-	plansource->fully_planned = fully_planned;
-	plansource->fixed_result = fixed_result;
-	plansource->search_path = search_path;
-	plansource->generation = 0; /* StoreCachedPlan will increment */
-	plansource->resultDesc = PlanCacheComputeResultDesc(stmt_list);
-	plansource->plan = NULL;
+	plansource->cursor_options = 0;
+	plansource->fixed_result = false;
+	plansource->resultDesc = NULL;
+	plansource->search_path = NULL;
 	plansource->context = source_context;
-	plansource->orig_plan = NULL;
-
-	/*
-	 * Copy the current output plans into the plancache entry.
-	 */
-	StoreCachedPlan(plansource, stmt_list, NULL);
-
-	/*
-	 * Now we can add the entry to the list of cached plans.  The List nodes
-	 * live in CacheMemoryContext.
-	 */
-	MemoryContextSwitchTo(CacheMemoryContext);
-
-	cached_plans_list = lappend(cached_plans_list, plansource);
+	plansource->query_list = NIL;
+	plansource->relationOids = NIL;
+	plansource->invalItems = NIL;
+	plansource->query_context = NULL;
+	plansource->gplan = NULL;
+	plansource->is_complete = false;
+	plansource->is_saved = false;
+	plansource->is_valid = false;
+	plansource->generation = 0;
+	plansource->next_saved = NULL;
+	plansource->generic_cost = -1;
+	plansource->total_custom_cost = 0;
+	plansource->num_custom_plans = 0;
 
 	MemoryContextSwitchTo(oldcxt);
 
@@ -185,274 +194,465 @@ CreateCachedPlan(Node *raw_parse_tree,
 }
 
 /*
- * FastCreateCachedPlan: create a plan cache entry with minimal data copying.
+ * CompleteCachedPlan: second step of creating a plan cache entry.
+ *
+ * Pass in the analyzed-and-rewritten form of the query, as well as the
+ * required subsidiary data about parameters and such.  All passed values will
+ * be copied into the CachedPlanSource's memory, except as specified below.
+ * After this is called, GetCachedPlan can be called to obtain a plan, and
+ * optionally the CachedPlanSource can be saved using SaveCachedPlan.
+ *
+ * If querytree_context is not NULL, the querytree_list must be stored in that
+ * context (but the other parameters need not be).  The querytree_list is not
+ * copied, rather the given context is kept as the initial query_context of
+ * the CachedPlanSource.  (It should have been created as a child of the
+ * caller's working memory context, but it will now be reparented to belong
+ * to the CachedPlanSource.)  The querytree_context is normally the context in
+ * which the caller did raw parsing and parse analysis.  This approach saves
+ * one tree copying step compared to passing NULL, but leaves lots of extra
+ * cruft in the query_context, namely whatever extraneous stuff parse analysis
+ * created, as well as whatever went unused from the raw parse tree.  Using
+ * this option is a space-for-time tradeoff that is appropriate if the
+ * CachedPlanSource is not expected to survive long.
  *
- * For plans that aren't expected to live very long, the copying overhead of
- * CreateCachedPlan is annoying.  We provide this variant entry point in which
- * the caller has already placed all the data in a suitable memory context.
- * The source data and completed plan are in the same context, since this
- * avoids extra copy steps during plan construction.  If the query ever does
- * need replanning, we'll generate a separate new CachedPlan at that time, but
- * the CachedPlanSource and the initial CachedPlan share the caller-provided
- * context and go away together when neither is needed any longer.	(Because
- * the parser and planner generate extra cruft in addition to their real
- * output, this approach means that the context probably contains a bunch of
- * useless junk as well as the useful trees.  Hence, this method is a
- * space-for-time tradeoff, which is worth making for plans expected to be
- * short-lived.)
+ * plancache.c cannot know how to copy the data referenced by parserSetupArg,
+ * and it would often be inappropriate to do so anyway.  When using that
+ * option, it is caller's responsibility that the referenced data remains
+ * valid for as long as the CachedPlanSource exists.
  *
- * raw_parse_tree, query_string, param_types, and stmt_list must reside in the
- * given context, which must have adequate lifespan (recommendation: make it a
- * child of CacheMemoryContext).  Otherwise the API is the same as
- * CreateCachedPlan.
+ * plansource: structure returned by CreateCachedPlan
+ * querytree_list: analyzed-and-rewritten form of query (list of Query nodes)
+ * querytree_context: memory context containing querytree_list,
+ *					  or NULL to copy querytree_list into a fresh context
+ * param_types: array of fixed parameter type OIDs, or NULL if none
+ * num_params: number of fixed parameters
+ * parserSetup: alternate method for handling query parameters
+ * parserSetupArg: data to pass to parserSetup
+ * cursor_options: options bitmask to pass to planner
+ * fixed_result: TRUE to disallow future changes in query's result tupdesc
  */
-CachedPlanSource *
-FastCreateCachedPlan(Node *raw_parse_tree,
-					 char *query_string,
-					 const char *commandTag,
-					 Oid *param_types,
-					 int num_params,
-					 int cursor_options,
-					 List *stmt_list,
-					 bool fully_planned,
-					 bool fixed_result,
-					 MemoryContext context)
+void
+CompleteCachedPlan(CachedPlanSource *plansource,
+				   List *querytree_list,
+				   MemoryContext querytree_context,
+				   Oid *param_types,
+				   int num_params,
+				   ParserSetupHook parserSetup,
+				   void *parserSetupArg,
+				   int cursor_options,
+				   bool fixed_result)
 {
-	CachedPlanSource *plansource;
-	OverrideSearchPath *search_path;
-	MemoryContext oldcxt;
+	MemoryContext source_context = plansource->context;
+	MemoryContext oldcxt = CurrentMemoryContext;
 
-	Assert(query_string != NULL);		/* required as of 8.4 */
+	/* Assert caller is doing things in a sane order */
+	Assert(plansource->magic == CACHEDPLANSOURCE_MAGIC);
+	Assert(!plansource->is_complete);
+
+	/*
+	 * If caller supplied a querytree_context, reparent it underneath the
+	 * CachedPlanSource's context; otherwise, create a suitable context and
+	 * copy the querytree_list into it.
+	 */
+	if (querytree_context != NULL)
+	{
+		MemoryContextSetParent(querytree_context, source_context);
+		MemoryContextSwitchTo(querytree_context);
+	}
+	else
+	{
+		/* Again, it's a good bet the querytree_context can be small */
+		querytree_context = AllocSetContextCreate(source_context,
+												  "CachedPlanQuery",
+												  ALLOCSET_SMALL_MINSIZE,
+												  ALLOCSET_SMALL_INITSIZE,
+												  ALLOCSET_DEFAULT_MAXSIZE);
+		MemoryContextSwitchTo(querytree_context);
+		querytree_list = (List *) copyObject(querytree_list);
+	}
+
+	plansource->query_context = querytree_context;
+	plansource->query_list = querytree_list;
 
 	/*
-	 * Fetch current search_path into given context, but do any recalculation
-	 * work required in caller's context.
+	 * Use the planner machinery to extract dependencies.  Data is saved in
+	 * query_context.  (We assume that not a lot of extra cruft is created
+	 * by this call.)
 	 */
-	search_path = GetOverrideSearchPath(context);
+	extract_query_dependencies((Node *) querytree_list,
+							   &plansource->relationOids,
+							   &plansource->invalItems);
 
 	/*
-	 * Create and fill the CachedPlanSource struct within the given context.
+	 * Save the final parameter types (or other parameter specification data)
+	 * into the source_context, as well as our other parameters.  Also save
+	 * the result tuple descriptor.
 	 */
-	oldcxt = MemoryContextSwitchTo(context);
-	plansource = (CachedPlanSource *) palloc(sizeof(CachedPlanSource));
-	plansource->raw_parse_tree = raw_parse_tree;
-	plansource->query_string = query_string;
-	plansource->commandTag = commandTag;		/* no copying needed */
-	plansource->param_types = param_types;
+	MemoryContextSwitchTo(source_context);
+
+	if (num_params > 0)
+	{
+		plansource->param_types = (Oid *) palloc(num_params * sizeof(Oid));
+		memcpy(plansource->param_types, param_types, num_params * sizeof(Oid));
+	}
+	else
+		plansource->param_types = NULL;
 	plansource->num_params = num_params;
-	/* these can be set later with CachedPlanSetParserHook: */
-	plansource->parserSetup = NULL;
-	plansource->parserSetupArg = NULL;
+	plansource->parserSetup = parserSetup;
+	plansource->parserSetupArg = parserSetupArg;
 	plansource->cursor_options = cursor_options;
-	plansource->fully_planned = fully_planned;
 	plansource->fixed_result = fixed_result;
-	plansource->search_path = search_path;
-	plansource->generation = 0; /* StoreCachedPlan will increment */
-	plansource->resultDesc = PlanCacheComputeResultDesc(stmt_list);
-	plansource->plan = NULL;
-	plansource->context = context;
-	plansource->orig_plan = NULL;
+	plansource->resultDesc = PlanCacheComputeResultDesc(querytree_list);
+
+	MemoryContextSwitchTo(oldcxt);
 
 	/*
-	 * Store the current output plans into the plancache entry.
+	 * Fetch current search_path into dedicated context, but do any
+	 * recalculation work required in caller's context.
 	 */
-	StoreCachedPlan(plansource, stmt_list, context);
+	plansource->search_path = GetOverrideSearchPath(source_context);
+
+	plansource->is_complete = true;
+	plansource->is_valid = true;
+}
+
+/*
+ * SaveCachedPlan: save a cached plan permanently
+ *
+ * This function moves the cached plan underneath CacheMemoryContext (making
+ * it live for the life of the backend, unless explicitly dropped), and adds
+ * it to the list of cached plans that are checked for invalidation when an
+ * sinval event occurs.
+ *
+ * This is guaranteed not to throw error; callers typically depend on that
+ * since this is called just before or just after adding a pointer to the
+ * CachedPlanSource to some permanent data structure of their own.  Up until
+ * this is done, a CachedPlanSource is just transient data that will go away
+ * automatically on transaction abort.
+ */
+void
+SaveCachedPlan(CachedPlanSource *plansource)
+{
+	/* Assert caller is doing things in a sane order */
+	Assert(plansource->magic == CACHEDPLANSOURCE_MAGIC);
+	Assert(plansource->is_complete);
+	Assert(!plansource->is_saved);
 
 	/*
-	 * Since the context is owned by the CachedPlan, advance its refcount.
+	 * In typical use, this function would be called before generating any
+	 * plans from the CachedPlanSource.  If there is a generic plan, moving
+	 * it into CacheMemoryContext would be pretty risky since it's unclear
+	 * whether the caller has taken suitable care with making references
+	 * long-lived.  Best thing to do seems to be to discard the plan.
 	 */
-	plansource->orig_plan = plansource->plan;
-	plansource->orig_plan->refcount++;
+	ReleaseGenericPlan(plansource);
 
 	/*
-	 * Now we can add the entry to the list of cached plans.  The List nodes
-	 * live in CacheMemoryContext.
+	 * Reparent the source memory context under CacheMemoryContext so that
+	 * it will live indefinitely.  The query_context follows along since it's
+	 * already a child of the other one.
 	 */
-	MemoryContextSwitchTo(CacheMemoryContext);
-
-	cached_plans_list = lappend(cached_plans_list, plansource);
+	MemoryContextSetParent(plansource->context, CacheMemoryContext);
 
-	MemoryContextSwitchTo(oldcxt);
+	/*
+	 * Add the entry to the global list of cached plans.
+	 */
+	plansource->next_saved = first_saved_plan;
+	first_saved_plan = plansource;
 
-	return plansource;
+	plansource->is_saved = true;
 }
 
 /*
- * CachedPlanSetParserHook: set up to use parser callback hooks
+ * DropCachedPlan: destroy a cached plan.
  *
- * Use this when a caller wants to manage parameter information via parser
- * callbacks rather than a fixed parameter-types list.	Beware that the
- * information pointed to by parserSetupArg must be valid for as long as
- * the cached plan might be replanned!
+ * Actually this only destroys the CachedPlanSource: any referenced CachedPlan
+ * is released, but not destroyed until its refcount goes to zero.	That
+ * handles the situation where DropCachedPlan is called while the plan is
+ * still in use.
  */
 void
-CachedPlanSetParserHook(CachedPlanSource *plansource,
-						ParserSetupHook parserSetup,
-						void *parserSetupArg)
+DropCachedPlan(CachedPlanSource *plansource)
 {
-	/* Must not have specified a fixed parameter-types list */
-	Assert(plansource->param_types == NULL);
-	Assert(plansource->num_params == 0);
-	/* OK, save hook info */
-	plansource->parserSetup = parserSetup;
-	plansource->parserSetupArg = parserSetupArg;
+	Assert(plansource->magic == CACHEDPLANSOURCE_MAGIC);
+
+	/* If it's been saved, remove it from the list */
+	if (plansource->is_saved)
+	{
+		if (first_saved_plan == plansource)
+			first_saved_plan = plansource->next_saved;
+		else
+		{
+			CachedPlanSource *psrc;
+
+			for (psrc = first_saved_plan; psrc; psrc = psrc->next_saved)
+			{
+				if (psrc->next_saved == plansource)
+				{
+					psrc->next_saved = plansource->next_saved;
+					break;
+				}
+			}
+		}
+		plansource->is_saved = false;
+	}
+
+	/* Decrement generic CachePlan's refcount and drop if no longer needed */
+	ReleaseGenericPlan(plansource);
+
+	/*
+	 * Remove the CachedPlanSource and all subsidiary data (including the
+	 * query_context if any).
+	 */
+	MemoryContextDelete(plansource->context);
 }
 
 /*
- * StoreCachedPlan: store a built or rebuilt plan into a plancache entry.
- *
- * Common subroutine for CreateCachedPlan and RevalidateCachedPlan.
+ * ReleaseGenericPlan: release a CachedPlanSource's generic plan, if any.
  */
 static void
-StoreCachedPlan(CachedPlanSource *plansource,
-				List *stmt_list,
-				MemoryContext plan_context)
+ReleaseGenericPlan(CachedPlanSource *plansource)
 {
-	CachedPlan *plan;
+	/* Be paranoid about the possibility that ReleaseCachedPlan fails */
+	if (plansource->gplan)
+	{
+		CachedPlan *plan = plansource->gplan;
+
+		Assert(plan->magic == CACHEDPLAN_MAGIC);
+		plansource->gplan = NULL;
+		ReleaseCachedPlan(plan, false);
+	}
+}
+
+/*
+ * RevalidateCachedQuery: ensure validity of analyzed-and-rewritten query tree.
+ *
+ * What we do here is re-acquire locks and redo parse analysis if necessary.
+ * On return, the query_list is valid and we have sufficient locks to begin
+ * planning.
+ *
+ * If any parse analysis activity is required, the caller's memory context is
+ * used for that work.
+ *
+ * The result value is the transient analyzed-and-rewritten query tree if we
+ * had to do re-analysis, and NIL otherwise.  (This is returned just to save
+ * a tree copying step in a subsequent BuildCachedPlan call.)
+ */
+static List *
+RevalidateCachedQuery(CachedPlanSource *plansource)
+{
+	bool		snapshot_set;
+	Node	   *rawtree;
+	List	   *tlist;			/* transient query-tree list */
+	List	   *qlist;			/* permanent query-tree list */
+	TupleDesc	resultDesc;
+	MemoryContext querytree_context;
 	MemoryContext oldcxt;
 
-	if (plan_context == NULL)
+	/*
+	 * If the query is currently valid, acquire locks on the referenced
+	 * objects; then check again.  We need to do it this way to cover the race
+	 * condition that an invalidation message arrives before we get the locks.
+	 */
+	if (plansource->is_valid)
 	{
-		/*
-		 * Make a dedicated memory context for the CachedPlan and its
-		 * subsidiary data.  It's probably not going to be large, but just in
-		 * case, use the default maxsize parameter.
-		 */
-		plan_context = AllocSetContextCreate(CacheMemoryContext,
-											 "CachedPlan",
-											 ALLOCSET_SMALL_MINSIZE,
-											 ALLOCSET_SMALL_INITSIZE,
-											 ALLOCSET_DEFAULT_MAXSIZE);
+		AcquirePlannerLocks(plansource->query_list, true);
 
 		/*
-		 * Copy supplied data into the new context.
+		 * By now, if any invalidation has happened, the inval callback
+		 * functions will have marked the query invalid.
 		 */
-		oldcxt = MemoryContextSwitchTo(plan_context);
+		if (plansource->is_valid)
+		{
+			/* Successfully revalidated and locked the query. */
+			return NIL;
+		}
 
-		stmt_list = (List *) copyObject(stmt_list);
+		/* Ooops, the race case happened.  Release useless locks. */
+		AcquirePlannerLocks(plansource->query_list, false);
 	}
-	else
+
+	/*
+	 * Discard the no-longer-useful query tree.  (Note: we don't want to
+	 * do this any earlier, else we'd not have been able to release locks
+	 * correctly in the race condition case.)
+	 */
+	plansource->is_valid = false;
+	plansource->query_list = NIL;
+	plansource->relationOids = NIL;
+	plansource->invalItems = NIL;
+
+	/*
+	 * Free the query_context.  We don't really expect MemoryContextDelete to
+	 * fail, but just in case, make sure the CachedPlanSource is left in a
+	 * reasonably sane state.  (The generic plan won't get unlinked yet,
+	 * but that's acceptable.)
+	 */
+	if (plansource->query_context)
 	{
-		/* Assume subsidiary data is in the given context */
-		oldcxt = MemoryContextSwitchTo(plan_context);
+		MemoryContext	qcxt = plansource->query_context;
+
+		plansource->query_context = NULL;
+		MemoryContextDelete(qcxt);
 	}
 
+	/* Drop the generic plan reference if any */
+	ReleaseGenericPlan(plansource);
+
 	/*
-	 * Create and fill the CachedPlan struct within the new context.
+	 * Now re-do parse analysis and rewrite.  This not incidentally acquires
+	 * the locks we need to do planning safely.
 	 */
-	plan = (CachedPlan *) palloc(sizeof(CachedPlan));
-	plan->stmt_list = stmt_list;
-	plan->fully_planned = plansource->fully_planned;
-	plan->dead = false;
-	if (plansource->fully_planned && plan_list_is_transient(stmt_list))
+	Assert(plansource->is_complete);
+
+	/*
+	 * Restore the search_path that was in use when the plan was made. See
+	 * comments for PushOverrideSearchPath about limitations of this.
+	 *
+	 * (XXX is there anything else we really need to restore?)
+	 */
+	PushOverrideSearchPath(plansource->search_path);
+
+	/*
+	 * If a snapshot is already set (the normal case), we can just use that
+	 * for parsing/planning.  But if it isn't, install one.  Note: no point in
+	 * checking whether parse analysis requires a snapshot; utility commands
+	 * don't have invalidatable plans, so we'd not get here for such a
+	 * command.
+	 */
+	snapshot_set = false;
+	if (!ActiveSnapshotSet())
 	{
-		Assert(TransactionIdIsNormal(TransactionXmin));
-		plan->saved_xmin = TransactionXmin;
+		PushActiveSnapshot(GetTransactionSnapshot());
+		snapshot_set = true;
 	}
+
+	/*
+	 * Run parse analysis and rule rewriting.  The parser tends to scribble on
+	 * its input, so we must copy the raw parse tree to prevent corruption of
+	 * the cache.
+	 */
+	rawtree = copyObject(plansource->raw_parse_tree);
+	if (plansource->parserSetup != NULL)
+		tlist = pg_analyze_and_rewrite_params(rawtree,
+											  plansource->query_string,
+											  plansource->parserSetup,
+											  plansource->parserSetupArg);
 	else
-		plan->saved_xmin = InvalidTransactionId;
-	plan->refcount = 1;			/* for the parent's link */
-	plan->generation = ++(plansource->generation);
-	plan->context = plan_context;
-	if (plansource->fully_planned)
-	{
-		/*
-		 * Planner already extracted dependencies, we don't have to ... except
-		 * in the case of EXPLAIN.	We assume here that EXPLAIN can't appear
-		 * in a list with other commands.
-		 */
-		plan->relationOids = plan->invalItems = NIL;
+		tlist = pg_analyze_and_rewrite(rawtree,
+									   plansource->query_string,
+									   plansource->param_types,
+									   plansource->num_params);
 
-		if (list_length(stmt_list) == 1 &&
-			IsA(linitial(stmt_list), ExplainStmt))
-		{
-			ExplainStmt *estmt = (ExplainStmt *) linitial(stmt_list);
+	/* Release snapshot if we got one */
+	if (snapshot_set)
+		PopActiveSnapshot();
 
-			extract_query_dependencies(estmt->query,
-									   &plan->relationOids,
-									   &plan->invalItems);
-		}
+	/* Now we can restore current search path */
+	PopOverrideSearchPath();
+
+	/*
+	 * Check or update the result tupdesc.  XXX should we use a weaker
+	 * condition than equalTupleDescs() here?
+	 *
+	 * We assume the parameter types didn't change from the first time, so no
+	 * need to update that.
+	 */
+	resultDesc = PlanCacheComputeResultDesc(tlist);
+	if (resultDesc == NULL && plansource->resultDesc == NULL)
+	{
+		/* OK, doesn't return tuples */
 	}
-	else
+	else if (resultDesc == NULL || plansource->resultDesc == NULL ||
+			 !equalTupleDescs(resultDesc, plansource->resultDesc))
 	{
-		/* Use the planner machinery to extract dependencies */
-		extract_query_dependencies((Node *) stmt_list,
-								   &plan->relationOids,
-								   &plan->invalItems);
+		/* can we give a better error message? */
+		if (plansource->fixed_result)
+			ereport(ERROR,
+					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+					 errmsg("cached plan must not change result type")));
+		oldcxt = MemoryContextSwitchTo(plansource->context);
+		if (resultDesc)
+			resultDesc = CreateTupleDescCopy(resultDesc);
+		if (plansource->resultDesc)
+			FreeTupleDesc(plansource->resultDesc);
+		plansource->resultDesc = resultDesc;
+		MemoryContextSwitchTo(oldcxt);
 	}
 
-	Assert(plansource->plan == NULL);
-	plansource->plan = plan;
+	/*
+	 * Allocate new query_context and copy the completed querytree into it.
+	 * It's transient until we complete the copying and dependency extraction.
+	 */
+	querytree_context = AllocSetContextCreate(CurrentMemoryContext,
+											  "CachedPlanQuery",
+											  ALLOCSET_SMALL_MINSIZE,
+											  ALLOCSET_SMALL_INITSIZE,
+											  ALLOCSET_DEFAULT_MAXSIZE);
+	oldcxt = MemoryContextSwitchTo(querytree_context);
 
-	MemoryContextSwitchTo(oldcxt);
-}
+	qlist = (List *) copyObject(tlist);
 
-/*
- * DropCachedPlan: destroy a cached plan.
- *
- * Actually this only destroys the CachedPlanSource: the referenced CachedPlan
- * is released, but not destroyed until its refcount goes to zero.	That
- * handles the situation where DropCachedPlan is called while the plan is
- * still in use.
- */
-void
-DropCachedPlan(CachedPlanSource *plansource)
-{
-	/* Validity check that we were given a CachedPlanSource */
-	Assert(list_member_ptr(cached_plans_list, plansource));
+	/*
+	 * Use the planner machinery to extract dependencies.  Data is saved in
+	 * query_context.  (We assume that not a lot of extra cruft is created
+	 * by this call.)
+	 */
+	extract_query_dependencies((Node *) qlist,
+							   &plansource->relationOids,
+							   &plansource->invalItems);
 
-	/* Remove it from the list */
-	cached_plans_list = list_delete_ptr(cached_plans_list, plansource);
+	MemoryContextSwitchTo(oldcxt);
+
+	/* Now reparent the finished query_context and save the links */
+	MemoryContextSetParent(querytree_context, plansource->context);
 
-	/* Decrement child CachePlan's refcount and drop if no longer needed */
-	if (plansource->plan)
-		ReleaseCachedPlan(plansource->plan, false);
+	plansource->query_context = querytree_context;
+	plansource->query_list = qlist;
 
 	/*
-	 * If CachedPlanSource has independent storage, just drop it.  Otherwise
-	 * decrement the refcount on the CachePlan that owns the storage.
+	 * Note: we do not reset generic_cost or total_custom_cost, although
+	 * we could choose to do so.  If the DDL or statistics change that
+	 * prompted the invalidation meant a significant change in the cost
+	 * estimates, it would be better to reset those variables and start
+	 * fresh; but often it doesn't, and we're better retaining our hard-won
+	 * knowledge about the relative costs.
 	 */
-	if (plansource->orig_plan == NULL)
-	{
-		/* Remove the CachedPlanSource and all subsidiary data */
-		MemoryContextDelete(plansource->context);
-	}
-	else
-	{
-		Assert(plansource->context == plansource->orig_plan->context);
-		ReleaseCachedPlan(plansource->orig_plan, false);
-	}
+
+	plansource->is_valid = true;
+
+	/* Return transient copy of querytrees for possible use in planning */
+	return tlist;
 }
 
 /*
- * RevalidateCachedPlan: prepare for re-use of a previously cached plan.
- *
- * What we do here is re-acquire locks and rebuild the plan if necessary.
- * On return, the plan is valid and we have sufficient locks to begin
- * execution (or planning, if not fully_planned).
+ * CheckCachedPlan: see if the CachedPlanSource's generic plan is valid.
  *
- * On return, the refcount of the plan has been incremented; a later
- * ReleaseCachedPlan() call is expected.  The refcount has been reported
- * to the CurrentResourceOwner if useResOwner is true.
+ * Caller must have already called RevalidateCachedQuery to verify that the
+ * querytree is up to date.
  *
- * Note: if any replanning activity is required, the caller's memory context
- * is used for that work.
+ * On a "true" return, we have acquired the locks needed to run the plan.
+ * (We must do this for the "true" result to be race-condition-free.)
  */
-CachedPlan *
-RevalidateCachedPlan(CachedPlanSource *plansource, bool useResOwner)
+static bool
+CheckCachedPlan(CachedPlanSource *plansource)
 {
-	CachedPlan *plan;
+	CachedPlan *plan = plansource->gplan;
+
+	/* Assert that caller checked the querytree */
+	Assert(plansource->is_valid);
 
-	/* Validity check that we were given a CachedPlanSource */
-	Assert(list_member_ptr(cached_plans_list, plansource));
+	/* If there's no generic plan, just say "false" */
+	if (!plan)
+		return false;
+
+	Assert(plan->magic == CACHEDPLAN_MAGIC);
 
 	/*
-	 * If the plan currently appears valid, acquire locks on the referenced
-	 * objects; then check again.  We need to do it this way to cover the race
-	 * condition that an invalidation message arrives before we get the lock.
+	 * If it appears valid, acquire locks and recheck; this is much the same
+	 * logic as in RevalidateCachedQuery, but for a plan.
 	 */
-	plan = plansource->plan;
-	if (plan && !plan->dead)
+	if (plan->is_valid)
 	{
 		/*
 		 * Plan must have positive refcount because it is referenced by
@@ -460,164 +660,348 @@ RevalidateCachedPlan(CachedPlanSource *plansource, bool useResOwner)
 		 */
 		Assert(plan->refcount > 0);
 
-		if (plan->fully_planned)
-			AcquireExecutorLocks(plan->stmt_list, true);
-		else
-			AcquirePlannerLocks(plan->stmt_list, true);
+		AcquireExecutorLocks(plan->stmt_list, true);
 
 		/*
 		 * If plan was transient, check to see if TransactionXmin has
 		 * advanced, and if so invalidate it.
 		 */
-		if (!plan->dead &&
+		if (plan->is_valid &&
 			TransactionIdIsValid(plan->saved_xmin) &&
 			!TransactionIdEquals(plan->saved_xmin, TransactionXmin))
-			plan->dead = true;
+			plan->is_valid = false;
 
 		/*
 		 * By now, if any invalidation has happened, the inval callback
-		 * functions will have marked the plan dead.
+		 * functions will have marked the plan invalid.
 		 */
-		if (plan->dead)
+		if (plan->is_valid)
 		{
-			/* Ooops, the race case happened.  Release useless locks. */
-			if (plan->fully_planned)
-				AcquireExecutorLocks(plan->stmt_list, false);
-			else
-				AcquirePlannerLocks(plan->stmt_list, false);
+			/* Successfully revalidated and locked the query. */
+			return true;
 		}
+
+		/* Ooops, the race case happened.  Release useless locks. */
+		AcquireExecutorLocks(plan->stmt_list, false);
 	}
 
 	/*
-	 * If plan has been invalidated, unlink it from the parent and release it.
+	 * Plan has been invalidated, so unlink it from the parent and release it.
 	 */
-	if (plan && plan->dead)
+	ReleaseGenericPlan(plansource);
+
+	return false;
+}
+
+/*
+ * BuildCachedPlan: construct a new CachedPlan from a CachedPlanSource.
+ *
+ * qlist should be the result value from a previous RevalidateCachedQuery.
+ *
+ * To build a generic, parameter-value-independent plan, pass NULL for
+ * boundParams.  To build a custom plan, pass the actual parameter values via
+ * boundParams.  For best effect, the PARAM_FLAG_CONST flag should be set on
+ * each parameter value; otherwise the planner will treat the value as a
+ * hint rather than a hard constant.
+ *
+ * Planning work is done in the caller's memory context.  The finished plan
+ * is in a child memory context, which typically should get reparented.
+ */
+static CachedPlan *
+BuildCachedPlan(CachedPlanSource *plansource, List *qlist,
+				ParamListInfo boundParams)
+{
+	CachedPlan *plan;
+	List	   *plist;
+	bool		snapshot_set;
+	bool		spi_pushed;
+	MemoryContext plan_context;
+	MemoryContext oldcxt;
+
+	/* Assert that caller checked the querytree */
+	Assert(plansource->is_valid);
+
+	/*
+	 * If we don't already have a copy of the querytree list that can be
+	 * scribbled on by the planner, make one.
+	 */
+	if (qlist == NIL)
+		qlist = (List *) copyObject(plansource->query_list);
+
+	/*
+	 * Restore the search_path that was in use when the plan was made. See
+	 * comments for PushOverrideSearchPath about limitations of this.
+	 *
+	 * (XXX is there anything else we really need to restore?)
+	 *
+	 * Note: it's a bit annoying to do this and snapshot-setting twice in the
+	 * case where we have to do both re-analysis and re-planning.  However,
+	 * until there's some evidence that the cost is actually meaningful
+	 * compared to parse analysis + planning, I'm not going to contort the
+	 * code enough to avoid that.
+	 */
+	PushOverrideSearchPath(plansource->search_path);
+
+	/*
+	 * If a snapshot is already set (the normal case), we can just use
+	 * that for parsing/planning.  But if it isn't, install one.  Note: no
+	 * point in checking whether parse analysis requires a snapshot;
+	 * utility commands don't have invalidatable plans, so we'd not get
+	 * here for such a command.
+	 */
+	snapshot_set = false;
+	if (!ActiveSnapshotSet())
 	{
-		plansource->plan = NULL;
-		ReleaseCachedPlan(plan, false);
-		plan = NULL;
+		PushActiveSnapshot(GetTransactionSnapshot());
+		snapshot_set = true;
 	}
 
 	/*
-	 * Build a new plan if needed.
+	 * The planner may try to call SPI-using functions, which causes a
+	 * problem if we're already inside one.  Rather than expect all
+	 * SPI-using code to do SPI_push whenever a replan could happen,
+	 * it seems best to take care of the case here.
 	 */
-	if (!plan)
+	spi_pushed = SPI_push_conditional();
+
+	/*
+	 * Generate the plan.
+	 */
+	plist = pg_plan_queries(qlist, plansource->cursor_options, boundParams);
+
+	/* Clean up SPI state */
+	SPI_pop_conditional(spi_pushed);
+
+	/* Release snapshot if we got one */
+	if (snapshot_set)
+		PopActiveSnapshot();
+
+	/* Now we can restore current search path */
+	PopOverrideSearchPath();
+
+	/*
+	 * Make a dedicated memory context for the CachedPlan and its subsidiary
+	 * data.  It's probably not going to be large, but just in case, use the
+	 * default maxsize parameter.  It's transient for the moment.
+	 */
+	plan_context = AllocSetContextCreate(CurrentMemoryContext,
+										 "CachedPlan",
+										 ALLOCSET_SMALL_MINSIZE,
+										 ALLOCSET_SMALL_INITSIZE,
+										 ALLOCSET_DEFAULT_MAXSIZE);
+
+	/*
+	 * Copy plan into the new context.
+	 */
+	oldcxt = MemoryContextSwitchTo(plan_context);
+
+	plist = (List *) copyObject(plist);
+
+	/*
+	 * Create and fill the CachedPlan struct within the new context.
+	 */
+	plan = (CachedPlan *) palloc(sizeof(CachedPlan));
+	plan->magic = CACHEDPLAN_MAGIC;
+	plan->stmt_list = plist;
+	if (plan_list_is_transient(plist))
 	{
-		bool		snapshot_set = false;
-		Node	   *rawtree;
-		List	   *slist;
-		TupleDesc	resultDesc;
+		Assert(TransactionIdIsNormal(TransactionXmin));
+		plan->saved_xmin = TransactionXmin;
+	}
+	else
+		plan->saved_xmin = InvalidTransactionId;
+	plan->refcount = 0;
+	plan->context = plan_context;
+	plan->is_saved = false;
+	plan->is_valid = true;
 
-		/*
-		 * Restore the search_path that was in use when the plan was made. See
-		 * comments for PushOverrideSearchPath about limitations of this.
-		 *
-		 * (XXX is there anything else we really need to restore?)
-		 */
-		PushOverrideSearchPath(plansource->search_path);
+	/* assign generation number to new plan */
+	plan->generation = ++(plansource->generation);
 
-		/*
-		 * If a snapshot is already set (the normal case), we can just use
-		 * that for parsing/planning.  But if it isn't, install one.  Note: no
-		 * point in checking whether parse analysis requires a snapshot;
-		 * utility commands don't have invalidatable plans, so we'd not get
-		 * here for such a command.
-		 */
-		if (!ActiveSnapshotSet())
-		{
-			PushActiveSnapshot(GetTransactionSnapshot());
-			snapshot_set = true;
-		}
+	MemoryContextSwitchTo(oldcxt);
 
-		/*
-		 * Run parse analysis and rule rewriting.  The parser tends to
-		 * scribble on its input, so we must copy the raw parse tree to
-		 * prevent corruption of the cache.
-		 */
-		rawtree = copyObject(plansource->raw_parse_tree);
-		if (plansource->parserSetup != NULL)
-			slist = pg_analyze_and_rewrite_params(rawtree,
-												  plansource->query_string,
-												  plansource->parserSetup,
-												  plansource->parserSetupArg);
-		else
-			slist = pg_analyze_and_rewrite(rawtree,
-										   plansource->query_string,
-										   plansource->param_types,
-										   plansource->num_params);
+	return plan;
+}
 
-		if (plansource->fully_planned)
-		{
-			/*
-			 * Generate plans for queries.
-			 *
-			 * The planner may try to call SPI-using functions, which causes a
-			 * problem if we're already inside one.  Rather than expect all
-			 * SPI-using code to do SPI_push whenever a replan could happen,
-			 * it seems best to take care of the case here.
-			 */
-			bool		pushed;
+/*
+ * choose_custom_plan: choose whether to use custom or generic plan
+ *
+ * This defines the policy followed by GetCachedPlan.
+ */
+static bool
+choose_custom_plan(CachedPlanSource *plansource, ParamListInfo boundParams)
+{
+	double		avg_custom_cost;
 
-			pushed = SPI_push_conditional();
+	/* Never any point in a custom plan if there's no parameters */
+	if (boundParams == NULL)
+		return false;
 
-			slist = pg_plan_queries(slist, plansource->cursor_options, NULL);
+	/* See if caller wants to force the decision */
+	if (plansource->cursor_options & CURSOR_OPT_GENERIC_PLAN)
+		return false;
+	if (plansource->cursor_options & CURSOR_OPT_CUSTOM_PLAN)
+		return true;
 
-			SPI_pop_conditional(pushed);
-		}
+	/* Generate custom plans until we have done at least 5 (arbitrary) */
+	if (plansource->num_custom_plans < 5)
+		return true;
 
-		/*
-		 * Check or update the result tupdesc.	XXX should we use a weaker
-		 * condition than equalTupleDescs() here?
-		 */
-		resultDesc = PlanCacheComputeResultDesc(slist);
-		if (resultDesc == NULL && plansource->resultDesc == NULL)
+	avg_custom_cost = plansource->total_custom_cost / plansource->num_custom_plans;
+
+	/*
+	 * Prefer generic plan if it's less than 10% more expensive than average
+	 * custom plan.  This threshold is a bit arbitrary; it'd be better if we
+	 * had some means of comparing planning time to the estimated runtime
+	 * cost differential.
+	 *
+	 * Note that if generic_cost is -1 (indicating we've not yet determined
+	 * the generic plan cost), we'll always prefer generic at this point.
+	 */
+	if (plansource->generic_cost < avg_custom_cost * 1.1)
+		return false;
+
+	return true;
+}
+
+/*
+ * cached_plan_cost: calculate estimated cost of a plan
+ */
+static double
+cached_plan_cost(CachedPlan *plan)
+{
+	double		result = 0;
+	ListCell   *lc;
+
+	foreach(lc, plan->stmt_list)
+	{
+		PlannedStmt *plannedstmt = (PlannedStmt *) lfirst(lc);
+
+		if (!IsA(plannedstmt, PlannedStmt))
+			continue;			/* Ignore utility statements */
+
+		result += plannedstmt->planTree->total_cost;
+	}
+
+	return result;
+}
+
+/*
+ * GetCachedPlan: get a cached plan from a CachedPlanSource.
+ *
+ * This function hides the logic that decides whether to use a generic
+ * plan or a custom plan for the given parameters: the caller does not know
+ * which it will get.
+ *
+ * On return, the plan is valid and we have sufficient locks to begin
+ * execution.
+ *
+ * On return, the refcount of the plan has been incremented; a later
+ * ReleaseCachedPlan() call is expected.  The refcount has been reported
+ * to the CurrentResourceOwner if useResOwner is true (note that that must
+ * only be true if it's a "saved" CachedPlanSource).
+ *
+ * Note: if any replanning activity is required, the caller's memory context
+ * is used for that work.
+ */
+CachedPlan *
+GetCachedPlan(CachedPlanSource *plansource, ParamListInfo boundParams,
+			  bool useResOwner)
+{
+	CachedPlan *plan;
+	List	   *qlist;
+	bool		customplan;
+
+	/* Assert caller is doing things in a sane order */
+	Assert(plansource->magic == CACHEDPLANSOURCE_MAGIC);
+	Assert(plansource->is_complete);
+	/* This seems worth a real test, though */
+	if (useResOwner && !plansource->is_saved)
+		elog(ERROR, "cannot apply ResourceOwner to non-saved cached plan");
+
+	/* Make sure the querytree list is valid and we have parse-time locks */
+	qlist = RevalidateCachedQuery(plansource);
+
+	/* Decide whether to use a custom plan */
+	customplan = choose_custom_plan(plansource, boundParams);
+
+	if (!customplan)
+	{
+		if (CheckCachedPlan(plansource))
 		{
-			/* OK, doesn't return tuples */
+			/* We want a generic plan, and we already have a valid one */
+			plan = plansource->gplan;
+			Assert(plan->magic == CACHEDPLAN_MAGIC);
 		}
-		else if (resultDesc == NULL || plansource->resultDesc == NULL ||
-				 !equalTupleDescs(resultDesc, plansource->resultDesc))
+		else
 		{
-			MemoryContext oldcxt;
-
-			/* can we give a better error message? */
-			if (plansource->fixed_result)
-				ereport(ERROR,
-						(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
-						 errmsg("cached plan must not change result type")));
-			oldcxt = MemoryContextSwitchTo(plansource->context);
-			if (resultDesc)
-				resultDesc = CreateTupleDescCopy(resultDesc);
-			if (plansource->resultDesc)
-				FreeTupleDesc(plansource->resultDesc);
-			plansource->resultDesc = resultDesc;
-			MemoryContextSwitchTo(oldcxt);
-		}
-
-		/* Release snapshot if we got one */
-		if (snapshot_set)
-			PopActiveSnapshot();
-
-		/* Now we can restore current search path */
-		PopOverrideSearchPath();
+			/* Build a new generic plan */
+			plan = BuildCachedPlan(plansource, qlist, NULL);
+			/* Just make real sure plansource->gplan is clear */
+			ReleaseGenericPlan(plansource);
+			/* Link the new generic plan into the plansource */
+			plansource->gplan = plan;
+			plan->refcount++;
+			/* Immediately reparent into appropriate context */
+			if (plansource->is_saved)
+			{
+				/* saved plans all live under CacheMemoryContext */
+				MemoryContextSetParent(plan->context, CacheMemoryContext);
+				plan->is_saved = true;
+			}
+			else
+			{
+				/* otherwise, it should be a sibling of the plansource */
+				MemoryContextSetParent(plan->context,
+									   MemoryContextGetParent(plansource->context));
+			}
+			/* Update generic_cost whenever we make a new generic plan */
+			plansource->generic_cost = cached_plan_cost(plan);
 
-		/*
-		 * Store the plans into the plancache entry, advancing the generation
-		 * count.
-		 */
-		StoreCachedPlan(plansource, slist, NULL);
+			/*
+			 * If, based on the now-known value of generic_cost, we'd not have
+			 * chosen to use a generic plan, then forget it and make a custom
+			 * plan.  This is a bit of a wart but is necessary to avoid a
+			 * glitch in behavior when the custom plans are consistently big
+			 * winners; at some point we'll experiment with a generic plan and
+			 * find it's a loser, but we don't want to actually execute that
+			 * plan.
+			 */
+			customplan = choose_custom_plan(plansource, boundParams);
+		}
+	}
 
-		plan = plansource->plan;
+	if (customplan)
+	{
+		/* Build a custom plan */
+		plan = BuildCachedPlan(plansource, qlist, boundParams);
+		/* Accumulate total costs of custom plans, but 'ware overflow */
+		if (plansource->num_custom_plans < INT_MAX)
+		{
+			plansource->total_custom_cost += cached_plan_cost(plan);
+			plansource->num_custom_plans++;
+		}
 	}
 
-	/*
-	 * Last step: flag the plan as in use by caller.
-	 */
+	/* Flag the plan as in use by caller */
 	if (useResOwner)
 		ResourceOwnerEnlargePlanCacheRefs(CurrentResourceOwner);
 	plan->refcount++;
 	if (useResOwner)
 		ResourceOwnerRememberPlanCacheRef(CurrentResourceOwner, plan);
 
+	/*
+	 * Saved plans should be under CacheMemoryContext so they will not go away
+	 * until their reference count goes to zero.  In the generic-plan cases we
+	 * already took care of that, but for a custom plan, do it as soon as we
+	 * have created a reference-counted link.
+	 */
+	if (customplan && plansource->is_saved)
+	{
+		MemoryContextSetParent(plan->context, CacheMemoryContext);
+		plan->is_saved = true;
+	}
+
 	return plan;
 }
 
@@ -635,8 +1019,12 @@ RevalidateCachedPlan(CachedPlanSource *plansource, bool useResOwner)
 void
 ReleaseCachedPlan(CachedPlan *plan, bool useResOwner)
 {
+	Assert(plan->magic == CACHEDPLAN_MAGIC);
 	if (useResOwner)
+	{
+		Assert(plan->is_saved);
 		ResourceOwnerForgetPlanCacheRef(CurrentResourceOwner, plan);
+	}
 	Assert(plan->refcount > 0);
 	plan->refcount--;
 	if (plan->refcount == 0)
@@ -644,8 +1032,125 @@ ReleaseCachedPlan(CachedPlan *plan, bool useResOwner)
 }
 
 /*
- * CachedPlanIsValid: test whether the plan within a CachedPlanSource is
- * currently valid (that is, not marked as being in need of revalidation).
+ * CachedPlanSetParentContext: move a CachedPlanSource to a new memory context
+ *
+ * This can only be applied to unsaved plans; once saved, a plan always
+ * lives underneath CacheMemoryContext.
+ */
+void
+CachedPlanSetParentContext(CachedPlanSource *plansource,
+						   MemoryContext newcontext)
+{
+	/* Assert caller is doing things in a sane order */
+	Assert(plansource->magic == CACHEDPLANSOURCE_MAGIC);
+	Assert(plansource->is_complete);
+
+	/* This seems worth a real test, though */
+	if (plansource->is_saved)
+		elog(ERROR, "cannot move a saved cached plan to another context");
+
+	/* OK, let the caller keep the plan where he wishes */
+	MemoryContextSetParent(plansource->context, newcontext);
+
+	/*
+	 * The query_context needs no special handling, since it's a child of
+	 * plansource->context.  But if there's a generic plan, it should be
+	 * maintained as a sibling of plansource->context.
+	 */
+	if (plansource->gplan)
+	{
+		Assert(plansource->gplan->magic == CACHEDPLAN_MAGIC);
+		MemoryContextSetParent(plansource->gplan->context, newcontext);
+	}
+}
+
+/*
+ * CopyCachedPlan: make a copy of a CachedPlanSource
+ *
+ * This is a convenience routine that does the equivalent of
+ * CreateCachedPlan + CompleteCachedPlan, using the data stored in the
+ * input CachedPlanSource.  The result is therefore "unsaved" (regardless
+ * of the state of the source), and we don't copy any generic plan either.
+ * The result will be currently valid, or not, the same as the source.
+ */
+CachedPlanSource *
+CopyCachedPlan(CachedPlanSource *plansource)
+{
+	CachedPlanSource *newsource;
+	MemoryContext source_context;
+	MemoryContext querytree_context;
+	MemoryContext oldcxt;
+
+	Assert(plansource->magic == CACHEDPLANSOURCE_MAGIC);
+	Assert(plansource->is_complete);
+
+	source_context = AllocSetContextCreate(CurrentMemoryContext,
+										   "CachedPlanSource",
+										   ALLOCSET_SMALL_MINSIZE,
+										   ALLOCSET_SMALL_INITSIZE,
+										   ALLOCSET_DEFAULT_MAXSIZE);
+
+	oldcxt = MemoryContextSwitchTo(source_context);
+
+	newsource = (CachedPlanSource *) palloc0(sizeof(CachedPlanSource));
+	newsource->magic = CACHEDPLANSOURCE_MAGIC;
+	newsource->raw_parse_tree = copyObject(plansource->raw_parse_tree);
+	newsource->query_string = pstrdup(plansource->query_string);
+	newsource->commandTag = plansource->commandTag;
+	if (plansource->num_params > 0)
+	{
+		newsource->param_types = (Oid *)
+			palloc(plansource->num_params * sizeof(Oid));
+		memcpy(newsource->param_types, plansource->param_types,
+			   plansource->num_params * sizeof(Oid));
+	}
+	else
+		newsource->param_types = NULL;
+	newsource->num_params = plansource->num_params;
+	newsource->parserSetup = plansource->parserSetup;
+	newsource->parserSetupArg = plansource->parserSetupArg;
+	newsource->cursor_options = plansource->cursor_options;
+	newsource->fixed_result = plansource->fixed_result;
+	if (plansource->resultDesc)
+		newsource->resultDesc = CreateTupleDescCopy(plansource->resultDesc);
+	else
+		newsource->resultDesc = NULL;
+	newsource->search_path = CopyOverrideSearchPath(plansource->search_path);
+	newsource->context = source_context;
+
+	querytree_context = AllocSetContextCreate(source_context,
+											  "CachedPlanQuery",
+											  ALLOCSET_SMALL_MINSIZE,
+											  ALLOCSET_SMALL_INITSIZE,
+											  ALLOCSET_DEFAULT_MAXSIZE);
+	MemoryContextSwitchTo(querytree_context);
+	newsource->query_list = (List *) copyObject(plansource->query_list);
+	newsource->relationOids = (List *) copyObject(plansource->relationOids);
+	newsource->invalItems = (List *) copyObject(plansource->invalItems);
+	newsource->query_context = querytree_context;
+
+	newsource->gplan = NULL;
+
+	newsource->is_complete = true;
+	newsource->is_saved = false;
+	newsource->is_valid = plansource->is_valid;
+	newsource->generation = plansource->generation;
+	newsource->next_saved = NULL;
+
+	/* We may as well copy any acquired cost knowledge */
+	newsource->generic_cost = plansource->generic_cost;
+	newsource->total_custom_cost = plansource->total_custom_cost;
+	newsource->num_custom_plans = plansource->num_custom_plans;
+
+	MemoryContextSwitchTo(oldcxt);
+
+	return newsource;
+}
+
+/*
+ * CachedPlanIsValid: test whether the rewritten querytree within a
+ * CachedPlanSource is currently valid (that is, not marked as being in need
+ * of revalidation).
  *
  * This result is only trustworthy (ie, free from race conditions) if
  * the caller has acquired locks on all the relations used in the plan.
@@ -653,37 +1158,44 @@ ReleaseCachedPlan(CachedPlan *plan, bool useResOwner)
 bool
 CachedPlanIsValid(CachedPlanSource *plansource)
 {
-	CachedPlan *plan;
+	Assert(plansource->magic == CACHEDPLANSOURCE_MAGIC);
+	return plansource->is_valid;
+}
 
-	/* Validity check that we were given a CachedPlanSource */
-	Assert(list_member_ptr(cached_plans_list, plansource));
+/*
+ * CachedPlanGetTargetList: return tlist, if any, describing plan's output
+ *
+ * The result is guaranteed up-to-date.  However, it is local storage
+ * within the cached plan, and may disappear next time the plan is updated.
+ */
+List *
+CachedPlanGetTargetList(CachedPlanSource *plansource)
+{
+	Node	   *pstmt;
 
-	plan = plansource->plan;
-	if (plan && !plan->dead)
-	{
-		/*
-		 * Plan must have positive refcount because it is referenced by
-		 * plansource; so no need to fear it disappears under us here.
-		 */
-		Assert(plan->refcount > 0);
+	/* Assert caller is doing things in a sane order */
+	Assert(plansource->magic == CACHEDPLANSOURCE_MAGIC);
+	Assert(plansource->is_complete);
 
-		/*
-		 * Although we don't want to acquire locks here, it still seems useful
-		 * to check for expiration of a transient plan.
-		 */
-		if (TransactionIdIsValid(plan->saved_xmin) &&
-			!TransactionIdEquals(plan->saved_xmin, TransactionXmin))
-			plan->dead = true;
-		else
-			return true;
-	}
+	/*
+	 * No work needed if statement doesn't return tuples (we assume this
+	 * feature cannot be changed by an invalidation)
+	 */
+	if (plansource->resultDesc == NULL)
+		return NIL;
 
-	return false;
+	/* Make sure the querytree list is valid and we have parse-time locks */
+	RevalidateCachedQuery(plansource);
+
+	/* Get the primary statement and find out what it returns */
+	pstmt = PortalListGetPrimaryStmt(plansource->query_list);
+
+	return FetchStatementTargetList(pstmt);
 }
 
 /*
- * AcquireExecutorLocks: acquire locks needed for execution of a fully-planned
- * cached plan; or release them if acquire is false.
+ * AcquireExecutorLocks: acquire locks needed for execution of a cached plan;
+ * or release them if acquire is false.
  */
 static void
 AcquireExecutorLocks(List *stmt_list, bool acquire)
@@ -752,8 +1264,8 @@ AcquireExecutorLocks(List *stmt_list, bool acquire)
 }
 
 /*
- * AcquirePlannerLocks: acquire locks needed for planning and execution of a
- * not-fully-planned cached plan; or release them if acquire is false.
+ * AcquirePlannerLocks: acquire locks needed for planning of a querytree list;
+ * or release them if acquire is false.
  *
  * Note that we don't actually try to open the relations, and hence will not
  * fail if one has been dropped entirely --- we'll just transiently acquire
@@ -903,64 +1415,36 @@ plan_list_is_transient(List *stmt_list)
 }
 
 /*
- * PlanCacheComputeResultDesc: given a list of either fully-planned statements
- * or Queries, determine the result tupledesc it will produce.	Returns NULL
- * if the execution will not return tuples.
+ * PlanCacheComputeResultDesc: given a list of analyzed-and-rewritten Queries,
+ * determine the result tupledesc it will produce.  Returns NULL if the
+ * execution will not return tuples.
  *
  * Note: the result is created or copied into current memory context.
  */
-TupleDesc
+static TupleDesc
 PlanCacheComputeResultDesc(List *stmt_list)
 {
-	Node	   *node;
 	Query	   *query;
-	PlannedStmt *pstmt;
 
 	switch (ChoosePortalStrategy(stmt_list))
 	{
 		case PORTAL_ONE_SELECT:
 		case PORTAL_ONE_MOD_WITH:
-			node = (Node *) linitial(stmt_list);
-			if (IsA(node, Query))
-			{
-				query = (Query *) node;
-				return ExecCleanTypeFromTL(query->targetList, false);
-			}
-			if (IsA(node, PlannedStmt))
-			{
-				pstmt = (PlannedStmt *) node;
-				return ExecCleanTypeFromTL(pstmt->planTree->targetlist, false);
-			}
-			/* other cases shouldn't happen, but return NULL */
-			break;
+			query = (Query *) linitial(stmt_list);
+			Assert(IsA(query, Query));
+			return ExecCleanTypeFromTL(query->targetList, false);
 
 		case PORTAL_ONE_RETURNING:
-			node = PortalListGetPrimaryStmt(stmt_list);
-			if (IsA(node, Query))
-			{
-				query = (Query *) node;
-				Assert(query->returningList);
-				return ExecCleanTypeFromTL(query->returningList, false);
-			}
-			if (IsA(node, PlannedStmt))
-			{
-				pstmt = (PlannedStmt *) node;
-				Assert(pstmt->hasReturning);
-				return ExecCleanTypeFromTL(pstmt->planTree->targetlist, false);
-			}
-			/* other cases shouldn't happen, but return NULL */
-			break;
+			query = (Query *) PortalListGetPrimaryStmt(stmt_list);
+			Assert(IsA(query, Query));
+			Assert(query->returningList);
+			return ExecCleanTypeFromTL(query->returningList, false);
 
 		case PORTAL_UTIL_SELECT:
-			node = (Node *) linitial(stmt_list);
-			if (IsA(node, Query))
-			{
-				query = (Query *) node;
-				Assert(query->utilityStmt);
-				return UtilityTupleDescriptor(query->utilityStmt);
-			}
-			/* else it's a bare utility statement */
-			return UtilityTupleDescriptor(node);
+			query = (Query *) linitial(stmt_list);
+			Assert(IsA(query, Query));
+			Assert(query->utilityStmt);
+			return UtilityTupleDescriptor(query->utilityStmt);
 
 		case PORTAL_MULTI_QUERY:
 			/* will not return tuples */
@@ -979,33 +1463,39 @@ PlanCacheComputeResultDesc(List *stmt_list)
 static void
 PlanCacheRelCallback(Datum arg, Oid relid)
 {
-	ListCell   *lc1;
+	CachedPlanSource *plansource;
 
-	foreach(lc1, cached_plans_list)
+	for (plansource = first_saved_plan; plansource; plansource = plansource->next_saved)
 	{
-		CachedPlanSource *plansource = (CachedPlanSource *) lfirst(lc1);
-		CachedPlan *plan = plansource->plan;
+		Assert(plansource->magic == CACHEDPLANSOURCE_MAGIC);
 
 		/* No work if it's already invalidated */
-		if (!plan || plan->dead)
+		if (!plansource->is_valid)
 			continue;
 
 		/*
-		 * Check the list we built ourselves; this covers unplanned cases
-		 * including EXPLAIN.
+		 * Check the dependency list for the rewritten querytree.
 		 */
-		if ((relid == InvalidOid) ? plan->relationOids != NIL :
-			list_member_oid(plan->relationOids, relid))
-			plan->dead = true;
+		if ((relid == InvalidOid) ? plansource->relationOids != NIL :
+			list_member_oid(plansource->relationOids, relid))
+		{
+			/* Invalidate the querytree and generic plan */
+			plansource->is_valid = false;
+			if (plansource->gplan)
+				plansource->gplan->is_valid = false;
+		}
 
-		if (plan->fully_planned && !plan->dead)
+		/*
+		 * The generic plan, if any, could have more dependencies than the
+		 * querytree does, so we have to check it too.
+		 */
+		if (plansource->gplan && plansource->gplan->is_valid)
 		{
-			/* Have to check the per-PlannedStmt relid lists */
-			ListCell   *lc2;
+			ListCell   *lc;
 
-			foreach(lc2, plan->stmt_list)
+			foreach(lc, plansource->gplan->stmt_list)
 			{
-				PlannedStmt *plannedstmt = (PlannedStmt *) lfirst(lc2);
+				PlannedStmt *plannedstmt = (PlannedStmt *) lfirst(lc);
 
 				Assert(!IsA(plannedstmt, Query));
 				if (!IsA(plannedstmt, PlannedStmt))
@@ -1013,8 +1503,8 @@ PlanCacheRelCallback(Datum arg, Oid relid)
 				if ((relid == InvalidOid) ? plannedstmt->relationOids != NIL :
 					list_member_oid(plannedstmt->relationOids, relid))
 				{
-					/* Invalidate the plan! */
-					plan->dead = true;
+					/* Invalidate the generic plan only */
+					plansource->gplan->is_valid = false;
 					break;		/* out of stmt_list scan */
 				}
 			}
@@ -1035,43 +1525,47 @@ PlanCacheRelCallback(Datum arg, Oid relid)
 static void
 PlanCacheFuncCallback(Datum arg, int cacheid, uint32 hashvalue)
 {
-	ListCell   *lc1;
+	CachedPlanSource *plansource;
 
-	foreach(lc1, cached_plans_list)
+	for (plansource = first_saved_plan; plansource; plansource = plansource->next_saved)
 	{
-		CachedPlanSource *plansource = (CachedPlanSource *) lfirst(lc1);
-		CachedPlan *plan = plansource->plan;
-		ListCell   *lc2;
+		ListCell   *lc;
+
+		Assert(plansource->magic == CACHEDPLANSOURCE_MAGIC);
 
 		/* No work if it's already invalidated */
-		if (!plan || plan->dead)
+		if (!plansource->is_valid)
 			continue;
 
 		/*
-		 * Check the list we built ourselves; this covers unplanned cases
-		 * including EXPLAIN.
+		 * Check the dependency list for the rewritten querytree.
 		 */
-		foreach(lc2, plan->invalItems)
+		foreach(lc, plansource->invalItems)
 		{
-			PlanInvalItem *item = (PlanInvalItem *) lfirst(lc2);
+			PlanInvalItem *item = (PlanInvalItem *) lfirst(lc);
 
 			if (item->cacheId != cacheid)
 				continue;
 			if (hashvalue == 0 ||
 				item->hashValue == hashvalue)
 			{
-				/* Invalidate the plan! */
-				plan->dead = true;
+				/* Invalidate the querytree and generic plan */
+				plansource->is_valid = false;
+				if (plansource->gplan)
+					plansource->gplan->is_valid = false;
 				break;
 			}
 		}
 
-		if (plan->fully_planned && !plan->dead)
+		/*
+		 * The generic plan, if any, could have more dependencies than the
+		 * querytree does, so we have to check it too.
+		 */
+		if (plansource->gplan && plansource->gplan->is_valid)
 		{
-			/* Have to check the per-PlannedStmt inval-item lists */
-			foreach(lc2, plan->stmt_list)
+			foreach(lc, plansource->gplan->stmt_list)
 			{
-				PlannedStmt *plannedstmt = (PlannedStmt *) lfirst(lc2);
+				PlannedStmt *plannedstmt = (PlannedStmt *) lfirst(lc);
 				ListCell   *lc3;
 
 				Assert(!IsA(plannedstmt, Query));
@@ -1086,12 +1580,12 @@ PlanCacheFuncCallback(Datum arg, int cacheid, uint32 hashvalue)
 					if (hashvalue == 0 ||
 						item->hashValue == hashvalue)
 					{
-						/* Invalidate the plan! */
-						plan->dead = true;
+						/* Invalidate the generic plan only */
+						plansource->gplan->is_valid = false;
 						break;	/* out of invalItems scan */
 					}
 				}
-				if (plan->dead)
+				if (!plansource->gplan->is_valid)
 					break;		/* out of stmt_list scan */
 			}
 		}
@@ -1111,65 +1605,46 @@ PlanCacheSysCallback(Datum arg, int cacheid, uint32 hashvalue)
 }
 
 /*
- * ResetPlanCache: drop all cached plans.
+ * ResetPlanCache: invalidate all cached plans.
  */
 void
 ResetPlanCache(void)
 {
-	ListCell   *lc1;
+	CachedPlanSource *plansource;
 
-	foreach(lc1, cached_plans_list)
+	for (plansource = first_saved_plan; plansource; plansource = plansource->next_saved)
 	{
-		CachedPlanSource *plansource = (CachedPlanSource *) lfirst(lc1);
-		CachedPlan *plan = plansource->plan;
-		ListCell   *lc2;
+		ListCell   *lc;
+
+		Assert(plansource->magic == CACHEDPLANSOURCE_MAGIC);
 
 		/* No work if it's already invalidated */
-		if (!plan || plan->dead)
+		if (!plansource->is_valid)
 			continue;
 
 		/*
-		 * We *must not* mark transaction control statements as dead,
+		 * We *must not* mark transaction control statements as invalid,
 		 * particularly not ROLLBACK, because they may need to be executed in
 		 * aborted transactions when we can't revalidate them (cf bug #5269).
 		 * In general there is no point in invalidating utility statements
-		 * since they have no plans anyway.  So mark it dead only if it
+		 * since they have no plans anyway.  So invalidate it only if it
 		 * contains at least one non-utility statement.  (EXPLAIN counts as a
 		 * non-utility statement, though, since it contains an analyzed query
 		 * that might have dependencies.)
 		 */
-		if (plan->fully_planned)
+		foreach(lc, plansource->query_list)
 		{
-			/* Search statement list for non-utility statements */
-			foreach(lc2, plan->stmt_list)
-			{
-				PlannedStmt *plannedstmt = (PlannedStmt *) lfirst(lc2);
+			Query	   *query = (Query *) lfirst(lc);
 
-				Assert(!IsA(plannedstmt, Query));
-				if (IsA(plannedstmt, PlannedStmt) ||
-					IsA(plannedstmt, ExplainStmt))
-				{
-					/* non-utility statement, so invalidate */
-					plan->dead = true;
-					break;		/* out of stmt_list scan */
-				}
-			}
-		}
-		else
-		{
-			/* Search Query list for non-utility statements */
-			foreach(lc2, plan->stmt_list)
+			Assert(IsA(query, Query));
+			if (query->commandType != CMD_UTILITY ||
+				IsA(query->utilityStmt, ExplainStmt))
 			{
-				Query	   *query = (Query *) lfirst(lc2);
-
-				Assert(IsA(query, Query));
-				if (query->commandType != CMD_UTILITY ||
-					IsA(query->utilityStmt, ExplainStmt))
-				{
-					/* non-utility statement, so invalidate */
-					plan->dead = true;
-					break;		/* out of stmt_list scan */
-				}
+				/* non-utility statement, so invalidate */
+				plansource->is_valid = false;
+				if (plansource->gplan)
+					plansource->gplan->is_valid = false;
+				break;
 			}
 		}
 	}