1 /*-------------------------------------------------------------------------
4 * private declarations for GiST -- declarations related to the
5 * internal implementation of GiST, not the public API
7 * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
10 * src/include/access/gist_private.h
12 *-------------------------------------------------------------------------
14 #ifndef GIST_PRIVATE_H
15 #define GIST_PRIVATE_H
17 #include "access/amapi.h"
18 #include "access/gist.h"
19 #include "access/itup.h"
21 #include "lib/pairingheap.h"
22 #include "storage/bufmgr.h"
23 #include "storage/buffile.h"
24 #include "utils/hsearch.h"
25 #include "access/genam.h"
28 * Maximum number of "halves" a page can be split into in one operation.
29 * Typically a split produces 2 halves, but can be more if keys have very
30 * different lengths, or when inserting multiple keys in one operation (as
31 * when inserting downlinks to an internal node). There is no theoretical
32 * limit on this, but in practice if you get more than a handful page halves
33 * in one split, there's something wrong with the opclass implementation.
34 * GIST_MAX_SPLIT_PAGES is an arbitrary limit on that, used to size some
35 * local arrays used during split. Note that there is also a limit on the
36 * number of buffers that can be held locked at a time, MAX_SIMUL_LWLOCKS,
37 * so if you raise this higher than that limit, you'll just get a different
40 #define GIST_MAX_SPLIT_PAGES 75
42 /* Buffer lock modes */
43 #define GIST_SHARE BUFFER_LOCK_SHARE
44 #define GIST_EXCLUSIVE BUFFER_LOCK_EXCLUSIVE
45 #define GIST_UNLOCK BUFFER_LOCK_UNLOCK
51 char tupledata[FLEXIBLE_ARRAY_MEMBER];
54 #define BUFFER_PAGE_DATA_OFFSET MAXALIGN(offsetof(GISTNodeBufferPage, tupledata))
55 /* Returns free space in node buffer page */
56 #define PAGE_FREE_SPACE(nbp) (nbp->freespace)
57 /* Checks if node buffer page is empty */
58 #define PAGE_IS_EMPTY(nbp) (nbp->freespace == BLCKSZ - BUFFER_PAGE_DATA_OFFSET)
59 /* Checks if node buffers page don't contain sufficient space for index tuple */
60 #define PAGE_NO_SPACE(nbp, itup) (PAGE_FREE_SPACE(nbp) < \
61 MAXALIGN(IndexTupleSize(itup)))
64 * GISTSTATE: information needed for any GiST index operation
66 * This struct retains call info for the index's opclass-specific support
67 * functions (per index column), plus the index's tuple descriptor.
69 * scanCxt holds the GISTSTATE itself as well as any data that lives for the
70 * lifetime of the index operation. We pass this to the support functions
71 * via fn_mcxt, so that they can store scan-lifespan data in it. The
72 * functions are invoked in tempCxt, which is typically short-lifespan
73 * (that is, it's reset after each tuple). However, tempCxt can be the same
74 * as scanCxt if we're not bothering with per-tuple context resets.
76 typedef struct GISTSTATE
78 MemoryContext scanCxt; /* context for scan-lifespan data */
79 MemoryContext tempCxt; /* short-term context for calling functions */
81 TupleDesc tupdesc; /* index's tuple descriptor */
82 TupleDesc fetchTupdesc; /* tuple descriptor for tuples returned in an
85 FmgrInfo consistentFn[INDEX_MAX_KEYS];
86 FmgrInfo unionFn[INDEX_MAX_KEYS];
87 FmgrInfo compressFn[INDEX_MAX_KEYS];
88 FmgrInfo decompressFn[INDEX_MAX_KEYS];
89 FmgrInfo penaltyFn[INDEX_MAX_KEYS];
90 FmgrInfo picksplitFn[INDEX_MAX_KEYS];
91 FmgrInfo equalFn[INDEX_MAX_KEYS];
92 FmgrInfo distanceFn[INDEX_MAX_KEYS];
93 FmgrInfo fetchFn[INDEX_MAX_KEYS];
95 /* Collations to pass to the support functions */
96 Oid supportCollation[INDEX_MAX_KEYS];
101 * During a GiST index search, we must maintain a queue of unvisited items,
102 * which can be either individual heap tuples or whole index pages. If it
103 * is an ordered search, the unvisited items should be visited in distance
104 * order. Unvisited items at the same distance should be visited in
105 * depth-first order, that is heap items first, then lower index pages, then
106 * upper index pages; this rule avoids doing extra work during a search that
107 * ends early due to LIMIT.
109 * To perform an ordered search, we use a pairing heap to manage the
110 * distance-order queue. In a non-ordered search (no order-by operators),
111 * we use it to return heap tuples before unvisited index pages, to
112 * ensure depth-first order, but all entries are otherwise considered
116 /* Individual heap tuple to be visited */
117 typedef struct GISTSearchHeapItem
119 ItemPointerData heapPtr;
120 bool recheck; /* T if quals must be rechecked */
121 bool recheckDistances; /* T if distances must be rechecked */
122 IndexTuple ftup; /* data fetched back from the index, used in
123 * index-only scans */
124 OffsetNumber offnum; /* track offset in page to mark tuple as
126 } GISTSearchHeapItem;
128 /* Unvisited item, either index page or heap tuple */
129 typedef struct GISTSearchItem
131 pairingheap_node phNode;
132 BlockNumber blkno; /* index page number, or InvalidBlockNumber */
135 GistNSN parentlsn; /* parent page's LSN, if index page */
136 /* we must store parentlsn to detect whether a split occurred */
137 GISTSearchHeapItem heap; /* heap info, if heap tuple */
139 double distances[FLEXIBLE_ARRAY_MEMBER]; /* numberOfOrderBys
143 #define GISTSearchItemIsHeap(item) ((item).blkno == InvalidBlockNumber)
145 #define SizeOfGISTSearchItem(n_distances) (offsetof(GISTSearchItem, distances) + sizeof(double) * (n_distances))
148 * GISTScanOpaqueData: private state for a scan of a GiST index
150 typedef struct GISTScanOpaqueData
152 GISTSTATE *giststate; /* index information, see above */
153 Oid *orderByTypes; /* datatypes of ORDER BY expressions */
155 pairingheap *queue; /* queue of unvisited items */
156 MemoryContext queueCxt; /* context holding the queue */
157 bool qual_ok; /* false if qual can never be satisfied */
158 bool firstCall; /* true until first gistgettuple call */
160 /* pre-allocated workspace arrays */
161 double *distances; /* output area for gistindex_keytest */
163 /* info about killed items if any (killedItems is NULL if never used) */
164 OffsetNumber *killedItems; /* offset numbers of killed items */
165 int numKilled; /* number of currently stored items */
166 BlockNumber curBlkno; /* current number of block */
167 GistNSN curPageLSN; /* pos in the WAL stream when page was read */
169 /* In a non-ordered search, returnable heap items are stored here: */
170 GISTSearchHeapItem pageData[BLCKSZ / sizeof(IndexTupleData)];
171 OffsetNumber nPageData; /* number of valid items in array */
172 OffsetNumber curPageData; /* next item to return */
173 MemoryContext pageDataCxt; /* context holding the fetched tuples, for
174 * index-only scans */
175 } GISTScanOpaqueData;
177 typedef GISTScanOpaqueData *GISTScanOpaque;
179 /* despite the name, gistxlogPage is not part of any xlog record */
180 typedef struct gistxlogPage
183 int num; /* number of index tuples following */
186 /* SplitedPageLayout - gistSplit function result */
187 typedef struct SplitedPageLayout
190 IndexTupleData *list;
192 IndexTuple itup; /* union key for page */
193 Page page; /* to operate */
194 Buffer buffer; /* to write after all proceed */
196 struct SplitedPageLayout *next;
200 * GISTInsertStack used for locking buffers and transfer arguments during
203 typedef struct GISTInsertStack
211 * log sequence number from page->lsn to recognize page update and compare
212 * it with page's nsn to recognize page split
216 /* offset of the downlink in the parent page, that points to this page */
217 OffsetNumber downlinkoffnum;
219 /* pointer to parent */
220 struct GISTInsertStack *parent;
223 /* Working state and results for multi-column split logic in gistsplit.c */
224 typedef struct GistSplitVector
226 GIST_SPLITVEC splitVector; /* passed to/from user PickSplit method */
228 Datum spl_lattr[INDEX_MAX_KEYS]; /* Union of subkeys in
229 * splitVector.spl_left */
230 bool spl_lisnull[INDEX_MAX_KEYS];
232 Datum spl_rattr[INDEX_MAX_KEYS]; /* Union of subkeys in
233 * splitVector.spl_right */
234 bool spl_risnull[INDEX_MAX_KEYS];
236 bool *spl_dontcare; /* flags tuples which could go to either side
237 * of the split for zero penalty */
243 Size freespace; /* free space to be left */
245 GISTInsertStack *stack;
248 /* root page of a gist index */
249 #define GIST_ROOT_BLKNO 0
252 * Before PostgreSQL 9.1, we used to rely on so-called "invalid tuples" on
253 * inner pages to finish crash recovery of incomplete page splits. If a crash
254 * happened in the middle of a page split, so that the downlink pointers were
255 * not yet inserted, crash recovery inserted a special downlink pointer. The
256 * semantics of an invalid tuple was that it if you encounter one in a scan,
257 * it must always be followed, because we don't know if the tuples on the
258 * child page match or not.
260 * We no longer create such invalid tuples, we now mark the left-half of such
261 * an incomplete split with the F_FOLLOW_RIGHT flag instead, and finish the
262 * split properly the next time we need to insert on that page. To retain
263 * on-disk compatibility for the sake of pg_upgrade, we still store 0xffff as
264 * the offset number of all inner tuples. If we encounter any invalid tuples
265 * with 0xfffe during insertion, we throw an error, though scans still handle
266 * them. You should only encounter invalid tuples if you pg_upgrade a pre-9.1
267 * gist index which already has invalid tuples in it because of a crash. That
268 * should be rare, and you are recommended to REINDEX anyway if you have any
269 * invalid tuples in an index, so throwing an error is as far as we go with
272 #define TUPLE_IS_VALID 0xffff
273 #define TUPLE_IS_INVALID 0xfffe
275 #define GistTupleIsInvalid(itup) ( ItemPointerGetOffsetNumber( &((itup)->t_tid) ) == TUPLE_IS_INVALID )
276 #define GistTupleSetValid(itup) ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_VALID )
282 * A buffer attached to an internal node, used when building an index in
287 BlockNumber nodeBlocknum; /* index block # this buffer is for */
288 int32 blocksCount; /* current # of blocks occupied by buffer */
290 BlockNumber pageBlocknum; /* temporary file block # */
291 GISTNodeBufferPage *pageBuffer; /* in-memory buffer page */
293 /* is this buffer queued for emptying? */
294 bool queuedForEmptying;
296 /* is this a temporary copy, not in the hash table? */
299 int level; /* 0 == leaf */
303 * Does specified level have buffers? (Beware of multiple evaluation of
306 #define LEVEL_HAS_BUFFERS(nlevel, gfbb) \
307 ((nlevel) != 0 && (nlevel) % (gfbb)->levelStep == 0 && \
308 (nlevel) != (gfbb)->rootlevel)
310 /* Is specified buffer at least half-filled (should be queued for emptying)? */
311 #define BUFFER_HALF_FILLED(nodeBuffer, gfbb) \
312 ((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer / 2)
315 * Is specified buffer full? Our buffers can actually grow indefinitely,
316 * beyond the "maximum" size, so this just means whether the buffer has grown
317 * beyond the nominal maximum size.
319 #define BUFFER_OVERFLOWED(nodeBuffer, gfbb) \
320 ((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer)
323 * Data structure with general information about build buffers.
325 typedef struct GISTBuildBuffers
327 /* Persistent memory context for the buffers and metadata. */
328 MemoryContext context;
330 BufFile *pfile; /* Temporary file to store buffers in */
331 long nFileBlocks; /* Current size of the temporary file */
334 * resizable array of free blocks.
337 int nFreeBlocks; /* # of currently free blocks in the array */
338 int freeBlocksLen; /* current allocated length of the array */
340 /* Hash for buffers by block number */
341 HTAB *nodeBuffersTab;
343 /* List of buffers scheduled for emptying */
344 List *bufferEmptyingQueue;
347 * Parameters to the buffering build algorithm. levelStep determines which
348 * levels in the tree have buffers, and pagesPerBuffer determines how
349 * large each buffer is.
354 /* Array of lists of buffers on each level, for final emptying */
355 List **buffersOnLevels;
356 int buffersOnLevelsLen;
359 * Dynamically-sized array of buffers that currently have their last page
360 * loaded in main memory.
362 GISTNodeBuffer **loadedBuffers;
363 int loadedBuffersCount; /* # of entries in loadedBuffers */
364 int loadedBuffersLen; /* allocated size of loadedBuffers */
366 /* Level of the current root node (= height of the index tree - 1) */
371 * Storage type for GiST's reloptions
373 typedef struct GiSTOptions
375 int32 vl_len_; /* varlena header (do not touch directly!) */
376 int fillfactor; /* page fill factor in percent (0..100) */
377 int bufferingModeOffset; /* use buffering build? */
381 extern void gistbuildempty(Relation index);
382 extern bool gistinsert(Relation r, Datum *values, bool *isnull,
383 ItemPointer ht_ctid, Relation heapRel,
384 IndexUniqueCheck checkUnique,
385 struct IndexInfo *indexInfo);
386 extern MemoryContext createTempGistContext(void);
387 extern GISTSTATE *initGISTstate(Relation index);
388 extern void freeGISTstate(GISTSTATE *giststate);
389 extern void gistdoinsert(Relation r,
392 GISTSTATE *GISTstate);
394 /* A List of these is returned from gistplacetopage() in *splitinfo */
397 Buffer buf; /* the split page "half" */
398 IndexTuple downlink; /* downlink for this half. */
401 extern bool gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
403 IndexTuple *itup, int ntup,
404 OffsetNumber oldoffnum, BlockNumber *newblkno,
409 extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,
410 int len, GISTSTATE *giststate);
412 extern XLogRecPtr gistXLogUpdate(Buffer buffer,
413 OffsetNumber *todelete, int ntodelete,
414 IndexTuple *itup, int ntup,
417 extern XLogRecPtr gistXLogSplit(bool page_is_leaf,
418 SplitedPageLayout *dist,
419 BlockNumber origrlink, GistNSN oldnsn,
420 Buffer leftchild, bool markfollowright);
423 extern bool gistgettuple(IndexScanDesc scan, ScanDirection dir);
424 extern int64 gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
425 extern bool gistcanreturn(Relation index, int attno);
428 extern bool gistvalidate(Oid opclassoid);
432 #define GiSTPageSize \
433 ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GISTPageOpaqueData)) )
435 #define GIST_MIN_FILLFACTOR 10
436 #define GIST_DEFAULT_FILLFACTOR 90
438 extern bytea *gistoptions(Datum reloptions, bool validate);
439 extern bool gistproperty(Oid index_oid, int attno,
440 IndexAMProperty prop, const char *propname,
441 bool *res, bool *isnull);
442 extern bool gistfitpage(IndexTuple *itvec, int len);
443 extern bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace);
444 extern void gistcheckpage(Relation rel, Buffer buf);
445 extern Buffer gistNewBuffer(Relation r);
446 extern void gistfillbuffer(Page page, IndexTuple *itup, int len,
448 extern IndexTuple *gistextractpage(Page page, int *len /* out */ );
449 extern IndexTuple *gistjoinvector(
450 IndexTuple *itvec, int *len,
451 IndexTuple *additvec, int addlen);
452 extern IndexTupleData *gistfillitupvec(IndexTuple *vec, int veclen, int *memlen);
454 extern IndexTuple gistunion(Relation r, IndexTuple *itvec,
455 int len, GISTSTATE *giststate);
456 extern IndexTuple gistgetadjusted(Relation r,
459 GISTSTATE *giststate);
460 extern IndexTuple gistFormTuple(GISTSTATE *giststate,
461 Relation r, Datum *attdata, bool *isnull, bool isleaf);
463 extern OffsetNumber gistchoose(Relation r, Page p,
465 GISTSTATE *giststate);
467 extern void GISTInitBuffer(Buffer b, uint32 f);
468 extern void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
469 Datum k, Relation r, Page pg, OffsetNumber o,
470 bool l, bool isNull);
472 extern float gistpenalty(GISTSTATE *giststate, int attno,
473 GISTENTRY *key1, bool isNull1,
474 GISTENTRY *key2, bool isNull2);
475 extern void gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len,
476 Datum *attr, bool *isnull);
477 extern bool gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b);
478 extern void gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,
479 OffsetNumber o, GISTENTRY *attdata, bool *isnull);
480 extern IndexTuple gistFetchTuple(GISTSTATE *giststate, Relation r,
482 extern void gistMakeUnionKey(GISTSTATE *giststate, int attno,
483 GISTENTRY *entry1, bool isnull1,
484 GISTENTRY *entry2, bool isnull2,
485 Datum *dst, bool *dstisnull);
487 extern XLogRecPtr gistGetFakeLSN(Relation rel);
490 extern IndexBulkDeleteResult *gistbulkdelete(IndexVacuumInfo *info,
491 IndexBulkDeleteResult *stats,
492 IndexBulkDeleteCallback callback,
493 void *callback_state);
494 extern IndexBulkDeleteResult *gistvacuumcleanup(IndexVacuumInfo *info,
495 IndexBulkDeleteResult *stats);
498 extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,
499 int len, GISTSTATE *giststate,
504 extern IndexBuildResult *gistbuild(Relation heap, Relation index,
505 struct IndexInfo *indexInfo);
506 extern void gistValidateBufferingOption(char *value);
508 /* gistbuildbuffers.c */
509 extern GISTBuildBuffers *gistInitBuildBuffers(int pagesPerBuffer, int levelStep,
511 extern GISTNodeBuffer *gistGetNodeBuffer(GISTBuildBuffers *gfbb,
512 GISTSTATE *giststate,
513 BlockNumber blkno, int level);
514 extern void gistPushItupToNodeBuffer(GISTBuildBuffers *gfbb,
515 GISTNodeBuffer *nodeBuffer, IndexTuple item);
516 extern bool gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb,
517 GISTNodeBuffer *nodeBuffer, IndexTuple *item);
518 extern void gistFreeBuildBuffers(GISTBuildBuffers *gfbb);
519 extern void gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb,
520 GISTSTATE *giststate, Relation r,
521 int level, Buffer buffer,
523 extern void gistUnloadNodeBuffers(GISTBuildBuffers *gfbb);
525 #endif /* GIST_PRIVATE_H */