#include "postgres.h"
#include "access/gin_private.h"
#include "access/relscan.h"
#include "common/pg_prng.h"
#include "miscadmin.h"
#include "storage/predicate.h"
#include "utils/datum.h"
#include "utils/memutils.h"
#include "utils/rel.h"

Include dependency graph for ginget.c:

Data Structures
struct	pendingPosition

Macros
#define	gin_rand() pg_prng_double(&pg_global_prng_state)

#define	dropItem(e) ( gin_rand() > ((double)GinFuzzySearchLimit)/((double)((e)->predictNumberResult)) )

#define	GinIsVoidRes(s) ( ((GinScanOpaque) scan->opaque)->isVoidRes )

Typedefs
typedef struct pendingPosition	pendingPosition

Functions
static bool	moveRightIfItNeeded (GinBtreeData btree, GinBtreeStack stack, Snapshot snapshot)

static void	scanPostingTree (Relation index, GinScanEntry scanEntry, BlockNumber rootPostingTree, Snapshot snapshot)

static bool	collectMatchBitmap (GinBtreeData btree, GinBtreeStack stack, GinScanEntry scanEntry, Snapshot snapshot)

static void	startScanEntry (GinState *ginstate, GinScanEntry entry, Snapshot snapshot)

static int	entryIndexByFrequencyCmp (const void a1, const void a2, void *arg)

static void	startScanKey (GinState *ginstate, GinScanOpaque so, GinScanKey key)

static void	startScan (IndexScanDesc scan)

static void	entryLoadMoreItems (GinState *ginstate, GinScanEntry entry, ItemPointerData advancePast, Snapshot snapshot)

static void	entryGetItem (GinState *ginstate, GinScanEntry entry, ItemPointerData advancePast, Snapshot snapshot)

static void	keyGetItem (GinState *ginstate, MemoryContext tempCtx, GinScanKey key, ItemPointerData advancePast, Snapshot snapshot)

static bool	scanGetItem (IndexScanDesc scan, ItemPointerData advancePast, ItemPointerData item, bool recheck)

static bool	scanGetCandidate (IndexScanDesc scan, pendingPosition *pos)

static bool	matchPartialInPendingList (GinState ginstate, Page page, OffsetNumber off, OffsetNumber maxoff, GinScanEntry entry, Datum datum, GinNullCategory category, bool datumExtracted)

static bool	collectMatchesForHeapRow (IndexScanDesc scan, pendingPosition *pos)

static void	scanPendingInsert (IndexScanDesc scan, TIDBitmap tbm, int64 ntids)

int64	gingetbitmap (IndexScanDesc scan, TIDBitmap *tbm)

Variables
int	GinFuzzySearchLimit = 0

Macro Definition Documentation

◆ dropItem

#define dropItem ( e ) ( gin_rand() > ((double)GinFuzzySearchLimit)/((double)((e)->predictNumberResult)) )

Definition at line 792 of file ginget.c.

◆ gin_rand

#define gin_rand ( ) pg_prng_double(&pg_global_prng_state)

Definition at line 791 of file ginget.c.

◆ GinIsVoidRes

#define GinIsVoidRes ( s ) ( ((GinScanOpaque) scan->opaque)->isVoidRes )

Definition at line 1915 of file ginget.c.

Typedef Documentation

◆ pendingPosition

typedef struct pendingPosition pendingPosition

Function Documentation

◆ collectMatchBitmap()

static bool collectMatchBitmap	(	GinBtreeData *	btree,
		GinBtreeStack *	stack,
		GinScanEntry	scanEntry,
		Snapshot	snapshot
	)

static

Definition at line 121 of file ginget.c.

 {
     OffsetNumber attnum;
     Form_pg_attribute attr;
  
     /* Initialize empty bitmap result */
     scanEntry->matchBitmap = tbm_create(work_mem * 1024L, NULL);
  
     /* Null query cannot partial-match anything */
     if (scanEntry->isPartialMatch &&
         scanEntry->queryCategory != GIN_CAT_NORM_KEY)
         return true;
  
     /* Locate tupdesc entry for key column (for attbyval/attlen data) */
     attnum = scanEntry->attnum;
     attr = TupleDescAttr(btree->ginstate->origTupdesc, attnum - 1);
  
     /*
      * Predicate lock entry leaf page, following pages will be locked by
      * moveRightIfItNeeded()
      */
     PredicateLockPage(btree->index, stack->buffer, snapshot);
  
     for (;;)
     {
         Page        page;
         IndexTuple  itup;
         Datum       idatum;
         GinNullCategory icategory;
  
         /*
          * stack->off points to the interested entry, buffer is already locked
          */
         if (moveRightIfItNeeded(btree, stack, snapshot) == false)
             return true;
  
         page = BufferGetPage(stack->buffer);
         TestForOldSnapshot(snapshot, btree->index, page);
         itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
  
         /*
          * If tuple stores another attribute then stop scan
          */
         if (gintuple_get_attrnum(btree->ginstate, itup) != attnum)
             return true;
  
         /* Safe to fetch attribute value */
         idatum = gintuple_get_key(btree->ginstate, itup, &icategory);
  
         /*
          * Check for appropriate scan stop conditions
          */
         if (scanEntry->isPartialMatch)
         {
             int32       cmp;
  
             /*
              * In partial match, stop scan at any null (including
              * placeholders); partial matches never match nulls
              */
             if (icategory != GIN_CAT_NORM_KEY)
                 return true;
  
             /*----------
              * Check of partial match.
              * case cmp == 0 => match
              * case cmp > 0 => not match and finish scan
              * case cmp < 0 => not match and continue scan
              *----------
              */
             cmp = DatumGetInt32(FunctionCall4Coll(&btree->ginstate->comparePartialFn[attnum - 1],
                                                   btree->ginstate->supportCollation[attnum - 1],
                                                   scanEntry->queryKey,
                                                   idatum,
                                                   UInt16GetDatum(scanEntry->strategy),
                                                   PointerGetDatum(scanEntry->extra_data)));
  
             if (cmp > 0)
                 return true;
             else if (cmp < 0)
             {
                 stack->off++;
                 continue;
             }
         }
         else if (scanEntry->searchMode == GIN_SEARCH_MODE_ALL)
         {
             /*
              * In ALL mode, we are not interested in null items, so we can
              * stop if we get to a null-item placeholder (which will be the
              * last entry for a given attnum).  We do want to include NULL_KEY
              * and EMPTY_ITEM entries, though.
              */
             if (icategory == GIN_CAT_NULL_ITEM)
                 return true;
         }
  
         /*
          * OK, we want to return the TIDs listed in this entry.
          */
         if (GinIsPostingTree(itup))
         {
             BlockNumber rootPostingTree = GinGetPostingTree(itup);
  
             /*
              * We should unlock current page (but not unpin) during tree scan
              * to prevent deadlock with vacuum processes.
              *
              * We save current entry value (idatum) to be able to re-find our
              * tuple after re-locking
              */
             if (icategory == GIN_CAT_NORM_KEY)
                 idatum = datumCopy(idatum, attr->attbyval, attr->attlen);
  
             LockBuffer(stack->buffer, GIN_UNLOCK);
  
             /*
              * Acquire predicate lock on the posting tree.  We already hold a
              * lock on the entry page, but insertions to the posting tree
              * don't check for conflicts on that level.
              */
             PredicateLockPage(btree->index, rootPostingTree, snapshot);
  
             /* Collect all the TIDs in this entry's posting tree */
             scanPostingTree(btree->index, scanEntry, rootPostingTree,
                             snapshot);
  
             /*
              * We lock again the entry page and while it was unlocked insert
              * might have occurred, so we need to re-find our position.
              */
             LockBuffer(stack->buffer, GIN_SHARE);
             page = BufferGetPage(stack->buffer);
             if (!GinPageIsLeaf(page))
             {
                 /*
                  * Root page becomes non-leaf while we unlock it. We will
                  * start again, this situation doesn't occur often - root can
                  * became a non-leaf only once per life of index.
                  */
                 return false;
             }
  
             /* Search forward to re-find idatum */
             for (;;)
             {
                 if (moveRightIfItNeeded(btree, stack, snapshot) == false)
                     ereport(ERROR,
                             (errcode(ERRCODE_INTERNAL_ERROR),
                              errmsg("failed to re-find tuple within index \"%s\"",
                                     RelationGetRelationName(btree->index))));
  
                 page = BufferGetPage(stack->buffer);
                 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
  
                 if (gintuple_get_attrnum(btree->ginstate, itup) == attnum)
                 {
                     Datum       newDatum;
                     GinNullCategory newCategory;
  
                     newDatum = gintuple_get_key(btree->ginstate, itup,
                                                 &newCategory);
  
                     if (ginCompareEntries(btree->ginstate, attnum,
                                           newDatum, newCategory,
                                           idatum, icategory) == 0)
                         break;  /* Found! */
                 }
  
                 stack->off++;
             }
  
             if (icategory == GIN_CAT_NORM_KEY && !attr->attbyval)
                 pfree(DatumGetPointer(idatum));
         }
         else
         {
             ItemPointer ipd;
             int         nipd;
  
             ipd = ginReadTuple(btree->ginstate, scanEntry->attnum, itup, &nipd);
             tbm_add_tuples(scanEntry->matchBitmap, ipd, nipd, false);
             scanEntry->predictNumberResult += GinGetNPosting(itup);
             pfree(ipd);
         }
  
         /*
          * Done with this entry, go to the next
          */
         stack->off++;
     }
 }

Referenced by startScanEntry().

◆ collectMatchesForHeapRow()

static bool collectMatchesForHeapRow	(	IndexScanDesc	scan,
		pendingPosition *	pos
	)

static

Definition at line 1607 of file ginget.c.

 {
     GinScanOpaque so = (GinScanOpaque) scan->opaque;
     OffsetNumber attrnum;
     Page        page;
     IndexTuple  itup;
     int         i,
                 j;
  
     /*
      * Reset all entryRes and hasMatchKey flags
      */
     for (i = 0; i < so->nkeys; i++)
     {
         GinScanKey  key = so->keys + i;
  
         memset(key->entryRes, GIN_FALSE, key->nentries);
     }
     memset(pos->hasMatchKey, false, so->nkeys);
  
     /*
      * Outer loop iterates over multiple pending-list pages when a single heap
      * row has entries spanning those pages.
      */
     for (;;)
     {
         Datum       datum[BLCKSZ / sizeof(IndexTupleData)];
         GinNullCategory category[BLCKSZ / sizeof(IndexTupleData)];
         bool        datumExtracted[BLCKSZ / sizeof(IndexTupleData)];
  
         Assert(pos->lastOffset > pos->firstOffset);
         memset(datumExtracted + pos->firstOffset - 1, 0,
                sizeof(bool) * (pos->lastOffset - pos->firstOffset));
  
         page = BufferGetPage(pos->pendingBuffer);
         TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
  
         for (i = 0; i < so->nkeys; i++)
         {
             GinScanKey  key = so->keys + i;
  
             for (j = 0; j < key->nentries; j++)
             {
                 GinScanEntry entry = key->scanEntry[j];
                 OffsetNumber StopLow = pos->firstOffset,
                             StopHigh = pos->lastOffset,
                             StopMiddle;
  
                 /* If already matched on earlier page, do no extra work */
                 if (key->entryRes[j])
                     continue;
  
                 /*
                  * Interesting tuples are from pos->firstOffset to
                  * pos->lastOffset and they are ordered by (attnum, Datum) as
                  * it's done in entry tree.  So we can use binary search to
                  * avoid linear scanning.
                  */
                 while (StopLow < StopHigh)
                 {
                     int         res;
  
                     StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
  
                     itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, StopMiddle));
  
                     attrnum = gintuple_get_attrnum(&so->ginstate, itup);
  
                     if (key->attnum < attrnum)
                     {
                         StopHigh = StopMiddle;
                         continue;
                     }
                     if (key->attnum > attrnum)
                     {
                         StopLow = StopMiddle + 1;
                         continue;
                     }
  
                     if (datumExtracted[StopMiddle - 1] == false)
                     {
                         datum[StopMiddle - 1] =
                             gintuple_get_key(&so->ginstate, itup,
                                              &category[StopMiddle - 1]);
                         datumExtracted[StopMiddle - 1] = true;
                     }
  
                     if (entry->queryCategory == GIN_CAT_EMPTY_QUERY)
                     {
                         /* special behavior depending on searchMode */
                         if (entry->searchMode == GIN_SEARCH_MODE_ALL)
                         {
                             /* match anything except NULL_ITEM */
                             if (category[StopMiddle - 1] == GIN_CAT_NULL_ITEM)
                                 res = -1;
                             else
                                 res = 0;
                         }
                         else
                         {
                             /* match everything */
                             res = 0;
                         }
                     }
                     else
                     {
                         res = ginCompareEntries(&so->ginstate,
                                                 entry->attnum,
                                                 entry->queryKey,
                                                 entry->queryCategory,
                                                 datum[StopMiddle - 1],
                                                 category[StopMiddle - 1]);
                     }
  
                     if (res == 0)
                     {
                         /*
                          * Found exact match (there can be only one, except in
                          * EMPTY_QUERY mode).
                          *
                          * If doing partial match, scan forward from here to
                          * end of page to check for matches.
                          *
                          * See comment above about tuple's ordering.
                          */
                         if (entry->isPartialMatch)
                             key->entryRes[j] =
                                 matchPartialInPendingList(&so->ginstate,
                                                           page,
                                                           StopMiddle,
                                                           pos->lastOffset,
                                                           entry,
                                                           datum,
                                                           category,
                                                           datumExtracted);
                         else
                             key->entryRes[j] = true;
  
                         /* done with binary search */
                         break;
                     }
                     else if (res < 0)
                         StopHigh = StopMiddle;
                     else
                         StopLow = StopMiddle + 1;
                 }
  
                 if (StopLow >= StopHigh && entry->isPartialMatch)
                 {
                     /*
                      * No exact match on this page.  If doing partial match,
                      * scan from the first tuple greater than target value to
                      * end of page.  Note that since we don't remember whether
                      * the comparePartialFn told us to stop early on a
                      * previous page, we will uselessly apply comparePartialFn
                      * to the first tuple on each subsequent page.
                      */
                     key->entryRes[j] =
                         matchPartialInPendingList(&so->ginstate,
                                                   page,
                                                   StopHigh,
                                                   pos->lastOffset,
                                                   entry,
                                                   datum,
                                                   category,
                                                   datumExtracted);
                 }
  
                 pos->hasMatchKey[i] |= key->entryRes[j];
             }
         }
  
         /* Advance firstOffset over the scanned tuples */
         pos->firstOffset = pos->lastOffset;
  
         if (GinPageHasFullRow(page))
         {
             /*
              * We have examined all pending entries for the current heap row.
              * Break out of loop over pages.
              */
             break;
         }
         else
         {
             /*
              * Advance to next page of pending entries for the current heap
              * row.  Complain if there isn't one.
              */
             ItemPointerData item = pos->item;
  
             if (scanGetCandidate(scan, pos) == false ||
                 !ItemPointerEquals(&pos->item, &item))
                 elog(ERROR, "could not find additional pending pages for same heap tuple");
         }
     }
  
     /*
      * All scan keys except excludeOnly require at least one entry to match.
      * excludeOnly keys are an exception, because their implied
      * GIN_CAT_EMPTY_QUERY scanEntry always matches.  So return "true" if all
      * non-excludeOnly scan keys have at least one match.
      */
     for (i = 0; i < so->nkeys; i++)
     {
         if (pos->hasMatchKey[i] == false && !so->keys[i].excludeOnly)
             return false;
     }
  
     return true;
 }

References Assert(), GinScanEntryData::attnum, BufferGetPage(), elog(), ERROR, GinScanKeyData::excludeOnly, pendingPosition::firstOffset, GIN_CAT_EMPTY_QUERY, GIN_CAT_NULL_ITEM, GIN_FALSE, GIN_SEARCH_MODE_ALL, ginCompareEntries(), GinPageHasFullRow, GinScanOpaqueData::ginstate, gintuple_get_attrnum(), gintuple_get_key(), pendingPosition::hasMatchKey, i, IndexScanDescData::indexRelation, GinScanEntryData::isPartialMatch, pendingPosition::item, ItemPointerEquals(), j, sort-test::key, GinScanOpaqueData::keys, pendingPosition::lastOffset, matchPartialInPendingList(), GinScanOpaqueData::nkeys, IndexScanDescData::opaque, PageGetItem(), PageGetItemId(), pendingPosition::pendingBuffer, GinScanEntryData::queryCategory, GinScanEntryData::queryKey, res, scanGetCandidate(), GinScanEntryData::searchMode, TestForOldSnapshot(), and IndexScanDescData::xs_snapshot.

Referenced by scanPendingInsert().

◆ entryGetItem()

static void entryGetItem	(	GinState *	ginstate,
		GinScanEntry	entry,
		ItemPointerData	advancePast,
		Snapshot	snapshot
	)

static

Definition at line 808 of file ginget.c.

 {
     Assert(!entry->isFinished);
  
     Assert(!ItemPointerIsValid(&entry->curItem) ||
            ginCompareItemPointers(&entry->curItem, &advancePast) <= 0);
  
     if (entry->matchBitmap)
     {
         /* A bitmap result */
         BlockNumber advancePastBlk = GinItemPointerGetBlockNumber(&advancePast);
         OffsetNumber advancePastOff = GinItemPointerGetOffsetNumber(&advancePast);
  
         for (;;)
         {
             /*
              * If we've exhausted all items on this block, move to next block
              * in the bitmap.
              */
             while (entry->matchResult == NULL ||
                    (entry->matchResult->ntuples >= 0 &&
                     entry->offset >= entry->matchResult->ntuples) ||
                    entry->matchResult->blockno < advancePastBlk ||
                    (ItemPointerIsLossyPage(&advancePast) &&
                     entry->matchResult->blockno == advancePastBlk))
             {
                 entry->matchResult = tbm_iterate(entry->matchIterator);
  
                 if (entry->matchResult == NULL)
                 {
                     ItemPointerSetInvalid(&entry->curItem);
                     tbm_end_iterate(entry->matchIterator);
                     entry->matchIterator = NULL;
                     entry->isFinished = true;
                     break;
                 }
  
                 /*
                  * Reset counter to the beginning of entry->matchResult. Note:
                  * entry->offset is still greater than matchResult->ntuples if
                  * matchResult is lossy.  So, on next call we will get next
                  * result from TIDBitmap.
                  */
                 entry->offset = 0;
             }
             if (entry->isFinished)
                 break;
  
             /*
              * We're now on the first page after advancePast which has any
              * items on it. If it's a lossy result, return that.
              */
             if (entry->matchResult->ntuples < 0)
             {
                 ItemPointerSetLossyPage(&entry->curItem,
                                         entry->matchResult->blockno);
  
                 /*
                  * We might as well fall out of the loop; we could not
                  * estimate number of results on this page to support correct
                  * reducing of result even if it's enabled.
                  */
                 break;
             }
  
             /*
              * Not a lossy page. Skip over any offsets <= advancePast, and
              * return that.
              */
             if (entry->matchResult->blockno == advancePastBlk)
             {
                 /*
                  * First, do a quick check against the last offset on the
                  * page. If that's > advancePast, so are all the other
                  * offsets, so just go back to the top to get the next page.
                  */
                 if (entry->matchResult->offsets[entry->matchResult->ntuples - 1] <= advancePastOff)
                 {
                     entry->offset = entry->matchResult->ntuples;
                     continue;
                 }
  
                 /* Otherwise scan to find the first item > advancePast */
                 while (entry->matchResult->offsets[entry->offset] <= advancePastOff)
                     entry->offset++;
             }
  
             ItemPointerSet(&entry->curItem,
                            entry->matchResult->blockno,
                            entry->matchResult->offsets[entry->offset]);
             entry->offset++;
  
             /* Done unless we need to reduce the result */
             if (!entry->reduceResult || !dropItem(entry))
                 break;
         }
     }
     else if (!BufferIsValid(entry->buffer))
     {
         /*
          * A posting list from an entry tuple, or the last page of a posting
          * tree.
          */
         for (;;)
         {
             if (entry->offset >= entry->nlist)
             {
                 ItemPointerSetInvalid(&entry->curItem);
                 entry->isFinished = true;
                 break;
             }
  
             entry->curItem = entry->list[entry->offset++];
  
             /* If we're not past advancePast, keep scanning */
             if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
                 continue;
  
             /* Done unless we need to reduce the result */
             if (!entry->reduceResult || !dropItem(entry))
                 break;
         }
     }
     else
     {
         /* A posting tree */
         for (;;)
         {
             /* If we've processed the current batch, load more items */
             while (entry->offset >= entry->nlist)
             {
                 entryLoadMoreItems(ginstate, entry, advancePast, snapshot);
  
                 if (entry->isFinished)
                 {
                     ItemPointerSetInvalid(&entry->curItem);
                     return;
                 }
             }
  
             entry->curItem = entry->list[entry->offset++];
  
             /* If we're not past advancePast, keep scanning */
             if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
                 continue;
  
             /* Done unless we need to reduce the result */
             if (!entry->reduceResult || !dropItem(entry))
                 break;
  
             /*
              * Advance advancePast (so that entryLoadMoreItems will load the
              * right data), and keep scanning
              */
             advancePast = entry->curItem;
         }
     }
 }

Referenced by keyGetItem().

◆ entryIndexByFrequencyCmp()

static int entryIndexByFrequencyCmp	(	const void *	a1,
		const void *	a2,
		void *	arg
	)

static

Definition at line 488 of file ginget.c.

 {
     const GinScanKey key = (const GinScanKey) arg;
     int         i1 = *(const int *) a1;
     int         i2 = *(const int *) a2;
     uint32      n1 = key->scanEntry[i1]->predictNumberResult;
     uint32      n2 = key->scanEntry[i2]->predictNumberResult;
  
     if (n1 < n2)
         return -1;
     else if (n1 == n2)
         return 0;
     else
         return 1;
 }

References a1, a2, arg, and sort-test::key.

Referenced by startScanKey().

◆ entryLoadMoreItems()

static void entryLoadMoreItems	(	GinState *	ginstate,
		GinScanEntry	entry,
		ItemPointerData	advancePast,
		Snapshot	snapshot
	)

static

Definition at line 653 of file ginget.c.

 {
     Page        page;
     int         i;
     bool        stepright;
  
     if (!BufferIsValid(entry->buffer))
     {
         entry->isFinished = true;
         return;
     }
  
     /*
      * We have two strategies for finding the correct page: step right from
      * the current page, or descend the tree again from the root. If
      * advancePast equals the current item, the next matching item should be
      * on the next page, so we step right. Otherwise, descend from root.
      */
     if (ginCompareItemPointers(&entry->curItem, &advancePast) == 0)
     {
         stepright = true;
         LockBuffer(entry->buffer, GIN_SHARE);
     }
     else
     {
         GinBtreeStack *stack;
  
         ReleaseBuffer(entry->buffer);
  
         /*
          * Set the search key, and find the correct leaf page.
          */
         if (ItemPointerIsLossyPage(&advancePast))
         {
             ItemPointerSet(&entry->btree.itemptr,
                            GinItemPointerGetBlockNumber(&advancePast) + 1,
                            FirstOffsetNumber);
         }
         else
         {
             ItemPointerSet(&entry->btree.itemptr,
                            GinItemPointerGetBlockNumber(&advancePast),
                            OffsetNumberNext(GinItemPointerGetOffsetNumber(&advancePast)));
         }
         entry->btree.fullScan = false;
         stack = ginFindLeafPage(&entry->btree, true, false, snapshot);
  
         /* we don't need the stack, just the buffer. */
         entry->buffer = stack->buffer;
         IncrBufferRefCount(entry->buffer);
         freeGinBtreeStack(stack);
         stepright = false;
     }
  
     elog(DEBUG2, "entryLoadMoreItems, %u/%u, skip: %d",
          GinItemPointerGetBlockNumber(&advancePast),
          GinItemPointerGetOffsetNumber(&advancePast),
          !stepright);
  
     page = BufferGetPage(entry->buffer);
     for (;;)
     {
         entry->offset = InvalidOffsetNumber;
         if (entry->list)
         {
             pfree(entry->list);
             entry->list = NULL;
             entry->nlist = 0;
         }
  
         if (stepright)
         {
             /*
              * We've processed all the entries on this page. If it was the
              * last page in the tree, we're done.
              */
             if (GinPageRightMost(page))
             {
                 UnlockReleaseBuffer(entry->buffer);
                 entry->buffer = InvalidBuffer;
                 entry->isFinished = true;
                 return;
             }
  
             /*
              * Step to next page, following the right link. then find the
              * first ItemPointer greater than advancePast.
              */
             entry->buffer = ginStepRight(entry->buffer,
                                          ginstate->index,
                                          GIN_SHARE);
             page = BufferGetPage(entry->buffer);
         }
         stepright = true;
  
         if (GinPageGetOpaque(page)->flags & GIN_DELETED)
             continue;           /* page was deleted by concurrent vacuum */
  
         /*
          * The first item > advancePast might not be on this page, but
          * somewhere to the right, if the page was split, or a non-match from
          * another key in the query allowed us to skip some items from this
          * entry. Keep following the right-links until we re-find the correct
          * page.
          */
         if (!GinPageRightMost(page) &&
             ginCompareItemPointers(&advancePast, GinDataPageGetRightBound(page)) >= 0)
         {
             /*
              * the item we're looking is > the right bound of the page, so it
              * can't be on this page.
              */
             continue;
         }
  
         entry->list = GinDataLeafPageGetItems(page, &entry->nlist, advancePast);
  
         for (i = 0; i < entry->nlist; i++)
         {
             if (ginCompareItemPointers(&advancePast, &entry->list[i]) < 0)
             {
                 entry->offset = i;
  
                 if (GinPageRightMost(page))
                 {
                     /* after processing the copied items, we're done. */
                     UnlockReleaseBuffer(entry->buffer);
                     entry->buffer = InvalidBuffer;
                 }
                 else
                     LockBuffer(entry->buffer, GIN_UNLOCK);
                 return;
             }
         }
     }
 }

References GinScanEntryData::btree, GinBtreeStack::buffer, GinScanEntryData::buffer, BufferGetPage(), BufferIsValid(), GinScanEntryData::curItem, DEBUG2, elog(), FirstOffsetNumber, freeGinBtreeStack(), GinBtreeData::fullScan, GIN_DELETED, GIN_SHARE, GIN_UNLOCK, ginCompareItemPointers(), GinDataLeafPageGetItems(), GinDataPageGetRightBound, ginFindLeafPage(), GinItemPointerGetBlockNumber, GinItemPointerGetOffsetNumber, GinPageGetOpaque, GinPageRightMost, ginStepRight(), i, IncrBufferRefCount(), GinState::index, InvalidBuffer, InvalidOffsetNumber, GinScanEntryData::isFinished, ItemPointerIsLossyPage, ItemPointerSet(), GinBtreeData::itemptr, GinScanEntryData::list, LockBuffer(), GinScanEntryData::nlist, GinScanEntryData::offset, OffsetNumberNext, pfree(), ReleaseBuffer(), and UnlockReleaseBuffer().

Referenced by entryGetItem().

◆ gingetbitmap()

int64 gingetbitmap	(	IndexScanDesc	scan,
		TIDBitmap *	tbm
	)

Definition at line 1918 of file ginget.c.

 {
     GinScanOpaque so = (GinScanOpaque) scan->opaque;
     int64       ntids;
     ItemPointerData iptr;
     bool        recheck;
  
     /*
      * Set up the scan keys, and check for unsatisfiable query.
      */
     ginFreeScanKeys(so);        /* there should be no keys yet, but just to be
                                  * sure */
     ginNewScanKey(scan);
  
     if (GinIsVoidRes(scan))
         return 0;
  
     ntids = 0;
  
     /*
      * First, scan the pending list and collect any matching entries into the
      * bitmap.  After we scan a pending item, some other backend could post it
      * into the main index, and so we might visit it a second time during the
      * main scan.  This is okay because we'll just re-set the same bit in the
      * bitmap.  (The possibility of duplicate visits is a major reason why GIN
      * can't support the amgettuple API, however.) Note that it would not do
      * to scan the main index before the pending list, since concurrent
      * cleanup could then make us miss entries entirely.
      */
     scanPendingInsert(scan, tbm, &ntids);
  
     /*
      * Now scan the main index.
      */
     startScan(scan);
  
     ItemPointerSetMin(&iptr);
  
     for (;;)
     {
         CHECK_FOR_INTERRUPTS();
  
         if (!scanGetItem(scan, iptr, &iptr, &recheck))
             break;
  
         if (ItemPointerIsLossyPage(&iptr))
             tbm_add_page(tbm, ItemPointerGetBlockNumber(&iptr));
         else
             tbm_add_tuples(tbm, &iptr, 1, recheck);
         ntids++;
     }
  
     return ntids;
 }

References CHECK_FOR_INTERRUPTS, ginFreeScanKeys(), GinIsVoidRes, ginNewScanKey(), ItemPointerGetBlockNumber(), ItemPointerIsLossyPage, ItemPointerSetMin, IndexScanDescData::opaque, scanGetItem(), scanPendingInsert(), startScan(), tbm_add_page(), and tbm_add_tuples().

Referenced by ginhandler().

◆ keyGetItem()

static void keyGetItem	(	GinState *	ginstate,
		MemoryContext	tempCtx,
		GinScanKey	key,
		ItemPointerData	advancePast,
		Snapshot	snapshot
	)

static

Definition at line 990 of file ginget.c.

 {
     ItemPointerData minItem;
     ItemPointerData curPageLossy;
     uint32      i;
     bool        haveLossyEntry;
     GinScanEntry entry;
     GinTernaryValue res;
     MemoryContext oldCtx;
     bool        allFinished;
  
     Assert(!key->isFinished);
  
     /*
      * We might have already tested this item; if so, no need to repeat work.
      * (Note: the ">" case can happen, if advancePast is exact but we
      * previously had to set curItem to a lossy-page pointer.)
      */
     if (ginCompareItemPointers(&key->curItem, &advancePast) > 0)
         return;
  
     /*
      * Find the minimum item > advancePast among the active entry streams.
      *
      * Note: a lossy-page entry is encoded by a ItemPointer with max value for
      * offset (0xffff), so that it will sort after any exact entries for the
      * same page.  So we'll prefer to return exact pointers not lossy
      * pointers, which is good.
      */
     ItemPointerSetMax(&minItem);
     allFinished = true;
     for (i = 0; i < key->nrequired; i++)
     {
         entry = key->requiredEntries[i];
  
         if (entry->isFinished)
             continue;
  
         /*
          * Advance this stream if necessary.
          *
          * In particular, since entry->curItem was initialized with
          * ItemPointerSetMin, this ensures we fetch the first item for each
          * entry on the first call.
          */
         if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
         {
             entryGetItem(ginstate, entry, advancePast, snapshot);
             if (entry->isFinished)
                 continue;
         }
  
         allFinished = false;
         if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
             minItem = entry->curItem;
     }
  
     if (allFinished && !key->excludeOnly)
     {
         /* all entries are finished */
         key->isFinished = true;
         return;
     }
  
     if (!key->excludeOnly)
     {
         /*
          * For a normal scan key, we now know there are no matches < minItem.
          *
          * If minItem is lossy, it means that there were no exact items on the
          * page among requiredEntries, because lossy pointers sort after exact
          * items. However, there might be exact items for the same page among
          * additionalEntries, so we mustn't advance past them.
          */
         if (ItemPointerIsLossyPage(&minItem))
         {
             if (GinItemPointerGetBlockNumber(&advancePast) <
                 GinItemPointerGetBlockNumber(&minItem))
             {
                 ItemPointerSet(&advancePast,
                                GinItemPointerGetBlockNumber(&minItem),
                                InvalidOffsetNumber);
             }
         }
         else
         {
             Assert(GinItemPointerGetOffsetNumber(&minItem) > 0);
             ItemPointerSet(&advancePast,
                            GinItemPointerGetBlockNumber(&minItem),
                            OffsetNumberPrev(GinItemPointerGetOffsetNumber(&minItem)));
         }
     }
     else
     {
         /*
          * excludeOnly scan keys don't have any entries that are necessarily
          * present in matching items.  So, we consider the item just after
          * advancePast.
          */
         Assert(key->nrequired == 0);
         ItemPointerSet(&minItem,
                        GinItemPointerGetBlockNumber(&advancePast),
                        OffsetNumberNext(GinItemPointerGetOffsetNumber(&advancePast)));
     }
  
     /*
      * We might not have loaded all the entry streams for this TID yet. We
      * could call the consistent function, passing MAYBE for those entries, to
      * see if it can decide if this TID matches based on the information we
      * have. But if the consistent-function is expensive, and cannot in fact
      * decide with partial information, that could be a big loss. So, load all
      * the additional entries, before calling the consistent function.
      */
     for (i = 0; i < key->nadditional; i++)
     {
         entry = key->additionalEntries[i];
  
         if (entry->isFinished)
             continue;
  
         if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
         {
             entryGetItem(ginstate, entry, advancePast, snapshot);
             if (entry->isFinished)
                 continue;
         }
  
         /*
          * Normally, none of the items in additionalEntries can have a curItem
          * larger than minItem. But if minItem is a lossy page, then there
          * might be exact items on the same page among additionalEntries.
          */
         if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
         {
             Assert(ItemPointerIsLossyPage(&minItem));
             minItem = entry->curItem;
         }
     }
  
     /*
      * Ok, we've advanced all the entries up to minItem now. Set key->curItem,
      * and perform consistentFn test.
      *
      * Lossy-page entries pose a problem, since we don't know the correct
      * entryRes state to pass to the consistentFn, and we also don't know what
      * its combining logic will be (could be AND, OR, or even NOT). If the
      * logic is OR then the consistentFn might succeed for all items in the
      * lossy page even when none of the other entries match.
      *
      * Our strategy is to call the tri-state consistent function, with the
      * lossy-page entries set to MAYBE, and all the other entries FALSE. If it
      * returns FALSE, none of the lossy items alone are enough for a match, so
      * we don't need to return a lossy-page pointer. Otherwise, return a
      * lossy-page pointer to indicate that the whole heap page must be
      * checked.  (On subsequent calls, we'll do nothing until minItem is past
      * the page altogether, thus ensuring that we never return both regular
      * and lossy pointers for the same page.)
      *
      * An exception is that it doesn't matter what we pass for lossy pointers
      * in "hidden" entries, because the consistentFn's result can't depend on
      * them. We could pass them as MAYBE as well, but if we're using the
      * "shim" implementation of a tri-state consistent function (see
      * ginlogic.c), it's better to pass as few MAYBEs as possible. So pass
      * them as true.
      *
      * Note that only lossy-page entries pointing to the current item's page
      * should trigger this processing; we might have future lossy pages in the
      * entry array, but they aren't relevant yet.
      */
     key->curItem = minItem;
     ItemPointerSetLossyPage(&curPageLossy,
                             GinItemPointerGetBlockNumber(&key->curItem));
     haveLossyEntry = false;
     for (i = 0; i < key->nentries; i++)
     {
         entry = key->scanEntry[i];
         if (entry->isFinished == false &&
             ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0)
         {
             if (i < key->nuserentries)
                 key->entryRes[i] = GIN_MAYBE;
             else
                 key->entryRes[i] = GIN_TRUE;
             haveLossyEntry = true;
         }
         else
             key->entryRes[i] = GIN_FALSE;
     }
  
     /* prepare for calling consistentFn in temp context */
     oldCtx = MemoryContextSwitchTo(tempCtx);
  
     if (haveLossyEntry)
     {
         /* Have lossy-page entries, so see if whole page matches */
         res = key->triConsistentFn(key);
  
         if (res == GIN_TRUE || res == GIN_MAYBE)
         {
             /* Yes, so clean up ... */
             MemoryContextSwitchTo(oldCtx);
             MemoryContextReset(tempCtx);
  
             /* and return lossy pointer for whole page */
             key->curItem = curPageLossy;
             key->curItemMatches = true;
             key->recheckCurItem = true;
             return;
         }
     }
  
     /*
      * At this point we know that we don't need to return a lossy whole-page
      * pointer, but we might have matches for individual exact item pointers,
      * possibly in combination with a lossy pointer. Pass lossy pointers as
      * MAYBE to the ternary consistent function, to let it decide if this
      * tuple satisfies the overall key, even though we don't know if the lossy
      * entries match.
      *
      * Prepare entryRes array to be passed to consistentFn.
      */
     for (i = 0; i < key->nentries; i++)
     {
         entry = key->scanEntry[i];
         if (entry->isFinished)
             key->entryRes[i] = GIN_FALSE;
 #if 0
  
         /*
          * This case can't currently happen, because we loaded all the entries
          * for this item earlier.
          */
         else if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
             key->entryRes[i] = GIN_MAYBE;
 #endif
         else if (ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0)
             key->entryRes[i] = GIN_MAYBE;
         else if (ginCompareItemPointers(&entry->curItem, &minItem) == 0)
             key->entryRes[i] = GIN_TRUE;
         else
             key->entryRes[i] = GIN_FALSE;
     }
  
     res = key->triConsistentFn(key);
  
     switch (res)
     {
         case GIN_TRUE:
             key->curItemMatches = true;
             /* triConsistentFn set recheckCurItem */
             break;
  
         case GIN_FALSE:
             key->curItemMatches = false;
             break;
  
         case GIN_MAYBE:
             key->curItemMatches = true;
             key->recheckCurItem = true;
             break;
  
         default:
  
             /*
              * the 'default' case shouldn't happen, but if the consistent
              * function returns something bogus, this is the safe result
              */
             key->curItemMatches = true;
             key->recheckCurItem = true;
             break;
     }
  
     /*
      * We have a tuple, and we know if it matches or not. If it's a non-match,
      * we could continue to find the next matching tuple, but let's break out
      * and give scanGetItem a chance to advance the other keys. They might be
      * able to skip past to a much higher TID, allowing us to save work.
      */
  
     /* clean up after consistentFn calls */
     MemoryContextSwitchTo(oldCtx);
     MemoryContextReset(tempCtx);
 }

References Assert(), GinScanEntryData::curItem, entryGetItem(), GIN_FALSE, GIN_MAYBE, GIN_TRUE, ginCompareItemPointers(), GinItemPointerGetBlockNumber, GinItemPointerGetOffsetNumber, i, InvalidOffsetNumber, GinScanEntryData::isFinished, ItemPointerIsLossyPage, ItemPointerSet(), ItemPointerSetLossyPage, ItemPointerSetMax, sort-test::key, MemoryContextReset(), MemoryContextSwitchTo(), OffsetNumberNext, OffsetNumberPrev, and res.

Referenced by scanGetItem().

◆ matchPartialInPendingList()

static bool matchPartialInPendingList	(	GinState *	ginstate,
		Page	page,
		OffsetNumber	off,
		OffsetNumber	maxoff,
		GinScanEntry	entry,
		Datum *	datum,
		GinNullCategory *	category,
		bool *	datumExtracted
	)

static

Definition at line 1539 of file ginget.c.

 {
     IndexTuple  itup;
     int32       cmp;
  
     /* Partial match to a null is not possible */
     if (entry->queryCategory != GIN_CAT_NORM_KEY)
         return false;
  
     while (off < maxoff)
     {
         itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
  
         if (gintuple_get_attrnum(ginstate, itup) != entry->attnum)
             return false;
  
         if (datumExtracted[off - 1] == false)
         {
             datum[off - 1] = gintuple_get_key(ginstate, itup,
                                               &category[off - 1]);
             datumExtracted[off - 1] = true;
         }
  
         /* Once we hit nulls, no further match is possible */
         if (category[off - 1] != GIN_CAT_NORM_KEY)
             return false;
  
         /*----------
          * Check partial match.
          * case cmp == 0 => match
          * case cmp > 0 => not match and end scan (no later match possible)
          * case cmp < 0 => not match and continue scan
          *----------
          */
         cmp = DatumGetInt32(FunctionCall4Coll(&ginstate->comparePartialFn[entry->attnum - 1],
                                               ginstate->supportCollation[entry->attnum - 1],
                                               entry->queryKey,
                                               datum[off - 1],
                                               UInt16GetDatum(entry->strategy),
                                               PointerGetDatum(entry->extra_data)));
         if (cmp == 0)
             return true;
         else if (cmp > 0)
             return false;
  
         off++;
     }
  
     return false;
 }

References GinScanEntryData::attnum, cmp(), GinState::comparePartialFn, DatumGetInt32(), GinScanEntryData::extra_data, FunctionCall4Coll(), GIN_CAT_NORM_KEY, gintuple_get_attrnum(), gintuple_get_key(), PageGetItem(), PageGetItemId(), PointerGetDatum(), GinScanEntryData::queryCategory, GinScanEntryData::queryKey, GinScanEntryData::strategy, GinState::supportCollation, and UInt16GetDatum().

Referenced by collectMatchesForHeapRow().

◆ moveRightIfItNeeded()

static bool moveRightIfItNeeded	(	GinBtreeData *	btree,
		GinBtreeStack *	stack,
		Snapshot	snapshot
	)

static

Definition at line 43 of file ginget.c.

 {
     Page        page = BufferGetPage(stack->buffer);
  
     if (stack->off > PageGetMaxOffsetNumber(page))
     {
         /*
          * We scanned the whole page, so we should take right page
          */
         if (GinPageRightMost(page))
             return false;       /* no more pages */
  
         stack->buffer = ginStepRight(stack->buffer, btree->index, GIN_SHARE);
         stack->blkno = BufferGetBlockNumber(stack->buffer);
         stack->off = FirstOffsetNumber;
         PredicateLockPage(btree->index, stack->blkno, snapshot);
     }
  
     return true;
 }

References GinBtreeStack::blkno, GinBtreeStack::buffer, BufferGetBlockNumber(), BufferGetPage(), FirstOffsetNumber, GIN_SHARE, GinPageRightMost, ginStepRight(), GinBtreeData::index, GinBtreeStack::off, PageGetMaxOffsetNumber(), and PredicateLockPage().

Referenced by collectMatchBitmap().

◆ scanGetCandidate()

static bool scanGetCandidate	(	IndexScanDesc	scan,
		pendingPosition *	pos
	)

static

Definition at line 1451 of file ginget.c.

 {
     OffsetNumber maxoff;
     Page        page;
     IndexTuple  itup;
  
     ItemPointerSetInvalid(&pos->item);
     for (;;)
     {
         page = BufferGetPage(pos->pendingBuffer);
         TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
  
         maxoff = PageGetMaxOffsetNumber(page);
         if (pos->firstOffset > maxoff)
         {
             BlockNumber blkno = GinPageGetOpaque(page)->rightlink;
  
             if (blkno == InvalidBlockNumber)
             {
                 UnlockReleaseBuffer(pos->pendingBuffer);
                 pos->pendingBuffer = InvalidBuffer;
  
                 return false;
             }
             else
             {
                 /*
                  * Here we must prevent deletion of next page by insertcleanup
                  * process, which may be trying to obtain exclusive lock on
                  * current page.  So, we lock next page before releasing the
                  * current one
                  */
                 Buffer      tmpbuf = ReadBuffer(scan->indexRelation, blkno);
  
                 LockBuffer(tmpbuf, GIN_SHARE);
                 UnlockReleaseBuffer(pos->pendingBuffer);
  
                 pos->pendingBuffer = tmpbuf;
                 pos->firstOffset = FirstOffsetNumber;
             }
         }
         else
         {
             itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->firstOffset));
             pos->item = itup->t_tid;
             if (GinPageHasFullRow(page))
             {
                 /*
                  * find itempointer to the next row
                  */
                 for (pos->lastOffset = pos->firstOffset + 1; pos->lastOffset <= maxoff; pos->lastOffset++)
                 {
                     itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->lastOffset));
                     if (!ItemPointerEquals(&pos->item, &itup->t_tid))
                         break;
                 }
             }
             else
             {
                 /*
                  * All itempointers are the same on this page
                  */
                 pos->lastOffset = maxoff + 1;
             }
  
             /*
              * Now pos->firstOffset points to the first tuple of current heap
              * row, pos->lastOffset points to the first tuple of next heap row
              * (or to the end of page)
              */
             break;
         }
     }
  
     return true;
 }

References BufferGetPage(), pendingPosition::firstOffset, FirstOffsetNumber, GIN_SHARE, GinPageGetOpaque, GinPageHasFullRow, IndexScanDescData::indexRelation, InvalidBlockNumber, InvalidBuffer, pendingPosition::item, ItemPointerEquals(), ItemPointerSetInvalid(), pendingPosition::lastOffset, LockBuffer(), PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), pendingPosition::pendingBuffer, ReadBuffer(), IndexTupleData::t_tid, TestForOldSnapshot(), tmpbuf, UnlockReleaseBuffer(), and IndexScanDescData::xs_snapshot.

Referenced by collectMatchesForHeapRow(), and scanPendingInsert().

◆ scanGetItem()

static bool scanGetItem	(	IndexScanDesc	scan,
		ItemPointerData	advancePast,
		ItemPointerData *	item,
		bool *	recheck
	)

static

Definition at line 1285 of file ginget.c.

 {
     GinScanOpaque so = (GinScanOpaque) scan->opaque;
     uint32      i;
     bool        match;
  
     /*----------
      * Advance the scan keys in lock-step, until we find an item that matches
      * all the keys. If any key reports isFinished, meaning its subset of the
      * entries is exhausted, we can stop.  Otherwise, set *item to the next
      * matching item.
      *
      * This logic works only if a keyGetItem stream can never contain both
      * exact and lossy pointers for the same page.  Else we could have a
      * case like
      *
      *      stream 1        stream 2
      *      ...             ...
      *      42/6            42/7
      *      50/1            42/0xffff
      *      ...             ...
      *
      * We would conclude that 42/6 is not a match and advance stream 1,
      * thus never detecting the match to the lossy pointer in stream 2.
      * (keyGetItem has a similar problem versus entryGetItem.)
      *----------
      */
     do
     {
         ItemPointerSetMin(item);
         match = true;
         for (i = 0; i < so->nkeys && match; i++)
         {
             GinScanKey  key = so->keys + i;
  
             /*
              * If we're considering a lossy page, skip excludeOnly keys. They
              * can't exclude the whole page anyway.
              */
             if (ItemPointerIsLossyPage(item) && key->excludeOnly)
             {
                 /*
                  * ginNewScanKey() should never mark the first key as
                  * excludeOnly.
                  */
                 Assert(i > 0);
                 continue;
             }
  
             /* Fetch the next item for this key that is > advancePast. */
             keyGetItem(&so->ginstate, so->tempCtx, key, advancePast,
                        scan->xs_snapshot);
  
             if (key->isFinished)
                 return false;
  
             /*
              * If it's not a match, we can immediately conclude that nothing
              * <= this item matches, without checking the rest of the keys.
              */
             if (!key->curItemMatches)
             {
                 advancePast = key->curItem;
                 match = false;
                 break;
             }
  
             /*
              * It's a match. We can conclude that nothing < matches, so the
              * other key streams can skip to this item.
              *
              * Beware of lossy pointers, though; from a lossy pointer, we can
              * only conclude that nothing smaller than this *block* matches.
              */
             if (ItemPointerIsLossyPage(&key->curItem))
             {
                 if (GinItemPointerGetBlockNumber(&advancePast) <
                     GinItemPointerGetBlockNumber(&key->curItem))
                 {
                     ItemPointerSet(&advancePast,
                                    GinItemPointerGetBlockNumber(&key->curItem),
                                    InvalidOffsetNumber);
                 }
             }
             else
             {
                 Assert(GinItemPointerGetOffsetNumber(&key->curItem) > 0);
                 ItemPointerSet(&advancePast,
                                GinItemPointerGetBlockNumber(&key->curItem),
                                OffsetNumberPrev(GinItemPointerGetOffsetNumber(&key->curItem)));
             }
  
             /*
              * If this is the first key, remember this location as a potential
              * match, and proceed to check the rest of the keys.
              *
              * Otherwise, check if this is the same item that we checked the
              * previous keys for (or a lossy pointer for the same page). If
              * not, loop back to check the previous keys for this item (we
              * will check this key again too, but keyGetItem returns quickly
              * for that)
              */
             if (i == 0)
             {
                 *item = key->curItem;
             }
             else
             {
                 if (ItemPointerIsLossyPage(&key->curItem) ||
                     ItemPointerIsLossyPage(item))
                 {
                     Assert(GinItemPointerGetBlockNumber(&key->curItem) >= GinItemPointerGetBlockNumber(item));
                     match = (GinItemPointerGetBlockNumber(&key->curItem) ==
                              GinItemPointerGetBlockNumber(item));
                 }
                 else
                 {
                     Assert(ginCompareItemPointers(&key->curItem, item) >= 0);
                     match = (ginCompareItemPointers(&key->curItem, item) == 0);
                 }
             }
         }
     } while (!match);
  
     Assert(!ItemPointerIsMin(item));
  
     /*
      * Now *item contains the first ItemPointer after previous result that
      * satisfied all the keys for that exact TID, or a lossy reference to the
      * same page.
      *
      * We must return recheck = true if any of the keys are marked recheck.
      */
     *recheck = false;
     for (i = 0; i < so->nkeys; i++)
     {
         GinScanKey  key = so->keys + i;
  
         if (key->recheckCurItem)
         {
             *recheck = true;
             break;
         }
     }
  
     return true;
 }

References Assert(), ginCompareItemPointers(), GinItemPointerGetBlockNumber, GinItemPointerGetOffsetNumber, GinScanOpaqueData::ginstate, i, InvalidOffsetNumber, ItemPointerIsLossyPage, ItemPointerSet(), ItemPointerSetMin, sort-test::key, keyGetItem(), GinScanOpaqueData::keys, GinScanOpaqueData::nkeys, OffsetNumberPrev, IndexScanDescData::opaque, GinScanOpaqueData::tempCtx, and IndexScanDescData::xs_snapshot.

Referenced by gingetbitmap().

◆ scanPendingInsert()

static void scanPendingInsert	(	IndexScanDesc	scan,
		TIDBitmap *	tbm,
		int64 *	ntids
	)

static

Definition at line 1823 of file ginget.c.

 {
     GinScanOpaque so = (GinScanOpaque) scan->opaque;
     MemoryContext oldCtx;
     bool        recheck,
                 match;
     int         i;
     pendingPosition pos;
     Buffer      metabuffer = ReadBuffer(scan->indexRelation, GIN_METAPAGE_BLKNO);
     Page        page;
     BlockNumber blkno;
  
     *ntids = 0;
  
     /*
      * Acquire predicate lock on the metapage, to conflict with any fastupdate
      * insertions.
      */
     PredicateLockPage(scan->indexRelation, GIN_METAPAGE_BLKNO, scan->xs_snapshot);
  
     LockBuffer(metabuffer, GIN_SHARE);
     page = BufferGetPage(metabuffer);
     TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
     blkno = GinPageGetMeta(page)->head;
  
     /*
      * fetch head of list before unlocking metapage. head page must be pinned
      * to prevent deletion by vacuum process
      */
     if (blkno == InvalidBlockNumber)
     {
         /* No pending list, so proceed with normal scan */
         UnlockReleaseBuffer(metabuffer);
         return;
     }
  
     pos.pendingBuffer = ReadBuffer(scan->indexRelation, blkno);
     LockBuffer(pos.pendingBuffer, GIN_SHARE);
     pos.firstOffset = FirstOffsetNumber;
     UnlockReleaseBuffer(metabuffer);
     pos.hasMatchKey = palloc(sizeof(bool) * so->nkeys);
  
     /*
      * loop for each heap row. scanGetCandidate returns full row or row's
      * tuples from first page.
      */
     while (scanGetCandidate(scan, &pos))
     {
         /*
          * Check entries in tuple and set up entryRes array.
          *
          * If pending tuples belonging to the current heap row are spread
          * across several pages, collectMatchesForHeapRow will read all of
          * those pages.
          */
         if (!collectMatchesForHeapRow(scan, &pos))
             continue;
  
         /*
          * Matching of entries of one row is finished, so check row using
          * consistent functions.
          */
         oldCtx = MemoryContextSwitchTo(so->tempCtx);
         recheck = false;
         match = true;
  
         for (i = 0; i < so->nkeys; i++)
         {
             GinScanKey  key = so->keys + i;
  
             if (!key->boolConsistentFn(key))
             {
                 match = false;
                 break;
             }
             recheck |= key->recheckCurItem;
         }
  
         MemoryContextSwitchTo(oldCtx);
         MemoryContextReset(so->tempCtx);
  
         if (match)
         {
             tbm_add_tuples(tbm, &pos.item, 1, recheck);
             (*ntids)++;
         }
     }
  
     pfree(pos.hasMatchKey);
 }

References BufferGetPage(), collectMatchesForHeapRow(), FirstOffsetNumber, GIN_METAPAGE_BLKNO, GIN_SHARE, GinPageGetMeta, i, IndexScanDescData::indexRelation, InvalidBlockNumber, sort-test::key, GinScanOpaqueData::keys, LockBuffer(), MemoryContextReset(), MemoryContextSwitchTo(), GinScanOpaqueData::nkeys, IndexScanDescData::opaque, palloc(), pfree(), PredicateLockPage(), ReadBuffer(), scanGetCandidate(), tbm_add_tuples(), GinScanOpaqueData::tempCtx, TestForOldSnapshot(), UnlockReleaseBuffer(), and IndexScanDescData::xs_snapshot.

Referenced by gingetbitmap().

◆ scanPostingTree()

static void scanPostingTree	(	Relation	index,
		GinScanEntry	scanEntry,
		BlockNumber	rootPostingTree,
		Snapshot	snapshot
	)

static

Definition at line 69 of file ginget.c.

 {
     GinBtreeData btree;
     GinBtreeStack *stack;
     Buffer      buffer;
     Page        page;
  
     /* Descend to the leftmost leaf page */
     stack = ginScanBeginPostingTree(&btree, index, rootPostingTree, snapshot);
     buffer = stack->buffer;
  
     IncrBufferRefCount(buffer); /* prevent unpin in freeGinBtreeStack */
  
     freeGinBtreeStack(stack);
  
     /*
      * Loop iterates through all leaf pages of posting tree
      */
     for (;;)
     {
         page = BufferGetPage(buffer);
         if ((GinPageGetOpaque(page)->flags & GIN_DELETED) == 0)
         {
             int         n = GinDataLeafPageGetItemsToTbm(page, scanEntry->matchBitmap);
  
             scanEntry->predictNumberResult += n;
         }
  
         if (GinPageRightMost(page))
             break;              /* no more pages */
  
         buffer = ginStepRight(buffer, index, GIN_SHARE);
     }
  
     UnlockReleaseBuffer(buffer);
 }

References GinBtreeStack::buffer, BufferGetPage(), freeGinBtreeStack(), GIN_DELETED, GIN_SHARE, GinDataLeafPageGetItemsToTbm(), GinPageGetOpaque, GinPageRightMost, ginScanBeginPostingTree(), ginStepRight(), IncrBufferRefCount(), GinScanEntryData::matchBitmap, GinScanEntryData::predictNumberResult, and UnlockReleaseBuffer().

Referenced by collectMatchBitmap().

◆ startScan()

static void startScan ( IndexScanDesc scan )

static

Definition at line 601 of file ginget.c.

 {
     GinScanOpaque so = (GinScanOpaque) scan->opaque;
     GinState   *ginstate = &so->ginstate;
     uint32      i;
  
     for (i = 0; i < so->totalentries; i++)
         startScanEntry(ginstate, so->entries[i], scan->xs_snapshot);
  
     if (GinFuzzySearchLimit > 0)
     {
         /*
          * If all of keys more than threshold we will try to reduce result, we
          * hope (and only hope, for intersection operation of array our
          * supposition isn't true), that total result will not more than
          * minimal predictNumberResult.
          */
         bool        reduce = true;
  
         for (i = 0; i < so->totalentries; i++)
         {
             if (so->entries[i]->predictNumberResult <= so->totalentries * GinFuzzySearchLimit)
             {
                 reduce = false;
                 break;
             }
         }
         if (reduce)
         {
             for (i = 0; i < so->totalentries; i++)
             {
                 so->entries[i]->predictNumberResult /= so->totalentries;
                 so->entries[i]->reduceResult = true;
             }
         }
     }
  
     /*
      * Now that we have the estimates for the entry frequencies, finish
      * initializing the scan keys.
      */
     for (i = 0; i < so->nkeys; i++)
         startScanKey(ginstate, so, so->keys + i);
 }

References GinScanOpaqueData::entries, GinFuzzySearchLimit, GinScanOpaqueData::ginstate, i, GinScanOpaqueData::keys, GinScanOpaqueData::nkeys, IndexScanDescData::opaque, GinScanEntryData::predictNumberResult, reduce(), GinScanEntryData::reduceResult, startScanEntry(), startScanKey(), GinScanOpaqueData::totalentries, and IndexScanDescData::xs_snapshot.

Referenced by gingetbitmap().

◆ startScanEntry()

static void startScanEntry	(	GinState *	ginstate,
		GinScanEntry	entry,
		Snapshot	snapshot
	)

static

Definition at line 319 of file ginget.c.

 {
     GinBtreeData btreeEntry;
     GinBtreeStack *stackEntry;
     Page        page;
     bool        needUnlock;
  
 restartScanEntry:
     entry->buffer = InvalidBuffer;
     ItemPointerSetMin(&entry->curItem);
     entry->offset = InvalidOffsetNumber;
     if (entry->list)
         pfree(entry->list);
     entry->list = NULL;
     entry->nlist = 0;
     entry->matchBitmap = NULL;
     entry->matchResult = NULL;
     entry->reduceResult = false;
     entry->predictNumberResult = 0;
  
     /*
      * we should find entry, and begin scan of posting tree or just store
      * posting list in memory
      */
     ginPrepareEntryScan(&btreeEntry, entry->attnum,
                         entry->queryKey, entry->queryCategory,
                         ginstate);
     stackEntry = ginFindLeafPage(&btreeEntry, true, false, snapshot);
     page = BufferGetPage(stackEntry->buffer);
  
     /* ginFindLeafPage() will have already checked snapshot age. */
     needUnlock = true;
  
     entry->isFinished = true;
  
     if (entry->isPartialMatch ||
         entry->queryCategory == GIN_CAT_EMPTY_QUERY)
     {
         /*
          * btreeEntry.findItem locates the first item >= given search key.
          * (For GIN_CAT_EMPTY_QUERY, it will find the leftmost index item
          * because of the way the GIN_CAT_EMPTY_QUERY category code is
          * assigned.)  We scan forward from there and collect all TIDs needed
          * for the entry type.
          */
         btreeEntry.findItem(&btreeEntry, stackEntry);
         if (collectMatchBitmap(&btreeEntry, stackEntry, entry, snapshot)
             == false)
         {
             /*
              * GIN tree was seriously restructured, so we will cleanup all
              * found data and rescan. See comments near 'return false' in
              * collectMatchBitmap()
              */
             if (entry->matchBitmap)
             {
                 if (entry->matchIterator)
                     tbm_end_iterate(entry->matchIterator);
                 entry->matchIterator = NULL;
                 tbm_free(entry->matchBitmap);
                 entry->matchBitmap = NULL;
             }
             LockBuffer(stackEntry->buffer, GIN_UNLOCK);
             freeGinBtreeStack(stackEntry);
             goto restartScanEntry;
         }
  
         if (entry->matchBitmap && !tbm_is_empty(entry->matchBitmap))
         {
             entry->matchIterator = tbm_begin_iterate(entry->matchBitmap);
             entry->isFinished = false;
         }
     }
     else if (btreeEntry.findItem(&btreeEntry, stackEntry))
     {
         IndexTuple  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stackEntry->off));
  
         if (GinIsPostingTree(itup))
         {
             BlockNumber rootPostingTree = GinGetPostingTree(itup);
             GinBtreeStack *stack;
             Page        entrypage;
             ItemPointerData minItem;
  
             /*
              * This is an equality scan, so lock the root of the posting tree.
              * It represents a lock on the exact key value, and covers all the
              * items in the posting tree.
              */
             PredicateLockPage(ginstate->index, rootPostingTree, snapshot);
  
             /*
              * We should unlock entry page before touching posting tree to
              * prevent deadlocks with vacuum processes. Because entry is never
              * deleted from page and posting tree is never reduced to the
              * posting list, we can unlock page after getting BlockNumber of
              * root of posting tree.
              */
             LockBuffer(stackEntry->buffer, GIN_UNLOCK);
             needUnlock = false;
  
             stack = ginScanBeginPostingTree(&entry->btree, ginstate->index,
                                             rootPostingTree, snapshot);
             entry->buffer = stack->buffer;
  
             /*
              * We keep buffer pinned because we need to prevent deletion of
              * page during scan. See GIN's vacuum implementation. RefCount is
              * increased to keep buffer pinned after freeGinBtreeStack() call.
              */
             IncrBufferRefCount(entry->buffer);
  
             entrypage = BufferGetPage(entry->buffer);
  
             /*
              * Load the first page into memory.
              */
             ItemPointerSetMin(&minItem);
             entry->list = GinDataLeafPageGetItems(entrypage, &entry->nlist, minItem);
  
             entry->predictNumberResult = stack->predictNumber * entry->nlist;
  
             LockBuffer(entry->buffer, GIN_UNLOCK);
             freeGinBtreeStack(stack);
             entry->isFinished = false;
         }
         else
         {
             /*
              * Lock the entry leaf page.  This is more coarse-grained than
              * necessary, because it will conflict with any insertions that
              * land on the same leaf page, not only the exact key we searched
              * for.  But locking an individual tuple would require updating
              * that lock whenever it moves because of insertions or vacuums,
              * which seems too complicated.
              */
             PredicateLockPage(ginstate->index,
                               BufferGetBlockNumber(stackEntry->buffer),
                               snapshot);
             if (GinGetNPosting(itup) > 0)
             {
                 entry->list = ginReadTuple(ginstate, entry->attnum, itup,
                                            &entry->nlist);
                 entry->predictNumberResult = entry->nlist;
  
                 entry->isFinished = false;
             }
         }
     }
     else
     {
         /*
          * No entry found.  Predicate lock the leaf page, to lock the place
          * where the entry would've been, had there been one.
          */
         PredicateLockPage(ginstate->index,
                           BufferGetBlockNumber(stackEntry->buffer), snapshot);
     }
  
     if (needUnlock)
         LockBuffer(stackEntry->buffer, GIN_UNLOCK);
     freeGinBtreeStack(stackEntry);
 }

Referenced by startScan().

◆ startScanKey()

static void startScanKey	(	GinState *	ginstate,
		GinScanOpaque	so,
		GinScanKey	key
	)

static

Definition at line 505 of file ginget.c.

 {
     MemoryContext oldCtx = CurrentMemoryContext;
     int         i;
     int         j;
     int        *entryIndexes;
  
     ItemPointerSetMin(&key->curItem);
     key->curItemMatches = false;
     key->recheckCurItem = false;
     key->isFinished = false;
  
     /*
      * Divide the entries into two distinct sets: required and additional.
      * Additional entries are not enough for a match alone, without any items
      * from the required set, but are needed by the consistent function to
      * decide if an item matches. When scanning, we can skip over items from
      * additional entries that have no corresponding matches in any of the
      * required entries. That speeds up queries like "frequent & rare"
      * considerably, if the frequent term can be put in the additional set.
      *
      * There can be many legal ways to divide them entries into these two
      * sets. A conservative division is to just put everything in the required
      * set, but the more you can put in the additional set, the more you can
      * skip during the scan. To maximize skipping, we try to put as many
      * frequent items as possible into additional, and less frequent ones into
      * required. To do that, sort the entries by frequency
      * (predictNumberResult), and put entries into the required set in that
      * order, until the consistent function says that none of the remaining
      * entries can form a match, without any items from the required set. The
      * rest go to the additional set.
      *
      * Exclude-only scan keys are known to have no required entries.
      */
     if (key->excludeOnly)
     {
         MemoryContextSwitchTo(so->keyCtx);
  
         key->nrequired = 0;
         key->nadditional = key->nentries;
         key->additionalEntries = palloc(key->nadditional * sizeof(GinScanEntry));
         for (i = 0; i < key->nadditional; i++)
             key->additionalEntries[i] = key->scanEntry[i];
     }
     else if (key->nentries > 1)
     {
         MemoryContextSwitchTo(so->tempCtx);
  
         entryIndexes = (int *) palloc(sizeof(int) * key->nentries);
         for (i = 0; i < key->nentries; i++)
             entryIndexes[i] = i;
         qsort_arg(entryIndexes, key->nentries, sizeof(int),
                   entryIndexByFrequencyCmp, key);
  
         for (i = 0; i < key->nentries - 1; i++)
         {
             /* Pass all entries <= i as FALSE, and the rest as MAYBE */
             for (j = 0; j <= i; j++)
                 key->entryRes[entryIndexes[j]] = GIN_FALSE;
             for (j = i + 1; j < key->nentries; j++)
                 key->entryRes[entryIndexes[j]] = GIN_MAYBE;
  
             if (key->triConsistentFn(key) == GIN_FALSE)
                 break;
         }
         /* i is now the last required entry. */
  
         MemoryContextSwitchTo(so->keyCtx);
  
         key->nrequired = i + 1;
         key->nadditional = key->nentries - key->nrequired;
         key->requiredEntries = palloc(key->nrequired * sizeof(GinScanEntry));
         key->additionalEntries = palloc(key->nadditional * sizeof(GinScanEntry));
  
         j = 0;
         for (i = 0; i < key->nrequired; i++)
             key->requiredEntries[i] = key->scanEntry[entryIndexes[j++]];
         for (i = 0; i < key->nadditional; i++)
             key->additionalEntries[i] = key->scanEntry[entryIndexes[j++]];
  
         /* clean up after consistentFn calls (also frees entryIndexes) */
         MemoryContextReset(so->tempCtx);
     }
     else
     {
         MemoryContextSwitchTo(so->keyCtx);
  
         key->nrequired = 1;
         key->nadditional = 0;
         key->requiredEntries = palloc(1 * sizeof(GinScanEntry));
         key->requiredEntries[0] = key->scanEntry[0];
     }
     MemoryContextSwitchTo(oldCtx);
 }

References CurrentMemoryContext, entryIndexByFrequencyCmp(), GIN_FALSE, GIN_MAYBE, i, if(), ItemPointerSetMin, j, sort-test::key, GinScanOpaqueData::keyCtx, MemoryContextReset(), MemoryContextSwitchTo(), palloc(), qsort_arg(), and GinScanOpaqueData::tempCtx.

Referenced by startScan().

Variable Documentation

◆ GinFuzzySearchLimit

int GinFuzzySearchLimit = 0

Definition at line 27 of file ginget.c.

Referenced by startScan().

Data Structures

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ dropItem

◆ gin_rand

◆ GinIsVoidRes

Typedef Documentation

◆ pendingPosition

Function Documentation

◆ collectMatchBitmap()

◆ collectMatchesForHeapRow()

◆ entryGetItem()

◆ entryIndexByFrequencyCmp()

◆ entryLoadMoreItems()

◆ gingetbitmap()

◆ keyGetItem()

◆ matchPartialInPendingList()

◆ moveRightIfItNeeded()

◆ scanGetCandidate()

◆ scanGetItem()

◆ scanPendingInsert()

◆ scanPostingTree()

◆ startScan()

◆ startScanEntry()

◆ startScanKey()

Variable Documentation

◆ GinFuzzySearchLimit