Re: GiST insert algorithm rewrite

Heikki Linnakangas <heikki(dot)linnakangas(at)enterprisedb(dot)com> writes:
> There are two key changes to the insert algorithm:

> 1. When we walk down the tree searching for a suitable leaf page to
> insert the new tuple to, we update the nodes on the way down so that
> they are consistent with the new key we're inserting. The old GiST
> algorithm adjusted all the parent pages only after inserting the tuple
> on the leaf. Updating them on the way down ensures that the tree is
> self-consistent at all times, even if we crash just after inserting the
> new tuple on the leaf page.

> 2. When a page is split, we mark the new left page with a flag to
> indicate that the downlink for the page to the right hasn't been
> inserted yet. When the downlink is inserted, the flag is cleared. Again
> the purpose is to ensure that the tree is self-consistent at all times.
> If we crash just after a page split, before the downlink is inserted,
> scans will find the tuples on the right page by following the rightlink.
> It's slightly less performant, but correct.

The one thought that comes to mind is how does the flag business work
after multiple splittings? That is, assume we have a page that has the
flag set because of a previous crash. If we have to split either that
page or its right sibling, what do we do with the flags? I think that
it can be made to work, so long as searches keep moving right as long
as the flag is set. But this needs to be thought through, and
documented in the README file. I'm particularly worried whether the
after-the-fact fixup that you mention in README might fail in such
scenarios.

regards, tom lane