* private declarations for GiST -- declarations related to the
* internal implementation of GiST, not the public API
*
- * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
* src/include/access/gist_private.h
#ifndef GIST_PRIVATE_H
#define GIST_PRIVATE_H
+#include "access/amapi.h"
#include "access/gist.h"
#include "access/itup.h"
#include "fmgr.h"
+#include "lib/pairingheap.h"
#include "storage/bufmgr.h"
#include "storage/buffile.h"
-#include "utils/rbtree.h"
#include "utils/hsearch.h"
+#include "access/genam.h"
/*
* Maximum number of "halves" a page can be split into in one operation.
{
BlockNumber prev;
uint32 freespace;
- char tupledata[1];
+ char tupledata[FLEXIBLE_ARRAY_MEMBER];
} GISTNodeBufferPage;
#define BUFFER_PAGE_DATA_OFFSET MAXALIGN(offsetof(GISTNodeBufferPage, tupledata))
MemoryContext tempCxt; /* short-term context for calling functions */
TupleDesc tupdesc; /* index's tuple descriptor */
+ TupleDesc fetchTupdesc; /* tuple descriptor for tuples returned in an
+ * index-only scan */
FmgrInfo consistentFn[INDEX_MAX_KEYS];
FmgrInfo unionFn[INDEX_MAX_KEYS];
FmgrInfo picksplitFn[INDEX_MAX_KEYS];
FmgrInfo equalFn[INDEX_MAX_KEYS];
FmgrInfo distanceFn[INDEX_MAX_KEYS];
+ FmgrInfo fetchFn[INDEX_MAX_KEYS];
/* Collations to pass to the support functions */
Oid supportCollation[INDEX_MAX_KEYS];
* upper index pages; this rule avoids doing extra work during a search that
* ends early due to LIMIT.
*
- * To perform an ordered search, we use an RBTree to manage the distance-order
- * queue. Each GISTSearchTreeItem stores all unvisited items of the same
- * distance; they are GISTSearchItems chained together via their next fields.
- *
- * In a non-ordered search (no order-by operators), the RBTree degenerates
- * to a single item, which we use as a queue of unvisited index pages only.
- * In this case matched heap items from the current index leaf page are
- * remembered in GISTScanOpaqueData.pageData[] and returned directly from
- * there, instead of building a separate GISTSearchItem for each one.
+ * To perform an ordered search, we use a pairing heap to manage the
+ * distance-order queue. In a non-ordered search (no order-by operators),
+ * we use it to return heap tuples before unvisited index pages, to
+ * ensure depth-first order, but all entries are otherwise considered
+ * equal.
*/
/* Individual heap tuple to be visited */
{
ItemPointerData heapPtr;
bool recheck; /* T if quals must be rechecked */
+ bool recheckDistances; /* T if distances must be rechecked */
+ HeapTuple recontup; /* data reconstructed from the index, used in
+ * index-only scans */
+ OffsetNumber offnum; /* track offset in page to mark tuple as
+ * LP_DEAD */
} GISTSearchHeapItem;
/* Unvisited item, either index page or heap tuple */
typedef struct GISTSearchItem
{
- struct GISTSearchItem *next; /* list link */
+ pairingheap_node phNode;
BlockNumber blkno; /* index page number, or InvalidBlockNumber */
union
{
/* we must store parentlsn to detect whether a split occurred */
GISTSearchHeapItem heap; /* heap info, if heap tuple */
} data;
+ double distances[FLEXIBLE_ARRAY_MEMBER]; /* numberOfOrderBys
+ * entries */
} GISTSearchItem;
#define GISTSearchItemIsHeap(item) ((item).blkno == InvalidBlockNumber)
-/*
- * Within a GISTSearchTreeItem's chain, heap items always appear before
- * index-page items, since we want to visit heap items first. lastHeap points
- * to the last heap item in the chain, or is NULL if there are none.
- */
-typedef struct GISTSearchTreeItem
-{
- RBNode rbnode; /* this is an RBTree item */
- GISTSearchItem *head; /* first chain member */
- GISTSearchItem *lastHeap; /* last heap-tuple member, if any */
- double distances[1]; /* array with numberOfOrderBys entries */
-} GISTSearchTreeItem;
-
-#define GSTIHDRSZ offsetof(GISTSearchTreeItem, distances)
+#define SizeOfGISTSearchItem(n_distances) (offsetof(GISTSearchItem, distances) + sizeof(double) * (n_distances))
/*
* GISTScanOpaqueData: private state for a scan of a GiST index
typedef struct GISTScanOpaqueData
{
GISTSTATE *giststate; /* index information, see above */
- RBTree *queue; /* queue of unvisited items */
+ Oid *orderByTypes; /* datatypes of ORDER BY expressions */
+
+ pairingheap *queue; /* queue of unvisited items */
MemoryContext queueCxt; /* context holding the queue */
bool qual_ok; /* false if qual can never be satisfied */
bool firstCall; /* true until first gistgettuple call */
- GISTSearchTreeItem *curTreeItem; /* current queue item, if any */
-
/* pre-allocated workspace arrays */
- GISTSearchTreeItem *tmpTreeItem; /* workspace to pass to rb_insert */
double *distances; /* output area for gistindex_keytest */
+ /* info about killed items if any (killedItems is NULL if never used) */
+ OffsetNumber *killedItems; /* offset numbers of killed items */
+ int numKilled; /* number of currently stored items */
+ BlockNumber curBlkno; /* current number of block */
+ GistNSN curPageLSN; /* pos in the WAL stream when page was read */
+
/* In a non-ordered search, returnable heap items are stored here: */
GISTSearchHeapItem pageData[BLCKSZ / sizeof(IndexTupleData)];
OffsetNumber nPageData; /* number of valid items in array */
OffsetNumber curPageData; /* next item to return */
+ MemoryContext pageDataCxt; /* context holding the fetched tuples, for
+ * index-only scans */
} GISTScanOpaqueData;
typedef GISTScanOpaqueData *GISTScanOpaque;
-
-/* XLog stuff */
-
-#define XLOG_GIST_PAGE_UPDATE 0x00
- /* #define XLOG_GIST_NEW_ROOT 0x20 */ /* not used anymore */
-#define XLOG_GIST_PAGE_SPLIT 0x30
- /* #define XLOG_GIST_INSERT_COMPLETE 0x40 */ /* not used anymore */
-#define XLOG_GIST_CREATE_INDEX 0x50
- /* #define XLOG_GIST_PAGE_DELETE 0x60 */ /* not used anymore */
-
-typedef struct gistxlogPageUpdate
-{
- RelFileNode node;
- BlockNumber blkno;
-
- /*
- * If this operation completes a page split, by inserting a downlink for
- * the split page, leftchild points to the left half of the split.
- */
- BlockNumber leftchild;
-
- /* number of deleted offsets */
- uint16 ntodelete;
-
- /*
- * follow: 1. todelete OffsetNumbers 2. tuples to insert
- */
-} gistxlogPageUpdate;
-
-typedef struct gistxlogPageSplit
-{
- RelFileNode node;
- BlockNumber origblkno; /* splitted page */
- BlockNumber origrlink; /* rightlink of the page before split */
- GistNSN orignsn; /* NSN of the page before split */
- bool origleaf; /* was splitted page a leaf page? */
-
- BlockNumber leftchild; /* like in gistxlogPageUpdate */
- uint16 npage; /* # of pages in the split */
- bool markfollowright; /* set F_FOLLOW_RIGHT flags */
-
- /*
- * follow: 1. gistxlogPage and array of IndexTupleData per page
- */
-} gistxlogPageSplit;
-
+/* despite the name, gistxlogPage is not part of any xlog record */
typedef struct gistxlogPage
{
BlockNumber blkno;
#define GIST_ROOT_BLKNO 0
/*
- * Before PostgreSQL 9.1, we used rely on so-called "invalid tuples" on inner
- * pages to finish crash recovery of incomplete page splits. If a crash
+ * Before PostgreSQL 9.1, we used to rely on so-called "invalid tuples" on
+ * inner pages to finish crash recovery of incomplete page splits. If a crash
* happened in the middle of a page split, so that the downlink pointers were
* not yet inserted, crash recovery inserted a special downlink pointer. The
* semantics of an invalid tuple was that it if you encounter one in a scan,
} GiSTOptions;
/* gist.c */
-extern Datum gistbuildempty(PG_FUNCTION_ARGS);
-extern Datum gistinsert(PG_FUNCTION_ARGS);
+extern void gistbuildempty(Relation index);
+extern bool gistinsert(Relation r, Datum *values, bool *isnull,
+ ItemPointer ht_ctid, Relation heapRel,
+ IndexUniqueCheck checkUnique,
+ struct IndexInfo *indexInfo);
extern MemoryContext createTempGistContext(void);
extern GISTSTATE *initGISTstate(Relation index);
extern void freeGISTstate(GISTSTATE *giststate);
extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,
int len, GISTSTATE *giststate);
-/* gistxlog.c */
-extern void gist_redo(XLogRecPtr lsn, XLogRecord *record);
-extern void gist_desc(StringInfo buf, XLogRecord *record);
-extern const char *gist_identify(uint8 info);
-extern void gist_xlog_startup(void);
-extern void gist_xlog_cleanup(void);
-
-extern XLogRecPtr gistXLogUpdate(RelFileNode node, Buffer buffer,
+extern XLogRecPtr gistXLogUpdate(Buffer buffer,
OffsetNumber *todelete, int ntodelete,
IndexTuple *itup, int ntup,
Buffer leftchild);
-extern XLogRecPtr gistXLogSplit(RelFileNode node,
- BlockNumber blkno, bool page_is_leaf,
+extern XLogRecPtr gistXLogSplit(bool page_is_leaf,
SplitedPageLayout *dist,
BlockNumber origrlink, GistNSN oldnsn,
Buffer leftchild, bool markfollowright);
/* gistget.c */
-extern Datum gistgettuple(PG_FUNCTION_ARGS);
-extern Datum gistgetbitmap(PG_FUNCTION_ARGS);
+extern bool gistgettuple(IndexScanDesc scan, ScanDirection dir);
+extern int64 gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
+extern bool gistcanreturn(Relation index, int attno);
+
+/* gistvalidate.c */
+extern bool gistvalidate(Oid opclassoid);
/* gistutil.c */
#define GIST_MIN_FILLFACTOR 10
#define GIST_DEFAULT_FILLFACTOR 90
-extern Datum gistoptions(PG_FUNCTION_ARGS);
+extern bytea *gistoptions(Datum reloptions, bool validate);
+extern bool gistproperty(Oid index_oid, int attno,
+ IndexAMProperty prop, const char *propname,
+ bool *res, bool *isnull);
extern bool gistfitpage(IndexTuple *itvec, int len);
extern bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace);
extern void gistcheckpage(Relation rel, Buffer buf);
IndexTuple addtup,
GISTSTATE *giststate);
extern IndexTuple gistFormTuple(GISTSTATE *giststate,
- Relation r, Datum *attdata, bool *isnull, bool newValues);
+ Relation r, Datum *attdata, bool *isnull, bool isleaf);
extern OffsetNumber gistchoose(Relation r, Page p,
IndexTuple it,
GISTSTATE *giststate);
-extern void gistcentryinit(GISTSTATE *giststate, int nkey,
- GISTENTRY *e, Datum k,
- Relation r, Page pg,
- OffsetNumber o, bool l, bool isNull);
extern void GISTInitBuffer(Buffer b, uint32 f);
extern void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
extern bool gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b);
extern void gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,
OffsetNumber o, GISTENTRY *attdata, bool *isnull);
-
+extern HeapTuple gistFetchTuple(GISTSTATE *giststate, Relation r,
+ IndexTuple tuple);
extern void gistMakeUnionKey(GISTSTATE *giststate, int attno,
GISTENTRY *entry1, bool isnull1,
GISTENTRY *entry2, bool isnull2,
extern XLogRecPtr gistGetFakeLSN(Relation rel);
/* gistvacuum.c */
-extern Datum gistbulkdelete(PG_FUNCTION_ARGS);
-extern Datum gistvacuumcleanup(PG_FUNCTION_ARGS);
+extern IndexBulkDeleteResult *gistbulkdelete(IndexVacuumInfo *info,
+ IndexBulkDeleteResult *stats,
+ IndexBulkDeleteCallback callback,
+ void *callback_state);
+extern IndexBulkDeleteResult *gistvacuumcleanup(IndexVacuumInfo *info,
+ IndexBulkDeleteResult *stats);
/* gistsplit.c */
extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,
int attno);
/* gistbuild.c */
-extern Datum gistbuild(PG_FUNCTION_ARGS);
+extern IndexBuildResult *gistbuild(Relation heap, Relation index,
+ struct IndexInfo *indexInfo);
extern void gistValidateBufferingOption(char *value);
/* gistbuildbuffers.c */
projects / postgresql / blobdiff