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
*/
65
typedef
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
*/
78
typedef
PageXLogRecPtr
PageGistNSN
;
79
80
typedef
struct
GISTPageOpaqueData
81
{
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 */
86
}
GISTPageOpaqueData
;
87
88
typedef
GISTPageOpaqueData
*
GISTPageOpaque
;
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
*/
143
typedef
struct
GIST_SPLITVEC
144
{
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. */
149
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. */
154
}
GIST_SPLITVEC
;
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
*/
161
typedef
struct
GISTENTRY
162
{
163
Datum
key
;
164
Relation
rel
;
165
Page
page
;
166
OffsetNumber
offset
;
167
bool
leafkey
;
168
}
GISTENTRY
;
169
170
#define GistPageGetOpaque(page) ( (GISTPageOpaque) PageGetSpecialPointer(page) )
171
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)
176
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)
180
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)
184
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)
188
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
*/
200
typedef
struct
GISTDeletedPageContents
201
{
202
/* last xid which could see the page in a scan */
203
FullTransactionId
deleteXid
;
204
}
GISTDeletedPageContents
;
205
206
static
inline
void
207
GistPageSetDeleted
(
Page
page,
FullTransactionId
deletexid)
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
}
216
217
static
inline
FullTransactionId
218
GistPageGetDeleteXid
(
Page
page)
219
{
220
Assert
(
GistPageIsDeleted
(page));
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
229
return
FullTransactionIdFromEpochAndXid
(0,
FirstNormalTransactionId
);
230
}
231
232
/*
233
* Vector of GISTENTRY structs; user-defined methods union and picksplit
234
* take it as one of their arguments
235
*/
236
typedef
struct
237
{
238
int32
n;
/* number of elements */
239
GISTENTRY
vector[
FLEXIBLE_ARRAY_MEMBER
];
240
}
GistEntryVector
;
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
251
extern
StrategyNumber
gisttranslatecmptype
(
CompareType
cmptype,
Oid
opfamily,
Oid
opcintype);
252
253
#endif
/* GIST_H */
block.h
BlockNumber
uint32 BlockNumber
Definition:
block.h:31
bufpage.h
PageIsEmpty
static bool PageIsEmpty(const PageData *page)
Definition:
bufpage.h:224
PageHeader
PageHeaderData * PageHeader
Definition:
bufpage.h:174
SizeOfPageHeaderData
#define SizeOfPageHeaderData
Definition:
bufpage.h:217
PageGetContents
static char * PageGetContents(Page page)
Definition:
bufpage.h:258
Page
PageData * Page
Definition:
bufpage.h:82
MAXALIGN
#define MAXALIGN(LEN)
Definition:
c.h:768
Assert
#define Assert(condition)
Definition:
c.h:815
FLEXIBLE_ARRAY_MEMBER
#define FLEXIBLE_ARRAY_MEMBER
Definition:
c.h:420
int32
int32_t int32
Definition:
c.h:484
uint16
uint16_t uint16
Definition:
c.h:487
CompareType
CompareType
Definition:
cmptype.h:32
GISTPageOpaque
GISTPageOpaqueData * GISTPageOpaque
Definition:
gist.h:86
gisttranslatecmptype
StrategyNumber gisttranslatecmptype(CompareType cmptype, Oid opfamily, Oid opcintype)
Definition:
gistutil.c:1098
PageGistNSN
PageXLogRecPtr PageGistNSN
Definition:
gist.h:76
GISTENTRY
struct GISTENTRY GISTENTRY
GISTPageOpaqueData
struct GISTPageOpaqueData GISTPageOpaqueData
GistPageSetDeleted
static void GistPageSetDeleted(Page page, FullTransactionId deletexid)
Definition:
gist.h:205
GISTDeletedPageContents
struct GISTDeletedPageContents GISTDeletedPageContents
GIST_SPLITVEC
struct GIST_SPLITVEC GIST_SPLITVEC
GistPageGetDeleteXid
static FullTransactionId GistPageGetDeleteXid(Page page)
Definition:
gist.h:216
GistPageIsDeleted
#define GistPageIsDeleted(page)
Definition:
gist.h:173
GistPageGetOpaque
#define GistPageGetOpaque(page)
Definition:
gist.h:168
F_DELETED
#define F_DELETED
Definition:
gist.h:50
GistNSN
XLogRecPtr GistNSN
Definition:
gist.h:63
itup.h
OffsetNumber
uint16 OffsetNumber
Definition:
off.h:24
Datum
uintptr_t Datum
Definition:
postgres.h:69
Oid
unsigned int Oid
Definition:
postgres_ext.h:32
primnodes.h
relcache.h
stratnum.h
StrategyNumber
uint16 StrategyNumber
Definition:
stratnum.h:22
FullTransactionId
Definition:
transam.h:66
GISTDeletedPageContents
Definition:
gist.h:199
GISTDeletedPageContents::deleteXid
FullTransactionId deleteXid
Definition:
gist.h:201
GISTENTRY
Definition:
gist.h:160
GISTENTRY::offset
OffsetNumber offset
Definition:
gist.h:164
GISTENTRY::key
Datum key
Definition:
gist.h:161
GISTENTRY::page
Page page
Definition:
gist.h:163
GISTENTRY::rel
Relation rel
Definition:
gist.h:162
GISTENTRY::leafkey
bool leafkey
Definition:
gist.h:165
GISTPageOpaqueData
Definition:
gist.h:79
GISTPageOpaqueData::nsn
PageGistNSN nsn
Definition:
gist.h:80
GISTPageOpaqueData::gist_page_id
uint16 gist_page_id
Definition:
gist.h:83
GISTPageOpaqueData::rightlink
BlockNumber rightlink
Definition:
gist.h:81
GISTPageOpaqueData::flags
uint16 flags
Definition:
gist.h:82
GIST_SPLITVEC
Definition:
gist.h:142
GIST_SPLITVEC::spl_ldatum_exists
bool spl_ldatum_exists
Definition:
gist.h:146
GIST_SPLITVEC::spl_rdatum_exists
bool spl_rdatum_exists
Definition:
gist.h:151
GIST_SPLITVEC::spl_nleft
int spl_nleft
Definition:
gist.h:144
GIST_SPLITVEC::spl_right
OffsetNumber * spl_right
Definition:
gist.h:148
GIST_SPLITVEC::spl_ldatum
Datum spl_ldatum
Definition:
gist.h:145
GIST_SPLITVEC::spl_rdatum
Datum spl_rdatum
Definition:
gist.h:150
GIST_SPLITVEC::spl_nright
int spl_nright
Definition:
gist.h:149
GIST_SPLITVEC::spl_left
OffsetNumber * spl_left
Definition:
gist.h:143
GistEntryVector
Definition:
gist.h:235
PageHeaderData
Definition:
bufpage.h:160
PageXLogRecPtr
Definition:
bufpage.h:99
RelationData
Definition:
rel.h:56
transam.h
FirstNormalTransactionId
#define FirstNormalTransactionId
Definition:
transam.h:34
FullTransactionIdFromEpochAndXid
static FullTransactionId FullTransactionIdFromEpochAndXid(uint32 epoch, TransactionId xid)
Definition:
transam.h:71
xlog.h
xlogdefs.h
XLogRecPtr
uint64 XLogRecPtr
Definition:
xlogdefs.h:21
src
include
access
gist.h
Generated on Sun Feb 16 2025 00:13:24 for PostgreSQL Source Code by
1.9.4