Caching negative lookup results in typcache.c - Mailing list pgsql-hackers

In the pgsql-performance thread at
http://www.postgresql.org/message-id/flat/CAOR=d=3j1U_q-zf8+jUx1hkx8ps+N8pm=EUTqyFdJ5ov=+fawg@mail.gmail.com
it emerged that a substantial part of the slowdown Scott saw from 8.4 to
9.2 was an unexpected consequence of the fact that the planner now
considers hashing methods for implementing UNION.  That leads to requests
to typcache.c to look up the hash opclass for a UNION'd datatype.
Which is fine, and fast, as long as there is one ... but if there is not,
each request causes a new physical probe into pg_opclass, because
typcache.c is not designed to cache negative results.  Fixing that
results in about a 16% reduction in total query time on Scott's example
(for me, 432 ms to 360 ms, in a cassert-off build).

We learned years ago that it was critical for the catalog caches to
remember negative lookup results, so I'm a bit surprised that it's
taken us this long to realize that typcache.c needs to do it too.

If memory serves, the reason for not caching negative results was the
thought that opclasses might get added to a type over the course of a
session.  However, that's pretty lame logic, because they could also
get dropped over the course of a session, and the existing typcache.c
code utterly fails to cope with that scenario; it could easily result
in attempts to call no-longer-existing operators/functions.

The attached proposed patch adjusts the typcache.c code so that negative
results are cacheable, and adds a syscache invalidation callback so that
all such results are forgotten whenever an update occurs in pg_opclass.
That's sufficient to cover the cases of CREATE/DROP OPERATOR CLASS, which
are the only supported scenarios for altering operator classes.  I think
it is not necessary to watch for pg_amop or pg_amproc updates, because
the supported uses of ALTER OPERATOR FAMILY ADD/DROP OPERATOR/FUNCTION
are for cross-type family members, none of which are cached in typcache.

Comments?

Is it reasonable to think of back-patching this?  I'm inclined to think
that performance is not a sufficient argument for doing that, because the
lossage occurs only for types that have a default btree opclass but no
default hash opclass or vice versa; and that is a fairly short list,
with no heavily-used types involved.  However, failure to honor DROP
OPERATOR CLASS is clearly a bug, and that might be a good argument for
back-patching (though I've not heard any field complaints about it).

            regards, tom lane

diff --git a/src/backend/utils/cache/typcache.c b/src/backend/utils/cache/typcache.c
index 8c6c7fc..9aa9182 100644
*** a/src/backend/utils/cache/typcache.c
--- b/src/backend/utils/cache/typcache.c
***************
*** 17,36 ****
   * is kept in the type cache.
   *
   * Once created, a type cache entry lives as long as the backend does, so
!  * there is no need for a call to release a cache entry.  (For present uses,
   * it would be okay to flush type cache entries at the ends of transactions,
   * if we needed to reclaim space.)
   *
!  * There is presently no provision for clearing out a cache entry if the
!  * stored data becomes obsolete.  (The code will work if a type acquires
!  * opclasses it didn't have before while a backend runs --- but not if the
!  * definition of an existing opclass is altered.)  However, the relcache
!  * doesn't cope with opclasses changing under it, either, so this seems
!  * a low-priority problem.
!  *
!  * We do support clearing the tuple descriptor and operator/function parts
!  * of a rowtype's cache entry, since those may need to change as a consequence
!  * of ALTER TABLE.
   *
   *
   * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
--- 17,32 ----
   * is kept in the type cache.
   *
   * Once created, a type cache entry lives as long as the backend does, so
!  * there is no need for a call to release a cache entry.  If the type is
!  * dropped, the cache entry simply becomes wasted storage.  (For present uses,
   * it would be okay to flush type cache entries at the ends of transactions,
   * if we needed to reclaim space.)
   *
!  * We have some provisions for updating cache entries if the stored data
!  * becomes obsolete.  Information dependent on opclasses is cleared if we
!  * detect updates to pg_opclass.  We also support clearing the tuple
!  * descriptor and operator/function parts of a rowtype's cache entry,
!  * since those may need to change as a consequence of ALTER TABLE.
   *
   *
   * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
*************** static HTAB *TypeCacheHash = NULL;
*** 77,82 ****
--- 73,85 ----
  #define TCFLAGS_CHECKED_FIELD_PROPERTIES    0x0010
  #define TCFLAGS_HAVE_FIELD_EQUALITY            0x0020
  #define TCFLAGS_HAVE_FIELD_COMPARE            0x0040
+ #define TCFLAGS_CHECKED_BTREE_OPCLASS        0x0080
+ #define TCFLAGS_CHECKED_HASH_OPCLASS        0x0100
+ #define TCFLAGS_CHECKED_EQ_OPR                0x0200
+ #define TCFLAGS_CHECKED_LT_OPR                0x0400
+ #define TCFLAGS_CHECKED_GT_OPR                0x0800
+ #define TCFLAGS_CHECKED_CMP_PROC            0x1000
+ #define TCFLAGS_CHECKED_HASH_PROC            0x2000

  /* Private information to support comparisons of enum values */
  typedef struct
*************** static bool record_fields_have_equality(
*** 132,137 ****
--- 135,141 ----
  static bool record_fields_have_compare(TypeCacheEntry *typentry);
  static void cache_record_field_properties(TypeCacheEntry *typentry);
  static void TypeCacheRelCallback(Datum arg, Oid relid);
+ static void TypeCacheOpcCallback(Datum arg, int cacheid, uint32 hashvalue);
  static void load_enum_cache_data(TypeCacheEntry *tcache);
  static EnumItem *find_enumitem(TypeCacheEnumData *enumdata, Oid arg);
  static int    enum_oid_cmp(const void *left, const void *right);
*************** lookup_type_cache(Oid type_id, int flags
*** 166,173 ****
          TypeCacheHash = hash_create("Type information cache", 64,
                                      &ctl, HASH_ELEM | HASH_FUNCTION);

!         /* Also set up a callback for relcache SI invalidations */
          CacheRegisterRelcacheCallback(TypeCacheRelCallback, (Datum) 0);

          /* Also make sure CacheMemoryContext exists */
          if (!CacheMemoryContext)
--- 170,178 ----
          TypeCacheHash = hash_create("Type information cache", 64,
                                      &ctl, HASH_ELEM | HASH_FUNCTION);

!         /* Also set up callbacks for SI invalidations */
          CacheRegisterRelcacheCallback(TypeCacheRelCallback, (Datum) 0);
+         CacheRegisterSyscacheCallback(CLAOID, TypeCacheOpcCallback, (Datum) 0);

          /* Also make sure CacheMemoryContext exists */
          if (!CacheMemoryContext)
*************** lookup_type_cache(Oid type_id, int flags
*** 217,229 ****
      }

      /*
!      * If we haven't already found the opclasses, try to do so
       */
      if ((flags & (TYPECACHE_EQ_OPR | TYPECACHE_LT_OPR | TYPECACHE_GT_OPR |
                    TYPECACHE_CMP_PROC |
                    TYPECACHE_EQ_OPR_FINFO | TYPECACHE_CMP_PROC_FINFO |
                    TYPECACHE_BTREE_OPFAMILY)) &&
!         typentry->btree_opf == InvalidOid)
      {
          Oid            opclass;

--- 222,235 ----
      }

      /*
!      * Look up opclasses if we haven't already and any dependent info is
!      * requested.
       */
      if ((flags & (TYPECACHE_EQ_OPR | TYPECACHE_LT_OPR | TYPECACHE_GT_OPR |
                    TYPECACHE_CMP_PROC |
                    TYPECACHE_EQ_OPR_FINFO | TYPECACHE_CMP_PROC_FINFO |
                    TYPECACHE_BTREE_OPFAMILY)) &&
!         !(typentry->flags & TCFLAGS_CHECKED_BTREE_OPCLASS))
      {
          Oid            opclass;

*************** lookup_type_cache(Oid type_id, int flags
*** 233,270 ****
              typentry->btree_opf = get_opclass_family(opclass);
              typentry->btree_opintype = get_opclass_input_type(opclass);
          }
-         /* If no btree opclass, we force lookup of the hash opclass */
-         if (typentry->btree_opf == InvalidOid)
-         {
-             if (typentry->hash_opf == InvalidOid)
-             {
-                 opclass = GetDefaultOpClass(type_id, HASH_AM_OID);
-                 if (OidIsValid(opclass))
-                 {
-                     typentry->hash_opf = get_opclass_family(opclass);
-                     typentry->hash_opintype = get_opclass_input_type(opclass);
-                 }
-             }
-         }
          else
          {
!             /*
!              * In case we find a btree opclass where previously we only found
!              * a hash opclass, reset eq_opr and derived information so that we
!              * can fetch the btree equality operator instead of the hash
!              * equality operator.  (They're probably the same operator, but we
!              * don't assume that here.)
!              */
!             typentry->eq_opr = InvalidOid;
!             typentry->eq_opr_finfo.fn_oid = InvalidOid;
!             typentry->hash_proc = InvalidOid;
!             typentry->hash_proc_finfo.fn_oid = InvalidOid;
          }
      }

      if ((flags & (TYPECACHE_HASH_PROC | TYPECACHE_HASH_PROC_FINFO |
                    TYPECACHE_HASH_OPFAMILY)) &&
!         typentry->hash_opf == InvalidOid)
      {
          Oid            opclass;

--- 239,274 ----
              typentry->btree_opf = get_opclass_family(opclass);
              typentry->btree_opintype = get_opclass_input_type(opclass);
          }
          else
          {
!             typentry->btree_opf = typentry->btree_opintype = InvalidOid;
          }
+
+         /*
+          * Reset information derived from btree opclass.  Note in particular
+          * that we'll redetermine the eq_opr even if we previously found one;
+          * this matters in case a btree opclass has been added to a type that
+          * previously had only a hash opclass.
+          */
+         typentry->flags &= ~(TCFLAGS_CHECKED_EQ_OPR |
+                              TCFLAGS_CHECKED_LT_OPR |
+                              TCFLAGS_CHECKED_GT_OPR |
+                              TCFLAGS_CHECKED_CMP_PROC);
+         typentry->flags |= TCFLAGS_CHECKED_BTREE_OPCLASS;
      }

+     /*
+      * If we need to look up equality operator, and there's no btree opclass,
+      * force lookup of hash opclass.
+      */
+     if ((flags & (TYPECACHE_EQ_OPR | TYPECACHE_EQ_OPR_FINFO)) &&
+         !(typentry->flags & TCFLAGS_CHECKED_EQ_OPR) &&
+         typentry->btree_opf == InvalidOid)
+         flags |= TYPECACHE_HASH_OPFAMILY;
+
      if ((flags & (TYPECACHE_HASH_PROC | TYPECACHE_HASH_PROC_FINFO |
                    TYPECACHE_HASH_OPFAMILY)) &&
!         !(typentry->flags & TCFLAGS_CHECKED_HASH_OPCLASS))
      {
          Oid            opclass;

*************** lookup_type_cache(Oid type_id, int flags
*** 274,284 ****
              typentry->hash_opf = get_opclass_family(opclass);
              typentry->hash_opintype = get_opclass_input_type(opclass);
          }
      }

!     /* Look for requested operators and functions */
      if ((flags & (TYPECACHE_EQ_OPR | TYPECACHE_EQ_OPR_FINFO)) &&
!         typentry->eq_opr == InvalidOid)
      {
          Oid            eq_opr = InvalidOid;

--- 278,302 ----
              typentry->hash_opf = get_opclass_family(opclass);
              typentry->hash_opintype = get_opclass_input_type(opclass);
          }
+         else
+         {
+             typentry->hash_opf = typentry->hash_opintype = InvalidOid;
+         }
+
+         /*
+          * Reset information derived from hash opclass.  We do *not* reset the
+          * eq_opr; if we already found one from the btree opclass, that
+          * decision is still good.
+          */
+         typentry->flags &= ~(TCFLAGS_CHECKED_HASH_PROC);
+         typentry->flags |= TCFLAGS_CHECKED_HASH_OPCLASS;
      }

!     /*
!      * Look for requested operators and functions, if we haven't already.
!      */
      if ((flags & (TYPECACHE_EQ_OPR | TYPECACHE_EQ_OPR_FINFO)) &&
!         !(typentry->flags & TCFLAGS_CHECKED_EQ_OPR))
      {
          Oid            eq_opr = InvalidOid;

*************** lookup_type_cache(Oid type_id, int flags
*** 310,323 ****
          typentry->eq_opr = eq_opr;

          /*
!          * Reset info about hash function whenever we pick up new info about
!          * equality operator.  This is so we can ensure that the hash function
!          * matches the operator.
           */
!         typentry->hash_proc = InvalidOid;
!         typentry->hash_proc_finfo.fn_oid = InvalidOid;
      }
!     if ((flags & TYPECACHE_LT_OPR) && typentry->lt_opr == InvalidOid)
      {
          Oid            lt_opr = InvalidOid;

--- 328,343 ----
          typentry->eq_opr = eq_opr;

          /*
!          * Reset derived info.  In particular, reset info about hash function
!          * whenever we pick up new info about equality operator.  This is so
!          * we can ensure that the hash function matches the operator.
           */
!         typentry->eq_opr_finfo.fn_oid = InvalidOid;
!         typentry->flags &= ~(TCFLAGS_CHECKED_HASH_PROC);
!         typentry->flags |= TCFLAGS_CHECKED_EQ_OPR;
      }
!     if ((flags & TYPECACHE_LT_OPR) &&
!         !(typentry->flags & TCFLAGS_CHECKED_LT_OPR))
      {
          Oid            lt_opr = InvalidOid;

*************** lookup_type_cache(Oid type_id, int flags
*** 336,343 ****
              lt_opr = InvalidOid;

          typentry->lt_opr = lt_opr;
      }
!     if ((flags & TYPECACHE_GT_OPR) && typentry->gt_opr == InvalidOid)
      {
          Oid            gt_opr = InvalidOid;

--- 356,365 ----
              lt_opr = InvalidOid;

          typentry->lt_opr = lt_opr;
+         typentry->flags |= TCFLAGS_CHECKED_LT_OPR;
      }
!     if ((flags & TYPECACHE_GT_OPR) &&
!         !(typentry->flags & TCFLAGS_CHECKED_GT_OPR))
      {
          Oid            gt_opr = InvalidOid;

*************** lookup_type_cache(Oid type_id, int flags
*** 356,364 ****
              gt_opr = InvalidOid;

          typentry->gt_opr = gt_opr;
      }
      if ((flags & (TYPECACHE_CMP_PROC | TYPECACHE_CMP_PROC_FINFO)) &&
!         typentry->cmp_proc == InvalidOid)
      {
          Oid            cmp_proc = InvalidOid;

--- 378,387 ----
              gt_opr = InvalidOid;

          typentry->gt_opr = gt_opr;
+         typentry->flags |= TCFLAGS_CHECKED_GT_OPR;
      }
      if ((flags & (TYPECACHE_CMP_PROC | TYPECACHE_CMP_PROC_FINFO)) &&
!         !(typentry->flags & TCFLAGS_CHECKED_CMP_PROC))
      {
          Oid            cmp_proc = InvalidOid;

*************** lookup_type_cache(Oid type_id, int flags
*** 377,385 ****
              cmp_proc = InvalidOid;

          typentry->cmp_proc = cmp_proc;
      }
      if ((flags & (TYPECACHE_HASH_PROC | TYPECACHE_HASH_PROC_FINFO)) &&
!         typentry->hash_proc == InvalidOid)
      {
          Oid            hash_proc = InvalidOid;

--- 400,410 ----
              cmp_proc = InvalidOid;

          typentry->cmp_proc = cmp_proc;
+         typentry->cmp_proc_finfo.fn_oid = InvalidOid;
+         typentry->flags |= TCFLAGS_CHECKED_CMP_PROC;
      }
      if ((flags & (TYPECACHE_HASH_PROC | TYPECACHE_HASH_PROC_FINFO)) &&
!         !(typentry->flags & TCFLAGS_CHECKED_HASH_PROC))
      {
          Oid            hash_proc = InvalidOid;

*************** lookup_type_cache(Oid type_id, int flags
*** 408,413 ****
--- 433,440 ----
              hash_proc = InvalidOid;

          typentry->hash_proc = hash_proc;
+         typentry->hash_proc_finfo.fn_oid = InvalidOid;
+         typentry->flags |= TCFLAGS_CHECKED_HASH_PROC;
      }

      /*
*************** TypeCacheRelCallback(Datum arg, Oid reli
*** 928,942 ****
              typentry->tupDesc = NULL;
          }

!         /* Reset equality/comparison/hashing information */
!         typentry->eq_opr = InvalidOid;
!         typentry->lt_opr = InvalidOid;
!         typentry->gt_opr = InvalidOid;
!         typentry->cmp_proc = InvalidOid;
!         typentry->hash_proc = InvalidOid;
!         typentry->eq_opr_finfo.fn_oid = InvalidOid;
!         typentry->cmp_proc_finfo.fn_oid = InvalidOid;
!         typentry->hash_proc_finfo.fn_oid = InvalidOid;
          typentry->flags = 0;
      }
  }
--- 955,992 ----
              typentry->tupDesc = NULL;
          }

!         /* Reset equality/comparison/hashing validity information */
!         typentry->flags = 0;
!     }
! }
!
! /*
!  * TypeCacheOpcCallback
!  *        Syscache inval callback function
!  *
!  * This is called when a syscache invalidation event occurs for any pg_opclass
!  * row.  In principle we could probably just invalidate data dependent on the
!  * particular opclass, but since updates on pg_opclass are rare in production
!  * it doesn't seem worth a lot of complication: we just mark all cached data
!  * invalid.
!  *
!  * Note that we don't bother watching for updates on pg_amop or pg_amproc.
!  * This should be safe because ALTER OPERATOR FAMILY ADD/DROP OPERATOR/FUNCTION
!  * is not allowed to be used to add/drop the primary operators and functions
!  * of an opclass, only cross-type members of a family; and the latter sorts
!  * of members are not going to get cached here.
!  */
! static void
! TypeCacheOpcCallback(Datum arg, int cacheid, uint32 hashvalue)
! {
!     HASH_SEQ_STATUS status;
!     TypeCacheEntry *typentry;
!
!     /* TypeCacheHash must exist, else this callback wouldn't be registered */
!     hash_seq_init(&status, TypeCacheHash);
!     while ((typentry = (TypeCacheEntry *) hash_seq_search(&status)) != NULL)
!     {
!         /* Reset equality/comparison/hashing validity information */
          typentry->flags = 0;
      }
  }