src/include/access/gist.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * gist.h
   4  *        The public API for GiST indexes. This API is exposed to
   5  *        individuals implementing GiST indexes, so backward-incompatible
   6  *        changes should be made with care.
   7  *
   8  *
   9  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
  10  * Portions Copyright (c) 1994, Regents of the University of California
  11  *
  12  * src/include/access/gist.h
  13  *
  14  *-------------------------------------------------------------------------
  15  */
  16 #ifndef GIST_H
  17 #define GIST_H
  18
  19 #include "access/itup.h"
  20 #include "access/stratnum.h"
  21 #include "access/transam.h"
  22 #include "access/xlog.h"
  23 #include "access/xlogdefs.h"
  24 #include "storage/block.h"
  25 #include "storage/bufpage.h"
  26 #include "utils/relcache.h"
  27
  28 /*
  29  * amproc indexes for GiST indexes.
  30  */
  31 #define GIST_CONSISTENT_PROC                    1
  32 #define GIST_UNION_PROC                                 2
  33 #define GIST_COMPRESS_PROC                              3
  34 #define GIST_DECOMPRESS_PROC                    4
  35 #define GIST_PENALTY_PROC                               5
  36 #define GIST_PICKSPLIT_PROC                             6
  37 #define GIST_EQUAL_PROC                                 7
  38 #define GIST_DISTANCE_PROC                              8
  39 #define GIST_FETCH_PROC                                 9
  40 #define GIST_OPTIONS_PROC                               10
  41 #define GIST_SORTSUPPORT_PROC                   11
  42 #define GIST_STRATNUM_PROC                              12
  43 #define GISTNProcs                                      12
  44
  45 /*
  46  * Page opaque data in a GiST index page.
  47  */
  48 #define F_LEAF                          (1 << 0)        /* leaf page */
  49 #define F_DELETED                       (1 << 1)        /* the page has been deleted */
  50 #define F_TUPLES_DELETED        (1 << 2)        /* some tuples on the page were
  51                                                                                  * deleted */
  52 #define F_FOLLOW_RIGHT          (1 << 3)        /* page to the right has no downlink */
  53 #define F_HAS_GARBAGE           (1 << 4)        /* some tuples on the page are dead,
  54                                                                                  * but not deleted yet */
  55
  56 /*
  57  * NSN (node sequence number) is a special-purpose LSN which is stored on each
  58  * index page in GISTPageOpaqueData and updated only during page splits.  By
  59  * recording the parent's LSN in GISTSearchItem.parentlsn, it is possible to
  60  * detect concurrent child page splits by checking if parentlsn < child's NSN,
  61  * and handle them properly.  The child page's LSN is insufficient for this
  62  * purpose since it is updated for every page change.
  63  */
  64 typedef XLogRecPtr GistNSN;
  65
  66 /*
  67  * A fake LSN / NSN value used during index builds. Must be smaller than any
  68  * real or fake (unlogged) LSN generated after the index build completes so
  69  * that all splits are considered complete.
  70  */
  71 #define GistBuildLSN    ((XLogRecPtr) 1)
  72
  73 /*
  74  * For on-disk compatibility with pre-9.3 servers, NSN is stored as two
  75  * 32-bit fields on disk, same as LSNs.
  76  */
  77 typedef PageXLogRecPtr PageGistNSN;
  78
  79 typedef struct GISTPageOpaqueData
  80 {
  81         PageGistNSN nsn;                        /* this value must change on page split */
  82         BlockNumber rightlink;          /* next page if any */
  83         uint16          flags;                  /* see bit definitions above */
  84         uint16          gist_page_id;   /* for identification of GiST indexes */
  85 } GISTPageOpaqueData;
  86
  87 typedef GISTPageOpaqueData *GISTPageOpaque;
  88
  89 /*
  90  * Maximum possible sizes for GiST index tuple and index key.  Calculation is
  91  * based on assumption that GiST page should fit at least 4 tuples.  In theory,
  92  * GiST index can be functional when page can fit 3 tuples.  But that seems
  93  * rather inefficient, so we use a bit conservative estimate.
  94  *
  95  * The maximum size of index key is true for unicolumn index.  Therefore, this
  96  * estimation should be used to figure out which maximum size of GiST index key
  97  * makes sense at all.  For multicolumn indexes, user might be able to tune
  98  * key size using opclass parameters.
  99  */
 100 #define GISTMaxIndexTupleSize   \
 101         MAXALIGN_DOWN((BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)) / \
 102                                   4 - sizeof(ItemIdData))
 103
 104 #define GISTMaxIndexKeySize     \
 105         (GISTMaxIndexTupleSize - MAXALIGN(sizeof(IndexTupleData)))
 106
 107 /*
 108  * The page ID is for the convenience of pg_filedump and similar utilities,
 109  * which otherwise would have a hard time telling pages of different index
 110  * types apart.  It should be the last 2 bytes on the page.  This is more or
 111  * less "free" due to alignment considerations.
 112  */
 113 #define GIST_PAGE_ID            0xFF81
 114
 115 /*
 116  * This is the Split Vector to be returned by the PickSplit method.
 117  * PickSplit should fill the indexes of tuples to go to the left side into
 118  * spl_left[], and those to go to the right into spl_right[] (note the method
 119  * is responsible for palloc'ing both of these arrays!).  The tuple counts
 120  * go into spl_nleft/spl_nright, and spl_ldatum/spl_rdatum must be set to
 121  * the union keys for each side.
 122  *
 123  * If spl_ldatum_exists and spl_rdatum_exists are true, then we are performing
 124  * a "secondary split" using a non-first index column.  In this case some
 125  * decisions have already been made about a page split, and the set of tuples
 126  * being passed to PickSplit is just the tuples about which we are undecided.
 127  * spl_ldatum/spl_rdatum then contain the union keys for the tuples already
 128  * chosen to go left or right.  Ideally the PickSplit method should take those
 129  * keys into account while deciding what to do with the remaining tuples, ie
 130  * it should try to "build out" from those unions so as to minimally expand
 131  * them.  If it does so, it should union the given tuples' keys into the
 132  * existing spl_ldatum/spl_rdatum values rather than just setting those values
 133  * from scratch, and then set spl_ldatum_exists/spl_rdatum_exists to false to
 134  * show it has done this.
 135  *
 136  * If the PickSplit method fails to clear spl_ldatum_exists/spl_rdatum_exists,
 137  * the core GiST code will make its own decision about how to merge the
 138  * secondary-split results with the previously-chosen tuples, and will then
 139  * recompute the union keys from scratch.  This is a workable though often not
 140  * optimal approach.
 141  */
 142 typedef struct GIST_SPLITVEC
 143 {
 144         OffsetNumber *spl_left;         /* array of entries that go left */
 145         int                     spl_nleft;              /* size of this array */
 146         Datum           spl_ldatum;             /* Union of keys in spl_left */
 147         bool            spl_ldatum_exists;      /* true, if spl_ldatum already exists. */
 148
 149         OffsetNumber *spl_right;        /* array of entries that go right */
 150         int                     spl_nright;             /* size of the array */
 151         Datum           spl_rdatum;             /* Union of keys in spl_right */
 152         bool            spl_rdatum_exists;      /* true, if spl_rdatum already exists. */
 153 } GIST_SPLITVEC;
 154
 155 /*
 156  * An entry on a GiST node.  Contains the key, as well as its own
 157  * location (rel,page,offset) which can supply the matching pointer.
 158  * leafkey is a flag to tell us if the entry is in a leaf node.
 159  */
 160 typedef struct GISTENTRY
 161 {
 162         Datum           key;
 163         Relation        rel;
 164         Page            page;
 165         OffsetNumber offset;
 166         bool            leafkey;
 167 } GISTENTRY;
 168
 169 #define GistPageGetOpaque(page) ( (GISTPageOpaque) PageGetSpecialPointer(page) )
 170
 171 #define GistPageIsLeaf(page)    ( GistPageGetOpaque(page)->flags & F_LEAF)
 172 #define GIST_LEAF(entry) (GistPageIsLeaf((entry)->page))
 173
 174 #define GistPageIsDeleted(page) ( GistPageGetOpaque(page)->flags & F_DELETED)
 175
 176 #define GistTuplesDeleted(page) ( GistPageGetOpaque(page)->flags & F_TUPLES_DELETED)
 177 #define GistMarkTuplesDeleted(page) ( GistPageGetOpaque(page)->flags |= F_TUPLES_DELETED)
 178 #define GistClearTuplesDeleted(page)    ( GistPageGetOpaque(page)->flags &= ~F_TUPLES_DELETED)
 179
 180 #define GistPageHasGarbage(page) ( GistPageGetOpaque(page)->flags & F_HAS_GARBAGE)
 181 #define GistMarkPageHasGarbage(page) ( GistPageGetOpaque(page)->flags |= F_HAS_GARBAGE)
 182 #define GistClearPageHasGarbage(page)   ( GistPageGetOpaque(page)->flags &= ~F_HAS_GARBAGE)
 183
 184 #define GistFollowRight(page) ( GistPageGetOpaque(page)->flags & F_FOLLOW_RIGHT)
 185 #define GistMarkFollowRight(page) ( GistPageGetOpaque(page)->flags |= F_FOLLOW_RIGHT)
 186 #define GistClearFollowRight(page)      ( GistPageGetOpaque(page)->flags &= ~F_FOLLOW_RIGHT)
 187
 188 #define GistPageGetNSN(page) ( PageXLogRecPtrGet(GistPageGetOpaque(page)->nsn))
 189 #define GistPageSetNSN(page, val) ( PageXLogRecPtrSet(GistPageGetOpaque(page)->nsn, val))
 190
 191
 192 /*
 193  * On a deleted page, we store this struct. A deleted page doesn't contain any
 194  * tuples, so we don't use the normal page layout with line pointers. Instead,
 195  * this struct is stored right after the standard page header. pd_lower points
 196  * to the end of this struct. If we add fields to this struct in the future, we
 197  * can distinguish the old and new formats by pd_lower.
 198  */
 199 typedef struct GISTDeletedPageContents
 200 {
 201         /* last xid which could see the page in a scan */
 202         FullTransactionId deleteXid;
 203 } GISTDeletedPageContents;
 204
 205 static inline void
 206 GistPageSetDeleted(Page page, FullTransactionId deletexid)
 207 {
 208         Assert(PageIsEmpty(page));
 209
 210         GistPageGetOpaque(page)->flags |= F_DELETED;
 211         ((PageHeader) page)->pd_lower = MAXALIGN(SizeOfPageHeaderData) + sizeof(GISTDeletedPageContents);
 212
 213         ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid = deletexid;
 214 }
 215
 216 static inline FullTransactionId
 217 GistPageGetDeleteXid(Page page)
 218 {
 219         Assert(GistPageIsDeleted(page));
 220
 221         /* Is the deleteXid field present? */
 222         if (((PageHeader) page)->pd_lower >= MAXALIGN(SizeOfPageHeaderData) +
 223                 offsetof(GISTDeletedPageContents, deleteXid) + sizeof(FullTransactionId))
 224         {
 225                 return ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid;
 226         }
 227         else
 228                 return FullTransactionIdFromEpochAndXid(0, FirstNormalTransactionId);
 229 }
 230
 231 /*
 232  * Vector of GISTENTRY structs; user-defined methods union and picksplit
 233  * take it as one of their arguments
 234  */
 235 typedef struct
 236 {
 237         int32           n;                              /* number of elements */
 238         GISTENTRY       vector[FLEXIBLE_ARRAY_MEMBER];
 239 } GistEntryVector;
 240
 241 #define GEVHDRSZ        (offsetof(GistEntryVector, vector))
 242
 243 /*
 244  * macro to initialize a GISTENTRY
 245  */
 246 #define gistentryinit(e, k, r, pg, o, l) \
 247         do { (e).key = (k); (e).rel = (r); (e).page = (pg); \
 248                  (e).offset = (o); (e).leafkey = (l); } while (0)
 249
 250 extern StrategyNumber GistTranslateStratnum(Oid opclass, StrategyNumber strat);
 251
 252 #endif                                                  /* GIST_H */