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