Date: Tue, 24 Oct 2023 20:04:59 -0700
From: Noah Misch <noah@leadboat.com>
To: Peter Geoghegan <pg@bowt.ie>
Cc: pgsql-hackers@postgresql.org, Alexander Korotkov <aekorotkov@gmail.com>
Subject: Re: post-recovery amcheck expectations
Message-ID: <20231025030459.6f@rfd.leadboat.com>
References: <20231005025232.c7.nmisch@google.com>
 <CAH2-Wz=e4WihDXD6-aKW7dgVyQ0dNcnW5BWJZBKvw7Mmrcv59Q@mail.gmail.com>
 <20231021035457.cb.nmisch@google.com>
 <CAH2-WznBJZQxKRYgtMDAhre-R4YasPNqXGy=g_yNQGKLHP9C2Q@mail.gmail.com>
 <20231024022848.87.nmisch@google.com>
 <CAH2-WzmQJoLRSN6xTtK6ROyhDEX-m0+z8WJ8hSDtgrc4moVsRg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: 
 <CAH2-WzmQJoLRSN6xTtK6ROyhDEX-m0+z8WJ8hSDtgrc4moVsRg@mail.gmail.com>
User-Agent: Mutt/2.2.12 (2023-09-09)
Archived-At: 
 <https://www.postgresql.org/message-id/20231025030459.6f%40rfd.leadboat.com>
Precedence: bulk

On Tue, Oct 24, 2023 at 07:03:34PM -0700, Peter Geoghegan wrote:
> On Mon, Oct 23, 2023 at 7:28 PM Noah Misch <noah@leadboat.com> wrote:
> > > That makes sense to me. I believe that it's not possible to have a
> > > string of consecutive sibling pages that are all half-dead (regardless
> > > of the BlockNumber order of sibling pages, even). But I'd probably
> > > have written the fix in roughly the same way. Although...maybe you
> > > should try to detect a string of half-dead pages? Hard to say if it's
> > > worth the trouble.
> >
> > I imagined a string of half-dead siblings could arise in structure like this:
> >
> >  *               1
> >  *          /    |    \
> >  *         4 <-> 2 <-> 3
> >
> > With events like this:
> >
> > - DELETE renders blk 4 deletable.
> > - Crash with concurrent VACUUM, leaving 4 half-dead after having visited 1-4.
> > - DELETE renders blk 2 deletable.
> > - Crash with concurrent VACUUM, leaving 2 half-dead after having visited 1-2.
> >
> > I didn't try to reproduce that, and something may well prevent it.
> 
> FWIW a couple of factors prevent it (in the absence of corruption). These are:
> 
> 1. Only VACUUM can delete pages, and in general the only possible
> source of half-dead pages is an unfortunately timed crash/error within
> VACUUM. Each interrupted VACUUM can leave behind at most one half-dead
> page.

Agreed.

> 2. One thing that makes VACUUM back out of deleting an empty page is
> the presence of a half-dead right sibling leaf page left behind by
> some VACUUM that was interrupted at some point in the past -- see
> _bt_rightsib_halfdeadflag() for details.
> 
> Obviously, factors 1 and 2 together make three consecutive half-dead
> sibling pages impossible.

Can't it still happen if the sequence of unfortunately timed crashes causes
deletions from left to right?  Take this example, expanding the one above.
Half-kill 4, crash, half-kill 3, crash, half-kill 2 in:

 *                  1
 *           /    / | \    \
 *         4 <-> 3 <-> 2 <-> 1

(That's not to say it has ever happened outside of a test.)