Age Owner Branch data TLA 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-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
1726 heikki.linnakangas@i 206 :CBC 324 : GistPageSetDeleted(Page page, FullTransactionId deletexid)
207 : : {
208 [ - + ]: 324 : Assert(PageIsEmpty(page));
209 : :
210 : 324 : GistPageGetOpaque(page)->flags |= F_DELETED;
211 : 324 : ((PageHeader) page)->pd_lower = MAXALIGN(SizeOfPageHeaderData) + sizeof(GISTDeletedPageContents);
212 : :
213 : 324 : ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid = deletexid;
214 : 324 : }
215 : :
216 : : static inline FullTransactionId
1726 heikki.linnakangas@i 217 :UBC 0 : GistPageGetDeleteXid(Page page)
218 : : {
219 [ # # ]: 0 : Assert(GistPageIsDeleted(page));
220 : :
221 : : /* Is the deleteXid field present? */
222 [ # # ]: 0 : if (((PageHeader) page)->pd_lower >= MAXALIGN(SizeOfPageHeaderData) +
223 : : offsetof(GISTDeletedPageContents, deleteXid) + sizeof(FullTransactionId))
224 : : {
225 : 0 : return ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid;
226 : : }
227 : : else
228 : 0 : 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 */
|
