pg.ddx.io  pgsql-committers@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Tom Lane <tgl@sss.pgh.pa.us>
To: pgsql-committers@lists.postgresql.org
Subject: pgsql: Avoid O(N^2) behavior in SyncPostCheckpoint().
Date: Tue, 02 Nov 2021 15:32:06 +0000
Message-ID: <E1mhvle-0008Q2-Ey@gemulon.postgresql.org> (raw)

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

As in commits 6301c3ada and e9d9ba2a4, avoid doing repetitive
list_delete_first() operations, since that would be expensive when
there are many files waiting to be unlinked.  This is a slightly
larger change than in those cases.  We have to keep the list state
valid for calls to AbsorbSyncRequests(), so it's necessary to invent a
"canceled" field instead of immediately deleting PendingUnlinkEntry
entries.  Also, because we might not be able to process all the
entries, we need a new list primitive list_delete_first_n().

list_delete_first_n() is almost list_copy_tail(), but it modifies the
input List instead of making a new copy.  I found a couple of existing
uses of the latter that could profitably use the new function.  (There
might be more, but the other callers look like they probably shouldn't
overwrite the input List.)

As before, back-patch to v13.

Discussion: https://postgr.es/m/CD2F0E7F-9822-45EC-A411-AE56F14DEA9F@amazon.com

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/65c6cab1365ac33b11a49a2a193f6b3f9c53e487

Modified Files
--------------
src/backend/nodes/list.c             | 66 ++++++++++++++++++++++++++++++++++++
src/backend/optimizer/util/clauses.c |  2 +-
src/backend/parser/parse_func.c      |  2 +-
src/backend/storage/sync/sync.c      | 46 ++++++++++++++++++-------
src/include/nodes/pg_list.h          |  1 +
5 files changed, 103 insertions(+), 14 deletions(-)



view thread (3+ messages)

Message-ID: <E1mhvle-0008Q2-Ey@gemulon.postgresql.org>
Permalink:  ../E1mhvle-0008Q2-Ey@gemulon.postgresql.org/
Also on:    postgresql.org/message-id/E1mhvle-0008Q2-Ey@gemulon.postgresql.org

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-committers@postgresql.org
  Cc: tgl@sss.pgh.pa.us
  Subject: Re: pgsql: Avoid O(N^2) behavior in SyncPostCheckpoint().
  In-Reply-To: <E1mhvle-0008Q2-Ey@gemulon.postgresql.org>
  References: <E1mhvle-0008Q2-Ey@gemulon.postgresql.org>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox