From 22251686f07f70527aecda22ab5402986884f6f5 Mon Sep 17 00:00:00 2001 From: Heikki Linnakangas Date: Tue, 14 May 2019 13:18:44 +0300 Subject: [PATCH] Detect internal GiST page splits correctly during index build. As we descend the GiST tree during insertion, we modify any downlinks on the way down to include the new tuple we're about to insert (if they don't cover it already). Modifying an existing downlink might cause an internal page to split, if the new downlink tuple is larger than the old one. If that happens, we need to back up to the parent and re-choose a page to insert to. We used to detect that situation, thanks to the NSN-LSN interlock normally used to detect concurrent page splits, but that got broken by commit 9155580fd5. With that commit, we now use a dummy constant LSN value for every page during index build, so the LSN-NSN interlock no longer works. I thought that was OK because there can't be any other backends modifying the index during index build, but missed that the insertion itself can modify the page we're inserting to. The consequence was that we would sometimes insert the new tuple to an incorrect page, one whose downlink doesn't cover the new tuple. To fix, add a flag to the stack that keeps track of the state while descending tree, to indicate that a page was split, and that we need to retry the descend from the parent. Thomas Munro first reported that the contrib/intarray regression test was failing occasionally on the buildfarm after commit 9155580fd5. The failure was intermittent, because the gistchoose() function is not deterministic, and would only occasionally create the right circumstances for this bug to cause the failure. Patch by Anastasia Lubennikova, with some changes by me to make it work correctly also when the internal page split also causes the "grandparent" to be split. Discussion: https://www.postgresql.org/message-id/CA%2BhUKGJRzLo7tZExWfSbwM3XuK7aAK7FhdBV0FLkbUG%2BW0v0zg%40mail.gmail.com --- src/backend/access/gist/gist.c | 33 +++++++++++++++++++++++++++++++ src/include/access/gist_private.h | 7 +++++++ 2 files changed, 40 insertions(+) diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c index 769aca42e3..d70a138f54 100644 --- a/src/backend/access/gist/gist.c +++ b/src/backend/access/gist/gist.c @@ -639,6 +639,7 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace, /* Start from the root */ firststack.blkno = GIST_ROOT_BLKNO; firststack.lsn = 0; + firststack.retry_from_parent = false; firststack.parent = NULL; firststack.downlinkoffnum = InvalidOffsetNumber; state.stack = stack = &firststack; @@ -651,6 +652,21 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace, */ for (;;) { + /* + * If we split an internal page while descending the tree, we have to + * retry at the parent. (Normally, the LSN-NSN interlock below would + * also catch this and cause us to retry. But LSNs are not updated + * during index build.) + */ + while (stack->retry_from_parent) + { + if (xlocked) + LockBuffer(stack->buffer, GIST_UNLOCK); + xlocked = false; + ReleaseBuffer(stack->buffer); + state.stack = stack = stack->parent; + } + if (XLogRecPtrIsInvalid(stack->lsn)) stack->buffer = ReadBuffer(state.r, stack->blkno); @@ -1376,6 +1392,23 @@ gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack, unlockbuf /* Unlock stack->buffer if caller wants that */ ); Assert(left->buf == stack->buffer); + + /* + * If we split the page because we had to adjust the downlink on an + * internal page, while descending the tree for inserting a new tuple, + * then this might no longer be the correct page for the new tuple. The + * downlink to this page might not cover the new tuple anymore, it might + * need to go to the newly-created right sibling instead. Tell the caller + * to walk back up the stack, to re-check at the parent which page to + * insert to. + * + * Normally, the LSN-NSN interlock during the tree descend would also + * detect that a concurrent split happened (by ourselves), and cause us to + * retry at the parent. But that mechanism doesn't work during index + * build, because we don't do WAL-logging, and don't update LSNs, during + * index build. + */ + stack->retry_from_parent = true; } /* diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.h index ccf050cd62..614d9996ec 100644 --- a/src/include/access/gist_private.h +++ b/src/include/access/gist_private.h @@ -215,6 +215,13 @@ typedef struct GISTInsertStack */ GistNSN lsn; + /* + * If set, we split the page while descending the tree to find an + * insertion target. It means that we need to retry from the parent, + * because the downlink of this page might no longer cover the new key. + */ + bool retry_from_parent; + /* offset of the downlink in the parent page, that points to this page */ OffsetNumber downlinkoffnum; -- 2.40.0