TLA  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-2023, 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 UBC           0 : GistPageSetDeleted(Page page, FullTransactionId deletexid)
     205                 : {
     206               0 :     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               0 :     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 */