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