LCOV - code coverage report
Current view: top level - src/backend/access/nbtree - nbtsearch.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18beta1 Lines: 639 708 90.3 %
Date: 2025-06-06 18:17:16 Functions: 20 20 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * nbtsearch.c
       4             :  *    Search code for postgres btrees.
       5             :  *
       6             :  *
       7             :  * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
       8             :  * Portions Copyright (c) 1994, Regents of the University of California
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *    src/backend/access/nbtree/nbtsearch.c
      12             :  *
      13             :  *-------------------------------------------------------------------------
      14             :  */
      15             : 
      16             : #include "postgres.h"
      17             : 
      18             : #include "access/nbtree.h"
      19             : #include "access/relscan.h"
      20             : #include "access/xact.h"
      21             : #include "miscadmin.h"
      22             : #include "pgstat.h"
      23             : #include "storage/predicate.h"
      24             : #include "utils/lsyscache.h"
      25             : #include "utils/rel.h"
      26             : 
      27             : 
      28             : static inline void _bt_drop_lock_and_maybe_pin(Relation rel, BTScanOpaque so);
      29             : static Buffer _bt_moveright(Relation rel, Relation heaprel, BTScanInsert key,
      30             :                             Buffer buf, bool forupdate, BTStack stack,
      31             :                             int access);
      32             : static OffsetNumber _bt_binsrch(Relation rel, BTScanInsert key, Buffer buf);
      33             : static int  _bt_binsrch_posting(BTScanInsert key, Page page,
      34             :                                 OffsetNumber offnum);
      35             : static bool _bt_readpage(IndexScanDesc scan, ScanDirection dir,
      36             :                          OffsetNumber offnum, bool firstpage);
      37             : static void _bt_saveitem(BTScanOpaque so, int itemIndex,
      38             :                          OffsetNumber offnum, IndexTuple itup);
      39             : static int  _bt_setuppostingitems(BTScanOpaque so, int itemIndex,
      40             :                                   OffsetNumber offnum, ItemPointer heapTid,
      41             :                                   IndexTuple itup);
      42             : static inline void _bt_savepostingitem(BTScanOpaque so, int itemIndex,
      43             :                                        OffsetNumber offnum,
      44             :                                        ItemPointer heapTid, int tupleOffset);
      45             : static inline void _bt_returnitem(IndexScanDesc scan, BTScanOpaque so);
      46             : static bool _bt_steppage(IndexScanDesc scan, ScanDirection dir);
      47             : static bool _bt_readfirstpage(IndexScanDesc scan, OffsetNumber offnum,
      48             :                               ScanDirection dir);
      49             : static bool _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno,
      50             :                              BlockNumber lastcurrblkno, ScanDirection dir,
      51             :                              bool seized);
      52             : static Buffer _bt_lock_and_validate_left(Relation rel, BlockNumber *blkno,
      53             :                                          BlockNumber lastcurrblkno);
      54             : static bool _bt_endpoint(IndexScanDesc scan, ScanDirection dir);
      55             : 
      56             : 
      57             : /*
      58             :  *  _bt_drop_lock_and_maybe_pin()
      59             :  *
      60             :  * Unlock so->currPos.buf.  If scan is so->dropPin, drop the pin, too.
      61             :  * Dropping the pin prevents VACUUM from blocking on acquiring a cleanup lock.
      62             :  */
      63             : static inline void
      64    11548292 : _bt_drop_lock_and_maybe_pin(Relation rel, BTScanOpaque so)
      65             : {
      66    11548292 :     if (!so->dropPin)
      67             :     {
      68             :         /* Just drop the lock (not the pin) */
      69      474608 :         _bt_unlockbuf(rel, so->currPos.buf);
      70      474608 :         return;
      71             :     }
      72             : 
      73             :     /*
      74             :      * Drop both the lock and the pin.
      75             :      *
      76             :      * Have to set so->currPos.lsn so that _bt_killitems has a way to detect
      77             :      * when concurrent heap TID recycling by VACUUM might have taken place.
      78             :      */
      79             :     Assert(RelationNeedsWAL(rel));
      80    11073684 :     so->currPos.lsn = BufferGetLSNAtomic(so->currPos.buf);
      81    11073684 :     _bt_relbuf(rel, so->currPos.buf);
      82    11073684 :     so->currPos.buf = InvalidBuffer;
      83             : }
      84             : 
      85             : /*
      86             :  *  _bt_search() -- Search the tree for a particular scankey,
      87             :  *      or more precisely for the first leaf page it could be on.
      88             :  *
      89             :  * The passed scankey is an insertion-type scankey (see nbtree/README),
      90             :  * but it can omit the rightmost column(s) of the index.
      91             :  *
      92             :  * Return value is a stack of parent-page pointers (i.e. there is no entry for
      93             :  * the leaf level/page).  *bufP is set to the address of the leaf-page buffer,
      94             :  * which is locked and pinned.  No locks are held on the parent pages,
      95             :  * however!
      96             :  *
      97             :  * The returned buffer is locked according to access parameter.  Additionally,
      98             :  * access = BT_WRITE will allow an empty root page to be created and returned.
      99             :  * When access = BT_READ, an empty index will result in *bufP being set to
     100             :  * InvalidBuffer.  Also, in BT_WRITE mode, any incomplete splits encountered
     101             :  * during the search will be finished.
     102             :  *
     103             :  * heaprel must be provided by callers that pass access = BT_WRITE, since we
     104             :  * might need to allocate a new root page for caller -- see _bt_allocbuf.
     105             :  */
     106             : BTStack
     107    23462808 : _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP,
     108             :            int access)
     109             : {
     110    23462808 :     BTStack     stack_in = NULL;
     111    23462808 :     int         page_access = BT_READ;
     112             : 
     113             :     /* heaprel must be set whenever _bt_allocbuf is reachable */
     114             :     Assert(access == BT_READ || access == BT_WRITE);
     115             :     Assert(access == BT_READ || heaprel != NULL);
     116             : 
     117             :     /* Get the root page to start with */
     118    23462808 :     *bufP = _bt_getroot(rel, heaprel, access);
     119             : 
     120             :     /* If index is empty and access = BT_READ, no root page is created. */
     121    23462808 :     if (!BufferIsValid(*bufP))
     122      540144 :         return (BTStack) NULL;
     123             : 
     124             :     /* Loop iterates once per level descended in the tree */
     125             :     for (;;)
     126    18899086 :     {
     127             :         Page        page;
     128             :         BTPageOpaque opaque;
     129             :         OffsetNumber offnum;
     130             :         ItemId      itemid;
     131             :         IndexTuple  itup;
     132             :         BlockNumber child;
     133             :         BTStack     new_stack;
     134             : 
     135             :         /*
     136             :          * Race -- the page we just grabbed may have split since we read its
     137             :          * downlink in its parent page (or the metapage).  If it has, we may
     138             :          * need to move right to its new sibling.  Do that.
     139             :          *
     140             :          * In write-mode, allow _bt_moveright to finish any incomplete splits
     141             :          * along the way.  Strictly speaking, we'd only need to finish an
     142             :          * incomplete split on the leaf page we're about to insert to, not on
     143             :          * any of the upper levels (internal pages with incomplete splits are
     144             :          * also taken care of in _bt_getstackbuf).  But this is a good
     145             :          * opportunity to finish splits of internal pages too.
     146             :          */
     147    41821750 :         *bufP = _bt_moveright(rel, heaprel, key, *bufP, (access == BT_WRITE),
     148             :                               stack_in, page_access);
     149             : 
     150             :         /* if this is a leaf page, we're done */
     151    41821750 :         page = BufferGetPage(*bufP);
     152    41821750 :         opaque = BTPageGetOpaque(page);
     153    41821750 :         if (P_ISLEAF(opaque))
     154    22922664 :             break;
     155             : 
     156             :         /*
     157             :          * Find the appropriate pivot tuple on this page.  Its downlink points
     158             :          * to the child page that we're about to descend to.
     159             :          */
     160    18899086 :         offnum = _bt_binsrch(rel, key, *bufP);
     161    18899086 :         itemid = PageGetItemId(page, offnum);
     162    18899086 :         itup = (IndexTuple) PageGetItem(page, itemid);
     163             :         Assert(BTreeTupleIsPivot(itup) || !key->heapkeyspace);
     164    18899086 :         child = BTreeTupleGetDownLink(itup);
     165             : 
     166             :         /*
     167             :          * We need to save the location of the pivot tuple we chose in a new
     168             :          * stack entry for this page/level.  If caller ends up splitting a
     169             :          * page one level down, it usually ends up inserting a new pivot
     170             :          * tuple/downlink immediately after the location recorded here.
     171             :          */
     172    18899086 :         new_stack = (BTStack) palloc(sizeof(BTStackData));
     173    18899086 :         new_stack->bts_blkno = BufferGetBlockNumber(*bufP);
     174    18899086 :         new_stack->bts_offset = offnum;
     175    18899086 :         new_stack->bts_parent = stack_in;
     176             : 
     177             :         /*
     178             :          * Page level 1 is lowest non-leaf page level prior to leaves.  So, if
     179             :          * we're on the level 1 and asked to lock leaf page in write mode,
     180             :          * then lock next page in write mode, because it must be a leaf.
     181             :          */
     182    18899086 :         if (opaque->btpo_level == 1 && access == BT_WRITE)
     183     6280288 :             page_access = BT_WRITE;
     184             : 
     185             :         /* drop the read lock on the page, then acquire one on its child */
     186    18899086 :         *bufP = _bt_relandgetbuf(rel, *bufP, child, page_access);
     187             : 
     188             :         /* okay, all set to move down a level */
     189    18899086 :         stack_in = new_stack;
     190             :     }
     191             : 
     192             :     /*
     193             :      * If we're asked to lock leaf in write mode, but didn't manage to, then
     194             :      * relock.  This should only happen when the root page is a leaf page (and
     195             :      * the only page in the index other than the metapage).
     196             :      */
     197    22922664 :     if (access == BT_WRITE && page_access == BT_READ)
     198             :     {
     199             :         /* trade in our read lock for a write lock */
     200      889098 :         _bt_unlockbuf(rel, *bufP);
     201      889098 :         _bt_lockbuf(rel, *bufP, BT_WRITE);
     202             : 
     203             :         /*
     204             :          * Race -- the leaf page may have split after we dropped the read lock
     205             :          * but before we acquired a write lock.  If it has, we may need to
     206             :          * move right to its new sibling.  Do that.
     207             :          */
     208      889098 :         *bufP = _bt_moveright(rel, heaprel, key, *bufP, true, stack_in, BT_WRITE);
     209             :     }
     210             : 
     211    22922664 :     return stack_in;
     212             : }
     213             : 
     214             : /*
     215             :  *  _bt_moveright() -- move right in the btree if necessary.
     216             :  *
     217             :  * When we follow a pointer to reach a page, it is possible that
     218             :  * the page has changed in the meanwhile.  If this happens, we're
     219             :  * guaranteed that the page has "split right" -- that is, that any
     220             :  * data that appeared on the page originally is either on the page
     221             :  * or strictly to the right of it.
     222             :  *
     223             :  * This routine decides whether or not we need to move right in the
     224             :  * tree by examining the high key entry on the page.  If that entry is
     225             :  * strictly less than the scankey, or <= the scankey in the
     226             :  * key.nextkey=true case, then we followed the wrong link and we need
     227             :  * to move right.
     228             :  *
     229             :  * The passed insertion-type scankey can omit the rightmost column(s) of the
     230             :  * index. (see nbtree/README)
     231             :  *
     232             :  * When key.nextkey is false (the usual case), we are looking for the first
     233             :  * item >= key.  When key.nextkey is true, we are looking for the first item
     234             :  * strictly greater than key.
     235             :  *
     236             :  * If forupdate is true, we will attempt to finish any incomplete splits
     237             :  * that we encounter.  This is required when locking a target page for an
     238             :  * insertion, because we don't allow inserting on a page before the split is
     239             :  * completed.  'heaprel' and 'stack' are only used if forupdate is true.
     240             :  *
     241             :  * On entry, we have the buffer pinned and a lock of the type specified by
     242             :  * 'access'.  If we move right, we release the buffer and lock and acquire
     243             :  * the same on the right sibling.  Return value is the buffer we stop at.
     244             :  */
     245             : static Buffer
     246    42710848 : _bt_moveright(Relation rel,
     247             :               Relation heaprel,
     248             :               BTScanInsert key,
     249             :               Buffer buf,
     250             :               bool forupdate,
     251             :               BTStack stack,
     252             :               int access)
     253             : {
     254             :     Page        page;
     255             :     BTPageOpaque opaque;
     256             :     int32       cmpval;
     257             : 
     258             :     Assert(!forupdate || heaprel != NULL);
     259             : 
     260             :     /*
     261             :      * When nextkey = false (normal case): if the scan key that brought us to
     262             :      * this page is > the high key stored on the page, then the page has split
     263             :      * and we need to move right.  (pg_upgrade'd !heapkeyspace indexes could
     264             :      * have some duplicates to the right as well as the left, but that's
     265             :      * something that's only ever dealt with on the leaf level, after
     266             :      * _bt_search has found an initial leaf page.)
     267             :      *
     268             :      * When nextkey = true: move right if the scan key is >= page's high key.
     269             :      * (Note that key.scantid cannot be set in this case.)
     270             :      *
     271             :      * The page could even have split more than once, so scan as far as
     272             :      * needed.
     273             :      *
     274             :      * We also have to move right if we followed a link that brought us to a
     275             :      * dead page.
     276             :      */
     277    42710848 :     cmpval = key->nextkey ? 0 : 1;
     278             : 
     279             :     for (;;)
     280             :     {
     281    42712746 :         page = BufferGetPage(buf);
     282    42712746 :         opaque = BTPageGetOpaque(page);
     283             : 
     284    42712746 :         if (P_RIGHTMOST(opaque))
     285    32290632 :             break;
     286             : 
     287             :         /*
     288             :          * Finish any incomplete splits we encounter along the way.
     289             :          */
     290    10422114 :         if (forupdate && P_INCOMPLETE_SPLIT(opaque))
     291           0 :         {
     292           0 :             BlockNumber blkno = BufferGetBlockNumber(buf);
     293             : 
     294             :             /* upgrade our lock if necessary */
     295           0 :             if (access == BT_READ)
     296             :             {
     297           0 :                 _bt_unlockbuf(rel, buf);
     298           0 :                 _bt_lockbuf(rel, buf, BT_WRITE);
     299             :             }
     300             : 
     301           0 :             if (P_INCOMPLETE_SPLIT(opaque))
     302           0 :                 _bt_finish_split(rel, heaprel, buf, stack);
     303             :             else
     304           0 :                 _bt_relbuf(rel, buf);
     305             : 
     306             :             /* re-acquire the lock in the right mode, and re-check */
     307           0 :             buf = _bt_getbuf(rel, blkno, access);
     308           0 :             continue;
     309             :         }
     310             : 
     311    10422114 :         if (P_IGNORE(opaque) || _bt_compare(rel, key, page, P_HIKEY) >= cmpval)
     312             :         {
     313             :             /* step right one page */
     314        1898 :             buf = _bt_relandgetbuf(rel, buf, opaque->btpo_next, access);
     315        1898 :             continue;
     316             :         }
     317             :         else
     318             :             break;
     319             :     }
     320             : 
     321    42710848 :     if (P_IGNORE(opaque))
     322           0 :         elog(ERROR, "fell off the end of index \"%s\"",
     323             :              RelationGetRelationName(rel));
     324             : 
     325    42710848 :     return buf;
     326             : }
     327             : 
     328             : /*
     329             :  *  _bt_binsrch() -- Do a binary search for a key on a particular page.
     330             :  *
     331             :  * On an internal (non-leaf) page, _bt_binsrch() returns the OffsetNumber
     332             :  * of the last key < given scankey, or last key <= given scankey if nextkey
     333             :  * is true.  (Since _bt_compare treats the first data key of such a page as
     334             :  * minus infinity, there will be at least one key < scankey, so the result
     335             :  * always points at one of the keys on the page.)
     336             :  *
     337             :  * On a leaf page, _bt_binsrch() returns the final result of the initial
     338             :  * positioning process that started with _bt_first's call to _bt_search.
     339             :  * We're returning a non-pivot tuple offset, so things are a little different.
     340             :  * It is possible that we'll return an offset that's either past the last
     341             :  * non-pivot slot, or (in the case of a backward scan) before the first slot.
     342             :  *
     343             :  * This procedure is not responsible for walking right, it just examines
     344             :  * the given page.  _bt_binsrch() has no lock or refcount side effects
     345             :  * on the buffer.
     346             :  */
     347             : static OffsetNumber
     348    34244756 : _bt_binsrch(Relation rel,
     349             :             BTScanInsert key,
     350             :             Buffer buf)
     351             : {
     352             :     Page        page;
     353             :     BTPageOpaque opaque;
     354             :     OffsetNumber low,
     355             :                 high;
     356             :     int32       result,
     357             :                 cmpval;
     358             : 
     359    34244756 :     page = BufferGetPage(buf);
     360    34244756 :     opaque = BTPageGetOpaque(page);
     361             : 
     362             :     /* Requesting nextkey semantics while using scantid seems nonsensical */
     363             :     Assert(!key->nextkey || key->scantid == NULL);
     364             :     /* scantid-set callers must use _bt_binsrch_insert() on leaf pages */
     365             :     Assert(!P_ISLEAF(opaque) || key->scantid == NULL);
     366             : 
     367    34244756 :     low = P_FIRSTDATAKEY(opaque);
     368    34244756 :     high = PageGetMaxOffsetNumber(page);
     369             : 
     370             :     /*
     371             :      * If there are no keys on the page, return the first available slot. Note
     372             :      * this covers two cases: the page is really empty (no keys), or it
     373             :      * contains only a high key.  The latter case is possible after vacuuming.
     374             :      * This can never happen on an internal page, however, since they are
     375             :      * never empty (an internal page must have at least one child).
     376             :      */
     377    34244756 :     if (unlikely(high < low))
     378       16420 :         return low;
     379             : 
     380             :     /*
     381             :      * Binary search to find the first key on the page >= scan key, or first
     382             :      * key > scankey when nextkey is true.
     383             :      *
     384             :      * For nextkey=false (cmpval=1), the loop invariant is: all slots before
     385             :      * 'low' are < scan key, all slots at or after 'high' are >= scan key.
     386             :      *
     387             :      * For nextkey=true (cmpval=0), the loop invariant is: all slots before
     388             :      * 'low' are <= scan key, all slots at or after 'high' are > scan key.
     389             :      *
     390             :      * We can fall out when high == low.
     391             :      */
     392    34228336 :     high++;                     /* establish the loop invariant for high */
     393             : 
     394    34228336 :     cmpval = key->nextkey ? 0 : 1;   /* select comparison value */
     395             : 
     396   223104126 :     while (high > low)
     397             :     {
     398   188875790 :         OffsetNumber mid = low + ((high - low) / 2);
     399             : 
     400             :         /* We have low <= mid < high, so mid points at a real slot */
     401             : 
     402   188875790 :         result = _bt_compare(rel, key, page, mid);
     403             : 
     404   188875790 :         if (result >= cmpval)
     405   117078454 :             low = mid + 1;
     406             :         else
     407    71797336 :             high = mid;
     408             :     }
     409             : 
     410             :     /*
     411             :      * At this point we have high == low.
     412             :      *
     413             :      * On a leaf page we always return the first non-pivot tuple >= scan key
     414             :      * (resp. > scan key) for forward scan callers.  For backward scans, it's
     415             :      * always the _last_ non-pivot tuple < scan key (resp. <= scan key).
     416             :      */
     417    34228336 :     if (P_ISLEAF(opaque))
     418             :     {
     419             :         /*
     420             :          * In the backward scan case we're supposed to locate the last
     421             :          * matching tuple on the leaf level -- not the first matching tuple
     422             :          * (the last tuple will be the first one returned by the scan).
     423             :          *
     424             :          * At this point we've located the first non-pivot tuple immediately
     425             :          * after the last matching tuple (which might just be maxoff + 1).
     426             :          * Compensate by stepping back.
     427             :          */
     428    15329250 :         if (key->backward)
     429       54512 :             return OffsetNumberPrev(low);
     430             : 
     431    15274738 :         return low;
     432             :     }
     433             : 
     434             :     /*
     435             :      * On a non-leaf page, return the last key < scan key (resp. <= scan key).
     436             :      * There must be one if _bt_compare() is playing by the rules.
     437             :      *
     438             :      * _bt_compare() will seldom see any exactly-matching pivot tuples, since
     439             :      * a truncated -inf heap TID is usually enough to prevent it altogether.
     440             :      * Even omitted scan key entries are treated as > truncated attributes.
     441             :      *
     442             :      * However, during backward scans _bt_compare() interprets omitted scan
     443             :      * key attributes as == corresponding truncated -inf attributes instead.
     444             :      * This works just like < would work here.  Under this scheme, < strategy
     445             :      * backward scans will always directly descend to the correct leaf page.
     446             :      * In particular, they will never incur an "extra" leaf page access with a
     447             :      * scan key that happens to contain the same prefix of values as some
     448             :      * pivot tuple's untruncated prefix.  VACUUM relies on this guarantee when
     449             :      * it uses a leaf page high key to "re-find" a page undergoing deletion.
     450             :      */
     451             :     Assert(low > P_FIRSTDATAKEY(opaque));
     452             : 
     453    18899086 :     return OffsetNumberPrev(low);
     454             : }
     455             : 
     456             : /*
     457             :  *
     458             :  *  _bt_binsrch_insert() -- Cacheable, incremental leaf page binary search.
     459             :  *
     460             :  * Like _bt_binsrch(), but with support for caching the binary search
     461             :  * bounds.  Only used during insertion, and only on the leaf page that it
     462             :  * looks like caller will insert tuple on.  Exclusive-locked and pinned
     463             :  * leaf page is contained within insertstate.
     464             :  *
     465             :  * Caches the bounds fields in insertstate so that a subsequent call can
     466             :  * reuse the low and strict high bounds of original binary search.  Callers
     467             :  * that use these fields directly must be prepared for the case where low
     468             :  * and/or stricthigh are not on the same page (one or both exceed maxoff
     469             :  * for the page).  The case where there are no items on the page (high <
     470             :  * low) makes bounds invalid.
     471             :  *
     472             :  * Caller is responsible for invalidating bounds when it modifies the page
     473             :  * before calling here a second time, and for dealing with posting list
     474             :  * tuple matches (callers can use insertstate's postingoff field to
     475             :  * determine which existing heap TID will need to be replaced by a posting
     476             :  * list split).
     477             :  */
     478             : OffsetNumber
     479    12801012 : _bt_binsrch_insert(Relation rel, BTInsertState insertstate)
     480             : {
     481    12801012 :     BTScanInsert key = insertstate->itup_key;
     482             :     Page        page;
     483             :     BTPageOpaque opaque;
     484             :     OffsetNumber low,
     485             :                 high,
     486             :                 stricthigh;
     487             :     int32       result,
     488             :                 cmpval;
     489             : 
     490    12801012 :     page = BufferGetPage(insertstate->buf);
     491    12801012 :     opaque = BTPageGetOpaque(page);
     492             : 
     493             :     Assert(P_ISLEAF(opaque));
     494             :     Assert(!key->nextkey);
     495             :     Assert(insertstate->postingoff == 0);
     496             : 
     497    12801012 :     if (!insertstate->bounds_valid)
     498             :     {
     499             :         /* Start new binary search */
     500     7659962 :         low = P_FIRSTDATAKEY(opaque);
     501     7659962 :         high = PageGetMaxOffsetNumber(page);
     502             :     }
     503             :     else
     504             :     {
     505             :         /* Restore result of previous binary search against same page */
     506     5141050 :         low = insertstate->low;
     507     5141050 :         high = insertstate->stricthigh;
     508             :     }
     509             : 
     510             :     /* If there are no keys on the page, return the first available slot */
     511    12801012 :     if (unlikely(high < low))
     512             :     {
     513             :         /* Caller can't reuse bounds */
     514       22988 :         insertstate->low = InvalidOffsetNumber;
     515       22988 :         insertstate->stricthigh = InvalidOffsetNumber;
     516       22988 :         insertstate->bounds_valid = false;
     517       22988 :         return low;
     518             :     }
     519             : 
     520             :     /*
     521             :      * Binary search to find the first key on the page >= scan key. (nextkey
     522             :      * is always false when inserting).
     523             :      *
     524             :      * The loop invariant is: all slots before 'low' are < scan key, all slots
     525             :      * at or after 'high' are >= scan key.  'stricthigh' is > scan key, and is
     526             :      * maintained to save additional search effort for caller.
     527             :      *
     528             :      * We can fall out when high == low.
     529             :      */
     530    12778024 :     if (!insertstate->bounds_valid)
     531     7636974 :         high++;                 /* establish the loop invariant for high */
     532    12778024 :     stricthigh = high;          /* high initially strictly higher */
     533             : 
     534    12778024 :     cmpval = 1;                 /* !nextkey comparison value */
     535             : 
     536    68712600 :     while (high > low)
     537             :     {
     538    55934576 :         OffsetNumber mid = low + ((high - low) / 2);
     539             : 
     540             :         /* We have low <= mid < high, so mid points at a real slot */
     541             : 
     542    55934576 :         result = _bt_compare(rel, key, page, mid);
     543             : 
     544    55934576 :         if (result >= cmpval)
     545    42656540 :             low = mid + 1;
     546             :         else
     547             :         {
     548    13278036 :             high = mid;
     549    13278036 :             if (result != 0)
     550    12171852 :                 stricthigh = high;
     551             :         }
     552             : 
     553             :         /*
     554             :          * If tuple at offset located by binary search is a posting list whose
     555             :          * TID range overlaps with caller's scantid, perform posting list
     556             :          * binary search to set postingoff for caller.  Caller must split the
     557             :          * posting list when postingoff is set.  This should happen
     558             :          * infrequently.
     559             :          */
     560    55934576 :         if (unlikely(result == 0 && key->scantid != NULL))
     561             :         {
     562             :             /*
     563             :              * postingoff should never be set more than once per leaf page
     564             :              * binary search.  That would mean that there are duplicate table
     565             :              * TIDs in the index, which is never okay.  Check for that here.
     566             :              */
     567      426296 :             if (insertstate->postingoff != 0)
     568           0 :                 ereport(ERROR,
     569             :                         (errcode(ERRCODE_INDEX_CORRUPTED),
     570             :                          errmsg_internal("table tid from new index tuple (%u,%u) cannot find insert offset between offsets %u and %u of block %u in index \"%s\"",
     571             :                                          ItemPointerGetBlockNumber(key->scantid),
     572             :                                          ItemPointerGetOffsetNumber(key->scantid),
     573             :                                          low, stricthigh,
     574             :                                          BufferGetBlockNumber(insertstate->buf),
     575             :                                          RelationGetRelationName(rel))));
     576             : 
     577      426296 :             insertstate->postingoff = _bt_binsrch_posting(key, page, mid);
     578             :         }
     579             :     }
     580             : 
     581             :     /*
     582             :      * On a leaf page, a binary search always returns the first key >= scan
     583             :      * key (at least in !nextkey case), which could be the last slot + 1. This
     584             :      * is also the lower bound of cached search.
     585             :      *
     586             :      * stricthigh may also be the last slot + 1, which prevents caller from
     587             :      * using bounds directly, but is still useful to us if we're called a
     588             :      * second time with cached bounds (cached low will be < stricthigh when
     589             :      * that happens).
     590             :      */
     591    12778024 :     insertstate->low = low;
     592    12778024 :     insertstate->stricthigh = stricthigh;
     593    12778024 :     insertstate->bounds_valid = true;
     594             : 
     595    12778024 :     return low;
     596             : }
     597             : 
     598             : /*----------
     599             :  *  _bt_binsrch_posting() -- posting list binary search.
     600             :  *
     601             :  * Helper routine for _bt_binsrch_insert().
     602             :  *
     603             :  * Returns offset into posting list where caller's scantid belongs.
     604             :  *----------
     605             :  */
     606             : static int
     607      426296 : _bt_binsrch_posting(BTScanInsert key, Page page, OffsetNumber offnum)
     608             : {
     609             :     IndexTuple  itup;
     610             :     ItemId      itemid;
     611             :     int         low,
     612             :                 high,
     613             :                 mid,
     614             :                 res;
     615             : 
     616             :     /*
     617             :      * If this isn't a posting tuple, then the index must be corrupt (if it is
     618             :      * an ordinary non-pivot tuple then there must be an existing tuple with a
     619             :      * heap TID that equals inserter's new heap TID/scantid).  Defensively
     620             :      * check that tuple is a posting list tuple whose posting list range
     621             :      * includes caller's scantid.
     622             :      *
     623             :      * (This is also needed because contrib/amcheck's rootdescend option needs
     624             :      * to be able to relocate a non-pivot tuple using _bt_binsrch_insert().)
     625             :      */
     626      426296 :     itemid = PageGetItemId(page, offnum);
     627      426296 :     itup = (IndexTuple) PageGetItem(page, itemid);
     628      426296 :     if (!BTreeTupleIsPosting(itup))
     629      402196 :         return 0;
     630             : 
     631             :     Assert(key->heapkeyspace && key->allequalimage);
     632             : 
     633             :     /*
     634             :      * In the event that posting list tuple has LP_DEAD bit set, indicate this
     635             :      * to _bt_binsrch_insert() caller by returning -1, a sentinel value.  A
     636             :      * second call to _bt_binsrch_insert() can take place when its caller has
     637             :      * removed the dead item.
     638             :      */
     639       24100 :     if (ItemIdIsDead(itemid))
     640           0 :         return -1;
     641             : 
     642             :     /* "high" is past end of posting list for loop invariant */
     643       24100 :     low = 0;
     644       24100 :     high = BTreeTupleGetNPosting(itup);
     645             :     Assert(high >= 2);
     646             : 
     647      194874 :     while (high > low)
     648             :     {
     649      170774 :         mid = low + ((high - low) / 2);
     650      170774 :         res = ItemPointerCompare(key->scantid,
     651             :                                  BTreeTupleGetPostingN(itup, mid));
     652             : 
     653      170774 :         if (res > 0)
     654       87798 :             low = mid + 1;
     655       82976 :         else if (res < 0)
     656       82976 :             high = mid;
     657             :         else
     658           0 :             return mid;
     659             :     }
     660             : 
     661             :     /* Exact match not found */
     662       24100 :     return low;
     663             : }
     664             : 
     665             : /*----------
     666             :  *  _bt_compare() -- Compare insertion-type scankey to tuple on a page.
     667             :  *
     668             :  *  page/offnum: location of btree item to be compared to.
     669             :  *
     670             :  *      This routine returns:
     671             :  *          <0 if scankey < tuple at offnum;
     672             :  *           0 if scankey == tuple at offnum;
     673             :  *          >0 if scankey > tuple at offnum.
     674             :  *
     675             :  * NULLs in the keys are treated as sortable values.  Therefore
     676             :  * "equality" does not necessarily mean that the item should be returned
     677             :  * to the caller as a matching key.  Similarly, an insertion scankey
     678             :  * with its scantid set is treated as equal to a posting tuple whose TID
     679             :  * range overlaps with their scantid.  There generally won't be a
     680             :  * matching TID in the posting tuple, which caller must handle
     681             :  * themselves (e.g., by splitting the posting list tuple).
     682             :  *
     683             :  * CRUCIAL NOTE: on a non-leaf page, the first data key is assumed to be
     684             :  * "minus infinity": this routine will always claim it is less than the
     685             :  * scankey.  The actual key value stored is explicitly truncated to 0
     686             :  * attributes (explicitly minus infinity) with version 3+ indexes, but
     687             :  * that isn't relied upon.  This allows us to implement the Lehman and
     688             :  * Yao convention that the first down-link pointer is before the first
     689             :  * key.  See backend/access/nbtree/README for details.
     690             :  *----------
     691             :  */
     692             : int32
     693   272393448 : _bt_compare(Relation rel,
     694             :             BTScanInsert key,
     695             :             Page page,
     696             :             OffsetNumber offnum)
     697             : {
     698   272393448 :     TupleDesc   itupdesc = RelationGetDescr(rel);
     699   272393448 :     BTPageOpaque opaque = BTPageGetOpaque(page);
     700             :     IndexTuple  itup;
     701             :     ItemPointer heapTid;
     702             :     ScanKey     scankey;
     703             :     int         ncmpkey;
     704             :     int         ntupatts;
     705             :     int32       result;
     706             : 
     707             :     Assert(_bt_check_natts(rel, key->heapkeyspace, page, offnum));
     708             :     Assert(key->keysz <= IndexRelationGetNumberOfKeyAttributes(rel));
     709             :     Assert(key->heapkeyspace || key->scantid == NULL);
     710             : 
     711             :     /*
     712             :      * Force result ">" if target item is first data item on an internal page
     713             :      * --- see NOTE above.
     714             :      */
     715   272393448 :     if (!P_ISLEAF(opaque) && offnum == P_FIRSTDATAKEY(opaque))
     716     3728640 :         return 1;
     717             : 
     718   268664808 :     itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
     719   268664808 :     ntupatts = BTreeTupleGetNAtts(itup, rel);
     720             : 
     721             :     /*
     722             :      * The scan key is set up with the attribute number associated with each
     723             :      * term in the key.  It is important that, if the index is multi-key, the
     724             :      * scan contain the first k key attributes, and that they be in order.  If
     725             :      * you think about how multi-key ordering works, you'll understand why
     726             :      * this is.
     727             :      *
     728             :      * We don't test for violation of this condition here, however.  The
     729             :      * initial setup for the index scan had better have gotten it right (see
     730             :      * _bt_first).
     731             :      */
     732             : 
     733   268664808 :     ncmpkey = Min(ntupatts, key->keysz);
     734             :     Assert(key->heapkeyspace || ncmpkey == key->keysz);
     735             :     Assert(!BTreeTupleIsPosting(itup) || key->allequalimage);
     736   268664808 :     scankey = key->scankeys;
     737   337217214 :     for (int i = 1; i <= ncmpkey; i++)
     738             :     {
     739             :         Datum       datum;
     740             :         bool        isNull;
     741             : 
     742   313513780 :         datum = index_getattr(itup, scankey->sk_attno, itupdesc, &isNull);
     743             : 
     744   313513780 :         if (scankey->sk_flags & SK_ISNULL)   /* key is NULL */
     745             :         {
     746      543768 :             if (isNull)
     747      157384 :                 result = 0;     /* NULL "=" NULL */
     748      386384 :             else if (scankey->sk_flags & SK_BT_NULLS_FIRST)
     749         624 :                 result = -1;    /* NULL "<" NOT_NULL */
     750             :             else
     751      385760 :                 result = 1;     /* NULL ">" NOT_NULL */
     752             :         }
     753   312970012 :         else if (isNull)        /* key is NOT_NULL and item is NULL */
     754             :         {
     755         264 :             if (scankey->sk_flags & SK_BT_NULLS_FIRST)
     756           0 :                 result = 1;     /* NOT_NULL ">" NULL */
     757             :             else
     758         264 :                 result = -1;    /* NOT_NULL "<" NULL */
     759             :         }
     760             :         else
     761             :         {
     762             :             /*
     763             :              * The sk_func needs to be passed the index value as left arg and
     764             :              * the sk_argument as right arg (they might be of different
     765             :              * types).  Since it is convenient for callers to think of
     766             :              * _bt_compare as comparing the scankey to the index item, we have
     767             :              * to flip the sign of the comparison result.  (Unless it's a DESC
     768             :              * column, in which case we *don't* flip the sign.)
     769             :              */
     770   312969748 :             result = DatumGetInt32(FunctionCall2Coll(&scankey->sk_func,
     771             :                                                      scankey->sk_collation,
     772             :                                                      datum,
     773             :                                                      scankey->sk_argument));
     774             : 
     775   312969748 :             if (!(scankey->sk_flags & SK_BT_DESC))
     776   312969682 :                 INVERT_COMPARE_RESULT(result);
     777             :         }
     778             : 
     779             :         /* if the keys are unequal, return the difference */
     780   313513780 :         if (result != 0)
     781   244961374 :             return result;
     782             : 
     783    68552406 :         scankey++;
     784             :     }
     785             : 
     786             :     /*
     787             :      * All non-truncated attributes (other than heap TID) were found to be
     788             :      * equal.  Treat truncated attributes as minus infinity when scankey has a
     789             :      * key attribute value that would otherwise be compared directly.
     790             :      *
     791             :      * Note: it doesn't matter if ntupatts includes non-key attributes;
     792             :      * scankey won't, so explicitly excluding non-key attributes isn't
     793             :      * necessary.
     794             :      */
     795    23703434 :     if (key->keysz > ntupatts)
     796      198674 :         return 1;
     797             : 
     798             :     /*
     799             :      * Use the heap TID attribute and scantid to try to break the tie.  The
     800             :      * rules are the same as any other key attribute -- only the
     801             :      * representation differs.
     802             :      */
     803    23504760 :     heapTid = BTreeTupleGetHeapTID(itup);
     804    23504760 :     if (key->scantid == NULL)
     805             :     {
     806             :         /*
     807             :          * Forward scans have a scankey that is considered greater than a
     808             :          * truncated pivot tuple if and when the scankey has equal values for
     809             :          * attributes up to and including the least significant untruncated
     810             :          * attribute in tuple.  Even attributes that were omitted from the
     811             :          * scan key are considered greater than -inf truncated attributes.
     812             :          * (See _bt_binsrch for an explanation of our backward scan behavior.)
     813             :          *
     814             :          * For example, if an index has the minimum two attributes (single
     815             :          * user key attribute, plus heap TID attribute), and a page's high key
     816             :          * is ('foo', -inf), and scankey is ('foo', <omitted>), the search
     817             :          * will not descend to the page to the left.  The search will descend
     818             :          * right instead.  The truncated attribute in pivot tuple means that
     819             :          * all non-pivot tuples on the page to the left are strictly < 'foo',
     820             :          * so it isn't necessary to descend left.  In other words, search
     821             :          * doesn't have to descend left because it isn't interested in a match
     822             :          * that has a heap TID value of -inf.
     823             :          *
     824             :          * Note: the heap TID part of the test ensures that scankey is being
     825             :          * compared to a pivot tuple with one or more truncated -inf key
     826             :          * attributes.  The heap TID attribute is the last key attribute in
     827             :          * every index, of course, but other than that it isn't special.
     828             :          */
     829    19036852 :         if (!key->backward && key->keysz == ntupatts && heapTid == NULL &&
     830        9690 :             key->heapkeyspace)
     831        9690 :             return 1;
     832             : 
     833             :         /* All provided scankey arguments found to be equal */
     834    19027162 :         return 0;
     835             :     }
     836             : 
     837             :     /*
     838             :      * Treat truncated heap TID as minus infinity, since scankey has a key
     839             :      * attribute value (scantid) that would otherwise be compared directly
     840             :      */
     841             :     Assert(key->keysz == IndexRelationGetNumberOfKeyAttributes(rel));
     842     4467908 :     if (heapTid == NULL)
     843        3966 :         return 1;
     844             : 
     845             :     /*
     846             :      * Scankey must be treated as equal to a posting list tuple if its scantid
     847             :      * value falls within the range of the posting list.  In all other cases
     848             :      * there can only be a single heap TID value, which is compared directly
     849             :      * with scantid.
     850             :      */
     851             :     Assert(ntupatts >= IndexRelationGetNumberOfKeyAttributes(rel));
     852     4463942 :     result = ItemPointerCompare(key->scantid, heapTid);
     853     4463942 :     if (result <= 0 || !BTreeTupleIsPosting(itup))
     854     4292086 :         return result;
     855             :     else
     856             :     {
     857      171856 :         result = ItemPointerCompare(key->scantid,
     858             :                                     BTreeTupleGetMaxHeapTID(itup));
     859      171856 :         if (result > 0)
     860      147756 :             return 1;
     861             :     }
     862             : 
     863       24100 :     return 0;
     864             : }
     865             : 
     866             : /*
     867             :  *  _bt_first() -- Find the first item in a scan.
     868             :  *
     869             :  *      We need to be clever about the direction of scan, the search
     870             :  *      conditions, and the tree ordering.  We find the first item (or,
     871             :  *      if backwards scan, the last item) in the tree that satisfies the
     872             :  *      qualifications in the scan key.  On success exit, data about the
     873             :  *      matching tuple(s) on the page has been loaded into so->currPos.  We'll
     874             :  *      drop all locks and hold onto a pin on page's buffer, except during
     875             :  *      so->dropPin scans, when we drop both the lock and the pin.
     876             :  *      _bt_returnitem sets the next item to return to scan on success exit.
     877             :  *
     878             :  * If there are no matching items in the index, we return false, with no
     879             :  * pins or locks held.  so->currPos will remain invalid.
     880             :  *
     881             :  * Note that scan->keyData[], and the so->keyData[] scankey built from it,
     882             :  * are both search-type scankeys (see nbtree/README for more about this).
     883             :  * Within this routine, we build a temporary insertion-type scankey to use
     884             :  * in locating the scan start position.
     885             :  */
     886             : bool
     887    15968998 : _bt_first(IndexScanDesc scan, ScanDirection dir)
     888             : {
     889    15968998 :     Relation    rel = scan->indexRelation;
     890    15968998 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     891             :     BTStack     stack;
     892             :     OffsetNumber offnum;
     893             :     BTScanInsertData inskey;
     894             :     ScanKey     startKeys[INDEX_MAX_KEYS];
     895             :     ScanKeyData notnullkeys[INDEX_MAX_KEYS];
     896    15968998 :     int         keysz = 0;
     897             :     StrategyNumber strat_total;
     898    15968998 :     BlockNumber blkno = InvalidBlockNumber,
     899             :                 lastcurrblkno;
     900             : 
     901             :     Assert(!BTScanPosIsValid(so->currPos));
     902             : 
     903             :     /*
     904             :      * Examine the scan keys and eliminate any redundant keys; also mark the
     905             :      * keys that must be matched to continue the scan.
     906             :      */
     907    15968998 :     _bt_preprocess_keys(scan);
     908             : 
     909             :     /*
     910             :      * Quit now if _bt_preprocess_keys() discovered that the scan keys can
     911             :      * never be satisfied (eg, x == 1 AND x > 2).
     912             :      */
     913    15968998 :     if (!so->qual_ok)
     914             :     {
     915             :         Assert(!so->needPrimScan);
     916        1142 :         _bt_parallel_done(scan);
     917        1142 :         return false;
     918             :     }
     919             : 
     920             :     /*
     921             :      * If this is a parallel scan, we must seize the scan.  _bt_readfirstpage
     922             :      * will likely release the parallel scan later on.
     923             :      */
     924    15967856 :     if (scan->parallel_scan != NULL &&
     925         446 :         !_bt_parallel_seize(scan, &blkno, &lastcurrblkno, true))
     926         290 :         return false;
     927             : 
     928             :     /*
     929             :      * Initialize the scan's arrays (if any) for the current scan direction
     930             :      * (except when they were already set to later values as part of
     931             :      * scheduling the primitive index scan that is now underway)
     932             :      */
     933    15967566 :     if (so->numArrayKeys && !so->needPrimScan)
     934       70868 :         _bt_start_array_keys(scan, dir);
     935             : 
     936    15967566 :     if (blkno != InvalidBlockNumber)
     937             :     {
     938             :         /*
     939             :          * We anticipated calling _bt_search, but another worker bet us to it.
     940             :          * _bt_readnextpage releases the scan for us (not _bt_readfirstpage).
     941             :          */
     942             :         Assert(scan->parallel_scan != NULL);
     943             :         Assert(!so->needPrimScan);
     944             :         Assert(blkno != P_NONE);
     945             : 
     946          32 :         if (!_bt_readnextpage(scan, blkno, lastcurrblkno, dir, true))
     947           0 :             return false;
     948             : 
     949          32 :         _bt_returnitem(scan, so);
     950          32 :         return true;
     951             :     }
     952             : 
     953             :     /*
     954             :      * Count an indexscan for stats, now that we know that we'll call
     955             :      * _bt_search/_bt_endpoint below
     956             :      */
     957    15967534 :     pgstat_count_index_scan(rel);
     958    15967534 :     if (scan->instrument)
     959      852824 :         scan->instrument->nsearches++;
     960             : 
     961             :     /*----------
     962             :      * Examine the scan keys to discover where we need to start the scan.
     963             :      *
     964             :      * We want to identify the keys that can be used as starting boundaries;
     965             :      * these are =, >, or >= keys for a forward scan or =, <, <= keys for
     966             :      * a backwards scan.  We can use keys for multiple attributes so long as
     967             :      * the prior attributes had only =, >= (resp. =, <=) keys.  Once we accept
     968             :      * a > or < boundary or find an attribute with no boundary (which can be
     969             :      * thought of as the same as "> -infinity"), we can't use keys for any
     970             :      * attributes to its right, because it would break our simplistic notion
     971             :      * of what initial positioning strategy to use.
     972             :      *
     973             :      * When the scan keys include cross-type operators, _bt_preprocess_keys
     974             :      * may not be able to eliminate redundant keys; in such cases we will
     975             :      * arbitrarily pick a usable one for each attribute.  This is correct
     976             :      * but possibly not optimal behavior.  (For example, with keys like
     977             :      * "x >= 4 AND x >= 5" we would elect to scan starting at x=4 when
     978             :      * x=5 would be more efficient.)  Since the situation only arises given
     979             :      * a poorly-worded query plus an incomplete opfamily, live with it.
     980             :      *
     981             :      * When both equality and inequality keys appear for a single attribute
     982             :      * (again, only possible when cross-type operators appear), we *must*
     983             :      * select one of the equality keys for the starting point, because
     984             :      * _bt_checkkeys() will stop the scan as soon as an equality qual fails.
     985             :      * For example, if we have keys like "x >= 4 AND x = 10" and we elect to
     986             :      * start at x=4, we will fail and stop before reaching x=10.  If multiple
     987             :      * equality quals survive preprocessing, however, it doesn't matter which
     988             :      * one we use --- by definition, they are either redundant or
     989             :      * contradictory.
     990             :      *
     991             :      * In practice we rarely see any "attribute boundary key gaps" here.
     992             :      * Preprocessing can usually backfill skip array keys for any attributes
     993             :      * that were omitted from the original scan->keyData[] input keys.  All
     994             :      * array keys are always considered = keys, but we'll sometimes need to
     995             :      * treat the current key value as if we were using an inequality strategy.
     996             :      * This happens with range skip arrays, which store inequality keys in the
     997             :      * array's low_compare/high_compare fields (used to find the first/last
     998             :      * set of matches, when = key will lack a usable sk_argument value).
     999             :      * These are always preferred over any redundant "standard" inequality
    1000             :      * keys on the same column (per the usual rule about preferring = keys).
    1001             :      * Note also that any column with an = skip array key can never have an
    1002             :      * additional, contradictory = key.
    1003             :      *
    1004             :      * All keys (with the exception of SK_SEARCHNULL keys and SK_BT_SKIP
    1005             :      * array keys whose array is "null_elem=true") imply a NOT NULL qualifier.
    1006             :      * If the index stores nulls at the end of the index we'll be starting
    1007             :      * from, and we have no boundary key for the column (which means the key
    1008             :      * we deduced NOT NULL from is an inequality key that constrains the other
    1009             :      * end of the index), then we cons up an explicit SK_SEARCHNOTNULL key to
    1010             :      * use as a boundary key.  If we didn't do this, we might find ourselves
    1011             :      * traversing a lot of null entries at the start of the scan.
    1012             :      *
    1013             :      * In this loop, row-comparison keys are treated the same as keys on their
    1014             :      * first (leftmost) columns.  We'll add on lower-order columns of the row
    1015             :      * comparison below, if possible.
    1016             :      *
    1017             :      * The selected scan keys (at most one per index column) are remembered by
    1018             :      * storing their addresses into the local startKeys[] array.
    1019             :      *
    1020             :      * _bt_checkkeys/_bt_advance_array_keys decide whether and when to start
    1021             :      * the next primitive index scan (for scans with array keys) based in part
    1022             :      * on an understanding of how it'll enable us to reposition the scan.
    1023             :      * They're directly aware of how we'll sometimes cons up an explicit
    1024             :      * SK_SEARCHNOTNULL key.  They'll even end primitive scans by applying a
    1025             :      * symmetric "deduce NOT NULL" rule of their own.  This allows top-level
    1026             :      * scans to skip large groups of NULLs through repeated deductions about
    1027             :      * key strictness (for a required inequality key) and whether NULLs in the
    1028             :      * key's index column are stored last or first (relative to non-NULLs).
    1029             :      * If you update anything here, _bt_checkkeys/_bt_advance_array_keys might
    1030             :      * need to be kept in sync.
    1031             :      *----------
    1032             :      */
    1033    15967534 :     strat_total = BTEqualStrategyNumber;
    1034    15967534 :     if (so->numberOfKeys > 0)
    1035             :     {
    1036             :         AttrNumber  curattr;
    1037             :         ScanKey     chosen;
    1038             :         ScanKey     impliesNN;
    1039             :         ScanKey     cur;
    1040             : 
    1041             :         /*
    1042             :          * chosen is the so-far-chosen key for the current attribute, if any.
    1043             :          * We don't cast the decision in stone until we reach keys for the
    1044             :          * next attribute.
    1045             :          */
    1046    15954346 :         cur = so->keyData;
    1047    15954346 :         curattr = 1;
    1048    15954346 :         chosen = NULL;
    1049             :         /* Also remember any scankey that implies a NOT NULL constraint */
    1050    15954346 :         impliesNN = NULL;
    1051             : 
    1052             :         /*
    1053             :          * Loop iterates from 0 to numberOfKeys inclusive; we use the last
    1054             :          * pass to handle after-last-key processing.  Actual exit from the
    1055             :          * loop is at one of the "break" statements below.
    1056             :          */
    1057    41092000 :         for (int i = 0;; cur++, i++)
    1058             :         {
    1059    41092000 :             if (i >= so->numberOfKeys || cur->sk_attno != curattr)
    1060             :             {
    1061             :                 /*
    1062             :                  * Done looking at keys for curattr.
    1063             :                  *
    1064             :                  * If this is a scan key for a skip array whose current
    1065             :                  * element is MINVAL, choose low_compare (when scanning
    1066             :                  * backwards it'll be MAXVAL, and we'll choose high_compare).
    1067             :                  *
    1068             :                  * Note: if the array's low_compare key makes 'chosen' NULL,
    1069             :                  * then we behave as if the array's first element is -inf,
    1070             :                  * except when !array->null_elem implies a usable NOT NULL
    1071             :                  * constraint.
    1072             :                  */
    1073    25135844 :                 if (chosen != NULL &&
    1074    25064602 :                     (chosen->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL)))
    1075             :                 {
    1076        3624 :                     int         ikey = chosen - so->keyData;
    1077        3624 :                     ScanKey     skipequalitykey = chosen;
    1078        3624 :                     BTArrayKeyInfo *array = NULL;
    1079             : 
    1080        3734 :                     for (int arridx = 0; arridx < so->numArrayKeys; arridx++)
    1081             :                     {
    1082        3734 :                         array = &so->arrayKeys[arridx];
    1083        3734 :                         if (array->scan_key == ikey)
    1084        3624 :                             break;
    1085             :                     }
    1086             : 
    1087        3624 :                     if (ScanDirectionIsForward(dir))
    1088             :                     {
    1089             :                         Assert(!(skipequalitykey->sk_flags & SK_BT_MAXVAL));
    1090        3606 :                         chosen = array->low_compare;
    1091             :                     }
    1092             :                     else
    1093             :                     {
    1094             :                         Assert(!(skipequalitykey->sk_flags & SK_BT_MINVAL));
    1095          18 :                         chosen = array->high_compare;
    1096             :                     }
    1097             : 
    1098             :                     Assert(chosen == NULL ||
    1099             :                            chosen->sk_attno == skipequalitykey->sk_attno);
    1100             : 
    1101        3624 :                     if (!array->null_elem)
    1102         128 :                         impliesNN = skipequalitykey;
    1103             :                     else
    1104             :                         Assert(chosen == NULL && impliesNN == NULL);
    1105             :                 }
    1106             : 
    1107             :                 /*
    1108             :                  * If we didn't find a usable boundary key, see if we can
    1109             :                  * deduce a NOT NULL key
    1110             :                  */
    1111    25207146 :                 if (chosen == NULL && impliesNN != NULL &&
    1112       71302 :                     ((impliesNN->sk_flags & SK_BT_NULLS_FIRST) ?
    1113             :                      ScanDirectionIsForward(dir) :
    1114             :                      ScanDirectionIsBackward(dir)))
    1115             :                 {
    1116             :                     /* Yes, so build the key in notnullkeys[keysz] */
    1117          30 :                     chosen = &notnullkeys[keysz];
    1118          30 :                     ScanKeyEntryInitialize(chosen,
    1119             :                                            (SK_SEARCHNOTNULL | SK_ISNULL |
    1120          30 :                                             (impliesNN->sk_flags &
    1121             :                                              (SK_BT_DESC | SK_BT_NULLS_FIRST))),
    1122             :                                            curattr,
    1123          30 :                                            ((impliesNN->sk_flags & SK_BT_NULLS_FIRST) ?
    1124             :                                             BTGreaterStrategyNumber :
    1125             :                                             BTLessStrategyNumber),
    1126             :                                            InvalidOid,
    1127             :                                            InvalidOid,
    1128             :                                            InvalidOid,
    1129             :                                            (Datum) 0);
    1130             :                 }
    1131             : 
    1132             :                 /*
    1133             :                  * If we still didn't find a usable boundary key, quit; else
    1134             :                  * save the boundary key pointer in startKeys.
    1135             :                  */
    1136    25135844 :                 if (chosen == NULL)
    1137       74768 :                     break;
    1138    25061076 :                 startKeys[keysz++] = chosen;
    1139             : 
    1140             :                 /*
    1141             :                  * We can only consider adding more boundary keys when the one
    1142             :                  * that we just chose to add uses either the = or >= strategy
    1143             :                  * (during backwards scans we can only do so when the key that
    1144             :                  * we just added to startKeys[] uses the = or <= strategy)
    1145             :                  */
    1146    25061076 :                 strat_total = chosen->sk_strategy;
    1147    25061076 :                 if (strat_total == BTGreaterStrategyNumber ||
    1148             :                     strat_total == BTLessStrategyNumber)
    1149             :                     break;
    1150             : 
    1151             :                 /*
    1152             :                  * If the key that we just added to startKeys[] is a skip
    1153             :                  * array = key whose current element is marked NEXT or PRIOR,
    1154             :                  * make strat_total > or < (and stop adding boundary keys).
    1155             :                  * This can only happen with opclasses that lack skip support.
    1156             :                  */
    1157    23368022 :                 if (chosen->sk_flags & (SK_BT_NEXT | SK_BT_PRIOR))
    1158             :                 {
    1159             :                     Assert(chosen->sk_flags & SK_BT_SKIP);
    1160             :                     Assert(strat_total == BTEqualStrategyNumber);
    1161             : 
    1162          12 :                     if (ScanDirectionIsForward(dir))
    1163             :                     {
    1164             :                         Assert(!(chosen->sk_flags & SK_BT_PRIOR));
    1165           6 :                         strat_total = BTGreaterStrategyNumber;
    1166             :                     }
    1167             :                     else
    1168             :                     {
    1169             :                         Assert(!(chosen->sk_flags & SK_BT_NEXT));
    1170           6 :                         strat_total = BTLessStrategyNumber;
    1171             :                     }
    1172             : 
    1173             :                     /*
    1174             :                      * We're done.  We'll never find an exact = match for a
    1175             :                      * NEXT or PRIOR sentinel sk_argument value.  There's no
    1176             :                      * sense in trying to add more keys to startKeys[].
    1177             :                      */
    1178          12 :                     break;
    1179             :                 }
    1180             : 
    1181             :                 /*
    1182             :                  * Done if that was the last scan key output by preprocessing.
    1183             :                  * Also done if there is a gap index attribute that lacks a
    1184             :                  * usable key (only possible when preprocessing was unable to
    1185             :                  * generate a skip array key to "fill in the gap").
    1186             :                  */
    1187    23368010 :                 if (i >= so->numberOfKeys ||
    1188     9181498 :                     cur->sk_attno != curattr + 1)
    1189             :                     break;
    1190             : 
    1191             :                 /*
    1192             :                  * Reset for next attr.
    1193             :                  */
    1194     9181498 :                 curattr = cur->sk_attno;
    1195     9181498 :                 chosen = NULL;
    1196     9181498 :                 impliesNN = NULL;
    1197             :             }
    1198             : 
    1199             :             /*
    1200             :              * Can we use this key as a starting boundary for this attr?
    1201             :              *
    1202             :              * If not, does it imply a NOT NULL constraint?  (Because
    1203             :              * SK_SEARCHNULL keys are always assigned BTEqualStrategyNumber,
    1204             :              * *any* inequality key works for that; we need not test.)
    1205             :              */
    1206    25137654 :             switch (cur->sk_strategy)
    1207             :             {
    1208      127348 :                 case BTLessStrategyNumber:
    1209             :                 case BTLessEqualStrategyNumber:
    1210      127348 :                     if (chosen == NULL)
    1211             :                     {
    1212      125562 :                         if (ScanDirectionIsBackward(dir))
    1213       54332 :                             chosen = cur;
    1214             :                         else
    1215       71230 :                             impliesNN = cur;
    1216             :                     }
    1217      127348 :                     break;
    1218    23367120 :                 case BTEqualStrategyNumber:
    1219             :                     /* override any non-equality choice */
    1220    23367120 :                     chosen = cur;
    1221    23367120 :                     break;
    1222     1643186 :                 case BTGreaterEqualStrategyNumber:
    1223             :                 case BTGreaterStrategyNumber:
    1224     1643186 :                     if (chosen == NULL)
    1225             :                     {
    1226     1643186 :                         if (ScanDirectionIsForward(dir))
    1227     1643150 :                             chosen = cur;
    1228             :                         else
    1229          36 :                             impliesNN = cur;
    1230             :                     }
    1231     1643186 :                     break;
    1232             :             }
    1233             :         }
    1234             :     }
    1235             : 
    1236             :     /*
    1237             :      * If we found no usable boundary keys, we have to start from one end of
    1238             :      * the tree.  Walk down that edge to the first or last key, and scan from
    1239             :      * there.
    1240             :      *
    1241             :      * Note: calls _bt_readfirstpage for us, which releases the parallel scan.
    1242             :      */
    1243    15967534 :     if (keysz == 0)
    1244       87230 :         return _bt_endpoint(scan, dir);
    1245             : 
    1246             :     /*
    1247             :      * We want to start the scan somewhere within the index.  Set up an
    1248             :      * insertion scankey we can use to search for the boundary point we
    1249             :      * identified above.  The insertion scankey is built using the keys
    1250             :      * identified by startKeys[].  (Remaining insertion scankey fields are
    1251             :      * initialized after initial-positioning scan keys are finalized.)
    1252             :      */
    1253             :     Assert(keysz <= INDEX_MAX_KEYS);
    1254    40941344 :     for (int i = 0; i < keysz; i++)
    1255             :     {
    1256    25061076 :         ScanKey     cur = startKeys[i];
    1257             : 
    1258             :         Assert(cur->sk_attno == i + 1);
    1259             : 
    1260    25061076 :         if (cur->sk_flags & SK_ROW_HEADER)
    1261             :         {
    1262             :             /*
    1263             :              * Row comparison header: look to the first row member instead
    1264             :              */
    1265          36 :             ScanKey     subkey = (ScanKey) DatumGetPointer(cur->sk_argument);
    1266             : 
    1267             :             /*
    1268             :              * Cannot be a NULL in the first row member: _bt_preprocess_keys
    1269             :              * would've marked the qual as unsatisfiable, preventing us from
    1270             :              * ever getting this far
    1271             :              */
    1272             :             Assert(subkey->sk_flags & SK_ROW_MEMBER);
    1273             :             Assert(subkey->sk_attno == cur->sk_attno);
    1274             :             Assert(!(subkey->sk_flags & SK_ISNULL));
    1275             : 
    1276             :             /*
    1277             :              * The member scankeys are already in insertion format (ie, they
    1278             :              * have sk_func = 3-way-comparison function)
    1279             :              */
    1280          36 :             memcpy(inskey.scankeys + i, subkey, sizeof(ScanKeyData));
    1281             : 
    1282             :             /*
    1283             :              * If the row comparison is the last positioning key we accepted,
    1284             :              * try to add additional keys from the lower-order row members.
    1285             :              * (If we accepted independent conditions on additional index
    1286             :              * columns, we use those instead --- doesn't seem worth trying to
    1287             :              * determine which is more restrictive.)  Note that this is OK
    1288             :              * even if the row comparison is of ">" or "<" type, because the
    1289             :              * condition applied to all but the last row member is effectively
    1290             :              * ">=" or "<=", and so the extra keys don't break the positioning
    1291             :              * scheme.  But, by the same token, if we aren't able to use all
    1292             :              * the row members, then the part of the row comparison that we
    1293             :              * did use has to be treated as just a ">=" or "<=" condition, and
    1294             :              * so we'd better adjust strat_total accordingly.
    1295             :              */
    1296          36 :             if (i == keysz - 1)
    1297             :             {
    1298          36 :                 bool        used_all_subkeys = false;
    1299             : 
    1300             :                 Assert(!(subkey->sk_flags & SK_ROW_END));
    1301             :                 for (;;)
    1302             :                 {
    1303          36 :                     subkey++;
    1304             :                     Assert(subkey->sk_flags & SK_ROW_MEMBER);
    1305          36 :                     if (subkey->sk_attno != keysz + 1)
    1306          12 :                         break;  /* out-of-sequence, can't use it */
    1307          24 :                     if (subkey->sk_strategy != cur->sk_strategy)
    1308           0 :                         break;  /* wrong direction, can't use it */
    1309          24 :                     if (subkey->sk_flags & SK_ISNULL)
    1310           0 :                         break;  /* can't use null keys */
    1311             :                     Assert(keysz < INDEX_MAX_KEYS);
    1312          24 :                     memcpy(inskey.scankeys + keysz, subkey,
    1313             :                            sizeof(ScanKeyData));
    1314          24 :                     keysz++;
    1315          24 :                     if (subkey->sk_flags & SK_ROW_END)
    1316             :                     {
    1317          24 :                         used_all_subkeys = true;
    1318          24 :                         break;
    1319             :                     }
    1320             :                 }
    1321          36 :                 if (!used_all_subkeys)
    1322             :                 {
    1323          12 :                     switch (strat_total)
    1324             :                     {
    1325           6 :                         case BTLessStrategyNumber:
    1326           6 :                             strat_total = BTLessEqualStrategyNumber;
    1327           6 :                             break;
    1328           6 :                         case BTGreaterStrategyNumber:
    1329           6 :                             strat_total = BTGreaterEqualStrategyNumber;
    1330           6 :                             break;
    1331             :                     }
    1332             :                 }
    1333          36 :                 break;          /* done with outer loop */
    1334             :             }
    1335             :         }
    1336             :         else
    1337             :         {
    1338             :             /*
    1339             :              * Ordinary comparison key.  Transform the search-style scan key
    1340             :              * to an insertion scan key by replacing the sk_func with the
    1341             :              * appropriate btree comparison function.
    1342             :              *
    1343             :              * If scankey operator is not a cross-type comparison, we can use
    1344             :              * the cached comparison function; otherwise gotta look it up in
    1345             :              * the catalogs.  (That can't lead to infinite recursion, since no
    1346             :              * indexscan initiated by syscache lookup will use cross-data-type
    1347             :              * operators.)
    1348             :              *
    1349             :              * We support the convention that sk_subtype == InvalidOid means
    1350             :              * the opclass input type; this is a hack to simplify life for
    1351             :              * ScanKeyInit().
    1352             :              */
    1353    25061040 :             if (cur->sk_subtype == rel->rd_opcintype[i] ||
    1354    24165440 :                 cur->sk_subtype == InvalidOid)
    1355    25050500 :             {
    1356             :                 FmgrInfo   *procinfo;
    1357             : 
    1358    25050500 :                 procinfo = index_getprocinfo(rel, cur->sk_attno, BTORDER_PROC);
    1359    25050500 :                 ScanKeyEntryInitializeWithInfo(inskey.scankeys + i,
    1360             :                                                cur->sk_flags,
    1361    25050500 :                                                cur->sk_attno,
    1362             :                                                InvalidStrategy,
    1363             :                                                cur->sk_subtype,
    1364             :                                                cur->sk_collation,
    1365             :                                                procinfo,
    1366             :                                                cur->sk_argument);
    1367             :             }
    1368             :             else
    1369             :             {
    1370             :                 RegProcedure cmp_proc;
    1371             : 
    1372       10540 :                 cmp_proc = get_opfamily_proc(rel->rd_opfamily[i],
    1373       10540 :                                              rel->rd_opcintype[i],
    1374             :                                              cur->sk_subtype,
    1375             :                                              BTORDER_PROC);
    1376       10540 :                 if (!RegProcedureIsValid(cmp_proc))
    1377           0 :                     elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
    1378             :                          BTORDER_PROC, rel->rd_opcintype[i], cur->sk_subtype,
    1379             :                          cur->sk_attno, RelationGetRelationName(rel));
    1380       10540 :                 ScanKeyEntryInitialize(inskey.scankeys + i,
    1381             :                                        cur->sk_flags,
    1382       10540 :                                        cur->sk_attno,
    1383             :                                        InvalidStrategy,
    1384             :                                        cur->sk_subtype,
    1385             :                                        cur->sk_collation,
    1386             :                                        cmp_proc,
    1387             :                                        cur->sk_argument);
    1388             :             }
    1389             :         }
    1390             :     }
    1391             : 
    1392             :     /*----------
    1393             :      * Examine the selected initial-positioning strategy to determine exactly
    1394             :      * where we need to start the scan, and set flag variables to control the
    1395             :      * initial descent by _bt_search (and our _bt_binsrch call for the leaf
    1396             :      * page _bt_search returns).
    1397             :      *----------
    1398             :      */
    1399    15880304 :     _bt_metaversion(rel, &inskey.heapkeyspace, &inskey.allequalimage);
    1400    15880304 :     inskey.anynullkeys = false; /* unused */
    1401    15880304 :     inskey.scantid = NULL;
    1402    15880304 :     inskey.keysz = keysz;
    1403    15880304 :     switch (strat_total)
    1404             :     {
    1405       54344 :         case BTLessStrategyNumber:
    1406             : 
    1407       54344 :             inskey.nextkey = false;
    1408       54344 :             inskey.backward = true;
    1409       54344 :             break;
    1410             : 
    1411          12 :         case BTLessEqualStrategyNumber:
    1412             : 
    1413          12 :             inskey.nextkey = true;
    1414          12 :             inskey.backward = true;
    1415          12 :             break;
    1416             : 
    1417    14182774 :         case BTEqualStrategyNumber:
    1418             : 
    1419             :             /*
    1420             :              * If a backward scan was specified, need to start with last equal
    1421             :              * item not first one.
    1422             :              */
    1423    14182774 :             if (ScanDirectionIsBackward(dir))
    1424             :             {
    1425             :                 /*
    1426             :                  * This is the same as the <= strategy
    1427             :                  */
    1428         182 :                 inskey.nextkey = true;
    1429         182 :                 inskey.backward = true;
    1430             :             }
    1431             :             else
    1432             :             {
    1433             :                 /*
    1434             :                  * This is the same as the >= strategy
    1435             :                  */
    1436    14182592 :                 inskey.nextkey = false;
    1437    14182592 :                 inskey.backward = false;
    1438             :             }
    1439    14182774 :             break;
    1440             : 
    1441        4464 :         case BTGreaterEqualStrategyNumber:
    1442             : 
    1443             :             /*
    1444             :              * Find first item >= scankey
    1445             :              */
    1446        4464 :             inskey.nextkey = false;
    1447        4464 :             inskey.backward = false;
    1448        4464 :             break;
    1449             : 
    1450     1638710 :         case BTGreaterStrategyNumber:
    1451             : 
    1452             :             /*
    1453             :              * Find first item > scankey
    1454             :              */
    1455     1638710 :             inskey.nextkey = true;
    1456     1638710 :             inskey.backward = false;
    1457     1638710 :             break;
    1458             : 
    1459           0 :         default:
    1460             :             /* can't get here, but keep compiler quiet */
    1461           0 :             elog(ERROR, "unrecognized strat_total: %d", (int) strat_total);
    1462             :             return false;
    1463             :     }
    1464             : 
    1465             :     /*
    1466             :      * Use the manufactured insertion scan key to descend the tree and
    1467             :      * position ourselves on the target leaf page.
    1468             :      */
    1469             :     Assert(ScanDirectionIsBackward(dir) == inskey.backward);
    1470    15880304 :     stack = _bt_search(rel, NULL, &inskey, &so->currPos.buf, BT_READ);
    1471             : 
    1472             :     /* don't need to keep the stack around... */
    1473    15880304 :     _bt_freestack(stack);
    1474             : 
    1475    15880304 :     if (!BufferIsValid(so->currPos.buf))
    1476             :     {
    1477             :         /*
    1478             :          * We only get here if the index is completely empty. Lock relation
    1479             :          * because nothing finer to lock exists.  Without a buffer lock, it's
    1480             :          * possible for another transaction to insert data between
    1481             :          * _bt_search() and PredicateLockRelation().  We have to try again
    1482             :          * after taking the relation-level predicate lock, to close a narrow
    1483             :          * window where we wouldn't scan concurrently inserted tuples, but the
    1484             :          * writer wouldn't see our predicate lock.
    1485             :          */
    1486      534634 :         if (IsolationIsSerializable())
    1487             :         {
    1488        5510 :             PredicateLockRelation(rel, scan->xs_snapshot);
    1489        5510 :             stack = _bt_search(rel, NULL, &inskey, &so->currPos.buf, BT_READ);
    1490        5510 :             _bt_freestack(stack);
    1491             :         }
    1492             : 
    1493      534634 :         if (!BufferIsValid(so->currPos.buf))
    1494             :         {
    1495             :             Assert(!so->needPrimScan);
    1496      534634 :             _bt_parallel_done(scan);
    1497      534634 :             return false;
    1498             :         }
    1499             :     }
    1500             : 
    1501             :     /* position to the precise item on the page */
    1502    15345670 :     offnum = _bt_binsrch(rel, &inskey, so->currPos.buf);
    1503             : 
    1504             :     /*
    1505             :      * Now load data from the first page of the scan (usually the page
    1506             :      * currently in so->currPos.buf).
    1507             :      *
    1508             :      * If inskey.nextkey = false and inskey.backward = false, offnum is
    1509             :      * positioned at the first non-pivot tuple >= inskey.scankeys.
    1510             :      *
    1511             :      * If inskey.nextkey = false and inskey.backward = true, offnum is
    1512             :      * positioned at the last non-pivot tuple < inskey.scankeys.
    1513             :      *
    1514             :      * If inskey.nextkey = true and inskey.backward = false, offnum is
    1515             :      * positioned at the first non-pivot tuple > inskey.scankeys.
    1516             :      *
    1517             :      * If inskey.nextkey = true and inskey.backward = true, offnum is
    1518             :      * positioned at the last non-pivot tuple <= inskey.scankeys.
    1519             :      *
    1520             :      * It's possible that _bt_binsrch returned an offnum that is out of bounds
    1521             :      * for the page.  For example, when inskey is both < the leaf page's high
    1522             :      * key and > all of its non-pivot tuples, offnum will be "maxoff + 1".
    1523             :      */
    1524    15345670 :     if (!_bt_readfirstpage(scan, offnum, dir))
    1525     3903736 :         return false;
    1526             : 
    1527    11441934 :     _bt_returnitem(scan, so);
    1528    11441934 :     return true;
    1529             : }
    1530             : 
    1531             : /*
    1532             :  *  _bt_next() -- Get the next item in a scan.
    1533             :  *
    1534             :  *      On entry, so->currPos describes the current page, which may be pinned
    1535             :  *      but is not locked, and so->currPos.itemIndex identifies which item was
    1536             :  *      previously returned.
    1537             :  *
    1538             :  *      On success exit, so->currPos is updated as needed, and _bt_returnitem
    1539             :  *      sets the next item to return to the scan.  so->currPos remains valid.
    1540             :  *
    1541             :  *      On failure exit (no more tuples), we invalidate so->currPos.  It'll
    1542             :  *      still be possible for the scan to return tuples by changing direction,
    1543             :  *      though we'll need to call _bt_first anew in that other direction.
    1544             :  */
    1545             : bool
    1546    19559726 : _bt_next(IndexScanDesc scan, ScanDirection dir)
    1547             : {
    1548    19559726 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
    1549             : 
    1550             :     Assert(BTScanPosIsValid(so->currPos));
    1551             : 
    1552             :     /*
    1553             :      * Advance to next tuple on current page; or if there's no more, try to
    1554             :      * step to the next page with data.
    1555             :      */
    1556    19559726 :     if (ScanDirectionIsForward(dir))
    1557             :     {
    1558    19526410 :         if (++so->currPos.itemIndex > so->currPos.lastItem)
    1559             :         {
    1560     2619360 :             if (!_bt_steppage(scan, dir))
    1561     2591310 :                 return false;
    1562             :         }
    1563             :     }
    1564             :     else
    1565             :     {
    1566       33316 :         if (--so->currPos.itemIndex < so->currPos.firstItem)
    1567             :         {
    1568         120 :             if (!_bt_steppage(scan, dir))
    1569          92 :                 return false;
    1570             :         }
    1571             :     }
    1572             : 
    1573    16968324 :     _bt_returnitem(scan, so);
    1574    16968324 :     return true;
    1575             : }
    1576             : 
    1577             : /*
    1578             :  *  _bt_readpage() -- Load data from current index page into so->currPos
    1579             :  *
    1580             :  * Caller must have pinned and read-locked so->currPos.buf; the buffer's state
    1581             :  * is not changed here.  Also, currPos.moreLeft and moreRight must be valid;
    1582             :  * they are updated as appropriate.  All other fields of so->currPos are
    1583             :  * initialized from scratch here.
    1584             :  *
    1585             :  * We scan the current page starting at offnum and moving in the indicated
    1586             :  * direction.  All items matching the scan keys are loaded into currPos.items.
    1587             :  * moreLeft or moreRight (as appropriate) is cleared if _bt_checkkeys reports
    1588             :  * that there can be no more matching tuples in the current scan direction
    1589             :  * (could just be for the current primitive index scan when scan has arrays).
    1590             :  *
    1591             :  * In the case of a parallel scan, caller must have called _bt_parallel_seize
    1592             :  * prior to calling this function; this function will invoke
    1593             :  * _bt_parallel_release before returning.
    1594             :  *
    1595             :  * Returns true if any matching items found on the page, false if none.
    1596             :  */
    1597             : static bool
    1598    15460778 : _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum,
    1599             :              bool firstpage)
    1600             : {
    1601    15460778 :     Relation    rel = scan->indexRelation;
    1602    15460778 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
    1603             :     Page        page;
    1604             :     BTPageOpaque opaque;
    1605             :     OffsetNumber minoff;
    1606             :     OffsetNumber maxoff;
    1607             :     BTReadPageState pstate;
    1608             :     bool        arrayKeys;
    1609             :     int         itemIndex,
    1610             :                 indnatts;
    1611             : 
    1612             :     /* save the page/buffer block number, along with its sibling links */
    1613    15460778 :     page = BufferGetPage(so->currPos.buf);
    1614    15460778 :     opaque = BTPageGetOpaque(page);
    1615    15460778 :     so->currPos.currPage = BufferGetBlockNumber(so->currPos.buf);
    1616    15460778 :     so->currPos.prevPage = opaque->btpo_prev;
    1617    15460778 :     so->currPos.nextPage = opaque->btpo_next;
    1618             :     /* delay setting so->currPos.lsn until _bt_drop_lock_and_maybe_pin */
    1619    15460778 :     so->currPos.dir = dir;
    1620    15460778 :     so->currPos.nextTupleOffset = 0;
    1621             : 
    1622             :     /* either moreRight or moreLeft should be set now (may be unset later) */
    1623             :     Assert(ScanDirectionIsForward(dir) ? so->currPos.moreRight :
    1624             :            so->currPos.moreLeft);
    1625             :     Assert(!P_IGNORE(opaque));
    1626             :     Assert(BTScanPosIsPinned(so->currPos));
    1627             :     Assert(!so->needPrimScan);
    1628             : 
    1629    15460778 :     if (scan->parallel_scan)
    1630             :     {
    1631             :         /* allow next/prev page to be read by other worker without delay */
    1632        1336 :         if (ScanDirectionIsForward(dir))
    1633        1336 :             _bt_parallel_release(scan, so->currPos.nextPage,
    1634             :                                  so->currPos.currPage);
    1635             :         else
    1636           0 :             _bt_parallel_release(scan, so->currPos.prevPage,
    1637             :                                  so->currPos.currPage);
    1638             :     }
    1639             : 
    1640    15460778 :     PredicateLockPage(rel, so->currPos.currPage, scan->xs_snapshot);
    1641             : 
    1642             :     /* initialize local variables */
    1643    15460778 :     indnatts = IndexRelationGetNumberOfAttributes(rel);
    1644    15460778 :     arrayKeys = so->numArrayKeys != 0;
    1645    15460778 :     minoff = P_FIRSTDATAKEY(opaque);
    1646    15460778 :     maxoff = PageGetMaxOffsetNumber(page);
    1647             : 
    1648             :     /* initialize page-level state that we'll pass to _bt_checkkeys */
    1649    15460778 :     pstate.minoff = minoff;
    1650    15460778 :     pstate.maxoff = maxoff;
    1651    15460778 :     pstate.finaltup = NULL;
    1652    15460778 :     pstate.page = page;
    1653    15460778 :     pstate.firstpage = firstpage;
    1654    15460778 :     pstate.forcenonrequired = false;
    1655    15460778 :     pstate.startikey = 0;
    1656    15460778 :     pstate.offnum = InvalidOffsetNumber;
    1657    15460778 :     pstate.skip = InvalidOffsetNumber;
    1658    15460778 :     pstate.continuescan = true; /* default assumption */
    1659    15460778 :     pstate.rechecks = 0;
    1660    15460778 :     pstate.targetdistance = 0;
    1661    15460778 :     pstate.nskipadvances = 0;
    1662             : 
    1663    15460778 :     if (ScanDirectionIsForward(dir))
    1664             :     {
    1665             :         /* SK_SEARCHARRAY forward scans must provide high key up front */
    1666    15406060 :         if (arrayKeys)
    1667             :         {
    1668       91024 :             if (!P_RIGHTMOST(opaque))
    1669             :             {
    1670       28500 :                 ItemId      iid = PageGetItemId(page, P_HIKEY);
    1671             : 
    1672       28500 :                 pstate.finaltup = (IndexTuple) PageGetItem(page, iid);
    1673             : 
    1674       28500 :                 if (so->scanBehind &&
    1675        2416 :                     !_bt_scanbehind_checkkeys(scan, dir, pstate.finaltup))
    1676             :                 {
    1677             :                     /* Schedule another primitive index scan after all */
    1678         412 :                     so->currPos.moreRight = false;
    1679         412 :                     so->needPrimScan = true;
    1680         412 :                     if (scan->parallel_scan)
    1681           0 :                         _bt_parallel_primscan_schedule(scan,
    1682             :                                                        so->currPos.currPage);
    1683         412 :                     return false;
    1684             :                 }
    1685             :             }
    1686             : 
    1687       90612 :             so->scanBehind = so->oppositeDirCheck = false;    /* reset */
    1688             :         }
    1689             : 
    1690             :         /*
    1691             :          * Consider pstate.startikey optimization once the ongoing primitive
    1692             :          * index scan has already read at least one page
    1693             :          */
    1694    15405648 :         if (!pstate.firstpage && minoff < maxoff)
    1695       34480 :             _bt_set_startikey(scan, &pstate);
    1696             : 
    1697             :         /* load items[] in ascending order */
    1698    15405648 :         itemIndex = 0;
    1699             : 
    1700    15405648 :         offnum = Max(offnum, minoff);
    1701             : 
    1702    59622992 :         while (offnum <= maxoff)
    1703             :         {
    1704    56325300 :             ItemId      iid = PageGetItemId(page, offnum);
    1705             :             IndexTuple  itup;
    1706             :             bool        passes_quals;
    1707             : 
    1708             :             /*
    1709             :              * If the scan specifies not to return killed tuples, then we
    1710             :              * treat a killed tuple as not passing the qual
    1711             :              */
    1712    56325300 :             if (scan->ignore_killed_tuples && ItemIdIsDead(iid))
    1713             :             {
    1714     4265078 :                 offnum = OffsetNumberNext(offnum);
    1715     4265078 :                 continue;
    1716             :             }
    1717             : 
    1718    52060222 :             itup = (IndexTuple) PageGetItem(page, iid);
    1719             :             Assert(!BTreeTupleIsPivot(itup));
    1720             : 
    1721    52060222 :             pstate.offnum = offnum;
    1722    52060222 :             passes_quals = _bt_checkkeys(scan, &pstate, arrayKeys,
    1723             :                                          itup, indnatts);
    1724             : 
    1725             :             /*
    1726             :              * Check if we need to skip ahead to a later tuple (only possible
    1727             :              * when the scan uses array keys)
    1728             :              */
    1729    52060222 :             if (arrayKeys && OffsetNumberIsValid(pstate.skip))
    1730             :             {
    1731             :                 Assert(!passes_quals && pstate.continuescan);
    1732             :                 Assert(offnum < pstate.skip);
    1733             :                 Assert(!pstate.forcenonrequired);
    1734             : 
    1735        3956 :                 offnum = pstate.skip;
    1736        3956 :                 pstate.skip = InvalidOffsetNumber;
    1737        3956 :                 continue;
    1738             :             }
    1739             : 
    1740    52056266 :             if (passes_quals)
    1741             :             {
    1742             :                 /* tuple passes all scan key conditions */
    1743    39408068 :                 if (!BTreeTupleIsPosting(itup))
    1744             :                 {
    1745             :                     /* Remember it */
    1746    38876724 :                     _bt_saveitem(so, itemIndex, offnum, itup);
    1747    38876724 :                     itemIndex++;
    1748             :                 }
    1749             :                 else
    1750             :                 {
    1751             :                     int         tupleOffset;
    1752             : 
    1753             :                     /*
    1754             :                      * Set up state to return posting list, and remember first
    1755             :                      * TID
    1756             :                      */
    1757             :                     tupleOffset =
    1758      531344 :                         _bt_setuppostingitems(so, itemIndex, offnum,
    1759             :                                               BTreeTupleGetPostingN(itup, 0),
    1760             :                                               itup);
    1761      531344 :                     itemIndex++;
    1762             :                     /* Remember additional TIDs */
    1763     2975352 :                     for (int i = 1; i < BTreeTupleGetNPosting(itup); i++)
    1764             :                     {
    1765     2444008 :                         _bt_savepostingitem(so, itemIndex, offnum,
    1766             :                                             BTreeTupleGetPostingN(itup, i),
    1767             :                                             tupleOffset);
    1768     2444008 :                         itemIndex++;
    1769             :                     }
    1770             :                 }
    1771             :             }
    1772             :             /* When !continuescan, there can't be any more matches, so stop */
    1773    52056266 :             if (!pstate.continuescan)
    1774    12107956 :                 break;
    1775             : 
    1776    39948310 :             offnum = OffsetNumberNext(offnum);
    1777             :         }
    1778             : 
    1779             :         /*
    1780             :          * We don't need to visit page to the right when the high key
    1781             :          * indicates that no more matches will be found there.
    1782             :          *
    1783             :          * Checking the high key like this works out more often than you might
    1784             :          * think.  Leaf page splits pick a split point between the two most
    1785             :          * dissimilar tuples (this is weighed against the need to evenly share
    1786             :          * free space).  Leaf pages with high key attribute values that can
    1787             :          * only appear on non-pivot tuples on the right sibling page are
    1788             :          * common.
    1789             :          */
    1790    15405648 :         if (pstate.continuescan && !so->scanBehind && !P_RIGHTMOST(opaque))
    1791             :         {
    1792      149096 :             ItemId      iid = PageGetItemId(page, P_HIKEY);
    1793      149096 :             IndexTuple  itup = (IndexTuple) PageGetItem(page, iid);
    1794             :             int         truncatt;
    1795             : 
    1796             :             /* Reset arrays, per _bt_set_startikey contract */
    1797      149096 :             if (pstate.forcenonrequired)
    1798        2004 :                 _bt_start_array_keys(scan, dir);
    1799      149096 :             pstate.forcenonrequired = false;
    1800      149096 :             pstate.startikey = 0;   /* _bt_set_startikey ignores P_HIKEY */
    1801             : 
    1802      149096 :             truncatt = BTreeTupleGetNAtts(itup, rel);
    1803      149096 :             _bt_checkkeys(scan, &pstate, arrayKeys, itup, truncatt);
    1804             :         }
    1805             : 
    1806    15405648 :         if (!pstate.continuescan)
    1807    12202018 :             so->currPos.moreRight = false;
    1808             : 
    1809             :         Assert(itemIndex <= MaxTIDsPerBTreePage);
    1810    15405648 :         so->currPos.firstItem = 0;
    1811    15405648 :         so->currPos.lastItem = itemIndex - 1;
    1812    15405648 :         so->currPos.itemIndex = 0;
    1813             :     }
    1814             :     else
    1815             :     {
    1816             :         /* SK_SEARCHARRAY backward scans must provide final tuple up front */
    1817       54718 :         if (arrayKeys)
    1818             :         {
    1819          78 :             if (minoff <= maxoff && !P_LEFTMOST(opaque))
    1820             :             {
    1821          60 :                 ItemId      iid = PageGetItemId(page, minoff);
    1822             : 
    1823          60 :                 pstate.finaltup = (IndexTuple) PageGetItem(page, iid);
    1824             : 
    1825          60 :                 if (so->scanBehind &&
    1826          12 :                     !_bt_scanbehind_checkkeys(scan, dir, pstate.finaltup))
    1827             :                 {
    1828             :                     /* Schedule another primitive index scan after all */
    1829           6 :                     so->currPos.moreLeft = false;
    1830           6 :                     so->needPrimScan = true;
    1831           6 :                     if (scan->parallel_scan)
    1832           0 :                         _bt_parallel_primscan_schedule(scan,
    1833             :                                                        so->currPos.currPage);
    1834           6 :                     return false;
    1835             :                 }
    1836             :             }
    1837             : 
    1838          72 :             so->scanBehind = so->oppositeDirCheck = false;    /* reset */
    1839             :         }
    1840             : 
    1841             :         /*
    1842             :          * Consider pstate.startikey optimization once the ongoing primitive
    1843             :          * index scan has already read at least one page
    1844             :          */
    1845       54712 :         if (!pstate.firstpage && minoff < maxoff)
    1846         132 :             _bt_set_startikey(scan, &pstate);
    1847             : 
    1848             :         /* load items[] in descending order */
    1849       54712 :         itemIndex = MaxTIDsPerBTreePage;
    1850             : 
    1851       54712 :         offnum = Min(offnum, maxoff);
    1852             : 
    1853     9237382 :         while (offnum >= minoff)
    1854             :         {
    1855     9182796 :             ItemId      iid = PageGetItemId(page, offnum);
    1856             :             IndexTuple  itup;
    1857             :             bool        tuple_alive;
    1858             :             bool        passes_quals;
    1859             : 
    1860             :             /*
    1861             :              * If the scan specifies not to return killed tuples, then we
    1862             :              * treat a killed tuple as not passing the qual.  Most of the
    1863             :              * time, it's a win to not bother examining the tuple's index
    1864             :              * keys, but just skip to the next tuple (previous, actually,
    1865             :              * since we're scanning backwards).  However, if this is the first
    1866             :              * tuple on the page, we do check the index keys, to prevent
    1867             :              * uselessly advancing to the page to the left.  This is similar
    1868             :              * to the high key optimization used by forward scans.
    1869             :              */
    1870     9182796 :             if (scan->ignore_killed_tuples && ItemIdIsDead(iid))
    1871             :             {
    1872      411820 :                 if (offnum > minoff)
    1873             :                 {
    1874      411056 :                     offnum = OffsetNumberPrev(offnum);
    1875      411056 :                     continue;
    1876             :                 }
    1877             : 
    1878         764 :                 tuple_alive = false;
    1879             :             }
    1880             :             else
    1881     8770976 :                 tuple_alive = true;
    1882             : 
    1883     8771740 :             itup = (IndexTuple) PageGetItem(page, iid);
    1884             :             Assert(!BTreeTupleIsPivot(itup));
    1885             : 
    1886     8771740 :             pstate.offnum = offnum;
    1887     8771740 :             if (arrayKeys && offnum == minoff && pstate.forcenonrequired)
    1888             :             {
    1889             :                 /* Reset arrays, per _bt_set_startikey contract */
    1890           6 :                 pstate.forcenonrequired = false;
    1891           6 :                 pstate.startikey = 0;
    1892           6 :                 _bt_start_array_keys(scan, dir);
    1893             :             }
    1894     8771740 :             passes_quals = _bt_checkkeys(scan, &pstate, arrayKeys,
    1895             :                                          itup, indnatts);
    1896             : 
    1897     8771740 :             if (arrayKeys && so->scanBehind)
    1898             :             {
    1899             :                 /*
    1900             :                  * Done scanning this page, but not done with the current
    1901             :                  * primscan.
    1902             :                  *
    1903             :                  * Note: Forward scans don't check this explicitly, since they
    1904             :                  * prefer to reuse pstate.skip for this instead.
    1905             :                  */
    1906             :                 Assert(!passes_quals && pstate.continuescan);
    1907             :                 Assert(!pstate.forcenonrequired);
    1908             : 
    1909          18 :                 break;
    1910             :             }
    1911             : 
    1912             :             /*
    1913             :              * Check if we need to skip ahead to a later tuple (only possible
    1914             :              * when the scan uses array keys)
    1915             :              */
    1916     8771722 :             if (arrayKeys && OffsetNumberIsValid(pstate.skip))
    1917             :             {
    1918             :                 Assert(!passes_quals && pstate.continuescan);
    1919             :                 Assert(offnum > pstate.skip);
    1920             :                 Assert(!pstate.forcenonrequired);
    1921             : 
    1922          36 :                 offnum = pstate.skip;
    1923          36 :                 pstate.skip = InvalidOffsetNumber;
    1924          36 :                 continue;
    1925             :             }
    1926             : 
    1927     8771686 :             if (passes_quals && tuple_alive)
    1928             :             {
    1929             :                 /* tuple passes all scan key conditions */
    1930     8768960 :                 if (!BTreeTupleIsPosting(itup))
    1931             :                 {
    1932             :                     /* Remember it */
    1933     8720920 :                     itemIndex--;
    1934     8720920 :                     _bt_saveitem(so, itemIndex, offnum, itup);
    1935             :                 }
    1936             :                 else
    1937             :                 {
    1938             :                     int         tupleOffset;
    1939             : 
    1940             :                     /*
    1941             :                      * Set up state to return posting list, and remember first
    1942             :                      * TID.
    1943             :                      *
    1944             :                      * Note that we deliberately save/return items from
    1945             :                      * posting lists in ascending heap TID order for backwards
    1946             :                      * scans.  This allows _bt_killitems() to make a
    1947             :                      * consistent assumption about the order of items
    1948             :                      * associated with the same posting list tuple.
    1949             :                      */
    1950       48040 :                     itemIndex--;
    1951             :                     tupleOffset =
    1952       48040 :                         _bt_setuppostingitems(so, itemIndex, offnum,
    1953             :                                               BTreeTupleGetPostingN(itup, 0),
    1954             :                                               itup);
    1955             :                     /* Remember additional TIDs */
    1956      175242 :                     for (int i = 1; i < BTreeTupleGetNPosting(itup); i++)
    1957             :                     {
    1958      127202 :                         itemIndex--;
    1959      127202 :                         _bt_savepostingitem(so, itemIndex, offnum,
    1960             :                                             BTreeTupleGetPostingN(itup, i),
    1961             :                                             tupleOffset);
    1962             :                     }
    1963             :                 }
    1964             :             }
    1965             :             /* When !continuescan, there can't be any more matches, so stop */
    1966     8771686 :             if (!pstate.continuescan)
    1967         108 :                 break;
    1968             : 
    1969     8771578 :             offnum = OffsetNumberPrev(offnum);
    1970             :         }
    1971             : 
    1972             :         /*
    1973             :          * We don't need to visit page to the left when no more matches will
    1974             :          * be found there
    1975             :          */
    1976       54712 :         if (!pstate.continuescan)
    1977         108 :             so->currPos.moreLeft = false;
    1978             : 
    1979             :         Assert(itemIndex >= 0);
    1980       54712 :         so->currPos.firstItem = itemIndex;
    1981       54712 :         so->currPos.lastItem = MaxTIDsPerBTreePage - 1;
    1982       54712 :         so->currPos.itemIndex = MaxTIDsPerBTreePage - 1;
    1983             :     }
    1984             : 
    1985             :     /*
    1986             :      * If _bt_set_startikey told us to temporarily treat the scan's keys as
    1987             :      * nonrequired (possible only during scans with array keys), there must be
    1988             :      * no lasting consequences for the scan's array keys.  The scan's arrays
    1989             :      * should now have exactly the same elements as they would have had if the
    1990             :      * nonrequired behavior had never been used.  (In general, a scan's arrays
    1991             :      * are expected to track its progress through the index's key space.)
    1992             :      *
    1993             :      * We are required (by _bt_set_startikey) to call _bt_checkkeys against
    1994             :      * pstate.finaltup with pstate.forcenonrequired=false to allow the scan's
    1995             :      * arrays to recover.  Assert that that step hasn't been missed.
    1996             :      */
    1997             :     Assert(!pstate.forcenonrequired);
    1998             : 
    1999    15460360 :     return (so->currPos.firstItem <= so->currPos.lastItem);
    2000             : }
    2001             : 
    2002             : /* Save an index item into so->currPos.items[itemIndex] */
    2003             : static void
    2004    47597644 : _bt_saveitem(BTScanOpaque so, int itemIndex,
    2005             :              OffsetNumber offnum, IndexTuple itup)
    2006             : {
    2007    47597644 :     BTScanPosItem *currItem = &so->currPos.items[itemIndex];
    2008             : 
    2009             :     Assert(!BTreeTupleIsPivot(itup) && !BTreeTupleIsPosting(itup));
    2010             : 
    2011    47597644 :     currItem->heapTid = itup->t_tid;
    2012    47597644 :     currItem->indexOffset = offnum;
    2013    47597644 :     if (so->currTuples)
    2014             :     {
    2015    22523054 :         Size        itupsz = IndexTupleSize(itup);
    2016             : 
    2017    22523054 :         currItem->tupleOffset = so->currPos.nextTupleOffset;
    2018    22523054 :         memcpy(so->currTuples + so->currPos.nextTupleOffset, itup, itupsz);
    2019    22523054 :         so->currPos.nextTupleOffset += MAXALIGN(itupsz);
    2020             :     }
    2021    47597644 : }
    2022             : 
    2023             : /*
    2024             :  * Setup state to save TIDs/items from a single posting list tuple.
    2025             :  *
    2026             :  * Saves an index item into so->currPos.items[itemIndex] for TID that is
    2027             :  * returned to scan first.  Second or subsequent TIDs for posting list should
    2028             :  * be saved by calling _bt_savepostingitem().
    2029             :  *
    2030             :  * Returns an offset into tuple storage space that main tuple is stored at if
    2031             :  * needed.
    2032             :  */
    2033             : static int
    2034      579384 : _bt_setuppostingitems(BTScanOpaque so, int itemIndex, OffsetNumber offnum,
    2035             :                       ItemPointer heapTid, IndexTuple itup)
    2036             : {
    2037      579384 :     BTScanPosItem *currItem = &so->currPos.items[itemIndex];
    2038             : 
    2039             :     Assert(BTreeTupleIsPosting(itup));
    2040             : 
    2041      579384 :     currItem->heapTid = *heapTid;
    2042      579384 :     currItem->indexOffset = offnum;
    2043      579384 :     if (so->currTuples)
    2044             :     {
    2045             :         /* Save base IndexTuple (truncate posting list) */
    2046             :         IndexTuple  base;
    2047      172674 :         Size        itupsz = BTreeTupleGetPostingOffset(itup);
    2048             : 
    2049      172674 :         itupsz = MAXALIGN(itupsz);
    2050      172674 :         currItem->tupleOffset = so->currPos.nextTupleOffset;
    2051      172674 :         base = (IndexTuple) (so->currTuples + so->currPos.nextTupleOffset);
    2052      172674 :         memcpy(base, itup, itupsz);
    2053             :         /* Defensively reduce work area index tuple header size */
    2054      172674 :         base->t_info &= ~INDEX_SIZE_MASK;
    2055      172674 :         base->t_info |= itupsz;
    2056      172674 :         so->currPos.nextTupleOffset += itupsz;
    2057             : 
    2058      172674 :         return currItem->tupleOffset;
    2059             :     }
    2060             : 
    2061      406710 :     return 0;
    2062             : }
    2063             : 
    2064             : /*
    2065             :  * Save an index item into so->currPos.items[itemIndex] for current posting
    2066             :  * tuple.
    2067             :  *
    2068             :  * Assumes that _bt_setuppostingitems() has already been called for current
    2069             :  * posting list tuple.  Caller passes its return value as tupleOffset.
    2070             :  */
    2071             : static inline void
    2072     2571210 : _bt_savepostingitem(BTScanOpaque so, int itemIndex, OffsetNumber offnum,
    2073             :                     ItemPointer heapTid, int tupleOffset)
    2074             : {
    2075     2571210 :     BTScanPosItem *currItem = &so->currPos.items[itemIndex];
    2076             : 
    2077     2571210 :     currItem->heapTid = *heapTid;
    2078     2571210 :     currItem->indexOffset = offnum;
    2079             : 
    2080             :     /*
    2081             :      * Have index-only scans return the same base IndexTuple for every TID
    2082             :      * that originates from the same posting list
    2083             :      */
    2084     2571210 :     if (so->currTuples)
    2085      951728 :         currItem->tupleOffset = tupleOffset;
    2086     2571210 : }
    2087             : 
    2088             : /*
    2089             :  * Return the index item from so->currPos.items[so->currPos.itemIndex] to the
    2090             :  * index scan by setting the relevant fields in caller's index scan descriptor
    2091             :  */
    2092             : static inline void
    2093    28488538 : _bt_returnitem(IndexScanDesc scan, BTScanOpaque so)
    2094             : {
    2095    28488538 :     BTScanPosItem *currItem = &so->currPos.items[so->currPos.itemIndex];
    2096             : 
    2097             :     /* Most recent _bt_readpage must have succeeded */
    2098             :     Assert(BTScanPosIsValid(so->currPos));
    2099             :     Assert(so->currPos.itemIndex >= so->currPos.firstItem);
    2100             :     Assert(so->currPos.itemIndex <= so->currPos.lastItem);
    2101             : 
    2102             :     /* Return next item, per amgettuple contract */
    2103    28488538 :     scan->xs_heaptid = currItem->heapTid;
    2104    28488538 :     if (so->currTuples)
    2105     4224218 :         scan->xs_itup = (IndexTuple) (so->currTuples + currItem->tupleOffset);
    2106    28488538 : }
    2107             : 
    2108             : /*
    2109             :  *  _bt_steppage() -- Step to next page containing valid data for scan
    2110             :  *
    2111             :  * Wrapper on _bt_readnextpage that performs final steps for the current page.
    2112             :  *
    2113             :  * On entry, so->currPos must be valid.  Its buffer will be pinned, though
    2114             :  * never locked. (Actually, when so->dropPin there won't even be a pin held,
    2115             :  * though so->currPos.currPage must still be set to a valid block number.)
    2116             :  */
    2117             : static bool
    2118     6529754 : _bt_steppage(IndexScanDesc scan, ScanDirection dir)
    2119             : {
    2120     6529754 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
    2121             :     BlockNumber blkno,
    2122             :                 lastcurrblkno;
    2123             : 
    2124             :     Assert(BTScanPosIsValid(so->currPos));
    2125             : 
    2126             :     /* Before leaving current page, deal with any killed items */
    2127     6529754 :     if (so->numKilled > 0)
    2128       79998 :         _bt_killitems(scan);
    2129             : 
    2130             :     /*
    2131             :      * Before we modify currPos, make a copy of the page data if there was a
    2132             :      * mark position that needs it.
    2133             :      */
    2134     6529754 :     if (so->markItemIndex >= 0)
    2135             :     {
    2136             :         /* bump pin on current buffer for assignment to mark buffer */
    2137         370 :         if (BTScanPosIsPinned(so->currPos))
    2138         350 :             IncrBufferRefCount(so->currPos.buf);
    2139         370 :         memcpy(&so->markPos, &so->currPos,
    2140             :                offsetof(BTScanPosData, items[1]) +
    2141         370 :                so->currPos.lastItem * sizeof(BTScanPosItem));
    2142         370 :         if (so->markTuples)
    2143         348 :             memcpy(so->markTuples, so->currTuples,
    2144         348 :                    so->currPos.nextTupleOffset);
    2145         370 :         so->markPos.itemIndex = so->markItemIndex;
    2146         370 :         so->markItemIndex = -1;
    2147             : 
    2148             :         /*
    2149             :          * If we're just about to start the next primitive index scan
    2150             :          * (possible with a scan that has arrays keys, and needs to skip to
    2151             :          * continue in the current scan direction), moreLeft/moreRight only
    2152             :          * indicate the end of the current primitive index scan.  They must
    2153             :          * never be taken to indicate that the top-level index scan has ended
    2154             :          * (that would be wrong).
    2155             :          *
    2156             :          * We could handle this case by treating the current array keys as
    2157             :          * markPos state.  But depending on the current array state like this
    2158             :          * would add complexity.  Instead, we just unset markPos's copy of
    2159             :          * moreRight or moreLeft (whichever might be affected), while making
    2160             :          * btrestrpos reset the scan's arrays to their initial scan positions.
    2161             :          * In effect, btrestrpos leaves advancing the arrays up to the first
    2162             :          * _bt_readpage call (that takes place after it has restored markPos).
    2163             :          */
    2164         370 :         if (so->needPrimScan)
    2165             :         {
    2166           0 :             if (ScanDirectionIsForward(so->currPos.dir))
    2167           0 :                 so->markPos.moreRight = true;
    2168             :             else
    2169           0 :                 so->markPos.moreLeft = true;
    2170             :         }
    2171             : 
    2172             :         /* mark/restore not supported by parallel scans */
    2173             :         Assert(!scan->parallel_scan);
    2174             :     }
    2175             : 
    2176     6529754 :     BTScanPosUnpinIfPinned(so->currPos);
    2177             : 
    2178             :     /* Walk to the next page with data */
    2179     6529754 :     if (ScanDirectionIsForward(dir))
    2180     6529528 :         blkno = so->currPos.nextPage;
    2181             :     else
    2182         226 :         blkno = so->currPos.prevPage;
    2183     6529754 :     lastcurrblkno = so->currPos.currPage;
    2184             : 
    2185             :     /*
    2186             :      * Cancel primitive index scans that were scheduled when the call to
    2187             :      * _bt_readpage for currPos happened to use the opposite direction to the
    2188             :      * one that we're stepping in now.  (It's okay to leave the scan's array
    2189             :      * keys as-is, since the next _bt_readpage will advance them.)
    2190             :      */
    2191     6529754 :     if (so->currPos.dir != dir)
    2192          36 :         so->needPrimScan = false;
    2193             : 
    2194     6529754 :     return _bt_readnextpage(scan, blkno, lastcurrblkno, dir, false);
    2195             : }
    2196             : 
    2197             : /*
    2198             :  *  _bt_readfirstpage() -- Read first page containing valid data for _bt_first
    2199             :  *
    2200             :  * _bt_first caller passes us an offnum returned by _bt_binsrch, which might
    2201             :  * be an out of bounds offnum such as "maxoff + 1" in certain corner cases.
    2202             :  * _bt_checkkeys will stop the scan as soon as an equality qual fails (when
    2203             :  * its scan key was marked required), so _bt_first _must_ pass us an offnum
    2204             :  * exactly at the beginning of where equal tuples are to be found.  When we're
    2205             :  * passed an offnum past the end of the page, we might still manage to stop
    2206             :  * the scan on this page by calling _bt_checkkeys against the high key.  See
    2207             :  * _bt_readpage for full details.
    2208             :  *
    2209             :  * On entry, so->currPos must be pinned and locked (so offnum stays valid).
    2210             :  * Parallel scan callers must have seized the scan before calling here.
    2211             :  *
    2212             :  * On exit, we'll have updated so->currPos and retained locks and pins
    2213             :  * according to the same rules as those laid out for _bt_readnextpage exit.
    2214             :  * Like _bt_readnextpage, our return value indicates if there are any matching
    2215             :  * records in the given direction.
    2216             :  *
    2217             :  * We always release the scan for a parallel scan caller, regardless of
    2218             :  * success or failure; we'll call _bt_parallel_release as soon as possible.
    2219             :  */
    2220             : static bool
    2221    15425686 : _bt_readfirstpage(IndexScanDesc scan, OffsetNumber offnum, ScanDirection dir)
    2222             : {
    2223    15425686 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
    2224             : 
    2225    15425686 :     so->numKilled = 0;           /* just paranoia */
    2226    15425686 :     so->markItemIndex = -1;      /* ditto */
    2227             : 
    2228             :     /* Initialize so->currPos for the first page (page in so->currPos.buf) */
    2229    15425686 :     if (so->needPrimScan)
    2230             :     {
    2231             :         Assert(so->numArrayKeys);
    2232             : 
    2233       17530 :         so->currPos.moreLeft = true;
    2234       17530 :         so->currPos.moreRight = true;
    2235       17530 :         so->needPrimScan = false;
    2236             :     }
    2237    15408156 :     else if (ScanDirectionIsForward(dir))
    2238             :     {
    2239    15353588 :         so->currPos.moreLeft = false;
    2240    15353588 :         so->currPos.moreRight = true;
    2241             :     }
    2242             :     else
    2243             :     {
    2244       54568 :         so->currPos.moreLeft = true;
    2245       54568 :         so->currPos.moreRight = false;
    2246             :     }
    2247             : 
    2248             :     /*
    2249             :      * Attempt to load matching tuples from the first page.
    2250             :      *
    2251             :      * Note that _bt_readpage will finish initializing the so->currPos fields.
    2252             :      * _bt_readpage also releases parallel scan (even when it returns false).
    2253             :      */
    2254    15425686 :     if (_bt_readpage(scan, dir, offnum, true))
    2255             :     {
    2256    11515412 :         Relation    rel = scan->indexRelation;
    2257             : 
    2258             :         /*
    2259             :          * _bt_readpage succeeded.  Drop the lock (and maybe the pin) on
    2260             :          * so->currPos.buf in preparation for btgettuple returning tuples.
    2261             :          */
    2262             :         Assert(BTScanPosIsPinned(so->currPos));
    2263    11515412 :         _bt_drop_lock_and_maybe_pin(rel, so);
    2264    11515412 :         return true;
    2265             :     }
    2266             : 
    2267             :     /* There's no actually-matching data on the page in so->currPos.buf */
    2268     3910274 :     _bt_unlockbuf(scan->indexRelation, so->currPos.buf);
    2269             : 
    2270             :     /* Call _bt_readnextpage using its _bt_steppage wrapper function */
    2271     3910274 :     if (!_bt_steppage(scan, dir))
    2272     3905504 :         return false;
    2273             : 
    2274             :     /* _bt_readpage for a later page (now in so->currPos) succeeded */
    2275        4770 :     return true;
    2276             : }
    2277             : 
    2278             : /*
    2279             :  *  _bt_readnextpage() -- Read next page containing valid data for _bt_next
    2280             :  *
    2281             :  * Caller's blkno is the next interesting page's link, taken from either the
    2282             :  * previously-saved right link or left link.  lastcurrblkno is the page that
    2283             :  * was current at the point where the blkno link was saved, which we use to
    2284             :  * reason about concurrent page splits/page deletions during backwards scans.
    2285             :  *
    2286             :  * On entry, caller shouldn't hold any locks or pins on any page (we work
    2287             :  * directly off of blkno and lastcurrblkno instead).  Parallel scan callers
    2288             :  * that seized the scan before calling here should pass seized=true; such a
    2289             :  * caller's blkno and lastcurrblkno arguments come from the seized scan.
    2290             :  * seized=false callers just pass us the blkno/lastcurrblkno taken from their
    2291             :  * so->currPos, which (along with so->currPos itself) can be used to end the
    2292             :  * scan.  A seized=false caller's blkno can never be assumed to be the page
    2293             :  * that must be read next during a parallel scan, though.  We must figure that
    2294             :  * part out for ourselves by seizing the scan (the correct page to read might
    2295             :  * already be beyond the seized=false caller's blkno during a parallel scan,
    2296             :  * unless blkno/so->currPos.nextPage/so->currPos.prevPage is already P_NONE,
    2297             :  * or unless so->currPos.moreRight/so->currPos.moreLeft is already unset).
    2298             :  *
    2299             :  * On success exit, so->currPos is updated to contain data from the next
    2300             :  * interesting page, and we return true.  We hold a pin on the buffer on
    2301             :  * success exit (except during so->dropPin index scans, when we drop the pin
    2302             :  * eagerly to avoid blocking VACUUM).
    2303             :  *
    2304             :  * If there are no more matching records in the given direction, we drop all
    2305             :  * locks and pins, invalidate so->currPos, and return false.
    2306             :  *
    2307             :  * We always release the scan for a parallel scan caller, regardless of
    2308             :  * success or failure; we'll call _bt_parallel_release as soon as possible.
    2309             :  */
    2310             : static bool
    2311     6529786 : _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno,
    2312             :                  BlockNumber lastcurrblkno, ScanDirection dir, bool seized)
    2313             : {
    2314     6529786 :     Relation    rel = scan->indexRelation;
    2315     6529786 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
    2316             : 
    2317             :     Assert(so->currPos.currPage == lastcurrblkno || seized);
    2318             :     Assert(!(blkno == P_NONE && seized));
    2319             :     Assert(!BTScanPosIsPinned(so->currPos));
    2320             : 
    2321             :     /*
    2322             :      * Remember that the scan already read lastcurrblkno, a page to the left
    2323             :      * of blkno (or remember reading a page to the right, for backwards scans)
    2324             :      */
    2325     6529786 :     if (ScanDirectionIsForward(dir))
    2326     6529560 :         so->currPos.moreLeft = true;
    2327             :     else
    2328         226 :         so->currPos.moreRight = true;
    2329             : 
    2330             :     for (;;)
    2331        2212 :     {
    2332             :         Page        page;
    2333             :         BTPageOpaque opaque;
    2334             : 
    2335     6531998 :         if (blkno == P_NONE ||
    2336             :             (ScanDirectionIsForward(dir) ?
    2337     2079496 :              !so->currPos.moreRight : !so->currPos.moreLeft))
    2338             :         {
    2339             :             /* most recent _bt_readpage call (for lastcurrblkno) ended scan */
    2340             :             Assert(so->currPos.currPage == lastcurrblkno && !seized);
    2341     6496874 :             BTScanPosInvalidate(so->currPos);
    2342     6496874 :             _bt_parallel_done(scan);    /* iff !so->needPrimScan */
    2343     6496874 :             return false;
    2344             :         }
    2345             : 
    2346             :         Assert(!so->needPrimScan);
    2347             : 
    2348             :         /* parallel scan must never actually visit so->currPos blkno */
    2349       35124 :         if (!seized && scan->parallel_scan != NULL &&
    2350        1212 :             !_bt_parallel_seize(scan, &blkno, &lastcurrblkno, false))
    2351             :         {
    2352             :             /* whole scan is now done (or another primitive scan required) */
    2353          32 :             BTScanPosInvalidate(so->currPos);
    2354          32 :             return false;
    2355             :         }
    2356             : 
    2357       35092 :         if (ScanDirectionIsForward(dir))
    2358             :         {
    2359             :             /* read blkno, but check for interrupts first */
    2360       34954 :             CHECK_FOR_INTERRUPTS();
    2361       34954 :             so->currPos.buf = _bt_getbuf(rel, blkno, BT_READ);
    2362             :         }
    2363             :         else
    2364             :         {
    2365             :             /* read blkno, avoiding race (also checks for interrupts) */
    2366         138 :             so->currPos.buf = _bt_lock_and_validate_left(rel, &blkno,
    2367             :                                                          lastcurrblkno);
    2368         138 :             if (so->currPos.buf == InvalidBuffer)
    2369             :             {
    2370             :                 /* must have been a concurrent deletion of leftmost page */
    2371           0 :                 BTScanPosInvalidate(so->currPos);
    2372           0 :                 _bt_parallel_done(scan);
    2373           0 :                 return false;
    2374             :             }
    2375             :         }
    2376             : 
    2377       35092 :         page = BufferGetPage(so->currPos.buf);
    2378       35092 :         opaque = BTPageGetOpaque(page);
    2379       35092 :         lastcurrblkno = blkno;
    2380       35092 :         if (likely(!P_IGNORE(opaque)))
    2381             :         {
    2382             :             /* see if there are any matches on this page */
    2383       35092 :             if (ScanDirectionIsForward(dir))
    2384             :             {
    2385             :                 /* note that this will clear moreRight if we can stop */
    2386       34954 :                 if (_bt_readpage(scan, dir, P_FIRSTDATAKEY(opaque), seized))
    2387       32764 :                     break;
    2388        2190 :                 blkno = so->currPos.nextPage;
    2389             :             }
    2390             :             else
    2391             :             {
    2392             :                 /* note that this will clear moreLeft if we can stop */
    2393         138 :                 if (_bt_readpage(scan, dir, PageGetMaxOffsetNumber(page), seized))
    2394         116 :                     break;
    2395          22 :                 blkno = so->currPos.prevPage;
    2396             :             }
    2397             :         }
    2398             :         else
    2399             :         {
    2400             :             /* _bt_readpage not called, so do all this for ourselves */
    2401           0 :             if (ScanDirectionIsForward(dir))
    2402           0 :                 blkno = opaque->btpo_next;
    2403             :             else
    2404           0 :                 blkno = opaque->btpo_prev;
    2405           0 :             if (scan->parallel_scan != NULL)
    2406           0 :                 _bt_parallel_release(scan, blkno, lastcurrblkno);
    2407             :         }
    2408             : 
    2409             :         /* no matching tuples on this page */
    2410        2212 :         _bt_relbuf(rel, so->currPos.buf);
    2411        2212 :         seized = false;         /* released by _bt_readpage (or by us) */
    2412             :     }
    2413             : 
    2414             :     /*
    2415             :      * _bt_readpage succeeded.  Drop the lock (and maybe the pin) on
    2416             :      * so->currPos.buf in preparation for btgettuple returning tuples.
    2417             :      */
    2418             :     Assert(so->currPos.currPage == blkno);
    2419             :     Assert(BTScanPosIsPinned(so->currPos));
    2420       32880 :     _bt_drop_lock_and_maybe_pin(rel, so);
    2421             : 
    2422       32880 :     return true;
    2423             : }
    2424             : 
    2425             : /*
    2426             :  * _bt_lock_and_validate_left() -- lock caller's left sibling blkno,
    2427             :  * recovering from concurrent page splits/page deletions when necessary
    2428             :  *
    2429             :  * Called during backwards scans, to deal with their unique concurrency rules.
    2430             :  *
    2431             :  * blkno points to the block number of the page that we expect to move the
    2432             :  * scan to.  We'll successfully move the scan there when we find that its
    2433             :  * right sibling link still points to lastcurrblkno (the page we just read).
    2434             :  * Otherwise, we have to figure out which page is the correct one for the scan
    2435             :  * to now read the hard way, reasoning about concurrent splits and deletions.
    2436             :  * See nbtree/README.
    2437             :  *
    2438             :  * On return, we have both a pin and a read lock on the returned page, whose
    2439             :  * block number will be set in *blkno.  Returns InvalidBuffer if there is no
    2440             :  * page to the left (no lock or pin is held in that case).
    2441             :  *
    2442             :  * It is possible for the returned leaf page to be half-dead; caller must
    2443             :  * check that condition and step left again when required.
    2444             :  */
    2445             : static Buffer
    2446         138 : _bt_lock_and_validate_left(Relation rel, BlockNumber *blkno,
    2447             :                            BlockNumber lastcurrblkno)
    2448             : {
    2449         138 :     BlockNumber origblkno = *blkno; /* detects circular links */
    2450             : 
    2451             :     for (;;)
    2452           0 :     {
    2453             :         Buffer      buf;
    2454             :         Page        page;
    2455             :         BTPageOpaque opaque;
    2456             :         int         tries;
    2457             : 
    2458             :         /* check for interrupts while we're not holding any buffer lock */
    2459         138 :         CHECK_FOR_INTERRUPTS();
    2460         138 :         buf = _bt_getbuf(rel, *blkno, BT_READ);
    2461         138 :         page = BufferGetPage(buf);
    2462         138 :         opaque = BTPageGetOpaque(page);
    2463             : 
    2464             :         /*
    2465             :          * If this isn't the page we want, walk right till we find what we
    2466             :          * want --- but go no more than four hops (an arbitrary limit). If we
    2467             :          * don't find the correct page by then, the most likely bet is that
    2468             :          * lastcurrblkno got deleted and isn't in the sibling chain at all
    2469             :          * anymore, not that its left sibling got split more than four times.
    2470             :          *
    2471             :          * Note that it is correct to test P_ISDELETED not P_IGNORE here,
    2472             :          * because half-dead pages are still in the sibling chain.
    2473             :          */
    2474         138 :         tries = 0;
    2475             :         for (;;)
    2476             :         {
    2477         138 :             if (likely(!P_ISDELETED(opaque) &&
    2478             :                        opaque->btpo_next == lastcurrblkno))
    2479             :             {
    2480             :                 /* Found desired page, return it */
    2481         138 :                 return buf;
    2482             :             }
    2483           0 :             if (P_RIGHTMOST(opaque) || ++tries > 4)
    2484             :                 break;
    2485             :             /* step right */
    2486           0 :             *blkno = opaque->btpo_next;
    2487           0 :             buf = _bt_relandgetbuf(rel, buf, *blkno, BT_READ);
    2488           0 :             page = BufferGetPage(buf);
    2489           0 :             opaque = BTPageGetOpaque(page);
    2490             :         }
    2491             : 
    2492             :         /*
    2493             :          * Return to the original page (usually the page most recently read by
    2494             :          * _bt_readpage, which is passed by caller as lastcurrblkno) to see
    2495             :          * what's up with its prev sibling link
    2496             :          */
    2497           0 :         buf = _bt_relandgetbuf(rel, buf, lastcurrblkno, BT_READ);
    2498           0 :         page = BufferGetPage(buf);
    2499           0 :         opaque = BTPageGetOpaque(page);
    2500           0 :         if (P_ISDELETED(opaque))
    2501             :         {
    2502             :             /*
    2503             :              * It was deleted.  Move right to first nondeleted page (there
    2504             :              * must be one); that is the page that has acquired the deleted
    2505             :              * one's keyspace, so stepping left from it will take us where we
    2506             :              * want to be.
    2507             :              */
    2508             :             for (;;)
    2509             :             {
    2510           0 :                 if (P_RIGHTMOST(opaque))
    2511           0 :                     elog(ERROR, "fell off the end of index \"%s\"",
    2512             :                          RelationGetRelationName(rel));
    2513           0 :                 lastcurrblkno = opaque->btpo_next;
    2514           0 :                 buf = _bt_relandgetbuf(rel, buf, lastcurrblkno, BT_READ);
    2515           0 :                 page = BufferGetPage(buf);
    2516           0 :                 opaque = BTPageGetOpaque(page);
    2517           0 :                 if (!P_ISDELETED(opaque))
    2518           0 :                     break;
    2519             :             }
    2520             :         }
    2521             :         else
    2522             :         {
    2523             :             /*
    2524             :              * Original lastcurrblkno wasn't deleted; the explanation had
    2525             :              * better be that the page to the left got split or deleted.
    2526             :              * Without this check, we risk going into an infinite loop.
    2527             :              */
    2528           0 :             if (opaque->btpo_prev == origblkno)
    2529           0 :                 elog(ERROR, "could not find left sibling of block %u in index \"%s\"",
    2530             :                      lastcurrblkno, RelationGetRelationName(rel));
    2531             :             /* Okay to try again, since left sibling link changed */
    2532             :         }
    2533             : 
    2534             :         /*
    2535             :          * Original lastcurrblkno from caller was concurrently deleted (could
    2536             :          * also have been a great many concurrent left sibling page splits).
    2537             :          * Found a non-deleted page that should now act as our lastcurrblkno.
    2538             :          */
    2539           0 :         if (P_LEFTMOST(opaque))
    2540             :         {
    2541             :             /* New lastcurrblkno has no left sibling (concurrently deleted) */
    2542           0 :             _bt_relbuf(rel, buf);
    2543           0 :             break;
    2544             :         }
    2545             : 
    2546             :         /* Start from scratch with new lastcurrblkno's blkno/prev link */
    2547           0 :         *blkno = origblkno = opaque->btpo_prev;
    2548           0 :         _bt_relbuf(rel, buf);
    2549             :     }
    2550             : 
    2551           0 :     return InvalidBuffer;
    2552             : }
    2553             : 
    2554             : /*
    2555             :  * _bt_get_endpoint() -- Find the first or last page on a given tree level
    2556             :  *
    2557             :  * If the index is empty, we will return InvalidBuffer; any other failure
    2558             :  * condition causes ereport().  We will not return a dead page.
    2559             :  *
    2560             :  * The returned buffer is pinned and read-locked.
    2561             :  */
    2562             : Buffer
    2563       87254 : _bt_get_endpoint(Relation rel, uint32 level, bool rightmost)
    2564             : {
    2565             :     Buffer      buf;
    2566             :     Page        page;
    2567             :     BTPageOpaque opaque;
    2568             :     OffsetNumber offnum;
    2569             :     BlockNumber blkno;
    2570             :     IndexTuple  itup;
    2571             : 
    2572             :     /*
    2573             :      * If we are looking for a leaf page, okay to descend from fast root;
    2574             :      * otherwise better descend from true root.  (There is no point in being
    2575             :      * smarter about intermediate levels.)
    2576             :      */
    2577       87254 :     if (level == 0)
    2578       87230 :         buf = _bt_getroot(rel, NULL, BT_READ);
    2579             :     else
    2580          24 :         buf = _bt_gettrueroot(rel);
    2581             : 
    2582       87254 :     if (!BufferIsValid(buf))
    2583        7214 :         return InvalidBuffer;
    2584             : 
    2585       80040 :     page = BufferGetPage(buf);
    2586       80040 :     opaque = BTPageGetOpaque(page);
    2587             : 
    2588             :     for (;;)
    2589             :     {
    2590             :         /*
    2591             :          * If we landed on a deleted page, step right to find a live page
    2592             :          * (there must be one).  Also, if we want the rightmost page, step
    2593             :          * right if needed to get to it (this could happen if the page split
    2594             :          * since we obtained a pointer to it).
    2595             :          */
    2596      101976 :         while (P_IGNORE(opaque) ||
    2597          66 :                (rightmost && !P_RIGHTMOST(opaque)))
    2598             :         {
    2599           0 :             blkno = opaque->btpo_next;
    2600           0 :             if (blkno == P_NONE)
    2601           0 :                 elog(ERROR, "fell off the end of index \"%s\"",
    2602             :                      RelationGetRelationName(rel));
    2603           0 :             buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ);
    2604           0 :             page = BufferGetPage(buf);
    2605           0 :             opaque = BTPageGetOpaque(page);
    2606             :         }
    2607             : 
    2608             :         /* Done? */
    2609      101976 :         if (opaque->btpo_level == level)
    2610       80040 :             break;
    2611       21936 :         if (opaque->btpo_level < level)
    2612           0 :             ereport(ERROR,
    2613             :                     (errcode(ERRCODE_INDEX_CORRUPTED),
    2614             :                      errmsg_internal("btree level %u not found in index \"%s\"",
    2615             :                                      level, RelationGetRelationName(rel))));
    2616             : 
    2617             :         /* Descend to leftmost or rightmost child page */
    2618       21936 :         if (rightmost)
    2619           6 :             offnum = PageGetMaxOffsetNumber(page);
    2620             :         else
    2621       21930 :             offnum = P_FIRSTDATAKEY(opaque);
    2622             : 
    2623       21936 :         itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
    2624       21936 :         blkno = BTreeTupleGetDownLink(itup);
    2625             : 
    2626       21936 :         buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ);
    2627       21936 :         page = BufferGetPage(buf);
    2628       21936 :         opaque = BTPageGetOpaque(page);
    2629             :     }
    2630             : 
    2631       80040 :     return buf;
    2632             : }
    2633             : 
    2634             : /*
    2635             :  *  _bt_endpoint() -- Find the first or last page in the index, and scan
    2636             :  * from there to the first key satisfying all the quals.
    2637             :  *
    2638             :  * This is used by _bt_first() to set up a scan when we've determined
    2639             :  * that the scan must start at the beginning or end of the index (for
    2640             :  * a forward or backward scan respectively).
    2641             :  *
    2642             :  * Parallel scan callers must have seized the scan before calling here.
    2643             :  * Exit conditions are the same as for _bt_first().
    2644             :  */
    2645             : static bool
    2646       87230 : _bt_endpoint(IndexScanDesc scan, ScanDirection dir)
    2647             : {
    2648       87230 :     Relation    rel = scan->indexRelation;
    2649       87230 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
    2650             :     Page        page;
    2651             :     BTPageOpaque opaque;
    2652             :     OffsetNumber start;
    2653             : 
    2654             :     Assert(!BTScanPosIsValid(so->currPos));
    2655             :     Assert(!so->needPrimScan);
    2656             : 
    2657             :     /*
    2658             :      * Scan down to the leftmost or rightmost leaf page.  This is a simplified
    2659             :      * version of _bt_search().
    2660             :      */
    2661       87230 :     so->currPos.buf = _bt_get_endpoint(rel, 0, ScanDirectionIsBackward(dir));
    2662             : 
    2663       87230 :     if (!BufferIsValid(so->currPos.buf))
    2664             :     {
    2665             :         /*
    2666             :          * Empty index. Lock the whole relation, as nothing finer to lock
    2667             :          * exists.
    2668             :          */
    2669        7214 :         PredicateLockRelation(rel, scan->xs_snapshot);
    2670        7214 :         _bt_parallel_done(scan);
    2671        7214 :         return false;
    2672             :     }
    2673             : 
    2674       80016 :     page = BufferGetPage(so->currPos.buf);
    2675       80016 :     opaque = BTPageGetOpaque(page);
    2676             :     Assert(P_ISLEAF(opaque));
    2677             : 
    2678       80016 :     if (ScanDirectionIsForward(dir))
    2679             :     {
    2680             :         /* There could be dead pages to the left, so not this: */
    2681             :         /* Assert(P_LEFTMOST(opaque)); */
    2682             : 
    2683       79956 :         start = P_FIRSTDATAKEY(opaque);
    2684             :     }
    2685          60 :     else if (ScanDirectionIsBackward(dir))
    2686             :     {
    2687             :         Assert(P_RIGHTMOST(opaque));
    2688             : 
    2689          60 :         start = PageGetMaxOffsetNumber(page);
    2690             :     }
    2691             :     else
    2692             :     {
    2693           0 :         elog(ERROR, "invalid scan direction: %d", (int) dir);
    2694             :         start = 0;              /* keep compiler quiet */
    2695             :     }
    2696             : 
    2697             :     /*
    2698             :      * Now load data from the first page of the scan.
    2699             :      */
    2700       80016 :     if (!_bt_readfirstpage(scan, start, dir))
    2701        1768 :         return false;
    2702             : 
    2703       78248 :     _bt_returnitem(scan, so);
    2704       78248 :     return true;
    2705             : }

Generated by: LCOV version 1.16