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

On Sat, Jan 21, 2017 at 4:25 AM, Andrew Borodin <borodin(at)octonica(dot)com> wrote:
> Hello Jeff!
>
>>Review of the code itself:
> How do you think, is there anything else to improve in that patch or
> we can mark it as 'Ready for committer'?
>
> I've checked the concurrency algorithm with original work of Lehman
> and Yao on B-link-tree. For me everything looks fine (safe, deadlock
> free and not increased probability of livelock due to
> LockBufferForCleanup call).

Hi,

I looked at the patch some more.

I have some reservations about the complexity and novelty of the
approach. I don't think I've seen an approach quite like this one
before. It seems like the main reason you are using this approach is
because the btree structure was too simple (no left links); is that
right? My gut is telling me we should either leave it simple, or use a
real concurrent btree implementation.

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.

Another idea is to partition the posting tree so that the root page
actually points to K posting trees. Scans would need to merge them,
but it would allow inserts to progress in one tree while the other is
being vacuumed. I think this would give good concurrency even for K=2.
I just had this idea now, so I didn't think it through very well.

What do you think?

Regards,
Jeff Davis