_bt_parent_deletion_safe() isn't safe

The btree page deletion logic has a restriction that it cannot delete
the rightmost child page of any non-leaf btree page (see nbtree/README
for explanations). This is checked by _bt_parent_deletion_safe(),
which claims

* Note: it's OK to release page locks after checking, because a safe
* deletion can't become unsafe due to concurrent activity. A non-rightmost
* page cannot become rightmost unless there's a concurrent page deletion,
* but only VACUUM does page deletion and we only allow one VACUUM on an index
* at a time. An only child could acquire a sibling (of the same parent) only
* by being split ... but that would make it a non-rightmost child so the
* deletion is still safe.

This analysis missed a case, though. What if an insertion into some
nearby leaf page causes a split, and the resulting insertion into the
parent page causes it to split, and we choose a split point just after
the downlink for the page that VACUUM is trying to delete? That will
leave the deletion target as the rightmost child, and we're screwed.

I realized this while thinking about Jeff Amiel's report here:
http://archives.postgresql.org/pgsql-general/2010-06/msg00351.php
I can't prove that this is what's causing his crashes, but it could
produce the symptom he's reporting. And it'd also explain the
observation that the crash doesn't recur when autovacuum tries again,
since at that time it'll see the page as a rightmost child and not try
to delete it. Maybe the reason he's seeing it repeatedly is that in his
installation the deletions lag behind insertions at about the right rate
for the problem case to occur.

Right at the moment I'm not seeing a fix other than to have page
deletion hold lock on the parent page till it's done. That's unpleasant
from a concurrency standpoint. Anybody see a better way?

regards, tom lane