[HACKERS] Broken O(n^2) avoidance in wal segment recycling. - Mailing list pgsql-hackers

From Andres Freund
Subject [HACKERS] Broken O(n^2) avoidance in wal segment recycling.
Date
Msg-id 20170621211016.eln6cxxp3jrv7m4m@alap3.anarazel.de
Whole thread Raw
Responses Re: [HACKERS] Broken O(n^2) avoidance in wal segment recycling.
List pgsql-hackers
Hi,

Author: Heikki Linnakangas <heikki.linnakangas@iki.fi>
Branch: master Release: REL9_5_BR [b2a5545bd] 2015-04-13 16:53:49 +0300
Branch: REL9_4_STABLE Release: REL9_4_2 [d72792d02] 2015-04-13 17:22:21 +0300
Branch: REL9_3_STABLE Release: REL9_3_7 [a800267e4] 2015-04-13 17:22:35 +0300
Branch: REL9_2_STABLE Release: REL9_2_11 [cc2939f44] 2015-04-13 17:26:59 +0300
Branch: REL9_1_STABLE Release: REL9_1_16 [ad2925e20] 2015-04-13 17:26:49 +0300
Branch: REL9_0_STABLE Release: REL9_0_20 [5b6938186] 2015-04-13 17:26:35 +0300
   Don't archive bogus recycled or preallocated files after timeline switch.

Moved xlog file deletion from RemoveOldXlogFiles() into its own
RemoveXlogFile() routine, because it introduced a new function also
deleting/recycling segments.

It did so moving
+       /* Needn't recheck that slot on future iterations */
+       endlogSegNo++;
into the new routine. But it's useless there, because it's just a stack
variable, which is going to be freshly computed with
+   XLByteToPrevSeg(endptr, endlogSegNo);
on the next call.

That logic was introduced in

commit 61b861421b0b849a0dffe36238b8e504624831c1
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date:   2005-04-15 18:48:10 +0000
   Modify MoveOfflineLogs/InstallXLogFileSegment to avoid O(N^2) behavior   when recycling a large number of xlog
segmentsduring checkpoint.   The former behavior searched from the same start point each time,   requiring
O(checkpoint_segments^2)stat() calls to relocate all the   segments.  Instead keep track of where we stopped last time
through.

but was neutered by the commit above.

We've not heard any complaints about this afaik, but it's not something
that's easily diagnosable as being a problem.  Therefore I suspect we
should fix and backpatch this?

Heikki?

Greetings,

Andres Freund



pgsql-hackers by date:

Previous
From: Bruce Momjian
Date:
Subject: Re: [HACKERS] Re-indent HEAD tomorrow?
Next
From: Tom Lane
Date:
Subject: Re: [HACKERS] Re-indent HEAD tomorrow?