Re: Failure while inserting parent tuple to B-tree is not fun

On 25.10.2013 22:13, Heikki Linnakangas wrote:
> On 22.10.2013 19:55, Heikki Linnakangas wrote:
>> I fixed the the same problem in GiST a few years back, by making it
>> tolerate missing downlinks, and inserting them lazily. The B-tree code
>> tolerates them already on scans, but gets confused on insertion, as seen
>> above. I propose that we use the same approach I used with GiST, and add
>> a flag to the page header to indicate "the downlink hasn't been inserted
>> yet". When insertion (or vacuum) bumps into a flagged page, it can
>> finish the incomplete action by inserting the downlink.
>
> This is what I came up with.
>
> One thing I'm not totally happy about is the way page deletions of
> incompletely split pages are handled. Basically, it just bails out and
> refuses to delete a page that is part of an incomplete split. That's
> probably OK in practice, as incomplete splits should be very rare
> anyway, but it's a bit dissatisfying to not handle the case because at
> first glance it seems like it should be even simpler than usual to
> delete a page that has no downlink. Nevertheless, I decided to just skip
> that for now.
>
> After this patch, deleting the only child of a parent and the parent
> itself is still a multi-WAL-record operation that needs to be tracked
> during recovery, and completed at the end of recovery. I'd like to
> eliminate that too, but that's another patch.

Here's a new version of this, which uses a similar technique to handle
page deletions, eliminating the "incomplete action" tracking code
altogether (from btree). When an internal page is marked as half-dead,
its right sibling is atomically marked with a
"left-sibling-is-half-dead" flag. Whenever an insertion encounters a
page with that flag set, it will finish the deletion of the left sibling
before proceeding with the insertion.

This needs a lot more testing, but I wanted to get this out for review,
in case someone sees a fundamental problem with this.

- Heikki