PostgreSQL Source Code  git master
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-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 
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  */
65 
66 typedef 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 */
73 
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  */
111 typedef 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  */
129 typedef struct GISTENTRY
130 {
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  */
169 {
170  /* last xid which could see the page in a scan */
173 
174 static inline void
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 
185 static inline FullTransactionId
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
198 }
199 
200 /*
201  * Vector of GISTENTRY structs; user-defined methods union and picksplit
202  * take it as one of their arguments
203  */
204 typedef struct
205 {
206  int32 n; /* number of elements */
207  GISTENTRY vector[FLEXIBLE_ARRAY_MEMBER];
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 */
Relation rel
Definition: gist.h:132
bool spl_rdatum_exists
Definition: gist.h:121
#define GistPageIsDeleted(page)
Definition: gist.h:143
#define PageIsEmpty(page)
Definition: bufpage.h:222
struct GIST_SPLITVEC GIST_SPLITVEC
OffsetNumber * spl_left
Definition: gist.h:113
Datum spl_rdatum
Definition: gist.h:120
int32 n
Definition: gist.h:206
bool spl_ldatum_exists
Definition: gist.h:116
uint32 BlockNumber
Definition: block.h:31
int spl_nleft
Definition: gist.h:114
#define SizeOfPageHeaderData
Definition: bufpage.h:216
signed int int32
Definition: c.h:346
uint16 OffsetNumber
Definition: off.h:24
Page page
Definition: gist.h:133
uint16 gist_page_id
Definition: gist.h:71
PageXLogRecPtr PageGistNSN
Definition: gist.h:64
unsigned short uint16
Definition: c.h:357
struct GISTENTRY GISTENTRY
#define FirstNormalTransactionId
Definition: transam.h:34
int spl_nright
Definition: gist.h:119
Datum key
Definition: gist.h:131
struct GISTPageOpaqueData GISTPageOpaqueData
uint16 flags
Definition: gist.h:70
static void GistPageSetDeleted(Page page, FullTransactionId deletexid)
Definition: gist.h:175
bool leafkey
Definition: gist.h:135
FullTransactionId deleteXid
Definition: gist.h:171
#define PageGetContents(page)
Definition: bufpage.h:246
uintptr_t Datum
Definition: postgres.h:367
#define GistPageGetOpaque(page)
Definition: gist.h:138
PageHeaderData * PageHeader
Definition: bufpage.h:166
struct GISTDeletedPageContents GISTDeletedPageContents
Datum spl_ldatum
Definition: gist.h:115
uint64 XLogRecPtr
Definition: xlogdefs.h:21
#define Assert(condition)
Definition: c.h:732
OffsetNumber * spl_right
Definition: gist.h:118
static FullTransactionId FullTransactionIdFromEpochAndXid(uint32 epoch, TransactionId xid)
Definition: transam.h:65
#define MAXALIGN(LEN)
Definition: c.h:685
XLogRecPtr GistNSN
Definition: gist.h:51
PageGistNSN nsn
Definition: gist.h:68
static FullTransactionId GistPageGetDeleteXid(Page page)
Definition: gist.h:186
GISTPageOpaqueData * GISTPageOpaque
Definition: gist.h:74
BlockNumber rightlink
Definition: gist.h:69
#define F_DELETED
Definition: gist.h:44
OffsetNumber offset
Definition: gist.h:134
#define offsetof(type, field)
Definition: c.h:655
Pointer Page
Definition: bufpage.h:78