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