PostgreSQL Source Code
git master
Main Page
Related Pages
Namespaces
Namespace List
Namespace Members
All
Functions
Variables
Data Structures
Data Structures
Data Structure Index
Class Hierarchy
Data Fields
All
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
~
Functions
_
a
f
h
i
n
o
p
r
s
~
Variables
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
Enumerations
Files
File List
Globals
All
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
Functions
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
Variables
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
Typedefs
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
Enumerations
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
Enumerator
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
z
Macros
_
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
•
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
*/
77
typedef
PageXLogRecPtr
PageGistNSN
;
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 */
85
}
GISTPageOpaqueData
;
86
87
typedef
GISTPageOpaqueData
*
GISTPageOpaque
;
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
{
162
Datum
key
;
163
Relation
rel
;
164
Page
page
;
165
OffsetNumber
offset
;
166
bool
leafkey
;
167
}
GISTENTRY
;
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 */
202
FullTransactionId
deleteXid
;
203
}
GISTDeletedPageContents
;
204
205
static
inline
void
206
GistPageSetDeleted
(
Page
page,
FullTransactionId
deletexid)
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
217
GistPageGetDeleteXid
(
Page
page)
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
228
return
FullTransactionIdFromEpochAndXid
(0,
FirstNormalTransactionId
);
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 */
238
GISTENTRY
vector[
FLEXIBLE_ARRAY_MEMBER
];
239
}
GistEntryVector
;
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
250
extern
StrategyNumber
GistTranslateStratnum
(
Oid
opclass,
StrategyNumber
strat);
251
252
#endif
/* GIST_H */
block.h
BlockNumber
uint32 BlockNumber
Definition:
block.h:31
bufpage.h
PageHeader
PageHeaderData * PageHeader
Definition:
bufpage.h:173
PageIsEmpty
static bool PageIsEmpty(Page page)
Definition:
bufpage.h:223
PageGetContents
static char * PageGetContents(Page page)
Definition:
bufpage.h:257
Page
Pointer Page
Definition:
bufpage.h:81
SizeOfPageHeaderData
#define SizeOfPageHeaderData
Definition:
bufpage.h:216
uint16
unsigned short uint16
Definition:
c.h:517
MAXALIGN
#define MAXALIGN(LEN)
Definition:
c.h:816
int32
signed int int32
Definition:
c.h:508
Assert
#define Assert(condition)
Definition:
c.h:863
FLEXIBLE_ARRAY_MEMBER
#define FLEXIBLE_ARRAY_MEMBER
Definition:
c.h:413
GISTPageOpaque
GISTPageOpaqueData * GISTPageOpaque
Definition:
gist.h:85
PageGistNSN
PageXLogRecPtr PageGistNSN
Definition:
gist.h:75
GISTENTRY
struct GISTENTRY GISTENTRY
GISTPageOpaqueData
struct GISTPageOpaqueData GISTPageOpaqueData
GistPageSetDeleted
static void GistPageSetDeleted(Page page, FullTransactionId deletexid)
Definition:
gist.h:204
GISTDeletedPageContents
struct GISTDeletedPageContents GISTDeletedPageContents
GIST_SPLITVEC
struct GIST_SPLITVEC GIST_SPLITVEC
GistTranslateStratnum
StrategyNumber GistTranslateStratnum(Oid opclass, StrategyNumber strat)
Definition:
gistutil.c:1081
GistPageGetDeleteXid
static FullTransactionId GistPageGetDeleteXid(Page page)
Definition:
gist.h:215
GistPageIsDeleted
#define GistPageIsDeleted(page)
Definition:
gist.h:172
GistPageGetOpaque
#define GistPageGetOpaque(page)
Definition:
gist.h:167
F_DELETED
#define F_DELETED
Definition:
gist.h:49
GistNSN
XLogRecPtr GistNSN
Definition:
gist.h:62
itup.h
OffsetNumber
uint16 OffsetNumber
Definition:
off.h:24
Datum
uintptr_t Datum
Definition:
postgres.h:64
Oid
unsigned int Oid
Definition:
postgres_ext.h:31
relcache.h
stratnum.h
StrategyNumber
uint16 StrategyNumber
Definition:
stratnum.h:22
FullTransactionId
Definition:
transam.h:66
GISTDeletedPageContents
Definition:
gist.h:198
GISTDeletedPageContents::deleteXid
FullTransactionId deleteXid
Definition:
gist.h:200
GISTENTRY
Definition:
gist.h:159
GISTENTRY::offset
OffsetNumber offset
Definition:
gist.h:163
GISTENTRY::key
Datum key
Definition:
gist.h:160
GISTENTRY::page
Page page
Definition:
gist.h:162
GISTENTRY::rel
Relation rel
Definition:
gist.h:161
GISTENTRY::leafkey
bool leafkey
Definition:
gist.h:164
GISTPageOpaqueData
Definition:
gist.h:78
GISTPageOpaqueData::nsn
PageGistNSN nsn
Definition:
gist.h:79
GISTPageOpaqueData::gist_page_id
uint16 gist_page_id
Definition:
gist.h:82
GISTPageOpaqueData::rightlink
BlockNumber rightlink
Definition:
gist.h:80
GISTPageOpaqueData::flags
uint16 flags
Definition:
gist.h:81
GIST_SPLITVEC
Definition:
gist.h:141
GIST_SPLITVEC::spl_ldatum_exists
bool spl_ldatum_exists
Definition:
gist.h:145
GIST_SPLITVEC::spl_rdatum_exists
bool spl_rdatum_exists
Definition:
gist.h:150
GIST_SPLITVEC::spl_nleft
int spl_nleft
Definition:
gist.h:143
GIST_SPLITVEC::spl_right
OffsetNumber * spl_right
Definition:
gist.h:147
GIST_SPLITVEC::spl_ldatum
Datum spl_ldatum
Definition:
gist.h:144
GIST_SPLITVEC::spl_rdatum
Datum spl_rdatum
Definition:
gist.h:149
GIST_SPLITVEC::spl_nright
int spl_nright
Definition:
gist.h:148
GIST_SPLITVEC::spl_left
OffsetNumber * spl_left
Definition:
gist.h:142
GistEntryVector
Definition:
gist.h:234
PageHeaderData
Definition:
bufpage.h:159
PageXLogRecPtr
Definition:
bufpage.h:98
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 Mon Nov 25 2024 12:13:26 for PostgreSQL Source Code by
1.9.1