Re: [HACKERS] Review: GIN non-intrusive vacuum of posting tree

2017-01-25 12:09 GMT+05:00 Andrew Borodin <borodin@octonica.com>:
> 2017-01-24 22:29 GMT+05:00 Jeff Davis <pgsql@j-davis.com>:
>> By the way, can you show me where the Lehman and Yao paper addresses
>> page recycling?
>
> Here J. Hellerstein comments L&Y paper [1] saying that effectively
> there is no deletion algorithm provided.
> Here [2] is paper referenced from nbtree docs. I'll check if this is
> applicable to GIN B-tree.
>
> [1] http://db.cs.berkeley.edu/jmh/cs262b/treeCCR.html
> [2] http://dl.acm.org/citation.cfm?id=324589

Hi!

I'll summarize here my state of studying concurrent methods of page unlinking.

GIN B-tree does not have "high key". That means, that rightmost key on
a page is maximal for the non-leaf page.
But I do not see anything theoretical in a way of implementation of
Lanin and Shasha`s methods of page merging, with slight modifications.
Their paper does not even mention high key(high fence key in papers by
Goetz Graefe).

But it's not a simple task due to large portions of shared code
between entry tree and posting tree.

Also, I do not see a reason why this method can be practically
superior to proposed patch.

Currently, I do not have resources to implement a proof of concept for
fully concurrent page unlinking to make benchmarking.

Best regards, Andrey Borodin.