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-2021, 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
GistPageSetDeleted(Page page,FullTransactionId deletexid)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
GistPageGetDeleteXid(Page page)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 */
249