From: Tom Lane <tgl@sss.pgh.pa.us>
To: Nathan Bossart <nathandbossart@gmail.com>
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
In-reply-to: <20240322005139.GA2060816@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>
Comments: In-reply-to Nathan Bossart <nathandbossart@gmail.com>
	message dated "Thu, 21 Mar 2024 19:51:39 -0500"
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <806360.1711069194.1@sss.pgh.pa.us>
Date: Thu, 21 Mar 2024 20:59:54 -0400
Message-ID: <806361.1711069194@sss.pgh.pa.us>
Archived-At: 
 <https://www.postgresql.org/message-id/806361.1711069194%40sss.pgh.pa.us>
Precedence: bulk

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