BUG #19774: Incremental backup loses re-extended blocks when WAL summaries are merged out of LSN order

The following bug has been logged on the website:

Bug reference: 19774
Logged by: Ke
Email address: kehan5800(at)gmail(dot)com
PostgreSQL version: 18.6
Operating system: Ubuntu 22.04 (Linux 5.15, x86_64)
Description:

An incremental backup taken after a relation was truncated by VACUUM and
then
extended again can omit the re-extended blocks, although the WAL summaries
list
them. pg_combinebackup then takes those blocks from the prior backup. In the
script below, every live row of the table is lost in the restored cluster
and
the 20000 rows deleted before the incremental backup come back.
pg_verifybackup
reports both input backups as valid.

Reproduced on master (45fc51fcbf) and 18.6, built from source with
./configure --without-icu.

The work directory must be on tmpfs, where readdir() returns the newest file
first. On ext4 the script also reproduced once the summaries directory was
large enough to be read in hash order (I created 150 extra summary files
first).

---- repro.sh: PGBIN=/usr/local/pgsql/bin sh repro.sh /dev/shm/inc ----
#!/bin/sh
set -e
W=$1; P=5440
rm -rf "$W"; mkdir -p "$W"
"$PGBIN/initdb" -D "$W/src" -A trust --no-locale >/dev/null
cat >> "$W/src/postgresql.conf" <<EOC
port = $P
unix_socket_directories = '$W'
listen_addresses = ''
summarize_wal = on
autovacuum = off
EOC
"$PGBIN/pg_ctl" -D "$W/src" -l "$W/src.log" -w start >/dev/null
q() { "$PGBIN/psql" -X -h "$W" -p "$1" -d postgres -Atq -c "$2"; }
sw() { q $P "SELECT pg_switch_wal()" >/dev/null; q $P "CHECKPOINT"; sleep 2;
} # end the current WAL summary
q $P "CREATE TABLE t (id int PRIMARY KEY, pad text)"
q $P "INSERT INTO t SELECT g, md5(g::text) FROM generate_series(1, 30000) g"
q $P "INSERT INTO t SELECT g, repeat('w', 3000) FROM
generate_series(1000001, 1020000) g"
sw
"$PGBIN/pg_basebackup" -h "$W" -p $P -D "$W/full" -c fast
q $P "DELETE FROM t WHERE id > 1000000"
q $P "VACUUM t" # truncates the heap
sw
q $P "UPDATE t SET pad = pad || 'u'" # the new row versions extend the
heap again
sw
"$PGBIN/pg_basebackup" -h "$W" -p $P -D "$W/incr" -c fast --incremental
"$W/full/backup_manifest"
REL=$(q $P "SELECT pg_relation_filepath('t')")
echo "source: $(q $P "SELECT count(*), max(id), pg_relation_size('t') /
8192 FROM t")"
"$PGBIN/pg_ctl" -D "$W/src" -w stop >/dev/null
echo "summaries for t in the order the server reads them (ls -U):"
for f in $(ls -U "$W/src/pg_wal/summaries"); do
s=$("$PGBIN/pg_walsummary" "$W/src/pg_wal/summaries/$f" | grep "REL
${REL##*/}, FORK main" | sed 's/.*FORK main: //' | tr '\n' ' ')
[ -n "$s" ] && echo " $f: $s"
done
set -- $(od -A n -t u4 -N 12 "$W/incr/$(dirname $REL)/INCREMENTAL.$(basename
$REL)")
echo "incr/$(dirname $REL)/INCREMENTAL.$(basename $REL): $2 blocks,
truncation_block_length $3"
"$PGBIN/pg_combinebackup" -o "$W/restored" "$W/full" "$W/incr"
echo "port = $((P + 1))" >> "$W/restored/postgresql.conf"
"$PGBIN/pg_ctl" -D "$W/restored" -l "$W/restored.log" -w start >/dev/null
echo "restored: $(q $((P + 1)) "SELECT count(*), max(id),
pg_relation_size('t') / 8192 FROM t")"
"$PGBIN/pg_ctl" -D "$W/restored" -w stop >/dev/null
---- end ----

Output on master (18.6 prints the same apart from the name of the last
summary file):

source: 30000|30000|500
summaries for t in the order the server reads them (ls -U):
0000000100000000050000280000000006000028.summary: blocks 0..499
0000000100000000030000280000000005000028.summary: limit 250 blocks 0..249
0000000100000000016F4FE80000000002000028.summary: limit 0 blocks 0..436
incr/base/5/INCREMENTAL.16384: 250 blocks, truncation_block_length 500
restored: 20000|1020000|500

Expected "restored: 30000|30000|500". The restored table has none of the
30000 live rows, and it has the 20000 deleted rows (ids 1000001..1020000).

The summaries are correct. The one ending at 0/5000028 holds the truncation
(limit 250) and the one ending at 0/6000028 holds the re-extension (blocks
0..499). PrepareForIncrementalBackup() merges the summaries in the order
GetWalSummaries() returns them, and that is readdir() order:

https://github.com/postgres/postgres/blob/45fc51fcbf4534ea2f6f85e36f8155dbd5ba9851/src/backend/backup/walsummary.c#L49-L84
https://github.com/postgres/postgres/blob/45fc51fcbf4534ea2f6f85e36f8155dbd5ba9851/src/backend/backup/basebackup_incremental.c#L571-L612

Here the later summary is merged first, so blocks 0..499 are recorded. The
earlier summary's limit 250 then goes through
BlockRefTableEntrySetLimitBlock(),
which drops every recorded block at or above the new limit:

https://github.com/postgres/postgres/blob/45fc51fcbf4534ea2f6f85e36f8155dbd5ba9851/src/common/blkreftable.c#L938-L961

As a result, the INCREMENTAL file holds blocks 0..249 only, while its
truncation_block_length is the file size (500). pg_combinebackup takes
blocks
250..436 from the full backup, which still holds the deleted wide rows
there,
and zero-fills 437..499. The new versions of the 30000 rows were in blocks
250..499, so they are lost. If the summaries are merged in LSN order, all
500
blocks are marked modified and the file is sent whole.

WalSummariesAreComplete() already sorts its own copy of the list by start
LSN
(walsummary.c line 151-153), but the merge loop uses the unsorted list.
Sorting
the list before the merge fixes this. With the patch below, the same script
on
master restores 30000|30000|500:

--- a/src/backend/backup/basebackup_incremental.c
+++ b/src/backend/backup/basebackup_incremental.c
@@ -142,6 +142,7 @@ static void
manifest_process_wal_range(JsonManifestParseContext *context,
pg_noreturn static void manifest_report_error(JsonManifestParseContext
*context,
const char *fmt, ...)
pg_attribute_printf(2, 3);
+static int CompareWalSummaryStartLSN(const ListCell *a, const ListCell
*b);
static int compare_block_numbers(const void *a, const void *b);

/*
@@ -568,6 +569,13 @@ PrepareForIncrementalBackup(IncrementalBackupInfo *ib,
* memory usage.
*/
ib->brtab = CreateEmptyBlockRefTable();
+
+ /*
+ * Merge the summaries in LSN order: applying a limit block discards
the
+ * blocks already recorded at or above it, so a summary's limit must
be
+ * applied before the blocks of later summaries are added.
+ */
+ list_sort(required_wslist, CompareWalSummaryStartLSN);
foreach(lc, required_wslist)
{
WalSummaryFile *ws = lfirst(lc);
@@ -614,6 +622,18 @@ PrepareForIncrementalBackup(IncrementalBackupInfo *ib,
MemoryContextSwitchTo(oldcontext);
}

+/*
+ * list_sort comparator: order WalSummaryFile objects by start LSN.
+ */
+static int
+CompareWalSummaryStartLSN(const ListCell *a, const ListCell *b)
+{
+ WalSummaryFile *ws1 = lfirst(a);
+ WalSummaryFile *ws2 = lfirst(b);
+
+ return pg_cmp_u64(ws1->start_lsn, ws2->start_lsn);
+}
+
/*
* Get the pathname that should be used when a file is sent incrementally.
*

Related, not the same cause: "Incremental backup inconsistency after vacuum
truncation + COPY regrowth" (pgsql-hackers, 2026-07-29,
https://www.postgresql.org/message-id/CAPnDWbagY0Y91qZmJkuJX4+byVJ-dJysnx4QmW23wgR_AvECVg@mail.gmail.com)
has the same symptom. There, the re-extended blocks are zero pages that were
never WAL-logged, so no summary lists them. Here, every re-extended block is
WAL-logged and listed in a summary, and the server drops the blocks itself
while
merging. If I read the diff in that thread correctly, its proposed change
(send any segment with a limit block in full) would avoid this case for new
backups, but the merge order would still be wrong.