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

------- =_aaaaaaaaaa0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <341088.1711037174.1@sss.pgh.pa.us>
Content-Transfer-Encoding: quoted-printable

[ redirecting to -hackers ]

alex work <alexwork033@gmail.com> writes:
> 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 C=
PU.
> 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 mo=
de.

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


------- =_aaaaaaaaaa0
Content-Type: text/x-shellscript; name="grant_with_many_roles.sh";
	charset="us-ascii"
Content-ID: <341088.1711037174.2@sss.pgh.pa.us>
Content-Description: grant_with_many_roles.sh
Content-Transfer-Encoding: quoted-printable

#!/bin/bash

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

#create a lot of `a_` roles and make sure `acc` is member of each one of t=
hem:
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 NOC=
REATEROLE 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 t=
hem:
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 NOC=
REATEROLE 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 NOC=
REATEROLE 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;'

------- =_aaaaaaaaaa0--