src/include/access/gin.h

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