Header And Logo

PostgreSQL
| The world's most advanced open source database.

gist.h

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * gist.h
00004  *    The public API for GiST indexes. This API is exposed to
00005  *    individuals implementing GiST indexes, so backward-incompatible
00006  *    changes should be made with care.
00007  *
00008  *
00009  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00010  * Portions Copyright (c) 1994, Regents of the University of California
00011  *
00012  * src/include/access/gist.h
00013  *
00014  *-------------------------------------------------------------------------
00015  */
00016 #ifndef GIST_H
00017 #define GIST_H
00018 
00019 #include "access/xlog.h"
00020 #include "access/xlogdefs.h"
00021 #include "storage/block.h"
00022 #include "storage/bufpage.h"
00023 #include "utils/relcache.h"
00024 
00025 /*
00026  * amproc indexes for GiST indexes.
00027  */
00028 #define GIST_CONSISTENT_PROC            1
00029 #define GIST_UNION_PROC                 2
00030 #define GIST_COMPRESS_PROC              3
00031 #define GIST_DECOMPRESS_PROC            4
00032 #define GIST_PENALTY_PROC               5
00033 #define GIST_PICKSPLIT_PROC             6
00034 #define GIST_EQUAL_PROC                 7
00035 #define GIST_DISTANCE_PROC              8
00036 #define GISTNProcs                      8
00037 
00038 /*
00039  * strategy numbers for GiST opclasses that want to implement the old
00040  * RTREE behavior.
00041  */
00042 #define RTLeftStrategyNumber            1
00043 #define RTOverLeftStrategyNumber        2
00044 #define RTOverlapStrategyNumber         3
00045 #define RTOverRightStrategyNumber       4
00046 #define RTRightStrategyNumber           5
00047 #define RTSameStrategyNumber            6
00048 #define RTContainsStrategyNumber        7       /* for @> */
00049 #define RTContainedByStrategyNumber     8       /* for <@ */
00050 #define RTOverBelowStrategyNumber       9
00051 #define RTBelowStrategyNumber           10
00052 #define RTAboveStrategyNumber           11
00053 #define RTOverAboveStrategyNumber       12
00054 #define RTOldContainsStrategyNumber     13      /* for old spelling of @> */
00055 #define RTOldContainedByStrategyNumber  14      /* for old spelling of <@ */
00056 #define RTKNNSearchStrategyNumber       15
00057 
00058 /*
00059  * Page opaque data in a GiST index page.
00060  */
00061 #define F_LEAF              (1 << 0)    /* leaf page */
00062 #define F_DELETED           (1 << 1)    /* the page has been deleted */
00063 #define F_TUPLES_DELETED    (1 << 2)    /* some tuples on the page are dead */
00064 #define F_FOLLOW_RIGHT      (1 << 3)    /* page to the right has no downlink */
00065 
00066 typedef XLogRecPtr GistNSN;
00067 /*
00068  * For on-disk compatibility with pre-9.3 servers, NSN is stored as two
00069  * 32-bit fields on disk, same as LSNs.
00070  */
00071 typedef PageXLogRecPtr PageGistNSN;
00072 
00073 typedef struct GISTPageOpaqueData
00074 {
00075     PageGistNSN nsn;            /* this value must change on page split */
00076     BlockNumber rightlink;      /* next page if any */
00077     uint16      flags;          /* see bit definitions above */
00078     uint16      gist_page_id;   /* for identification of GiST indexes */
00079 } GISTPageOpaqueData;
00080 
00081 typedef GISTPageOpaqueData *GISTPageOpaque;
00082 
00083 /*
00084  * The page ID is for the convenience of pg_filedump and similar utilities,
00085  * which otherwise would have a hard time telling pages of different index
00086  * types apart.  It should be the last 2 bytes on the page.  This is more or
00087  * less "free" due to alignment considerations.
00088  */
00089 #define GIST_PAGE_ID        0xFF81
00090 
00091 /*
00092  * This is the Split Vector to be returned by the PickSplit method.
00093  * PickSplit should fill the indexes of tuples to go to the left side into
00094  * spl_left[], and those to go to the right into spl_right[] (note the method
00095  * is responsible for palloc'ing both of these arrays!).  The tuple counts
00096  * go into spl_nleft/spl_nright, and spl_ldatum/spl_rdatum must be set to
00097  * the union keys for each side.
00098  *
00099  * If spl_ldatum_exists and spl_rdatum_exists are true, then we are performing
00100  * a "secondary split" using a non-first index column.  In this case some
00101  * decisions have already been made about a page split, and the set of tuples
00102  * being passed to PickSplit is just the tuples about which we are undecided.
00103  * spl_ldatum/spl_rdatum then contain the union keys for the tuples already
00104  * chosen to go left or right.  Ideally the PickSplit method should take those
00105  * keys into account while deciding what to do with the remaining tuples, ie
00106  * it should try to "build out" from those unions so as to minimally expand
00107  * them.  If it does so, it should union the given tuples' keys into the
00108  * existing spl_ldatum/spl_rdatum values rather than just setting those values
00109  * from scratch, and then set spl_ldatum_exists/spl_rdatum_exists to false to
00110  * show it has done this.
00111  *
00112  * If the PickSplit method fails to clear spl_ldatum_exists/spl_rdatum_exists,
00113  * the core GiST code will make its own decision about how to merge the
00114  * secondary-split results with the previously-chosen tuples, and will then
00115  * recompute the union keys from scratch.  This is a workable though often not
00116  * optimal approach.
00117  */
00118 typedef struct GIST_SPLITVEC
00119 {
00120     OffsetNumber *spl_left;     /* array of entries that go left */
00121     int         spl_nleft;      /* size of this array */
00122     Datum       spl_ldatum;     /* Union of keys in spl_left */
00123     bool        spl_ldatum_exists;      /* true, if spl_ldatum already exists. */
00124 
00125     OffsetNumber *spl_right;    /* array of entries that go right */
00126     int         spl_nright;     /* size of the array */
00127     Datum       spl_rdatum;     /* Union of keys in spl_right */
00128     bool        spl_rdatum_exists;      /* true, if spl_rdatum already exists. */
00129 } GIST_SPLITVEC;
00130 
00131 /*
00132  * An entry on a GiST node.  Contains the key, as well as its own
00133  * location (rel,page,offset) which can supply the matching pointer.
00134  * leafkey is a flag to tell us if the entry is in a leaf node.
00135  */
00136 typedef struct GISTENTRY
00137 {
00138     Datum       key;
00139     Relation    rel;
00140     Page        page;
00141     OffsetNumber offset;
00142     bool        leafkey;
00143 } GISTENTRY;
00144 
00145 #define GistPageGetOpaque(page) ( (GISTPageOpaque) PageGetSpecialPointer(page) )
00146 
00147 #define GistPageIsLeaf(page)    ( GistPageGetOpaque(page)->flags & F_LEAF)
00148 #define GIST_LEAF(entry) (GistPageIsLeaf((entry)->page))
00149 #define GistPageSetLeaf(page)   ( GistPageGetOpaque(page)->flags |= F_LEAF)
00150 #define GistPageSetNonLeaf(page)    ( GistPageGetOpaque(page)->flags &= ~F_LEAF)
00151 
00152 #define GistPageIsDeleted(page) ( GistPageGetOpaque(page)->flags & F_DELETED)
00153 #define GistPageSetDeleted(page)    ( GistPageGetOpaque(page)->flags |= F_DELETED)
00154 #define GistPageSetNonDeleted(page) ( GistPageGetOpaque(page)->flags &= ~F_DELETED)
00155 
00156 #define GistTuplesDeleted(page) ( GistPageGetOpaque(page)->flags & F_TUPLES_DELETED)
00157 #define GistMarkTuplesDeleted(page) ( GistPageGetOpaque(page)->flags |= F_TUPLES_DELETED)
00158 #define GistClearTuplesDeleted(page)    ( GistPageGetOpaque(page)->flags &= ~F_TUPLES_DELETED)
00159 
00160 #define GistFollowRight(page) ( GistPageGetOpaque(page)->flags & F_FOLLOW_RIGHT)
00161 #define GistMarkFollowRight(page) ( GistPageGetOpaque(page)->flags |= F_FOLLOW_RIGHT)
00162 #define GistClearFollowRight(page)  ( GistPageGetOpaque(page)->flags &= ~F_FOLLOW_RIGHT)
00163 
00164 #define GistPageGetNSN(page) ( PageXLogRecPtrGet(GistPageGetOpaque(page)->nsn))
00165 #define GistPageSetNSN(page, val) ( PageXLogRecPtrSet(GistPageGetOpaque(page)->nsn, val))
00166 
00167 /*
00168  * Vector of GISTENTRY structs; user-defined methods union and picksplit
00169  * take it as one of their arguments
00170  */
00171 typedef struct
00172 {
00173     int32       n;              /* number of elements */
00174     GISTENTRY   vector[FLEXIBLE_ARRAY_MEMBER];
00175 } GistEntryVector;
00176 
00177 #define GEVHDRSZ    (offsetof(GistEntryVector, vector))
00178 
00179 /*
00180  * macro to initialize a GISTENTRY
00181  */
00182 #define gistentryinit(e, k, r, pg, o, l) \
00183     do { (e).key = (k); (e).rel = (r); (e).page = (pg); \
00184          (e).offset = (o); (e).leafkey = (l); } while (0)
00185 
00186 #endif   /* GIST_H */