On 02/05/2019 10:37, Heikki Linnakangas wrote:
(resending, previous attempt didn't make it to pgsql-hackers)On 29/04/2019 16:16, Anastasia Lubennikova wrote:In previous emails, I have sent two patches with test and bugfix (see attached). After Heikki shared his concerns, I've rechecked the algorithm and haven't found any potential error. So, if other hackers are agreed with my reasoning, the suggested fix is sufficient and can be committed.I still believe there is a problem with grandparent splits with this. I'll try to construct a test case later this week, unless you manage to create one before that.
Here you go. If you apply the two patches from https://www.postgresql.org/message-id/5d48ce28-34cf-9b03-5d42-dbd5457926bf%40postgrespro.ru, and run the attached script, it will print out something like this:
postgres=# \i grandparent.sql DROP TABLE CREATE TABLE INSERT 0 150000 CREATE INDEX psql:grandparent.sql:27: NOTICE: working on 10000 psql:grandparent.sql:27: NOTICE: working on 20000 psql:grandparent.sql:27: NOTICE: working on 30000 psql:grandparent.sql:27: NOTICE: working on 40000 psql:grandparent.sql:27: NOTICE: working on 50000 psql:grandparent.sql:27: NOTICE: working on 60000 psql:grandparent.sql:27: NOTICE: working on 70000 psql:grandparent.sql:27: NOTICE: working on 80000 psql:grandparent.sql:27: NOTICE: working on 90000 psql:grandparent.sql:27: NOTICE: working on 100000 psql:grandparent.sql:27: NOTICE: working on 110000 psql:grandparent.sql:27: NOTICE: failed for 114034 psql:grandparent.sql:27: NOTICE: working on 120000 DO That "failed for 114034" should not happen.Fortunately, that's not too hard to fix. We just need to arrange things so that the "retry_from_parent" flag also gets set for the grandparent, when the grandparent is split. Like in the attached patch.
- Heikki
>From 7e0b7fa120b9c4c3e0f0f71dc7a5f35ba806ea7f Mon Sep 17 00:00:00 2001 From: Heikki Linnakangas <heikki.linnakan...@iki.fi> Date: Wed, 8 May 2019 01:29:52 +0300 Subject: [PATCH 1/1] 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. Thomas Munro noticed that the contrib/intarray regression test started 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. 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 we need to retry the descend from the parent. 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.20.1
grandparent.sql
Description: application/sql
