1/*-------------------------------------------------------------------------
4 * fetch tuples from a GiST scan.
7 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
11 * src/backend/access/gist/gistget.c
13 *-------------------------------------------------------------------------
29 * gistkillitems() -- set LP_DEAD state for items an indexscan caller has
30 * told us were killed.
32 * We re-read page here, so it's important to check page LSN. If the page
33 * has been modified since the last read (as determined by LSN), we cannot
34 * flag any entries because it is possible that the old entry was vacuumed
35 * away and the TID was re-used by a completely different heap tuple.
46 bool killedsomething =
false;
61 * If page LSN differs it means that the page was modified since the last
62 * read. killedItems could be not valid so LP_DEAD hints applying is not
75 * Mark all killedItems as dead. We need no additional recheck, because,
76 * if page was modified, curPageLSN must have changed.
83 killedsomething =
true;
95 * Always reset the scan state, so we don't look for same items on other
102 * gistindex_keytest() -- does this index tuple satisfy the scan key(s)?
104 * The index tuple might represent either a heap tuple or a lower index page,
105 * depending on whether the containing page is a leaf page or not.
107 * On success return for a heap tuple, *recheck_p is set to indicate whether
108 * the quals need to be rechecked. We recheck if any of the consistent()
109 * functions request it. recheck is not interesting when examining a non-leaf
110 * entry, since we must visit the lower index page if there's any doubt.
111 * Similarly, *recheck_distances_p is set to indicate whether the distances
112 * need to be rechecked, and it is also ignored for non-leaf entries.
114 * If we are doing an ordered scan, so->distances[] is filled with distance
115 * data from the distance() functions before returning success.
117 * We must decompress the key in the IndexTuple before passing it to the
118 * sk_funcs (which actually are the opclass Consistent or Distance methods).
120 * Note that this function is always invoked in a short-lived memory context,
121 * so we don't need to worry about cleaning up allocated memory, either here
122 * or in the implementation of any Consistent or Distance methods.
130 bool *recheck_distances_p)
140 *recheck_distances_p =
false;
143 * If it's a leftover invalid tuple from pre-9.1, treat it as a match with
144 * minimum possible distances. This means we'll always follow it to the
152 elog(
ERROR,
"invalid GiST tuple found on leaf page");
161 /* Check whether it matches according to the Consistent functions */
169 giststate->leafTupdesc,
175 * On non-leaf page we can't conclude that child hasn't NULL
176 * values because of assumption in GiST: union (VAL, NULL) is VAL.
177 * But if on non-leaf page key IS NULL, then all children are
203 datum, r, page, offset,
207 * Call the Consistent function to evaluate the test. The
208 * arguments are the index datum (as a GISTENTRY*), the comparison
209 * datum, the comparison operator's strategy number and subtype
210 * from pg_amop, and the recheck flag.
212 * (Presently there's no need to pass the subtype since it'll
213 * always be zero, but might as well pass it for possible future
216 * We initialize the recheck flag to true (the safest assumption)
217 * in case the Consistent function forgets to set it.
231 *recheck_p |= recheck;
238 /* OK, it passes --- now let's compute the distances */
249 giststate->leafTupdesc,
254 /* Assume distance computes as null */
255 distance_p->value = 0.0;
256 distance_p->isnull =
true;
265 datum, r, page, offset,
269 * Call the Distance function to evaluate the distance. The
270 * arguments are the index datum (as a GISTENTRY*), the comparison
271 * datum, the ordering operator's strategy number and subtype from
272 * pg_amop, and the recheck flag.
274 * (Presently there's no need to pass the subtype since it'll
275 * always be zero, but might as well pass it for possible future
278 * If the function sets the recheck flag, the returned distance is
279 * a lower bound on the true distance and needs to be rechecked.
280 * We initialize the flag to 'false'. This flag was added in
281 * version 9.5; distance functions written before that won't know
282 * about the flag, but are expected to never be lossy.
292 *recheck_distances_p |= recheck;
294 distance_p->isnull =
false;
306 * Scan all items on the GiST index page identified by *pageItem, and insert
307 * them into the queue (or directly to output areas)
309 * scan: index scan we are executing
310 * pageItem: search queue item identifying an index page to scan
311 * myDistances: distances array associated with pageItem, or NULL at the root
312 * tbm: if not NULL, gistgetbitmap's output bitmap
313 * ntids: if not NULL, gistgetbitmap's output tuple counter
315 * If tbm/ntids aren't NULL, we are doing an amgetbitmap scan, and heap
316 * tuples should be reported directly into the bitmap. If they are NULL,
317 * we're doing a plain or ordered indexscan. For a plain indexscan, heap
318 * tuple TIDs are returned into so->pageData[]. For an ordered indexscan,
319 * heap tuple TIDs are pushed into individual search queue items. In an
320 * index-only scan, reconstructed index tuples are returned along with the
323 * If we detect that the index page has split since we saw its downlink
324 * in the parent, we push its new right sibling onto the queue so the
325 * sibling will be processed next.
351 * Check if we need to follow the rightlink. We need to follow it if the
352 * page was concurrently split since we visited the parent (in which case
353 * parentlsn < nsn), or if the system crashed after a page split but
354 * before the downlink was inserted into the parent.
361 /* There was a page split, follow right link to add pages */
364 /* This can't happen when starting at the root */
365 Assert(myDistances != NULL);
369 /* Create new GISTSearchItem for the right sibling index page */
371 item->
blkno = opaque->rightlink;
374 /* Insert it into the queue using same distances as for this page */
384 * Check if the page was deleted after we saw the downlink. There's
385 * nothing of interest on a deleted page. Note that we must do this after
386 * checking the NSN for concurrent splits! It's possible that the page
387 * originally contained some tuples that are visible to us, but was split
388 * so that all the visible tuples were moved to another page, and then
389 * this page was deleted.
398 scan->
xs_hitup = NULL;
/* might point into pageDataCxt */
403 * We save the LSN of the page as we read it, so that we know whether it
404 * safe to apply LP_DEAD hints to the page later. This allows us to drop
405 * the pin for MVCC scans, which allows vacuum to avoid blocking.
410 * check all tuples on page
419 bool recheck_distances;
422 * If the scan specifies not to return killed tuples, then we treat a
423 * killed tuple as not passing the qual.
431 * Must call gistindex_keytest in tempCxt, and clean up any leftover
437 &recheck, &recheck_distances);
442 /* Ignore tuple if it doesn't match */
449 * getbitmap scan, so just push heap tuple TIDs into the bitmap
450 * without worrying about ordering
458 * Non-ordered scan, so report tuples in so->pageData[]
465 * In an index-only scan, also fetch the data from the tuple. The
466 * reconstructed tuples are stored in pageDataCxt.
480 * Must push item into search queue. We get here for any lower
481 * index page, and also for heap tuples if doing an ordered
489 /* Create new GISTSearchItem for this item */
494 /* Creating heap-tuple GISTSearchItem */
501 * In an index-only scan, also fetch the data from the tuple.
508 /* Creating index-page GISTSearchItem */
512 * LSN of current page is lsn of parent page for child. We
513 * only have a shared lock, so we need to get the LSN
519 /* Insert it into the queue using new distance data */
533 * Extract next item (in order) from search queue
535 * Returns a GISTSearchItem or NULL. Caller must pfree item when done with it.
548 /* Done when both heaps are empty */
552 /* Return item; caller is responsible to pfree it */
557 * Fetch next heap tuple in an ordered search
567 /* free previously returned tuple */
581 /* found a heap item at currently minimal distance */
589 /* in an index-only scan, also return the reconstructed tuple. */
596 /* visit an index page, extract its items into queue */
609 * gistgettuple() -- Get the next tuple in the scan
617 elog(
ERROR,
"GiST only supports forward scan direction");
624 /* Begin the scan by processing the root page */
644 /* Must fetch tuples in strict distance order */
649 /* Fetch tuples index-page-at-a-time */
672 /* continuing to return tuples from a leaf page */
676 /* in an index-only scan, also return the reconstructed tuple */
686 * Check the last returned tuple and add it to killedItems if
709 /* find and process the next index page */
724 /* save current item BlockNumber for next gistkillitems() call */
728 * While scanning a leaf page, ItemPointers of matching heap
729 * tuples are stored in so->pageData. If there are any on
730 * this page, we fall out of the inner "do" and loop around to
742 * gistgetbitmap() -- Get a bitmap of all heap tuple locations
758 /* Begin the scan by processing the root page */
765 memset(&fakeItem.data.parentlsn, 0,
sizeof(
GistNSN));
769 * While scanning a leaf page, ItemPointers of matching heap tuples will
770 * be stored directly into tbm, so we don't need to deal with them here.
790 * Can we do index-only scans on the given index column?
792 * Opclasses that implement a fetch function support index-only scans.
793 * Opclasses without compression functions also support index-only scans.
794 * Included attributes always can be fetched for index-only scans.
#define InvalidBlockNumber
BlockNumber BufferGetBlockNumber(Buffer buffer)
XLogRecPtr BufferGetLSNAtomic(Buffer buffer)
void UnlockReleaseBuffer(Buffer buffer)
void LockBuffer(Buffer buffer, int mode)
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
static Page BufferGetPage(Buffer buffer)
static bool BufferIsValid(Buffer bufnum)
static Item PageGetItem(const PageData *page, const ItemIdData *itemId)
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
#define OidIsValid(objectId)
static float8 get_float8_infinity(void)
Datum FunctionCall5Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2, Datum arg3, Datum arg4, Datum arg5)
#define GIST_COMPRESS_PROC
#define GistPageIsLeaf(page)
#define GistFollowRight(page)
#define GistPageIsDeleted(page)
#define GistPageGetOpaque(page)
#define GistMarkPageHasGarbage(page)
#define GistPageGetNSN(page)
GISTScanOpaqueData * GISTScanOpaque
#define SizeOfGISTSearchItem(n_distances)
#define GistTupleIsInvalid(itup)
#define GISTSearchItemIsHeap(item)
static bool getNextNearest(IndexScanDesc scan)
static GISTSearchItem * getNextGISTSearchItem(GISTScanOpaque so)
static bool gistindex_keytest(IndexScanDesc scan, IndexTuple tuple, Page page, OffsetNumber offset, bool *recheck_p, bool *recheck_distances_p)
bool gistgettuple(IndexScanDesc scan, ScanDirection dir)
int64 gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
bool gistcanreturn(Relation index, int attno)
static void gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, IndexOrderByDistance *myDistances, TIDBitmap *tbm, int64 *ntids)
static void gistkillitems(IndexScanDesc scan)
HeapTuple gistFetchTuple(GISTSTATE *giststate, Relation r, IndexTuple tuple)
void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e, Datum k, Relation r, Page pg, OffsetNumber o, bool l, bool isNull)
void gistcheckpage(Relation rel, Buffer buf)
Assert(PointerIsAligned(start, uint64))
RegProcedure index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
void index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes, IndexOrderByDistance *distances, bool recheckOrderBy)
if(TABLE==NULL||TABLE_index==NULL)
#define ItemIdMarkDead(itemId)
#define ItemIdIsDead(itemId)
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
IndexTupleData * IndexTuple
static Datum index_getattr(IndexTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
#define MaxIndexTuplesPerPage
void MemoryContextReset(MemoryContext context)
void pfree(void *pointer)
#define CHECK_FOR_INTERRUPTS()
#define OffsetNumberNext(offsetNumber)
#define FirstOffsetNumber
void pairingheap_add(pairingheap *heap, pairingheap_node *node)
pairingheap_node * pairingheap_remove_first(pairingheap *heap)
#define pairingheap_is_empty(h)
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
#define pgstat_count_index_scan(rel)
static bool DatumGetBool(Datum X)
static Datum PointerGetDatum(const void *X)
static Datum Int16GetDatum(int16 X)
static float8 DatumGetFloat8(Datum X)
static Datum ObjectIdGetDatum(Oid X)
void PredicateLockPage(Relation relation, BlockNumber blkno, Snapshot snapshot)
#define IndexRelationGetNumberOfKeyAttributes(relation)
OffsetNumber * killedItems
GISTSearchHeapItem pageData[BLCKSZ/sizeof(IndexTupleData)]
IndexOrderByDistance * distances
MemoryContext pageDataCxt
IndexOrderByDistance distances[FLEXIBLE_ARRAY_MEMBER]
union GISTSearchItem::@47 data
struct ScanKeyData * keyData
struct ScanKeyData * orderByData
bool ignore_killed_tuples
struct IndexScanInstrumentation * instrument
ItemPointerData xs_heaptid
struct SnapshotData * xs_snapshot
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
#define XLogRecPtrIsInvalid(r)