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-2025, 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_STRATNUM_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 */
65typedef 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 */
79
80typedef struct GISTPageOpaqueData
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 */
87
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 */
143typedef struct GIST_SPLITVEC
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. */
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. */
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 */
161typedef struct GISTENTRY
167 bool leafkey;
169
170#define GistPageGetOpaque(page) ( (GISTPageOpaque) PageGetSpecialPointer(page) )
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)
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)
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)
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)
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 */
200typedef struct GISTDeletedPageContents
202 /* last xid which could see the page in a scan */
206static inline void
208{
209 Assert(PageIsEmpty(page));
210
211 GistPageGetOpaque(page)->flags |= F_DELETED;
212 ((PageHeader) page)->pd_lower = MAXALIGN(SizeOfPageHeaderData) + sizeof(GISTDeletedPageContents);
213
214 ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid = deletexid;
215}
217static inline FullTransactionId
219{
221
222 /* Is the deleteXid field present? */
223 if (((PageHeader) page)->pd_lower >= MAXALIGN(SizeOfPageHeaderData) +
224 offsetof(GISTDeletedPageContents, deleteXid) + sizeof(FullTransactionId))
225 {
226 return ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid;
227 }
228 else
230}
231
232/*
233 * Vector of GISTENTRY structs; user-defined methods union and picksplit
234 * take it as one of their arguments
235 */
236typedef struct
238 int32 n; /* number of elements */
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
251extern StrategyNumber gisttranslatecmptype(CompareType cmptype, Oid opfamily, Oid opcintype);
252
253#endif /* GIST_H */
uint32 BlockNumber
Definition: block.h:31
static bool PageIsEmpty(const PageData *page)
Definition: bufpage.h:224
PageHeaderData * PageHeader
Definition: bufpage.h:174
#define SizeOfPageHeaderData
Definition: bufpage.h:217
static char * PageGetContents(Page page)
Definition: bufpage.h:258
PageData * Page
Definition: bufpage.h:82
#define MAXALIGN(LEN)
Definition: c.h:768
#define Assert(condition)
Definition: c.h:815
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:420
int32_t int32
Definition: c.h:484
uint16_t uint16
Definition: c.h:487
CompareType
Definition: cmptype.h:32
GISTPageOpaqueData * GISTPageOpaque
Definition: gist.h:86
StrategyNumber gisttranslatecmptype(CompareType cmptype, Oid opfamily, Oid opcintype)
Definition: gistutil.c:1098
PageXLogRecPtr PageGistNSN
Definition: gist.h:76
struct GISTENTRY GISTENTRY
struct GISTPageOpaqueData GISTPageOpaqueData
static void GistPageSetDeleted(Page page, FullTransactionId deletexid)
Definition: gist.h:205
struct GISTDeletedPageContents GISTDeletedPageContents
struct GIST_SPLITVEC GIST_SPLITVEC
static FullTransactionId GistPageGetDeleteXid(Page page)
Definition: gist.h:216
#define GistPageIsDeleted(page)
Definition: gist.h:173
#define GistPageGetOpaque(page)
Definition: gist.h:168
#define F_DELETED
Definition: gist.h:50
XLogRecPtr GistNSN
Definition: gist.h:63
uint16 OffsetNumber
Definition: off.h:24
uintptr_t Datum
Definition: postgres.h:69
unsigned int Oid
Definition: postgres_ext.h:32
uint16 StrategyNumber
Definition: stratnum.h:22
FullTransactionId deleteXid
Definition: gist.h:201
OffsetNumber offset
Definition: gist.h:164
Datum key
Definition: gist.h:161
Page page
Definition: gist.h:163
Relation rel
Definition: gist.h:162
bool leafkey
Definition: gist.h:165
PageGistNSN nsn
Definition: gist.h:80
uint16 gist_page_id
Definition: gist.h:83
BlockNumber rightlink
Definition: gist.h:81
uint16 flags
Definition: gist.h:82
bool spl_ldatum_exists
Definition: gist.h:146
bool spl_rdatum_exists
Definition: gist.h:151
int spl_nleft
Definition: gist.h:144
OffsetNumber * spl_right
Definition: gist.h:148
Datum spl_ldatum
Definition: gist.h:145
Datum spl_rdatum
Definition: gist.h:150
int spl_nright
Definition: gist.h:149
OffsetNumber * spl_left
Definition: gist.h:143
#define FirstNormalTransactionId
Definition: transam.h:34
static FullTransactionId FullTransactionIdFromEpochAndXid(uint32 epoch, TransactionId xid)
Definition: transam.h:71
uint64 XLogRecPtr
Definition: xlogdefs.h:21