Inside the Kernel: The Complete Path to PostgreSQL Delete Recovery — From FPW to Data Resurrection

Introduction: Can Data Be Recovered After a DELETE?

In PostgreSQL, a DELETE operation does not immediately erase data from disk. The MVCC mechanism retains deleted rows as dead tuples, and reading these dead tuples is one viable approach to data recovery.

However, this approach has a clear time limitation: once autovacuum completes its cleanup, the dead tuples are physically removed, and recovery methods based on data files become ineffective.

At this point, the WAL (Write-Ahead Log) offers an alternative recovery path. Specifically, the FPW (Full Page Write) mechanism within WAL is the foundation of this approach. PostgreSQL DELETE recovery tools — including PDU (PostgreSQL Data Unloader) — rely on this technique. Its key property: as long as the WAL files generated during the deletion period still exist, the data can be fully recovered regardless of how much time has passed.

This article dissects that recovery path function by function, based on PostgreSQL 18 source code.

---

Chapter 1: Full Page Write (FPW) — Complete Page Snapshots in WAL

1.1 What Is FPW?

The rule is deceptively simple: after every checkpoint, the first time a data page is modified, PostgreSQL writes the entire 8KB page into the WAL record for that modification.

Why? Because the operating system does not write 8KB pages atomically. A power failure mid-write can leave a page half-old, half-new — a torn page. If crash recovery then tries to replay WAL on top of that corrupted page, the result is catastrophic. FPW addresses this by storing a complete snapshot of the page in the WAL, ensuring that a consistent page state can always be restored.

For DELETE recovery, FPW has additional value — it preserves a complete copy of the data page within WAL, from which recovery tools can extract the deleted data.

1.2 How Does the Kernel Decide Whether to Write an FPW?

The core decision lives in XLogRecordAssemble in src/backend/access/transam/xloginsert.c:

// File: src/backend/access/transam/xloginsert.c
// Function: XLogRecordAssemble

for (block_id = 0; block_id < max_registered_block_id; block_id++)
{
    registered_buffer *regbuf = &registered_buffers[block_id];
    bool needs_backup;

    if (!regbuf->in_use)
        continue;

    /* Determine if this block needs to be backed up */
    if (regbuf->flags & REGBUF_FORCE_IMAGE)
        needs_backup = true;
    else if (regbuf->flags & REGBUF_NO_IMAGE)
        needs_backup = false;
    else if (!doPageWrites)
        needs_backup = false;
    else
    {
        XLogRecPtr  page_lsn = PageGetLSN(regbuf->page);
        needs_backup = (page_lsn <= RedoRecPtr);
    }

    /* ... if needs_backup is true, the full page is written into WAL ... */
}

The decision tree boils down to four rules:

1. REGBUF_FORCE_IMAGE: Force an FPW regardless of any other condition.
2. REGBUF_NO_IMAGE: Explicitly suppress the FPW.
3. !doPageWrites: full_page_writes = off and no online backup running — skip it.
4. The core test: page_lsn <= RedoRecPtr — if the page's LSN is at or before the last checkpoint's redo point, this page has not been modified since the last checkpoint. This is the first modification. An FPW is required.

PostgreSQL also provides a simplified query interface, XLogCheckBufferNeedsBackup, so callers can check in advance:

// File: src/backend/access/transam/xloginsert.c

bool
XLogCheckBufferNeedsBackup(Buffer buffer)
{
    XLogRecPtr  RedoRecPtr;
    bool        doPageWrites;
    Page        page;

    GetFullPageWriteInfo(&RedoRecPtr, &doPageWrites);
    page = BufferGetPage(buffer);

    if (doPageWrites && PageGetLSN(page) <= RedoRecPtr)
        return true;            /* buffer requires backup */

    return false;
}

One sentence summary: first modification to a page after checkpoint = FPW.

1.3 What Does an FPW Contain?

The storage structure for FPW data is DecodedBkpBlock, defined in src/include/access/xlogreader.h:

// File: src/include/access/xlogreader.h

typedef struct
{
    bool        in_use;           /* is this block ref active? */
    RelFileLocator rlocator;      /* physical location of the relation */
    ForkNumber  forknum;          /* fork number */
    BlockNumber blkno;            /* block number */
    /* ... prefetch_buffer, flags omitted ... */

    /* Full page image info — the core fields for FPW recovery */
    bool        has_image;        /* does it contain a full page image? */
    bool        apply_image;      /* should the image be applied during recovery? */
    char       *bkp_image;        /* pointer to the full page image data */
    uint16      hole_offset;      /* offset of the page hole */
    uint16      hole_length;      /* length of the page hole */
    uint16      bimg_len;         /* image data length (possibly compressed) */
    uint8       bimg_info;        /* compression algorithm metadata */

    /* ... rmgr-specific data fields omitted ... */
} DecodedBkpBlock;

The fields that matter most:

• rlocator + blkno: Identifies which table and which block — this is how a recovery tool links an FPW to the target table.
• bkp_image: Points to the actual full page image data — the complete 8KB page (possibly compressed).
• hole_offset / hole_length: The "hole" between pd_lower and pd_upper — the free space that PostgreSQL skips when writing to WAL to save space, then zero-fills during restoration.
• bimg_info: Indicates the compression algorithm (pglz / LZ4 / ZSTD) and whether the image should be applied during recovery (BKPIMAGE_APPLY).

1.4 Seeing FPW in Action

To make this tangible, here is a quick experiment:

DROP TABLE IF EXISTS xman;
CREATE TABLE xman (a int, b varchar);
INSERT INTO xman VALUES(1,'sdfghgfdsadfghgfds');
INSERT INTO xman VALUES(2,'wertyuijhbhghgtgvyhjujkgfdswerfcdsw');
INSERT INTO xman VALUES(3,'qwertyuiopoiufdfghjkjhvcvbnbvcfgfcfgdxfcd');
INSERT INTO xman VALUES(4,'wsxdedcfrfgbvgyhnujmjikm,kl,lp;.llkjhghjhgfg');
CHECKPOINT;
UPDATE xman SET b='aaaaaaaa' WHERE a=1;
UPDATE xman SET b='bbbbbbbb' WHERE a=2;
UPDATE xman SET b='cccccccc' WHERE a=3;
DELETE FROM xman WHERE a=1;

After looking up the table's relfilenode, run pg_waldump on the WAL file:

rmgr: Heap  desc: HOT_UPDATE off 1 xmax 203416 flags 0x20 ; new off 5 xmax 0,
      blkref #0: rel 1663/352324/602913 blk 0 FPW
rmgr: Heap  desc: HOT_UPDATE off 2 xmax 203417 flags 0x20 ; new off 6 xmax 0,
      blkref #0: rel 1663/352324/602913 blk 0
rmgr: Heap  desc: HOT_UPDATE off 3 xmax 203418 flags 0x20 ; new off 7 xmax 0,
      blkref #0: rel 1663/352324/602913 blk 0
rmgr: Heap  desc: DELETE off 5 flags 0x00 KEYS_UPDATED,
      blkref #0: rel 1663/352324/602913 blk 0

Notice that the first UPDATE carries the FPW tag — it is the first modification to blk 0 after the checkpoint. The subsequent UPDATEs and the DELETE carry no FPW, because blk 0 has already been modified in this checkpoint cycle.

This reveals a critical fact: the FPW does not necessarily appear in the DELETE record itself. It may appear in any earlier modification within the same checkpoint cycle. A recovery tool must look backwards to find it.

Starting from PG 16, pg_waldump added the --save-fullpage flag to export FPW data to a directory:

pg_waldump --save-fullpage=./fpw_output WAL_FILE_NAME

But be warned: the exported FPW is merely a "base snapshot." To use it for delete recovery, you must replay it forward to the exact moment of deletion.

---

Chapter 2: Extracting the FPW — Recovering a Complete Page from WAL

2.1 RestoreBlockImage: The FPW Decoder

When we need to recover a full page image from WAL, the workhorse is RestoreBlockImage in src/backend/access/transam/xlogreader.c:

// File: src/backend/access/transam/xlogreader.c

bool
RestoreBlockImage(XLogReaderState *record, uint8 block_id, char *page)
{
    DecodedBkpBlock *bkpb;
    char       *ptr;
    PGAlignedBlock tmp;

    /* Validate block_id, error handling omitted... */

    bkpb = &record->record->blocks[block_id];
    ptr = bkpb->bkp_image;

    /* If the FPW is compressed, decompress first (supports pglz/LZ4/ZSTD) */
    if (BKPIMAGE_COMPRESSED(bkpb->bimg_info))
    {
        /* Select decompression algorithm based on bimg_info flags, branches omitted... */
        if (!decomp_success)
            return false;
        ptr = tmp.data;
    }

    /* Reconstruct the full 8KB page, zero-filling the hole */
    if (bkpb->hole_length == 0)
    {
        memcpy(page, ptr, BLCKSZ);
    }
    else
    {
        memcpy(page, ptr, bkpb->hole_offset);
        MemSet(page + bkpb->hole_offset, 0, bkpb->hole_length);
        memcpy(page + (bkpb->hole_offset + bkpb->hole_length),
               ptr + bkpb->hole_offset,
               BLCKSZ - (bkpb->hole_offset + bkpb->hole_length));
    }

    return true;
}

Three steps: validate, decompress, reconstruct. The hole-filling logic deserves a close look: when hole_length == 0, it is a straight copy; otherwise the page is assembled in three segments — data before the hole, the zero-filled hole itself, and data after the hole. This hole corresponds to the free space between pd_lower (end of the line pointer array) and pd_upper (start of tuple data).

2.2 XLogReadBufferForRedo: The Replay Gateway

During WAL replay, every redo function calls XLogReadBufferForRedo to obtain the page it needs to operate on. This function is the central hub of the entire replay mechanism:

// File: src/backend/access/transam/xlogutils.c

XLogRedoAction
XLogReadBufferForRedoExtended(XLogReaderState *record,
                              uint8 block_id,
                              ReadBufferMode mode, bool get_cleanup_lock,
                              Buffer *buf)
{
    XLogRecPtr  lsn = record->EndRecPtr;

    /* If the WAL record carries an FPW marked for APPLY, restore the page from it */
    if (XLogRecBlockImageApply(record, block_id))
    {
        *buf = XLogReadBufferExtended(rlocator, forknum, blkno,
              get_cleanup_lock ? RBM_ZERO_AND_CLEANUP_LOCK : RBM_ZERO_AND_LOCK,
              prefetch_buffer);
        page = BufferGetPage(*buf);

        if (!RestoreBlockImage(record, block_id, page))
            ereport(ERROR, ...);

        if (!PageIsNew(page))
            PageSetLSN(page, lsn);

        MarkBufferDirty(*buf);
        return BLK_RESTORED;   /* Page fully restored from FPW */
    }
    else
    {
        /* No FPW — read the page from disk */
        *buf = XLogReadBufferExtended(rlocator, forknum, blkno,
                                      mode, prefetch_buffer);
        if (BufferIsValid(*buf))
        {
            if (lsn <= PageGetLSN(BufferGetPage(*buf)))
                return BLK_DONE;       /* Already up to date */
            else
                return BLK_NEEDS_REDO; /* Needs replay */
        }
        else
            return BLK_NOTFOUND;       /* Page doesn't exist */
    }
}

The return values are critical to understanding the replay flow:

Return Value	Meaning	Implication for Recovery
BLK_RESTORED	FPW fully restored the page	No further changes needed
BLK_NEEDS_REDO	Page is older than the WAL record	Must apply incremental changes
BLK_DONE	Page is already current	Skip this record
BLK_NOTFOUND	Page does not exist	Likely truncated away

For a delete recovery tool, we reuse RestoreBlockImage to extract the FPW as a "base page," then simulate the redo logic of subsequent WAL records to advance the page to the precise state at the moment of deletion.

---

Chapter 3: Replaying the FPW — Advancing the Page to the Moment of Deletion

3.1 The Necessity of Replay

It is important to note that an FPW captures the page state at the moment of the first modification after a checkpoint — not at the moment of deletion.

Consider this timeline:

18:00  CHECKPOINT
18:01  UPDATE → generates FPW (snapshot of the page at this instant)
18:02  INSERT → adds a new row to the same page
18:03  UPDATE → modifies another row on the page
18:04  DELETE → the operation we want to recover

If you naively use the 18:01 FPW to locate the 18:04 DELETE data, two things go wrong:

• The 18:02 INSERT changed the line pointer array, so offsets are now misaligned.
• The 18:03 UPDATE may have modified tuple contents, creating inconsistencies.

Therefore, every operation the database performed on that page between 18:01 and 18:04 must be replayed to bring the FPW to the correct data state at deletion time. This has been validated during the development of PDU (GitHub repository) — using the raw FPW page directly for recovery produces incorrect results or fails because the target offset position does not exist.

3.2 Which Operations Must Be Replayed?

Based on their impact on page content, operations fall into two categories:

Must replay (change data content and line pointer layout):

Operation	Impact
INSERT / MULTI_INSERT	Adds new tuples, extends line pointer array
UPDATE / HOT_UPDATE	Marks old tuple dead, adds new tuple
DELETE	Sets the tuple's xmax
PRUNE	Reclaims dead tuple space, redirects line pointers
VACUUM	Cleans the page, frees line pointers

Optional replay (only modify visibility flags, no data layout change):

Operation	Impact
LOCK	Modifies infomask lock bits
VISIBLE	Sets visibility map flag
FREEZE_PAGE	Freezes transaction IDs
CONFIRM	Confirms speculative insert

Let us walk through the kernel's redo functions for each critical operation.

3.3 INSERT Replay: Adding Tuples to the Page

// File: src/backend/access/heap/heapam_xlog.c

static void
heap_xlog_insert(XLogReaderState *record)
{
    XLogRecPtr  lsn = record->EndRecPtr;
    xl_heap_insert *xlrec = (xl_heap_insert *) XLogRecGetData(record);

    /* Get the page (initialize blank page if INIT_PAGE, otherwise read from disk) */
    if (XLogRecGetInfo(record) & XLOG_HEAP_INIT_PAGE)
    {   /* PageInit logic omitted... */   }
    else
        action = XLogReadBufferForRedo(record, 0, &buffer);

    if (action == BLK_NEEDS_REDO)
    {
        page = BufferGetPage(buffer);

        /* Extract tuple header and data from the WAL record */
        data = XLogRecGetBlockData(record, 0, &datalen);
        newlen = datalen - SizeOfHeapHeader;
        memcpy(&xlhdr, data, SizeOfHeapHeader);
        data += SizeOfHeapHeader;

        /* Reconstruct the complete tuple (set infomask, xmin, ctid, etc.) */
        htup = &tbuf.hdr;
        MemSet(htup, 0, SizeofHeapTupleHeader);
        memcpy((char *) htup + SizeofHeapTupleHeader, data, newlen);
        newlen += SizeofHeapTupleHeader;
        /* ... htup field assignments omitted ... */

        /* Insert the tuple at the specified offset — this changes the line pointer array! */
        if (PageAddItem(page, (Item) htup, newlen, xlrec->offnum,
                        true, true) == InvalidOffsetNumber)
            elog(PANIC, "failed to add tuple");

        PageSetLSN(page, lsn);
        MarkBufferDirty(buffer);
    }
}

When replaying an INSERT, the function reconstructs the full tuple (header + data) from WAL and calls PageAddItem to place it at the specified offset. This modifies the page's line pointer array, directly affecting the offset that a subsequent DELETE will reference. Skip the INSERT replay, and the offsets go wrong.

3.4 UPDATE Replay: Old Tuple Dies, New Tuple Is Born

UPDATE replay is the most complex, because it touches both the old and new pages (which differ in cross-page UPDATEs) and features a clever optimization — prefix/suffix reuse:

// File: src/backend/access/heap/heapam_xlog.c

static void
heap_xlog_update(XLogReaderState *record, bool hot_update)
{
    xl_heap_update *xlrec = (xl_heap_update *) XLogRecGetData(record);

    /* === Step 1: Process old tuple — mark it dead === */
    oldaction = XLogReadBufferForRedo(record,
                    (oldblk == newblk) ? 0 : 1, &obuffer);
    if (oldaction == BLK_NEEDS_REDO)
    {
        lp = PageGetItemId(page, xlrec->old_offnum);
        htup = (HeapTupleHeader) PageGetItem(page, lp);

        /* Set xmax to mark old tuple as "updated", set t_ctid to point to new tuple */
        htup->t_infomask &= ~(HEAP_XMAX_BITS | HEAP_MOVED);
        HeapTupleHeaderSetXmax(htup, xlrec->old_xmax);
        htup->t_ctid = newtid;
        /* ... infomask bit operations and HOT flag omitted ... */
    }

    /* === Step 2: Process new tuple — the prefix/suffix optimization === */
    if (newaction == BLK_NEEDS_REDO)
    {
        char *recdata = XLogRecGetBlockData(record, 0, &datalen);

        /* WAL may only record the changed portion; prefix/suffix reused from old tuple */
        if (xlrec->flags & XLH_UPDATE_PREFIX_FROM_OLD)
        {
            memcpy(&prefixlen, recdata, sizeof(uint16));
            recdata += sizeof(uint16);
        }
        if (xlrec->flags & XLH_UPDATE_SUFFIX_FROM_OLD)
        {
            memcpy(&suffixlen, recdata, sizeof(uint16));
            recdata += sizeof(uint16);
        }

        /* Reconstruct new tuple from: WAL delta + old tuple prefix + old tuple suffix */
        htup = &tbuf.hdr;
        if (prefixlen > 0)
        {
            /* Copy bitmap → copy unchanged prefix from old tuple → copy WAL delta */
            memcpy(newp, (char *) oldtup.t_data + oldtup.t_data->t_hoff,
                   prefixlen);
            /* ... detailed splicing omitted ... */
        }
        if (suffixlen > 0)
            memcpy(newp, (char *) oldtup.t_data + oldtup.t_len - suffixlen,
                   suffixlen);

        /* Insert the new tuple into the page */
        offnum = PageAddItem(page, (Item) htup, newlen, offnum, true, true);
        if (offnum == InvalidOffsetNumber)
            elog(PANIC, "failed to add tuple");
    }
}

The xl_heap_update structure captures the key metadata:

// File: src/include/access/heapam_xlog.h

typedef struct xl_heap_update
{
    TransactionId old_xmax;      /* xmax of the old tuple */
    OffsetNumber old_offnum;     /* offset of the old tuple */
    uint8       old_infobits_set;
    uint8       flags;
    TransactionId new_xmax;      /* xmax of the new tuple */
    OffsetNumber new_offnum;     /* offset of the new tuple */
} xl_heap_update;

Pay special attention to XLH_UPDATE_PREFIX_FROM_OLD and XLH_UPDATE_SUFFIX_FROM_OLD. When an UPDATE only changes a small slice in the middle of a tuple, WAL records only the delta — the unchanged prefix and suffix are reused from the old tuple. Replay must handle this correctly, or the reconstructed new tuple will be corrupted.

3.5 PRUNE Replay: Line Pointer Rearrangement — The Most Overlooked Critical Operation

PRUNE (page pruning) is the operation with the highest impact that is most easily overlooked. It redirects line pointers, marks them as DEAD or UNUSED, and can even compact page space. In PG18, the redo function is heap_xlog_prune_freeze:

// File: src/backend/access/heap/heapam_xlog.c

static void
heap_xlog_prune_freeze(XLogReaderState *record)
{
    xl_heap_prune xlrec;
    memcpy(&xlrec, XLogRecGetData(record), SizeOfHeapPrune);

    action = XLogReadBufferForRedoExtended(record, 0, RBM_NORMAL,
                    (xlrec.flags & XLHP_CLEANUP_LOCK) != 0, &buffer);

    if (action == BLK_NEEDS_REDO)
    {
        /* Deserialize pruning and freezing data from WAL */
        heap_xlog_deserialize_prune_and_freeze(dataptr, xlrec.flags,
                        &nplans, &plans, &frz_offsets,
                        &nredirected, &redirected,
                        &ndead, &nowdead,
                        &nunused, &nowunused);

        /* Core: redirect, mark dead, and mark unused line pointers */
        if (nredirected > 0 || ndead > 0 || nunused > 0)
            heap_page_prune_execute(buffer,
                        (xlrec.flags & XLHP_CLEANUP_LOCK) == 0,
                        redirected, nredirected,
                        nowdead, ndead,
                        nowunused, nunused);

        /* Freeze tuples per freeze plan (traversal logic omitted)... */

        PageSetLSN(page, lsn);
        MarkBufferDirty(buffer);
    }
}

The line pointer redirections inside heap_page_prune_execute are especially critical — for example, in a HOT chain, lp[1] may be redirected to lp[5]. If PRUNE replay is skipped, subsequent attempts to locate data via the DELETE record's offnum may point to the wrong location or an invalid region entirely.

---

Chapter 4: Locating the Deleted Data — Precision Navigation from WAL Records

4.1 The DELETE WAL Record Structure

When a DELETE is written to WAL, the core data structure is xl_heap_delete:

// File: src/include/access/heapam_xlog.h

/* xl_heap_delete flag values, 8 bits are available */
#define XLH_DELETE_ALL_VISIBLE_CLEARED   (1<<0)
#define XLH_DELETE_CONTAINS_OLD_TUPLE    (1<<1)
#define XLH_DELETE_CONTAINS_OLD_KEY      (1<<2)
#define XLH_DELETE_IS_SUPER              (1<<3)
#define XLH_DELETE_IS_PARTITION_MOVE      (1<<4)

typedef struct xl_heap_delete
{
    TransactionId xmax;         /* xmax of the deleted tuple */
    OffsetNumber offnum;        /* deleted tuple's offset within the page */
    uint8       infobits_set;   /* infomask bits to set */
    uint8       flags;          /* additional flags */
} xl_heap_delete;

What each field tells us:

• xmax: The transaction ID that performed the DELETE — who did it.
• offnum: The line pointer offset of the deleted tuple within the data page — this is the key that unlocks the deleted data.
• flags: Additional information — notably, XLH_DELETE_CONTAINS_OLD_TUPLE means the full old tuple was included (for logical replication scenarios).

The block reference in the WAL record provides the block number:

XLogRecGetBlockTag(record, 0, &target_locator, NULL, &blkno);

Combine blkno (which block) with offnum (which tuple within the block), and you have a precise address for the deleted row.

4.2 How the DELETE WAL Record Is Constructed

Inside the heap_delete function (src/backend/access/heap/heapam.c):

// File: src/backend/access/heap/heapam.c

if (RelationNeedsWAL(relation))
{
    xl_heap_delete xlrec;
    XLogRecPtr  recptr;

    /* Populate the DELETE WAL record structure */
    xlrec.flags = 0;
    if (all_visible_cleared)
        xlrec.flags |= XLH_DELETE_ALL_VISIBLE_CLEARED;
    xlrec.infobits_set = compute_infobits(tp.t_data->t_infomask,
                                          tp.t_data->t_infomask2);
    xlrec.offnum = ItemPointerGetOffsetNumber(&tp.t_self);  /* Key: record the offset */
    xlrec.xmax = new_xmax;

    XLogBeginInsert();
    XLogRegisterData(&xlrec, SizeOfHeapDelete);
    XLogRegisterBuffer(0, buffer, REGBUF_STANDARD);  /* Register buffer — may trigger FPW */

    /* If logical replication is enabled, old tuple data is also recorded (omitted)... */

    recptr = XLogInsert(RM_HEAP_ID, XLOG_HEAP_DELETE);
    PageSetLSN(page, recptr);
}

Note XLogRegisterBuffer(0, buffer, REGBUF_STANDARD) — this registers the current buffer. If this happens to be the first modification after a checkpoint, XLogRecordAssemble will automatically attach the entire page as an FPW to this DELETE's WAL record.

4.3 heap_xlog_delete: The DELETE Redo Function

heap_xlog_delete is our key reference for understanding how deleted data is located:

// File: src/backend/access/heap/heapam_xlog.c

static void
heap_xlog_delete(XLogReaderState *record)
{
    XLogRecPtr  lsn = record->EndRecPtr;
    xl_heap_delete *xlrec = (xl_heap_delete *) XLogRecGetData(record);

    /* Get the target block number and offset from the WAL record */
    XLogRecGetBlockTag(record, 0, &target_locator, NULL, &blkno);

    if (XLogReadBufferForRedo(record, 0, &buffer) == BLK_NEEDS_REDO)
    {
        page = BufferGetPage(buffer);

        /* Locate the deleted tuple via offnum — this is the critical navigation! */
        lp = PageGetItemId(page, xlrec->offnum);
        htup = (HeapTupleHeader) PageGetItem(page, lp);

        /* DELETE does not physically remove data — it only sets the xmax flag */
        htup->t_infomask &= ~(HEAP_XMAX_BITS | HEAP_MOVED);
        htup->t_infomask2 &= ~HEAP_KEYS_UPDATED;
        fix_infomask_from_infobits(xlrec->infobits_set,
                                   &htup->t_infomask, &htup->t_infomask2);
        HeapTupleHeaderSetXmax(htup, xlrec->xmax);
        /* ... Cmax setting and boundary checks omitted ... */

        PageSetLSN(page, lsn);
        MarkBufferDirty(buffer);
    }
    if (BufferIsValid(buffer))
        UnlockReleaseBuffer(buffer);
}

This code reveals a crucial fact: DELETE replay does not physically erase data — it merely stamps xmax onto the tuple header. The data remains fully intact on the page. All we need to do is:

1. Use offnum with PageGetItemId to find the line pointer
2. Use PageGetItem to get the tuple pointer
3. Read the tuple contents

At this point, the deleted data can be fully extracted.

---

Chapter 5: The Complete Recovery Pipeline — Five Steps to Recover Deleted Data

Bringing together every kernel mechanism discussed above, a complete DELETE data recovery pipeline can be distilled into five steps:

Step 1: Scan WAL, Build an Operation Index

Traverse the WAL files within the target range and record:

• Every DELETE-type record: LSN position, target table (rlocator), target block (blkno), and offset (offnum)
• Every WAL record carrying an FPW: position and corresponding block number
• Every intermediate operation affecting the target blocks (INSERT, UPDATE, PRUNE, etc.)

Step 2: Extract FPW as the Base Page

For each block involved in a deletion, locate the closest FPW that precedes the DELETE in time. Use the RestoreBlockImage logic to extract it from WAL and reconstruct the full 8KB page.

Step 3: Replay Intermediate Operations in Order

Apply all intermediate WAL records between the FPW and the DELETE to the base page, in LSN order. Reuse the kernel's redo logic:

• heap_xlog_insert — add tuples, extend line pointer array
• heap_xlog_update — mark old tuples, add new tuples, handle prefix/suffix optimization
• heap_xlog_prune_freeze — rearrange line pointers, freeze tuples
• Other operations that affect data layout

Step 4: Navigate to the Deleted Data via offnum

Extract the offset from xl_heap_delete.offnum and, on the fully replayed page, execute:

ItemId lp = PageGetItemId(page, offnum);      /* Get the line pointer */
HeapTupleHeader htup = (HeapTupleHeader) PageGetItem(page, lp); /* Get the tuple */

At this point, htup points to the complete data of the deleted tuple.

Step 5: Parse the Tuple, Restore User Data

Read the tuple header fields (t_infomask, t_hoff, etc.), skip the system columns (xmin, xmax, cmin, cmax, ctid), and parse each column's value according to the table's column definitions (types, lengths, and alignment from pg_attribute). The result is the user-readable row data.

For variable-length types (text, varchar, etc.), you may also need to handle TOAST external storage — TOASTed data lives in a companion TOAST table and requires additional lookup and reassembly.

---

Conclusion

The core logic of DELETE recovery can be summarized as follows:

FPW provides the base page snapshot, WAL replay advances the page to the precise state at deletion time, and xl_heap_delete.offnum locates the specific deleted tuple.

This mechanism has no dependency on dead tuples in data files, making it entirely immune to vacuum. As long as the WAL files are retained, recovery remains feasible.

A production-grade recovery tool is considerably more complex than what this article covers — it must handle cross-page UPDATEs, TOAST data, multiple FPW compression algorithms, logical replication edge cases, HOT chain traversal, and numerous boundary conditions. However, the core principle remains the same: the five-step pipeline described here forms the foundational framework of every WAL-based PostgreSQL DELETE recovery tool.

PDU (PostgreSQL Data Unloader) is an open-source PostgreSQL DELETE recovery tool built on the principles outlined above. It implements the complete recovery pipeline including FPW extraction, WAL replay, and tuple parsing. Readers interested in this area can refer to PDU's source code, or start from PostgreSQL's heapam_xlog.c to explore the WAL replay mechanism in greater depth.

When designing backup strategies, retaining sufficient WAL files is a critical measure for ensuring data recoverability.