LCOV - code coverage report
Current view: top level - src/include/access - gist.h (source / functions) Hit Total Coverage
Test: PostgreSQL 14devel Lines: 5 9 55.6 %
Date: 2020-11-27 12:05:55 Functions: 1 2 50.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * gist.h
       4             :  *    The public API for GiST indexes. This API is exposed to
       5             :  *    individuals implementing GiST indexes, so backward-incompatible
       6             :  *    changes should be made with care.
       7             :  *
       8             :  *
       9             :  * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
      10             :  * Portions Copyright (c) 1994, Regents of the University of California
      11             :  *
      12             :  * src/include/access/gist.h
      13             :  *
      14             :  *-------------------------------------------------------------------------
      15             :  */
      16             : #ifndef GIST_H
      17             : #define GIST_H
      18             : 
      19             : #include "access/itup.h"
      20             : #include "access/transam.h"
      21             : #include "access/xlog.h"
      22             : #include "access/xlogdefs.h"
      23             : #include "storage/block.h"
      24             : #include "storage/bufpage.h"
      25             : #include "utils/relcache.h"
      26             : 
      27             : /*
      28             :  * amproc indexes for GiST indexes.
      29             :  */
      30             : #define GIST_CONSISTENT_PROC            1
      31             : #define GIST_UNION_PROC                 2
      32             : #define GIST_COMPRESS_PROC              3
      33             : #define GIST_DECOMPRESS_PROC            4
      34             : #define GIST_PENALTY_PROC               5
      35             : #define GIST_PICKSPLIT_PROC             6
      36             : #define GIST_EQUAL_PROC                 7
      37             : #define GIST_DISTANCE_PROC              8
      38             : #define GIST_FETCH_PROC                 9
      39             : #define GIST_OPTIONS_PROC               10
      40             : #define GIST_SORTSUPPORT_PROC           11
      41             : #define GISTNProcs                  11
      42             : 
      43             : /*
      44             :  * Page opaque data in a GiST index page.
      45             :  */
      46             : #define F_LEAF              (1 << 0)  /* leaf page */
      47             : #define F_DELETED           (1 << 1)  /* the page has been deleted */
      48             : #define F_TUPLES_DELETED    (1 << 2)  /* some tuples on the page were
      49             :                                          * deleted */
      50             : #define F_FOLLOW_RIGHT      (1 << 3)  /* page to the right has no downlink */
      51             : #define F_HAS_GARBAGE       (1 << 4)  /* some tuples on the page are dead,
      52             :                                          * but not deleted yet */
      53             : 
      54             : typedef XLogRecPtr GistNSN;
      55             : 
      56             : /*
      57             :  * A bogus LSN / NSN value used during index build. Must be smaller than any
      58             :  * real or fake unlogged LSN, so that after an index build finishes, all the
      59             :  * splits are considered completed.
      60             :  */
      61             : #define GistBuildLSN    ((XLogRecPtr) 1)
      62             : 
      63             : /*
      64             :  * For on-disk compatibility with pre-9.3 servers, NSN is stored as two
      65             :  * 32-bit fields on disk, same as LSNs.
      66             :  */
      67             : typedef PageXLogRecPtr PageGistNSN;
      68             : 
      69             : typedef struct GISTPageOpaqueData
      70             : {
      71             :     PageGistNSN nsn;            /* this value must change on page split */
      72             :     BlockNumber rightlink;      /* next page if any */
      73             :     uint16      flags;          /* see bit definitions above */
      74             :     uint16      gist_page_id;   /* for identification of GiST indexes */
      75             : } GISTPageOpaqueData;
      76             : 
      77             : typedef GISTPageOpaqueData *GISTPageOpaque;
      78             : 
      79             : /*
      80             :  * Maximum possible sizes for GiST index tuple and index key.  Calculation is
      81             :  * based on assumption that GiST page should fit at least 4 tuples.  In theory,
      82             :  * GiST index can be functional when page can fit 3 tuples.  But that seems
      83             :  * rather inefficient, so we use a bit conservative estimate.
      84             :  *
      85             :  * The maximum size of index key is true for unicolumn index.  Therefore, this
      86             :  * estimation should be used to figure out which maximum size of GiST index key
      87             :  * makes sense at all.  For multicolumn indexes, user might be able to tune
      88             :  * key size using opclass parameters.
      89             :  */
      90             : #define GISTMaxIndexTupleSize   \
      91             :     MAXALIGN_DOWN((BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)) / \
      92             :                   4 - sizeof(ItemIdData))
      93             : 
      94             : #define GISTMaxIndexKeySize \
      95             :     (GISTMaxIndexTupleSize - MAXALIGN(sizeof(IndexTupleData)))
      96             : 
      97             : /*
      98             :  * The page ID is for the convenience of pg_filedump and similar utilities,
      99             :  * which otherwise would have a hard time telling pages of different index
     100             :  * types apart.  It should be the last 2 bytes on the page.  This is more or
     101             :  * less "free" due to alignment considerations.
     102             :  */
     103             : #define GIST_PAGE_ID        0xFF81
     104             : 
     105             : /*
     106             :  * This is the Split Vector to be returned by the PickSplit method.
     107             :  * PickSplit should fill the indexes of tuples to go to the left side into
     108             :  * spl_left[], and those to go to the right into spl_right[] (note the method
     109             :  * is responsible for palloc'ing both of these arrays!).  The tuple counts
     110             :  * go into spl_nleft/spl_nright, and spl_ldatum/spl_rdatum must be set to
     111             :  * the union keys for each side.
     112             :  *
     113             :  * If spl_ldatum_exists and spl_rdatum_exists are true, then we are performing
     114             :  * a "secondary split" using a non-first index column.  In this case some
     115             :  * decisions have already been made about a page split, and the set of tuples
     116             :  * being passed to PickSplit is just the tuples about which we are undecided.
     117             :  * spl_ldatum/spl_rdatum then contain the union keys for the tuples already
     118             :  * chosen to go left or right.  Ideally the PickSplit method should take those
     119             :  * keys into account while deciding what to do with the remaining tuples, ie
     120             :  * it should try to "build out" from those unions so as to minimally expand
     121             :  * them.  If it does so, it should union the given tuples' keys into the
     122             :  * existing spl_ldatum/spl_rdatum values rather than just setting those values
     123             :  * from scratch, and then set spl_ldatum_exists/spl_rdatum_exists to false to
     124             :  * show it has done this.
     125             :  *
     126             :  * If the PickSplit method fails to clear spl_ldatum_exists/spl_rdatum_exists,
     127             :  * the core GiST code will make its own decision about how to merge the
     128             :  * secondary-split results with the previously-chosen tuples, and will then
     129             :  * recompute the union keys from scratch.  This is a workable though often not
     130             :  * optimal approach.
     131             :  */
     132             : typedef struct GIST_SPLITVEC
     133             : {
     134             :     OffsetNumber *spl_left;     /* array of entries that go left */
     135             :     int         spl_nleft;      /* size of this array */
     136             :     Datum       spl_ldatum;     /* Union of keys in spl_left */
     137             :     bool        spl_ldatum_exists;  /* true, if spl_ldatum already exists. */
     138             : 
     139             :     OffsetNumber *spl_right;    /* array of entries that go right */
     140             :     int         spl_nright;     /* size of the array */
     141             :     Datum       spl_rdatum;     /* Union of keys in spl_right */
     142             :     bool        spl_rdatum_exists;  /* true, if spl_rdatum already exists. */
     143             : } GIST_SPLITVEC;
     144             : 
     145             : /*
     146             :  * An entry on a GiST node.  Contains the key, as well as its own
     147             :  * location (rel,page,offset) which can supply the matching pointer.
     148             :  * leafkey is a flag to tell us if the entry is in a leaf node.
     149             :  */
     150             : typedef struct GISTENTRY
     151             : {
     152             :     Datum       key;
     153             :     Relation    rel;
     154             :     Page        page;
     155             :     OffsetNumber offset;
     156             :     bool        leafkey;
     157             : } GISTENTRY;
     158             : 
     159             : #define GistPageGetOpaque(page) ( (GISTPageOpaque) PageGetSpecialPointer(page) )
     160             : 
     161             : #define GistPageIsLeaf(page)    ( GistPageGetOpaque(page)->flags & F_LEAF)
     162             : #define GIST_LEAF(entry) (GistPageIsLeaf((entry)->page))
     163             : 
     164             : #define GistPageIsDeleted(page) ( GistPageGetOpaque(page)->flags & F_DELETED)
     165             : 
     166             : #define GistTuplesDeleted(page) ( GistPageGetOpaque(page)->flags & F_TUPLES_DELETED)
     167             : #define GistMarkTuplesDeleted(page) ( GistPageGetOpaque(page)->flags |= F_TUPLES_DELETED)
     168             : #define GistClearTuplesDeleted(page)    ( GistPageGetOpaque(page)->flags &= ~F_TUPLES_DELETED)
     169             : 
     170             : #define GistPageHasGarbage(page) ( GistPageGetOpaque(page)->flags & F_HAS_GARBAGE)
     171             : #define GistMarkPageHasGarbage(page) ( GistPageGetOpaque(page)->flags |= F_HAS_GARBAGE)
     172             : #define GistClearPageHasGarbage(page)   ( GistPageGetOpaque(page)->flags &= ~F_HAS_GARBAGE)
     173             : 
     174             : #define GistFollowRight(page) ( GistPageGetOpaque(page)->flags & F_FOLLOW_RIGHT)
     175             : #define GistMarkFollowRight(page) ( GistPageGetOpaque(page)->flags |= F_FOLLOW_RIGHT)
     176             : #define GistClearFollowRight(page)  ( GistPageGetOpaque(page)->flags &= ~F_FOLLOW_RIGHT)
     177             : 
     178             : #define GistPageGetNSN(page) ( PageXLogRecPtrGet(GistPageGetOpaque(page)->nsn))
     179             : #define GistPageSetNSN(page, val) ( PageXLogRecPtrSet(GistPageGetOpaque(page)->nsn, val))
     180             : 
     181             : 
     182             : /*
     183             :  * On a deleted page, we store this struct. A deleted page doesn't contain any
     184             :  * tuples, so we don't use the normal page layout with line pointers. Instead,
     185             :  * this struct is stored right after the standard page header. pd_lower points
     186             :  * to the end of this struct. If we add fields to this struct in the future, we
     187             :  * can distinguish the old and new formats by pd_lower.
     188             :  */
     189             : typedef struct GISTDeletedPageContents
     190             : {
     191             :     /* last xid which could see the page in a scan */
     192             :     FullTransactionId deleteXid;
     193             : } GISTDeletedPageContents;
     194             : 
     195             : static inline void
     196         270 : GistPageSetDeleted(Page page, FullTransactionId deletexid)
     197             : {
     198             :     Assert(PageIsEmpty(page));
     199             : 
     200         270 :     GistPageGetOpaque(page)->flags |= F_DELETED;
     201         270 :     ((PageHeader) page)->pd_lower = MAXALIGN(SizeOfPageHeaderData) + sizeof(GISTDeletedPageContents);
     202             : 
     203         270 :     ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid = deletexid;
     204         270 : }
     205             : 
     206             : static inline FullTransactionId
     207           0 : GistPageGetDeleteXid(Page page)
     208             : {
     209             :     Assert(GistPageIsDeleted(page));
     210             : 
     211             :     /* Is the deleteXid field present? */
     212           0 :     if (((PageHeader) page)->pd_lower >= MAXALIGN(SizeOfPageHeaderData) +
     213             :         offsetof(GISTDeletedPageContents, deleteXid) + sizeof(FullTransactionId))
     214             :     {
     215           0 :         return ((GISTDeletedPageContents *) PageGetContents(page))->deleteXid;
     216             :     }
     217             :     else
     218           0 :         return FullTransactionIdFromEpochAndXid(0, FirstNormalTransactionId);
     219             : }
     220             : 
     221             : /*
     222             :  * Vector of GISTENTRY structs; user-defined methods union and picksplit
     223             :  * take it as one of their arguments
     224             :  */
     225             : typedef struct
     226             : {
     227             :     int32       n;              /* number of elements */
     228             :     GISTENTRY   vector[FLEXIBLE_ARRAY_MEMBER];
     229             : } GistEntryVector;
     230             : 
     231             : #define GEVHDRSZ    (offsetof(GistEntryVector, vector))
     232             : 
     233             : /*
     234             :  * macro to initialize a GISTENTRY
     235             :  */
     236             : #define gistentryinit(e, k, r, pg, o, l) \
     237             :     do { (e).key = (k); (e).rel = (r); (e).page = (pg); \
     238             :          (e).offset = (o); (e).leafkey = (l); } while (0)
     239             : 
     240             : #endif                          /* GIST_H */

Generated by: LCOV version 1.13