From: Tom Lane <tgl@sss.pgh.pa.us>
To: pgsql-hackers@lists.postgresql.org
cc: alex work <alexwork033@gmail.com>, Robert Haas <robertmhaas@gmail.com>
Subject: Re: Slow GRANT ROLE on PostgreSQL 16 with thousands of ROLEs
In-reply-to: <341186.1711037256@sss.pgh.pa.us>
References: <CAGvXd3OSMbJQwOSc-Tq-Ro1CAz=vggErdSG7pv2s6vmmTOLJSg@mail.gmail.com> <341186.1711037256@sss.pgh.pa.us>
Comments: In-reply-to Tom Lane <tgl@sss.pgh.pa.us>
	message dated "Thu, 21 Mar 2024 12:07:36 -0400"
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0"
Content-ID: <618633.1711050091.0@sss.pgh.pa.us>
Date: Thu, 21 Mar 2024 15:42:14 -0400
Message-ID: <619340.1711050134@sss.pgh.pa.us>
Archived-At: <https://www.postgresql.org/message-id/619340.1711050134%40sss.pgh.pa.us>
Precedence: bulk

------- =_aaaaaaaaaa0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <618633.1711050091.1@sss.pgh.pa.us>

I wrote:
> It looks like part of the blame might be ascribable to catcache.c,
> as if you look at the problem microscopically you find that
> roles_is_member_of is causing catcache to make a ton of AUTHMEMMEMROLE
> catcache lists, and SearchSysCacheList is just iterating linearly
> through the cache's list-of-lists, so that search is where the O(N^2)
> time is actually getting taken.  Up to now that code has assumed that
> any one catcache would not have very many catcache lists.  Maybe it's
> time to make that smarter; but since we've gotten away with this
> implementation for decades, I can't help feeling that the real issue
> is with roles_is_member_of's usage pattern.

I wrote a quick finger exercise to make catcache.c use a hash table
instead of a single list for CatCLists, modeling it closely on the
existing hash logic for simple catcache entries.  This helps a good
deal, but I still see the problematic GRANT taking ~250ms, compared
to 5ms in v15.  roles_is_member_of is clearly on the hook for that.

			regards, tom lane


------- =_aaaaaaaaaa0
Content-Type: text/x-diff; name="v1-use-hash-table-for-CatCLists.patch";
	charset="us-ascii"
Content-ID: <618633.1711050091.2@sss.pgh.pa.us>
Content-Description: v1-use-hash-table-for-CatCLists.patch
Content-Transfer-Encoding: quoted-printable

diff --git a/src/backend/utils/cache/catcache.c b/src/backend/utils/cache/=
catcache.c
index d5a3c1b591..569f51cb33 100644
--- a/src/backend/utils/cache/catcache.c
+++ b/src/backend/utils/cache/catcache.c
@@ -88,6 +88,8 @@ static void CatCachePrintStats(int code, Datum arg);
 #endif
 static void CatCacheRemoveCTup(CatCache *cache, CatCTup *ct);
 static void CatCacheRemoveCList(CatCache *cache, CatCList *cl);
+static void RehashCatCache(CatCache *cp);
+static void RehashCatCacheLists(CatCache *cp);
 static void CatalogCacheInitializeCache(CatCache *cache);
 static CatCTup *CatalogCacheCreateEntry(CatCache *cache,
 										HeapTuple ntp, SysScanDesc scandesc,
@@ -444,6 +446,7 @@ CatCachePrintStats(int code, Datum arg)
 	long		cc_neg_hits =3D 0;
 	long		cc_newloads =3D 0;
 	long		cc_invals =3D 0;
+	long		cc_nlists =3D 0;
 	long		cc_lsearches =3D 0;
 	long		cc_lhits =3D 0;
 =

@@ -453,7 +456,7 @@ CatCachePrintStats(int code, Datum arg)
 =

 		if (cache->cc_ntup =3D=3D 0 && cache->cc_searches =3D=3D 0)
 			continue;			/* don't print unused caches */
-		elog(DEBUG2, "catcache %s/%u: %d tup, %ld srch, %ld+%ld=3D%ld hits, %ld=
+%ld=3D%ld loads, %ld invals, %ld lsrch, %ld lhits",
+		elog(DEBUG2, "catcache %s/%u: %d tup, %ld srch, %ld+%ld=3D%ld hits, %ld=
+%ld=3D%ld loads, %ld invals, %d lists, %ld lsrch, %ld lhits",
 			 cache->cc_relname,
 			 cache->cc_indexoid,
 			 cache->cc_ntup,
@@ -465,6 +468,7 @@ CatCachePrintStats(int code, Datum arg)
 			 cache->cc_searches - cache->cc_hits - cache->cc_neg_hits - cache->cc_=
newloads,
 			 cache->cc_searches - cache->cc_hits - cache->cc_neg_hits,
 			 cache->cc_invals,
+			 cache->cc_nlist,
 			 cache->cc_lsearches,
 			 cache->cc_lhits);
 		cc_searches +=3D cache->cc_searches;
@@ -472,10 +476,11 @@ CatCachePrintStats(int code, Datum arg)
 		cc_neg_hits +=3D cache->cc_neg_hits;
 		cc_newloads +=3D cache->cc_newloads;
 		cc_invals +=3D cache->cc_invals;
+		cc_nlists +=3D cache->cc_nlist;
 		cc_lsearches +=3D cache->cc_lsearches;
 		cc_lhits +=3D cache->cc_lhits;
 	}
-	elog(DEBUG2, "catcache totals: %d tup, %ld srch, %ld+%ld=3D%ld hits, %ld=
+%ld=3D%ld loads, %ld invals, %ld lsrch, %ld lhits",
+	elog(DEBUG2, "catcache totals: %d tup, %ld srch, %ld+%ld=3D%ld hits, %ld=
+%ld=3D%ld loads, %ld invals, %ld lists, %ld lsrch, %ld lhits",
 		 CacheHdr->ch_ntup,
 		 cc_searches,
 		 cc_hits,
@@ -485,6 +490,7 @@ CatCachePrintStats(int code, Datum arg)
 		 cc_searches - cc_hits - cc_neg_hits - cc_newloads,
 		 cc_searches - cc_hits - cc_neg_hits,
 		 cc_invals,
+		 cc_nlists,
 		 cc_lsearches,
 		 cc_lhits);
 }
@@ -573,6 +579,8 @@ CatCacheRemoveCList(CatCache *cache, CatCList *cl)
 					 cache->cc_keyno, cl->keys);
 =

 	pfree(cl);
+
+	--cache->cc_nlist;
 }
 =

 =

@@ -611,14 +619,19 @@ CatCacheInvalidate(CatCache *cache, uint32 hashValue=
)
 	 * Invalidate *all* CatCLists in this cache; it's too hard to tell which
 	 * searches might still be correct, so just zap 'em all.
 	 */
-	dlist_foreach_modify(iter, &cache->cc_lists)
+	for (int i =3D 0; i < cache->cc_nlbuckets; i++)
 	{
-		CatCList   *cl =3D dlist_container(CatCList, cache_elem, iter.cur);
+		dlist_head *bucket =3D &cache->cc_lbucket[i];
 =

-		if (cl->refcount > 0)
-			cl->dead =3D true;
-		else
-			CatCacheRemoveCList(cache, cl);
+		dlist_foreach_modify(iter, bucket)
+		{
+			CatCList   *cl =3D dlist_container(CatCList, cache_elem, iter.cur);
+
+			if (cl->refcount > 0)
+				cl->dead =3D true;
+			else
+				CatCacheRemoveCList(cache, cl);
+		}
 	}
 =

 	/*
@@ -691,14 +704,19 @@ ResetCatalogCache(CatCache *cache)
 	int			i;
 =

 	/* Remove each list in this cache, or at least mark it dead */
-	dlist_foreach_modify(iter, &cache->cc_lists)
+	for (i =3D 0; i < cache->cc_nlbuckets; i++)
 	{
-		CatCList   *cl =3D dlist_container(CatCList, cache_elem, iter.cur);
+		dlist_head *bucket =3D &cache->cc_lbucket[i];
 =

-		if (cl->refcount > 0)
-			cl->dead =3D true;
-		else
-			CatCacheRemoveCList(cache, cl);
+		dlist_foreach_modify(iter, bucket)
+		{
+			CatCList   *cl =3D dlist_container(CatCList, cache_elem, iter.cur);
+
+			if (cl->refcount > 0)
+				cl->dead =3D true;
+			else
+				CatCacheRemoveCList(cache, cl);
+		}
 	}
 =

 	/* Remove each tuple in this cache, or at least mark it dead */
@@ -862,6 +880,12 @@ InitCatCache(int id,
 									 MCXT_ALLOC_ZERO);
 	cp->cc_bucket =3D palloc0(nbuckets * sizeof(dlist_head));
 =

+	/*
+	 * Many catcaches never receive any list searches.  Therefore, we don't
+	 * allocate the cc_lbuckets till we get a list search.
+	 */
+	cp->cc_lbucket =3D NULL;
+
 	/*
 	 * initialize the cache's relation information for the relation
 	 * corresponding to this cache, and initialize some of the new cache's
@@ -874,7 +898,9 @@ InitCatCache(int id,
 	cp->cc_relisshared =3D false; /* temporary */
 	cp->cc_tupdesc =3D (TupleDesc) NULL;
 	cp->cc_ntup =3D 0;
+	cp->cc_nlist =3D 0;
 	cp->cc_nbuckets =3D nbuckets;
+	cp->cc_nlbuckets =3D 0;
 	cp->cc_nkeys =3D nkeys;
 	for (i =3D 0; i < nkeys; ++i)
 	{
@@ -939,6 +965,44 @@ RehashCatCache(CatCache *cp)
 	cp->cc_bucket =3D newbucket;
 }
 =

+/*
+ * Enlarge a catcache's list storage, doubling the number of buckets.
+ */
+static void
+RehashCatCacheLists(CatCache *cp)
+{
+	dlist_head *newbucket;
+	int			newnbuckets;
+	int			i;
+
+	elog(DEBUG1, "rehashing catalog cache id %d for %s; %d lists, %d buckets=
",
+		 cp->id, cp->cc_relname, cp->cc_nlist, cp->cc_nlbuckets);
+
+	/* Allocate a new, larger, hash table. */
+	newnbuckets =3D cp->cc_nlbuckets * 2;
+	newbucket =3D (dlist_head *) MemoryContextAllocZero(CacheMemoryContext, =
newnbuckets * sizeof(dlist_head));
+
+	/* Move all entries from old hash table to new. */
+	for (i =3D 0; i < cp->cc_nlbuckets; i++)
+	{
+		dlist_mutable_iter iter;
+
+		dlist_foreach_modify(iter, &cp->cc_lbucket[i])
+		{
+			CatCList   *cl =3D dlist_container(CatCList, cache_elem, iter.cur);
+			int			hashIndex =3D HASH_INDEX(cl->hash_value, newnbuckets);
+
+			dlist_delete(iter.cur);
+			dlist_push_head(&newbucket[hashIndex], &cl->cache_elem);
+		}
+	}
+
+	/* Switch to the new array. */
+	pfree(cp->cc_lbucket);
+	cp->cc_nlbuckets =3D newnbuckets;
+	cp->cc_lbucket =3D newbucket;
+}
+
 /*
  *		CatalogCacheInitializeCache
  *
@@ -1588,7 +1652,9 @@ SearchCatCacheList(CatCache *cache,
 	Datum		v4 =3D 0;			/* dummy last-column value */
 	Datum		arguments[CATCACHE_MAXKEYS];
 	uint32		lHashValue;
+	Index		lHashIndex;
 	dlist_iter	iter;
+	dlist_head *lbucket;
 	CatCList   *cl;
 	CatCTup    *ct;
 	List	   *volatile ctlist;
@@ -1602,7 +1668,7 @@ SearchCatCacheList(CatCache *cache,
 	/*
 	 * one-time startup overhead for each cache
 	 */
-	if (cache->cc_tupdesc =3D=3D NULL)
+	if (unlikely(cache->cc_tupdesc =3D=3D NULL))
 		CatalogCacheInitializeCache(cache);
 =

 	Assert(nkeys > 0 && nkeys < cache->cc_nkeys);
@@ -1618,11 +1684,36 @@ SearchCatCacheList(CatCache *cache,
 	arguments[3] =3D v4;
 =

 	/*
-	 * compute a hash value of the given keys for faster search.  We don't
-	 * presently divide the CatCList items into buckets, but this still lets
-	 * us skip non-matching items quickly most of the time.
+	 * If we haven't previously done a list search in this cache, create the
+	 * bucket header array; otherwise, consider whether it's time to enlarge
+	 * it.
+	 */
+	if (cache->cc_lbucket =3D=3D NULL)
+	{
+		/* Arbitrary initial size --- must be a power of 2 */
+		int			nbuckets =3D 16;
+
+		cache->cc_lbucket =3D (dlist_head *)
+			MemoryContextAllocZero(CacheMemoryContext,
+								   nbuckets * sizeof(dlist_head));
+		/* Don't set cc_nlbuckets if we get OOM allocating cc_lbucket */
+		cache->cc_nlbuckets =3D nbuckets;
+	}
+	else
+	{
+		/*
+		 * If the hash table has become too full, enlarge the buckets array.
+		 * Quite arbitrarily, we enlarge when fill factor > 2.
+		 */
+		if (cache->cc_nlist > cache->cc_nlbuckets * 2)
+			RehashCatCacheLists(cache);
+	}
+
+	/*
+	 * Find the hash bucket in which to look for the CatCList.
 	 */
 	lHashValue =3D CatalogCacheComputeHashValue(cache, nkeys, v1, v2, v3, v4=
);
+	lHashIndex =3D HASH_INDEX(lHashValue, cache->cc_nlbuckets);
 =

 	/*
 	 * scan the items until we find a match or exhaust our list
@@ -1630,7 +1721,8 @@ SearchCatCacheList(CatCache *cache,
 	 * Note: it's okay to use dlist_foreach here, even though we modify the
 	 * dlist within the loop, because we don't continue the loop afterwards.
 	 */
-	dlist_foreach(iter, &cache->cc_lists)
+	lbucket =3D &cache->cc_lbucket[lHashIndex];
+	dlist_foreach(iter, lbucket)
 	{
 		cl =3D dlist_container(CatCList, cache_elem, iter.cur);
 =

@@ -1650,13 +1742,13 @@ SearchCatCacheList(CatCache *cache,
 			continue;
 =

 		/*
-		 * We found a matching list.  Move the list to the front of the
-		 * cache's list-of-lists, to speed subsequent searches.  (We do not
+		 * We found a matching list.  Move the list to the front of the list
+		 * for its hashbucket, so as to speed subsequent searches.  (We do not
 		 * move the members to the fronts of their hashbucket lists, however,
 		 * since there's no point in that unless they are searched for
 		 * individually.)
 		 */
-		dlist_move_head(&cache->cc_lists, &cl->cache_elem);
+		dlist_move_head(lbucket, &cl->cache_elem);
 =

 		/* Bump the list's refcount and return it */
 		ResourceOwnerEnlarge(CurrentResourceOwner);
@@ -1868,7 +1960,12 @@ SearchCatCacheList(CatCache *cache,
 	}
 	Assert(i =3D=3D nmembers);
 =

-	dlist_push_head(&cache->cc_lists, &cl->cache_elem);
+	/*
+	 * Add the CatCList to the appropriate bucket, and count it.
+	 */
+	dlist_push_head(lbucket, &cl->cache_elem);
+
+	cache->cc_nlist++;
 =

 	/* Finally, bump the list's refcount and return it */
 	cl->refcount++;
diff --git a/src/include/utils/catcache.h b/src/include/utils/catcache.h
index a75a528de8..3fb9647b87 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 */

------- =_aaaaaaaaaa0--