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

2017-01-24 22:29 GMT+05:00 Jeff Davis <pgsql@j-davis.com>:
> On Tue, Jan 24, 2017 at 3:18 AM, Andrew Borodin <borodin@octonica.com> wrote:
>> Technically, approach of locking a subtree is not novel. Lehman and
>> Yao focused on "that any process for manipulating the tree uses only a
>> small (constant) number of locks at any time." We are locking unknown
>> and possibly large amount of pages.
>
> By the way, can you show me where the Lehman and Yao paper addresses
> page recycling?
>
> It says that one approach is to allow fewer than K entries on a leaf
> node; presumably as few as zero. But it doesn't seem to show how to
> remove all references to the page and recycle it in a new place in the
> tree.
>
> Regards,
>      Jeff Davis

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