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