/*-------------------------------------------------------------------------
*
* gindatapage.c
- * page utilities routines for the postgres inverted index access method.
+ * routines for handling GIN posting tree pages.
*
*
- * Portions Copyright (c) 1996-2006, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
* IDENTIFICATION
- * $PostgreSQL: pgsql/src/backend/access/gin/gindatapage.c,v 1.3 2006/07/16 00:52:05 tgl Exp $
+ * src/backend/access/gin/gindatapage.c
*-------------------------------------------------------------------------
*/
#include "postgres.h"
-#include "access/gin.h"
-int
-compareItemPointers( ItemPointer a, ItemPointer b ) {
- if ( GinItemPointerGetBlockNumber(a) == GinItemPointerGetBlockNumber(b) ) {
- if ( GinItemPointerGetOffsetNumber(a) == GinItemPointerGetOffsetNumber(b) )
- return 0;
- return ( GinItemPointerGetOffsetNumber(a) > GinItemPointerGetOffsetNumber(b) ) ? 1 : -1;
- }
-
- return ( GinItemPointerGetBlockNumber(a) > GinItemPointerGetBlockNumber(b) ) ? 1 : -1;
-}
+#include "access/gin_private.h"
+#include "access/heapam_xlog.h"
+#include "lib/ilist.h"
+#include "miscadmin.h"
+#include "utils/memutils.h"
+#include "utils/rel.h"
/*
- * Merge two ordered array of itempointer
+ * Min, Max and Target size of posting lists stored on leaf pages, in bytes.
+ *
+ * The code can deal with any size, but random access is more efficient when
+ * a number of smaller lists are stored, rather than one big list. If a
+ * posting list would become larger than Max size as a result of insertions,
+ * it is split into two. If a posting list would be smaller than minimum
+ * size, it is merged with the next posting list.
*/
-void
-MergeItemPointers(ItemPointerData *dst, ItemPointerData *a, uint32 na, ItemPointerData *b, uint32 nb) {
- ItemPointerData *dptr = dst;
- ItemPointerData *aptr = a, *bptr = b;
-
- while( aptr - a < na && bptr - b < nb ) {
- if ( compareItemPointers(aptr, bptr) > 0 )
- *dptr++ = *bptr++;
- else
- *dptr++ = *aptr++;
- }
+#define GinPostingListSegmentMaxSize 384
+#define GinPostingListSegmentTargetSize 256
+#define GinPostingListSegmentMinSize 128
- while( aptr - a < na )
- *dptr++ = *aptr++;
+/*
+ * At least this many items fit in a GinPostingListSegmentMaxSize-bytes
+ * long segment. This is used when estimating how much space is required
+ * for N items, at minimum.
+ */
+#define MinTuplesPerSegment ((GinPostingListSegmentMaxSize - 2) / 6)
- while( bptr - b < nb )
- *dptr++ = *bptr++;
-}
+/*
+ * A working struct for manipulating a posting tree leaf page.
+ */
+typedef struct
+{
+ dlist_head segments; /* a list of leafSegmentInfos */
+
+ /*
+ * The following fields represent how the segments are split across
+ * pages, if a page split is required. Filled in by leafRepackItems.
+ */
+ dlist_node *lastleft; /* last segment on left page */
+ int lsize; /* total size on left page */
+ int rsize; /* total size on right page */
+
+ bool oldformat; /* page is in pre-9.4 format on disk */
+} disassembledLeaf;
+
+typedef struct
+{
+ dlist_node node; /* linked list pointers */
+
+ /*-------------
+ * 'action' indicates the status of this in-memory segment, compared to
+ * what's on disk. It is one of the GIN_SEGMENT_* action codes:
+ *
+ * UNMODIFIED no changes
+ * DELETE the segment is to be removed. 'seg' and 'items' are
+ * ignored
+ * INSERT this is a completely new segment
+ * REPLACE this replaces an existing segment with new content
+ * ADDITEMS like REPLACE, but no items have been removed, and we track
+ * in detail what items have been added to this segment, in
+ * 'modifieditems'
+ *-------------
+ */
+ char action;
+
+ ItemPointerData *modifieditems;
+ int nmodifieditems;
+
+ /*
+ * The following fields represent the items in this segment. If 'items'
+ * is not NULL, it contains a palloc'd array of the itemsin this segment.
+ * If 'seg' is not NULL, it contains the items in an already-compressed
+ * format. It can point to an on-disk page (!modified), or a palloc'd
+ * segment in memory. If both are set, they must represent the same items.
+ */
+ GinPostingList *seg;
+ ItemPointer items;
+ int nitems; /* # of items in 'items', if items != NULL */
+} leafSegmentInfo;
+
+static ItemPointer dataLeafPageGetUncompressed(Page page, int *nitems);
+static void dataSplitPageInternal(GinBtree btree, Buffer origbuf,
+ GinBtreeStack *stack,
+ void *insertdata, BlockNumber updateblkno,
+ XLogRecData **prdata, Page *newlpage, Page *newrpage);
+
+static disassembledLeaf *disassembleLeaf(Page page);
+static bool leafRepackItems(disassembledLeaf *leaf, ItemPointer remaining);
+static bool addItemsToLeaf(disassembledLeaf *leaf, ItemPointer newItems,
+ int nNewItems);
+
+static XLogRecData *constructLeafRecompressWALData(Buffer buf,
+ disassembledLeaf *leaf);
+static void dataPlaceToPageLeafRecompress(Buffer buf, disassembledLeaf *leaf);
+static void dataPlaceToPageLeafSplit(Buffer buf,
+ disassembledLeaf *leaf,
+ ItemPointerData lbound, ItemPointerData rbound,
+ XLogRecData **prdata, Page lpage, Page rpage);
/*
- * Checks, should we move to right link...
- * Compares inserting itemp pointer with right bound of current page
+ * Read TIDs from leaf data page to single uncompressed array. The TIDs are
+ * returned in ascending order.
+ *
+ * advancePast is a hint, indicating that the caller is only interested in
+ * TIDs > advancePast. To return all items, use ItemPointerSetMin.
+ *
+ * Note: This function can still return items smaller than advancePast that
+ * are in the same posting list as the items of interest, so the caller must
+ * still check all the returned items. But passing it allows this function to
+ * skip whole posting lists.
*/
-static bool
-dataIsMoveRight(GinBtree btree, Page page) {
- ItemPointer iptr = GinDataPageGetRightBound(page);
+ItemPointer
+GinDataLeafPageGetItems(Page page, int *nitems, ItemPointerData advancePast)
+{
+ ItemPointer result;
+
+ if (GinPageIsCompressed(page))
+ {
+ GinPostingList *seg = GinDataLeafPageGetPostingList(page);
+ Size len = GinDataLeafPageGetPostingListSize(page);
+ Pointer endptr = ((Pointer) seg) + len;
+ GinPostingList *next;
+
+ /* Skip to the segment containing advancePast+1 */
+ if (ItemPointerIsValid(&advancePast))
+ {
+ next = GinNextPostingListSegment(seg);
+ while ((Pointer) next < endptr &&
+ ginCompareItemPointers(&next->first, &advancePast) <= 0)
+ {
+ seg = next;
+ next = GinNextPostingListSegment(seg);
+ }
+ len = endptr - (Pointer) seg;
+ }
+
+ if (len > 0)
+ result = ginPostingListDecodeAllSegments(seg, len, nitems);
+ else
+ {
+ result = NULL;
+ *nitems = 0;
+ }
+ }
+ else
+ {
+ ItemPointer tmp = dataLeafPageGetUncompressed(page, nitems);
- if ( GinPageRightMost(page) )
- return FALSE;
+ result = palloc((*nitems) * sizeof(ItemPointerData));
+ memcpy(result, tmp, (*nitems) * sizeof(ItemPointerData));
+ }
- return ( compareItemPointers( btree->items + btree->curitem, iptr ) > 0 ) ? TRUE : FALSE;
+ return result;
}
/*
- * Find correct PostingItem in non-leaf page. It supposed that
- * page correctly choosen and searching value SHOULD be on page
+ * Places all TIDs from leaf data page to bitmap.
*/
-static BlockNumber
-dataLocateItem(GinBtree btree, GinBtreeStack *stack) {
- OffsetNumber low, high, maxoff;
- PostingItem *pitem=NULL;
- int result;
- Page page = BufferGetPage( stack->buffer );
+int
+GinDataLeafPageGetItemsToTbm(Page page, TIDBitmap *tbm)
+{
+ ItemPointer uncompressed;
+ int nitems;
- Assert( !GinPageIsLeaf(page) );
- Assert( GinPageIsData(page) );
+ if (GinPageIsCompressed(page))
+ {
+ GinPostingList *segment = GinDataLeafPageGetPostingList(page);
+ Size len = GinDataLeafPageGetPostingListSize(page);
- if ( btree->fullScan ) {
- stack->off = FirstOffsetNumber;
- stack->predictNumber *= GinPageGetOpaque(page)->maxoff;
- return btree->getLeftMostPage(btree, page);
+ nitems = ginPostingListDecodeAllSegmentsToTbm(segment, len, tbm);
}
+ else
+ {
+ uncompressed = dataLeafPageGetUncompressed(page, &nitems);
- low = FirstOffsetNumber;
- maxoff = high = GinPageGetOpaque(page)->maxoff;
- Assert( high >= low );
+ if (nitems > 0)
+ tbm_add_tuples(tbm, uncompressed, nitems, false);
+ }
- high++;
+ return nitems;
+}
- while (high > low) {
- OffsetNumber mid = low + ((high - low) / 2);
- pitem = (PostingItem*)GinDataPageGetItem(page,mid);
+/*
+ * Get pointer to the uncompressed array of items on a pre-9.4 format
+ * uncompressed leaf page. The number of items in the array is returned in
+ * *nitems.
+ */
+static ItemPointer
+dataLeafPageGetUncompressed(Page page, int *nitems)
+{
+ ItemPointer items;
- if ( mid == maxoff )
- /* Right infinity, page already correctly choosen
- with a help of dataIsMoveRight */
- result = -1;
- else {
- pitem = (PostingItem*)GinDataPageGetItem(page,mid);
- result = compareItemPointers( btree->items + btree->curitem, &( pitem->key ) );
- }
+ Assert(!GinPageIsCompressed(page));
- if ( result == 0 ) {
- stack->off = mid;
- return PostingItemGetBlockNumber(pitem);
- } else if ( result > 0 )
- low = mid + 1;
- else
- high = mid;
- }
+ /*
+ * In the old pre-9.4 page format, the whole page content is used for
+ * uncompressed items, and the number of items is stored in 'maxoff'
+ */
+ items = (ItemPointer) GinDataPageGetData(page);
+ *nitems = GinPageGetOpaque(page)->maxoff;
- Assert( high>=FirstOffsetNumber && high <= maxoff );
-
- stack->off = high;
- pitem = (PostingItem*)GinDataPageGetItem(page,high);
- return PostingItemGetBlockNumber(pitem);
+ return items;
}
-/*
- * Searches correct position for value on leaf page.
- * Page should be corrrectly choosen.
- * Returns true if value found on page.
+/*
+ * Check if we should follow the right link to find the item we're searching
+ * for.
+ *
+ * Compares inserting item pointer with the right bound of the current page.
*/
static bool
-dataLocateLeafItem(GinBtree btree, GinBtreeStack *stack) {
- Page page = BufferGetPage( stack->buffer );
- OffsetNumber low, high;
- int result;
+dataIsMoveRight(GinBtree btree, Page page)
+{
+ ItemPointer iptr = GinDataPageGetRightBound(page);
- Assert( GinPageIsLeaf(page) );
- Assert( GinPageIsData(page) );
+ if (GinPageRightMost(page))
+ return FALSE;
- if ( btree->fullScan ) {
- stack->off = FirstOffsetNumber;
- return TRUE;
- }
-
- low=FirstOffsetNumber;
- high = GinPageGetOpaque(page)->maxoff;
+ return (ginCompareItemPointers(&btree->itemptr, iptr) > 0) ? TRUE : FALSE;
+}
- if ( high < low ) {
+/*
+ * Find correct PostingItem in non-leaf page. It is assumed that this is
+ * the correct page, and the searched value SHOULD be on the page.
+ */
+static BlockNumber
+dataLocateItem(GinBtree btree, GinBtreeStack *stack)
+{
+ OffsetNumber low,
+ high,
+ maxoff;
+ PostingItem *pitem = NULL;
+ int result;
+ Page page = BufferGetPage(stack->buffer);
+
+ Assert(!GinPageIsLeaf(page));
+ Assert(GinPageIsData(page));
+
+ if (btree->fullScan)
+ {
stack->off = FirstOffsetNumber;
- return false;
+ stack->predictNumber *= GinPageGetOpaque(page)->maxoff;
+ return btree->getLeftMostChild(btree, page);
}
+ low = FirstOffsetNumber;
+ maxoff = high = GinPageGetOpaque(page)->maxoff;
+ Assert(high >= low);
+
high++;
- while (high > low) {
+ while (high > low)
+ {
OffsetNumber mid = low + ((high - low) / 2);
- result = compareItemPointers( btree->items + btree->curitem, (ItemPointer)GinDataPageGetItem(page,mid) );
+ pitem = GinDataPageGetPostingItem(page, mid);
- if ( result == 0 ) {
+ if (mid == maxoff)
+ {
+ /*
+ * Right infinity, page already correctly chosen with a help of
+ * dataIsMoveRight
+ */
+ result = -1;
+ }
+ else
+ {
+ pitem = GinDataPageGetPostingItem(page, mid);
+ result = ginCompareItemPointers(&btree->itemptr, &(pitem->key));
+ }
+
+ if (result == 0)
+ {
stack->off = mid;
- return true;
- } else if ( result > 0 )
+ return PostingItemGetBlockNumber(pitem);
+ }
+ else if (result > 0)
low = mid + 1;
else
high = mid;
}
+ Assert(high >= FirstOffsetNumber && high <= maxoff);
+
stack->off = high;
- return false;
+ pitem = GinDataPageGetPostingItem(page, high);
+ return PostingItemGetBlockNumber(pitem);
}
/*
- * Finds links to blkno on non-leaf page, retuns
- * offset of PostingItem
+ * Find link to blkno on non-leaf page, returns offset of PostingItem
*/
static OffsetNumber
-dataFindChildPtr(GinBtree btree, Page page, BlockNumber blkno, OffsetNumber storedOff) {
- OffsetNumber i, maxoff = GinPageGetOpaque(page)->maxoff;
+dataFindChildPtr(GinBtree btree, Page page, BlockNumber blkno, OffsetNumber storedOff)
+{
+ OffsetNumber i,
+ maxoff = GinPageGetOpaque(page)->maxoff;
PostingItem *pitem;
- Assert( !GinPageIsLeaf(page) );
- Assert( GinPageIsData(page) );
+ Assert(!GinPageIsLeaf(page));
+ Assert(GinPageIsData(page));
- /* if page isn't changed, we returns storedOff */
- if ( storedOff>= FirstOffsetNumber && storedOff<=maxoff) {
- pitem = (PostingItem*)GinDataPageGetItem(page, storedOff);
- if ( PostingItemGetBlockNumber(pitem) == blkno )
+ /* if page isn't changed, we return storedOff */
+ if (storedOff >= FirstOffsetNumber && storedOff <= maxoff)
+ {
+ pitem = GinDataPageGetPostingItem(page, storedOff);
+ if (PostingItemGetBlockNumber(pitem) == blkno)
return storedOff;
- /* we hope, that needed pointer goes to right. It's true
- if there wasn't a deletion */
- for( i=storedOff+1 ; i <= maxoff ; i++ ) {
- pitem = (PostingItem*)GinDataPageGetItem(page, i);
- if ( PostingItemGetBlockNumber(pitem) == blkno )
+ /*
+ * we hope, that needed pointer goes to right. It's true if there
+ * wasn't a deletion
+ */
+ for (i = storedOff + 1; i <= maxoff; i++)
+ {
+ pitem = GinDataPageGetPostingItem(page, i);
+ if (PostingItemGetBlockNumber(pitem) == blkno)
return i;
}
- maxoff = storedOff-1;
+ maxoff = storedOff - 1;
}
/* last chance */
- for( i=FirstOffsetNumber; i <= maxoff ; i++ ) {
- pitem = (PostingItem*)GinDataPageGetItem(page, i);
- if ( PostingItemGetBlockNumber(pitem) == blkno )
+ for (i = FirstOffsetNumber; i <= maxoff; i++)
+ {
+ pitem = GinDataPageGetPostingItem(page, i);
+ if (PostingItemGetBlockNumber(pitem) == blkno)
return i;
}
}
/*
- * retunrs blkno of lefmost child
+ * Return blkno of leftmost child
*/
static BlockNumber
-dataGetLeftMostPage(GinBtree btree, Page page) {
+dataGetLeftMostPage(GinBtree btree, Page page)
+{
PostingItem *pitem;
- Assert( !GinPageIsLeaf(page) );
- Assert( GinPageIsData(page) );
- Assert( GinPageGetOpaque(page)->maxoff >= FirstOffsetNumber );
+ Assert(!GinPageIsLeaf(page));
+ Assert(GinPageIsData(page));
+ Assert(GinPageGetOpaque(page)->maxoff >= FirstOffsetNumber);
- pitem = (PostingItem*)GinDataPageGetItem(page, FirstOffsetNumber);
+ pitem = GinDataPageGetPostingItem(page, FirstOffsetNumber);
return PostingItemGetBlockNumber(pitem);
}
/*
- * add ItemPointer or PostingItem to page. data should points to
- * correct value! depending on leaf or non-leaf page
+ * Add PostingItem to a non-leaf page.
*/
void
-GinDataPageAddItem( Page page, void *data, OffsetNumber offset ) {
+GinDataPageAddPostingItem(Page page, PostingItem *data, OffsetNumber offset)
+{
OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
- char *ptr;
+ char *ptr;
+
+ Assert(PostingItemGetBlockNumber(data) != InvalidBlockNumber);
+ Assert(!GinPageIsLeaf(page));
- if ( offset == InvalidOffsetNumber ) {
- ptr = GinDataPageGetItem(page,maxoff+1);
- } else {
- ptr = GinDataPageGetItem(page,offset);
- if ( maxoff+1-offset != 0 )
- memmove( ptr+GinSizeOfItem(page), ptr, (maxoff-offset+1) * GinSizeOfItem(page) );
+ if (offset == InvalidOffsetNumber)
+ {
+ ptr = (char *) GinDataPageGetPostingItem(page, maxoff + 1);
}
- memcpy( ptr, data, GinSizeOfItem(page) );
+ else
+ {
+ ptr = (char *) GinDataPageGetPostingItem(page, offset);
+ if (offset != maxoff + 1)
+ memmove(ptr + sizeof(PostingItem),
+ ptr,
+ (maxoff - offset + 1) * sizeof(PostingItem));
+ }
+ memcpy(ptr, data, sizeof(PostingItem));
GinPageGetOpaque(page)->maxoff++;
}
/*
- * Deletes posting item from non-leaf page
+ * Delete posting item from non-leaf page
*/
void
-PageDeletePostingItem(Page page, OffsetNumber offset) {
- OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
+GinPageDeletePostingItem(Page page, OffsetNumber offset)
+{
+ OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
- Assert( !GinPageIsLeaf(page) );
- Assert( offset>=FirstOffsetNumber && offset <= maxoff );
+ Assert(!GinPageIsLeaf(page));
+ Assert(offset >= FirstOffsetNumber && offset <= maxoff);
- if ( offset != maxoff )
- memmove( GinDataPageGetItem(page,offset), GinDataPageGetItem(page,offset+1),
- sizeof(PostingItem) * (maxoff-offset) );
+ if (offset != maxoff)
+ memmove(GinDataPageGetPostingItem(page, offset),
+ GinDataPageGetPostingItem(page, offset + 1),
+ sizeof(PostingItem) * (maxoff - offset));
GinPageGetOpaque(page)->maxoff--;
}
/*
- * checks space to install new value,
- * item pointer never deletes!
+ * Places keys to leaf data page and fills WAL record.
*/
-static bool
-dataIsEnoughSpace( GinBtree btree, Buffer buf, OffsetNumber off ) {
- Page page = BufferGetPage(buf);
-
- Assert( GinPageIsData(page) );
- Assert( !btree->isDelete );
-
- if ( GinPageIsLeaf(page) ) {
- if ( GinPageRightMost(page) && off > GinPageGetOpaque(page)->maxoff ) {
- if ( (btree->nitem - btree->curitem) * sizeof(ItemPointerData) <= GinDataPageGetFreeSpace(page) )
- return true;
- } else if ( sizeof(ItemPointerData) <= GinDataPageGetFreeSpace(page) )
- return true;
- } else if ( sizeof(PostingItem) <= GinDataPageGetFreeSpace(page) )
- return true;
+static GinPlaceToPageRC
+dataPlaceToPageLeaf(GinBtree btree, Buffer buf, GinBtreeStack *stack,
+ void *insertdata, XLogRecData **prdata,
+ Page *newlpage, Page *newrpage)
+{
+ GinBtreeDataLeafInsertData *items = insertdata;
+ ItemPointer newItems = &items->items[items->curitem];
+ int maxitems = items->nitem - items->curitem;
+ Page page = BufferGetPage(buf);
+ int i;
+ ItemPointerData rbound;
+ ItemPointerData lbound;
+ bool needsplit;
+ bool append;
+ int segsize;
+ Size freespace;
+ MemoryContext tmpCxt;
+ MemoryContext oldCxt;
+ disassembledLeaf *leaf;
+ leafSegmentInfo *lastleftinfo;
+ ItemPointerData maxOldItem;
+ ItemPointerData remaining;
+
+ Assert(GinPageIsData(page));
+
+ rbound = *GinDataPageGetRightBound(page);
+
+ /*
+ * Count how many of the new items belong to this page.
+ */
+ if (!GinPageRightMost(page))
+ {
+ for (i = 0; i < maxitems; i++)
+ {
+ if (ginCompareItemPointers(&newItems[i], &rbound) > 0)
+ {
+ /*
+ * This needs to go to some other location in the tree. (The
+ * caller should've chosen the insert location so that at least
+ * the first item goes here.)
+ */
+ Assert(i > 0);
+ break;
+ }
+ }
+ maxitems = i;
+ }
- return false;
+ /*
+ * The following operations do quite a lot of small memory allocations,
+ * create a temporary memory context so that we don't need to keep track
+ * of them individually.
+ */
+ tmpCxt = AllocSetContextCreate(CurrentMemoryContext,
+ "Gin split temporary context",
+ ALLOCSET_DEFAULT_MINSIZE,
+ ALLOCSET_DEFAULT_INITSIZE,
+ ALLOCSET_DEFAULT_MAXSIZE);
+ oldCxt = MemoryContextSwitchTo(tmpCxt);
+
+ leaf = disassembleLeaf(page);
+
+ /*
+ * Are we appending to the end of the page? IOW, are all the new items
+ * larger than any of the existing items.
+ */
+ if (!dlist_is_empty(&leaf->segments))
+ {
+ lastleftinfo = dlist_container(leafSegmentInfo, node,
+ dlist_tail_node(&leaf->segments));
+ if (!lastleftinfo->items)
+ lastleftinfo->items = ginPostingListDecode(lastleftinfo->seg,
+ &lastleftinfo->nitems);
+ maxOldItem = lastleftinfo->items[lastleftinfo->nitems - 1];
+ if (ginCompareItemPointers(&newItems[0], &maxOldItem) >= 0)
+ append = true;
+ else
+ append = false;
+ }
+ else
+ {
+ ItemPointerSetMin(&maxOldItem);
+ append = true;
+ }
+
+ /*
+ * If we're appending to the end of the page, we will append as many items
+ * as we can fit (after splitting), and stop when the pages becomes full.
+ * Otherwise we have to limit the number of new items to insert, because
+ * once we start packing we can't just stop when we run out of space,
+ * because we must make sure that all the old items still fit.
+ */
+ if (GinPageIsCompressed(page))
+ freespace = GinDataLeafPageGetFreeSpace(page);
+ else
+ freespace = 0;
+ if (append)
+ {
+ /*
+ * Even when appending, trying to append more items than will fit is
+ * not completely free, because we will merge the new items and old
+ * items into an array below. In the best case, every new item fits in
+ * a single byte, and we can use all the free space on the old page as
+ * well as the new page. For simplicity, ignore segment overhead etc.
+ */
+ maxitems = Min(maxitems, freespace + GinDataLeafMaxContentSize);
+ }
+ else
+ {
+ /*
+ * Calculate a conservative estimate of how many new items we can fit
+ * on the two pages after splitting.
+ *
+ * We can use any remaining free space on the old page to store full
+ * segments, as well as the new page. Each full-sized segment can hold
+ * at least MinTuplesPerSegment items
+ */
+ int nnewsegments;
+
+ nnewsegments = freespace / GinPostingListSegmentMaxSize;
+ nnewsegments += GinDataLeafMaxContentSize / GinPostingListSegmentMaxSize;
+ maxitems = Min(maxitems, nnewsegments * MinTuplesPerSegment);
+ }
+
+ /* Add the new items to the segments */
+ if (!addItemsToLeaf(leaf, newItems, maxitems))
+ {
+ /* all items were duplicates, we have nothing to do */
+ items->curitem += maxitems;
+
+ MemoryContextSwitchTo(oldCxt);
+ MemoryContextDelete(tmpCxt);
+
+ return UNMODIFIED;
+ }
+
+ /*
+ * Pack the items back to compressed segments, ready for writing to disk.
+ */
+ needsplit = leafRepackItems(leaf, &remaining);
+
+ /*
+ * Did all the new items fit?
+ *
+ * If we're appending, it's OK if they didn't. But as a sanity check,
+ * verify that all the old items fit.
+ */
+ if (ItemPointerIsValid(&remaining))
+ {
+ if (!append || ItemPointerCompare(&maxOldItem, &remaining) >= 0)
+ elog(ERROR, "could not split GIN page; all old items didn't fit");
+
+ /* Count how many of the new items did fit. */
+ for (i = 0; i < maxitems; i++)
+ {
+ if (ginCompareItemPointers(&newItems[i], &remaining) >= 0)
+ break;
+ }
+ if (i == 0)
+ elog(ERROR, "could not split GIN page; no new items fit");
+ maxitems = i;
+ }
+
+ if (!needsplit)
+ {
+ /*
+ * Great, all the items fit on a single page. Construct a WAL record
+ * describing the changes we made, and write the segments back to the
+ * page.
+ *
+ * Once we start modifying the page, there's no turning back. The
+ * caller is responsible for calling END_CRIT_SECTION() after writing
+ * the WAL record.
+ */
+ MemoryContextSwitchTo(oldCxt);
+ if (RelationNeedsWAL(btree->index))
+ *prdata = constructLeafRecompressWALData(buf, leaf);
+ else
+ *prdata = NULL;
+ START_CRIT_SECTION();
+ dataPlaceToPageLeafRecompress(buf, leaf);
+
+ if (append)
+ elog(DEBUG2, "appended %d new items to block %u; %d bytes (%d to go)",
+ maxitems, BufferGetBlockNumber(buf), (int) leaf->lsize,
+ items->nitem - items->curitem - maxitems);
+ else
+ elog(DEBUG2, "inserted %d new items to block %u; %d bytes (%d to go)",
+ maxitems, BufferGetBlockNumber(buf), (int) leaf->lsize,
+ items->nitem - items->curitem - maxitems);
+ }
+ else
+ {
+ /*
+ * Had to split.
+ *
+ * We already divided the segments between the left and the right
+ * page. The left page was filled as full as possible, and the rest
+ * overflowed to the right page. When building a new index, that's
+ * good, because the table is scanned from beginning to end and there
+ * won't be any more insertions to the left page during the build.
+ * This packs the index as tight as possible. But otherwise, split
+ * 50/50, by moving segments from the left page to the right page
+ * until they're balanced.
+ *
+ * As a further heuristic, when appending items to the end of the
+ * page, split 75/25, one the assumption that subsequent insertions
+ * will probably also go to the end. This packs the index somewhat
+ * tighter when appending to a table, which is very common.
+ */
+ if (!btree->isBuild)
+ {
+ while (dlist_has_prev(&leaf->segments, leaf->lastleft))
+ {
+ lastleftinfo = dlist_container(leafSegmentInfo, node, leaf->lastleft);
+
+ segsize = SizeOfGinPostingList(lastleftinfo->seg);
+ if (append)
+ {
+ if ((leaf->lsize - segsize) - (leaf->lsize - segsize) < BLCKSZ / 4)
+ break;
+ }
+ else
+ {
+ if ((leaf->lsize - segsize) - (leaf->rsize + segsize) < 0)
+ break;
+ }
+
+ leaf->lsize -= segsize;
+ leaf->rsize += segsize;
+ leaf->lastleft = dlist_prev_node(&leaf->segments, leaf->lastleft);
+ }
+ }
+ Assert(leaf->lsize <= GinDataLeafMaxContentSize);
+ Assert(leaf->rsize <= GinDataLeafMaxContentSize);
+
+ /*
+ * Fetch the max item in the left page's last segment; it becomes the
+ * right bound of the page.
+ */
+ lastleftinfo = dlist_container(leafSegmentInfo, node, leaf->lastleft);
+ if (!lastleftinfo->items)
+ lastleftinfo->items = ginPostingListDecode(lastleftinfo->seg,
+ &lastleftinfo->nitems);
+ lbound = lastleftinfo->items[lastleftinfo->nitems - 1];
+
+ *newlpage = MemoryContextAlloc(oldCxt, BLCKSZ);
+ *newrpage = MemoryContextAlloc(oldCxt, BLCKSZ);
+
+ dataPlaceToPageLeafSplit(buf, leaf, lbound, rbound,
+ prdata, *newlpage, *newrpage);
+
+ Assert(GinPageRightMost(page) ||
+ ginCompareItemPointers(GinDataPageGetRightBound(*newlpage),
+ GinDataPageGetRightBound(*newrpage)) < 0);
+
+ if (append)
+ elog(DEBUG2, "appended %d items to block %u; split %d/%d (%d to go)",
+ maxitems, BufferGetBlockNumber(buf), (int) leaf->lsize, (int) leaf->rsize,
+ items->nitem - items->curitem - maxitems);
+ else
+ elog(DEBUG2, "inserted %d items to block %u; split %d/%d (%d to go)",
+ maxitems, BufferGetBlockNumber(buf), (int) leaf->lsize, (int) leaf->rsize,
+ items->nitem - items->curitem - maxitems);
+ }
+
+ MemoryContextSwitchTo(oldCxt);
+ MemoryContextDelete(tmpCxt);
+
+ items->curitem += maxitems;
+
+ return needsplit ? SPLIT : INSERTED;
}
/*
- * In case of previous split update old child blkno to
- * new right page
- * item pointer never deletes!
+ * Vacuum a posting tree leaf page.
*/
-static BlockNumber
-dataPrepareData( GinBtree btree, Page page, OffsetNumber off) {
- BlockNumber ret = InvalidBlockNumber;
+void
+ginVacuumPostingTreeLeaf(Relation indexrel, Buffer buffer, GinVacuumState *gvs)
+{
+ Page page = BufferGetPage(buffer);
+ disassembledLeaf *leaf;
+ bool removedsomething = false;
+ dlist_iter iter;
+
+ leaf = disassembleLeaf(page);
+
+ /* Vacuum each segment. */
+ dlist_foreach(iter, &leaf->segments)
+ {
+ leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node, iter.cur);
+ int oldsegsize;
+ ItemPointer cleaned;
+ int ncleaned;
+
+ if (!seginfo->items)
+ seginfo->items = ginPostingListDecode(seginfo->seg,
+ &seginfo->nitems);
+ if (seginfo->seg)
+ oldsegsize = SizeOfGinPostingList(seginfo->seg);
+ else
+ oldsegsize = GinDataLeafMaxContentSize;
+
+ cleaned = ginVacuumItemPointers(gvs,
+ seginfo->items,
+ seginfo->nitems,
+ &ncleaned);
+ pfree(seginfo->items);
+ seginfo->items = NULL;
+ seginfo->nitems = 0;
+ if (cleaned)
+ {
+ if (ncleaned > 0)
+ {
+ int npacked;
+
+ seginfo->seg = ginCompressPostingList(cleaned,
+ ncleaned,
+ oldsegsize,
+ &npacked);
+ /* Removing an item never increases the size of the segment */
+ if (npacked != ncleaned)
+ elog(ERROR, "could not fit vacuumed posting list");
+ seginfo->action = GIN_SEGMENT_REPLACE;
+ }
+ else
+ {
+ seginfo->seg = NULL;
+ seginfo->items = NULL;
+ seginfo->action = GIN_SEGMENT_DELETE;
+ }
+ seginfo->nitems = ncleaned;
+
+ removedsomething = true;
+ }
+ }
+
+ /*
+ * If we removed any items, reconstruct the page from the pieces.
+ *
+ * We don't try to re-encode the segments here, even though some of them
+ * might be really small now that we've removed some items from them. It
+ * seems like a waste of effort, as there isn't really any benefit from
+ * larger segments per se; larger segments only help to pack more items
+ * in the same space. We might as well delay doing that until the next
+ * insertion, which will need to re-encode at least part of the page
+ * anyway.
+ *
+ * Also note if the page was in uncompressed, pre-9.4 format before, it
+ * is now represented as one huge segment that contains all the items.
+ * It might make sense to split that, to speed up random access, but we
+ * don't bother. You'll have to REINDEX anyway if you want the full gain
+ * of the new tighter index format.
+ */
+ if (removedsomething)
+ {
+ XLogRecData *payloadrdata = NULL;
+ bool modified;
+
+ /*
+ * Make sure we have a palloc'd copy of all segments, after the first
+ * segment that is modified. (dataPlaceToPageLeafRecompress requires
+ * this).
+ */
+ modified = false;
+ dlist_foreach(iter, &leaf->segments)
+ {
+ leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
+ iter.cur);
+ if (seginfo->action != GIN_SEGMENT_UNMODIFIED)
+ modified = true;
+ if (modified && seginfo->action != GIN_SEGMENT_DELETE)
+ {
+ int segsize = SizeOfGinPostingList(seginfo->seg);
+ GinPostingList *tmp = (GinPostingList *) palloc(segsize);
+
+ memcpy(tmp, seginfo->seg, segsize);
+ seginfo->seg = tmp;
+ }
+ }
+
+ if (RelationNeedsWAL(indexrel))
+ payloadrdata = constructLeafRecompressWALData(buffer, leaf);
+ START_CRIT_SECTION();
+ dataPlaceToPageLeafRecompress(buffer, leaf);
+
+ MarkBufferDirty(buffer);
+
+ if (RelationNeedsWAL(indexrel))
+ {
+ XLogRecPtr recptr;
+ XLogRecData rdata;
+ ginxlogVacuumDataLeafPage xlrec;
+
+ xlrec.node = indexrel->rd_node;
+ xlrec.blkno = BufferGetBlockNumber(buffer);
- Assert( GinPageIsData(page) );
+ rdata.buffer = InvalidBuffer;
+ rdata.data = (char *) &xlrec;
+ rdata.len = offsetof(ginxlogVacuumDataLeafPage, data);
+ rdata.next = payloadrdata;
- if ( !GinPageIsLeaf(page) && btree->rightblkno != InvalidBlockNumber ) {
- PostingItem *pitem = (PostingItem*)GinDataPageGetItem(page,off);
- PostingItemSetBlockNumber( pitem, btree->rightblkno );
- ret = btree->rightblkno;
+ recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_VACUUM_DATA_LEAF_PAGE, &rdata);
+ PageSetLSN(page, recptr);
+ }
+
+ END_CRIT_SECTION();
}
+}
- btree->rightblkno = InvalidBlockNumber;
+/*
+ * Construct a ginxlogRecompressDataLeaf record representing the changes
+ * in *leaf.
+ */
+static XLogRecData *
+constructLeafRecompressWALData(Buffer buf, disassembledLeaf *leaf)
+{
+ int nmodified = 0;
+ char *walbufbegin;
+ char *walbufend;
+ XLogRecData *rdata;
+ dlist_iter iter;
+ int segno;
+ ginxlogRecompressDataLeaf *recompress_xlog;
+
+ /* Count the modified segments */
+ dlist_foreach(iter, &leaf->segments)
+ {
+ leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
+ iter.cur);
+
+ if (seginfo->action != GIN_SEGMENT_UNMODIFIED)
+ nmodified++;
+ }
+
+ walbufbegin = palloc(
+ sizeof(ginxlogRecompressDataLeaf) +
+ BLCKSZ + /* max size needed to hold the segment data */
+ nmodified * 2 + /* (segno + action) per action */
+ sizeof(XLogRecData));
+ walbufend = walbufbegin;
+
+ recompress_xlog = (ginxlogRecompressDataLeaf *) walbufend;
+ walbufend += sizeof(ginxlogRecompressDataLeaf);
+
+ recompress_xlog->nactions = nmodified;
+
+ segno = 0;
+ dlist_foreach(iter, &leaf->segments)
+ {
+ leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
+ iter.cur);
+ int segsize = 0;
+ int datalen;
+ uint8 action = seginfo->action;
+
+ if (action == GIN_SEGMENT_UNMODIFIED)
+ {
+ segno++;
+ continue;
+ }
+
+ if (action != GIN_SEGMENT_DELETE)
+ segsize = SizeOfGinPostingList(seginfo->seg);
+
+ /*
+ * If storing the uncompressed list of added item pointers would take
+ * more space than storing the compressed segment as is, do that
+ * instead.
+ */
+ if (action == GIN_SEGMENT_ADDITEMS &&
+ seginfo->nmodifieditems * sizeof(ItemPointerData) > segsize)
+ {
+ action = GIN_SEGMENT_REPLACE;
+ }
+
+ *((uint8 *) (walbufend++)) = segno;
+ *(walbufend++) = action;
+
+ switch (action)
+ {
+ case GIN_SEGMENT_DELETE:
+ datalen = 0;
+ break;
+
+ case GIN_SEGMENT_ADDITEMS:
+ datalen = seginfo->nmodifieditems * sizeof(ItemPointerData);
+ memcpy(walbufend, &seginfo->nmodifieditems, sizeof(uint16));
+ memcpy(walbufend + sizeof(uint16), seginfo->modifieditems, datalen);
+ datalen += sizeof(uint16);
+ break;
+
+ case GIN_SEGMENT_INSERT:
+ case GIN_SEGMENT_REPLACE:
+ datalen = SHORTALIGN(segsize);
+ memcpy(walbufend, seginfo->seg, segsize);
+ break;
+
+ default:
+ elog(ERROR, "unexpected GIN leaf action %d", action);
+ }
+ walbufend += datalen;
+
+ if (action != GIN_SEGMENT_INSERT)
+ segno++;
+ }
- return ret;
+ rdata = (XLogRecData *) MAXALIGN(walbufend);
+ rdata->buffer = buf;
+ rdata->buffer_std = TRUE;
+ rdata->data = walbufbegin;
+ rdata->len = walbufend - walbufbegin;
+ rdata->next = NULL;
+
+ return rdata;
+}
+
+/*
+ * Assemble a disassembled posting tree leaf page back to a buffer.
+ *
+ * *prdata is filled with WAL information about this operation. The caller
+ * is responsible for inserting to the WAL, along with any other information
+ * about the operation that triggered this recompression.
+ *
+ * NOTE: The segment pointers must not point directly to the same buffer,
+ * except for segments that have not been modified and whose preceding
+ * segments have not been modified either.
+ */
+static void
+dataPlaceToPageLeafRecompress(Buffer buf, disassembledLeaf *leaf)
+{
+ Page page = BufferGetPage(buf);
+ char *ptr;
+ int newsize;
+ bool modified = false;
+ dlist_iter iter;
+ int segsize;
+
+ /*
+ * If the page was in pre-9.4 format before, convert the header, and
+ * force all segments to be copied to the page whether they were modified
+ * or not.
+ */
+ if (!GinPageIsCompressed(page))
+ {
+ Assert(leaf->oldformat);
+ GinPageSetCompressed(page);
+ GinPageGetOpaque(page)->maxoff = InvalidOffsetNumber;
+ modified = true;
+ }
+
+ ptr = (char *) GinDataLeafPageGetPostingList(page);
+ newsize = 0;
+ dlist_foreach(iter, &leaf->segments)
+ {
+ leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node, iter.cur);
+
+ if (seginfo->action != GIN_SEGMENT_UNMODIFIED)
+ modified = true;
+
+ if (seginfo->action != GIN_SEGMENT_DELETE)
+ {
+ segsize = SizeOfGinPostingList(seginfo->seg);
+
+ if (modified)
+ memcpy(ptr, seginfo->seg, segsize);
+
+ ptr += segsize;
+ newsize += segsize;
+ }
+ }
+
+ Assert(newsize <= GinDataLeafMaxContentSize);
+ GinDataLeafPageSetPostingListSize(page, newsize);
}
-/*
- * Places keys to page and fills WAL record. In case leaf page and
- * build mode puts all ItemPointers to page.
+/*
+ * Like dataPlaceToPageLeafRecompress, but writes the disassembled leaf
+ * segments to two pages instead of one.
+ *
+ * This is different from the non-split cases in that this does not modify
+ * the original page directly, but to temporary in-memory copies of the new
+ * left and right pages.
*/
static void
-dataPlaceToPage(GinBtree btree, Buffer buf, OffsetNumber off, XLogRecData **prdata) {
- Page page = BufferGetPage(buf);
+dataPlaceToPageLeafSplit(Buffer buf, disassembledLeaf *leaf,
+ ItemPointerData lbound, ItemPointerData rbound,
+ XLogRecData **prdata, Page lpage, Page rpage)
+{
+ char *ptr;
+ int segsize;
+ int lsize;
+ int rsize;
+ dlist_node *node;
+ dlist_node *firstright;
+ leafSegmentInfo *seginfo;
+ /* these must be static so they can be returned to caller */
+ static ginxlogSplitDataLeaf split_xlog;
static XLogRecData rdata[3];
- int sizeofitem = GinSizeOfItem(page);
- static ginxlogInsert data;
- *prdata = rdata;
- Assert( GinPageIsData(page) );
+ /* Initialize temporary pages to hold the new left and right pages */
+ GinInitPage(lpage, GIN_DATA | GIN_LEAF | GIN_COMPRESSED, BLCKSZ);
+ GinInitPage(rpage, GIN_DATA | GIN_LEAF | GIN_COMPRESSED, BLCKSZ);
+
+ /*
+ * Copy the segments that go to the left page.
+ *
+ * XXX: We should skip copying the unmodified part of the left page, like
+ * we do when recompressing.
+ */
+ lsize = 0;
+ ptr = (char *) GinDataLeafPageGetPostingList(lpage);
+ firstright = dlist_next_node(&leaf->segments, leaf->lastleft);
+ for (node = dlist_head_node(&leaf->segments);
+ node != firstright;
+ node = dlist_next_node(&leaf->segments, node))
+ {
+ seginfo = dlist_container(leafSegmentInfo, node, node);
+
+ if (seginfo->action != GIN_SEGMENT_DELETE)
+ {
+ segsize = SizeOfGinPostingList(seginfo->seg);
+ memcpy(ptr, seginfo->seg, segsize);
+ ptr += segsize;
+ lsize += segsize;
+ }
+ }
+ Assert(lsize == leaf->lsize);
+ GinDataLeafPageSetPostingListSize(lpage, lsize);
+ *GinDataPageGetRightBound(lpage) = lbound;
+
+ /* Copy the segments that go to the right page */
+ ptr = (char *) GinDataLeafPageGetPostingList(rpage);
+ rsize = 0;
+ for (node = firstright;
+ ;
+ node = dlist_next_node(&leaf->segments, node))
+ {
+ seginfo = dlist_container(leafSegmentInfo, node, node);
+
+ if (seginfo->action != GIN_SEGMENT_DELETE)
+ {
+ segsize = SizeOfGinPostingList(seginfo->seg);
+ memcpy(ptr, seginfo->seg, segsize);
+ ptr += segsize;
+ rsize += segsize;
+ }
- data.updateBlkno = dataPrepareData( btree, page, off );
+ if (!dlist_has_next(&leaf->segments, node))
+ break;
+ }
+ Assert(rsize == leaf->rsize);
+ GinDataLeafPageSetPostingListSize(rpage, rsize);
+ *GinDataPageGetRightBound(rpage) = rbound;
- data.node = btree->index->rd_node;
- data.blkno = BufferGetBlockNumber( buf );
- data.offset = off;
- data.nitem = 1;
- data.isDelete = FALSE;
- data.isData = TRUE;
- data.isLeaf = GinPageIsLeaf(page) ? TRUE : FALSE;
-
- rdata[0].buffer = buf;
- rdata[0].buffer_std = FALSE;
- rdata[0].data = NULL;
- rdata[0].len = 0;
+ /* Create WAL record */
+ split_xlog.lsize = lsize;
+ split_xlog.rsize = rsize;
+ split_xlog.lrightbound = lbound;
+ split_xlog.rrightbound = rbound;
+
+ rdata[0].buffer = InvalidBuffer;
+ rdata[0].data = (char *) &split_xlog;
+ rdata[0].len = sizeof(ginxlogSplitDataLeaf);
rdata[0].next = &rdata[1];
rdata[1].buffer = InvalidBuffer;
- rdata[1].data = (char *) &data;
- rdata[1].len = sizeof(ginxlogInsert);
+ rdata[1].data = (char *) GinDataLeafPageGetPostingList(lpage);
+ rdata[1].len = lsize;
rdata[1].next = &rdata[2];
rdata[2].buffer = InvalidBuffer;
- rdata[2].data = (GinPageIsLeaf(page)) ? ((char*)(btree->items+btree->curitem)) : ((char*)&(btree->pitem));
- rdata[2].len = sizeofitem;
+ rdata[2].data = (char *) GinDataLeafPageGetPostingList(rpage);
+ rdata[2].len = rsize;
rdata[2].next = NULL;
- if ( GinPageIsLeaf(page) ) {
- if ( GinPageRightMost(page) && off > GinPageGetOpaque(page)->maxoff ) {
- /* usually, create index... */
- uint32 savedPos = btree->curitem;
+ *prdata = rdata;
+}
- while( btree->curitem < btree->nitem ) {
- GinDataPageAddItem(page, btree->items+btree->curitem, off);
- off++;
- btree->curitem++;
- }
- data.nitem = btree->curitem-savedPos;
- rdata[2].len = sizeofitem * data.nitem;
- } else {
- GinDataPageAddItem(page, btree->items+btree->curitem, off);
- btree->curitem++;
- }
- } else
- GinDataPageAddItem(page, &(btree->pitem), off);
+/*
+ * Place a PostingItem to page, and fill a WAL record.
+ *
+ * If the item doesn't fit, returns false without modifying the page.
+ *
+ * In addition to inserting the given item, the downlink of the existing item
+ * at 'off' is updated to point to 'updateblkno'.
+ */
+static GinPlaceToPageRC
+dataPlaceToPageInternal(GinBtree btree, Buffer buf, GinBtreeStack *stack,
+ void *insertdata, BlockNumber updateblkno,
+ XLogRecData **prdata, Page *newlpage, Page *newrpage)
+{
+ Page page = BufferGetPage(buf);
+ OffsetNumber off = stack->off;
+ PostingItem *pitem;
+ /* these must be static so they can be returned to caller */
+ static XLogRecData rdata;
+ static ginxlogInsertDataInternal data;
+
+ /* split if we have to */
+ if (GinNonLeafDataPageGetFreeSpace(page) < sizeof(PostingItem))
+ {
+ dataSplitPageInternal(btree, buf, stack, insertdata, updateblkno,
+ prdata, newlpage, newrpage);
+ return SPLIT;
+ }
+
+ *prdata = &rdata;
+ Assert(GinPageIsData(page));
+
+ START_CRIT_SECTION();
+
+ /* Update existing downlink to point to next page (on internal page) */
+ pitem = GinDataPageGetPostingItem(page, off);
+ PostingItemSetBlockNumber(pitem, updateblkno);
+
+ /* Add new item */
+ pitem = (PostingItem *) insertdata;
+ GinDataPageAddPostingItem(page, pitem, off);
+
+ data.offset = off;
+ data.newitem = *pitem;
+
+ rdata.buffer = buf;
+ rdata.buffer_std = false;
+ rdata.data = (char *) &data;
+ rdata.len = sizeof(ginxlogInsertDataInternal);
+ rdata.next = NULL;
+
+ return INSERTED;
}
/*
- * split page and fills WAL record. original buffer(lbuf) leaves untouched,
- * returns shadow page of lbuf filled new data. In leaf page and build mode puts all
- * ItemPointers to pages. Also, in build mode splits data by way to full fulled
- * left page
+ * Places an item (or items) to a posting tree. Calls relevant function of
+ * internal of leaf page because they are handled very differently.
*/
-static Page
-dataSplitPage(GinBtree btree, Buffer lbuf, Buffer rbuf, OffsetNumber off, XLogRecData **prdata) {
- static ginxlogSplit data;
- static XLogRecData rdata[4];
- static char vector[2*BLCKSZ];
- char *ptr;
- OffsetNumber separator;
+static GinPlaceToPageRC
+dataPlaceToPage(GinBtree btree, Buffer buf, GinBtreeStack *stack,
+ void *insertdata, BlockNumber updateblkno,
+ XLogRecData **prdata,
+ Page *newlpage, Page *newrpage)
+{
+ Page page = BufferGetPage(buf);
+
+ Assert(GinPageIsData(page));
+
+ if (GinPageIsLeaf(page))
+ return dataPlaceToPageLeaf(btree, buf, stack, insertdata,
+ prdata, newlpage, newrpage);
+ else
+ return dataPlaceToPageInternal(btree, buf, stack,
+ insertdata, updateblkno,
+ prdata, newlpage, newrpage);
+}
+
+/*
+ * Split page and fill WAL record. Returns a new temp buffer filled with data
+ * that should go to the left page. The original buffer is left untouched.
+ */
+static void
+dataSplitPageInternal(GinBtree btree, Buffer origbuf,
+ GinBtreeStack *stack,
+ void *insertdata, BlockNumber updateblkno,
+ XLogRecData **prdata, Page *newlpage, Page *newrpage)
+{
+ Page oldpage = BufferGetPage(origbuf);
+ OffsetNumber off = stack->off;
+ int nitems = GinPageGetOpaque(oldpage)->maxoff;
+ Size pageSize = PageGetPageSize(oldpage);
+ ItemPointerData oldbound = *GinDataPageGetRightBound(oldpage);
ItemPointer bound;
- Page lpage = GinPageGetCopyPage( BufferGetPage( lbuf ) );
- ItemPointerData oldbound = *GinDataPageGetRightBound(lpage);
- int sizeofitem = GinSizeOfItem(lpage);
- OffsetNumber maxoff = GinPageGetOpaque(lpage)->maxoff;
- Page rpage = BufferGetPage( rbuf );
- Size pageSize = PageGetPageSize( lpage );
- Size freeSpace;
- uint32 nCopied = 1;
-
- GinInitPage( rpage, GinPageGetOpaque(lpage)->flags, pageSize );
- freeSpace = GinDataPageGetFreeSpace(rpage);
+ Page lpage;
+ Page rpage;
+ OffsetNumber separator;
+
+ /* these must be static so they can be returned to caller */
+ static ginxlogSplitDataInternal data;
+ static XLogRecData rdata[4];
+ static PostingItem allitems[(BLCKSZ / sizeof(PostingItem)) + 1];
+
+ lpage = PageGetTempPage(oldpage);
+ rpage = PageGetTempPage(oldpage);
+ GinInitPage(lpage, GinPageGetOpaque(oldpage)->flags, pageSize);
+ GinInitPage(rpage, GinPageGetOpaque(oldpage)->flags, pageSize);
*prdata = rdata;
- data.leftChildBlkno = ( GinPageIsLeaf(lpage) ) ?
- InvalidOffsetNumber : PostingItemGetBlockNumber( &(btree->pitem) );
- data.updateBlkno = dataPrepareData( btree, lpage, off );
-
- memcpy(vector, GinDataPageGetItem(lpage, FirstOffsetNumber),
- maxoff*sizeofitem);
-
- if ( GinPageIsLeaf(lpage) && GinPageRightMost(lpage) && off > GinPageGetOpaque(lpage)->maxoff ) {
- nCopied = 0;
- while( btree->curitem < btree->nitem && maxoff*sizeof(ItemPointerData) < 2*(freeSpace - sizeof(ItemPointerData)) ) {
- memcpy( vector + maxoff*sizeof(ItemPointerData), btree->items+btree->curitem,
- sizeof(ItemPointerData) );
- maxoff++;
- nCopied++;
- btree->curitem++;
- }
- } else {
- ptr = vector + (off-1)*sizeofitem;
- if ( maxoff+1-off != 0 )
- memmove( ptr+sizeofitem, ptr, (maxoff-off+1) * sizeofitem );
- if ( GinPageIsLeaf(lpage) ) {
- memcpy(ptr, btree->items+btree->curitem, sizeofitem );
- btree->curitem++;
- } else
- memcpy(ptr, &(btree->pitem), sizeofitem );
-
- maxoff++;
- }
-
- /* we suppose that during index creation table scaned from
- begin to end, so ItemPointers are monotonically increased.. */
- if ( btree->isBuild && GinPageRightMost(lpage) )
- separator=freeSpace/sizeofitem;
- else
- separator=maxoff/2;
- GinInitPage( rpage, GinPageGetOpaque(lpage)->flags, pageSize );
- GinInitPage( lpage, GinPageGetOpaque(rpage)->flags, pageSize );
+ /*
+ * First construct a new list of PostingItems, which includes all the
+ * old items, and the new item.
+ */
+ memcpy(allitems, GinDataPageGetPostingItem(oldpage, FirstOffsetNumber),
+ (off - 1) * sizeof(PostingItem));
+
+ allitems[off - 1] = *((PostingItem *) insertdata);
+ memcpy(&allitems[off], GinDataPageGetPostingItem(oldpage, off),
+ (nitems - (off - 1)) * sizeof(PostingItem));
+ nitems++;
+
+ /* Update existing downlink to point to next page */
+ PostingItemSetBlockNumber(&allitems[off], updateblkno);
+
+ /*
+ * When creating a new index, fit as many tuples as possible on the left
+ * page, on the assumption that the table is scanned from beginning to
+ * end. This packs the index as tight as possible.
+ */
+ if (btree->isBuild && GinPageRightMost(oldpage))
+ separator = GinNonLeafDataPageGetFreeSpace(rpage) / sizeof(PostingItem);
+ else
+ separator = nitems / 2;
- memcpy( GinDataPageGetItem(lpage, FirstOffsetNumber), vector, separator * sizeofitem );
+ memcpy(GinDataPageGetPostingItem(lpage, FirstOffsetNumber), allitems, separator * sizeof(PostingItem));
GinPageGetOpaque(lpage)->maxoff = separator;
- memcpy( GinDataPageGetItem(rpage, FirstOffsetNumber),
- vector + separator * sizeofitem, (maxoff-separator) * sizeofitem );
- GinPageGetOpaque(rpage)->maxoff = maxoff-separator;
-
- PostingItemSetBlockNumber( &(btree->pitem), BufferGetBlockNumber(lbuf) );
- if ( GinPageIsLeaf(lpage) )
- btree->pitem.key = *(ItemPointerData*)GinDataPageGetItem(lpage,
- GinPageGetOpaque(lpage)->maxoff);
- else
- btree->pitem.key = ((PostingItem*)GinDataPageGetItem(lpage,
- GinPageGetOpaque(lpage)->maxoff))->key;
- btree->rightblkno = BufferGetBlockNumber(rbuf);
+ memcpy(GinDataPageGetPostingItem(rpage, FirstOffsetNumber),
+ &allitems[separator], (nitems - separator) * sizeof(PostingItem));
+ GinPageGetOpaque(rpage)->maxoff = nitems - separator;
/* set up right bound for left page */
bound = GinDataPageGetRightBound(lpage);
- *bound = btree->pitem.key;
+ *bound = GinDataPageGetPostingItem(lpage,
+ GinPageGetOpaque(lpage)->maxoff)->key;
/* set up right bound for right page */
- bound = GinDataPageGetRightBound(rpage);
- *bound = oldbound;
+ *GinDataPageGetRightBound(rpage) = oldbound;
- data.node = btree->index->rd_node;
- data.rootBlkno = InvalidBlockNumber;
- data.lblkno = BufferGetBlockNumber( lbuf );
- data.rblkno = BufferGetBlockNumber( rbuf );
data.separator = separator;
- data.nitem = maxoff;
- data.isData = TRUE;
- data.isLeaf = GinPageIsLeaf(lpage) ? TRUE : FALSE;
- data.isRootSplit = FALSE;
+ data.nitem = nitems;
data.rightbound = oldbound;
rdata[0].buffer = InvalidBuffer;
rdata[0].data = (char *) &data;
- rdata[0].len = sizeof(ginxlogSplit);
+ rdata[0].len = sizeof(ginxlogSplitDataInternal);
rdata[0].next = &rdata[1];
rdata[1].buffer = InvalidBuffer;
- rdata[1].data = vector;
- rdata[1].len = MAXALIGN( maxoff * sizeofitem );
+ rdata[1].data = (char *) allitems;
+ rdata[1].len = nitems * sizeof(PostingItem);
rdata[1].next = NULL;
- return lpage;
+ *newlpage = lpage;
+ *newrpage = rpage;
+}
+
+/*
+ * Construct insertion payload for inserting the downlink for given buffer.
+ */
+static void *
+dataPrepareDownlink(GinBtree btree, Buffer lbuf)
+{
+ PostingItem *pitem = palloc(sizeof(PostingItem));
+ Page lpage = BufferGetPage(lbuf);
+
+ PostingItemSetBlockNumber(pitem, BufferGetBlockNumber(lbuf));
+ pitem->key = *GinDataPageGetRightBound(lpage);
+
+ return pitem;
}
/*
- * Fills new root by right bound values from child.
+ * Fills new root by right bound values from child.
* Also called from ginxlog, should not use btree
*/
void
-dataFillRoot(GinBtree btree, Buffer root, Buffer lbuf, Buffer rbuf) {
- Page page = BufferGetPage(root),
- lpage = BufferGetPage(lbuf),
- rpage = BufferGetPage(rbuf);
- PostingItem li, ri;
+ginDataFillRoot(GinBtree btree, Page root, BlockNumber lblkno, Page lpage, BlockNumber rblkno, Page rpage)
+{
+ PostingItem li,
+ ri;
li.key = *GinDataPageGetRightBound(lpage);
- PostingItemSetBlockNumber( &li, BufferGetBlockNumber(lbuf) );
- GinDataPageAddItem(page, &li, InvalidOffsetNumber );
+ PostingItemSetBlockNumber(&li, lblkno);
+ GinDataPageAddPostingItem(root, &li, InvalidOffsetNumber);
ri.key = *GinDataPageGetRightBound(rpage);
- PostingItemSetBlockNumber( &ri, BufferGetBlockNumber(rbuf) );
- GinDataPageAddItem(page, &ri, InvalidOffsetNumber );
+ PostingItemSetBlockNumber(&ri, rblkno);
+ GinDataPageAddPostingItem(root, &ri, InvalidOffsetNumber);
}
-void
-prepareDataScan( GinBtree btree, Relation index) {
- memset(btree, 0, sizeof(GinBtreeData));
- btree->index = index;
- btree->isMoveRight = dataIsMoveRight;
- btree->findChildPage = dataLocateItem;
- btree->findItem = dataLocateLeafItem;
- btree->findChildPtr = dataFindChildPtr;
- btree->getLeftMostPage = dataGetLeftMostPage;
- btree->isEnoughSpace = dataIsEnoughSpace;
- btree->placeToPage = dataPlaceToPage;
- btree->splitPage = dataSplitPage;
- btree->fillRoot = dataFillRoot;
- btree->searchMode = FALSE;
- btree->isDelete = FALSE;
- btree->fullScan = FALSE;
- btree->isBuild= FALSE;
+/*** Functions to work with disassembled leaf pages ***/
+
+/*
+ * Disassemble page into a disassembledLeaf struct.
+ */
+static disassembledLeaf *
+disassembleLeaf(Page page)
+{
+ disassembledLeaf *leaf;
+ GinPostingList *seg;
+ Pointer segbegin;
+ Pointer segend;
+
+ leaf = palloc0(sizeof(disassembledLeaf));
+ dlist_init(&leaf->segments);
+
+ if (GinPageIsCompressed(page))
+ {
+ /*
+ * Create a leafSegment entry for each segment.
+ */
+ seg = GinDataLeafPageGetPostingList(page);
+ segbegin = (Pointer) seg;
+ segend = segbegin + GinDataLeafPageGetPostingListSize(page);
+ while ((Pointer) seg < segend)
+ {
+ leafSegmentInfo *seginfo = palloc(sizeof(leafSegmentInfo));
+
+ seginfo->action = GIN_SEGMENT_UNMODIFIED;
+ seginfo->seg = seg;
+ seginfo->items = NULL;
+ seginfo->nitems = 0;
+ dlist_push_tail(&leaf->segments, &seginfo->node);
+
+ seg = GinNextPostingListSegment(seg);
+ }
+ leaf->oldformat = false;
+ }
+ else
+ {
+ /*
+ * A pre-9.4 format uncompressed page is represented by a single
+ * segment, with an array of items.
+ */
+ ItemPointer uncompressed;
+ int nuncompressed;
+ leafSegmentInfo *seginfo;
+
+ uncompressed = dataLeafPageGetUncompressed(page, &nuncompressed);
+
+ seginfo = palloc(sizeof(leafSegmentInfo));
+
+ seginfo->action = GIN_SEGMENT_REPLACE;
+ seginfo->seg = NULL;
+ seginfo->items = palloc(nuncompressed * sizeof(ItemPointerData));
+ memcpy(seginfo->items, uncompressed, nuncompressed * sizeof(ItemPointerData));
+ seginfo->nitems = nuncompressed;
+
+ dlist_push_tail(&leaf->segments, &seginfo->node);
+
+ leaf->oldformat = true;
+ }
+
+ return leaf;
}
-GinPostingTreeScan*
-prepareScanPostingTree( Relation index, BlockNumber rootBlkno, bool searchMode) {
- GinPostingTreeScan *gdi = (GinPostingTreeScan*)palloc0( sizeof(GinPostingTreeScan) );
+/*
+ * Distribute newItems to the segments.
+ *
+ * Any segments that acquire new items are decoded, and the new items are
+ * merged with the old items.
+ *
+ * Returns true if any new items were added. False means they were all
+ * duplicates of existing items on the page.
+ */
+static bool
+addItemsToLeaf(disassembledLeaf *leaf, ItemPointer newItems, int nNewItems)
+{
+ dlist_iter iter;
+ ItemPointer nextnew = newItems;
+ int newleft = nNewItems;
+ bool modified = false;
+ leafSegmentInfo *newseg;
+
+ /*
+ * If the page is completely empty, just construct one new segment to
+ * hold all the new items.
+ */
+ if (dlist_is_empty(&leaf->segments))
+ {
+ newseg = palloc(sizeof(leafSegmentInfo));
+ newseg->seg = NULL;
+ newseg->items = newItems;
+ newseg->nitems = nNewItems;
+ newseg->action = GIN_SEGMENT_INSERT;
+ dlist_push_tail(&leaf->segments, &newseg->node);
+ return true;
+ }
+
+ dlist_foreach(iter, &leaf->segments)
+ {
+ leafSegmentInfo *cur = (leafSegmentInfo *) dlist_container(leafSegmentInfo, node, iter.cur);
+ int nthis;
+ ItemPointer tmpitems;
+ int ntmpitems;
+
+ /*
+ * How many of the new items fall into this segment?
+ */
+ if (!dlist_has_next(&leaf->segments, iter.cur))
+ nthis = newleft;
+ else
+ {
+ leafSegmentInfo *next;
+ ItemPointerData next_first;
+
+ next = (leafSegmentInfo *) dlist_container(leafSegmentInfo, node,
+ dlist_next_node(&leaf->segments, iter.cur));
+ if (next->items)
+ next_first = next->items[0];
+ else
+ {
+ Assert(next->seg != NULL);
+ next_first = next->seg->first;
+ }
+
+ nthis = 0;
+ while (nthis < newleft && ginCompareItemPointers(&nextnew[nthis], &next_first) < 0)
+ nthis++;
+ }
+ if (nthis == 0)
+ continue;
+
+ /* Merge the new items with the existing items. */
+ if (!cur->items)
+ cur->items = ginPostingListDecode(cur->seg, &cur->nitems);
+
+ /*
+ * Fast path for the important special case that we're appending to
+ * the end of the page: don't let the last segment on the page grow
+ * larger than the target, create a new segment before that happens.
+ */
+ if (!dlist_has_next(&leaf->segments, iter.cur) &&
+ ginCompareItemPointers(&cur->items[cur->nitems - 1], &nextnew[0]) < 0 &&
+ cur->seg != NULL &&
+ SizeOfGinPostingList(cur->seg) >= GinPostingListSegmentTargetSize)
+ {
+ newseg = palloc(sizeof(leafSegmentInfo));
+ newseg->seg = NULL;
+ newseg->items = nextnew;
+ newseg->nitems = nthis;
+ newseg->action = GIN_SEGMENT_INSERT;
+ dlist_push_tail(&leaf->segments, &newseg->node);
+ modified = true;
+ break;
+ }
- prepareDataScan( &gdi->btree, index );
-
- gdi->btree.searchMode = searchMode;
- gdi->btree.fullScan = searchMode;
+ tmpitems = ginMergeItemPointers(cur->items, cur->nitems,
+ nextnew, nthis,
+ &ntmpitems);
+ if (ntmpitems != cur->nitems)
+ {
+ /*
+ * If there are no duplicates, track the added items so that we
+ * can emit a compact ADDITEMS WAL record later on. (it doesn't
+ * seem worth re-checking which items were duplicates, if there
+ * were any)
+ */
+ if (ntmpitems == nthis + cur->nitems &&
+ cur->action == GIN_SEGMENT_UNMODIFIED)
+ {
+ cur->action = GIN_SEGMENT_ADDITEMS;
+ cur->modifieditems = nextnew;
+ cur->nmodifieditems = nthis;
+ }
+ else
+ cur->action = GIN_SEGMENT_REPLACE;
- gdi->stack = ginPrepareFindLeafPage( &gdi->btree, rootBlkno );
+ cur->items = tmpitems;
+ cur->nitems = ntmpitems;
+ cur->seg = NULL;
+ modified = true;
+ }
- return gdi;
+ nextnew += nthis;
+ newleft -= nthis;
+ if (newleft == 0)
+ break;
+ }
+
+ return modified;
}
/*
- * Inserts array of item pointers, may execute several tree scan (very rare)
+ * Recompresses all segments that have been modified.
+ *
+ * If not all the items fit on two pages (ie. after split), we store as
+ * many items as fit, and set *remaining to the first item that didn't fit.
+ * If all items fit, *remaining is set to invalid.
+ *
+ * Returns true if the page has to be split.
*/
-void
-insertItemPointer(GinPostingTreeScan *gdi, ItemPointerData *items, uint32 nitem) {
- BlockNumber rootBlkno = gdi->stack->blkno;
+static bool
+leafRepackItems(disassembledLeaf *leaf, ItemPointer remaining)
+{
+ int pgused = 0;
+ bool needsplit = false;
+ dlist_iter iter;
+ int segsize;
+ leafSegmentInfo *nextseg;
+ int npacked;
+ bool modified;
+ dlist_node *cur_node;
+ dlist_node *next_node;
+
+ ItemPointerSetInvalid(remaining);
+
+ /*
+ * cannot use dlist_foreach_modify here because we insert adjacent items
+ * while iterating.
+ */
+ for (cur_node = dlist_head_node(&leaf->segments);
+ cur_node != NULL;
+ cur_node = next_node)
+ {
+ leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
+ cur_node);
+
+ if (dlist_has_next(&leaf->segments, cur_node))
+ next_node = dlist_next_node(&leaf->segments, cur_node);
+ else
+ next_node = NULL;
+
+ /* Compress the posting list, if necessary */
+ if (seginfo->action != GIN_SEGMENT_DELETE)
+ {
+ if (seginfo->seg == NULL)
+ {
+ if (seginfo->nitems > GinPostingListSegmentMaxSize)
+ npacked = 0; /* no chance that it would fit. */
+ else
+ {
+ seginfo->seg = ginCompressPostingList(seginfo->items,
+ seginfo->nitems,
+ GinPostingListSegmentMaxSize,
+ &npacked);
+ }
+ if (npacked != seginfo->nitems)
+ {
+ /*
+ * Too large. Compress again to the target size, and create
+ * a new segment to represent the remaining items. The new
+ * segment is inserted after this one, so it will be
+ * processed in the next iteration of this loop.
+ */
+ if (seginfo->seg)
+ pfree(seginfo->seg);
+ seginfo->seg = ginCompressPostingList(seginfo->items,
+ seginfo->nitems,
+ GinPostingListSegmentTargetSize,
+ &npacked);
+ if (seginfo->action != GIN_SEGMENT_INSERT)
+ seginfo->action = GIN_SEGMENT_REPLACE;
+
+ nextseg = palloc(sizeof(leafSegmentInfo));
+ nextseg->action = GIN_SEGMENT_INSERT;
+ nextseg->seg = NULL;
+ nextseg->items = &seginfo->items[npacked];
+ nextseg->nitems = seginfo->nitems - npacked;
+ next_node = &nextseg->node;
+ dlist_insert_after(cur_node, next_node);
+ }
+ }
+
+ /*
+ * If the segment is very small, merge it with the next segment.
+ */
+ if (SizeOfGinPostingList(seginfo->seg) < GinPostingListSegmentMinSize && next_node)
+ {
+ int nmerged;
+
+ nextseg = dlist_container(leafSegmentInfo, node, next_node);
+
+ if (seginfo->items == NULL)
+ seginfo->items = ginPostingListDecode(seginfo->seg,
+ &seginfo->nitems);
+ if (nextseg->items == NULL)
+ nextseg->items = ginPostingListDecode(nextseg->seg,
+ &nextseg->nitems);
+ nextseg->items =
+ ginMergeItemPointers(seginfo->items, seginfo->nitems,
+ nextseg->items, nextseg->nitems,
+ &nmerged);
+ Assert(nmerged == seginfo->nitems + nextseg->nitems);
+ nextseg->nitems = nmerged;
+ nextseg->seg = NULL;
+
+ nextseg->action = GIN_SEGMENT_REPLACE;
+ nextseg->modifieditems = NULL;
+ nextseg->nmodifieditems = 0;
+
+ if (seginfo->action == GIN_SEGMENT_INSERT)
+ {
+ dlist_delete(cur_node);
+ continue;
+ }
+ else
+ {
+ seginfo->action = GIN_SEGMENT_DELETE;
+ seginfo->seg = NULL;
+ }
+ }
+
+ seginfo->items = NULL;
+ seginfo->nitems = 0;
+ }
+
+ if (seginfo->action == GIN_SEGMENT_DELETE)
+ continue;
+
+ /*
+ * OK, we now have a compressed version of this segment ready for
+ * copying to the page. Did we exceed the size that fits on one page?
+ */
+ segsize = SizeOfGinPostingList(seginfo->seg);
+ if (pgused + segsize > GinDataLeafMaxContentSize)
+ {
+ if (!needsplit)
+ {
+ /* switch to right page */
+ Assert(pgused > 0);
+ leaf->lastleft = dlist_prev_node(&leaf->segments, cur_node);
+ needsplit = true;
+ leaf->lsize = pgused;
+ pgused = 0;
+ }
+ else
+ {
+ /*
+ * Filled both pages. The last segment we constructed did not
+ * fit.
+ */
+ *remaining = seginfo->seg->first;
+
+ /*
+ * remove all segments that did not fit from the list.
+ */
+ while (dlist_has_next(&leaf->segments, cur_node))
+ dlist_delete(dlist_next_node(&leaf->segments, cur_node));
+ dlist_delete(cur_node);
+ break;
+ }
+ }
+
+ pgused += segsize;
+ }
+
+ if (!needsplit)
+ {
+ leaf->lsize = pgused;
+ leaf->rsize = 0;
+ }
+ else
+ leaf->rsize = pgused;
+
+ Assert(leaf->lsize <= GinDataLeafMaxContentSize);
+ Assert(leaf->rsize <= GinDataLeafMaxContentSize);
+
+ /*
+ * Make a palloc'd copy of every segment after the first modified one,
+ * because as we start copying items to the original page, we might
+ * overwrite an existing segment.
+ */
+ modified = false;
+ dlist_foreach(iter, &leaf->segments)
+ {
+ leafSegmentInfo *seginfo = dlist_container(leafSegmentInfo, node,
+ iter.cur);
+
+ if (!modified && seginfo->action != GIN_SEGMENT_UNMODIFIED)
+ {
+ modified = true;
+ }
+ else if (modified && seginfo->action == GIN_SEGMENT_UNMODIFIED)
+ {
+ GinPostingList *tmp;
+
+ segsize = SizeOfGinPostingList(seginfo->seg);
+ tmp = palloc(segsize);
+ memcpy(tmp, seginfo->seg, segsize);
+ seginfo->seg = tmp;
+ }
+ }
+
+ return needsplit;
+}
+
- gdi->btree.items = items;
- gdi->btree.nitem = nitem;
- gdi->btree.curitem = 0;
+/*** Functions that are exported to the rest of the GIN code ***/
- while( gdi->btree.curitem < gdi->btree.nitem ) {
- if (!gdi->stack)
- gdi->stack = ginPrepareFindLeafPage( &gdi->btree, rootBlkno );
+/*
+ * Creates new posting tree containing the given TIDs. Returns the page
+ * number of the root of the new posting tree.
+ *
+ * items[] must be in sorted order with no duplicates.
+ */
+BlockNumber
+createPostingTree(Relation index, ItemPointerData *items, uint32 nitems,
+ GinStatsData *buildStats)
+{
+ BlockNumber blkno;
+ Buffer buffer;
+ Page page;
+ Pointer ptr;
+ int nrootitems;
+ int rootsize;
+
+ /*
+ * Create the root page.
+ */
+ buffer = GinNewBuffer(index);
+ page = BufferGetPage(buffer);
+ blkno = BufferGetBlockNumber(buffer);
+
+ START_CRIT_SECTION();
+
+ GinInitPage(page, GIN_DATA | GIN_LEAF | GIN_COMPRESSED, BLCKSZ);
+ GinPageGetOpaque(page)->rightlink = InvalidBlockNumber;
+
+ /*
+ * Write as many of the items to the root page as fit. In segments
+ * of max GinPostingListSegmentMaxSize bytes each.
+ */
+ nrootitems = 0;
+ rootsize = 0;
+ ptr = (Pointer) GinDataLeafPageGetPostingList(page);
+ while (nrootitems < nitems)
+ {
+ GinPostingList *segment;
+ int npacked;
+ int segsize;
+
+ segment = ginCompressPostingList(&items[nrootitems],
+ nitems - nrootitems,
+ GinPostingListSegmentMaxSize,
+ &npacked);
+ segsize = SizeOfGinPostingList(segment);
+ if (rootsize + segsize > GinDataLeafMaxContentSize)
+ break;
+
+ memcpy(ptr, segment, segsize);
+ ptr += segsize;
+ rootsize += segsize;
+ nrootitems += npacked;
+ pfree(segment);
+ }
+ GinDataLeafPageSetPostingListSize(page, rootsize);
+ MarkBufferDirty(buffer);
+
+ elog(DEBUG2, "created GIN posting tree with %d items", nrootitems);
- gdi->stack = ginFindLeafPage( &gdi->btree, gdi->stack );
+ if (RelationNeedsWAL(index))
+ {
+ XLogRecPtr recptr;
+ XLogRecData rdata[2];
+ ginxlogCreatePostingTree data;
- if ( gdi->btree.findItem( &(gdi->btree), gdi->stack ) )
- elog(ERROR,"item pointer (%u,%d) already exists",
- ItemPointerGetBlockNumber(gdi->btree.items + gdi->btree.curitem),
- ItemPointerGetOffsetNumber(gdi->btree.items + gdi->btree.curitem));
+ data.node = index->rd_node;
+ data.blkno = blkno;
+ data.size = rootsize;
- ginInsertValue(&(gdi->btree), gdi->stack);
+ rdata[0].buffer = InvalidBuffer;
+ rdata[0].data = (char *) &data;
+ rdata[0].len = sizeof(ginxlogCreatePostingTree);
+ rdata[0].next = &rdata[1];
- gdi->stack=NULL;
+ rdata[1].buffer = InvalidBuffer;
+ rdata[1].data = (char *) GinDataLeafPageGetPostingList(page);
+ rdata[1].len = rootsize;
+ rdata[1].next = NULL;
+
+ recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_CREATE_PTREE, rdata);
+ PageSetLSN(page, recptr);
}
+
+ UnlockReleaseBuffer(buffer);
+
+ END_CRIT_SECTION();
+
+ /* During index build, count the newly-added data page */
+ if (buildStats)
+ buildStats->nDataPages++;
+
+ /*
+ * Add any remaining TIDs to the newly-created posting tree.
+ */
+ if (nitems > nrootitems)
+ {
+ ginInsertItemPointers(index, blkno,
+ items + nrootitems,
+ nitems - nrootitems,
+ buildStats);
+ }
+
+ return blkno;
}
-Buffer
-scanBeginPostingTree( GinPostingTreeScan *gdi ) {
- gdi->stack = ginFindLeafPage( &gdi->btree, gdi->stack );
- return gdi->stack->buffer;
+void
+ginPrepareDataScan(GinBtree btree, Relation index, BlockNumber rootBlkno)
+{
+ memset(btree, 0, sizeof(GinBtreeData));
+
+ btree->index = index;
+ btree->rootBlkno = rootBlkno;
+
+ btree->findChildPage = dataLocateItem;
+ btree->getLeftMostChild = dataGetLeftMostPage;
+ btree->isMoveRight = dataIsMoveRight;
+ btree->findItem = NULL;
+ btree->findChildPtr = dataFindChildPtr;
+ btree->placeToPage = dataPlaceToPage;
+ btree->fillRoot = ginDataFillRoot;
+ btree->prepareDownlink = dataPrepareDownlink;
+
+ btree->isData = TRUE;
+ btree->fullScan = FALSE;
+ btree->isBuild = FALSE;
+}
+
+/*
+ * Inserts array of item pointers, may execute several tree scan (very rare)
+ */
+void
+ginInsertItemPointers(Relation index, BlockNumber rootBlkno,
+ ItemPointerData *items, uint32 nitem,
+ GinStatsData *buildStats)
+{
+ GinBtreeData btree;
+ GinBtreeDataLeafInsertData insertdata;
+ GinBtreeStack *stack;
+
+ ginPrepareDataScan(&btree, index, rootBlkno);
+ btree.isBuild = (buildStats != NULL);
+ insertdata.items = items;
+ insertdata.nitem = nitem;
+ insertdata.curitem = 0;
+
+ while (insertdata.curitem < insertdata.nitem)
+ {
+ /* search for the leaf page where the first item should go to */
+ btree.itemptr = insertdata.items[insertdata.curitem];
+ stack = ginFindLeafPage(&btree, false);
+
+ ginInsertValue(&btree, stack, &insertdata, buildStats);
+ }
}
+/*
+ * Starts a new scan on a posting tree.
+ */
+GinBtreeStack *
+ginScanBeginPostingTree(GinBtree btree, Relation index, BlockNumber rootBlkno)
+{
+ GinBtreeStack *stack;
+
+ ginPrepareDataScan(btree, index, rootBlkno);
+
+ btree->fullScan = TRUE;
+
+ stack = ginFindLeafPage(btree, TRUE);
+
+ return stack;
+}
projects / postgresql / blobdiff