PostgreSQL Source Code  git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
gist.h
Go to the documentation of this file.
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  */
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 */
86 
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 {
166  bool leafkey;
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 */
204 
205 static inline void
207 {
208  Assert(PageIsEmpty(page));
209 
210  GistPageGetOpaque(page)->flags |= F_DELETED;
211  ((PageHeader) page)->pd_lower = MAXALIGN(SizeOfPageHeaderData) + sizeof(GISTDeletedPageContents);
212 
213  ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid = deletexid;
214 }
215 
216 static inline FullTransactionId
218 {
219  Assert(GistPageIsDeleted(page));
220 
221  /* Is the deleteXid field present? */
222  if (((PageHeader) page)->pd_lower >= MAXALIGN(SizeOfPageHeaderData) +
223  offsetof(GISTDeletedPageContents, deleteXid) + sizeof(FullTransactionId))
224  {
225  return ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid;
226  }
227  else
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 */
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 
251 
252 #endif /* GIST_H */
uint32 BlockNumber
Definition: block.h:31
PageHeaderData * PageHeader
Definition: bufpage.h:173
static bool PageIsEmpty(Page page)
Definition: bufpage.h:223
static char * PageGetContents(Page page)
Definition: bufpage.h:257
Pointer Page
Definition: bufpage.h:81
#define SizeOfPageHeaderData
Definition: bufpage.h:216
unsigned short uint16
Definition: c.h:517
#define MAXALIGN(LEN)
Definition: c.h:816
signed int int32
Definition: c.h:508
#define Assert(condition)
Definition: c.h:863
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:413
GISTPageOpaqueData * GISTPageOpaque
Definition: gist.h:85
PageXLogRecPtr PageGistNSN
Definition: gist.h:75
struct GISTENTRY GISTENTRY
struct GISTPageOpaqueData GISTPageOpaqueData
static void GistPageSetDeleted(Page page, FullTransactionId deletexid)
Definition: gist.h:204
struct GISTDeletedPageContents GISTDeletedPageContents
struct GIST_SPLITVEC GIST_SPLITVEC
StrategyNumber GistTranslateStratnum(Oid opclass, StrategyNumber strat)
Definition: gistutil.c:1081
static FullTransactionId GistPageGetDeleteXid(Page page)
Definition: gist.h:215
#define GistPageIsDeleted(page)
Definition: gist.h:172
#define GistPageGetOpaque(page)
Definition: gist.h:167
#define F_DELETED
Definition: gist.h:49
XLogRecPtr GistNSN
Definition: gist.h:62
uint16 OffsetNumber
Definition: off.h:24
uintptr_t Datum
Definition: postgres.h:64
unsigned int Oid
Definition: postgres_ext.h:31
uint16 StrategyNumber
Definition: stratnum.h:22
FullTransactionId deleteXid
Definition: gist.h:200
OffsetNumber offset
Definition: gist.h:163
Datum key
Definition: gist.h:160
Page page
Definition: gist.h:162
Relation rel
Definition: gist.h:161
bool leafkey
Definition: gist.h:164
PageGistNSN nsn
Definition: gist.h:79
uint16 gist_page_id
Definition: gist.h:82
BlockNumber rightlink
Definition: gist.h:80
uint16 flags
Definition: gist.h:81
bool spl_ldatum_exists
Definition: gist.h:145
bool spl_rdatum_exists
Definition: gist.h:150
int spl_nleft
Definition: gist.h:143
OffsetNumber * spl_right
Definition: gist.h:147
Datum spl_ldatum
Definition: gist.h:144
Datum spl_rdatum
Definition: gist.h:149
int spl_nright
Definition: gist.h:148
OffsetNumber * spl_left
Definition: gist.h:142
#define FirstNormalTransactionId
Definition: transam.h:34
static FullTransactionId FullTransactionIdFromEpochAndXid(uint32 epoch, TransactionId xid)
Definition: transam.h:71
uint64 XLogRecPtr
Definition: xlogdefs.h:21