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

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: pgsql-committers(at)lists(dot)postgresql(dot)org
Subject: pgsql: Avoid O(N^2) behavior in SyncPostCheckpoint().
Date: 2021-11-02 15:32:06
Message-ID: E1mhvle-0008Q6-Fs@gemulon.postgresql.org
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-committers

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
------
REL_13_STABLE

Details
-------
https://git.postgresql.org/pg/commitdiff/0151af40cd4e0321bc549cea9f0c631bce0303c5

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(-)

Browse pgsql-committers by date

  From Date Subject
Next Message Tom Lane 2021-11-02 16:12:10 pgsql: Doc: be more precise about conflicts between relation names.
Previous Message Fujii Masao 2021-11-02 14:09:52 pgsql: pgbench: Fix typo in comment.