Race condition in b-tree page deletion

The B-tree page deletion algorithm has a race condition. We don't allow 
a page to be deleted if it's the rightmost child of its parent, but that 
situation can change after we check for it.

Problem
-------

We check that the page to be deleted is not the rightmost child of its 
parent, and then lock its left sibling, the page itself, its right 
sibling, and the parent, in that order. However, if the parent page is 
split after the check but before acquiring the locks, the target page 
might become the rightmost child, if the split happens at the right 
place. That leads to an error in vacuum (I reproduced this by setting a 
breakpoint in debugger):

ERROR:  failed to delete rightmost child 41 of block 3 in index "foo_pkey"

We currently re-check that the page is still the rightmost child, and 
throw the above error if it's not. We could easily just give up rather 
than throw an error, but that approach doesn't scale to half-dead pages. 
To recap, although we don't normally allow deleting the rightmost child, 
if the page is the *only* child of its parent, we delete the child page 
and mark the parent page as half-dead in one atomic operation. But 
before we do that, we check that the parent can later be deleted, by 
checking that it in turn is not the rightmost child of the grandparent 
(potentially recursing all the way up to the root). But the same 
situation can arise there - the grandparent can be split while we're not 
holding the locks. We end up with a half-dead page that we cannot delete.

To make things worse, the keyspace of the deleted page has already been 
transferred to its right sibling. As the README points out, the keyspace 
at the grandparent level is "out-of-whack" until the half-dead page is 
deleted, and if enough tuples with keys in the transferred keyspace are 
inserted, the page might get split and a downlink might be inserted into 
the grandparent that is out-of-order. That might not cause any serious 
problem if it's transient (as the README ponders), but is surely bad if 
it stays that way.

Solutions
---------

1. The simplest solution I can see is to never delete internal pages, 
avoiding the whole concept of half-dead pages. That obviously leads to 
some bloat, though.

2. The second-simplest solution I see is to keep locked the whole chain 
of pages that will be deleted, and delete all of them as one atomic 
WAL-logged operation. Ie. the leaf page, and all the parent pages above 
it that will become half-dead, and the parent of the last half-dead page.

3. Another approach would be to get rid of the "can't delete rightmost 
child" limitation. We currently have that limitation because it ensures 
that we never need to change the high-key of a page. If we delete a page 
that is the rightmost child of its parent, we transfer the deleted 
keyspace from the parent page to its right sibling. To do that, we need 
to update the high key of the parent, as well as the downlink of the 
right sibling at the grandparent level. That's a bit complicated, 
because updating the high key might require splitting the page.

Still, I think it would be doable: When we delete a page that is the 
rightmost child of its parent, we mark the right sibling with an 
"out-of-whack" flag. It indicates that the keyspace of that page is not 
in sync in the parent level. Searches work fine, as there are no keys in 
the keyspace that is out-of-whack, but before allowing any insertions to 
the page, the situation needs to be fixed. That is the responsibility of 
the next insert to the page that comes along. To fix it, the parent's 
left sibling's high key needs to be updated, as well as the parent's 
downlink in the grandparent. We can do that in a few discrete steps; 
first update the high key, then update the downlink, and finally once 
the high key and parent's downlink are in sync with the reality at the 
bottom level, clear the "out-of-whack" flag.

On reflection, approach 2 seems best. It's fairly simple, although it 
potentially requires holding many pages locked simultaneously. In 
practice, B-trees are typically not very deep. We have a limit of 4 
full-page images in a single WAL record, but since all the pages are 
empty, we can just WAL-log all the information needed to reconstruct the 
pages in deleted state without using full-page images. This also might 
be back-patchable, although it requires changing the WAL record format, 
so it would break replication from higher minor version to lower.

- Heikki