Re: GiST insert algorithm rewrite

> 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
Hm, performance? while you traverse to leaf page, on each inner page you will
need to call unionFn/equalFn methods to decide update or not key on inner page.
Now we stops do that after first positive result of equalFn while walking up.
Next, when child page splits then you need to update parent twice - first time
while walk down, and second while walk up.

As I see, you try to implement algorithm very close to original, but it was
rather slow.
http://git.postgresql.org/gitweb?p=postgresql.git;a=commit;h=0ad7db4be4b1f0208271c49fc1c8348f11ebc5b3

> 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
Again, twice write of new children (it could be several because of
implementation of user-defined picksplit method).

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/