Re: BUG #18129: GiST index produces incorrect query results

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)