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 */ 39 typedef 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 48 typedef 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 */ 78 typedef 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 87 typedef struct SpGistLUPCache 88 { 89 SpGistLastUsedPage cachedPage[SPGIST_CACHED_PAGES]; 90 } SpGistLUPCache; 91 92 /* 93 * metapage 94 */ 95 typedef 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 */ 112 typedef struct SpGistTypeDesc 113 { 114 Oid type; 115 bool attbyval; 116 int16 attlen; 117 } SpGistTypeDesc; 118 119 typedef 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 134 typedef 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 */ 157 typedef 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 213 typedef 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 */ 219 typedef 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 */ 253 typedef 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 264 typedef 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 297 typedef IndexTupleData SpGistNodeTupleData; 298 299 typedef 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 */ 333 typedef 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 342 typedef 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 */ 361 typedef 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 370 typedef 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 */ 426 extern SpGistCache *spgGetCache(Relation index); 427 extern void initSpGistState(SpGistState *state, Relation index); 428 extern Buffer SpGistNewBuffer(Relation index); 429 extern void SpGistUpdateMetaPage(Relation index); 430 extern Buffer SpGistGetBuffer(Relation index, int flags, 431 int needSpace, bool *isNew); 432 extern void SpGistSetLastUsedPage(Relation index, Buffer buffer); 433 extern void SpGistInitPage(Page page, uint16 f); 434 extern void SpGistInitBuffer(Buffer b, uint16 f); 435 extern void SpGistInitMetapage(Page page); 436 extern unsigned int SpGistGetTypeSize(SpGistTypeDesc *att, Datum datum); 437 extern SpGistLeafTuple spgFormLeafTuple(SpGistState *state, 438 ItemPointer heapPtr, 439 Datum datum, bool isnull); 440 extern SpGistNodeTuple spgFormNodeTuple(SpGistState *state, 441 Datum label, bool isnull); 442 extern SpGistInnerTuple spgFormInnerTuple(SpGistState *state, 443 bool hasPrefix, Datum prefix, 444 int nNodes, SpGistNodeTuple *nodes); 445 extern SpGistDeadTuple spgFormDeadTuple(SpGistState *state, int tupstate, 446 BlockNumber blkno, OffsetNumber offnum); 447 extern Datum *spgExtractNodeLabels(SpGistState *state, 448 SpGistInnerTuple innerTuple); 449 extern OffsetNumber SpGistPageAddNewItem(SpGistState *state, Page page, 450 Item item, Size size, 451 OffsetNumber *startOffset, 452 bool errorOK); 453 extern bool spgproperty(Oid index_oid, int attno, 454 IndexAMProperty prop, const char *propname, 455 bool *res, bool *isnull); 456 457 /* spgdoinsert.c */ 458 extern void spgUpdateNodeLink(SpGistInnerTuple tup, int nodeN, 459 BlockNumber blkno, OffsetNumber offset); 460 extern void spgPageIndexMultiDelete(SpGistState *state, Page page, 461 OffsetNumber *itemnos, int nitems, 462 int firststate, int reststate, 463 BlockNumber blkno, OffsetNumber offnum); 464 extern bool spgdoinsert(Relation index, SpGistState *state, 465 ItemPointer heapPtr, Datum datum, bool isnull); 466 467 /* spgproc.c */ 468 extern double *spg_key_orderbys_distances(Datum key, bool isLeaf, 469 ScanKey orderbys, int norderbys); 470 extern BOX *box_copy(BOX *orig); 471 472 #endif /* SPGIST_PRIVATE_H */ 473