Horton

Re: inefficient loop in StandbyReleaseLockList()

Andres Freund <andres@anarazel.de>

View thread View on postgr.es
From: Andres Freund <andres@anarazel.de>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: "Bossart, Nathan" <bossartn@amazon.com>, Michael Paquier <michael@paquier.xyz>, Kyotaro Horiguchi <horikyota.ntt@gmail.com>, "sulamul@gmail.com" <sulamul@gmail.com>, "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org>
Date: 2021-10-31T20:37:48Z
Lists: pgsql-hackers 
Hi,

On 2021-10-31 15:38:15 -0400, Tom Lane wrote:
> Yeah, there's no expectation that this data structure needs to be kept
> consistent after an error; and I'm not real sure that the existing
> code could claim to satisfy such a requirement if we did need it.

To be clear, I was making that comment in response to the search for
other places doing the while(!empty) delete_first() style loops. Some of
them are reached via resowners etc, where reaching the same code
repeatedly is perhaps more realistic.

Greetings,

Andres Freund

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.