Age         Owner                  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
 1355 heikki.linnakangas        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 */