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