1 /*-------------------------------------------------------------------------- 2 * ginblock.h 3 * details of structures stored in GIN index blocks 4 * 5 * Copyright (c) 2006-2021, PostgreSQL Global Development Group 6 * 7 * src/include/access/ginblock.h 8 *-------------------------------------------------------------------------- 9 */ 10 #ifndef GINBLOCK_H 11 #define GINBLOCK_H 12 13 #include "access/transam.h" 14 #include "storage/block.h" 15 #include "storage/bufpage.h" 16 #include "storage/itemptr.h" 17 #include "storage/off.h" 18 19 /* 20 * Page opaque data in an inverted index page. 21 * 22 * Note: GIN does not include a page ID word as do the other index types. 23 * This is OK because the opaque data is only 8 bytes and so can be reliably 24 * distinguished by size. Revisit this if the size ever increases. 25 * Further note: as of 9.2, SP-GiST also uses 8-byte special space, as does 26 * BRIN as of 9.5. This is still OK, as long as GIN isn't using all of the 27 * high-order bits in its flags word, because that way the flags word cannot 28 * match the page IDs used by SP-GiST and BRIN. 29 */ 30 typedef struct GinPageOpaqueData 31 { 32 BlockNumber rightlink; /* next page if any */ 33 OffsetNumber maxoff; /* number of PostingItems on GIN_DATA & 34 * ~GIN_LEAF page. On GIN_LIST page, number of 35 * heap tuples. */ 36 uint16 flags; /* see bit definitions below */ 37 } GinPageOpaqueData; 38 39 typedef GinPageOpaqueData *GinPageOpaque; 40 41 #define GIN_DATA (1 << 0) 42 #define GIN_LEAF (1 << 1) 43 #define GIN_DELETED (1 << 2) 44 #define GIN_META (1 << 3) 45 #define GIN_LIST (1 << 4) 46 #define GIN_LIST_FULLROW (1 << 5) /* makes sense only on GIN_LIST page */ 47 #define GIN_INCOMPLETE_SPLIT (1 << 6) /* page was split, but parent not 48 * updated */ 49 #define GIN_COMPRESSED (1 << 7) 50 51 /* Page numbers of fixed-location pages */ 52 #define GIN_METAPAGE_BLKNO (0) 53 #define GIN_ROOT_BLKNO (1) 54 55 typedef struct GinMetaPageData 56 { 57 /* 58 * Pointers to head and tail of pending list, which consists of GIN_LIST 59 * pages. These store fast-inserted entries that haven't yet been moved 60 * into the regular GIN structure. 61 */ 62 BlockNumber head; 63 BlockNumber tail; 64 65 /* 66 * Free space in bytes in the pending list's tail page. 67 */ 68 uint32 tailFreeSize; 69 70 /* 71 * We store both number of pages and number of heap tuples that are in the 72 * pending list. 73 */ 74 BlockNumber nPendingPages; 75 int64 nPendingHeapTuples; 76 77 /* 78 * Statistics for planner use (accurate as of last VACUUM) 79 */ 80 BlockNumber nTotalPages; 81 BlockNumber nEntryPages; 82 BlockNumber nDataPages; 83 int64 nEntries; 84 85 /* 86 * GIN version number (ideally this should have been at the front, but too 87 * late now. Don't move it!) 88 * 89 * Currently 2 (for indexes initialized in 9.4 or later) 90 * 91 * Version 1 (indexes initialized in version 9.1, 9.2 or 9.3), is 92 * compatible, but may contain uncompressed posting tree (leaf) pages and 93 * posting lists. They will be converted to compressed format when 94 * modified. 95 * 96 * Version 0 (indexes initialized in 9.0 or before) is compatible but may 97 * be missing null entries, including both null keys and placeholders. 98 * Reject full-index-scan attempts on such indexes. 99 */ 100 int32 ginVersion; 101 } GinMetaPageData; 102 103 #define GIN_CURRENT_VERSION 2 104 105 #define GinPageGetMeta(p) \ 106 ((GinMetaPageData *) PageGetContents(p)) 107 108 /* 109 * Macros for accessing a GIN index page's opaque data 110 */ 111 #define GinPageGetOpaque(page) ( (GinPageOpaque) PageGetSpecialPointer(page) ) 112 113 #define GinPageIsLeaf(page) ( (GinPageGetOpaque(page)->flags & GIN_LEAF) != 0 ) 114 #define GinPageSetLeaf(page) ( GinPageGetOpaque(page)->flags |= GIN_LEAF ) 115 #define GinPageSetNonLeaf(page) ( GinPageGetOpaque(page)->flags &= ~GIN_LEAF ) 116 #define GinPageIsData(page) ( (GinPageGetOpaque(page)->flags & GIN_DATA) != 0 ) 117 #define GinPageSetData(page) ( GinPageGetOpaque(page)->flags |= GIN_DATA ) 118 #define GinPageIsList(page) ( (GinPageGetOpaque(page)->flags & GIN_LIST) != 0 ) 119 #define GinPageSetList(page) ( GinPageGetOpaque(page)->flags |= GIN_LIST ) 120 #define GinPageHasFullRow(page) ( (GinPageGetOpaque(page)->flags & GIN_LIST_FULLROW) != 0 ) 121 #define GinPageSetFullRow(page) ( GinPageGetOpaque(page)->flags |= GIN_LIST_FULLROW ) 122 #define GinPageIsCompressed(page) ( (GinPageGetOpaque(page)->flags & GIN_COMPRESSED) != 0 ) 123 #define GinPageSetCompressed(page) ( GinPageGetOpaque(page)->flags |= GIN_COMPRESSED ) 124 125 #define GinPageIsDeleted(page) ( (GinPageGetOpaque(page)->flags & GIN_DELETED) != 0 ) 126 #define GinPageSetDeleted(page) ( GinPageGetOpaque(page)->flags |= GIN_DELETED) 127 #define GinPageSetNonDeleted(page) ( GinPageGetOpaque(page)->flags &= ~GIN_DELETED) 128 #define GinPageIsIncompleteSplit(page) ( (GinPageGetOpaque(page)->flags & GIN_INCOMPLETE_SPLIT) != 0 ) 129 130 #define GinPageRightMost(page) ( GinPageGetOpaque(page)->rightlink == InvalidBlockNumber) 131 132 /* 133 * We should reclaim deleted page only once every transaction started before 134 * its deletion is over. 135 */ 136 #define GinPageGetDeleteXid(page) ( ((PageHeader) (page))->pd_prune_xid ) 137 #define GinPageSetDeleteXid(page, xid) ( ((PageHeader) (page))->pd_prune_xid = xid) 138 extern bool GinPageIsRecyclable(Page page); 139 140 /* 141 * We use our own ItemPointerGet(BlockNumber|OffsetNumber) 142 * to avoid Asserts, since sometimes the ip_posid isn't "valid" 143 */ 144 #define GinItemPointerGetBlockNumber(pointer) \ 145 (ItemPointerGetBlockNumberNoCheck(pointer)) 146 147 #define GinItemPointerGetOffsetNumber(pointer) \ 148 (ItemPointerGetOffsetNumberNoCheck(pointer)) 149 150 #define GinItemPointerSetBlockNumber(pointer, blkno) \ 151 (ItemPointerSetBlockNumber((pointer), (blkno))) 152 153 #define GinItemPointerSetOffsetNumber(pointer, offnum) \ 154 (ItemPointerSetOffsetNumber((pointer), (offnum))) 155 156 157 /* 158 * Special-case item pointer values needed by the GIN search logic. 159 * MIN: sorts less than any valid item pointer 160 * MAX: sorts greater than any valid item pointer 161 * LOSSY PAGE: indicates a whole heap page, sorts after normal item 162 * pointers for that page 163 * Note that these are all distinguishable from an "invalid" item pointer 164 * (which is InvalidBlockNumber/0) as well as from all normal item 165 * pointers (which have item numbers in the range 1..MaxHeapTuplesPerPage). 166 */ 167 #define ItemPointerSetMin(p) \ 168 ItemPointerSet((p), (BlockNumber)0, (OffsetNumber)0) 169 #define ItemPointerIsMin(p) \ 170 (GinItemPointerGetOffsetNumber(p) == (OffsetNumber)0 && \ 171 GinItemPointerGetBlockNumber(p) == (BlockNumber)0) 172 #define ItemPointerSetMax(p) \ 173 ItemPointerSet((p), InvalidBlockNumber, (OffsetNumber)0xffff) 174 #define ItemPointerSetLossyPage(p, b) \ 175 ItemPointerSet((p), (b), (OffsetNumber)0xffff) 176 #define ItemPointerIsLossyPage(p) \ 177 (GinItemPointerGetOffsetNumber(p) == (OffsetNumber)0xffff && \ 178 GinItemPointerGetBlockNumber(p) != InvalidBlockNumber) 179 180 /* 181 * Posting item in a non-leaf posting-tree page 182 */ 183 typedef struct 184 { 185 /* We use BlockIdData not BlockNumber to avoid padding space wastage */ 186 BlockIdData child_blkno; 187 ItemPointerData key; 188 } PostingItem; 189 190 #define PostingItemGetBlockNumber(pointer) \ 191 BlockIdGetBlockNumber(&(pointer)->child_blkno) 192 193 #define PostingItemSetBlockNumber(pointer, blockNumber) \ 194 BlockIdSet(&((pointer)->child_blkno), (blockNumber)) 195 196 /* 197 * Category codes to distinguish placeholder nulls from ordinary NULL keys. 198 * 199 * The first two code values were chosen to be compatible with the usual usage 200 * of bool isNull flags. However, casting between bool and GinNullCategory is 201 * risky because of the possibility of different bit patterns and type sizes, 202 * so it is no longer done. 203 * 204 * GIN_CAT_EMPTY_QUERY is never stored in the index; and notice that it is 205 * chosen to sort before not after regular key values. 206 */ 207 typedef signed char GinNullCategory; 208 209 #define GIN_CAT_NORM_KEY 0 /* normal, non-null key value */ 210 #define GIN_CAT_NULL_KEY 1 /* null key value */ 211 #define GIN_CAT_EMPTY_ITEM 2 /* placeholder for zero-key item */ 212 #define GIN_CAT_NULL_ITEM 3 /* placeholder for null item */ 213 #define GIN_CAT_EMPTY_QUERY (-1) /* placeholder for full-scan query */ 214 215 /* 216 * Access macros for null category byte in entry tuples 217 */ 218 #define GinCategoryOffset(itup,ginstate) \ 219 (IndexInfoFindDataOffset((itup)->t_info) + \ 220 ((ginstate)->oneCol ? 0 : sizeof(int16))) 221 #define GinGetNullCategory(itup,ginstate) \ 222 (*((GinNullCategory *) ((char*)(itup) + GinCategoryOffset(itup,ginstate)))) 223 #define GinSetNullCategory(itup,ginstate,c) \ 224 (*((GinNullCategory *) ((char*)(itup) + GinCategoryOffset(itup,ginstate))) = (c)) 225 226 /* 227 * Access macros for leaf-page entry tuples (see discussion in README) 228 */ 229 #define GinGetNPosting(itup) GinItemPointerGetOffsetNumber(&(itup)->t_tid) 230 #define GinSetNPosting(itup,n) ItemPointerSetOffsetNumber(&(itup)->t_tid,n) 231 #define GIN_TREE_POSTING ((OffsetNumber)0xffff) 232 #define GinIsPostingTree(itup) (GinGetNPosting(itup) == GIN_TREE_POSTING) 233 #define GinSetPostingTree(itup, blkno) ( GinSetNPosting((itup),GIN_TREE_POSTING), ItemPointerSetBlockNumber(&(itup)->t_tid, blkno) ) 234 #define GinGetPostingTree(itup) GinItemPointerGetBlockNumber(&(itup)->t_tid) 235 236 #define GIN_ITUP_COMPRESSED (1U << 31) 237 #define GinGetPostingOffset(itup) (GinItemPointerGetBlockNumber(&(itup)->t_tid) & (~GIN_ITUP_COMPRESSED)) 238 #define GinSetPostingOffset(itup,n) ItemPointerSetBlockNumber(&(itup)->t_tid,(n)|GIN_ITUP_COMPRESSED) 239 #define GinGetPosting(itup) ((Pointer) ((char*)(itup) + GinGetPostingOffset(itup))) 240 #define GinItupIsCompressed(itup) ((GinItemPointerGetBlockNumber(&(itup)->t_tid) & GIN_ITUP_COMPRESSED) != 0) 241 242 /* 243 * Maximum size of an item on entry tree page. Make sure that we fit at least 244 * three items on each page. (On regular B-tree indexes, we must fit at least 245 * three items: two data items and the "high key". In GIN entry tree, we don't 246 * currently store the high key explicitly, we just use the rightmost item on 247 * the page, so it would actually be enough to fit two items.) 248 */ 249 #define GinMaxItemSize \ 250 Min(INDEX_SIZE_MASK, \ 251 MAXALIGN_DOWN(((BLCKSZ - \ 252 MAXALIGN(SizeOfPageHeaderData + 3 * sizeof(ItemIdData)) - \ 253 MAXALIGN(sizeof(GinPageOpaqueData))) / 3))) 254 255 /* 256 * Access macros for non-leaf entry tuples 257 */ 258 #define GinGetDownlink(itup) GinItemPointerGetBlockNumber(&(itup)->t_tid) 259 #define GinSetDownlink(itup,blkno) ItemPointerSet(&(itup)->t_tid, blkno, InvalidOffsetNumber) 260 261 262 /* 263 * Data (posting tree) pages 264 * 265 * Posting tree pages don't store regular tuples. Non-leaf pages contain 266 * PostingItems, which are pairs of ItemPointers and child block numbers. 267 * Leaf pages contain GinPostingLists and an uncompressed array of item 268 * pointers. 269 * 270 * In a leaf page, the compressed posting lists are stored after the regular 271 * page header, one after each other. Although we don't store regular tuples, 272 * pd_lower is used to indicate the end of the posting lists. After that, free 273 * space follows. This layout is compatible with the "standard" heap and 274 * index page layout described in bufpage.h, so that we can e.g set buffer_std 275 * when writing WAL records. 276 * 277 * In the special space is the GinPageOpaque struct. 278 */ 279 #define GinDataLeafPageGetPostingList(page) \ 280 (GinPostingList *) ((PageGetContents(page) + MAXALIGN(sizeof(ItemPointerData)))) 281 #define GinDataLeafPageGetPostingListSize(page) \ 282 (((PageHeader) page)->pd_lower - MAXALIGN(SizeOfPageHeaderData) - MAXALIGN(sizeof(ItemPointerData))) 283 284 #define GinDataLeafPageIsEmpty(page) \ 285 (GinPageIsCompressed(page) ? (GinDataLeafPageGetPostingListSize(page) == 0) : (GinPageGetOpaque(page)->maxoff < FirstOffsetNumber)) 286 287 #define GinDataLeafPageGetFreeSpace(page) PageGetExactFreeSpace(page) 288 289 #define GinDataPageGetRightBound(page) ((ItemPointer) PageGetContents(page)) 290 /* 291 * Pointer to the data portion of a posting tree page. For internal pages, 292 * that's the beginning of the array of PostingItems. For compressed leaf 293 * pages, the first compressed posting list. For uncompressed (pre-9.4) leaf 294 * pages, it's the beginning of the ItemPointer array. 295 */ 296 #define GinDataPageGetData(page) \ 297 (PageGetContents(page) + MAXALIGN(sizeof(ItemPointerData))) 298 /* non-leaf pages contain PostingItems */ 299 #define GinDataPageGetPostingItem(page, i) \ 300 ((PostingItem *) (GinDataPageGetData(page) + ((i)-1) * sizeof(PostingItem))) 301 302 /* 303 * Note: there is no GinDataPageGetDataSize macro, because before version 304 * 9.4, we didn't set pd_lower on data pages. There can be pages in the index 305 * that were binary-upgraded from earlier versions and still have an invalid 306 * pd_lower, so we cannot trust it in general. Compressed posting tree leaf 307 * pages are new in 9.4, however, so we can trust them; see 308 * GinDataLeafPageGetPostingListSize. 309 */ 310 #define GinDataPageSetDataSize(page, size) \ 311 { \ 312 Assert(size <= GinDataPageMaxDataSize); \ 313 ((PageHeader) page)->pd_lower = (size) + MAXALIGN(SizeOfPageHeaderData) + MAXALIGN(sizeof(ItemPointerData)); \ 314 } 315 316 #define GinNonLeafDataPageGetFreeSpace(page) \ 317 (GinDataPageMaxDataSize - \ 318 GinPageGetOpaque(page)->maxoff * sizeof(PostingItem)) 319 320 #define GinDataPageMaxDataSize \ 321 (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) \ 322 - MAXALIGN(sizeof(ItemPointerData)) \ 323 - MAXALIGN(sizeof(GinPageOpaqueData))) 324 325 /* 326 * List pages 327 */ 328 #define GinListPageSize \ 329 ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GinPageOpaqueData)) ) 330 331 /* 332 * A compressed posting list. 333 * 334 * Note: This requires 2-byte alignment. 335 */ 336 typedef struct 337 { 338 ItemPointerData first; /* first item in this posting list (unpacked) */ 339 uint16 nbytes; /* number of bytes that follow */ 340 unsigned char bytes[FLEXIBLE_ARRAY_MEMBER]; /* varbyte encoded items */ 341 } GinPostingList; 342 343 #define SizeOfGinPostingList(plist) (offsetof(GinPostingList, bytes) + SHORTALIGN((plist)->nbytes) ) 344 #define GinNextPostingListSegment(cur) ((GinPostingList *) (((char *) (cur)) + SizeOfGinPostingList((cur)))) 345 346 #endif /* GINBLOCK_H */ 347