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-2010, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * src/include/access/gist_private.h
  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
  91 #define XLOG_GIST_PAGE_UPDATE           0x00
  92 #define XLOG_GIST_NEW_ROOT                      0x20
  93 #define XLOG_GIST_PAGE_SPLIT            0x30
  94 #define XLOG_GIST_INSERT_COMPLETE       0x40
  95 #define XLOG_GIST_CREATE_INDEX          0x50
  96 #define XLOG_GIST_PAGE_DELETE           0x60
  97
  98 typedef struct gistxlogPageUpdate
  99 {
 100         RelFileNode node;
 101         BlockNumber blkno;
 102
 103         /*
 104          * It used to identify completeness of insert. Sets to leaf itup
 105          */
 106         ItemPointerData key;
 107
 108         /* number of deleted offsets */
 109         uint16          ntodelete;
 110
 111         /*
 112          * follow: 1. todelete OffsetNumbers 2. tuples to insert
 113          */
 114 } gistxlogPageUpdate;
 115
 116 typedef struct gistxlogPageSplit
 117 {
 118         RelFileNode node;
 119         BlockNumber origblkno;          /* splitted page */
 120         bool            origleaf;               /* was splitted page a leaf page? */
 121         uint16          npage;
 122
 123         /* see comments on gistxlogPageUpdate */
 124         ItemPointerData key;
 125
 126         /*
 127          * follow: 1. gistxlogPage and array of IndexTupleData per page
 128          */
 129 } gistxlogPageSplit;
 130
 131 typedef struct gistxlogPage
 132 {
 133         BlockNumber blkno;
 134         int                     num;                    /* number of index tuples following */
 135 } gistxlogPage;
 136
 137 typedef struct gistxlogInsertComplete
 138 {
 139         RelFileNode node;
 140         /* follows ItemPointerData key to clean */
 141 } gistxlogInsertComplete;
 142
 143 typedef struct gistxlogPageDelete
 144 {
 145         RelFileNode node;
 146         BlockNumber blkno;
 147 } gistxlogPageDelete;
 148
 149 /* SplitedPageLayout - gistSplit function result */
 150 typedef struct SplitedPageLayout
 151 {
 152         gistxlogPage block;
 153         IndexTupleData *list;
 154         int                     lenlist;
 155         IndexTuple      itup;                   /* union key for page */
 156         Page            page;                   /* to operate */
 157         Buffer          buffer;                 /* to write after all proceed */
 158
 159         struct SplitedPageLayout *next;
 160 } SplitedPageLayout;
 161
 162 /*
 163  * GISTInsertStack used for locking buffers and transfer arguments during
 164  * insertion
 165  */
 166
 167 typedef struct GISTInsertStack
 168 {
 169         /* current page */
 170         BlockNumber blkno;
 171         Buffer          buffer;
 172         Page            page;
 173
 174         /*
 175          * log sequence number from page->lsn to recognize page update  and
 176          * compare it with page's nsn to recognize page split
 177          */
 178         GistNSN         lsn;
 179
 180         /* child's offset */
 181         OffsetNumber childoffnum;
 182
 183         /* pointer to parent and child */
 184         struct GISTInsertStack *parent;
 185         struct GISTInsertStack *child;
 186
 187         /* for gistFindPath */
 188         struct GISTInsertStack *next;
 189 } GISTInsertStack;
 190
 191 typedef struct GistSplitVector
 192 {
 193         GIST_SPLITVEC splitVector;      /* to/from PickSplit method */
 194
 195         Datum           spl_lattr[INDEX_MAX_KEYS];              /* Union of subkeys in
 196                                                                                                  * spl_left */
 197         bool            spl_lisnull[INDEX_MAX_KEYS];
 198         bool            spl_leftvalid;
 199
 200         Datum           spl_rattr[INDEX_MAX_KEYS];              /* Union of subkeys in
 201                                                                                                  * spl_right */
 202         bool            spl_risnull[INDEX_MAX_KEYS];
 203         bool            spl_rightvalid;
 204
 205         bool       *spl_equiv;          /* equivalent tuples which can be freely
 206                                                                  * distributed between left and right pages */
 207 } GistSplitVector;
 208
 209 typedef struct
 210 {
 211         Relation        r;
 212         IndexTuple *itup;                       /* in/out, points to compressed entry */
 213         int                     ituplen;                /* length of itup */
 214         Size            freespace;              /* free space to be left */
 215         GISTInsertStack *stack;
 216         bool            needInsertComplete;
 217
 218         /* pointer to heap tuple */
 219         ItemPointerData key;
 220 } GISTInsertState;
 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 gistgetbitmap(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 void gistfillbuffer(Page page, IndexTuple *itup, int len,
 285                            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 extern XLogRecPtr GetXLogRecPtrForTemp(void);
 329
 330 /* gistvacuum.c */
 331 extern Datum gistbulkdelete(PG_FUNCTION_ARGS);
 332 extern Datum gistvacuumcleanup(PG_FUNCTION_ARGS);
 333
 334 /* gistsplit.c */
 335 extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,
 336                            int len, GISTSTATE *giststate,
 337                            GistSplitVector *v, GistEntryVector *entryvec,
 338                            int attno);
 339
 340 #endif   /* GIST_PRIVATE_H */