Date: Thu, 21 Mar 2024 20:52:51 -0500
From: Nathan Bossart <nathandbossart@gmail.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: pgsql-hackers@lists.postgresql.org, alex work <alexwork033@gmail.com>,
	Robert Haas <robertmhaas@gmail.com>
Subject: Re: Slow GRANT ROLE on PostgreSQL 16 with thousands of ROLEs
Message-ID: <20240322015251.GA2193900@nathanxps13>
References: <CAGvXd3OSMbJQwOSc-Tq-Ro1CAz=vggErdSG7pv2s6vmmTOLJSg@mail.gmail.com>
 <341186.1711037256@sss.pgh.pa.us>
 <619340.1711050134@sss.pgh.pa.us>
 <642442.1711053105@sss.pgh.pa.us>
 <20240321204012.GA1992418@nathanxps13>
 <20240322005139.GA2060816@nathanxps13>
 <806361.1711069194@sss.pgh.pa.us>
 <20240322010332.GA2109205@nathanxps13>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="u3/rZRmxL6MmkK24"
Content-Disposition: inline
In-Reply-To: <20240322010332.GA2109205@nathanxps13>
Archived-At: <https://www.postgresql.org/message-id/20240322015251.GA2193900%40nathanxps13>
Precedence: bulk


--u3/rZRmxL6MmkK24
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

On Thu, Mar 21, 2024 at 08:03:32PM -0500, Nathan Bossart wrote:
> On Thu, Mar 21, 2024 at 08:59:54PM -0400, Tom Lane wrote:
>> However ... I just remembered that we have a Bloom filter implementation
>> in core now (src/backend/lib/bloomfilter.c).  How about using that
>> to quickly reject (hopefully) most role OIDs, and only do the
>> list_member_oid check if the filter passes?
> 
> Seems worth a try.  I've been looking for an excuse to use that...

The Bloom filter appears to help a bit, although it regresses the
create-roles.sql portion of the test.  I'm assuming that's thanks to all
the extra pallocs and pfrees, which are probably avoidable if we store the
filter in a long-lived context and just clear it at the beginning of each
call to roles_is_member_of().

        HEAD  hash  hash+bloom
create  2.02  2.06  2.92
grant   4.63  0.27  0.08

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com

--u3/rZRmxL6MmkK24
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment; filename="bloom.patch"

diff --git a/src/backend/utils/adt/acl.c b/src/backend/utils/adt/acl.c
index cf5d08576a..445a14646c 100644
--- a/src/backend/utils/adt/acl.c
+++ b/src/backend/utils/adt/acl.c
@@ -36,6 +36,7 @@
 #include "common/hashfn.h"
 #include "foreign/foreign.h"
 #include "funcapi.h"
+#include "lib/bloomfilter.h"
 #include "lib/qunique.h"
 #include "miscadmin.h"
 #include "utils/acl.h"
@@ -4946,6 +4947,7 @@ roles_is_member_of(Oid roleid, enum RoleRecurseType type,
 	ListCell   *l;
 	List	   *new_cached_roles;
 	MemoryContext oldctx;
+	bloom_filter *bf;
 
 	Assert(OidIsValid(admin_of) == PointerIsValid(admin_role));
 	if (admin_role != NULL)
@@ -4987,6 +4989,9 @@ roles_is_member_of(Oid roleid, enum RoleRecurseType type,
 	 */
 	roles_list = list_make1_oid(roleid);
 
+	bf = bloom_create(1024, work_mem, 0);
+	bloom_add_element(bf, (unsigned char *) &roleid, sizeof(Oid));
+
 	foreach(l, roles_list)
 	{
 		Oid			memberid = lfirst_oid(l);
@@ -5023,16 +5028,29 @@ roles_is_member_of(Oid roleid, enum RoleRecurseType type,
 			 * graph, we must test for having already seen this role. It is
 			 * legal for instance to have both A->B and A->C->B.
 			 */
-			roles_list = list_append_unique_oid(roles_list, otherid);
+			if (bloom_lacks_element(bf, (unsigned char *) &otherid, sizeof(Oid)))
+				roles_list = lappend_oid(roles_list, otherid);
+			else
+				roles_list = list_append_unique_oid(roles_list, otherid);
+			bloom_add_element(bf, (unsigned char *) &otherid, sizeof(Oid));
 		}
 		ReleaseSysCacheList(memlist);
 
 		/* implement pg_database_owner implicit membership */
 		if (memberid == dba && OidIsValid(dba))
-			roles_list = list_append_unique_oid(roles_list,
-												ROLE_PG_DATABASE_OWNER);
+		{
+			Oid dbowner = ROLE_PG_DATABASE_OWNER;
+
+			if (bloom_lacks_element(bf, (unsigned char *) &dbowner, sizeof(Oid)))
+				roles_list = lappend_oid(roles_list, ROLE_PG_DATABASE_OWNER);
+			else
+				roles_list = list_append_unique_oid(roles_list, ROLE_PG_DATABASE_OWNER);
+			bloom_add_element(bf, (unsigned char *) &dbowner, sizeof(Oid));
+		}
 	}
 
+	bloom_free(bf);
+
 	/*
 	 * Copy the completed list into TopMemoryContext so it will persist.
 	 */

--u3/rZRmxL6MmkK24--