Hi,
I've been working on a patch to add a little cache to SubPlans, to speed
up queries with correlated subqueries, where the same subquery is
currently executed multiple times with the same parameters. The idea is
to cache the result of the subplan, with the correlation vars as the
cache key.
That helps a lot, if you happen to have that kind of a query. I bumped
into this while looking at TPC-DS query 6:
select a.ca_state state, count(*) cnt
from customer_address a
,customer c
,store_sales s
,date_dim d
,item i
where a.ca_address_sk = c.c_current_addr_sk
and c.c_customer_sk = s.ss_customer_sk
and s.ss_sold_date_sk = d.d_date_sk
and s.ss_item_sk = i.i_item_sk
and d.d_month_seq =
(select distinct (d_month_seq)
from date_dim
where d_year = 2000
and d_moy = 5 )
and i.i_current_price > 1.2 *
(select avg(j.i_current_price)
from item j
where j.i_category = i.i_category)
group by a.ca_state
having count(*) >= 10
order by cnt
The first subquery is uncorrelated, and is already handled efficiently
as an InitPlan. This patch helps with the second subquery. There are
only 11 different categories, but we currently re-execute it for every
row of the outer query, over 26000 times. (I think I have about 1 GB of
data in my little database I've been testing with, I'm not sure how this
would scale with the amount of data.) With this patch, it's only
executed 11 times, the cache avoids the rest of the executions. That
brings the runtime, on my laptop, from about 30 s to 120 ms.
For this particular query, I actually wish we could pull up that
subquery, instead. I did some investigation into that last summer,
https://www.postgresql.org/message-id/67e353e8-c20e-7980-a282-538779edf25b%40iki.fi,
but that's a much bigger project. In any case, even if the planner was
able to pull up subqueries in more cases, a cache like this would still
be helpful for those cases where pulling up was still not possible.
Thoughts?
- Heikki
>From d3a738ea6427df908b61a5fdd3ee14a7b78b724a Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakan...@iki.fi>
Date: Tue, 22 May 2018 08:59:33 +0300
Subject: [PATCH 1/3] Add comment to explain that SubPlan can return its
results in two ways.
It took me a while to understand this, I hope this helps the next person
reading the code to grok it faster.
---
src/backend/executor/nodeSubplan.c | 6 ++++++
1 file changed, 6 insertions(+)
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index 44f551bcf1..aab1c7942a 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -10,6 +10,12 @@
* direct correlation variables from the parent plan level), and "regular"
* subplans, which are re-evaluated every time their result is required.
*
+ * There are two ways a SubPlan node can return the result. The first is
+ * that ExecSubPlan() runs the subquery, and returns its result like any
+ * other expression. The second way is to return the result in executor
+ * Params. In this method, the execution happens when ExecSetParamPlan() is
+ * called, and the subquery's results are set as the current values of
+ * executor Params, as indicated by SubPlan->setParam.
*
* Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
--
2.11.0
>From fcf040b589ffc318cbbc060deec296577b3ff24b Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakan...@iki.fi>
Date: Tue, 22 May 2018 09:05:38 +0300
Subject: [PATCH 2/3] Remove some unused code.
---
src/backend/executor/nodeSubplan.c | 10 ----------
src/include/nodes/execnodes.h | 1 -
2 files changed, 11 deletions(-)
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index aab1c7942a..909f77905c 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -802,7 +802,6 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
sstate->keyColIdx = NULL;
sstate->tab_eq_funcoids = NULL;
sstate->tab_hash_funcs = NULL;
- sstate->tab_eq_funcs = NULL;
sstate->lhs_hash_funcs = NULL;
sstate->cur_eq_funcs = NULL;
@@ -900,7 +899,6 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
lefttlist = righttlist = NIL;
sstate->tab_eq_funcoids = (Oid *) palloc(ncols * sizeof(Oid));
sstate->tab_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
- sstate->tab_eq_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
sstate->lhs_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
sstate->cur_eq_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
i = 1;
@@ -909,7 +907,6 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
OpExpr *opexpr = lfirst_node(OpExpr, l);
Expr *expr;
TargetEntry *tle;
- Oid rhs_eq_oper;
Oid left_hashfn;
Oid right_hashfn;
@@ -936,13 +933,6 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
fmgr_info(opexpr->opfuncid, &sstate->cur_eq_funcs[i - 1]);
fmgr_info_set_expr((Node *) opexpr, &sstate->cur_eq_funcs[i - 1]);
- /* Look up the equality function for the RHS type */
- if (!get_compatible_hash_operators(opexpr->opno,
- NULL, &rhs_eq_oper))
- elog(ERROR, "could not find compatible hash operator for operator %u",
- opexpr->opno);
- fmgr_info(get_opcode(rhs_eq_oper), &sstate->tab_eq_funcs[i - 1]);
-
/* Lookup the associated hash functions */
if (!get_op_hash_functions(opexpr->opno,
&left_hashfn, &right_hashfn))
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index da7f52cab0..1f3c786b30 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -839,7 +839,6 @@ typedef struct SubPlanState
Oid *tab_eq_funcoids; /* equality func oids for table
* datatype(s) */
FmgrInfo *tab_hash_funcs; /* hash functions for table datatype(s) */
- FmgrInfo *tab_eq_funcs; /* equality functions for table datatype(s) */
FmgrInfo *lhs_hash_funcs; /* hash functions for lefthand datatype(s) */
FmgrInfo *cur_eq_funcs; /* equality functions for LHS vs. table */
ExprState *cur_eq_comp; /* equality comparator for LHS vs. table */
--
2.11.0
>From ff8630a06eee0fc39dc03dc7f8eed0ea271f29ff Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakan...@iki.fi>
Date: Wed, 10 May 2017 13:29:09 +0300
Subject: [PATCH 3/3] Add a Param -> result cache to SubPlan nodes.
---
src/backend/executor/nodeSubplan.c | 466 ++++++++++++++++++++++++++++++++-
src/backend/optimizer/plan/subselect.c | 86 +++++-
src/include/nodes/execnodes.h | 25 +-
src/include/nodes/primnodes.h | 5 +
4 files changed, 568 insertions(+), 14 deletions(-)
diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c
index 909f77905c..287010dee2 100644
--- a/src/backend/executor/nodeSubplan.c
+++ b/src/backend/executor/nodeSubplan.c
@@ -17,6 +17,17 @@
* called, and the subquery's results are set as the current values of
* executor Params, as indicated by SubPlan->setParam.
*
+ * For correlated subplans, which need to be re-evaluated every time the
+ * outer parameter values change, we optionally keep a cache of the results.
+ * If the subplan is called again with the same set of parameters, we can
+ * avoid re-executing the subquery, and return the result from the cache
+ * instead. This helps a lot if the subplan is expensive, and the same
+ * parameters are used many times.
+ *
+ * TODO: The cache is currently only used in ExecSubPlan, not
+ * ExecSetParamPlan.
+ *
+ *
* Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
@@ -38,10 +49,14 @@
#include "access/htup_details.h"
#include "executor/executor.h"
#include "executor/nodeSubplan.h"
+#include "lib/ilist.h"
#include "nodes/makefuncs.h"
+#include "nodes/nodeFuncs.h"
#include "miscadmin.h"
#include "optimizer/clauses.h"
#include "utils/array.h"
+#include "utils/datum.h"
+#include "utils/hashutils.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
@@ -58,6 +73,60 @@ static bool findPartialMatch(TupleHashTable hashtable, TupleTableSlot *slot,
static bool slotAllNulls(TupleTableSlot *slot);
static bool slotNoNulls(TupleTableSlot *slot);
+/*
+ * Subplan result cache.
+ *
+ * If the subplan doesn't contain volatile expressions, we can avoid
+ * executing it repeatedly for the same parameters, by caching the results.
+ *
+ * The cache is a hash table. The cache key consists of the parameter values.
+ * The number of parameters depends on the subquery, so we keep them at the
+ * end of the struct.
+ *
+ * The cached result is the final result of ExecSubPlan, after evaluating any
+ * 'testexpr' or other sublink-specific processing. For ARRAY type sublink,
+ * it is the fully formed array, for EXISTS and ROWCOMPARE, it is a boolean.
+ *
+ * The cache is of fixed size. If it fills up, we throw away old entries,
+ * using a simple LRU policy.
+ */
+typedef struct
+{
+ Datum result; /* result of the SubPlan with this param */
+ bool resultNull;
+
+ dlist_node lru_link; /* link in the LRU list. */
+
+ /*
+ * SubPlan parameters. These form the cache key.
+ *
+ * After the 'params', there is a corresponding array of 'isnull' flags.
+ * Use SUBPLAN_RESULT_CACHE_ENTRY_GET_NULLS to access it.
+ */
+ Datum params[FLEXIBLE_ARRAY_MEMBER];
+
+ /* bool paramNulls[FLEXIBLE_ARRAY_MEMBER]; */
+
+} SubPlanResultCacheEntry;
+
+/* Macros to work with SubPlanResultCacheEntry */
+#define SUBPLAN_RESULT_CACHE_KEY_SIZE(numparams) \
+ ((numparams) * sizeof(Datum) + (numparams) * sizeof(bool))
+#define SUBPLAN_RESULT_CACHE_ENTRY_SIZE(numparams) \
+ (offsetof(SubPlanResultCacheEntry, params) + \
+ SUBPLAN_RESULT_CACHE_KEY_SIZE(numparams))
+
+#define SUBPLAN_RESULT_CACHE_ENTRY_GET_NULLS(entry, numparams) \
+ ((bool *) &(entry)->params[numparams])
+
+static void init_result_cache(SubPlanState *sstate);
+static SubPlanResultCacheEntry * lookup_result_cache(SubPlanState *sstate,
+ SubPlanResultCacheEntry *key, bool *found);
+static uint32 result_cache_hash(const void *key, Size keysize);
+static int result_cache_match(const void *key1, const void *key2, Size keysize);
+static void *result_cache_keycopy(void *dest, const void *src, Size keysize);
+
+static SubPlanState *curr_sstate;
/* ----------------------------------------------------------------
* ExecSubPlan
@@ -230,6 +299,10 @@ ExecScanSubPlan(SubPlanState *node,
ListCell *pvar;
ListCell *l;
ArrayBuildStateAny *astate = NULL;
+ SubPlanResultCacheEntry *resultCacheEntry = NULL;
+ int i;
+ Datum *currParams;
+ bool *currParamNulls;
/*
* MULTIEXPR subplans, when "executed", just return NULL; but first we
@@ -263,6 +336,12 @@ ExecScanSubPlan(SubPlanState *node,
CurrentMemoryContext, true);
/*
+ * If first time through, initialize the result cache.
+ */
+ if (subplan->useResultCache && node->resultcachetab == NULL)
+ init_result_cache(node);
+
+ /*
* We are probably in a short-lived expression-evaluation context. Switch
* to the per-query context for manipulating the child plan's chgParam,
* calling ExecProcNode on it, etc.
@@ -276,6 +355,9 @@ ExecScanSubPlan(SubPlanState *node,
*/
Assert(list_length(subplan->parParam) == list_length(node->args));
+ i = 0;
+ currParams = ((SubPlanResultCacheEntry *) node->currCacheKey)->params;
+ currParamNulls = SUBPLAN_RESULT_CACHE_ENTRY_GET_NULLS((SubPlanResultCacheEntry *) node->currCacheKey, node->numparams);
forboth(l, subplan->parParam, pvar, node->args)
{
int paramid = lfirst_int(l);
@@ -285,6 +367,51 @@ ExecScanSubPlan(SubPlanState *node,
econtext,
&(prm->isnull));
planstate->chgParam = bms_add_member(planstate->chgParam, paramid);
+
+ if (subplan->useResultCache)
+ {
+ currParams[i] = prm->value;
+ currParamNulls[i] = prm->isnull;
+ }
+
+ i++;
+ }
+
+ /*
+ * If we're caching the subplan results, check the cache first.
+ *
+ * On cache miss, this creates a new entry for this set of parameters.
+ * We'll fill it with the subplan's result later.
+ */
+ if (subplan->useResultCache)
+ {
+ bool found;
+
+ resultCacheEntry = lookup_result_cache(node, node->currCacheKey,
+ &found);
+ if (found)
+ {
+ /*
+ * Cache hit. If the result datatype is pass-by-ref, make a copy
+ * of it in a short-lived memory context.
+ */
+ if (resultCacheEntry->resultNull)
+ {
+ result = (Datum) 0;
+ *isNull = true;
+ }
+ else
+ {
+ result = datumCopy(resultCacheEntry->result,
+ node->resultByVal,
+ node->resultLen);
+ *isNull = false;
+ }
+
+ return result;
+ }
+
+ /* Not found. Fall through to execute the subplan. */
}
/*
@@ -456,6 +583,31 @@ ExecScanSubPlan(SubPlanState *node,
}
}
+ /*
+ * If we're using the result cache, copy the result of the subplan into
+ * the cache entry.
+ */
+ if (resultCacheEntry)
+ {
+ if (*isNull)
+ {
+ resultCacheEntry->result = (Datum) 0;
+ resultCacheEntry->resultNull = true;
+ }
+ else
+ {
+ MemoryContext oldcxt = MemoryContextSwitchTo(node->hashtablecxt);
+
+ resultCacheEntry->result = datumCopy(result,
+ node->resultByVal,
+ node->resultLen);
+ resultCacheEntry->resultNull = false;
+ MemoryContextSwitchTo(oldcxt);
+ if (!node->resultByVal)
+ node->memUsed += GetMemoryChunkSpace(DatumGetPointer(resultCacheEntry->result));
+ }
+ }
+
return result;
}
@@ -831,6 +983,24 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
}
/*
+ * Initialize memory contexts used by the initplan hash table or the
+ * result cache.
+ */
+ if (subplan->useHashTable || subplan->useResultCache)
+ {
+ /* We need a memory context to hold the hash table(s) */
+ sstate->hashtablecxt =
+ AllocSetContextCreate(CurrentMemoryContext,
+ "Subplan HashTable Context",
+ ALLOCSET_DEFAULT_SIZES);
+ /* and a small one for the hash tables to use as temp storage */
+ sstate->hashtempcxt =
+ AllocSetContextCreate(CurrentMemoryContext,
+ "Subplan HashTable Temp Context",
+ ALLOCSET_SMALL_SIZES);
+ }
+
+ /*
* If we are going to hash the subquery output, initialize relevant stuff.
* (We don't create the hashtable until needed, though.)
*/
@@ -846,18 +1016,9 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
*righttlist;
ListCell *l;
- /* We need a memory context to hold the hash table(s) */
- sstate->hashtablecxt =
- AllocSetContextCreate(CurrentMemoryContext,
- "Subplan HashTable Context",
- ALLOCSET_DEFAULT_SIZES);
- /* and a small one for the hash tables to use as temp storage */
- sstate->hashtempcxt =
- AllocSetContextCreate(CurrentMemoryContext,
- "Subplan HashTable Temp Context",
- ALLOCSET_SMALL_SIZES);
- /* and a short-lived exprcontext for function evaluation */
+ /* a short-lived exprcontext for function evaluation */
sstate->innerecontext = CreateExprContext(estate);
+
/* Silly little array of column numbers 1..n */
ncols = list_length(subplan->paramIds);
sstate->keyColIdx = (AttrNumber *) palloc(ncols * sizeof(AttrNumber));
@@ -980,6 +1141,30 @@ ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
}
+ /*
+ * If we are going to use the result cache, which is keyed by the
+ * parameters, initialize the equality and hash functions for the
+ * parameter datatypes. (We don't create the cache itself until needed,
+ * though.)
+ */
+ if (subplan->useResultCache)
+ {
+ int i;
+
+ Assert (!subplan->useHashTable);
+
+ sstate->numparams = list_length(subplan->args);
+ sstate->param_hash_funcs =
+ (FmgrInfo *) palloc(sstate->numparams * sizeof(FmgrInfo));
+ sstate->param_eq_funcs =
+ (FmgrInfo *) palloc(sstate->numparams * sizeof(FmgrInfo));
+ for (i = 0; i < sstate->numparams; i++)
+ {
+ fmgr_info(subplan->paramEqFuncs[i], &sstate->param_eq_funcs[i]);
+ fmgr_info(subplan->paramHashFuncs[i], &sstate->param_hash_funcs[i]);
+ }
+ }
+
return sstate;
}
@@ -1291,3 +1476,262 @@ ExecAlternativeSubPlan(AlternativeSubPlanState *node,
return ExecSubPlan(activesp, econtext, isNull);
}
+
+
+
+/*-------------------
+ * SubPlan result cache
+ *-------------------
+ */
+
+static void
+init_result_cache(SubPlanState *sstate)
+{
+ HASHCTL hash_ctl;
+ Size entrysize = SUBPLAN_RESULT_CACHE_ENTRY_SIZE(sstate->numparams);
+ long nbuckets;
+ int i;
+ ListCell *l;
+ MemoryContext oldcxt;
+
+ nbuckets = 100; /* TODO? */
+
+ /* Limit initial table size request to not more than work_mem */
+ nbuckets = Min(nbuckets, (long) ((work_mem * 1024L) / entrysize));
+
+ /* TODO: should we use a hash_iv like execGrouping.c does? */
+
+ oldcxt = MemoryContextSwitchTo(sstate->hashtablecxt);
+
+ memset(&hash_ctl, 0, sizeof(hash_ctl));
+ hash_ctl.keysize = SUBPLAN_RESULT_CACHE_KEY_SIZE(sstate->numparams);
+ hash_ctl.entrysize = SUBPLAN_RESULT_CACHE_ENTRY_SIZE(sstate->numparams);
+ hash_ctl.hash = result_cache_hash;
+ hash_ctl.match = result_cache_match;
+ hash_ctl.keycopy = result_cache_keycopy;
+ hash_ctl.hcxt = sstate->hashtablecxt;
+
+ sstate->resultcachetab = hash_create("subplan result cache",
+ 100 /* XXX */,
+ &hash_ctl,
+ HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_KEYCOPY | HASH_CONTEXT);
+
+ sstate->paramLens = palloc(sstate->numparams * sizeof(int16));
+ sstate->paramByVals = palloc(sstate->numparams * sizeof(bool));
+
+ sstate->memUsed = 0;
+ sstate->memLimit = work_mem * 1024L;
+
+ i = 0;
+ foreach(l, sstate->subplan->args)
+ {
+ Expr *arg = (Expr *) lfirst(l);
+
+ get_typlenbyval(exprType((Node *) arg),
+ &sstate->paramLens[i],
+ &sstate->paramByVals[i]);
+ i++;
+ }
+
+ /*
+ * Also initialize this temporary cache key, to hold the parameter
+ * values, while we look up in the cache.
+ */
+ sstate->currCacheKey = (void *) palloc0(SUBPLAN_RESULT_CACHE_ENTRY_SIZE(sstate->numparams));
+
+ /*
+ * For all sublink types except EXPR_SUBLINK and ARRAY_SUBLINK, the result is
+ * a boolean as are the results fo the combining operators. The cache will store
+ * the final result, after evaluating any combining operators.
+ */
+ if (sstate->subplan->subLinkType == EXPR_SUBLINK)
+ {
+ get_typlenbyval(sstate->subplan->firstColType,
+ &sstate->resultLen,
+ &sstate->resultByVal);
+ }
+ else if (sstate->subplan->subLinkType == ARRAY_SUBLINK)
+ {
+ /* array type. They're all varlenas */
+ sstate->resultLen = -1;
+ sstate->resultByVal = false;
+ }
+ else
+ {
+ /* boolean */
+ sstate->resultLen = 1;
+ sstate->resultByVal = true;
+ }
+
+ MemoryContextSwitchTo(oldcxt);
+}
+
+/*
+ * Insert or return existing entry in the cache.
+ */
+static SubPlanResultCacheEntry *
+lookup_result_cache(SubPlanState *sstate, SubPlanResultCacheEntry *key, bool *found)
+{
+ MemoryContext oldContext;
+ SubPlanResultCacheEntry *newentry;
+ int i;
+ SubPlanState *prev_sstate;
+ Datum *params = key->params;
+ bool *isnulls = SUBPLAN_RESULT_CACHE_ENTRY_GET_NULLS(key, sstate->numparams);
+
+ /* Need to run the hash functions in short-lived context */
+ oldContext = MemoryContextSwitchTo(sstate->hashtempcxt);
+
+ /*
+ * To keep memory use in check, if there are too many entries in the
+ * cache, remove the oldest entry to make space.
+ */
+ while (sstate->memUsed > sstate->memLimit)
+ {
+ SubPlanResultCacheEntry *oldentry;
+ bool foundold;
+ Datum *oldparams;
+ bool *oldparamnulls;
+
+ /* Remove the oldest entry */
+ oldentry = dlist_tail_element(SubPlanResultCacheEntry, lru_link, &sstate->lru_list);
+
+ dlist_delete(&oldentry->lru_link);
+
+ if (!sstate->resultByVal && !oldentry->resultNull)
+ {
+ sstate->memUsed -= GetMemoryChunkSpace(DatumGetPointer(oldentry->result));
+ pfree(DatumGetPointer(oldentry->result));
+ }
+
+ /* Remove the entry from the hash table. */
+ prev_sstate = curr_sstate;
+ curr_sstate = sstate;
+ hash_search(sstate->resultcachetab, oldentry, HASH_REMOVE, &foundold);
+ if (!foundold)
+ elog(ERROR, "subplan cache is corrupt");
+ curr_sstate = prev_sstate;
+
+ sstate->memUsed -= SUBPLAN_RESULT_CACHE_ENTRY_SIZE(sstate->numparams);
+
+ /*
+ * XXX we assume the key is still valid, even though we've removed it from
+ * the hash table.
+ */
+ oldparams = oldentry->params;
+ oldparamnulls = SUBPLAN_RESULT_CACHE_ENTRY_GET_NULLS(oldentry, sstate->numparams);
+ for (i = 0; i < sstate->numparams; i++)
+ {
+ if (!sstate->paramByVals[i] && !oldparamnulls[i])
+ {
+ sstate->memUsed -= GetMemoryChunkSpace(DatumGetPointer(oldparams[i]));
+ pfree(DatumGetPointer(oldparams[i]));
+ }
+ }
+ }
+
+ prev_sstate = curr_sstate;
+ curr_sstate = sstate;
+ newentry = hash_search(sstate->resultcachetab, key, HASH_ENTER, found);
+ curr_sstate = prev_sstate;
+
+ if (!(*found))
+ {
+ /*
+ * We created a new entry.
+ */
+ Datum *newparams = newentry->params;
+
+ sstate->memUsed += SUBPLAN_RESULT_CACHE_ENTRY_SIZE(sstate->numparams);
+
+ dlist_push_head(&sstate->lru_list, &newentry->lru_link);
+
+ /*
+ * Need to make a copy of the key in the long-lived memory context.
+ */
+ MemoryContextSwitchTo(sstate->hashtablecxt);
+
+ for (i = 0; i < sstate->numparams; i++)
+ {
+ if (!sstate->paramByVals[i] && !isnulls[i])
+ {
+ newparams[i] = datumCopy(params[i],
+ sstate->paramByVals[i],
+ sstate->paramLens[i]);
+ sstate->memUsed += GetMemoryChunkSpace(DatumGetPointer(newparams[i]));
+ }
+ }
+ }
+ else
+ {
+ dlist_delete(&newentry->lru_link);
+ dlist_push_head(&sstate->lru_list, &newentry->lru_link);
+ }
+
+ MemoryContextSwitchTo(oldContext);
+
+ return newentry;
+}
+
+static uint32
+result_cache_hash(const void *key, Size keysize)
+{
+ const SubPlanResultCacheEntry *entry = (const SubPlanResultCacheEntry *) key;
+ SubPlanState *sstate = curr_sstate;
+ int i;
+ uint32 hash = 0;
+ const Datum *params = entry->params;
+ const bool *isnulls = SUBPLAN_RESULT_CACHE_ENTRY_GET_NULLS(entry, sstate->numparams);
+
+ for (i = 0; i < sstate->numparams; i++)
+ {
+ uint32 thishash;
+
+ if (isnulls[i])
+ thishash = 0;
+ else
+ thishash = DatumGetUInt32(FunctionCall1(&sstate->param_hash_funcs[i],
+ params[i]));
+ hash = hash_combine(hash, thishash);
+ }
+
+ return hash;
+}
+
+static int
+result_cache_match(const void *key1, const void *key2, Size keysize)
+{
+ const SubPlanResultCacheEntry *entry1 = (const SubPlanResultCacheEntry *) key1;
+ const SubPlanResultCacheEntry *entry2 = (const SubPlanResultCacheEntry *) key2;
+ SubPlanState *sstate = curr_sstate;
+ const Datum *params1 = entry1->params;
+ const bool *isnulls1 = SUBPLAN_RESULT_CACHE_ENTRY_GET_NULLS(entry1, sstate->numparams);
+ const Datum *params2 = entry2->params;
+ const bool *isnulls2 = SUBPLAN_RESULT_CACHE_ENTRY_GET_NULLS(entry2, sstate->numparams);
+ int i;
+
+ for (i = 0; i < sstate->numparams; i++)
+ {
+ if (isnulls1[i] != isnulls2[i])
+ return 1;
+ else if (!isnulls1[i])
+ {
+ if (!DatumGetBool(FunctionCall2(&sstate->param_eq_funcs[0],
+ params1[i],
+ params2[i])))
+ return 1;
+ }
+ }
+ return 0; /* they're equal */
+}
+
+static void *
+result_cache_keycopy(void *dest, const void *src, Size keysize)
+{
+ SubPlanResultCacheEntry *destentry = (SubPlanResultCacheEntry *) dest;
+ const SubPlanResultCacheEntry *srcentry = (const SubPlanResultCacheEntry *) src;
+
+ memcpy(destentry->params, srcentry->params, keysize);
+
+ return destentry;
+}
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 83008d7661..1fd419be5c 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -33,6 +33,7 @@
#include "utils/builtins.h"
#include "utils/lsyscache.h"
#include "utils/syscache.h"
+#include "utils/typcache.h"
typedef struct convert_testexpr_context
@@ -70,6 +71,7 @@ static Node *convert_testexpr_mutator(Node *node,
convert_testexpr_context *context);
static bool subplan_is_hashable(Plan *plan);
static bool testexpr_is_hashable(Node *testexpr);
+static bool params_are_hashable(SubPlan *splan);
static bool hash_ok_operator(OpExpr *expr);
static bool simplify_EXISTS_query(PlannerInfo *root, Query *query);
static Query *convert_EXISTS_to_ANY(PlannerInfo *root, Query *subselect,
@@ -844,7 +846,6 @@ build_subplan(PlannerInfo *root, Plan *plan, PlannerInfo *subroot,
subplan_is_hashable(plan) &&
testexpr_is_hashable(splan->testexpr))
splan->useHashTable = true;
-
/*
* Otherwise, we have the option to tack a Material node onto the top
* of the subplan, to reduce the cost of reading it repeatedly. This
@@ -859,6 +860,44 @@ build_subplan(PlannerInfo *root, Plan *plan, PlannerInfo *subroot,
!ExecMaterializesOutput(nodeTag(plan)))
plan = materialize_finished_plan(plan);
+ /*
+ * If it's a correlated subplan, we can't use an initPlan, but we
+ * might be able to cache the subplan's result for each combination of
+ * correlation params.
+ *
+ * If the subplan or testexpr contains volatile expressions, caching
+ * is not possible. Also, if the 'testexpr' is contains any Vars from
+ * the outer query, no caching, because the result would depend not
+ * only on the subquery, but also on the Vars. (We could still use
+ * the cache if we used the outer Vars as part of the cache key, but
+ * we don't do that.)
+ *
+ * Also, the parameters have to be hashable, so that we can use them
+ * as the key for the hash table to implement the cache.
+ */
+ if (splan->parParam &&
+ !contain_volatile_functions((Node *) subroot->parse) &&
+ !contain_volatile_functions((Node *) splan->testexpr) &&
+ !contain_var_clause((Node *) splan->testexpr) &&
+ params_are_hashable(splan))
+ {
+ Cost lookup_cost;
+ int i;
+
+ Assert(!splan->useHashTable);
+
+ lookup_cost = 0;
+ for (i = 0; i < list_length(splan->args); i++)
+ {
+ lookup_cost += get_func_cost(splan->paramHashFuncs[i]);
+ lookup_cost += get_func_cost(splan->paramEqFuncs[i]);
+ }
+
+ /* Assume a 10% hit ratio. */
+ if (plan->total_cost > lookup_cost + 0.9 * plan->total_cost)
+ splan->useResultCache = true;
+ }
+
result = (Node *) splan;
isInitPlan = false;
}
@@ -1145,6 +1184,51 @@ hash_ok_operator(OpExpr *expr)
}
}
+/*
+ * Check if all params are hashable
+ */
+static bool
+params_are_hashable(SubPlan *splan)
+{
+ ListCell *lc;
+ Oid *hash_funcs;
+ Oid *eq_funcs;
+ int i;
+
+ hash_funcs = (Oid *) palloc(list_length(splan->args) * sizeof(Oid));
+ eq_funcs = (Oid *) palloc(list_length(splan->args) * sizeof(Oid));
+
+ i = 0;
+ foreach(lc, splan->args)
+ {
+ Node *expr = lfirst(lc);
+ Oid eq_opr;
+ Oid hash_proc;
+ TypeCacheEntry *typentry;
+
+ typentry = lookup_type_cache(exprType(expr),
+ TYPECACHE_EQ_OPR | TYPECACHE_HASH_PROC);
+ eq_opr = typentry->eq_opr;
+ hash_proc = typentry->hash_proc;
+ if (!OidIsValid(eq_opr) || !OidIsValid(hash_proc))
+ {
+ pfree(hash_funcs);
+ pfree(eq_funcs);
+ return false;
+ }
+
+ hash_funcs[i] = hash_proc;
+ eq_funcs[i] = get_opcode(eq_opr);
+
+ i++;
+ }
+
+ /* Note: as a side-effect, we filled in the paramHashFuncs and paramEqFuncs arrays. */
+ splan->paramHashFuncs = hash_funcs;
+ splan->paramEqFuncs = eq_funcs;
+
+ return true;
+}
/*
* SS_process_ctes: process a query's WITH list
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 1f3c786b30..7aef33b83b 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -18,6 +18,7 @@
#include "access/heapam.h"
#include "access/tupconvert.h"
#include "executor/instrument.h"
+#include "lib/ilist.h"
#include "lib/pairingheap.h"
#include "nodes/params.h"
#include "nodes/plannodes.h"
@@ -824,6 +825,10 @@ typedef struct SubPlanState
List *args; /* states of argument expression(s) */
HeapTuple curTuple; /* copy of most recent tuple from subplan */
Datum curArray; /* most recent array from ARRAY() subplan */
+
+ MemoryContext hashtablecxt; /* memory context containing hash tables */
+ MemoryContext hashtempcxt; /* temp memory context for hash tables */
+
/* these are used when hashing the subselect's output: */
TupleDesc descRight; /* subselect desc after projection */
ProjectionInfo *projLeft; /* for projecting lefthand exprs */
@@ -832,8 +837,6 @@ typedef struct SubPlanState
TupleHashTable hashnulls; /* hash table for rows with null(s) */
bool havehashrows; /* true if hashtable is not empty */
bool havenullrows; /* true if hashnulls is not empty */
- MemoryContext hashtablecxt; /* memory context containing hash tables */
- MemoryContext hashtempcxt; /* temp memory context for hash tables */
ExprContext *innerecontext; /* econtext for computing inner tuples */
AttrNumber *keyColIdx; /* control data for hash tables */
Oid *tab_eq_funcoids; /* equality func oids for table
@@ -842,6 +845,24 @@ typedef struct SubPlanState
FmgrInfo *lhs_hash_funcs; /* hash functions for lefthand datatype(s) */
FmgrInfo *cur_eq_funcs; /* equality functions for LHS vs. table */
ExprState *cur_eq_comp; /* equality comparator for LHS vs. table */
+
+ /* these are for the result cache: */
+ int numparams; /* number of input parameters for subplan */
+
+ HTAB *resultcachetab; /* hash table forming the result cache */
+ dlist_head lru_list; /* LRU list for cache replacement */
+ size_t memUsed; /* amount of memory used by the cache */
+ size_t memLimit; /* max cache size, in bytes */
+
+ void *currCacheKey; /* temporary cache key variable */
+
+ bool *paramByVals; /* parameter type information */
+ int16 *paramLens;
+ FmgrInfo *param_hash_funcs; /* hash funcs for param datatype(s) */
+ FmgrInfo *param_eq_funcs; /* equality funcs for param datatype(s) */
+
+ bool resultByVal; /* result type information, for the cache */
+ int16 resultLen;
} SubPlanState;
/* ----------------
diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h
index f90aa7b2a1..7ca89dae21 100644
--- a/src/include/nodes/primnodes.h
+++ b/src/include/nodes/primnodes.h
@@ -695,12 +695,17 @@ typedef struct SubPlan
int32 firstColTypmod; /* Typmod of first column of subplan result */
Oid firstColCollation; /* Collation of first column of subplan
* result */
+ /* Information about parameter types, for caching subplan's results */
+ Oid *paramHashFuncs; /* hash functions for Params */
+ Oid *paramEqFuncs; /* equality operators to compare Params with */
/* Information about execution strategy: */
bool useHashTable; /* true to store subselect output in a hash
* table (implies we are doing "IN") */
bool unknownEqFalse; /* true if it's okay to return FALSE when the
* spec result is UNKNOWN; this allows much
* simpler handling of null values */
+ bool useResultCache; /* true to maintain a cache subselect's output
+ * for params (implies we are doing "EXPR") */
bool parallel_safe; /* is the subplan parallel-safe? */
/* Note: parallel_safe does not consider contents of testexpr or args */
/* Information for passing params into and out of the subselect: */
--
2.11.0
