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