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
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.
*/
