Header And Logo

PostgreSQL
| The world's most advanced open source database.

gin_private.h

Go to the documentation of this file.
00001 /*--------------------------------------------------------------------------
00002  * gin_private.h
00003  *    header file for postgres inverted index access method implementation.
00004  *
00005  *  Copyright (c) 2006-2013, PostgreSQL Global Development Group
00006  *
00007  *  src/include/access/gin_private.h
00008  *--------------------------------------------------------------------------
00009  */
00010 #ifndef GIN_PRIVATE_H
00011 #define GIN_PRIVATE_H
00012 
00013 #include "access/genam.h"
00014 #include "access/gin.h"
00015 #include "access/itup.h"
00016 #include "fmgr.h"
00017 #include "storage/bufmgr.h"
00018 #include "utils/rbtree.h"
00019 
00020 
00021 /*
00022  * Page opaque data in a inverted index page.
00023  *
00024  * Note: GIN does not include a page ID word as do the other index types.
00025  * This is OK because the opaque data is only 8 bytes and so can be reliably
00026  * distinguished by size.  Revisit this if the size ever increases.
00027  * Further note: as of 9.2, SP-GiST also uses 8-byte special space.  This is
00028  * still OK, as long as GIN isn't using all of the high-order bits in its
00029  * flags word, because that way the flags word cannot match the page ID used
00030  * by SP-GiST.
00031  */
00032 typedef struct GinPageOpaqueData
00033 {
00034     BlockNumber rightlink;      /* next page if any */
00035     OffsetNumber maxoff;        /* number entries on GIN_DATA page: number of
00036                                  * heap ItemPointers on GIN_DATA|GIN_LEAF page
00037                                  * or number of PostingItems on GIN_DATA &
00038                                  * ~GIN_LEAF page. On GIN_LIST page, number of
00039                                  * heap tuples. */
00040     uint16      flags;          /* see bit definitions below */
00041 } GinPageOpaqueData;
00042 
00043 typedef GinPageOpaqueData *GinPageOpaque;
00044 
00045 #define GIN_DATA          (1 << 0)
00046 #define GIN_LEAF          (1 << 1)
00047 #define GIN_DELETED       (1 << 2)
00048 #define GIN_META          (1 << 3)
00049 #define GIN_LIST          (1 << 4)
00050 #define GIN_LIST_FULLROW  (1 << 5)      /* makes sense only on GIN_LIST page */
00051 
00052 /* Page numbers of fixed-location pages */
00053 #define GIN_METAPAGE_BLKNO  (0)
00054 #define GIN_ROOT_BLKNO      (1)
00055 
00056 typedef struct GinMetaPageData
00057 {
00058     /*
00059      * Pointers to head and tail of pending list, which consists of GIN_LIST
00060      * pages.  These store fast-inserted entries that haven't yet been moved
00061      * into the regular GIN structure.
00062      */
00063     BlockNumber head;
00064     BlockNumber tail;
00065 
00066     /*
00067      * Free space in bytes in the pending list's tail page.
00068      */
00069     uint32      tailFreeSize;
00070 
00071     /*
00072      * We store both number of pages and number of heap tuples that are in the
00073      * pending list.
00074      */
00075     BlockNumber nPendingPages;
00076     int64       nPendingHeapTuples;
00077 
00078     /*
00079      * Statistics for planner use (accurate as of last VACUUM)
00080      */
00081     BlockNumber nTotalPages;
00082     BlockNumber nEntryPages;
00083     BlockNumber nDataPages;
00084     int64       nEntries;
00085 
00086     /*
00087      * GIN version number (ideally this should have been at the front, but too
00088      * late now.  Don't move it!)
00089      *
00090      * Currently 1 (for indexes initialized in 9.1 or later)
00091      *
00092      * Version 0 (indexes initialized in 9.0 or before) is compatible but may
00093      * be missing null entries, including both null keys and placeholders.
00094      * Reject full-index-scan attempts on such indexes.
00095      */
00096     int32       ginVersion;
00097 } GinMetaPageData;
00098 
00099 #define GIN_CURRENT_VERSION     1
00100 
00101 #define GinPageGetMeta(p) \
00102     ((GinMetaPageData *) PageGetContents(p))
00103 
00104 /*
00105  * Macros for accessing a GIN index page's opaque data
00106  */
00107 #define GinPageGetOpaque(page) ( (GinPageOpaque) PageGetSpecialPointer(page) )
00108 
00109 #define GinPageIsLeaf(page)    ( GinPageGetOpaque(page)->flags & GIN_LEAF )
00110 #define GinPageSetLeaf(page)   ( GinPageGetOpaque(page)->flags |= GIN_LEAF )
00111 #define GinPageSetNonLeaf(page)    ( GinPageGetOpaque(page)->flags &= ~GIN_LEAF )
00112 #define GinPageIsData(page)    ( GinPageGetOpaque(page)->flags & GIN_DATA )
00113 #define GinPageSetData(page)   ( GinPageGetOpaque(page)->flags |= GIN_DATA )
00114 #define GinPageIsList(page)    ( GinPageGetOpaque(page)->flags & GIN_LIST )
00115 #define GinPageSetList(page)   ( GinPageGetOpaque(page)->flags |= GIN_LIST )
00116 #define GinPageHasFullRow(page)    ( GinPageGetOpaque(page)->flags & GIN_LIST_FULLROW )
00117 #define GinPageSetFullRow(page)   ( GinPageGetOpaque(page)->flags |= GIN_LIST_FULLROW )
00118 
00119 #define GinPageIsDeleted(page) ( GinPageGetOpaque(page)->flags & GIN_DELETED)
00120 #define GinPageSetDeleted(page)    ( GinPageGetOpaque(page)->flags |= GIN_DELETED)
00121 #define GinPageSetNonDeleted(page) ( GinPageGetOpaque(page)->flags &= ~GIN_DELETED)
00122 
00123 #define GinPageRightMost(page) ( GinPageGetOpaque(page)->rightlink == InvalidBlockNumber)
00124 
00125 /*
00126  * We use our own ItemPointerGet(BlockNumber|GetOffsetNumber)
00127  * to avoid Asserts, since sometimes the ip_posid isn't "valid"
00128  */
00129 #define GinItemPointerGetBlockNumber(pointer) \
00130     BlockIdGetBlockNumber(&(pointer)->ip_blkid)
00131 
00132 #define GinItemPointerGetOffsetNumber(pointer) \
00133     ((pointer)->ip_posid)
00134 
00135 /*
00136  * Special-case item pointer values needed by the GIN search logic.
00137  *  MIN: sorts less than any valid item pointer
00138  *  MAX: sorts greater than any valid item pointer
00139  *  LOSSY PAGE: indicates a whole heap page, sorts after normal item
00140  *              pointers for that page
00141  * Note that these are all distinguishable from an "invalid" item pointer
00142  * (which is InvalidBlockNumber/0) as well as from all normal item
00143  * pointers (which have item numbers in the range 1..MaxHeapTuplesPerPage).
00144  */
00145 #define ItemPointerSetMin(p)  \
00146     ItemPointerSet((p), (BlockNumber)0, (OffsetNumber)0)
00147 #define ItemPointerIsMin(p)  \
00148     (GinItemPointerGetOffsetNumber(p) == (OffsetNumber)0 && \
00149      GinItemPointerGetBlockNumber(p) == (BlockNumber)0)
00150 #define ItemPointerSetMax(p)  \
00151     ItemPointerSet((p), InvalidBlockNumber, (OffsetNumber)0xffff)
00152 #define ItemPointerIsMax(p)  \
00153     (GinItemPointerGetOffsetNumber(p) == (OffsetNumber)0xffff && \
00154      GinItemPointerGetBlockNumber(p) == InvalidBlockNumber)
00155 #define ItemPointerSetLossyPage(p, b)  \
00156     ItemPointerSet((p), (b), (OffsetNumber)0xffff)
00157 #define ItemPointerIsLossyPage(p)  \
00158     (GinItemPointerGetOffsetNumber(p) == (OffsetNumber)0xffff && \
00159      GinItemPointerGetBlockNumber(p) != InvalidBlockNumber)
00160 
00161 /*
00162  * Posting item in a non-leaf posting-tree page
00163  */
00164 typedef struct
00165 {
00166     /* We use BlockIdData not BlockNumber to avoid padding space wastage */
00167     BlockIdData child_blkno;
00168     ItemPointerData key;
00169 } PostingItem;
00170 
00171 #define PostingItemGetBlockNumber(pointer) \
00172     BlockIdGetBlockNumber(&(pointer)->child_blkno)
00173 
00174 #define PostingItemSetBlockNumber(pointer, blockNumber) \
00175     BlockIdSet(&((pointer)->child_blkno), (blockNumber))
00176 
00177 /*
00178  * Category codes to distinguish placeholder nulls from ordinary NULL keys.
00179  * Note that the datatype size and the first two code values are chosen to be
00180  * compatible with the usual usage of bool isNull flags.
00181  *
00182  * GIN_CAT_EMPTY_QUERY is never stored in the index; and notice that it is
00183  * chosen to sort before not after regular key values.
00184  */
00185 typedef signed char GinNullCategory;
00186 
00187 #define GIN_CAT_NORM_KEY        0       /* normal, non-null key value */
00188 #define GIN_CAT_NULL_KEY        1       /* null key value */
00189 #define GIN_CAT_EMPTY_ITEM      2       /* placeholder for zero-key item */
00190 #define GIN_CAT_NULL_ITEM       3       /* placeholder for null item */
00191 #define GIN_CAT_EMPTY_QUERY     (-1)    /* placeholder for full-scan query */
00192 
00193 /*
00194  * Access macros for null category byte in entry tuples
00195  */
00196 #define GinCategoryOffset(itup,ginstate) \
00197     (IndexInfoFindDataOffset((itup)->t_info) + \
00198      ((ginstate)->oneCol ? 0 : sizeof(int16)))
00199 #define GinGetNullCategory(itup,ginstate) \
00200     (*((GinNullCategory *) ((char*)(itup) + GinCategoryOffset(itup,ginstate))))
00201 #define GinSetNullCategory(itup,ginstate,c) \
00202     (*((GinNullCategory *) ((char*)(itup) + GinCategoryOffset(itup,ginstate))) = (c))
00203 
00204 /*
00205  * Access macros for leaf-page entry tuples (see discussion in README)
00206  */
00207 #define GinGetNPosting(itup)    GinItemPointerGetOffsetNumber(&(itup)->t_tid)
00208 #define GinSetNPosting(itup,n)  ItemPointerSetOffsetNumber(&(itup)->t_tid,n)
00209 #define GIN_TREE_POSTING        ((OffsetNumber)0xffff)
00210 #define GinIsPostingTree(itup)  (GinGetNPosting(itup) == GIN_TREE_POSTING)
00211 #define GinSetPostingTree(itup, blkno)  ( GinSetNPosting((itup),GIN_TREE_POSTING), ItemPointerSetBlockNumber(&(itup)->t_tid, blkno) )
00212 #define GinGetPostingTree(itup) GinItemPointerGetBlockNumber(&(itup)->t_tid)
00213 
00214 #define GinGetPostingOffset(itup)   GinItemPointerGetBlockNumber(&(itup)->t_tid)
00215 #define GinSetPostingOffset(itup,n) ItemPointerSetBlockNumber(&(itup)->t_tid,n)
00216 #define GinGetPosting(itup)         ((ItemPointer) ((char*)(itup) + GinGetPostingOffset(itup)))
00217 
00218 #define GinMaxItemSize \
00219     MAXALIGN_DOWN(((BLCKSZ - SizeOfPageHeaderData - \
00220         MAXALIGN(sizeof(GinPageOpaqueData))) / 3 - sizeof(ItemIdData)))
00221 
00222 /*
00223  * Access macros for non-leaf entry tuples
00224  */
00225 #define GinGetDownlink(itup)    GinItemPointerGetBlockNumber(&(itup)->t_tid)
00226 #define GinSetDownlink(itup,blkno)  ItemPointerSet(&(itup)->t_tid, blkno, InvalidOffsetNumber)
00227 
00228 
00229 /*
00230  * Data (posting tree) pages
00231  */
00232 #define GinDataPageGetRightBound(page)  ((ItemPointer) PageGetContents(page))
00233 #define GinDataPageGetData(page)    \
00234     (PageGetContents(page) + MAXALIGN(sizeof(ItemPointerData)))
00235 #define GinSizeOfDataPageItem(page) \
00236     (GinPageIsLeaf(page) ? sizeof(ItemPointerData) : sizeof(PostingItem))
00237 #define GinDataPageGetItem(page,i)  \
00238     (GinDataPageGetData(page) + ((i)-1) * GinSizeOfDataPageItem(page))
00239 
00240 #define GinDataPageGetFreeSpace(page)   \
00241     (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) \
00242      - MAXALIGN(sizeof(ItemPointerData)) \
00243      - GinPageGetOpaque(page)->maxoff * GinSizeOfDataPageItem(page) \
00244      - MAXALIGN(sizeof(GinPageOpaqueData)))
00245 
00246 #define GinMaxLeafDataItems \
00247     ((BLCKSZ - MAXALIGN(SizeOfPageHeaderData) - \
00248       MAXALIGN(sizeof(ItemPointerData)) - \
00249       MAXALIGN(sizeof(GinPageOpaqueData))) \
00250      / sizeof(ItemPointerData))
00251 
00252 /*
00253  * List pages
00254  */
00255 #define GinListPageSize  \
00256     ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GinPageOpaqueData)) )
00257 
00258 /*
00259  * Storage type for GIN's reloptions
00260  */
00261 typedef struct GinOptions
00262 {
00263     int32       vl_len_;        /* varlena header (do not touch directly!) */
00264     bool        useFastUpdate;  /* use fast updates? */
00265 } GinOptions;
00266 
00267 #define GIN_DEFAULT_USE_FASTUPDATE  true
00268 #define GinGetUseFastUpdate(relation) \
00269     ((relation)->rd_options ? \
00270      ((GinOptions *) (relation)->rd_options)->useFastUpdate : GIN_DEFAULT_USE_FASTUPDATE)
00271 
00272 
00273 /* Macros for buffer lock/unlock operations */
00274 #define GIN_UNLOCK  BUFFER_LOCK_UNLOCK
00275 #define GIN_SHARE   BUFFER_LOCK_SHARE
00276 #define GIN_EXCLUSIVE  BUFFER_LOCK_EXCLUSIVE
00277 
00278 
00279 /*
00280  * GinState: working data structure describing the index being worked on
00281  */
00282 typedef struct GinState
00283 {
00284     Relation    index;
00285     bool        oneCol;         /* true if single-column index */
00286 
00287     /*
00288      * origTupDesc is the nominal tuple descriptor of the index, ie, the i'th
00289      * attribute shows the key type (not the input data type!) of the i'th
00290      * index column.  In a single-column index this describes the actual leaf
00291      * index tuples.  In a multi-column index, the actual leaf tuples contain
00292      * a smallint column number followed by a key datum of the appropriate
00293      * type for that column.  We set up tupdesc[i] to describe the actual
00294      * rowtype of the index tuples for the i'th column, ie, (int2, keytype).
00295      * Note that in any case, leaf tuples contain more data than is known to
00296      * the TupleDesc; see access/gin/README for details.
00297      */
00298     TupleDesc   origTupdesc;
00299     TupleDesc   tupdesc[INDEX_MAX_KEYS];
00300 
00301     /*
00302      * Per-index-column opclass support functions
00303      */
00304     FmgrInfo    compareFn[INDEX_MAX_KEYS];
00305     FmgrInfo    extractValueFn[INDEX_MAX_KEYS];
00306     FmgrInfo    extractQueryFn[INDEX_MAX_KEYS];
00307     FmgrInfo    consistentFn[INDEX_MAX_KEYS];
00308     FmgrInfo    comparePartialFn[INDEX_MAX_KEYS];       /* optional method */
00309     /* canPartialMatch[i] is true if comparePartialFn[i] is valid */
00310     bool        canPartialMatch[INDEX_MAX_KEYS];
00311     /* Collations to pass to the support functions */
00312     Oid         supportCollation[INDEX_MAX_KEYS];
00313 } GinState;
00314 
00315 /* XLog stuff */
00316 
00317 #define XLOG_GIN_CREATE_INDEX  0x00
00318 
00319 #define XLOG_GIN_CREATE_PTREE  0x10
00320 
00321 typedef struct ginxlogCreatePostingTree
00322 {
00323     RelFileNode node;
00324     BlockNumber blkno;
00325     uint32      nitem;
00326     /* follows list of heap's ItemPointer */
00327 } ginxlogCreatePostingTree;
00328 
00329 #define XLOG_GIN_INSERT  0x20
00330 
00331 typedef struct ginxlogInsert
00332 {
00333     RelFileNode node;
00334     BlockNumber blkno;
00335     BlockNumber updateBlkno;
00336     OffsetNumber offset;
00337     bool        isDelete;
00338     bool        isData;
00339     bool        isLeaf;
00340     OffsetNumber nitem;
00341 
00342     /*
00343      * follows: tuples or ItemPointerData or PostingItem or list of
00344      * ItemPointerData
00345      */
00346 } ginxlogInsert;
00347 
00348 #define XLOG_GIN_SPLIT  0x30
00349 
00350 typedef struct ginxlogSplit
00351 {
00352     RelFileNode node;
00353     BlockNumber lblkno;
00354     BlockNumber rootBlkno;
00355     BlockNumber rblkno;
00356     BlockNumber rrlink;
00357     OffsetNumber separator;
00358     OffsetNumber nitem;
00359 
00360     bool        isData;
00361     bool        isLeaf;
00362     bool        isRootSplit;
00363 
00364     BlockNumber leftChildBlkno;
00365     BlockNumber updateBlkno;
00366 
00367     ItemPointerData rightbound; /* used only in posting tree */
00368     /* follows: list of tuple or ItemPointerData or PostingItem */
00369 } ginxlogSplit;
00370 
00371 #define XLOG_GIN_VACUUM_PAGE    0x40
00372 
00373 typedef struct ginxlogVacuumPage
00374 {
00375     RelFileNode node;
00376     BlockNumber blkno;
00377     OffsetNumber nitem;
00378     /* follows content of page */
00379 } ginxlogVacuumPage;
00380 
00381 #define XLOG_GIN_DELETE_PAGE    0x50
00382 
00383 typedef struct ginxlogDeletePage
00384 {
00385     RelFileNode node;
00386     BlockNumber blkno;
00387     BlockNumber parentBlkno;
00388     OffsetNumber parentOffset;
00389     BlockNumber leftBlkno;
00390     BlockNumber rightLink;
00391 } ginxlogDeletePage;
00392 
00393 #define XLOG_GIN_UPDATE_META_PAGE 0x60
00394 
00395 typedef struct ginxlogUpdateMeta
00396 {
00397     RelFileNode node;
00398     GinMetaPageData metadata;
00399     BlockNumber prevTail;
00400     BlockNumber newRightlink;
00401     int32       ntuples;        /* if ntuples > 0 then metadata.tail was
00402                                  * updated with that many tuples; else new sub
00403                                  * list was inserted */
00404     /* array of inserted tuples follows */
00405 } ginxlogUpdateMeta;
00406 
00407 #define XLOG_GIN_INSERT_LISTPAGE  0x70
00408 
00409 typedef struct ginxlogInsertListPage
00410 {
00411     RelFileNode node;
00412     BlockNumber blkno;
00413     BlockNumber rightlink;
00414     int32       ntuples;
00415     /* array of inserted tuples follows */
00416 } ginxlogInsertListPage;
00417 
00418 #define XLOG_GIN_DELETE_LISTPAGE  0x80
00419 
00420 #define GIN_NDELETE_AT_ONCE 16
00421 typedef struct ginxlogDeleteListPages
00422 {
00423     RelFileNode node;
00424     GinMetaPageData metadata;
00425     int32       ndeleted;
00426     BlockNumber toDelete[GIN_NDELETE_AT_ONCE];
00427 } ginxlogDeleteListPages;
00428 
00429 
00430 /* ginutil.c */
00431 extern Datum ginoptions(PG_FUNCTION_ARGS);
00432 extern void initGinState(GinState *state, Relation index);
00433 extern Buffer GinNewBuffer(Relation index);
00434 extern void GinInitBuffer(Buffer b, uint32 f);
00435 extern void GinInitPage(Page page, uint32 f, Size pageSize);
00436 extern void GinInitMetabuffer(Buffer b);
00437 extern int ginCompareEntries(GinState *ginstate, OffsetNumber attnum,
00438                   Datum a, GinNullCategory categorya,
00439                   Datum b, GinNullCategory categoryb);
00440 extern int ginCompareAttEntries(GinState *ginstate,
00441                      OffsetNumber attnuma, Datum a, GinNullCategory categorya,
00442                    OffsetNumber attnumb, Datum b, GinNullCategory categoryb);
00443 extern Datum *ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
00444                   Datum value, bool isNull,
00445                   int32 *nentries, GinNullCategory **categories);
00446 
00447 extern OffsetNumber gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple);
00448 extern Datum gintuple_get_key(GinState *ginstate, IndexTuple tuple,
00449                  GinNullCategory *category);
00450 
00451 /* gininsert.c */
00452 extern Datum ginbuild(PG_FUNCTION_ARGS);
00453 extern Datum ginbuildempty(PG_FUNCTION_ARGS);
00454 extern Datum gininsert(PG_FUNCTION_ARGS);
00455 extern void ginEntryInsert(GinState *ginstate,
00456                OffsetNumber attnum, Datum key, GinNullCategory category,
00457                ItemPointerData *items, uint32 nitem,
00458                GinStatsData *buildStats);
00459 
00460 /* ginbtree.c */
00461 
00462 typedef struct GinBtreeStack
00463 {
00464     BlockNumber blkno;
00465     Buffer      buffer;
00466     OffsetNumber off;
00467     /* predictNumber contains predicted number of pages on current level */
00468     uint32      predictNumber;
00469     struct GinBtreeStack *parent;
00470 } GinBtreeStack;
00471 
00472 typedef struct GinBtreeData *GinBtree;
00473 
00474 typedef struct GinBtreeData
00475 {
00476     /* search methods */
00477     BlockNumber (*findChildPage) (GinBtree, GinBtreeStack *);
00478     bool        (*isMoveRight) (GinBtree, Page);
00479     bool        (*findItem) (GinBtree, GinBtreeStack *);
00480 
00481     /* insert methods */
00482     OffsetNumber (*findChildPtr) (GinBtree, Page, BlockNumber, OffsetNumber);
00483     BlockNumber (*getLeftMostPage) (GinBtree, Page);
00484     bool        (*isEnoughSpace) (GinBtree, Buffer, OffsetNumber);
00485     void        (*placeToPage) (GinBtree, Buffer, OffsetNumber, XLogRecData **);
00486     Page        (*splitPage) (GinBtree, Buffer, Buffer, OffsetNumber, XLogRecData **);
00487     void        (*fillRoot) (GinBtree, Buffer, Buffer, Buffer);
00488 
00489     bool        isData;
00490     bool        searchMode;
00491 
00492     Relation    index;
00493     GinState   *ginstate;       /* not valid in a data scan */
00494     bool        fullScan;
00495     bool        isBuild;
00496 
00497     BlockNumber rightblkno;
00498 
00499     /* Entry options */
00500     OffsetNumber entryAttnum;
00501     Datum       entryKey;
00502     GinNullCategory entryCategory;
00503     IndexTuple  entry;
00504     bool        isDelete;
00505 
00506     /* Data (posting tree) options */
00507     ItemPointerData *items;
00508     uint32      nitem;
00509     uint32      curitem;
00510 
00511     PostingItem pitem;
00512 } GinBtreeData;
00513 
00514 extern GinBtreeStack *ginPrepareFindLeafPage(GinBtree btree, BlockNumber blkno);
00515 extern GinBtreeStack *ginFindLeafPage(GinBtree btree, GinBtreeStack *stack);
00516 extern void freeGinBtreeStack(GinBtreeStack *stack);
00517 extern void ginInsertValue(GinBtree btree, GinBtreeStack *stack,
00518                GinStatsData *buildStats);
00519 extern void ginFindParents(GinBtree btree, GinBtreeStack *stack, BlockNumber rootBlkno);
00520 
00521 /* ginentrypage.c */
00522 extern IndexTuple GinFormTuple(GinState *ginstate,
00523              OffsetNumber attnum, Datum key, GinNullCategory category,
00524              ItemPointerData *ipd, uint32 nipd, bool errorTooBig);
00525 extern void GinShortenTuple(IndexTuple itup, uint32 nipd);
00526 extern void ginPrepareEntryScan(GinBtree btree, OffsetNumber attnum,
00527                     Datum key, GinNullCategory category,
00528                     GinState *ginstate);
00529 extern void ginEntryFillRoot(GinBtree btree, Buffer root, Buffer lbuf, Buffer rbuf);
00530 extern IndexTuple ginPageGetLinkItup(Buffer buf);
00531 
00532 /* gindatapage.c */
00533 extern int  ginCompareItemPointers(ItemPointer a, ItemPointer b);
00534 extern uint32 ginMergeItemPointers(ItemPointerData *dst,
00535                      ItemPointerData *a, uint32 na,
00536                      ItemPointerData *b, uint32 nb);
00537 
00538 extern void GinDataPageAddItem(Page page, void *data, OffsetNumber offset);
00539 extern void GinPageDeletePostingItem(Page page, OffsetNumber offset);
00540 
00541 typedef struct
00542 {
00543     GinBtreeData btree;
00544     GinBtreeStack *stack;
00545 } GinPostingTreeScan;
00546 
00547 extern GinPostingTreeScan *ginPrepareScanPostingTree(Relation index,
00548                           BlockNumber rootBlkno, bool searchMode);
00549 extern void ginInsertItemPointers(GinPostingTreeScan *gdi,
00550                       ItemPointerData *items, uint32 nitem,
00551                       GinStatsData *buildStats);
00552 extern Buffer ginScanBeginPostingTree(GinPostingTreeScan *gdi);
00553 extern void ginDataFillRoot(GinBtree btree, Buffer root, Buffer lbuf, Buffer rbuf);
00554 extern void ginPrepareDataScan(GinBtree btree, Relation index);
00555 
00556 /* ginscan.c */
00557 
00558 /*
00559  * GinScanKeyData describes a single GIN index qualifier expression.
00560  *
00561  * From each qual expression, we extract one or more specific index search
00562  * conditions, which are represented by GinScanEntryData.  It's quite
00563  * possible for identical search conditions to be requested by more than
00564  * one qual expression, in which case we merge such conditions to have just
00565  * one unique GinScanEntry --- this is particularly important for efficiency
00566  * when dealing with full-index-scan entries.  So there can be multiple
00567  * GinScanKeyData.scanEntry pointers to the same GinScanEntryData.
00568  *
00569  * In each GinScanKeyData, nentries is the true number of entries, while
00570  * nuserentries is the number that extractQueryFn returned (which is what
00571  * we report to consistentFn).  The "user" entries must come first.
00572  */
00573 typedef struct GinScanKeyData *GinScanKey;
00574 
00575 typedef struct GinScanEntryData *GinScanEntry;
00576 
00577 typedef struct GinScanKeyData
00578 {
00579     /* Real number of entries in scanEntry[] (always > 0) */
00580     uint32      nentries;
00581     /* Number of entries that extractQueryFn and consistentFn know about */
00582     uint32      nuserentries;
00583 
00584     /* array of GinScanEntry pointers, one per extracted search condition */
00585     GinScanEntry *scanEntry;
00586 
00587     /* array of check flags, reported to consistentFn */
00588     bool       *entryRes;
00589 
00590     /* other data needed for calling consistentFn */
00591     Datum       query;
00592     /* NB: these three arrays have only nuserentries elements! */
00593     Datum      *queryValues;
00594     GinNullCategory *queryCategories;
00595     Pointer    *extra_data;
00596     StrategyNumber strategy;
00597     int32       searchMode;
00598     OffsetNumber attnum;
00599 
00600     /*
00601      * Match status data.  curItem is the TID most recently tested (could be a
00602      * lossy-page pointer).  curItemMatches is TRUE if it passes the
00603      * consistentFn test; if so, recheckCurItem is the recheck flag.
00604      * isFinished means that all the input entry streams are finished, so this
00605      * key cannot succeed for any later TIDs.
00606      */
00607     ItemPointerData curItem;
00608     bool        curItemMatches;
00609     bool        recheckCurItem;
00610     bool        isFinished;
00611 }   GinScanKeyData;
00612 
00613 typedef struct GinScanEntryData
00614 {
00615     /* query key and other information from extractQueryFn */
00616     Datum       queryKey;
00617     GinNullCategory queryCategory;
00618     bool        isPartialMatch;
00619     Pointer     extra_data;
00620     StrategyNumber strategy;
00621     int32       searchMode;
00622     OffsetNumber attnum;
00623 
00624     /* Current page in posting tree */
00625     Buffer      buffer;
00626 
00627     /* current ItemPointer to heap */
00628     ItemPointerData curItem;
00629 
00630     /* for a partial-match or full-scan query, we accumulate all TIDs here */
00631     TIDBitmap  *matchBitmap;
00632     TBMIterator *matchIterator;
00633     TBMIterateResult *matchResult;
00634 
00635     /* used for Posting list and one page in Posting tree */
00636     ItemPointerData *list;
00637     uint32      nlist;
00638     OffsetNumber offset;
00639 
00640     bool        isFinished;
00641     bool        reduceResult;
00642     uint32      predictNumberResult;
00643 }   GinScanEntryData;
00644 
00645 typedef struct GinScanOpaqueData
00646 {
00647     MemoryContext tempCtx;
00648     GinState    ginstate;
00649 
00650     GinScanKey  keys;           /* one per scan qualifier expr */
00651     uint32      nkeys;
00652 
00653     GinScanEntry *entries;      /* one per index search condition */
00654     uint32      totalentries;
00655     uint32      allocentries;   /* allocated length of entries[] */
00656 
00657     bool        isVoidRes;      /* true if query is unsatisfiable */
00658 } GinScanOpaqueData;
00659 
00660 typedef GinScanOpaqueData *GinScanOpaque;
00661 
00662 extern Datum ginbeginscan(PG_FUNCTION_ARGS);
00663 extern Datum ginendscan(PG_FUNCTION_ARGS);
00664 extern Datum ginrescan(PG_FUNCTION_ARGS);
00665 extern Datum ginmarkpos(PG_FUNCTION_ARGS);
00666 extern Datum ginrestrpos(PG_FUNCTION_ARGS);
00667 extern void ginNewScanKey(IndexScanDesc scan);
00668 
00669 /* ginget.c */
00670 extern Datum gingetbitmap(PG_FUNCTION_ARGS);
00671 
00672 /* ginvacuum.c */
00673 extern Datum ginbulkdelete(PG_FUNCTION_ARGS);
00674 extern Datum ginvacuumcleanup(PG_FUNCTION_ARGS);
00675 
00676 /* ginbulk.c */
00677 typedef struct GinEntryAccumulator
00678 {
00679     RBNode      rbnode;
00680     Datum       key;
00681     GinNullCategory category;
00682     OffsetNumber attnum;
00683     bool        shouldSort;
00684     ItemPointerData *list;
00685     uint32      maxcount;       /* allocated size of list[] */
00686     uint32      count;          /* current number of list[] entries */
00687 } GinEntryAccumulator;
00688 
00689 typedef struct
00690 {
00691     GinState   *ginstate;
00692     long        allocatedMemory;
00693     GinEntryAccumulator *entryallocator;
00694     uint32      eas_used;
00695     RBTree     *tree;
00696 } BuildAccumulator;
00697 
00698 extern void ginInitBA(BuildAccumulator *accum);
00699 extern void ginInsertBAEntries(BuildAccumulator *accum,
00700                    ItemPointer heapptr, OffsetNumber attnum,
00701                    Datum *entries, GinNullCategory *categories,
00702                    int32 nentries);
00703 extern void ginBeginBAScan(BuildAccumulator *accum);
00704 extern ItemPointerData *ginGetBAEntry(BuildAccumulator *accum,
00705               OffsetNumber *attnum, Datum *key, GinNullCategory *category,
00706               uint32 *n);
00707 
00708 /* ginfast.c */
00709 
00710 typedef struct GinTupleCollector
00711 {
00712     IndexTuple *tuples;
00713     uint32      ntuples;
00714     uint32      lentuples;
00715     uint32      sumsize;
00716 } GinTupleCollector;
00717 
00718 extern void ginHeapTupleFastInsert(GinState *ginstate,
00719                        GinTupleCollector *collector);
00720 extern void ginHeapTupleFastCollect(GinState *ginstate,
00721                         GinTupleCollector *collector,
00722                         OffsetNumber attnum, Datum value, bool isNull,
00723                         ItemPointer ht_ctid);
00724 extern void ginInsertCleanup(GinState *ginstate,
00725                  bool vac_delay, IndexBulkDeleteResult *stats);
00726 
00727 #endif   /* GIN_PRIVATE_H */