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
*** a/src/backend/access/gist/gist.c
--- b/src/backend/access/gist/gist.c
***
*** 148,163 gistinsert(PG_FUNCTION_ARGS)
--- 148,169
* pages are released; note that new tuple(s) are *not* on the root page
* but in one of the new child pages.
*
+ * If 'newblkno' is not NULL, returns the block number of page the first
+ * new/updated tuple was inserted to. Usually it's the given page, but could
+ * be its right sibling if the page was split.
+ *
* Returns 'true' if the page was split, 'false' otherwise.
*/
bool
gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
Buffer buffer,
IndexTuple *itup, int ntup, OffsetNumber oldoffnum,
+ BlockNumber *newblkno,
Buffer leftchildbuf,
List **splitinfo,
bool markfollowright)
{
+ BlockNumber blkno = BufferGetBlockNumber(buffer);
Page page = BufferGetPage(buffer);
bool is_leaf = (GistPageIsLeaf(page)) ? true : false;
XLogRecPtr recptr;
***
*** 199,205 gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
BlockNumber oldrlink = InvalidBlockNumber;
GistNSN oldnsn = 0;
SplitedPageLayout rootpg;
- BlockNumber blkno = BufferGetBlockNumber(buffer);
bool is_rootsplit;
is_rootsplit = (blkno == GIST_ROOT_BLKNO);
--- 205,210
***
*** 319,327 gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
for (i = 0; i < ptr->block.num; i++)
{
! if (PageAddItem(ptr->page, (Item) data, IndexTupleSize((IndexTuple) data), i + FirstOffsetNumber, false, false) == InvalidOffsetNumber)
elog(ERROR, "failed to add item to index page in \"%s\"", RelationGetRelationName(rel));
! data += IndexTupleSize((IndexTuple) data);
}
/* Set up rightlinks */
--- 324,342
for (i = 0; i < ptr->block.num; i++)
{
! IndexTuple thistup = (IndexTuple) data;
!
! if (PageAddItem(ptr->page, (Item) data, IndexTupleSize(thistup), i + FirstOffsetNumber, false, false) == InvalidOffsetNumber)
elog(ERROR, "failed to add item to index page in \"%s\"", RelationGetRelationName(rel));
!
! /*
! * If this is the first inserted/updated tuple, let the caller
! * know which page it landed on.
! */
! if (newblkno && ItemPointerEquals(&thistup->t_tid, &(*itup)->t_tid
