Re: ERROR - CREATE GIST INDEX on 9.2 beta3

On 15.08.2012 09:50, Heikki Linnakangas wrote:
> On 15.08.2012 01:02, Zdeněk Jílovec wrote:
>> Hello,
>>
>> I use PostgreSQL 9.2beta3 with PostGIS 2.0.1 and if I try create GIST
>> index
>> on column geometry(Point,2065) I get error:
>>
>> test=> CREATE INDEX places_point ON places USING GIST(def_point);
>> ERROR: failed to re-find parent for block 18097
>>
>> It works on 9.1
>
> Hmm, I bet this is a bug in the new GiST buffering build code. There was
> an earlier bug that led to "failed to re-find parent" errors that I
> fixed back in May, but maybe I missed some corner case.

Zdeněk sent me the dump and instructions off-list, and I was able to
reproduce and diagnose the bug. Many thanks for that! It was indeed a
corner-case in the parent tracking logic.

During the build, we maintain a hash table of the parent of each page.
The hash table is used to find the parent of a page, when a page is
split and we have to insert the downlinks of the new pages to the
parent. In a regular GiST insertion, we always descend the tree from the
root to leaf, and we get the parent pointers from the stack. During a
buffered build, we don't have such a stack available, because we can
start the descend from a buffer in the middle of the tree. So we use the
parent map instead.

However, the parent hash table does not track the immediate parents of
leaf pages. That's not required, because even though we can begin the
descend somewhere in the middle of the tree, when we descend to a leaf
page we know the immediate parent where we came from. Not tracking the
leaf level saves a considerable amount of memory.

But just before we descend to the leaf page, we check if the downlink
needs to be adjusted to accommodate the new tuple, and replace it with
an updated tuple if so. The bug arises when updating the downlink of the
leaf splits the parent page, and the downlink is moved to a right
sibling. When we then descend to the leaf page, the parent of the leaf
page is incorrect, the real parent is somewhere to the right of where we
think it is.

In a normal index insert that case is covered by the logic to move right
if the downlink is not found on the expected page. In the buffering
build, we don't do that because we think we know exactly what the parent
of each page is.

I committed the attached patch to fix that. With the patch, when the
downlink is updated in the parent page, the gistbufferinginserttuples()
function returns the block where the updated tuple was placed, so that
when we descend to the leaf, we know the parent of the leaf correctly.

--
   Heikki Linnakangas
   EnterpriseDB   http://www.enterprisedb.com