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

On Thu, Mar 21, 2024 at 08:59:54PM -0400, Tom Lane wrote:
> 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.

I apparently had some sort of major brain fade when I did this because I
didn't apply your hashing patch when I ran this SIMD test.  With it
applied, I see a speedup of ~39%, which makes a whole lot more sense to me.
If I add the Bloom patch (updated with your suggestions), I get another
~73% improvement from there, and a much smaller regression in the role
creation portion.

            hash     hash+simd hash+simd+bloom
    create  1.27     1.27      1.28
    grant   0.18     0.11      0.03

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