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