Re: GiST insert algorithm rewrite

On 16.11.2010 21:20, Teodor Sigaev wrote:
>> 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.

Hmm, will have to do some benchmarking on that. I'm using the Consistent
function when walking down to check if the downlink needs to be updated,
and assumed that it would be insignificant compared to the cost of
calling Penalty on all the keys on the page.

> 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

Thanks for that, I'll have to read that through as well.

>> 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).

There should be no difference in performance here AFAICS. The children
need to be updated a second time to clear the flag, but we don't release
the locks on them in the middle, and we're only talking about setting a
single flag, so it should make no difference.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com