Date: Tue, 26 Mar 2024 11:59:18 -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: <20240326165918.GA3350222@nathanxps13>
References: <20240322145532.GA2346110@nathanxps13>
 <907785.1711121266@sss.pgh.pa.us>
 <20240322163952.GA2347986@nathanxps13>
 <939945.1711126395@sss.pgh.pa.us>
 <20240322165448.GA2350322@nathanxps13>
 <20240322193506.GA2352051@nathanxps13>
 <1084642.1711140109@sss.pgh.pa.us>
 <20240325144743.GA2618709@nathanxps13>
 <2490242.1711379319@sss.pgh.pa.us>
 <20240325151647.GA2662364@nathanxps13>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="HlL+5n6rz5pIUxbD"
Content-Disposition: inline
In-Reply-To: <20240325151647.GA2662364@nathanxps13>
Archived-At: 
 <https://www.postgresql.org/message-id/20240326165918.GA3350222%40nathanxps13>
Precedence: bulk


--HlL+5n6rz5pIUxbD
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Here is a new version of the patch that I feel is in decent shape.

On Mon, Mar 25, 2024 at 10:16:47AM -0500, Nathan Bossart wrote:
> On Mon, Mar 25, 2024 at 11:08:39AM -0400, Tom Lane wrote:
>> * The magic constants (crossover list length and bloom filter size)
>> need some testing to see if there are better values.  They should
>> probably be made into named #defines, too.  I suspect, with little
>> proof, that the bloom filter size isn't particularly critical --- but
>> I know we pulled the crossover of 1000 out of thin air, and I have
>> no certainty that it's even within an order of magnitude of being a
>> good choice.
> 
> I'll try to construct a couple of tests to see if we can determine a proper
> order of magnitude.

I spent some time trying to get some ballpark figures but have thus far
been unsuccessful.  Even if I was able to get good numbers, I'm not sure
how much they'd help us, as we'll still need to decide how much overhead we
are willing to take in comparison to the linear search.  I don't think
~1000 is an unreasonable starting point, as it seems generally more likely
that you will have many more roles to process at that point than if the
threshold was, say, 100.  And if the threshold is too high (e.g., 10,000),
this optimization will only kick in for the most extreme cases, so we'd
likely be leaving a lot on the table.  But, I will be the first to admit
that my reasoning here is pretty unscientific, and I'm open to suggestions
for how to make it less so.

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

--HlL+5n6rz5pIUxbD
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment;
	filename="v3-0001-Optimize-roles_is_member_of-with-a-Bloom-filter.patch"