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

Nathan Bossart <nathandbossart@gmail.com> writes:
> On Thu, Mar 21, 2024 at 03:40:12PM -0500, Nathan Bossart wrote:
>> On Thu, Mar 21, 2024 at 04:31:45PM -0400, Tom Lane wrote:
>>> I don't think we have any really cheap way to de-duplicate the role
>>> OIDs, especially seeing that it has to be done on-the-fly within the
>>> collection loop, and the order of roles_list is at least potentially
>>> interesting.  Not sure how to make further progress without a lot of
>>> work.

>> Assuming these are larger lists, this might benefit from optimizations
>> involving SIMD intrinsics.

> Never mind.  With the reproduction script, I'm only seeing a ~2%
> improvement with my patches.

Yeah, you cannot beat an O(N^2) problem by throwing SIMD at it.

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?

            regards, tom lane