src/include/access/ginblock.h

   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 */