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

   1 /*--------------------------------------------------------------------------
   2  * gin.h
   3  *        header file for postgres inverted index access method implementation.
   4  *
   5  *      Copyright (c) 2006, PostgreSQL Global Development Group
   6  *      $PostgreSQL: pgsql/src/include/access/gin.h,v 1.10 2007/01/31 15:09:45 teodor Exp $
   7  *--------------------------------------------------------------------------
   8  */
   9
  10
  11 #ifndef GIN_H
  12 #define GIN_H
  13
  14 #include "access/relscan.h"
  15 #include "access/skey.h"
  16 #include "access/xlog.h"
  17 #include "access/xlogdefs.h"
  18 #include "storage/bufpage.h"
  19 #include "storage/off.h"
  20 #include "utils/rel.h"
  21 #include "access/itup.h"
  22 #include "fmgr.h"
  23
  24
  25 /*
  26  * amproc indexes for inverted indexes.
  27  */
  28 #define GIN_COMPARE_PROC                           1
  29 #define GIN_EXTRACTVALUE_PROC              2
  30 #define GIN_EXTRACTQUERY_PROC              3
  31 #define GIN_CONSISTENT_PROC                        4
  32 #define GINNProcs                                          4
  33
  34 typedef XLogRecPtr GinNSN;
  35
  36 /*
  37  * Page opaque data in a inverted index page.
  38  */
  39 typedef struct GinPageOpaqueData
  40 {
  41         uint16          flags;
  42         OffsetNumber maxoff;            /* number entries on GIN_DATA page: number of
  43                                                                  * heap ItemPointer on GIN_DATA|GIN_LEAF page
  44                                                                  * and number of records on GIN_DATA &
  45                                                                  * ~GIN_LEAF page */
  46         BlockNumber rightlink;
  47 } GinPageOpaqueData;
  48
  49 typedef GinPageOpaqueData *GinPageOpaque;
  50
  51 #define GIN_ROOT_BLKNO  (0)
  52
  53 typedef struct
  54 {
  55         BlockIdData child_blkno;        /* use it instead of BlockNumber to save space
  56                                                                  * on page */
  57         ItemPointerData key;
  58 } PostingItem;
  59
  60 #define PostingItemGetBlockNumber(pointer) \
  61         BlockIdGetBlockNumber(&(pointer)->child_blkno)
  62
  63 #define PostingItemSetBlockNumber(pointer, blockNumber) \
  64         BlockIdSet(&((pointer)->child_blkno), (blockNumber))
  65
  66 /*
  67  * Page opaque data in a inverted index page.
  68  */
  69 #define GIN_DATA                  (1 << 0)
  70 #define GIN_LEAF                  (1 << 1)
  71 #define GIN_DELETED               (1 << 2)
  72
  73 /*
  74  * Works on page
  75  */
  76 #define GinPageGetOpaque(page) ( (GinPageOpaque) PageGetSpecialPointer(page) )
  77
  78 #define GinPageIsLeaf(page)    ( GinPageGetOpaque(page)->flags & GIN_LEAF )
  79 #define GinPageSetLeaf(page)   ( GinPageGetOpaque(page)->flags |= GIN_LEAF )
  80 #define GinPageSetNonLeaf(page)    ( GinPageGetOpaque(page)->flags &= ~GIN_LEAF )
  81 #define GinPageIsData(page)    ( GinPageGetOpaque(page)->flags & GIN_DATA )
  82 #define GinPageSetData(page)   ( GinPageGetOpaque(page)->flags |= GIN_DATA )
  83
  84 #define GinPageIsDeleted(page) ( GinPageGetOpaque(page)->flags & GIN_DELETED)
  85 #define GinPageSetDeleted(page)    ( GinPageGetOpaque(page)->flags |= GIN_DELETED)
  86 #define GinPageSetNonDeleted(page) ( GinPageGetOpaque(page)->flags &= ~GIN_DELETED)
  87
  88 #define GinPageRightMost(page) ( GinPageGetOpaque(page)->rightlink == InvalidBlockNumber)
  89
  90 /*
  91  * Define our ItemPointerGet(BlockNumber|GetOffsetNumber)
  92  * to prevent asserts
  93  */
  94
  95 #define GinItemPointerGetBlockNumber(pointer) \
  96         BlockIdGetBlockNumber(&(pointer)->ip_blkid)
  97
  98 #define GinItemPointerGetOffsetNumber(pointer) \
  99         ((pointer)->ip_posid)
 100
 101 /*
 102  * Support work on IndexTuuple on leaf pages
 103  */
 104 #define GinGetNPosting(itup)    GinItemPointerGetOffsetNumber(&(itup)->t_tid)
 105 #define GinSetNPosting(itup,n)  ItemPointerSetOffsetNumber(&(itup)->t_tid,(n))
 106 #define GIN_TREE_POSTING                ((OffsetNumber)0xffff)
 107 #define GinIsPostingTree(itup)  ( GinGetNPosting(itup)==GIN_TREE_POSTING )
 108 #define GinSetPostingTree(itup, blkno)  ( GinSetNPosting((itup),GIN_TREE_POSTING ), ItemPointerSetBlockNumber(&(itup)->t_tid, blkno) )
 109 #define GinGetPostingTree(itup) GinItemPointerGetBlockNumber(&(itup)->t_tid)
 110
 111 #define GinGetOrigSizePosting(itup) GinItemPointerGetBlockNumber(&(itup)->t_tid)
 112 #define GinSetOrigSizePosting(itup,n)   ItemPointerSetBlockNumber(&(itup)->t_tid,(n))
 113 #define GinGetPosting(itup)                     ( (ItemPointer)(( ((char*)(itup)) + SHORTALIGN(GinGetOrigSizePosting(itup)) )) )
 114
 115 #define GinMaxItemSize \
 116         ((BLCKSZ - SizeOfPageHeaderData - \
 117                 MAXALIGN(sizeof(GinPageOpaqueData))) / 3 - sizeof(ItemIdData))
 118
 119
 120 /*
 121  * Data (posting tree) pages
 122  */
 123 #define GinDataPageGetData(page)        \
 124         (PageGetContents(page)+MAXALIGN(sizeof(ItemPointerData)))
 125 #define GinDataPageGetRightBound(page)  ((ItemPointer)PageGetContents(page))
 126 #define GinSizeOfItem(page) ( (GinPageIsLeaf(page)) ? sizeof(ItemPointerData) : sizeof(PostingItem) )
 127 #define GinDataPageGetItem(page,i) ( GinDataPageGetData(page) + ((i)-1) * GinSizeOfItem(page) )
 128
 129 #define GinDataPageGetFreeSpace(page)   \
 130         ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GinPageOpaqueData)) - \
 131                 GinPageGetOpaque(page)->maxoff * GinSizeOfItem(page) - \
 132                 MAXALIGN(sizeof(ItemPointerData)))
 133
 134
 135
 136 #define GIN_UNLOCK      BUFFER_LOCK_UNLOCK
 137 #define GIN_SHARE       BUFFER_LOCK_SHARE
 138 #define GIN_EXCLUSIVE  BUFFER_LOCK_EXCLUSIVE
 139
 140 typedef struct GinState
 141 {
 142         FmgrInfo        compareFn;
 143         FmgrInfo        extractValueFn;
 144         FmgrInfo        extractQueryFn;
 145         FmgrInfo        consistentFn;
 146
 147         TupleDesc       tupdesc;
 148 } GinState;
 149
 150 /* XLog stuff */
 151
 152 #define XLOG_GIN_CREATE_INDEX  0x00
 153
 154 #define XLOG_GIN_CREATE_PTREE  0x10
 155
 156 typedef struct ginxlogCreatePostingTree
 157 {
 158         RelFileNode node;
 159         BlockNumber blkno;
 160         uint32          nitem;
 161         /* follows list of heap's ItemPointer */
 162 } ginxlogCreatePostingTree;
 163
 164 #define XLOG_GIN_INSERT  0x20
 165
 166 typedef struct ginxlogInsert
 167 {
 168         RelFileNode node;
 169         BlockNumber blkno;
 170         BlockNumber updateBlkno;
 171         OffsetNumber offset;
 172         bool            isDelete;
 173         bool            isData;
 174         bool            isLeaf;
 175         OffsetNumber nitem;
 176
 177         /*
 178          * follows: tuples or ItemPointerData or PostingItem or list of
 179          * ItemPointerData
 180          */
 181 } ginxlogInsert;
 182
 183 #define XLOG_GIN_SPLIT  0x30
 184
 185 typedef struct ginxlogSplit
 186 {
 187         RelFileNode node;
 188         BlockNumber lblkno;
 189         BlockNumber rootBlkno;
 190         BlockNumber rblkno;
 191         BlockNumber rrlink;
 192         OffsetNumber separator;
 193         OffsetNumber nitem;
 194
 195         bool            isData;
 196         bool            isLeaf;
 197         bool            isRootSplit;
 198
 199         BlockNumber leftChildBlkno;
 200         BlockNumber updateBlkno;
 201
 202         ItemPointerData rightbound; /* used only in posting tree */
 203         /* follows: list of tuple or ItemPointerData or PostingItem */
 204 } ginxlogSplit;
 205
 206 #define XLOG_GIN_VACUUM_PAGE    0x40
 207
 208 typedef struct ginxlogVacuumPage
 209 {
 210         RelFileNode node;
 211         BlockNumber blkno;
 212         OffsetNumber nitem;
 213         /* follows content of page */
 214 } ginxlogVacuumPage;
 215
 216 #define XLOG_GIN_DELETE_PAGE    0x50
 217
 218 typedef struct ginxlogDeletePage
 219 {
 220         RelFileNode node;
 221         BlockNumber blkno;
 222         BlockNumber parentBlkno;
 223         OffsetNumber parentOffset;
 224         BlockNumber leftBlkno;
 225         BlockNumber rightLink;
 226 } ginxlogDeletePage;
 227
 228 /* ginutil.c */
 229 extern Datum ginoptions(PG_FUNCTION_ARGS);
 230 extern void initGinState(GinState *state, Relation index);
 231 extern Buffer GinNewBuffer(Relation index);
 232 extern void GinInitBuffer(Buffer b, uint32 f);
 233 extern void GinInitPage(Page page, uint32 f, Size pageSize);
 234 extern int      compareEntries(GinState *ginstate, Datum a, Datum b);
 235 extern Datum *extractEntriesS(GinState *ginstate, Datum value,
 236                                                           int32 *nentries, bool *needUnique);
 237 extern Datum *extractEntriesSU(GinState *ginstate, Datum value, int32 *nentries);
 238 extern Page GinPageGetCopyPage(Page page);
 239
 240 /* gininsert.c */
 241 extern Datum ginbuild(PG_FUNCTION_ARGS);
 242 extern Datum gininsert(PG_FUNCTION_ARGS);
 243
 244 /* ginxlog.c */
 245 extern void gin_redo(XLogRecPtr lsn, XLogRecord *record);
 246 extern void gin_desc(StringInfo buf, uint8 xl_info, char *rec);
 247 extern void gin_xlog_startup(void);
 248 extern void gin_xlog_cleanup(void);
 249 extern bool gin_safe_restartpoint(void);
 250
 251 /* ginbtree.c */
 252
 253 typedef struct GinBtreeStack
 254 {
 255         BlockNumber blkno;
 256         Buffer          buffer;
 257         OffsetNumber off;
 258         /* predictNumber contains prediction number of pages on current level */
 259         uint32          predictNumber;
 260         struct GinBtreeStack *parent;
 261 } GinBtreeStack;
 262
 263 typedef struct GinBtreeData *GinBtree;
 264
 265 typedef struct GinBtreeData
 266 {
 267         /* search methods */
 268         BlockNumber (*findChildPage) (GinBtree, GinBtreeStack *);
 269         bool            (*isMoveRight) (GinBtree, Page);
 270         bool            (*findItem) (GinBtree, GinBtreeStack *);
 271
 272         /* insert methods */
 273         OffsetNumber (*findChildPtr) (GinBtree, Page, BlockNumber, OffsetNumber);
 274         BlockNumber (*getLeftMostPage) (GinBtree, Page);
 275         bool            (*isEnoughSpace) (GinBtree, Buffer, OffsetNumber);
 276         void            (*placeToPage) (GinBtree, Buffer, OffsetNumber, XLogRecData **);
 277         Page            (*splitPage) (GinBtree, Buffer, Buffer, OffsetNumber, XLogRecData **);
 278         void            (*fillRoot) (GinBtree, Buffer, Buffer, Buffer);
 279
 280         bool            searchMode;
 281
 282         Relation        index;
 283         GinState   *ginstate;
 284         bool            fullScan;
 285         bool            isBuild;
 286
 287         BlockNumber rightblkno;
 288
 289         /* Entry options */
 290         Datum           entryValue;
 291         IndexTuple      entry;
 292         bool            isDelete;
 293
 294         /* Data (posting tree) option */
 295         ItemPointerData *items;
 296         uint32          nitem;
 297         uint32          curitem;
 298
 299         PostingItem pitem;
 300 } GinBtreeData;
 301
 302 extern GinBtreeStack *ginPrepareFindLeafPage(GinBtree btree, BlockNumber blkno);
 303 extern GinBtreeStack *ginFindLeafPage(GinBtree btree, GinBtreeStack *stack);
 304 extern void freeGinBtreeStack(GinBtreeStack *stack);
 305 extern void ginInsertValue(GinBtree btree, GinBtreeStack *stack);
 306 extern void findParents(GinBtree btree, GinBtreeStack *stack, BlockNumber rootBlkno);
 307
 308 /* ginentrypage.c */
 309 extern IndexTuple GinFormTuple(GinState *ginstate, Datum key, ItemPointerData *ipd, uint32 nipd);
 310 extern Datum ginGetHighKey(GinState *ginstate, Page page);
 311 extern void prepareEntryScan(GinBtree btree, Relation index, Datum value, GinState *ginstate);
 312 extern void entryFillRoot(GinBtree btree, Buffer root, Buffer lbuf, Buffer rbuf);
 313 extern IndexTuple ginPageGetLinkItup(Buffer buf);
 314
 315 /* gindatapage.c */
 316 extern int      compareItemPointers(ItemPointer a, ItemPointer b);
 317 extern void
 318 MergeItemPointers(
 319                                   ItemPointerData *dst,
 320                                   ItemPointerData *a, uint32 na,
 321                                   ItemPointerData *b, uint32 nb
 322 );
 323
 324 extern void GinDataPageAddItem(Page page, void *data, OffsetNumber offset);
 325 extern void PageDeletePostingItem(Page page, OffsetNumber offset);
 326
 327 typedef struct
 328 {
 329         GinBtreeData btree;
 330         GinBtreeStack *stack;
 331 } GinPostingTreeScan;
 332
 333 extern GinPostingTreeScan *prepareScanPostingTree(Relation index,
 334                                            BlockNumber rootBlkno, bool searchMode);
 335 extern void insertItemPointer(GinPostingTreeScan *gdi,
 336                                   ItemPointerData *items, uint32 nitem);
 337 extern Buffer scanBeginPostingTree(GinPostingTreeScan *gdi);
 338 extern void dataFillRoot(GinBtree btree, Buffer root, Buffer lbuf, Buffer rbuf);
 339 extern void prepareDataScan(GinBtree btree, Relation index);
 340
 341 /* ginscan.c */
 342
 343 typedef struct GinScanEntryData *GinScanEntry;
 344
 345 typedef struct GinScanEntryData
 346 {
 347         /* link to the equals entry in current scan key */
 348         GinScanEntry master;
 349
 350         /*
 351          * link to values reported to consistentFn, points to
 352          * GinScanKey->entryRes[i]
 353          */
 354         bool       *pval;
 355
 356         /* entry, got from extractQueryFn */
 357         Datum           entry;
 358
 359         /* current ItemPointer to heap, its offset in buffer and buffer */
 360         ItemPointerData curItem;
 361         OffsetNumber offset;
 362         Buffer          buffer;
 363
 364         /* in case of Posing list */
 365         ItemPointerData *list;
 366         uint32          nlist;
 367
 368         bool            isFinished;
 369         bool            reduceResult;
 370         uint32          predictNumberResult;
 371 } GinScanEntryData;
 372
 373 typedef struct GinScanKeyData
 374 {
 375         /* Number of entries in query (got by extractQueryFn) */
 376         uint32          nentries;
 377
 378         /* array of ItemPointer result, reported to consistentFn */
 379         bool       *entryRes;
 380
 381         /* array of scans per entry */
 382         GinScanEntry scanEntry;
 383
 384         /* for calling consistentFn(GinScanKey->entryRes, strategy, query) */
 385         StrategyNumber strategy;
 386         Datum           query;
 387
 388         ItemPointerData curItem;
 389         bool            firstCall;
 390         bool            isFinished;
 391 } GinScanKeyData;
 392
 393 typedef GinScanKeyData *GinScanKey;
 394
 395 typedef struct GinScanOpaqueData
 396 {
 397         MemoryContext tempCtx;
 398         GinState        ginstate;
 399
 400         GinScanKey      keys;
 401         uint32          nkeys;
 402         bool            isVoidRes; /* true if ginstate.extractQueryFn
 403                                                           guarantees that nothing will be found */
 404
 405         GinScanKey      markPos;
 406 } GinScanOpaqueData;
 407
 408 typedef GinScanOpaqueData *GinScanOpaque;
 409
 410 extern Datum ginbeginscan(PG_FUNCTION_ARGS);
 411 extern Datum ginendscan(PG_FUNCTION_ARGS);
 412 extern Datum ginrescan(PG_FUNCTION_ARGS);
 413 extern Datum ginmarkpos(PG_FUNCTION_ARGS);
 414 extern Datum ginrestrpos(PG_FUNCTION_ARGS);
 415 extern void newScanKey(IndexScanDesc scan);
 416
 417 /* ginget.c */
 418 extern DLLIMPORT int GinFuzzySearchLimit;
 419
 420 #define ItemPointerSetMax(p)    ItemPointerSet( (p), (BlockNumber)0xffffffff, (OffsetNumber)0xffff )
 421 #define ItemPointerIsMax(p) ( ItemPointerGetBlockNumber(p) == (BlockNumber)0xffffffff && ItemPointerGetOffsetNumber(p) == (OffsetNumber)0xffff )
 422 #define ItemPointerSetMin(p)    ItemPointerSet( (p), (BlockNumber)0, (OffsetNumber)0)
 423 #define ItemPointerIsMin(p) ( ItemPointerGetBlockNumber(p) == (BlockNumber)0 && ItemPointerGetOffsetNumber(p) == (OffsetNumber)0 )
 424
 425 extern Datum gingetmulti(PG_FUNCTION_ARGS);
 426 extern Datum gingettuple(PG_FUNCTION_ARGS);
 427
 428 /* ginvacuum.c */
 429 extern Datum ginbulkdelete(PG_FUNCTION_ARGS);
 430 extern Datum ginvacuumcleanup(PG_FUNCTION_ARGS);
 431
 432 /* ginarrayproc.c */
 433 extern Datum ginarrayextract(PG_FUNCTION_ARGS);
 434 extern Datum ginarrayconsistent(PG_FUNCTION_ARGS);
 435
 436 /* ginbulk.c */
 437 typedef struct EntryAccumulator
 438 {
 439         Datum           value;
 440         uint32          length;
 441         uint32          number;
 442         ItemPointerData *list;
 443         bool            shouldSort;
 444         struct EntryAccumulator *left;
 445         struct EntryAccumulator *right;
 446 } EntryAccumulator;
 447
 448 typedef struct
 449 {
 450         GinState   *ginstate;
 451         EntryAccumulator *entries;
 452         uint32          maxdepth;
 453         EntryAccumulator **stack;
 454         uint32          stackpos;
 455         uint32          allocatedMemory;
 456
 457         uint32          length;
 458         EntryAccumulator *entryallocator;
 459 } BuildAccumulator;
 460
 461 extern void ginInitBA(BuildAccumulator *accum);
 462 extern void ginInsertRecordBA(BuildAccumulator *accum,
 463                                   ItemPointer heapptr, Datum *entries, int32 nentry);
 464 extern ItemPointerData *ginGetEntry(BuildAccumulator *accum, Datum *entry, uint32 *n);
 465
 466 #endif