util/X86MAC64/include/postgresql/server/access/gin_private.h

   1 /*--------------------------------------------------------------------------
   2  * gin_private.h
   3  *        header file for postgres inverted index access method implementation.
   4  *
   5  *      Copyright (c) 2006-2014, PostgreSQL Global Development Group
   6  *
   7  *      src/include/access/gin_private.h
   8  *--------------------------------------------------------------------------
   9  */
  10 #ifndef GIN_PRIVATE_H
  11 #define GIN_PRIVATE_H
  12
  13 #include "access/genam.h"
  14 #include "access/gin.h"
  15 #include "access/itup.h"
  16 #include "fmgr.h"
  17 #include "storage/bufmgr.h"
  18 #include "utils/rbtree.h"
  19
  20
  21 /*
  22  * Page opaque data in an inverted index page.
  23  *
  24  * Note: GIN does not include a page ID word as do the other index types.
  25  * This is OK because the opaque data is only 8 bytes and so can be reliably
  26  * distinguished by size.  Revisit this if the size ever increases.
  27  * Further note: as of 9.2, SP-GiST also uses 8-byte special space.  This is
  28  * still OK, as long as GIN isn't using all of the high-order bits in its
  29  * flags word, because that way the flags word cannot match the page ID used
  30  * by SP-GiST.
  31  */
  32 typedef struct GinPageOpaqueData
  33 {
  34         BlockNumber rightlink;          /* next page if any */
  35         OffsetNumber maxoff;            /* number of PostingItems on GIN_DATA &
  36                                                                  * ~GIN_LEAF page. On GIN_LIST page, number of
  37                                                                  * heap tuples. */
  38         uint16          flags;                  /* see bit definitions below */
  39 } GinPageOpaqueData;
  40
  41 typedef GinPageOpaqueData *GinPageOpaque;
  42
  43 #define GIN_DATA                  (1 << 0)
  44 #define GIN_LEAF                  (1 << 1)
  45 #define GIN_DELETED               (1 << 2)
  46 #define GIN_META                  (1 << 3)
  47 #define GIN_LIST                  (1 << 4)
  48 #define GIN_LIST_FULLROW  (1 << 5)              /* makes sense only on GIN_LIST page */
  49 #define GIN_INCOMPLETE_SPLIT (1 << 6)   /* page was split, but parent not
  50                                                                                  * updated */
  51 #define GIN_COMPRESSED    (1 << 7)
  52
  53 /* Page numbers of fixed-location pages */
  54 #define GIN_METAPAGE_BLKNO      (0)
  55 #define GIN_ROOT_BLKNO          (1)
  56
  57 typedef struct GinMetaPageData
  58 {
  59         /*
  60          * Pointers to head and tail of pending list, which consists of GIN_LIST
  61          * pages.  These store fast-inserted entries that haven't yet been moved
  62          * into the regular GIN structure.
  63          */
  64         BlockNumber head;
  65         BlockNumber tail;
  66
  67         /*
  68          * Free space in bytes in the pending list's tail page.
  69          */
  70         uint32          tailFreeSize;
  71
  72         /*
  73          * We store both number of pages and number of heap tuples that are in the
  74          * pending list.
  75          */
  76         BlockNumber nPendingPages;
  77         int64           nPendingHeapTuples;
  78
  79         /*
  80          * Statistics for planner use (accurate as of last VACUUM)
  81          */
  82         BlockNumber nTotalPages;
  83         BlockNumber nEntryPages;
  84         BlockNumber nDataPages;
  85         int64           nEntries;
  86
  87         /*
  88          * GIN version number (ideally this should have been at the front, but too
  89          * late now.  Don't move it!)
  90          *
  91          * Currently 2 (for indexes initialized in 9.4 or later)
  92          *
  93          * Version 1 (indexes initialized in version 9.1, 9.2 or 9.3), is
  94          * compatible, but may contain uncompressed posting tree (leaf) pages and
  95          * posting lists. They will be converted to compressed format when
  96          * modified.
  97          *
  98          * Version 0 (indexes initialized in 9.0 or before) is compatible but may
  99          * be missing null entries, including both null keys and placeholders.
 100          * Reject full-index-scan attempts on such indexes.
 101          */
 102         int32           ginVersion;
 103 } GinMetaPageData;
 104
 105 #define GIN_CURRENT_VERSION             2
 106
 107 #define GinPageGetMeta(p) \
 108         ((GinMetaPageData *) PageGetContents(p))
 109
 110 /*
 111  * Macros for accessing a GIN index page's opaque data
 112  */
 113 #define GinPageGetOpaque(page) ( (GinPageOpaque) PageGetSpecialPointer(page) )
 114
 115 #define GinPageIsLeaf(page)    ( GinPageGetOpaque(page)->flags & GIN_LEAF )
 116 #define GinPageSetLeaf(page)   ( GinPageGetOpaque(page)->flags |= GIN_LEAF )
 117 #define GinPageSetNonLeaf(page)    ( GinPageGetOpaque(page)->flags &= ~GIN_LEAF )
 118 #define GinPageIsData(page)    ( GinPageGetOpaque(page)->flags & GIN_DATA )
 119 #define GinPageSetData(page)   ( GinPageGetOpaque(page)->flags |= GIN_DATA )
 120 #define GinPageIsList(page)    ( GinPageGetOpaque(page)->flags & GIN_LIST )
 121 #define GinPageSetList(page)   ( GinPageGetOpaque(page)->flags |= GIN_LIST )
 122 #define GinPageHasFullRow(page)    ( GinPageGetOpaque(page)->flags & GIN_LIST_FULLROW )
 123 #define GinPageSetFullRow(page)   ( GinPageGetOpaque(page)->flags |= GIN_LIST_FULLROW )
 124 #define GinPageIsCompressed(page)        ( GinPageGetOpaque(page)->flags & GIN_COMPRESSED )
 125 #define GinPageSetCompressed(page)       ( GinPageGetOpaque(page)->flags |= GIN_COMPRESSED )
 126
 127 #define GinPageIsDeleted(page) ( GinPageGetOpaque(page)->flags & GIN_DELETED)
 128 #define GinPageSetDeleted(page)    ( GinPageGetOpaque(page)->flags |= GIN_DELETED)
 129 #define GinPageSetNonDeleted(page) ( GinPageGetOpaque(page)->flags &= ~GIN_DELETED)
 130 #define GinPageIsIncompleteSplit(page) ( GinPageGetOpaque(page)->flags & GIN_INCOMPLETE_SPLIT)
 131
 132 #define GinPageRightMost(page) ( GinPageGetOpaque(page)->rightlink == InvalidBlockNumber)
 133
 134 /*
 135  * We use our own ItemPointerGet(BlockNumber|OffsetNumber)
 136  * to avoid Asserts, since sometimes the ip_posid isn't "valid"
 137  */
 138 #define GinItemPointerGetBlockNumber(pointer) \
 139         BlockIdGetBlockNumber(&(pointer)->ip_blkid)
 140
 141 #define GinItemPointerGetOffsetNumber(pointer) \
 142         ((pointer)->ip_posid)
 143
 144 /*
 145  * Special-case item pointer values needed by the GIN search logic.
 146  *      MIN: sorts less than any valid item pointer
 147  *      MAX: sorts greater than any valid item pointer
 148  *      LOSSY PAGE: indicates a whole heap page, sorts after normal item
 149  *                              pointers for that page
 150  * Note that these are all distinguishable from an "invalid" item pointer
 151  * (which is InvalidBlockNumber/0) as well as from all normal item
 152  * pointers (which have item numbers in the range 1..MaxHeapTuplesPerPage).
 153  */
 154 #define ItemPointerSetMin(p)  \
 155         ItemPointerSet((p), (BlockNumber)0, (OffsetNumber)0)
 156 #define ItemPointerIsMin(p)  \
 157         (GinItemPointerGetOffsetNumber(p) == (OffsetNumber)0 && \
 158          GinItemPointerGetBlockNumber(p) == (BlockNumber)0)
 159 #define ItemPointerSetMax(p)  \
 160         ItemPointerSet((p), InvalidBlockNumber, (OffsetNumber)0xffff)
 161 #define ItemPointerIsMax(p)  \
 162         (GinItemPointerGetOffsetNumber(p) == (OffsetNumber)0xffff && \
 163          GinItemPointerGetBlockNumber(p) == InvalidBlockNumber)
 164 #define ItemPointerSetLossyPage(p, b)  \
 165         ItemPointerSet((p), (b), (OffsetNumber)0xffff)
 166 #define ItemPointerIsLossyPage(p)  \
 167         (GinItemPointerGetOffsetNumber(p) == (OffsetNumber)0xffff && \
 168          GinItemPointerGetBlockNumber(p) != InvalidBlockNumber)
 169
 170 /*
 171  * Posting item in a non-leaf posting-tree page
 172  */
 173 typedef struct
 174 {
 175         /* We use BlockIdData not BlockNumber to avoid padding space wastage */
 176         BlockIdData child_blkno;
 177         ItemPointerData key;
 178 } PostingItem;
 179
 180 #define PostingItemGetBlockNumber(pointer) \
 181         BlockIdGetBlockNumber(&(pointer)->child_blkno)
 182
 183 #define PostingItemSetBlockNumber(pointer, blockNumber) \
 184         BlockIdSet(&((pointer)->child_blkno), (blockNumber))
 185
 186 /*
 187  * Category codes to distinguish placeholder nulls from ordinary NULL keys.
 188  * Note that the datatype size and the first two code values are chosen to be
 189  * compatible with the usual usage of bool isNull flags.
 190  *
 191  * GIN_CAT_EMPTY_QUERY is never stored in the index; and notice that it is
 192  * chosen to sort before not after regular key values.
 193  */
 194 typedef signed char GinNullCategory;
 195
 196 #define GIN_CAT_NORM_KEY                0               /* normal, non-null key value */
 197 #define GIN_CAT_NULL_KEY                1               /* null key value */
 198 #define GIN_CAT_EMPTY_ITEM              2               /* placeholder for zero-key item */
 199 #define GIN_CAT_NULL_ITEM               3               /* placeholder for null item */
 200 #define GIN_CAT_EMPTY_QUERY             (-1)    /* placeholder for full-scan query */
 201
 202 /*
 203  * Access macros for null category byte in entry tuples
 204  */
 205 #define GinCategoryOffset(itup,ginstate) \
 206         (IndexInfoFindDataOffset((itup)->t_info) + \
 207          ((ginstate)->oneCol ? 0 : sizeof(int16)))
 208 #define GinGetNullCategory(itup,ginstate) \
 209         (*((GinNullCategory *) ((char*)(itup) + GinCategoryOffset(itup,ginstate))))
 210 #define GinSetNullCategory(itup,ginstate,c) \
 211         (*((GinNullCategory *) ((char*)(itup) + GinCategoryOffset(itup,ginstate))) = (c))
 212
 213 /*
 214  * Access macros for leaf-page entry tuples (see discussion in README)
 215  */
 216 #define GinGetNPosting(itup)    GinItemPointerGetOffsetNumber(&(itup)->t_tid)
 217 #define GinSetNPosting(itup,n)  ItemPointerSetOffsetNumber(&(itup)->t_tid,n)
 218 #define GIN_TREE_POSTING                ((OffsetNumber)0xffff)
 219 #define GinIsPostingTree(itup)  (GinGetNPosting(itup) == GIN_TREE_POSTING)
 220 #define GinSetPostingTree(itup, blkno)  ( GinSetNPosting((itup),GIN_TREE_POSTING), ItemPointerSetBlockNumber(&(itup)->t_tid, blkno) )
 221 #define GinGetPostingTree(itup) GinItemPointerGetBlockNumber(&(itup)->t_tid)
 222
 223 #define GIN_ITUP_COMPRESSED             (1U << 31)
 224 #define GinGetPostingOffset(itup)       (GinItemPointerGetBlockNumber(&(itup)->t_tid) & (~GIN_ITUP_COMPRESSED))
 225 #define GinSetPostingOffset(itup,n) ItemPointerSetBlockNumber(&(itup)->t_tid,(n)|GIN_ITUP_COMPRESSED)
 226 #define GinGetPosting(itup)                     ((Pointer) ((char*)(itup) + GinGetPostingOffset(itup)))
 227 #define GinItupIsCompressed(itup)       (GinItemPointerGetBlockNumber(&(itup)->t_tid) & GIN_ITUP_COMPRESSED)
 228
 229 /*
 230  * Maximum size of an item on entry tree page. Make sure that we fit at least
 231  * three items on each page. (On regular B-tree indexes, we must fit at least
 232  * three items: two data items and the "high key". In GIN entry tree, we don't
 233  * currently store the high key explicitly, we just use the rightmost item on
 234  * the page, so it would actually be enough to fit two items.)
 235  */
 236 #define GinMaxItemSize \
 237         Min(INDEX_SIZE_MASK, \
 238                 MAXALIGN_DOWN(((BLCKSZ - \
 239                                                 MAXALIGN(SizeOfPageHeaderData + 3 * sizeof(ItemIdData)) - \
 240                                                 MAXALIGN(sizeof(GinPageOpaqueData))) / 3)))
 241
 242 /*
 243  * Access macros for non-leaf entry tuples
 244  */
 245 #define GinGetDownlink(itup)    GinItemPointerGetBlockNumber(&(itup)->t_tid)
 246 #define GinSetDownlink(itup,blkno)      ItemPointerSet(&(itup)->t_tid, blkno, InvalidOffsetNumber)
 247
 248
 249 /*
 250  * Data (posting tree) pages
 251  *
 252  * Posting tree pages don't store regular tuples. Non-leaf pages contain
 253  * PostingItems, which are pairs of ItemPointers and child block numbers.
 254  * Leaf pages contain GinPostingLists and an uncompressed array of item
 255  * pointers.
 256  *
 257  * In a leaf page, the compressed posting lists are stored after the regular
 258  * page header, one after each other. Although we don't store regular tuples,
 259  * pd_lower is used to indicate the end of the posting lists. After that, free
 260  * space follows.  This layout is compatible with the "standard" heap and
 261  * index page layout described in bufpage.h, so that we can e.g set buffer_std
 262  * when writing WAL records.
 263  *
 264  * In the special space is the GinPageOpaque struct.
 265  */
 266 #define GinDataLeafPageGetPostingList(page) \
 267         (GinPostingList *) ((PageGetContents(page) + MAXALIGN(sizeof(ItemPointerData))))
 268 #define GinDataLeafPageGetPostingListSize(page) \
 269         (((PageHeader) page)->pd_lower - MAXALIGN(SizeOfPageHeaderData) - MAXALIGN(sizeof(ItemPointerData)))
 270
 271 #define GinDataLeafPageIsEmpty(page) \
 272         (GinPageIsCompressed(page) ? (GinDataLeafPageGetPostingListSize(page) == 0) : (GinPageGetOpaque(page)->maxoff < FirstOffsetNumber))
 273
 274 #define GinDataLeafPageGetFreeSpace(page) PageGetExactFreeSpace(page)
 275
 276 #define GinDataPageGetRightBound(page)  ((ItemPointer) PageGetContents(page))
 277 /*
 278  * Pointer to the data portion of a posting tree page. For internal pages,
 279  * that's the beginning of the array of PostingItems. For compressed leaf
 280  * pages, the first compressed posting list. For uncompressed (pre-9.4) leaf
 281  * pages, it's the beginning of the ItemPointer array.
 282  */
 283 #define GinDataPageGetData(page)        \
 284         (PageGetContents(page) + MAXALIGN(sizeof(ItemPointerData)))
 285 /* non-leaf pages contain PostingItems */
 286 #define GinDataPageGetPostingItem(page, i)      \
 287         ((PostingItem *) (GinDataPageGetData(page) + ((i)-1) * sizeof(PostingItem)))
 288
 289 /*
 290  * Note: there is no GinDataPageGetDataSize macro, because before version
 291  * 9.4, we didn't set pd_lower on data pages. There can be pages in the index
 292  * that were binary-upgraded from earlier versions and still have an invalid
 293  * pd_lower, so we cannot trust it in general. Compressed posting tree leaf
 294  * pages are new in 9.4, however, so we can trust them; see
 295  * GinDataLeafPageGetPostingListSize.
 296  */
 297 #define GinDataPageSetDataSize(page, size) \
 298         { \
 299                 Assert(size <= GinDataPageMaxDataSize); \
 300                 ((PageHeader) page)->pd_lower = (size) + MAXALIGN(SizeOfPageHeaderData) + MAXALIGN(sizeof(ItemPointerData)); \
 301         }
 302
 303 #define GinNonLeafDataPageGetFreeSpace(page)    \
 304         (GinDataPageMaxDataSize - \
 305          GinPageGetOpaque(page)->maxoff * sizeof(PostingItem))
 306
 307 #define GinDataPageMaxDataSize  \
 308         (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) \
 309          - MAXALIGN(sizeof(ItemPointerData)) \
 310          - MAXALIGN(sizeof(GinPageOpaqueData)))
 311
 312 /*
 313  * List pages
 314  */
 315 #define GinListPageSize  \
 316         ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GinPageOpaqueData)) )
 317
 318 /*
 319  * Storage type for GIN's reloptions
 320  */
 321 typedef struct GinOptions
 322 {
 323         int32           vl_len_;                /* varlena header (do not touch directly!) */
 324         bool            useFastUpdate;  /* use fast updates? */
 325 } GinOptions;
 326
 327 #define GIN_DEFAULT_USE_FASTUPDATE      true
 328 #define GinGetUseFastUpdate(relation) \
 329         ((relation)->rd_options ? \
 330          ((GinOptions *) (relation)->rd_options)->useFastUpdate : GIN_DEFAULT_USE_FASTUPDATE)
 331
 332
 333 /* Macros for buffer lock/unlock operations */
 334 #define GIN_UNLOCK      BUFFER_LOCK_UNLOCK
 335 #define GIN_SHARE       BUFFER_LOCK_SHARE
 336 #define GIN_EXCLUSIVE  BUFFER_LOCK_EXCLUSIVE
 337
 338
 339 /*
 340  * GinState: working data structure describing the index being worked on
 341  */
 342 typedef struct GinState
 343 {
 344         Relation        index;
 345         bool            oneCol;                 /* true if single-column index */
 346
 347         /*
 348          * origTupDesc is the nominal tuple descriptor of the index, ie, the i'th
 349          * attribute shows the key type (not the input data type!) of the i'th
 350          * index column.  In a single-column index this describes the actual leaf
 351          * index tuples.  In a multi-column index, the actual leaf tuples contain
 352          * a smallint column number followed by a key datum of the appropriate
 353          * type for that column.  We set up tupdesc[i] to describe the actual
 354          * rowtype of the index tuples for the i'th column, ie, (int2, keytype).
 355          * Note that in any case, leaf tuples contain more data than is known to
 356          * the TupleDesc; see access/gin/README for details.
 357          */
 358         TupleDesc       origTupdesc;
 359         TupleDesc       tupdesc[INDEX_MAX_KEYS];
 360
 361         /*
 362          * Per-index-column opclass support functions
 363          */
 364         FmgrInfo        compareFn[INDEX_MAX_KEYS];
 365         FmgrInfo        extractValueFn[INDEX_MAX_KEYS];
 366         FmgrInfo        extractQueryFn[INDEX_MAX_KEYS];
 367         FmgrInfo        consistentFn[INDEX_MAX_KEYS];
 368         FmgrInfo        triConsistentFn[INDEX_MAX_KEYS];
 369         FmgrInfo        comparePartialFn[INDEX_MAX_KEYS];               /* optional method */
 370         /* canPartialMatch[i] is true if comparePartialFn[i] is valid */
 371         bool            canPartialMatch[INDEX_MAX_KEYS];
 372         /* Collations to pass to the support functions */
 373         Oid                     supportCollation[INDEX_MAX_KEYS];
 374 } GinState;
 375
 376
 377 /*
 378  * A compressed posting list.
 379  *
 380  * Note: This requires 2-byte alignment.
 381  */
 382 typedef struct
 383 {
 384         ItemPointerData first;          /* first item in this posting list (unpacked) */
 385         uint16          nbytes;                 /* number of bytes that follow */
 386         unsigned char bytes[1];         /* varbyte encoded items (variable length) */
 387 } GinPostingList;
 388
 389 #define SizeOfGinPostingList(plist) (offsetof(GinPostingList, bytes) + SHORTALIGN((plist)->nbytes) )
 390 #define GinNextPostingListSegment(cur) ((GinPostingList *) (((char *) (cur)) + SizeOfGinPostingList((cur))))
 391
 392
 393 /* XLog stuff */
 394
 395 #define XLOG_GIN_CREATE_INDEX  0x00
 396
 397 #define XLOG_GIN_CREATE_PTREE  0x10
 398
 399 typedef struct ginxlogCreatePostingTree
 400 {
 401         RelFileNode node;
 402         BlockNumber blkno;
 403         uint32          size;
 404         /* A compressed posting list follows */
 405 } ginxlogCreatePostingTree;
 406
 407 #define XLOG_GIN_INSERT  0x20
 408
 409 /*
 410  * The format of the insertion record varies depending on the page type.
 411  * ginxlogInsert is the common part between all variants.
 412  */
 413 typedef struct
 414 {
 415         RelFileNode node;
 416         BlockNumber blkno;
 417         uint16          flags;                  /* GIN_SPLIT_ISLEAF and/or GIN_SPLIT_ISDATA */
 418
 419         /*
 420          * FOLLOWS:
 421          *
 422          * 1. if not leaf page, block numbers of the left and right child pages
 423          * whose split this insertion finishes. As BlockIdData[2] (beware of
 424          * adding fields before this that would make them not 16-bit aligned)
 425          *
 426          * 2. an ginxlogInsertEntry or ginxlogRecompressDataLeaf struct, depending
 427          * on tree type.
 428          *
 429          * NB: the below structs are only 16-bit aligned when appended to a
 430          * ginxlogInsert struct! Beware of adding fields to them that require
 431          * stricter alignment.
 432          */
 433 } ginxlogInsert;
 434
 435 typedef struct
 436 {
 437         OffsetNumber offset;
 438         bool            isDelete;
 439         IndexTupleData tuple;           /* variable length */
 440 } ginxlogInsertEntry;
 441
 442
 443 typedef struct
 444 {
 445         uint16          nactions;
 446
 447         /* Variable number of 'actions' follow */
 448 } ginxlogRecompressDataLeaf;
 449
 450 /*
 451  * Note: this struct is currently not used in code, and only acts as
 452  * documentation. The WAL record format is as specified here, but the code
 453  * uses straight access through a Pointer and memcpy to read/write these.
 454  */
 455 typedef struct
 456 {
 457         uint8           segno;                  /* segment this action applies to */
 458         char            type;                   /* action type (see below) */
 459
 460         /*
 461          * Action-specific data follows. For INSERT and REPLACE actions that is a
 462          * GinPostingList struct. For ADDITEMS, a uint16 for the number of items
 463          * added, followed by the items themselves as ItemPointers. DELETE actions
 464          * have no further data.
 465          */
 466 }       ginxlogSegmentAction;
 467
 468 /* Action types */
 469 #define GIN_SEGMENT_UNMODIFIED  0               /* no action (not used in WAL records) */
 470 #define GIN_SEGMENT_DELETE              1               /* a whole segment is removed */
 471 #define GIN_SEGMENT_INSERT              2               /* a whole segment is added */
 472 #define GIN_SEGMENT_REPLACE             3               /* a segment is replaced */
 473 #define GIN_SEGMENT_ADDITEMS    4               /* items are added to existing segment */
 474
 475 typedef struct
 476 {
 477         OffsetNumber offset;
 478         PostingItem newitem;
 479 } ginxlogInsertDataInternal;
 480
 481
 482 #define XLOG_GIN_SPLIT  0x30
 483
 484 typedef struct ginxlogSplit
 485 {
 486         RelFileNode node;
 487         BlockNumber lblkno;
 488         BlockNumber rblkno;
 489         BlockNumber rrlink;                     /* right link, or root's blocknumber if root
 490                                                                  * split */
 491         BlockNumber leftChildBlkno; /* valid on a non-leaf split */
 492         BlockNumber rightChildBlkno;
 493         uint16          flags;
 494
 495         /* follows: one of the following structs */
 496 } ginxlogSplit;
 497
 498 /*
 499  * Flags used in ginxlogInsert and ginxlogSplit records
 500  */
 501 #define GIN_INSERT_ISDATA       0x01    /* for both insert and split records */
 502 #define GIN_INSERT_ISLEAF       0x02    /* .. */
 503 #define GIN_SPLIT_ROOT          0x04    /* only for split records */
 504
 505 typedef struct
 506 {
 507         OffsetNumber separator;
 508         OffsetNumber nitem;
 509
 510         /* FOLLOWS: IndexTuples */
 511 } ginxlogSplitEntry;
 512
 513 typedef struct
 514 {
 515         uint16          lsize;
 516         uint16          rsize;
 517         ItemPointerData lrightbound;    /* new right bound of left page */
 518         ItemPointerData rrightbound;    /* new right bound of right page */
 519
 520         /* FOLLOWS: new compressed posting lists of left and right page */
 521         char            newdata[1];
 522 } ginxlogSplitDataLeaf;
 523
 524 typedef struct
 525 {
 526         OffsetNumber separator;
 527         OffsetNumber nitem;
 528         ItemPointerData rightbound;
 529
 530         /* FOLLOWS: array of PostingItems */
 531 } ginxlogSplitDataInternal;
 532
 533 /*
 534  * Vacuum simply WAL-logs the whole page, when anything is modified. This
 535  * functionally identical heap_newpage records, but is kept separate for
 536  * debugging purposes. (When inspecting the WAL stream, it's easier to see
 537  * what's going on when GIN vacuum records are marked as such, not as heap
 538  * records.) This is currently only used for entry tree leaf pages.
 539  */
 540 #define XLOG_GIN_VACUUM_PAGE    0x40
 541
 542 typedef struct ginxlogVacuumPage
 543 {
 544         RelFileNode node;
 545         BlockNumber blkno;
 546         uint16          hole_offset;    /* number of bytes before "hole" */
 547         uint16          hole_length;    /* number of bytes in "hole" */
 548         /* entire page contents (minus the hole) follow at end of record */
 549 } ginxlogVacuumPage;
 550
 551 /*
 552  * Vacuuming posting tree leaf page is WAL-logged like recompression caused
 553  * by insertion.
 554  */
 555 #define XLOG_GIN_VACUUM_DATA_LEAF_PAGE  0x90
 556
 557 typedef struct ginxlogVacuumDataLeafPage
 558 {
 559         RelFileNode node;
 560         BlockNumber blkno;
 561
 562         ginxlogRecompressDataLeaf data;
 563 } ginxlogVacuumDataLeafPage;
 564
 565 #define XLOG_GIN_DELETE_PAGE    0x50
 566
 567 typedef struct ginxlogDeletePage
 568 {
 569         RelFileNode node;
 570         BlockNumber blkno;
 571         BlockNumber parentBlkno;
 572         OffsetNumber parentOffset;
 573         BlockNumber leftBlkno;
 574         BlockNumber rightLink;
 575 } ginxlogDeletePage;
 576
 577 #define XLOG_GIN_UPDATE_META_PAGE 0x60
 578
 579 typedef struct ginxlogUpdateMeta
 580 {
 581         RelFileNode node;
 582         GinMetaPageData metadata;
 583         BlockNumber prevTail;
 584         BlockNumber newRightlink;
 585         int32           ntuples;                /* if ntuples > 0 then metadata.tail was
 586                                                                  * updated with that many tuples; else new sub
 587                                                                  * list was inserted */
 588         /* array of inserted tuples follows */
 589 } ginxlogUpdateMeta;
 590
 591 #define XLOG_GIN_INSERT_LISTPAGE  0x70
 592
 593 typedef struct ginxlogInsertListPage
 594 {
 595         RelFileNode node;
 596         BlockNumber blkno;
 597         BlockNumber rightlink;
 598         int32           ntuples;
 599         /* array of inserted tuples follows */
 600 } ginxlogInsertListPage;
 601
 602 #define XLOG_GIN_DELETE_LISTPAGE  0x80
 603
 604 #define GIN_NDELETE_AT_ONCE 16
 605 typedef struct ginxlogDeleteListPages
 606 {
 607         RelFileNode node;
 608         GinMetaPageData metadata;
 609         int32           ndeleted;
 610         BlockNumber toDelete[GIN_NDELETE_AT_ONCE];
 611 } ginxlogDeleteListPages;
 612
 613
 614 /* ginutil.c */
 615 extern Datum ginoptions(PG_FUNCTION_ARGS);
 616 extern void initGinState(GinState *state, Relation index);
 617 extern Buffer GinNewBuffer(Relation index);
 618 extern void GinInitBuffer(Buffer b, uint32 f);
 619 extern void GinInitPage(Page page, uint32 f, Size pageSize);
 620 extern void GinInitMetabuffer(Buffer b);
 621 extern int ginCompareEntries(GinState *ginstate, OffsetNumber attnum,
 622                                   Datum a, GinNullCategory categorya,
 623                                   Datum b, GinNullCategory categoryb);
 624 extern int ginCompareAttEntries(GinState *ginstate,
 625                                          OffsetNumber attnuma, Datum a, GinNullCategory categorya,
 626                                    OffsetNumber attnumb, Datum b, GinNullCategory categoryb);
 627 extern Datum *ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
 628                                   Datum value, bool isNull,
 629                                   int32 *nentries, GinNullCategory **categories);
 630
 631 extern OffsetNumber gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple);
 632 extern Datum gintuple_get_key(GinState *ginstate, IndexTuple tuple,
 633                                  GinNullCategory *category);
 634
 635 /* gininsert.c */
 636 extern Datum ginbuild(PG_FUNCTION_ARGS);
 637 extern Datum ginbuildempty(PG_FUNCTION_ARGS);
 638 extern Datum gininsert(PG_FUNCTION_ARGS);
 639 extern void ginEntryInsert(GinState *ginstate,
 640                            OffsetNumber attnum, Datum key, GinNullCategory category,
 641                            ItemPointerData *items, uint32 nitem,
 642                            GinStatsData *buildStats);
 643
 644 /* ginbtree.c */
 645
 646 typedef struct GinBtreeStack
 647 {
 648         BlockNumber blkno;
 649         Buffer          buffer;
 650         OffsetNumber off;
 651         ItemPointerData iptr;
 652         /* predictNumber contains predicted number of pages on current level */
 653         uint32          predictNumber;
 654         struct GinBtreeStack *parent;
 655 } GinBtreeStack;
 656
 657 typedef struct GinBtreeData *GinBtree;
 658
 659 /* Return codes for GinBtreeData.placeToPage method */
 660 typedef enum
 661 {
 662         UNMODIFIED,
 663         INSERTED,
 664         SPLIT
 665 } GinPlaceToPageRC;
 666
 667 typedef struct GinBtreeData
 668 {
 669         /* search methods */
 670         BlockNumber (*findChildPage) (GinBtree, GinBtreeStack *);
 671         BlockNumber (*getLeftMostChild) (GinBtree, Page);
 672         bool            (*isMoveRight) (GinBtree, Page);
 673         bool            (*findItem) (GinBtree, GinBtreeStack *);
 674
 675         /* insert methods */
 676         OffsetNumber (*findChildPtr) (GinBtree, Page, BlockNumber, OffsetNumber);
 677         GinPlaceToPageRC (*placeToPage) (GinBtree, Buffer, GinBtreeStack *, void *, BlockNumber, XLogRecData **, Page *, Page *);
 678         void       *(*prepareDownlink) (GinBtree, Buffer);
 679         void            (*fillRoot) (GinBtree, Page, BlockNumber, Page, BlockNumber, Page);
 680
 681         bool            isData;
 682
 683         Relation        index;
 684         BlockNumber rootBlkno;
 685         GinState   *ginstate;           /* not valid in a data scan */
 686         bool            fullScan;
 687         bool            isBuild;
 688
 689         /* Search key for Entry tree */
 690         OffsetNumber entryAttnum;
 691         Datum           entryKey;
 692         GinNullCategory entryCategory;
 693
 694         /* Search key for data tree (posting tree) */
 695         ItemPointerData itemptr;
 696 } GinBtreeData;
 697
 698 /* This represents a tuple to be inserted to entry tree. */
 699 typedef struct
 700 {
 701         IndexTuple      entry;                  /* tuple to insert */
 702         bool            isDelete;               /* delete old tuple at same offset? */
 703 } GinBtreeEntryInsertData;
 704
 705 /*
 706  * This represents an itempointer, or many itempointers, to be inserted to
 707  * a data (posting tree) leaf page
 708  */
 709 typedef struct
 710 {
 711         ItemPointerData *items;
 712         uint32          nitem;
 713         uint32          curitem;
 714 } GinBtreeDataLeafInsertData;
 715
 716 /*
 717  * For internal data (posting tree) pages, the insertion payload is a
 718  * PostingItem
 719  */
 720
 721 extern GinBtreeStack *ginFindLeafPage(GinBtree btree, bool searchMode);
 722 extern Buffer ginStepRight(Buffer buffer, Relation index, int lockmode);
 723 extern void freeGinBtreeStack(GinBtreeStack *stack);
 724 extern void ginInsertValue(GinBtree btree, GinBtreeStack *stack,
 725                            void *insertdata, GinStatsData *buildStats);
 726
 727 /* ginentrypage.c */
 728 extern IndexTuple GinFormTuple(GinState *ginstate,
 729                          OffsetNumber attnum, Datum key, GinNullCategory category,
 730                          Pointer data, Size dataSize, int nipd, bool errorTooBig);
 731 extern void ginPrepareEntryScan(GinBtree btree, OffsetNumber attnum,
 732                                         Datum key, GinNullCategory category,
 733                                         GinState *ginstate);
 734 extern void ginEntryFillRoot(GinBtree btree, Page root, BlockNumber lblkno, Page lpage, BlockNumber rblkno, Page rpage);
 735 extern ItemPointer ginReadTuple(GinState *ginstate, OffsetNumber attnum,
 736                          IndexTuple itup, int *nitems);
 737
 738 /* gindatapage.c */
 739 extern ItemPointer GinDataLeafPageGetItems(Page page, int *nitems, ItemPointerData advancePast);
 740 extern int      GinDataLeafPageGetItemsToTbm(Page page, TIDBitmap *tbm);
 741 extern BlockNumber createPostingTree(Relation index,
 742                                   ItemPointerData *items, uint32 nitems,
 743                                   GinStatsData *buildStats);
 744 extern void GinDataPageAddPostingItem(Page page, PostingItem *data, OffsetNumber offset);
 745 extern void GinPageDeletePostingItem(Page page, OffsetNumber offset);
 746 extern void ginInsertItemPointers(Relation index, BlockNumber rootBlkno,
 747                                           ItemPointerData *items, uint32 nitem,
 748                                           GinStatsData *buildStats);
 749 extern GinBtreeStack *ginScanBeginPostingTree(GinBtree btree, Relation index, BlockNumber rootBlkno);
 750 extern void ginDataFillRoot(GinBtree btree, Page root, BlockNumber lblkno, Page lpage, BlockNumber rblkno, Page rpage);
 751 extern void ginPrepareDataScan(GinBtree btree, Relation index, BlockNumber rootBlkno);
 752
 753 /*
 754  * This is declared in ginvacuum.c, but is passed between ginVacuumItemPointers
 755  * and ginVacuumPostingTreeLeaf and as an opaque struct, so we need a forward
 756  * declaration for it.
 757  */
 758 typedef struct GinVacuumState GinVacuumState;
 759
 760 extern void ginVacuumPostingTreeLeaf(Relation rel, Buffer buf, GinVacuumState *gvs);
 761
 762 /* ginscan.c */
 763
 764 /*
 765  * GinScanKeyData describes a single GIN index qualifier expression.
 766  *
 767  * From each qual expression, we extract one or more specific index search
 768  * conditions, which are represented by GinScanEntryData.  It's quite
 769  * possible for identical search conditions to be requested by more than
 770  * one qual expression, in which case we merge such conditions to have just
 771  * one unique GinScanEntry --- this is particularly important for efficiency
 772  * when dealing with full-index-scan entries.  So there can be multiple
 773  * GinScanKeyData.scanEntry pointers to the same GinScanEntryData.
 774  *
 775  * In each GinScanKeyData, nentries is the true number of entries, while
 776  * nuserentries is the number that extractQueryFn returned (which is what
 777  * we report to consistentFn).  The "user" entries must come first.
 778  */
 779 typedef struct GinScanKeyData *GinScanKey;
 780
 781 typedef struct GinScanEntryData *GinScanEntry;
 782
 783 typedef struct GinScanKeyData
 784 {
 785         /* Real number of entries in scanEntry[] (always > 0) */
 786         uint32          nentries;
 787         /* Number of entries that extractQueryFn and consistentFn know about */
 788         uint32          nuserentries;
 789
 790         /* array of GinScanEntry pointers, one per extracted search condition */
 791         GinScanEntry *scanEntry;
 792
 793         /*
 794          * At least one of the entries in requiredEntries must be present for a
 795          * tuple to match the overall qual.
 796          *
 797          * additionalEntries contains entries that are needed by the consistent
 798          * function to decide if an item matches, but are not sufficient to
 799          * satisfy the qual without entries from requiredEntries.
 800          */
 801         GinScanEntry *requiredEntries;
 802         int                     nrequired;
 803         GinScanEntry *additionalEntries;
 804         int                     nadditional;
 805
 806         /* array of check flags, reported to consistentFn */
 807         bool       *entryRes;
 808         bool            (*boolConsistentFn) (GinScanKey key);
 809         GinTernaryValue (*triConsistentFn) (GinScanKey key);
 810         FmgrInfo   *consistentFmgrInfo;
 811         FmgrInfo   *triConsistentFmgrInfo;
 812         Oid                     collation;
 813
 814         /* other data needed for calling consistentFn */
 815         Datum           query;
 816         /* NB: these three arrays have only nuserentries elements! */
 817         Datum      *queryValues;
 818         GinNullCategory *queryCategories;
 819         Pointer    *extra_data;
 820         StrategyNumber strategy;
 821         int32           searchMode;
 822         OffsetNumber attnum;
 823
 824         /*
 825          * Match status data.  curItem is the TID most recently tested (could be a
 826          * lossy-page pointer).  curItemMatches is TRUE if it passes the
 827          * consistentFn test; if so, recheckCurItem is the recheck flag.
 828          * isFinished means that all the input entry streams are finished, so this
 829          * key cannot succeed for any later TIDs.
 830          */
 831         ItemPointerData curItem;
 832         bool            curItemMatches;
 833         bool            recheckCurItem;
 834         bool            isFinished;
 835 }       GinScanKeyData;
 836
 837 typedef struct GinScanEntryData
 838 {
 839         /* query key and other information from extractQueryFn */
 840         Datum           queryKey;
 841         GinNullCategory queryCategory;
 842         bool            isPartialMatch;
 843         Pointer         extra_data;
 844         StrategyNumber strategy;
 845         int32           searchMode;
 846         OffsetNumber attnum;
 847
 848         /* Current page in posting tree */
 849         Buffer          buffer;
 850
 851         /* current ItemPointer to heap */
 852         ItemPointerData curItem;
 853
 854         /* for a partial-match or full-scan query, we accumulate all TIDs here */
 855         TIDBitmap  *matchBitmap;
 856         TBMIterator *matchIterator;
 857         TBMIterateResult *matchResult;
 858
 859         /* used for Posting list and one page in Posting tree */
 860         ItemPointerData *list;
 861         int                     nlist;
 862         OffsetNumber offset;
 863
 864         bool            isFinished;
 865         bool            reduceResult;
 866         uint32          predictNumberResult;
 867         GinBtreeData btree;
 868 }       GinScanEntryData;
 869
 870 typedef struct GinScanOpaqueData
 871 {
 872         MemoryContext tempCtx;
 873         GinState        ginstate;
 874
 875         GinScanKey      keys;                   /* one per scan qualifier expr */
 876         uint32          nkeys;
 877
 878         GinScanEntry *entries;          /* one per index search condition */
 879         uint32          totalentries;
 880         uint32          allocentries;   /* allocated length of entries[] */
 881
 882         bool            isVoidRes;              /* true if query is unsatisfiable */
 883 } GinScanOpaqueData;
 884
 885 typedef GinScanOpaqueData *GinScanOpaque;
 886
 887 extern Datum ginbeginscan(PG_FUNCTION_ARGS);
 888 extern Datum ginendscan(PG_FUNCTION_ARGS);
 889 extern Datum ginrescan(PG_FUNCTION_ARGS);
 890 extern Datum ginmarkpos(PG_FUNCTION_ARGS);
 891 extern Datum ginrestrpos(PG_FUNCTION_ARGS);
 892 extern void ginNewScanKey(IndexScanDesc scan);
 893 extern void ginFreeScanKeys(GinScanOpaque so);
 894
 895 /* ginget.c */
 896 extern Datum gingetbitmap(PG_FUNCTION_ARGS);
 897
 898 /* ginlogic.c */
 899 extern void ginInitConsistentFunction(GinState *ginstate, GinScanKey key);
 900
 901 /* ginvacuum.c */
 902 extern Datum ginbulkdelete(PG_FUNCTION_ARGS);
 903 extern Datum ginvacuumcleanup(PG_FUNCTION_ARGS);
 904 extern ItemPointer ginVacuumItemPointers(GinVacuumState *gvs,
 905                                           ItemPointerData *items, int nitem, int *nremaining);
 906
 907 /* ginbulk.c */
 908 typedef struct GinEntryAccumulator
 909 {
 910         RBNode          rbnode;
 911         Datum           key;
 912         GinNullCategory category;
 913         OffsetNumber attnum;
 914         bool            shouldSort;
 915         ItemPointerData *list;
 916         uint32          maxcount;               /* allocated size of list[] */
 917         uint32          count;                  /* current number of list[] entries */
 918 } GinEntryAccumulator;
 919
 920 typedef struct
 921 {
 922         GinState   *ginstate;
 923         long            allocatedMemory;
 924         GinEntryAccumulator *entryallocator;
 925         uint32          eas_used;
 926         RBTree     *tree;
 927 } BuildAccumulator;
 928
 929 extern void ginInitBA(BuildAccumulator *accum);
 930 extern void ginInsertBAEntries(BuildAccumulator *accum,
 931                                    ItemPointer heapptr, OffsetNumber attnum,
 932                                    Datum *entries, GinNullCategory *categories,
 933                                    int32 nentries);
 934 extern void ginBeginBAScan(BuildAccumulator *accum);
 935 extern ItemPointerData *ginGetBAEntry(BuildAccumulator *accum,
 936                           OffsetNumber *attnum, Datum *key, GinNullCategory *category,
 937                           uint32 *n);
 938
 939 /* ginfast.c */
 940
 941 typedef struct GinTupleCollector
 942 {
 943         IndexTuple *tuples;
 944         uint32          ntuples;
 945         uint32          lentuples;
 946         uint32          sumsize;
 947 } GinTupleCollector;
 948
 949 extern void ginHeapTupleFastInsert(GinState *ginstate,
 950                                            GinTupleCollector *collector);
 951 extern void ginHeapTupleFastCollect(GinState *ginstate,
 952                                                 GinTupleCollector *collector,
 953                                                 OffsetNumber attnum, Datum value, bool isNull,
 954                                                 ItemPointer ht_ctid);
 955 extern void ginInsertCleanup(GinState *ginstate,
 956                                  bool vac_delay, IndexBulkDeleteResult *stats);
 957
 958 /* ginpostinglist.c */
 959
 960 extern GinPostingList *ginCompressPostingList(const ItemPointer ptrs, int nptrs,
 961                                            int maxsize, int *nwritten);
 962 extern int      ginPostingListDecodeAllSegmentsToTbm(GinPostingList *ptr, int totalsize, TIDBitmap *tbm);
 963
 964 extern ItemPointer ginPostingListDecodeAllSegments(GinPostingList *ptr, int len, int *ndecoded);
 965 extern ItemPointer ginPostingListDecode(GinPostingList *ptr, int *ndecoded);
 966 extern ItemPointer ginMergeItemPointers(ItemPointerData *a, uint32 na,
 967                                          ItemPointerData *b, uint32 nb,
 968                                          int *nmerged);
 969
 970 /*
 971  * Merging the results of several gin scans compares item pointers a lot,
 972  * so we want this to be inlined. But if the compiler doesn't support that,
 973  * fall back on the non-inline version from itemptr.c. See STATIC_IF_INLINE in
 974  * c.h.
 975  */
 976 #ifdef PG_USE_INLINE
 977 static inline int
 978 ginCompareItemPointers(ItemPointer a, ItemPointer b)
 979 {
 980         uint64          ia = (uint64) a->ip_blkid.bi_hi << 32 | (uint64) a->ip_blkid.bi_lo << 16 | a->ip_posid;
 981         uint64          ib = (uint64) b->ip_blkid.bi_hi << 32 | (uint64) b->ip_blkid.bi_lo << 16 | b->ip_posid;
 982
 983         if (ia == ib)
 984                 return 0;
 985         else if (ia > ib)
 986                 return 1;
 987         else
 988                 return -1;
 989 }
 990 #else
 991 #define ginCompareItemPointers(a, b) ItemPointerCompare(a, b)
 992 #endif   /* PG_USE_INLINE */
 993
 994 #endif   /* GIN_PRIVATE_H */