pg.ddx.io pgsql-bugs@postgresql.org mailing list archive
help / color / mirror / Atom feedBUG #18129: GiST index produces incorrect query results
6+ messages / 3 participants
[nested] [flat]
* BUG #18129: GiST index produces incorrect query results
@ 2023-09-22 06:00 PG Bug reporting form <noreply@postgresql.org>
2023-09-22 13:43 ` Re: BUG #18129: GiST index produces incorrect query results Heikki Linnakangas <hlinnaka@iki.fi>
2023-09-23 22:06 ` Re: BUG #18129: GiST index produces incorrect query results Heikki Linnakangas <hlinnaka@iki.fi>
0 siblings, 2 replies; 6+ messages in thread
From: PG Bug reporting form @ 2023-09-22 06:00 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org; +Cc: exclusion@gmail.com
The following bug has been logged on the website:
Bug reference: 18129
Logged by: Alexander Lakhin
Email address: exclusion@gmail.com
PostgreSQL version: 16.0
Operating system: Ubuntu 22.04
Description:
The following test data manipulation:
sed '/{73,23,20}/!s/\([0-9]\+\)/\1,10\1,20\1,30\1/g' -i
contrib/intarray/data/test__int.data
(effectively multiplying contents of all arrays (except for one) in the
test by 3)
makes `make check contrib/intarray` fail, with random results, e.g.:
--- .../contrib/intarray/expected/_int.out 2023-09-21
21:44:46.967470822 +0300
+++ .../contrib/intarray/results/_int.out 2023-09-22 08:12:18.269739402
+0300
@@ -497,13 +497,13 @@
SELECT count(*) from test__int WHERE a && '{23,50}';
count
-------
- 403
+ 395
(1 row)
SELECT count(*) from test__int WHERE a @@ '23|50';
count
-------
- 403
+ 395
(1 row)
SELECT count(*) from test__int WHERE a @> '{23,50}';
@@ -557,13 +557,13 @@
SELECT count(*) from test__int WHERE a @@ '20 | !21';
count
-------
- 6566
+ 6478
(1 row)
SELECT count(*) from test__int WHERE a @@ '!20 & !21';
count
-------
- 6343
+ 6258
(1 row)
INSERT INTO test__int SELECT array(SELECT x FROM generate_series(1, 1001)
x); -- should fail
@@ -639,13 +639,13 @@
SELECT count(*) from test__int WHERE a @@ '20 | !21';
count
-------
- 6566
+ 6381
(1 row)
SELECT count(*) from test__int WHERE a @@ '!20 & !21';
count
-------
- 6343
+ 6165
(1 row)
DROP INDEX text_idx;
(Here we deal with intarray's gist__int_ops, but I suspect that other gist
opclasses might be affected as well.)
First bad commit is 9155580fd, on which three different outcomes are
possible: test passes/test fails/assertion fails.
Assertion failures, that we had observed after 9155580fd, were fixed by
a7ee7c851 and 741b88435, but apparently there is another defect induced
by that gist implementation change.
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: BUG #18129: GiST index produces incorrect query results
2023-09-22 06:00 BUG #18129: GiST index produces incorrect query results PG Bug reporting form <noreply@postgresql.org>
@ 2023-09-22 13:43 ` Heikki Linnakangas <hlinnaka@iki.fi>
1 sibling, 0 replies; 6+ messages in thread
From: Heikki Linnakangas @ 2023-09-22 13:43 UTC (permalink / raw)
To: exclusion@gmail.com; pgsql-bugs@lists.postgresql.org
On 22/09/2023 09:00, PG Bug reporting form wrote:
> First bad commit is 9155580fd, on which three different outcomes are
> possible: test passes/test fails/assertion fails.
> Assertion failures, that we had observed after 9155580fd, were fixed by
> a7ee7c851 and 741b88435, but apparently there is another defect induced
> by that gist implementation change.
I can reproduce this. I suspect something's still wrong with the LSN <->
NSN cross check, when the pages are WAL logged in physical order. Thanks
for the report, I'll take a look.
--
Heikki Linnakangas
Neon (https://neon.tech)
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: BUG #18129: GiST index produces incorrect query results
2023-09-22 06:00 BUG #18129: GiST index produces incorrect query results PG Bug reporting form <noreply@postgresql.org>
@ 2023-09-23 22:06 ` Heikki Linnakangas <hlinnaka@iki.fi>
2023-09-25 21:24 ` Re: BUG #18129: GiST index produces incorrect query results Heikki Linnakangas <hlinnaka@iki.fi>
1 sibling, 1 reply; 6+ messages in thread
From: Heikki Linnakangas @ 2023-09-23 22:06 UTC (permalink / raw)
To: exclusion@gmail.com; pgsql-bugs@lists.postgresql.org
On 22/09/2023 09:00, PG Bug reporting form wrote:
> First bad commit is 9155580fd, on which three different outcomes are
> possible: test passes/test fails/assertion fails.
> Assertion failures, that we had observed after 9155580fd, were fixed by
> a7ee7c851 and 741b88435, but apparently there is another defect induced
> by that gist implementation change.
This is indeed a similar bug to that fixed in 741b88435 and a7ee7c851.
In those commits, we fixed the insertion code so that whenever we insert
a downlink to the parent page and that causes the parent page to split,
we invalidate the 'downlinkoffnum' we had memorized for the child.
Because when the parent page is split, the downlink for the child likely
moves.
However, the downlink can move even when we *don't* split the parent.
Splitting a page not only inserts the new tuple for the new right page,
but also updates the old downlink, because the key representing what is
now the left page covers less keys than the original page. And updating
a tuple is implemented as delete+insert. The delete moves existing
tuples on the page! In other words, this code and comment in
gistfinishsplit():
> if (gistinserttuples(state, stack->parent, giststate,
> tuples, 2,
> stack->downlinkoffnum,
> left->buf, right->buf,
> true, /* Unlock parent */
> unlockbuf /* Unlock stack->buffer if caller wants
> * that */
> ))
> {
> /*
> * If the parent page was split, the downlink might have moved.
> */
> stack->downlinkoffnum = InvalidOffsetNumber;
> }
is wrong. We must invalidate 'downlinkoffnum' whether or not the parent
page was split, because updating an existing tuple can also move other
tuples on the page.
Attached is a set of patches to fix this:
1. To catch the problem earlier - already during the index build - I
modified getFindCorrectParent() to always find the parent the hard way
by scanning the parent page, even if 'downlinkoffnum' is set. Once the
downlink is found, it compares it with the 'downlinkoffnum', and PANICs
if it wasn't where we expected. That defeats the point of memorizing the
'downlinkoffnum' in the first place, but it's a useful cross-check.
I don't intend to commit this, but it was useful during debugging.
2. A straightforward fix for the bug.
3. Looking at gistFindCorrectParent, when it steps right, it also
doesn't update 'downlinkoffnum' of the parent page. Surely if we step to
a different block altogether, the memorized downlink position of the
previous block no longer applies.
Worryingly, I haven't been able to get a test failure caused by that.
Maybe there are some reasons why we never need to split the parent after
that, not sure. But it sure looks wrong.
4. Given how many bugs we've already had with this, I'd like to make
this more robust. Currently, we meticulously track if we have made any
inserts that invalidate the memorized location of the downlink. Instead,
gistFindCorrectParent() could treat the memorized location as just a
hint, and always check if the downlink is still at the memorized
location. If it is, great, and if it's not, find it the hard way. That
makes it unnecessary to clear 'downlinkoffnum' at the right places. We
still need the 'retry_from_parent' flag, though.
5. Re-indent the code after previous commit. Separated for easier review.
I'd also like to add something to our regression test suite for better
coverage of this. The intarray test case is very useful, but it'd be
nice to have something in the main regression suite, as this is a
general GiST issue, not related to intarray. I haven't spent any time on
that yet.
--
Heikki Linnakangas
Neon (https://neon.tech)
Attachments:
[text/x-patch] 0001-Add-assertion-that-downlinkoffnum-is-set-correctly.patch (1.5K, ../../80e4ef74-4a00-4631-963f-3dd11e64c6fe@iki.fi/2-0001-Add-assertion-that-downlinkoffnum-is-set-correctly.patch)
download | inline diff:
From adca01fd7dd566f6da905c800480176978b5663f Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakangas@iki.fi>
Date: Sun, 24 Sep 2023 00:52:20 +0300
Subject: [PATCH 1/5] Add assertion that 'downlinkoffnum' is set correctly.
I don't intend to push this, but it was useful while debugging.
---
src/backend/access/gist/gist.c | 16 ++++++++++++++++
1 file changed, 16 insertions(+)
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index b1f19f6a8e6..10405239027 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -1022,6 +1022,13 @@ gistFindCorrectParent(Relation r, GISTInsertStack *child)
{
GISTInsertStack *parent = child->parent;
+#ifdef USE_ASSERT_CHECKING
+ int save_downlinkoffnum = child->downlinkoffnum;
+ BlockNumber save_parent_blkno = parent->blkno;
+
+ child->downlinkoffnum = InvalidOffsetNumber;
+#endif
+
gistcheckpage(r, parent->buffer);
parent->page = (Page) BufferGetPage(parent->buffer);
@@ -1047,6 +1054,15 @@ gistFindCorrectParent(Relation r, GISTInsertStack *child)
{
/* yes!!, found */
child->downlinkoffnum = i;
+#ifdef USE_ASSERT_CHECKING
+ if (parent->lsn == PageGetLSN(parent->page) && save_downlinkoffnum != InvalidOffsetNumber) {
+ if (i != save_downlinkoffnum) {
+ elog(PANIC, "expected to find downlink for %u on blk %u offset %u, but it was found on blk %u offset %u",
+ child->blkno, save_parent_blkno, save_downlinkoffnum,
+ parent->blkno, i);
+ }
+ }
+#endif
return;
}
}
--
2.39.2
[text/x-patch] 0002-Fix-another-bug-in-GiST-index-build.patch (3.3K, ../../80e4ef74-4a00-4631-963f-3dd11e64c6fe@iki.fi/3-0002-Fix-another-bug-in-GiST-index-build.patch)
download | inline diff:
From f405db22b6ea2cb39a9b063e4759c0f97fa281a6 Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakangas@iki.fi>
Date: Sun, 24 Sep 2023 00:22:30 +0300
Subject: [PATCH 2/5] Fix another bug in GiST index build.
Yet another bug in the ilk of commits a7ee7c851 and 741b88435. In
741b88435, we took care to clear the memorized location of the
downlink when we split the parent page, because splitting the parent
page can move the downlink. But we missed that even *updating* a tuple
on the parent can move it, because updating a tuple on a gist page is
implemented as a delete+insert, so the updated tuple gets moved to the
end of the page. To fix, clear the downlink when we updatie a tuple on
the parent page, even if it's not split.
Backpatch XXX
Reported-by: Alexander Lakhin
Discussion: https://www.postgresql.org/message-id/18129-caca016eaf0c3702@postgresql.org
---
src/backend/access/gist/gist.c | 37 +++++++++++++++++++---------------
1 file changed, 21 insertions(+), 16 deletions(-)
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index 10405239027..d4469eb7cc4 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -1272,7 +1272,10 @@ gistinserttuple(GISTInsertState *state, GISTInsertStack *stack,
*
* Returns 'true' if the page had to be split. Note that if the page was
* split, the inserted/updated tuples might've been inserted to a right
- * sibling of stack->buffer instead of stack->buffer itself.
+ * sibling of stack->buffer instead of stack->buffer itself. Even if the page
+ * was not split but an old tuple was updated, any existing tuples on the page
+ * including the one that's updated might move to a different offset on th
+ * epage.
*/
static bool
gistinserttuples(GISTInsertState *state, GISTInsertStack *stack,
@@ -1371,7 +1374,8 @@ gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
{
/*
* If the parent page was split, the existing downlink might have
- * moved.
+ * moved. This assumes that gistinsettuples() doesn't move the
+ * tuples around unless the page is split.
*/
stack->downlinkoffnum = InvalidOffsetNumber;
}
@@ -1389,20 +1393,21 @@ gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
tuples[0] = left->downlink;
tuples[1] = right->downlink;
gistFindCorrectParent(state->r, stack);
- if (gistinserttuples(state, stack->parent, giststate,
- tuples, 2,
- stack->downlinkoffnum,
- left->buf, right->buf,
- true, /* Unlock parent */
- unlockbuf /* Unlock stack->buffer if caller wants
- * that */
- ))
- {
- /*
- * If the parent page was split, the downlink might have moved.
- */
- stack->downlinkoffnum = InvalidOffsetNumber;
- }
+ (void) gistinserttuples(state, stack->parent, giststate,
+ tuples, 2,
+ stack->downlinkoffnum,
+ left->buf, right->buf,
+ true, /* Unlock parent */
+ unlockbuf /* Unlock stack->buffer if caller
+ * wants that */
+ );
+
+ /*
+ * The downlink might have moved when we updated it. Even if the page
+ * wasn't split, because gistinserttuples() implements updating the old
+ * tuple by removing and re-inserting it!
+ */
+ stack->downlinkoffnum = InvalidOffsetNumber;
Assert(left->buf == stack->buffer);
--
2.39.2
[text/x-patch] 0003-Also-clear-downlinkoffnum-when-the-parent-block-is-c.patch (1.0K, ../../80e4ef74-4a00-4631-963f-3dd11e64c6fe@iki.fi/4-0003-Also-clear-downlinkoffnum-when-the-parent-block-is-c.patch)
download | inline diff:
From 99a71e9543ba2cae0bf91403f78c57671a6aebf8 Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakangas@iki.fi>
Date: Sat, 23 Sep 2023 20:50:38 +0300
Subject: [PATCH 3/5] Also clear 'downlinkoffnum' when the parent block is
changed.
While looking at bug #18129, I noticed this spot where we update the
parent block in the stack, but we don't clear the
'downlinkoffnum'. This case wasn't hit by the test case, but it could
lead to similar bugs.
---
src/backend/access/gist/gist.c | 1 +
1 file changed, 1 insertion(+)
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index d4469eb7cc4..b3749bbb432 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -1068,6 +1068,7 @@ gistFindCorrectParent(Relation r, GISTInsertStack *child)
}
parent->blkno = GistPageGetOpaque(parent->page)->rightlink;
+ parent->downlinkoffnum = InvalidOffsetNumber;
UnlockReleaseBuffer(parent->buffer);
if (parent->blkno == InvalidBlockNumber)
{
--
2.39.2
[text/x-patch] 0004-Treat-downlinkoffnum-only-as-a-hint-in-gistFindCorre.patch (5.9K, ../../80e4ef74-4a00-4631-963f-3dd11e64c6fe@iki.fi/5-0004-Treat-downlinkoffnum-only-as-a-hint-in-gistFindCorre.patch)
download | inline diff:
From 661bd1bbb029f71e0dbe7d37a731cae50afb862b Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakangas@iki.fi>
Date: Sun, 24 Sep 2023 00:49:08 +0300
Subject: [PATCH 4/5] Treat 'downlinkoffnum' only as a hint in
gistFindCorrectParent.
We have had a number of bugs in trying to meticulously clear
'downlinkoffnum' when we update a parent page. But instead of trying
hard to clear it all the right places, we can treat is merely as a
hint, so that if we forget to clear it, it still works.
This makes the fixes in commit XXX and a7ee7c8513 unnecessary. It
doesn't hurt to still clear 'downlinkoffnum', but everything would
work without it now.
---
src/backend/access/gist/gist.c | 69 ++++++++++++++++++----------------
1 file changed, 36 insertions(+), 33 deletions(-)
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index b3749bbb432..42f9408becb 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -1018,34 +1018,46 @@ gistFindPath(Relation r, BlockNumber child, OffsetNumber *downlinkoffnum)
* remain so at exit, but it might not be the same page anymore.
*/
static void
-gistFindCorrectParent(Relation r, GISTInsertStack *child)
+gistFindCorrectParent(Relation r, GISTInsertStack *child, bool is_build)
{
GISTInsertStack *parent = child->parent;
-
-#ifdef USE_ASSERT_CHECKING
- int save_downlinkoffnum = child->downlinkoffnum;
- BlockNumber save_parent_blkno = parent->blkno;
-
- child->downlinkoffnum = InvalidOffsetNumber;
-#endif
+ ItemId iid;
+ IndexTuple idxtuple;
+ OffsetNumber i,
+ maxoff;
+ GISTInsertStack *ptr;
gistcheckpage(r, parent->buffer);
parent->page = (Page) BufferGetPage(parent->buffer);
+ maxoff = PageGetMaxOffsetNumber(parent->page);
- /* here we don't need to distinguish between split and page update */
- if (child->downlinkoffnum == InvalidOffsetNumber ||
- parent->lsn != PageGetLSN(parent->page))
+ /* Check if the downlink is still where it was before */
+ if (child->downlinkoffnum != InvalidOffsetNumber && child->downlinkoffnum <= maxoff)
{
- /* parent is changed, look child in right links until found */
- OffsetNumber i,
- maxoff;
- ItemId iid;
- IndexTuple idxtuple;
- GISTInsertStack *ptr;
+ iid = PageGetItemId(parent->page, child->downlinkoffnum);
+ idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
+ if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
+ return; /* still there */
+ }
+ /*
+ * The page has changed since we looked. During normal operation, every
+ * update of a page changes its LSN, so the LSN we memorized should have
+ * changed too. During index build, however, we don't WAL-log the changes
+ * until we have built the index, so the LSN doesn't change. There is no
+ * concurrent activity during index build, but we might have changed the
+ * parent ourselves.
+ */
+ Assert(parent->lsn != PageGetLSN(parent->page) || is_build);
+
+ /*
+ * Scan the page to re-find the downlink. If the page was split, it might
+ * have moved to a different page, so follow the right links until we find
+ * it.
+ */
+ {
while (true)
{
- maxoff = PageGetMaxOffsetNumber(parent->page);
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
{
iid = PageGetItemId(parent->page, i);
@@ -1054,15 +1066,6 @@ gistFindCorrectParent(Relation r, GISTInsertStack *child)
{
/* yes!!, found */
child->downlinkoffnum = i;
-#ifdef USE_ASSERT_CHECKING
- if (parent->lsn == PageGetLSN(parent->page) && save_downlinkoffnum != InvalidOffsetNumber) {
- if (i != save_downlinkoffnum) {
- elog(PANIC, "expected to find downlink for %u on blk %u offset %u, but it was found on blk %u offset %u",
- child->blkno, save_parent_blkno, save_downlinkoffnum,
- parent->blkno, i);
- }
- }
-#endif
return;
}
}
@@ -1114,7 +1117,7 @@ gistFindCorrectParent(Relation r, GISTInsertStack *child)
/* make recursive call to normal processing */
LockBuffer(child->parent->buffer, GIST_EXCLUSIVE);
- gistFindCorrectParent(r, child);
+ gistFindCorrectParent(r, child, is_build);
}
}
@@ -1123,7 +1126,7 @@ gistFindCorrectParent(Relation r, GISTInsertStack *child)
*/
static IndexTuple
gistformdownlink(Relation rel, Buffer buf, GISTSTATE *giststate,
- GISTInsertStack *stack)
+ GISTInsertStack *stack, bool is_build)
{
Page page = BufferGetPage(buf);
OffsetNumber maxoff;
@@ -1164,7 +1167,7 @@ gistformdownlink(Relation rel, Buffer buf, GISTSTATE *giststate,
ItemId iid;
LockBuffer(stack->parent->buffer, GIST_EXCLUSIVE);
- gistFindCorrectParent(rel, stack);
+ gistFindCorrectParent(rel, stack, is_build);
iid = PageGetItemId(stack->parent->page, stack->downlinkoffnum);
downlink = (IndexTuple) PageGetItem(stack->parent->page, iid);
downlink = CopyIndexTuple(downlink);
@@ -1210,7 +1213,7 @@ gistfixsplit(GISTInsertState *state, GISTSTATE *giststate)
page = BufferGetPage(buf);
/* Form the new downlink tuples to insert to parent */
- downlink = gistformdownlink(state->r, buf, giststate, stack);
+ downlink = gistformdownlink(state->r, buf, giststate, stack, state->is_build);
si->buf = buf;
si->downlink = downlink;
@@ -1367,7 +1370,7 @@ gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
right = (GISTPageSplitInfo *) list_nth(splitinfo, pos);
left = (GISTPageSplitInfo *) list_nth(splitinfo, pos - 1);
- gistFindCorrectParent(state->r, stack);
+ gistFindCorrectParent(state->r, stack, state->is_build);
if (gistinserttuples(state, stack->parent, giststate,
&right->downlink, 1,
InvalidOffsetNumber,
@@ -1393,7 +1396,7 @@ gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
*/
tuples[0] = left->downlink;
tuples[1] = right->downlink;
- gistFindCorrectParent(state->r, stack);
+ gistFindCorrectParent(state->r, stack, state->is_build);
(void) gistinserttuples(state, stack->parent, giststate,
tuples, 2,
stack->downlinkoffnum,
--
2.39.2
[text/x-patch] 0005-Re-indent-the-code.patch (4.3K, ../../80e4ef74-4a00-4631-963f-3dd11e64c6fe@iki.fi/6-0005-Re-indent-the-code.patch)
download | inline diff:
From 2de2283bba14674a66eecb46fc99d95b26bb1002 Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakangas@iki.fi>
Date: Sun, 24 Sep 2023 00:58:24 +0300
Subject: [PATCH 5/5] Re-indent the code.
Remove the stray braces and re-indent the code. This should be
squashed with the previous commit, but it makes it easier to review
when there's not so much whitespace change.
---
src/backend/access/gist/gist.c | 99 +++++++++++++++++-----------------
1 file changed, 48 insertions(+), 51 deletions(-)
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index 42f9408becb..ec9d7035468 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -1055,70 +1055,67 @@ gistFindCorrectParent(Relation r, GISTInsertStack *child, bool is_build)
* have moved to a different page, so follow the right links until we find
* it.
*/
+ while (true)
{
- while (true)
+ for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
{
- for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
- {
- iid = PageGetItemId(parent->page, i);
- idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
- if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
- {
- /* yes!!, found */
- child->downlinkoffnum = i;
- return;
- }
- }
-
- parent->blkno = GistPageGetOpaque(parent->page)->rightlink;
- parent->downlinkoffnum = InvalidOffsetNumber;
- UnlockReleaseBuffer(parent->buffer);
- if (parent->blkno == InvalidBlockNumber)
+ iid = PageGetItemId(parent->page, i);
+ idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
+ if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
{
- /*
- * End of chain and still didn't find parent. It's a very-very
- * rare situation when root splitted.
- */
- break;
+ /* yes!!, found */
+ child->downlinkoffnum = i;
+ return;
}
- parent->buffer = ReadBuffer(r, parent->blkno);
- LockBuffer(parent->buffer, GIST_EXCLUSIVE);
- gistcheckpage(r, parent->buffer);
- parent->page = (Page) BufferGetPage(parent->buffer);
}
- /*
- * awful!!, we need search tree to find parent ... , but before we
- * should release all old parent
- */
-
- ptr = child->parent->parent; /* child->parent already released
- * above */
- while (ptr)
+ parent->blkno = GistPageGetOpaque(parent->page)->rightlink;
+ parent->downlinkoffnum = InvalidOffsetNumber;
+ UnlockReleaseBuffer(parent->buffer);
+ if (parent->blkno == InvalidBlockNumber)
{
- ReleaseBuffer(ptr->buffer);
- ptr = ptr->parent;
+ /*
+ * End of chain and still didn't find parent. It's a very-very
+ * rare situation when root splitted.
+ */
+ break;
}
+ parent->buffer = ReadBuffer(r, parent->blkno);
+ LockBuffer(parent->buffer, GIST_EXCLUSIVE);
+ gistcheckpage(r, parent->buffer);
+ parent->page = (Page) BufferGetPage(parent->buffer);
+ }
- /* ok, find new path */
- ptr = parent = gistFindPath(r, child->blkno, &child->downlinkoffnum);
+ /*
+ * awful!!, we need search tree to find parent ... , but before we should
+ * release all old parent
+ */
- /* read all buffers as expected by caller */
- /* note we don't lock them or gistcheckpage them here! */
- while (ptr)
- {
- ptr->buffer = ReadBuffer(r, ptr->blkno);
- ptr->page = (Page) BufferGetPage(ptr->buffer);
- ptr = ptr->parent;
- }
+ ptr = child->parent->parent; /* child->parent already released above */
+ while (ptr)
+ {
+ ReleaseBuffer(ptr->buffer);
+ ptr = ptr->parent;
+ }
- /* install new chain of parents to stack */
- child->parent = parent;
+ /* ok, find new path */
+ ptr = parent = gistFindPath(r, child->blkno, &child->downlinkoffnum);
- /* make recursive call to normal processing */
- LockBuffer(child->parent->buffer, GIST_EXCLUSIVE);
- gistFindCorrectParent(r, child, is_build);
+ /* read all buffers as expected by caller */
+ /* note we don't lock them or gistcheckpage them here! */
+ while (ptr)
+ {
+ ptr->buffer = ReadBuffer(r, ptr->blkno);
+ ptr->page = (Page) BufferGetPage(ptr->buffer);
+ ptr = ptr->parent;
}
+
+ /* install new chain of parents to stack */
+ child->parent = parent;
+
+ /* make recursive call to normal processing */
+ LockBuffer(child->parent->buffer, GIST_EXCLUSIVE);
+ gistFindCorrectParent(r, child, is_build);
}
/*
--
2.39.2
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: BUG #18129: GiST index produces incorrect query results
2023-09-22 06:00 BUG #18129: GiST index produces incorrect query results PG Bug reporting form <noreply@postgresql.org>
2023-09-23 22:06 ` Re: BUG #18129: GiST index produces incorrect query results Heikki Linnakangas <hlinnaka@iki.fi>
@ 2023-09-25 21:24 ` Heikki Linnakangas <hlinnaka@iki.fi>
2023-09-26 08:08 ` Re: BUG #18129: GiST index produces incorrect query results Alexander Lakhin <exclusion@gmail.com>
0 siblings, 1 reply; 6+ messages in thread
From: Heikki Linnakangas @ 2023-09-25 21:24 UTC (permalink / raw)
To: exclusion@gmail.com; pgsql-bugs@lists.postgresql.org
On 24/09/2023 01:06, Heikki Linnakangas wrote:
> On 22/09/2023 09:00, PG Bug reporting form wrote:
>> First bad commit is 9155580fd, on which three different outcomes are
>> possible: test passes/test fails/assertion fails.
>> Assertion failures, that we had observed after 9155580fd, were fixed by
>> a7ee7c851 and 741b88435, but apparently there is another defect induced
>> by that gist implementation change.
>
> This is indeed a similar bug to that fixed in 741b88435 and a7ee7c851.
> In those commits, we fixed the insertion code so that whenever we insert
> a downlink to the parent page and that causes the parent page to split,
> we invalidate the 'downlinkoffnum' we had memorized for the child.
> Because when the parent page is split, the downlink for the child likely
> moves.
>
> However, the downlink can move even when we *don't* split the parent.
> Splitting a page not only inserts the new tuple for the new right page,
> but also updates the old downlink, because the key representing what is
> now the left page covers less keys than the original page. And updating
> a tuple is implemented as delete+insert. The delete moves existing
> tuples on the page! In other words, this code and comment in
> gistfinishsplit():
>
>> if (gistinserttuples(state, stack->parent, giststate,
>> tuples, 2,
>> stack->downlinkoffnum,
>> left->buf, right->buf,
>> true, /* Unlock parent */
>> unlockbuf /* Unlock stack->buffer if caller wants
>> * that */
>> ))
>> {
>> /*
>> * If the parent page was split, the downlink might have moved.
>> */
>> stack->downlinkoffnum = InvalidOffsetNumber;
>> }
>
> is wrong. We must invalidate 'downlinkoffnum' whether or not the parent
> page was split, because updating an existing tuple can also move other
> tuples on the page.
>
> Attached is a set of patches to fix this:
>
> 1. To catch the problem earlier - already during the index build - I
> modified getFindCorrectParent() to always find the parent the hard way
> by scanning the parent page, even if 'downlinkoffnum' is set. Once the
> downlink is found, it compares it with the 'downlinkoffnum', and PANICs
> if it wasn't where we expected. That defeats the point of memorizing the
> 'downlinkoffnum' in the first place, but it's a useful cross-check.
>
> I don't intend to commit this, but it was useful during debugging.
>
> 2. A straightforward fix for the bug.
>
> 3. Looking at gistFindCorrectParent, when it steps right, it also
> doesn't update 'downlinkoffnum' of the parent page. Surely if we step to
> a different block altogether, the memorized downlink position of the
> previous block no longer applies.
>
> Worryingly, I haven't been able to get a test failure caused by that.
> Maybe there are some reasons why we never need to split the parent after
> that, not sure. But it sure looks wrong.
>
> 4. Given how many bugs we've already had with this, I'd like to make
> this more robust. Currently, we meticulously track if we have made any
> inserts that invalidate the memorized location of the downlink. Instead,
> gistFindCorrectParent() could treat the memorized location as just a
> hint, and always check if the downlink is still at the memorized
> location. If it is, great, and if it's not, find it the hard way. That
> makes it unnecessary to clear 'downlinkoffnum' at the right places. We
> still need the 'retry_from_parent' flag, though.
>
> 5. Re-indent the code after previous commit. Separated for easier review.
>
> I'd also like to add something to our regression test suite for better
> coverage of this. The intarray test case is very useful, but it'd be
> nice to have something in the main regression suite, as this is a
> general GiST issue, not related to intarray. I haven't spent any time on
> that yet.
I spent a while trying to create a test case for this that would not
require expanding the test data so much, but no avail. I even tried to
take the same data set, but instead of duplicating each element like you
did, I appended a random number of integers to each array, but even that
did not trigger the failure. That particular data set seems cursed; how
did you stumble upon it?
I'm reluctant to just make all the arrays larger, as it makes the test
2x slower. So instead of running all the commands over the larger data
set, I added one more copy of the CREATE INDEX and the test queries to
the end that uses the larger set.
See attached. It's squashed version of the previous patches I posted,
with the test case. Barring objections, I'll commit this.
While I was playing with this, I ran into this unrelated issue:
CREATE EXTENSION pgcrypto; -- for gen_random_bytes
CREATE EXTENSION btree_gist;
CREATE TABLE byteatest (a bytea);
INSERT INTO byteatest SELECT (gen_random_bytes(1000) ||
gen_random_bytes(1000) || gen_random_bytes(1000)) FROM
generate_series(1, 10) g;
CREATE INDEX ON byteatest USING GIST ( a );
Fails with:
ERROR: failed to add item to index page in "byteatest_a_idx1"
If you make that value even larger, then it fails with a better error
message:
ERROR: index row requires 8208 bytes, maximum size is 8191
So the "failed to add item" error doesn't seem expected.
--
Heikki Linnakangas
Neon (https://neon.tech)
Attachments:
[text/x-patch] v2-0001-Fix-another-bug-in-parent-page-splitting-during-G.patch (16.1K, ../../ab9b8a32-25bc-e473-3927-0975a838a26b@iki.fi/2-v2-0001-Fix-another-bug-in-parent-page-splitting-during-G.patch)
download | inline diff:
From a1105af75a6c6e71d209bd3df80cbfcca516a2f4 Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakangas@iki.fi>
Date: Tue, 26 Sep 2023 00:21:47 +0300
Subject: [PATCH v2 1/1] Fix another bug in parent page splitting during GiST
index build.
Yet another bug in the ilk of commits a7ee7c851 and 741b88435. In
741b88435, we took care to clear the memorized location of the
downlink when we split the parent page, because splitting the parent
page can move the downlink. But we missed that even *updating* a tuple
on the parent can move it, because updating a tuple on a gist page is
implemented as a delete+insert, so the updated tuple gets moved to the
end of the page.
This commit fixes the bug in two different ways (belt and suspenders):
1. Clear the downlink when we update a tuple on the parent page, even
if it's not split. This the same approach as in commits a7ee7c851
and 741b88435.
I also noticed that gistFindCorrectParent did not clear the
'downlinkoffnum' when it stepped to the right sibling. Fix that
too, as it seems like a clear bug even though I haven't been able
to find a test case to hit that.
2. Change gistFindCorrectParent so that it treats 'downlinkoffnum'
merely as a hint. It now always first checks if the downlink is
still at that location, and if not, it scans the page like before.
That's more robust if there are still more cases where we fail to
clear 'downlinkoffnum' that we haven't yet uncovered. With this,
it's no longer necessary to meticulously clear 'downlinkoffnum',
so this makes the previous fixes unnecessary, but I didn't revert
them because it still seems nice to clear it when we know that the
downlink has moved.
Also add the test case using the same test data that Alexander
posted. I tried to reduce it to a smaller test, and I also tried to
reproduce this with different test data, but I was not able to, so
let's just include what we have.
Backpatch to v12, like the previous fixes.
Reported-by: Alexander Lakhin
Discussion: https://www.postgresql.org/message-id/18129-caca016eaf0c3702@postgresql.org
test data change
Add assertion that 'downlinkoffnum' is set correctly.
I don't intend to push this, but it was useful while debugging.
test changes
Also clear 'downlinkoffnum' when the parent block is changed.
While looking at bug #18129, I noticed this spot where we update the
parent block in the stack, but we don't clear the
'downlinkoffnum'. This case wasn't hit by the test case, but it could
lead to similar bugs.
Treat 'downlinkoffnum' only as a hint in gistFindCorrectParent.
We have had a number of bugs in trying to meticulously clear
'downlinkoffnum' when we update a parent page. But instead of trying
hard to clear it all the right places, we can treat is merely as a
hint, so that if we forget to clear it, it still works.
This makes the fixes in commit XXX and a7ee7c8513 unnecessary. It
doesn't hurt to still clear 'downlinkoffnum', but everything would
work without it now.
Re-indent the code.
Remove the stray braces and re-indent the code. This should be
squashed with the previous commit, but it makes it easier to review
when there's not so much whitespace change.
reduce comment again
---
contrib/intarray/expected/_int.out | 91 +++++++++++++++
contrib/intarray/sql/_int.sql | 35 ++++++
src/backend/access/gist/gist.c | 178 ++++++++++++++++-------------
3 files changed, 224 insertions(+), 80 deletions(-)
diff --git a/contrib/intarray/expected/_int.out b/contrib/intarray/expected/_int.out
index cad37f1a244..b6cf5757825 100644
--- a/contrib/intarray/expected/_int.out
+++ b/contrib/intarray/expected/_int.out
@@ -876,4 +876,95 @@ SELECT count(*) from test__int WHERE a @@ '!20 & !21';
6343
(1 row)
+DROP INDEX text_idx;
+-- Repeat the same queries with an extended data set. The data set is the
+-- same that we used before, except that each element in the array is
+-- repeated three times, offset by 1000 and 2000. For example, {1, 5}
+-- becomes {1, 1001, 2001, 5, 1005, 2005}.
+--
+-- That has proven to be unreasonably effective at exercising codepaths in
+-- core GiST code related to splitting parent pages, which is not covered by
+-- other tests. This is a bit out-of-place as the point is to test core GiST
+-- code rather than this extension, but there is no suitable GiST opclass in
+-- core that would reach the same codepaths.
+CREATE TABLE more__int AS SELECT
+ -- Leave alone NULLs, empty arrays and the one row that we use to test
+ -- equality
+ CASE WHEN a IS NULL OR a = '{}' OR a = '{73,23,20}' THEN a ELSE
+ (select array_agg(u) || array_agg(u + 1000) || array_agg(u + 2000) from (select unnest(a) u) x)
+ END AS a, a as b
+ FROM test__int;
+CREATE INDEX ON more__int using gist (a gist__int_ops(numranges = 252));
+SELECT count(*) from more__int WHERE a && '{23,50}';
+ count
+-------
+ 403
+(1 row)
+
+SELECT count(*) from more__int WHERE a @@ '23|50';
+ count
+-------
+ 403
+(1 row)
+
+SELECT count(*) from more__int WHERE a @> '{23,50}';
+ count
+-------
+ 12
+(1 row)
+
+SELECT count(*) from more__int WHERE a @@ '23&50';
+ count
+-------
+ 12
+(1 row)
+
+SELECT count(*) from more__int WHERE a @> '{20,23}';
+ count
+-------
+ 12
+(1 row)
+
+SELECT count(*) from more__int WHERE a <@ '{73,23,20}';
+ count
+-------
+ 10
+(1 row)
+
+SELECT count(*) from more__int WHERE a = '{73,23,20}';
+ count
+-------
+ 1
+(1 row)
+
+SELECT count(*) from more__int WHERE a @@ '50&68';
+ count
+-------
+ 9
+(1 row)
+
+SELECT count(*) from more__int WHERE a @> '{20,23}' or a @> '{50,68}';
+ count
+-------
+ 21
+(1 row)
+
+SELECT count(*) from more__int WHERE a @@ '(20&23)|(50&68)';
+ count
+-------
+ 21
+(1 row)
+
+SELECT count(*) from more__int WHERE a @@ '20 | !21';
+ count
+-------
+ 6566
+(1 row)
+
+SELECT count(*) from more__int WHERE a @@ '!20 & !21';
+ count
+-------
+ 6343
+(1 row)
+
RESET enable_seqscan;
diff --git a/contrib/intarray/sql/_int.sql b/contrib/intarray/sql/_int.sql
index a947c4f8fdd..dd5c668a0f4 100644
--- a/contrib/intarray/sql/_int.sql
+++ b/contrib/intarray/sql/_int.sql
@@ -195,4 +195,39 @@ SELECT count(*) from test__int WHERE a @@ '(20&23)|(50&68)';
SELECT count(*) from test__int WHERE a @@ '20 | !21';
SELECT count(*) from test__int WHERE a @@ '!20 & !21';
+DROP INDEX text_idx;
+
+-- Repeat the same queries with an extended data set. The data set is the
+-- same that we used before, except that each element in the array is
+-- repeated three times, offset by 1000 and 2000. For example, {1, 5}
+-- becomes {1, 1001, 2001, 5, 1005, 2005}.
+--
+-- That has proven to be unreasonably effective at exercising codepaths in
+-- core GiST code related to splitting parent pages, which is not covered by
+-- other tests. This is a bit out-of-place as the point is to test core GiST
+-- code rather than this extension, but there is no suitable GiST opclass in
+-- core that would reach the same codepaths.
+CREATE TABLE more__int AS SELECT
+ -- Leave alone NULLs, empty arrays and the one row that we use to test
+ -- equality
+ CASE WHEN a IS NULL OR a = '{}' OR a = '{73,23,20}' THEN a ELSE
+ (select array_agg(u) || array_agg(u + 1000) || array_agg(u + 2000) from (select unnest(a) u) x)
+ END AS a, a as b
+ FROM test__int;
+CREATE INDEX ON more__int using gist (a gist__int_ops(numranges = 252));
+
+SELECT count(*) from more__int WHERE a && '{23,50}';
+SELECT count(*) from more__int WHERE a @@ '23|50';
+SELECT count(*) from more__int WHERE a @> '{23,50}';
+SELECT count(*) from more__int WHERE a @@ '23&50';
+SELECT count(*) from more__int WHERE a @> '{20,23}';
+SELECT count(*) from more__int WHERE a <@ '{73,23,20}';
+SELECT count(*) from more__int WHERE a = '{73,23,20}';
+SELECT count(*) from more__int WHERE a @@ '50&68';
+SELECT count(*) from more__int WHERE a @> '{20,23}' or a @> '{50,68}';
+SELECT count(*) from more__int WHERE a @@ '(20&23)|(50&68)';
+SELECT count(*) from more__int WHERE a @@ '20 | !21';
+SELECT count(*) from more__int WHERE a @@ '!20 & !21';
+
+
RESET enable_seqscan;
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index b1f19f6a8e6..3422e875ab0 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -1018,87 +1018,104 @@ gistFindPath(Relation r, BlockNumber child, OffsetNumber *downlinkoffnum)
* remain so at exit, but it might not be the same page anymore.
*/
static void
-gistFindCorrectParent(Relation r, GISTInsertStack *child)
+gistFindCorrectParent(Relation r, GISTInsertStack *child, bool is_build)
{
GISTInsertStack *parent = child->parent;
+ ItemId iid;
+ IndexTuple idxtuple;
+ OffsetNumber i,
+ maxoff;
+ GISTInsertStack *ptr;
gistcheckpage(r, parent->buffer);
parent->page = (Page) BufferGetPage(parent->buffer);
+ maxoff = PageGetMaxOffsetNumber(parent->page);
- /* here we don't need to distinguish between split and page update */
- if (child->downlinkoffnum == InvalidOffsetNumber ||
- parent->lsn != PageGetLSN(parent->page))
+ /* Check if the downlink is still where it was before */
+ if (child->downlinkoffnum != InvalidOffsetNumber && child->downlinkoffnum <= maxoff)
{
- /* parent is changed, look child in right links until found */
- OffsetNumber i,
- maxoff;
- ItemId iid;
- IndexTuple idxtuple;
- GISTInsertStack *ptr;
+ iid = PageGetItemId(parent->page, child->downlinkoffnum);
+ idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
+ if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
+ return; /* still there */
+ }
- while (true)
- {
- maxoff = PageGetMaxOffsetNumber(parent->page);
- for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
- {
- iid = PageGetItemId(parent->page, i);
- idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
- if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
- {
- /* yes!!, found */
- child->downlinkoffnum = i;
- return;
- }
- }
+ /*
+ * The page has changed since we looked. During normal operation, every
+ * update of a page changes its LSN, so the LSN we memorized should have
+ * changed too. During index build, however, we don't WAL-log the changes
+ * until we have built the index, so the LSN doesn't change. There is no
+ * concurrent activity during index build, but we might have changed the
+ * parent ourselves.
+ */
+ Assert(parent->lsn != PageGetLSN(parent->page) || is_build);
- parent->blkno = GistPageGetOpaque(parent->page)->rightlink;
- UnlockReleaseBuffer(parent->buffer);
- if (parent->blkno == InvalidBlockNumber)
+ /*
+ * Scan the page to re-find the downlink. If the page was split, it might
+ * have moved to a different page, so follow the right links until we find
+ * it.
+ */
+ while (true)
+ {
+ for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
+ {
+ iid = PageGetItemId(parent->page, i);
+ idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
+ if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
{
- /*
- * End of chain and still didn't find parent. It's a very-very
- * rare situation when root splitted.
- */
- break;
+ /* yes!!, found */
+ child->downlinkoffnum = i;
+ return;
}
- parent->buffer = ReadBuffer(r, parent->blkno);
- LockBuffer(parent->buffer, GIST_EXCLUSIVE);
- gistcheckpage(r, parent->buffer);
- parent->page = (Page) BufferGetPage(parent->buffer);
}
- /*
- * awful!!, we need search tree to find parent ... , but before we
- * should release all old parent
- */
-
- ptr = child->parent->parent; /* child->parent already released
- * above */
- while (ptr)
+ parent->blkno = GistPageGetOpaque(parent->page)->rightlink;
+ parent->downlinkoffnum = InvalidOffsetNumber;
+ UnlockReleaseBuffer(parent->buffer);
+ if (parent->blkno == InvalidBlockNumber)
{
- ReleaseBuffer(ptr->buffer);
- ptr = ptr->parent;
+ /*
+ * End of chain and still didn't find parent. It's a very-very
+ * rare situation when root splitted.
+ */
+ break;
}
+ parent->buffer = ReadBuffer(r, parent->blkno);
+ LockBuffer(parent->buffer, GIST_EXCLUSIVE);
+ gistcheckpage(r, parent->buffer);
+ parent->page = (Page) BufferGetPage(parent->buffer);
+ }
- /* ok, find new path */
- ptr = parent = gistFindPath(r, child->blkno, &child->downlinkoffnum);
+ /*
+ * awful!!, we need search tree to find parent ... , but before we should
+ * release all old parent
+ */
- /* read all buffers as expected by caller */
- /* note we don't lock them or gistcheckpage them here! */
- while (ptr)
- {
- ptr->buffer = ReadBuffer(r, ptr->blkno);
- ptr->page = (Page) BufferGetPage(ptr->buffer);
- ptr = ptr->parent;
- }
+ ptr = child->parent->parent; /* child->parent already released above */
+ while (ptr)
+ {
+ ReleaseBuffer(ptr->buffer);
+ ptr = ptr->parent;
+ }
- /* install new chain of parents to stack */
- child->parent = parent;
+ /* ok, find new path */
+ ptr = parent = gistFindPath(r, child->blkno, &child->downlinkoffnum);
- /* make recursive call to normal processing */
- LockBuffer(child->parent->buffer, GIST_EXCLUSIVE);
- gistFindCorrectParent(r, child);
+ /* read all buffers as expected by caller */
+ /* note we don't lock them or gistcheckpage them here! */
+ while (ptr)
+ {
+ ptr->buffer = ReadBuffer(r, ptr->blkno);
+ ptr->page = (Page) BufferGetPage(ptr->buffer);
+ ptr = ptr->parent;
}
+
+ /* install new chain of parents to stack */
+ child->parent = parent;
+
+ /* make recursive call to normal processing */
+ LockBuffer(child->parent->buffer, GIST_EXCLUSIVE);
+ gistFindCorrectParent(r, child, is_build);
}
/*
@@ -1106,7 +1123,7 @@ gistFindCorrectParent(Relation r, GISTInsertStack *child)
*/
static IndexTuple
gistformdownlink(Relation rel, Buffer buf, GISTSTATE *giststate,
- GISTInsertStack *stack)
+ GISTInsertStack *stack, bool is_build)
{
Page page = BufferGetPage(buf);
OffsetNumber maxoff;
@@ -1147,7 +1164,7 @@ gistformdownlink(Relation rel, Buffer buf, GISTSTATE *giststate,
ItemId iid;
LockBuffer(stack->parent->buffer, GIST_EXCLUSIVE);
- gistFindCorrectParent(rel, stack);
+ gistFindCorrectParent(rel, stack, is_build);
iid = PageGetItemId(stack->parent->page, stack->downlinkoffnum);
downlink = (IndexTuple) PageGetItem(stack->parent->page, iid);
downlink = CopyIndexTuple(downlink);
@@ -1193,7 +1210,7 @@ gistfixsplit(GISTInsertState *state, GISTSTATE *giststate)
page = BufferGetPage(buf);
/* Form the new downlink tuples to insert to parent */
- downlink = gistformdownlink(state->r, buf, giststate, stack);
+ downlink = gistformdownlink(state->r, buf, giststate, stack, state->is_build);
si->buf = buf;
si->downlink = downlink;
@@ -1347,7 +1364,7 @@ gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
right = (GISTPageSplitInfo *) list_nth(splitinfo, pos);
left = (GISTPageSplitInfo *) list_nth(splitinfo, pos - 1);
- gistFindCorrectParent(state->r, stack);
+ gistFindCorrectParent(state->r, stack, state->is_build);
if (gistinserttuples(state, stack->parent, giststate,
&right->downlink, 1,
InvalidOffsetNumber,
@@ -1372,21 +1389,22 @@ gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
*/
tuples[0] = left->downlink;
tuples[1] = right->downlink;
- gistFindCorrectParent(state->r, stack);
- if (gistinserttuples(state, stack->parent, giststate,
- tuples, 2,
- stack->downlinkoffnum,
- left->buf, right->buf,
- true, /* Unlock parent */
- unlockbuf /* Unlock stack->buffer if caller wants
- * that */
- ))
- {
- /*
- * If the parent page was split, the downlink might have moved.
- */
- stack->downlinkoffnum = InvalidOffsetNumber;
- }
+ gistFindCorrectParent(state->r, stack, state->is_build);
+ (void) gistinserttuples(state, stack->parent, giststate,
+ tuples, 2,
+ stack->downlinkoffnum,
+ left->buf, right->buf,
+ true, /* Unlock parent */
+ unlockbuf /* Unlock stack->buffer if caller
+ * wants that */
+ );
+
+ /*
+ * The downlink might have moved when we updated it. Even if the page
+ * wasn't split, because gistinserttuples() implements updating the old
+ * tuple by removing and re-inserting it!
+ */
+ stack->downlinkoffnum = InvalidOffsetNumber;
Assert(left->buf == stack->buffer);
--
2.39.2
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: BUG #18129: GiST index produces incorrect query results
2023-09-22 06:00 BUG #18129: GiST index produces incorrect query results PG Bug reporting form <noreply@postgresql.org>
2023-09-23 22:06 ` Re: BUG #18129: GiST index produces incorrect query results Heikki Linnakangas <hlinnaka@iki.fi>
2023-09-25 21:24 ` Re: BUG #18129: GiST index produces incorrect query results Heikki Linnakangas <hlinnaka@iki.fi>
@ 2023-09-26 08:08 ` Alexander Lakhin <exclusion@gmail.com>
2023-10-02 11:28 ` Re: BUG #18129: GiST index produces incorrect query results Heikki Linnakangas <hlinnaka@iki.fi>
0 siblings, 1 reply; 6+ messages in thread
From: Alexander Lakhin @ 2023-09-26 08:08 UTC (permalink / raw)
To: Heikki Linnakangas <hlinnaka@iki.fi>; pgsql-bugs@lists.postgresql.org
Hello Heikki,
26.09.2023 00:24, Heikki Linnakangas wrote:
> I spent a while trying to create a test case for this that would not require expanding the test data so much, but no
> avail. I even tried to take the same data set, but instead of duplicating each element like you did, I appended a
> random number of integers to each array, but even that did not trigger the failure. That particular data set seems
> cursed; how did you stumble upon it?
>
> I'm reluctant to just make all the arrays larger, as it makes the test 2x slower. So instead of running all the
> commands over the larger data set, I added one more copy of the CREATE INDEX and the test queries to the end that uses
> the larger set.
>
> See attached. It's squashed version of the previous patches I posted, with the test case. Barring objections, I'll
> commit this.
Thank you for working on this!
I can't review the code change in depth, unfortunately (I need time to
study gist guts), but I've tried to just test it.
And with the patch applied I get an assertion failure when the server
compiled --with-blocksize=1 (and -O0):
CPPFLAGS="-O0" ./configure -q --with-blocksize=1 --enable-debug --enable-cassert && make -s -j8 && make -s -j8 -C
contrib && make -s check -C contrib/intarray
not ok 1 - _int 806 ms
# (test process exited with exit code 2)
^C# could not stop postmaster: exit code was 2
(gdb) bt
#0 __pthread_kill_implementation (no_tid=0, signo=6, threadid=140373756303168) at ./nptl/pthread_kill.c:44
#1 __pthread_kill_internal (signo=6, threadid=140373756303168) at ./nptl/pthread_kill.c:78
#2 __GI___pthread_kill (threadid=140373756303168, signo=signo@entry=6) at ./nptl/pthread_kill.c:89
#3 0x00007fab4f409476 in __GI_raise (sig=sig@entry=6) at ../sysdeps/posix/raise.c:26
#4 0x00007fab4f3ef7f3 in __GI_abort () at ./stdlib/abort.c:79
#5 0x0000559563a87ed9 in ExceptionalCondition (conditionName=0x559563b17a28 "ItemIdHasStorage(itemId)",
fileName=0x559563b17990 "../../../../src/include/storage/bufpage.h", lineNumber=355) at assert.c:66
#6 0x00005595633334fb in PageGetItem (page=0x7fab43d15800 "", itemId=0x7fab43d1581c) at
../../../../src/include/storage/bufpage.h:355
#7 0x00005595633358e9 in gistFindCorrectParent (r=0x7fab4176b118, child=0x559565b45b18, is_build=true) at gist.c:1063
#8 0x00005595633361b5 in gistfinishsplit (state=0x7ffc087cd250, stack=0x559565b45b18, giststate=0x559565b7ecd8,
splitinfo=0x559565be0290, unlockbuf=false) at gist.c:1392
#9 0x0000559563335fdb in gistinserttuples (state=0x7ffc087cd250, stack=0x559565b45b18, giststate=0x559565b7ecd8,
tuples=0x559565b6b5d8, ntup=1, oldoffnum=0, leftchild=12421, rightchild=12422, unlockbuf=false, unlockleftchild=false)
at gist.c:1322
#10 0x000055956333612c in gistfinishsplit (state=0x7ffc087cd250, stack=0x559565b45fc8, giststate=0x559565b7ecd8,
splitinfo=0x559565b6b560, unlockbuf=false) at gist.c:1368
#11 0x0000559563335fdb in gistinserttuples (state=0x7ffc087cd250, stack=0x559565b45fc8, giststate=0x559565b7ecd8,
tuples=0x559565b692a8, ntup=1, oldoffnum=0, leftchild=12419, rightchild=12420, unlockbuf=false, unlockleftchild=false)
at gist.c:1322
....
(in fact it crashes even on `make check`)
I haven't understand the reason yet, just wanted to let you know that maybe
the patch needs one more fix before committing.
>
> ERROR: failed to add item to index page in "byteatest_a_idx1"
>
> If you make that value even larger, then it fails with a better error message:
>
> ERROR: index row requires 8208 bytes, maximum size is 8191
>
> So the "failed to add item" error doesn't seem expected.
>
Yeah, I saw that anomaly too.
Best regards,
Alexander
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: BUG #18129: GiST index produces incorrect query results
2023-09-22 06:00 BUG #18129: GiST index produces incorrect query results PG Bug reporting form <noreply@postgresql.org>
2023-09-23 22:06 ` Re: BUG #18129: GiST index produces incorrect query results Heikki Linnakangas <hlinnaka@iki.fi>
2023-09-25 21:24 ` Re: BUG #18129: GiST index produces incorrect query results Heikki Linnakangas <hlinnaka@iki.fi>
2023-09-26 08:08 ` Re: BUG #18129: GiST index produces incorrect query results Alexander Lakhin <exclusion@gmail.com>
@ 2023-10-02 11:28 ` Heikki Linnakangas <hlinnaka@iki.fi>
0 siblings, 0 replies; 6+ messages in thread
From: Heikki Linnakangas @ 2023-10-02 11:28 UTC (permalink / raw)
To: Alexander Lakhin <exclusion@gmail.com>; +Cc: pgsql-bugs
I just noticed that pgsql-bugs got dropped from this thread, so I'm
resending this with pgsql-bugs CC'd
On 26/09/2023 13:10, Alexander Lakhin wrote:
> 26.09.2023 11:08, Alexander Lakhin wrote:
>>
>> And with the patch applied I get an assertion failure when the server
>> compiled --with-blocksize=1 (and -O0):
>> CPPFLAGS="-O0" ./configure -q --with-blocksize=1 --enable-debug --enable-cassert && make -s -j8 && make -s -j8 -C
>> contrib && make -s check -C contrib/intarray
>> not ok 1 - _int 806 ms
>> # (test process exited with exit code 2)
>> ^C# could not stop postmaster: exit code was 2
>>
>> (gdb) bt
>> #0 __pthread_kill_implementation (no_tid=0, signo=6, threadid=140373756303168) at ./nptl/pthread_kill.c:44
>> #1 __pthread_kill_internal (signo=6, threadid=140373756303168) at ./nptl/pthread_kill.c:78
>> #2 __GI___pthread_kill (threadid=140373756303168, signo=signo@entry=6) at ./nptl/pthread_kill.c:89
>> #3 0x00007fab4f409476 in __GI_raise (sig=sig@entry=6) at ../sysdeps/posix/raise.c:26
>> #4 0x00007fab4f3ef7f3 in __GI_abort () at ./stdlib/abort.c:79
>> #5 0x0000559563a87ed9 in ExceptionalCondition (conditionName=0x559563b17a28 "ItemIdHasStorage(itemId)",
>> fileName=0x559563b17990 "../../../../src/include/storage/bufpage.h", lineNumber=355) at assert.c:66
>>
>> (in fact it crashes even on `make check`)
>
> My note about "-O0" was excessive — I see the failure even with "-O3", it
> just occurs not every time.
> And as to make check - that was the same issue as I reported before (bug
> #18127).
> Sorry for the noise.
>
> As to the assertion failure, maybe it's explained by the line
> maxoff = PageGetMaxOffsetNumber(parent->page);
> removed inside the while loop (I guess that maxoff recalculation is needed
> as parent->page changes inside the loop).
Yes, you're right. Fixed that, and pushed (commit 28d3c2ddcf). Thanks
for the report and debugging!
--
Heikki Linnakangas
Neon (https://neon.tech)
^ permalink raw reply [nested|flat] 6+ messages in thread
end of thread, other threads:[~2023-10-02 11:28 UTC | newest]
Thread overview: 6+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2023-09-22 06:00 BUG #18129: GiST index produces incorrect query results PG Bug reporting form <noreply@postgresql.org>
2023-09-22 13:43 ` Heikki Linnakangas <hlinnaka@iki.fi>
2023-09-23 22:06 ` Heikki Linnakangas <hlinnaka@iki.fi>
2023-09-25 21:24 ` Heikki Linnakangas <hlinnaka@iki.fi>
2023-09-26 08:08 ` Alexander Lakhin <exclusion@gmail.com>
2023-10-02 11:28 ` Heikki Linnakangas <hlinnaka@iki.fi>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox