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-2008, PostgreSQL Global Development Group
   6  *
   7  *      $PostgreSQL: pgsql/src/include/access/gin.h,v 1.21 2008/06/06 22:35:22 alvherre Exp $
   8  *--------------------------------------------------------------------------
   9  */
  10
  11
  12 #ifndef GIN_H
  13 #define GIN_H
  14
  15 #include "access/itup.h"
  16 #include "access/relscan.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 GinDataPageGetData(page)        \
 125         (PageGetContents(page)+MAXALIGN(sizeof(ItemPointerData)))
 126 #define GinDataPageGetRightBound(page)  ((ItemPointer)PageGetContents(page))
 127 #define GinSizeOfItem(page) ( (GinPageIsLeaf(page)) ? sizeof(ItemPointerData) : sizeof(PostingItem) )
 128 #define GinDataPageGetItem(page,i) ( GinDataPageGetData(page) + ((i)-1) * GinSizeOfItem(page) )
 129
 130 #define GinDataPageGetFreeSpace(page)   \
 131         ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GinPageOpaqueData)) - \
 132                 GinPageGetOpaque(page)->maxoff * GinSizeOfItem(page) - \
 133                 MAXALIGN(sizeof(ItemPointerData)))
 134
 135
 136
 137 #define GIN_UNLOCK      BUFFER_LOCK_UNLOCK
 138 #define GIN_SHARE       BUFFER_LOCK_SHARE
 139 #define GIN_EXCLUSIVE  BUFFER_LOCK_EXCLUSIVE
 140
 141 typedef struct GinState
 142 {
 143         FmgrInfo        compareFn;
 144         FmgrInfo        extractValueFn;
 145         FmgrInfo        extractQueryFn;
 146         FmgrInfo        consistentFn;
 147         FmgrInfo        comparePartialFn;       /* optional method */
 148
 149         bool            canPartialMatch;        /* can opclass perform partial
 150                                                                          * match (prefix search)? */
 151         TupleDesc       tupdesc;
 152 } GinState;
 153
 154 /* XLog stuff */
 155
 156 #define XLOG_GIN_CREATE_INDEX  0x00
 157
 158 #define XLOG_GIN_CREATE_PTREE  0x10
 159
 160 typedef struct ginxlogCreatePostingTree
 161 {
 162         RelFileNode node;
 163         BlockNumber blkno;
 164         uint32          nitem;
 165         /* follows list of heap's ItemPointer */
 166 } ginxlogCreatePostingTree;
 167
 168 #define XLOG_GIN_INSERT  0x20
 169
 170 typedef struct ginxlogInsert
 171 {
 172         RelFileNode node;
 173         BlockNumber blkno;
 174         BlockNumber updateBlkno;
 175         OffsetNumber offset;
 176         bool            isDelete;
 177         bool            isData;
 178         bool            isLeaf;
 179         OffsetNumber nitem;
 180
 181         /*
 182          * follows: tuples or ItemPointerData or PostingItem or list of
 183          * ItemPointerData
 184          */
 185 } ginxlogInsert;
 186
 187 #define XLOG_GIN_SPLIT  0x30
 188
 189 typedef struct ginxlogSplit
 190 {
 191         RelFileNode node;
 192         BlockNumber lblkno;
 193         BlockNumber rootBlkno;
 194         BlockNumber rblkno;
 195         BlockNumber rrlink;
 196         OffsetNumber separator;
 197         OffsetNumber nitem;
 198
 199         bool            isData;
 200         bool            isLeaf;
 201         bool            isRootSplit;
 202
 203         BlockNumber leftChildBlkno;
 204         BlockNumber updateBlkno;
 205
 206         ItemPointerData rightbound; /* used only in posting tree */
 207         /* follows: list of tuple or ItemPointerData or PostingItem */
 208 } ginxlogSplit;
 209
 210 #define XLOG_GIN_VACUUM_PAGE    0x40
 211
 212 typedef struct ginxlogVacuumPage
 213 {
 214         RelFileNode node;
 215         BlockNumber blkno;
 216         OffsetNumber nitem;
 217         /* follows content of page */
 218 } ginxlogVacuumPage;
 219
 220 #define XLOG_GIN_DELETE_PAGE    0x50
 221
 222 typedef struct ginxlogDeletePage
 223 {
 224         RelFileNode node;
 225         BlockNumber blkno;
 226         BlockNumber parentBlkno;
 227         OffsetNumber parentOffset;
 228         BlockNumber leftBlkno;
 229         BlockNumber rightLink;
 230 } ginxlogDeletePage;
 231
 232 /* ginutil.c */
 233 extern Datum ginoptions(PG_FUNCTION_ARGS);
 234 extern void initGinState(GinState *state, Relation index);
 235 extern Buffer GinNewBuffer(Relation index);
 236 extern void GinInitBuffer(Buffer b, uint32 f);
 237 extern void GinInitPage(Page page, uint32 f, Size pageSize);
 238 extern int      compareEntries(GinState *ginstate, Datum a, Datum b);
 239 extern Datum *extractEntriesS(GinState *ginstate, Datum value,
 240                                 int32 *nentries, bool *needUnique);
 241 extern Datum *extractEntriesSU(GinState *ginstate, Datum value, int32 *nentries);
 242 extern Page GinPageGetCopyPage(Page page);
 243
 244 /* gininsert.c */
 245 extern Datum ginbuild(PG_FUNCTION_ARGS);
 246 extern Datum gininsert(PG_FUNCTION_ARGS);
 247
 248 /* ginxlog.c */
 249 extern void gin_redo(XLogRecPtr lsn, XLogRecord *record);
 250 extern void gin_desc(StringInfo buf, uint8 xl_info, char *rec);
 251 extern void gin_xlog_startup(void);
 252 extern void gin_xlog_cleanup(void);
 253 extern bool gin_safe_restartpoint(void);
 254
 255 /* ginbtree.c */
 256
 257 typedef struct GinBtreeStack
 258 {
 259         BlockNumber blkno;
 260         Buffer          buffer;
 261         OffsetNumber off;
 262         /* predictNumber contains prediction number of pages on current level */
 263         uint32          predictNumber;
 264         struct GinBtreeStack *parent;
 265 } GinBtreeStack;
 266
 267 typedef struct GinBtreeData *GinBtree;
 268
 269 typedef struct GinBtreeData
 270 {
 271         /* search methods */
 272         BlockNumber (*findChildPage) (GinBtree, GinBtreeStack *);
 273         bool            (*isMoveRight) (GinBtree, Page);
 274         bool            (*findItem) (GinBtree, GinBtreeStack *);
 275
 276         /* insert methods */
 277         OffsetNumber (*findChildPtr) (GinBtree, Page, BlockNumber, OffsetNumber);
 278         BlockNumber (*getLeftMostPage) (GinBtree, Page);
 279         bool            (*isEnoughSpace) (GinBtree, Buffer, OffsetNumber);
 280         void            (*placeToPage) (GinBtree, Buffer, OffsetNumber, XLogRecData **);
 281         Page            (*splitPage) (GinBtree, Buffer, Buffer, OffsetNumber, XLogRecData **);
 282         void            (*fillRoot) (GinBtree, Buffer, Buffer, Buffer);
 283
 284         bool            searchMode;
 285
 286         Relation        index;
 287         GinState   *ginstate;
 288         bool            fullScan;
 289         bool            isBuild;
 290
 291         BlockNumber rightblkno;
 292
 293         /* Entry options */
 294         Datum           entryValue;
 295         IndexTuple      entry;
 296         bool            isDelete;
 297
 298         /* Data (posting tree) option */
 299         ItemPointerData *items;
 300         uint32          nitem;
 301         uint32          curitem;
 302
 303         PostingItem pitem;
 304 } GinBtreeData;
 305
 306 extern GinBtreeStack *ginPrepareFindLeafPage(GinBtree btree, BlockNumber blkno);
 307 extern GinBtreeStack *ginFindLeafPage(GinBtree btree, GinBtreeStack *stack);
 308 extern void freeGinBtreeStack(GinBtreeStack *stack);
 309 extern void ginInsertValue(GinBtree btree, GinBtreeStack *stack);
 310 extern void findParents(GinBtree btree, GinBtreeStack *stack, BlockNumber rootBlkno);
 311
 312 /* ginentrypage.c */
 313 extern IndexTuple GinFormTuple(GinState *ginstate, Datum key, ItemPointerData *ipd, uint32 nipd);
 314 extern Datum ginGetHighKey(GinState *ginstate, Page page);
 315 extern void prepareEntryScan(GinBtree btree, Relation index, Datum value, GinState *ginstate);
 316 extern void entryFillRoot(GinBtree btree, Buffer root, Buffer lbuf, Buffer rbuf);
 317 extern IndexTuple ginPageGetLinkItup(Buffer buf);
 318
 319 /* gindatapage.c */
 320 extern int      compareItemPointers(ItemPointer a, ItemPointer b);
 321 extern void
 322 MergeItemPointers(
 323                                   ItemPointerData *dst,
 324                                   ItemPointerData *a, uint32 na,
 325                                   ItemPointerData *b, uint32 nb
 326 );
 327
 328 extern void GinDataPageAddItem(Page page, void *data, OffsetNumber offset);
 329 extern void PageDeletePostingItem(Page page, OffsetNumber offset);
 330
 331 typedef struct
 332 {
 333         GinBtreeData btree;
 334         GinBtreeStack *stack;
 335 } GinPostingTreeScan;
 336
 337 extern GinPostingTreeScan *prepareScanPostingTree(Relation index,
 338                                            BlockNumber rootBlkno, bool searchMode);
 339 extern void insertItemPointer(GinPostingTreeScan *gdi,
 340                                   ItemPointerData *items, uint32 nitem);
 341 extern Buffer scanBeginPostingTree(GinPostingTreeScan *gdi);
 342 extern void dataFillRoot(GinBtree btree, Buffer root, Buffer lbuf, Buffer rbuf);
 343 extern void prepareDataScan(GinBtree btree, Relation index);
 344
 345 /* ginscan.c */
 346
 347 typedef struct GinScanEntryData *GinScanEntry;
 348
 349 typedef struct GinScanEntryData
 350 {
 351         /* link to the equals entry in current scan key */
 352         GinScanEntry master;
 353
 354         /*
 355          * link to values reported to consistentFn, points to
 356          * GinScanKey->entryRes[i]
 357          */
 358         bool       *pval;
 359
 360         /* entry, got from extractQueryFn */
 361         Datum           entry;
 362
 363         /* Current page in posting tree */
 364         Buffer          buffer;
 365
 366         /* current ItemPointer to heap */
 367         ItemPointerData curItem;
 368
 369         /* partial match support */
 370         bool            isPartialMatch;
 371         TIDBitmap  *partialMatch;
 372         TBMIterateResult *partialMatchResult;
 373         StrategyNumber strategy;
 374
 375         /* used for Posting list and one page in Posting tree */
 376         ItemPointerData *list;
 377         uint32                   nlist;
 378         OffsetNumber     offset;
 379
 380         bool            isFinished;
 381         bool            reduceResult;
 382         uint32          predictNumberResult;
 383 } GinScanEntryData;
 384
 385 typedef struct GinScanKeyData
 386 {
 387         /* Number of entries in query (got by extractQueryFn) */
 388         uint32          nentries;
 389
 390         /* array of ItemPointer result, reported to consistentFn */
 391         bool       *entryRes;
 392
 393         /* array of scans per entry */
 394         GinScanEntry scanEntry;
 395
 396         /* for calling consistentFn(GinScanKey->entryRes, strategy, query) */
 397         StrategyNumber strategy;
 398         Datum           query;
 399
 400         ItemPointerData curItem;
 401         bool            firstCall;
 402         bool            isFinished;
 403 } GinScanKeyData;
 404
 405 typedef GinScanKeyData *GinScanKey;
 406
 407 typedef struct GinScanOpaqueData
 408 {
 409         MemoryContext tempCtx;
 410         GinState        ginstate;
 411
 412         GinScanKey      keys;
 413         uint32          nkeys;
 414         bool            isVoidRes;              /* true if ginstate.extractQueryFn guarantees
 415                                                                  * that nothing will be found */
 416
 417         GinScanKey      markPos;
 418 } GinScanOpaqueData;
 419
 420 typedef GinScanOpaqueData *GinScanOpaque;
 421
 422 extern Datum ginbeginscan(PG_FUNCTION_ARGS);
 423 extern Datum ginendscan(PG_FUNCTION_ARGS);
 424 extern Datum ginrescan(PG_FUNCTION_ARGS);
 425 extern Datum ginmarkpos(PG_FUNCTION_ARGS);
 426 extern Datum ginrestrpos(PG_FUNCTION_ARGS);
 427 extern void newScanKey(IndexScanDesc scan);
 428
 429 /* ginget.c */
 430 extern PGDLLIMPORT int GinFuzzySearchLimit;
 431
 432 #define ItemPointerSetMax(p)    ItemPointerSet( (p), (BlockNumber)0xffffffff, (OffsetNumber)0xffff )
 433 #define ItemPointerIsMax(p) ( ItemPointerGetBlockNumber(p) == (BlockNumber)0xffffffff && ItemPointerGetOffsetNumber(p) == (OffsetNumber)0xffff )
 434 #define ItemPointerSetMin(p)    ItemPointerSet( (p), (BlockNumber)0, (OffsetNumber)0)
 435 #define ItemPointerIsMin(p) ( ItemPointerGetBlockNumber(p) == (BlockNumber)0 && ItemPointerGetOffsetNumber(p) == (OffsetNumber)0 )
 436
 437 extern Datum gingetbitmap(PG_FUNCTION_ARGS);
 438 extern Datum gingettuple(PG_FUNCTION_ARGS);
 439 extern void ginrestartentry(GinScanEntry entry);
 440
 441 /* ginvacuum.c */
 442 extern Datum ginbulkdelete(PG_FUNCTION_ARGS);
 443 extern Datum ginvacuumcleanup(PG_FUNCTION_ARGS);
 444
 445 /* ginarrayproc.c */
 446 extern Datum ginarrayextract(PG_FUNCTION_ARGS);
 447 extern Datum ginqueryarrayextract(PG_FUNCTION_ARGS);
 448 extern Datum ginarrayconsistent(PG_FUNCTION_ARGS);
 449
 450 /* ginbulk.c */
 451 typedef struct EntryAccumulator
 452 {
 453         Datum           value;
 454         uint32          length;
 455         uint32          number;
 456         ItemPointerData *list;
 457         bool            shouldSort;
 458         struct EntryAccumulator *left;
 459         struct EntryAccumulator *right;
 460 } EntryAccumulator;
 461
 462 typedef struct
 463 {
 464         GinState   *ginstate;
 465         EntryAccumulator *entries;
 466         uint32          maxdepth;
 467         EntryAccumulator **stack;
 468         uint32          stackpos;
 469         long            allocatedMemory;
 470
 471         uint32          length;
 472         EntryAccumulator *entryallocator;
 473 } BuildAccumulator;
 474
 475 extern void ginInitBA(BuildAccumulator *accum);
 476 extern void ginInsertRecordBA(BuildAccumulator *accum,
 477                                   ItemPointer heapptr, Datum *entries, int32 nentry);
 478 extern ItemPointerData *ginGetEntry(BuildAccumulator *accum, Datum *entry, uint32 *n);
 479
 480 #endif