granicus.if.org Git - postgresql/blob - src/include/access/gist_private.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * gist_private.h
   4  *        private declarations for GiST -- declarations related to the
   5  *        internal implementation of GiST, not the public API
   6  *
   7  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * src/include/access/gist_private.h
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #ifndef GIST_PRIVATE_H
  15 #define GIST_PRIVATE_H
  16
  17 #include "access/amapi.h"
  18 #include "access/gist.h"
  19 #include "access/itup.h"
  20 #include "fmgr.h"
  21 #include "lib/pairingheap.h"
  22 #include "storage/bufmgr.h"
  23 #include "storage/buffile.h"
  24 #include "utils/hsearch.h"
  25 #include "access/genam.h"
  26
  27 /*
  28  * Maximum number of "halves" a page can be split into in one operation.
  29  * Typically a split produces 2 halves, but can be more if keys have very
  30  * different lengths, or when inserting multiple keys in one operation (as
  31  * when inserting downlinks to an internal node).  There is no theoretical
  32  * limit on this, but in practice if you get more than a handful page halves
  33  * in one split, there's something wrong with the opclass implementation.
  34  * GIST_MAX_SPLIT_PAGES is an arbitrary limit on that, used to size some
  35  * local arrays used during split.  Note that there is also a limit on the
  36  * number of buffers that can be held locked at a time, MAX_SIMUL_LWLOCKS,
  37  * so if you raise this higher than that limit, you'll just get a different
  38  * error.
  39  */
  40 #define GIST_MAX_SPLIT_PAGES            75
  41
  42 /* Buffer lock modes */
  43 #define GIST_SHARE      BUFFER_LOCK_SHARE
  44 #define GIST_EXCLUSIVE  BUFFER_LOCK_EXCLUSIVE
  45 #define GIST_UNLOCK BUFFER_LOCK_UNLOCK
  46
  47 typedef struct
  48 {
  49         BlockNumber prev;
  50         uint32          freespace;
  51         char            tupledata[FLEXIBLE_ARRAY_MEMBER];
  52 } GISTNodeBufferPage;
  53
  54 #define BUFFER_PAGE_DATA_OFFSET MAXALIGN(offsetof(GISTNodeBufferPage, tupledata))
  55 /* Returns free space in node buffer page */
  56 #define PAGE_FREE_SPACE(nbp) (nbp->freespace)
  57 /* Checks if node buffer page is empty */
  58 #define PAGE_IS_EMPTY(nbp) (nbp->freespace == BLCKSZ - BUFFER_PAGE_DATA_OFFSET)
  59 /* Checks if node buffers page don't contain sufficient space for index tuple */
  60 #define PAGE_NO_SPACE(nbp, itup) (PAGE_FREE_SPACE(nbp) < \
  61                                                                                 MAXALIGN(IndexTupleSize(itup)))
  62
  63 /*
  64  * GISTSTATE: information needed for any GiST index operation
  65  *
  66  * This struct retains call info for the index's opclass-specific support
  67  * functions (per index column), plus the index's tuple descriptor.
  68  *
  69  * scanCxt holds the GISTSTATE itself as well as any data that lives for the
  70  * lifetime of the index operation.  We pass this to the support functions
  71  * via fn_mcxt, so that they can store scan-lifespan data in it.  The
  72  * functions are invoked in tempCxt, which is typically short-lifespan
  73  * (that is, it's reset after each tuple).  However, tempCxt can be the same
  74  * as scanCxt if we're not bothering with per-tuple context resets.
  75  */
  76 typedef struct GISTSTATE
  77 {
  78         MemoryContext scanCxt;          /* context for scan-lifespan data */
  79         MemoryContext tempCxt;          /* short-term context for calling functions */
  80
  81         TupleDesc       tupdesc;                /* index's tuple descriptor */
  82         TupleDesc       fetchTupdesc;   /* tuple descriptor for tuples returned in an
  83                                                                  * index-only scan */
  84
  85         FmgrInfo        consistentFn[INDEX_MAX_KEYS];
  86         FmgrInfo        unionFn[INDEX_MAX_KEYS];
  87         FmgrInfo        compressFn[INDEX_MAX_KEYS];
  88         FmgrInfo        decompressFn[INDEX_MAX_KEYS];
  89         FmgrInfo        penaltyFn[INDEX_MAX_KEYS];
  90         FmgrInfo        picksplitFn[INDEX_MAX_KEYS];
  91         FmgrInfo        equalFn[INDEX_MAX_KEYS];
  92         FmgrInfo        distanceFn[INDEX_MAX_KEYS];
  93         FmgrInfo        fetchFn[INDEX_MAX_KEYS];
  94
  95         /* Collations to pass to the support functions */
  96         Oid                     supportCollation[INDEX_MAX_KEYS];
  97 } GISTSTATE;
  98
  99
 100 /*
 101  * During a GiST index search, we must maintain a queue of unvisited items,
 102  * which can be either individual heap tuples or whole index pages.  If it
 103  * is an ordered search, the unvisited items should be visited in distance
 104  * order.  Unvisited items at the same distance should be visited in
 105  * depth-first order, that is heap items first, then lower index pages, then
 106  * upper index pages; this rule avoids doing extra work during a search that
 107  * ends early due to LIMIT.
 108  *
 109  * To perform an ordered search, we use a pairing heap to manage the
 110  * distance-order queue.  In a non-ordered search (no order-by operators),
 111  * we use it to return heap tuples before unvisited index pages, to
 112  * ensure depth-first order, but all entries are otherwise considered
 113  * equal.
 114  */
 115
 116 /* Individual heap tuple to be visited */
 117 typedef struct GISTSearchHeapItem
 118 {
 119         ItemPointerData heapPtr;
 120         bool            recheck;                /* T if quals must be rechecked */
 121         bool            recheckDistances;               /* T if distances must be rechecked */
 122         HeapTuple       recontup;               /* data reconstructed from the index, used in
 123                                                                  * index-only scans */
 124         OffsetNumber offnum;            /* track offset in page to mark tuple as
 125                                                                  * LP_DEAD */
 126 } GISTSearchHeapItem;
 127
 128 /* Unvisited item, either index page or heap tuple */
 129 typedef struct GISTSearchItem
 130 {
 131         pairingheap_node phNode;
 132         BlockNumber blkno;                      /* index page number, or InvalidBlockNumber */
 133         union
 134         {
 135                 GistNSN         parentlsn;      /* parent page's LSN, if index page */
 136                 /* we must store parentlsn to detect whether a split occurred */
 137                 GISTSearchHeapItem heap;        /* heap info, if heap tuple */
 138         }                       data;
 139         double          distances[FLEXIBLE_ARRAY_MEMBER];               /* numberOfOrderBys
 140                                                                                                                  * entries */
 141 } GISTSearchItem;
 142
 143 #define GISTSearchItemIsHeap(item)      ((item).blkno == InvalidBlockNumber)
 144
 145 #define SizeOfGISTSearchItem(n_distances) (offsetof(GISTSearchItem, distances) + sizeof(double) * (n_distances))
 146
 147 /*
 148  * GISTScanOpaqueData: private state for a scan of a GiST index
 149  */
 150 typedef struct GISTScanOpaqueData
 151 {
 152         GISTSTATE  *giststate;          /* index information, see above */
 153         Oid                *orderByTypes;       /* datatypes of ORDER BY expressions */
 154
 155         pairingheap *queue;                     /* queue of unvisited items */
 156         MemoryContext queueCxt;         /* context holding the queue */
 157         bool            qual_ok;                /* false if qual can never be satisfied */
 158         bool            firstCall;              /* true until first gistgettuple call */
 159
 160         /* pre-allocated workspace arrays */
 161         double     *distances;          /* output area for gistindex_keytest */
 162
 163         /* info about killed items if any (killedItems is NULL if never used) */
 164         OffsetNumber *killedItems;      /* offset numbers of killed items */
 165         int                     numKilled;              /* number of currently stored items */
 166         BlockNumber curBlkno;           /* current number of block */
 167         GistNSN         curPageLSN;             /* pos in the WAL stream when page was read */
 168
 169         /* In a non-ordered search, returnable heap items are stored here: */
 170         GISTSearchHeapItem pageData[BLCKSZ / sizeof(IndexTupleData)];
 171         OffsetNumber nPageData;         /* number of valid items in array */
 172         OffsetNumber curPageData;       /* next item to return */
 173         MemoryContext pageDataCxt;      /* context holding the fetched tuples, for
 174                                                                  * index-only scans */
 175 } GISTScanOpaqueData;
 176
 177 typedef GISTScanOpaqueData *GISTScanOpaque;
 178
 179 /* despite the name, gistxlogPage is not part of any xlog record */
 180 typedef struct gistxlogPage
 181 {
 182         BlockNumber blkno;
 183         int                     num;                    /* number of index tuples following */
 184 } gistxlogPage;
 185
 186 /* SplitedPageLayout - gistSplit function result */
 187 typedef struct SplitedPageLayout
 188 {
 189         gistxlogPage block;
 190         IndexTupleData *list;
 191         int                     lenlist;
 192         IndexTuple      itup;                   /* union key for page */
 193         Page            page;                   /* to operate */
 194         Buffer          buffer;                 /* to write after all proceed */
 195
 196         struct SplitedPageLayout *next;
 197 } SplitedPageLayout;
 198
 199 /*
 200  * GISTInsertStack used for locking buffers and transfer arguments during
 201  * insertion
 202  */
 203 typedef struct GISTInsertStack
 204 {
 205         /* current page */
 206         BlockNumber blkno;
 207         Buffer          buffer;
 208         Page            page;
 209
 210         /*
 211          * log sequence number from page->lsn to recognize page update and compare
 212          * it with page's nsn to recognize page split
 213          */
 214         GistNSN         lsn;
 215
 216         /* offset of the downlink in the parent page, that points to this page */
 217         OffsetNumber downlinkoffnum;
 218
 219         /* pointer to parent */
 220         struct GISTInsertStack *parent;
 221 } GISTInsertStack;
 222
 223 /* Working state and results for multi-column split logic in gistsplit.c */
 224 typedef struct GistSplitVector
 225 {
 226         GIST_SPLITVEC splitVector;      /* passed to/from user PickSplit method */
 227
 228         Datum           spl_lattr[INDEX_MAX_KEYS];              /* Union of subkeys in
 229                                                                                                  * splitVector.spl_left */
 230         bool            spl_lisnull[INDEX_MAX_KEYS];
 231
 232         Datum           spl_rattr[INDEX_MAX_KEYS];              /* Union of subkeys in
 233                                                                                                  * splitVector.spl_right */
 234         bool            spl_risnull[INDEX_MAX_KEYS];
 235
 236         bool       *spl_dontcare;       /* flags tuples which could go to either side
 237                                                                  * of the split for zero penalty */
 238 } GistSplitVector;
 239
 240 typedef struct
 241 {
 242         Relation        r;
 243         Size            freespace;              /* free space to be left */
 244
 245         GISTInsertStack *stack;
 246 } GISTInsertState;
 247
 248 /* root page of a gist index */
 249 #define GIST_ROOT_BLKNO                         0
 250
 251 /*
 252  * Before PostgreSQL 9.1, we used to rely on so-called "invalid tuples" on
 253  * inner pages to finish crash recovery of incomplete page splits. If a crash
 254  * happened in the middle of a page split, so that the downlink pointers were
 255  * not yet inserted, crash recovery inserted a special downlink pointer. The
 256  * semantics of an invalid tuple was that it if you encounter one in a scan,
 257  * it must always be followed, because we don't know if the tuples on the
 258  * child page match or not.
 259  *
 260  * We no longer create such invalid tuples, we now mark the left-half of such
 261  * an incomplete split with the F_FOLLOW_RIGHT flag instead, and finish the
 262  * split properly the next time we need to insert on that page. To retain
 263  * on-disk compatibility for the sake of pg_upgrade, we still store 0xffff as
 264  * the offset number of all inner tuples. If we encounter any invalid tuples
 265  * with 0xfffe during insertion, we throw an error, though scans still handle
 266  * them. You should only encounter invalid tuples if you pg_upgrade a pre-9.1
 267  * gist index which already has invalid tuples in it because of a crash. That
 268  * should be rare, and you are recommended to REINDEX anyway if you have any
 269  * invalid tuples in an index, so throwing an error is as far as we go with
 270  * supporting that.
 271  */
 272 #define TUPLE_IS_VALID          0xffff
 273 #define TUPLE_IS_INVALID        0xfffe
 274
 275 #define  GistTupleIsInvalid(itup)       ( ItemPointerGetOffsetNumber( &((itup)->t_tid) ) == TUPLE_IS_INVALID )
 276 #define  GistTupleSetValid(itup)        ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_VALID )
 277
 278
 279
 280
 281 /*
 282  * A buffer attached to an internal node, used when building an index in
 283  * buffering mode.
 284  */
 285 typedef struct
 286 {
 287         BlockNumber nodeBlocknum;       /* index block # this buffer is for */
 288         int32           blocksCount;    /* current # of blocks occupied by buffer */
 289
 290         BlockNumber pageBlocknum;       /* temporary file block # */
 291         GISTNodeBufferPage *pageBuffer;         /* in-memory buffer page */
 292
 293         /* is this buffer queued for emptying? */
 294         bool            queuedForEmptying;
 295
 296         /* is this a temporary copy, not in the hash table? */
 297         bool            isTemp;
 298
 299         int                     level;                  /* 0 == leaf */
 300 } GISTNodeBuffer;
 301
 302 /*
 303  * Does specified level have buffers? (Beware of multiple evaluation of
 304  * arguments.)
 305  */
 306 #define LEVEL_HAS_BUFFERS(nlevel, gfbb) \
 307         ((nlevel) != 0 && (nlevel) % (gfbb)->levelStep == 0 && \
 308          (nlevel) != (gfbb)->rootlevel)
 309
 310 /* Is specified buffer at least half-filled (should be queued for emptying)? */
 311 #define BUFFER_HALF_FILLED(nodeBuffer, gfbb) \
 312         ((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer / 2)
 313
 314 /*
 315  * Is specified buffer full? Our buffers can actually grow indefinitely,
 316  * beyond the "maximum" size, so this just means whether the buffer has grown
 317  * beyond the nominal maximum size.
 318  */
 319 #define BUFFER_OVERFLOWED(nodeBuffer, gfbb) \
 320         ((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer)
 321
 322 /*
 323  * Data structure with general information about build buffers.
 324  */
 325 typedef struct GISTBuildBuffers
 326 {
 327         /* Persistent memory context for the buffers and metadata. */
 328         MemoryContext context;
 329
 330         BufFile    *pfile;                      /* Temporary file to store buffers in */
 331         long            nFileBlocks;    /* Current size of the temporary file */
 332
 333         /*
 334          * resizable array of free blocks.
 335          */
 336         long       *freeBlocks;
 337         int                     nFreeBlocks;    /* # of currently free blocks in the array */
 338         int                     freeBlocksLen;  /* current allocated length of the array */
 339
 340         /* Hash for buffers by block number */
 341         HTAB       *nodeBuffersTab;
 342
 343         /* List of buffers scheduled for emptying */
 344         List       *bufferEmptyingQueue;
 345
 346         /*
 347          * Parameters to the buffering build algorithm. levelStep determines which
 348          * levels in the tree have buffers, and pagesPerBuffer determines how
 349          * large each buffer is.
 350          */
 351         int                     levelStep;
 352         int                     pagesPerBuffer;
 353
 354         /* Array of lists of buffers on each level, for final emptying */
 355         List      **buffersOnLevels;
 356         int                     buffersOnLevelsLen;
 357
 358         /*
 359          * Dynamically-sized array of buffers that currently have their last page
 360          * loaded in main memory.
 361          */
 362         GISTNodeBuffer **loadedBuffers;
 363         int                     loadedBuffersCount;             /* # of entries in loadedBuffers */
 364         int                     loadedBuffersLen;               /* allocated size of loadedBuffers */
 365
 366         /* Level of the current root node (= height of the index tree - 1) */
 367         int                     rootlevel;
 368 } GISTBuildBuffers;
 369
 370 /*
 371  * Storage type for GiST's reloptions
 372  */
 373 typedef struct GiSTOptions
 374 {
 375         int32           vl_len_;                /* varlena header (do not touch directly!) */
 376         int                     fillfactor;             /* page fill factor in percent (0..100) */
 377         int                     bufferingModeOffset;    /* use buffering build? */
 378 } GiSTOptions;
 379
 380 /* gist.c */
 381 extern void gistbuildempty(Relation index);
 382 extern bool gistinsert(Relation r, Datum *values, bool *isnull,
 383                    ItemPointer ht_ctid, Relation heapRel,
 384                    IndexUniqueCheck checkUnique,
 385                    struct IndexInfo *indexInfo);
 386 extern MemoryContext createTempGistContext(void);
 387 extern GISTSTATE *initGISTstate(Relation index);
 388 extern void freeGISTstate(GISTSTATE *giststate);
 389 extern void gistdoinsert(Relation r,
 390                          IndexTuple itup,
 391                          Size freespace,
 392                          GISTSTATE *GISTstate);
 393
 394 /* A List of these is returned from gistplacetopage() in *splitinfo */
 395 typedef struct
 396 {
 397         Buffer          buf;                    /* the split page "half" */
 398         IndexTuple      downlink;               /* downlink for this half. */
 399 } GISTPageSplitInfo;
 400
 401 extern bool gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
 402                                 Buffer buffer,
 403                                 IndexTuple *itup, int ntup,
 404                                 OffsetNumber oldoffnum, BlockNumber *newblkno,
 405                                 Buffer leftchildbuf,
 406                                 List **splitinfo,
 407                                 bool markleftchild);
 408
 409 extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,
 410                   int len, GISTSTATE *giststate);
 411
 412 extern XLogRecPtr gistXLogUpdate(Buffer buffer,
 413                            OffsetNumber *todelete, int ntodelete,
 414                            IndexTuple *itup, int ntup,
 415                            Buffer leftchild);
 416
 417 extern XLogRecPtr gistXLogSplit(bool page_is_leaf,
 418                           SplitedPageLayout *dist,
 419                           BlockNumber origrlink, GistNSN oldnsn,
 420                           Buffer leftchild, bool markfollowright);
 421
 422 /* gistget.c */
 423 extern bool gistgettuple(IndexScanDesc scan, ScanDirection dir);
 424 extern int64 gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
 425 extern bool gistcanreturn(Relation index, int attno);
 426
 427 /* gistvalidate.c */
 428 extern bool gistvalidate(Oid opclassoid);
 429
 430 /* gistutil.c */
 431
 432 #define GiSTPageSize   \
 433         ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GISTPageOpaqueData)) )
 434
 435 #define GIST_MIN_FILLFACTOR                     10
 436 #define GIST_DEFAULT_FILLFACTOR         90
 437
 438 extern bytea *gistoptions(Datum reloptions, bool validate);
 439 extern bool gistproperty(Oid index_oid, int attno,
 440                          IndexAMProperty prop, const char *propname,
 441                          bool *res, bool *isnull);
 442 extern bool gistfitpage(IndexTuple *itvec, int len);
 443 extern bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace);
 444 extern void gistcheckpage(Relation rel, Buffer buf);
 445 extern Buffer gistNewBuffer(Relation r);
 446 extern void gistfillbuffer(Page page, IndexTuple *itup, int len,
 447                            OffsetNumber off);
 448 extern IndexTuple *gistextractpage(Page page, int *len /* out */ );
 449 extern IndexTuple *gistjoinvector(
 450                            IndexTuple *itvec, int *len,
 451                            IndexTuple *additvec, int addlen);
 452 extern IndexTupleData *gistfillitupvec(IndexTuple *vec, int veclen, int *memlen);
 453
 454 extern IndexTuple gistunion(Relation r, IndexTuple *itvec,
 455                   int len, GISTSTATE *giststate);
 456 extern IndexTuple gistgetadjusted(Relation r,
 457                                 IndexTuple oldtup,
 458                                 IndexTuple addtup,
 459                                 GISTSTATE *giststate);
 460 extern IndexTuple gistFormTuple(GISTSTATE *giststate,
 461                           Relation r, Datum *attdata, bool *isnull, bool isleaf);
 462
 463 extern OffsetNumber gistchoose(Relation r, Page p,
 464                    IndexTuple it,
 465                    GISTSTATE *giststate);
 466
 467 extern void GISTInitBuffer(Buffer b, uint32 f);
 468 extern void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
 469                            Datum k, Relation r, Page pg, OffsetNumber o,
 470                            bool l, bool isNull);
 471
 472 extern float gistpenalty(GISTSTATE *giststate, int attno,
 473                         GISTENTRY *key1, bool isNull1,
 474                         GISTENTRY *key2, bool isNull2);
 475 extern void gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len,
 476                                    Datum *attr, bool *isnull);
 477 extern bool gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b);
 478 extern void gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,
 479                                   OffsetNumber o, GISTENTRY *attdata, bool *isnull);
 480 extern HeapTuple gistFetchTuple(GISTSTATE *giststate, Relation r,
 481                            IndexTuple tuple);
 482 extern void gistMakeUnionKey(GISTSTATE *giststate, int attno,
 483                                  GISTENTRY *entry1, bool isnull1,
 484                                  GISTENTRY *entry2, bool isnull2,
 485                                  Datum *dst, bool *dstisnull);
 486
 487 extern XLogRecPtr gistGetFakeLSN(Relation rel);
 488
 489 /* gistvacuum.c */
 490 extern IndexBulkDeleteResult *gistbulkdelete(IndexVacuumInfo *info,
 491                            IndexBulkDeleteResult *stats,
 492                            IndexBulkDeleteCallback callback,
 493                            void *callback_state);
 494 extern IndexBulkDeleteResult *gistvacuumcleanup(IndexVacuumInfo *info,
 495                                   IndexBulkDeleteResult *stats);
 496
 497 /* gistsplit.c */
 498 extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,
 499                            int len, GISTSTATE *giststate,
 500                            GistSplitVector *v,
 501                            int attno);
 502
 503 /* gistbuild.c */
 504 extern IndexBuildResult *gistbuild(Relation heap, Relation index,
 505                   struct IndexInfo *indexInfo);
 506 extern void gistValidateBufferingOption(char *value);
 507
 508 /* gistbuildbuffers.c */
 509 extern GISTBuildBuffers *gistInitBuildBuffers(int pagesPerBuffer, int levelStep,
 510                                          int maxLevel);
 511 extern GISTNodeBuffer *gistGetNodeBuffer(GISTBuildBuffers *gfbb,
 512                                   GISTSTATE *giststate,
 513                                   BlockNumber blkno, int level);
 514 extern void gistPushItupToNodeBuffer(GISTBuildBuffers *gfbb,
 515                                                  GISTNodeBuffer *nodeBuffer, IndexTuple item);
 516 extern bool gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb,
 517                                                   GISTNodeBuffer *nodeBuffer, IndexTuple *item);
 518 extern void gistFreeBuildBuffers(GISTBuildBuffers *gfbb);
 519 extern void gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb,
 520                                                                 GISTSTATE *giststate, Relation r,
 521                                                                 int level, Buffer buffer,
 522                                                                 List *splitinfo);
 523 extern void gistUnloadNodeBuffers(GISTBuildBuffers *gfbb);
 524
 525 #endif   /* GIST_PRIVATE_H */