diff --git a/src/backend/access/gist/gistbuild.c b/src/backend/access/gist/gistbuild.c index 988896d..9d9a031 100644 --- a/src/backend/access/gist/gistbuild.c +++ b/src/backend/access/gist/gistbuild.c @@ -55,16 +55,24 @@ typedef struct { Relation indexrel; GISTSTATE *giststate; - GISTBuildBuffers *gfbb; int64 indtuples; /* number of tuples indexed */ int64 indtuplesSize; /* total size of all indexed tuples */ Size freespace; /* amount of free space to leave on pages */ + /* + * Extra data structures used during a buffering build. GISTBuildBuffers + * contains information related to managing the build buffers. parentMap + * is a lookup table of the parent of each internal page. + */ + GISTBuildBuffers *gfbb; + HTAB *parentMap; + GistBufferingMode bufferingMode; } GISTBuildState; +/* prototypes for private functions */ static void gistInitBuffering(GISTBuildState *buildstate); static int calculatePagesPerBuffer(GISTBuildState *buildstate, int levelStep); static void gistBuildCallback(Relation index, @@ -76,18 +84,23 @@ static void gistBuildCallback(Relation index, static void gistBufferingBuildInsert(GISTBuildState *buildstate, IndexTuple itup); static bool gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, - GISTBufferingInsertStack *startparent); + BlockNumber startblkno, int startlevel); static void gistbufferinginserttuples(GISTBuildState *buildstate, Buffer buffer, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, - GISTBufferingInsertStack *path); -static void gistBufferingFindCorrectParent(GISTBuildState *buildstate, - GISTBufferingInsertStack *child); + int level, BlockNumber parent); +static Buffer gistBufferingFindCorrectParent(GISTBuildState *buildstate, + BlockNumber childblkno, + OffsetNumber *downlinkoffnum, + BlockNumber *parentblkno, int level); static void gistProcessEmptyingQueue(GISTBuildState *buildstate); static void gistEmptyAllBuffers(GISTBuildState *buildstate); -static void gistFreeUnreferencedPath(GISTBufferingInsertStack *path); static int gistGetMaxLevel(Relation index); +static void gistInitParentMap(GISTBuildState *buildstate); +static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, BlockNumber parent); +static void gistMemorizeAllDownlinks(GISTBuildState *buildstate, Buffer parent); +static BlockNumber gistGetParent(GISTBuildState *buildstate, BlockNumber child); /* * Main entry point to GiST index build. Initially calls insert over and over, @@ -392,6 +405,8 @@ gistInitBuffering(GISTBuildState *buildstate) buildstate->gfbb = gistInitBuildBuffers(pagesPerBuffer, levelStep, gistGetMaxLevel(index)); + gistInitParentMap(buildstate); + buildstate->bufferingMode = GIST_BUFFERING_ACTIVE; elog(DEBUG1, "switched to buffered GiST build; level step = %d, pagesPerBuffer = %d", @@ -514,7 +529,7 @@ static void gistBufferingBuildInsert(GISTBuildState *buildstate, IndexTuple itup) { /* Insert the tuple to buffers. */ - gistProcessItup(buildstate, itup, NULL); + gistProcessItup(buildstate, itup, 0, buildstate->gfbb->rootlevel); /* If we filled up (half of a) buffer, process buffer emptying. */ gistProcessEmptyingQueue(buildstate); @@ -528,30 +543,28 @@ gistBufferingBuildInsert(GISTBuildState *buildstate, IndexTuple itup) */ static bool gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, - GISTBufferingInsertStack *startparent) + BlockNumber startblkno, int startlevel) { GISTSTATE *giststate = buildstate->giststate; GISTBuildBuffers *gfbb = buildstate->gfbb; Relation indexrel = buildstate->indexrel; - GISTBufferingInsertStack *path; BlockNumber childblkno; Buffer buffer; bool result = false; + BlockNumber blkno; + int level; + OffsetNumber downlinkoffnum; + BlockNumber parentblkno = InvalidBlockNumber; - /* - * NULL passed in startparent means that we start index tuple processing - * from the root. - */ - if (!startparent) - path = gfbb->rootitem; - else - path = startparent; + CHECK_FOR_INTERRUPTS(); /* * Loop until we reach a leaf page (level == 0) or a level with buffers * (not including the level we start at, because we would otherwise make * no progress). */ + blkno = startblkno; + level = startlevel; for (;;) { ItemId iid; @@ -559,21 +572,21 @@ gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, newtup; Page page; OffsetNumber childoffnum; - GISTBufferingInsertStack *parent; /* Have we reached a level with buffers? */ - if (LEVEL_HAS_BUFFERS(path->level, gfbb) && path != startparent) + if (LEVEL_HAS_BUFFERS(level, gfbb) && level != startlevel) break; /* Have we reached a leaf page? */ - if (path->level == 0) + if (level == 0) break; /* * Nope. Descend down to the next level then. Choose a child to * descend down to. */ - buffer = ReadBuffer(indexrel, path->blkno); + + buffer = ReadBuffer(indexrel, blkno); LockBuffer(buffer, GIST_EXCLUSIVE); page = (Page) BufferGetPage(buffer); @@ -582,32 +595,32 @@ gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, idxtuple = (IndexTuple) PageGetItem(page, iid); childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid)); + if (level > 1) + gistMemorizeParent(buildstate, childblkno, blkno); + /* * Check that the key representing the target child node is consistent * with the key we're inserting. Update it if it's not. */ newtup = gistgetadjusted(indexrel, idxtuple, itup, giststate); if (newtup) + { gistbufferinginserttuples(buildstate, buffer, &newtup, 1, - childoffnum, path); - UnlockReleaseBuffer(buffer); + childoffnum, level, InvalidBlockNumber); + /* gistbufferinginserttuples() released the buffer */ + } + else + UnlockReleaseBuffer(buffer); - /* Create new path item representing current page */ - parent = path; - path = (GISTBufferingInsertStack *) MemoryContextAlloc(gfbb->context, - sizeof(GISTBufferingInsertStack)); - path->parent = parent; - path->level = parent->level - 1; - path->blkno = childblkno; - path->downlinkoffnum = childoffnum; - path->refCount = 0; /* it's unreferenced for now */ - - /* Adjust reference count of parent */ - if (parent) - parent->refCount++; + /* Descend to the child */ + parentblkno = blkno; + blkno = childblkno; + downlinkoffnum = childoffnum; + Assert(level > 0); + level--; } - if (LEVEL_HAS_BUFFERS(path->level, gfbb)) + if (LEVEL_HAS_BUFFERS(level, gfbb)) { /* * We've reached level with buffers. Place the index tuple to the @@ -616,8 +629,7 @@ gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, GISTNodeBuffer *childNodeBuffer; /* Find the buffer or create a new one */ - childNodeBuffer = gistGetNodeBuffer(gfbb, giststate, path->blkno, - path->downlinkoffnum, path->parent); + childNodeBuffer = gistGetNodeBuffer(gfbb, giststate, blkno, level); /* Add index tuple to it */ gistPushItupToNodeBuffer(gfbb, childNodeBuffer, itup); @@ -630,19 +642,16 @@ gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, /* * We've reached a leaf page. Place the tuple here. */ - buffer = ReadBuffer(indexrel, path->blkno); + Assert(level == 0); + buffer = ReadBuffer(indexrel, blkno); LockBuffer(buffer, GIST_EXCLUSIVE); gistbufferinginserttuples(buildstate, buffer, &itup, 1, - InvalidOffsetNumber, path); - UnlockReleaseBuffer(buffer); + InvalidOffsetNumber, level, parentblkno); + /* TODO: we should pass the downlink offnum, to avoid having to scan + * the whole parent page to find the downlink */ + /* gistbufferinginserttuples() released the buffer */ } - /* - * Free unreferenced path items, if any. Path item may be referenced by - * node buffer. - */ - gistFreeUnreferencedPath(path); - return result; } @@ -650,11 +659,14 @@ gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, * Insert tuples to a given page. * * This is analogous with gistinserttuples() in the regular insertion code. + * + * Caller should hold a lock on 'buffer' on entry. This function will unlock + * and unpin it. */ static void gistbufferinginserttuples(GISTBuildState *buildstate, Buffer buffer, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, - GISTBufferingInsertStack *path) + int level, BlockNumber parentblkno) { GISTBuildBuffers *gfbb = buildstate->gfbb; List *splitinfo; @@ -677,33 +689,40 @@ gistbufferinginserttuples(GISTBuildState *buildstate, Buffer buffer, */ if (is_split && BufferGetBlockNumber(buffer) == GIST_ROOT_BLKNO) { - GISTBufferingInsertStack *oldroot = gfbb->rootitem; Page page = BufferGetPage(buffer); - ItemId iid; - IndexTuple idxtuple; - BlockNumber leftmostchild; + OffsetNumber off; + OffsetNumber maxoff; + + Assert(level == gfbb->rootlevel); + gfbb->rootlevel++; - gfbb->rootitem = (GISTBufferingInsertStack *) MemoryContextAlloc( - gfbb->context, sizeof(GISTBufferingInsertStack)); - gfbb->rootitem->parent = NULL; - gfbb->rootitem->blkno = GIST_ROOT_BLKNO; - gfbb->rootitem->downlinkoffnum = InvalidOffsetNumber; - gfbb->rootitem->level = oldroot->level + 1; - gfbb->rootitem->refCount = 1; + elog(DEBUG1, "splitting GiST root page, now %d levels deep", gfbb->rootlevel); /* * All the downlinks on the old root page are now on one of the child - * pages. Change the block number of the old root entry in the stack - * to point to the leftmost child. The other child pages will be - * accessible from there by walking right. + * pages. Visit all the new child pages to memorize the parents of + * the grandchildren. */ - iid = PageGetItemId(page, FirstOffsetNumber); - idxtuple = (IndexTuple) PageGetItem(page, iid); - leftmostchild = ItemPointerGetBlockNumber(&(idxtuple->t_tid)); + if (gfbb->rootlevel > 1) + { + maxoff = PageGetMaxOffsetNumber(page); + for (off = FirstOffsetNumber; off <= maxoff; off++) + { + ItemId iid = PageGetItemId(page, FirstOffsetNumber); + IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid); + BlockNumber childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid)); + Buffer childbuf = ReadBuffer(buildstate->indexrel, childblkno); + LockBuffer(childbuf, GIST_SHARE); + gistMemorizeAllDownlinks(buildstate, childbuf); + UnlockReleaseBuffer(childbuf); - oldroot->parent = gfbb->rootitem; - oldroot->blkno = leftmostchild; - oldroot->downlinkoffnum = InvalidOffsetNumber; + /* + * Also remember that the parent of the new child page is + * the root block. + */ + gistMemorizeParent(buildstate, childblkno, GIST_ROOT_BLKNO); + } + } } if (splitinfo) @@ -711,16 +730,22 @@ gistbufferinginserttuples(GISTBuildState *buildstate, Buffer buffer, /* * Insert the downlinks to the parent. This is analogous with * gistfinishsplit() in the regular insertion code, but the locking is - * simpler, and we have to maintain the buffers. + * simpler, and we have to maintain the buffers on internal nodes and + * the parent map. */ IndexTuple *downlinks; int ndownlinks, i; Buffer parentBuffer; ListCell *lc; + OffsetNumber downlinkoffnum = InvalidOffsetNumber; /* Parent may have changed since we memorized this path. */ - gistBufferingFindCorrectParent(buildstate, path); + parentBuffer = gistBufferingFindCorrectParent(buildstate, + BufferGetBlockNumber(buffer), + &downlinkoffnum, + &parentblkno, + level); /* * If there's a buffer associated with this page, that needs to be @@ -732,7 +757,8 @@ gistbufferinginserttuples(GISTBuildState *buildstate, Buffer buffer, gistRelocateBuildBuffersOnSplit(gfbb, buildstate->giststate, buildstate->indexrel, - path, buffer, splitinfo); + level, + buffer, splitinfo); /* Create an array of all the downlink tuples */ ndownlinks = list_length(splitinfo); @@ -743,124 +769,115 @@ gistbufferinginserttuples(GISTBuildState *buildstate, Buffer buffer, GISTPageSplitInfo *splitinfo = lfirst(lc); /* + * Remember the parent of each new child page in our parent map. + * This assumes that the downlinks fit on the parent page. If the + * parent page is split, too, when we recurse up to insert the + * downlinks, the recursive gistbufferinginserttuples() call + * will update the map again. + */ + if (level > 0) + gistMemorizeParent(buildstate, + BufferGetBlockNumber(splitinfo->buf), + BufferGetBlockNumber(parentBuffer)); + + /* + * Also update the parent map for all the downlinks that got moved + * to a different page. (actually this also loops through the + * downlinks that stayed on the original page, but it does no + * harm). + */ + if (level > 1) + gistMemorizeAllDownlinks(buildstate, splitinfo->buf); + + /* * Since there's no concurrent access, we can release the lower - * level buffers immediately. Don't release the buffer for the - * original page, though, because the caller will release that. + * level buffers immediately. This includes the original page. */ - if (splitinfo->buf != buffer) - UnlockReleaseBuffer(splitinfo->buf); + UnlockReleaseBuffer(splitinfo->buf); downlinks[i++] = splitinfo->downlink; } /* Insert them into parent. */ - parentBuffer = ReadBuffer(buildstate->indexrel, path->parent->blkno); - LockBuffer(parentBuffer, GIST_EXCLUSIVE); gistbufferinginserttuples(buildstate, parentBuffer, downlinks, ndownlinks, - path->downlinkoffnum, path->parent); - UnlockReleaseBuffer(parentBuffer); + downlinkoffnum, level + 1, InvalidBlockNumber); list_free_deep(splitinfo); /* we don't need this anymore */ } + else + UnlockReleaseBuffer(buffer); } /* * Find correct parent by following rightlinks in buffering index build. This * method of parent searching is possible because no concurrent activity is * possible while index builds. + * + * Returns a buffer containing the parent page, exclusively-locked. + * *downlinkoffnum and *parentblkno are set to point to the downlink. */ -static void +static Buffer gistBufferingFindCorrectParent(GISTBuildState *buildstate, - GISTBufferingInsertStack *child) + BlockNumber childblkno, + OffsetNumber *downlinkoffnum, + BlockNumber *parentblkno, + int level) { - GISTBuildBuffers *gfbb = buildstate->gfbb; - Relation indexrel = buildstate->indexrel; - GISTBufferingInsertStack *parent = child->parent; - OffsetNumber i, - maxoff; - ItemId iid; - IndexTuple idxtuple; + BlockNumber parent; Buffer buffer; Page page; - bool copied = false; + OffsetNumber maxoff; + OffsetNumber off; + + if (level > 0) + parent = gistGetParent(buildstate, childblkno); + else + { + if (*parentblkno == InvalidBlockNumber) + elog(ERROR, "no parent buffer provided of child %d", childblkno); + parent = *parentblkno; + } - buffer = ReadBuffer(indexrel, parent->blkno); + buffer = ReadBuffer(buildstate->indexrel, parent); page = BufferGetPage(buffer); LockBuffer(buffer, GIST_EXCLUSIVE); - gistcheckpage(indexrel, buffer); + gistcheckpage(buildstate->indexrel, buffer); + maxoff = PageGetMaxOffsetNumber(page); /* Check if it was not moved */ - if (child->downlinkoffnum != InvalidOffsetNumber && - child->downlinkoffnum <= PageGetMaxOffsetNumber(page)) + if (parent == *parentblkno && *parentblkno != InvalidBlockNumber && + *downlinkoffnum != InvalidOffsetNumber && *downlinkoffnum <= maxoff) { - iid = PageGetItemId(page, child->downlinkoffnum); - idxtuple = (IndexTuple) PageGetItem(page, iid); - if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno) + ItemId iid = PageGetItemId(page, *downlinkoffnum); + IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid); + if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == childblkno) { /* Still there */ - UnlockReleaseBuffer(buffer); - return; + return buffer; } } - /* parent has changed, look child in right links until found */ - while (true) + /* + * Downlink was not at the offset where it used to be. Scan the page + * to find it. During normal gist insertions, it might've moved to another + * page, to the right, but during a buffering build, we keep track of + * the parent of each page in the lookup table so we should always know + * what page it's on. + */ + for (off = FirstOffsetNumber; off <= maxoff; off = OffsetNumberNext(off)) { - /* Search for relevant downlink in the current page */ - maxoff = PageGetMaxOffsetNumber(page); - for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) + ItemId iid = PageGetItemId(page, off); + IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid); + if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == childblkno) { - iid = PageGetItemId(page, i); - idxtuple = (IndexTuple) PageGetItem(page, iid); - if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno) - { - /* yes!!, found */ - child->downlinkoffnum = i; - UnlockReleaseBuffer(buffer); - return; - } + /* yes!!, found it */ + *downlinkoffnum = off; + return buffer; } - - /* - * We should copy parent path item because some other path items can - * refer to it. - */ - if (!copied) - { - parent = (GISTBufferingInsertStack *) MemoryContextAlloc(gfbb->context, - sizeof(GISTBufferingInsertStack)); - memcpy(parent, child->parent, sizeof(GISTBufferingInsertStack)); - if (parent->parent) - parent->parent->refCount++; - gistDecreasePathRefcount(child->parent); - child->parent = parent; - parent->refCount = 1; - copied = true; - } - - /* - * Not found in current page. Move towards rightlink. - */ - parent->blkno = GistPageGetOpaque(page)->rightlink; - UnlockReleaseBuffer(buffer); - - if (parent->blkno == InvalidBlockNumber) - { - /* - * End of chain and still didn't find parent. Should not happen - * during index build. - */ - break; - } - - /* Get the next page */ - buffer = ReadBuffer(indexrel, parent->blkno); - page = BufferGetPage(buffer); - LockBuffer(buffer, GIST_EXCLUSIVE); - gistcheckpage(indexrel, buffer); } - elog(ERROR, "failed to re-find parent for block %u", child->blkno); + elog(ERROR, "failed to re-find parent for block %u", childblkno); + return InvalidBuffer; /* keep compiler quiet */ } /* @@ -919,7 +936,7 @@ gistProcessEmptyingQueue(GISTBuildState *buildstate) * threshold, but we might as well keep flushing tuples from it * until we fill a lower-level buffer. */ - if (gistProcessItup(buildstate, itup, emptyingNodeBuffer->path)) + if (gistProcessItup(buildstate, itup, emptyingNodeBuffer->nodeBlocknum, emptyingNodeBuffer->level)) { /* * A lower level buffer filled up. Stop emptying this buffer, @@ -988,46 +1005,12 @@ gistEmptyAllBuffers(GISTBuildState *buildstate) gfbb->buffersOnLevels[i] = list_delete_first(gfbb->buffersOnLevels[i]); } + elog(DEBUG2, "emptied all buffers at level %d", i); } MemoryContextSwitchTo(oldCtx); } /* - * Free unreferenced parts of a path stack. - */ -static void -gistFreeUnreferencedPath(GISTBufferingInsertStack *path) -{ - while (path->refCount == 0) - { - /* - * Path part is unreferenced. We can free it and decrease reference - * count of parent. If parent becomes unreferenced too procedure - * should be repeated for it. - */ - GISTBufferingInsertStack *tmp = path->parent; - - pfree(path); - path = tmp; - if (path) - path->refCount--; - else - break; - } -} - -/* - * Decrease reference count of a path part, and free any unreferenced parts of - * the path stack. - */ -void -gistDecreasePathRefcount(GISTBufferingInsertStack *path) -{ - path->refCount--; - gistFreeUnreferencedPath(path); -} - -/* * Get the depth of the GiST index. */ static int @@ -1076,9 +1059,112 @@ gistGetMaxLevel(Relation index) /* * We're going down on the tree. It means that there is yet one more - * level is the tree. + * level in the tree. */ maxLevel++; } return maxLevel; } + + +/* + * Routines for managing the parent map. + * + * Whenever a page is split, we need to insert the downlinks into the parent. + * We need to somehow find the parent page to do that. In normal insertions, + * we keep a stack of nodes visited when we descend the tree. However, in + * buffering build, we can start descending the tree from any internal node, + * when we empty a buffer by cascading tuples to its children. So we don't + * have a full stack up to the root available at that time. + * + * So instead, we maintain a hash table to track the parent of every internal + * page. We don't need to track the parents of leaf nodes, however. Whenever + * we insert to a leaf, we've just descended down from its parent, so we know + * its immediate parent already. This helps a lot to limit the memory used + * by this hash table. + * + * Whenever an internal node is split, the parent map needs to be updated. + * the parent of the new child page needs to be recorded, and also the + * entries for all page whose downlinks are moved to a new page at the split + * needs to be updated. + * + * We also update the parent map whenever we descend the tree. That might seem + * unnecessary, because we maintain the map whenever a downlink is moved or + * created, but it is needed because we switch to buffering mode after + * creating a tree with regular index inserts. Any pages created before + * switching to buffering mode will not be present in the parent map initially, + * but will be added there the first time we visit them. + */ + +typedef struct +{ + BlockNumber childblkno; /* hash key */ + BlockNumber parentblkno; + int childlevel; +} ParentMapEntry; + +static void +gistInitParentMap(GISTBuildState *buildstate) +{ + HASHCTL hashCtl; + + hashCtl.keysize = sizeof(BlockNumber); + hashCtl.entrysize = sizeof(ParentMapEntry); + hashCtl.hcxt = CurrentMemoryContext; + hashCtl.hash = oid_hash; + buildstate->parentMap = hash_create("gistbuild parent map", + 1024, + &hashCtl, + HASH_ELEM | HASH_CONTEXT + | HASH_FUNCTION); +} + +static void +gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, BlockNumber parent) +{ + ParentMapEntry *entry; + bool found; + + entry = (ParentMapEntry *) hash_search(buildstate->parentMap, + (const void *) &child, + HASH_ENTER, + &found); + entry->parentblkno = parent; +} + +static void +gistMemorizeAllDownlinks(GISTBuildState *buildstate, Buffer parentbuf) +{ + OffsetNumber maxoff; + OffsetNumber off; + BlockNumber parentblkno = BufferGetBlockNumber(parentbuf); + Page page = BufferGetPage(parentbuf); + + Assert(!GistPageIsLeaf(page)); + + maxoff = PageGetMaxOffsetNumber(page); + for (off = FirstOffsetNumber; off <= maxoff; off++) + { + ItemId iid = PageGetItemId(page, off); + IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid); + BlockNumber childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid)); + gistMemorizeParent(buildstate, childblkno, parentblkno); + } +} + +static BlockNumber +gistGetParent(GISTBuildState *buildstate, BlockNumber child) +{ + ParentMapEntry *entry; + bool found; + + /* Find node buffer in hash table */ + entry = (ParentMapEntry *) hash_search(buildstate->parentMap, + (const void *) &child, + HASH_FIND, + &found); + if (!found) + elog(ERROR, "could not find parent of block %d in lookup table", child); + + return entry->parentblkno; +} diff --git a/src/backend/access/gist/gistbuildbuffers.c b/src/backend/access/gist/gistbuildbuffers.c index a40b838..211ad21 100644 --- a/src/backend/access/gist/gistbuildbuffers.c +++ b/src/backend/access/gist/gistbuildbuffers.c @@ -107,16 +107,7 @@ gistInitBuildBuffers(int pagesPerBuffer, int levelStep, int maxLevel) sizeof(GISTNodeBuffer *)); gfbb->loadedBuffersCount = 0; - /* - * Root path item of the tree. Updated on each root node split. - */ - gfbb->rootitem = (GISTBufferingInsertStack *) MemoryContextAlloc( - gfbb->context, sizeof(GISTBufferingInsertStack)); - gfbb->rootitem->parent = NULL; - gfbb->rootitem->blkno = GIST_ROOT_BLKNO; - gfbb->rootitem->downlinkoffnum = InvalidOffsetNumber; - gfbb->rootitem->level = maxLevel; - gfbb->rootitem->refCount = 1; + gfbb->rootlevel = maxLevel; return gfbb; } @@ -127,9 +118,7 @@ gistInitBuildBuffers(int pagesPerBuffer, int levelStep, int maxLevel) */ GISTNodeBuffer * gistGetNodeBuffer(GISTBuildBuffers *gfbb, GISTSTATE *giststate, - BlockNumber nodeBlocknum, - OffsetNumber downlinkoffnum, - GISTBufferingInsertStack *parent) + BlockNumber nodeBlocknum, int level) { GISTNodeBuffer *nodeBuffer; bool found; @@ -144,8 +133,6 @@ gistGetNodeBuffer(GISTBuildBuffers *gfbb, GISTSTATE *giststate, /* * Node buffer wasn't found. Initialize the new buffer as empty. */ - GISTBufferingInsertStack *path; - int level; MemoryContext oldcxt = MemoryContextSwitchTo(gfbb->context); /* nodeBuffer->nodeBlocknum is the hash key and was filled in already */ @@ -153,33 +140,12 @@ gistGetNodeBuffer(GISTBuildBuffers *gfbb, GISTSTATE *giststate, nodeBuffer->pageBlocknum = InvalidBlockNumber; nodeBuffer->pageBuffer = NULL; nodeBuffer->queuedForEmptying = false; - - /* - * Create a path stack for the page. - */ - if (nodeBlocknum != GIST_ROOT_BLKNO) - { - path = (GISTBufferingInsertStack *) palloc( - sizeof(GISTBufferingInsertStack)); - path->parent = parent; - path->blkno = nodeBlocknum; - path->downlinkoffnum = downlinkoffnum; - path->level = parent->level - 1; - path->refCount = 0; /* initially unreferenced */ - parent->refCount++; /* this path references its parent */ - Assert(path->level > 0); - } - else - path = gfbb->rootitem; - - nodeBuffer->path = path; - path->refCount++; + nodeBuffer->level = level; /* * Add this buffer to the list of buffers on this level. Enlarge * buffersOnLevels array if needed. */ - level = path->level; if (level >= gfbb->buffersOnLevelsLen) { int i; @@ -210,20 +176,6 @@ gistGetNodeBuffer(GISTBuildBuffers *gfbb, GISTSTATE *giststate, MemoryContextSwitchTo(oldcxt); } - else - { - if (parent != nodeBuffer->path->parent) - { - /* - * A different parent path item was provided than we've - * remembered. We trust caller to provide more correct parent than - * we have. Previous parent may be outdated by page split. - */ - gistDecreasePathRefcount(nodeBuffer->path->parent); - nodeBuffer->path->parent = parent; - parent->refCount++; - } - } return nodeBuffer; } @@ -585,7 +537,7 @@ typedef struct */ void gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb, GISTSTATE *giststate, - Relation r, GISTBufferingInsertStack *path, + Relation r, int level, Buffer buffer, List *splitinfo) { RelocationBufferInfo *relocationBuffersInfos; @@ -601,7 +553,7 @@ gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb, GISTSTATE *giststate, ListCell *lc; /* If the splitted page doesn't have buffers, we have nothing to do. */ - if (!LEVEL_HAS_BUFFERS(path->level, gfbb)) + if (!LEVEL_HAS_BUFFERS(level, gfbb)) return; /* @@ -660,14 +612,11 @@ gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb, GISTSTATE *giststate, /* * Create a node buffer for the page. The leftmost half is on the same * block as the old page before split, so for the leftmost half this - * will return the original buffer, which was emptied earlier in this - * function. + * will return the original buffer. The tuples on the original buffer + * were relinked to the temporary buffer, so the original one is now + * empty. */ - newNodeBuffer = gistGetNodeBuffer(gfbb, - giststate, - BufferGetBlockNumber(si->buf), - path->downlinkoffnum, - path->parent); + newNodeBuffer = gistGetNodeBuffer(gfbb, giststate, BufferGetBlockNumber(si->buf), level); relocationBuffersInfos[i].nodeBuffer = newNodeBuffer; relocationBuffersInfos[i].splitinfo = si; diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.h index 481ef5f..5ad9858 100644 --- a/src/include/access/gist_private.h +++ b/src/include/access/gist_private.h @@ -329,7 +329,7 @@ typedef struct /* is this a temporary copy, not in the hash table? */ bool isTemp; - struct GISTBufferingInsertStack *path; + int level; /* 0 == leaf */ } GISTNodeBuffer; /* @@ -338,7 +338,7 @@ typedef struct */ #define LEVEL_HAS_BUFFERS(nlevel, gfbb) \ ((nlevel) != 0 && (nlevel) % (gfbb)->levelStep == 0 && \ - (nlevel) != (gfbb)->rootitem->level) + (nlevel) != (gfbb)->rootlevel) /* Is specified buffer at least half-filled (should be queued for emptying)? */ #define BUFFER_HALF_FILLED(nodeBuffer, gfbb) \ @@ -353,26 +353,6 @@ typedef struct ((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer) /* - * Extended GISTInsertStack for buffering GiST index build. - */ -typedef struct GISTBufferingInsertStack -{ - /* current page */ - BlockNumber blkno; - - /* offset of the downlink in the parent page, that points to this page */ - OffsetNumber downlinkoffnum; - - /* pointer to parent */ - struct GISTBufferingInsertStack *parent; - - int refCount; - - /* level number */ - int level; -} GISTBufferingInsertStack; - -/* * Data structure with general information about build buffers. */ typedef struct GISTBuildBuffers @@ -416,8 +396,8 @@ typedef struct GISTBuildBuffers int loadedBuffersCount; /* # of entries in loadedBuffers */ int loadedBuffersLen; /* allocated size of loadedBuffers */ - /* A path item that points to the current root node */ - GISTBufferingInsertStack *rootitem; + /* Level of the current root node (= height of the index tree - 1) */ + int rootlevel; } GISTBuildBuffers; /* @@ -551,15 +531,13 @@ extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup, /* gistbuild.c */ extern Datum gistbuild(PG_FUNCTION_ARGS); extern void gistValidateBufferingOption(char *value); -extern void gistDecreasePathRefcount(GISTBufferingInsertStack *path); /* gistbuildbuffers.c */ extern GISTBuildBuffers *gistInitBuildBuffers(int pagesPerBuffer, int levelStep, int maxLevel); extern GISTNodeBuffer *gistGetNodeBuffer(GISTBuildBuffers *gfbb, GISTSTATE *giststate, - BlockNumber blkno, OffsetNumber downlinkoffnum, - GISTBufferingInsertStack *parent); + BlockNumber blkno, int level); extern void gistPushItupToNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer, IndexTuple item); extern bool gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb, @@ -567,7 +545,7 @@ extern bool gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb, extern void gistFreeBuildBuffers(GISTBuildBuffers *gfbb); extern void gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb, GISTSTATE *giststate, Relation r, - GISTBufferingInsertStack *path, Buffer buffer, + int level, Buffer buffer, List *splitinfo); extern void gistUnloadNodeBuffers(GISTBuildBuffers *gfbb);