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