gistbuild.c File Reference

#include "postgres.h"
#include <math.h>
#include "access/genam.h"
#include "access/gist_private.h"
#include "access/gistxlog.h"
#include "access/tableam.h"
#include "access/xloginsert.h"
#include "catalog/index.h"
#include "miscadmin.h"
#include "optimizer/optimizer.h"
#include "storage/bufmgr.h"
#include "storage/smgr.h"
#include "utils/memutils.h"
#include "utils/rel.h"
#include "utils/tuplesort.h"

Include dependency graph for gistbuild.c:

Go to the source code of this file.

Data Structures
struct	GISTBuildState
struct	GistSortedBuildLevelState
struct	ParentMapEntry

Macros
#define	BUFFERING_MODE_SWITCH_CHECK_STEP   256
#define	BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET   4096
#define	GIST_SORTED_BUILD_PAGE_NUM   4

Typedefs
typedef struct GistSortedBuildLevelState	GistSortedBuildLevelState

Enumerations
enum	GistBuildMode {   GIST_SORTED_BUILD , GIST_BUFFERING_DISABLED , GIST_BUFFERING_AUTO , GIST_BUFFERING_STATS ,   GIST_BUFFERING_ACTIVE }

Functions
static void	gistSortedBuildCallback (Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
static void	gist_indexsortbuild (GISTBuildState *state)
static void	gist_indexsortbuild_levelstate_add (GISTBuildState *state, GistSortedBuildLevelState *levelstate, IndexTuple itup)
static void	gist_indexsortbuild_levelstate_flush (GISTBuildState *state, GistSortedBuildLevelState *levelstate)
static void	gist_indexsortbuild_flush_ready_pages (GISTBuildState *state)
static void	gistInitBuffering (GISTBuildState *buildstate)
static int	calculatePagesPerBuffer (GISTBuildState *buildstate, int levelStep)
static void	gistBuildCallback (Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
static void	gistBufferingBuildInsert (GISTBuildState *buildstate, IndexTuple itup)
static bool	gistProcessItup (GISTBuildState *buildstate, IndexTuple itup, BlockNumber startblkno, int startlevel)
static BlockNumber	gistbufferinginserttuples (GISTBuildState *buildstate, Buffer buffer, int level, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, BlockNumber parentblk, OffsetNumber downlinkoffnum)
static Buffer	gistBufferingFindCorrectParent (GISTBuildState *buildstate, BlockNumber childblkno, int level, BlockNumber *parentblkno, OffsetNumber *downlinkoffnum)
static void	gistProcessEmptyingQueue (GISTBuildState *buildstate)
static void	gistEmptyAllBuffers (GISTBuildState *buildstate)
static int	gistGetMaxLevel (Relation index)
static void	gistInitParentMap (GISTBuildState *buildstate)
static void	gistMemorizeParent (GISTBuildState *buildstate, BlockNumber child, BlockNumber parent)
static void	gistMemorizeAllDownlinks (GISTBuildState *buildstate, Buffer parentbuf)
static BlockNumber	gistGetParent (GISTBuildState *buildstate, BlockNumber child)
IndexBuildResult *	gistbuild (Relation heap, Relation index, IndexInfo *indexInfo)

Macro Definition Documentation

BUFFERING_MODE_SWITCH_CHECK_STEP

#define BUFFERING_MODE_SWITCH_CHECK_STEP   256

Definition at line 52 of file gistbuild.c.

BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET

#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET   4096

Definition at line 60 of file gistbuild.c.

GIST_SORTED_BUILD_PAGE_NUM

#define GIST_SORTED_BUILD_PAGE_NUM   4

Definition at line 116 of file gistbuild.c.

Typedef Documentation

GistSortedBuildLevelState

typedef struct GistSortedBuildLevelState GistSortedBuildLevelState

Enumeration Type Documentation

GistBuildMode

enum GistBuildMode

Enumerator
GIST_SORTED_BUILD
GIST_BUFFERING_DISABLED
GIST_BUFFERING_AUTO
GIST_BUFFERING_STATS
GIST_BUFFERING_ACTIVE

Definition at line 67 of file gistbuild.c.

{
    GIST_SORTED_BUILD,          /* bottom-up build by sorting */
    GIST_BUFFERING_DISABLED,    /* in regular build mode and aren't going to
                                 * switch */
    GIST_BUFFERING_AUTO,        /* in regular build mode, but will switch to
                                 * buffering build mode if the index grows too
                                 * big */
    GIST_BUFFERING_STATS,       /* gathering statistics of index tuple size
                                 * before switching to the buffering build
                                 * mode */
    GIST_BUFFERING_ACTIVE       /* in buffering build mode */
} GistBuildMode;

Function Documentation

calculatePagesPerBuffer()

static int calculatePagesPerBuffer ( GISTBuildState *  buildstate, int  levelStep  )

static

Definition at line 853 of file gistbuild.c.

{
    double      pagesPerBuffer;
    double      avgIndexTuplesPerPage;
    double      itupAvgSize;
    Size        pageFreeSpace;
 
    /* Calc space of index page which is available for index tuples */
    pageFreeSpace = BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)
        - sizeof(ItemIdData)
        - buildstate->freespace;
 
    /*
     * Calculate average size of already inserted index tuples using gathered
     * statistics.
     */
    itupAvgSize = (double) buildstate->indtuplesSize /
        (double) buildstate->indtuples;
 
    avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;
 
    /*
     * Recalculate required size of buffers.
     */
    pagesPerBuffer = 2 * pow(avgIndexTuplesPerPage, levelStep);
 
    return (int) rint(pagesPerBuffer);
}

References GISTBuildState::freespace, GISTBuildState::indtuples, GISTBuildState::indtuplesSize, and SizeOfPageHeaderData.

Referenced by gistBuildCallback(), and gistInitBuffering().

gist_indexsortbuild()

static void gist_indexsortbuild ( GISTBuildState *  state )

static

Definition at line 404 of file gistbuild.c.

{
    IndexTuple  itup;
    GistSortedBuildLevelState *levelstate;
    Page        page;
 
    state->pages_allocated = 0;
    state->pages_written = 0;
    state->ready_num_pages = 0;
 
    /*
     * Write an empty page as a placeholder for the root page. It will be
     * replaced with the real root page at the end.
     */
    page = palloc_aligned(BLCKSZ, PG_IO_ALIGN_SIZE, MCXT_ALLOC_ZERO);
    smgrextend(RelationGetSmgr(state->indexrel), MAIN_FORKNUM, GIST_ROOT_BLKNO,
               page, true);
    state->pages_allocated++;
    state->pages_written++;
 
    /* Allocate a temporary buffer for the first leaf page batch. */
    levelstate = palloc0(sizeof(GistSortedBuildLevelState));
    levelstate->pages[0] = page;
    levelstate->parent = NULL;
    gistinitpage(page, F_LEAF);
 
    /*
     * Fill index pages with tuples in the sorted order.
     */
    while ((itup = tuplesort_getindextuple(state->sortstate, true)) != NULL)
    {
        gist_indexsortbuild_levelstate_add(state, levelstate, itup);
        MemoryContextReset(state->giststate->tempCxt);
    }
 
    /*
     * Write out the partially full non-root pages.
     *
     * Keep in mind that flush can build a new root. If number of pages is > 1
     * then new root is required.
     */
    while (levelstate->parent != NULL || levelstate->current_page != 0)
    {
        GistSortedBuildLevelState *parent;
 
        gist_indexsortbuild_levelstate_flush(state, levelstate);
        parent = levelstate->parent;
        for (int i = 0; i < GIST_SORTED_BUILD_PAGE_NUM; i++)
            if (levelstate->pages[i])
                pfree(levelstate->pages[i]);
        pfree(levelstate);
        levelstate = parent;
    }
 
    gist_indexsortbuild_flush_ready_pages(state);
 
    /* Write out the root */
    PageSetLSN(levelstate->pages[0], GistBuildLSN);
    PageSetChecksumInplace(levelstate->pages[0], GIST_ROOT_BLKNO);
    smgrwrite(RelationGetSmgr(state->indexrel), MAIN_FORKNUM, GIST_ROOT_BLKNO,
              levelstate->pages[0], true);
    if (RelationNeedsWAL(state->indexrel))
        log_newpage(&state->indexrel->rd_locator, MAIN_FORKNUM, GIST_ROOT_BLKNO,
                    levelstate->pages[0], true);
 
    pfree(levelstate->pages[0]);
    pfree(levelstate);
 
    /*
     * When we WAL-logged index pages, we must nonetheless fsync index files.
     * Since we're building outside shared buffers, a CHECKPOINT occurring
     * during the build has no way to flush the previously written data to
     * disk (indeed it won't know the index even exists).  A crash later on
     * would replay WAL from the checkpoint, therefore it wouldn't replay our
     * earlier WAL entries. If we do not fsync those pages here, they might
     * still not be on disk when the crash occurs.
     */
    if (RelationNeedsWAL(state->indexrel))
        smgrimmedsync(RelationGetSmgr(state->indexrel), MAIN_FORKNUM);
}

References GistSortedBuildLevelState::current_page, F_LEAF, gist_indexsortbuild_flush_ready_pages(), gist_indexsortbuild_levelstate_add(), gist_indexsortbuild_levelstate_flush(), GIST_ROOT_BLKNO, GIST_SORTED_BUILD_PAGE_NUM, GistBuildLSN, gistinitpage(), i, log_newpage(), MAIN_FORKNUM, MCXT_ALLOC_ZERO, MemoryContextReset(), GistSortedBuildLevelState::pages, PageSetChecksumInplace(), PageSetLSN(), palloc0(), palloc_aligned(), GistSortedBuildLevelState::parent, pfree(), PG_IO_ALIGN_SIZE, RelationGetSmgr(), RelationNeedsWAL, smgrextend(), smgrimmedsync(), smgrwrite(), and tuplesort_getindextuple().

Referenced by gistbuild().

gist_indexsortbuild_flush_ready_pages()

static void gist_indexsortbuild_flush_ready_pages ( GISTBuildState *  state )

static

Definition at line 645 of file gistbuild.c.

{
    if (state->ready_num_pages == 0)
        return;
 
    for (int i = 0; i < state->ready_num_pages; i++)
    {
        Page        page = state->ready_pages[i];
        BlockNumber blkno = state->ready_blknos[i];
 
        /* Currently, the blocks must be buffered in order. */
        if (blkno != state->pages_written)
            elog(ERROR, "unexpected block number to flush GiST sorting build");
 
        PageSetLSN(page, GistBuildLSN);
        PageSetChecksumInplace(page, blkno);
        smgrextend(RelationGetSmgr(state->indexrel), MAIN_FORKNUM, blkno, page,
                   true);
 
        state->pages_written++;
    }
 
    if (RelationNeedsWAL(state->indexrel))
        log_newpages(&state->indexrel->rd_locator, MAIN_FORKNUM, state->ready_num_pages,
                     state->ready_blknos, state->ready_pages, true);
 
    for (int i = 0; i < state->ready_num_pages; i++)
        pfree(state->ready_pages[i]);
 
    state->ready_num_pages = 0;
}

References elog(), ERROR, GistBuildLSN, i, log_newpages(), MAIN_FORKNUM, PageSetChecksumInplace(), PageSetLSN(), pfree(), RelationGetSmgr(), RelationNeedsWAL, and smgrextend().

Referenced by gist_indexsortbuild(), and gist_indexsortbuild_levelstate_flush().

gist_indexsortbuild_levelstate_add()

static void gist_indexsortbuild_levelstate_add ( GISTBuildState *  state, GistSortedBuildLevelState *  levelstate, IndexTuple  itup  )

static

Definition at line 490 of file gistbuild.c.

{
    Size        sizeNeeded;
 
    /* Check if tuple can be added to the current page */
    sizeNeeded = IndexTupleSize(itup) + sizeof(ItemIdData); /* fillfactor ignored */
    if (PageGetFreeSpace(levelstate->pages[levelstate->current_page]) < sizeNeeded)
    {
        Page        newPage;
        Page        old_page = levelstate->pages[levelstate->current_page];
        uint16      old_page_flags = GistPageGetOpaque(old_page)->flags;
 
        if (levelstate->current_page + 1 == GIST_SORTED_BUILD_PAGE_NUM)
        {
            gist_indexsortbuild_levelstate_flush(state, levelstate);
        }
        else
            levelstate->current_page++;
 
        if (levelstate->pages[levelstate->current_page] == NULL)
            levelstate->pages[levelstate->current_page] =
                palloc_aligned(BLCKSZ, PG_IO_ALIGN_SIZE, 0);
 
        newPage = levelstate->pages[levelstate->current_page];
        gistinitpage(newPage, old_page_flags);
    }
 
    gistfillbuffer(levelstate->pages[levelstate->current_page], &itup, 1, InvalidOffsetNumber);
}

References GistSortedBuildLevelState::current_page, gist_indexsortbuild_levelstate_flush(), GIST_SORTED_BUILD_PAGE_NUM, gistfillbuffer(), gistinitpage(), GistPageGetOpaque, IndexTupleSize, InvalidOffsetNumber, PageGetFreeSpace(), GistSortedBuildLevelState::pages, palloc_aligned(), and PG_IO_ALIGN_SIZE.

Referenced by gist_indexsortbuild(), and gist_indexsortbuild_levelstate_flush().

gist_indexsortbuild_levelstate_flush()

static void gist_indexsortbuild_levelstate_flush ( GISTBuildState *  state, GistSortedBuildLevelState *  levelstate  )

static

Definition at line 523 of file gistbuild.c.

{
    GistSortedBuildLevelState *parent;
    BlockNumber blkno;
    MemoryContext oldCtx;
    IndexTuple  union_tuple;
    SplitedPageLayout *dist;
    IndexTuple *itvec;
    int         vect_len;
    bool        isleaf = GistPageIsLeaf(levelstate->pages[0]);
 
    CHECK_FOR_INTERRUPTS();
 
    oldCtx = MemoryContextSwitchTo(state->giststate->tempCxt);
 
    /* Get index tuples from first page */
    itvec = gistextractpage(levelstate->pages[0], &vect_len);
    if (levelstate->current_page > 0)
    {
        /* Append tuples from each page */
        for (int i = 1; i < levelstate->current_page + 1; i++)
        {
            int         len_local;
            IndexTuple *itvec_local = gistextractpage(levelstate->pages[i], &len_local);
 
            itvec = gistjoinvector(itvec, &vect_len, itvec_local, len_local);
            pfree(itvec_local);
        }
 
        /* Apply picksplit to list of all collected tuples */
        dist = gistSplit(state->indexrel, levelstate->pages[0], itvec, vect_len, state->giststate);
    }
    else
    {
        /* Create splitted layout from single page */
        dist = (SplitedPageLayout *) palloc0(sizeof(SplitedPageLayout));
        union_tuple = gistunion(state->indexrel, itvec, vect_len,
                                state->giststate);
        dist->itup = union_tuple;
        dist->list = gistfillitupvec(itvec, vect_len, &(dist->lenlist));
        dist->block.num = vect_len;
    }
 
    MemoryContextSwitchTo(oldCtx);
 
    /* Reset page counter */
    levelstate->current_page = 0;
 
    /* Create pages for all partitions in split result */
    for (; dist != NULL; dist = dist->next)
    {
        char       *data;
        Page        target;
 
        /* check once per page */
        CHECK_FOR_INTERRUPTS();
 
        /* Create page and copy data */
        data = (char *) (dist->list);
        target = palloc_aligned(BLCKSZ, PG_IO_ALIGN_SIZE, MCXT_ALLOC_ZERO);
        gistinitpage(target, isleaf ? F_LEAF : 0);
        for (int i = 0; i < dist->block.num; i++)
        {
            IndexTuple  thistup = (IndexTuple) data;
 
            if (PageAddItem(target, (Item) data, IndexTupleSize(thistup), i + FirstOffsetNumber, false, false) == InvalidOffsetNumber)
                elog(ERROR, "failed to add item to index page in \"%s\"", RelationGetRelationName(state->indexrel));
 
            data += IndexTupleSize(thistup);
        }
        union_tuple = dist->itup;
 
        if (state->ready_num_pages == XLR_MAX_BLOCK_ID)
            gist_indexsortbuild_flush_ready_pages(state);
 
        /*
         * The page is now complete. Assign a block number to it, and add it
         * to the list of finished pages. (We don't write it out immediately,
         * because we want to WAL-log the pages in batches.)
         */
        blkno = state->pages_allocated++;
        state->ready_blknos[state->ready_num_pages] = blkno;
        state->ready_pages[state->ready_num_pages] = target;
        state->ready_num_pages++;
        ItemPointerSetBlockNumber(&(union_tuple->t_tid), blkno);
 
        /*
         * Set the right link to point to the previous page. This is just for
         * debugging purposes: GiST only follows the right link if a page is
         * split concurrently to a scan, and that cannot happen during index
         * build.
         *
         * It's a bit counterintuitive that we set the right link on the new
         * page to point to the previous page, not the other way around. But
         * GiST pages are not ordered like B-tree pages are, so as long as the
         * right-links form a chain through all the pages at the same level,
         * the order doesn't matter.
         */
        if (levelstate->last_blkno)
            GistPageGetOpaque(target)->rightlink = levelstate->last_blkno;
        levelstate->last_blkno = blkno;
 
        /*
         * Insert the downlink to the parent page. If this was the root,
         * create a new page as the parent, which becomes the new root.
         */
        parent = levelstate->parent;
        if (parent == NULL)
        {
            parent = palloc0(sizeof(GistSortedBuildLevelState));
            parent->pages[0] = (Page) palloc_aligned(BLCKSZ, PG_IO_ALIGN_SIZE, 0);
            parent->parent = NULL;
            gistinitpage(parent->pages[0], 0);
 
            levelstate->parent = parent;
        }
        gist_indexsortbuild_levelstate_add(state, parent, union_tuple);
    }
}

References SplitedPageLayout::block, CHECK_FOR_INTERRUPTS, GistSortedBuildLevelState::current_page, data, elog(), ERROR, F_LEAF, FirstOffsetNumber, gist_indexsortbuild_flush_ready_pages(), gist_indexsortbuild_levelstate_add(), gistextractpage(), gistfillitupvec(), gistinitpage(), gistjoinvector(), GistPageGetOpaque, GistPageIsLeaf, gistSplit(), gistunion(), i, IndexTupleSize, InvalidOffsetNumber, ItemPointerSetBlockNumber(), SplitedPageLayout::itup, GistSortedBuildLevelState::last_blkno, SplitedPageLayout::lenlist, SplitedPageLayout::list, MCXT_ALLOC_ZERO, MemoryContextSwitchTo(), SplitedPageLayout::next, gistxlogPage::num, PageAddItem, GistSortedBuildLevelState::pages, palloc0(), palloc_aligned(), GistSortedBuildLevelState::parent, pfree(), PG_IO_ALIGN_SIZE, RelationGetRelationName, IndexTupleData::t_tid, and XLR_MAX_BLOCK_ID.

Referenced by gist_indexsortbuild(), and gist_indexsortbuild_levelstate_add().

gistBufferingBuildInsert()

static void gistBufferingBuildInsert ( GISTBuildState *  buildstate, IndexTuple  itup  )

static

Definition at line 973 of file gistbuild.c.

{
    /* Insert the tuple to buffers. */
    gistProcessItup(buildstate, itup, 0, buildstate->gfbb->rootlevel);
 
    /* If we filled up (half of a) buffer, process buffer emptying. */
    gistProcessEmptyingQueue(buildstate);
}

References GISTBuildState::gfbb, gistProcessEmptyingQueue(), gistProcessItup(), and GISTBuildBuffers::rootlevel.

Referenced by gistBuildCallback().

gistBufferingFindCorrectParent()

static Buffer gistBufferingFindCorrectParent ( GISTBuildState *  buildstate, BlockNumber  childblkno, int  level, BlockNumber *  parentblkno, OffsetNumber *  downlinkoffnum  )

static

Definition at line 1289 of file gistbuild.c.

{
    BlockNumber parent;
    Buffer      buffer;
    Page        page;
    OffsetNumber maxoff;
    OffsetNumber off;
 
    if (level > 0)
        parent = gistGetParent(buildstate, childblkno);
    else
    {
        /*
         * For a leaf page, the caller must supply a correct parent block
         * number.
         */
        if (*parentblkno == InvalidBlockNumber)
            elog(ERROR, "no parent buffer provided of child %u", childblkno);
        parent = *parentblkno;
    }
 
    buffer = ReadBuffer(buildstate->indexrel, parent);
    page = BufferGetPage(buffer);
    LockBuffer(buffer, GIST_EXCLUSIVE);
    gistcheckpage(buildstate->indexrel, buffer);
    maxoff = PageGetMaxOffsetNumber(page);
 
    /* Check if it was not moved */
    if (parent == *parentblkno && *parentblkno != InvalidBlockNumber &&
        *downlinkoffnum != InvalidOffsetNumber && *downlinkoffnum <= maxoff)
    {
        ItemId      iid = PageGetItemId(page, *downlinkoffnum);
        IndexTuple  idxtuple = (IndexTuple) PageGetItem(page, iid);
 
        if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == childblkno)
        {
            /* Still there */
            return buffer;
        }
    }
 
    /*
     * Downlink was not at the offset where it used to be. Scan the page to
     * find it. During normal gist insertions, it might've moved to another
     * page, to the right, but during a buffering build, we keep track of the
     * parent of each page in the lookup table so we should always know what
     * page it's on.
     */
    for (off = FirstOffsetNumber; off <= maxoff; off = OffsetNumberNext(off))
    {
        ItemId      iid = PageGetItemId(page, off);
        IndexTuple  idxtuple = (IndexTuple) PageGetItem(page, iid);
 
        if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == childblkno)
        {
            /* yes!!, found it */
            *downlinkoffnum = off;
            return buffer;
        }
    }
 
    elog(ERROR, "failed to re-find parent for block %u", childblkno);
    return InvalidBuffer;       /* keep compiler quiet */
}

References BufferGetPage(), elog(), ERROR, FirstOffsetNumber, GIST_EXCLUSIVE, gistcheckpage(), gistGetParent(), GISTBuildState::indexrel, InvalidBlockNumber, InvalidBuffer, InvalidOffsetNumber, ItemPointerGetBlockNumber(), LockBuffer(), OffsetNumberNext, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), GistSortedBuildLevelState::parent, ReadBuffer(), and IndexTupleData::t_tid.

Referenced by gistbufferinginserttuples().

gistbufferinginserttuples()

static BlockNumber gistbufferinginserttuples ( GISTBuildState *  buildstate, Buffer  buffer, int  level, IndexTuple *  itup, int  ntup, OffsetNumber  oldoffnum, BlockNumber  parentblk, OffsetNumber  downlinkoffnum  )

static

Definition at line 1120 of file gistbuild.c.

{
    GISTBuildBuffers *gfbb = buildstate->gfbb;
    List       *splitinfo;
    bool        is_split;
    BlockNumber placed_to_blk = InvalidBlockNumber;
 
    is_split = gistplacetopage(buildstate->indexrel,
                               buildstate->freespace,
                               buildstate->giststate,
                               buffer,
                               itup, ntup, oldoffnum, &placed_to_blk,
                               InvalidBuffer,
                               &splitinfo,
                               false,
                               buildstate->heaprel, true);
 
    /*
     * If this is a root split, update the root path item kept in memory. This
     * ensures that all path stacks are always complete, including all parent
     * nodes up to the root. That simplifies the algorithm to re-find correct
     * parent.
     */
    if (is_split && BufferGetBlockNumber(buffer) == GIST_ROOT_BLKNO)
    {
        Page        page = BufferGetPage(buffer);
        OffsetNumber off;
        OffsetNumber maxoff;
 
        Assert(level == gfbb->rootlevel);
        gfbb->rootlevel++;
 
        elog(DEBUG2, "splitting GiST root page, now %d levels deep", gfbb->rootlevel);
 
        /*
         * All the downlinks on the old root page are now on one of the child
         * pages. Visit all the new child pages to memorize the parents of the
         * grandchildren.
         */
        if (gfbb->rootlevel > 1)
        {
            maxoff = PageGetMaxOffsetNumber(page);
            for (off = FirstOffsetNumber; off <= maxoff; off++)
            {
                ItemId      iid = PageGetItemId(page, off);
                IndexTuple  idxtuple = (IndexTuple) PageGetItem(page, iid);
                BlockNumber childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
                Buffer      childbuf = ReadBuffer(buildstate->indexrel, childblkno);
 
                LockBuffer(childbuf, GIST_SHARE);
                gistMemorizeAllDownlinks(buildstate, childbuf);
                UnlockReleaseBuffer(childbuf);
 
                /*
                 * Also remember that the parent of the new child page is the
                 * root block.
                 */
                gistMemorizeParent(buildstate, childblkno, GIST_ROOT_BLKNO);
            }
        }
    }
 
    if (splitinfo)
    {
        /*
         * Insert the downlinks to the parent. This is analogous with
         * gistfinishsplit() in the regular insertion code, but the locking is
         * simpler, and we have to maintain the buffers on internal nodes and
         * the parent map.
         */
        IndexTuple *downlinks;
        int         ndownlinks,
                    i;
        Buffer      parentBuffer;
        ListCell   *lc;
 
        /* Parent may have changed since we memorized this path. */
        parentBuffer =
            gistBufferingFindCorrectParent(buildstate,
                                           BufferGetBlockNumber(buffer),
                                           level,
                                           &parentblk,
                                           &downlinkoffnum);
 
        /*
         * If there's a buffer associated with this page, that needs to be
         * split too. gistRelocateBuildBuffersOnSplit() will also adjust the
         * downlinks in 'splitinfo', to make sure they're consistent not only
         * with the tuples already on the pages, but also the tuples in the
         * buffers that will eventually be inserted to them.
         */
        gistRelocateBuildBuffersOnSplit(gfbb,
                                        buildstate->giststate,
                                        buildstate->indexrel,
                                        level,
                                        buffer, splitinfo);
 
        /* Create an array of all the downlink tuples */
        ndownlinks = list_length(splitinfo);
        downlinks = (IndexTuple *) palloc(sizeof(IndexTuple) * ndownlinks);
        i = 0;
        foreach(lc, splitinfo)
        {
            GISTPageSplitInfo *splitinfo = lfirst(lc);
 
            /*
             * Remember the parent of each new child page in our parent map.
             * This assumes that the downlinks fit on the parent page. If the
             * parent page is split, too, when we recurse up to insert the
             * downlinks, the recursive gistbufferinginserttuples() call will
             * update the map again.
             */
            if (level > 0)
                gistMemorizeParent(buildstate,
                                   BufferGetBlockNumber(splitinfo->buf),
                                   BufferGetBlockNumber(parentBuffer));
 
            /*
             * Also update the parent map for all the downlinks that got moved
             * to a different page. (actually this also loops through the
             * downlinks that stayed on the original page, but it does no
             * harm).
             */
            if (level > 1)
                gistMemorizeAllDownlinks(buildstate, splitinfo->buf);
 
            /*
             * Since there's no concurrent access, we can release the lower
             * level buffers immediately. This includes the original page.
             */
            UnlockReleaseBuffer(splitinfo->buf);
            downlinks[i++] = splitinfo->downlink;
        }
 
        /* Insert them into parent. */
        gistbufferinginserttuples(buildstate, parentBuffer, level + 1,
                                  downlinks, ndownlinks, downlinkoffnum,
                                  InvalidBlockNumber, InvalidOffsetNumber);
 
        list_free_deep(splitinfo);  /* we don't need this anymore */
    }
    else
        UnlockReleaseBuffer(buffer);
 
    return placed_to_blk;
}

References Assert(), GISTPageSplitInfo::buf, BufferGetBlockNumber(), BufferGetPage(), DEBUG2, GISTPageSplitInfo::downlink, elog(), FirstOffsetNumber, GISTBuildState::freespace, GISTBuildState::gfbb, GIST_ROOT_BLKNO, GIST_SHARE, gistBufferingFindCorrectParent(), gistMemorizeAllDownlinks(), gistMemorizeParent(), gistplacetopage(), gistRelocateBuildBuffersOnSplit(), GISTBuildState::giststate, GISTBuildState::heaprel, i, GISTBuildState::indexrel, InvalidBlockNumber, InvalidBuffer, InvalidOffsetNumber, ItemPointerGetBlockNumber(), lfirst, list_free_deep(), list_length(), LockBuffer(), PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), palloc(), ReadBuffer(), GISTBuildBuffers::rootlevel, IndexTupleData::t_tid, and UnlockReleaseBuffer().

Referenced by gistProcessItup().

gistbuild()

IndexBuildResult* gistbuild	(	Relation	heap,
		Relation	index,
		IndexInfo *	indexInfo
	)

Definition at line 183 of file gistbuild.c.

{
    IndexBuildResult *result;
    double      reltuples;
    GISTBuildState buildstate;
    MemoryContext oldcxt = CurrentMemoryContext;
    int         fillfactor;
    Oid         SortSupportFnOids[INDEX_MAX_KEYS];
    GiSTOptions *options = (GiSTOptions *) index->rd_options;
 
    /*
     * We expect to be called exactly once for any index relation. If that's
     * not the case, big trouble's what we have.
     */
    if (RelationGetNumberOfBlocks(index) != 0)
        elog(ERROR, "index \"%s\" already contains data",
             RelationGetRelationName(index));
 
    buildstate.indexrel = index;
    buildstate.heaprel = heap;
    buildstate.sortstate = NULL;
    buildstate.giststate = initGISTstate(index);
 
    /*
     * Create a temporary memory context that is reset once for each tuple
     * processed.  (Note: we don't bother to make this a child of the
     * giststate's scanCxt, so we have to delete it separately at the end.)
     */
    buildstate.giststate->tempCxt = createTempGistContext();
 
    /*
     * Choose build strategy.  First check whether the user specified to use
     * buffering mode.  (The use-case for that in the field is somewhat
     * questionable perhaps, but it's important for testing purposes.)
     */
    if (options)
    {
        if (options->buffering_mode == GIST_OPTION_BUFFERING_ON)
            buildstate.buildMode = GIST_BUFFERING_STATS;
        else if (options->buffering_mode == GIST_OPTION_BUFFERING_OFF)
            buildstate.buildMode = GIST_BUFFERING_DISABLED;
        else                    /* must be "auto" */
            buildstate.buildMode = GIST_BUFFERING_AUTO;
    }
    else
    {
        buildstate.buildMode = GIST_BUFFERING_AUTO;
    }
 
    /*
     * Unless buffering mode was forced, see if we can use sorting instead.
     */
    if (buildstate.buildMode != GIST_BUFFERING_STATS)
    {
        bool        hasallsortsupports = true;
        int         keyscount = IndexRelationGetNumberOfKeyAttributes(index);
 
        for (int i = 0; i < keyscount; i++)
        {
            SortSupportFnOids[i] = index_getprocid(index, i + 1,
                                                   GIST_SORTSUPPORT_PROC);
            if (!OidIsValid(SortSupportFnOids[i]))
            {
                hasallsortsupports = false;
                break;
            }
        }
        if (hasallsortsupports)
            buildstate.buildMode = GIST_SORTED_BUILD;
    }
 
    /*
     * Calculate target amount of free space to leave on pages.
     */
    fillfactor = options ? options->fillfactor : GIST_DEFAULT_FILLFACTOR;
    buildstate.freespace = BLCKSZ * (100 - fillfactor) / 100;
 
    /*
     * Build the index using the chosen strategy.
     */
    buildstate.indtuples = 0;
    buildstate.indtuplesSize = 0;
 
    if (buildstate.buildMode == GIST_SORTED_BUILD)
    {
        /*
         * Sort all data, build the index from bottom up.
         */
        buildstate.sortstate = tuplesort_begin_index_gist(heap,
                                                          index,
                                                          maintenance_work_mem,
                                                          NULL,
                                                          TUPLESORT_NONE);
 
        /* Scan the table, adding all tuples to the tuplesort */
        reltuples = table_index_build_scan(heap, index, indexInfo, true, true,
                                           gistSortedBuildCallback,
                                           (void *) &buildstate, NULL);
 
        /*
         * Perform the sort and build index pages.
         */
        tuplesort_performsort(buildstate.sortstate);
 
        gist_indexsortbuild(&buildstate);
 
        tuplesort_end(buildstate.sortstate);
    }
    else
    {
        /*
         * Initialize an empty index and insert all tuples, possibly using
         * buffers on intermediate levels.
         */
        Buffer      buffer;
        Page        page;
 
        /* initialize the root page */
        buffer = gistNewBuffer(index, heap);
        Assert(BufferGetBlockNumber(buffer) == GIST_ROOT_BLKNO);
        page = BufferGetPage(buffer);
 
        START_CRIT_SECTION();
 
        GISTInitBuffer(buffer, F_LEAF);
 
        MarkBufferDirty(buffer);
        PageSetLSN(page, GistBuildLSN);
 
        UnlockReleaseBuffer(buffer);
 
        END_CRIT_SECTION();
 
        /* Scan the table, inserting all the tuples to the index. */
        reltuples = table_index_build_scan(heap, index, indexInfo, true, true,
                                           gistBuildCallback,
                                           (void *) &buildstate, NULL);
 
        /*
         * If buffering was used, flush out all the tuples that are still in
         * the buffers.
         */
        if (buildstate.buildMode == GIST_BUFFERING_ACTIVE)
        {
            elog(DEBUG1, "all tuples processed, emptying buffers");
            gistEmptyAllBuffers(&buildstate);
            gistFreeBuildBuffers(buildstate.gfbb);
        }
 
        /*
         * We didn't write WAL records as we built the index, so if
         * WAL-logging is required, write all pages to the WAL now.
         */
        if (RelationNeedsWAL(index))
        {
            log_newpage_range(index, MAIN_FORKNUM,
                              0, RelationGetNumberOfBlocks(index),
                              true);
        }
    }
 
    /* okay, all heap tuples are indexed */
    MemoryContextSwitchTo(oldcxt);
    MemoryContextDelete(buildstate.giststate->tempCxt);
 
    freeGISTstate(buildstate.giststate);
 
    /*
     * Return statistics
     */
    result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));
 
    result->heap_tuples = reltuples;
    result->index_tuples = (double) buildstate.indtuples;
 
    return result;
}

References Assert(), BufferGetBlockNumber(), BufferGetPage(), GISTBuildState::buildMode, createTempGistContext(), CurrentMemoryContext, DEBUG1, elog(), END_CRIT_SECTION, ERROR, F_LEAF, fillfactor, freeGISTstate(), GISTBuildState::freespace, GIST_BUFFERING_ACTIVE, GIST_BUFFERING_AUTO, GIST_BUFFERING_DISABLED, GIST_BUFFERING_STATS, GIST_DEFAULT_FILLFACTOR, gist_indexsortbuild(), GIST_OPTION_BUFFERING_OFF, GIST_OPTION_BUFFERING_ON, GIST_ROOT_BLKNO, GIST_SORTED_BUILD, GIST_SORTSUPPORT_PROC, gistBuildCallback(), GistBuildLSN, gistEmptyAllBuffers(), gistFreeBuildBuffers(), GISTInitBuffer(), gistNewBuffer(), gistSortedBuildCallback(), GISTBuildState::giststate, IndexBuildResult::heap_tuples, GISTBuildState::heaprel, i, if(), index_getprocid(), INDEX_MAX_KEYS, IndexBuildResult::index_tuples, GISTBuildState::indexrel, IndexRelationGetNumberOfKeyAttributes, GISTBuildState::indtuples, GISTBuildState::indtuplesSize, initGISTstate(), log_newpage_range(), MAIN_FORKNUM, maintenance_work_mem, MarkBufferDirty(), MemoryContextDelete(), MemoryContextSwitchTo(), OidIsValid, PageSetLSN(), palloc(), RelationGetNumberOfBlocks, RelationGetRelationName, RelationNeedsWAL, GISTBuildState::sortstate, START_CRIT_SECTION, table_index_build_scan(), GISTSTATE::tempCxt, tuplesort_begin_index_gist(), tuplesort_end(), TUPLESORT_NONE, tuplesort_performsort(), and UnlockReleaseBuffer().

Referenced by gisthandler().

gistBuildCallback()

static void gistBuildCallback ( Relation  index, ItemPointer  tid, Datum *  values, bool *  isnull, bool  tupleIsAlive, void *  state  )

static

Definition at line 886 of file gistbuild.c.

{
    GISTBuildState *buildstate = (GISTBuildState *) state;
    IndexTuple  itup;
    MemoryContext oldCtx;
 
    oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
 
    /* form an index tuple and point it at the heap tuple */
    itup = gistFormTuple(buildstate->giststate, index,
                         values, isnull,
                         true);
    itup->t_tid = *tid;
 
    /* Update tuple count and total size. */
    buildstate->indtuples += 1;
    buildstate->indtuplesSize += IndexTupleSize(itup);
 
    /*
     * XXX In buffering builds, the tempCxt is also reset down inside
     * gistProcessEmptyingQueue().  This is not great because it risks
     * confusion and possible use of dangling pointers (for example, itup
     * might be already freed when control returns here).  It's generally
     * better that a memory context be "owned" by only one function.  However,
     * currently this isn't causing issues so it doesn't seem worth the amount
     * of refactoring that would be needed to avoid it.
     */
    if (buildstate->buildMode == GIST_BUFFERING_ACTIVE)
    {
        /* We have buffers, so use them. */
        gistBufferingBuildInsert(buildstate, itup);
    }
    else
    {
        /*
         * There's no buffers (yet). Since we already have the index relation
         * locked, we call gistdoinsert directly.
         */
        gistdoinsert(index, itup, buildstate->freespace,
                     buildstate->giststate, buildstate->heaprel, true);
    }
 
    MemoryContextSwitchTo(oldCtx);
    MemoryContextReset(buildstate->giststate->tempCxt);
 
    if (buildstate->buildMode == GIST_BUFFERING_ACTIVE &&
        buildstate->indtuples % BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET == 0)
    {
        /* Adjust the target buffer size now */
        buildstate->gfbb->pagesPerBuffer =
            calculatePagesPerBuffer(buildstate, buildstate->gfbb->levelStep);
    }
 
    /*
     * In 'auto' mode, check if the index has grown too large to fit in cache,
     * and switch to buffering mode if it has.
     *
     * To avoid excessive calls to smgrnblocks(), only check this every
     * BUFFERING_MODE_SWITCH_CHECK_STEP index tuples.
     *
     * In 'stats' state, switch as soon as we have seen enough tuples to have
     * some idea of the average tuple size.
     */
    if ((buildstate->buildMode == GIST_BUFFERING_AUTO &&
         buildstate->indtuples % BUFFERING_MODE_SWITCH_CHECK_STEP == 0 &&
         effective_cache_size < smgrnblocks(RelationGetSmgr(index),
                                            MAIN_FORKNUM)) ||
        (buildstate->buildMode == GIST_BUFFERING_STATS &&
         buildstate->indtuples >= BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET))
    {
        /*
         * Index doesn't fit in effective cache anymore. Try to switch to
         * buffering build mode.
         */
        gistInitBuffering(buildstate);
    }
}

References BUFFERING_MODE_SWITCH_CHECK_STEP, BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET, GISTBuildState::buildMode, calculatePagesPerBuffer(), effective_cache_size, GISTBuildState::freespace, GISTBuildState::gfbb, GIST_BUFFERING_ACTIVE, GIST_BUFFERING_AUTO, GIST_BUFFERING_STATS, gistBufferingBuildInsert(), gistdoinsert(), gistFormTuple(), gistInitBuffering(), GISTBuildState::giststate, GISTBuildState::heaprel, IndexTupleSize, GISTBuildState::indtuples, GISTBuildState::indtuplesSize, GISTBuildBuffers::levelStep, MAIN_FORKNUM, MemoryContextReset(), MemoryContextSwitchTo(), GISTBuildBuffers::pagesPerBuffer, RelationGetSmgr(), smgrnblocks(), IndexTupleData::t_tid, GISTSTATE::tempCxt, and values.

Referenced by gistbuild().

gistEmptyAllBuffers()

static void gistEmptyAllBuffers ( GISTBuildState *  buildstate )

static

Definition at line 1436 of file gistbuild.c.

{
    GISTBuildBuffers *gfbb = buildstate->gfbb;
    MemoryContext oldCtx;
    int         i;
 
    oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
 
    /*
     * Iterate through the levels from top to bottom.
     */
    for (i = gfbb->buffersOnLevelsLen - 1; i >= 0; i--)
    {
        /*
         * Empty all buffers on this level. Note that new buffers can pop up
         * in the list during the processing, as a result of page splits, so a
         * simple walk through the list won't work. We remove buffers from the
         * list when we see them empty; a buffer can't become non-empty once
         * it's been fully emptied.
         */
        while (gfbb->buffersOnLevels[i] != NIL)
        {
            GISTNodeBuffer *nodeBuffer;
 
            nodeBuffer = (GISTNodeBuffer *) linitial(gfbb->buffersOnLevels[i]);
 
            if (nodeBuffer->blocksCount != 0)
            {
                /*
                 * Add this buffer to the emptying queue, and proceed to empty
                 * the queue.
                 */
                if (!nodeBuffer->queuedForEmptying)
                {
                    MemoryContextSwitchTo(gfbb->context);
                    nodeBuffer->queuedForEmptying = true;
                    gfbb->bufferEmptyingQueue =
                        lcons(nodeBuffer, gfbb->bufferEmptyingQueue);
                    MemoryContextSwitchTo(buildstate->giststate->tempCxt);
                }
                gistProcessEmptyingQueue(buildstate);
            }
            else
                gfbb->buffersOnLevels[i] =
                    list_delete_first(gfbb->buffersOnLevels[i]);
        }
        elog(DEBUG2, "emptied all buffers at level %d", i);
    }
    MemoryContextSwitchTo(oldCtx);
}

References GISTNodeBuffer::blocksCount, GISTBuildBuffers::bufferEmptyingQueue, GISTBuildBuffers::buffersOnLevels, GISTBuildBuffers::buffersOnLevelsLen, GISTBuildBuffers::context, DEBUG2, elog(), GISTBuildState::gfbb, gistProcessEmptyingQueue(), GISTBuildState::giststate, i, lcons(), linitial, list_delete_first(), MemoryContextSwitchTo(), NIL, GISTNodeBuffer::queuedForEmptying, and GISTSTATE::tempCxt.

Referenced by gistbuild().

gistGetMaxLevel()

static int gistGetMaxLevel ( Relation  index )

static

Definition at line 1491 of file gistbuild.c.

{
    int         maxLevel;
    BlockNumber blkno;
 
    /*
     * Traverse down the tree, starting from the root, until we hit the leaf
     * level.
     */
    maxLevel = 0;
    blkno = GIST_ROOT_BLKNO;
    while (true)
    {
        Buffer      buffer;
        Page        page;
        IndexTuple  itup;
 
        buffer = ReadBuffer(index, blkno);
 
        /*
         * There's no concurrent access during index build, so locking is just
         * pro forma.
         */
        LockBuffer(buffer, GIST_SHARE);
        page = (Page) BufferGetPage(buffer);
 
        if (GistPageIsLeaf(page))
        {
            /* We hit the bottom, so we're done. */
            UnlockReleaseBuffer(buffer);
            break;
        }
 
        /*
         * Pick the first downlink on the page, and follow it. It doesn't
         * matter which downlink we choose, the tree has the same depth
         * everywhere, so we just pick the first one.
         */
        itup = (IndexTuple) PageGetItem(page,
                                        PageGetItemId(page, FirstOffsetNumber));
        blkno = ItemPointerGetBlockNumber(&(itup->t_tid));
        UnlockReleaseBuffer(buffer);
 
        /*
         * We're going down on the tree. It means that there is yet one more
         * level in the tree.
         */
        maxLevel++;
    }
    return maxLevel;
}

References BufferGetPage(), FirstOffsetNumber, GIST_ROOT_BLKNO, GIST_SHARE, GistPageIsLeaf, ItemPointerGetBlockNumber(), LockBuffer(), PageGetItem(), PageGetItemId(), ReadBuffer(), IndexTupleData::t_tid, and UnlockReleaseBuffer().

Referenced by gistInitBuffering().

gistGetParent()

static BlockNumber gistGetParent ( GISTBuildState *  buildstate, BlockNumber  child  )

static

Definition at line 1631 of file gistbuild.c.

{
    ParentMapEntry *entry;
    bool        found;
 
    /* Find node buffer in hash table */
    entry = (ParentMapEntry *) hash_search(buildstate->parentMap,
                                           &child,
                                           HASH_FIND,
                                           &found);
    if (!found)
        elog(ERROR, "could not find parent of block %u in lookup table", child);
 
    return entry->parentblkno;
}

References elog(), ERROR, HASH_FIND, hash_search(), ParentMapEntry::parentblkno, and GISTBuildState::parentMap.

Referenced by gistBufferingFindCorrectParent().

gistInitBuffering()

static void gistInitBuffering ( GISTBuildState *  buildstate )

static

Definition at line 692 of file gistbuild.c.

{
    Relation    index = buildstate->indexrel;
    int         pagesPerBuffer;
    Size        pageFreeSpace;
    Size        itupAvgSize,
                itupMinSize;
    double      avgIndexTuplesPerPage,
                maxIndexTuplesPerPage;
    int         i;
    int         levelStep;
 
    /* Calc space of index page which is available for index tuples */
    pageFreeSpace = BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)
        - sizeof(ItemIdData)
        - buildstate->freespace;
 
    /*
     * Calculate average size of already inserted index tuples using gathered
     * statistics.
     */
    itupAvgSize = (double) buildstate->indtuplesSize /
        (double) buildstate->indtuples;
 
    /*
     * Calculate minimal possible size of index tuple by index metadata.
     * Minimal possible size of varlena is VARHDRSZ.
     *
     * XXX: that's not actually true, as a short varlen can be just 2 bytes.
     * And we should take padding into account here.
     */
    itupMinSize = (Size) MAXALIGN(sizeof(IndexTupleData));
    for (i = 0; i < index->rd_att->natts; i++)
    {
        if (TupleDescAttr(index->rd_att, i)->attlen < 0)
            itupMinSize += VARHDRSZ;
        else
            itupMinSize += TupleDescAttr(index->rd_att, i)->attlen;
    }
 
    /* Calculate average and maximal number of index tuples which fit to page */
    avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;
    maxIndexTuplesPerPage = pageFreeSpace / itupMinSize;
 
    /*
     * We need to calculate two parameters for the buffering algorithm:
     * levelStep and pagesPerBuffer.
     *
     * levelStep determines the size of subtree that we operate on, while
     * emptying a buffer. A higher value is better, as you need fewer buffer
     * emptying steps to build the index. However, if you set it too high, the
     * subtree doesn't fit in cache anymore, and you quickly lose the benefit
     * of the buffers.
     *
     * In Arge et al's paper, levelStep is chosen as logB(M/4B), where B is
     * the number of tuples on page (ie. fanout), and M is the amount of
     * internal memory available. Curiously, they doesn't explain *why* that
     * setting is optimal. We calculate it by taking the highest levelStep so
     * that a subtree still fits in cache. For a small B, our way of
     * calculating levelStep is very close to Arge et al's formula. For a
     * large B, our formula gives a value that is 2x higher.
     *
     * The average size (in pages) of a subtree of depth n can be calculated
     * as a geometric series:
     *
     * B^0 + B^1 + B^2 + ... + B^n = (1 - B^(n + 1)) / (1 - B)
     *
     * where B is the average number of index tuples on page. The subtree is
     * cached in the shared buffer cache and the OS cache, so we choose
     * levelStep so that the subtree size is comfortably smaller than
     * effective_cache_size, with a safety factor of 4.
     *
     * The estimate on the average number of index tuples on page is based on
     * average tuple sizes observed before switching to buffered build, so the
     * real subtree size can be somewhat larger. Also, it would selfish to
     * gobble the whole cache for our index build. The safety factor of 4
     * should account for those effects.
     *
     * The other limiting factor for setting levelStep is that while
     * processing a subtree, we need to hold one page for each buffer at the
     * next lower buffered level. The max. number of buffers needed for that
     * is maxIndexTuplesPerPage^levelStep. This is very conservative, but
     * hopefully maintenance_work_mem is set high enough that you're
     * constrained by effective_cache_size rather than maintenance_work_mem.
     *
     * XXX: the buffer hash table consumes a fair amount of memory too per
     * buffer, but that is not currently taken into account. That scales on
     * the total number of buffers used, ie. the index size and on levelStep.
     * Note that a higher levelStep *reduces* the amount of memory needed for
     * the hash table.
     */
    levelStep = 1;
    for (;;)
    {
        double      subtreesize;
        double      maxlowestlevelpages;
 
        /* size of an average subtree at this levelStep (in pages). */
        subtreesize =
            (1 - pow(avgIndexTuplesPerPage, (double) (levelStep + 1))) /
            (1 - avgIndexTuplesPerPage);
 
        /* max number of pages at the lowest level of a subtree */
        maxlowestlevelpages = pow(maxIndexTuplesPerPage, (double) levelStep);
 
        /* subtree must fit in cache (with safety factor of 4) */
        if (subtreesize > effective_cache_size / 4)
            break;
 
        /* each node in the lowest level of a subtree has one page in memory */
        if (maxlowestlevelpages > ((double) maintenance_work_mem * 1024) / BLCKSZ)
            break;
 
        /* Good, we can handle this levelStep. See if we can go one higher. */
        levelStep++;
    }
 
    /*
     * We just reached an unacceptable value of levelStep in previous loop.
     * So, decrease levelStep to get last acceptable value.
     */
    levelStep--;
 
    /*
     * If there's not enough cache or maintenance_work_mem, fall back to plain
     * inserts.
     */
    if (levelStep <= 0)
    {
        elog(DEBUG1, "failed to switch to buffered GiST build");
        buildstate->buildMode = GIST_BUFFERING_DISABLED;
        return;
    }
 
    /*
     * The second parameter to set is pagesPerBuffer, which determines the
     * size of each buffer. We adjust pagesPerBuffer also during the build,
     * which is why this calculation is in a separate function.
     */
    pagesPerBuffer = calculatePagesPerBuffer(buildstate, levelStep);
 
    /* Initialize GISTBuildBuffers with these parameters */
    buildstate->gfbb = gistInitBuildBuffers(pagesPerBuffer, levelStep,
                                            gistGetMaxLevel(index));
 
    gistInitParentMap(buildstate);
 
    buildstate->buildMode = GIST_BUFFERING_ACTIVE;
 
    elog(DEBUG1, "switched to buffered GiST build; level step = %d, pagesPerBuffer = %d",
         levelStep, pagesPerBuffer);
}

References GISTBuildState::buildMode, calculatePagesPerBuffer(), DEBUG1, effective_cache_size, elog(), GISTBuildState::freespace, GISTBuildState::gfbb, GIST_BUFFERING_ACTIVE, GIST_BUFFERING_DISABLED, gistGetMaxLevel(), gistInitBuildBuffers(), gistInitParentMap(), i, GISTBuildState::indexrel, GISTBuildState::indtuples, GISTBuildState::indtuplesSize, maintenance_work_mem, MAXALIGN, SizeOfPageHeaderData, TupleDescAttr, and VARHDRSZ.

Referenced by gistBuildCallback().

gistInitParentMap()

static void gistInitParentMap ( GISTBuildState *  buildstate )

static

Definition at line 1580 of file gistbuild.c.

{
    HASHCTL     hashCtl;
 
    hashCtl.keysize = sizeof(BlockNumber);
    hashCtl.entrysize = sizeof(ParentMapEntry);
    hashCtl.hcxt = CurrentMemoryContext;
    buildstate->parentMap = hash_create("gistbuild parent map",
                                        1024,
                                        &hashCtl,
                                        HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
}

References CurrentMemoryContext, HASHCTL::entrysize, HASH_BLOBS, HASH_CONTEXT, hash_create(), HASH_ELEM, HASHCTL::hcxt, HASHCTL::keysize, and GISTBuildState::parentMap.

Referenced by gistInitBuffering().

gistMemorizeAllDownlinks()

static void gistMemorizeAllDownlinks ( GISTBuildState *  buildstate, Buffer  parentbuf  )

static

Definition at line 1610 of file gistbuild.c.

{
    OffsetNumber maxoff;
    OffsetNumber off;
    BlockNumber parentblkno = BufferGetBlockNumber(parentbuf);
    Page        page = BufferGetPage(parentbuf);
 
    Assert(!GistPageIsLeaf(page));
 
    maxoff = PageGetMaxOffsetNumber(page);
    for (off = FirstOffsetNumber; off <= maxoff; off++)
    {
        ItemId      iid = PageGetItemId(page, off);
        IndexTuple  idxtuple = (IndexTuple) PageGetItem(page, iid);
        BlockNumber childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
 
        gistMemorizeParent(buildstate, childblkno, parentblkno);
    }
}

References Assert(), BufferGetBlockNumber(), BufferGetPage(), FirstOffsetNumber, gistMemorizeParent(), GistPageIsLeaf, ItemPointerGetBlockNumber(), PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), and IndexTupleData::t_tid.

Referenced by gistbufferinginserttuples().

gistMemorizeParent()

static void gistMemorizeParent ( GISTBuildState *  buildstate, BlockNumber  child, BlockNumber  parent  )

static

Definition at line 1594 of file gistbuild.c.

{
    ParentMapEntry *entry;
    bool        found;
 
    entry = (ParentMapEntry *) hash_search(buildstate->parentMap,
                                           &child,
                                           HASH_ENTER,
                                           &found);
    entry->parentblkno = parent;
}

References HASH_ENTER, hash_search(), GistSortedBuildLevelState::parent, ParentMapEntry::parentblkno, and GISTBuildState::parentMap.

Referenced by gistbufferinginserttuples(), gistMemorizeAllDownlinks(), and gistProcessItup().

gistProcessEmptyingQueue()

static void gistProcessEmptyingQueue ( GISTBuildState *  buildstate )

static

Definition at line 1363 of file gistbuild.c.

{
    GISTBuildBuffers *gfbb = buildstate->gfbb;
 
    /* Iterate while we have elements in buffers emptying stack. */
    while (gfbb->bufferEmptyingQueue != NIL)
    {
        GISTNodeBuffer *emptyingNodeBuffer;
 
        /* Get node buffer from emptying stack. */
        emptyingNodeBuffer = (GISTNodeBuffer *) linitial(gfbb->bufferEmptyingQueue);
        gfbb->bufferEmptyingQueue = list_delete_first(gfbb->bufferEmptyingQueue);
        emptyingNodeBuffer->queuedForEmptying = false;
 
        /*
         * We are going to load last pages of buffers where emptying will be
         * to. So let's unload any previously loaded buffers.
         */
        gistUnloadNodeBuffers(gfbb);
 
        /*
         * Pop tuples from the buffer and run them down to the buffers at
         * lower level, or leaf pages. We continue until one of the lower
         * level buffers fills up, or this buffer runs empty.
         *
         * In Arge et al's paper, the buffer emptying is stopped after
         * processing 1/2 node buffer worth of tuples, to avoid overfilling
         * any of the lower level buffers. However, it's more efficient to
         * keep going until one of the lower level buffers actually fills up,
         * so that's what we do. This doesn't need to be exact, if a buffer
         * overfills by a few tuples, there's no harm done.
         */
        while (true)
        {
            IndexTuple  itup;
 
            /* Get next index tuple from the buffer */
            if (!gistPopItupFromNodeBuffer(gfbb, emptyingNodeBuffer, &itup))
                break;
 
            /*
             * Run it down to the underlying node buffer or leaf page.
             *
             * Note: it's possible that the buffer we're emptying splits as a
             * result of this call. If that happens, our emptyingNodeBuffer
             * points to the left half of the split. After split, it's very
             * likely that the new left buffer is no longer over the half-full
             * threshold, but we might as well keep flushing tuples from it
             * until we fill a lower-level buffer.
             */
            if (gistProcessItup(buildstate, itup, emptyingNodeBuffer->nodeBlocknum, emptyingNodeBuffer->level))
            {
                /*
                 * A lower level buffer filled up. Stop emptying this buffer,
                 * to avoid overflowing the lower level buffer.
                 */
                break;
            }
 
            /* Free all the memory allocated during index tuple processing */
            MemoryContextReset(buildstate->giststate->tempCxt);
        }
    }
}

References GISTBuildBuffers::bufferEmptyingQueue, GISTBuildState::gfbb, gistPopItupFromNodeBuffer(), gistProcessItup(), GISTBuildState::giststate, gistUnloadNodeBuffers(), GISTNodeBuffer::level, linitial, list_delete_first(), MemoryContextReset(), NIL, GISTNodeBuffer::nodeBlocknum, GISTNodeBuffer::queuedForEmptying, and GISTSTATE::tempCxt.

Referenced by gistBufferingBuildInsert(), and gistEmptyAllBuffers().

gistProcessItup()

static bool gistProcessItup ( GISTBuildState *  buildstate, IndexTuple  itup, BlockNumber  startblkno, int  startlevel  )

static

Definition at line 989 of file gistbuild.c.

{
    GISTSTATE  *giststate = buildstate->giststate;
    GISTBuildBuffers *gfbb = buildstate->gfbb;
    Relation    indexrel = buildstate->indexrel;
    BlockNumber childblkno;
    Buffer      buffer;
    bool        result = false;
    BlockNumber blkno;
    int         level;
    OffsetNumber downlinkoffnum = InvalidOffsetNumber;
    BlockNumber parentblkno = InvalidBlockNumber;
 
    CHECK_FOR_INTERRUPTS();
 
    /*
     * Loop until we reach a leaf page (level == 0) or a level with buffers
     * (not including the level we start at, because we would otherwise make
     * no progress).
     */
    blkno = startblkno;
    level = startlevel;
    for (;;)
    {
        ItemId      iid;
        IndexTuple  idxtuple,
                    newtup;
        Page        page;
        OffsetNumber childoffnum;
 
        /* Have we reached a level with buffers? */
        if (LEVEL_HAS_BUFFERS(level, gfbb) && level != startlevel)
            break;
 
        /* Have we reached a leaf page? */
        if (level == 0)
            break;
 
        /*
         * Nope. Descend down to the next level then. Choose a child to
         * descend down to.
         */
 
        buffer = ReadBuffer(indexrel, blkno);
        LockBuffer(buffer, GIST_EXCLUSIVE);
 
        page = (Page) BufferGetPage(buffer);
        childoffnum = gistchoose(indexrel, page, itup, giststate);
        iid = PageGetItemId(page, childoffnum);
        idxtuple = (IndexTuple) PageGetItem(page, iid);
        childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
 
        if (level > 1)
            gistMemorizeParent(buildstate, childblkno, blkno);
 
        /*
         * Check that the key representing the target child node is consistent
         * with the key we're inserting. Update it if it's not.
         */
        newtup = gistgetadjusted(indexrel, idxtuple, itup, giststate);
        if (newtup)
        {
            blkno = gistbufferinginserttuples(buildstate,
                                              buffer,
                                              level,
                                              &newtup,
                                              1,
                                              childoffnum,
                                              InvalidBlockNumber,
                                              InvalidOffsetNumber);
            /* gistbufferinginserttuples() released the buffer */
        }
        else
            UnlockReleaseBuffer(buffer);
 
        /* Descend to the child */
        parentblkno = blkno;
        blkno = childblkno;
        downlinkoffnum = childoffnum;
        Assert(level > 0);
        level--;
    }
 
    if (LEVEL_HAS_BUFFERS(level, gfbb))
    {
        /*
         * We've reached level with buffers. Place the index tuple to the
         * buffer, and add the buffer to the emptying queue if it overflows.
         */
        GISTNodeBuffer *childNodeBuffer;
 
        /* Find the buffer or create a new one */
        childNodeBuffer = gistGetNodeBuffer(gfbb, giststate, blkno, level);
 
        /* Add index tuple to it */
        gistPushItupToNodeBuffer(gfbb, childNodeBuffer, itup);
 
        if (BUFFER_OVERFLOWED(childNodeBuffer, gfbb))
            result = true;
    }
    else
    {
        /*
         * We've reached a leaf page. Place the tuple here.
         */
        Assert(level == 0);
        buffer = ReadBuffer(indexrel, blkno);
        LockBuffer(buffer, GIST_EXCLUSIVE);
        gistbufferinginserttuples(buildstate, buffer, level,
                                  &itup, 1, InvalidOffsetNumber,
                                  parentblkno, downlinkoffnum);
        /* gistbufferinginserttuples() released the buffer */
    }
 
    return result;
}

References Assert(), BUFFER_OVERFLOWED, BufferGetPage(), CHECK_FOR_INTERRUPTS, GISTBuildState::gfbb, GIST_EXCLUSIVE, gistbufferinginserttuples(), gistchoose(), gistgetadjusted(), gistGetNodeBuffer(), gistMemorizeParent(), gistPushItupToNodeBuffer(), GISTBuildState::giststate, GISTBuildState::indexrel, InvalidBlockNumber, InvalidOffsetNumber, ItemPointerGetBlockNumber(), LEVEL_HAS_BUFFERS, LockBuffer(), PageGetItem(), PageGetItemId(), ReadBuffer(), IndexTupleData::t_tid, and UnlockReleaseBuffer().

Referenced by gistBufferingBuildInsert(), and gistProcessEmptyingQueue().

gistSortedBuildCallback()

static void gistSortedBuildCallback ( Relation  index, ItemPointer  tid, Datum *  values, bool *  isnull, bool  tupleIsAlive, void *  state  )

static

Definition at line 370 of file gistbuild.c.

{
    GISTBuildState *buildstate = (GISTBuildState *) state;
    MemoryContext oldCtx;
    Datum       compressed_values[INDEX_MAX_KEYS];
 
    oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
 
    /* Form an index tuple and point it at the heap tuple */
    gistCompressValues(buildstate->giststate, index,
                       values, isnull,
                       true, compressed_values);
 
    tuplesort_putindextuplevalues(buildstate->sortstate,
                                  buildstate->indexrel,
                                  tid,
                                  compressed_values, isnull);
 
    MemoryContextSwitchTo(oldCtx);
    MemoryContextReset(buildstate->giststate->tempCxt);
 
    /* Update tuple count. */
    buildstate->indtuples += 1;
}

References gistCompressValues(), GISTBuildState::giststate, INDEX_MAX_KEYS, GISTBuildState::indexrel, GISTBuildState::indtuples, MemoryContextReset(), MemoryContextSwitchTo(), GISTBuildState::sortstate, GISTSTATE::tempCxt, tuplesort_putindextuplevalues(), and values.

Referenced by gistbuild().