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