gindatapage.c File Reference

#include "postgres.h"
#include "access/gin_private.h"
#include "access/ginxlog.h"
#include "access/xloginsert.h"
#include "lib/ilist.h"
#include "miscadmin.h"
#include "storage/predicate.h"
#include "utils/rel.h"

Include dependency graph for gindatapage.c:

Go to the source code of this file.

Data Structures
struct	disassembledLeaf
struct	leafSegmentInfo

Macros
#define	GinPostingListSegmentMaxSize   384
#define	GinPostingListSegmentTargetSize   256
#define	GinPostingListSegmentMinSize   128
#define	MinTuplesPerSegment   ((GinPostingListSegmentMaxSize - 2) / 6)

Functions
static ItemPointer	dataLeafPageGetUncompressed (Page page, int *nitems)
static void	dataSplitPageInternal (GinBtree btree, Buffer origbuf, GinBtreeStack *stack, void *insertdata, BlockNumber updateblkno, 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 void	computeLeafRecompressWALData (disassembledLeaf *leaf)
static void	dataPlaceToPageLeafRecompress (Buffer buf, disassembledLeaf *leaf)
static void	dataPlaceToPageLeafSplit (disassembledLeaf *leaf, ItemPointerData lbound, ItemPointerData rbound, Page lpage, Page rpage)
ItemPointer	GinDataLeafPageGetItems (Page page, int *nitems, ItemPointerData advancePast)
int	GinDataLeafPageGetItemsToTbm (Page page, TIDBitmap *tbm)
static bool	dataIsMoveRight (GinBtree btree, Page page)
static BlockNumber	dataLocateItem (GinBtree btree, GinBtreeStack *stack)
static OffsetNumber	dataFindChildPtr (GinBtree btree, Page page, BlockNumber blkno, OffsetNumber storedOff)
static BlockNumber	dataGetLeftMostPage (GinBtree btree, Page page)
void	GinDataPageAddPostingItem (Page page, PostingItem *data, OffsetNumber offset)
void	GinPageDeletePostingItem (Page page, OffsetNumber offset)
static GinPlaceToPageRC	dataBeginPlaceToPageLeaf (GinBtree btree, Buffer buf, GinBtreeStack *stack, void *insertdata, void **ptp_workspace, Page *newlpage, Page *newrpage)
static void	dataExecPlaceToPageLeaf (GinBtree btree, Buffer buf, GinBtreeStack *stack, void *insertdata, void *ptp_workspace)
void	ginVacuumPostingTreeLeaf (Relation indexrel, Buffer buffer, GinVacuumState *gvs)
static GinPlaceToPageRC	dataBeginPlaceToPageInternal (GinBtree btree, Buffer buf, GinBtreeStack *stack, void *insertdata, BlockNumber updateblkno, void **ptp_workspace, Page *newlpage, Page *newrpage)
static void	dataExecPlaceToPageInternal (GinBtree btree, Buffer buf, GinBtreeStack *stack, void *insertdata, BlockNumber updateblkno, void *ptp_workspace)
static GinPlaceToPageRC	dataBeginPlaceToPage (GinBtree btree, Buffer buf, GinBtreeStack *stack, void *insertdata, BlockNumber updateblkno, void **ptp_workspace, Page *newlpage, Page *newrpage)
static void	dataExecPlaceToPage (GinBtree btree, Buffer buf, GinBtreeStack *stack, void *insertdata, BlockNumber updateblkno, void *ptp_workspace)
static void *	dataPrepareDownlink (GinBtree btree, Buffer lbuf)
void	ginDataFillRoot (GinBtree btree, Page root, BlockNumber lblkno, Page lpage, BlockNumber rblkno, Page rpage)
BlockNumber	createPostingTree (Relation index, ItemPointerData *items, uint32 nitems, GinStatsData *buildStats, Buffer entrybuffer)
static void	ginPrepareDataScan (GinBtree btree, Relation index, BlockNumber rootBlkno)
void	ginInsertItemPointers (Relation index, BlockNumber rootBlkno, ItemPointerData *items, uint32 nitem, GinStatsData *buildStats)
GinBtreeStack *	ginScanBeginPostingTree (GinBtree btree, Relation index, BlockNumber rootBlkno)

Macro Definition Documentation

GinPostingListSegmentMaxSize

#define GinPostingListSegmentMaxSize   384

Definition at line 34 of file gindatapage.c.

GinPostingListSegmentMinSize

#define GinPostingListSegmentMinSize   128

Definition at line 36 of file gindatapage.c.

GinPostingListSegmentTargetSize

#define GinPostingListSegmentTargetSize   256

Definition at line 35 of file gindatapage.c.

MinTuplesPerSegment

#define MinTuplesPerSegment   ((GinPostingListSegmentMaxSize - 2) / 6)

Definition at line 43 of file gindatapage.c.

Function Documentation

addItemsToLeaf()

static bool addItemsToLeaf ( disassembledLeaf *  leaf, ItemPointer  newItems, int  nNewItems  )

static

Definition at line 1444 of file gindatapage.c.

{
    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;
        }
 
        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;
 
            cur->items = tmpitems;
            cur->nitems = ntmpitems;
            cur->seg = NULL;
            modified = true;
        }
 
        nextnew += nthis;
        newleft -= nthis;
        if (newleft == 0)
            break;
    }
 
    return modified;
}

References leafSegmentInfo::action, Assert(), dlist_iter::cur, cur, dlist_container, dlist_foreach, dlist_has_next(), dlist_is_empty(), dlist_next_node(), dlist_push_tail(), GIN_SEGMENT_ADDITEMS, GIN_SEGMENT_INSERT, GIN_SEGMENT_REPLACE, GIN_SEGMENT_UNMODIFIED, ginCompareItemPointers(), ginMergeItemPointers(), ginPostingListDecode(), GinPostingListSegmentTargetSize, leafSegmentInfo::items, next, leafSegmentInfo::nitems, leafSegmentInfo::node, palloc(), leafSegmentInfo::seg, disassembledLeaf::segments, and SizeOfGinPostingList.

Referenced by dataBeginPlaceToPageLeaf().

computeLeafRecompressWALData()

static void computeLeafRecompressWALData ( disassembledLeaf *  leaf )

static

Definition at line 872 of file gindatapage.c.

{
    int         nmodified = 0;
    char       *walbufbegin;
    char       *walbufend;
    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 */
        );
    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++;
    }
 
    /* Pass back the constructed info via *leaf */
    leaf->walinfo = walbufbegin;
    leaf->walinfolen = walbufend - walbufbegin;
}

References generate_unaccent_rules::action, leafSegmentInfo::action, dlist_iter::cur, dlist_container, dlist_foreach, elog, ERROR, GIN_SEGMENT_ADDITEMS, GIN_SEGMENT_DELETE, GIN_SEGMENT_INSERT, GIN_SEGMENT_REPLACE, GIN_SEGMENT_UNMODIFIED, leafSegmentInfo::modifieditems, ginxlogRecompressDataLeaf::nactions, leafSegmentInfo::nmodifieditems, palloc(), leafSegmentInfo::seg, disassembledLeaf::segments, SHORTALIGN, SizeOfGinPostingList, disassembledLeaf::walinfo, and disassembledLeaf::walinfolen.

Referenced by dataBeginPlaceToPageLeaf(), and ginVacuumPostingTreeLeaf().

createPostingTree()

BlockNumber createPostingTree	(	Relation	index,
		ItemPointerData *	items,
		uint32	nitems,
		GinStatsData *	buildStats,
		Buffer	entrybuffer
	)

Definition at line 1775 of file gindatapage.c.

{
    BlockNumber blkno;
    Buffer      buffer;
    Page        tmppage;
    Page        page;
    Pointer     ptr;
    int         nrootitems;
    int         rootsize;
    bool        is_build = (buildStats != NULL);
 
    /* Construct the new root page in memory first. */
    tmppage = (Page) palloc(BLCKSZ);
    GinInitPage(tmppage, GIN_DATA | GIN_LEAF | GIN_COMPRESSED, BLCKSZ);
    GinPageGetOpaque(tmppage)->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(tmppage);
    while (nrootitems < nitems)
    {
        GinPostingList *segment;
        int         npacked;
        int         segsize;
 
        segment = ginCompressPostingList(&items[nrootitems],
                                         nitems - nrootitems,
                                         GinPostingListSegmentMaxSize,
                                         &npacked);
        segsize = SizeOfGinPostingList(segment);
        if (rootsize + segsize > GinDataPageMaxDataSize)
            break;
 
        memcpy(ptr, segment, segsize);
        ptr += segsize;
        rootsize += segsize;
        nrootitems += npacked;
        pfree(segment);
    }
    GinDataPageSetDataSize(tmppage, rootsize);
 
    /*
     * All set. Get a new physical page, and copy the in-memory page to it.
     */
    buffer = GinNewBuffer(index);
    page = BufferGetPage(buffer);
    blkno = BufferGetBlockNumber(buffer);
 
    /*
     * Copy any predicate locks from the entry tree leaf (containing posting
     * list) to the posting tree.
     */
    PredicateLockPageSplit(index, BufferGetBlockNumber(entrybuffer), blkno);
 
    START_CRIT_SECTION();
 
    PageRestoreTempPage(tmppage, page);
    MarkBufferDirty(buffer);
 
    if (RelationNeedsWAL(index) && !is_build)
    {
        XLogRecPtr  recptr;
        ginxlogCreatePostingTree data;
 
        data.size = rootsize;
 
        XLogBeginInsert();
        XLogRegisterData(&data, sizeof(ginxlogCreatePostingTree));
 
        XLogRegisterData(GinDataLeafPageGetPostingList(page),
                         rootsize);
        XLogRegisterBuffer(0, buffer, REGBUF_WILL_INIT);
 
        recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_CREATE_PTREE);
        PageSetLSN(page, recptr);
    }
 
    UnlockReleaseBuffer(buffer);
 
    END_CRIT_SECTION();
 
    /* During index build, count the newly-added data page */
    if (buildStats)
        buildStats->nDataPages++;
 
    elog(DEBUG2, "created GIN posting tree with %d items", nrootitems);
 
    /*
     * Add any remaining TIDs to the newly-created posting tree.
     */
    if (nitems > nrootitems)
    {
        ginInsertItemPointers(index, blkno,
                              items + nrootitems,
                              nitems - nrootitems,
                              buildStats);
    }
 
    return blkno;
}

References BufferGetBlockNumber(), BufferGetPage(), data, DEBUG2, elog, END_CRIT_SECTION, GIN_COMPRESSED, GIN_DATA, GIN_LEAF, ginCompressPostingList(), GinDataLeafPageGetPostingList, GinDataPageMaxDataSize, GinDataPageSetDataSize, GinInitPage(), ginInsertItemPointers(), GinNewBuffer(), GinPageGetOpaque, GinPostingListSegmentMaxSize, InvalidBlockNumber, items, MarkBufferDirty(), GinStatsData::nDataPages, nitems, PageRestoreTempPage(), PageSetLSN(), palloc(), pfree(), PredicateLockPageSplit(), REGBUF_WILL_INIT, RelationNeedsWAL, SizeOfGinPostingList, START_CRIT_SECTION, UnlockReleaseBuffer(), XLOG_GIN_CREATE_PTREE, XLogBeginInsert(), XLogInsert(), XLogRegisterBuffer(), and XLogRegisterData().

Referenced by addItemPointersToLeafTuple(), and buildFreshLeafTuple().

dataBeginPlaceToPage()

static GinPlaceToPageRC dataBeginPlaceToPage ( GinBtree  btree, Buffer  buf, GinBtreeStack *  stack, void *  insertdata, BlockNumber  updateblkno, void **  ptp_workspace, Page *  newlpage, Page *  newrpage  )

static

Definition at line 1201 of file gindatapage.c.

{
    Page        page = BufferGetPage(buf);
 
    Assert(GinPageIsData(page));
 
    if (GinPageIsLeaf(page))
        return dataBeginPlaceToPageLeaf(btree, buf, stack, insertdata,
                                        ptp_workspace,
                                        newlpage, newrpage);
    else
        return dataBeginPlaceToPageInternal(btree, buf, stack,
                                            insertdata, updateblkno,
                                            ptp_workspace,
                                            newlpage, newrpage);
}

References Assert(), buf, BufferGetPage(), dataBeginPlaceToPageInternal(), dataBeginPlaceToPageLeaf(), GinPageIsData, and GinPageIsLeaf.

Referenced by ginPrepareDataScan().

dataBeginPlaceToPageInternal()

static GinPlaceToPageRC dataBeginPlaceToPageInternal ( GinBtree  btree, Buffer  buf, GinBtreeStack *  stack, void *  insertdata, BlockNumber  updateblkno, void **  ptp_workspace, Page *  newlpage, Page *  newrpage  )

static

Definition at line 1119 of file gindatapage.c.

{
    Page        page = BufferGetPage(buf);
 
    /* If it doesn't fit, deal with split case */
    if (GinNonLeafDataPageGetFreeSpace(page) < sizeof(PostingItem))
    {
        dataSplitPageInternal(btree, buf, stack, insertdata, updateblkno,
                              newlpage, newrpage);
        return GPTP_SPLIT;
    }
 
    /* Else, we're ready to proceed with insertion */
    return GPTP_INSERT;
}

References buf, BufferGetPage(), dataSplitPageInternal(), GinNonLeafDataPageGetFreeSpace, GPTP_INSERT, and GPTP_SPLIT.

Referenced by dataBeginPlaceToPage().

dataBeginPlaceToPageLeaf()

static GinPlaceToPageRC dataBeginPlaceToPageLeaf ( GinBtree  btree, Buffer  buf, GinBtreeStack *  stack, void *  insertdata, void **  ptp_workspace, Page *  newlpage, Page *  newrpage  )

static

Definition at line 448 of file gindatapage.c.

{
    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;
    disassembledLeaf *leaf;
    leafSegmentInfo *lastleftinfo;
    ItemPointerData maxOldItem;
    ItemPointerData remaining;
 
    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;
    }
 
    /* Disassemble the data on the page */
    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 + GinDataPageMaxDataSize);
    }
    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 += GinDataPageMaxDataSize / GinPostingListSegmentMaxSize;
        maxitems = Min(maxitems, nnewsegments * MinTuplesPerSegment);
    }
 
    /* Add the new items to the segment list */
    if (!addItemsToLeaf(leaf, newItems, maxitems))
    {
        /* all items were duplicates, we have nothing to do */
        items->curitem += maxitems;
 
        return GPTP_NO_WORK;
    }
 
    /*
     * 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.  If needed, prepare data
         * for a WAL record describing the changes we'll make.
         */
        if (RelationNeedsWAL(btree->index) && !btree->isBuild)
            computeLeafRecompressWALData(leaf);
 
        /*
         * We're ready to enter the critical section, but
         * dataExecPlaceToPageLeaf will need access to the "leaf" data.
         */
        *ptp_workspace = 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
    {
        /*
         * Have to split.
         *
         * leafRepackItems already divided the segments between the left and
         * the right page. It filled the left page as full as possible, and
         * put the rest 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, try to make the left page 75% full, on 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);
 
                /* ignore deleted segments */
                if (lastleftinfo->action != GIN_SEGMENT_DELETE)
                {
                    segsize = SizeOfGinPostingList(lastleftinfo->seg);
 
                    /*
                     * Note that we check that the right page doesn't become
                     * more full than the left page even when appending. It's
                     * possible that we added enough items to make both pages
                     * more than 75% full.
                     */
                    if ((leaf->lsize - segsize) - (leaf->rsize + segsize) < 0)
                        break;
                    if (append)
                    {
                        if ((leaf->lsize - segsize) < (BLCKSZ * 3) / 4)
                            break;
                    }
 
                    leaf->lsize -= segsize;
                    leaf->rsize += segsize;
                }
                leaf->lastleft = dlist_prev_node(&leaf->segments, leaf->lastleft);
            }
        }
        Assert(leaf->lsize <= GinDataPageMaxDataSize);
        Assert(leaf->rsize <= GinDataPageMaxDataSize);
 
        /*
         * 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];
 
        /*
         * Now allocate a couple of temporary page images, and fill them.
         */
        *newlpage = palloc(BLCKSZ);
        *newrpage = palloc(BLCKSZ);
 
        dataPlaceToPageLeafSplit(leaf, lbound, rbound,
                                 *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);
    }
 
    items->curitem += maxitems;
 
    return needsplit ? GPTP_SPLIT : GPTP_INSERT;
}

References leafSegmentInfo::action, addItemsToLeaf(), Assert(), buf, BufferGetBlockNumber(), BufferGetPage(), computeLeafRecompressWALData(), dataPlaceToPageLeafSplit(), DEBUG2, disassembleLeaf(), dlist_container, dlist_has_prev(), dlist_is_empty(), dlist_prev_node(), dlist_tail_node(), elog, ERROR, GIN_SEGMENT_DELETE, ginCompareItemPointers(), GinDataLeafPageGetFreeSpace, GinDataPageGetRightBound, GinDataPageMaxDataSize, GinPageIsCompressed, GinPageRightMost, ginPostingListDecode(), GinPostingListSegmentMaxSize, GPTP_INSERT, GPTP_NO_WORK, GPTP_SPLIT, i, GinBtreeData::index, GinBtreeData::isBuild, ItemPointerCompare(), ItemPointerIsValid(), ItemPointerSetMin, leafSegmentInfo::items, items, disassembledLeaf::lastleft, leafRepackItems(), disassembledLeaf::lsize, Min, MinTuplesPerSegment, leafSegmentInfo::nitems, palloc(), RelationNeedsWAL, remaining, disassembledLeaf::rsize, leafSegmentInfo::seg, disassembledLeaf::segments, and SizeOfGinPostingList.

Referenced by dataBeginPlaceToPage().

dataExecPlaceToPage()

static void dataExecPlaceToPage ( GinBtree  btree, Buffer  buf, GinBtreeStack *  stack, void *  insertdata, BlockNumber  updateblkno, void *  ptp_workspace  )

static

Definition at line 1231 of file gindatapage.c.

{
    Page        page = BufferGetPage(buf);
 
    if (GinPageIsLeaf(page))
        dataExecPlaceToPageLeaf(btree, buf, stack, insertdata,
                                ptp_workspace);
    else
        dataExecPlaceToPageInternal(btree, buf, stack, insertdata,
                                    updateblkno, ptp_workspace);
}

References buf, BufferGetPage(), dataExecPlaceToPageInternal(), dataExecPlaceToPageLeaf(), and GinPageIsLeaf.

Referenced by ginPrepareDataScan().

dataExecPlaceToPageInternal()

static void dataExecPlaceToPageInternal ( GinBtree  btree, Buffer  buf, GinBtreeStack *  stack, void *  insertdata, BlockNumber  updateblkno, void *  ptp_workspace  )

static

Definition at line 1145 of file gindatapage.c.

{
    Page        page = BufferGetPage(buf);
    OffsetNumber off = stack->off;
    PostingItem *pitem;
 
    /* 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);
 
    MarkBufferDirty(buf);
 
    if (RelationNeedsWAL(btree->index) && !btree->isBuild)
    {
        /*
         * This must be static, because it has to survive until XLogInsert,
         * and we can't palloc here.  Ugly, but the XLogInsert infrastructure
         * isn't reentrant anyway.
         */
        static ginxlogInsertDataInternal data;
 
        data.offset = off;
        data.newitem = *pitem;
 
        XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
        XLogRegisterBufData(0, &data,
                            sizeof(ginxlogInsertDataInternal));
    }
}

References buf, BufferGetPage(), data, GinDataPageAddPostingItem(), GinDataPageGetPostingItem, GinBtreeData::index, GinBtreeData::isBuild, MarkBufferDirty(), GinBtreeStack::off, PostingItemSetBlockNumber, REGBUF_STANDARD, RelationNeedsWAL, XLogRegisterBufData(), and XLogRegisterBuffer().

Referenced by dataExecPlaceToPage().

dataExecPlaceToPageLeaf()

static void dataExecPlaceToPageLeaf ( GinBtree  btree, Buffer  buf, GinBtreeStack *  stack, void *  insertdata, void *  ptp_workspace  )

static

Definition at line 716 of file gindatapage.c.

{
    disassembledLeaf *leaf = (disassembledLeaf *) ptp_workspace;
 
    /* Apply changes to page */
    dataPlaceToPageLeafRecompress(buf, leaf);
 
    MarkBufferDirty(buf);
 
    /* If needed, register WAL data built by computeLeafRecompressWALData */
    if (RelationNeedsWAL(btree->index) && !btree->isBuild)
    {
        XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
        XLogRegisterBufData(0, leaf->walinfo, leaf->walinfolen);
    }
}

References buf, dataPlaceToPageLeafRecompress(), GinBtreeData::index, GinBtreeData::isBuild, MarkBufferDirty(), REGBUF_STANDARD, RelationNeedsWAL, disassembledLeaf::walinfo, disassembledLeaf::walinfolen, XLogRegisterBufData(), and XLogRegisterBuffer().

Referenced by dataExecPlaceToPage().

dataFindChildPtr()

static OffsetNumber dataFindChildPtr ( GinBtree  btree, Page  page, BlockNumber  blkno, OffsetNumber  storedOff  )

static

Definition at line 319 of file gindatapage.c.

{
    OffsetNumber i,
                maxoff = GinPageGetOpaque(page)->maxoff;
    PostingItem *pitem;
 
    Assert(!GinPageIsLeaf(page));
    Assert(GinPageIsData(page));
 
    /* 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 = GinDataPageGetPostingItem(page, i);
            if (PostingItemGetBlockNumber(pitem) == blkno)
                return i;
        }
 
        maxoff = storedOff - 1;
    }
 
    /* last chance */
    for (i = FirstOffsetNumber; i <= maxoff; i++)
    {
        pitem = GinDataPageGetPostingItem(page, i);
        if (PostingItemGetBlockNumber(pitem) == blkno)
            return i;
    }
 
    return InvalidOffsetNumber;
}

References Assert(), FirstOffsetNumber, GinDataPageGetPostingItem, GinPageGetOpaque, GinPageIsData, GinPageIsLeaf, i, InvalidOffsetNumber, and PostingItemGetBlockNumber.

Referenced by ginPrepareDataScan().

dataGetLeftMostPage()

static BlockNumber dataGetLeftMostPage ( GinBtree  btree, Page  page  )

static

Definition at line 364 of file gindatapage.c.

{
    PostingItem *pitem;
 
    Assert(!GinPageIsLeaf(page));
    Assert(GinPageIsData(page));
    Assert(GinPageGetOpaque(page)->maxoff >= FirstOffsetNumber);
 
    pitem = GinDataPageGetPostingItem(page, FirstOffsetNumber);
    return PostingItemGetBlockNumber(pitem);
}

References Assert(), FirstOffsetNumber, GinDataPageGetPostingItem, GinPageGetOpaque, GinPageIsData, GinPageIsLeaf, and PostingItemGetBlockNumber.

Referenced by ginPrepareDataScan().

dataIsMoveRight()

static bool dataIsMoveRight ( GinBtree  btree, Page  page  )

static

Definition at line 234 of file gindatapage.c.

{
    ItemPointer iptr = GinDataPageGetRightBound(page);
 
    if (GinPageRightMost(page))
        return false;
 
    if (GinPageIsDeleted(page))
        return true;
 
    return (ginCompareItemPointers(&btree->itemptr, iptr) > 0);
}

References ginCompareItemPointers(), GinDataPageGetRightBound, GinPageIsDeleted, GinPageRightMost, and GinBtreeData::itemptr.

Referenced by ginPrepareDataScan().

dataLeafPageGetUncompressed()

static ItemPointer dataLeafPageGetUncompressed ( Page  page, int *  nitems  )

static

Definition at line 211 of file gindatapage.c.

{
    ItemPointer items;
 
    Assert(!GinPageIsCompressed(page));
 
    /*
     * 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;
 
    return items;
}

References Assert(), GinDataPageGetData, GinPageGetOpaque, GinPageIsCompressed, items, and nitems.

Referenced by disassembleLeaf(), GinDataLeafPageGetItems(), and GinDataLeafPageGetItemsToTbm().

dataLocateItem()

static BlockNumber dataLocateItem ( GinBtree  btree, GinBtreeStack *  stack  )

static

Definition at line 252 of file gindatapage.c.

{
    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;
        stack->predictNumber *= GinPageGetOpaque(page)->maxoff;
        return btree->getLeftMostChild(btree, page);
    }
 
    low = FirstOffsetNumber;
    maxoff = high = GinPageGetOpaque(page)->maxoff;
    Assert(high >= low);
 
    high++;
 
    while (high > low)
    {
        OffsetNumber mid = low + ((high - low) / 2);
 
        pitem = GinDataPageGetPostingItem(page, mid);
 
        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 PostingItemGetBlockNumber(pitem);
        }
        else if (result > 0)
            low = mid + 1;
        else
            high = mid;
    }
 
    Assert(high >= FirstOffsetNumber && high <= maxoff);
 
    stack->off = high;
    pitem = GinDataPageGetPostingItem(page, high);
    return PostingItemGetBlockNumber(pitem);
}

References Assert(), GinBtreeStack::buffer, BufferGetPage(), FirstOffsetNumber, GinBtreeData::fullScan, GinBtreeData::getLeftMostChild, ginCompareItemPointers(), GinDataPageGetPostingItem, GinPageGetOpaque, GinPageIsData, GinPageIsLeaf, GinBtreeData::itemptr, PostingItem::key, GinBtreeStack::off, PostingItemGetBlockNumber, and GinBtreeStack::predictNumber.

Referenced by ginPrepareDataScan().

dataPlaceToPageLeafRecompress()

static void dataPlaceToPageLeafRecompress ( Buffer  buf, disassembledLeaf *  leaf  )

static

Definition at line 978 of file gindatapage.c.

{
    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 <= GinDataPageMaxDataSize);
    GinDataPageSetDataSize(page, newsize);
}

References leafSegmentInfo::action, Assert(), buf, BufferGetPage(), dlist_iter::cur, dlist_container, dlist_foreach, GIN_SEGMENT_DELETE, GIN_SEGMENT_UNMODIFIED, GinDataLeafPageGetPostingList, GinDataPageMaxDataSize, GinDataPageSetDataSize, GinPageGetOpaque, GinPageIsCompressed, GinPageSetCompressed, InvalidOffsetNumber, disassembledLeaf::oldformat, leafSegmentInfo::seg, disassembledLeaf::segments, and SizeOfGinPostingList.

Referenced by dataExecPlaceToPageLeaf(), and ginVacuumPostingTreeLeaf().

dataPlaceToPageLeafSplit()

static void dataPlaceToPageLeafSplit ( disassembledLeaf *  leaf, ItemPointerData  lbound, ItemPointerData  rbound, Page  lpage, Page  rpage  )

static

Definition at line 1034 of file gindatapage.c.

{
    char       *ptr;
    int         segsize;
    int         lsize;
    int         rsize;
    dlist_node *node;
    dlist_node *firstright;
    leafSegmentInfo *seginfo;
 
    /* 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);
    GinDataPageSetDataSize(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;
        }
 
        if (!dlist_has_next(&leaf->segments, node))
            break;
    }
    Assert(rsize == leaf->rsize);
    GinDataPageSetDataSize(rpage, rsize);
    *GinDataPageGetRightBound(rpage) = rbound;
}

References leafSegmentInfo::action, Assert(), dlist_container, dlist_has_next(), dlist_head_node(), dlist_next_node(), GIN_COMPRESSED, GIN_DATA, GIN_LEAF, GIN_SEGMENT_DELETE, GinDataLeafPageGetPostingList, GinDataPageGetRightBound, GinDataPageSetDataSize, GinInitPage(), disassembledLeaf::lastleft, disassembledLeaf::lsize, disassembledLeaf::rsize, leafSegmentInfo::seg, disassembledLeaf::segments, and SizeOfGinPostingList.

Referenced by dataBeginPlaceToPageLeaf().

dataPrepareDownlink()

static void * dataPrepareDownlink ( GinBtree  btree, Buffer  lbuf  )

static

Definition at line 1333 of file gindatapage.c.

{
    PostingItem *pitem = palloc(sizeof(PostingItem));
    Page        lpage = BufferGetPage(lbuf);
 
    PostingItemSetBlockNumber(pitem, BufferGetBlockNumber(lbuf));
    pitem->key = *GinDataPageGetRightBound(lpage);
 
    return pitem;
}

References BufferGetBlockNumber(), BufferGetPage(), GinDataPageGetRightBound, PostingItem::key, palloc(), and PostingItemSetBlockNumber.

Referenced by ginPrepareDataScan().

dataSplitPageInternal()

static void dataSplitPageInternal ( GinBtree  btree, Buffer  origbuf, GinBtreeStack *  stack, void *  insertdata, BlockNumber  updateblkno, Page *  newlpage, Page *  newrpage  )

static

Definition at line 1252 of file gindatapage.c.

{
    Page        oldpage = BufferGetPage(origbuf);
    OffsetNumber off = stack->off;
    int         nitems = GinPageGetOpaque(oldpage)->maxoff;
    int         nleftitems;
    int         nrightitems;
    Size        pageSize = PageGetPageSize(oldpage);
    ItemPointerData oldbound = *GinDataPageGetRightBound(oldpage);
    ItemPointer bound;
    Page        lpage;
    Page        rpage;
    OffsetNumber separator;
    PostingItem allitems[(BLCKSZ / sizeof(PostingItem)) + 1];
 
    lpage = PageGetTempPage(oldpage);
    rpage = PageGetTempPage(oldpage);
    GinInitPage(lpage, GinPageGetOpaque(oldpage)->flags, pageSize);
    GinInitPage(rpage, GinPageGetOpaque(oldpage)->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;
    nleftitems = separator;
    nrightitems = nitems - separator;
 
    memcpy(GinDataPageGetPostingItem(lpage, FirstOffsetNumber),
           allitems,
           nleftitems * sizeof(PostingItem));
    GinPageGetOpaque(lpage)->maxoff = nleftitems;
    memcpy(GinDataPageGetPostingItem(rpage, FirstOffsetNumber),
           &allitems[separator],
           nrightitems * sizeof(PostingItem));
    GinPageGetOpaque(rpage)->maxoff = nrightitems;
 
    /*
     * Also set pd_lower for both pages, like GinDataPageAddPostingItem does.
     */
    GinDataPageSetDataSize(lpage, nleftitems * sizeof(PostingItem));
    GinDataPageSetDataSize(rpage, nrightitems * sizeof(PostingItem));
 
    /* set up right bound for left page */
    bound = GinDataPageGetRightBound(lpage);
    *bound = GinDataPageGetPostingItem(lpage, nleftitems)->key;
 
    /* set up right bound for right page */
    *GinDataPageGetRightBound(rpage) = oldbound;
 
    /* return temp pages to caller */
    *newlpage = lpage;
    *newrpage = rpage;
}

References BufferGetPage(), FirstOffsetNumber, GinDataPageGetPostingItem, GinDataPageGetRightBound, GinDataPageSetDataSize, GinInitPage(), GinNonLeafDataPageGetFreeSpace, GinPageGetOpaque, GinPageRightMost, GinBtreeData::isBuild, nitems, GinBtreeStack::off, PageGetPageSize(), PageGetTempPage(), and PostingItemSetBlockNumber.

Referenced by dataBeginPlaceToPageInternal().

disassembleLeaf()

static disassembledLeaf * disassembleLeaf ( Page  page )

static

Definition at line 1370 of file gindatapage.c.

{
    disassembledLeaf *leaf;
    GinPostingList *seg;
    Pointer     segbegin;
    Pointer     segend;
 
    leaf = palloc0(sizeof(disassembledLeaf));
    dlist_init(&leaf->segments);
 
    if (GinPageIsCompressed(page))
    {
        /*
         * Create a leafSegmentInfo 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.  The corner case is uncompressed
         * page containing no items, which is represented as no segments.
         */
        ItemPointer uncompressed;
        int         nuncompressed;
        leafSegmentInfo *seginfo;
 
        uncompressed = dataLeafPageGetUncompressed(page, &nuncompressed);
 
        if (nuncompressed > 0)
        {
            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;
}

References leafSegmentInfo::action, dataLeafPageGetUncompressed(), dlist_init(), dlist_push_tail(), GIN_SEGMENT_REPLACE, GIN_SEGMENT_UNMODIFIED, GinDataLeafPageGetPostingList, GinDataLeafPageGetPostingListSize, GinNextPostingListSegment, GinPageIsCompressed, leafSegmentInfo::items, leafSegmentInfo::nitems, leafSegmentInfo::node, disassembledLeaf::oldformat, palloc(), palloc0(), leafSegmentInfo::seg, and disassembledLeaf::segments.

Referenced by dataBeginPlaceToPageLeaf(), and ginVacuumPostingTreeLeaf().

ginDataFillRoot()

void ginDataFillRoot	(	GinBtree	btree,
		Page	root,
		BlockNumber	lblkno,
		Page	lpage,
		BlockNumber	rblkno,
		Page	rpage
	)

Definition at line 1349 of file gindatapage.c.

{
    PostingItem li,
                ri;
 
    li.key = *GinDataPageGetRightBound(lpage);
    PostingItemSetBlockNumber(&li, lblkno);
    GinDataPageAddPostingItem(root, &li, InvalidOffsetNumber);
 
    ri.key = *GinDataPageGetRightBound(rpage);
    PostingItemSetBlockNumber(&ri, rblkno);
    GinDataPageAddPostingItem(root, &ri, InvalidOffsetNumber);
}

References GinDataPageAddPostingItem(), GinDataPageGetRightBound, InvalidOffsetNumber, PostingItem::key, PostingItemSetBlockNumber, and root.

Referenced by ginPrepareDataScan().

GinDataLeafPageGetItems()

ItemPointer GinDataLeafPageGetItems	(	Page	page,
		int *	nitems,
		ItemPointerData	advancePast
	)

Definition at line 135 of file gindatapage.c.

{
    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);
 
        result = palloc((*nitems) * sizeof(ItemPointerData));
        memcpy(result, tmp, (*nitems) * sizeof(ItemPointerData));
    }
 
    return result;
}

References dataLeafPageGetUncompressed(), ginCompareItemPointers(), GinDataLeafPageGetPostingList, GinDataLeafPageGetPostingListSize, GinNextPostingListSegment, GinPageIsCompressed, ginPostingListDecodeAllSegments(), ItemPointerIsValid(), len, next, nitems, and palloc().

Referenced by entryLoadMoreItems(), and startScanEntry().

GinDataLeafPageGetItemsToTbm()

int GinDataLeafPageGetItemsToTbm	(	Page	page,
		TIDBitmap *	tbm
	)

Definition at line 182 of file gindatapage.c.

{
    ItemPointer uncompressed;
    int         nitems;
 
    if (GinPageIsCompressed(page))
    {
        GinPostingList *segment = GinDataLeafPageGetPostingList(page);
        Size        len = GinDataLeafPageGetPostingListSize(page);
 
        nitems = ginPostingListDecodeAllSegmentsToTbm(segment, len, tbm);
    }
    else
    {
        uncompressed = dataLeafPageGetUncompressed(page, &nitems);
 
        if (nitems > 0)
            tbm_add_tuples(tbm, uncompressed, nitems, false);
    }
 
    return nitems;
}

References dataLeafPageGetUncompressed(), GinDataLeafPageGetPostingList, GinDataLeafPageGetPostingListSize, GinPageIsCompressed, ginPostingListDecodeAllSegmentsToTbm(), len, nitems, and tbm_add_tuples().

Referenced by scanPostingTree().

GinDataPageAddPostingItem()

void GinDataPageAddPostingItem	(	Page	page,
		PostingItem *	data,
		OffsetNumber	offset
	)

Definition at line 380 of file gindatapage.c.

{
    OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
    char       *ptr;
 
    Assert(PostingItemGetBlockNumber(data) != InvalidBlockNumber);
    Assert(!GinPageIsLeaf(page));
 
    if (offset == InvalidOffsetNumber)
    {
        ptr = (char *) GinDataPageGetPostingItem(page, maxoff + 1);
    }
    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));
 
    maxoff++;
    GinPageGetOpaque(page)->maxoff = maxoff;
 
    /*
     * Also set pd_lower to the end of the posting items, to follow the
     * "standard" page layout, so that we can squeeze out the unused space
     * from full-page images.
     */
    GinDataPageSetDataSize(page, maxoff * sizeof(PostingItem));
}

References Assert(), data, GinDataPageGetPostingItem, GinDataPageSetDataSize, GinPageGetOpaque, GinPageIsLeaf, InvalidBlockNumber, InvalidOffsetNumber, and PostingItemGetBlockNumber.

Referenced by dataExecPlaceToPageInternal(), ginDataFillRoot(), and ginRedoInsertData().

ginInsertItemPointers()

void ginInsertItemPointers	(	Relation	index,
		BlockNumber	rootBlkno,
		ItemPointerData *	items,
		uint32	nitem,
		GinStatsData *	buildStats
	)

Definition at line 1908 of file gindatapage.c.

{
    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, true);
 
        ginInsertValue(&btree, stack, &insertdata, buildStats);
    }
}

References GinBtreeDataLeafInsertData::curitem, ginFindLeafPage(), ginInsertValue(), ginPrepareDataScan(), GinBtreeData::isBuild, GinBtreeData::itemptr, GinBtreeDataLeafInsertData::items, items, and GinBtreeDataLeafInsertData::nitem.

Referenced by addItemPointersToLeafTuple(), createPostingTree(), and ginEntryInsert().

GinPageDeletePostingItem()

void GinPageDeletePostingItem	(	Page	page,
		OffsetNumber	offset
	)

Definition at line 417 of file gindatapage.c.

{
    OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
 
    Assert(!GinPageIsLeaf(page));
    Assert(offset >= FirstOffsetNumber && offset <= maxoff);
 
    if (offset != maxoff)
        memmove(GinDataPageGetPostingItem(page, offset),
                GinDataPageGetPostingItem(page, offset + 1),
                sizeof(PostingItem) * (maxoff - offset));
 
    maxoff--;
    GinPageGetOpaque(page)->maxoff = maxoff;
 
    GinDataPageSetDataSize(page, maxoff * sizeof(PostingItem));
}

References Assert(), FirstOffsetNumber, GinDataPageGetPostingItem, GinDataPageSetDataSize, GinPageGetOpaque, and GinPageIsLeaf.

Referenced by ginDeletePage(), and ginRedoDeletePage().

ginPrepareDataScan()

static void ginPrepareDataScan ( GinBtree  btree, Relation  index, BlockNumber  rootBlkno  )

static

Definition at line 1882 of file gindatapage.c.

{
    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->beginPlaceToPage = dataBeginPlaceToPage;
    btree->execPlaceToPage = dataExecPlaceToPage;
    btree->fillRoot = ginDataFillRoot;
    btree->prepareDownlink = dataPrepareDownlink;
 
    btree->isData = true;
    btree->fullScan = false;
    btree->isBuild = false;
}

References GinBtreeData::beginPlaceToPage, dataBeginPlaceToPage(), dataExecPlaceToPage(), dataFindChildPtr(), dataGetLeftMostPage(), dataIsMoveRight(), dataLocateItem(), dataPrepareDownlink(), GinBtreeData::execPlaceToPage, GinBtreeData::fillRoot, GinBtreeData::findChildPage, GinBtreeData::findChildPtr, GinBtreeData::findItem, GinBtreeData::fullScan, GinBtreeData::getLeftMostChild, ginDataFillRoot(), GinBtreeData::index, GinBtreeData::isBuild, GinBtreeData::isData, GinBtreeData::isMoveRight, GinBtreeData::prepareDownlink, and GinBtreeData::rootBlkno.

Referenced by ginInsertItemPointers(), and ginScanBeginPostingTree().

ginScanBeginPostingTree()

GinBtreeStack * ginScanBeginPostingTree	(	GinBtree	btree,
		Relation	index,
		BlockNumber	rootBlkno
	)

Definition at line 1936 of file gindatapage.c.

{
    GinBtreeStack *stack;
 
    ginPrepareDataScan(btree, index, rootBlkno);
 
    btree->fullScan = true;
 
    stack = ginFindLeafPage(btree, true, false);
 
    return stack;
}

References GinBtreeData::fullScan, ginFindLeafPage(), and ginPrepareDataScan().

Referenced by scanPostingTree(), and startScanEntry().

ginVacuumPostingTreeLeaf()

void ginVacuumPostingTreeLeaf	(	Relation	indexrel,
		Buffer	buffer,
		GinVacuumState *	gvs
	)

Definition at line 738 of file gindatapage.c.

{
    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 = GinDataPageMaxDataSize;
 
        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)
    {
        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))
            computeLeafRecompressWALData(leaf);
 
        /* Apply changes to page */
        START_CRIT_SECTION();
 
        dataPlaceToPageLeafRecompress(buffer, leaf);
 
        MarkBufferDirty(buffer);
 
        if (RelationNeedsWAL(indexrel))
        {
            XLogRecPtr  recptr;
 
            XLogBeginInsert();
            XLogRegisterBuffer(0, buffer, REGBUF_STANDARD);
            XLogRegisterBufData(0, leaf->walinfo, leaf->walinfolen);
            recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_VACUUM_DATA_LEAF_PAGE);
            PageSetLSN(page, recptr);
        }
 
        END_CRIT_SECTION();
    }
}

References leafSegmentInfo::action, BufferGetPage(), computeLeafRecompressWALData(), dlist_iter::cur, dataPlaceToPageLeafRecompress(), disassembleLeaf(), dlist_container, dlist_foreach, elog, END_CRIT_SECTION, ERROR, GIN_SEGMENT_DELETE, GIN_SEGMENT_REPLACE, GIN_SEGMENT_UNMODIFIED, ginCompressPostingList(), GinDataPageMaxDataSize, ginPostingListDecode(), ginVacuumItemPointers(), leafSegmentInfo::items, MarkBufferDirty(), leafSegmentInfo::nitems, PageSetLSN(), palloc(), pfree(), REGBUF_STANDARD, RelationNeedsWAL, leafSegmentInfo::seg, disassembledLeaf::segments, SizeOfGinPostingList, START_CRIT_SECTION, disassembledLeaf::walinfo, disassembledLeaf::walinfolen, XLOG_GIN_VACUUM_DATA_LEAF_PAGE, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), and XLogRegisterBuffer().

Referenced by ginVacuumPostingTreeLeaves().

leafRepackItems()

static bool leafRepackItems ( disassembledLeaf *  leaf, ItemPointer  remaining  )

static

Definition at line 1571 of file gindatapage.c.

{
    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 > GinDataPageMaxDataSize)
        {
            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 <= GinDataPageMaxDataSize);
    Assert(leaf->rsize <= GinDataPageMaxDataSize);
 
    /*
     * 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;
}

References leafSegmentInfo::action, Assert(), dlist_iter::cur, dlist_container, dlist_delete(), dlist_foreach, dlist_has_next(), dlist_head_node(), dlist_insert_after(), dlist_next_node(), dlist_prev_node(), GinPostingList::first, GIN_SEGMENT_DELETE, GIN_SEGMENT_INSERT, GIN_SEGMENT_REPLACE, GIN_SEGMENT_UNMODIFIED, ginCompressPostingList(), GinDataPageMaxDataSize, ginMergeItemPointers(), ginPostingListDecode(), GinPostingListSegmentMaxSize, GinPostingListSegmentMinSize, GinPostingListSegmentTargetSize, ItemPointerSetInvalid(), leafSegmentInfo::items, disassembledLeaf::lastleft, disassembledLeaf::lsize, leafSegmentInfo::modifieditems, leafSegmentInfo::nitems, leafSegmentInfo::nmodifieditems, leafSegmentInfo::node, palloc(), pfree(), remaining, disassembledLeaf::rsize, leafSegmentInfo::seg, disassembledLeaf::segments, and SizeOfGinPostingList.

Referenced by dataBeginPlaceToPageLeaf().