=== Applying patches on top of PostgreSQL commit ID 3c982c9bf1af994090a181c68f9407ff39d3ddf7 === /etc/rc.d/jail: WARNING: Per-jail configuration via jail_* variables is obsolete. Please consider migrating to /etc/jail.conf. Tue Aug 25 18:48:35 UTC 2026 On branch cf/7199 nothing to commit, working tree clean === using 'git am' to apply patch ./0001-Delete-GIN-posting-tree-pages-without-locking-out-th.patch === Applying: Delete GIN posting tree pages without locking out the whole tree Using index info to reconstruct a base tree... M src/backend/access/gin/ginvacuum.c Falling back to patching base and 3-way merge... Auto-merging src/backend/access/gin/ginvacuum.c CONFLICT (content): Merge conflict in src/backend/access/gin/ginvacuum.c error: Failed to merge in the changes. hint: Use 'git am --show-current-patch=diff' to see the failed patch Patch failed at 0001 Delete GIN posting tree pages without locking out the whole tree When you have resolved this problem, run "git am --continue". If you prefer to skip this patch, run "git am --skip" instead. To restore the original branch and stop patching, run "git am --abort". === using patch(1) to apply patch ./0001-Delete-GIN-posting-tree-pages-without-locking-out-th.patch === patching file src/backend/access/gin/README patching file src/backend/access/gin/ginbtree.c patching file src/backend/access/gin/ginvacuum.c Hunk #2 FAILED at 220. 1 out of 2 hunks FAILED -- saving rejects to file src/backend/access/gin/ginvacuum.c.rej Unstaged changes after reset: M src/backend/access/gin/README M src/backend/access/gin/ginbtree.c M src/backend/access/gin/ginvacuum.c Removing src/backend/access/gin/ginvacuum.c.rej === using 'git apply' to apply patch ./0001-Delete-GIN-posting-tree-pages-without-locking-out-th.patch === Applied patch to 'src/backend/access/gin/README' cleanly. Applied patch to 'src/backend/access/gin/ginbtree.c' cleanly. Applied patch to 'src/backend/access/gin/ginvacuum.c' with conflicts. U src/backend/access/gin/ginvacuum.c diff --cc src/backend/access/gin/ginvacuum.c index 2cd4e50aa61,ca4c2c4d953..00000000000 --- a/src/backend/access/gin/ginvacuum.c +++ b/src/backend/access/gin/ginvacuum.c @@@ -249,156 -220,105 +222,134 @@@ ginDeletePostingPage(GinVacuumState *gv /* - * Scans a posting tree and deletes empty pages. - * - * The caller must hold a cleanup lock on the root page to prevent concurrent - * inserts. The entire path from the root down to the current page is kept - * exclusively locked throughout the scan. The left sibling at each level is - * also kept locked, because ginDeletePostingPage() needs it to update the - * rightlink of the left sibling; re-acquiring the left sibling lock later - * could deadlock with ginStepRight(), which acquires page locks - * left-to-right. + * Descend from the posting tree root to its leftmost leaf page. * - * All per-level state is carried in 'myStackItem': the buffer to process - * (must already be pinned and exclusively locked), the left sibling buffer, - * and this page's offset in the parent's downlink array. The root entry is - * set up by ginVacuumPostingTree(); child entries are populated here before - * recursing. + * On return, the leftmost leaf is pinned and exclusively locked, and + * *parentBlkno is set to the block number of its parent (the leftmost + * internal page one level above the leaves), or InvalidBlockNumber if the + * root itself is a leaf. * - * Returns true if the page was deleted, false otherwise. + * The leftmost path is stable: page splits move keyspace to the right, and + * the leftmost page of each level is never deleted (see README), so the + * downlinks we follow cannot go away under us. */ - static bool - ginScanPostingTreeToDelete(GinVacuumState *gvs, DataPageDeleteStack *myStackItem) + static Buffer + ginStepToLeftmostLeaf(GinVacuumState *gvs, BlockNumber rootBlkno, + BlockNumber *parentBlkno) { - Buffer buffer = myStackItem->buffer; - Page page; - bool pageWasDeleted = false; - bool isempty; + BlockNumber blkno = rootBlkno; - page = BufferGetPage(buffer); + *parentBlkno = InvalidBlockNumber; - Assert(GinPageIsData(page)); - - if (!GinPageIsLeaf(page)) + while (true) { - OffsetNumber i; - - for (i = FirstOffsetNumber; i <= GinPageGetOpaque(page)->maxoff;) - { - PostingItem *pitem = GinDataPageGetPostingItem(page, i); - Buffer childBuffer; + Buffer buffer; + Page page; + PostingItem *pitem; - childBuffer = ReadBufferExtended(gvs->index, - MAIN_FORKNUM, - PostingItemGetBlockNumber(pitem), - RBM_NORMAL, gvs->strategy); - LockBuffer(childBuffer, GIN_EXCLUSIVE); + buffer = ReadBufferExtended(gvs->index, MAIN_FORKNUM, blkno, + RBM_NORMAL, gvs->strategy); + LockBuffer(buffer, GIN_SHARE); + page = BufferGetPage(buffer); - /* Allocate a child stack entry on first use; reuse thereafter */ - if (!myStackItem->child) - { - myStackItem->child = palloc0_object(DataPageDeleteStack); - myStackItem->child->parent = myStackItem; - myStackItem->child->leftBuffer = InvalidBuffer; - } + Assert(GinPageIsData(page)); - myStackItem->child->buffer = childBuffer; - myStackItem->child->isRoot = false; - myStackItem->child->myoff = i; + if (GinPageIsLeaf(page)) + { + LockBuffer(buffer, GIN_UNLOCK); + LockBuffer(buffer, GIN_EXCLUSIVE); /* - * Recurse into child. If the child page was deleted, its - * downlink was removed from our page, so re-examine the same - * offset; otherwise advance to the next downlink. + * While the page was unlocked, a concurrent insert could have + * turned the root into an internal page. Retry from the same + * block if so. (Non-root pages never change their leaf-ness.) */ - if (!ginScanPostingTreeToDelete(gvs, myStackItem->child)) - i++; - } - myStackItem->buffer = InvalidBuffer; + if (GinPageIsLeaf(page)) + return buffer; - /* - * After processing all children at this level, release the child - * level's leftBuffer if we're at the rightmost page. There is no - * right sibling that could need it for deletion. - */ - if (GinPageRightMost(page) && BufferIsValid(myStackItem->child->leftBuffer)) - { - UnlockReleaseBuffer(myStackItem->child->leftBuffer); - myStackItem->child->leftBuffer = InvalidBuffer; + UnlockReleaseBuffer(buffer); + continue; } - } - if (GinPageIsLeaf(page)) - isempty = GinDataLeafPageIsEmpty(page); - else - isempty = GinPageGetOpaque(page)->maxoff < FirstOffsetNumber; + Assert(PageGetMaxOffsetNumber(page) >= FirstOffsetNumber); ++<<<<<<< ours + if (isempty) + { + /* + * Proceed to the ginDeletePostingPage() if target page is not the + * leftmost or the rightmost page. + * + * leftBuffer is the target's left sibling according to the parent + * level, which is not necessarily its left sibling in the sibling + * link chain (the rightlinks stored on pages): the new right half of + * an incompletely split page is in the sibling chain, but has no + * downlink yet. ginDeletePostingPage isn't prepared to deal with + * that, so we must refuse to delete when either the target or its + * left sibling page is marked incompletely split. + */ + if (BufferIsValid(myStackItem->leftBuffer) && !GinPageRightMost(page) && + !GinPageIsIncompleteSplit(page) && + !GinPageIsIncompleteSplit(BufferGetPage(myStackItem->leftBuffer))) + { + Assert(!myStackItem->isRoot); + ginDeletePostingPage(gvs, buffer, myStackItem->leftBuffer, + myStackItem->parent->buffer, + myStackItem->myoff, + myStackItem->parent->isRoot); + pageWasDeleted = true; + } + } ++======= + *parentBlkno = blkno; + pitem = GinDataPageGetPostingItem(page, FirstOffsetNumber); + blkno = PostingItemGetBlockNumber(pitem); + Assert(blkno != InvalidBlockNumber); ++>>>>>>> theirs - if (!pageWasDeleted) - { - /* - * Keep this page as the new leftBuffer for this level: the next - * sibling to the right might need it for deletion. Release any - * previously held left page first. - */ - if (BufferIsValid(myStackItem->leftBuffer)) - UnlockReleaseBuffer(myStackItem->leftBuffer); - myStackItem->leftBuffer = buffer; - } - else - { - /* - * Page was deleted; release the buffer. leftBuffer remains the same. - */ UnlockReleaseBuffer(buffer); } - - return pageWasDeleted; } - /* - * Scan through posting tree leafs, delete empty tuples. Returns true if there - * is at least one empty page. + * Find and exclusively lock the parent of leaf page leafBlkno, in + * preparation for deleting the leaf. + * + * *parentBlkno is used as a search hint, pointing to some page of the + * internal level immediately above the leaves, at or to the left of the + * parent we are looking for. Because downlinks only ever move right (when + * internal pages split) and our caller processes the leaves in + * left-to-right order, the hint page from a previous call remains valid. + * The search walks right from the hint until the downlink is found. + * + * On success, returns the pinned and exclusively locked parent buffer, + * sets *off to the downlink's offset, and advances *parentBlkno to the + * parent's block number. Returns InvalidBuffer (with *parentBlkno + * unchanged, so that searches for subsequent leaves can still succeed) if: + * + * - the downlink was not found (e.g. the leaf's split was never completed, + * so the downlink was never inserted); or + * + * - the downlink is the last one on the parent page. Posting tree internal + * pages have no high keys; dataLocateItem() treats the last downlink as + * having no upper bound ("right infinity"). Removing it would cut the + * parent's keyspace short, sending insertions of keys between the + * remaining downlinks and the parent's right bound to pages under the + * parent's right sibling, corrupting the key order of the tree. So the + * last downlink, and thereby the page it points to, must stay. */ - static bool - ginVacuumPostingTreeLeaves(GinVacuumState *gvs, BlockNumber blkno) + static Buffer + ginLockLeafParent(GinVacuumState *gvs, BlockNumber *parentBlkno, + BlockNumber leafBlkno, OffsetNumber *off) { - Buffer buffer; - Page page; - bool hasVoidPage = false; - MemoryContext oldCxt; + BlockNumber blkno = *parentBlkno; - /* Find leftmost leaf page of posting tree and lock it in exclusive mode */ - while (true) + while (BlockNumberIsValid(blkno)) { - PostingItem *pitem; + Buffer buffer; + Page page; + OffsetNumber i, + maxoff; buffer = ReadBufferExtended(gvs->index, MAIN_FORKNUM, blkno, RBM_NORMAL, gvs->strategy); @@@ -406,58 -326,113 +357,139 @@@ page = BufferGetPage(buffer); Assert(GinPageIsData(page)); + Assert(!GinPageIsLeaf(page)); - if (GinPageIsLeaf(page)) + maxoff = GinPageGetOpaque(page)->maxoff; + for (i = FirstOffsetNumber; i <= maxoff; i++) { ++<<<<<<< ours + LockBuffer(buffer, GIN_UNLOCK); + LockBuffer(buffer, GIN_EXCLUSIVE); + + if (!GinPageIsLeaf(page)) + { + /* + * The root page was a leaf page, but became an internal page + * while no lock was held. Unlock and reacquire a share lock. + */ + UnlockReleaseBuffer(buffer); + continue; + } + break; + } ++======= + PostingItem *pitem = GinDataPageGetPostingItem(page, i); ++>>>>>>> theirs - Assert(PageGetMaxOffsetNumber(page) >= FirstOffsetNumber); - - pitem = GinDataPageGetPostingItem(page, FirstOffsetNumber); - blkno = PostingItemGetBlockNumber(pitem); - Assert(blkno != InvalidBlockNumber); + if (PostingItemGetBlockNumber(pitem) == leafBlkno) + { + /* never delete the last downlink of an internal page */ + if (i == maxoff) + { + UnlockReleaseBuffer(buffer); + return InvalidBuffer; + } + + *parentBlkno = blkno; + *off = i; + return buffer; + } + } + blkno = GinPageGetOpaque(page)->rightlink; UnlockReleaseBuffer(buffer); } - /* Iterate all posting tree leaves using rightlinks and vacuum them */ - while (true) + return InvalidBuffer; + } + + /* + * Vacuum a posting tree: remove deletable TIDs from its leaf pages, and + * delete leaf pages that become completely empty. + * + * The leaves are processed in a single left-to-right sweep by following + * rightlinks, holding exclusive locks on the current page and its right + * sibling at once (lock coupling). Keeping the left sibling locked while + * acquiring the right one both pins down the sibling link needed for the + * deletion and follows the left-to-right page locking order used everywhere + * else in GIN, so it cannot deadlock with concurrent insertions or searches. + * + * A page is deleted only if, in addition to being empty, no other backend + * holds a pin on it (IsBufferCleanupOK), so nobody is about to insert into + * or read from it. If somebody does, we just leave the page in place; a + * future vacuum can delete it. + * + * Empty leaves are deleted right away, except for pages that must survive + * for the tree to stay navigable: the leftmost leaf (fullScan descents + * cannot recover from stepping onto a deleted page), the rightmost leaf, + * and leaves referenced by the last downlink of their parent (see + * ginLockLeafParent). Internal pages are never deleted; without high keys + * their empty siblings cannot be spliced out safely. Concurrent inserters + * and searchers that run into a page we deleted recover by moving right, + * as deleted pages keep their rightlink (see README). + */ + static void + ginVacuumPostingTree(GinVacuumState *gvs, BlockNumber rootBlkno) + { + BlockNumber parentBlkno; + Buffer prevBuffer; + Page prevPage; + MemoryContext oldCxt; + + prevBuffer = ginStepToLeftmostLeaf(gvs, rootBlkno, &parentBlkno); + prevPage = BufferGetPage(prevBuffer); + + /* The leftmost leaf is never deleted, just vacuum its tuples */ + oldCxt = MemoryContextSwitchTo(gvs->tmpCxt); + ginVacuumPostingTreeLeaf(gvs->index, prevBuffer, gvs); + MemoryContextSwitchTo(oldCxt); + MemoryContextReset(gvs->tmpCxt); + + while (!GinPageRightMost(prevPage)) { - oldCxt = MemoryContextSwitchTo(gvs->tmpCxt); - ginVacuumPostingTreeLeaf(gvs->index, buffer, gvs); - MemoryContextSwitchTo(oldCxt); - MemoryContextReset(gvs->tmpCxt); + BlockNumber prevBlkno = BufferGetBlockNumber(prevBuffer); + BlockNumber blkno; + Buffer buffer; + Page page; - if (GinDataLeafPageIsEmpty(page)) - hasVoidPage = true; + /* + * Come up for air: release all locks and pins before the delay + * point, both to let it process interrupts (which is impossible + * while a buffer lock is held) and to avoid blocking readers of + * this page while cost-based vacuum delay makes us sleep. + * + * Only vacuum deletes posting tree pages, and there is at most one + * vacuum per index, so the page is still there when we re-lock it. + * If it was concurrently split, the pages that were split off to + * the right contain only tuples that we have already vacuumed, so + * it is fine to continue from the page's new rightlink. + */ + UnlockReleaseBuffer(prevBuffer); - blkno = GinPageGetOpaque(page)->rightlink; + vacuum_delay_point(false); - UnlockReleaseBuffer(buffer); + prevBuffer = ReadBufferExtended(gvs->index, MAIN_FORKNUM, prevBlkno, + RBM_NORMAL, gvs->strategy); + LockBuffer(prevBuffer, GIN_EXCLUSIVE); + prevPage = BufferGetPage(prevBuffer); - if (blkno == InvalidBlockNumber) + if (GinPageRightMost(prevPage)) break; + blkno = GinPageGetOpaque(prevPage)->rightlink; /* ++<<<<<<< ours + * A safe point to delay/accept interrupts: the previous page has been + * unlocked and released, so we hold no buffer content lock (nor any + * other LWLock) here and CHECK_FOR_INTERRUPTS() can do its job. + */ + vacuum_delay_point(false); + ++======= + * Lock the right sibling before releasing the current page, so that + * we can delete it if it turns out to be empty. + */ ++>>>>>>> theirs buffer = ReadBufferExtended(gvs->index, MAIN_FORKNUM, blkno, RBM_NORMAL, gvs->strategy); LockBuffer(buffer, GIN_EXCLUSIVE);