1 /*------------------------------------------------------------------------- 2 * 3 * spgist_private.h 4 * Private declarations for SP-GiST access method. 5 * 6 * 7 * Portions Copyright (c) 1996-2018, 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 */ 45 } SpGistPageOpaqueData; 46 47 typedef SpGistPageOpaqueData *SpGistPageOpaque; 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!) */ 81 } SpGistLastUsedPage; 82 83 /* Note: indexes in cachedPage[] match flag assignments for SpGistGetBuffer */ 84 #define SPGIST_CACHED_PAGES 8 85 86 typedef struct SpGistLUPCache 87 { 88 SpGistLastUsedPage cachedPage[SPGIST_CACHED_PAGES]; 89 } SpGistLUPCache; 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 */ 98 } SpGistMetaPageData; 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 { 113 Oid type; 114 bool attbyval; 115 int16 attlen; 116 } SpGistTypeDesc; 117 118 typedef struct SpGistState 119 { 120 spgConfigOut config; /* filled in by opclass config method */ 121 122 SpGistTypeDesc attType; /* type of values to be indexed/restored */ 123 SpGistTypeDesc attLeafType; /* type of leaf-tuple values */ 124 SpGistTypeDesc attPrefixType; /* type of inner-tuple prefix values */ 125 SpGistTypeDesc attLabelType; /* type of node label values */ 126 127 char *deadTupleStorage; /* workspace for spgFormDeadTuple */ 128 129 TransactionId myXid; /* XID to use when creating a redirect tuple */ 130 bool isBuild; /* true if doing index build */ 131 } SpGistState; 132 133 /* 134 * Private state of an index scan 135 */ 136 typedef struct SpGistScanOpaqueData 137 { 138 SpGistState state; /* see above */ 139 MemoryContext tempCxt; /* short-lived memory context */ 140 MemoryContext traversalCxt; /* memory context for traversalValues */ 141 142 /* Control flags showing whether to search nulls and/or non-nulls */ 143 bool searchNulls; /* scan matches (all) null entries */ 144 bool searchNonNulls; /* scan matches (some) non-null entries */ 145 146 /* Index quals to be passed to opclass (null-related quals removed) */ 147 int numberOfKeys; /* number of index qualifier conditions */ 148 ScanKey keyData; /* array of index qualifier descriptors */ 149 150 /* Stack of yet-to-be-visited pages */ 151 List *scanStack; /* List of ScanStackEntrys */ 152 153 /* These fields are only used in amgetbitmap scans: */ 154 TIDBitmap *tbm; /* bitmap being filled */ 155 int64 ntids; /* number of TIDs passed to bitmap */ 156 157 /* These fields are only used in amgettuple scans: */ 158 bool want_itup; /* are we reconstructing tuples? */ 159 TupleDesc indexTupDesc; /* if so, tuple descriptor for them */ 160 int nPtrs; /* number of TIDs found on current page */ 161 int iPtr; /* index for scanning through same */ 162 ItemPointerData heapPtrs[MaxIndexTuplesPerPage]; /* TIDs from cur page */ 163 bool recheck[MaxIndexTuplesPerPage]; /* their recheck flags */ 164 HeapTuple reconTups[MaxIndexTuplesPerPage]; /* reconstructed tuples */ 165 166 /* 167 * Note: using MaxIndexTuplesPerPage above is a bit hokey since 168 * SpGistLeafTuples aren't exactly IndexTuples; however, they are larger, 169 * so this is safe. 170 */ 171 } SpGistScanOpaqueData; 172 173 typedef SpGistScanOpaqueData *SpGistScanOpaque; 174 175 /* 176 * This struct is what we actually keep in index->rd_amcache. It includes 177 * static configuration information as well as the lastUsedPages cache. 178 */ 179 typedef struct SpGistCache 180 { 181 spgConfigOut config; /* filled in by opclass config method */ 182 183 SpGistTypeDesc attType; /* type of values to be indexed/restored */ 184 SpGistTypeDesc attLeafType; /* type of leaf-tuple values */ 185 SpGistTypeDesc attPrefixType; /* type of inner-tuple prefix values */ 186 SpGistTypeDesc attLabelType; /* type of node label values */ 187 188 SpGistLUPCache lastUsedPages; /* local storage of last-used info */ 189 } SpGistCache; 190 191 192 /* 193 * SPGiST tuple types. Note: inner, leaf, and dead tuple structs 194 * must have the same tupstate field in the same position! Real inner and 195 * leaf tuples always have tupstate = LIVE; if the state is something else, 196 * use the SpGistDeadTuple struct to inspect the tuple. 197 */ 198 199 /* values of tupstate (see README for more info) */ 200 #define SPGIST_LIVE 0 /* normal live tuple (either inner or leaf) */ 201 #define SPGIST_REDIRECT 1 /* temporary redirection placeholder */ 202 #define SPGIST_DEAD 2 /* dead, cannot be removed because of links */ 203 #define SPGIST_PLACEHOLDER 3 /* placeholder, used to preserve offsets */ 204 205 /* 206 * SPGiST inner tuple: list of "nodes" that subdivide a set of tuples 207 * 208 * Inner tuple layout: 209 * header/optional prefix/array of nodes, which are SpGistNodeTuples 210 * 211 * size and prefixSize must be multiples of MAXALIGN 212 */ 213 typedef struct SpGistInnerTupleData 214 { 215 unsigned int tupstate:2, /* LIVE/REDIRECT/DEAD/PLACEHOLDER */ 216 allTheSame:1, /* all nodes in tuple are equivalent */ 217 nNodes:13, /* number of nodes within inner tuple */ 218 prefixSize:16; /* size of prefix, or 0 if none */ 219 uint16 size; /* total size of inner tuple */ 220 /* On most machines there will be a couple of wasted bytes here */ 221 /* prefix datum follows, then nodes */ 222 } SpGistInnerTupleData; 223 224 typedef SpGistInnerTupleData *SpGistInnerTuple; 225 226 /* these must match largest values that fit in bit fields declared above */ 227 #define SGITMAXNNODES 0x1FFF 228 #define SGITMAXPREFIXSIZE 0xFFFF 229 #define SGITMAXSIZE 0xFFFF 230 231 #define SGITHDRSZ MAXALIGN(sizeof(SpGistInnerTupleData)) 232 #define _SGITDATA(x) (((char *) (x)) + SGITHDRSZ) 233 #define SGITDATAPTR(x) ((x)->prefixSize ? _SGITDATA(x) : NULL) 234 #define SGITDATUM(x, s) ((x)->prefixSize ? \ 235 ((s)->attPrefixType.attbyval ? \ 236 *(Datum *) _SGITDATA(x) : \ 237 PointerGetDatum(_SGITDATA(x))) \ 238 : (Datum) 0) 239 #define SGITNODEPTR(x) ((SpGistNodeTuple) (_SGITDATA(x) + (x)->prefixSize)) 240 241 /* Macro for iterating through the nodes of an inner tuple */ 242 #define SGITITERATE(x, i, nt) \ 243 for ((i) = 0, (nt) = SGITNODEPTR(x); \ 244 (i) < (x)->nNodes; \ 245 (i)++, (nt) = (SpGistNodeTuple) (((char *) (nt)) + IndexTupleSize(nt))) 246 247 /* 248 * SPGiST node tuple: one node within an inner tuple 249 * 250 * Node tuples use the same header as ordinary Postgres IndexTuples, but 251 * we do not use a null bitmap, because we know there is only one column 252 * so the INDEX_NULL_MASK bit suffices. Also, pass-by-value datums are 253 * stored as a full Datum, the same convention as for inner tuple prefixes 254 * and leaf tuple datums. 255 */ 256 257 typedef IndexTupleData SpGistNodeTupleData; 258 259 typedef SpGistNodeTupleData *SpGistNodeTuple; 260 261 #define SGNTHDRSZ MAXALIGN(sizeof(SpGistNodeTupleData)) 262 #define SGNTDATAPTR(x) (((char *) (x)) + SGNTHDRSZ) 263 #define SGNTDATUM(x, s) ((s)->attLabelType.attbyval ? \ 264 *(Datum *) SGNTDATAPTR(x) : \ 265 PointerGetDatum(SGNTDATAPTR(x))) 266 267 /* 268 * SPGiST leaf tuple: carries a datum and a heap tuple TID 269 * 270 * In the simplest case, the datum is the same as the indexed value; but 271 * it could also be a suffix or some other sort of delta that permits 272 * reconstruction given knowledge of the prefix path traversed to get here. 273 * 274 * The size field is wider than could possibly be needed for an on-disk leaf 275 * tuple, but this allows us to form leaf tuples even when the datum is too 276 * wide to be stored immediately, and it costs nothing because of alignment 277 * considerations. 278 * 279 * Normally, nextOffset links to the next tuple belonging to the same parent 280 * node (which must be on the same page). But when the root page is a leaf 281 * page, we don't chain its tuples, so nextOffset is always 0 on the root. 282 * 283 * size must be a multiple of MAXALIGN; also, it must be at least SGDTSIZE 284 * so that the tuple can be converted to REDIRECT status later. (This 285 * restriction only adds bytes for the null-datum case, otherwise alignment 286 * restrictions force it anyway.) 287 * 288 * In a leaf tuple for a NULL indexed value, there's no useful datum value; 289 * however, the SGDTSIZE limit ensures that's there's a Datum word there 290 * anyway, so SGLTDATUM can be applied safely as long as you don't do 291 * anything with the result. 292 */ 293 typedef struct SpGistLeafTupleData 294 { 295 unsigned int tupstate:2, /* LIVE/REDIRECT/DEAD/PLACEHOLDER */ 296 size:30; /* large enough for any palloc'able value */ 297 OffsetNumber nextOffset; /* next tuple in chain, or InvalidOffset */ 298 ItemPointerData heapPtr; /* TID of represented heap tuple */ 299 /* leaf datum follows */ 300 } SpGistLeafTupleData; 301 302 typedef SpGistLeafTupleData *SpGistLeafTuple; 303 304 #define SGLTHDRSZ MAXALIGN(sizeof(SpGistLeafTupleData)) 305 #define SGLTDATAPTR(x) (((char *) (x)) + SGLTHDRSZ) 306 #define SGLTDATUM(x, s) ((s)->attLeafType.attbyval ? \ 307 *(Datum *) SGLTDATAPTR(x) : \ 308 PointerGetDatum(SGLTDATAPTR(x))) 309 310 /* 311 * SPGiST dead tuple: declaration for examining non-live tuples 312 * 313 * The tupstate field of this struct must match those of regular inner and 314 * leaf tuples, and its size field must match a leaf tuple's. 315 * Also, the pointer field must be in the same place as a leaf tuple's heapPtr 316 * field, to satisfy some Asserts that we make when replacing a leaf tuple 317 * with a dead tuple. 318 * We don't use nextOffset, but it's needed to align the pointer field. 319 * pointer and xid are only valid when tupstate = REDIRECT. 320 */ 321 typedef struct SpGistDeadTupleData 322 { 323 unsigned int tupstate:2, /* LIVE/REDIRECT/DEAD/PLACEHOLDER */ 324 size:30; 325 OffsetNumber nextOffset; /* not used in dead tuples */ 326 ItemPointerData pointer; /* redirection inside index */ 327 TransactionId xid; /* ID of xact that inserted this tuple */ 328 } SpGistDeadTupleData; 329 330 typedef SpGistDeadTupleData *SpGistDeadTuple; 331 332 #define SGDTSIZE MAXALIGN(sizeof(SpGistDeadTupleData)) 333 334 /* 335 * Macros for doing free-space calculations. Note that when adding up the 336 * space needed for tuples, we always consider each tuple to need the tuple's 337 * size plus sizeof(ItemIdData) (for the line pointer). This works correctly 338 * so long as tuple sizes are always maxaligned. 339 */ 340 341 /* Page capacity after allowing for fixed header and special space */ 342 #define SPGIST_PAGE_CAPACITY \ 343 MAXALIGN_DOWN(BLCKSZ - \ 344 SizeOfPageHeaderData - \ 345 MAXALIGN(sizeof(SpGistPageOpaqueData))) 346 347 /* 348 * Compute free space on page, assuming that up to n placeholders can be 349 * recycled if present (n should be the number of tuples to be inserted) 350 */ 351 #define SpGistPageGetFreeSpace(p, n) \ 352 (PageGetExactFreeSpace(p) + \ 353 Min(SpGistPageGetOpaque(p)->nPlaceholder, n) * \ 354 (SGDTSIZE + sizeof(ItemIdData))) 355 356 /* 357 * XLOG stuff 358 */ 359 360 #define STORE_STATE(s, d) \ 361 do { \ 362 (d).myXid = (s)->myXid; \ 363 (d).isBuild = (s)->isBuild; \ 364 } while(0) 365 366 /* 367 * The "flags" argument for SpGistGetBuffer should be either GBUF_LEAF to 368 * get a leaf page, or GBUF_INNER_PARITY(blockNumber) to get an inner 369 * page in the same triple-parity group as the specified block number. 370 * (Typically, this should be GBUF_INNER_PARITY(parentBlockNumber + 1) 371 * to follow the rule described in spgist/README.) 372 * In addition, GBUF_NULLS can be OR'd in to get a page for storage of 373 * null-valued tuples. 374 * 375 * Note: these flag values are used as indexes into lastUsedPages. 376 */ 377 #define GBUF_LEAF 0x03 378 #define GBUF_INNER_PARITY(x) ((x) % 3) 379 #define GBUF_NULLS 0x04 380 381 #define GBUF_PARITY_MASK 0x03 382 #define GBUF_REQ_LEAF(flags) (((flags) & GBUF_PARITY_MASK) == GBUF_LEAF) 383 #define GBUF_REQ_NULLS(flags) ((flags) & GBUF_NULLS) 384 385 /* spgutils.c */ 386 extern SpGistCache *spgGetCache(Relation index); 387 extern void initSpGistState(SpGistState *state, Relation index); 388 extern Buffer SpGistNewBuffer(Relation index); 389 extern void SpGistUpdateMetaPage(Relation index); 390 extern Buffer SpGistGetBuffer(Relation index, int flags, 391 int needSpace, bool *isNew); 392 extern void SpGistSetLastUsedPage(Relation index, Buffer buffer); 393 extern void SpGistInitPage(Page page, uint16 f); 394 extern void SpGistInitBuffer(Buffer b, uint16 f); 395 extern void SpGistInitMetapage(Page page); 396 extern unsigned int SpGistGetTypeSize(SpGistTypeDesc *att, Datum datum); 397 extern SpGistLeafTuple spgFormLeafTuple(SpGistState *state, 398 ItemPointer heapPtr, 399 Datum datum, bool isnull); 400 extern SpGistNodeTuple spgFormNodeTuple(SpGistState *state, 401 Datum label, bool isnull); 402 extern SpGistInnerTuple spgFormInnerTuple(SpGistState *state, 403 bool hasPrefix, Datum prefix, 404 int nNodes, SpGistNodeTuple *nodes); 405 extern SpGistDeadTuple spgFormDeadTuple(SpGistState *state, int tupstate, 406 BlockNumber blkno, OffsetNumber offnum); 407 extern Datum *spgExtractNodeLabels(SpGistState *state, 408 SpGistInnerTuple innerTuple); 409 extern OffsetNumber SpGistPageAddNewItem(SpGistState *state, Page page, 410 Item item, Size size, 411 OffsetNumber *startOffset, 412 bool errorOK); 413 414 /* spgdoinsert.c */ 415 extern void spgUpdateNodeLink(SpGistInnerTuple tup, int nodeN, 416 BlockNumber blkno, OffsetNumber offset); 417 extern void spgPageIndexMultiDelete(SpGistState *state, Page page, 418 OffsetNumber *itemnos, int nitems, 419 int firststate, int reststate, 420 BlockNumber blkno, OffsetNumber offnum); 421 extern bool spgdoinsert(Relation index, SpGistState *state, 422 ItemPointer heapPtr, Datum datum, bool isnull); 423 424 #endif /* SPGIST_PRIVATE_H */ 425