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