src/include/access/gin_private.h

   1 /*--------------------------------------------------------------------------
   2  * gin_private.h
   3  *        header file for postgres inverted index access method implementation.
   4  *
   5  *      Copyright (c) 2006-2021, 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/amapi.h"
  14 #include "access/gin.h"
  15 #include "access/ginblock.h"
  16 #include "access/itup.h"
  17 #include "catalog/pg_am_d.h"
  18 #include "fmgr.h"
  19 #include "lib/rbtree.h"
  20 #include "storage/bufmgr.h"
  21
  22 /*
  23  * Storage type for GIN's reloptions
  24  */
  25 typedef struct GinOptions
  26 {
  27         int32           vl_len_;                /* varlena header (do not touch directly!) */
  28         bool            useFastUpdate;  /* use fast updates? */
  29         int                     pendingListCleanupSize; /* maximum size of pending list */
  30 } GinOptions;
  31
  32 #define GIN_DEFAULT_USE_FASTUPDATE      true
  33 #define GinGetUseFastUpdate(relation) \
  34         (AssertMacro(relation->rd_rel->relkind == RELKIND_INDEX && \
  35                                  relation->rd_rel->relam == GIN_AM_OID), \
  36          (relation)->rd_options ? \
  37          ((GinOptions *) (relation)->rd_options)->useFastUpdate : GIN_DEFAULT_USE_FASTUPDATE)
  38 #define GinGetPendingListCleanupSize(relation) \
  39         (AssertMacro(relation->rd_rel->relkind == RELKIND_INDEX && \
  40                                  relation->rd_rel->relam == GIN_AM_OID), \
  41          (relation)->rd_options && \
  42          ((GinOptions *) (relation)->rd_options)->pendingListCleanupSize != -1 ? \
  43          ((GinOptions *) (relation)->rd_options)->pendingListCleanupSize : \
  44          gin_pending_list_limit)
  45
  46
  47 /* Macros for buffer lock/unlock operations */
  48 #define GIN_UNLOCK      BUFFER_LOCK_UNLOCK
  49 #define GIN_SHARE       BUFFER_LOCK_SHARE
  50 #define GIN_EXCLUSIVE  BUFFER_LOCK_EXCLUSIVE
  51
  52
  53 /*
  54  * GinState: working data structure describing the index being worked on
  55  */
  56 typedef struct GinState
  57 {
  58         Relation        index;
  59         bool            oneCol;                 /* true if single-column index */
  60
  61         /*
  62          * origTupdesc is the nominal tuple descriptor of the index, ie, the i'th
  63          * attribute shows the key type (not the input data type!) of the i'th
  64          * index column.  In a single-column index this describes the actual leaf
  65          * index tuples.  In a multi-column index, the actual leaf tuples contain
  66          * a smallint column number followed by a key datum of the appropriate
  67          * type for that column.  We set up tupdesc[i] to describe the actual
  68          * rowtype of the index tuples for the i'th column, ie, (int2, keytype).
  69          * Note that in any case, leaf tuples contain more data than is known to
  70          * the TupleDesc; see access/gin/README for details.
  71          */
  72         TupleDesc       origTupdesc;
  73         TupleDesc       tupdesc[INDEX_MAX_KEYS];
  74
  75         /*
  76          * Per-index-column opclass support functions
  77          */
  78         FmgrInfo        compareFn[INDEX_MAX_KEYS];
  79         FmgrInfo        extractValueFn[INDEX_MAX_KEYS];
  80         FmgrInfo        extractQueryFn[INDEX_MAX_KEYS];
  81         FmgrInfo        consistentFn[INDEX_MAX_KEYS];
  82         FmgrInfo        triConsistentFn[INDEX_MAX_KEYS];
  83         FmgrInfo        comparePartialFn[INDEX_MAX_KEYS];       /* optional method */
  84         /* canPartialMatch[i] is true if comparePartialFn[i] is valid */
  85         bool            canPartialMatch[INDEX_MAX_KEYS];
  86         /* Collations to pass to the support functions */
  87         Oid                     supportCollation[INDEX_MAX_KEYS];
  88 } GinState;
  89
  90
  91 /* ginutil.c */
  92 extern bytea *ginoptions(Datum reloptions, bool validate);
  93 extern void initGinState(GinState *state, Relation index);
  94 extern Buffer GinNewBuffer(Relation index);
  95 extern void GinInitBuffer(Buffer b, uint32 f);
  96 extern void GinInitPage(Page page, uint32 f, Size pageSize);
  97 extern void GinInitMetabuffer(Buffer b);
  98 extern int      ginCompareEntries(GinState *ginstate, OffsetNumber attnum,
  99                                                           Datum a, GinNullCategory categorya,
 100                                                           Datum b, GinNullCategory categoryb);
 101 extern int      ginCompareAttEntries(GinState *ginstate,
 102                                                                  OffsetNumber attnuma, Datum a, GinNullCategory categorya,
 103                                                                  OffsetNumber attnumb, Datum b, GinNullCategory categoryb);
 104 extern Datum *ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
 105                                                                 Datum value, bool isNull,
 106                                                                 int32 *nentries, GinNullCategory **categories);
 107
 108 extern OffsetNumber gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple);
 109 extern Datum gintuple_get_key(GinState *ginstate, IndexTuple tuple,
 110                                                           GinNullCategory *category);
 111
 112 /* gininsert.c */
 113 extern IndexBuildResult *ginbuild(Relation heap, Relation index,
 114                                                                   struct IndexInfo *indexInfo);
 115 extern void ginbuildempty(Relation index);
 116 extern bool gininsert(Relation index, Datum *values, bool *isnull,
 117                                           ItemPointer ht_ctid, Relation heapRel,
 118                                           IndexUniqueCheck checkUnique,
 119                                           bool indexUnchanged,
 120                                           struct IndexInfo *indexInfo);
 121 extern void ginEntryInsert(GinState *ginstate,
 122                                                    OffsetNumber attnum, Datum key, GinNullCategory category,
 123                                                    ItemPointerData *items, uint32 nitem,
 124                                                    GinStatsData *buildStats);
 125
 126 /* ginbtree.c */
 127
 128 typedef struct GinBtreeStack
 129 {
 130         BlockNumber blkno;
 131         Buffer          buffer;
 132         OffsetNumber off;
 133         ItemPointerData iptr;
 134         /* predictNumber contains predicted number of pages on current level */
 135         uint32          predictNumber;
 136         struct GinBtreeStack *parent;
 137 } GinBtreeStack;
 138
 139 typedef struct GinBtreeData *GinBtree;
 140
 141 /* Return codes for GinBtreeData.beginPlaceToPage method */
 142 typedef enum
 143 {
 144         GPTP_NO_WORK,
 145         GPTP_INSERT,
 146         GPTP_SPLIT
 147 } GinPlaceToPageRC;
 148
 149 typedef struct GinBtreeData
 150 {
 151         /* search methods */
 152         BlockNumber (*findChildPage) (GinBtree, GinBtreeStack *);
 153         BlockNumber (*getLeftMostChild) (GinBtree, Page);
 154         bool            (*isMoveRight) (GinBtree, Page);
 155         bool            (*findItem) (GinBtree, GinBtreeStack *);
 156
 157         /* insert methods */
 158         OffsetNumber (*findChildPtr) (GinBtree, Page, BlockNumber, OffsetNumber);
 159         GinPlaceToPageRC (*beginPlaceToPage) (GinBtree, Buffer, GinBtreeStack *, void *, BlockNumber, void **, Page *, Page *);
 160         void            (*execPlaceToPage) (GinBtree, Buffer, GinBtreeStack *, void *, BlockNumber, void *);
 161         void       *(*prepareDownlink) (GinBtree, Buffer);
 162         void            (*fillRoot) (GinBtree, Page, BlockNumber, Page, BlockNumber, Page);
 163
 164         bool            isData;
 165
 166         Relation        index;
 167         BlockNumber rootBlkno;
 168         GinState   *ginstate;           /* not valid in a data scan */
 169         bool            fullScan;
 170         bool            isBuild;
 171
 172         /* Search key for Entry tree */
 173         OffsetNumber entryAttnum;
 174         Datum           entryKey;
 175         GinNullCategory entryCategory;
 176
 177         /* Search key for data tree (posting tree) */
 178         ItemPointerData itemptr;
 179 } GinBtreeData;
 180
 181 /* This represents a tuple to be inserted to entry tree. */
 182 typedef struct
 183 {
 184         IndexTuple      entry;                  /* tuple to insert */
 185         bool            isDelete;               /* delete old tuple at same offset? */
 186 } GinBtreeEntryInsertData;
 187
 188 /*
 189  * This represents an itempointer, or many itempointers, to be inserted to
 190  * a data (posting tree) leaf page
 191  */
 192 typedef struct
 193 {
 194         ItemPointerData *items;
 195         uint32          nitem;
 196         uint32          curitem;
 197 } GinBtreeDataLeafInsertData;
 198
 199 /*
 200  * For internal data (posting tree) pages, the insertion payload is a
 201  * PostingItem
 202  */
 203
 204 extern GinBtreeStack *ginFindLeafPage(GinBtree btree, bool searchMode,
 205                                                                           bool rootConflictCheck, Snapshot snapshot);
 206 extern Buffer ginStepRight(Buffer buffer, Relation index, int lockmode);
 207 extern void freeGinBtreeStack(GinBtreeStack *stack);
 208 extern void ginInsertValue(GinBtree btree, GinBtreeStack *stack,
 209                                                    void *insertdata, GinStatsData *buildStats);
 210
 211 /* ginentrypage.c */
 212 extern IndexTuple GinFormTuple(GinState *ginstate,
 213                                                            OffsetNumber attnum, Datum key, GinNullCategory category,
 214                                                            Pointer data, Size dataSize, int nipd, bool errorTooBig);
 215 extern void ginPrepareEntryScan(GinBtree btree, OffsetNumber attnum,
 216                                                                 Datum key, GinNullCategory category,
 217                                                                 GinState *ginstate);
 218 extern void ginEntryFillRoot(GinBtree btree, Page root, BlockNumber lblkno, Page lpage, BlockNumber rblkno, Page rpage);
 219 extern ItemPointer ginReadTuple(GinState *ginstate, OffsetNumber attnum,
 220                                                                 IndexTuple itup, int *nitems);
 221
 222 /* gindatapage.c */
 223 extern ItemPointer GinDataLeafPageGetItems(Page page, int *nitems, ItemPointerData advancePast);
 224 extern int      GinDataLeafPageGetItemsToTbm(Page page, TIDBitmap *tbm);
 225 extern BlockNumber createPostingTree(Relation index,
 226                                                                          ItemPointerData *items, uint32 nitems,
 227                                                                          GinStatsData *buildStats, Buffer entrybuffer);
 228 extern void GinDataPageAddPostingItem(Page page, PostingItem *data, OffsetNumber offset);
 229 extern void GinPageDeletePostingItem(Page page, OffsetNumber offset);
 230 extern void ginInsertItemPointers(Relation index, BlockNumber rootBlkno,
 231                                                                   ItemPointerData *items, uint32 nitem,
 232                                                                   GinStatsData *buildStats);
 233 extern GinBtreeStack *ginScanBeginPostingTree(GinBtree btree, Relation index, BlockNumber rootBlkno, Snapshot snapshot);
 234 extern void ginDataFillRoot(GinBtree btree, Page root, BlockNumber lblkno, Page lpage, BlockNumber rblkno, Page rpage);
 235
 236 /*
 237  * This is declared in ginvacuum.c, but is passed between ginVacuumItemPointers
 238  * and ginVacuumPostingTreeLeaf and as an opaque struct, so we need a forward
 239  * declaration for it.
 240  */
 241 typedef struct GinVacuumState GinVacuumState;
 242
 243 extern void ginVacuumPostingTreeLeaf(Relation rel, Buffer buf, GinVacuumState *gvs);
 244
 245 /* ginscan.c */
 246
 247 /*
 248  * GinScanKeyData describes a single GIN index qualifier expression.
 249  *
 250  * From each qual expression, we extract one or more specific index search
 251  * conditions, which are represented by GinScanEntryData.  It's quite
 252  * possible for identical search conditions to be requested by more than
 253  * one qual expression, in which case we merge such conditions to have just
 254  * one unique GinScanEntry --- this is particularly important for efficiency
 255  * when dealing with full-index-scan entries.  So there can be multiple
 256  * GinScanKeyData.scanEntry pointers to the same GinScanEntryData.
 257  *
 258  * In each GinScanKeyData, nentries is the true number of entries, while
 259  * nuserentries is the number that extractQueryFn returned (which is what
 260  * we report to consistentFn).  The "user" entries must come first.
 261  */
 262 typedef struct GinScanKeyData *GinScanKey;
 263
 264 typedef struct GinScanEntryData *GinScanEntry;
 265
 266 typedef struct GinScanKeyData
 267 {
 268         /* Real number of entries in scanEntry[] (always > 0) */
 269         uint32          nentries;
 270         /* Number of entries that extractQueryFn and consistentFn know about */
 271         uint32          nuserentries;
 272
 273         /* array of GinScanEntry pointers, one per extracted search condition */
 274         GinScanEntry *scanEntry;
 275
 276         /*
 277          * At least one of the entries in requiredEntries must be present for a
 278          * tuple to match the overall qual.
 279          *
 280          * additionalEntries contains entries that are needed by the consistent
 281          * function to decide if an item matches, but are not sufficient to
 282          * satisfy the qual without entries from requiredEntries.
 283          */
 284         GinScanEntry *requiredEntries;
 285         int                     nrequired;
 286         GinScanEntry *additionalEntries;
 287         int                     nadditional;
 288
 289         /* array of check flags, reported to consistentFn */
 290         GinTernaryValue *entryRes;
 291         bool            (*boolConsistentFn) (GinScanKey key);
 292         GinTernaryValue (*triConsistentFn) (GinScanKey key);
 293         FmgrInfo   *consistentFmgrInfo;
 294         FmgrInfo   *triConsistentFmgrInfo;
 295         Oid                     collation;
 296
 297         /* other data needed for calling consistentFn */
 298         Datum           query;
 299         /* NB: these three arrays have only nuserentries elements! */
 300         Datum      *queryValues;
 301         GinNullCategory *queryCategories;
 302         Pointer    *extra_data;
 303         StrategyNumber strategy;
 304         int32           searchMode;
 305         OffsetNumber attnum;
 306
 307         /*
 308          * An excludeOnly scan key is not able to enumerate all matching tuples.
 309          * That is, to be semantically correct on its own, it would need to have a
 310          * GIN_CAT_EMPTY_QUERY scanEntry, but it doesn't.  Such a key can still be
 311          * used to filter tuples returned by other scan keys, so we will get the
 312          * right answers as long as there's at least one non-excludeOnly scan key
 313          * for each index attribute considered by the search.  For efficiency
 314          * reasons we don't want to have unnecessary GIN_CAT_EMPTY_QUERY entries,
 315          * so we will convert an excludeOnly scan key to non-excludeOnly (by
 316          * adding a GIN_CAT_EMPTY_QUERY scanEntry) only if there are no other
 317          * non-excludeOnly scan keys.
 318          */
 319         bool            excludeOnly;
 320
 321         /*
 322          * Match status data.  curItem is the TID most recently tested (could be a
 323          * lossy-page pointer).  curItemMatches is true if it passes the
 324          * consistentFn test; if so, recheckCurItem is the recheck flag.
 325          * isFinished means that all the input entry streams are finished, so this
 326          * key cannot succeed for any later TIDs.
 327          */
 328         ItemPointerData curItem;
 329         bool            curItemMatches;
 330         bool            recheckCurItem;
 331         bool            isFinished;
 332 }                       GinScanKeyData;
 333
 334 typedef struct GinScanEntryData
 335 {
 336         /* query key and other information from extractQueryFn */
 337         Datum           queryKey;
 338         GinNullCategory queryCategory;
 339         bool            isPartialMatch;
 340         Pointer         extra_data;
 341         StrategyNumber strategy;
 342         int32           searchMode;
 343         OffsetNumber attnum;
 344
 345         /* Current page in posting tree */
 346         Buffer          buffer;
 347
 348         /* current ItemPointer to heap */
 349         ItemPointerData curItem;
 350
 351         /* for a partial-match or full-scan query, we accumulate all TIDs here */
 352         TIDBitmap  *matchBitmap;
 353         TBMIterator *matchIterator;
 354         TBMIterateResult *matchResult;
 355
 356         /* used for Posting list and one page in Posting tree */
 357         ItemPointerData *list;
 358         int                     nlist;
 359         OffsetNumber offset;
 360
 361         bool            isFinished;
 362         bool            reduceResult;
 363         uint32          predictNumberResult;
 364         GinBtreeData btree;
 365 }                       GinScanEntryData;
 366
 367 typedef struct GinScanOpaqueData
 368 {
 369         MemoryContext tempCtx;
 370         GinState        ginstate;
 371
 372         GinScanKey      keys;                   /* one per scan qualifier expr */
 373         uint32          nkeys;
 374
 375         GinScanEntry *entries;          /* one per index search condition */
 376         uint32          totalentries;
 377         uint32          allocentries;   /* allocated length of entries[] */
 378
 379         MemoryContext keyCtx;           /* used to hold key and entry data */
 380
 381         bool            isVoidRes;              /* true if query is unsatisfiable */
 382 } GinScanOpaqueData;
 383
 384 typedef GinScanOpaqueData *GinScanOpaque;
 385
 386 extern IndexScanDesc ginbeginscan(Relation rel, int nkeys, int norderbys);
 387 extern void ginendscan(IndexScanDesc scan);
 388 extern void ginrescan(IndexScanDesc scan, ScanKey key, int nscankeys,
 389                                           ScanKey orderbys, int norderbys);
 390 extern void ginNewScanKey(IndexScanDesc scan);
 391 extern void ginFreeScanKeys(GinScanOpaque so);
 392
 393 /* ginget.c */
 394 extern int64 gingetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
 395
 396 /* ginlogic.c */
 397 extern void ginInitConsistentFunction(GinState *ginstate, GinScanKey key);
 398
 399 /* ginvacuum.c */
 400 extern IndexBulkDeleteResult *ginbulkdelete(IndexVacuumInfo *info,
 401                                                                                         IndexBulkDeleteResult *stats,
 402                                                                                         IndexBulkDeleteCallback callback,
 403                                                                                         void *callback_state);
 404 extern IndexBulkDeleteResult *ginvacuumcleanup(IndexVacuumInfo *info,
 405                                                                                            IndexBulkDeleteResult *stats);
 406 extern ItemPointer ginVacuumItemPointers(GinVacuumState *gvs,
 407                                                                                  ItemPointerData *items, int nitem, int *nremaining);
 408
 409 /* ginvalidate.c */
 410 extern bool ginvalidate(Oid opclassoid);
 411 extern void ginadjustmembers(Oid opfamilyoid,
 412                                                          Oid opclassoid,
 413                                                          List *operators,
 414                                                          List *functions);
 415
 416 /* ginbulk.c */
 417 typedef struct GinEntryAccumulator
 418 {
 419         RBTNode         rbtnode;
 420         Datum           key;
 421         GinNullCategory category;
 422         OffsetNumber attnum;
 423         bool            shouldSort;
 424         ItemPointerData *list;
 425         uint32          maxcount;               /* allocated size of list[] */
 426         uint32          count;                  /* current number of list[] entries */
 427 } GinEntryAccumulator;
 428
 429 typedef struct
 430 {
 431         GinState   *ginstate;
 432         Size            allocatedMemory;
 433         GinEntryAccumulator *entryallocator;
 434         uint32          eas_used;
 435         RBTree     *tree;
 436         RBTreeIterator tree_walk;
 437 } BuildAccumulator;
 438
 439 extern void ginInitBA(BuildAccumulator *accum);
 440 extern void ginInsertBAEntries(BuildAccumulator *accum,
 441                                                            ItemPointer heapptr, OffsetNumber attnum,
 442                                                            Datum *entries, GinNullCategory *categories,
 443                                                            int32 nentries);
 444 extern void ginBeginBAScan(BuildAccumulator *accum);
 445 extern ItemPointerData *ginGetBAEntry(BuildAccumulator *accum,
 446                                                                           OffsetNumber *attnum, Datum *key, GinNullCategory *category,
 447                                                                           uint32 *n);
 448
 449 /* ginfast.c */
 450
 451 typedef struct GinTupleCollector
 452 {
 453         IndexTuple *tuples;
 454         uint32          ntuples;
 455         uint32          lentuples;
 456         uint32          sumsize;
 457 } GinTupleCollector;
 458
 459 extern void ginHeapTupleFastInsert(GinState *ginstate,
 460                                                                    GinTupleCollector *collector);
 461 extern void ginHeapTupleFastCollect(GinState *ginstate,
 462                                                                         GinTupleCollector *collector,
 463                                                                         OffsetNumber attnum, Datum value, bool isNull,
 464                                                                         ItemPointer ht_ctid);
 465 extern void ginInsertCleanup(GinState *ginstate, bool full_clean,
 466                                                          bool fill_fsm, bool forceCleanup, IndexBulkDeleteResult *stats);
 467
 468 /* ginpostinglist.c */
 469
 470 extern GinPostingList *ginCompressPostingList(const ItemPointer ipd, int nipd,
 471                                                                                           int maxsize, int *nwritten);
 472 extern int      ginPostingListDecodeAllSegmentsToTbm(GinPostingList *ptr, int totalsize, TIDBitmap *tbm);
 473
 474 extern ItemPointer ginPostingListDecodeAllSegments(GinPostingList *ptr, int len, int *ndecoded);
 475 extern ItemPointer ginPostingListDecode(GinPostingList *ptr, int *ndecoded);
 476 extern ItemPointer ginMergeItemPointers(ItemPointerData *a, uint32 na,
 477                                                                                 ItemPointerData *b, uint32 nb,
 478                                                                                 int *nmerged);
 479
 480 /*
 481  * Merging the results of several gin scans compares item pointers a lot,
 482  * so we want this to be inlined.
 483  */
 484 static inline int
 485 ginCompareItemPointers(ItemPointer a, ItemPointer b)
 486 {
 487         uint64          ia = (uint64) GinItemPointerGetBlockNumber(a) << 32 | GinItemPointerGetOffsetNumber(a);
 488         uint64          ib = (uint64) GinItemPointerGetBlockNumber(b) << 32 | GinItemPointerGetOffsetNumber(b);
 489
 490         if (ia == ib)
 491                 return 0;
 492         else if (ia > ib)
 493                 return 1;
 494         else
 495                 return -1;
 496 }
 497
 498 extern int      ginTraverseLock(Buffer buffer, bool searchMode);
 499
 500 #endif                                                  /* GIN_PRIVATE_H */