Re: Review: GIN non-intrusive vacuum of posting tree

Hi, Jeff!

2017-02-05 3:45 GMT+05:00 Jeff Davis <pgsql(at)j-davis(dot)com>:
> On Sun, Jan 22, 2017 at 10:32 PM, Jeff Davis <pgsql(at)j-davis(dot)com> wrote:
>> On Sat, Jan 21, 2017 at 4:25 AM, Andrew Borodin <borodin(at)octonica(dot)com> wrote:
>> One idea I had that might be simpler is to use a two-stage page
>> delete. The first stage would remove the link from the parent and mark
>> the page deleted, but leave the right link intact and prevent
>> recycling. The second stage would follow the chain of right links
>> along each level, removing the right links to deleted pages and
>> freeing the page to be recycled.
>
> Do you think this approach is viable as a simplification?

To consider this approach I need to ask several questions.

1. Are we discussing simplification of existing GIN vacuum? Or
proposed GIN vacuum? Please, note that they do not differ in the way
page is unlinked, function ginDeletePage() is almost untoched.

2. What do you mean by "stage"? In terms of the paper "A symmetric
concurrent B-tree algorithm" by Lanin&Shasha: stage is an
uninterrupted period of holding lock on nonempty page set.
Here's the picture https://www.screencast.com/t/xUpGKgkkU from L&S
Both paper (L&Y and L&S) tend to avoid lock coupling, which is
inevitable if you want to do parent unlink first. To prevent insertion
of records on a page, you have to mark it. If you are doing this in
the stage when you unlink from parent - you have to own both locks.

3. What do you want to simplify? Currently we unlink a page from
parent and left sibling in one stage, at cost of aquiring CleanUp lock
(the way we aquire it - is the diference between current and patched
version).
2-stage algorithms will not be simplier, yet it will be more concurrent.
Please note, that during absence of high fence keys in GIN B-tree we
actually should implement algorithm from figure 3A
https://www.screencast.com/t/2cfGZtrzaz0z (It would be incorrect, but
only with presence of high keys)

Best regards, Andrey Borodin.