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
0001-Delete-GIN-posting-tree-pages-without-locking-out-th.patch
Description: Binary data
0002-Add-isolation-test-for-GIN-posting-tree-page-deletio.patch
Description: Binary data
0003-Add-deadlock-provocation-tests-for-GIN-posting-tree-.patch
Description: Binary data
