Subject: Slow GRANT ROLE on PostgreSQL 16 with thousands of ROLEs

From: alex work <[email-masked]>
Date: Thu, 21 Mar 2024 14:10:06 +0700

Hello,

we run multiple versions of PostgreSQL instances on production. Some time ago
we add new physical servers and decided to go with latest GA from pgdg APT
repository, that is PostgreSQL 16.

We encounter slow `GRANT ROLES` only on PostgreSQL 16 instances up to 42 seconds
in production, the client process at PostgresSQL would use 100% of the CPU.
Which is a surprise compared to other instances running older PostgreSQL
releases. On production we have a *LOT* of ROLEs, which unfortunately a case
that we did not test before switching the new servers into production mode.

The Application & ROLEs
-----------------------
Our application make use of ROLEs. We create group ROLEs for each tenant of our
application, these ROLEs are named with `d_` and `a_` prefix.

A special ROLE, called `acc`, it will be a member to each of these `d_` and
`a_` ROLEs.

The application have a concept of "session", which it would mantain and I think
outside the scope of this e-mail. In relation to PostgreSQL, the application
would create a PostgreSQL ROLE that corresponds to its own (application)
session. It would name these ROLEs with `s_` prefix, which CREATEd and
GRANTed its permission on every application's "session".

When an application "session" started, user with `acc` ROLE would grant
membersip of `d_` ROLE to `s_` ROLE (ie. GRANT ROLE `d_xxxx` TO `s_xxxx`;)

To make this clear, for example, we have (say) role `d_202402` already existing
and application would create a new ROLE `s_0000001` which corresponds to
application's "session". Application that connects with special ROLE `acc`
would GRANT ROLE `d_202402` to the ROLE `s_0000001`, like so:

GRANT d_202402 TO s_0000001;

In production we have up to 13 thousands of these ROLEs, each:

$ sudo -u postgres psql -p 5531
psql (16.2 (Debian 16.2-1.pgdg120+2))
Type "help" for help.

postgres=# select count(*) s_roles_count from pg_catalog.pg_authid
where rolname like 's_%';
s_roles_count
---------------
13299
(1 row)

postgres=# select count(*) a_roles_count from pg_catalog.pg_authid
where rolname like 'a_%';
a_roles_count
---------------
12776
(1 row)

postgres=# select count(*) d_roles_count from pg_catalog.pg_authid
where rolname like 'd_%';
d_roles_count
---------------
13984
(1 row)

The Setup
---------

Investigating this slow `GRANT ROLE` we start a VM running Debian 11,
and create a lot of roles.

create special `acc` role and write to some file:
$ echo -e "CREATE ROLE acc WITH LOGIN NOSUPERUSER INHERIT CREATEDB
CREATEROLE NOREPLICATION;\n\n" > create_acc.sql

create a lot of `a_` roles and make sure `acc` is member of each one of them:
$ for idx1 in $(seq -w 1 100); do for idx2 in $(seq -w 1 12); do for
idx3 in $(seq -w 1 10); do echo "CREATE ROLE a_${idx1}${idx2}${idx3}
WITH NOSUPERUSER NOCREATEDB NOCREATEROLE INHERIT LOGIN;"; echo "GRANT
a_${idx1}${idx2}${idx3} TO acc WITH ADMIN OPTION;"; done; done; done >
create_a.sql

create a lot of `d_` roles and make sure `acc` is member of each one of them:
$ for idx1 in $(seq -w 1 100); do for idx2 in $(seq -w 1 12); do for
idx3 in $(seq -w 1 10); do echo "CREATE ROLE d_${idx1}${idx2}${idx3}
WITH NOSUPERUSER NOCREATEDB NOCREATEROLE INHERIT LOGIN;"; echo "GRANT
d_${idx1}${idx2}${idx3} TO acc WITH ADMIN OPTION;"; done; done; done >
create_d.sql

create a lot of `s_` roles:
$ for idx1 in $(seq -w 1 100); do for idx2 in $(seq -w 1 12); do for
idx3 in $(seq -w 1 10); do echo "CREATE ROLE s_${idx1}${idx2}${idx3}
WITH NOSUPERUSER NOCREATEDB NOCREATEROLE INHERIT LOGIN;"; done; done;
done > create_s.sql

merge ROLE creation into one file:
$ cat create_acc.sql create_a.sql create_d.sql create_s.sql >
/tmp/create-roles.sql

PostgreSQL 16
-------------

Install PostgreSQL 16:
--
$ sudo sh -c 'echo "deb https://apt.postgresql.org/pub/repos/apt
$(lsb_release -cs)-pgdg main" > /etc/apt/sources.list.d/pgdg.list'
$ sudo apt install gnupg2
$ wget --quiet -O - https://www.postgresql.org/media/keys/ACCC4CF8.asc
| sudo apt-key add -
$ sudo apt-get update
$ sudo apt-get -y install postgresql-16 postgresql-client-16

Create PostgreSQL 16 instance:
--
$ sudo pg_dropcluster --stop 16 main  # drop default Debian cluster
$ sudo pg_createcluster 16 pg16
$ echo "local   all        acc                 trust" | sudo tee
/etc/postgresql/16/pg16/pg_hba.conf
$ echo "local   all        postgres            peer"  | sudo tee -a
/etc/postgresql/16/pg16/pg_hba.conf
$ sudo systemctl start [email-masked]

Import lots of roles:
--
$ sudo -u postgres /usr/lib/postgresql/16/bin/psql -f
/tmp/create-roles.sql -p 5432 -d postgres

Using ROLE `acc`, grant `d_` ROLE to a session ROLE:
--
$ time sudo -u postgres /usr/lib/postgresql/16/bin/psql -U acc
postgres -c 'GRANT d_0010109 TO s_0010109;'
GRANT ROLE

real    0m7.579s
user    0m0.054s
sys     0m0.020s

This is the surprising behavior for PostgreSQL 16. It seems there's a new logic
in PostgreSQL that checks against each role, and it took 100% of CPU.

At this point we know `acc` is just another ROLE that happens to have ADMIN
privilege that is a member of `d_0010109` group ROLE.

But what happens when `acc` is a SUPERUSER?

Alter role `acc` as SUPERUSER:
--
$ sudo -u postgres /usr/lib/postgresql/16/bin/psql -c 'ALTER ROLE acc
WITH SUPERUSER'
ALTER ROLE

This is a workaround to make GRANT ROLE bearable.

Using ROLE `acc`, grant `d_` ROLE to a session ROLE, again:
--
$ time sudo -u postgres /usr/lib/postgresql/16/bin/psql -U acc
postgres -c 'GRANT d_0010108 TO s_0010108;'
GRANT ROLE

real    0m0.079s
user    0m0.054s
sys     0m0.019s

OK this is fast.

But what hapens when `acc` is back being not a SUPERUSER?

Alter role `acc` to stop being SUPERUSER:
--
$ sudo -u postgres psql -c 'ALTER ROLE acc WITH NOSUPERUSER'
ALTER ROLE

Using ROLE `acc`, grant `d_` ROLE to a session ROLE with `acc` not a SUPERUSER:
--
$ time sudo -u postgres /usr/lib/postgresql/16/bin/psql -U acc
postgres -c 'GRANT d_0010107 TO s_0010107;'
GRANT ROLE

real    0m7.741s
user    0m0.055s
sys     0m0.021s

As expected, slow `GRANT ROLE` again.

At this point, we try with PostgreSQL 15 just to make sure that this
is new to PostgreSQL 16.

$ sudo systemctl stop postgresql@16-pg16

PostgreSQL 15
-------------

Install PostgreSQL 15:
--
$ sudo apt-get update
$ sudo apt-get -y install postgresql-15 postgresql-client-15

$ sudo pg_dropcluster --stop 15 main  # drop default Debian cluster
$ sudo pg_createcluster 15 pg15
$ echo "local   all        acc                 trust" | sudo tee
/etc/postgresql/15/pg15/pg_hba.conf
$ echo "local   all        postgres            peer"  | sudo tee -a
/etc/postgresql/15/pg15/pg_hba.conf
$ sudo systemctl start [email-masked]

Import lots of roles:
--
$ sudo -u postgres /usr/lib/postgresql/15/bin/psql -f
/tmp/create-roles.sql -p 5433 -d postgres

Using ROLE `acc`, grant `d_` ROLE to a session ROLE:
--
$ time sudo -u postgres /usr/lib/postgresql/15/bin/psql -U acc -p 5433
postgres -c 'GRANT d_0010109 TO s_0010109;'
GRANT ROLE

real    0m0.077s
user    0m0.054s
sys     0m0.017s

Seems OK with the same amount of ROLEs. The `acc` ROLE is not a SUPERUSER here.

Alter role `acc` as SUPERUSER:
--
$ sudo -u postgres /usr/lib/postgresql/15/bin/psql -p 5433 -c 'ALTER
ROLE acc WITH SUPERUSER'
ALTER ROLE

Using ROLE `acc`, grant `d_` ROLE to a session ROLE, again:
--
$ time sudo -u postgres /usr/lib/postgresql/15/bin/psql -p 5433 -U acc
postgres -c 'GRANT d_0010108 TO s_0010108;'
GRANT ROLE

real    0m0.084s
user    0m0.057s
sys     0m0.021s

Doesn't matter, GRANT ROLE works still as fast.

Alter role `acc` to stop being a SUPERUSER:
--
$ sudo -u postgres /usr/lib/postgresql/15/bin/psql -p 5433 -c 'ALTER
ROLE acc WITH NOSUPERUSER'
ALTER ROLE

Using ROLE `acc`, grant `d_` ROLE to a session ROLE with `acc` not a SUPERUSER:
--
$ time sudo -u postgres /usr/lib/postgresql/15/bin/psql -p 5433 -U acc
postgres -c 'GRANT d_0010107 TO s_0010107;'
GRANT ROLE

real    0m0.077s
user    0m0.054s
sys     0m0.017s

Again, doesn't matter, GRANT ROLE works still as fast.

Looking At The Source Code
--------------------------

Looking at git diff of `REL_15_6` against `REL_16_0`, it seems the
`roles_is_member_of` function called by the new in PostgreSQL 16
`check_role_membership_authorization`
is expensive for our use case.

    REL_16_0: src/backend/commands/user.c:1562
    ---8<------
(errcode(ERRCODE_INVALID_GRANT_OPERATION),
errmsg("column names cannot be included in GRANT/REVOKE ROLE")));

roleid = get_role_oid(rolename, false);
check_role_membership_authorization(currentUserId,
roleid, stmt->is_grant);
if (stmt->is_grant)
    --->8------

While I can see the value in improvements on how ROLEs are being handled
PostgreSQL 16 onward, I'm curious what would help for setups that has thousands
of ROLEs like us outside of patching the source code?

---

From: Dominique Devienne <[email-masked]>
Date: Thu, 21 Mar 2024 08:59:29 +0100

On Thu, Mar 21, 2024 at 8:10 AM alex work <[email-masked]> wrote:

> in production, the client process at PostgresSQL would use 100% of the
> CPU. [...]
>
Using ROLE `acc`, grant `d_` ROLE to a session ROLE:
> real    0m7.579s [...]

PostgreSQL 15
> Using ROLE `acc`, grant `d_` ROLE to a session ROLE:

Ouch, that's a ~ 100x regression. Thanks for the write-up, that's worrying.
We don't have as many ROLEs, but we do have plenty, so this is worrying.

On top of the v16 ROLE changes breaking on ROLE logic, which was fine prior
(v12-v15).
We've paused for now our planned v16 upgrade, until we have more time to
adapt.

Like you, I welcome the changes. But it turns out more expensive to adapt
to them.
And your report certainly makes me wonder whether we should hold off until
that perf regression is addressed.

Thanks, --DD

---

From: Tom Lane <[email-masked]>
Date: Thu, 21 Mar 2024 12:07:36 -0400

[ redirecting to -hackers ]

> that we did not test before switching the new servers into production mode.

I poked into this a bit.  It seems the problem is that as of v16, we
try to search for the "best" role membership path from the current
user to the target role, and that's done in a very brute-force way,
as a side effect of computing the set of *all* role memberships the
current role has.  In the given case, we could have skipped all that
if we simply tested whether the current role is directly a member
of the target: it is, so there can't be any shorter path.  But in
any case roles_is_member_of has horrid performance when the current
role is a member of a lot of roles.

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.

For self-containedness, attached is a directly usable shell script
to reproduce the problem.  The complaint is that the last GRANT
takes multiple seconds (about 5s on my machine), rather than
milliseconds.

			regards, tom lane

#!/bin/bash

echo "CREATE ROLE acc WITH LOGIN NOSUPERUSER INHERIT CREATEDB CREATEROLE NOREPLICATION;" > create-roles.sql

#create a lot of `a_` roles and make sure `acc` is member of each one of them:
for idx1 in $(seq -w 1 100); do for idx2 in $(seq -w 1 12); do for idx3 in $(seq -w 1 10); do
 echo "CREATE ROLE a_${idx1}${idx2}${idx3} WITH NOSUPERUSER NOCREATEDB NOCREATEROLE INHERIT LOGIN;"
 echo "GRANT a_${idx1}${idx2}${idx3} TO acc WITH ADMIN OPTION;"
done; done; done >>create-roles.sql

#create a lot of `d_` roles and make sure `acc` is member of each one of them:
for idx1 in $(seq -w 1 100); do for idx2 in $(seq -w 1 12); do for idx3 in $(seq -w 1 10); do
 echo "CREATE ROLE d_${idx1}${idx2}${idx3} WITH NOSUPERUSER NOCREATEDB NOCREATEROLE INHERIT LOGIN;"
 echo "GRANT d_${idx1}${idx2}${idx3} TO acc WITH ADMIN OPTION;"
done; done; done >>create-roles.sql

#create a lot of `s_` roles:
for idx1 in $(seq -w 1 100); do for idx2 in $(seq -w 1 12); do for idx3 in $(seq -w 1 10); do
 echo "CREATE ROLE s_${idx1}${idx2}${idx3} WITH NOSUPERUSER NOCREATEDB NOCREATEROLE INHERIT LOGIN;"
done; done; done >>create-roles.sql

time psql -f create-roles.sql -q -d postgres

time psql -U acc postgres -c 'GRANT d_0010109 TO s_0010109;'

---

From: Tom Lane <[email-masked]>
Date: Thu, 21 Mar 2024 13:00:39 -0400

I wrote:
> current role has.

Actually, roles_is_member_of sucks before v16 too; the new thing
is only that it's being invoked during GRANT ROLE.  Using the
roles created by the given test case, I see in v15:

$ psql
psql (15.6)
Type "help" for help.

regression=# drop table at;
DROP TABLE
regression=# set role a_0010308;
SET
regression=> create table at(f1 int);
CREATE TABLE
regression=> \timing
Timing is on.
regression=> set role acc;
SET
Time: 0.493 ms
regression=> insert into at values(1);
INSERT 0 1
Time: 3565.029 ms (00:03.565)
regression=> insert into at values(1);
INSERT 0 1
Time: 2.308 ms

So it takes ~3.5s to populate the roles_is_member_of cache for "acc"
given this membership set.  This is actually considerably worse than
in v16 or HEAD, where the same test takes about 1.6s for me.

Apparently the OP has designed their use-case so that they dodge these
implementation problems in v15 and earlier, but that's a far cry from
saying that there were no problems with lots-o-roles before v16.

			regards, tom lane

---

From: Tom Lane <[email-masked]>
Date: Thu, 21 Mar 2024 15:42:14 -0400

> 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

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 = 0;
 	long		cc_newloads = 0;
 	long		cc_invals = 0;
+	long		cc_nlists = 0;
 	long		cc_lsearches = 0;
 	long		cc_lhits = 0;
 
@@ -453,7 +456,7 @@ CatCachePrintStats(int code, Datum arg)
 
 		if (cache->cc_ntup == 0 && cache->cc_searches == 0)
 			continue;			/* don't print unused caches */
-		elog(DEBUG2, "catcache %s/%u: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%ld loads, %ld invals, %ld lsrch, %ld lhits",
+		elog(DEBUG2, "catcache %s/%u: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%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 += cache->cc_searches;
@@ -472,10 +476,11 @@ CatCachePrintStats(int code, Datum arg)
 		cc_neg_hits += cache->cc_neg_hits;
 		cc_newloads += cache->cc_newloads;
 		cc_invals += cache->cc_invals;
+		cc_nlists += cache->cc_nlist;
 		cc_lsearches += cache->cc_lsearches;
 		cc_lhits += cache->cc_lhits;
 	}
-	elog(DEBUG2, "catcache totals: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%ld loads, %ld invals, %ld lsrch, %ld lhits",
+	elog(DEBUG2, "catcache totals: %d tup, %ld srch, %ld+%ld=%ld hits, %ld+%ld=%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 = 0; i < cache->cc_nlbuckets; i++)
 	{
-		CatCList   *cl = dlist_container(CatCList, cache_elem, iter.cur);
+		dlist_head *bucket = &cache->cc_lbucket[i];
 
-		if (cl->refcount > 0)
-			cl->dead = true;
-		else
-			CatCacheRemoveCList(cache, cl);
+		dlist_foreach_modify(iter, bucket)
+		{
+			CatCList   *cl = dlist_container(CatCList, cache_elem, iter.cur);
+
+			if (cl->refcount > 0)
+				cl->dead = 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 = 0; i < cache->cc_nlbuckets; i++)
 	{
-		CatCList   *cl = dlist_container(CatCList, cache_elem, iter.cur);
+		dlist_head *bucket = &cache->cc_lbucket[i];
 
-		if (cl->refcount > 0)
-			cl->dead = true;
-		else
-			CatCacheRemoveCList(cache, cl);
+		dlist_foreach_modify(iter, bucket)
+		{
+			CatCList   *cl = dlist_container(CatCList, cache_elem, iter.cur);
+
+			if (cl->refcount > 0)
+				cl->dead = 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 = 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 = 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 = false; /* temporary */
 	cp->cc_tupdesc = (TupleDesc) NULL;
 	cp->cc_ntup = 0;
+	cp->cc_nlist = 0;
 	cp->cc_nbuckets = nbuckets;
+	cp->cc_nlbuckets = 0;
 	cp->cc_nkeys = nkeys;
 	for (i = 0; i < nkeys; ++i)
 	{
@@ -939,6 +965,44 @@ RehashCatCache(CatCache *cp)
 	cp->cc_bucket = 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 = cp->cc_nlbuckets * 2;
+	newbucket = (dlist_head *) MemoryContextAllocZero(CacheMemoryContext, newnbuckets * sizeof(dlist_head));
+
+	/* Move all entries from old hash table to new. */
+	for (i = 0; i < cp->cc_nlbuckets; i++)
+	{
+		dlist_mutable_iter iter;
+
+		dlist_foreach_modify(iter, &cp->cc_lbucket[i])
+		{
+			CatCList   *cl = dlist_container(CatCList, cache_elem, iter.cur);
+			int			hashIndex = 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 = newnbuckets;
+	cp->cc_lbucket = newbucket;
+}
+
 /*
  *		CatalogCacheInitializeCache
  *
@@ -1588,7 +1652,9 @@ SearchCatCacheList(CatCache *cache,
 	Datum		v4 = 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 == NULL)
+	if (unlikely(cache->cc_tupdesc == NULL))
 		CatalogCacheInitializeCache(cache);
 
 	Assert(nkeys > 0 && nkeys < cache->cc_nkeys);
@@ -1618,11 +1684,36 @@ SearchCatCacheList(CatCache *cache,
 	arguments[3] = 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 == NULL)
+	{
+		/* Arbitrary initial size --- must be a power of 2 */
+		int			nbuckets = 16;
+
+		cache->cc_lbucket = (dlist_head *)
+			MemoryContextAllocZero(CacheMemoryContext,
+								   nbuckets * sizeof(dlist_head));
+		/* Don't set cc_nlbuckets if we get OOM allocating cc_lbucket */
+		cache->cc_nlbuckets = 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 = CatalogCacheComputeHashValue(cache, nkeys, v1, v2, v3, v4);
+	lHashIndex = 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 = &cache->cc_lbucket[lHashIndex];
+	dlist_foreach(iter, lbucket)
 	{
 		cl = 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 == 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 */