Re: Protect syscache from bloating with negative cache entries - Mailing list pgsql-hackers

I'm really disappointed by the direction this thread is going in.
The latest patches add an enormous amount of mechanism, and user-visible
complexity, to do something that we learned was a bad idea decades ago.
Putting a limit on the size of the syscaches doesn't accomplish anything
except to add cycles if your cache working set is below the limit, or
make performance fall off a cliff if it's above the limit.  I don't think
there's any reason to believe that making it more complicated will avoid
that problem.

What does seem promising is something similar to Horiguchi-san's
original patches all the way back at

https://www.postgresql.org/message-id/20161219.201505.11562604.horiguchi.kyotaro@lab.ntt.co.jp

That is, identify usage patterns in which we tend to fill the caches with
provably no-longer-useful entries, and improve those particular cases.
Horiguchi-san identified one such case in that message: negative entries
in the STATRELATTINH cache, caused by the planner probing for stats that
aren't there, and then not cleared when the relevant table gets dropped
(since, by definition, they don't match any pg_statistic entry that gets
deleted).  We saw another recent report of the same problem at

https://www.postgresql.org/message-id/flat/2114009259.1866365.1544469996900%40mail.yahoo.com

so I'd been thinking about ways to fix that case in particular.  I came
up with a fix that I think is simpler and a bit more efficient than
what Horiguchi-san proposed originally: rather than trying to reverse-
engineer what to do in low-level cache callbacks, let's have the catalog
manipulation code explicitly send out invalidation commands when the
relevant situations arise.  In the attached, heap.c's RemoveStatistics
sends out an sinval message commanding deletion of negative STATRELATTINH
entries that match the OID of the table being deleted.  We could use the
same infrastructure to clean out dead RELNAMENSP entries after a schema
deletion, as per Horiguchi-san's second original suggestion; although
I haven't done so here because I'm not really convinced that that's got
an attractive cost-benefit ratio.  (In both my patch and Horiguchi-san's,
we have to traverse all entries in the affected cache, so sending out one
of these messages is potentially not real cheap.)

To do this we need to adjust the representation of sinval messages so
that we can have two different kinds of messages that include a cache ID.
Fortunately, because there's padding space available, that's not costly.
0001 below is a simple refactoring patch that converts the message type
ID into a plain enum field that's separate from the cache ID if any.
(I'm inclined to apply this whether or not people like 0002: it makes
the code clearer, more maintainable, and probably a shade faster thanks
to replacing an if-then-else chain with a switch.)  Then 0002 adds the
feature of an sinval message type saying "delete negative entries in
cache X that have OID Y in key column Z", and teaches RemoveStatistics
to use that.

Thoughts?

            regards, tom lane

diff --git a/src/backend/access/rmgrdesc/standbydesc.c b/src/backend/access/rmgrdesc/standbydesc.c
index c295358..a7f367c 100644
*** a/src/backend/access/rmgrdesc/standbydesc.c
--- b/src/backend/access/rmgrdesc/standbydesc.c
*************** standby_desc_invalidations(StringInfo bu
*** 111,131 ****
      {
          SharedInvalidationMessage *msg = &msgs[i];

!         if (msg->id >= 0)
!             appendStringInfo(buf, " catcache %d", msg->id);
!         else if (msg->id == SHAREDINVALCATALOG_ID)
!             appendStringInfo(buf, " catalog %u", msg->cat.catId);
!         else if (msg->id == SHAREDINVALRELCACHE_ID)
!             appendStringInfo(buf, " relcache %u", msg->rc.relId);
!         /* not expected, but print something anyway */
!         else if (msg->id == SHAREDINVALSMGR_ID)
!             appendStringInfoString(buf, " smgr");
!         /* not expected, but print something anyway */
!         else if (msg->id == SHAREDINVALRELMAP_ID)
!             appendStringInfo(buf, " relmap db %u", msg->rm.dbId);
!         else if (msg->id == SHAREDINVALSNAPSHOT_ID)
!             appendStringInfo(buf, " snapshot %u", msg->sn.relId);
!         else
!             appendStringInfo(buf, " unrecognized id %d", msg->id);
      }
  }
--- 111,141 ----
      {
          SharedInvalidationMessage *msg = &msgs[i];

!         switch ((SharedInvalMsgType) msg->id)
!         {
!             case SharedInvalCatcache:
!                 appendStringInfo(buf, " catcache %d", msg->cc.cacheId);
!                 break;
!             case SharedInvalCatalog:
!                 appendStringInfo(buf, " catalog %u", msg->cat.catId);
!                 break;
!             case SharedInvalRelcache:
!                 appendStringInfo(buf, " relcache %u", msg->rc.relId);
!                 break;
!             case SharedInvalSmgr:
!                 /* not expected, but print something anyway */
!                 appendStringInfoString(buf, " smgr");
!                 break;
!             case SharedInvalRelmap:
!                 /* not expected, but print something anyway */
!                 appendStringInfo(buf, " relmap db %u", msg->rm.dbId);
!                 break;
!             case SharedInvalSnapshot:
!                 appendStringInfo(buf, " snapshot %u", msg->sn.relId);
!                 break;
!             default:
!                 appendStringInfo(buf, " unrecognized id %d", msg->id);
!                 break;
!         }
      }
  }
diff --git a/src/backend/utils/cache/inval.c b/src/backend/utils/cache/inval.c
index 80d7a76..5bc08b0 100644
*** a/src/backend/utils/cache/inval.c
--- b/src/backend/utils/cache/inval.c
*************** AddCatcacheInvalidationMessage(Invalidat
*** 340,346 ****
      SharedInvalidationMessage msg;

      Assert(id < CHAR_MAX);
!     msg.cc.id = (int8) id;
      msg.cc.dbId = dbId;
      msg.cc.hashValue = hashValue;

--- 340,347 ----
      SharedInvalidationMessage msg;

      Assert(id < CHAR_MAX);
!     msg.cc.id = SharedInvalCatcache;
!     msg.cc.cacheId = (int8) id;
      msg.cc.dbId = dbId;
      msg.cc.hashValue = hashValue;

*************** AddCatalogInvalidationMessage(Invalidati
*** 367,373 ****
  {
      SharedInvalidationMessage msg;

!     msg.cat.id = SHAREDINVALCATALOG_ID;
      msg.cat.dbId = dbId;
      msg.cat.catId = catId;
      /* check AddCatcacheInvalidationMessage() for an explanation */
--- 368,374 ----
  {
      SharedInvalidationMessage msg;

!     msg.cat.id = SharedInvalCatalog;
      msg.cat.dbId = dbId;
      msg.cat.catId = catId;
      /* check AddCatcacheInvalidationMessage() for an explanation */
*************** AddRelcacheInvalidationMessage(Invalidat
*** 391,403 ****
       * don't need to add individual ones when it is present.
       */
      ProcessMessageList(hdr->rclist,
!                        if (msg->rc.id == SHAREDINVALRELCACHE_ID &&
                             (msg->rc.relId == relId ||
                              msg->rc.relId == InvalidOid))
                         return);

      /* OK, add the item */
!     msg.rc.id = SHAREDINVALRELCACHE_ID;
      msg.rc.dbId = dbId;
      msg.rc.relId = relId;
      /* check AddCatcacheInvalidationMessage() for an explanation */
--- 392,404 ----
       * don't need to add individual ones when it is present.
       */
      ProcessMessageList(hdr->rclist,
!                        if (msg->rc.id == SharedInvalRelcache &&
                             (msg->rc.relId == relId ||
                              msg->rc.relId == InvalidOid))
                         return);

      /* OK, add the item */
!     msg.rc.id = SharedInvalRelcache;
      msg.rc.dbId = dbId;
      msg.rc.relId = relId;
      /* check AddCatcacheInvalidationMessage() for an explanation */
*************** AddSnapshotInvalidationMessage(Invalidat
*** 418,429 ****
      /* Don't add a duplicate item */
      /* We assume dbId need not be checked because it will never change */
      ProcessMessageList(hdr->rclist,
!                        if (msg->sn.id == SHAREDINVALSNAPSHOT_ID &&
                             msg->sn.relId == relId)
                         return);

      /* OK, add the item */
!     msg.sn.id = SHAREDINVALSNAPSHOT_ID;
      msg.sn.dbId = dbId;
      msg.sn.relId = relId;
      /* check AddCatcacheInvalidationMessage() for an explanation */
--- 419,430 ----
      /* Don't add a duplicate item */
      /* We assume dbId need not be checked because it will never change */
      ProcessMessageList(hdr->rclist,
!                        if (msg->sn.id == SharedInvalSnapshot &&
                             msg->sn.relId == relId)
                         return);

      /* OK, add the item */
!     msg.sn.id = SharedInvalSnapshot;
      msg.sn.dbId = dbId;
      msg.sn.relId = relId;
      /* check AddCatcacheInvalidationMessage() for an explanation */
*************** RegisterSnapshotInvalidation(Oid dbId, O
*** 553,629 ****
  void
  LocalExecuteInvalidationMessage(SharedInvalidationMessage *msg)
  {
!     if (msg->id >= 0)
      {
!         if (msg->cc.dbId == MyDatabaseId || msg->cc.dbId == InvalidOid)
!         {
!             InvalidateCatalogSnapshot();

!             SysCacheInvalidate(msg->cc.id, msg->cc.hashValue);

!             CallSyscacheCallbacks(msg->cc.id, msg->cc.hashValue);
!         }
!     }
!     else if (msg->id == SHAREDINVALCATALOG_ID)
!     {
!         if (msg->cat.dbId == MyDatabaseId || msg->cat.dbId == InvalidOid)
!         {
!             InvalidateCatalogSnapshot();

!             CatalogCacheFlushCatalog(msg->cat.catId);

!             /* CatalogCacheFlushCatalog calls CallSyscacheCallbacks as needed */
!         }
!     }
!     else if (msg->id == SHAREDINVALRELCACHE_ID)
!     {
!         if (msg->rc.dbId == MyDatabaseId || msg->rc.dbId == InvalidOid)
!         {
!             int            i;

!             if (msg->rc.relId == InvalidOid)
!                 RelationCacheInvalidate();
!             else
!                 RelationCacheInvalidateEntry(msg->rc.relId);

!             for (i = 0; i < relcache_callback_count; i++)
!             {
!                 struct RELCACHECALLBACK *ccitem = relcache_callback_list + i;

!                 ccitem->function(ccitem->arg, msg->rc.relId);
              }
!         }
!     }
!     else if (msg->id == SHAREDINVALSMGR_ID)
!     {
!         /*
!          * We could have smgr entries for relations of other databases, so no
!          * short-circuit test is possible here.
!          */
!         RelFileNodeBackend rnode;

!         rnode.node = msg->sm.rnode;
!         rnode.backend = (msg->sm.backend_hi << 16) | (int) msg->sm.backend_lo;
!         smgrclosenode(rnode);
!     }
!     else if (msg->id == SHAREDINVALRELMAP_ID)
!     {
!         /* We only care about our own database and shared catalogs */
!         if (msg->rm.dbId == InvalidOid)
!             RelationMapInvalidate(true);
!         else if (msg->rm.dbId == MyDatabaseId)
!             RelationMapInvalidate(false);
!     }
!     else if (msg->id == SHAREDINVALSNAPSHOT_ID)
!     {
!         /* We only care about our own database and shared catalogs */
!         if (msg->rm.dbId == InvalidOid)
!             InvalidateCatalogSnapshot();
!         else if (msg->rm.dbId == MyDatabaseId)
!             InvalidateCatalogSnapshot();
      }
-     else
-         elog(FATAL, "unrecognized SI message ID: %d", msg->id);
  }

  /*
--- 554,633 ----
  void
  LocalExecuteInvalidationMessage(SharedInvalidationMessage *msg)
  {
!     switch ((SharedInvalMsgType) msg->id)
      {
!         case SharedInvalCatcache:
!             if (msg->cc.dbId == MyDatabaseId || msg->cc.dbId == InvalidOid)
!             {
!                 InvalidateCatalogSnapshot();

!                 SysCacheInvalidate(msg->cc.cacheId, msg->cc.hashValue);

!                 CallSyscacheCallbacks(msg->cc.cacheId, msg->cc.hashValue);
!             }
!             break;
!         case SharedInvalCatalog:
!             if (msg->cat.dbId == MyDatabaseId || msg->cat.dbId == InvalidOid)
!             {
!                 InvalidateCatalogSnapshot();

!                 CatalogCacheFlushCatalog(msg->cat.catId);

!                 /*
!                  * CatalogCacheFlushCatalog calls CallSyscacheCallbacks as
!                  * needed
!                  */
!             }
!             break;
!         case SharedInvalRelcache:
!             if (msg->rc.dbId == MyDatabaseId || msg->rc.dbId == InvalidOid)
!             {
!                 int            i;

!                 if (msg->rc.relId == InvalidOid)
!                     RelationCacheInvalidate();
!                 else
!                     RelationCacheInvalidateEntry(msg->rc.relId);

!                 for (i = 0; i < relcache_callback_count; i++)
!                 {
!                     struct RELCACHECALLBACK *ccitem = relcache_callback_list + i;

!                     ccitem->function(ccitem->arg, msg->rc.relId);
!                 }
              }
!             break;
!         case SharedInvalSmgr:
!             {
!                 /*
!                  * We could have smgr entries for relations of other
!                  * databases, so no short-circuit test is possible here.
!                  */
!                 RelFileNodeBackend rnode;

!                 rnode.node = msg->sm.rnode;
!                 rnode.backend = (msg->sm.backend_hi << 16) | (int) msg->sm.backend_lo;
!                 smgrclosenode(rnode);
!                 break;
!             }
!         case SharedInvalRelmap:
!             /* We only care about our own database and shared catalogs */
!             if (msg->rm.dbId == InvalidOid)
!                 RelationMapInvalidate(true);
!             else if (msg->rm.dbId == MyDatabaseId)
!                 RelationMapInvalidate(false);
!             break;
!         case SharedInvalSnapshot:
!             /* We only care about our own database and shared catalogs */
!             if (msg->rm.dbId == InvalidOid)
!                 InvalidateCatalogSnapshot();
!             else if (msg->rm.dbId == MyDatabaseId)
!                 InvalidateCatalogSnapshot();
!             break;
!         default:
!             elog(FATAL, "unrecognized SI message ID: %d", msg->id);
!             break;
      }
  }

  /*
*************** CacheInvalidateSmgr(RelFileNodeBackend r
*** 1351,1357 ****
  {
      SharedInvalidationMessage msg;

!     msg.sm.id = SHAREDINVALSMGR_ID;
      msg.sm.backend_hi = rnode.backend >> 16;
      msg.sm.backend_lo = rnode.backend & 0xffff;
      msg.sm.rnode = rnode.node;
--- 1355,1361 ----
  {
      SharedInvalidationMessage msg;

!     msg.sm.id = SharedInvalSmgr;
      msg.sm.backend_hi = rnode.backend >> 16;
      msg.sm.backend_lo = rnode.backend & 0xffff;
      msg.sm.rnode = rnode.node;
*************** CacheInvalidateRelmap(Oid databaseId)
*** 1381,1387 ****
  {
      SharedInvalidationMessage msg;

!     msg.rm.id = SHAREDINVALRELMAP_ID;
      msg.rm.dbId = databaseId;
      /* check AddCatcacheInvalidationMessage() for an explanation */
      VALGRIND_MAKE_MEM_DEFINED(&msg, sizeof(msg));
--- 1385,1391 ----
  {
      SharedInvalidationMessage msg;

!     msg.rm.id = SharedInvalRelmap;
      msg.rm.dbId = databaseId;
      /* check AddCatcacheInvalidationMessage() for an explanation */
      VALGRIND_MAKE_MEM_DEFINED(&msg, sizeof(msg));
diff --git a/src/include/storage/sinval.h b/src/include/storage/sinval.h
index 635acda..d0d9ece 100644
*** a/src/include/storage/sinval.h
--- b/src/include/storage/sinval.h
***************
*** 28,36 ****
   *    * invalidate the mapped-relation mapping for a given database
   *    * invalidate any saved snapshot that might be used to scan a given relation
   * More types could be added if needed.  The message type is identified by
!  * the first "int8" field of the message struct.  Zero or positive means a
!  * specific-catcache inval message (and also serves as the catcache ID field).
!  * Negative values identify the other message types, as per codes below.
   *
   * Catcache inval events are initially driven by detecting tuple inserts,
   * updates and deletions in system catalogs (see CacheInvalidateHeapTuple).
--- 28,34 ----
   *    * invalidate the mapped-relation mapping for a given database
   *    * invalidate any saved snapshot that might be used to scan a given relation
   * More types could be added if needed.  The message type is identified by
!  * the first "int8" field of the message struct.
   *
   * Catcache inval events are initially driven by detecting tuple inserts,
   * updates and deletions in system catalogs (see CacheInvalidateHeapTuple).
***************
*** 57,71 ****
   * sent immediately when the underlying file change is made.
   */

  typedef struct
  {
!     int8        id;                /* cache ID --- must be first */
      Oid            dbId;            /* database ID, or 0 if a shared relation */
      uint32        hashValue;        /* hash value of key for this catcache */
  } SharedInvalCatcacheMsg;

- #define SHAREDINVALCATALOG_ID    (-1)
-
  typedef struct
  {
      int8        id;                /* type field --- must be first */
--- 55,78 ----
   * sent immediately when the underlying file change is made.
   */

+ typedef enum SharedInvalMsgType
+ {
+     SharedInvalCatcache,
+     SharedInvalCatalog,
+     SharedInvalRelcache,
+     SharedInvalSmgr,
+     SharedInvalRelmap,
+     SharedInvalSnapshot
+ } SharedInvalMsgType;
+
  typedef struct
  {
!     int8        id;                /* type field --- must be first */
!     int8        cacheId;        /* cache ID */
      Oid            dbId;            /* database ID, or 0 if a shared relation */
      uint32        hashValue;        /* hash value of key for this catcache */
  } SharedInvalCatcacheMsg;

  typedef struct
  {
      int8        id;                /* type field --- must be first */
*************** typedef struct
*** 73,80 ****
      Oid            catId;            /* ID of catalog whose contents are invalid */
  } SharedInvalCatalogMsg;

- #define SHAREDINVALRELCACHE_ID    (-2)
-
  typedef struct
  {
      int8        id;                /* type field --- must be first */
--- 80,85 ----
*************** typedef struct
*** 82,89 ****
      Oid            relId;            /* relation ID, or 0 if whole relcache */
  } SharedInvalRelcacheMsg;

- #define SHAREDINVALSMGR_ID        (-3)
-
  typedef struct
  {
      /* note: field layout chosen to pack into 16 bytes */
--- 87,92 ----
*************** typedef struct
*** 93,108 ****
      RelFileNode rnode;            /* spcNode, dbNode, relNode */
  } SharedInvalSmgrMsg;

- #define SHAREDINVALRELMAP_ID    (-4)
-
  typedef struct
  {
      int8        id;                /* type field --- must be first */
      Oid            dbId;            /* database ID, or 0 for shared catalogs */
  } SharedInvalRelmapMsg;

- #define SHAREDINVALSNAPSHOT_ID    (-5)
-
  typedef struct
  {
      int8        id;                /* type field --- must be first */
--- 96,107 ----
diff --git a/src/backend/access/rmgrdesc/standbydesc.c b/src/backend/access/rmgrdesc/standbydesc.c
index a7f367c..79823c2 100644
*** a/src/backend/access/rmgrdesc/standbydesc.c
--- b/src/backend/access/rmgrdesc/standbydesc.c
*************** standby_desc_invalidations(StringInfo bu
*** 113,120 ****

          switch ((SharedInvalMsgType) msg->id)
          {
!             case SharedInvalCatcache:
!                 appendStringInfo(buf, " catcache %d", msg->cc.cacheId);
                  break;
              case SharedInvalCatalog:
                  appendStringInfo(buf, " catalog %u", msg->cat.catId);
--- 113,123 ----

          switch ((SharedInvalMsgType) msg->id)
          {
!             case SharedInvalCatcacheHash:
!                 appendStringInfo(buf, " catcache %d by hash", msg->cch.cacheId);
!                 break;
!             case SharedInvalCatcacheOid:
!                 appendStringInfo(buf, " catcache %d by OID", msg->cco.cacheId);
                  break;
              case SharedInvalCatalog:
                  appendStringInfo(buf, " catalog %u", msg->cat.catId);
diff --git a/src/backend/catalog/heap.c b/src/backend/catalog/heap.c
index 472285d..ebf4321 100644
*** a/src/backend/catalog/heap.c
--- b/src/backend/catalog/heap.c
*************** RemoveStatistics(Oid relid, AttrNumber a
*** 3025,3030 ****
--- 3025,3048 ----

      systable_endscan(scan);

+     /*
+      * Aside from removing the catalog entries, issue sinval messages to
+      * remove any negative catcache entries for stats that weren't present.
+      * (Positive entries will get flushed as a consequence of deleting the
+      * catalog entries.)  Without this, repeatedly creating and dropping temp
+      * tables tends to lead to catcache bloat, since any negative catcache
+      * entries created by planner lookups won't get dropped.
+      *
+      * We only bother with this for the whole-table case, since (a) it's less
+      * likely to be a problem for DROP COLUMN, and (b) the sinval
+      * infrastructure only supports matching an OID cache key column.
+      * (Alternatively, we could issue the sinval message always, accepting the
+      * collateral damage of losing negative catcache entries for other columns
+      * to be sure we get rid of entries for this one.)
+      */
+     if (attnum == 0)
+         CacheInvalidateCatcacheByOid(STATRELATTINH, false, 1, relid);
+
      heap_close(pgstatistic, RowExclusiveLock);
  }

diff --git a/src/backend/utils/cache/catcache.c b/src/backend/utils/cache/catcache.c
index 8152f7e..81c01f6 100644
*** a/src/backend/utils/cache/catcache.c
--- b/src/backend/utils/cache/catcache.c
*************** CatCacheRemoveCList(CatCache *cache, Cat
*** 540,546 ****


  /*
!  *    CatCacheInvalidate
   *
   *    Invalidate entries in the specified cache, given a hash value.
   *
--- 540,546 ----


  /*
!  *    CatCacheInvalidateByHash
   *
   *    Invalidate entries in the specified cache, given a hash value.
   *
*************** CatCacheRemoveCList(CatCache *cache, Cat
*** 558,569 ****
   *    This routine is only quasi-public: it should only be used by inval.c.
   */
  void
! CatCacheInvalidate(CatCache *cache, uint32 hashValue)
  {
      Index        hashIndex;
      dlist_mutable_iter iter;

!     CACHE1_elog(DEBUG2, "CatCacheInvalidate: called");

      /*
       * We don't bother to check whether the cache has finished initialization
--- 558,569 ----
   *    This routine is only quasi-public: it should only be used by inval.c.
   */
  void
! CatCacheInvalidateByHash(CatCache *cache, uint32 hashValue)
  {
      Index        hashIndex;
      dlist_mutable_iter iter;

!     CACHE1_elog(DEBUG2, "CatCacheInvalidateByHash: called");

      /*
       * We don't bother to check whether the cache has finished initialization
*************** CatCacheInvalidate(CatCache *cache, uint
*** 603,609 ****
              }
              else
                  CatCacheRemoveCTup(cache, ct);
!             CACHE1_elog(DEBUG2, "CatCacheInvalidate: invalidated");
  #ifdef CATCACHE_STATS
              cache->cc_invals++;
  #endif
--- 603,609 ----
              }
              else
                  CatCacheRemoveCTup(cache, ct);
!             CACHE1_elog(DEBUG2, "CatCacheInvalidateByHash: invalidated");
  #ifdef CATCACHE_STATS
              cache->cc_invals++;
  #endif
*************** CatCacheInvalidate(CatCache *cache, uint
*** 612,617 ****
--- 612,683 ----
      }
  }

+ /*
+  *    CatCacheInvalidateByOid
+  *
+  *    Invalidate negative entries in the specified cache, given a target OID.
+  *
+  *    We delete negative cache entries that have that OID value in column ckey.
+  *    While we could also examine positive entries, there's no need to do so in
+  *    current usage: any relevant positive entries should have been flushed by
+  *    CatCacheInvalidateByHash calls due to deletions of those catalog entries.
+  *
+  *    This routine is only quasi-public: it should only be used by inval.c.
+  */
+ void
+ CatCacheInvalidateByOid(CatCache *cache, int ckey, Oid oid)
+ {
+     dlist_mutable_iter iter;
+     int            i;
+
+     CACHE1_elog(DEBUG2, "CatCacheInvalidateByOid: called");
+
+     /* If the cache hasn't finished initialization, there's nothing to do */
+     if (cache->cc_tupdesc == NULL)
+         return;
+
+     /* Assert that an OID column has been targeted */
+     Assert(TupleDescAttr(cache->cc_tupdesc,
+                          cache->cc_keyno[ckey - 1] - 1)->atttypid == OIDOID);
+
+     /*
+      * There seems no need to flush CatCLists; removal of negative entries
+      * shouldn't affect the validity of searches.
+      */
+
+     /*
+      * Scan the whole cache for matches
+      */
+     for (i = 0; i < cache->cc_nbuckets; i++)
+     {
+         dlist_head *bucket = &cache->cc_bucket[i];
+
+         dlist_foreach_modify(iter, bucket)
+         {
+             CatCTup    *ct = dlist_container(CatCTup, cache_elem, iter.cur);
+
+             /* We only care about live negative entries */
+             if (ct->dead || !ct->negative)
+                 continue;
+             /* Negative entries won't be in clists */
+             Assert(ct->c_list == NULL);
+
+             if (oid == DatumGetObjectId(ct->keys[ckey - 1]))
+             {
+                 if (ct->refcount > 0)
+                     ct->dead = true;
+                 else
+                     CatCacheRemoveCTup(cache, ct);
+                 CACHE1_elog(DEBUG2, "CatCacheInvalidateByOid: invalidated");
+ #ifdef CATCACHE_STATS
+                 cache->cc_invals++;
+ #endif
+                 /* could be multiple matches, so keep looking! */
+             }
+         }
+     }
+ }
+
  /* ----------------------------------------------------------------
   *                       public functions
   * ----------------------------------------------------------------
*************** CatCacheCopyKeys(TupleDesc tupdesc, int
*** 1995,2001 ****
   *    the specified relation, find all catcaches it could be in, compute the
   *    correct hash value for each such catcache, and call the specified
   *    function to record the cache id and hash value in inval.c's lists.
!  *    SysCacheInvalidate will be called later, if appropriate,
   *    using the recorded information.
   *
   *    For an insert or delete, tuple is the target tuple and newtuple is NULL.
--- 2061,2067 ----
   *    the specified relation, find all catcaches it could be in, compute the
   *    correct hash value for each such catcache, and call the specified
   *    function to record the cache id and hash value in inval.c's lists.
!  *    SysCacheInvalidateByHash will be called later, if appropriate,
   *    using the recorded information.
   *
   *    For an insert or delete, tuple is the target tuple and newtuple is NULL.
diff --git a/src/backend/utils/cache/inval.c b/src/backend/utils/cache/inval.c
index 5bc08b0..168a97d 100644
*** a/src/backend/utils/cache/inval.c
--- b/src/backend/utils/cache/inval.c
*************** AppendInvalidationMessageList(Invalidati
*** 331,349 ****
   */

  /*
!  * Add a catcache inval entry
   */
  static void
! AddCatcacheInvalidationMessage(InvalidationListHeader *hdr,
!                                int id, uint32 hashValue, Oid dbId)
  {
      SharedInvalidationMessage msg;

      Assert(id < CHAR_MAX);
!     msg.cc.id = SharedInvalCatcache;
!     msg.cc.cacheId = (int8) id;
!     msg.cc.dbId = dbId;
!     msg.cc.hashValue = hashValue;

      /*
       * Define padding bytes in SharedInvalidationMessage structs to be
--- 331,349 ----
   */

  /*
!  * Add a catcache inval-by-hash entry
   */
  static void
! AddCatcacheHashInvalidationMessage(InvalidationListHeader *hdr,
!                                    int id, uint32 hashValue, Oid dbId)
  {
      SharedInvalidationMessage msg;

      Assert(id < CHAR_MAX);
!     msg.cch.id = SharedInvalCatcacheHash;
!     msg.cch.cacheId = (int8) id;
!     msg.cch.dbId = dbId;
!     msg.cch.hashValue = hashValue;

      /*
       * Define padding bytes in SharedInvalidationMessage structs to be
*************** AddCatcacheInvalidationMessage(Invalidat
*** 360,365 ****
--- 360,386 ----
  }

  /*
+  * Add a catcache inval-by-OID entry
+  */
+ static void
+ AddCatcacheOidInvalidationMessage(InvalidationListHeader *hdr,
+                                   int id, int ckey, Oid oid, Oid dbId)
+ {
+     SharedInvalidationMessage msg;
+
+     Assert(id < CHAR_MAX);
+     msg.cco.id = SharedInvalCatcacheOid;
+     msg.cco.cacheId = (int8) id;
+     msg.cco.ckey = (int8) ckey;
+     msg.cco.oid = oid;
+     msg.cco.dbId = dbId;
+     /* check AddCatcacheHashInvalidationMessage() for an explanation */
+     VALGRIND_MAKE_MEM_DEFINED(&msg, sizeof(msg));
+
+     AddInvalidationMessage(&hdr->cclist, &msg);
+ }
+
+ /*
   * Add a whole-catalog inval entry
   */
  static void
*************** AddCatalogInvalidationMessage(Invalidati
*** 371,377 ****
      msg.cat.id = SharedInvalCatalog;
      msg.cat.dbId = dbId;
      msg.cat.catId = catId;
!     /* check AddCatcacheInvalidationMessage() for an explanation */
      VALGRIND_MAKE_MEM_DEFINED(&msg, sizeof(msg));

      AddInvalidationMessage(&hdr->cclist, &msg);
--- 392,398 ----
      msg.cat.id = SharedInvalCatalog;
      msg.cat.dbId = dbId;
      msg.cat.catId = catId;
!     /* check AddCatcacheHashInvalidationMessage() for an explanation */
      VALGRIND_MAKE_MEM_DEFINED(&msg, sizeof(msg));

      AddInvalidationMessage(&hdr->cclist, &msg);
*************** AddRelcacheInvalidationMessage(Invalidat
*** 401,407 ****
      msg.rc.id = SharedInvalRelcache;
      msg.rc.dbId = dbId;
      msg.rc.relId = relId;
!     /* check AddCatcacheInvalidationMessage() for an explanation */
      VALGRIND_MAKE_MEM_DEFINED(&msg, sizeof(msg));

      AddInvalidationMessage(&hdr->rclist, &msg);
--- 422,428 ----
      msg.rc.id = SharedInvalRelcache;
      msg.rc.dbId = dbId;
      msg.rc.relId = relId;
!     /* check AddCatcacheHashInvalidationMessage() for an explanation */
      VALGRIND_MAKE_MEM_DEFINED(&msg, sizeof(msg));

      AddInvalidationMessage(&hdr->rclist, &msg);
*************** AddSnapshotInvalidationMessage(Invalidat
*** 427,433 ****
      msg.sn.id = SharedInvalSnapshot;
      msg.sn.dbId = dbId;
      msg.sn.relId = relId;
!     /* check AddCatcacheInvalidationMessage() for an explanation */
      VALGRIND_MAKE_MEM_DEFINED(&msg, sizeof(msg));

      AddInvalidationMessage(&hdr->rclist, &msg);
--- 448,454 ----
      msg.sn.id = SharedInvalSnapshot;
      msg.sn.dbId = dbId;
      msg.sn.relId = relId;
!     /* check AddCatcacheHashInvalidationMessage() for an explanation */
      VALGRIND_MAKE_MEM_DEFINED(&msg, sizeof(msg));

      AddInvalidationMessage(&hdr->rclist, &msg);
*************** ProcessInvalidationMessagesMulti(Invalid
*** 477,493 ****
   */

  /*
!  * RegisterCatcacheInvalidation
   *
!  * Register an invalidation event for a catcache tuple entry.
   */
  static void
! RegisterCatcacheInvalidation(int cacheId,
!                              uint32 hashValue,
!                              Oid dbId)
  {
!     AddCatcacheInvalidationMessage(&transInvalInfo->CurrentCmdInvalidMsgs,
!                                    cacheId, hashValue, dbId);
  }

  /*
--- 498,529 ----
   */

  /*
!  * RegisterCatcacheHashInvalidation
   *
!  * Register an invalidation event for a catcache tuple entry identified
!  * by hash value.
   */
  static void
! RegisterCatcacheHashInvalidation(int cacheId,
!                                  uint32 hashValue,
!                                  Oid dbId)
  {
!     AddCatcacheHashInvalidationMessage(&transInvalInfo->CurrentCmdInvalidMsgs,
!                                        cacheId, hashValue, dbId);
! }
!
! /*
!  * RegisterCatcacheOidInvalidation
!  *
!  * Register an invalidation event for catcache tuple entries having
!  * the specified OID in a particular cache key column.
!  */
! static void
! RegisterCatcacheOidInvalidation(int cacheId,
!                                 int ckey, Oid oid, Oid dbId)
! {
!     AddCatcacheOidInvalidationMessage(&transInvalInfo->CurrentCmdInvalidMsgs,
!                                       cacheId, ckey, oid, dbId);
  }

  /*
*************** LocalExecuteInvalidationMessage(SharedIn
*** 556,569 ****
  {
      switch ((SharedInvalMsgType) msg->id)
      {
!         case SharedInvalCatcache:
!             if (msg->cc.dbId == MyDatabaseId || msg->cc.dbId == InvalidOid)
              {
                  InvalidateCatalogSnapshot();

!                 SysCacheInvalidate(msg->cc.cacheId, msg->cc.hashValue);

!                 CallSyscacheCallbacks(msg->cc.cacheId, msg->cc.hashValue);
              }
              break;
          case SharedInvalCatalog:
--- 592,612 ----
  {
      switch ((SharedInvalMsgType) msg->id)
      {
!         case SharedInvalCatcacheHash:
!             if (msg->cch.dbId == MyDatabaseId || msg->cch.dbId == InvalidOid)
              {
                  InvalidateCatalogSnapshot();

!                 SysCacheInvalidateByHash(msg->cch.cacheId, msg->cch.hashValue);

!                 CallSyscacheCallbacks(msg->cch.cacheId, msg->cch.hashValue);
!             }
!             break;
!         case SharedInvalCatcacheOid:
!             if (msg->cco.dbId == MyDatabaseId || msg->cco.dbId == InvalidOid)
!             {
!                 SysCacheInvalidateByOid(msg->cco.cacheId, msg->cco.ckey,
!                                         msg->cco.oid);
              }
              break;
          case SharedInvalCatalog:
*************** CacheInvalidateHeapTuple(Relation relati
*** 1157,1163 ****
      }
      else
          PrepareToInvalidateCacheTuple(relation, tuple, newtuple,
!                                       RegisterCatcacheInvalidation);

      /*
       * Now, is this tuple one of the primary definers of a relcache entry? See
--- 1200,1206 ----
      }
      else
          PrepareToInvalidateCacheTuple(relation, tuple, newtuple,
!                                       RegisterCatcacheHashInvalidation);

      /*
       * Now, is this tuple one of the primary definers of a relcache entry? See
*************** CacheInvalidateHeapTuple(Relation relati
*** 1217,1222 ****
--- 1260,1286 ----
  }

  /*
+  * CacheInvalidateCatcacheByOid
+  *        Register invalidation of catcache entries referencing a given OID.
+  *
+  * This is used to kill negative catcache entries that are believed to be
+  * no longer useful.  The entries are identified by which cache they are
+  * in, the cache key column to look at, and the target OID.
+  *
+  * Note: we expect caller to know whether the specified cache is on a
+  * shared or local system catalog.  We could ask syscache.c for that info,
+  * but it seems probably not worth the trouble, since this is likely to
+  * have few callers.
+  */
+ void
+ CacheInvalidateCatcacheByOid(int cacheId, bool isshared, int ckey, Oid oid)
+ {
+     Oid            dbId = isshared ? (Oid) 0 : MyDatabaseId;
+
+     RegisterCatcacheOidInvalidation(cacheId, ckey, oid, dbId);
+ }
+
+ /*
   * CacheInvalidateCatalog
   *        Register invalidation of the whole content of a system catalog.
   *
*************** CacheInvalidateSmgr(RelFileNodeBackend r
*** 1359,1365 ****
      msg.sm.backend_hi = rnode.backend >> 16;
      msg.sm.backend_lo = rnode.backend & 0xffff;
      msg.sm.rnode = rnode.node;
!     /* check AddCatcacheInvalidationMessage() for an explanation */
      VALGRIND_MAKE_MEM_DEFINED(&msg, sizeof(msg));

      SendSharedInvalidMessages(&msg, 1);
--- 1423,1429 ----
      msg.sm.backend_hi = rnode.backend >> 16;
      msg.sm.backend_lo = rnode.backend & 0xffff;
      msg.sm.rnode = rnode.node;
!     /* check AddCatcacheHashInvalidationMessage() for an explanation */
      VALGRIND_MAKE_MEM_DEFINED(&msg, sizeof(msg));

      SendSharedInvalidMessages(&msg, 1);
*************** CacheInvalidateRelmap(Oid databaseId)
*** 1387,1393 ****

      msg.rm.id = SharedInvalRelmap;
      msg.rm.dbId = databaseId;
!     /* check AddCatcacheInvalidationMessage() for an explanation */
      VALGRIND_MAKE_MEM_DEFINED(&msg, sizeof(msg));

      SendSharedInvalidMessages(&msg, 1);
--- 1451,1457 ----

      msg.rm.id = SharedInvalRelmap;
      msg.rm.dbId = databaseId;
!     /* check AddCatcacheHashInvalidationMessage() for an explanation */
      VALGRIND_MAKE_MEM_DEFINED(&msg, sizeof(msg));

      SendSharedInvalidMessages(&msg, 1);
diff --git a/src/backend/utils/cache/syscache.c b/src/backend/utils/cache/syscache.c
index ac98c19..3e5acd5 100644
*** a/src/backend/utils/cache/syscache.c
--- b/src/backend/utils/cache/syscache.c
*************** SearchSysCacheList(int cacheId, int nkey
*** 1434,1448 ****
  }

  /*
!  * SysCacheInvalidate
   *
   *    Invalidate entries in the specified cache, given a hash value.
!  *    See CatCacheInvalidate() for more info.
   *
   *    This routine is only quasi-public: it should only be used by inval.c.
   */
  void
! SysCacheInvalidate(int cacheId, uint32 hashValue)
  {
      if (cacheId < 0 || cacheId >= SysCacheSize)
          elog(ERROR, "invalid cache ID: %d", cacheId);
--- 1434,1448 ----
  }

  /*
!  * SysCacheInvalidateByHash
   *
   *    Invalidate entries in the specified cache, given a hash value.
!  *    See CatCacheInvalidateByHash() for more info.
   *
   *    This routine is only quasi-public: it should only be used by inval.c.
   */
  void
! SysCacheInvalidateByHash(int cacheId, uint32 hashValue)
  {
      if (cacheId < 0 || cacheId >= SysCacheSize)
          elog(ERROR, "invalid cache ID: %d", cacheId);
*************** SysCacheInvalidate(int cacheId, uint32 h
*** 1451,1457 ****
      if (!PointerIsValid(SysCache[cacheId]))
          return;

!     CatCacheInvalidate(SysCache[cacheId], hashValue);
  }

  /*
--- 1451,1478 ----
      if (!PointerIsValid(SysCache[cacheId]))
          return;

!     CatCacheInvalidateByHash(SysCache[cacheId], hashValue);
! }
!
! /*
!  * SysCacheInvalidateByOid
!  *
!  *    Invalidate negative entries in the specified cache, given a target OID.
!  *    See CatCacheInvalidateByOid() for more info.
!  *
!  *    This routine is only quasi-public: it should only be used by inval.c.
!  */
! void
! SysCacheInvalidateByOid(int cacheId, int ckey, Oid oid)
! {
!     if (cacheId < 0 || cacheId >= SysCacheSize)
!         elog(ERROR, "invalid cache ID: %d", cacheId);
!
!     /* if this cache isn't initialized yet, no need to do anything */
!     if (!PointerIsValid(SysCache[cacheId]))
!         return;
!
!     CatCacheInvalidateByOid(SysCache[cacheId], ckey, oid);
  }

  /*
diff --git a/src/include/storage/sinval.h b/src/include/storage/sinval.h
index d0d9ece..004cb45 100644
*** a/src/include/storage/sinval.h
--- b/src/include/storage/sinval.h
***************
*** 20,26 ****

  /*
   * We support several types of shared-invalidation messages:
!  *    * invalidate a specific tuple in a specific catcache
   *    * invalidate all catcache entries from a given system catalog
   *    * invalidate a relcache entry for a specific logical relation
   *    * invalidate all relcache entries
--- 20,27 ----

  /*
   * We support several types of shared-invalidation messages:
!  *    * invalidate a specific tuple (identified by hash) in a specific catcache
!  *    * invalidate negative entries matching a given OID in a specific catcache
   *    * invalidate all catcache entries from a given system catalog
   *    * invalidate a relcache entry for a specific logical relation
   *    * invalidate all relcache entries
***************
*** 30,36 ****
   * More types could be added if needed.  The message type is identified by
   * the first "int8" field of the message struct.
   *
!  * Catcache inval events are initially driven by detecting tuple inserts,
   * updates and deletions in system catalogs (see CacheInvalidateHeapTuple).
   * An update can generate two inval events, one for the old tuple and one for
   * the new, but this is reduced to one event if the tuple's hash key doesn't
--- 31,37 ----
   * More types could be added if needed.  The message type is identified by
   * the first "int8" field of the message struct.
   *
!  * Catcache hash inval events are initially driven by detecting tuple inserts,
   * updates and deletions in system catalogs (see CacheInvalidateHeapTuple).
   * An update can generate two inval events, one for the old tuple and one for
   * the new, but this is reduced to one event if the tuple's hash key doesn't
***************
*** 57,63 ****

  typedef enum SharedInvalMsgType
  {
!     SharedInvalCatcache,
      SharedInvalCatalog,
      SharedInvalRelcache,
      SharedInvalSmgr,
--- 58,65 ----

  typedef enum SharedInvalMsgType
  {
!     SharedInvalCatcacheHash,
!     SharedInvalCatcacheOid,
      SharedInvalCatalog,
      SharedInvalRelcache,
      SharedInvalSmgr,
*************** typedef struct
*** 71,77 ****
      int8        cacheId;        /* cache ID */
      Oid            dbId;            /* database ID, or 0 if a shared relation */
      uint32        hashValue;        /* hash value of key for this catcache */
! } SharedInvalCatcacheMsg;

  typedef struct
  {
--- 73,88 ----
      int8        cacheId;        /* cache ID */
      Oid            dbId;            /* database ID, or 0 if a shared relation */
      uint32        hashValue;        /* hash value of key for this catcache */
! } SharedInvalCatcacheHashMsg;
!
! typedef struct
! {
!     int8        id;                /* type field --- must be first */
!     int8        cacheId;        /* cache ID */
!     int8        ckey;            /* cache key column (1..CATCACHE_MAXKEYS) */
!     Oid            oid;            /* OID of cache entries to remove */
!     Oid            dbId;            /* database ID, or 0 if a shared relation */
! } SharedInvalCatcacheOidMsg;

  typedef struct
  {
*************** typedef struct
*** 112,118 ****
  typedef union
  {
      int8        id;                /* type field --- must be first */
!     SharedInvalCatcacheMsg cc;
      SharedInvalCatalogMsg cat;
      SharedInvalRelcacheMsg rc;
      SharedInvalSmgrMsg sm;
--- 123,130 ----
  typedef union
  {
      int8        id;                /* type field --- must be first */
!     SharedInvalCatcacheHashMsg cch;
!     SharedInvalCatcacheOidMsg cco;
      SharedInvalCatalogMsg cat;
      SharedInvalRelcacheMsg rc;
      SharedInvalSmgrMsg sm;
diff --git a/src/include/utils/catcache.h b/src/include/utils/catcache.h
index 65d816a..47b72d6 100644
*** a/src/include/utils/catcache.h
--- b/src/include/utils/catcache.h
*************** extern void ReleaseCatCacheList(CatCList
*** 219,225 ****

  extern void ResetCatalogCaches(void);
  extern void CatalogCacheFlushCatalog(Oid catId);
! extern void CatCacheInvalidate(CatCache *cache, uint32 hashValue);
  extern void PrepareToInvalidateCacheTuple(Relation relation,
                                HeapTuple tuple,
                                HeapTuple newtuple,
--- 219,226 ----

  extern void ResetCatalogCaches(void);
  extern void CatalogCacheFlushCatalog(Oid catId);
! extern void CatCacheInvalidateByHash(CatCache *cache, uint32 hashValue);
! extern void CatCacheInvalidateByOid(CatCache *cache, int ckey, Oid oid);
  extern void PrepareToInvalidateCacheTuple(Relation relation,
                                HeapTuple tuple,
                                HeapTuple newtuple,
diff --git a/src/include/utils/inval.h b/src/include/utils/inval.h
index c557640..d1181bc 100644
*** a/src/include/utils/inval.h
--- b/src/include/utils/inval.h
*************** extern void CacheInvalidateHeapTuple(Rel
*** 39,44 ****
--- 39,47 ----
                           HeapTuple tuple,
                           HeapTuple newtuple);

+ extern void CacheInvalidateCatcacheByOid(int cacheId, bool isshared,
+                              int ckey, Oid oid);
+
  extern void CacheInvalidateCatalog(Oid catalogId);

  extern void CacheInvalidateRelcache(Relation relation);
diff --git a/src/include/utils/syscache.h b/src/include/utils/syscache.h
index 95ee489..983fd00 100644
*** a/src/include/utils/syscache.h
--- b/src/include/utils/syscache.h
*************** struct catclist;
*** 159,165 ****
  extern struct catclist *SearchSysCacheList(int cacheId, int nkeys,
                     Datum key1, Datum key2, Datum key3);

! extern void SysCacheInvalidate(int cacheId, uint32 hashValue);

  extern bool RelationInvalidatesSnapshotsOnly(Oid relid);
  extern bool RelationHasSysCache(Oid relid);
--- 159,166 ----
  extern struct catclist *SearchSysCacheList(int cacheId, int nkeys,
                     Datum key1, Datum key2, Datum key3);

! extern void SysCacheInvalidateByHash(int cacheId, uint32 hashValue);
! extern void SysCacheInvalidateByOid(int cacheId, int ckey, Oid oid);

  extern bool RelationInvalidatesSnapshotsOnly(Oid relid);
  extern bool RelationHasSysCache(Oid relid);