1 /*-------------------------------------------------------------------------- 2 * ginblock.h 3 * details of structures stored in GIN index blocks 4 * 5 * Copyright (c) 2006-2017, 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/itemptr.h" 16 #include "storage/off.h" 17 18 /* 19 * Page opaque data in an inverted index page. 20 * 21 * Note: GIN does not include a page ID word as do the other index types. 22 * This is OK because the opaque data is only 8 bytes and so can be reliably 23 * distinguished by size. Revisit this if the size ever increases. 24 * Further note: as of 9.2, SP-GiST also uses 8-byte special space, as does 25 * BRIN as of 9.5. This is still OK, as long as GIN isn't using all of the 26 * high-order bits in its flags word, because that way the flags word cannot 27 * match the page IDs used by SP-GiST and BRIN. 28 */ 29 typedef struct GinPageOpaqueData 30 { 31 BlockNumber rightlink; /* next page if any */ 32 OffsetNumber maxoff; /* number of PostingItems on GIN_DATA & 33 * ~GIN_LEAF page. On GIN_LIST page, number of 34 * heap tuples. */ 35 uint16 flags; /* see bit definitions below */ 36 } GinPageOpaqueData; 37 38 typedef GinPageOpaqueData *GinPageOpaque; 39 40 #define GIN_DATA (1 << 0) 41 #define GIN_LEAF (1 << 1) 42 #define GIN_DELETED (1 << 2) 43 #define GIN_META (1 << 3) 44 #define GIN_LIST (1 << 4) 45 #define GIN_LIST_FULLROW (1 << 5) /* makes sense only on GIN_LIST page */ 46 #define GIN_INCOMPLETE_SPLIT (1 << 6) /* page was split, but parent not 47 * updated */ 48 #define GIN_COMPRESSED (1 << 7) 49 50 /* Page numbers of fixed-location pages */ 51 #define GIN_METAPAGE_BLKNO (0) 52 #define GIN_ROOT_BLKNO (1) 53 54 typedef struct GinMetaPageData 55 { 56 /* 57 * Pointers to head and tail of pending list, which consists of GIN_LIST 58 * pages. These store fast-inserted entries that haven't yet been moved 59 * into the regular GIN structure. 60 */ 61 BlockNumber head; 62 BlockNumber tail; 63 64 /* 65 * Free space in bytes in the pending list's tail page. 66 */ 67 uint32 tailFreeSize; 68 69 /* 70 * We store both number of pages and number of heap tuples that are in the 71 * pending list. 72 */ 73 BlockNumber nPendingPages; 74 int64 nPendingHeapTuples; 75 76 /* 77 * Statistics for planner use (accurate as of last VACUUM) 78 */ 79 BlockNumber nTotalPages; 80 BlockNumber nEntryPages; 81 BlockNumber nDataPages; 82 int64 nEntries; 83 84 /* 85 * GIN version number (ideally this should have been at the front, but too 86 * late now. Don't move it!) 87 * 88 * Currently 2 (for indexes initialized in 9.4 or later) 89 * 90 * Version 1 (indexes initialized in version 9.1, 9.2 or 9.3), is 91 * compatible, but may contain uncompressed posting tree (leaf) pages and 92 * posting lists. They will be converted to compressed format when 93 * modified. 94 * 95 * Version 0 (indexes initialized in 9.0 or before) is compatible but may 96 * be missing null entries, including both null keys and placeholders. 97 * Reject full-index-scan attempts on such indexes. 98 */ 99 int32 ginVersion; 100 } GinMetaPageData; 101 102 #define GIN_CURRENT_VERSION 2 103 104 #define GinPageGetMeta(p) \ 105 ((GinMetaPageData *) PageGetContents(p)) 106 107 /* 108 * Macros for accessing a GIN index page's opaque data 109 */ 110 #define GinPageGetOpaque(page) ( (GinPageOpaque) PageGetSpecialPointer(page) ) 111 112 #define GinPageIsLeaf(page) ( (GinPageGetOpaque(page)->flags & GIN_LEAF) != 0 ) 113 #define GinPageSetLeaf(page) ( GinPageGetOpaque(page)->flags |= GIN_LEAF ) 114 #define GinPageSetNonLeaf(page) ( GinPageGetOpaque(page)->flags &= ~GIN_LEAF ) 115 #define GinPageIsData(page) ( (GinPageGetOpaque(page)->flags & GIN_DATA) != 0 ) 116 #define GinPageSetData(page) ( GinPageGetOpaque(page)->flags |= GIN_DATA ) 117 #define GinPageIsList(page) ( (GinPageGetOpaque(page)->flags & GIN_LIST) != 0 ) 118 #define GinPageSetList(page) ( GinPageGetOpaque(page)->flags |= GIN_LIST ) 119 #define GinPageHasFullRow(page) ( (GinPageGetOpaque(page)->flags & GIN_LIST_FULLROW) != 0 ) 120 #define GinPageSetFullRow(page) ( GinPageGetOpaque(page)->flags |= GIN_LIST_FULLROW ) 121 #define GinPageIsCompressed(page) ( (GinPageGetOpaque(page)->flags & GIN_COMPRESSED) != 0 ) 122 #define GinPageSetCompressed(page) ( GinPageGetOpaque(page)->flags |= GIN_COMPRESSED ) 123 124 #define GinPageIsDeleted(page) ( (GinPageGetOpaque(page)->flags & GIN_DELETED) != 0 ) 125 #define GinPageSetDeleted(page) ( GinPageGetOpaque(page)->flags |= GIN_DELETED) 126 #define GinPageSetNonDeleted(page) ( GinPageGetOpaque(page)->flags &= ~GIN_DELETED) 127 #define GinPageIsIncompleteSplit(page) ( (GinPageGetOpaque(page)->flags & GIN_INCOMPLETE_SPLIT) != 0 ) 128 129 #define GinPageRightMost(page) ( GinPageGetOpaque(page)->rightlink == InvalidBlockNumber) 130 131 /* 132 * We should reclaim deleted page only once every transaction started before 133 * its deletion is over. 134 */ 135 #define GinPageGetDeleteXid(page) ( ((PageHeader) (page))->pd_prune_xid ) 136 #define GinPageSetDeleteXid(page, xid) ( ((PageHeader) (page))->pd_prune_xid = xid) 137 #define GinPageIsRecyclable(page) ( PageIsNew(page) || (GinPageIsDeleted(page) \ 138 && TransactionIdPrecedes(GinPageGetDeleteXid(page), RecentGlobalXmin))) 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 ItemPointerIsMax(p) \ 175 (GinItemPointerGetOffsetNumber(p) == (OffsetNumber)0xffff && \ 176 GinItemPointerGetBlockNumber(p) == InvalidBlockNumber) 177 #define ItemPointerSetLossyPage(p, b) \ 178 ItemPointerSet((p), (b), (OffsetNumber)0xffff) 179 #define ItemPointerIsLossyPage(p) \ 180 (GinItemPointerGetOffsetNumber(p) == (OffsetNumber)0xffff && \ 181 GinItemPointerGetBlockNumber(p) != InvalidBlockNumber) 182 183 /* 184 * Posting item in a non-leaf posting-tree page 185 */ 186 typedef struct 187 { 188 /* We use BlockIdData not BlockNumber to avoid padding space wastage */ 189 BlockIdData child_blkno; 190 ItemPointerData key; 191 } PostingItem; 192 193 #define PostingItemGetBlockNumber(pointer) \ 194 BlockIdGetBlockNumber(&(pointer)->child_blkno) 195 196 #define PostingItemSetBlockNumber(pointer, blockNumber) \ 197 BlockIdSet(&((pointer)->child_blkno), (blockNumber)) 198 199 /* 200 * Category codes to distinguish placeholder nulls from ordinary NULL keys. 201 * Note that the datatype size and the first two code values are chosen to be 202 * compatible with the usual usage of bool isNull flags. 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