PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
spgist_private.h
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * spgist_private.h
4  * Private declarations for SP-GiST access method.
5  *
6  *
7  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
8  * Portions Copyright (c) 1994, Regents of the University of California
9  *
10  * src/include/access/spgist_private.h
11  *
12  *-------------------------------------------------------------------------
13  */
14 #ifndef SPGIST_PRIVATE_H
15 #define SPGIST_PRIVATE_H
16 
17 #include "access/itup.h"
18 #include "access/spgist.h"
19 #include "nodes/tidbitmap.h"
20 #include "storage/buf.h"
21 #include "utils/relcache.h"
22 
23 
24 /* Page numbers of fixed-location pages */
25 #define SPGIST_METAPAGE_BLKNO (0) /* metapage */
26 #define SPGIST_ROOT_BLKNO (1) /* root for normal entries */
27 #define SPGIST_NULL_BLKNO (2) /* root for null-value entries */
28 #define SPGIST_LAST_FIXED_BLKNO SPGIST_NULL_BLKNO
29 
30 #define SpGistBlockIsRoot(blkno) \
31  ((blkno) == SPGIST_ROOT_BLKNO || (blkno) == SPGIST_NULL_BLKNO)
32 #define SpGistBlockIsFixed(blkno) \
33  ((BlockNumber) (blkno) <= (BlockNumber) SPGIST_LAST_FIXED_BLKNO)
34 
35 /*
36  * Contents of page special space on SPGiST index pages
37  */
38 typedef struct SpGistPageOpaqueData
39 {
40  uint16 flags; /* see bit definitions below */
41  uint16 nRedirection; /* number of redirection tuples on page */
42  uint16 nPlaceholder; /* number of placeholder tuples on page */
43  /* note there's no count of either LIVE or DEAD tuples ... */
44  uint16 spgist_page_id; /* for identification of SP-GiST indexes */
46 
48 
49 /* Flag bits in page special space */
50 #define SPGIST_META (1<<0)
51 #define SPGIST_DELETED (1<<1) /* never set, but keep for backwards
52  * compatibility */
53 #define SPGIST_LEAF (1<<2)
54 #define SPGIST_NULLS (1<<3)
55 
56 #define SpGistPageGetOpaque(page) ((SpGistPageOpaque) PageGetSpecialPointer(page))
57 #define SpGistPageIsMeta(page) (SpGistPageGetOpaque(page)->flags & SPGIST_META)
58 #define SpGistPageIsDeleted(page) (SpGistPageGetOpaque(page)->flags & SPGIST_DELETED)
59 #define SpGistPageIsLeaf(page) (SpGistPageGetOpaque(page)->flags & SPGIST_LEAF)
60 #define SpGistPageStoresNulls(page) (SpGistPageGetOpaque(page)->flags & SPGIST_NULLS)
61 
62 /*
63  * The page ID is for the convenience of pg_filedump and similar utilities,
64  * which otherwise would have a hard time telling pages of different index
65  * types apart. It should be the last 2 bytes on the page. This is more or
66  * less "free" due to alignment considerations.
67  *
68  * See comments above GinPageOpaqueData.
69  */
70 #define SPGIST_PAGE_ID 0xFF82
71 
72 /*
73  * Each backend keeps a cache of last-used page info in its index->rd_amcache
74  * area. This is initialized from, and occasionally written back to,
75  * shared storage in the index metapage.
76  */
77 typedef struct SpGistLastUsedPage
78 {
79  BlockNumber blkno; /* block number, or InvalidBlockNumber */
80  int freeSpace; /* page's free space (could be obsolete!) */
82 
83 /* Note: indexes in cachedPage[] match flag assignments for SpGistGetBuffer */
84 #define SPGIST_CACHED_PAGES 8
85 
86 typedef struct SpGistLUPCache
87 {
90 
91 /*
92  * metapage
93  */
94 typedef struct SpGistMetaPageData
95 {
96  uint32 magicNumber; /* for identity cross-check */
97  SpGistLUPCache lastUsedPages; /* shared storage of last-used info */
99 
100 #define SPGIST_MAGIC_NUMBER (0xBA0BABEE)
101 
102 #define SpGistPageGetMeta(p) \
103  ((SpGistMetaPageData *) PageGetContents(p))
104 
105 /*
106  * Private state of index AM. SpGistState is common to both insert and
107  * search code; SpGistScanOpaque is for searches only.
108  */
109 
110 /* Per-datatype info needed in SpGistState */
111 typedef struct SpGistTypeDesc
112 {
114  bool attbyval;
117 
118 typedef struct SpGistState
119 {
120  spgConfigOut config; /* filled in by opclass config method */
121 
122  SpGistTypeDesc attType; /* type of input data and leaf values */
123  SpGistTypeDesc attPrefixType; /* type of inner-tuple prefix values */
124  SpGistTypeDesc attLabelType; /* type of node label values */
125 
126  char *deadTupleStorage; /* workspace for spgFormDeadTuple */
127 
128  TransactionId myXid; /* XID to use when creating a redirect tuple */
129  bool isBuild; /* true if doing index build */
130 } SpGistState;
131 
132 /*
133  * Private state of an index scan
134  */
135 typedef struct SpGistScanOpaqueData
136 {
137  SpGistState state; /* see above */
138  MemoryContext tempCxt; /* short-lived memory context */
139 
140  /* Control flags showing whether to search nulls and/or non-nulls */
141  bool searchNulls; /* scan matches (all) null entries */
142  bool searchNonNulls; /* scan matches (some) non-null entries */
143 
144  /* Index quals to be passed to opclass (null-related quals removed) */
145  int numberOfKeys; /* number of index qualifier conditions */
146  ScanKey keyData; /* array of index qualifier descriptors */
147 
148  /* Stack of yet-to-be-visited pages */
149  List *scanStack; /* List of ScanStackEntrys */
150 
151  /* These fields are only used in amgetbitmap scans: */
152  TIDBitmap *tbm; /* bitmap being filled */
153  int64 ntids; /* number of TIDs passed to bitmap */
154 
155  /* These fields are only used in amgettuple scans: */
156  bool want_itup; /* are we reconstructing tuples? */
157  TupleDesc indexTupDesc; /* if so, tuple descriptor for them */
158  int nPtrs; /* number of TIDs found on current page */
159  int iPtr; /* index for scanning through same */
160  ItemPointerData heapPtrs[MaxIndexTuplesPerPage]; /* TIDs from cur page */
161  bool recheck[MaxIndexTuplesPerPage]; /* their recheck flags */
162  HeapTuple reconTups[MaxIndexTuplesPerPage]; /* reconstructed tuples */
163 
164  /*
165  * Note: using MaxIndexTuplesPerPage above is a bit hokey since
166  * SpGistLeafTuples aren't exactly IndexTuples; however, they are larger,
167  * so this is safe.
168  */
170 
172 
173 /*
174  * This struct is what we actually keep in index->rd_amcache. It includes
175  * static configuration information as well as the lastUsedPages cache.
176  */
177 typedef struct SpGistCache
178 {
179  spgConfigOut config; /* filled in by opclass config method */
180 
181  SpGistTypeDesc attType; /* type of input data and leaf values */
182  SpGistTypeDesc attPrefixType; /* type of inner-tuple prefix values */
183  SpGistTypeDesc attLabelType; /* type of node label values */
184 
185  SpGistLUPCache lastUsedPages; /* local storage of last-used info */
186 } SpGistCache;
187 
188 
189 /*
190  * SPGiST tuple types. Note: inner, leaf, and dead tuple structs
191  * must have the same tupstate field in the same position! Real inner and
192  * leaf tuples always have tupstate = LIVE; if the state is something else,
193  * use the SpGistDeadTuple struct to inspect the tuple.
194  */
195 
196 /* values of tupstate (see README for more info) */
197 #define SPGIST_LIVE 0 /* normal live tuple (either inner or leaf) */
198 #define SPGIST_REDIRECT 1 /* temporary redirection placeholder */
199 #define SPGIST_DEAD 2 /* dead, cannot be removed because of links */
200 #define SPGIST_PLACEHOLDER 3 /* placeholder, used to preserve offsets */
201 
202 /*
203  * SPGiST inner tuple: list of "nodes" that subdivide a set of tuples
204  *
205  * Inner tuple layout:
206  * header/optional prefix/array of nodes, which are SpGistNodeTuples
207  *
208  * size and prefixSize must be multiples of MAXALIGN
209  */
210 typedef struct SpGistInnerTupleData
211 {
212  unsigned int tupstate:2, /* LIVE/REDIRECT/DEAD/PLACEHOLDER */
213  allTheSame:1, /* all nodes in tuple are equivalent */
214  nNodes:13, /* number of nodes within inner tuple */
215  prefixSize:16; /* size of prefix, or 0 if none */
216  uint16 size; /* total size of inner tuple */
217  /* On most machines there will be a couple of wasted bytes here */
218  /* prefix datum follows, then nodes */
220 
222 
223 /* these must match largest values that fit in bit fields declared above */
224 #define SGITMAXNNODES 0x1FFF
225 #define SGITMAXPREFIXSIZE 0xFFFF
226 #define SGITMAXSIZE 0xFFFF
227 
228 #define SGITHDRSZ MAXALIGN(sizeof(SpGistInnerTupleData))
229 #define _SGITDATA(x) (((char *) (x)) + SGITHDRSZ)
230 #define SGITDATAPTR(x) ((x)->prefixSize ? _SGITDATA(x) : NULL)
231 #define SGITDATUM(x, s) ((x)->prefixSize ? \
232  ((s)->attPrefixType.attbyval ? \
233  *(Datum *) _SGITDATA(x) : \
234  PointerGetDatum(_SGITDATA(x))) \
235  : (Datum) 0)
236 #define SGITNODEPTR(x) ((SpGistNodeTuple) (_SGITDATA(x) + (x)->prefixSize))
237 
238 /* Macro for iterating through the nodes of an inner tuple */
239 #define SGITITERATE(x, i, nt) \
240  for ((i) = 0, (nt) = SGITNODEPTR(x); \
241  (i) < (x)->nNodes; \
242  (i)++, (nt) = (SpGistNodeTuple) (((char *) (nt)) + IndexTupleSize(nt)))
243 
244 /*
245  * SPGiST node tuple: one node within an inner tuple
246  *
247  * Node tuples use the same header as ordinary Postgres IndexTuples, but
248  * we do not use a null bitmap, because we know there is only one column
249  * so the INDEX_NULL_MASK bit suffices. Also, pass-by-value datums are
250  * stored as a full Datum, the same convention as for inner tuple prefixes
251  * and leaf tuple datums.
252  */
253 
255 
257 
258 #define SGNTHDRSZ MAXALIGN(sizeof(SpGistNodeTupleData))
259 #define SGNTDATAPTR(x) (((char *) (x)) + SGNTHDRSZ)
260 #define SGNTDATUM(x, s) ((s)->attLabelType.attbyval ? \
261  *(Datum *) SGNTDATAPTR(x) : \
262  PointerGetDatum(SGNTDATAPTR(x)))
263 
264 /*
265  * SPGiST leaf tuple: carries a datum and a heap tuple TID
266  *
267  * In the simplest case, the datum is the same as the indexed value; but
268  * it could also be a suffix or some other sort of delta that permits
269  * reconstruction given knowledge of the prefix path traversed to get here.
270  *
271  * The size field is wider than could possibly be needed for an on-disk leaf
272  * tuple, but this allows us to form leaf tuples even when the datum is too
273  * wide to be stored immediately, and it costs nothing because of alignment
274  * considerations.
275  *
276  * Normally, nextOffset links to the next tuple belonging to the same parent
277  * node (which must be on the same page). But when the root page is a leaf
278  * page, we don't chain its tuples, so nextOffset is always 0 on the root.
279  *
280  * size must be a multiple of MAXALIGN; also, it must be at least SGDTSIZE
281  * so that the tuple can be converted to REDIRECT status later. (This
282  * restriction only adds bytes for the null-datum case, otherwise alignment
283  * restrictions force it anyway.)
284  *
285  * In a leaf tuple for a NULL indexed value, there's no useful datum value;
286  * however, the SGDTSIZE limit ensures that's there's a Datum word there
287  * anyway, so SGLTDATUM can be applied safely as long as you don't do
288  * anything with the result.
289  */
290 typedef struct SpGistLeafTupleData
291 {
292  unsigned int tupstate:2, /* LIVE/REDIRECT/DEAD/PLACEHOLDER */
293  size:30; /* large enough for any palloc'able value */
294  OffsetNumber nextOffset; /* next tuple in chain, or InvalidOffset */
295  ItemPointerData heapPtr; /* TID of represented heap tuple */
296  /* leaf datum follows */
298 
300 
301 #define SGLTHDRSZ MAXALIGN(sizeof(SpGistLeafTupleData))
302 #define SGLTDATAPTR(x) (((char *) (x)) + SGLTHDRSZ)
303 #define SGLTDATUM(x, s) ((s)->attType.attbyval ? \
304  *(Datum *) SGLTDATAPTR(x) : \
305  PointerGetDatum(SGLTDATAPTR(x)))
306 
307 /*
308  * SPGiST dead tuple: declaration for examining non-live tuples
309  *
310  * The tupstate field of this struct must match those of regular inner and
311  * leaf tuples, and its size field must match a leaf tuple's.
312  * Also, the pointer field must be in the same place as a leaf tuple's heapPtr
313  * field, to satisfy some Asserts that we make when replacing a leaf tuple
314  * with a dead tuple.
315  * We don't use nextOffset, but it's needed to align the pointer field.
316  * pointer and xid are only valid when tupstate = REDIRECT.
317  */
318 typedef struct SpGistDeadTupleData
319 {
320  unsigned int tupstate:2, /* LIVE/REDIRECT/DEAD/PLACEHOLDER */
321  size:30;
322  OffsetNumber nextOffset; /* not used in dead tuples */
323  ItemPointerData pointer; /* redirection inside index */
324  TransactionId xid; /* ID of xact that inserted this tuple */
326 
328 
329 #define SGDTSIZE MAXALIGN(sizeof(SpGistDeadTupleData))
330 
331 /*
332  * Macros for doing free-space calculations. Note that when adding up the
333  * space needed for tuples, we always consider each tuple to need the tuple's
334  * size plus sizeof(ItemIdData) (for the line pointer). This works correctly
335  * so long as tuple sizes are always maxaligned.
336  */
337 
338 /* Page capacity after allowing for fixed header and special space */
339 #define SPGIST_PAGE_CAPACITY \
340  MAXALIGN_DOWN(BLCKSZ - \
341  SizeOfPageHeaderData - \
342  MAXALIGN(sizeof(SpGistPageOpaqueData)))
343 
344 /*
345  * Compute free space on page, assuming that up to n placeholders can be
346  * recycled if present (n should be the number of tuples to be inserted)
347  */
348 #define SpGistPageGetFreeSpace(p, n) \
349  (PageGetExactFreeSpace(p) + \
350  Min(SpGistPageGetOpaque(p)->nPlaceholder, n) * \
351  (SGDTSIZE + sizeof(ItemIdData)))
352 
353 /*
354  * XLOG stuff
355  */
356 
357 #define STORE_STATE(s, d) \
358  do { \
359  (d).myXid = (s)->myXid; \
360  (d).isBuild = (s)->isBuild; \
361  } while(0)
362 
363 /*
364  * The "flags" argument for SpGistGetBuffer should be either GBUF_LEAF to
365  * get a leaf page, or GBUF_INNER_PARITY(blockNumber) to get an inner
366  * page in the same triple-parity group as the specified block number.
367  * (Typically, this should be GBUF_INNER_PARITY(parentBlockNumber + 1)
368  * to follow the rule described in spgist/README.)
369  * In addition, GBUF_NULLS can be OR'd in to get a page for storage of
370  * null-valued tuples.
371  *
372  * Note: these flag values are used as indexes into lastUsedPages.
373  */
374 #define GBUF_LEAF 0x03
375 #define GBUF_INNER_PARITY(x) ((x) % 3)
376 #define GBUF_NULLS 0x04
377 
378 #define GBUF_PARITY_MASK 0x03
379 #define GBUF_REQ_LEAF(flags) (((flags) & GBUF_PARITY_MASK) == GBUF_LEAF)
380 #define GBUF_REQ_NULLS(flags) ((flags) & GBUF_NULLS)
381 
382 /* spgutils.c */
386 extern void SpGistUpdateMetaPage(Relation index);
387 extern Buffer SpGistGetBuffer(Relation index, int flags,
388  int needSpace, bool *isNew);
390 extern void SpGistInitPage(Page page, uint16 f);
391 extern void SpGistInitBuffer(Buffer b, uint16 f);
392 extern void SpGistInitMetapage(Page page);
393 extern unsigned int SpGistGetTypeSize(SpGistTypeDesc *att, Datum datum);
395  ItemPointer heapPtr,
396  Datum datum, bool isnull);
398  Datum label, bool isnull);
400  bool hasPrefix, Datum prefix,
401  int nNodes, SpGistNodeTuple *nodes);
402 extern SpGistDeadTuple spgFormDeadTuple(SpGistState *state, int tupstate,
403  BlockNumber blkno, OffsetNumber offnum);
405  SpGistInnerTuple innerTuple);
407  Item item, Size size,
408  OffsetNumber *startOffset,
409  bool errorOK);
410 
411 /* spgdoinsert.c */
412 extern void spgUpdateNodeLink(SpGistInnerTuple tup, int nodeN,
413  BlockNumber blkno, OffsetNumber offset);
414 extern void spgPageIndexMultiDelete(SpGistState *state, Page page,
415  OffsetNumber *itemnos, int nitems,
416  int firststate, int reststate,
417  BlockNumber blkno, OffsetNumber offnum);
419  ItemPointer heapPtr, Datum datum, bool isnull);
420 
421 #endif /* SPGIST_PRIVATE_H */
signed short int16
Definition: c.h:255
SpGistLeafTuple spgFormLeafTuple(SpGistState *state, ItemPointer heapPtr, Datum datum, bool isnull)
Definition: spgutils.c:592
SpGistCache * spgGetCache(Relation index)
Definition: spgutils.c:92
SpGistPageOpaqueData * SpGistPageOpaque
SpGistTypeDesc attPrefixType
SpGistInnerTupleData * SpGistInnerTuple
uint32 TransactionId
Definition: c.h:397
void initSpGistState(SpGistState *state, Relation index)
Definition: spgutils.c:158
ItemPointerData heapPtrs[MaxIndexTuplesPerPage]
SpGistNodeTuple spgFormNodeTuple(SpGistState *state, Datum label, bool isnull)
Definition: spgutils.c:629
void SpGistInitPage(Page page, uint16 f)
Definition: spgutils.c:499
struct SpGistPageOpaqueData SpGistPageOpaqueData
SpGistTypeDesc attType
Datum * spgExtractNodeLabels(SpGistState *state, SpGistInnerTuple innerTuple)
Definition: spgutils.c:784
Pointer Item
Definition: item.h:17
MemoryContext tempCxt
uint32 BlockNumber
Definition: block.h:31
SpGistTypeDesc attLabelType
IndexTupleData SpGistNodeTupleData
unsigned int Oid
Definition: postgres_ext.h:31
struct SpGistDeadTupleData SpGistDeadTupleData
SpGistTypeDesc attType
bool spgdoinsert(Relation index, SpGistState *state, ItemPointer heapPtr, Datum datum, bool isnull)
Definition: spgdoinsert.c:1891
struct SpGistLeafTupleData SpGistLeafTupleData
HeapTuple reconTups[MaxIndexTuplesPerPage]
SpGistLUPCache lastUsedPages
uint16 OffsetNumber
Definition: off.h:24
Definition: type.h:89
spgConfigOut config
SpGistLastUsedPage cachedPage[SPGIST_CACHED_PAGES]
unsigned short uint16
Definition: c.h:267
unsigned int allTheSame
ItemPointerData pointer
struct SpGistLastUsedPage SpGistLastUsedPage
struct SpGistTypeDesc SpGistTypeDesc
unsigned int prefixSize
void spgUpdateNodeLink(SpGistInnerTuple tup, int nodeN, BlockNumber blkno, OffsetNumber offset)
Definition: spgdoinsert.c:50
struct SpGistMetaPageData SpGistMetaPageData
Buffer SpGistNewBuffer(Relation index)
Definition: spgutils.c:187
bool recheck[MaxIndexTuplesPerPage]
unsigned int SpGistGetTypeSize(SpGistTypeDesc *att, Datum datum)
Definition: spgutils.c:555
SpGistDeadTupleData * SpGistDeadTuple
struct SpGistLUPCache SpGistLUPCache
unsigned int uint32
Definition: c.h:268
TransactionId myXid
Buffer SpGistGetBuffer(Relation index, int flags, int needSpace, bool *isNew)
Definition: spgutils.c:359
void spgPageIndexMultiDelete(SpGistState *state, Page page, OffsetNumber *itemnos, int nitems, int firststate, int reststate, BlockNumber blkno, OffsetNumber offnum)
Definition: spgdoinsert.c:131
SpGistDeadTuple spgFormDeadTuple(SpGistState *state, int tupstate, BlockNumber blkno, OffsetNumber offnum)
Definition: spgutils.c:754
SpGistInnerTuple spgFormInnerTuple(SpGistState *state, bool hasPrefix, Datum prefix, int nNodes, SpGistNodeTuple *nodes)
Definition: spgutils.c:671
void SpGistSetLastUsedPage(Relation index, Buffer buffer)
Definition: spgutils.c:464
spgConfigOut config
unsigned int tupstate
SpGistLUPCache lastUsedPages
OffsetNumber SpGistPageAddNewItem(SpGistState *state, Page page, Item item, Size size, OffsetNumber *startOffset, bool errorOK)
Definition: spgutils.c:827
unsigned int tupstate
uintptr_t Datum
Definition: postgres.h:372
void SpGistUpdateMetaPage(Relation index)
Definition: spgutils.c:252
static char * label
Definition: pg_basebackup.c:81
char * deadTupleStorage
SpGistScanOpaqueData * SpGistScanOpaque
OffsetNumber nextOffset
void SpGistInitBuffer(Buffer b, uint16 f)
Definition: spgutils.c:514
Definition: regguts.h:298
WalTimeSample buffer[LAG_TRACKER_BUFFER_SIZE]
Definition: walsender.c:214
size_t Size
Definition: c.h:356
OffsetNumber nextOffset
#define SPGIST_CACHED_PAGES
SpGistTypeDesc attLabelType
struct SpGistCache SpGistCache
#define MaxIndexTuplesPerPage
Definition: itup.h:137
void SpGistInitMetapage(Page page)
Definition: spgutils.c:524
SpGistTypeDesc attPrefixType
ItemPointerData heapPtr
struct SpGistInnerTupleData SpGistInnerTupleData
SpGistLeafTupleData * SpGistLeafTuple
struct SpGistScanOpaqueData SpGistScanOpaqueData
Definition: pg_list.h:45
int Buffer
Definition: buf.h:23
struct SpGistState SpGistState
Pointer Page
Definition: bufpage.h:74
SpGistNodeTupleData * SpGistNodeTuple