Delete GIN posting tree pages without excessive locking

Hi hackers,

Back in 2016 I was working on GIN locking to fix a production problem
in Yandex.Mail (folder search backed by GIN indexes). That fix turned
out to be incorrect, and most of the optimizations were reverted in
fd83c83d094. While working on the revert I also had put together a
patch with a full page deletion protocol for posting trees, but what
remained after fd83c83d094 was enough to solve the production
problems, so I never did anything with it.

Recently thread[0] reminded me of that patch. Is anyone interested in this
technology - vacuuming a posting tree without blocking SELECTs?
Currently, deleting empty posting tree pages takes a cleanup lock on
the tree root for a whole pass over the tree, blocking all searches
and insertions in it, uninterruptibly. I'm happy to work on the patch
if anyone actually suffers from this; if not, I'm posting it anyway,
for the historical record.

Also, it is not 2018 anymore: now we have amcheck for GIN and
injection points, and maybe I'm somewhat less foolish (that's
not certain). Getting this right should be easier than it was almost
a decade ago.

How it works (0001): empty leaf pages are deleted on the fly during
the regular left-to-right vacuum sweep of the leaf level. The sweep
couples leaf locks in the same left-to-right order used everywhere
else in GIN; the parent is found by walking right along the level
above the leaves. A page is deleted only if nobody else holds a pin
on it. The leftmost and rightmost leaves, leaves referenced by the
last downlink of their parent, and internal pages are never deleted.
An inserter that reaches a deleted page through a stale downlink
recovers by moving right; the existing XID stamping of deleted pages
prevents premature reuse.

How it is tested (0002, 0003): isolation tests in src/test/modules/gin
built on injection points. 0002 covers the baseline deletion path and
checks that searches and insertions into the same posting tree proceed
while vacuum is paused mid-sweep; the structure is verified with
amcheck's gin_index_check(). 0003 adds two deadlock provocations:
each suspends one side of the would-be lock cycle at its maximal lock
footprint (vacuum just before a page deletion, holding the leaf pair
and the parent; an inserter finishing an incomplete split, holding the
leaf) and drives the other side into the held locks. I think a
regression in the locking protocol would make these tests hang.

Is anyone interested?

Best regards, Andrey Borodin.

[0] https://www.postgresql.org/message-id/flat/178447127453.110.12276981925360691905%40mail.gmail.com