diff options
| author | Tom Lane <tgl@sss.pgh.pa.us> | 2024-03-22 17:13:53 -0400 |
|---|---|---|
| committer | Tom Lane <tgl@sss.pgh.pa.us> | 2024-03-22 17:13:53 -0400 |
| commit | 473182c9523afad10e9507145690d902a0bc7f04 (patch) | |
| tree | e98fcd77f023c1b110c70727ded9e9a7decea443 /src/include/utils/catcache.h | |
| parent | 6acb0a628eccab8764e0306582c2b7e2a1441b9b (diff) | |
Use a hash table for catcache.c's CatCList objects.
Up to now, all of the "catcache list" objects within a catalog cache
were just chained together on a single dlist, requiring O(N) time to
search. Remarkably, we've not had serious performance problems with
that so far; but we got a complaint of a bad performance regression
from v15 in a case with a large number of roles in the system, which
traced down to O(N^2) total time when we probed N catcache lists.
Replace that data structure with a hashtable having an enlargeable
number of dlists, in an exactly parallel way to the data structure
we've used for years for the plain CatCTup cache members. The extra
cost of maintaining a hash table seems negligible, since we were
already computing a hash value for list searches.
Normally this'd be HEAD-only material, but in view of the performance
regression it seems advisable to back-patch into v16. In the v16
version of the patch, leave the dead cc_lists field where it is and
add the new fields at the end of struct catcache, to avoid possible
ABI breakage in case any external code is looking at these structs.
(We assume no external code is actually allocating new catcache
structs.)
Per report from alex work.
Discussion: https://postgr.es/m/CAGvXd3OSMbJQwOSc-Tq-Ro1CAz=vggErdSG7pv2s6vmmTOLJSg@mail.gmail.com
Diffstat (limited to 'src/include/utils/catcache.h')
| -rw-r--r-- | src/include/utils/catcache.h | 6 |
1 files changed, 4 insertions, 2 deletions
diff --git a/src/include/utils/catcache.h b/src/include/utils/catcache.h index a75a528de88..3fb9647b87c 100644 --- a/src/include/utils/catcache.h +++ b/src/include/utils/catcache.h @@ -51,9 +51,11 @@ typedef struct catcache CCFastEqualFN cc_fastequal[CATCACHE_MAXKEYS]; /* fast equal function for * each key */ int cc_keyno[CATCACHE_MAXKEYS]; /* AttrNumber of each key */ - dlist_head cc_lists; /* list of CatCList structs */ - int cc_ntup; /* # of tuples currently in this cache */ int cc_nkeys; /* # of keys (1..CATCACHE_MAXKEYS) */ + int cc_ntup; /* # of tuples currently in this cache */ + int cc_nlist; /* # of CatCLists currently in this cache */ + int cc_nlbuckets; /* # of CatCList hash buckets in this cache */ + dlist_head *cc_lbucket; /* hash buckets for CatCLists */ const char *cc_relname; /* name of relation the tuples come from */ Oid cc_reloid; /* OID of relation the tuples come from */ Oid cc_indexoid; /* OID of index matching cache keys */ |