gist.h File Reference

#include "access/itup.h"
#include "access/stratnum.h"
#include "access/transam.h"
#include "access/xlog.h"
#include "access/xlogdefs.h"
#include "nodes/primnodes.h"
#include "storage/block.h"
#include "storage/bufpage.h"
#include "utils/relcache.h"

Include dependency graph for gist.h:

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

Go to the source code of this file.

Data Structures
struct	GISTPageOpaqueData
struct	GIST_SPLITVEC
struct	GISTENTRY
struct	GISTDeletedPageContents
struct	GistEntryVector

Macros
#define	GIST_CONSISTENT_PROC   1
#define	GIST_UNION_PROC   2
#define	GIST_COMPRESS_PROC   3
#define	GIST_DECOMPRESS_PROC   4
#define	GIST_PENALTY_PROC   5
#define	GIST_PICKSPLIT_PROC   6
#define	GIST_EQUAL_PROC   7
#define	GIST_DISTANCE_PROC   8
#define	GIST_FETCH_PROC   9
#define	GIST_OPTIONS_PROC   10
#define	GIST_SORTSUPPORT_PROC   11
#define	GIST_TRANSLATE_CMPTYPE_PROC   12
#define	GISTNProcs   12
#define	F_LEAF   (1 << 0) /* leaf page */
#define	F_DELETED   (1 << 1) /* the page has been deleted */
#define	F_TUPLES_DELETED
#define	F_FOLLOW_RIGHT   (1 << 3) /* page to the right has no downlink */
#define	F_HAS_GARBAGE
#define	GistBuildLSN   ((XLogRecPtr) 1)
#define	GISTMaxIndexTupleSize
#define	GISTMaxIndexKeySize    (GISTMaxIndexTupleSize - MAXALIGN(sizeof(IndexTupleData)))
#define	GIST_PAGE_ID   0xFF81
#define	GistPageGetOpaque(page)   ( (GISTPageOpaque) PageGetSpecialPointer(page) )
#define	GistPageIsLeaf(page)   ( GistPageGetOpaque(page)->flags & F_LEAF)
#define	GIST_LEAF(entry)   (GistPageIsLeaf((entry)->page))
#define	GistPageIsDeleted(page)   ( GistPageGetOpaque(page)->flags & F_DELETED)
#define	GistTuplesDeleted(page)   ( GistPageGetOpaque(page)->flags & F_TUPLES_DELETED)
#define	GistMarkTuplesDeleted(page)   ( GistPageGetOpaque(page)->flags |= F_TUPLES_DELETED)
#define	GistClearTuplesDeleted(page)   ( GistPageGetOpaque(page)->flags &= ~F_TUPLES_DELETED)
#define	GistPageHasGarbage(page)   ( GistPageGetOpaque(page)->flags & F_HAS_GARBAGE)
#define	GistMarkPageHasGarbage(page)   ( GistPageGetOpaque(page)->flags |= F_HAS_GARBAGE)
#define	GistClearPageHasGarbage(page)   ( GistPageGetOpaque(page)->flags &= ~F_HAS_GARBAGE)
#define	GistFollowRight(page)   ( GistPageGetOpaque(page)->flags & F_FOLLOW_RIGHT)
#define	GistMarkFollowRight(page)   ( GistPageGetOpaque(page)->flags |= F_FOLLOW_RIGHT)
#define	GistClearFollowRight(page)   ( GistPageGetOpaque(page)->flags &= ~F_FOLLOW_RIGHT)
#define	GistPageGetNSN(page)   ( PageXLogRecPtrGet(GistPageGetOpaque(page)->nsn))
#define	GistPageSetNSN(page, val)   ( PageXLogRecPtrSet(GistPageGetOpaque(page)->nsn, val))
#define	GEVHDRSZ   (offsetof(GistEntryVector, vector))
#define	gistentryinit(e, k, r, pg, o, l)

Typedefs
typedef XLogRecPtr	GistNSN
typedef PageXLogRecPtr	PageGistNSN
typedef struct GISTPageOpaqueData	GISTPageOpaqueData
typedef GISTPageOpaqueData *	GISTPageOpaque
typedef struct GIST_SPLITVEC	GIST_SPLITVEC
typedef struct GISTENTRY	GISTENTRY
typedef struct GISTDeletedPageContents	GISTDeletedPageContents

Functions
static void	GistPageSetDeleted (Page page, FullTransactionId deletexid)
static FullTransactionId	GistPageGetDeleteXid (Page page)
StrategyNumber	gisttranslatecmptype (CompareType cmptype, Oid opfamily)

Macro Definition Documentation

F_DELETED

#define F_DELETED   (1 << 1) /* the page has been deleted */

Definition at line 50 of file gist.h.

F_FOLLOW_RIGHT

#define F_FOLLOW_RIGHT   (1 << 3) /* page to the right has no downlink */

Definition at line 52 of file gist.h.

F_HAS_GARBAGE

#define F_HAS_GARBAGE

Value:

                                         (1 << 4)   /* some tuples on the page are dead,
                                         * but not deleted yet */

Definition at line 53 of file gist.h.

{
    PageGistNSN nsn;            /* this value must change on page split */
    BlockNumber rightlink;      /* next page if any */
    uint16      flags;          /* see bit definitions above */
    uint16      gist_page_id;   /* for identification of GiST indexes */
} GISTPageOpaqueData;
 
typedef GISTPageOpaqueData *GISTPageOpaque;
 
/*
 * Maximum possible sizes for GiST index tuple and index key.  Calculation is
 * based on assumption that GiST page should fit at least 4 tuples.  In theory,
 * GiST index can be functional when page can fit 3 tuples.  But that seems
 * rather inefficient, so we use a bit conservative estimate.
 *
 * The maximum size of index key is true for unicolumn index.  Therefore, this
 * estimation should be used to figure out which maximum size of GiST index key
 * makes sense at all.  For multicolumn indexes, user might be able to tune
 * key size using opclass parameters.
 */
#define GISTMaxIndexTupleSize   \
    MAXALIGN_DOWN((BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)) / \
                  4 - sizeof(ItemIdData))
 
#define GISTMaxIndexKeySize \
    (GISTMaxIndexTupleSize - MAXALIGN(sizeof(IndexTupleData)))
 
/*
 * The page ID is for the convenience of pg_filedump and similar utilities,
 * which otherwise would have a hard time telling pages of different index
 * types apart.  It should be the last 2 bytes on the page.  This is more or
 * less "free" due to alignment considerations.
 */
#define GIST_PAGE_ID        0xFF81
 
/*
 * This is the Split Vector to be returned by the PickSplit method.
 * PickSplit should fill the indexes of tuples to go to the left side into
 * spl_left[], and those to go to the right into spl_right[] (note the method
 * is responsible for palloc'ing both of these arrays!).  The tuple counts
 * go into spl_nleft/spl_nright, and spl_ldatum/spl_rdatum must be set to
 * the union keys for each side.
 *
 * If spl_ldatum_exists and spl_rdatum_exists are true, then we are performing
 * a "secondary split" using a non-first index column.  In this case some
 * decisions have already been made about a page split, and the set of tuples
 * being passed to PickSplit is just the tuples about which we are undecided.
 * spl_ldatum/spl_rdatum then contain the union keys for the tuples already
 * chosen to go left or right.  Ideally the PickSplit method should take those
 * keys into account while deciding what to do with the remaining tuples, ie
 * it should try to "build out" from those unions so as to minimally expand
 * them.  If it does so, it should union the given tuples' keys into the
 * existing spl_ldatum/spl_rdatum values rather than just setting those values
 * from scratch, and then set spl_ldatum_exists/spl_rdatum_exists to false to
 * show it has done this.
 *
 * If the PickSplit method fails to clear spl_ldatum_exists/spl_rdatum_exists,
 * the core GiST code will make its own decision about how to merge the
 * secondary-split results with the previously-chosen tuples, and will then
 * recompute the union keys from scratch.  This is a workable though often not
 * optimal approach.
 */
typedef struct GIST_SPLITVEC
{
    OffsetNumber *spl_left;     /* array of entries that go left */
    int         spl_nleft;      /* size of this array */
    Datum       spl_ldatum;     /* Union of keys in spl_left */
    bool        spl_ldatum_exists;  /* true, if spl_ldatum already exists. */
 
    OffsetNumber *spl_right;    /* array of entries that go right */
    int         spl_nright;     /* size of the array */
    Datum       spl_rdatum;     /* Union of keys in spl_right */
    bool        spl_rdatum_exists;  /* true, if spl_rdatum already exists. */
} GIST_SPLITVEC;
 
/*
 * An entry on a GiST node.  Contains the key, as well as its own
 * location (rel,page,offset) which can supply the matching pointer.
 * leafkey is a flag to tell us if the entry is in a leaf node.
 */
typedef struct GISTENTRY
{
    Datum       key;
    Relation    rel;
    Page        page;
    OffsetNumber offset;
    bool        leafkey;
} GISTENTRY;
 
#define GistPageGetOpaque(page) ( (GISTPageOpaque) PageGetSpecialPointer(page) )
 
#define GistPageIsLeaf(page)    ( GistPageGetOpaque(page)->flags & F_LEAF)
#define GIST_LEAF(entry) (GistPageIsLeaf((entry)->page))
 
#define GistPageIsDeleted(page) ( GistPageGetOpaque(page)->flags & F_DELETED)
 
#define GistTuplesDeleted(page) ( GistPageGetOpaque(page)->flags & F_TUPLES_DELETED)
#define GistMarkTuplesDeleted(page) ( GistPageGetOpaque(page)->flags |= F_TUPLES_DELETED)
#define GistClearTuplesDeleted(page)    ( GistPageGetOpaque(page)->flags &= ~F_TUPLES_DELETED)
 
#define GistPageHasGarbage(page) ( GistPageGetOpaque(page)->flags & F_HAS_GARBAGE)
#define GistMarkPageHasGarbage(page) ( GistPageGetOpaque(page)->flags |= F_HAS_GARBAGE)
#define GistClearPageHasGarbage(page)   ( GistPageGetOpaque(page)->flags &= ~F_HAS_GARBAGE)
 
#define GistFollowRight(page) ( GistPageGetOpaque(page)->flags & F_FOLLOW_RIGHT)
#define GistMarkFollowRight(page) ( GistPageGetOpaque(page)->flags |= F_FOLLOW_RIGHT)
#define GistClearFollowRight(page)  ( GistPageGetOpaque(page)->flags &= ~F_FOLLOW_RIGHT)
 
#define GistPageGetNSN(page) ( PageXLogRecPtrGet(GistPageGetOpaque(page)->nsn))
#define GistPageSetNSN(page, val) ( PageXLogRecPtrSet(GistPageGetOpaque(page)->nsn, val))
 
 
/*
 * On a deleted page, we store this struct. A deleted page doesn't contain any
 * tuples, so we don't use the normal page layout with line pointers. Instead,
 * this struct is stored right after the standard page header. pd_lower points
 * to the end of this struct. If we add fields to this struct in the future, we
 * can distinguish the old and new formats by pd_lower.
 */
typedef struct GISTDeletedPageContents
{
    /* last xid which could see the page in a scan */
    FullTransactionId deleteXid;
} GISTDeletedPageContents;
 
static inline void
GistPageSetDeleted(Page page, FullTransactionId deletexid)
{
    Assert(PageIsEmpty(page));
 
    GistPageGetOpaque(page)->flags |= F_DELETED;
    ((PageHeader) page)->pd_lower = MAXALIGN(SizeOfPageHeaderData) + sizeof(GISTDeletedPageContents);
 
    ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid = deletexid;
}
 
static inline FullTransactionId
GistPageGetDeleteXid(Page page)
{
    Assert(GistPageIsDeleted(page));
 
    /* Is the deleteXid field present? */
    if (((PageHeader) page)->pd_lower >= MAXALIGN(SizeOfPageHeaderData) +
        offsetof(GISTDeletedPageContents, deleteXid) + sizeof(FullTransactionId))
    {
        return ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid;
    }
    else
        return FullTransactionIdFromEpochAndXid(0, FirstNormalTransactionId);
}
 
/*
 * Vector of GISTENTRY structs; user-defined methods union and picksplit
 * take it as one of their arguments
 */
typedef struct
{
    int32       n;              /* number of elements */
    GISTENTRY   vector[FLEXIBLE_ARRAY_MEMBER];
} GistEntryVector;
 
#define GEVHDRSZ    (offsetof(GistEntryVector, vector))
 
/*
 * macro to initialize a GISTENTRY
 */
#define gistentryinit(e, k, r, pg, o, l) \
    do { (e).key = (k); (e).rel = (r); (e).page = (pg); \
         (e).offset = (o); (e).leafkey = (l); } while (0)
 
extern StrategyNumber gisttranslatecmptype(CompareType cmptype, Oid opfamily);
 
#endif                          /* GIST_H */

F_LEAF

#define F_LEAF   (1 << 0) /* leaf page */

Definition at line 49 of file gist.h.

F_TUPLES_DELETED

#define F_TUPLES_DELETED

Value:

                                         (1 << 2)   /* some tuples on the page were
                                         * deleted */

Definition at line 51 of file gist.h.

GEVHDRSZ

#define GEVHDRSZ   (offsetof(GistEntryVector, vector))

Definition at line 240 of file gist.h.

GIST_COMPRESS_PROC

#define GIST_COMPRESS_PROC   3

Definition at line 34 of file gist.h.

GIST_CONSISTENT_PROC

#define GIST_CONSISTENT_PROC   1

Definition at line 32 of file gist.h.

GIST_DECOMPRESS_PROC

#define GIST_DECOMPRESS_PROC   4

Definition at line 35 of file gist.h.

GIST_DISTANCE_PROC

#define GIST_DISTANCE_PROC   8

Definition at line 39 of file gist.h.

GIST_EQUAL_PROC

#define GIST_EQUAL_PROC   7

Definition at line 38 of file gist.h.

GIST_FETCH_PROC

#define GIST_FETCH_PROC   9

Definition at line 40 of file gist.h.

GIST_LEAF

#define GIST_LEAF

(

entry

)

(GistPageIsLeaf((entry)->page))

Definition at line 171 of file gist.h.

GIST_OPTIONS_PROC

#define GIST_OPTIONS_PROC   10

Definition at line 41 of file gist.h.

GIST_PAGE_ID

#define GIST_PAGE_ID   0xFF81

Definition at line 112 of file gist.h.

GIST_PENALTY_PROC

#define GIST_PENALTY_PROC   5

Definition at line 36 of file gist.h.

GIST_PICKSPLIT_PROC

#define GIST_PICKSPLIT_PROC   6

Definition at line 37 of file gist.h.

GIST_SORTSUPPORT_PROC

#define GIST_SORTSUPPORT_PROC   11

Definition at line 42 of file gist.h.

GIST_TRANSLATE_CMPTYPE_PROC

#define GIST_TRANSLATE_CMPTYPE_PROC   12

Definition at line 43 of file gist.h.

GIST_UNION_PROC

#define GIST_UNION_PROC   2

Definition at line 33 of file gist.h.

GistBuildLSN

#define GistBuildLSN   ((XLogRecPtr) 1)

Definition at line 70 of file gist.h.

GistClearFollowRight

#define GistClearFollowRight

(

page

)

( GistPageGetOpaque(page)->flags &= ~F_FOLLOW_RIGHT)

Definition at line 185 of file gist.h.

GistClearPageHasGarbage

#define GistClearPageHasGarbage

(

page

)

( GistPageGetOpaque(page)->flags &= ~F_HAS_GARBAGE)

Definition at line 181 of file gist.h.

GistClearTuplesDeleted

#define GistClearTuplesDeleted

(

page

)

( GistPageGetOpaque(page)->flags &= ~F_TUPLES_DELETED)

Definition at line 177 of file gist.h.

gistentryinit

#define gistentryinit	(		e,
			k,
			r,
			pg,
			o,
			l
	)

Value:

    do { (e).key = (k); (e).rel = (r); (e).page = (pg); \
         (e).offset = (o); (e).leafkey = (l); } while (0)

Definition at line 245 of file gist.h.

GistFollowRight

#define GistFollowRight

(

page

)

( GistPageGetOpaque(page)->flags & F_FOLLOW_RIGHT)

Definition at line 183 of file gist.h.

GistMarkFollowRight

#define GistMarkFollowRight

(

page

)

( GistPageGetOpaque(page)->flags |= F_FOLLOW_RIGHT)

Definition at line 184 of file gist.h.

GistMarkPageHasGarbage

#define GistMarkPageHasGarbage

(

page

)

( GistPageGetOpaque(page)->flags |= F_HAS_GARBAGE)

Definition at line 180 of file gist.h.

GistMarkTuplesDeleted

#define GistMarkTuplesDeleted

(

page

)

( GistPageGetOpaque(page)->flags |= F_TUPLES_DELETED)

Definition at line 176 of file gist.h.

GISTMaxIndexKeySize

#define GISTMaxIndexKeySize    (GISTMaxIndexTupleSize - MAXALIGN(sizeof(IndexTupleData)))

Definition at line 103 of file gist.h.

GISTMaxIndexTupleSize

#define GISTMaxIndexTupleSize

Value:

    MAXALIGN_DOWN((BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)) / \
                  4 - sizeof(ItemIdData))

Definition at line 99 of file gist.h.

GISTNProcs

#define GISTNProcs   12

Definition at line 44 of file gist.h.

GistPageGetNSN

#define GistPageGetNSN

(

page

)

( PageXLogRecPtrGet(GistPageGetOpaque(page)->nsn))

Definition at line 187 of file gist.h.

GistPageGetOpaque

#define GistPageGetOpaque

(

page

)

( (GISTPageOpaque) PageGetSpecialPointer(page) )

Definition at line 168 of file gist.h.

GistPageHasGarbage

#define GistPageHasGarbage

(

page

)

( GistPageGetOpaque(page)->flags & F_HAS_GARBAGE)

Definition at line 179 of file gist.h.

GistPageIsDeleted

#define GistPageIsDeleted

(

page

)

( GistPageGetOpaque(page)->flags & F_DELETED)

Definition at line 173 of file gist.h.

GistPageIsLeaf

#define GistPageIsLeaf

(

page

)

( GistPageGetOpaque(page)->flags & F_LEAF)

Definition at line 170 of file gist.h.

GistPageSetNSN

#define GistPageSetNSN	(		page,
			val
	)		( PageXLogRecPtrSet(GistPageGetOpaque(page)->nsn, val))

Definition at line 188 of file gist.h.

GistTuplesDeleted

#define GistTuplesDeleted

(

page

)

( GistPageGetOpaque(page)->flags & F_TUPLES_DELETED)

Definition at line 175 of file gist.h.

Typedef Documentation

GIST_SPLITVEC

typedef struct GIST_SPLITVEC GIST_SPLITVEC

GISTDeletedPageContents

typedef struct GISTDeletedPageContents GISTDeletedPageContents

GISTENTRY

typedef struct GISTENTRY GISTENTRY

GistNSN

typedef XLogRecPtr GistNSN

Definition at line 63 of file gist.h.

GISTPageOpaque

typedef GISTPageOpaqueData* GISTPageOpaque

Definition at line 86 of file gist.h.

GISTPageOpaqueData

typedef struct GISTPageOpaqueData GISTPageOpaqueData

PageGistNSN

typedef PageXLogRecPtr PageGistNSN

Definition at line 76 of file gist.h.

Function Documentation

GistPageGetDeleteXid()

static FullTransactionId GistPageGetDeleteXid ( Page  page )

inlinestatic

Definition at line 216 of file gist.h.

{
    Assert(GistPageIsDeleted(page));
 
    /* Is the deleteXid field present? */
    if (((PageHeader) page)->pd_lower >= MAXALIGN(SizeOfPageHeaderData) +
        offsetof(GISTDeletedPageContents, deleteXid) + sizeof(FullTransactionId))
    {
        return ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid;
    }
    else

References Assert, fb(), FirstNormalTransactionId, FullTransactionIdFromEpochAndXid(), GistPageIsDeleted, MAXALIGN, PageGetContents(), and SizeOfPageHeaderData.

Referenced by gistNewBuffer(), and gistPageRecyclable().

GistPageSetDeleted()

static void GistPageSetDeleted ( Page  page, FullTransactionId  deletexid  )

inlinestatic

Definition at line 205 of file gist.h.

{
    Assert(PageIsEmpty(page));
 
    GistPageGetOpaque(page)->flags |= F_DELETED;
    ((PageHeader) page)->pd_lower = MAXALIGN(SizeOfPageHeaderData) + sizeof(GISTDeletedPageContents);
 

References Assert, F_DELETED, fb(), GistPageGetOpaque, MAXALIGN, PageGetContents(), PageIsEmpty(), and SizeOfPageHeaderData.

Referenced by gistdeletepage(), and gistRedoPageDelete().

gisttranslatecmptype()

StrategyNumber gisttranslatecmptype ( CompareType  cmptype, Oid  opfamily  )

extern

Definition at line 1098 of file gistutil.c.

{
    Oid         funcid;
    Datum       result;
 
    /* Check whether the function is provided. */
    funcid = get_opfamily_proc(opfamily, ANYOID, ANYOID, GIST_TRANSLATE_CMPTYPE_PROC);
    if (!OidIsValid(funcid))
        return InvalidStrategy;
 
    /* Ask the translation function */
    result = OidFunctionCall1Coll(funcid, InvalidOid, Int32GetDatum(cmptype));
    return DatumGetUInt16(result);
}

References DatumGetUInt16(), fb(), get_opfamily_proc(), GIST_TRANSLATE_CMPTYPE_PROC, Int32GetDatum(), InvalidOid, InvalidStrategy, OidFunctionCall1Coll(), and OidIsValid.

Referenced by gisthandler().