gist_private.h File Reference

#include "access/amapi.h"
#include "access/gist.h"
#include "access/itup.h"
#include "lib/pairingheap.h"
#include "storage/bufmgr.h"
#include "storage/buffile.h"
#include "utils/hsearch.h"
#include "access/genam.h"

Include dependency graph for gist_private.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	GISTNodeBufferPage
struct	GISTSTATE
struct	GISTSearchHeapItem
struct	GISTSearchItem
struct	GISTScanOpaqueData
struct	gistxlogPage
struct	SplitedPageLayout
struct	GISTInsertStack
struct	GistSplitVector
struct	GISTInsertState
struct	GISTNodeBuffer
struct	GISTBuildBuffers
struct	GiSTOptions
struct	GISTPageSplitInfo

Macros
#define	GIST_MAX_SPLIT_PAGES   75
#define	GIST_SHARE   BUFFER_LOCK_SHARE
#define	GIST_EXCLUSIVE   BUFFER_LOCK_EXCLUSIVE
#define	GIST_UNLOCK   BUFFER_LOCK_UNLOCK
#define	BUFFER_PAGE_DATA_OFFSET   MAXALIGN(offsetof(GISTNodeBufferPage, tupledata))
#define	PAGE_FREE_SPACE(nbp)   (nbp->freespace)
#define	PAGE_IS_EMPTY(nbp)   (nbp->freespace == BLCKSZ - BUFFER_PAGE_DATA_OFFSET)
#define	PAGE_NO_SPACE(nbp, itup)
#define	GISTSearchItemIsHeap(item)   ((item).blkno == InvalidBlockNumber)
#define	SizeOfGISTSearchItem(n_distances)
#define	GIST_ROOT_BLKNO   0
#define	TUPLE_IS_VALID   0xffff
#define	TUPLE_IS_INVALID   0xfffe
#define	GistTupleIsInvalid(itup)   ( ItemPointerGetOffsetNumber( &((itup)->t_tid) ) == TUPLE_IS_INVALID )
#define	GistTupleSetValid(itup)   ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_VALID )
#define	LEVEL_HAS_BUFFERS(nlevel, gfbb)
#define	BUFFER_HALF_FILLED(nodeBuffer, gfbb)   ((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer / 2)
#define	BUFFER_OVERFLOWED(nodeBuffer, gfbb)   ((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer)
#define	GiSTPageSize   ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GISTPageOpaqueData)) )
#define	GIST_MIN_FILLFACTOR   10
#define	GIST_DEFAULT_FILLFACTOR   90

Typedefs
typedef struct GISTSTATE	GISTSTATE
typedef struct GISTSearchHeapItem	GISTSearchHeapItem
typedef struct GISTSearchItem	GISTSearchItem
typedef struct GISTScanOpaqueData	GISTScanOpaqueData
typedef GISTScanOpaqueData *	GISTScanOpaque
typedef struct gistxlogPage	gistxlogPage
typedef struct SplitedPageLayout	SplitedPageLayout
typedef struct GISTInsertStack	GISTInsertStack
typedef struct GistSplitVector	GistSplitVector
typedef struct GISTBuildBuffers	GISTBuildBuffers
typedef enum GistOptBufferingMode	GistOptBufferingMode
typedef struct GiSTOptions	GiSTOptions

Enumerations
enum	GistOptBufferingMode { GIST_OPTION_BUFFERING_AUTO, GIST_OPTION_BUFFERING_ON, GIST_OPTION_BUFFERING_OFF }

Functions
void	gistbuildempty (Relation index)
bool	gistinsert (Relation r, Datum *values, bool *isnull, ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique, bool indexUnchanged, struct IndexInfo *indexInfo)
MemoryContext	createTempGistContext (void)
GISTSTATE *	initGISTstate (Relation index)
void	freeGISTstate (GISTSTATE *giststate)
void	gistdoinsert (Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate, Relation heapRel, bool is_build)
bool	gistplacetopage (Relation rel, Size freespace, GISTSTATE *giststate, Buffer buffer, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, BlockNumber *newblkno, Buffer leftchildbuf, List **splitinfo, bool markfollowright, Relation heapRel, bool is_build)
SplitedPageLayout *	gistSplit (Relation r, Page page, IndexTuple *itup, int len, GISTSTATE *giststate)
XLogRecPtr	gistXLogPageDelete (Buffer buffer, FullTransactionId xid, Buffer parentBuffer, OffsetNumber downlinkOffset)
void	gistXLogPageReuse (Relation rel, BlockNumber blkno, FullTransactionId latestRemovedXid)
XLogRecPtr	gistXLogUpdate (Buffer buffer, OffsetNumber *todelete, int ntodelete, IndexTuple *itup, int ntup, Buffer leftchild)
XLogRecPtr	gistXLogDelete (Buffer buffer, OffsetNumber *todelete, int ntodelete, TransactionId latestRemovedXid)
XLogRecPtr	gistXLogSplit (bool page_is_leaf, SplitedPageLayout *dist, BlockNumber origrlink, GistNSN oldnsn, Buffer leftchild, bool markfollowright)
XLogRecPtr	gistXLogAssignLSN (void)
bool	gistgettuple (IndexScanDesc scan, ScanDirection dir)
int64	gistgetbitmap (IndexScanDesc scan, TIDBitmap *tbm)
bool	gistcanreturn (Relation index, int attno)
bool	gistvalidate (Oid opclassoid)
void	gistadjustmembers (Oid opfamilyoid, Oid opclassoid, List *operators, List *functions)
bytea *	gistoptions (Datum reloptions, bool validate)
bool	gistproperty (Oid index_oid, int attno, IndexAMProperty prop, const char *propname, bool *res, bool *isnull)
bool	gistfitpage (IndexTuple *itvec, int len)
bool	gistnospace (Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace)
void	gistcheckpage (Relation rel, Buffer buf)
Buffer	gistNewBuffer (Relation r)
bool	gistPageRecyclable (Page page)
void	gistfillbuffer (Page page, IndexTuple *itup, int len, OffsetNumber off)
IndexTuple *	gistextractpage (Page page, int *len)
IndexTuple *	gistjoinvector (IndexTuple *itvec, int *len, IndexTuple *additvec, int addlen)
IndexTupleData *	gistfillitupvec (IndexTuple *vec, int veclen, int *memlen)
IndexTuple	gistunion (Relation r, IndexTuple *itvec, int len, GISTSTATE *giststate)
IndexTuple	gistgetadjusted (Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *giststate)
IndexTuple	gistFormTuple (GISTSTATE *giststate, Relation r, Datum *attdata, bool *isnull, bool isleaf)
void	gistCompressValues (GISTSTATE *giststate, Relation r, Datum *attdata, bool *isnull, bool isleaf, Datum *compatt)
OffsetNumber	gistchoose (Relation r, Page p, IndexTuple it, GISTSTATE *giststate)
void	GISTInitBuffer (Buffer b, uint32 f)
void	gistinitpage (Page page, uint32 f)
void	gistdentryinit (GISTSTATE *giststate, int nkey, GISTENTRY *e, Datum k, Relation r, Page pg, OffsetNumber o, bool l, bool isNull)
float	gistpenalty (GISTSTATE *giststate, int attno, GISTENTRY *key1, bool isNull1, GISTENTRY *key2, bool isNull2)
void	gistMakeUnionItVec (GISTSTATE *giststate, IndexTuple *itvec, int len, Datum *attr, bool *isnull)
bool	gistKeyIsEQ (GISTSTATE *giststate, int attno, Datum a, Datum b)
void	gistDeCompressAtt (GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p, OffsetNumber o, GISTENTRY *attdata, bool *isnull)
HeapTuple	gistFetchTuple (GISTSTATE *giststate, Relation r, IndexTuple tuple)
void	gistMakeUnionKey (GISTSTATE *giststate, int attno, GISTENTRY *entry1, bool isnull1, GISTENTRY *entry2, bool isnull2, Datum *dst, bool *dstisnull)
XLogRecPtr	gistGetFakeLSN (Relation rel)
IndexBulkDeleteResult *	gistbulkdelete (IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, void *callback_state)
IndexBulkDeleteResult *	gistvacuumcleanup (IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
void	gistSplitByKey (Relation r, Page page, IndexTuple *itup, int len, GISTSTATE *giststate, GistSplitVector *v, int attno)
IndexBuildResult *	gistbuild (Relation heap, Relation index, struct IndexInfo *indexInfo)
void	gistValidateBufferingOption (const char *value)
GISTBuildBuffers *	gistInitBuildBuffers (int pagesPerBuffer, int levelStep, int maxLevel)
GISTNodeBuffer *	gistGetNodeBuffer (GISTBuildBuffers *gfbb, GISTSTATE *giststate, BlockNumber blkno, int level)
void	gistPushItupToNodeBuffer (GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer, IndexTuple item)
bool	gistPopItupFromNodeBuffer (GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer, IndexTuple *item)
void	gistFreeBuildBuffers (GISTBuildBuffers *gfbb)
void	gistRelocateBuildBuffersOnSplit (GISTBuildBuffers *gfbb, GISTSTATE *giststate, Relation r, int level, Buffer buffer, List *splitinfo)
void	gistUnloadNodeBuffers (GISTBuildBuffers *gfbb)

Macro Definition Documentation

BUFFER_HALF_FILLED

#define BUFFER_HALF_FILLED	(		nodeBuffer,
			gfbb
	)		((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer / 2)

Definition at line 324 of file gist_private.h.

Referenced by gistPushItupToNodeBuffer().

BUFFER_OVERFLOWED

#define BUFFER_OVERFLOWED	(		nodeBuffer,
			gfbb
	)		((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer)

Definition at line 332 of file gist_private.h.

Referenced by gistProcessItup().

BUFFER_PAGE_DATA_OFFSET

#define BUFFER_PAGE_DATA_OFFSET   MAXALIGN(offsetof(GISTNodeBufferPage, tupledata))

Definition at line 53 of file gist_private.h.

Referenced by gistAllocateNewPageBuffer(), gistGetItupFromPage(), and gistPlaceItupToPage().

GIST_DEFAULT_FILLFACTOR

#define GIST_DEFAULT_FILLFACTOR   90

Definition at line 479 of file gist_private.h.

Referenced by gistbuild().

GIST_EXCLUSIVE

#define GIST_EXCLUSIVE   BUFFER_LOCK_EXCLUSIVE

Definition at line 43 of file gist_private.h.

Referenced by gistBufferingFindCorrectParent(), gistdoinsert(), gistFindCorrectParent(), gistfinishsplit(), gistfixsplit(), gistformdownlink(), gistNewBuffer(), gistProcessItup(), gistvacuum_delete_empty_pages(), and gistvacuumpage().

GIST_MAX_SPLIT_PAGES

#define GIST_MAX_SPLIT_PAGES   75

Definition at line 39 of file gist_private.h.

Referenced by gistplacetopage().

GIST_MIN_FILLFACTOR

#define GIST_MIN_FILLFACTOR   10

Definition at line 478 of file gist_private.h.

GIST_ROOT_BLKNO

#define GIST_ROOT_BLKNO   0

Definition at line 262 of file gist_private.h.

Referenced by gist_indexsortbuild(), gistbufferinginserttuples(), gistbuild(), gistdoinsert(), gistFindPath(), gistgetbitmap(), gistGetMaxLevel(), gistgettuple(), gistplacetopage(), gistRedoPageSplitRecord(), gistRelocateBuildBuffersOnSplit(), gistvacuumscan(), and pgstat_relation().

GIST_SHARE

#define GIST_SHARE   BUFFER_LOCK_SHARE

Definition at line 42 of file gist_private.h.

Referenced by gistbufferinginserttuples(), gistdoinsert(), gistFindPath(), gistGetMaxLevel(), gistkillitems(), gistScanPage(), gistvacuum_delete_empty_pages(), and pgstat_gist_page().

GIST_UNLOCK

#define GIST_UNLOCK   BUFFER_LOCK_UNLOCK

Definition at line 44 of file gist_private.h.

Referenced by gistdoinsert(), gistformdownlink(), gistinserttuples(), gistNewBuffer(), and gistvacuum_delete_empty_pages().

GiSTPageSize

#define GiSTPageSize   ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GISTPageOpaqueData)) )

Definition at line 475 of file gist_private.h.

Referenced by gistfitpage(), and gistSplit().

GISTSearchItemIsHeap

#define GISTSearchItemIsHeap

(

item

)

((item).blkno == InvalidBlockNumber)

Definition at line 145 of file gist_private.h.

Referenced by getNextNearest(), gistScanPage(), and pairingheap_GISTSearchItem_cmp().

GistTupleIsInvalid

#define GistTupleIsInvalid

(

itup

)

( ItemPointerGetOffsetNumber( &((itup)->t_tid) ) == TUPLE_IS_INVALID )

Definition at line 288 of file gist_private.h.

Referenced by gistdoinsert(), gistindex_keytest(), and gistvacuumpage().

GistTupleSetValid

#define GistTupleSetValid

(

itup

)

ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_VALID )

Definition at line 289 of file gist_private.h.

Referenced by gistformdownlink(), and gistplacetopage().

LEVEL_HAS_BUFFERS

#define LEVEL_HAS_BUFFERS	(		nlevel,
			gfbb
	)

Value:

((nlevel) != 0 && (nlevel) % (gfbb)->levelStep == 0 && \
     (nlevel) != (gfbb)->rootlevel)

Definition at line 319 of file gist_private.h.

Referenced by gistProcessItup(), and gistRelocateBuildBuffersOnSplit().

PAGE_FREE_SPACE

#define PAGE_FREE_SPACE

(

nbp

)

(nbp->freespace)

Definition at line 55 of file gist_private.h.

Referenced by gistAllocateNewPageBuffer(), gistGetItupFromPage(), gistPlaceItupToPage(), and gistPushItupToNodeBuffer().

PAGE_IS_EMPTY

#define PAGE_IS_EMPTY

(

nbp

)

(nbp->freespace == BLCKSZ - BUFFER_PAGE_DATA_OFFSET)

Definition at line 57 of file gist_private.h.

Referenced by gistGetItupFromPage(), and gistPopItupFromNodeBuffer().

PAGE_NO_SPACE

#define PAGE_NO_SPACE	(		nbp,
			itup
	)

Value:

(PAGE_FREE_SPACE(nbp) < \
                                        MAXALIGN(IndexTupleSize(itup)))

Definition at line 59 of file gist_private.h.

Referenced by gistPushItupToNodeBuffer().

SizeOfGISTSearchItem

#define SizeOfGISTSearchItem

(

n_distances

)

Value:

(offsetof(GISTSearchItem, distances) + \
     sizeof(IndexOrderByDistance) * (n_distances))

Definition at line 147 of file gist_private.h.

Referenced by gistScanPage().

TUPLE_IS_INVALID

#define TUPLE_IS_INVALID   0xfffe

Definition at line 286 of file gist_private.h.

TUPLE_IS_VALID

#define TUPLE_IS_VALID   0xffff

Definition at line 285 of file gist_private.h.

Typedef Documentation

GISTBuildBuffers

typedef struct GISTBuildBuffers GISTBuildBuffers

GISTInsertStack

typedef struct GISTInsertStack GISTInsertStack

GistOptBufferingMode

typedef enum GistOptBufferingMode GistOptBufferingMode

GiSTOptions

typedef struct GiSTOptions GiSTOptions

GISTScanOpaque

typedef GISTScanOpaqueData* GISTScanOpaque

Definition at line 181 of file gist_private.h.

GISTScanOpaqueData

typedef struct GISTScanOpaqueData GISTScanOpaqueData

GISTSearchHeapItem

typedef struct GISTSearchHeapItem GISTSearchHeapItem

GISTSearchItem

typedef struct GISTSearchItem GISTSearchItem

GistSplitVector

typedef struct GistSplitVector GistSplitVector

GISTSTATE

typedef struct GISTSTATE GISTSTATE

gistxlogPage

typedef struct gistxlogPage gistxlogPage

SplitedPageLayout

typedef struct SplitedPageLayout SplitedPageLayout

Enumeration Type Documentation

GistOptBufferingMode

enum GistOptBufferingMode

Enumerator
GIST_OPTION_BUFFERING_AUTO
GIST_OPTION_BUFFERING_ON
GIST_OPTION_BUFFERING_OFF

Definition at line 384 of file gist_private.h.

{
    GIST_OPTION_BUFFERING_AUTO,
    GIST_OPTION_BUFFERING_ON,
    GIST_OPTION_BUFFERING_OFF
} GistOptBufferingMode;

Function Documentation

createTempGistContext()

MemoryContext createTempGistContext

(

void

)

Definition at line 119 of file gist.c.

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, and CurrentMemoryContext.

Referenced by gist_xlog_startup(), gistbeginscan(), gistbuild(), and gistinsert().

{
    return AllocSetContextCreate(CurrentMemoryContext,
                                 "GiST temporary context",
                                 ALLOCSET_DEFAULT_SIZES);
}

freeGISTstate()

void freeGISTstate

(

GISTSTATE *

giststate

)

Definition at line 1631 of file gist.c.

References MemoryContextDelete(), and GISTSTATE::scanCxt.

Referenced by gistbuild(), and gistendscan().

{
    /* It's sufficient to delete the scanCxt */
    MemoryContextDelete(giststate->scanCxt);
}

gistadjustmembers()

void gistadjustmembers	(	Oid	opfamilyoid,
		Oid	opclassoid,
		List *	operators,
		List *	functions
	)

Definition at line 291 of file gistvalidate.c.

References ereport, errcode(), errmsg(), ERROR, GIST_COMPRESS_PROC, GIST_CONSISTENT_PROC, GIST_DECOMPRESS_PROC, GIST_DISTANCE_PROC, GIST_EQUAL_PROC, GIST_FETCH_PROC, GIST_OPTIONS_PROC, GIST_PENALTY_PROC, GIST_PICKSPLIT_PROC, GIST_SORTSUPPORT_PROC, GIST_UNION_PROC, lfirst, OpFamilyMember::number, OpFamilyMember::ref_is_family, OpFamilyMember::ref_is_hard, and OpFamilyMember::refobjid.

Referenced by gisthandler().

{
    ListCell   *lc;

    /*
     * Operator members of a GiST opfamily should never have hard
     * dependencies, since their connection to the opfamily depends only on
     * what the support functions think, and that can be altered.  For
     * consistency, we make all soft dependencies point to the opfamily,
     * though a soft dependency on the opclass would work as well in the
     * CREATE OPERATOR CLASS case.
     */
    foreach(lc, operators)
    {
        OpFamilyMember *op = (OpFamilyMember *) lfirst(lc);

        op->ref_is_hard = false;
        op->ref_is_family = true;
        op->refobjid = opfamilyoid;
    }

    /*
     * Required support functions should have hard dependencies.  Preferably
     * those are just dependencies on the opclass, but if we're in ALTER
     * OPERATOR FAMILY, we leave the dependency pointing at the whole
     * opfamily.  (Given that GiST opclasses generally don't share opfamilies,
     * it seems unlikely to be worth working harder.)
     */
    foreach(lc, functions)
    {
        OpFamilyMember *op = (OpFamilyMember *) lfirst(lc);

        switch (op->number)
        {
            case GIST_CONSISTENT_PROC:
            case GIST_UNION_PROC:
            case GIST_PENALTY_PROC:
            case GIST_PICKSPLIT_PROC:
            case GIST_EQUAL_PROC:
                /* Required support function */
                op->ref_is_hard = true;
                break;
            case GIST_COMPRESS_PROC:
            case GIST_DECOMPRESS_PROC:
            case GIST_DISTANCE_PROC:
            case GIST_FETCH_PROC:
            case GIST_OPTIONS_PROC:
            case GIST_SORTSUPPORT_PROC:
                /* Optional, so force it to be a soft family dependency */
                op->ref_is_hard = false;
                op->ref_is_family = true;
                op->refobjid = opfamilyoid;
                break;
            default:
                ereport(ERROR,
                        (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
                         errmsg("support function number %d is invalid for access method %s",
                                op->number, "gist")));
                break;
        }
    }
}

gistbuild()

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

Definition at line 175 of file gistbuild.c.

References Assert, BufferGetBlockNumber(), BufferGetPage, GiSTOptions::buffering_mode, GISTBuildState::buildMode, createTempGistContext(), CurrentMemoryContext, DEBUG1, elog, END_CRIT_SECTION, ERROR, F_LEAF, fillfactor, GiSTOptions::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, 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, GistSortedBuildPageState::page, PageSetLSN, palloc(), RelationData::rd_options, RelationGetNumberOfBlocks, RelationGetRelationName, RelationNeedsWAL, GISTBuildState::sortstate, START_CRIT_SECTION, table_index_build_scan(), GISTSTATE::tempCxt, tuplesort_begin_index_gist(), tuplesort_end(), tuplesort_performsort(), and UnlockReleaseBuffer().

Referenced by gisthandler().

{
    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,
                                                          false);

        /* 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);
        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;
}

gistbuildempty()

void gistbuildempty

(

Relation

index

)

Definition at line 130 of file gist.c.

References BUFFER_LOCK_EXCLUSIVE, END_CRIT_SECTION, F_LEAF, GISTInitBuffer(), INIT_FORKNUM, LockBuffer(), log_newpage_buffer(), MarkBufferDirty(), P_NEW, RBM_NORMAL, ReadBufferExtended(), START_CRIT_SECTION, and UnlockReleaseBuffer().

Referenced by gisthandler().

{
    Buffer      buffer;

    /* Initialize the root page */
    buffer = ReadBufferExtended(index, INIT_FORKNUM, P_NEW, RBM_NORMAL, NULL);
    LockBuffer(buffer, BUFFER_LOCK_EXCLUSIVE);

    /* Initialize and xlog buffer */
    START_CRIT_SECTION();
    GISTInitBuffer(buffer, F_LEAF);
    MarkBufferDirty(buffer);
    log_newpage_buffer(buffer, true);
    END_CRIT_SECTION();

    /* Unlock and release the buffer */
    UnlockReleaseBuffer(buffer);
}

gistbulkdelete()

IndexBulkDeleteResult* gistbulkdelete	(	IndexVacuumInfo *	info,
		IndexBulkDeleteResult *	stats,
		IndexBulkDeleteCallback	callback,
		void *	callback_state
	)

Definition at line 59 of file gistvacuum.c.

References gistvacuumscan(), and palloc0().

Referenced by gisthandler().

{
    /* allocate stats if first time through, else re-use existing struct */
    if (stats == NULL)
        stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));

    gistvacuumscan(info, stats, callback, callback_state);

    return stats;
}

gistcanreturn()

bool gistcanreturn	(	Relation	index,
		int	attno
	)

Definition at line 795 of file gistget.c.

References GIST_COMPRESS_PROC, GIST_FETCH_PROC, index_getprocid(), IndexRelationGetNumberOfKeyAttributes, and OidIsValid.

Referenced by gisthandler().

{
    if (attno > IndexRelationGetNumberOfKeyAttributes(index) ||
        OidIsValid(index_getprocid(index, attno, GIST_FETCH_PROC)) ||
        !OidIsValid(index_getprocid(index, attno, GIST_COMPRESS_PROC)))
        return true;
    else
        return false;
}

gistcheckpage()

void gistcheckpage	(	Relation	rel,
		Buffer	buf
	)

Definition at line 784 of file gistutil.c.

References BufferGetBlockNumber(), BufferGetPage, ereport, errcode(), errhint(), errmsg(), ERROR, MAXALIGN, GistSortedBuildPageState::page, PageGetSpecialSize, PageIsNew, and RelationGetRelationName.

Referenced by gistBufferingFindCorrectParent(), gistdoinsert(), gistFindCorrectParent(), gistFindPath(), gistkillitems(), gistNewBuffer(), gistScanPage(), gistvacuum_delete_empty_pages(), and pgstat_gist_page().

{
    Page        page = BufferGetPage(buf);

    /*
     * ReadBuffer verifies that every newly-read page passes
     * PageHeaderIsValid, which means it either contains a reasonably sane
     * page header or is all-zero.  We have to defend against the all-zero
     * case, however.
     */
    if (PageIsNew(page))
        ereport(ERROR,
                (errcode(ERRCODE_INDEX_CORRUPTED),
                 errmsg("index \"%s\" contains unexpected zero page at block %u",
                        RelationGetRelationName(rel),
                        BufferGetBlockNumber(buf)),
                 errhint("Please REINDEX it.")));

    /*
     * Additionally check that the special area looks sane.
     */
    if (PageGetSpecialSize(page) != MAXALIGN(sizeof(GISTPageOpaqueData)))
        ereport(ERROR,
                (errcode(ERRCODE_INDEX_CORRUPTED),
                 errmsg("index \"%s\" contains corrupted page at block %u",
                        RelationGetRelationName(rel),
                        BufferGetBlockNumber(buf)),
                 errhint("Please REINDEX it.")));
}

gistchoose()

OffsetNumber gistchoose	(	Relation	r,
		Page	p,
		IndexTuple	it,
		GISTSTATE *	giststate
	)

Definition at line 373 of file gistutil.c.

References Assert, FirstOffsetNumber, gistDeCompressAtt(), gistdentryinit(), GistPageIsLeaf, gistpenalty(), i, index_getattr, INDEX_MAX_KEYS, IndexRelationGetNumberOfKeyAttributes, GISTSTATE::leafTupdesc, MAX_RANDOM_VALUE, OffsetNumberNext, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, and random().

Referenced by gistdoinsert(), and gistProcessItup().

{
    OffsetNumber result;
    OffsetNumber maxoff;
    OffsetNumber i;
    float       best_penalty[INDEX_MAX_KEYS];
    GISTENTRY   entry,
                identry[INDEX_MAX_KEYS];
    bool        isnull[INDEX_MAX_KEYS];
    int         keep_current_best;

    Assert(!GistPageIsLeaf(p));

    gistDeCompressAtt(giststate, r,
                      it, NULL, (OffsetNumber) 0,
                      identry, isnull);

    /* we'll return FirstOffsetNumber if page is empty (shouldn't happen) */
    result = FirstOffsetNumber;

    /*
     * The index may have multiple columns, and there's a penalty value for
     * each column.  The penalty associated with a column that appears earlier
     * in the index definition is strictly more important than the penalty of
     * a column that appears later in the index definition.
     *
     * best_penalty[j] is the best penalty we have seen so far for column j,
     * or -1 when we haven't yet examined column j.  Array entries to the
     * right of the first -1 are undefined.
     */
    best_penalty[0] = -1;

    /*
     * If we find a tuple that's exactly as good as the currently best one, we
     * could use either one.  When inserting a lot of tuples with the same or
     * similar keys, it's preferable to descend down the same path when
     * possible, as that's more cache-friendly.  On the other hand, if all
     * inserts land on the same leaf page after a split, we're never going to
     * insert anything to the other half of the split, and will end up using
     * only 50% of the available space.  Distributing the inserts evenly would
     * lead to better space usage, but that hurts cache-locality during
     * insertion.  To get the best of both worlds, when we find a tuple that's
     * exactly as good as the previous best, choose randomly whether to stick
     * to the old best, or use the new one.  Once we decide to stick to the
     * old best, we keep sticking to it for any subsequent equally good tuples
     * we might find.  This favors tuples with low offsets, but still allows
     * some inserts to go to other equally-good subtrees.
     *
     * keep_current_best is -1 if we haven't yet had to make a random choice
     * whether to keep the current best tuple.  If we have done so, and
     * decided to keep it, keep_current_best is 1; if we've decided to
     * replace, keep_current_best is 0.  (This state will be reset to -1 as
     * soon as we've made the replacement, but sometimes we make the choice in
     * advance of actually finding a replacement best tuple.)
     */
    keep_current_best = -1;

    /*
     * Loop over tuples on page.
     */
    maxoff = PageGetMaxOffsetNumber(p);
    Assert(maxoff >= FirstOffsetNumber);

    for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
    {
        IndexTuple  itup = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
        bool        zero_penalty;
        int         j;

        zero_penalty = true;

        /* Loop over index attributes. */
        for (j = 0; j < IndexRelationGetNumberOfKeyAttributes(r); j++)
        {
            Datum       datum;
            float       usize;
            bool        IsNull;

            /* Compute penalty for this column. */
            datum = index_getattr(itup, j + 1, giststate->leafTupdesc,
                                  &IsNull);
            gistdentryinit(giststate, j, &entry, datum, r, p, i,
                           false, IsNull);
            usize = gistpenalty(giststate, j, &entry, IsNull,
                                &identry[j], isnull[j]);
            if (usize > 0)
                zero_penalty = false;

            if (best_penalty[j] < 0 || usize < best_penalty[j])
            {
                /*
                 * New best penalty for column.  Tentatively select this tuple
                 * as the target, and record the best penalty.  Then reset the
                 * next column's penalty to "unknown" (and indirectly, the
                 * same for all the ones to its right).  This will force us to
                 * adopt this tuple's penalty values as the best for all the
                 * remaining columns during subsequent loop iterations.
                 */
                result = i;
                best_penalty[j] = usize;

                if (j < IndexRelationGetNumberOfKeyAttributes(r) - 1)
                    best_penalty[j + 1] = -1;

                /* we have new best, so reset keep-it decision */
                keep_current_best = -1;
            }
            else if (best_penalty[j] == usize)
            {
                /*
                 * The current tuple is exactly as good for this column as the
                 * best tuple seen so far.  The next iteration of this loop
                 * will compare the next column.
                 */
            }
            else
            {
                /*
                 * The current tuple is worse for this column than the best
                 * tuple seen so far.  Skip the remaining columns and move on
                 * to the next tuple, if any.
                 */
                zero_penalty = false;   /* so outer loop won't exit */
                break;
            }
        }

        /*
         * If we looped past the last column, and did not update "result",
         * then this tuple is exactly as good as the prior best tuple.
         */
        if (j == IndexRelationGetNumberOfKeyAttributes(r) && result != i)
        {
            if (keep_current_best == -1)
            {
                /* we didn't make the random choice yet for this old best */
                keep_current_best = (random() <= (MAX_RANDOM_VALUE / 2)) ? 1 : 0;
            }
            if (keep_current_best == 0)
            {
                /* we choose to use the new tuple */
                result = i;
                /* choose again if there are even more exactly-as-good ones */
                keep_current_best = -1;
            }
        }

        /*
         * If we find a tuple with zero penalty for all columns, and we've
         * decided we don't want to search for another tuple with equal
         * penalty, there's no need to examine remaining tuples; just break
         * out of the loop and return it.
         */
        if (zero_penalty)
        {
            if (keep_current_best == -1)
            {
                /* we didn't make the random choice yet for this old best */
                keep_current_best = (random() <= (MAX_RANDOM_VALUE / 2)) ? 1 : 0;
            }
            if (keep_current_best == 1)
                break;
        }
    }

    return result;
}

gistCompressValues()

void gistCompressValues	(	GISTSTATE *	giststate,
		Relation	r,
		Datum *	attdata,
		bool *	isnull,
		bool	isleaf,
		Datum *	compatt
	)

Definition at line 595 of file gistutil.c.

References GISTSTATE::compressFn, DatumGetPointer, FmgrInfo::fn_oid, FunctionCall1Coll(), gistentryinit, i, IndexRelationGetNumberOfKeyAttributes, GISTENTRY::key, TupleDescData::natts, OidIsValid, PointerGetDatum, RelationData::rd_att, and GISTSTATE::supportCollation.

Referenced by gistFormTuple(), and gistSortedBuildCallback().

{
    int         i;

    /*
     * Call the compress method on each attribute.
     */
    for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(r); i++)
    {
        if (isnull[i])
            compatt[i] = (Datum) 0;
        else
        {
            GISTENTRY   centry;
            GISTENTRY  *cep;

            gistentryinit(centry, attdata[i], r, NULL, (OffsetNumber) 0,
                          isleaf);
            /* there may not be a compress function in opclass */
            if (OidIsValid(giststate->compressFn[i].fn_oid))
                cep = (GISTENTRY *)
                    DatumGetPointer(FunctionCall1Coll(&giststate->compressFn[i],
                                                      giststate->supportCollation[i],
                                                      PointerGetDatum(&centry)));
            else
                cep = &centry;
            compatt[i] = cep->key;
        }
    }

    if (isleaf)
    {
        /*
         * Emplace each included attribute if any.
         */
        for (; i < r->rd_att->natts; i++)
        {
            if (isnull[i])
                compatt[i] = (Datum) 0;
            else
                compatt[i] = attdata[i];
        }
    }
}

gistDeCompressAtt()

void gistDeCompressAtt	(	GISTSTATE *	giststate,
		Relation	r,
		IndexTuple	tuple,
		Page	p,
		OffsetNumber	o,
		GISTENTRY *	attdata,
		bool *	isnull
	)

Definition at line 295 of file gistutil.c.

References gistdentryinit(), i, index_getattr, IndexRelationGetNumberOfKeyAttributes, and GISTSTATE::leafTupdesc.

Referenced by gistchoose(), gistgetadjusted(), gistRelocateBuildBuffersOnSplit(), and placeOne().

{
    int         i;

    for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(r); i++)
    {
        Datum       datum;

        datum = index_getattr(tuple, i + 1, giststate->leafTupdesc, &isnull[i]);
        gistdentryinit(giststate, i, &attdata[i],
                       datum, r, p, o,
                       false, isnull[i]);
    }
}

gistdentryinit()

void gistdentryinit	(	GISTSTATE *	giststate,
		int	nkey,
		GISTENTRY *	e,
		Datum	k,
		Relation	r,
		Page	pg,
		OffsetNumber	o,
		bool	l,
		bool	isNull
	)

Definition at line 546 of file gistutil.c.

References DatumGetPointer, GISTSTATE::decompressFn, FmgrInfo::fn_oid, FunctionCall1Coll(), gistentryinit, GISTENTRY::key, GISTENTRY::leafkey, GISTENTRY::offset, OidIsValid, GISTENTRY::page, PointerGetDatum, GISTENTRY::rel, and GISTSTATE::supportCollation.

Referenced by gistchoose(), gistDeCompressAtt(), gistindex_keytest(), gistMakeUnionItVec(), and gistSplitByKey().

{
    if (!isNull)
    {
        GISTENTRY  *dep;

        gistentryinit(*e, k, r, pg, o, l);

        /* there may not be a decompress function in opclass */
        if (!OidIsValid(giststate->decompressFn[nkey].fn_oid))
            return;

        dep = (GISTENTRY *)
            DatumGetPointer(FunctionCall1Coll(&giststate->decompressFn[nkey],
                                              giststate->supportCollation[nkey],
                                              PointerGetDatum(e)));
        /* decompressFn may just return the given pointer */
        if (dep != e)
            gistentryinit(*e, dep->key, dep->rel, dep->page, dep->offset,
                          dep->leafkey);
    }
    else
        gistentryinit(*e, (Datum) 0, r, pg, o, l);
}

gistdoinsert()

void gistdoinsert	(	Relation	r,
		IndexTuple	itup,
		Size	freespace,
		GISTSTATE *	giststate,
		Relation	heapRel,
		bool	is_build
	)

Definition at line 632 of file gist.c.

References Assert, GISTInsertStack::blkno, GISTInsertStack::buffer, BufferGetLSNAtomic(), BufferGetPage, GISTInsertStack::downlinkoffnum, ereport, errdetail(), errhint(), errmsg(), ERROR, GISTInsertState::freespace, GIST_EXCLUSIVE, GIST_ROOT_BLKNO, GIST_SHARE, GIST_UNLOCK, gistcheckpage(), gistchoose(), gistfixsplit(), GistFollowRight, gistgetadjusted(), gistinserttuple(), GistPageGetNSN, GistPageIsDeleted, GistPageIsLeaf, GistTupleIsInvalid, GISTInsertState::heapRel, InvalidOffsetNumber, GISTInsertState::is_build, ItemPointerGetBlockNumber, LockBuffer(), GISTInsertStack::lsn, GISTInsertStack::page, PageGetItem, PageGetItemId, PageGetLSN, palloc0(), GISTInsertStack::parent, GISTInsertState::r, ReadBuffer(), RelationGetRelationName, RelationNeedsWAL, ReleaseBuffer(), GISTInsertStack::retry_from_parent, GISTInsertState::stack, IndexTupleData::t_tid, UnlockReleaseBuffer(), and XLogRecPtrIsInvalid.

Referenced by gistBuildCallback(), and gistinsert().

{
    ItemId      iid;
    IndexTuple  idxtuple;
    GISTInsertStack firststack;
    GISTInsertStack *stack;
    GISTInsertState state;
    bool        xlocked = false;

    memset(&state, 0, sizeof(GISTInsertState));
    state.freespace = freespace;
    state.r = r;
    state.heapRel = heapRel;
    state.is_build = is_build;

    /* Start from the root */
    firststack.blkno = GIST_ROOT_BLKNO;
    firststack.lsn = 0;
    firststack.retry_from_parent = false;
    firststack.parent = NULL;
    firststack.downlinkoffnum = InvalidOffsetNumber;
    state.stack = stack = &firststack;

    /*
     * Walk down along the path of smallest penalty, updating the parent
     * pointers with the key we're inserting as we go. If we crash in the
     * middle, the tree is consistent, although the possible parent updates
     * were a waste.
     */
    for (;;)
    {
        /*
         * If we split an internal page while descending the tree, we have to
         * retry at the parent. (Normally, the LSN-NSN interlock below would
         * also catch this and cause us to retry. But LSNs are not updated
         * during index build.)
         */
        while (stack->retry_from_parent)
        {
            if (xlocked)
                LockBuffer(stack->buffer, GIST_UNLOCK);
            xlocked = false;
            ReleaseBuffer(stack->buffer);
            state.stack = stack = stack->parent;
        }

        if (XLogRecPtrIsInvalid(stack->lsn))
            stack->buffer = ReadBuffer(state.r, stack->blkno);

        /*
         * Be optimistic and grab shared lock first. Swap it for an exclusive
         * lock later if we need to update the page.
         */
        if (!xlocked)
        {
            LockBuffer(stack->buffer, GIST_SHARE);
            gistcheckpage(state.r, stack->buffer);
        }

        stack->page = (Page) BufferGetPage(stack->buffer);
        stack->lsn = xlocked ?
            PageGetLSN(stack->page) : BufferGetLSNAtomic(stack->buffer);
        Assert(!RelationNeedsWAL(state.r) || !XLogRecPtrIsInvalid(stack->lsn));

        /*
         * If this page was split but the downlink was never inserted to the
         * parent because the inserting backend crashed before doing that, fix
         * that now.
         */
        if (GistFollowRight(stack->page))
        {
            if (!xlocked)
            {
                LockBuffer(stack->buffer, GIST_UNLOCK);
                LockBuffer(stack->buffer, GIST_EXCLUSIVE);
                xlocked = true;
                /* someone might've completed the split when we unlocked */
                if (!GistFollowRight(stack->page))
                    continue;
            }
            gistfixsplit(&state, giststate);

            UnlockReleaseBuffer(stack->buffer);
            xlocked = false;
            state.stack = stack = stack->parent;
            continue;
        }

        if ((stack->blkno != GIST_ROOT_BLKNO &&
             stack->parent->lsn < GistPageGetNSN(stack->page)) ||
            GistPageIsDeleted(stack->page))
        {
            /*
             * Concurrent split or page deletion detected. There's no
             * guarantee that the downlink for this page is consistent with
             * the tuple we're inserting anymore, so go back to parent and
             * rechoose the best child.
             */
            UnlockReleaseBuffer(stack->buffer);
            xlocked = false;
            state.stack = stack = stack->parent;
            continue;
        }

        if (!GistPageIsLeaf(stack->page))
        {
            /*
             * This is an internal page so continue to walk down the tree.
             * Find the child node that has the minimum insertion penalty.
             */
            BlockNumber childblkno;
            IndexTuple  newtup;
            GISTInsertStack *item;
            OffsetNumber downlinkoffnum;

            downlinkoffnum = gistchoose(state.r, stack->page, itup, giststate);
            iid = PageGetItemId(stack->page, downlinkoffnum);
            idxtuple = (IndexTuple) PageGetItem(stack->page, iid);
            childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));

            /*
             * Check that it's not a leftover invalid tuple from pre-9.1
             */
            if (GistTupleIsInvalid(idxtuple))
                ereport(ERROR,
                        (errmsg("index \"%s\" contains an inner tuple marked as invalid",
                                RelationGetRelationName(r)),
                         errdetail("This is caused by an incomplete page split at crash recovery before upgrading to PostgreSQL 9.1."),
                         errhint("Please REINDEX it.")));

            /*
             * 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(state.r, idxtuple, itup, giststate);
            if (newtup)
            {
                /*
                 * Swap shared lock for an exclusive one. Beware, the page may
                 * change while we unlock/lock the page...
                 */
                if (!xlocked)
                {
                    LockBuffer(stack->buffer, GIST_UNLOCK);
                    LockBuffer(stack->buffer, GIST_EXCLUSIVE);
                    xlocked = true;
                    stack->page = (Page) BufferGetPage(stack->buffer);

                    if (PageGetLSN(stack->page) != stack->lsn)
                    {
                        /* the page was changed while we unlocked it, retry */
                        continue;
                    }
                }

                /*
                 * Update the tuple.
                 *
                 * We still hold the lock after gistinserttuple(), but it
                 * might have to split the page to make the updated tuple fit.
                 * In that case the updated tuple might migrate to the other
                 * half of the split, so we have to go back to the parent and
                 * descend back to the half that's a better fit for the new
                 * tuple.
                 */
                if (gistinserttuple(&state, stack, giststate, newtup,
                                    downlinkoffnum))
                {
                    /*
                     * If this was a root split, the root page continues to be
                     * the parent and the updated tuple went to one of the
                     * child pages, so we just need to retry from the root
                     * page.
                     */
                    if (stack->blkno != GIST_ROOT_BLKNO)
                    {
                        UnlockReleaseBuffer(stack->buffer);
                        xlocked = false;
                        state.stack = stack = stack->parent;
                    }
                    continue;
                }
            }
            LockBuffer(stack->buffer, GIST_UNLOCK);
            xlocked = false;

            /* descend to the chosen child */
            item = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
            item->blkno = childblkno;
            item->parent = stack;
            item->downlinkoffnum = downlinkoffnum;
            state.stack = stack = item;
        }
        else
        {
            /*
             * Leaf page. Insert the new key. We've already updated all the
             * parents on the way down, but we might have to split the page if
             * it doesn't fit. gistinserttuple() will take care of that.
             */

            /*
             * Swap shared lock for an exclusive one. Be careful, the page may
             * change while we unlock/lock the page...
             */
            if (!xlocked)
            {
                LockBuffer(stack->buffer, GIST_UNLOCK);
                LockBuffer(stack->buffer, GIST_EXCLUSIVE);
                xlocked = true;
                stack->page = (Page) BufferGetPage(stack->buffer);
                stack->lsn = PageGetLSN(stack->page);

                if (stack->blkno == GIST_ROOT_BLKNO)
                {
                    /*
                     * the only page that can become inner instead of leaf is
                     * the root page, so for root we should recheck it
                     */
                    if (!GistPageIsLeaf(stack->page))
                    {
                        /*
                         * very rare situation: during unlock/lock index with
                         * number of pages = 1 was increased
                         */
                        LockBuffer(stack->buffer, GIST_UNLOCK);
                        xlocked = false;
                        continue;
                    }

                    /*
                     * we don't need to check root split, because checking
                     * leaf/inner is enough to recognize split for root
                     */
                }
                else if ((GistFollowRight(stack->page) ||
                          stack->parent->lsn < GistPageGetNSN(stack->page)) ||
                         GistPageIsDeleted(stack->page))
                {
                    /*
                     * The page was split or deleted while we momentarily
                     * unlocked the page. Go back to parent.
                     */
                    UnlockReleaseBuffer(stack->buffer);
                    xlocked = false;
                    state.stack = stack = stack->parent;
                    continue;
                }
            }

            /* now state.stack->(page, buffer and blkno) points to leaf page */

            gistinserttuple(&state, stack, giststate, itup,
                            InvalidOffsetNumber);
            LockBuffer(stack->buffer, GIST_UNLOCK);

            /* Release any pins we might still hold before exiting */
            for (; stack; stack = stack->parent)
                ReleaseBuffer(stack->buffer);
            break;
        }
    }
}

gistextractpage()

IndexTuple* gistextractpage	(	Page	page,
		int *	len
	)

Definition at line 94 of file gistutil.c.

References FirstOffsetNumber, i, OffsetNumberNext, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, and palloc().

Referenced by gist_indexsortbuild_pagestate_flush(), and gistplacetopage().

{
    OffsetNumber i,
                maxoff;
    IndexTuple *itvec;

    maxoff = PageGetMaxOffsetNumber(page);
    *len = maxoff;
    itvec = palloc(sizeof(IndexTuple) * maxoff);
    for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
        itvec[i - FirstOffsetNumber] = (IndexTuple) PageGetItem(page, PageGetItemId(page, i));

    return itvec;
}

gistFetchTuple()

HeapTuple gistFetchTuple	(	GISTSTATE *	giststate,
		Relation	r,
		IndexTuple	tuple
	)

Definition at line 666 of file gistutil.c.

References GISTSTATE::compressFn, fetchatt, GISTSTATE::fetchFn, GISTSTATE::fetchTupdesc, FmgrInfo::fn_oid, gistFetchAtt(), heap_form_tuple(), i, index_getattr, INDEX_MAX_KEYS, IndexRelationGetNumberOfKeyAttributes, InvalidOid, GISTSTATE::leafTupdesc, MemoryContextSwitchTo(), TupleDescData::natts, RelationData::rd_att, and GISTSTATE::tempCxt.

Referenced by gistScanPage().

{
    MemoryContext oldcxt = MemoryContextSwitchTo(giststate->tempCxt);
    Datum       fetchatt[INDEX_MAX_KEYS];
    bool        isnull[INDEX_MAX_KEYS];
    int         i;

    for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(r); i++)
    {
        Datum       datum;

        datum = index_getattr(tuple, i + 1, giststate->leafTupdesc, &isnull[i]);

        if (giststate->fetchFn[i].fn_oid != InvalidOid)
        {
            if (!isnull[i])
                fetchatt[i] = gistFetchAtt(giststate, i, datum, r);
            else
                fetchatt[i] = (Datum) 0;
        }
        else if (giststate->compressFn[i].fn_oid == InvalidOid)
        {
            /*
             * If opclass does not provide compress method that could change
             * original value, att is necessarily stored in original form.
             */
            if (!isnull[i])
                fetchatt[i] = datum;
            else
                fetchatt[i] = (Datum) 0;
        }
        else
        {
            /*
             * Index-only scans not supported for this column. Since the
             * planner chose an index-only scan anyway, it is not interested
             * in this column, and we can replace it with a NULL.
             */
            isnull[i] = true;
            fetchatt[i] = (Datum) 0;
        }
    }

    /*
     * Get each included attribute.
     */
    for (; i < r->rd_att->natts; i++)
    {
        fetchatt[i] = index_getattr(tuple, i + 1, giststate->leafTupdesc,
                                    &isnull[i]);
    }
    MemoryContextSwitchTo(oldcxt);

    return heap_form_tuple(giststate->fetchTupdesc, fetchatt, isnull);
}

gistfillbuffer()

void gistfillbuffer	(	Page	page,
		IndexTuple *	itup,
		int	len,
		OffsetNumber	off
	)

Definition at line 33 of file gistutil.c.

References elog, ERROR, FirstOffsetNumber, i, IndexTupleSize, InvalidOffsetNumber, OffsetNumberNext, PageAddItem, PageGetMaxOffsetNumber, and PageIsEmpty.

Referenced by gist_indexsortbuild_pagestate_add(), gistplacetopage(), and gistRedoPageSplitRecord().

{
    int         i;

    if (off == InvalidOffsetNumber)
        off = (PageIsEmpty(page)) ? FirstOffsetNumber :
            OffsetNumberNext(PageGetMaxOffsetNumber(page));

    for (i = 0; i < len; i++)
    {
        Size        sz = IndexTupleSize(itup[i]);
        OffsetNumber l;

        l = PageAddItem(page, (Item) itup[i], sz, off, false, false);
        if (l == InvalidOffsetNumber)
            elog(ERROR, "failed to add item to GiST index page, item %d out of %d, size %d bytes",
                 i, len, (int) sz);
        off++;
    }
}

gistfillitupvec()

IndexTupleData* gistfillitupvec	(	IndexTuple *	vec,
		int	veclen,
		int *	memlen
	)

Definition at line 126 of file gistutil.c.

References i, IndexTupleSize, and palloc().

Referenced by gistplacetopage(), and gistSplit().

{
    char       *ptr,
               *ret;
    int         i;

    *memlen = 0;

    for (i = 0; i < veclen; i++)
        *memlen += IndexTupleSize(vec[i]);

    ptr = ret = palloc(*memlen);

    for (i = 0; i < veclen; i++)
    {
        memcpy(ptr, vec[i], IndexTupleSize(vec[i]));
        ptr += IndexTupleSize(vec[i]);
    }

    return (IndexTupleData *) ret;
}

gistfitpage()

bool gistfitpage	(	IndexTuple *	itvec,
		int	len
	)

Definition at line 78 of file gistutil.c.

References GiSTPageSize, i, and IndexTupleSize.

Referenced by gistSplit().

{
    int         i;
    Size        size = 0;

    for (i = 0; i < len; i++)
        size += IndexTupleSize(itvec[i]) + sizeof(ItemIdData);

    /* TODO: Consider fillfactor */
    return (size <= GiSTPageSize);
}

gistFormTuple()

IndexTuple gistFormTuple	(	GISTSTATE *	giststate,
		Relation	r,
		Datum *	attdata,
		bool *	isnull,
		bool	isleaf
	)

Definition at line 574 of file gistutil.c.

References gistCompressValues(), index_form_tuple(), INDEX_MAX_KEYS, ItemPointerSetOffsetNumber, GISTSTATE::leafTupdesc, GISTSTATE::nonLeafTupdesc, and IndexTupleData::t_tid.

Referenced by gistBuildCallback(), gistgetadjusted(), gistinsert(), gistSplit(), and gistunion().

{
    Datum       compatt[INDEX_MAX_KEYS];
    IndexTuple  res;

    gistCompressValues(giststate, r, attdata, isnull, isleaf, compatt);

    res = index_form_tuple(isleaf ? giststate->leafTupdesc :
                           giststate->nonLeafTupdesc,
                           compatt, isnull);

    /*
     * The offset number on tuples on internal pages is unused. For historical
     * reasons, it is set to 0xffff.
     */
    ItemPointerSetOffsetNumber(&(res->t_tid), 0xffff);
    return res;
}

gistFreeBuildBuffers()

void gistFreeBuildBuffers

(

GISTBuildBuffers *

gfbb

)

Definition at line 511 of file gistbuildbuffers.c.

References BufFileClose(), and GISTBuildBuffers::pfile.

Referenced by gistbuild().

{
    /* Close buffers file. */
    BufFileClose(gfbb->pfile);

    /* All other things will be freed on memory context release */
}

gistgetadjusted()

IndexTuple gistgetadjusted	(	Relation	r,
		IndexTuple	oldtup,
		IndexTuple	addtup,
		GISTSTATE *	giststate
	)

Definition at line 315 of file gistutil.c.

References gistDeCompressAtt(), gistFormTuple(), gistKeyIsEQ(), gistMakeUnionKey(), i, INDEX_MAX_KEYS, IndexRelationGetNumberOfKeyAttributes, sort-test::key, and IndexTupleData::t_tid.

Referenced by gistdoinsert(), gistformdownlink(), gistProcessItup(), and gistRelocateBuildBuffersOnSplit().

{
    bool        neednew = false;
    GISTENTRY   oldentries[INDEX_MAX_KEYS],
                addentries[INDEX_MAX_KEYS];
    bool        oldisnull[INDEX_MAX_KEYS],
                addisnull[INDEX_MAX_KEYS];
    Datum       attr[INDEX_MAX_KEYS];
    bool        isnull[INDEX_MAX_KEYS];
    IndexTuple  newtup = NULL;
    int         i;

    gistDeCompressAtt(giststate, r, oldtup, NULL,
                      (OffsetNumber) 0, oldentries, oldisnull);

    gistDeCompressAtt(giststate, r, addtup, NULL,
                      (OffsetNumber) 0, addentries, addisnull);

    for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(r); i++)
    {
        gistMakeUnionKey(giststate, i,
                         oldentries + i, oldisnull[i],
                         addentries + i, addisnull[i],
                         attr + i, isnull + i);

        if (neednew)
            /* we already need new key, so we can skip check */
            continue;

        if (isnull[i])
            /* union of key may be NULL if and only if both keys are NULL */
            continue;

        if (!addisnull[i])
        {
            if (oldisnull[i] ||
                !gistKeyIsEQ(giststate, i, oldentries[i].key, attr[i]))
                neednew = true;
        }
    }

    if (neednew)
    {
        /* need to update key */
        newtup = gistFormTuple(giststate, r, attr, isnull, false);
        newtup->t_tid = oldtup->t_tid;
    }

    return newtup;
}

gistgetbitmap()

int64 gistgetbitmap	(	IndexScanDesc	scan,
		TIDBitmap *	tbm
	)

Definition at line 745 of file gistget.c.

References CHECK_FOR_INTERRUPTS, GISTScanOpaqueData::curPageData, GISTSearchItem::distances, getNextGISTSearchItem(), GIST_ROOT_BLKNO, gistScanPage(), IndexScanDescData::indexRelation, MemoryContextReset(), GISTScanOpaqueData::nPageData, IndexScanDescData::opaque, GISTScanOpaqueData::pageDataCxt, pfree(), pgstat_count_index_scan, GISTScanOpaqueData::qual_ok, and IndexScanDescData::xs_hitup.

Referenced by gisthandler().

{
    GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
    int64       ntids = 0;
    GISTSearchItem fakeItem;

    if (!so->qual_ok)
        return 0;

    pgstat_count_index_scan(scan->indexRelation);

    /* Begin the scan by processing the root page */
    so->curPageData = so->nPageData = 0;
    scan->xs_hitup = NULL;
    if (so->pageDataCxt)
        MemoryContextReset(so->pageDataCxt);

    fakeItem.blkno = GIST_ROOT_BLKNO;
    memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
    gistScanPage(scan, &fakeItem, NULL, tbm, &ntids);

    /*
     * While scanning a leaf page, ItemPointers of matching heap tuples will
     * be stored directly into tbm, so we don't need to deal with them here.
     */
    for (;;)
    {
        GISTSearchItem *item = getNextGISTSearchItem(so);

        if (!item)
            break;

        CHECK_FOR_INTERRUPTS();

        gistScanPage(scan, item, item->distances, tbm, &ntids);

        pfree(item);
    }

    return ntids;
}

gistGetFakeLSN()

XLogRecPtr gistGetFakeLSN

(

Relation

rel

)

Definition at line 1024 of file gistutil.c.

References Assert, FirstNormalUnloggedLSN, GetFakeLSNForUnloggedRel(), GetXLogInsertRecPtr(), gistXLogAssignLSN(), InvalidXLogRecPtr, RelationData::rd_rel, RelationIsPermanent, RelationNeedsWAL, and XLogRecPtrIsInvalid.

Referenced by gistdeletepage(), gistplacetopage(), gistprunepage(), gistvacuumpage(), and gistvacuumscan().

{
    if (rel->rd_rel->relpersistence == RELPERSISTENCE_TEMP)
    {
        /*
         * Temporary relations are only accessible in our session, so a simple
         * backend-local counter will do.
         */
        static XLogRecPtr counter = FirstNormalUnloggedLSN;

        return counter++;
    }
    else if (RelationIsPermanent(rel))
    {
        /*
         * WAL-logging on this relation will start after commit, so its LSNs
         * must be distinct numbers smaller than the LSN at the next commit.
         * Emit a dummy WAL record if insert-LSN hasn't advanced after the
         * last call.
         */
        static XLogRecPtr lastlsn = InvalidXLogRecPtr;
        XLogRecPtr  currlsn = GetXLogInsertRecPtr();

        /* Shouldn't be called for WAL-logging relations */
        Assert(!RelationNeedsWAL(rel));

        /* No need for an actual record if we already have a distinct LSN */
        if (!XLogRecPtrIsInvalid(lastlsn) && lastlsn == currlsn)
            currlsn = gistXLogAssignLSN();

        lastlsn = currlsn;
        return currlsn;
    }
    else
    {
        /*
         * Unlogged relations are accessible from other backends, and survive
         * (clean) restarts. GetFakeLSNForUnloggedRel() handles that for us.
         */
        Assert(rel->rd_rel->relpersistence == RELPERSISTENCE_UNLOGGED);
        return GetFakeLSNForUnloggedRel();
    }
}

gistGetNodeBuffer()

GISTNodeBuffer* gistGetNodeBuffer	(	GISTBuildBuffers *	gfbb,
		GISTSTATE *	giststate,
		BlockNumber	blkno,
		int	level
	)

Definition at line 117 of file gistbuildbuffers.c.

References GISTNodeBuffer::blocksCount, GISTBuildBuffers::buffersOnLevels, GISTBuildBuffers::buffersOnLevelsLen, GISTBuildBuffers::context, HASH_ENTER, hash_search(), i, InvalidBlockNumber, GISTNodeBuffer::isTemp, lcons(), GISTNodeBuffer::level, MemoryContextSwitchTo(), NIL, GISTBuildBuffers::nodeBuffersTab, GISTNodeBuffer::pageBlocknum, GISTNodeBuffer::pageBuffer, GISTNodeBuffer::queuedForEmptying, and repalloc().

Referenced by gistProcessItup(), and gistRelocateBuildBuffersOnSplit().

{
    GISTNodeBuffer *nodeBuffer;
    bool        found;

    /* Find node buffer in hash table */
    nodeBuffer = (GISTNodeBuffer *) hash_search(gfbb->nodeBuffersTab,
                                                (const void *) &nodeBlocknum,
                                                HASH_ENTER,
                                                &found);
    if (!found)
    {
        /*
         * Node buffer wasn't found. Initialize the new buffer as empty.
         */
        MemoryContext oldcxt = MemoryContextSwitchTo(gfbb->context);

        /* nodeBuffer->nodeBlocknum is the hash key and was filled in already */
        nodeBuffer->blocksCount = 0;
        nodeBuffer->pageBlocknum = InvalidBlockNumber;
        nodeBuffer->pageBuffer = NULL;
        nodeBuffer->queuedForEmptying = false;
        nodeBuffer->isTemp = false;
        nodeBuffer->level = level;

        /*
         * Add this buffer to the list of buffers on this level. Enlarge
         * buffersOnLevels array if needed.
         */
        if (level >= gfbb->buffersOnLevelsLen)
        {
            int         i;

            gfbb->buffersOnLevels =
                (List **) repalloc(gfbb->buffersOnLevels,
                                   (level + 1) * sizeof(List *));

            /* initialize the enlarged portion */
            for (i = gfbb->buffersOnLevelsLen; i <= level; i++)
                gfbb->buffersOnLevels[i] = NIL;
            gfbb->buffersOnLevelsLen = level + 1;
        }

        /*
         * Prepend the new buffer to the list of buffers on this level. It's
         * not arbitrary that the new buffer is put to the beginning of the
         * list: in the final emptying phase we loop through all buffers at
         * each level, and flush them. If a page is split during the emptying,
         * it's more efficient to flush the new splitted pages first, before
         * moving on to pre-existing pages on the level. The buffers just
         * created during the page split are likely still in cache, so
         * flushing them immediately is more efficient than putting them to
         * the end of the queue.
         */
        gfbb->buffersOnLevels[level] = lcons(nodeBuffer,
                                             gfbb->buffersOnLevels[level]);

        MemoryContextSwitchTo(oldcxt);
    }

    return nodeBuffer;
}

gistgettuple()

bool gistgettuple	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 614 of file gistget.c.

References GISTSearchItem::blkno, CHECK_FOR_INTERRUPTS, GISTScanOpaqueData::curBlkno, GISTScanOpaqueData::curPageData, GISTSearchItem::data, GISTSearchItem::distances, elog, ERROR, GISTScanOpaqueData::firstCall, ForwardScanDirection, getNextGISTSearchItem(), getNextNearest(), GIST_ROOT_BLKNO, gistkillitems(), gistScanPage(), GISTScanOpaqueData::giststate, GISTSearchHeapItem::heapPtr, IndexScanDescData::indexRelation, InvalidBlockNumber, IndexScanDescData::kill_prior_tuple, GISTScanOpaqueData::killedItems, MaxIndexTuplesPerPage, MemoryContextReset(), MemoryContextSwitchTo(), GISTScanOpaqueData::nPageData, IndexScanDescData::numberOfOrderBys, GISTScanOpaqueData::numKilled, GISTSearchHeapItem::offnum, IndexScanDescData::opaque, GISTScanOpaqueData::pageData, GISTScanOpaqueData::pageDataCxt, palloc(), GISTSearchItem::parentlsn, pfree(), pgstat_count_index_scan, GISTScanOpaqueData::qual_ok, GISTSearchHeapItem::recheck, GISTSearchHeapItem::recontup, GISTSTATE::scanCxt, IndexScanDescData::xs_heaptid, IndexScanDescData::xs_hitup, IndexScanDescData::xs_recheck, and IndexScanDescData::xs_want_itup.

Referenced by gisthandler().

{
    GISTScanOpaque so = (GISTScanOpaque) scan->opaque;

    if (dir != ForwardScanDirection)
        elog(ERROR, "GiST only supports forward scan direction");

    if (!so->qual_ok)
        return false;

    if (so->firstCall)
    {
        /* Begin the scan by processing the root page */
        GISTSearchItem fakeItem;

        pgstat_count_index_scan(scan->indexRelation);

        so->firstCall = false;
        so->curPageData = so->nPageData = 0;
        scan->xs_hitup = NULL;
        if (so->pageDataCxt)
            MemoryContextReset(so->pageDataCxt);

        fakeItem.blkno = GIST_ROOT_BLKNO;
        memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
        gistScanPage(scan, &fakeItem, NULL, NULL, NULL);
    }

    if (scan->numberOfOrderBys > 0)
    {
        /* Must fetch tuples in strict distance order */
        return getNextNearest(scan);
    }
    else
    {
        /* Fetch tuples index-page-at-a-time */
        for (;;)
        {
            if (so->curPageData < so->nPageData)
            {
                if (scan->kill_prior_tuple && so->curPageData > 0)
                {

                    if (so->killedItems == NULL)
                    {
                        MemoryContext oldCxt =
                        MemoryContextSwitchTo(so->giststate->scanCxt);

                        so->killedItems =
                            (OffsetNumber *) palloc(MaxIndexTuplesPerPage
                                                    * sizeof(OffsetNumber));

                        MemoryContextSwitchTo(oldCxt);
                    }
                    if (so->numKilled < MaxIndexTuplesPerPage)
                        so->killedItems[so->numKilled++] =
                            so->pageData[so->curPageData - 1].offnum;
                }
                /* continuing to return tuples from a leaf page */
                scan->xs_heaptid = so->pageData[so->curPageData].heapPtr;
                scan->xs_recheck = so->pageData[so->curPageData].recheck;

                /* in an index-only scan, also return the reconstructed tuple */
                if (scan->xs_want_itup)
                    scan->xs_hitup = so->pageData[so->curPageData].recontup;

                so->curPageData++;

                return true;
            }

            /*
             * Check the last returned tuple and add it to killedItems if
             * necessary
             */
            if (scan->kill_prior_tuple
                && so->curPageData > 0
                && so->curPageData == so->nPageData)
            {

                if (so->killedItems == NULL)
                {
                    MemoryContext oldCxt =
                    MemoryContextSwitchTo(so->giststate->scanCxt);

                    so->killedItems =
                        (OffsetNumber *) palloc(MaxIndexTuplesPerPage
                                                * sizeof(OffsetNumber));

                    MemoryContextSwitchTo(oldCxt);
                }
                if (so->numKilled < MaxIndexTuplesPerPage)
                    so->killedItems[so->numKilled++] =
                        so->pageData[so->curPageData - 1].offnum;
            }
            /* find and process the next index page */
            do
            {
                GISTSearchItem *item;

                if ((so->curBlkno != InvalidBlockNumber) && (so->numKilled > 0))
                    gistkillitems(scan);

                item = getNextGISTSearchItem(so);

                if (!item)
                    return false;

                CHECK_FOR_INTERRUPTS();

                /* save current item BlockNumber for next gistkillitems() call */
                so->curBlkno = item->blkno;

                /*
                 * While scanning a leaf page, ItemPointers of matching heap
                 * tuples are stored in so->pageData.  If there are any on
                 * this page, we fall out of the inner "do" and loop around to
                 * return them.
                 */
                gistScanPage(scan, item, item->distances, NULL, NULL);

                pfree(item);
            } while (so->nPageData == 0);
        }
    }
}

GISTInitBuffer()

void GISTInitBuffer	(	Buffer	b,
		uint32	f
	)

Definition at line 772 of file gistutil.c.

References BufferGetPage, gistinitpage(), and GistSortedBuildPageState::page.

Referenced by gistbuild(), gistbuildempty(), gistplacetopage(), and gistRedoPageSplitRecord().

{
    Page        page;

    page = BufferGetPage(b);
    gistinitpage(page, f);
}

gistInitBuildBuffers()

GISTBuildBuffers* gistInitBuildBuffers	(	int	pagesPerBuffer,
		int	levelStep,
		int	maxLevel
	)

Definition at line 48 of file gistbuildbuffers.c.

References GISTBuildBuffers::bufferEmptyingQueue, GISTBuildBuffers::buffersOnLevels, GISTBuildBuffers::buffersOnLevelsLen, BufFileCreateTemp(), GISTBuildBuffers::context, CurrentMemoryContext, HASHCTL::entrysize, GISTBuildBuffers::freeBlocks, GISTBuildBuffers::freeBlocksLen, HASH_BLOBS, HASH_CONTEXT, hash_create(), HASH_ELEM, HASHCTL::hcxt, HASHCTL::keysize, GISTBuildBuffers::levelStep, GISTBuildBuffers::loadedBuffers, GISTBuildBuffers::loadedBuffersCount, GISTBuildBuffers::loadedBuffersLen, GISTBuildBuffers::nFileBlocks, GISTBuildBuffers::nFreeBlocks, NIL, GISTBuildBuffers::nodeBuffersTab, GISTBuildBuffers::pagesPerBuffer, palloc(), GISTBuildBuffers::pfile, and GISTBuildBuffers::rootlevel.

Referenced by gistInitBuffering().

{
    GISTBuildBuffers *gfbb;
    HASHCTL     hashCtl;

    gfbb = palloc(sizeof(GISTBuildBuffers));
    gfbb->pagesPerBuffer = pagesPerBuffer;
    gfbb->levelStep = levelStep;

    /*
     * Create a temporary file to hold buffer pages that are swapped out of
     * memory.
     */
    gfbb->pfile = BufFileCreateTemp(false);
    gfbb->nFileBlocks = 0;

    /* Initialize free page management. */
    gfbb->nFreeBlocks = 0;
    gfbb->freeBlocksLen = 32;
    gfbb->freeBlocks = (long *) palloc(gfbb->freeBlocksLen * sizeof(long));

    /*
     * Current memory context will be used for all in-memory data structures
     * of buffers which are persistent during buffering build.
     */
    gfbb->context = CurrentMemoryContext;

    /*
     * nodeBuffersTab hash is association between index blocks and it's
     * buffers.
     */
    hashCtl.keysize = sizeof(BlockNumber);
    hashCtl.entrysize = sizeof(GISTNodeBuffer);
    hashCtl.hcxt = CurrentMemoryContext;
    gfbb->nodeBuffersTab = hash_create("gistbuildbuffers",
                                       1024,
                                       &hashCtl,
                                       HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);

    gfbb->bufferEmptyingQueue = NIL;

    /*
     * Per-level node buffers lists for final buffers emptying process. Node
     * buffers are inserted here when they are created.
     */
    gfbb->buffersOnLevelsLen = 1;
    gfbb->buffersOnLevels = (List **) palloc(sizeof(List *) *
                                             gfbb->buffersOnLevelsLen);
    gfbb->buffersOnLevels[0] = NIL;

    /*
     * Block numbers of node buffers which last pages are currently loaded
     * into main memory.
     */
    gfbb->loadedBuffersLen = 32;
    gfbb->loadedBuffers = (GISTNodeBuffer **) palloc(gfbb->loadedBuffersLen *
                                                     sizeof(GISTNodeBuffer *));
    gfbb->loadedBuffersCount = 0;

    gfbb->rootlevel = maxLevel;

    return gfbb;
}

gistinitpage()

void gistinitpage	(	Page	page,
		uint32	f
	)

Definition at line 756 of file gistutil.c.

References GISTPageOpaqueData::flags, GISTPageOpaqueData::gist_page_id, GIST_PAGE_ID, GistPageGetOpaque, InvalidBlockNumber, PageInit(), and GISTPageOpaqueData::rightlink.

Referenced by gist_indexsortbuild(), gist_indexsortbuild_pagestate_flush(), and GISTInitBuffer().

{
    GISTPageOpaque opaque;

    PageInit(page, BLCKSZ, sizeof(GISTPageOpaqueData));

    opaque = GistPageGetOpaque(page);
    opaque->rightlink = InvalidBlockNumber;
    opaque->flags = f;
    opaque->gist_page_id = GIST_PAGE_ID;
}

gistinsert()

bool gistinsert	(	Relation	r,
		Datum *	values,
		bool *	isnull,
		ItemPointer	ht_ctid,
		Relation	heapRel,
		IndexUniqueCheck	checkUnique,
		bool	indexUnchanged,
		struct IndexInfo *	indexInfo
	)

Definition at line 156 of file gist.c.

References createTempGistContext(), gistdoinsert(), gistFormTuple(), IndexInfo::ii_AmCache, IndexInfo::ii_Context, initGISTstate(), MemoryContextReset(), MemoryContextSwitchTo(), and GISTSTATE::tempCxt.

Referenced by gisthandler().

{
    GISTSTATE  *giststate = (GISTSTATE *) indexInfo->ii_AmCache;
    IndexTuple  itup;
    MemoryContext oldCxt;

    /* Initialize GISTSTATE cache if first call in this statement */
    if (giststate == NULL)
    {
        oldCxt = MemoryContextSwitchTo(indexInfo->ii_Context);
        giststate = initGISTstate(r);
        giststate->tempCxt = createTempGistContext();
        indexInfo->ii_AmCache = (void *) giststate;
        MemoryContextSwitchTo(oldCxt);
    }

    oldCxt = MemoryContextSwitchTo(giststate->tempCxt);

    itup = gistFormTuple(giststate, r,
                         values, isnull, true /* size is currently bogus */ );
    itup->t_tid = *ht_ctid;

    gistdoinsert(r, itup, 0, giststate, heapRel, false);

    /* cleanup */
    MemoryContextSwitchTo(oldCxt);
    MemoryContextReset(giststate->tempCxt);

    return false;
}

gistjoinvector()

IndexTuple* gistjoinvector	(	IndexTuple *	itvec,
		int *	len,
		IndexTuple *	additvec,
		int	addlen
	)

Definition at line 113 of file gistutil.c.

References repalloc().

Referenced by gistplacetopage().

{
    itvec = (IndexTuple *) repalloc((void *) itvec, sizeof(IndexTuple) * ((*len) + addlen));
    memmove(&itvec[*len], additvec, sizeof(IndexTuple) * addlen);
    *len += addlen;
    return itvec;
}

gistKeyIsEQ()

bool gistKeyIsEQ	(	GISTSTATE *	giststate,
		int	attno,
		Datum	a,
		Datum	b
	)

Definition at line 280 of file gistutil.c.

References GISTSTATE::equalFn, FunctionCall3Coll(), PointerGetDatum, and GISTSTATE::supportCollation.

Referenced by gistgetadjusted(), and gistUserPicksplit().

{
    bool        result;

    FunctionCall3Coll(&giststate->equalFn[attno],
                      giststate->supportCollation[attno],
                      a, b,
                      PointerGetDatum(&result));
    return result;
}

gistMakeUnionItVec()

void gistMakeUnionItVec	(	GISTSTATE *	giststate,
		IndexTuple *	itvec,
		int	len,
		Datum *	attr,
		bool *	isnull
	)

Definition at line 154 of file gistutil.c.

References FunctionCall2Coll(), GEVHDRSZ, gistdentryinit(), i, index_getattr, GISTSTATE::leafTupdesc, GistEntryVector::n, TupleDescData::natts, GISTSTATE::nonLeafTupdesc, palloc(), PointerGetDatum, GISTSTATE::supportCollation, GISTSTATE::unionFn, and GistEntryVector::vector.

Referenced by gistunion(), and gistunionsubkeyvec().

{
    int         i;
    GistEntryVector *evec;
    int         attrsize;

    evec = (GistEntryVector *) palloc((len + 2) * sizeof(GISTENTRY) + GEVHDRSZ);

    for (i = 0; i < giststate->nonLeafTupdesc->natts; i++)
    {
        int         j;

        /* Collect non-null datums for this column */
        evec->n = 0;
        for (j = 0; j < len; j++)
        {
            Datum       datum;
            bool        IsNull;

            datum = index_getattr(itvec[j], i + 1, giststate->leafTupdesc,
                                  &IsNull);
            if (IsNull)
                continue;

            gistdentryinit(giststate, i,
                           evec->vector + evec->n,
                           datum,
                           NULL, NULL, (OffsetNumber) 0,
                           false, IsNull);
            evec->n++;
        }

        /* If this column was all NULLs, the union is NULL */
        if (evec->n == 0)
        {
            attr[i] = (Datum) 0;
            isnull[i] = true;
        }
        else
        {
            if (evec->n == 1)
            {
                /* unionFn may expect at least two inputs */
                evec->n = 2;
                evec->vector[1] = evec->vector[0];
            }

            /* Make union and store in attr array */
            attr[i] = FunctionCall2Coll(&giststate->unionFn[i],
                                        giststate->supportCollation[i],
                                        PointerGetDatum(evec),
                                        PointerGetDatum(&attrsize));

            isnull[i] = false;
        }
    }
}

gistMakeUnionKey()

void gistMakeUnionKey	(	GISTSTATE *	giststate,
		int	attno,
		GISTENTRY *	entry1,
		bool	isnull1,
		GISTENTRY *	entry2,
		bool	isnull2,
		Datum *	dst,
		bool *	dstisnull
	)

Definition at line 232 of file gistutil.c.

References FunctionCall2Coll(), GEVHDRSZ, GistEntryVector::n, PointerGetDatum, GISTSTATE::supportCollation, GISTSTATE::unionFn, and GistEntryVector::vector.

Referenced by gistgetadjusted(), and supportSecondarySplit().

{
    /* we need a GistEntryVector with room for exactly 2 elements */
    union
    {
        GistEntryVector gev;
        char        padding[2 * sizeof(GISTENTRY) + GEVHDRSZ];
    }           storage;
    GistEntryVector *evec = &storage.gev;
    int         dstsize;

    evec->n = 2;

    if (isnull1 && isnull2)
    {
        *dstisnull = true;
        *dst = (Datum) 0;
    }
    else
    {
        if (isnull1 == false && isnull2 == false)
        {
            evec->vector[0] = *entry1;
            evec->vector[1] = *entry2;
        }
        else if (isnull1 == false)
        {
            evec->vector[0] = *entry1;
            evec->vector[1] = *entry1;
        }
        else
        {
            evec->vector[0] = *entry2;
            evec->vector[1] = *entry2;
        }

        *dstisnull = false;
        *dst = FunctionCall2Coll(&giststate->unionFn[attno],
                                 giststate->supportCollation[attno],
                                 PointerGetDatum(evec),
                                 PointerGetDatum(&dstsize));
    }
}

gistNewBuffer()

Buffer gistNewBuffer

(

Relation

r

)

Definition at line 823 of file gistutil.c.

References BufferGetPage, ConditionalLockBuffer(), ExclusiveLock, GetFreeIndexPage(), GIST_EXCLUSIVE, GIST_UNLOCK, gistcheckpage(), GistPageGetDeleteXid(), gistPageRecyclable(), gistXLogPageReuse(), InvalidBlockNumber, LockBuffer(), LockRelationForExtension(), P_NEW, GistSortedBuildPageState::page, PageIsNew, ReadBuffer(), RELATION_IS_LOCAL, RelationNeedsWAL, ReleaseBuffer(), UnlockRelationForExtension(), and XLogStandbyInfoActive.

Referenced by gistbuild(), and gistplacetopage().

{
    Buffer      buffer;
    bool        needLock;

    /* First, try to get a page from FSM */
    for (;;)
    {
        BlockNumber blkno = GetFreeIndexPage(r);

        if (blkno == InvalidBlockNumber)
            break;              /* nothing left in FSM */

        buffer = ReadBuffer(r, blkno);

        /*
         * We have to guard against the possibility that someone else already
         * recycled this page; the buffer may be locked if so.
         */
        if (ConditionalLockBuffer(buffer))
        {
            Page        page = BufferGetPage(buffer);

            /*
             * If the page was never initialized, it's OK to use.
             */
            if (PageIsNew(page))
                return buffer;

            gistcheckpage(r, buffer);

            /*
             * Otherwise, recycle it if deleted, and too old to have any
             * processes interested in it.
             */
            if (gistPageRecyclable(page))
            {
                /*
                 * If we are generating WAL for Hot Standby then create a WAL
                 * record that will allow us to conflict with queries running
                 * on standby, in case they have snapshots older than the
                 * page's deleteXid.
                 */
                if (XLogStandbyInfoActive() && RelationNeedsWAL(r))
                    gistXLogPageReuse(r, blkno, GistPageGetDeleteXid(page));

                return buffer;
            }

            LockBuffer(buffer, GIST_UNLOCK);
        }

        /* Can't use it, so release buffer and try again */
        ReleaseBuffer(buffer);
    }

    /* Must extend the file */
    needLock = !RELATION_IS_LOCAL(r);

    if (needLock)
        LockRelationForExtension(r, ExclusiveLock);

    buffer = ReadBuffer(r, P_NEW);
    LockBuffer(buffer, GIST_EXCLUSIVE);

    if (needLock)
        UnlockRelationForExtension(r, ExclusiveLock);

    return buffer;
}

gistnospace()

bool gistnospace	(	Page	page,
		IndexTuple *	itvec,
		int	len,
		OffsetNumber	todelete,
		Size	freespace
	)

Definition at line 58 of file gistutil.c.

References i, IndexTupleSize, InvalidOffsetNumber, PageGetFreeSpace(), PageGetItem, and PageGetItemId.

Referenced by gistplacetopage().

{
    unsigned int size = freespace,
                deleted = 0;
    int         i;

    for (i = 0; i < len; i++)
        size += IndexTupleSize(itvec[i]) + sizeof(ItemIdData);

    if (todelete != InvalidOffsetNumber)
    {
        IndexTuple  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, todelete));

        deleted = IndexTupleSize(itup) + sizeof(ItemIdData);
    }

    return (PageGetFreeSpace(page) + deleted < size);
}

gistoptions()

bytea* gistoptions	(	Datum	reloptions,
		bool	validate
	)

Definition at line 920 of file gistutil.c.

References build_reloptions(), fillfactor, lengthof, offsetof, RELOPT_KIND_GIST, RELOPT_TYPE_ENUM, and RELOPT_TYPE_INT.

Referenced by gisthandler().

{
    static const relopt_parse_elt tab[] = {
        {"fillfactor", RELOPT_TYPE_INT, offsetof(GiSTOptions, fillfactor)},
        {"buffering", RELOPT_TYPE_ENUM, offsetof(GiSTOptions, buffering_mode)}
    };

    return (bytea *) build_reloptions(reloptions, validate,
                                      RELOPT_KIND_GIST,
                                      sizeof(GiSTOptions),
                                      tab, lengthof(tab));
}

gistPageRecyclable()

bool gistPageRecyclable

(

Page

page

)

Definition at line 896 of file gistutil.c.

References GistPageGetDeleteXid(), GistPageIsDeleted, GlobalVisCheckRemovableFullXid(), and PageIsNew.

Referenced by gistNewBuffer(), and gistvacuumpage().

{
    if (PageIsNew(page))
        return true;
    if (GistPageIsDeleted(page))
    {
        /*
         * The page was deleted, but when? If it was just deleted, a scan
         * might have seen the downlink to it, and will read the page later.
         * As long as that can happen, we must keep the deleted page around as
         * a tombstone.
         *
         * For that check if the deletion XID could still be visible to
         * anyone. If not, then no scan that's still in progress could have
         * seen its downlink, and we can recycle it.
         */
        FullTransactionId deletexid_full = GistPageGetDeleteXid(page);

        return GlobalVisCheckRemovableFullXid(NULL, deletexid_full);
    }
    return false;
}

gistpenalty()

float gistpenalty	(	GISTSTATE *	giststate,
		int	attno,
		GISTENTRY *	key1,
		bool	isNull1,
		GISTENTRY *	key2,
		bool	isNull2
	)

Definition at line 723 of file gistutil.c.

References FmgrInfo::fn_strict, FunctionCall3Coll(), get_float4_infinity(), GISTSTATE::penaltyFn, PointerGetDatum, and GISTSTATE::supportCollation.

Referenced by findDontCares(), gistchoose(), gistRelocateBuildBuffersOnSplit(), placeOne(), and supportSecondarySplit().

{
    float       penalty = 0.0;

    if (giststate->penaltyFn[attno].fn_strict == false ||
        (isNullOrig == false && isNullAdd == false))
    {
        FunctionCall3Coll(&giststate->penaltyFn[attno],
                          giststate->supportCollation[attno],
                          PointerGetDatum(orig),
                          PointerGetDatum(add),
                          PointerGetDatum(&penalty));
        /* disallow negative or NaN penalty */
        if (isnan(penalty) || penalty < 0.0)
            penalty = 0.0;
    }
    else if (isNullOrig && isNullAdd)
        penalty = 0.0;
    else
    {
        /* try to prevent mixing null and non-null values */
        penalty = get_float4_infinity();
    }

    return penalty;
}

gistplacetopage()

bool gistplacetopage	(	Relation	rel,
		Size	freespace,
		GISTSTATE *	giststate,
		Buffer	buffer,
		IndexTuple *	itup,
		int	ntup,
		OffsetNumber	oldoffnum,
		BlockNumber *	newblkno,
		Buffer	leftchildbuf,
		List **	splitinfo,
		bool	markfollowright,
		Relation	heapRel,
		bool	is_build
	)

Definition at line 222 of file gist.c.

References Assert, DataPageDeleteStack::blkno, gistxlogPage::blkno, SplitedPageLayout::block, GISTPageSplitInfo::buf, SplitedPageLayout::buffer, BufferGetBlockNumber(), BufferGetPage, BufferIsValid, GISTPageSplitInfo::downlink, elog, END_CRIT_SECTION, ERROR, F_LEAF, FirstOffsetNumber, GIST_MAX_SPLIT_PAGES, GIST_ROOT_BLKNO, GistBuildLSN, GistClearFollowRight, gistextractpage(), gistfillbuffer(), gistfillitupvec(), GistFollowRight, gistGetFakeLSN(), GISTInitBuffer(), gistjoinvector(), GistMarkFollowRight, gistNewBuffer(), gistnospace(), GistPageGetNSN, GistPageGetOpaque, GistPageHasGarbage, GistPageIsDeleted, GistPageIsLeaf, GistPageSetNSN, gistprunepage(), gistSplit(), GistTupleSetValid, gistXLogSplit(), gistXLogUpdate(), i, IndexTupleSize, InvalidBlockNumber, InvalidOffsetNumber, ItemPointerEquals(), ItemPointerSetBlockNumber, SplitedPageLayout::itup, lappend(), SplitedPageLayout::lenlist, SplitedPageLayout::list, MarkBufferDirty(), SplitedPageLayout::next, NIL, gistxlogPage::num, OffsetNumberIsValid, SplitedPageLayout::page, PageAddItem, PageGetTempPageCopySpecial(), PageIndexTupleDelete(), PageIndexTupleOverwrite(), PageRestoreTempPage(), PageSetLSN, palloc(), PredicateLockPageSplit(), RelationGetRelationName, RelationNeedsWAL, START_CRIT_SECTION, IndexTupleData::t_tid, UnlockReleaseBuffer(), and XLogEnsureRecordSpace().

Referenced by gistbufferinginserttuples(), and gistinserttuples().

{
    BlockNumber blkno = BufferGetBlockNumber(buffer);
    Page        page = BufferGetPage(buffer);
    bool        is_leaf = (GistPageIsLeaf(page)) ? true : false;
    XLogRecPtr  recptr;
    int         i;
    bool        is_split;

    /*
     * Refuse to modify a page that's incompletely split. This should not
     * happen because we finish any incomplete splits while we walk down the
     * tree. However, it's remotely possible that another concurrent inserter
     * splits a parent page, and errors out before completing the split. We
     * will just throw an error in that case, and leave any split we had in
     * progress unfinished too. The next insert that comes along will clean up
     * the mess.
     */
    if (GistFollowRight(page))
        elog(ERROR, "concurrent GiST page split was incomplete");

    /* should never try to insert to a deleted page */
    Assert(!GistPageIsDeleted(page));

    *splitinfo = NIL;

    /*
     * if isupdate, remove old key: This node's key has been modified, either
     * because a child split occurred or because we needed to adjust our key
     * for an insert in a child node. Therefore, remove the old version of
     * this node's key.
     *
     * for WAL replay, in the non-split case we handle this by setting up a
     * one-element todelete array; in the split case, it's handled implicitly
     * because the tuple vector passed to gistSplit won't include this tuple.
     */
    is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);

    /*
     * If leaf page is full, try at first to delete dead tuples. And then
     * check again.
     */
    if (is_split && GistPageIsLeaf(page) && GistPageHasGarbage(page))
    {
        gistprunepage(rel, page, buffer, heapRel);
        is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
    }

    if (is_split)
    {
        /* no space for insertion */
        IndexTuple *itvec;
        int         tlen;
        SplitedPageLayout *dist = NULL,
                   *ptr;
        BlockNumber oldrlink = InvalidBlockNumber;
        GistNSN     oldnsn = 0;
        SplitedPageLayout rootpg;
        bool        is_rootsplit;
        int         npage;

        is_rootsplit = (blkno == GIST_ROOT_BLKNO);

        /*
         * Form index tuples vector to split. If we're replacing an old tuple,
         * remove the old version from the vector.
         */
        itvec = gistextractpage(page, &tlen);
        if (OffsetNumberIsValid(oldoffnum))
        {
            /* on inner page we should remove old tuple */
            int         pos = oldoffnum - FirstOffsetNumber;

            tlen--;
            if (pos != tlen)
                memmove(itvec + pos, itvec + pos + 1, sizeof(IndexTuple) * (tlen - pos));
        }
        itvec = gistjoinvector(itvec, &tlen, itup, ntup);
        dist = gistSplit(rel, page, itvec, tlen, giststate);

        /*
         * Check that split didn't produce too many pages.
         */
        npage = 0;
        for (ptr = dist; ptr; ptr = ptr->next)
            npage++;
        /* in a root split, we'll add one more page to the list below */
        if (is_rootsplit)
            npage++;
        if (npage > GIST_MAX_SPLIT_PAGES)
            elog(ERROR, "GiST page split into too many halves (%d, maximum %d)",
                 npage, GIST_MAX_SPLIT_PAGES);

        /*
         * Set up pages to work with. Allocate new buffers for all but the
         * leftmost page. The original page becomes the new leftmost page, and
         * is just replaced with the new contents.
         *
         * For a root-split, allocate new buffers for all child pages, the
         * original page is overwritten with new root page containing
         * downlinks to the new child pages.
         */
        ptr = dist;
        if (!is_rootsplit)
        {
            /* save old rightlink and NSN */
            oldrlink = GistPageGetOpaque(page)->rightlink;
            oldnsn = GistPageGetNSN(page);

            dist->buffer = buffer;
            dist->block.blkno = BufferGetBlockNumber(buffer);
            dist->page = PageGetTempPageCopySpecial(BufferGetPage(buffer));

            /* clean all flags except F_LEAF */
            GistPageGetOpaque(dist->page)->flags = (is_leaf) ? F_LEAF : 0;

            ptr = ptr->next;
        }
        for (; ptr; ptr = ptr->next)
        {
            /* Allocate new page */
            ptr->buffer = gistNewBuffer(rel);
            GISTInitBuffer(ptr->buffer, (is_leaf) ? F_LEAF : 0);
            ptr->page = BufferGetPage(ptr->buffer);
            ptr->block.blkno = BufferGetBlockNumber(ptr->buffer);
            PredicateLockPageSplit(rel,
                                   BufferGetBlockNumber(buffer),
                                   BufferGetBlockNumber(ptr->buffer));
        }

        /*
         * Now that we know which blocks the new pages go to, set up downlink
         * tuples to point to them.
         */
        for (ptr = dist; ptr; ptr = ptr->next)
        {
            ItemPointerSetBlockNumber(&(ptr->itup->t_tid), ptr->block.blkno);
            GistTupleSetValid(ptr->itup);
        }

        /*
         * If this is a root split, we construct the new root page with the
         * downlinks here directly, instead of requiring the caller to insert
         * them. Add the new root page to the list along with the child pages.
         */
        if (is_rootsplit)
        {
            IndexTuple *downlinks;
            int         ndownlinks = 0;
            int         i;

            rootpg.buffer = buffer;
            rootpg.page = PageGetTempPageCopySpecial(BufferGetPage(rootpg.buffer));
            GistPageGetOpaque(rootpg.page)->flags = 0;

            /* Prepare a vector of all the downlinks */
            for (ptr = dist; ptr; ptr = ptr->next)
                ndownlinks++;
            downlinks = palloc(sizeof(IndexTuple) * ndownlinks);
            for (i = 0, ptr = dist; ptr; ptr = ptr->next)
                downlinks[i++] = ptr->itup;

            rootpg.block.blkno = GIST_ROOT_BLKNO;
            rootpg.block.num = ndownlinks;
            rootpg.list = gistfillitupvec(downlinks, ndownlinks,
                                          &(rootpg.lenlist));
            rootpg.itup = NULL;

            rootpg.next = dist;
            dist = &rootpg;
        }
        else
        {
            /* Prepare split-info to be returned to caller */
            for (ptr = dist; ptr; ptr = ptr->next)
            {
                GISTPageSplitInfo *si = palloc(sizeof(GISTPageSplitInfo));

                si->buf = ptr->buffer;
                si->downlink = ptr->itup;
                *splitinfo = lappend(*splitinfo, si);
            }
        }

        /*
         * Fill all pages. All the pages are new, ie. freshly allocated empty
         * pages, or a temporary copy of the old page.
         */
        for (ptr = dist; ptr; ptr = ptr->next)
        {
            char       *data = (char *) (ptr->list);

            for (i = 0; i < ptr->block.num; i++)
            {
                IndexTuple  thistup = (IndexTuple) data;

                if (PageAddItem(ptr->page, (Item) data, IndexTupleSize(thistup), i + FirstOffsetNumber, false, false) == InvalidOffsetNumber)
                    elog(ERROR, "failed to add item to index page in \"%s\"", RelationGetRelationName(rel));

                /*
                 * If this is the first inserted/updated tuple, let the caller
                 * know which page it landed on.
                 */
                if (newblkno && ItemPointerEquals(&thistup->t_tid, &(*itup)->t_tid))
                    *newblkno = ptr->block.blkno;

                data += IndexTupleSize(thistup);
            }

            /* Set up rightlinks */
            if (ptr->next && ptr->block.blkno != GIST_ROOT_BLKNO)
                GistPageGetOpaque(ptr->page)->rightlink =
                    ptr->next->block.blkno;
            else
                GistPageGetOpaque(ptr->page)->rightlink = oldrlink;

            /*
             * Mark the all but the right-most page with the follow-right
             * flag. It will be cleared as soon as the downlink is inserted
             * into the parent, but this ensures that if we error out before
             * that, the index is still consistent. (in buffering build mode,
             * any error will abort the index build anyway, so this is not
             * needed.)
             */
            if (ptr->next && !is_rootsplit && markfollowright)
                GistMarkFollowRight(ptr->page);
            else
                GistClearFollowRight(ptr->page);

            /*
             * Copy the NSN of the original page to all pages. The
             * F_FOLLOW_RIGHT flags ensure that scans will follow the
             * rightlinks until the downlinks are inserted.
             */
            GistPageSetNSN(ptr->page, oldnsn);
        }

        /*
         * gistXLogSplit() needs to WAL log a lot of pages, prepare WAL
         * insertion for that. NB: The number of pages and data segments
         * specified here must match the calculations in gistXLogSplit()!
         */
        if (!is_build && RelationNeedsWAL(rel))
            XLogEnsureRecordSpace(npage, 1 + npage * 2);

        START_CRIT_SECTION();

        /*
         * Must mark buffers dirty before XLogInsert, even though we'll still
         * be changing their opaque fields below.
         */
        for (ptr = dist; ptr; ptr = ptr->next)
            MarkBufferDirty(ptr->buffer);
        if (BufferIsValid(leftchildbuf))
            MarkBufferDirty(leftchildbuf);

        /*
         * The first page in the chain was a temporary working copy meant to
         * replace the old page. Copy it over the old page.
         */
        PageRestoreTempPage(dist->page, BufferGetPage(dist->buffer));
        dist->page = BufferGetPage(dist->buffer);

        /*
         * Write the WAL record.
         *
         * If we're building a new index, however, we don't WAL-log changes
         * yet. The LSN-NSN interlock between parent and child requires that
         * LSNs never move backwards, so set the LSNs to a value that's
         * smaller than any real or fake unlogged LSN that might be generated
         * later. (There can't be any concurrent scans during index build, so
         * we don't need to be able to detect concurrent splits yet.)
         */
        if (is_build)
            recptr = GistBuildLSN;
        else
        {
            if (RelationNeedsWAL(rel))
                recptr = gistXLogSplit(is_leaf,
                                       dist, oldrlink, oldnsn, leftchildbuf,
                                       markfollowright);
            else
                recptr = gistGetFakeLSN(rel);
        }

        for (ptr = dist; ptr; ptr = ptr->next)
            PageSetLSN(ptr->page, recptr);

        /*
         * Return the new child buffers to the caller.
         *
         * If this was a root split, we've already inserted the downlink
         * pointers, in the form of a new root page. Therefore we can release
         * all the new buffers, and keep just the root page locked.
         */
        if (is_rootsplit)
        {
            for (ptr = dist->next; ptr; ptr = ptr->next)
                UnlockReleaseBuffer(ptr->buffer);
        }
    }
    else
    {
        /*
         * Enough space.  We always get here if ntup==0.
         */
        START_CRIT_SECTION();

        /*
         * Delete old tuple if any, then insert new tuple(s) if any.  If
         * possible, use the fast path of PageIndexTupleOverwrite.
         */
        if (OffsetNumberIsValid(oldoffnum))
        {
            if (ntup == 1)
            {
                /* One-for-one replacement, so use PageIndexTupleOverwrite */
                if (!PageIndexTupleOverwrite(page, oldoffnum, (Item) *itup,
                                             IndexTupleSize(*itup)))
                    elog(ERROR, "failed to add item to index page in \"%s\"",
                         RelationGetRelationName(rel));
            }
            else
            {
                /* Delete old, then append new tuple(s) to page */
                PageIndexTupleDelete(page, oldoffnum);
                gistfillbuffer(page, itup, ntup, InvalidOffsetNumber);
            }
        }
        else
        {
            /* Just append new tuples at the end of the page */
            gistfillbuffer(page, itup, ntup, InvalidOffsetNumber);
        }

        MarkBufferDirty(buffer);

        if (BufferIsValid(leftchildbuf))
            MarkBufferDirty(leftchildbuf);

        if (is_build)
            recptr = GistBuildLSN;
        else
        {
            if (RelationNeedsWAL(rel))
            {
                OffsetNumber ndeloffs = 0,
                            deloffs[1];

                if (OffsetNumberIsValid(oldoffnum))
                {
                    deloffs[0] = oldoffnum;
                    ndeloffs = 1;
                }

                recptr = gistXLogUpdate(buffer,
                                        deloffs, ndeloffs, itup, ntup,
                                        leftchildbuf);
            }
            else
                recptr = gistGetFakeLSN(rel);
        }
        PageSetLSN(page, recptr);

        if (newblkno)
            *newblkno = blkno;
    }

    /*
     * If we inserted the downlink for a child page, set NSN and clear
     * F_FOLLOW_RIGHT flag on the left child, so that concurrent scans know to
     * follow the rightlink if and only if they looked at the parent page
     * before we inserted the downlink.
     *
     * Note that we do this *after* writing the WAL record. That means that
     * the possible full page image in the WAL record does not include these
     * changes, and they must be replayed even if the page is restored from
     * the full page image. There's a chicken-and-egg problem: if we updated
     * the child pages first, we wouldn't know the recptr of the WAL record
     * we're about to write.
     */
    if (BufferIsValid(leftchildbuf))
    {
        Page        leftpg = BufferGetPage(leftchildbuf);

        GistPageSetNSN(leftpg, recptr);
        GistClearFollowRight(leftpg);

        PageSetLSN(leftpg, recptr);
    }

    END_CRIT_SECTION();

    return is_split;
}

gistPopItupFromNodeBuffer()

bool gistPopItupFromNodeBuffer	(	GISTBuildBuffers *	gfbb,
		GISTNodeBuffer *	nodeBuffer,
		IndexTuple *	item
	)

Definition at line 410 of file gistbuildbuffers.c.

References Assert, GISTNodeBuffer::blocksCount, gistBuffersReleaseBlock(), gistGetItupFromPage(), gistLoadNodeBuffer(), InvalidBlockNumber, PAGE_IS_EMPTY, GISTNodeBuffer::pageBuffer, GISTBuildBuffers::pfile, pfree(), GISTNodeBufferPage::prev, and ReadTempFileBlock().

Referenced by gistProcessEmptyingQueue(), and gistRelocateBuildBuffersOnSplit().

{
    /*
     * If node buffer is empty then return false.
     */
    if (nodeBuffer->blocksCount <= 0)
        return false;

    /* Load last page of node buffer if needed */
    if (!nodeBuffer->pageBuffer)
        gistLoadNodeBuffer(gfbb, nodeBuffer);

    /*
     * Get index tuple from last non-empty page.
     */
    gistGetItupFromPage(nodeBuffer->pageBuffer, itup);

    /*
     * If we just removed the last tuple from the page, fetch previous page on
     * this node buffer (if any).
     */
    if (PAGE_IS_EMPTY(nodeBuffer->pageBuffer))
    {
        BlockNumber prevblkno;

        /*
         * blocksCount includes the page in pageBuffer, so decrease it now.
         */
        nodeBuffer->blocksCount--;

        /*
         * If there's more pages, fetch previous one.
         */
        prevblkno = nodeBuffer->pageBuffer->prev;
        if (prevblkno != InvalidBlockNumber)
        {
            /* There is a previous page. Fetch it. */
            Assert(nodeBuffer->blocksCount > 0);
            ReadTempFileBlock(gfbb->pfile, prevblkno, nodeBuffer->pageBuffer);

            /*
             * Now that we've read the block in memory, we can release its
             * on-disk block for reuse.
             */
            gistBuffersReleaseBlock(gfbb, prevblkno);
        }
        else
        {
            /* No more pages. Free memory. */
            Assert(nodeBuffer->blocksCount == 0);
            pfree(nodeBuffer->pageBuffer);
            nodeBuffer->pageBuffer = NULL;
        }
    }
    return true;
}

gistproperty()

bool gistproperty	(	Oid	index_oid,
		int	attno,
		IndexAMProperty	prop,
		const char *	propname,
		bool *	res,
		bool *	isnull
	)

Definition at line 941 of file gistutil.c.

References AMPROCNUM, AMPROP_DISTANCE_ORDERABLE, AMPROP_RETURNABLE, get_index_column_opclass(), get_opclass_opfamily_and_input_type(), GIST_COMPRESS_PROC, GIST_DISTANCE_PROC, GIST_FETCH_PROC, Int16GetDatum, ObjectIdGetDatum, OidIsValid, and SearchSysCacheExists4.

Referenced by gisthandler().

{
    Oid         opclass,
                opfamily,
                opcintype;
    int16       procno;

    /* Only answer column-level inquiries */
    if (attno == 0)
        return false;

    /*
     * Currently, GiST distance-ordered scans require that there be a distance
     * function in the opclass with the default types (i.e. the one loaded
     * into the relcache entry, see initGISTstate).  So we assume that if such
     * a function exists, then there's a reason for it (rather than grubbing
     * through all the opfamily's operators to find an ordered one).
     *
     * Essentially the same code can test whether we support returning the
     * column data, since that's true if the opclass provides a fetch proc.
     */

    switch (prop)
    {
        case AMPROP_DISTANCE_ORDERABLE:
            procno = GIST_DISTANCE_PROC;
            break;
        case AMPROP_RETURNABLE:
            procno = GIST_FETCH_PROC;
            break;
        default:
            return false;
    }

    /* First we need to know the column's opclass. */
    opclass = get_index_column_opclass(index_oid, attno);
    if (!OidIsValid(opclass))
    {
        *isnull = true;
        return true;
    }

    /* Now look up the opclass family and input datatype. */
    if (!get_opclass_opfamily_and_input_type(opclass, &opfamily, &opcintype))
    {
        *isnull = true;
        return true;
    }

    /* And now we can check whether the function is provided. */

    *res = SearchSysCacheExists4(AMPROCNUM,
                                 ObjectIdGetDatum(opfamily),
                                 ObjectIdGetDatum(opcintype),
                                 ObjectIdGetDatum(opcintype),
                                 Int16GetDatum(procno));

    /*
     * Special case: even without a fetch function, AMPROP_RETURNABLE is true
     * if the opclass has no compress function.
     */
    if (prop == AMPROP_RETURNABLE && !*res)
    {
        *res = !SearchSysCacheExists4(AMPROCNUM,
                                      ObjectIdGetDatum(opfamily),
                                      ObjectIdGetDatum(opcintype),
                                      ObjectIdGetDatum(opcintype),
                                      Int16GetDatum(GIST_COMPRESS_PROC));
    }

    *isnull = false;

    return true;
}

gistPushItupToNodeBuffer()

void gistPushItupToNodeBuffer	(	GISTBuildBuffers *	gfbb,
		GISTNodeBuffer *	nodeBuffer,
		IndexTuple	item
	)

Definition at line 340 of file gistbuildbuffers.c.

References GISTNodeBuffer::blocksCount, BUFFER_HALF_FILLED, GISTBuildBuffers::bufferEmptyingQueue, GISTBuildBuffers::context, gistAddLoadedBuffer(), gistAllocateNewPageBuffer(), gistBuffersGetFreeBlock(), gistLoadNodeBuffer(), gistPlaceItupToPage(), lcons(), MAXALIGN, MemoryContextSwitchTo(), offsetof, PAGE_FREE_SPACE, PAGE_NO_SPACE, GISTNodeBuffer::pageBuffer, GISTBuildBuffers::pfile, GISTNodeBufferPage::prev, GISTNodeBuffer::queuedForEmptying, and WriteTempFileBlock().

Referenced by gistProcessItup(), and gistRelocateBuildBuffersOnSplit().

{
    /*
     * Most part of memory operations will be in buffering build persistent
     * context. So, let's switch to it.
     */
    MemoryContext oldcxt = MemoryContextSwitchTo(gfbb->context);

    /*
     * If the buffer is currently empty, create the first page.
     */
    if (nodeBuffer->blocksCount == 0)
    {
        nodeBuffer->pageBuffer = gistAllocateNewPageBuffer(gfbb);
        nodeBuffer->blocksCount = 1;
        gistAddLoadedBuffer(gfbb, nodeBuffer);
    }

    /* Load last page of node buffer if it wasn't in memory already */
    if (!nodeBuffer->pageBuffer)
        gistLoadNodeBuffer(gfbb, nodeBuffer);

    /*
     * Check if there is enough space on the last page for the tuple.
     */
    if (PAGE_NO_SPACE(nodeBuffer->pageBuffer, itup))
    {
        /*
         * Nope. Swap previous block to disk and allocate a new one.
         */
        BlockNumber blkno;

        /* Write filled page to the disk */
        blkno = gistBuffersGetFreeBlock(gfbb);
        WriteTempFileBlock(gfbb->pfile, blkno, nodeBuffer->pageBuffer);

        /*
         * Reset the in-memory page as empty, and link the previous block to
         * the new page by storing its block number in the prev-link.
         */
        PAGE_FREE_SPACE(nodeBuffer->pageBuffer) =
            BLCKSZ - MAXALIGN(offsetof(GISTNodeBufferPage, tupledata));
        nodeBuffer->pageBuffer->prev = blkno;

        /* We've just added one more page */
        nodeBuffer->blocksCount++;
    }

    gistPlaceItupToPage(nodeBuffer->pageBuffer, itup);

    /*
     * If the buffer just overflowed, add it to the emptying queue.
     */
    if (BUFFER_HALF_FILLED(nodeBuffer, gfbb) && !nodeBuffer->queuedForEmptying)
    {
        gfbb->bufferEmptyingQueue = lcons(nodeBuffer,
                                          gfbb->bufferEmptyingQueue);
        nodeBuffer->queuedForEmptying = true;
    }

    /* Restore memory context */
    MemoryContextSwitchTo(oldcxt);
}

gistRelocateBuildBuffersOnSplit()

void gistRelocateBuildBuffersOnSplit	(	GISTBuildBuffers *	gfbb,
		GISTSTATE *	giststate,
		Relation	r,
		int	level,
		Buffer	buffer,
		List *	splitinfo
	)

Definition at line 537 of file gistbuildbuffers.c.

References Assert, GISTNodeBuffer::blocksCount, GISTPageSplitInfo::buf, BufferGetBlockNumber(), GISTPageSplitInfo::downlink, RelocationBufferInfo::entry, GIST_ROOT_BLKNO, gistDeCompressAtt(), gistgetadjusted(), gistGetNodeBuffer(), gistpenalty(), gistPopItupFromNodeBuffer(), gistPushItupToNodeBuffer(), HASH_FIND, hash_search(), i, INDEX_MAX_KEYS, IndexRelationGetNumberOfKeyAttributes, InvalidBlockNumber, RelocationBufferInfo::isnull, GISTNodeBuffer::isTemp, LEVEL_HAS_BUFFERS, lfirst, list_length(), RelocationBufferInfo::nodeBuffer, GISTBuildBuffers::nodeBuffersTab, GISTNodeBuffer::pageBlocknum, GISTNodeBuffer::pageBuffer, palloc(), pfree(), and RelocationBufferInfo::splitinfo.

Referenced by gistbufferinginserttuples().

{
    RelocationBufferInfo *relocationBuffersInfos;
    bool        found;
    GISTNodeBuffer *nodeBuffer;
    BlockNumber blocknum;
    IndexTuple  itup;
    int         splitPagesCount = 0,
                i;
    GISTENTRY   entry[INDEX_MAX_KEYS];
    bool        isnull[INDEX_MAX_KEYS];
    GISTNodeBuffer oldBuf;
    ListCell   *lc;

    /* If the splitted page doesn't have buffers, we have nothing to do. */
    if (!LEVEL_HAS_BUFFERS(level, gfbb))
        return;

    /*
     * Get the node buffer of the splitted page.
     */
    blocknum = BufferGetBlockNumber(buffer);
    nodeBuffer = hash_search(gfbb->nodeBuffersTab, &blocknum,
                             HASH_FIND, &found);
    if (!found)
    {
        /* The page has no buffer, so we have nothing to do. */
        return;
    }

    /*
     * Make a copy of the old buffer, as we're going reuse it as the buffer
     * for the new left page, which is on the same block as the old page.
     * That's not true for the root page, but that's fine because we never
     * have a buffer on the root page anyway. The original algorithm as
     * described by Arge et al did, but it's of no use, as you might as well
     * read the tuples straight from the heap instead of the root buffer.
     */
    Assert(blocknum != GIST_ROOT_BLKNO);
    memcpy(&oldBuf, nodeBuffer, sizeof(GISTNodeBuffer));
    oldBuf.isTemp = true;

    /* Reset the old buffer, used for the new left page from now on */
    nodeBuffer->blocksCount = 0;
    nodeBuffer->pageBuffer = NULL;
    nodeBuffer->pageBlocknum = InvalidBlockNumber;

    /*
     * Allocate memory for information about relocation buffers.
     */
    splitPagesCount = list_length(splitinfo);
    relocationBuffersInfos =
        (RelocationBufferInfo *) palloc(sizeof(RelocationBufferInfo) *
                                        splitPagesCount);

    /*
     * Fill relocation buffers information for node buffers of pages produced
     * by split.
     */
    i = 0;
    foreach(lc, splitinfo)
    {
        GISTPageSplitInfo *si = (GISTPageSplitInfo *) lfirst(lc);
        GISTNodeBuffer *newNodeBuffer;

        /* Decompress parent index tuple of node buffer page. */
        gistDeCompressAtt(giststate, r,
                          si->downlink, NULL, (OffsetNumber) 0,
                          relocationBuffersInfos[i].entry,
                          relocationBuffersInfos[i].isnull);

        /*
         * Create a node buffer for the page. The leftmost half is on the same
         * block as the old page before split, so for the leftmost half this
         * will return the original buffer. The tuples on the original buffer
         * were relinked to the temporary buffer, so the original one is now
         * empty.
         */
        newNodeBuffer = gistGetNodeBuffer(gfbb, giststate, BufferGetBlockNumber(si->buf), level);

        relocationBuffersInfos[i].nodeBuffer = newNodeBuffer;
        relocationBuffersInfos[i].splitinfo = si;

        i++;
    }

    /*
     * Loop through all index tuples in the buffer of the page being split,
     * moving them to buffers for the new pages.  We try to move each tuple to
     * the page that will result in the lowest penalty for the leading column
     * or, in the case of a tie, the lowest penalty for the earliest column
     * that is not tied.
     *
     * The page searching logic is very similar to gistchoose().
     */
    while (gistPopItupFromNodeBuffer(gfbb, &oldBuf, &itup))
    {
        float       best_penalty[INDEX_MAX_KEYS];
        int         i,
                    which;
        IndexTuple  newtup;
        RelocationBufferInfo *targetBufferInfo;

        gistDeCompressAtt(giststate, r,
                          itup, NULL, (OffsetNumber) 0, entry, isnull);

        /* default to using first page (shouldn't matter) */
        which = 0;

        /*
         * best_penalty[j] is the best penalty we have seen so far for column
         * j, or -1 when we haven't yet examined column j.  Array entries to
         * the right of the first -1 are undefined.
         */
        best_penalty[0] = -1;

        /*
         * Loop over possible target pages, looking for one to move this tuple
         * to.
         */
        for (i = 0; i < splitPagesCount; i++)
        {
            RelocationBufferInfo *splitPageInfo = &relocationBuffersInfos[i];
            bool        zero_penalty;
            int         j;

            zero_penalty = true;

            /* Loop over index attributes. */
            for (j = 0; j < IndexRelationGetNumberOfKeyAttributes(r); j++)
            {
                float       usize;

                /* Compute penalty for this column. */
                usize = gistpenalty(giststate, j,
                                    &splitPageInfo->entry[j],
                                    splitPageInfo->isnull[j],
                                    &entry[j], isnull[j]);
                if (usize > 0)
                    zero_penalty = false;

                if (best_penalty[j] < 0 || usize < best_penalty[j])
                {
                    /*
                     * New best penalty for column.  Tentatively select this
                     * page as the target, and record the best penalty.  Then
                     * reset the next column's penalty to "unknown" (and
                     * indirectly, the same for all the ones to its right).
                     * This will force us to adopt this page's penalty values
                     * as the best for all the remaining columns during
                     * subsequent loop iterations.
                     */
                    which = i;
                    best_penalty[j] = usize;

                    if (j < IndexRelationGetNumberOfKeyAttributes(r) - 1)
                        best_penalty[j + 1] = -1;
                }
                else if (best_penalty[j] == usize)
                {
                    /*
                     * The current page is exactly as good for this column as
                     * the best page seen so far.  The next iteration of this
                     * loop will compare the next column.
                     */
                }
                else
                {
                    /*
                     * The current page is worse for this column than the best
                     * page seen so far.  Skip the remaining columns and move
                     * on to the next page, if any.
                     */
                    zero_penalty = false;   /* so outer loop won't exit */
                    break;
                }
            }

            /*
             * If we find a page with zero penalty for all columns, there's no
             * need to examine remaining pages; just break out of the loop and
             * return it.
             */
            if (zero_penalty)
                break;
        }

        /* OK, "which" is the page index to push the tuple to */
        targetBufferInfo = &relocationBuffersInfos[which];

        /* Push item to selected node buffer */
        gistPushItupToNodeBuffer(gfbb, targetBufferInfo->nodeBuffer, itup);

        /* Adjust the downlink for this page, if needed. */
        newtup = gistgetadjusted(r, targetBufferInfo->splitinfo->downlink,
                                 itup, giststate);
        if (newtup)
        {
            gistDeCompressAtt(giststate, r,
                              newtup, NULL, (OffsetNumber) 0,
                              targetBufferInfo->entry,
                              targetBufferInfo->isnull);

            targetBufferInfo->splitinfo->downlink = newtup;
        }
    }

    pfree(relocationBuffersInfos);
}

gistSplit()

SplitedPageLayout* gistSplit	(	Relation	r,
		Page	page,
		IndexTuple *	itup,
		int	len,
		GISTSTATE *	giststate
	)

Definition at line 1416 of file gist.c.

References Assert, SplitedPageLayout::block, check_stack_depth(), ereport, errcode(), errmsg(), ERROR, gistfillitupvec(), gistfitpage(), gistFormTuple(), GiSTPageSize, gistSplit(), gistSplitByKey(), i, IndexTupleSize, SplitedPageLayout::itup, SplitedPageLayout::lenlist, SplitedPageLayout::list, TupleDescData::natts, SplitedPageLayout::next, GISTSTATE::nonLeafTupdesc, gistxlogPage::num, palloc(), RelationGetRelationName, ROTATEDIST, GistSplitVector::spl_lattr, GIST_SPLITVEC::spl_left, GistSplitVector::spl_lisnull, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GistSplitVector::spl_rattr, GIST_SPLITVEC::spl_right, GistSplitVector::spl_risnull, and GistSplitVector::splitVector.

Referenced by gistplacetopage(), and gistSplit().

{
    IndexTuple *lvectup,
               *rvectup;
    GistSplitVector v;
    int         i;
    SplitedPageLayout *res = NULL;

    /* this should never recurse very deeply, but better safe than sorry */
    check_stack_depth();

    /* there's no point in splitting an empty page */
    Assert(len > 0);

    /*
     * If a single tuple doesn't fit on a page, no amount of splitting will
     * help.
     */
    if (len == 1)
        ereport(ERROR,
                (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
                 errmsg("index row size %zu exceeds maximum %zu for index \"%s\"",
                        IndexTupleSize(itup[0]), GiSTPageSize,
                        RelationGetRelationName(r))));

    memset(v.spl_lisnull, true,
           sizeof(bool) * giststate->nonLeafTupdesc->natts);
    memset(v.spl_risnull, true,
           sizeof(bool) * giststate->nonLeafTupdesc->natts);
    gistSplitByKey(r, page, itup, len, giststate, &v, 0);

    /* form left and right vector */
    lvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * (len + 1));
    rvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * (len + 1));

    for (i = 0; i < v.splitVector.spl_nleft; i++)
        lvectup[i] = itup[v.splitVector.spl_left[i] - 1];

    for (i = 0; i < v.splitVector.spl_nright; i++)
        rvectup[i] = itup[v.splitVector.spl_right[i] - 1];

    /* finalize splitting (may need another split) */
    if (!gistfitpage(rvectup, v.splitVector.spl_nright))
    {
        res = gistSplit(r, page, rvectup, v.splitVector.spl_nright, giststate);
    }
    else
    {
        ROTATEDIST(res);
        res->block.num = v.splitVector.spl_nright;
        res->list = gistfillitupvec(rvectup, v.splitVector.spl_nright, &(res->lenlist));
        res->itup = gistFormTuple(giststate, r, v.spl_rattr, v.spl_risnull, false);
    }

    if (!gistfitpage(lvectup, v.splitVector.spl_nleft))
    {
        SplitedPageLayout *resptr,
                   *subres;

        resptr = subres = gistSplit(r, page, lvectup, v.splitVector.spl_nleft, giststate);

        /* install on list's tail */
        while (resptr->next)
            resptr = resptr->next;

        resptr->next = res;
        res = subres;
    }
    else
    {
        ROTATEDIST(res);
        res->block.num = v.splitVector.spl_nleft;
        res->list = gistfillitupvec(lvectup, v.splitVector.spl_nleft, &(res->lenlist));
        res->itup = gistFormTuple(giststate, r, v.spl_lattr, v.spl_lisnull, false);
    }

    return res;
}

gistSplitByKey()

void gistSplitByKey	(	Relation	r,
		Page	page,
		IndexTuple *	itup,
		int	len,
		GISTSTATE *	giststate,
		GistSplitVector *	v,
		int	attno
	)

Definition at line 623 of file gistsplit.c.

References Assert, GEVHDRSZ, gistdentryinit(), gistSplitByKey(), gistSplitHalf(), gistunionsubkey(), gistUserPicksplit(), i, index_getattr, GISTSTATE::leafTupdesc, GistEntryVector::n, TupleDescData::natts, GISTSTATE::nonLeafTupdesc, palloc(), GistSplitVector::spl_dontcare, GIST_SPLITVEC::spl_left, GistSplitVector::spl_lisnull, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GIST_SPLITVEC::spl_right, GistSplitVector::spl_risnull, GistSplitVector::splitVector, and GistEntryVector::vector.

Referenced by gistSplit(), and gistSplitByKey().

{
    GistEntryVector *entryvec;
    OffsetNumber *offNullTuples;
    int         nOffNullTuples = 0;
    int         i;

    /* generate the item array, and identify tuples with null keys */
    /* note that entryvec->vector[0] goes unused in this code */
    entryvec = palloc(GEVHDRSZ + (len + 1) * sizeof(GISTENTRY));
    entryvec->n = len + 1;
    offNullTuples = (OffsetNumber *) palloc(len * sizeof(OffsetNumber));

    for (i = 1; i <= len; i++)
    {
        Datum       datum;
        bool        IsNull;

        datum = index_getattr(itup[i - 1], attno + 1, giststate->leafTupdesc,
                              &IsNull);
        gistdentryinit(giststate, attno, &(entryvec->vector[i]),
                       datum, r, page, i,
                       false, IsNull);
        if (IsNull)
            offNullTuples[nOffNullTuples++] = i;
    }

    if (nOffNullTuples == len)
    {
        /*
         * Corner case: All keys in attno column are null, so just transfer
         * our attention to the next column.  If there's no next column, just
         * split page in half.
         */
        v->spl_risnull[attno] = v->spl_lisnull[attno] = true;

        if (attno + 1 < giststate->nonLeafTupdesc->natts)
            gistSplitByKey(r, page, itup, len, giststate, v, attno + 1);
        else
            gistSplitHalf(&v->splitVector, len);
    }
    else if (nOffNullTuples > 0)
    {
        int         j = 0;

        /*
         * We don't want to mix NULL and not-NULL keys on one page, so split
         * nulls to right page and not-nulls to left.
         */
        v->splitVector.spl_right = offNullTuples;
        v->splitVector.spl_nright = nOffNullTuples;
        v->spl_risnull[attno] = true;

        v->splitVector.spl_left = (OffsetNumber *) palloc(len * sizeof(OffsetNumber));
        v->splitVector.spl_nleft = 0;
        for (i = 1; i <= len; i++)
            if (j < v->splitVector.spl_nright && offNullTuples[j] == i)
                j++;
            else
                v->splitVector.spl_left[v->splitVector.spl_nleft++] = i;

        /* Compute union keys, unless outer recursion level will handle it */
        if (attno == 0 && giststate->nonLeafTupdesc->natts == 1)
        {
            v->spl_dontcare = NULL;
            gistunionsubkey(giststate, itup, v);
        }
    }
    else
    {
        /*
         * All keys are not-null, so apply user-defined PickSplit method
         */
        if (gistUserPicksplit(r, entryvec, attno, v, itup, len, giststate))
        {
            /*
             * Splitting on attno column is not optimal, so consider
             * redistributing don't-care tuples according to the next column
             */
            Assert(attno + 1 < giststate->nonLeafTupdesc->natts);

            if (v->spl_dontcare == NULL)
            {
                /*
                 * This split was actually degenerate, so ignore it altogether
                 * and just split according to the next column.
                 */
                gistSplitByKey(r, page, itup, len, giststate, v, attno + 1);
            }
            else
            {
                /*
                 * Form an array of just the don't-care tuples to pass to a
                 * recursive invocation of this function for the next column.
                 */
                IndexTuple *newitup = (IndexTuple *) palloc(len * sizeof(IndexTuple));
                OffsetNumber *map = (OffsetNumber *) palloc(len * sizeof(OffsetNumber));
                int         newlen = 0;
                GIST_SPLITVEC backupSplit;

                for (i = 0; i < len; i++)
                {
                    if (v->spl_dontcare[i + 1])
                    {
                        newitup[newlen] = itup[i];
                        map[newlen] = i + 1;
                        newlen++;
                    }
                }

                Assert(newlen > 0);

                /*
                 * Make a backup copy of v->splitVector, since the recursive
                 * call will overwrite that with its own result.
                 */
                backupSplit = v->splitVector;
                backupSplit.spl_left = (OffsetNumber *) palloc(sizeof(OffsetNumber) * len);
                memcpy(backupSplit.spl_left, v->splitVector.spl_left, sizeof(OffsetNumber) * v->splitVector.spl_nleft);
                backupSplit.spl_right = (OffsetNumber *) palloc(sizeof(OffsetNumber) * len);
                memcpy(backupSplit.spl_right, v->splitVector.spl_right, sizeof(OffsetNumber) * v->splitVector.spl_nright);

                /* Recursively decide how to split the don't-care tuples */
                gistSplitByKey(r, page, newitup, newlen, giststate, v, attno + 1);

                /* Merge result of subsplit with non-don't-care tuples */
                for (i = 0; i < v->splitVector.spl_nleft; i++)
                    backupSplit.spl_left[backupSplit.spl_nleft++] = map[v->splitVector.spl_left[i] - 1];
                for (i = 0; i < v->splitVector.spl_nright; i++)
                    backupSplit.spl_right[backupSplit.spl_nright++] = map[v->splitVector.spl_right[i] - 1];

                v->splitVector = backupSplit;
            }
        }
    }

    /*
     * If we're handling a multicolumn index, at the end of the recursion
     * recompute the left and right union datums for all index columns.  This
     * makes sure we hand back correct union datums in all corner cases,
     * including when we haven't processed all columns to start with, or when
     * a secondary split moved "don't care" tuples from one side to the other
     * (we really shouldn't assume that that didn't change the union datums).
     *
     * Note: when we're in an internal recursion (attno > 0), we do not worry
     * about whether the union datums we return with are sensible, since
     * calling levels won't care.  Also, in a single-column index, we expect
     * that PickSplit (or the special cases above) produced correct union
     * datums.
     */
    if (attno == 0 && giststate->nonLeafTupdesc->natts > 1)
    {
        v->spl_dontcare = NULL;
        gistunionsubkey(giststate, itup, v);
    }
}

gistunion()

IndexTuple gistunion	(	Relation	r,
		IndexTuple *	itvec,
		int	len,
		GISTSTATE *	giststate
	)

Definition at line 218 of file gistutil.c.

References gistFormTuple(), gistMakeUnionItVec(), and INDEX_MAX_KEYS.

Referenced by gist_indexsortbuild_pagestate_flush().

{
    Datum       attr[INDEX_MAX_KEYS];
    bool        isnull[INDEX_MAX_KEYS];

    gistMakeUnionItVec(giststate, itvec, len, attr, isnull);

    return gistFormTuple(giststate, r, attr, isnull, false);
}

gistUnloadNodeBuffers()

void gistUnloadNodeBuffers

(

GISTBuildBuffers *

gfbb

)

Definition at line 276 of file gistbuildbuffers.c.

References gistUnloadNodeBuffer(), i, GISTBuildBuffers::loadedBuffers, and GISTBuildBuffers::loadedBuffersCount.

Referenced by gistProcessEmptyingQueue().

{
    int         i;

    /* Unload all the buffers that have a page loaded in memory. */
    for (i = 0; i < gfbb->loadedBuffersCount; i++)
        gistUnloadNodeBuffer(gfbb, gfbb->loadedBuffers[i]);

    /* Now there are no node buffers with loaded last page */
    gfbb->loadedBuffersCount = 0;
}

gistvacuumcleanup()

IndexBulkDeleteResult* gistvacuumcleanup	(	IndexVacuumInfo *	info,
		IndexBulkDeleteResult *	stats
	)

Definition at line 75 of file gistvacuum.c.

References IndexVacuumInfo::analyze_only, IndexVacuumInfo::estimated_count, gistvacuumscan(), IndexVacuumInfo::num_heap_tuples, IndexBulkDeleteResult::num_index_tuples, and palloc0().

Referenced by gisthandler().

{
    /* No-op in ANALYZE ONLY mode */
    if (info->analyze_only)
        return stats;

    /*
     * If gistbulkdelete was called, we need not do anything, just return the
     * stats from the latest gistbulkdelete call.  If it wasn't called, we
     * still need to do a pass over the index, to obtain index statistics.
     */
    if (stats == NULL)
    {
        stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
        gistvacuumscan(info, stats, NULL, NULL);
    }

    /*
     * It's quite possible for us to be fooled by concurrent page splits into
     * double-counting some index tuples, so disbelieve any total that exceeds
     * the underlying heap's count ... if we know that accurately.  Otherwise
     * this might just make matters worse.
     */
    if (!info->estimated_count)
    {
        if (stats->num_index_tuples > info->num_heap_tuples)
            stats->num_index_tuples = info->num_heap_tuples;
    }

    return stats;
}

gistvalidate()

bool gistvalidate

(

Oid

opclassoid

)

Definition at line 34 of file gistvalidate.c.

References AMOPSTRATEGY, AMPROCNUM, check_amop_signature(), check_amoptsproc_signature(), check_amproc_signature(), CLAOID, elog, ereport, errcode(), errmsg(), ERROR, format_operator(), format_procedure(), OpFamilyOpFuncGroup::functionset, get_op_rettype(), get_opfamily_proc(), GETSTRUCT, GIST_COMPRESS_PROC, GIST_CONSISTENT_PROC, GIST_DECOMPRESS_PROC, GIST_DISTANCE_PROC, GIST_EQUAL_PROC, GIST_FETCH_PROC, GIST_OPTIONS_PROC, GIST_PENALTY_PROC, GIST_PICKSPLIT_PROC, GIST_SORTSUPPORT_PROC, GIST_UNION_PROC, GISTNProcs, HeapTupleIsValid, i, identify_opfamily_groups(), INFO, OpFamilyOpFuncGroup::lefttype, lfirst, catclist::members, catclist::n_members, NameStr, ObjectIdGetDatum, OidIsValid, opfamily_can_sort_type(), OPFAMILYOID, ReleaseCatCacheList(), ReleaseSysCache(), OpFamilyOpFuncGroup::righttype, SearchSysCache1(), SearchSysCacheList1, and catctup::tuple.

Referenced by gisthandler().

{
    bool        result = true;
    HeapTuple   classtup;
    Form_pg_opclass classform;
    Oid         opfamilyoid;
    Oid         opcintype;
    Oid         opckeytype;
    char       *opclassname;
    HeapTuple   familytup;
    Form_pg_opfamily familyform;
    char       *opfamilyname;
    CatCList   *proclist,
               *oprlist;
    List       *grouplist;
    OpFamilyOpFuncGroup *opclassgroup;
    int         i;
    ListCell   *lc;

    /* Fetch opclass information */
    classtup = SearchSysCache1(CLAOID, ObjectIdGetDatum(opclassoid));
    if (!HeapTupleIsValid(classtup))
        elog(ERROR, "cache lookup failed for operator class %u", opclassoid);
    classform = (Form_pg_opclass) GETSTRUCT(classtup);

    opfamilyoid = classform->opcfamily;
    opcintype = classform->opcintype;
    opckeytype = classform->opckeytype;
    if (!OidIsValid(opckeytype))
        opckeytype = opcintype;
    opclassname = NameStr(classform->opcname);

    /* Fetch opfamily information */
    familytup = SearchSysCache1(OPFAMILYOID, ObjectIdGetDatum(opfamilyoid));
    if (!HeapTupleIsValid(familytup))
        elog(ERROR, "cache lookup failed for operator family %u", opfamilyoid);
    familyform = (Form_pg_opfamily) GETSTRUCT(familytup);

    opfamilyname = NameStr(familyform->opfname);

    /* Fetch all operators and support functions of the opfamily */
    oprlist = SearchSysCacheList1(AMOPSTRATEGY, ObjectIdGetDatum(opfamilyoid));
    proclist = SearchSysCacheList1(AMPROCNUM, ObjectIdGetDatum(opfamilyoid));

    /* Check individual support functions */
    for (i = 0; i < proclist->n_members; i++)
    {
        HeapTuple   proctup = &proclist->members[i]->tuple;
        Form_pg_amproc procform = (Form_pg_amproc) GETSTRUCT(proctup);
        bool        ok;

        /*
         * All GiST support functions should be registered with matching
         * left/right types
         */
        if (procform->amproclefttype != procform->amprocrighttype)
        {
            ereport(INFO,
                    (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
                     errmsg("operator family \"%s\" of access method %s contains support function %s with different left and right input types",
                            opfamilyname, "gist",
                            format_procedure(procform->amproc))));
            result = false;
        }

        /*
         * We can't check signatures except within the specific opclass, since
         * we need to know the associated opckeytype in many cases.
         */
        if (procform->amproclefttype != opcintype)
            continue;

        /* Check procedure numbers and function signatures */
        switch (procform->amprocnum)
        {
            case GIST_CONSISTENT_PROC:
                ok = check_amproc_signature(procform->amproc, BOOLOID, false,
                                            5, 5, INTERNALOID, opcintype,
                                            INT2OID, OIDOID, INTERNALOID);
                break;
            case GIST_UNION_PROC:
                ok = check_amproc_signature(procform->amproc, opckeytype, false,
                                            2, 2, INTERNALOID, INTERNALOID);
                break;
            case GIST_COMPRESS_PROC:
            case GIST_DECOMPRESS_PROC:
            case GIST_FETCH_PROC:
                ok = check_amproc_signature(procform->amproc, INTERNALOID, true,
                                            1, 1, INTERNALOID);
                break;
            case GIST_PENALTY_PROC:
                ok = check_amproc_signature(procform->amproc, INTERNALOID, true,
                                            3, 3, INTERNALOID,
                                            INTERNALOID, INTERNALOID);
                break;
            case GIST_PICKSPLIT_PROC:
                ok = check_amproc_signature(procform->amproc, INTERNALOID, true,
                                            2, 2, INTERNALOID, INTERNALOID);
                break;
            case GIST_EQUAL_PROC:
                ok = check_amproc_signature(procform->amproc, INTERNALOID, false,
                                            3, 3, opckeytype, opckeytype,
                                            INTERNALOID);
                break;
            case GIST_DISTANCE_PROC:
                ok = check_amproc_signature(procform->amproc, FLOAT8OID, false,
                                            5, 5, INTERNALOID, opcintype,
                                            INT2OID, OIDOID, INTERNALOID);
                break;
            case GIST_OPTIONS_PROC:
                ok = check_amoptsproc_signature(procform->amproc);
                break;
            case GIST_SORTSUPPORT_PROC:
                ok = check_amproc_signature(procform->amproc, VOIDOID, true,
                                            1, 1, INTERNALOID);
                break;
            default:
                ereport(INFO,
                        (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
                         errmsg("operator family \"%s\" of access method %s contains function %s with invalid support number %d",
                                opfamilyname, "gist",
                                format_procedure(procform->amproc),
                                procform->amprocnum)));
                result = false;
                continue;       /* don't want additional message */
        }

        if (!ok)
        {
            ereport(INFO,
                    (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
                     errmsg("operator family \"%s\" of access method %s contains function %s with wrong signature for support number %d",
                            opfamilyname, "gist",
                            format_procedure(procform->amproc),
                            procform->amprocnum)));
            result = false;
        }
    }

    /* Check individual operators */
    for (i = 0; i < oprlist->n_members; i++)
    {
        HeapTuple   oprtup = &oprlist->members[i]->tuple;
        Form_pg_amop oprform = (Form_pg_amop) GETSTRUCT(oprtup);
        Oid         op_rettype;

        /* TODO: Check that only allowed strategy numbers exist */
        if (oprform->amopstrategy < 1)
        {
            ereport(INFO,
                    (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
                     errmsg("operator family \"%s\" of access method %s contains operator %s with invalid strategy number %d",
                            opfamilyname, "gist",
                            format_operator(oprform->amopopr),
                            oprform->amopstrategy)));
            result = false;
        }

        /* GiST supports ORDER BY operators */
        if (oprform->amoppurpose != AMOP_SEARCH)
        {
            /* ... but must have matching distance proc */
            if (!OidIsValid(get_opfamily_proc(opfamilyoid,
                                              oprform->amoplefttype,
                                              oprform->amoplefttype,
                                              GIST_DISTANCE_PROC)))
            {
                ereport(INFO,
                        (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
                         errmsg("operator family \"%s\" of access method %s contains unsupported ORDER BY specification for operator %s",
                                opfamilyname, "gist",
                                format_operator(oprform->amopopr))));
                result = false;
            }
            /* ... and operator result must match the claimed btree opfamily */
            op_rettype = get_op_rettype(oprform->amopopr);
            if (!opfamily_can_sort_type(oprform->amopsortfamily, op_rettype))
            {
                ereport(INFO,
                        (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
                         errmsg("operator family \"%s\" of access method %s contains incorrect ORDER BY opfamily specification for operator %s",