pg.ddx.io pgsql-committers@postgresql.org mailing list archivehelp / color / mirror / Atom feed
pgsql: Avoid O(N^2) behavior in SyncPostCheckpoint(). 3+ messages / 1 participants [nested] [flat]
* pgsql: Avoid O(N^2) behavior in SyncPostCheckpoint(). @ 2021-11-02 15:32 Tom Lane <tgl@sss.pgh.pa.us> 0 siblings, 0 replies; 3+ messages in thread From: Tom Lane @ 2021-11-02 15:32 UTC (permalink / raw) To: pgsql-committers@lists.postgresql.org 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(-) ^ permalink raw reply [nested|flat] 3+ messages in thread
* pgsql: Avoid O(N^2) behavior in SyncPostCheckpoint(). @ 2021-11-02 15:32 Tom Lane <tgl@sss.pgh.pa.us> 0 siblings, 0 replies; 3+ messages in thread From: Tom Lane @ 2021-11-02 15:32 UTC (permalink / raw) To: pgsql-committers@lists.postgresql.org 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_14_STABLE Details ------- https://git.postgresql.org/pg/commitdiff/08cfa5981e17d9daaa861520a1d41259748732b8 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(-) ^ permalink raw reply [nested|flat] 3+ messages in thread
* pgsql: Avoid O(N^2) behavior in SyncPostCheckpoint(). @ 2021-11-02 15:32 Tom Lane <tgl@sss.pgh.pa.us> 0 siblings, 0 replies; 3+ messages in thread From: Tom Lane @ 2021-11-02 15:32 UTC (permalink / raw) To: pgsql-committers@lists.postgresql.org 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(-) ^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2021-11-02 15:32 UTC | newest] Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2021-11-02 15:32 pgsql: Avoid O(N^2) behavior in SyncPostCheckpoint(). Tom Lane <tgl@sss.pgh.pa.us> 2021-11-02 15:32 pgsql: Avoid O(N^2) behavior in SyncPostCheckpoint(). Tom Lane <tgl@sss.pgh.pa.us> 2021-11-02 15:32 pgsql: Avoid O(N^2) behavior in SyncPostCheckpoint(). Tom Lane <tgl@sss.pgh.pa.us>
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