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