LCOV - code coverage report
Current view: top level - src/backend/access/gin - ginget.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 429 589 72.8 %
Date: 2019-11-21 12:06:29 Functions: 14 16 87.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * ginget.c
       4             :  *    fetch tuples from a GIN scan.
       5             :  *
       6             :  *
       7             :  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
       8             :  * Portions Copyright (c) 1994, Regents of the University of California
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *          src/backend/access/gin/ginget.c
      12             :  *-------------------------------------------------------------------------
      13             :  */
      14             : 
      15             : #include "postgres.h"
      16             : 
      17             : #include "access/gin_private.h"
      18             : #include "access/relscan.h"
      19             : #include "miscadmin.h"
      20             : #include "storage/predicate.h"
      21             : #include "utils/datum.h"
      22             : #include "utils/memutils.h"
      23             : #include "utils/rel.h"
      24             : 
      25             : /* GUC parameter */
      26             : int         GinFuzzySearchLimit = 0;
      27             : 
      28             : typedef struct pendingPosition
      29             : {
      30             :     Buffer      pendingBuffer;
      31             :     OffsetNumber firstOffset;
      32             :     OffsetNumber lastOffset;
      33             :     ItemPointerData item;
      34             :     bool       *hasMatchKey;
      35             : } pendingPosition;
      36             : 
      37             : 
      38             : /*
      39             :  * Goes to the next page if current offset is outside of bounds
      40             :  */
      41             : static bool
      42       76522 : moveRightIfItNeeded(GinBtreeData *btree, GinBtreeStack *stack, Snapshot snapshot)
      43             : {
      44       76522 :     Page        page = BufferGetPage(stack->buffer);
      45             : 
      46       76522 :     if (stack->off > PageGetMaxOffsetNumber(page))
      47             :     {
      48             :         /*
      49             :          * We scanned the whole page, so we should take right page
      50             :          */
      51         828 :         if (GinPageRightMost(page))
      52         184 :             return false;       /* no more pages */
      53             : 
      54         644 :         stack->buffer = ginStepRight(stack->buffer, btree->index, GIN_SHARE);
      55         644 :         stack->blkno = BufferGetBlockNumber(stack->buffer);
      56         644 :         stack->off = FirstOffsetNumber;
      57         644 :         PredicateLockPage(btree->index, stack->blkno, snapshot);
      58             :     }
      59             : 
      60       76338 :     return true;
      61             : }
      62             : 
      63             : /*
      64             :  * Scan all pages of a posting tree and save all its heap ItemPointers
      65             :  * in scanEntry->matchBitmap
      66             :  */
      67             : static void
      68           0 : scanPostingTree(Relation index, GinScanEntry scanEntry,
      69             :                 BlockNumber rootPostingTree, Snapshot snapshot)
      70             : {
      71             :     GinBtreeData btree;
      72             :     GinBtreeStack *stack;
      73             :     Buffer      buffer;
      74             :     Page        page;
      75             : 
      76             :     /* Descend to the leftmost leaf page */
      77           0 :     stack = ginScanBeginPostingTree(&btree, index, rootPostingTree, snapshot);
      78           0 :     buffer = stack->buffer;
      79             : 
      80           0 :     IncrBufferRefCount(buffer); /* prevent unpin in freeGinBtreeStack */
      81             : 
      82           0 :     freeGinBtreeStack(stack);
      83             : 
      84             :     /*
      85             :      * Loop iterates through all leaf pages of posting tree
      86             :      */
      87             :     for (;;)
      88             :     {
      89           0 :         page = BufferGetPage(buffer);
      90           0 :         if ((GinPageGetOpaque(page)->flags & GIN_DELETED) == 0)
      91             :         {
      92           0 :             int         n = GinDataLeafPageGetItemsToTbm(page, scanEntry->matchBitmap);
      93             : 
      94           0 :             scanEntry->predictNumberResult += n;
      95             :         }
      96             : 
      97           0 :         if (GinPageRightMost(page))
      98           0 :             break;              /* no more pages */
      99             : 
     100           0 :         buffer = ginStepRight(buffer, index, GIN_SHARE);
     101             :     }
     102             : 
     103           0 :     UnlockReleaseBuffer(buffer);
     104           0 : }
     105             : 
     106             : /*
     107             :  * Collects TIDs into scanEntry->matchBitmap for all heap tuples that
     108             :  * match the search entry.  This supports three different match modes:
     109             :  *
     110             :  * 1. Partial-match support: scan from current point until the
     111             :  *    comparePartialFn says we're done.
     112             :  * 2. SEARCH_MODE_ALL: scan from current point (which should be first
     113             :  *    key for the current attnum) until we hit null items or end of attnum
     114             :  * 3. SEARCH_MODE_EVERYTHING: scan from current point (which should be first
     115             :  *    key for the current attnum) until we hit end of attnum
     116             :  *
     117             :  * Returns true if done, false if it's necessary to restart scan from scratch
     118             :  */
     119             : static bool
     120         328 : collectMatchBitmap(GinBtreeData *btree, GinBtreeStack *stack,
     121             :                    GinScanEntry scanEntry, Snapshot snapshot)
     122             : {
     123             :     OffsetNumber attnum;
     124             :     Form_pg_attribute attr;
     125             : 
     126             :     /* Initialize empty bitmap result */
     127         328 :     scanEntry->matchBitmap = tbm_create(work_mem * 1024L, NULL);
     128             : 
     129             :     /* Null query cannot partial-match anything */
     130         576 :     if (scanEntry->isPartialMatch &&
     131         248 :         scanEntry->queryCategory != GIN_CAT_NORM_KEY)
     132           0 :         return true;
     133             : 
     134             :     /* Locate tupdesc entry for key column (for attbyval/attlen data) */
     135         328 :     attnum = scanEntry->attnum;
     136         328 :     attr = TupleDescAttr(btree->ginstate->origTupdesc, attnum - 1);
     137             : 
     138             :     /*
     139             :      * Predicate lock entry leaf page, following pages will be locked by
     140             :      * moveRightIfItNeeded()
     141             :      */
     142         328 :     PredicateLockPage(btree->index, stack->buffer, snapshot);
     143             : 
     144             :     for (;;)
     145       76194 :     {
     146             :         Page        page;
     147             :         IndexTuple  itup;
     148             :         Datum       idatum;
     149             :         GinNullCategory icategory;
     150             : 
     151             :         /*
     152             :          * stack->off points to the interested entry, buffer is already locked
     153             :          */
     154       76522 :         if (moveRightIfItNeeded(btree, stack, snapshot) == false)
     155         512 :             return true;
     156             : 
     157       76338 :         page = BufferGetPage(stack->buffer);
     158       76338 :         TestForOldSnapshot(snapshot, btree->index, page);
     159       76338 :         itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
     160             : 
     161             :         /*
     162             :          * If tuple stores another attribute then stop scan
     163             :          */
     164       76338 :         if (gintuple_get_attrnum(btree->ginstate, itup) != attnum)
     165           0 :             return true;
     166             : 
     167             :         /* Safe to fetch attribute value */
     168       76338 :         idatum = gintuple_get_key(btree->ginstate, itup, &icategory);
     169             : 
     170             :         /*
     171             :          * Check for appropriate scan stop conditions
     172             :          */
     173       76338 :         if (scanEntry->isPartialMatch)
     174             :         {
     175             :             int32       cmp;
     176             : 
     177             :             /*
     178             :              * In partial match, stop scan at any null (including
     179             :              * placeholders); partial matches never match nulls
     180             :              */
     181        1158 :             if (icategory != GIN_CAT_NORM_KEY)
     182          10 :                 return true;
     183             : 
     184             :             /*----------
     185             :              * Check of partial match.
     186             :              * case cmp == 0 => match
     187             :              * case cmp > 0 => not match and finish scan
     188             :              * case cmp < 0 => not match and continue scan
     189             :              *----------
     190             :              */
     191        1148 :             cmp = DatumGetInt32(FunctionCall4Coll(&btree->ginstate->comparePartialFn[attnum - 1],
     192             :                                                   btree->ginstate->supportCollation[attnum - 1],
     193             :                                                   scanEntry->queryKey,
     194             :                                                   idatum,
     195             :                                                   UInt16GetDatum(scanEntry->strategy),
     196             :                                                   PointerGetDatum(scanEntry->extra_data)));
     197             : 
     198        1148 :             if (cmp > 0)
     199         122 :                 return true;
     200        1026 :             else if (cmp < 0)
     201             :             {
     202          60 :                 stack->off++;
     203          60 :                 continue;
     204             :             }
     205             :         }
     206       75180 :         else if (scanEntry->searchMode == GIN_SEARCH_MODE_ALL)
     207             :         {
     208             :             /*
     209             :              * In ALL mode, we are not interested in null items, so we can
     210             :              * stop if we get to a null-item placeholder (which will be the
     211             :              * last entry for a given attnum).  We do want to include NULL_KEY
     212             :              * and EMPTY_ITEM entries, though.
     213             :              */
     214       75180 :             if (icategory == GIN_CAT_NULL_ITEM)
     215          12 :                 return true;
     216             :         }
     217             : 
     218             :         /*
     219             :          * OK, we want to return the TIDs listed in this entry.
     220             :          */
     221       76134 :         if (GinIsPostingTree(itup))
     222             :         {
     223           0 :             BlockNumber rootPostingTree = GinGetPostingTree(itup);
     224             : 
     225             :             /*
     226             :              * We should unlock current page (but not unpin) during tree scan
     227             :              * to prevent deadlock with vacuum processes.
     228             :              *
     229             :              * We save current entry value (idatum) to be able to re-find our
     230             :              * tuple after re-locking
     231             :              */
     232           0 :             if (icategory == GIN_CAT_NORM_KEY)
     233           0 :                 idatum = datumCopy(idatum, attr->attbyval, attr->attlen);
     234             : 
     235           0 :             LockBuffer(stack->buffer, GIN_UNLOCK);
     236             : 
     237             :             /*
     238             :              * Acquire predicate lock on the posting tree.  We already hold a
     239             :              * lock on the entry page, but insertions to the posting tree
     240             :              * don't check for conflicts on that level.
     241             :              */
     242           0 :             PredicateLockPage(btree->index, rootPostingTree, snapshot);
     243             : 
     244             :             /* Collect all the TIDs in this entry's posting tree */
     245           0 :             scanPostingTree(btree->index, scanEntry, rootPostingTree,
     246             :                             snapshot);
     247             : 
     248             :             /*
     249             :              * We lock again the entry page and while it was unlocked insert
     250             :              * might have occurred, so we need to re-find our position.
     251             :              */
     252           0 :             LockBuffer(stack->buffer, GIN_SHARE);
     253           0 :             page = BufferGetPage(stack->buffer);
     254           0 :             if (!GinPageIsLeaf(page))
     255             :             {
     256             :                 /*
     257             :                  * Root page becomes non-leaf while we unlock it. We will
     258             :                  * start again, this situation doesn't occur often - root can
     259             :                  * became a non-leaf only once per life of index.
     260             :                  */
     261           0 :                 return false;
     262             :             }
     263             : 
     264             :             /* Search forward to re-find idatum */
     265             :             for (;;)
     266           0 :             {
     267             :                 Datum       newDatum;
     268             :                 GinNullCategory newCategory;
     269             : 
     270           0 :                 if (moveRightIfItNeeded(btree, stack, snapshot) == false)
     271           0 :                     elog(ERROR, "lost saved point in index"); /* must not happen !!! */
     272             : 
     273           0 :                 page = BufferGetPage(stack->buffer);
     274           0 :                 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
     275             : 
     276           0 :                 if (gintuple_get_attrnum(btree->ginstate, itup) != attnum)
     277           0 :                     elog(ERROR, "lost saved point in index"); /* must not happen !!! */
     278           0 :                 newDatum = gintuple_get_key(btree->ginstate, itup,
     279             :                                             &newCategory);
     280             : 
     281           0 :                 if (ginCompareEntries(btree->ginstate, attnum,
     282             :                                       newDatum, newCategory,
     283             :                                       idatum, icategory) == 0)
     284           0 :                     break;      /* Found! */
     285             : 
     286           0 :                 stack->off++;
     287             :             }
     288             : 
     289           0 :             if (icategory == GIN_CAT_NORM_KEY && !attr->attbyval)
     290           0 :                 pfree(DatumGetPointer(idatum));
     291             :         }
     292             :         else
     293             :         {
     294             :             ItemPointer ipd;
     295             :             int         nipd;
     296             : 
     297       76134 :             ipd = ginReadTuple(btree->ginstate, scanEntry->attnum, itup, &nipd);
     298       76134 :             tbm_add_tuples(scanEntry->matchBitmap, ipd, nipd, false);
     299       76134 :             scanEntry->predictNumberResult += GinGetNPosting(itup);
     300       76134 :             pfree(ipd);
     301             :         }
     302             : 
     303             :         /*
     304             :          * Done with this entry, go to the next
     305             :          */
     306       76134 :         stack->off++;
     307             :     }
     308             : }
     309             : 
     310             : /*
     311             :  * Start* functions setup beginning state of searches: finds correct buffer and pins it.
     312             :  */
     313             : static void
     314        2600 : startScanEntry(GinState *ginstate, GinScanEntry entry, Snapshot snapshot)
     315             : {
     316             :     GinBtreeData btreeEntry;
     317             :     GinBtreeStack *stackEntry;
     318             :     Page        page;
     319             :     bool        needUnlock;
     320             : 
     321             : restartScanEntry:
     322        2600 :     entry->buffer = InvalidBuffer;
     323        2600 :     ItemPointerSetMin(&entry->curItem);
     324        2600 :     entry->offset = InvalidOffsetNumber;
     325        2600 :     if (entry->list)
     326           0 :         pfree(entry->list);
     327        2600 :     entry->list = NULL;
     328        2600 :     entry->nlist = 0;
     329        2600 :     entry->matchBitmap = NULL;
     330        2600 :     entry->matchResult = NULL;
     331        2600 :     entry->reduceResult = false;
     332        2600 :     entry->predictNumberResult = 0;
     333             : 
     334             :     /*
     335             :      * we should find entry, and begin scan of posting tree or just store
     336             :      * posting list in memory
     337             :      */
     338        2600 :     ginPrepareEntryScan(&btreeEntry, entry->attnum,
     339        2600 :                         entry->queryKey, entry->queryCategory,
     340             :                         ginstate);
     341        2600 :     stackEntry = ginFindLeafPage(&btreeEntry, true, false, snapshot);
     342        2600 :     page = BufferGetPage(stackEntry->buffer);
     343             : 
     344             :     /* ginFindLeafPage() will have already checked snapshot age. */
     345        2600 :     needUnlock = true;
     346             : 
     347        2600 :     entry->isFinished = true;
     348             : 
     349        4952 :     if (entry->isPartialMatch ||
     350        2352 :         entry->queryCategory == GIN_CAT_EMPTY_QUERY)
     351             :     {
     352             :         /*
     353             :          * btreeEntry.findItem locates the first item >= given search key.
     354             :          * (For GIN_CAT_EMPTY_QUERY, it will find the leftmost index item
     355             :          * because of the way the GIN_CAT_EMPTY_QUERY category code is
     356             :          * assigned.)  We scan forward from there and collect all TIDs needed
     357             :          * for the entry type.
     358             :          */
     359         328 :         btreeEntry.findItem(&btreeEntry, stackEntry);
     360         656 :         if (collectMatchBitmap(&btreeEntry, stackEntry, entry, snapshot)
     361         328 :             == false)
     362             :         {
     363             :             /*
     364             :              * GIN tree was seriously restructured, so we will cleanup all
     365             :              * found data and rescan. See comments near 'return false' in
     366             :              * collectMatchBitmap()
     367             :              */
     368           0 :             if (entry->matchBitmap)
     369             :             {
     370           0 :                 if (entry->matchIterator)
     371           0 :                     tbm_end_iterate(entry->matchIterator);
     372           0 :                 entry->matchIterator = NULL;
     373           0 :                 tbm_free(entry->matchBitmap);
     374           0 :                 entry->matchBitmap = NULL;
     375             :             }
     376           0 :             LockBuffer(stackEntry->buffer, GIN_UNLOCK);
     377           0 :             freeGinBtreeStack(stackEntry);
     378           0 :             goto restartScanEntry;
     379             :         }
     380             : 
     381         656 :         if (entry->matchBitmap && !tbm_is_empty(entry->matchBitmap))
     382             :         {
     383         320 :             entry->matchIterator = tbm_begin_iterate(entry->matchBitmap);
     384         320 :             entry->isFinished = false;
     385             :         }
     386             :     }
     387        2272 :     else if (btreeEntry.findItem(&btreeEntry, stackEntry))
     388             :     {
     389        1446 :         IndexTuple  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stackEntry->off));
     390             : 
     391        1446 :         if (GinIsPostingTree(itup))
     392             :         {
     393          30 :             BlockNumber rootPostingTree = GinGetPostingTree(itup);
     394             :             GinBtreeStack *stack;
     395             :             Page        page;
     396             :             ItemPointerData minItem;
     397             : 
     398             :             /*
     399             :              * This is an equality scan, so lock the root of the posting tree.
     400             :              * It represents a lock on the exact key value, and covers all the
     401             :              * items in the posting tree.
     402             :              */
     403          30 :             PredicateLockPage(ginstate->index, rootPostingTree, snapshot);
     404             : 
     405             :             /*
     406             :              * We should unlock entry page before touching posting tree to
     407             :              * prevent deadlocks with vacuum processes. Because entry is never
     408             :              * deleted from page and posting tree is never reduced to the
     409             :              * posting list, we can unlock page after getting BlockNumber of
     410             :              * root of posting tree.
     411             :              */
     412          30 :             LockBuffer(stackEntry->buffer, GIN_UNLOCK);
     413          30 :             needUnlock = false;
     414             : 
     415          30 :             stack = ginScanBeginPostingTree(&entry->btree, ginstate->index,
     416             :                                             rootPostingTree, snapshot);
     417          30 :             entry->buffer = stack->buffer;
     418             : 
     419             :             /*
     420             :              * We keep buffer pinned because we need to prevent deletion of
     421             :              * page during scan. See GIN's vacuum implementation. RefCount is
     422             :              * increased to keep buffer pinned after freeGinBtreeStack() call.
     423             :              */
     424          30 :             IncrBufferRefCount(entry->buffer);
     425             : 
     426          30 :             page = BufferGetPage(entry->buffer);
     427             : 
     428             :             /*
     429             :              * Load the first page into memory.
     430             :              */
     431          30 :             ItemPointerSetMin(&minItem);
     432          30 :             entry->list = GinDataLeafPageGetItems(page, &entry->nlist, minItem);
     433             : 
     434          30 :             entry->predictNumberResult = stack->predictNumber * entry->nlist;
     435             : 
     436          30 :             LockBuffer(entry->buffer, GIN_UNLOCK);
     437          30 :             freeGinBtreeStack(stack);
     438          30 :             entry->isFinished = false;
     439             :         }
     440             :         else
     441             :         {
     442             :             /*
     443             :              * Lock the entry leaf page.  This is more coarse-grained than
     444             :              * necessary, because it will conflict with any insertions that
     445             :              * land on the same leaf page, not only the exact key we searched
     446             :              * for.  But locking an individual tuple would require updating
     447             :              * that lock whenever it moves because of insertions or vacuums,
     448             :              * which seems too complicated.
     449             :              */
     450        1416 :             PredicateLockPage(ginstate->index,
     451             :                               BufferGetBlockNumber(stackEntry->buffer),
     452             :                               snapshot);
     453        1416 :             if (GinGetNPosting(itup) > 0)
     454             :             {
     455        1416 :                 entry->list = ginReadTuple(ginstate, entry->attnum, itup,
     456             :                                            &entry->nlist);
     457        1416 :                 entry->predictNumberResult = entry->nlist;
     458             : 
     459        1416 :                 entry->isFinished = false;
     460             :             }
     461             :         }
     462             :     }
     463             :     else
     464             :     {
     465             :         /*
     466             :          * No entry found.  Predicate lock the leaf page, to lock the place
     467             :          * where the entry would've been, had there been one.
     468             :          */
     469         826 :         PredicateLockPage(ginstate->index,
     470             :                           BufferGetBlockNumber(stackEntry->buffer), snapshot);
     471             :     }
     472             : 
     473        2600 :     if (needUnlock)
     474        2570 :         LockBuffer(stackEntry->buffer, GIN_UNLOCK);
     475        2600 :     freeGinBtreeStack(stackEntry);
     476        2600 : }
     477             : 
     478             : /*
     479             :  * Comparison function for scan entry indexes. Sorts by predictNumberResult,
     480             :  * least frequent items first.
     481             :  */
     482             : static int
     483        2772 : entryIndexByFrequencyCmp(const void *a1, const void *a2, void *arg)
     484             : {
     485        2772 :     const GinScanKey key = (const GinScanKey) arg;
     486        2772 :     int         i1 = *(const int *) a1;
     487        2772 :     int         i2 = *(const int *) a2;
     488        2772 :     uint32      n1 = key->scanEntry[i1]->predictNumberResult;
     489        2772 :     uint32      n2 = key->scanEntry[i2]->predictNumberResult;
     490             : 
     491        2772 :     if (n1 < n2)
     492         374 :         return -1;
     493        2398 :     else if (n1 == n2)
     494         990 :         return 0;
     495             :     else
     496        1408 :         return 1;
     497             : }
     498             : 
     499             : static void
     500        1010 : startScanKey(GinState *ginstate, GinScanOpaque so, GinScanKey key)
     501             : {
     502        1010 :     MemoryContext oldCtx = CurrentMemoryContext;
     503             :     int         i;
     504             :     int         j;
     505             :     int        *entryIndexes;
     506             : 
     507        1010 :     ItemPointerSetMin(&key->curItem);
     508        1010 :     key->curItemMatches = false;
     509        1010 :     key->recheckCurItem = false;
     510        1010 :     key->isFinished = false;
     511             : 
     512             :     /*
     513             :      * Divide the entries into two distinct sets: required and additional.
     514             :      * Additional entries are not enough for a match alone, without any items
     515             :      * from the required set, but are needed by the consistent function to
     516             :      * decide if an item matches. When scanning, we can skip over items from
     517             :      * additional entries that have no corresponding matches in any of the
     518             :      * required entries. That speeds up queries like "frequent & rare"
     519             :      * considerably, if the frequent term can be put in the additional set.
     520             :      *
     521             :      * There can be many legal ways to divide them entries into these two
     522             :      * sets. A conservative division is to just put everything in the required
     523             :      * set, but the more you can put in the additional set, the more you can
     524             :      * skip during the scan. To maximize skipping, we try to put as many
     525             :      * frequent items as possible into additional, and less frequent ones into
     526             :      * required. To do that, sort the entries by frequency
     527             :      * (predictNumberResult), and put entries into the required set in that
     528             :      * order, until the consistent function says that none of the remaining
     529             :      * entries can form a match, without any items from the required set. The
     530             :      * rest go to the additional set.
     531             :      */
     532        1010 :     if (key->nentries > 1)
     533             :     {
     534         332 :         MemoryContextSwitchTo(so->tempCtx);
     535             : 
     536         332 :         entryIndexes = (int *) palloc(sizeof(int) * key->nentries);
     537        2254 :         for (i = 0; i < key->nentries; i++)
     538        1922 :             entryIndexes[i] = i;
     539         332 :         qsort_arg(entryIndexes, key->nentries, sizeof(int),
     540             :                   entryIndexByFrequencyCmp, key);
     541             : 
     542        1474 :         for (i = 0; i < key->nentries - 1; i++)
     543             :         {
     544             :             /* Pass all entries <= i as FALSE, and the rest as MAYBE */
     545       68884 :             for (j = 0; j <= i; j++)
     546       67470 :                 key->entryRes[entryIndexes[j]] = GIN_FALSE;
     547       69540 :             for (j = i + 1; j < key->nentries; j++)
     548       68126 :                 key->entryRes[entryIndexes[j]] = GIN_MAYBE;
     549             : 
     550        1414 :             if (key->triConsistentFn(key) == GIN_FALSE)
     551         272 :                 break;
     552             :         }
     553             :         /* i is now the last required entry. */
     554             : 
     555         332 :         MemoryContextSwitchTo(so->keyCtx);
     556             : 
     557         332 :         key->nrequired = i + 1;
     558         332 :         key->nadditional = key->nentries - key->nrequired;
     559         332 :         key->requiredEntries = palloc(key->nrequired * sizeof(GinScanEntry));
     560         332 :         key->additionalEntries = palloc(key->nadditional * sizeof(GinScanEntry));
     561             : 
     562         332 :         j = 0;
     563        1806 :         for (i = 0; i < key->nrequired; i++)
     564        1474 :             key->requiredEntries[i] = key->scanEntry[entryIndexes[j++]];
     565         780 :         for (i = 0; i < key->nadditional; i++)
     566         448 :             key->additionalEntries[i] = key->scanEntry[entryIndexes[j++]];
     567             : 
     568             :         /* clean up after consistentFn calls (also frees entryIndexes) */
     569         332 :         MemoryContextReset(so->tempCtx);
     570             :     }
     571             :     else
     572             :     {
     573         678 :         MemoryContextSwitchTo(so->keyCtx);
     574             : 
     575         678 :         key->nrequired = 1;
     576         678 :         key->nadditional = 0;
     577         678 :         key->requiredEntries = palloc(1 * sizeof(GinScanEntry));
     578         678 :         key->requiredEntries[0] = key->scanEntry[0];
     579             :     }
     580        1010 :     MemoryContextSwitchTo(oldCtx);
     581        1010 : }
     582             : 
     583             : static void
     584        1002 : startScan(IndexScanDesc scan)
     585             : {
     586        1002 :     GinScanOpaque so = (GinScanOpaque) scan->opaque;
     587        1002 :     GinState   *ginstate = &so->ginstate;
     588             :     uint32      i;
     589             : 
     590        3602 :     for (i = 0; i < so->totalentries; i++)
     591        2600 :         startScanEntry(ginstate, so->entries[i], scan->xs_snapshot);
     592             : 
     593        1002 :     if (GinFuzzySearchLimit > 0)
     594             :     {
     595             :         /*
     596             :          * If all of keys more than threshold we will try to reduce result, we
     597             :          * hope (and only hope, for intersection operation of array our
     598             :          * supposition isn't true), that total result will not more than
     599             :          * minimal predictNumberResult.
     600             :          */
     601           0 :         bool        reduce = true;
     602             : 
     603           0 :         for (i = 0; i < so->totalentries; i++)
     604             :         {
     605           0 :             if (so->entries[i]->predictNumberResult <= so->totalentries * GinFuzzySearchLimit)
     606             :             {
     607           0 :                 reduce = false;
     608           0 :                 break;
     609             :             }
     610             :         }
     611           0 :         if (reduce)
     612             :         {
     613           0 :             for (i = 0; i < so->totalentries; i++)
     614             :             {
     615           0 :                 so->entries[i]->predictNumberResult /= so->totalentries;
     616           0 :                 so->entries[i]->reduceResult = true;
     617             :             }
     618             :         }
     619             :     }
     620             : 
     621             :     /*
     622             :      * Now that we have the estimates for the entry frequencies, finish
     623             :      * initializing the scan keys.
     624             :      */
     625        2012 :     for (i = 0; i < so->nkeys; i++)
     626        1010 :         startScanKey(ginstate, so, so->keys + i);
     627        1002 : }
     628             : 
     629             : /*
     630             :  * Load the next batch of item pointers from a posting tree.
     631             :  *
     632             :  * Note that we copy the page into GinScanEntry->list array and unlock it, but
     633             :  * keep it pinned to prevent interference with vacuum.
     634             :  */
     635             : static void
     636          38 : entryLoadMoreItems(GinState *ginstate, GinScanEntry entry,
     637             :                    ItemPointerData advancePast, Snapshot snapshot)
     638             : {
     639             :     Page        page;
     640             :     int         i;
     641             :     bool        stepright;
     642             : 
     643          38 :     if (!BufferIsValid(entry->buffer))
     644             :     {
     645           0 :         entry->isFinished = true;
     646           0 :         return;
     647             :     }
     648             : 
     649             :     /*
     650             :      * We have two strategies for finding the correct page: step right from
     651             :      * the current page, or descend the tree again from the root. If
     652             :      * advancePast equals the current item, the next matching item should be
     653             :      * on the next page, so we step right. Otherwise, descend from root.
     654             :      */
     655          38 :     if (ginCompareItemPointers(&entry->curItem, &advancePast) == 0)
     656             :     {
     657          38 :         stepright = true;
     658          38 :         LockBuffer(entry->buffer, GIN_SHARE);
     659             :     }
     660             :     else
     661             :     {
     662             :         GinBtreeStack *stack;
     663             : 
     664           0 :         ReleaseBuffer(entry->buffer);
     665             : 
     666             :         /*
     667             :          * Set the search key, and find the correct leaf page.
     668             :          */
     669           0 :         if (ItemPointerIsLossyPage(&advancePast))
     670             :         {
     671           0 :             ItemPointerSet(&entry->btree.itemptr,
     672             :                            GinItemPointerGetBlockNumber(&advancePast) + 1,
     673             :                            FirstOffsetNumber);
     674             :         }
     675             :         else
     676             :         {
     677           0 :             ItemPointerSet(&entry->btree.itemptr,
     678             :                            GinItemPointerGetBlockNumber(&advancePast),
     679             :                            OffsetNumberNext(GinItemPointerGetOffsetNumber(&advancePast)));
     680             :         }
     681           0 :         entry->btree.fullScan = false;
     682           0 :         stack = ginFindLeafPage(&entry->btree, true, false, snapshot);
     683             : 
     684             :         /* we don't need the stack, just the buffer. */
     685           0 :         entry->buffer = stack->buffer;
     686           0 :         IncrBufferRefCount(entry->buffer);
     687           0 :         freeGinBtreeStack(stack);
     688           0 :         stepright = false;
     689             :     }
     690             : 
     691          38 :     elog(DEBUG2, "entryLoadMoreItems, %u/%u, skip: %d",
     692             :          GinItemPointerGetBlockNumber(&advancePast),
     693             :          GinItemPointerGetOffsetNumber(&advancePast),
     694             :          !stepright);
     695             : 
     696          38 :     page = BufferGetPage(entry->buffer);
     697             :     for (;;)
     698             :     {
     699          38 :         entry->offset = InvalidOffsetNumber;
     700          38 :         if (entry->list)
     701             :         {
     702          38 :             pfree(entry->list);
     703          38 :             entry->list = NULL;
     704          38 :             entry->nlist = 0;
     705             :         }
     706             : 
     707          38 :         if (stepright)
     708             :         {
     709             :             /*
     710             :              * We've processed all the entries on this page. If it was the
     711             :              * last page in the tree, we're done.
     712             :              */
     713          38 :             if (GinPageRightMost(page))
     714             :             {
     715           0 :                 UnlockReleaseBuffer(entry->buffer);
     716           0 :                 entry->buffer = InvalidBuffer;
     717           0 :                 entry->isFinished = true;
     718           0 :                 return;
     719             :             }
     720             : 
     721             :             /*
     722             :              * Step to next page, following the right link. then find the
     723             :              * first ItemPointer greater than advancePast.
     724             :              */
     725          38 :             entry->buffer = ginStepRight(entry->buffer,
     726             :                                          ginstate->index,
     727             :                                          GIN_SHARE);
     728          38 :             page = BufferGetPage(entry->buffer);
     729             :         }
     730          38 :         stepright = true;
     731             : 
     732          38 :         if (GinPageGetOpaque(page)->flags & GIN_DELETED)
     733           0 :             continue;           /* page was deleted by concurrent vacuum */
     734             : 
     735             :         /*
     736             :          * The first item > advancePast might not be on this page, but
     737             :          * somewhere to the right, if the page was split, or a non-match from
     738             :          * another key in the query allowed us to skip some items from this
     739             :          * entry. Keep following the right-links until we re-find the correct
     740             :          * page.
     741             :          */
     742          46 :         if (!GinPageRightMost(page) &&
     743           8 :             ginCompareItemPointers(&advancePast, GinDataPageGetRightBound(page)) >= 0)
     744             :         {
     745             :             /*
     746             :              * the item we're looking is > the right bound of the page, so it
     747             :              * can't be on this page.
     748             :              */
     749           0 :             continue;
     750             :         }
     751             : 
     752          38 :         entry->list = GinDataLeafPageGetItems(page, &entry->nlist, advancePast);
     753             : 
     754          38 :         for (i = 0; i < entry->nlist; i++)
     755             :         {
     756          38 :             if (ginCompareItemPointers(&advancePast, &entry->list[i]) < 0)
     757             :             {
     758          38 :                 entry->offset = i;
     759             : 
     760          38 :                 if (GinPageRightMost(page))
     761             :                 {
     762             :                     /* after processing the copied items, we're done. */
     763          30 :                     UnlockReleaseBuffer(entry->buffer);
     764          30 :                     entry->buffer = InvalidBuffer;
     765             :                 }
     766             :                 else
     767           8 :                     LockBuffer(entry->buffer, GIN_UNLOCK);
     768          38 :                 return;
     769             :             }
     770             :         }
     771             :     }
     772             : }
     773             : 
     774             : #define gin_rand() (((double) random()) / ((double) MAX_RANDOM_VALUE))
     775             : #define dropItem(e) ( gin_rand() > ((double)GinFuzzySearchLimit)/((double)((e)->predictNumberResult)) )
     776             : 
     777             : /*
     778             :  * Sets entry->curItem to next heap item pointer > advancePast, for one entry
     779             :  * of one scan key, or sets entry->isFinished to true if there are no more.
     780             :  *
     781             :  * Item pointers are returned in ascending order.
     782             :  *
     783             :  * Note: this can return a "lossy page" item pointer, indicating that the
     784             :  * entry potentially matches all items on that heap page.  However, it is
     785             :  * not allowed to return both a lossy page pointer and exact (regular)
     786             :  * item pointers for the same page.  (Doing so would break the key-combination
     787             :  * logic in keyGetItem and scanGetItem; see comment in scanGetItem.)  In the
     788             :  * current implementation this is guaranteed by the behavior of tidbitmaps.
     789             :  */
     790             : static void
     791      549708 : entryGetItem(GinState *ginstate, GinScanEntry entry,
     792             :              ItemPointerData advancePast, Snapshot snapshot)
     793             : {
     794             :     Assert(!entry->isFinished);
     795             : 
     796             :     Assert(!ItemPointerIsValid(&entry->curItem) ||
     797             :            ginCompareItemPointers(&entry->curItem, &advancePast) <= 0);
     798             : 
     799      549708 :     if (entry->matchBitmap)
     800             :     {
     801             :         /* A bitmap result */
     802       91406 :         BlockNumber advancePastBlk = GinItemPointerGetBlockNumber(&advancePast);
     803       91406 :         OffsetNumber advancePastOff = GinItemPointerGetOffsetNumber(&advancePast);
     804       91406 :         bool        gotitem = false;
     805             : 
     806             :         do
     807             :         {
     808             :             /*
     809             :              * If we've exhausted all items on this block, move to next block
     810             :              * in the bitmap.
     811             :              */
     812      277178 :             while (entry->matchResult == NULL ||
     813      185452 :                    (entry->matchResult->ntuples >= 0 &&
     814      183812 :                     entry->offset >= entry->matchResult->ntuples) ||
     815      182172 :                    entry->matchResult->blockno < advancePastBlk ||
     816       91086 :                    (ItemPointerIsLossyPage(&advancePast) &&
     817           0 :                     entry->matchResult->blockno == advancePastBlk))
     818             :             {
     819        1960 :                 entry->matchResult = tbm_iterate(entry->matchIterator);
     820             : 
     821        1960 :                 if (entry->matchResult == NULL)
     822             :                 {
     823         320 :                     ItemPointerSetInvalid(&entry->curItem);
     824         320 :                     tbm_end_iterate(entry->matchIterator);
     825         320 :                     entry->matchIterator = NULL;
     826         320 :                     entry->isFinished = true;
     827         320 :                     break;
     828             :                 }
     829             : 
     830             :                 /*
     831             :                  * Reset counter to the beginning of entry->matchResult. Note:
     832             :                  * entry->offset is still greater than matchResult->ntuples if
     833             :                  * matchResult is lossy.  So, on next call we will get next
     834             :                  * result from TIDBitmap.
     835             :                  */
     836        1640 :                 entry->offset = 0;
     837             :             }
     838       91406 :             if (entry->isFinished)
     839         320 :                 break;
     840             : 
     841             :             /*
     842             :              * We're now on the first page after advancePast which has any
     843             :              * items on it. If it's a lossy result, return that.
     844             :              */
     845       91086 :             if (entry->matchResult->ntuples < 0)
     846             :             {
     847           0 :                 ItemPointerSetLossyPage(&entry->curItem,
     848             :                                         entry->matchResult->blockno);
     849             : 
     850             :                 /*
     851             :                  * We might as well fall out of the loop; we could not
     852             :                  * estimate number of results on this page to support correct
     853             :                  * reducing of result even if it's enabled.
     854             :                  */
     855           0 :                 gotitem = true;
     856           0 :                 break;
     857             :             }
     858             : 
     859             :             /*
     860             :              * Not a lossy page. Skip over any offsets <= advancePast, and
     861             :              * return that.
     862             :              */
     863       91086 :             if (entry->matchResult->blockno == advancePastBlk)
     864             :             {
     865             :                 /*
     866             :                  * First, do a quick check against the last offset on the
     867             :                  * page. If that's > advancePast, so are all the other
     868             :                  * offsets.
     869             :                  */
     870       89766 :                 if (entry->matchResult->offsets[entry->matchResult->ntuples - 1] <= advancePastOff)
     871             :                 {
     872           0 :                     entry->offset = entry->matchResult->ntuples;
     873           0 :                     continue;
     874             :                 }
     875             : 
     876             :                 /* Otherwise scan to find the first item > advancePast */
     877      179532 :                 while (entry->matchResult->offsets[entry->offset] <= advancePastOff)
     878           0 :                     entry->offset++;
     879             :             }
     880             : 
     881       91086 :             ItemPointerSet(&entry->curItem,
     882             :                            entry->matchResult->blockno,
     883             :                            entry->matchResult->offsets[entry->offset]);
     884       91086 :             entry->offset++;
     885       91086 :             gotitem = true;
     886       91086 :         } while (!gotitem || (entry->reduceResult == true && dropItem(entry)));
     887             :     }
     888      458302 :     else if (!BufferIsValid(entry->buffer))
     889             :     {
     890             :         /*
     891             :          * A posting list from an entry tuple, or the last page of a posting
     892             :          * tree.
     893             :          */
     894             :         do
     895             :         {
     896      213950 :             if (entry->offset >= entry->nlist)
     897             :             {
     898        1154 :                 ItemPointerSetInvalid(&entry->curItem);
     899        1154 :                 entry->isFinished = true;
     900        1154 :                 break;
     901             :             }
     902             : 
     903      212796 :             entry->curItem = entry->list[entry->offset++];
     904      212796 :         } while (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0);
     905             :         /* XXX: shouldn't we apply the fuzzy search limit here? */
     906             :     }
     907             :     else
     908             :     {
     909             :         /* A posting tree */
     910             :         do
     911             :         {
     912             :             /* If we've processed the current batch, load more items */
     913      570354 :             while (entry->offset >= entry->nlist)
     914             :             {
     915          38 :                 entryLoadMoreItems(ginstate, entry, advancePast, snapshot);
     916             : 
     917          38 :                 if (entry->isFinished)
     918             :                 {
     919           0 :                     ItemPointerSetInvalid(&entry->curItem);
     920           0 :                     return;
     921             :                 }
     922             :             }
     923             : 
     924      285158 :             entry->curItem = entry->list[entry->offset++];
     925             : 
     926      570316 :         } while (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0 ||
     927      285158 :                  (entry->reduceResult == true && dropItem(entry)));
     928             :     }
     929             : }
     930             : 
     931             : /*
     932             :  * Identify the "current" item among the input entry streams for this scan key
     933             :  * that is greater than advancePast, and test whether it passes the scan key
     934             :  * qual condition.
     935             :  *
     936             :  * The current item is the smallest curItem among the inputs.  key->curItem
     937             :  * is set to that value.  key->curItemMatches is set to indicate whether that
     938             :  * TID passes the consistentFn test.  If so, key->recheckCurItem is set true
     939             :  * iff recheck is needed for this item pointer (including the case where the
     940             :  * item pointer is a lossy page pointer).
     941             :  *
     942             :  * If all entry streams are exhausted, sets key->isFinished to true.
     943             :  *
     944             :  * Item pointers must be returned in ascending order.
     945             :  *
     946             :  * Note: this can return a "lossy page" item pointer, indicating that the
     947             :  * key potentially matches all items on that heap page.  However, it is
     948             :  * not allowed to return both a lossy page pointer and exact (regular)
     949             :  * item pointers for the same page.  (Doing so would break the key-combination
     950             :  * logic in scanGetItem.)
     951             :  */
     952             : static void
     953      479634 : keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key,
     954             :            ItemPointerData advancePast, Snapshot snapshot)
     955             : {
     956             :     ItemPointerData minItem;
     957             :     ItemPointerData curPageLossy;
     958             :     uint32      i;
     959             :     bool        haveLossyEntry;
     960             :     GinScanEntry entry;
     961             :     GinTernaryValue res;
     962             :     MemoryContext oldCtx;
     963             :     bool        allFinished;
     964             : 
     965             :     Assert(!key->isFinished);
     966             : 
     967             :     /*
     968             :      * We might have already tested this item; if so, no need to repeat work.
     969             :      * (Note: the ">" case can happen, if advancePast is exact but we
     970             :      * previously had to set curItem to a lossy-page pointer.)
     971             :      */
     972      479634 :     if (ginCompareItemPointers(&key->curItem, &advancePast) > 0)
     973        1018 :         return;
     974             : 
     975             :     /*
     976             :      * Find the minimum item > advancePast among the active entry streams.
     977             :      *
     978             :      * Note: a lossy-page entry is encoded by a ItemPointer with max value for
     979             :      * offset (0xffff), so that it will sort after any exact entries for the
     980             :      * same page.  So we'll prefer to return exact pointers not lossy
     981             :      * pointers, which is good.
     982             :      */
     983      479626 :     ItemPointerSetMax(&minItem);
     984      479626 :     allFinished = true;
     985     1633908 :     for (i = 0; i < key->nrequired; i++)
     986             :     {
     987     1154282 :         entry = key->requiredEntries[i];
     988             : 
     989     1154282 :         if (entry->isFinished)
     990      522878 :             continue;
     991             : 
     992             :         /*
     993             :          * Advance this stream if necessary.
     994             :          *
     995             :          * In particular, since entry->curItem was initialized with
     996             :          * ItemPointerSetMin, this ensures we fetch the first item for each
     997             :          * entry on the first call.
     998             :          */
     999      631404 :         if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
    1000             :         {
    1001      506096 :             entryGetItem(ginstate, entry, advancePast, snapshot);
    1002      506096 :             if (entry->isFinished)
    1003        1326 :                 continue;
    1004             :         }
    1005             : 
    1006      630078 :         allFinished = false;
    1007      630078 :         if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
    1008      556064 :             minItem = entry->curItem;
    1009             :     }
    1010             : 
    1011      479626 :     if (allFinished)
    1012             :     {
    1013             :         /* all entries are finished */
    1014        1002 :         key->isFinished = true;
    1015        1002 :         return;
    1016             :     }
    1017             : 
    1018             :     /*
    1019             :      * Ok, we now know that there are no matches < minItem.
    1020             :      *
    1021             :      * If minItem is lossy, it means that there were no exact items on the
    1022             :      * page among requiredEntries, because lossy pointers sort after exact
    1023             :      * items. However, there might be exact items for the same page among
    1024             :      * additionalEntries, so we mustn't advance past them.
    1025             :      */
    1026      478624 :     if (ItemPointerIsLossyPage(&minItem))
    1027             :     {
    1028           0 :         if (GinItemPointerGetBlockNumber(&advancePast) <
    1029           0 :             GinItemPointerGetBlockNumber(&minItem))
    1030             :         {
    1031           0 :             ItemPointerSet(&advancePast,
    1032             :                            GinItemPointerGetBlockNumber(&minItem),
    1033             :                            InvalidOffsetNumber);
    1034             :         }
    1035             :     }
    1036             :     else
    1037             :     {
    1038             :         Assert(GinItemPointerGetOffsetNumber(&minItem) > 0);
    1039      478624 :         ItemPointerSet(&advancePast,
    1040             :                        GinItemPointerGetBlockNumber(&minItem),
    1041             :                        OffsetNumberPrev(GinItemPointerGetOffsetNumber(&minItem)));
    1042             :     }
    1043             : 
    1044             :     /*
    1045             :      * We might not have loaded all the entry streams for this TID yet. We
    1046             :      * could call the consistent function, passing MAYBE for those entries, to
    1047             :      * see if it can decide if this TID matches based on the information we
    1048             :      * have. But if the consistent-function is expensive, and cannot in fact
    1049             :      * decide with partial information, that could be a big loss. So, load all
    1050             :      * the additional entries, before calling the consistent function.
    1051             :      */
    1052      533022 :     for (i = 0; i < key->nadditional; i++)
    1053             :     {
    1054       54398 :         entry = key->additionalEntries[i];
    1055             : 
    1056       54398 :         if (entry->isFinished)
    1057         404 :             continue;
    1058             : 
    1059       53994 :         if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
    1060             :         {
    1061       43612 :             entryGetItem(ginstate, entry, advancePast, snapshot);
    1062       43612 :             if (entry->isFinished)
    1063         148 :                 continue;
    1064             :         }
    1065             : 
    1066             :         /*
    1067             :          * Normally, none of the items in additionalEntries can have a curItem
    1068             :          * larger than minItem. But if minItem is a lossy page, then there
    1069             :          * might be exact items on the same page among additionalEntries.
    1070             :          */
    1071       53846 :         if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
    1072             :         {
    1073             :             Assert(ItemPointerIsLossyPage(&minItem));
    1074           0 :             minItem = entry->curItem;
    1075             :         }
    1076             :     }
    1077             : 
    1078             :     /*
    1079             :      * Ok, we've advanced all the entries up to minItem now. Set key->curItem,
    1080             :      * and perform consistentFn test.
    1081             :      *
    1082             :      * Lossy-page entries pose a problem, since we don't know the correct
    1083             :      * entryRes state to pass to the consistentFn, and we also don't know what
    1084             :      * its combining logic will be (could be AND, OR, or even NOT). If the
    1085             :      * logic is OR then the consistentFn might succeed for all items in the
    1086             :      * lossy page even when none of the other entries match.
    1087             :      *
    1088             :      * Our strategy is to call the tri-state consistent function, with the
    1089             :      * lossy-page entries set to MAYBE, and all the other entries FALSE. If it
    1090             :      * returns FALSE, none of the lossy items alone are enough for a match, so
    1091             :      * we don't need to return a lossy-page pointer. Otherwise, return a
    1092             :      * lossy-page pointer to indicate that the whole heap page must be
    1093             :      * checked.  (On subsequent calls, we'll do nothing until minItem is past
    1094             :      * the page altogether, thus ensuring that we never return both regular
    1095             :      * and lossy pointers for the same page.)
    1096             :      *
    1097             :      * An exception is that it doesn't matter what we pass for lossy pointers
    1098             :      * in "hidden" entries, because the consistentFn's result can't depend on
    1099             :      * them. We could pass them as MAYBE as well, but if we're using the
    1100             :      * "shim" implementation of a tri-state consistent function (see
    1101             :      * ginlogic.c), it's better to pass as few MAYBEs as possible. So pass
    1102             :      * them as true.
    1103             :      *
    1104             :      * Note that only lossy-page entries pointing to the current item's page
    1105             :      * should trigger this processing; we might have future lossy pages in the
    1106             :      * entry array, but they aren't relevant yet.
    1107             :      */
    1108      478624 :     key->curItem = minItem;
    1109      478624 :     ItemPointerSetLossyPage(&curPageLossy,
    1110             :                             GinItemPointerGetBlockNumber(&key->curItem));
    1111      478624 :     haveLossyEntry = false;
    1112     1685160 :     for (i = 0; i < key->nentries; i++)
    1113             :     {
    1114     1206536 :         entry = key->scanEntry[i];
    1115     1890460 :         if (entry->isFinished == false &&
    1116      683924 :             ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0)
    1117             :         {
    1118           0 :             if (i < key->nuserentries)
    1119           0 :                 key->entryRes[i] = GIN_MAYBE;
    1120             :             else
    1121           0 :                 key->entryRes[i] = GIN_TRUE;
    1122           0 :             haveLossyEntry = true;
    1123             :         }
    1124             :         else
    1125     1206536 :             key->entryRes[i] = GIN_FALSE;
    1126             :     }
    1127             : 
    1128             :     /* prepare for calling consistentFn in temp context */
    1129      478624 :     oldCtx = MemoryContextSwitchTo(tempCtx);
    1130             : 
    1131      478624 :     if (haveLossyEntry)
    1132             :     {
    1133             :         /* Have lossy-page entries, so see if whole page matches */
    1134           0 :         res = key->triConsistentFn(key);
    1135             : 
    1136           0 :         if (res == GIN_TRUE || res == GIN_MAYBE)
    1137             :         {
    1138             :             /* Yes, so clean up ... */
    1139           0 :             MemoryContextSwitchTo(oldCtx);
    1140           0 :             MemoryContextReset(tempCtx);
    1141             : 
    1142             :             /* and return lossy pointer for whole page */
    1143           0 :             key->curItem = curPageLossy;
    1144           0 :             key->curItemMatches = true;
    1145           0 :             key->recheckCurItem = true;
    1146           0 :             return;
    1147             :         }
    1148             :     }
    1149             : 
    1150             :     /*
    1151             :      * At this point we know that we don't need to return a lossy whole-page
    1152             :      * pointer, but we might have matches for individual exact item pointers,
    1153             :      * possibly in combination with a lossy pointer. Pass lossy pointers as
    1154             :      * MAYBE to the ternary consistent function, to let it decide if this
    1155             :      * tuple satisfies the overall key, even though we don't know if the lossy
    1156             :      * entries match.
    1157             :      *
    1158             :      * Prepare entryRes array to be passed to consistentFn.
    1159             :      */
    1160     1685160 :     for (i = 0; i < key->nentries; i++)
    1161             :     {
    1162     1206536 :         entry = key->scanEntry[i];
    1163     1206536 :         if (entry->isFinished)
    1164      522612 :             key->entryRes[i] = GIN_FALSE;
    1165             : #if 0
    1166             : 
    1167             :         /*
    1168             :          * This case can't currently happen, because we loaded all the entries
    1169             :          * for this item earlier.
    1170             :          */
    1171             :         else if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
    1172             :             key->entryRes[i] = GIN_MAYBE;
    1173             : #endif
    1174      683924 :         else if (ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0)
    1175           0 :             key->entryRes[i] = GIN_MAYBE;
    1176      683924 :         else if (ginCompareItemPointers(&entry->curItem, &minItem) == 0)
    1177      540300 :             key->entryRes[i] = GIN_TRUE;
    1178             :         else
    1179      143624 :             key->entryRes[i] = GIN_FALSE;
    1180             :     }
    1181             : 
    1182      478624 :     res = key->triConsistentFn(key);
    1183             : 
    1184      478624 :     switch (res)
    1185             :     {
    1186             :         case GIN_TRUE:
    1187      390400 :             key->curItemMatches = true;
    1188             :             /* triConsistentFn set recheckCurItem */
    1189      390400 :             break;
    1190             : 
    1191             :         case GIN_FALSE:
    1192       13698 :             key->curItemMatches = false;
    1193       13698 :             break;
    1194             : 
    1195             :         case GIN_MAYBE:
    1196       74526 :             key->curItemMatches = true;
    1197       74526 :             key->recheckCurItem = true;
    1198       74526 :             break;
    1199             : 
    1200             :         default:
    1201             : 
    1202             :             /*
    1203             :              * the 'default' case shouldn't happen, but if the consistent
    1204             :              * function returns something bogus, this is the safe result
    1205             :              */
    1206           0 :             key->curItemMatches = true;
    1207           0 :             key->recheckCurItem = true;
    1208           0 :             break;
    1209             :     }
    1210             : 
    1211             :     /*
    1212             :      * We have a tuple, and we know if it matches or not. If it's a non-match,
    1213             :      * we could continue to find the next matching tuple, but let's break out
    1214             :      * and give scanGetItem a chance to advance the other keys. They might be
    1215             :      * able to skip past to a much higher TID, allowing us to save work.
    1216             :      */
    1217             : 
    1218             :     /* clean up after consistentFn calls */
    1219      478624 :     MemoryContextSwitchTo(oldCtx);
    1220      478624 :     MemoryContextReset(tempCtx);
    1221             : }
    1222             : 
    1223             : /*
    1224             :  * Get next heap item pointer (after advancePast) from scan.
    1225             :  * Returns true if anything found.
    1226             :  * On success, *item and *recheck are set.
    1227             :  *
    1228             :  * Note: this is very nearly the same logic as in keyGetItem(), except
    1229             :  * that we know the keys are to be combined with AND logic, whereas in
    1230             :  * keyGetItem() the combination logic is known only to the consistentFn.
    1231             :  */
    1232             : static bool
    1233      465864 : scanGetItem(IndexScanDesc scan, ItemPointerData advancePast,
    1234             :             ItemPointerData *item, bool *recheck)
    1235             : {
    1236      465864 :     GinScanOpaque so = (GinScanOpaque) scan->opaque;
    1237             :     uint32      i;
    1238             :     bool        match;
    1239             : 
    1240             :     /*----------
    1241             :      * Advance the scan keys in lock-step, until we find an item that matches
    1242             :      * all the keys. If any key reports isFinished, meaning its subset of the
    1243             :      * entries is exhausted, we can stop.  Otherwise, set *item to the next
    1244             :      * matching item.
    1245             :      *
    1246             :      * This logic works only if a keyGetItem stream can never contain both
    1247             :      * exact and lossy pointers for the same page.  Else we could have a
    1248             :      * case like
    1249             :      *
    1250             :      *      stream 1        stream 2
    1251             :      *      ...             ...
    1252             :      *      42/6            42/7
    1253             :      *      50/1            42/0xffff
    1254             :      *      ...             ...
    1255             :      *
    1256             :      * We would conclude that 42/6 is not a match and advance stream 1,
    1257             :      * thus never detecting the match to the lossy pointer in stream 2.
    1258             :      * (keyGetItem has a similar problem versus entryGetItem.)
    1259             :      *----------
    1260             :      */
    1261             :     do
    1262             :     {
    1263      479594 :         ItemPointerSetMin(item);
    1264      479594 :         match = true;
    1265      944528 :         for (i = 0; i < so->nkeys && match; i++)
    1266             :         {
    1267      479634 :             GinScanKey  key = so->keys + i;
    1268             : 
    1269             :             /* Fetch the next item for this key that is > advancePast. */
    1270      479634 :             keyGetItem(&so->ginstate, so->tempCtx, key, advancePast,
    1271             :                        scan->xs_snapshot);
    1272             : 
    1273      479634 :             if (key->isFinished)
    1274        1002 :                 return false;
    1275             : 
    1276             :             /*
    1277             :              * If it's not a match, we can immediately conclude that nothing
    1278             :              * <= this item matches, without checking the rest of the keys.
    1279             :              */
    1280      478632 :             if (!key->curItemMatches)
    1281             :             {
    1282       13698 :                 advancePast = key->curItem;
    1283       13698 :                 match = false;
    1284       13698 :                 break;
    1285             :             }
    1286             : 
    1287             :             /*
    1288             :              * It's a match. We can conclude that nothing < matches, so the
    1289             :              * other key streams can skip to this item.
    1290             :              *
    1291             :              * Beware of lossy pointers, though; from a lossy pointer, we can
    1292             :              * only conclude that nothing smaller than this *block* matches.
    1293             :              */
    1294      464934 :             if (ItemPointerIsLossyPage(&key->curItem))
    1295             :             {
    1296           0 :                 if (GinItemPointerGetBlockNumber(&advancePast) <
    1297           0 :                     GinItemPointerGetBlockNumber(&key->curItem))
    1298             :                 {
    1299           0 :                     ItemPointerSet(&advancePast,
    1300             :                                    GinItemPointerGetBlockNumber(&key->curItem),
    1301             :                                    InvalidOffsetNumber);
    1302             :                 }
    1303             :             }
    1304             :             else
    1305             :             {
    1306             :                 Assert(GinItemPointerGetOffsetNumber(&key->curItem) > 0);
    1307      464934 :                 ItemPointerSet(&advancePast,
    1308             :                                GinItemPointerGetBlockNumber(&key->curItem),
    1309             :                                OffsetNumberPrev(GinItemPointerGetOffsetNumber(&key->curItem)));
    1310             :             }
    1311             : 
    1312             :             /*
    1313             :              * If this is the first key, remember this location as a potential
    1314             :              * match, and proceed to check the rest of the keys.
    1315             :              *
    1316             :              * Otherwise, check if this is the same item that we checked the
    1317             :              * previous keys for (or a lossy pointer for the same page). If
    1318             :              * not, loop back to check the previous keys for this item (we
    1319             :              * will check this key again too, but keyGetItem returns quickly
    1320             :              * for that)
    1321             :              */
    1322      464934 :             if (i == 0)
    1323             :             {
    1324      464894 :                 *item = key->curItem;
    1325             :             }
    1326             :             else
    1327             :             {
    1328          80 :                 if (ItemPointerIsLossyPage(&key->curItem) ||
    1329          40 :                     ItemPointerIsLossyPage(item))
    1330             :                 {
    1331             :                     Assert(GinItemPointerGetBlockNumber(&key->curItem) >= GinItemPointerGetBlockNumber(item));
    1332           0 :                     match = (GinItemPointerGetBlockNumber(&key->curItem) ==
    1333           0 :                              GinItemPointerGetBlockNumber(item));
    1334             :                 }
    1335             :                 else
    1336             :                 {
    1337             :                     Assert(ginCompareItemPointers(&key->curItem, item) >= 0);
    1338          40 :                     match = (ginCompareItemPointers(&key->curItem, item) == 0);
    1339             :                 }
    1340             :             }
    1341             :         }
    1342      478592 :     } while (!match);
    1343             : 
    1344             :     Assert(!ItemPointerIsMin(item));
    1345             : 
    1346             :     /*
    1347             :      * Now *item contains the first ItemPointer after previous result that
    1348             :      * satisfied all the keys for that exact TID, or a lossy reference to the
    1349             :      * same page.
    1350             :      *
    1351             :      * We must return recheck = true if any of the keys are marked recheck.
    1352             :      */
    1353      464862 :     *recheck = false;
    1354      853896 :     for (i = 0; i < so->nkeys; i++)
    1355             :     {
    1356      464870 :         GinScanKey  key = so->keys + i;
    1357             : 
    1358      464870 :         if (key->recheckCurItem)
    1359             :         {
    1360       75836 :             *recheck = true;
    1361       75836 :             break;
    1362             :         }
    1363             :     }
    1364             : 
    1365      464862 :     return true;
    1366             : }
    1367             : 
    1368             : 
    1369             : /*
    1370             :  * Functions for scanning the pending list
    1371             :  */
    1372             : 
    1373             : 
    1374             : /*
    1375             :  * Get ItemPointer of next heap row to be checked from pending list.
    1376             :  * Returns false if there are no more. On pages with several heap rows
    1377             :  * it returns each row separately, on page with part of heap row returns
    1378             :  * per page data.  pos->firstOffset and pos->lastOffset are set to identify
    1379             :  * the range of pending-list tuples belonging to this heap row.
    1380             :  *
    1381             :  * The pendingBuffer is presumed pinned and share-locked on entry, and is
    1382             :  * pinned and share-locked on success exit.  On failure exit it's released.
    1383             :  */
    1384             : static bool
    1385          56 : scanGetCandidate(IndexScanDesc scan, pendingPosition *pos)
    1386             : {
    1387             :     OffsetNumber maxoff;
    1388             :     Page        page;
    1389             :     IndexTuple  itup;
    1390             : 
    1391          56 :     ItemPointerSetInvalid(&pos->item);
    1392             :     for (;;)
    1393             :     {
    1394          56 :         page = BufferGetPage(pos->pendingBuffer);
    1395          56 :         TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
    1396             : 
    1397          56 :         maxoff = PageGetMaxOffsetNumber(page);
    1398          56 :         if (pos->firstOffset > maxoff)
    1399             :         {
    1400          16 :             BlockNumber blkno = GinPageGetOpaque(page)->rightlink;
    1401             : 
    1402          16 :             if (blkno == InvalidBlockNumber)
    1403             :             {
    1404          16 :                 UnlockReleaseBuffer(pos->pendingBuffer);
    1405          16 :                 pos->pendingBuffer = InvalidBuffer;
    1406             : 
    1407          16 :                 return false;
    1408             :             }
    1409             :             else
    1410             :             {
    1411             :                 /*
    1412             :                  * Here we must prevent deletion of next page by insertcleanup
    1413             :                  * process, which may be trying to obtain exclusive lock on
    1414             :                  * current page.  So, we lock next page before releasing the
    1415             :                  * current one
    1416             :                  */
    1417           0 :                 Buffer      tmpbuf = ReadBuffer(scan->indexRelation, blkno);
    1418             : 
    1419           0 :                 LockBuffer(tmpbuf, GIN_SHARE);
    1420           0 :                 UnlockReleaseBuffer(pos->pendingBuffer);
    1421             : 
    1422           0 :                 pos->pendingBuffer = tmpbuf;
    1423           0 :                 pos->firstOffset = FirstOffsetNumber;
    1424             :             }
    1425             :         }
    1426             :         else
    1427             :         {
    1428          40 :             itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->firstOffset));
    1429          40 :             pos->item = itup->t_tid;
    1430          40 :             if (GinPageHasFullRow(page))
    1431             :             {
    1432             :                 /*
    1433             :                  * find itempointer to the next row
    1434             :                  */
    1435          72 :                 for (pos->lastOffset = pos->firstOffset + 1; pos->lastOffset <= maxoff; pos->lastOffset++)
    1436             :                 {
    1437          56 :                     itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, pos->lastOffset));
    1438          56 :                     if (!ItemPointerEquals(&pos->item, &itup->t_tid))
    1439          24 :                         break;
    1440             :                 }
    1441             :             }
    1442             :             else
    1443             :             {
    1444             :                 /*
    1445             :                  * All itempointers are the same on this page
    1446             :                  */
    1447           0 :                 pos->lastOffset = maxoff + 1;
    1448             :             }
    1449             : 
    1450             :             /*
    1451             :              * Now pos->firstOffset points to the first tuple of current heap
    1452             :              * row, pos->lastOffset points to the first tuple of next heap row
    1453             :              * (or to the end of page)
    1454             :              */
    1455          40 :             break;
    1456             :         }
    1457             :     }
    1458             : 
    1459          40 :     return true;
    1460             : }
    1461             : 
    1462             : /*
    1463             :  * Scan pending-list page from current tuple (off) up till the first of:
    1464             :  * - match is found (then returns true)
    1465             :  * - no later match is possible
    1466             :  * - tuple's attribute number is not equal to entry's attrnum
    1467             :  * - reach end of page
    1468             :  *
    1469             :  * datum[]/category[]/datumExtracted[] arrays are used to cache the results
    1470             :  * of gintuple_get_key() on the current page.
    1471             :  */
    1472             : static bool
    1473           0 : matchPartialInPendingList(GinState *ginstate, Page page,
    1474             :                           OffsetNumber off, OffsetNumber maxoff,
    1475             :                           GinScanEntry entry,
    1476             :                           Datum *datum, GinNullCategory *category,
    1477             :                           bool *datumExtracted)
    1478             : {
    1479             :     IndexTuple  itup;
    1480             :     int32       cmp;
    1481             : 
    1482             :     /* Partial match to a null is not possible */
    1483           0 :     if (entry->queryCategory != GIN_CAT_NORM_KEY)
    1484           0 :         return false;
    1485             : 
    1486           0 :     while (off < maxoff)
    1487             :     {
    1488           0 :         itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
    1489             : 
    1490           0 :         if (gintuple_get_attrnum(ginstate, itup) != entry->attnum)
    1491           0 :             return false;
    1492             : 
    1493           0 :         if (datumExtracted[off - 1] == false)
    1494             :         {
    1495           0 :             datum[off - 1] = gintuple_get_key(ginstate, itup,
    1496           0 :                                               &category[off - 1]);
    1497           0 :             datumExtracted[off - 1] = true;
    1498             :         }
    1499             : 
    1500             :         /* Once we hit nulls, no further match is possible */
    1501           0 :         if (category[off - 1] != GIN_CAT_NORM_KEY)
    1502           0 :             return false;
    1503             : 
    1504             :         /*----------
    1505             :          * Check partial match.
    1506             :          * case cmp == 0 => match
    1507             :          * case cmp > 0 => not match and end scan (no later match possible)
    1508             :          * case cmp < 0 => not match and continue scan
    1509             :          *----------
    1510             :          */
    1511           0 :         cmp = DatumGetInt32(FunctionCall4Coll(&ginstate->comparePartialFn[entry->attnum - 1],
    1512             :                                               ginstate->supportCollation[entry->attnum - 1],
    1513             :                                               entry->queryKey,
    1514             :                                               datum[off - 1],
    1515             :                                               UInt16GetDatum(entry->strategy),
    1516             :                                               PointerGetDatum(entry->extra_data)));
    1517           0 :         if (cmp == 0)
    1518           0 :             return true;
    1519           0 :         else if (cmp > 0)
    1520           0 :             return false;
    1521             : 
    1522           0 :         off++;
    1523             :     }
    1524             : 
    1525           0 :     return false;
    1526             : }
    1527             : 
    1528             : /*
    1529             :  * Set up the entryRes array for each key by looking at
    1530             :  * every entry for current heap row in pending list.
    1531             :  *
    1532             :  * Returns true if each scan key has at least one entryRes match.
    1533             :  * This corresponds to the situations where the normal index search will
    1534             :  * try to apply the key's consistentFn.  (A tuple not meeting that requirement
    1535             :  * cannot be returned by the normal search since no entry stream will
    1536             :  * source its TID.)
    1537             :  *
    1538             :  * The pendingBuffer is presumed pinned and share-locked on entry.
    1539             :  */
    1540             : static bool
    1541          40 : collectMatchesForHeapRow(IndexScanDesc scan, pendingPosition *pos)
    1542             : {
    1543          40 :     GinScanOpaque so = (GinScanOpaque) scan->opaque;
    1544             :     OffsetNumber attrnum;
    1545             :     Page        page;
    1546             :     IndexTuple  itup;
    1547             :     int         i,
    1548             :                 j;
    1549             : 
    1550             :     /*
    1551             :      * Reset all entryRes and hasMatchKey flags
    1552             :      */
    1553          80 :     for (i = 0; i < so->nkeys; i++)
    1554             :     {
    1555          40 :         GinScanKey  key = so->keys + i;
    1556             : 
    1557          40 :         memset(key->entryRes, GIN_FALSE, key->nentries);
    1558             :     }
    1559          40 :     memset(pos->hasMatchKey, false, so->nkeys);
    1560             : 
    1561             :     /*
    1562             :      * Outer loop iterates over multiple pending-list pages when a single heap
    1563             :      * row has entries spanning those pages.
    1564             :      */
    1565             :     for (;;)
    1566           0 :     {
    1567             :         Datum       datum[BLCKSZ / sizeof(IndexTupleData)];
    1568             :         GinNullCategory category[BLCKSZ / sizeof(IndexTupleData)];
    1569             :         bool        datumExtracted[BLCKSZ / sizeof(IndexTupleData)];
    1570             : 
    1571             :         Assert(pos->lastOffset > pos->firstOffset);
    1572          40 :         memset(datumExtracted + pos->firstOffset - 1, 0,
    1573          40 :                sizeof(bool) * (pos->lastOffset - pos->firstOffset));
    1574             : 
    1575          40 :         page = BufferGetPage(pos->pendingBuffer);
    1576          40 :         TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
    1577             : 
    1578          80 :         for (i = 0; i < so->nkeys; i++)
    1579             :         {
    1580          40 :             GinScanKey  key = so->keys + i;
    1581             : 
    1582         120 :             for (j = 0; j < key->nentries; j++)
    1583             :             {
    1584          80 :                 GinScanEntry entry = key->scanEntry[j];
    1585          80 :                 OffsetNumber StopLow = pos->firstOffset,
    1586          80 :                             StopHigh = pos->lastOffset,
    1587             :                             StopMiddle;
    1588             : 
    1589             :                 /* If already matched on earlier page, do no extra work */
    1590          80 :                 if (key->entryRes[j])
    1591           0 :                     continue;
    1592             : 
    1593             :                 /*
    1594             :                  * Interesting tuples are from pos->firstOffset to
    1595             :                  * pos->lastOffset and they are ordered by (attnum, Datum) as
    1596             :                  * it's done in entry tree.  So we can use binary search to
    1597             :                  * avoid linear scanning.
    1598             :                  */
    1599         240 :                 while (StopLow < StopHigh)
    1600             :                 {
    1601             :                     int         res;
    1602             : 
    1603         112 :                     StopMiddle = StopLow + ((StopHigh - StopLow) >> 1);
    1604             : 
    1605         112 :                     itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, StopMiddle));
    1606             : 
    1607         112 :                     attrnum = gintuple_get_attrnum(&so->ginstate, itup);
    1608             : 
    1609         112 :                     if (key->attnum < attrnum)
    1610             :                     {
    1611           0 :                         StopHigh = StopMiddle;
    1612           0 :                         continue;
    1613             :                     }
    1614         112 :                     if (key->attnum > attrnum)
    1615             :                     {
    1616           0 :                         StopLow = StopMiddle + 1;
    1617           0 :                         continue;
    1618             :                     }
    1619             : 
    1620         112 :                     if (datumExtracted[StopMiddle - 1] == false)
    1621             :                     {
    1622         144 :                         datum[StopMiddle - 1] =
    1623          72 :                             gintuple_get_key(&so->ginstate, itup,
    1624          72 :                                              &category[StopMiddle - 1]);
    1625          72 :                         datumExtracted[StopMiddle - 1] = true;
    1626             :                     }
    1627             : 
    1628         112 :                     if (entry->queryCategory == GIN_CAT_EMPTY_QUERY)
    1629             :                     {
    1630             :                         /* special behavior depending on searchMode */
    1631           0 :                         if (entry->searchMode == GIN_SEARCH_MODE_ALL)
    1632             :                         {
    1633             :                             /* match anything except NULL_ITEM */
    1634           0 :                             if (category[StopMiddle - 1] == GIN_CAT_NULL_ITEM)
    1635           0 :                                 res = -1;
    1636             :                             else
    1637           0 :                                 res = 0;
    1638             :                         }
    1639             :                         else
    1640             :                         {
    1641             :                             /* match everything */
    1642           0 :                             res = 0;
    1643             :                         }
    1644             :                     }
    1645             :                     else
    1646             :                     {
    1647         448 :                         res = ginCompareEntries(&so->ginstate,
    1648         112 :                                                 entry->attnum,
    1649             :                                                 entry->queryKey,
    1650         112 :                                                 entry->queryCategory,
    1651         112 :                                                 datum[StopMiddle - 1],
    1652         112 :                                                 category[StopMiddle - 1]);
    1653             :                     }
    1654             : 
    1655         112 :                     if (res == 0)
    1656             :                     {
    1657             :                         /*
    1658             :                          * Found exact match (there can be only one, except in
    1659             :                          * EMPTY_QUERY mode).
    1660             :                          *
    1661             :                          * If doing partial match, scan forward from here to
    1662             :                          * end of page to check for matches.
    1663             :                          *
    1664             :                          * See comment above about tuple's ordering.
    1665             :                          */
    1666          32 :                         if (entry->isPartialMatch)
    1667           0 :                             key->entryRes[j] =
    1668           0 :                                 matchPartialInPendingList(&so->ginstate,
    1669             :                                                           page,
    1670             :                                                           StopMiddle,
    1671           0 :                                                           pos->lastOffset,
    1672             :                                                           entry,
    1673             :                                                           datum,
    1674             :                                                           category,
    1675             :                                                           datumExtracted);
    1676             :                         else
    1677          32 :                             key->entryRes[j] = true;
    1678             : 
    1679             :                         /* done with binary search */
    1680          32 :                         break;
    1681             :                     }
    1682          80 :                     else if (res < 0)
    1683          64 :                         StopHigh = StopMiddle;
    1684             :                     else
    1685          16 :                         StopLow = StopMiddle + 1;
    1686             :                 }
    1687             : 
    1688          80 :                 if (StopLow >= StopHigh && entry->isPartialMatch)
    1689             :                 {
    1690             :                     /*
    1691             :                      * No exact match on this page.  If doing partial match,
    1692             :                      * scan from the first tuple greater than target value to
    1693             :                      * end of page.  Note that since we don't remember whether
    1694             :                      * the comparePartialFn told us to stop early on a
    1695             :                      * previous page, we will uselessly apply comparePartialFn
    1696             :                      * to the first tuple on each subsequent page.
    1697             :                      */
    1698           0 :                     key->entryRes[j] =
    1699           0 :                         matchPartialInPendingList(&so->ginstate,
    1700             :                                                   page,
    1701             :                                                   StopHigh,
    1702           0 :                                                   pos->lastOffset,
    1703             :                                                   entry,
    1704             :                                                   datum,
    1705             :                                                   category,
    1706             :                                                   datumExtracted);
    1707             :                 }
    1708             : 
    1709          80 :                 pos->hasMatchKey[i] |= key->entryRes[j];
    1710             :             }
    1711             :         }
    1712             : 
    1713             :         /* Advance firstOffset over the scanned tuples */
    1714          40 :         pos->firstOffset = pos->lastOffset;
    1715             : 
    1716          40 :         if (GinPageHasFullRow(page))
    1717             :         {
    1718             :             /*
    1719             :              * We have examined all pending entries for the current heap row.
    1720             :              * Break out of loop over pages.
    1721             :              */
    1722          40 :             break;
    1723             :         }
    1724             :         else
    1725             :         {
    1726             :             /*
    1727             :              * Advance to next page of pending entries for the current heap
    1728             :              * row.  Complain if there isn't one.
    1729             :              */
    1730           0 :             ItemPointerData item = pos->item;
    1731             : 
    1732           0 :             if (scanGetCandidate(scan, pos) == false ||
    1733           0 :                 !ItemPointerEquals(&pos->item, &item))
    1734           0 :                 elog(ERROR, "could not find additional pending pages for same heap tuple");
    1735             :         }
    1736             :     }
    1737             : 
    1738             :     /*
    1739             :      * Now return "true" if all scan keys have at least one matching datum
    1740             :      */
    1741          56 :     for (i = 0; i < so->nkeys; i++)
    1742             :     {
    1743          40 :         if (pos->hasMatchKey[i] == false)
    1744          24 :             return false;
    1745             :     }
    1746             : 
    1747          16 :     return true;
    1748             : }
    1749             : 
    1750             : /*
    1751             :  * Collect all matched rows from pending list into bitmap.
    1752             :  */
    1753             : static void
    1754        1002 : scanPendingInsert(IndexScanDesc scan, TIDBitmap *tbm, int64 *ntids)
    1755             : {
    1756        1002 :     GinScanOpaque so = (GinScanOpaque) scan->opaque;
    1757             :     MemoryContext oldCtx;
    1758             :     bool        recheck,
    1759             :                 match;
    1760             :     int         i;
    1761             :     pendingPosition pos;
    1762        1002 :     Buffer      metabuffer = ReadBuffer(scan->indexRelation, GIN_METAPAGE_BLKNO);
    1763             :     Page        page;
    1764             :     BlockNumber blkno;
    1765             : 
    1766        1002 :     *ntids = 0;
    1767             : 
    1768             :     /*
    1769             :      * Acquire predicate lock on the metapage, to conflict with any fastupdate
    1770             :      * insertions.
    1771             :      */
    1772        1002 :     PredicateLockPage(scan->indexRelation, GIN_METAPAGE_BLKNO, scan->xs_snapshot);
    1773             : 
    1774        1002 :     LockBuffer(metabuffer, GIN_SHARE);
    1775        1002 :     page = BufferGetPage(metabuffer);
    1776        1002 :     TestForOldSnapshot(scan->xs_snapshot, scan->indexRelation, page);
    1777        1002 :     blkno = GinPageGetMeta(page)->head;
    1778             : 
    1779             :     /*
    1780             :      * fetch head of list before unlocking metapage. head page must be pinned
    1781             :      * to prevent deletion by vacuum process
    1782             :      */
    1783        1002 :     if (blkno == InvalidBlockNumber)
    1784             :     {
    1785             :         /* No pending list, so proceed with normal scan */
    1786         986 :         UnlockReleaseBuffer(metabuffer);
    1787         986 :         return;
    1788             :     }
    1789             : 
    1790          16 :     pos.pendingBuffer = ReadBuffer(scan->indexRelation, blkno);
    1791          16 :     LockBuffer(pos.pendingBuffer, GIN_SHARE);
    1792          16 :     pos.firstOffset = FirstOffsetNumber;
    1793          16 :     UnlockReleaseBuffer(metabuffer);
    1794          16 :     pos.hasMatchKey = palloc(sizeof(bool) * so->nkeys);
    1795             : 
    1796             :     /*
    1797             :      * loop for each heap row. scanGetCandidate returns full row or row's
    1798             :      * tuples from first page.
    1799             :      */
    1800          72 :     while (scanGetCandidate(scan, &pos))
    1801             :     {
    1802             :         /*
    1803             :          * Check entries in tuple and set up entryRes array.
    1804             :          *
    1805             :          * If pending tuples belonging to the current heap row are spread
    1806             :          * across several pages, collectMatchesForHeapRow will read all of
    1807             :          * those pages.
    1808             :          */
    1809          40 :         if (!collectMatchesForHeapRow(scan, &pos))
    1810          24 :             continue;
    1811             : 
    1812             :         /*
    1813             :          * Matching of entries of one row is finished, so check row using
    1814             :          * consistent functions.
    1815             :          */
    1816          16 :         oldCtx = MemoryContextSwitchTo(so->tempCtx);
    1817          16 :         recheck = false;
    1818          16 :         match = true;
    1819             : 
    1820          32 :         for (i = 0; i < so->nkeys; i++)
    1821             :         {
    1822          16 :             GinScanKey  key = so->keys + i;
    1823             : 
    1824          16 :             if (!key->boolConsistentFn(key))
    1825             :             {
    1826           0 :                 match = false;
    1827           0 :                 break;
    1828             :             }
    1829          16 :             recheck |= key->recheckCurItem;
    1830             :         }
    1831             : 
    1832          16 :         MemoryContextSwitchTo(oldCtx);
    1833          16 :         MemoryContextReset(so->tempCtx);
    1834             : 
    1835          16 :         if (match)
    1836             :         {
    1837          16 :             tbm_add_tuples(tbm, &pos.item, 1, recheck);
    1838          16 :             (*ntids)++;
    1839             :         }
    1840             :     }
    1841             : 
    1842          16 :     pfree(pos.hasMatchKey);
    1843             : }
    1844             : 
    1845             : 
    1846             : #define GinIsVoidRes(s)     ( ((GinScanOpaque) scan->opaque)->isVoidRes )
    1847             : 
    1848             : int64
    1849        1010 : gingetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
    1850             : {
    1851        1010 :     GinScanOpaque so = (GinScanOpaque) scan->opaque;
    1852             :     int64       ntids;
    1853             :     ItemPointerData iptr;
    1854             :     bool        recheck;
    1855             : 
    1856             :     /*
    1857             :      * Set up the scan keys, and check for unsatisfiable query.
    1858             :      */
    1859        1010 :     ginFreeScanKeys(so);        /* there should be no keys yet, but just to be
    1860             :                                  * sure */
    1861        1010 :     ginNewScanKey(scan);
    1862             : 
    1863        1010 :     if (GinIsVoidRes(scan))
    1864           8 :         return 0;
    1865             : 
    1866        1002 :     ntids = 0;
    1867             : 
    1868             :     /*
    1869             :      * First, scan the pending list and collect any matching entries into the
    1870             :      * bitmap.  After we scan a pending item, some other backend could post it
    1871             :      * into the main index, and so we might visit it a second time during the
    1872             :      * main scan.  This is okay because we'll just re-set the same bit in the
    1873             :      * bitmap.  (The possibility of duplicate visits is a major reason why GIN
    1874             :      * can't support the amgettuple API, however.) Note that it would not do
    1875             :      * to scan the main index before the pending list, since concurrent
    1876             :      * cleanup could then make us miss entries entirely.
    1877             :      */
    1878        1002 :     scanPendingInsert(scan, tbm, &ntids);
    1879             : 
    1880             :     /*
    1881             :      * Now scan the main index.
    1882             :      */
    1883        1002 :     startScan(scan);
    1884             : 
    1885        1002 :     ItemPointerSetMin(&iptr);
    1886             : 
    1887             :     for (;;)
    1888             :     {
    1889      930726 :         CHECK_FOR_INTERRUPTS();
    1890             : 
    1891      465864 :         if (!scanGetItem(scan, iptr, &iptr, &recheck))
    1892        1002 :             break;
    1893             : 
    1894      464862 :         if (ItemPointerIsLossyPage(&iptr))
    1895           0 :             tbm_add_page(tbm, ItemPointerGetBlockNumber(&iptr));
    1896             :         else
    1897      464862 :             tbm_add_tuples(tbm, &iptr, 1, recheck);
    1898      464862 :         ntids++;
    1899             :     }
    1900             : 
    1901        1002 :     return ntids;
    1902             : }

Generated by: LCOV version 1.13