Horton

Re: inefficient loop in StandbyReleaseLockList()

Nathan Bossart <bossartn@amazon.com>

View thread View on postgr.es
From: "Bossart, Nathan" <bossartn@amazon.com>
To: Tom Lane <tgl@sss.pgh.pa.us>, Andres Freund <andres@anarazel.de>
Cc: Kyotaro Horiguchi <horikyota.ntt@gmail.com>, "sulamul@gmail.com" <sulamul@gmail.com>, "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org>
Date: 2021-10-28T23:15:50Z
Lists: pgsql-hackers 
On 10/28/21, 3:25 PM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> Andres Freund <andres@anarazel.de> writes:
>> Which leads to to wonder whether the better fix would be to switch to deleting
>> the last element, but still use the while (!empty) style. That should convert
>> the O(n^2) due to 1cff1b9 back to O(n). It might or might not be faster/slower
>> than using foreach(), but it should be within the same ballpark.
>
> Does it matter what order we're releasing the locks in?

I'm not seeing anything that indicates the ordering matters.  AFAICT
either approach would work in this case.  IMO changing the order is
scarier than switching to foreach(), though.

Nathan

Commits

  1. Doc: add some notes about performance of the List functions.

  2. Avoid O(N^2) behavior in SyncPostCheckpoint().

  3. Avoid some other O(N^2) hazards in list manipulation.

  4. Avoid O(N^2) behavior when the standby process releases many locks.