granicus.if.org Git - postgresql/blob - src/include/access/gist_private.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * gist_private.h
   4  *        private declarations for GiST -- declarations related to the
   5  *        internal implementation of GiST, not the public API
   6  *
   7  * Portions Copyright (c) 1996-2006, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * $PostgreSQL: pgsql/src/include/access/gist_private.h,v 1.23 2006/08/07 16:57:57 tgl Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #ifndef GIST_PRIVATE_H
  15 #define GIST_PRIVATE_H
  16
  17 #include "access/gist.h"
  18 #include "access/itup.h"
  19 #include "access/xlog.h"
  20 #include "access/xlogdefs.h"
  21 #include "fmgr.h"
  22
  23 #define GIST_UNLOCK BUFFER_LOCK_UNLOCK
  24 #define GIST_SHARE      BUFFER_LOCK_SHARE
  25 #define GIST_EXCLUSIVE  BUFFER_LOCK_EXCLUSIVE
  26
  27
  28 /*
  29  * XXX old comment!!!
  30  * When we descend a tree, we keep a stack of parent pointers. This
  31  * allows us to follow a chain of internal node points until we reach
  32  * a leaf node, and then back up the stack to re-examine the internal
  33  * nodes.
  34  *
  35  * 'parent' is the previous stack entry -- i.e. the node we arrived
  36  * from. 'block' is the node's block number. 'offset' is the offset in
  37  * the node's page that we stopped at (i.e. we followed the child
  38  * pointer located at the specified offset).
  39  */
  40 typedef struct GISTSearchStack
  41 {
  42         struct GISTSearchStack *next;
  43         BlockNumber block;
  44         /* to identify page changed */
  45         GistNSN         lsn;
  46         /* to recognize split occured */
  47         GistNSN         parentlsn;
  48 } GISTSearchStack;
  49
  50 typedef struct GISTSTATE
  51 {
  52         FmgrInfo        consistentFn[INDEX_MAX_KEYS];
  53         FmgrInfo        unionFn[INDEX_MAX_KEYS];
  54         FmgrInfo        compressFn[INDEX_MAX_KEYS];
  55         FmgrInfo        decompressFn[INDEX_MAX_KEYS];
  56         FmgrInfo        penaltyFn[INDEX_MAX_KEYS];
  57         FmgrInfo        picksplitFn[INDEX_MAX_KEYS];
  58         FmgrInfo        equalFn[INDEX_MAX_KEYS];
  59
  60         TupleDesc       tupdesc;
  61 } GISTSTATE;
  62
  63 /*
  64  *      When we're doing a scan, we need to keep track of the parent stack
  65  *      for the marked and current items.
  66  */
  67 typedef struct GISTScanOpaqueData
  68 {
  69         GISTSearchStack *stack;
  70         GISTSearchStack *markstk;
  71         uint16          flags;
  72         GISTSTATE  *giststate;
  73         MemoryContext tempCxt;
  74         Buffer          curbuf;
  75         Buffer          markbuf;
  76 } GISTScanOpaqueData;
  77
  78 typedef GISTScanOpaqueData *GISTScanOpaque;
  79
  80 /* XLog stuff */
  81 extern const XLogRecPtr XLogRecPtrForTemp;
  82
  83 #define XLOG_GIST_PAGE_UPDATE           0x00
  84 #define XLOG_GIST_NEW_ROOT                      0x20
  85 #define XLOG_GIST_PAGE_SPLIT            0x30
  86 #define XLOG_GIST_INSERT_COMPLETE       0x40
  87 #define XLOG_GIST_CREATE_INDEX          0x50
  88 #define XLOG_GIST_PAGE_DELETE           0x60
  89
  90 typedef struct gistxlogPageUpdate
  91 {
  92         RelFileNode node;
  93         BlockNumber blkno;
  94
  95         /*
  96          * It used to identify completeness of insert. Sets to leaf itup
  97          */
  98         ItemPointerData key;
  99
 100         /* number of deleted offsets */
 101         uint16          ntodelete;
 102
 103         /*
 104          * follow: 1. todelete OffsetNumbers 2. tuples to insert
 105          */
 106 } gistxlogPageUpdate;
 107
 108 typedef struct gistxlogPageSplit
 109 {
 110         RelFileNode node;
 111         BlockNumber origblkno;          /* splitted page */
 112         bool            origleaf;               /* was splitted page a leaf page? */
 113         uint16          npage;
 114
 115         /* see comments on gistxlogPageUpdate */
 116         ItemPointerData key;
 117
 118         /*
 119          * follow: 1. gistxlogPage and array of IndexTupleData per page
 120          */
 121 } gistxlogPageSplit;
 122
 123 typedef struct gistxlogPage
 124 {
 125         BlockNumber blkno;
 126         int                     num;                    /* number of index tuples following */
 127 } gistxlogPage;
 128
 129 typedef struct gistxlogInsertComplete
 130 {
 131         RelFileNode node;
 132         /* follows ItemPointerData key to clean */
 133 } gistxlogInsertComplete;
 134
 135 typedef struct gistxlogPageDelete
 136 {
 137         RelFileNode node;
 138         BlockNumber blkno;
 139 } gistxlogPageDelete;
 140
 141 /* SplitedPageLayout - gistSplit function result */
 142 typedef struct SplitedPageLayout
 143 {
 144         gistxlogPage block;
 145         IndexTupleData *list;
 146         int                     lenlist;
 147         IndexTuple      itup;  /* union key for page */
 148         Page            page;                   /* to operate */
 149         Buffer          buffer;                 /* to write after all proceed */
 150
 151         struct SplitedPageLayout *next;
 152 } SplitedPageLayout;
 153
 154 /*
 155  * GISTInsertStack used for locking buffers and transfer arguments during
 156  * insertion
 157  */
 158
 159 typedef struct GISTInsertStack
 160 {
 161         /* current page */
 162         BlockNumber blkno;
 163         Buffer          buffer;
 164         Page            page;
 165
 166         /*
 167          * log sequence number from page->lsn to recognize page update  and
 168          * compare it with page's nsn to recognize page split
 169          */
 170         GistNSN         lsn;
 171
 172         /* child's offset */
 173         OffsetNumber childoffnum;
 174
 175         /* pointer to parent and child */
 176         struct GISTInsertStack *parent;
 177         struct GISTInsertStack *child;
 178
 179         /* for gistFindPath */
 180         struct GISTInsertStack *next;
 181 } GISTInsertStack;
 182
 183 typedef struct GistSplitVector {
 184         GIST_SPLITVEC   splitVector;  /* to/from PickSplit method */
 185
 186         Datum       spl_lattr[INDEX_MAX_KEYS];      /* Union of subkeys in spl_left */
 187         bool        spl_lisnull[INDEX_MAX_KEYS];
 188         bool        spl_leftvalid;
 189
 190         Datum       spl_rattr[INDEX_MAX_KEYS];      /* Union of subkeys in spl_right */
 191         bool        spl_risnull[INDEX_MAX_KEYS];
 192         bool        spl_rightvalid;
 193
 194         bool        *spl_equiv; /* equivalent tuples which can be freely
 195                                                          * distributed between left and right pages */
 196 } GistSplitVector;
 197
 198 #define XLogRecPtrIsInvalid( r )        ( (r).xlogid == 0 && (r).xrecoff == 0 )
 199
 200 typedef struct
 201 {
 202         Relation        r;
 203         IndexTuple *itup;                       /* in/out, points to compressed entry */
 204         int                     ituplen;                /* length of itup */
 205         Size            freespace;              /* free space to be left */
 206         GISTInsertStack *stack;
 207         bool            needInsertComplete;
 208
 209         /* pointer to heap tuple */
 210         ItemPointerData key;
 211 } GISTInsertState;
 212
 213 /*
 214  * When we're doing a scan and updating a tree at the same time, the
 215  * updates may affect the scan.  We use the flags entry of the scan's
 216  * opaque space to record our actual position in response to updates
 217  * that we can't handle simply by adjusting pointers.
 218  */
 219 #define GS_CURBEFORE    ((uint16) (1 << 0))
 220 #define GS_MRKBEFORE    ((uint16) (1 << 1))
 221
 222 /* root page of a gist index */
 223 #define GIST_ROOT_BLKNO                         0
 224
 225 /*
 226  * mark tuples on inner pages during recovery
 227  */
 228 #define TUPLE_IS_VALID          0xffff
 229 #define TUPLE_IS_INVALID        0xfffe
 230
 231 #define  GistTupleIsInvalid(itup)       ( ItemPointerGetOffsetNumber( &((itup)->t_tid) ) == TUPLE_IS_INVALID )
 232 #define  GistTupleSetValid(itup)        ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_VALID )
 233 #define  GistTupleSetInvalid(itup)      ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_INVALID )
 234
 235 /* gist.c */
 236 extern Datum gistbuild(PG_FUNCTION_ARGS);
 237 extern Datum gistinsert(PG_FUNCTION_ARGS);
 238 extern MemoryContext createTempGistContext(void);
 239 extern void initGISTstate(GISTSTATE *giststate, Relation index);
 240 extern void freeGISTstate(GISTSTATE *giststate);
 241 extern void gistmakedeal(GISTInsertState *state, GISTSTATE *giststate);
 242 extern void gistnewroot(Relation r, Buffer buffer, IndexTuple *itup, int len, ItemPointer key);
 243
 244 extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,
 245                   int len, GISTSTATE *giststate);
 246
 247 extern GISTInsertStack *gistFindPath(Relation r, BlockNumber child);
 248
 249 /* gistxlog.c */
 250 extern void gist_redo(XLogRecPtr lsn, XLogRecord *record);
 251 extern void gist_desc(StringInfo buf, uint8 xl_info, char *rec);
 252 extern void gist_xlog_startup(void);
 253 extern void gist_xlog_cleanup(void);
 254 extern bool gist_safe_restartpoint(void);
 255 extern IndexTuple gist_form_invalid_tuple(BlockNumber blkno);
 256
 257 extern XLogRecData *formUpdateRdata(RelFileNode node, Buffer buffer,
 258                                 OffsetNumber *todelete, int ntodelete,
 259                                 IndexTuple *itup, int ituplen, ItemPointer key);
 260
 261 extern XLogRecData *formSplitRdata(RelFileNode node,
 262                            BlockNumber blkno, bool page_is_leaf,
 263                            ItemPointer key, SplitedPageLayout *dist);
 264
 265 extern XLogRecPtr gistxlogInsertCompletion(RelFileNode node, ItemPointerData *keys, int len);
 266
 267 /* gistget.c */
 268 extern Datum gistgettuple(PG_FUNCTION_ARGS);
 269 extern Datum gistgetmulti(PG_FUNCTION_ARGS);
 270
 271 /* gistutil.c */
 272
 273 #define GiSTPageSize   \
 274     ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GISTPageOpaqueData)) )
 275
 276 #define GIST_MIN_FILLFACTOR                     10
 277 #define GIST_DEFAULT_FILLFACTOR         90
 278
 279 extern Datum gistoptions(PG_FUNCTION_ARGS);
 280 extern bool gistfitpage(IndexTuple *itvec, int len);
 281 extern bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace);
 282 extern void gistcheckpage(Relation rel, Buffer buf);
 283 extern Buffer gistNewBuffer(Relation r);
 284 extern OffsetNumber gistfillbuffer(Relation r, Page page, IndexTuple *itup,
 285                            int len, OffsetNumber off);
 286 extern IndexTuple *gistextractpage(Page page, int *len /* out */ );
 287 extern IndexTuple *gistjoinvector(
 288                            IndexTuple *itvec, int *len,
 289                            IndexTuple *additvec, int addlen);
 290 extern IndexTupleData* gistfillitupvec(IndexTuple *vec, int veclen, int *memlen);
 291
 292 extern IndexTuple gistunion(Relation r, IndexTuple *itvec,
 293                   int len, GISTSTATE *giststate);
 294 extern IndexTuple gistgetadjusted(Relation r,
 295                                 IndexTuple oldtup,
 296                                 IndexTuple addtup,
 297                                 GISTSTATE *giststate);
 298 extern IndexTuple gistFormTuple(GISTSTATE *giststate,
 299                           Relation r, Datum *attdata, bool *isnull, bool newValues);
 300
 301 extern OffsetNumber gistchoose(Relation r, Page p,
 302                    IndexTuple it,
 303                    GISTSTATE *giststate);
 304 extern void gistcentryinit(GISTSTATE *giststate, int nkey,
 305                            GISTENTRY *e, Datum k,
 306                            Relation r, Page pg,
 307                            OffsetNumber o, bool l, bool isNull);
 308
 309 extern void GISTInitBuffer(Buffer b, uint32 f);
 310 extern void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
 311                            Datum k, Relation r, Page pg, OffsetNumber o,
 312                            bool l, bool isNull);
 313
 314 extern float gistpenalty(GISTSTATE *giststate, int attno,
 315                                 GISTENTRY *key1, bool isNull1,
 316                                                 GISTENTRY *key2, bool isNull2);
 317 extern bool gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len, int startkey,
 318                     Datum *attr, bool *isnull );
 319 extern bool gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b);
 320 extern void gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,
 321                                 OffsetNumber o, GISTENTRY *attdata, bool *isnull);
 322
 323 extern void gistMakeUnionKey( GISTSTATE *giststate, int attno,
 324                     GISTENTRY   *entry1, bool isnull1,
 325                                         GISTENTRY   *entry2, bool isnull2,
 326                                         Datum   *dst, bool *dstisnull );
 327
 328 /* gistvacuum.c */
 329 extern Datum gistbulkdelete(PG_FUNCTION_ARGS);
 330 extern Datum gistvacuumcleanup(PG_FUNCTION_ARGS);
 331
 332 /* gistsplit.c */
 333 extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,
 334                                                         int len, GISTSTATE *giststate,
 335                                                         GistSplitVector *v, GistEntryVector *entryvec,
 336                                                         int attno);
 337
 338 #endif   /* GIST_PRIVATE_H */