Re: Protect syscache from bloating with negative cache entries

Hello. I rebased this patchset.

At Thu, 15 Mar 2018 14:12:46 +0900 (Tokyo Standard Time), Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote in
<20180315.141246.130742928.horiguchi.kyotaro@lab.ntt.co.jp>
> At Mon, 12 Mar 2018 17:34:08 +0900 (Tokyo Standard Time), Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote
in<20180312.173408.162882093.horiguchi.kyotaro@lab.ntt.co.jp>
 
> > > > In short, it's not really apparent to me that negative syscache entries
> > > > are the major problem of this kind.  I'm afraid that you're drawing very
> > > > large conclusions from a specific workload.  Maybe we could fix that
> > > > workload some other way.
> > > 
> > > The current patch doesn't consider whether an entry is negative
> > > or positive(?). Just clean up all entries based on time.
> > > 
> > > If relation has to have the same characterictics to syscaches, it
> > > might be better be on the catcache mechanism, instaed of adding
> > > the same pruning mechanism to dynahash..

This means unifying catcache and dynahash. It doesn't seem
win-win consolidation. Addition to that relcache links palloc'ed
memory which needs additional treat.

Or we could abstract the pruning mechanism applicable to both
machinaries. Specifically unifying CatCacheCleanupOldEntries in
0001 and prune_entries in 0002. Or could refactor dynahash and
rebuild catcache based on dynahash.

> > For the moment, I added such feature to dynahash and let only
> > relcache use it in this patch. Hash element has different shape
> > in "prunable" hash and pruning is performed in a similar way
> > sharing the setting with syscache. This seems working fine.
> 
> I gave consideration on plancache. The most different
> characteristics from catcache and relcache is the fact that it is
> not voluntarily removable since CachedPlanSource, the root struct
> of a plan cache, holds some indispensable inforamtion. In regards
> to prepared queries, even if we store the information into
> another location, for example in "Prepred Queries" hash, it
> merely moving a big data into another place.
> 
> Looking into CachedPlanSoruce, generic plan is a part that is
> safely removable since it is rebuilt as necessary. Keeping "old"
> plancache entries not holding a generic plan can reduce memory
> usage.
> 
> For testing purpose, I made 50000 parepared statement like
> "select sum(c) from p where e < $" on 100 partitions,
> 
> With disabling the feature (0004 patch) VSZ of the backend
> exceeds 3GB (It is still increasing at the moment), while it
> stops to increase at about 997MB for min_cached_plans = 1000 and
> plancache_prune_min_age = '10s'.
> 
> # 10s is apparently short for acutual use, of course.
> 
> It is expected to be significant amount if the plan is large
> enough but I'm still not sure it is worth doing, or is a right
> way.
> 
> 
> The attached is the patch set including this plancache stuff.
> 
> 0001- catcache time-based expiration (The origin of this thread)
> 0002- introduces dynahash pruning feature
> 0003- implement relcache pruning using 0002
> 0004- (perhaps) independent from the three above. PoC of
>       plancache pruning. Details are shown above.

I found up to v3 in this thread so I named this version 4.

regards.


-- 
Kyotaro Horiguchi
NTT Open Source Software Center
From 842f7b9fd47c6ee4daf1316547679d4298538940 Mon Sep 17 00:00:00 2001
From: Kyotaro Horiguchi <horiguchi.kyotaro@lab.ntt.co.jp>
Date: Thu, 15 Mar 2018 12:04:43 +0900
Subject: [PATCH 4/4] Generic plan removal of PlanCacheSource.

We cannot remove saved cached plans while pruning since they are
pointed from other structures. But still we can remove generic plan of
each saved plans. The behavior is controled by two additional GUC
variables min_cached_plans and cache_prune_min_age. The former tells
to keep that number of generic plans without pruned. The latter tells
how long we shuold keep generic plans before pruning.
---
 src/backend/utils/cache/plancache.c | 163 ++++++++++++++++++++++++++++++++++++
 src/backend/utils/misc/guc.c        |  10 +++
 src/include/utils/plancache.h       |   7 +-
 3 files changed, 179 insertions(+), 1 deletion(-)

diff --git a/src/backend/utils/cache/plancache.c b/src/backend/utils/cache/plancache.c
index 0ad3e3c736..701ead152c 100644
--- a/src/backend/utils/cache/plancache.c
+++ b/src/backend/utils/cache/plancache.c
@@ -63,12 +63,14 @@
 #include "storage/lmgr.h"
 #include "tcop/pquery.h"
 #include "tcop/utility.h"
+#include "utils/catcache.h"
 #include "utils/inval.h"
 #include "utils/memutils.h"
 #include "utils/resowner_private.h"
 #include "utils/rls.h"
 #include "utils/snapmgr.h"
 #include "utils/syscache.h"
+#include "utils/timestamp.h"
 
 
 /*
@@ -86,6 +88,12 @@
  * guarantee to save a CachedPlanSource without error.
  */
 static CachedPlanSource *first_saved_plan = NULL;
+static CachedPlanSource *last_saved_plan = NULL;
+static int                 num_saved_plans = 0;
+static TimestampTz         oldest_saved_plan = 0;
+
+/* GUC variables */
+int                         min_cached_plans = 1000;
 
 static void ReleaseGenericPlan(CachedPlanSource *plansource);
 static List *RevalidateCachedQuery(CachedPlanSource *plansource,
@@ -105,6 +113,7 @@ 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);
+static void PruneCachedPlan(void);
 
 
 /*
@@ -208,6 +217,8 @@ CreateCachedPlan(RawStmt *raw_parse_tree,
     plansource->generic_cost = -1;
     plansource->total_custom_cost = 0;
     plansource->num_custom_plans = 0;
+    plansource->last_access = GetCatCacheClock();
+    
 
     MemoryContextSwitchTo(oldcxt);
 
@@ -423,6 +434,28 @@ CompleteCachedPlan(CachedPlanSource *plansource,
     plansource->is_valid = true;
 }
 
+/* moves the plansource to the first in the list */
+static inline void
+MovePlansourceToFirst(CachedPlanSource *plansource)
+{
+    if (first_saved_plan != plansource)
+    {
+        /* delink this element */
+        if (plansource->next_saved)
+            plansource->next_saved->prev_saved = plansource->prev_saved;
+        if (plansource->prev_saved)
+            plansource->prev_saved->next_saved = plansource->next_saved;
+        if (last_saved_plan == plansource)
+            last_saved_plan = plansource->prev_saved;
+
+        /* insert at the beginning */
+        first_saved_plan->prev_saved = plansource;
+        plansource->next_saved = first_saved_plan;
+        plansource->prev_saved = NULL;
+        first_saved_plan = plansource;
+    }
+}
+
 /*
  * SaveCachedPlan: save a cached plan permanently
  *
@@ -470,6 +503,11 @@ SaveCachedPlan(CachedPlanSource *plansource)
      * Add the entry to the global list of cached plans.
      */
     plansource->next_saved = first_saved_plan;
+    if (first_saved_plan)
+        first_saved_plan->prev_saved = plansource;
+    else
+        last_saved_plan = plansource;
+    plansource->prev_saved = NULL;
     first_saved_plan = plansource;
 
     plansource->is_saved = true;
@@ -492,7 +530,11 @@ DropCachedPlan(CachedPlanSource *plansource)
     if (plansource->is_saved)
     {
         if (first_saved_plan == plansource)
+        {
             first_saved_plan = plansource->next_saved;
+            if (first_saved_plan)
+                first_saved_plan->prev_saved = NULL;
+        }
         else
         {
             CachedPlanSource *psrc;
@@ -502,10 +544,19 @@ DropCachedPlan(CachedPlanSource *plansource)
                 if (psrc->next_saved == plansource)
                 {
                     psrc->next_saved = plansource->next_saved;
+                    if (psrc->next_saved)
+                        psrc->next_saved->prev_saved = psrc;
                     break;
                 }
             }
         }
+
+        if (last_saved_plan == plansource)
+        {
+            last_saved_plan = plansource->prev_saved;
+            if (last_saved_plan)
+                last_saved_plan->next_saved = NULL;
+        }
         plansource->is_saved = false;
     }
 
@@ -537,6 +588,13 @@ ReleaseGenericPlan(CachedPlanSource *plansource)
         Assert(plan->magic == CACHEDPLAN_MAGIC);
         plansource->gplan = NULL;
         ReleaseCachedPlan(plan, false);
+
+        /* decrement "saved plans" counter */
+        if (plansource->is_saved)
+        {
+            Assert (num_saved_plans > 0);
+            num_saved_plans--;
+        }
     }
 }
 
@@ -1148,6 +1206,17 @@ GetCachedPlan(CachedPlanSource *plansource, ParamListInfo boundParams,
     if (useResOwner && !plansource->is_saved)
         elog(ERROR, "cannot apply ResourceOwner to non-saved cached plan");
 
+    /*
+     * set last-accessed timestamp and move this plan to the first of the list
+     */
+    if (plansource->is_saved)
+    {
+        plansource->last_access = GetCatCacheClock();
+
+        /* move this plan to the first of the list */
+        MovePlansourceToFirst(plansource);
+    }
+
     /* Make sure the querytree list is valid and we have parse-time locks */
     qlist = RevalidateCachedQuery(plansource, queryEnv);
 
@@ -1156,6 +1225,11 @@ GetCachedPlan(CachedPlanSource *plansource, ParamListInfo boundParams,
 
     if (!customplan)
     {
+        /* Prune cached plans if needed */
+        if (plansource->is_saved &&
+            min_cached_plans >= 0 && num_saved_plans > min_cached_plans)
+                PruneCachedPlan();
+
         if (CheckCachedPlan(plansource))
         {
             /* We want a generic plan, and we already have a valid one */
@@ -1168,6 +1242,11 @@ GetCachedPlan(CachedPlanSource *plansource, ParamListInfo boundParams,
             plan = BuildCachedPlan(plansource, qlist, NULL, queryEnv);
             /* Just make real sure plansource->gplan is clear */
             ReleaseGenericPlan(plansource);
+
+            /* count this new saved plan */
+            if (plansource->is_saved)
+                num_saved_plans++;
+
             /* Link the new generic plan into the plansource */
             plansource->gplan = plan;
             plan->refcount++;
@@ -1856,6 +1935,90 @@ PlanCacheSysCallback(Datum arg, int cacheid, uint32 hashvalue)
     ResetPlanCache();
 }
 
+/*
+ * PrunePlanCache: removes generic plan of "old" saved plans.
+ */
+static void
+PruneCachedPlan(void)
+{
+    CachedPlanSource *plansource;
+    TimestampTz          currclock = GetCatCacheClock();
+    long              age;
+    int                  us;
+    int                  nremoved = 0;
+
+    /* do nothing if not wanted */
+    if (cache_prune_min_age < 0 || num_saved_plans <= min_cached_plans)
+        return;
+
+    /* Fast check for oldest cache */
+    if (oldest_saved_plan > 0)
+    {
+        TimestampDifference(oldest_saved_plan, currclock, &age, &us);
+        if (age < cache_prune_min_age)
+            return;
+    }        
+
+    /* last plan is the oldest. */
+    for (plansource = last_saved_plan; plansource; plansource = plansource->prev_saved)
+    {
+        long    plan_age;
+        int        us;
+
+        Assert(plansource->magic == CACHEDPLANSOURCE_MAGIC);
+
+        /* we want to prune no more plans */
+        if (num_saved_plans <= min_cached_plans)
+            break;
+
+        /*
+         * No work if it already doesn't have gplan and move it to the
+         * beginning so that we don't see it at the next time
+         */
+        if (!plansource->gplan)
+            continue;
+
+        /*
+         * Check age for pruning. Can exit immediately when finding a
+         * not-older element.
+         */
+        TimestampDifference(plansource->last_access, currclock, &plan_age, &us);
+        if (plan_age <= cache_prune_min_age)
+        {
+            /* this entry is the next oldest */
+            oldest_saved_plan = plansource->last_access;
+            break;
+        }
+
+        /*
+         * Here, remove generic plans of this plansrouceif it is not actually
+         * used and move it to the beginning of the list. Just update
+         * last_access and move it to the beginning if the plan is used.
+         */
+        if (plansource->gplan->refcount <= 1)
+        {
+            ReleaseGenericPlan(plansource);
+            nremoved++;
+        }
+
+        plansource->last_access = currclock;
+    }
+
+    /* move the "removed" plansrouces altogehter to the beginning of the list */
+    if (plansource != last_saved_plan && plansource)
+    {
+        plansource->next_saved->prev_saved = NULL;
+        first_saved_plan->prev_saved = last_saved_plan;
+         last_saved_plan->next_saved = first_saved_plan;
+        first_saved_plan = plansource->next_saved;
+        plansource->next_saved = NULL;
+        last_saved_plan = plansource;
+    }
+
+    if (nremoved > 0)
+        elog(DEBUG1, "plancache removed %d/%d", nremoved, num_saved_plans);
+}
+
 /*
  * ResetPlanCache: invalidate all cached plans.
  */
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index 9800252965..478bfe96a4 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -2128,6 +2128,16 @@ static struct config_int ConfigureNamesInt[] =
         NULL, NULL, NULL
     },
 
+    {
+        {"min_cached_plans", PGC_USERSET, RESOURCES_MEM,
+            gettext_noop("Sets the minimum number of cached plans kept on memory."),
+            gettext_noop("Timeout invalidation of plancache is not activated until the number of plancaches reaches
thisvalue. -1 means timeout invalidation is always active.")
 
+        },
+        &min_cached_plans,
+        1000, -1, INT_MAX,
+        NULL, NULL, NULL
+    },
+
     /*
      * We use the hopefully-safely-small value of 100kB as the compiled-in
      * default for max_stack_depth.  InitializeGUCOptions will increase it if
diff --git a/src/include/utils/plancache.h b/src/include/utils/plancache.h
index ab20aa04b0..f3c5b2010d 100644
--- a/src/include/utils/plancache.h
+++ b/src/include/utils/plancache.h
@@ -110,11 +110,13 @@ typedef struct CachedPlanSource
     bool        is_valid;        /* is the query_list currently valid? */
     int            generation;        /* increments each time we create a plan */
     /* If CachedPlanSource has been saved, it is a member of a global list */
-    struct CachedPlanSource *next_saved;    /* list link, if so */
+    struct CachedPlanSource *prev_saved;    /* list prev link, if so */
+    struct CachedPlanSource *next_saved;    /* list next link, if so */
     /* State kept to help decide whether to use custom or generic plans: */
     double        generic_cost;    /* cost of generic plan, or -1 if not known */
     double        total_custom_cost;    /* total cost of custom plans so far */
     int            num_custom_plans;    /* number of plans included in total */
+    TimestampTz    last_access;    /* timestamp of the last usage */
 } CachedPlanSource;
 
 /*
@@ -143,6 +145,9 @@ typedef struct CachedPlan
     MemoryContext context;        /* context containing this CachedPlan */
 } CachedPlan;
 
+/* GUC variables */
+extern int min_cached_plans;
+extern int plancache_prune_min_age;
 
 extern void InitPlanCache(void);
 extern void ResetPlanCache(void);
-- 
2.16.3

From 06bf577b5092a9fa443122bc8eef51284c6aa339 Mon Sep 17 00:00:00 2001
From: Kyotaro Horiguchi <horiguchi.kyotaro@lab.ntt.co.jp>
Date: Mon, 12 Mar 2018 17:31:43 +0900
Subject: [PATCH 3/3] Apply purning to relcache

---
 src/backend/utils/cache/relcache.c | 25 ++++++++++++++++++++++++-
 1 file changed, 24 insertions(+), 1 deletion(-)

diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index d85dc92505..dbbf9855b0 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -3442,6 +3442,26 @@ RelationSetNewRelfilenode(Relation relation, char persistence,
 
 #define INITRELCACHESIZE        400
 
+/* callback function for hash pruning */
+static bool
+relcache_prune_cb(HTAB *hashp, void *ent)
+{
+    RelIdCacheEnt  *relent = (RelIdCacheEnt *) ent;
+    Relation        relation;
+
+    /* this relation is requested to be removed.  */
+    RelationIdCacheLookup(relent->reloid, relation);
+
+    /* don't remove if currently in use */
+    if (!RelationHasReferenceCountZero(relation))
+        return false;
+
+    /* otherwise we can forget it unconditionally */
+    RelationClearRelation(relation, false);
+
+    return true;
+}
+
 void
 RelationCacheInitialize(void)
 {
@@ -3459,8 +3479,11 @@ RelationCacheInitialize(void)
     MemSet(&ctl, 0, sizeof(ctl));
     ctl.keysize = sizeof(Oid);
     ctl.entrysize = sizeof(RelIdCacheEnt);
+
+    /* use the same setting with syscache */
+    ctl.prune_cb = relcache_prune_cb;
     RelationIdCache = hash_create("Relcache by OID", INITRELCACHESIZE,
-                                  &ctl, HASH_ELEM | HASH_BLOBS);
+                                  &ctl, HASH_ELEM | HASH_BLOBS | HASH_PRUNABLE);
 
     /*
      * relation mapper needs to be initialized too
-- 
2.16.3

From 0c0f8ff6e786dc20aa43636cad57f3713c0c89dd Mon Sep 17 00:00:00 2001
From: Kyotaro Horiguchi <horiguchi.kyotaro@lab.ntt.co.jp>
Date: Mon, 12 Mar 2018 15:52:18 +0900
Subject: [PATCH 2/3] introduce dynhash pruning

---
 src/backend/utils/hash/dynahash.c | 166 +++++++++++++++++++++++++++++++++-----
 src/include/utils/catcache.h      |  12 +++
 src/include/utils/hsearch.h       |  21 ++++-
 3 files changed, 179 insertions(+), 20 deletions(-)

diff --git a/src/backend/utils/hash/dynahash.c b/src/backend/utils/hash/dynahash.c
index 785e0faffb..261f8d9577 100644
--- a/src/backend/utils/hash/dynahash.c
+++ b/src/backend/utils/hash/dynahash.c
@@ -88,6 +88,7 @@
 #include "access/xact.h"
 #include "storage/shmem.h"
 #include "storage/spin.h"
+#include "utils/catcache.h"
 #include "utils/dynahash.h"
 #include "utils/memutils.h"
 
@@ -184,6 +185,12 @@ struct HASHHDR
     long        ssize;            /* segment size --- must be power of 2 */
     int            sshift;            /* segment shift = log2(ssize) */
     int            nelem_alloc;    /* number of entries to allocate at once */
+    bool        prunable;        /* true if prunable */
+    HASH_PRUNE_CB    prune_cb;    /* function to call instead of just deleting */
+
+    /* These fields point to variables to control pruning */
+    int           *memory_target;    /* pointer to memory target value in kB */
+    int           *prune_min_age;    /* pointer to prune minimum age value in sec */
 
 #ifdef HASH_STATISTICS
 
@@ -227,16 +234,18 @@ struct HTAB
     int            sshift;            /* segment shift = log2(ssize) */
 };
 
+#define HASHELEMENT_SIZE(ctlp) MAXALIGN(ctlp->prunable ? sizeof(PRUNABLE_HASHELEMENT) : sizeof(HASHELEMENT))
+
 /*
  * Key (also entry) part of a HASHELEMENT
  */
-#define ELEMENTKEY(helem)  (((char *)(helem)) + MAXALIGN(sizeof(HASHELEMENT)))
+#define ELEMENTKEY(helem, ctlp)  (((char *)(helem)) + HASHELEMENT_SIZE(ctlp))
 
 /*
  * Obtain element pointer given pointer to key
  */
-#define ELEMENT_FROM_KEY(key)  \
-    ((HASHELEMENT *) (((char *) (key)) - MAXALIGN(sizeof(HASHELEMENT))))
+#define ELEMENT_FROM_KEY(key, ctlp)                                        \
+    ((HASHELEMENT *) (((char *) (key)) - HASHELEMENT_SIZE(ctlp)))
 
 /*
  * Fast MOD arithmetic, assuming that y is a power of 2 !
@@ -257,6 +266,7 @@ static HASHSEGMENT seg_alloc(HTAB *hashp);
 static bool element_alloc(HTAB *hashp, int nelem, int freelist_idx);
 static bool dir_realloc(HTAB *hashp);
 static bool expand_table(HTAB *hashp);
+static bool prune_entries(HTAB *hashp);
 static HASHBUCKET get_hash_entry(HTAB *hashp, int freelist_idx);
 static void hdefault(HTAB *hashp);
 static int    choose_nelem_alloc(Size entrysize);
@@ -499,6 +509,29 @@ hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
         hctl->entrysize = info->entrysize;
     }
 
+    /*
+     * Set up pruning.
+     *
+     * We have two knobs to control pruning and a hash can share them of
+     * syscache.
+     *
+     */
+    if (flags & HASH_PRUNABLE)
+    {
+        hctl->prunable = true;
+        hctl->prune_cb = info->prune_cb;
+        if (info->memory_target)
+            hctl->memory_target = info->memory_target;
+        else
+            hctl->memory_target = &cache_memory_target;
+        if (info->prune_min_age)
+            hctl->prune_min_age = info->prune_min_age;
+        else
+            hctl->prune_min_age = &cache_prune_min_age;
+    }
+    else
+        hctl->prunable = false;
+
     /* make local copies of heavily-used constant fields */
     hashp->keysize = hctl->keysize;
     hashp->ssize = hctl->ssize;
@@ -984,7 +1017,7 @@ hash_search_with_hash_value(HTAB *hashp,
     while (currBucket != NULL)
     {
         if (currBucket->hashvalue == hashvalue &&
-            match(ELEMENTKEY(currBucket), keyPtr, keysize) == 0)
+            match(ELEMENTKEY(currBucket, hctl), keyPtr, keysize) == 0)
             break;
         prevBucketPtr = &(currBucket->link);
         currBucket = *prevBucketPtr;
@@ -997,6 +1030,17 @@ hash_search_with_hash_value(HTAB *hashp,
     if (foundPtr)
         *foundPtr = (bool) (currBucket != NULL);
 
+    /* Update access counter if needed */
+    if (hctl->prunable && currBucket &&
+        (action == HASH_FIND || action == HASH_ENTER))
+    {
+        PRUNABLE_HASHELEMENT *prunable_elm =
+            (PRUNABLE_HASHELEMENT *) currBucket;
+        if (prunable_elm->naccess < 2)
+            prunable_elm->naccess++;
+        prunable_elm->last_access = GetCatCacheClock();
+    }
+
     /*
      * OK, now what?
      */
@@ -1004,7 +1048,8 @@ hash_search_with_hash_value(HTAB *hashp,
     {
         case HASH_FIND:
             if (currBucket != NULL)
-                return (void *) ELEMENTKEY(currBucket);
+                return (void *) ELEMENTKEY(currBucket, hctl);
+
             return NULL;
 
         case HASH_REMOVE:
@@ -1033,7 +1078,7 @@ hash_search_with_hash_value(HTAB *hashp,
                  * element, because someone else is going to reuse it the next
                  * time something is added to the table
                  */
-                return (void *) ELEMENTKEY(currBucket);
+                return (void *) ELEMENTKEY(currBucket, hctl);
             }
             return NULL;
 
@@ -1045,7 +1090,7 @@ hash_search_with_hash_value(HTAB *hashp,
         case HASH_ENTER:
             /* Return existing element if found, else create one */
             if (currBucket != NULL)
-                return (void *) ELEMENTKEY(currBucket);
+                return (void *) ELEMENTKEY(currBucket, hctl);
 
             /* disallow inserts if frozen */
             if (hashp->frozen)
@@ -1075,8 +1120,18 @@ hash_search_with_hash_value(HTAB *hashp,
 
             /* copy key into record */
             currBucket->hashvalue = hashvalue;
-            hashp->keycopy(ELEMENTKEY(currBucket), keyPtr, keysize);
+            hashp->keycopy(ELEMENTKEY(currBucket, hctl), keyPtr, keysize);
 
+            /* set access counter */
+            if (hctl->prunable)
+            {
+                PRUNABLE_HASHELEMENT *prunable_elm =
+                    (PRUNABLE_HASHELEMENT *) currBucket;
+                if (prunable_elm->naccess < 2)
+                    prunable_elm->naccess++;
+                prunable_elm->last_access = GetCatCacheClock();
+            }
+            
             /*
              * Caller is expected to fill the data field on return.  DO NOT
              * insert any code that could possibly throw error here, as doing
@@ -1084,7 +1139,7 @@ hash_search_with_hash_value(HTAB *hashp,
              * caller's data structure.
              */
 
-            return (void *) ELEMENTKEY(currBucket);
+            return (void *) ELEMENTKEY(currBucket, hctl);
     }
 
     elog(ERROR, "unrecognized hash action code: %d", (int) action);
@@ -1116,7 +1171,7 @@ hash_update_hash_key(HTAB *hashp,
                      void *existingEntry,
                      const void *newKeyPtr)
 {
-    HASHELEMENT *existingElement = ELEMENT_FROM_KEY(existingEntry);
+    HASHELEMENT *existingElement = ELEMENT_FROM_KEY(existingEntry, hashp->hctl);
     HASHHDR    *hctl = hashp->hctl;
     uint32        newhashvalue;
     Size        keysize;
@@ -1200,7 +1255,7 @@ hash_update_hash_key(HTAB *hashp,
     while (currBucket != NULL)
     {
         if (currBucket->hashvalue == newhashvalue &&
-            match(ELEMENTKEY(currBucket), newKeyPtr, keysize) == 0)
+            match(ELEMENTKEY(currBucket, hctl), newKeyPtr, keysize) == 0)
             break;
         prevBucketPtr = &(currBucket->link);
         currBucket = *prevBucketPtr;
@@ -1234,7 +1289,7 @@ hash_update_hash_key(HTAB *hashp,
 
     /* copy new key into record */
     currBucket->hashvalue = newhashvalue;
-    hashp->keycopy(ELEMENTKEY(currBucket), newKeyPtr, keysize);
+    hashp->keycopy(ELEMENTKEY(currBucket, hctl), newKeyPtr, keysize);
 
     /* rest of record is untouched */
 
@@ -1388,8 +1443,8 @@ hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp)
 void *
 hash_seq_search(HASH_SEQ_STATUS *status)
 {
-    HTAB       *hashp;
-    HASHHDR    *hctl;
+    HTAB       *hashp = status->hashp;
+    HASHHDR    *hctl = hashp->hctl;
     uint32        max_bucket;
     long        ssize;
     long        segment_num;
@@ -1404,15 +1459,13 @@ hash_seq_search(HASH_SEQ_STATUS *status)
         status->curEntry = curElem->link;
         if (status->curEntry == NULL)    /* end of this bucket */
             ++status->curBucket;
-        return (void *) ELEMENTKEY(curElem);
+        return (void *) ELEMENTKEY(curElem, hctl);
     }
 
     /*
      * Search for next nonempty bucket starting at curBucket.
      */
     curBucket = status->curBucket;
-    hashp = status->hashp;
-    hctl = hashp->hctl;
     ssize = hashp->ssize;
     max_bucket = hctl->max_bucket;
 
@@ -1458,7 +1511,7 @@ hash_seq_search(HASH_SEQ_STATUS *status)
     if (status->curEntry == NULL)    /* end of this bucket */
         ++curBucket;
     status->curBucket = curBucket;
-    return (void *) ELEMENTKEY(curElem);
+    return (void *) ELEMENTKEY(curElem, hctl);
 }
 
 void
@@ -1552,6 +1605,10 @@ expand_table(HTAB *hashp)
      */
     if ((uint32) new_bucket > hctl->high_mask)
     {
+        /* try pruning before expansion. return true on success */
+        if (hctl->prunable && prune_entries(hashp))
+            return true;
+
         hctl->low_mask = hctl->high_mask;
         hctl->high_mask = (uint32) new_bucket | hctl->low_mask;
     }
@@ -1594,6 +1651,77 @@ expand_table(HTAB *hashp)
     return true;
 }
 
+static bool
+prune_entries(HTAB *hashp)
+{
+    HASHHDR           *hctl = hashp->hctl;
+    HASH_SEQ_STATUS status;
+    void            *elm;
+    TimestampTz        currclock = GetCatCacheClock();
+    int                nall = 0,
+                    nremoved = 0;
+
+    Assert(hctl->prunable);
+
+    /* Return if pruning is currently disabled or not doable */
+    if (*hctl->prune_min_age < 0 || hashp->frozen || has_seq_scans(hashp))
+        return false;
+
+    /*
+     * we don't prune before reaching this size. We only consider bucket array
+     * size since it is the significant part of memory usage.
+     */
+    if (hctl->dsize * sizeof(HASHBUCKET) * hashp->ssize <
+        (Size) *hctl->memory_target * 1024L)
+        return false;
+
+    /* Ok, start pruning. we can use seq scan here. */
+    hash_seq_init(&status, hashp);
+    while ((elm = hash_seq_search(&status)) != NULL)
+    {
+        PRUNABLE_HASHELEMENT *helm =
+            (PRUNABLE_HASHELEMENT *)ELEMENT_FROM_KEY(elm, hctl);
+        long    entry_age;
+        int        us;
+
+        nall++;
+
+        TimestampDifference(helm->last_access, currclock, &entry_age, &us);
+
+        /*
+         * consider pruning if this entry has not been accessed for a certain
+         * time
+         */
+        if (entry_age > *hctl->prune_min_age)
+        {
+            /* Wait for the next chance if this is recently used */
+            if (helm->naccess > 0)
+                helm->naccess--;
+            else
+            {
+                /* just call it if callback is provided, remove otherwise */
+                if (hctl->prune_cb)
+                {
+                    if (hctl->prune_cb(hashp, (void *)elm))
+                        nremoved++;
+                }
+                else
+                {
+                    bool found;
+                    
+                    hash_search(hashp, elm, HASH_REMOVE, &found);
+                    Assert(found);
+                    nremoved++;
+                }
+            }
+        }
+    }
+
+    elog(DEBUG1, "removed %d/%d entries from hash \"%s\"",
+         nremoved, nall, hashp->tabname);
+
+    return nremoved > 0;
+}
 
 static bool
 dir_realloc(HTAB *hashp)
@@ -1667,7 +1795,7 @@ element_alloc(HTAB *hashp, int nelem, int freelist_idx)
         return false;
 
     /* Each element has a HASHELEMENT header plus user data. */
-    elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(hctl->entrysize);
+    elementSize = HASHELEMENT_SIZE(hctl) + MAXALIGN(hctl->entrysize);
 
     CurrentDynaHashCxt = hashp->hcxt;
     firstElement = (HASHELEMENT *) hashp->alloc(nelem * elementSize);
diff --git a/src/include/utils/catcache.h b/src/include/utils/catcache.h
index 599303be56..b3f73f53d2 100644
--- a/src/include/utils/catcache.h
+++ b/src/include/utils/catcache.h
@@ -208,6 +208,18 @@ SetCatCacheClock(TimestampTz ts)
     catcacheclock = ts;
 }
 
+/*
+ * GetCatCacheClock - get timestamp for catcache access record
+ *
+ * This clock is basically provided for catcache usage, but dynahash has a
+ * similar pruning mechanism and wants to use the same clock.
+ */
+static inline TimestampTz
+GetCatCacheClock(void)
+{
+    return catcacheclock;
+}
+
 extern void CreateCacheMemoryContext(void);
 
 extern CatCache *InitCatCache(int id, Oid reloid, Oid indexoid,
diff --git a/src/include/utils/hsearch.h b/src/include/utils/hsearch.h
index 8357faac5a..6e9fa74a4f 100644
--- a/src/include/utils/hsearch.h
+++ b/src/include/utils/hsearch.h
@@ -13,7 +13,7 @@
  */
 #ifndef HSEARCH_H
 #define HSEARCH_H
-
+#include "datatype/timestamp.h"
 
 /*
  * Hash functions must have this signature.
@@ -47,6 +47,7 @@ typedef void *(*HashAllocFunc) (Size request);
  * HASHELEMENT is the private part of a hashtable entry.  The caller's data
  * follows the HASHELEMENT structure (on a MAXALIGN'd boundary).  The hash key
  * is expected to be at the start of the caller's hash entry data structure.
+ * If this hash is prunable, PRUNABLE_HASHELEMENT is used instead.
  */
 typedef struct HASHELEMENT
 {
@@ -54,12 +55,26 @@ typedef struct HASHELEMENT
     uint32        hashvalue;        /* hash function result for this entry */
 } HASHELEMENT;
 
+typedef struct PRUNABLE_HASHELEMENT
+{
+    struct HASHELEMENT *link;    /* link to next entry in same bucket */
+    uint32        hashvalue;        /* hash function result for this entry */
+    TimestampTz    last_access;    /* timestamp of last usage */
+    int            naccess;        /* takes 0 to 2, counted up when used */
+} PRUNABLE_HASHELEMENT;
+
 /* Hash table header struct is an opaque type known only within dynahash.c */
 typedef struct HASHHDR HASHHDR;
 
 /* Hash table control struct is an opaque type known only within dynahash.c */
 typedef struct HTAB HTAB;
 
+/*
+ * Hash pruning callback which is called for the entries which is about to be
+ * pruned and returns false if the entry shuold be kept.
+ */
+typedef bool (*HASH_PRUNE_CB)(HTAB *hashp, void *ent);
+
 /* Parameter data structure for hash_create */
 /* Only those fields indicated by hash_flags need be set */
 typedef struct HASHCTL
@@ -77,6 +92,9 @@ typedef struct HASHCTL
     HashAllocFunc alloc;        /* memory allocator */
     MemoryContext hcxt;            /* memory context to use for allocations */
     HASHHDR    *hctl;            /* location of header in shared mem */
+    HASH_PRUNE_CB    prune_cb;    /* pruning callback. see above. */
+    int           *memory_target;    /* pointer to memory target */
+    int           *prune_min_age;    /* pointer to prune minimum age */
 } HASHCTL;
 
 /* Flags to indicate which parameters are supplied */
@@ -94,6 +112,7 @@ typedef struct HASHCTL
 #define HASH_SHARED_MEM 0x0800    /* Hashtable is in shared memory */
 #define HASH_ATTACH        0x1000    /* Do not initialize hctl */
 #define HASH_FIXED_SIZE 0x2000    /* Initial size is a hard limit */
+#define HASH_PRUNABLE    0x4000    /* pruning setting */
 
 
 /* max_dsize value to indicate expansible directory */
-- 
2.16.3

From 870ca3f1403310493b2580314c8b1b478dbff028 Mon Sep 17 00:00:00 2001
From: Kyotaro Horiguchi <horiguchi.kyotaro@lab.ntt.co.jp>
Date: Tue, 26 Dec 2017 17:43:09 +0900
Subject: [PATCH 1/3] Remove entries that haven't been used for a certain time

Catcache entries can be left alone for several reasons. It is not
desirable that they eat up memory. With this patch, This adds
consideration of removal of entries that haven't been used for a
certain time before enlarging the hash array.
---
 doc/src/sgml/config.sgml                      |  38 ++++++
 src/backend/access/transam/xact.c             |   3 +
 src/backend/utils/cache/catcache.c            | 153 +++++++++++++++++++++++-
 src/backend/utils/cache/plancache.c           | 163 ++++++++++++++++++++++++++
 src/backend/utils/misc/guc.c                  |  33 ++++++
 src/backend/utils/misc/postgresql.conf.sample |   2 +
 src/include/utils/catcache.h                  |  19 +++
 src/include/utils/plancache.h                 |   7 +-
 8 files changed, 413 insertions(+), 5 deletions(-)

diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index 7bfbc87109..4ba4327007 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -1617,6 +1617,44 @@ include_dir 'conf.d'
       </listitem>
      </varlistentry>
 
+     <varlistentry id="guc-syscache-memory-target" xreflabel="syscache_memory_target">
+      <term><varname>syscache_memory_target</varname> (<type>integer</type>)
+      <indexterm>
+       <primary><varname>syscache_memory_target</varname> configuration parameter</primary>
+      </indexterm>
+      </term>
+      <listitem>
+       <para>
+        Specifies the maximum amount of memory to which syscache is expanded
+        without pruning. The value defaults to 0, indicating that pruning is
+        always considered. After exceeding this size, syscache pruning is
+        considered according to
+        <xref linkend="guc-syscache-prune-min-age"/>. If you need to keep
+        certain amount of syscache entries with intermittent usage, try
+        increase this setting.
+       </para>
+      </listitem>
+     </varlistentry>
+
+     <varlistentry id="guc-syscache-prune-min-age" xreflabel="syscache_prune_min_age">
+      <term><varname>syscache_prune_min_age</varname> (<type>integer</type>)
+      <indexterm>
+       <primary><varname>syscache_prune_min_age</varname> configuration parameter</primary>
+      </indexterm>
+      </term>
+      <listitem>
+       <para>
+        Specifies the minimum amount of unused time in seconds at which a
+        syscache entry is considered to be removed. -1 indicates that syscache
+        pruning is disabled at all. The value defaults to 600 seconds
+        (<literal>10 minutes</literal>). The syscache entries that are not
+        used for the duration can be removed to prevent syscache bloat. This
+        behavior is suppressed until the size of syscache exceeds
+        <xref linkend="guc-syscache-memory-target"/>.
+       </para>
+      </listitem>
+     </varlistentry>
+
      <varlistentry id="guc-max-stack-depth" xreflabel="max_stack_depth">
       <term><varname>max_stack_depth</varname> (<type>integer</type>)
       <indexterm>
diff --git a/src/backend/access/transam/xact.c b/src/backend/access/transam/xact.c
index 8e6aef332c..e4a4a5874c 100644
--- a/src/backend/access/transam/xact.c
+++ b/src/backend/access/transam/xact.c
@@ -732,6 +732,9 @@ void
 SetCurrentStatementStartTimestamp(void)
 {
     stmtStartTimestamp = GetCurrentTimestamp();
+
+    /* Set this timestamp as aproximated current time */
+    SetCatCacheClock(stmtStartTimestamp);
 }
 
 /*
diff --git a/src/backend/utils/cache/catcache.c b/src/backend/utils/cache/catcache.c
index 5ddbf6eab1..9f421cd242 100644
--- a/src/backend/utils/cache/catcache.c
+++ b/src/backend/utils/cache/catcache.c
@@ -71,9 +71,24 @@
 #define CACHE6_elog(a,b,c,d,e,f,g)
 #endif
 
+/*
+ * GUC variable to define the minimum size of hash to cosider entry eviction.
+ * This variable is shared among various cache mechanisms.
+ */
+int cache_memory_target = 0;
+
+/* GUC variable to define the minimum age of entries that will be cosidered to
+ * be evicted in seconds. This variable is shared among various cache
+ * mechanisms.
+ */
+int cache_prune_min_age = 600;
+
 /* Cache management header --- pointer is NULL until created */
 static CatCacheHeader *CacheHdr = NULL;
 
+/* Timestamp used for any operation on caches. */
+TimestampTz    catcacheclock = 0;
+
 static inline HeapTuple SearchCatCacheInternal(CatCache *cache,
                        int nkeys,
                        Datum v1, Datum v2,
@@ -866,9 +881,130 @@ InitCatCache(int id,
      */
     MemoryContextSwitchTo(oldcxt);
 
+    /* initilize catcache reference clock if haven't done yet */
+    if (catcacheclock == 0)
+        catcacheclock = GetCurrentTimestamp();
+
     return cp;
 }
 
+/*
+ * CatCacheCleanupOldEntries - Remove infrequently-used entries
+ *
+ * Catcache entries can be left alone for several reasons. We remove them if
+ * they are not accessed for a certain time to prevent catcache from
+ * bloating. The eviction is performed with the similar algorithm with buffer
+ * eviction using access counter. Entries that are accessed several times can
+ * live longer than those that have had no access in the same duration.
+ */
+static bool
+CatCacheCleanupOldEntries(CatCache *cp)
+{
+    int            i;
+    int            nremoved = 0;
+    size_t        hash_size;
+#ifdef CATCACHE_STATS
+    /* These variables are only for debugging purpose */
+    int            ntotal = 0;
+    /*
+     * nth element in nentries stores the number of cache entries that have
+     * lived unaccessed for corresponding multiple in ageclass of
+     * cache_prune_min_age. The index of nremoved_entry is the value of the
+     * clock-sweep counter, which takes from 0 up to 2.
+     */
+    double        ageclass[] = {0.05, 0.1, 1.0, 2.0, 3.0, 0.0};
+    int            nentries[] = {0, 0, 0, 0, 0, 0};
+    int            nremoved_entry[3] = {0, 0, 0};
+    int            j;
+#endif
+
+    /* Return immediately if no pruning is wanted */
+    if (cache_prune_min_age < 0)
+        return false;
+
+    /*
+     * Return without pruning if the size of the hash is below the target.
+     * Since the area for bucket array is dominant, consider only it.
+     */
+    hash_size = cp->cc_nbuckets * sizeof(dlist_head);
+    if (hash_size < (Size) cache_memory_target * 1024L)
+        return false;
+    
+    /* Search the whole hash for entries to remove */
+    for (i = 0; i < cp->cc_nbuckets; i++)
+    {
+        dlist_mutable_iter iter;
+
+        dlist_foreach_modify(iter, &cp->cc_bucket[i])
+        {
+            CatCTup    *ct = dlist_container(CatCTup, cache_elem, iter.cur);
+            long entry_age;
+            int us;
+
+
+            /*
+             * Calculate the duration from the time of the last access to the
+             * "current" time. Since catcacheclock is not advanced within a
+             * transaction, the entries that are accessed within the current
+             * transaction won't be pruned.
+             */
+            TimestampDifference(ct->lastaccess, catcacheclock, &entry_age, &us);
+
+#ifdef CATCACHE_STATS
+            /* count catcache entries for each age class */
+            ntotal++;
+            for (j = 0 ;
+                 ageclass[j] != 0.0 &&
+                     entry_age > cache_prune_min_age * ageclass[j] ;
+                 j++);
+            if (ageclass[j] == 0.0) j--;
+            nentries[j]++;
+#endif
+
+            /*
+             * Try to remove entries older than cache_prune_min_age seconds.
+             * Entries that are not accessed after last pruning are removed in
+             * that seconds, and that has been accessed several times are
+             * removed after leaving alone for up to three times of the
+             * duration. We don't try shrink buckets since pruning effectively
+             * caps catcache expansion in the long term.
+             */
+            if (entry_age > cache_prune_min_age)
+            {
+#ifdef CATCACHE_STATS
+                Assert (ct->naccess >= 0 && ct->naccess <= 2);
+                nremoved_entry[ct->naccess]++;
+#endif
+                if (ct->naccess > 0)
+                    ct->naccess--;
+                else
+                {
+                    if (!ct->c_list || ct->c_list->refcount == 0)
+                    {
+                        CatCacheRemoveCTup(cp, ct);
+                        nremoved++;
+                    }
+                }
+            }
+        }
+    }
+
+#ifdef CATCACHE_STATS
+    ereport(DEBUG1,
+            (errmsg ("removed %d/%d, age(-%.0fs:%d, -%.0fs:%d, *-%.0fs:%d, -%.0fs:%d, -%.0fs:%d) naccessed(0:%d, 1:%d,
2:%d)",
+                     nremoved, ntotal,
+                     ageclass[0] * cache_prune_min_age, nentries[0],
+                     ageclass[1] * cache_prune_min_age, nentries[1],
+                     ageclass[2] * cache_prune_min_age, nentries[2],
+                     ageclass[3] * cache_prune_min_age, nentries[3],
+                     ageclass[4] * cache_prune_min_age, nentries[4],
+                     nremoved_entry[0], nremoved_entry[1], nremoved_entry[2]),
+             errhidestmt(true)));
+#endif
+
+    return nremoved > 0;
+}
+
 /*
  * Enlarge a catcache, doubling the number of buckets.
  */
@@ -1282,6 +1418,11 @@ SearchCatCacheInternal(CatCache *cache,
          */
         dlist_move_head(bucket, &ct->cache_elem);
 
+        /* Update access information for pruning */
+        if (ct->naccess < 2)
+            ct->naccess++;
+        ct->lastaccess = catcacheclock;
+
         /*
          * If it's a positive entry, bump its refcount and return it. If it's
          * negative, we can report failure to the caller.
@@ -1813,7 +1954,6 @@ ReleaseCatCacheList(CatCList *list)
         CatCacheRemoveCList(list->my_cache, list);
 }
 
-
 /*
  * CatalogCacheCreateEntry
  *        Create a new CatCTup entry, copying the given HeapTuple and other
@@ -1906,6 +2046,8 @@ CatalogCacheCreateEntry(CatCache *cache, HeapTuple ntp, Datum *arguments,
     ct->dead = false;
     ct->negative = negative;
     ct->hash_value = hashValue;
+    ct->naccess = 0;
+    ct->lastaccess = catcacheclock;
 
     dlist_push_head(&cache->cc_bucket[hashIndex], &ct->cache_elem);
 
@@ -1913,10 +2055,13 @@ CatalogCacheCreateEntry(CatCache *cache, HeapTuple ntp, Datum *arguments,
     CacheHdr->ch_ntup++;
 
     /*
-     * If the hash table has become too full, enlarge the buckets array. Quite
-     * arbitrarily, we enlarge when fill factor > 2.
+     * If the hash table has become too full, try cleanup by removing
+     * infrequently used entries to make a room for the new entry. If it
+     * failed, enlarge the bucket array instead.  Quite arbitrarily, we try
+     * this when fill factor > 2.
      */
-    if (cache->cc_ntup > cache->cc_nbuckets * 2)
+    if (cache->cc_ntup > cache->cc_nbuckets * 2 &&
+        !CatCacheCleanupOldEntries(cache))
         RehashCatCache(cache);
 
     return ct;
diff --git a/src/backend/utils/cache/plancache.c b/src/backend/utils/cache/plancache.c
index 0ad3e3c736..701ead152c 100644
--- a/src/backend/utils/cache/plancache.c
+++ b/src/backend/utils/cache/plancache.c
@@ -63,12 +63,14 @@
 #include "storage/lmgr.h"
 #include "tcop/pquery.h"
 #include "tcop/utility.h"
+#include "utils/catcache.h"
 #include "utils/inval.h"
 #include "utils/memutils.h"
 #include "utils/resowner_private.h"
 #include "utils/rls.h"
 #include "utils/snapmgr.h"
 #include "utils/syscache.h"
+#include "utils/timestamp.h"
 
 
 /*
@@ -86,6 +88,12 @@
  * guarantee to save a CachedPlanSource without error.
  */
 static CachedPlanSource *first_saved_plan = NULL;
+static CachedPlanSource *last_saved_plan = NULL;
+static int                 num_saved_plans = 0;
+static TimestampTz         oldest_saved_plan = 0;
+
+/* GUC variables */
+int                         min_cached_plans = 1000;
 
 static void ReleaseGenericPlan(CachedPlanSource *plansource);
 static List *RevalidateCachedQuery(CachedPlanSource *plansource,
@@ -105,6 +113,7 @@ 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);
+static void PruneCachedPlan(void);
 
 
 /*
@@ -208,6 +217,8 @@ CreateCachedPlan(RawStmt *raw_parse_tree,
     plansource->generic_cost = -1;
     plansource->total_custom_cost = 0;
     plansource->num_custom_plans = 0;
+    plansource->last_access = GetCatCacheClock();
+    
 
     MemoryContextSwitchTo(oldcxt);
 
@@ -423,6 +434,28 @@ CompleteCachedPlan(CachedPlanSource *plansource,
     plansource->is_valid = true;
 }
 
+/* moves the plansource to the first in the list */
+static inline void
+MovePlansourceToFirst(CachedPlanSource *plansource)
+{
+    if (first_saved_plan != plansource)
+    {
+        /* delink this element */
+        if (plansource->next_saved)
+            plansource->next_saved->prev_saved = plansource->prev_saved;
+        if (plansource->prev_saved)
+            plansource->prev_saved->next_saved = plansource->next_saved;
+        if (last_saved_plan == plansource)
+            last_saved_plan = plansource->prev_saved;
+
+        /* insert at the beginning */
+        first_saved_plan->prev_saved = plansource;
+        plansource->next_saved = first_saved_plan;
+        plansource->prev_saved = NULL;
+        first_saved_plan = plansource;
+    }
+}
+
 /*
  * SaveCachedPlan: save a cached plan permanently
  *
@@ -470,6 +503,11 @@ SaveCachedPlan(CachedPlanSource *plansource)
      * Add the entry to the global list of cached plans.
      */
     plansource->next_saved = first_saved_plan;
+    if (first_saved_plan)
+        first_saved_plan->prev_saved = plansource;
+    else
+        last_saved_plan = plansource;
+    plansource->prev_saved = NULL;
     first_saved_plan = plansource;
 
     plansource->is_saved = true;
@@ -492,7 +530,11 @@ DropCachedPlan(CachedPlanSource *plansource)
     if (plansource->is_saved)
     {
         if (first_saved_plan == plansource)
+        {
             first_saved_plan = plansource->next_saved;
+            if (first_saved_plan)
+                first_saved_plan->prev_saved = NULL;
+        }
         else
         {
             CachedPlanSource *psrc;
@@ -502,10 +544,19 @@ DropCachedPlan(CachedPlanSource *plansource)
                 if (psrc->next_saved == plansource)
                 {
                     psrc->next_saved = plansource->next_saved;
+                    if (psrc->next_saved)
+                        psrc->next_saved->prev_saved = psrc;
                     break;
                 }
             }
         }
+
+        if (last_saved_plan == plansource)
+        {
+            last_saved_plan = plansource->prev_saved;
+            if (last_saved_plan)
+                last_saved_plan->next_saved = NULL;
+        }
         plansource->is_saved = false;
     }
 
@@ -537,6 +588,13 @@ ReleaseGenericPlan(CachedPlanSource *plansource)
         Assert(plan->magic == CACHEDPLAN_MAGIC);
         plansource->gplan = NULL;
         ReleaseCachedPlan(plan, false);
+
+        /* decrement "saved plans" counter */
+        if (plansource->is_saved)
+        {
+            Assert (num_saved_plans > 0);
+            num_saved_plans--;
+        }
     }
 }
 
@@ -1148,6 +1206,17 @@ GetCachedPlan(CachedPlanSource *plansource, ParamListInfo boundParams,
     if (useResOwner && !plansource->is_saved)
         elog(ERROR, "cannot apply ResourceOwner to non-saved cached plan");
 
+    /*
+     * set last-accessed timestamp and move this plan to the first of the list
+     */
+    if (plansource->is_saved)
+    {
+        plansource->last_access = GetCatCacheClock();
+
+        /* move this plan to the first of the list */
+        MovePlansourceToFirst(plansource);
+    }
+
     /* Make sure the querytree list is valid and we have parse-time locks */
     qlist = RevalidateCachedQuery(plansource, queryEnv);
 
@@ -1156,6 +1225,11 @@ GetCachedPlan(CachedPlanSource *plansource, ParamListInfo boundParams,
 
     if (!customplan)
     {
+        /* Prune cached plans if needed */
+        if (plansource->is_saved &&
+            min_cached_plans >= 0 && num_saved_plans > min_cached_plans)
+                PruneCachedPlan();
+
         if (CheckCachedPlan(plansource))
         {
             /* We want a generic plan, and we already have a valid one */
@@ -1168,6 +1242,11 @@ GetCachedPlan(CachedPlanSource *plansource, ParamListInfo boundParams,
             plan = BuildCachedPlan(plansource, qlist, NULL, queryEnv);
             /* Just make real sure plansource->gplan is clear */
             ReleaseGenericPlan(plansource);
+
+            /* count this new saved plan */
+            if (plansource->is_saved)
+                num_saved_plans++;
+
             /* Link the new generic plan into the plansource */
             plansource->gplan = plan;
             plan->refcount++;
@@ -1856,6 +1935,90 @@ PlanCacheSysCallback(Datum arg, int cacheid, uint32 hashvalue)
     ResetPlanCache();
 }
 
+/*
+ * PrunePlanCache: removes generic plan of "old" saved plans.
+ */
+static void
+PruneCachedPlan(void)
+{
+    CachedPlanSource *plansource;
+    TimestampTz          currclock = GetCatCacheClock();
+    long              age;
+    int                  us;
+    int                  nremoved = 0;
+
+    /* do nothing if not wanted */
+    if (cache_prune_min_age < 0 || num_saved_plans <= min_cached_plans)
+        return;
+
+    /* Fast check for oldest cache */
+    if (oldest_saved_plan > 0)
+    {
+        TimestampDifference(oldest_saved_plan, currclock, &age, &us);
+        if (age < cache_prune_min_age)
+            return;
+    }        
+
+    /* last plan is the oldest. */
+    for (plansource = last_saved_plan; plansource; plansource = plansource->prev_saved)
+    {
+        long    plan_age;
+        int        us;
+
+        Assert(plansource->magic == CACHEDPLANSOURCE_MAGIC);
+
+        /* we want to prune no more plans */
+        if (num_saved_plans <= min_cached_plans)
+            break;
+
+        /*
+         * No work if it already doesn't have gplan and move it to the
+         * beginning so that we don't see it at the next time
+         */
+        if (!plansource->gplan)
+            continue;
+
+        /*
+         * Check age for pruning. Can exit immediately when finding a
+         * not-older element.
+         */
+        TimestampDifference(plansource->last_access, currclock, &plan_age, &us);
+        if (plan_age <= cache_prune_min_age)
+        {
+            /* this entry is the next oldest */
+            oldest_saved_plan = plansource->last_access;
+            break;
+        }
+
+        /*
+         * Here, remove generic plans of this plansrouceif it is not actually
+         * used and move it to the beginning of the list. Just update
+         * last_access and move it to the beginning if the plan is used.
+         */
+        if (plansource->gplan->refcount <= 1)
+        {
+            ReleaseGenericPlan(plansource);
+            nremoved++;
+        }
+
+        plansource->last_access = currclock;
+    }
+
+    /* move the "removed" plansrouces altogehter to the beginning of the list */
+    if (plansource != last_saved_plan && plansource)
+    {
+        plansource->next_saved->prev_saved = NULL;
+        first_saved_plan->prev_saved = last_saved_plan;
+         last_saved_plan->next_saved = first_saved_plan;
+        first_saved_plan = plansource->next_saved;
+        plansource->next_saved = NULL;
+        last_saved_plan = plansource;
+    }
+
+    if (nremoved > 0)
+        elog(DEBUG1, "plancache removed %d/%d", nremoved, num_saved_plans);
+}
+
 /*
  * ResetPlanCache: invalidate all cached plans.
  */
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index 859ef931e7..774a87ed2c 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -79,6 +79,7 @@
 #include "tsearch/ts_cache.h"
 #include "utils/builtins.h"
 #include "utils/bytea.h"
+#include "utils/catcache.h"
 #include "utils/guc_tables.h"
 #include "utils/memutils.h"
 #include "utils/pg_locale.h"
@@ -2105,6 +2106,38 @@ static struct config_int ConfigureNamesInt[] =
         NULL, NULL, NULL
     },
 
+    {
+        {"cache_memory_target", PGC_USERSET, RESOURCES_MEM,
+            gettext_noop("Sets the minimum syscache size to keep."),
+            gettext_noop("Cache is not pruned before exceeding this size."),
+            GUC_UNIT_KB
+        },
+        &cache_memory_target,
+        0, 0, MAX_KILOBYTES,
+        NULL, NULL, NULL
+    },
+
+    {
+        {"cache_prune_min_age", PGC_USERSET, RESOURCES_MEM,
+            gettext_noop("Sets the minimum unused duration of cache entries before removal."),
+            gettext_noop("Cache entries that live unused for longer than this seconds are considered to be
removed."),
+            GUC_UNIT_S
+        },
+        &cache_prune_min_age,
+        600, -1, INT_MAX,
+        NULL, NULL, NULL
+    },
+
+    {
+        {"min_cached_plans", PGC_USERSET, RESOURCES_MEM,
+            gettext_noop("Sets the minimum number of cached plans kept on memory."),
+            gettext_noop("Timeout invalidation of plancache is not activated until the number of plancaches reaches
thisvalue. -1 means timeout invalidation is always active.")
 
+        },
+        &min_cached_plans,
+        1000, -1, INT_MAX,
+        NULL, NULL, NULL
+    },
+
     /*
      * We use the hopefully-safely-small value of 100kB as the compiled-in
      * default for max_stack_depth.  InitializeGUCOptions will increase it if
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index 9e39baf466..3f2760ef9d 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -126,6 +126,8 @@
 #work_mem = 4MB                # min 64kB
 #maintenance_work_mem = 64MB        # min 1MB
 #autovacuum_work_mem = -1        # min 1MB, or -1 to use maintenance_work_mem
+#cache_memory_target = 0kB    # in kB
+#cache_prune_min_age = 600s    # -1 disables pruning
 #max_stack_depth = 2MB            # min 100kB
 #dynamic_shared_memory_type = posix    # the default is the first option
                     # supported by the operating system:
diff --git a/src/include/utils/catcache.h b/src/include/utils/catcache.h
index 7b22f9c7bc..599303be56 100644
--- a/src/include/utils/catcache.h
+++ b/src/include/utils/catcache.h
@@ -22,6 +22,7 @@
 
 #include "access/htup.h"
 #include "access/skey.h"
+#include "datatype/timestamp.h"
 #include "lib/ilist.h"
 #include "utils/relcache.h"
 
@@ -119,6 +120,8 @@ typedef struct catctup
     bool        dead;            /* dead but not yet removed? */
     bool        negative;        /* negative cache entry? */
     HeapTupleData tuple;        /* tuple management header */
+    int            naccess;        /* # of access to this entry, up to 2  */
+    TimestampTz    lastaccess;        /* approx. timestamp of the last usage */
 
     /*
      * The tuple may also be a member of at most one CatCList.  (If a single
@@ -189,6 +192,22 @@ typedef struct catcacheheader
 /* this extern duplicates utils/memutils.h... */
 extern PGDLLIMPORT MemoryContext CacheMemoryContext;
 
+/* for guc.c, not PGDLLPMPORT'ed */
+extern int cache_prune_min_age;
+extern int cache_memory_target;
+
+/* to use as access timestamp of catcache entries */
+extern TimestampTz catcacheclock;
+
+/*
+ * SetCatCacheClock - set timestamp for catcache access record
+ */
+static inline void
+SetCatCacheClock(TimestampTz ts)
+{
+    catcacheclock = ts;
+}
+
 extern void CreateCacheMemoryContext(void);
 
 extern CatCache *InitCatCache(int id, Oid reloid, Oid indexoid,
diff --git a/src/include/utils/plancache.h b/src/include/utils/plancache.h
index ab20aa04b0..f3c5b2010d 100644
--- a/src/include/utils/plancache.h
+++ b/src/include/utils/plancache.h
@@ -110,11 +110,13 @@ typedef struct CachedPlanSource
     bool        is_valid;        /* is the query_list currently valid? */
     int            generation;        /* increments each time we create a plan */
     /* If CachedPlanSource has been saved, it is a member of a global list */
-    struct CachedPlanSource *next_saved;    /* list link, if so */
+    struct CachedPlanSource *prev_saved;    /* list prev link, if so */
+    struct CachedPlanSource *next_saved;    /* list next link, if so */
     /* State kept to help decide whether to use custom or generic plans: */
     double        generic_cost;    /* cost of generic plan, or -1 if not known */
     double        total_custom_cost;    /* total cost of custom plans so far */
     int            num_custom_plans;    /* number of plans included in total */
+    TimestampTz    last_access;    /* timestamp of the last usage */
 } CachedPlanSource;
 
 /*
@@ -143,6 +145,9 @@ typedef struct CachedPlan
     MemoryContext context;        /* context containing this CachedPlan */
 } CachedPlan;
 
+/* GUC variables */
+extern int min_cached_plans;
+extern int plancache_prune_min_age;
 
 extern void InitPlanCache(void);
 extern void ResetPlanCache(void);
-- 
2.16.3