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

On 2/5/17 11:04 AM, Andrew Borodin wrote:
> 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)

This patch applies cleanly and compiles at cccbdde.

Jeff, any thoughts on Andrew's responses?

--
-David
david(at)pgmasters(dot)net