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-2018, 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/xlog.h" 20 #include "access/xlogdefs.h" 21 #include "storage/block.h" 22 #include "storage/bufpage.h" 23 #include "utils/relcache.h" 24 25 /* 26 * amproc indexes for GiST indexes. 27 */ 28 #define GIST_CONSISTENT_PROC 1 29 #define GIST_UNION_PROC 2 30 #define GIST_COMPRESS_PROC 3 31 #define GIST_DECOMPRESS_PROC 4 32 #define GIST_PENALTY_PROC 5 33 #define GIST_PICKSPLIT_PROC 6 34 #define GIST_EQUAL_PROC 7 35 #define GIST_DISTANCE_PROC 8 36 #define GIST_FETCH_PROC 9 37 #define GISTNProcs 9 38 39 /* 40 * Page opaque data in a GiST index page. 41 */ 42 #define F_LEAF (1 << 0) /* leaf page */ 43 #define F_DELETED (1 << 1) /* the page has been deleted */ 44 #define F_TUPLES_DELETED (1 << 2) /* some tuples on the page were 45 * deleted */ 46 #define F_FOLLOW_RIGHT (1 << 3) /* page to the right has no downlink */ 47 #define F_HAS_GARBAGE (1 << 4) /* some tuples on the page are dead, 48 * but not deleted yet */ 49 50 typedef XLogRecPtr GistNSN; 51 52 /* 53 * For on-disk compatibility with pre-9.3 servers, NSN is stored as two 54 * 32-bit fields on disk, same as LSNs. 55 */ 56 typedef PageXLogRecPtr PageGistNSN; 57 58 typedef struct GISTPageOpaqueData 59 { 60 PageGistNSN nsn; /* this value must change on page split */ 61 BlockNumber rightlink; /* next page if any */ 62 uint16 flags; /* see bit definitions above */ 63 uint16 gist_page_id; /* for identification of GiST indexes */ 64 } GISTPageOpaqueData; 65 66 typedef GISTPageOpaqueData *GISTPageOpaque; 67 68 /* 69 * The page ID is for the convenience of pg_filedump and similar utilities, 70 * which otherwise would have a hard time telling pages of different index 71 * types apart. It should be the last 2 bytes on the page. This is more or 72 * less "free" due to alignment considerations. 73 */ 74 #define GIST_PAGE_ID 0xFF81 75 76 /* 77 * This is the Split Vector to be returned by the PickSplit method. 78 * PickSplit should fill the indexes of tuples to go to the left side into 79 * spl_left[], and those to go to the right into spl_right[] (note the method 80 * is responsible for palloc'ing both of these arrays!). The tuple counts 81 * go into spl_nleft/spl_nright, and spl_ldatum/spl_rdatum must be set to 82 * the union keys for each side. 83 * 84 * If spl_ldatum_exists and spl_rdatum_exists are true, then we are performing 85 * a "secondary split" using a non-first index column. In this case some 86 * decisions have already been made about a page split, and the set of tuples 87 * being passed to PickSplit is just the tuples about which we are undecided. 88 * spl_ldatum/spl_rdatum then contain the union keys for the tuples already 89 * chosen to go left or right. Ideally the PickSplit method should take those 90 * keys into account while deciding what to do with the remaining tuples, ie 91 * it should try to "build out" from those unions so as to minimally expand 92 * them. If it does so, it should union the given tuples' keys into the 93 * existing spl_ldatum/spl_rdatum values rather than just setting those values 94 * from scratch, and then set spl_ldatum_exists/spl_rdatum_exists to false to 95 * show it has done this. 96 * 97 * If the PickSplit method fails to clear spl_ldatum_exists/spl_rdatum_exists, 98 * the core GiST code will make its own decision about how to merge the 99 * secondary-split results with the previously-chosen tuples, and will then 100 * recompute the union keys from scratch. This is a workable though often not 101 * optimal approach. 102 */ 103 typedef struct GIST_SPLITVEC 104 { 105 OffsetNumber *spl_left; /* array of entries that go left */ 106 int spl_nleft; /* size of this array */ 107 Datum spl_ldatum; /* Union of keys in spl_left */ 108 bool spl_ldatum_exists; /* true, if spl_ldatum already exists. */ 109 110 OffsetNumber *spl_right; /* array of entries that go right */ 111 int spl_nright; /* size of the array */ 112 Datum spl_rdatum; /* Union of keys in spl_right */ 113 bool spl_rdatum_exists; /* true, if spl_rdatum already exists. */ 114 } GIST_SPLITVEC; 115 116 /* 117 * An entry on a GiST node. Contains the key, as well as its own 118 * location (rel,page,offset) which can supply the matching pointer. 119 * leafkey is a flag to tell us if the entry is in a leaf node. 120 */ 121 typedef struct GISTENTRY 122 { 123 Datum key; 124 Relation rel; 125 Page page; 126 OffsetNumber offset; 127 bool leafkey; 128 } GISTENTRY; 129 130 #define GistPageGetOpaque(page) ( (GISTPageOpaque) PageGetSpecialPointer(page) ) 131 132 #define GistPageIsLeaf(page) ( GistPageGetOpaque(page)->flags & F_LEAF) 133 #define GIST_LEAF(entry) (GistPageIsLeaf((entry)->page)) 134 135 #define GistPageIsDeleted(page) ( GistPageGetOpaque(page)->flags & F_DELETED) 136 #define GistPageSetDeleted(page) ( GistPageGetOpaque(page)->flags |= F_DELETED) 137 #define GistPageSetNonDeleted(page) ( GistPageGetOpaque(page)->flags &= ~F_DELETED) 138 139 #define GistTuplesDeleted(page) ( GistPageGetOpaque(page)->flags & F_TUPLES_DELETED) 140 #define GistMarkTuplesDeleted(page) ( GistPageGetOpaque(page)->flags |= F_TUPLES_DELETED) 141 #define GistClearTuplesDeleted(page) ( GistPageGetOpaque(page)->flags &= ~F_TUPLES_DELETED) 142 143 #define GistPageHasGarbage(page) ( GistPageGetOpaque(page)->flags & F_HAS_GARBAGE) 144 #define GistMarkPageHasGarbage(page) ( GistPageGetOpaque(page)->flags |= F_HAS_GARBAGE) 145 #define GistClearPageHasGarbage(page) ( GistPageGetOpaque(page)->flags &= ~F_HAS_GARBAGE) 146 147 #define GistFollowRight(page) ( GistPageGetOpaque(page)->flags & F_FOLLOW_RIGHT) 148 #define GistMarkFollowRight(page) ( GistPageGetOpaque(page)->flags |= F_FOLLOW_RIGHT) 149 #define GistClearFollowRight(page) ( GistPageGetOpaque(page)->flags &= ~F_FOLLOW_RIGHT) 150 151 #define GistPageGetNSN(page) ( PageXLogRecPtrGet(GistPageGetOpaque(page)->nsn)) 152 #define GistPageSetNSN(page, val) ( PageXLogRecPtrSet(GistPageGetOpaque(page)->nsn, val)) 153 154 /* 155 * Vector of GISTENTRY structs; user-defined methods union and picksplit 156 * take it as one of their arguments 157 */ 158 typedef struct 159 { 160 int32 n; /* number of elements */ 161 GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER]; 162 } GistEntryVector; 163 164 #define GEVHDRSZ (offsetof(GistEntryVector, vector)) 165 166 /* 167 * macro to initialize a GISTENTRY 168 */ 169 #define gistentryinit(e, k, r, pg, o, l) \ 170 do { (e).key = (k); (e).rel = (r); (e).page = (pg); \ 171 (e).offset = (o); (e).leafkey = (l); } while (0) 172 173 #endif /* GIST_H */ 174