LCOV - code coverage report
Current view: top level - src/backend/access/nbtree - nbtree.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18beta1 Lines: 488 562 86.8 %
Date: 2025-06-27 17:17:16 Functions: 26 28 92.9 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * nbtree.c
       4             :  *    Implementation of Lehman and Yao's btree management algorithm for
       5             :  *    Postgres.
       6             :  *
       7             :  * NOTES
       8             :  *    This file contains only the public interface routines.
       9             :  *
      10             :  *
      11             :  * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
      12             :  * Portions Copyright (c) 1994, Regents of the University of California
      13             :  *
      14             :  * IDENTIFICATION
      15             :  *    src/backend/access/nbtree/nbtree.c
      16             :  *
      17             :  *-------------------------------------------------------------------------
      18             :  */
      19             : #include "postgres.h"
      20             : 
      21             : #include "access/nbtree.h"
      22             : #include "access/relscan.h"
      23             : #include "access/stratnum.h"
      24             : #include "commands/progress.h"
      25             : #include "commands/vacuum.h"
      26             : #include "nodes/execnodes.h"
      27             : #include "pgstat.h"
      28             : #include "storage/bulk_write.h"
      29             : #include "storage/condition_variable.h"
      30             : #include "storage/indexfsm.h"
      31             : #include "storage/ipc.h"
      32             : #include "storage/lmgr.h"
      33             : #include "storage/read_stream.h"
      34             : #include "utils/datum.h"
      35             : #include "utils/fmgrprotos.h"
      36             : #include "utils/index_selfuncs.h"
      37             : #include "utils/memutils.h"
      38             : 
      39             : 
      40             : /*
      41             :  * BTPARALLEL_NOT_INITIALIZED indicates that the scan has not started.
      42             :  *
      43             :  * BTPARALLEL_NEED_PRIMSCAN indicates that some process must now seize the
      44             :  * scan to advance it via another call to _bt_first.
      45             :  *
      46             :  * BTPARALLEL_ADVANCING indicates that some process is advancing the scan to
      47             :  * a new page; others must wait.
      48             :  *
      49             :  * BTPARALLEL_IDLE indicates that no backend is currently advancing the scan
      50             :  * to a new page; some process can start doing that.
      51             :  *
      52             :  * BTPARALLEL_DONE indicates that the scan is complete (including error exit).
      53             :  */
      54             : typedef enum
      55             : {
      56             :     BTPARALLEL_NOT_INITIALIZED,
      57             :     BTPARALLEL_NEED_PRIMSCAN,
      58             :     BTPARALLEL_ADVANCING,
      59             :     BTPARALLEL_IDLE,
      60             :     BTPARALLEL_DONE,
      61             : } BTPS_State;
      62             : 
      63             : /*
      64             :  * BTParallelScanDescData contains btree specific shared information required
      65             :  * for parallel scan.
      66             :  */
      67             : typedef struct BTParallelScanDescData
      68             : {
      69             :     BlockNumber btps_nextScanPage;  /* next page to be scanned */
      70             :     BlockNumber btps_lastCurrPage;  /* page whose sibling link was copied into
      71             :                                      * btps_nextScanPage */
      72             :     BTPS_State  btps_pageStatus;    /* indicates whether next page is
      73             :                                      * available for scan. see above for
      74             :                                      * possible states of parallel scan. */
      75             :     LWLock      btps_lock;      /* protects shared parallel state */
      76             :     ConditionVariable btps_cv;  /* used to synchronize parallel scan */
      77             : 
      78             :     /*
      79             :      * btps_arrElems is used when scans need to schedule another primitive
      80             :      * index scan with one or more SAOP arrays.  Holds BTArrayKeyInfo.cur_elem
      81             :      * offsets for each = scan key associated with a ScalarArrayOp array.
      82             :      */
      83             :     int         btps_arrElems[FLEXIBLE_ARRAY_MEMBER];
      84             : 
      85             :     /*
      86             :      * Additional space (at the end of the struct) is used when scans need to
      87             :      * schedule another primitive index scan with one or more skip arrays.
      88             :      * Holds a flattened datum representation for each = scan key associated
      89             :      * with a skip array.
      90             :      */
      91             : }           BTParallelScanDescData;
      92             : 
      93             : typedef struct BTParallelScanDescData *BTParallelScanDesc;
      94             : 
      95             : 
      96             : static void _bt_parallel_serialize_arrays(Relation rel, BTParallelScanDesc btscan,
      97             :                                           BTScanOpaque so);
      98             : static void _bt_parallel_restore_arrays(Relation rel, BTParallelScanDesc btscan,
      99             :                                         BTScanOpaque so);
     100             : static void btvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
     101             :                          IndexBulkDeleteCallback callback, void *callback_state,
     102             :                          BTCycleId cycleid);
     103             : static BlockNumber btvacuumpage(BTVacState *vstate, Buffer buf);
     104             : static BTVacuumPosting btreevacuumposting(BTVacState *vstate,
     105             :                                           IndexTuple posting,
     106             :                                           OffsetNumber updatedoffset,
     107             :                                           int *nremaining);
     108             : 
     109             : 
     110             : /*
     111             :  * Btree handler function: return IndexAmRoutine with access method parameters
     112             :  * and callbacks.
     113             :  */
     114             : Datum
     115     3284628 : bthandler(PG_FUNCTION_ARGS)
     116             : {
     117     3284628 :     IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
     118             : 
     119     3284628 :     amroutine->amstrategies = BTMaxStrategyNumber;
     120     3284628 :     amroutine->amsupport = BTNProcs;
     121     3284628 :     amroutine->amoptsprocnum = BTOPTIONS_PROC;
     122     3284628 :     amroutine->amcanorder = true;
     123     3284628 :     amroutine->amcanorderbyop = false;
     124     3284628 :     amroutine->amcanhash = false;
     125     3284628 :     amroutine->amconsistentequality = true;
     126     3284628 :     amroutine->amconsistentordering = true;
     127     3284628 :     amroutine->amcanbackward = true;
     128     3284628 :     amroutine->amcanunique = true;
     129     3284628 :     amroutine->amcanmulticol = true;
     130     3284628 :     amroutine->amoptionalkey = true;
     131     3284628 :     amroutine->amsearcharray = true;
     132     3284628 :     amroutine->amsearchnulls = true;
     133     3284628 :     amroutine->amstorage = false;
     134     3284628 :     amroutine->amclusterable = true;
     135     3284628 :     amroutine->ampredlocks = true;
     136     3284628 :     amroutine->amcanparallel = true;
     137     3284628 :     amroutine->amcanbuildparallel = true;
     138     3284628 :     amroutine->amcaninclude = true;
     139     3284628 :     amroutine->amusemaintenanceworkmem = false;
     140     3284628 :     amroutine->amsummarizing = false;
     141     3284628 :     amroutine->amparallelvacuumoptions =
     142             :         VACUUM_OPTION_PARALLEL_BULKDEL | VACUUM_OPTION_PARALLEL_COND_CLEANUP;
     143     3284628 :     amroutine->amkeytype = InvalidOid;
     144             : 
     145     3284628 :     amroutine->ambuild = btbuild;
     146     3284628 :     amroutine->ambuildempty = btbuildempty;
     147     3284628 :     amroutine->aminsert = btinsert;
     148     3284628 :     amroutine->aminsertcleanup = NULL;
     149     3284628 :     amroutine->ambulkdelete = btbulkdelete;
     150     3284628 :     amroutine->amvacuumcleanup = btvacuumcleanup;
     151     3284628 :     amroutine->amcanreturn = btcanreturn;
     152     3284628 :     amroutine->amcostestimate = btcostestimate;
     153     3284628 :     amroutine->amgettreeheight = btgettreeheight;
     154     3284628 :     amroutine->amoptions = btoptions;
     155     3284628 :     amroutine->amproperty = btproperty;
     156     3284628 :     amroutine->ambuildphasename = btbuildphasename;
     157     3284628 :     amroutine->amvalidate = btvalidate;
     158     3284628 :     amroutine->amadjustmembers = btadjustmembers;
     159     3284628 :     amroutine->ambeginscan = btbeginscan;
     160     3284628 :     amroutine->amrescan = btrescan;
     161     3284628 :     amroutine->amgettuple = btgettuple;
     162     3284628 :     amroutine->amgetbitmap = btgetbitmap;
     163     3284628 :     amroutine->amendscan = btendscan;
     164     3284628 :     amroutine->ammarkpos = btmarkpos;
     165     3284628 :     amroutine->amrestrpos = btrestrpos;
     166     3284628 :     amroutine->amestimateparallelscan = btestimateparallelscan;
     167     3284628 :     amroutine->aminitparallelscan = btinitparallelscan;
     168     3284628 :     amroutine->amparallelrescan = btparallelrescan;
     169     3284628 :     amroutine->amtranslatestrategy = bttranslatestrategy;
     170     3284628 :     amroutine->amtranslatecmptype = bttranslatecmptype;
     171             : 
     172     3284628 :     PG_RETURN_POINTER(amroutine);
     173             : }
     174             : 
     175             : /*
     176             :  *  btbuildempty() -- build an empty btree index in the initialization fork
     177             :  */
     178             : void
     179         164 : btbuildempty(Relation index)
     180             : {
     181         164 :     bool        allequalimage = _bt_allequalimage(index, false);
     182             :     BulkWriteState *bulkstate;
     183             :     BulkWriteBuffer metabuf;
     184             : 
     185         164 :     bulkstate = smgr_bulk_start_rel(index, INIT_FORKNUM);
     186             : 
     187             :     /* Construct metapage. */
     188         164 :     metabuf = smgr_bulk_get_buf(bulkstate);
     189         164 :     _bt_initmetapage((Page) metabuf, P_NONE, 0, allequalimage);
     190         164 :     smgr_bulk_write(bulkstate, BTREE_METAPAGE, metabuf, true);
     191             : 
     192         164 :     smgr_bulk_finish(bulkstate);
     193         164 : }
     194             : 
     195             : /*
     196             :  *  btinsert() -- insert an index tuple into a btree.
     197             :  *
     198             :  *      Descend the tree recursively, find the appropriate location for our
     199             :  *      new tuple, and put it there.
     200             :  */
     201             : bool
     202     7264292 : btinsert(Relation rel, Datum *values, bool *isnull,
     203             :          ItemPointer ht_ctid, Relation heapRel,
     204             :          IndexUniqueCheck checkUnique,
     205             :          bool indexUnchanged,
     206             :          IndexInfo *indexInfo)
     207             : {
     208             :     bool        result;
     209             :     IndexTuple  itup;
     210             : 
     211             :     /* generate an index tuple */
     212     7264292 :     itup = index_form_tuple(RelationGetDescr(rel), values, isnull);
     213     7264292 :     itup->t_tid = *ht_ctid;
     214             : 
     215     7264292 :     result = _bt_doinsert(rel, itup, checkUnique, indexUnchanged, heapRel);
     216             : 
     217     7263780 :     pfree(itup);
     218             : 
     219     7263780 :     return result;
     220             : }
     221             : 
     222             : /*
     223             :  *  btgettuple() -- Get the next tuple in the scan.
     224             :  */
     225             : bool
     226    35650960 : btgettuple(IndexScanDesc scan, ScanDirection dir)
     227             : {
     228    35650960 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     229             :     bool        res;
     230             : 
     231             :     Assert(scan->heapRelation != NULL);
     232             : 
     233             :     /* btree indexes are never lossy */
     234    35650960 :     scan->xs_recheck = false;
     235             : 
     236             :     /* Each loop iteration performs another primitive index scan */
     237             :     do
     238             :     {
     239             :         /*
     240             :          * If we've already initialized this scan, we can just advance it in
     241             :          * the appropriate direction.  If we haven't done so yet, we call
     242             :          * _bt_first() to get the first item in the scan.
     243             :          */
     244    35667872 :         if (!BTScanPosIsValid(so->currPos))
     245    15973326 :             res = _bt_first(scan, dir);
     246             :         else
     247             :         {
     248             :             /*
     249             :              * Check to see if we should kill the previously-fetched tuple.
     250             :              */
     251    19694546 :             if (scan->kill_prior_tuple)
     252             :             {
     253             :                 /*
     254             :                  * Yes, remember it for later. (We'll deal with all such
     255             :                  * tuples at once right before leaving the index page.)  The
     256             :                  * test for numKilled overrun is not just paranoia: if the
     257             :                  * caller reverses direction in the indexscan then the same
     258             :                  * item might get entered multiple times. It's not worth
     259             :                  * trying to optimize that, so we don't detect it, but instead
     260             :                  * just forget any excess entries.
     261             :                  */
     262      487092 :                 if (so->killedItems == NULL)
     263      171652 :                     so->killedItems = (int *)
     264      171652 :                         palloc(MaxTIDsPerBTreePage * sizeof(int));
     265      487092 :                 if (so->numKilled < MaxTIDsPerBTreePage)
     266      487092 :                     so->killedItems[so->numKilled++] = so->currPos.itemIndex;
     267             :             }
     268             : 
     269             :             /*
     270             :              * Now continue the scan.
     271             :              */
     272    19694546 :             res = _bt_next(scan, dir);
     273             :         }
     274             : 
     275             :         /* If we have a tuple, return it ... */
     276    35667872 :         if (res)
     277    28613888 :             break;
     278             :         /* ... otherwise see if we need another primitive index scan */
     279     7053984 :     } while (so->numArrayKeys && _bt_start_prim_scan(scan, dir));
     280             : 
     281    35650960 :     return res;
     282             : }
     283             : 
     284             : /*
     285             :  * btgetbitmap() -- gets all matching tuples, and adds them to a bitmap
     286             :  */
     287             : int64
     288       13066 : btgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
     289             : {
     290       13066 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     291       13066 :     int64       ntids = 0;
     292             :     ItemPointer heapTid;
     293             : 
     294             :     Assert(scan->heapRelation == NULL);
     295             : 
     296             :     /* Each loop iteration performs another primitive index scan */
     297             :     do
     298             :     {
     299             :         /* Fetch the first page & tuple */
     300       13696 :         if (_bt_first(scan, ForwardScanDirection))
     301             :         {
     302             :             /* Save tuple ID, and continue scanning */
     303        9766 :             heapTid = &scan->xs_heaptid;
     304        9766 :             tbm_add_tuples(tbm, heapTid, 1, false);
     305        9766 :             ntids++;
     306             : 
     307             :             for (;;)
     308             :             {
     309             :                 /*
     310             :                  * Advance to next tuple within page.  This is the same as the
     311             :                  * easy case in _bt_next().
     312             :                  */
     313     1998632 :                 if (++so->currPos.itemIndex > so->currPos.lastItem)
     314             :                 {
     315             :                     /* let _bt_next do the heavy lifting */
     316       15272 :                     if (!_bt_next(scan, ForwardScanDirection))
     317        9766 :                         break;
     318             :                 }
     319             : 
     320             :                 /* Save tuple ID, and continue scanning */
     321     1988866 :                 heapTid = &so->currPos.items[so->currPos.itemIndex].heapTid;
     322     1988866 :                 tbm_add_tuples(tbm, heapTid, 1, false);
     323     1988866 :                 ntids++;
     324             :             }
     325             :         }
     326             :         /* Now see if we need another primitive index scan */
     327       13696 :     } while (so->numArrayKeys && _bt_start_prim_scan(scan, ForwardScanDirection));
     328             : 
     329       13066 :     return ntids;
     330             : }
     331             : 
     332             : /*
     333             :  *  btbeginscan() -- start a scan on a btree index
     334             :  */
     335             : IndexScanDesc
     336    15293766 : btbeginscan(Relation rel, int nkeys, int norderbys)
     337             : {
     338             :     IndexScanDesc scan;
     339             :     BTScanOpaque so;
     340             : 
     341             :     /* no order by operators allowed */
     342             :     Assert(norderbys == 0);
     343             : 
     344             :     /* get the scan */
     345    15293766 :     scan = RelationGetIndexScan(rel, nkeys, norderbys);
     346             : 
     347             :     /* allocate private workspace */
     348    15293766 :     so = (BTScanOpaque) palloc(sizeof(BTScanOpaqueData));
     349    15293766 :     BTScanPosInvalidate(so->currPos);
     350    15293766 :     BTScanPosInvalidate(so->markPos);
     351    15293766 :     if (scan->numberOfKeys > 0)
     352    15280488 :         so->keyData = (ScanKey) palloc(scan->numberOfKeys * sizeof(ScanKeyData));
     353             :     else
     354       13278 :         so->keyData = NULL;
     355             : 
     356    15293766 :     so->skipScan = false;
     357    15293766 :     so->needPrimScan = false;
     358    15293766 :     so->scanBehind = false;
     359    15293766 :     so->oppositeDirCheck = false;
     360    15293766 :     so->arrayKeys = NULL;
     361    15293766 :     so->orderProcs = NULL;
     362    15293766 :     so->arrayContext = NULL;
     363             : 
     364    15293766 :     so->killedItems = NULL;      /* until needed */
     365    15293766 :     so->numKilled = 0;
     366             : 
     367             :     /*
     368             :      * We don't know yet whether the scan will be index-only, so we do not
     369             :      * allocate the tuple workspace arrays until btrescan.  However, we set up
     370             :      * scan->xs_itupdesc whether we'll need it or not, since that's so cheap.
     371             :      */
     372    15293766 :     so->currTuples = so->markTuples = NULL;
     373             : 
     374    15293766 :     scan->xs_itupdesc = RelationGetDescr(rel);
     375             : 
     376    15293766 :     scan->opaque = so;
     377             : 
     378    15293766 :     return scan;
     379             : }
     380             : 
     381             : /*
     382             :  *  btrescan() -- rescan an index relation
     383             :  */
     384             : void
     385    15970754 : btrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
     386             :          ScanKey orderbys, int norderbys)
     387             : {
     388    15970754 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     389             : 
     390             :     /* we aren't holding any read locks, but gotta drop the pins */
     391    15970754 :     if (BTScanPosIsValid(so->currPos))
     392             :     {
     393             :         /* Before leaving current page, deal with any killed items */
     394       71620 :         if (so->numKilled > 0)
     395        1006 :             _bt_killitems(scan);
     396       71620 :         BTScanPosUnpinIfPinned(so->currPos);
     397       71620 :         BTScanPosInvalidate(so->currPos);
     398             :     }
     399             : 
     400             :     /*
     401             :      * We prefer to eagerly drop leaf page pins before btgettuple returns.
     402             :      * This avoids making VACUUM wait to acquire a cleanup lock on the page.
     403             :      *
     404             :      * We cannot safely drop leaf page pins during index-only scans due to a
     405             :      * race condition involving VACUUM setting pages all-visible in the VM.
     406             :      * It's also unsafe for plain index scans that use a non-MVCC snapshot.
     407             :      *
     408             :      * When we drop pins eagerly, the mechanism that marks so->killedItems[]
     409             :      * index tuples LP_DEAD has to deal with concurrent TID recycling races.
     410             :      * The scheme used to detect unsafe TID recycling won't work when scanning
     411             :      * unlogged relations (since it involves saving an affected page's LSN).
     412             :      * Opt out of eager pin dropping during unlogged relation scans for now
     413             :      * (this is preferable to opting out of kill_prior_tuple LP_DEAD setting).
     414             :      *
     415             :      * Also opt out of dropping leaf page pins eagerly during bitmap scans.
     416             :      * Pins cannot be held for more than an instant during bitmap scans either
     417             :      * way, so we might as well avoid wasting cycles on acquiring page LSNs.
     418             :      *
     419             :      * See nbtree/README section on making concurrent TID recycling safe.
     420             :      *
     421             :      * Note: so->dropPin should never change across rescans.
     422             :      */
     423    47566362 :     so->dropPin = (!scan->xs_want_itup &&
     424    15624854 :                    IsMVCCSnapshot(scan->xs_snapshot) &&
     425    46030246 :                    RelationNeedsWAL(scan->indexRelation) &&
     426    14434638 :                    scan->heapRelation != NULL);
     427             : 
     428    15970754 :     so->markItemIndex = -1;
     429    15970754 :     so->needPrimScan = false;
     430    15970754 :     so->scanBehind = false;
     431    15970754 :     so->oppositeDirCheck = false;
     432    15970754 :     BTScanPosUnpinIfPinned(so->markPos);
     433    15970754 :     BTScanPosInvalidate(so->markPos);
     434             : 
     435             :     /*
     436             :      * Allocate tuple workspace arrays, if needed for an index-only scan and
     437             :      * not already done in a previous rescan call.  To save on palloc
     438             :      * overhead, both workspaces are allocated as one palloc block; only this
     439             :      * function and btendscan know that.
     440             :      *
     441             :      * NOTE: this data structure also makes it safe to return data from a
     442             :      * "name" column, even though btree name_ops uses an underlying storage
     443             :      * datatype of cstring.  The risk there is that "name" is supposed to be
     444             :      * padded to NAMEDATALEN, but the actual index tuple is probably shorter.
     445             :      * However, since we only return data out of tuples sitting in the
     446             :      * currTuples array, a fetch of NAMEDATALEN bytes can at worst pull some
     447             :      * data out of the markTuples array --- running off the end of memory for
     448             :      * a SIGSEGV is not possible.  Yeah, this is ugly as sin, but it beats
     449             :      * adding special-case treatment for name_ops elsewhere.
     450             :      */
     451    15970754 :     if (scan->xs_want_itup && so->currTuples == NULL)
     452             :     {
     453      135502 :         so->currTuples = (char *) palloc(BLCKSZ * 2);
     454      135502 :         so->markTuples = so->currTuples + BLCKSZ;
     455             :     }
     456             : 
     457             :     /*
     458             :      * Reset the scan keys
     459             :      */
     460    15970754 :     if (scankey && scan->numberOfKeys > 0)
     461    15957282 :         memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
     462    15970754 :     so->numberOfKeys = 0;        /* until _bt_preprocess_keys sets it */
     463    15970754 :     so->numArrayKeys = 0;        /* ditto */
     464    15970754 : }
     465             : 
     466             : /*
     467             :  *  btendscan() -- close down a scan
     468             :  */
     469             : void
     470    15292200 : btendscan(IndexScanDesc scan)
     471             : {
     472    15292200 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     473             : 
     474             :     /* we aren't holding any read locks, but gotta drop the pins */
     475    15292200 :     if (BTScanPosIsValid(so->currPos))
     476             :     {
     477             :         /* Before leaving current page, deal with any killed items */
     478     8846612 :         if (so->numKilled > 0)
     479       93178 :             _bt_killitems(scan);
     480     8846612 :         BTScanPosUnpinIfPinned(so->currPos);
     481             :     }
     482             : 
     483    15292200 :     so->markItemIndex = -1;
     484    15292200 :     BTScanPosUnpinIfPinned(so->markPos);
     485             : 
     486             :     /* No need to invalidate positions, the RAM is about to be freed. */
     487             : 
     488             :     /* Release storage */
     489    15292200 :     if (so->keyData != NULL)
     490    15278952 :         pfree(so->keyData);
     491             :     /* so->arrayKeys and so->orderProcs are in arrayContext */
     492    15292200 :     if (so->arrayContext != NULL)
     493        4494 :         MemoryContextDelete(so->arrayContext);
     494    15292200 :     if (so->killedItems != NULL)
     495      171586 :         pfree(so->killedItems);
     496    15292200 :     if (so->currTuples != NULL)
     497      135458 :         pfree(so->currTuples);
     498             :     /* so->markTuples should not be pfree'd, see btrescan */
     499    15292200 :     pfree(so);
     500    15292200 : }
     501             : 
     502             : /*
     503             :  *  btmarkpos() -- save current scan position
     504             :  */
     505             : void
     506      130138 : btmarkpos(IndexScanDesc scan)
     507             : {
     508      130138 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     509             : 
     510             :     /* There may be an old mark with a pin (but no lock). */
     511      130138 :     BTScanPosUnpinIfPinned(so->markPos);
     512             : 
     513             :     /*
     514             :      * Just record the current itemIndex.  If we later step to next page
     515             :      * before releasing the marked position, _bt_steppage makes a full copy of
     516             :      * the currPos struct in markPos.  If (as often happens) the mark is moved
     517             :      * before we leave the page, we don't have to do that work.
     518             :      */
     519      130138 :     if (BTScanPosIsValid(so->currPos))
     520      130138 :         so->markItemIndex = so->currPos.itemIndex;
     521             :     else
     522             :     {
     523           0 :         BTScanPosInvalidate(so->markPos);
     524           0 :         so->markItemIndex = -1;
     525             :     }
     526      130138 : }
     527             : 
     528             : /*
     529             :  *  btrestrpos() -- restore scan to last saved position
     530             :  */
     531             : void
     532       54066 : btrestrpos(IndexScanDesc scan)
     533             : {
     534       54066 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     535             : 
     536       54066 :     if (so->markItemIndex >= 0)
     537             :     {
     538             :         /*
     539             :          * The scan has never moved to a new page since the last mark.  Just
     540             :          * restore the itemIndex.
     541             :          *
     542             :          * NB: In this case we can't count on anything in so->markPos to be
     543             :          * accurate.
     544             :          */
     545       53958 :         so->currPos.itemIndex = so->markItemIndex;
     546             :     }
     547             :     else
     548             :     {
     549             :         /*
     550             :          * The scan moved to a new page after last mark or restore, and we are
     551             :          * now restoring to the marked page.  We aren't holding any read
     552             :          * locks, but if we're still holding the pin for the current position,
     553             :          * we must drop it.
     554             :          */
     555         108 :         if (BTScanPosIsValid(so->currPos))
     556             :         {
     557             :             /* Before leaving current page, deal with any killed items */
     558         108 :             if (so->numKilled > 0)
     559           0 :                 _bt_killitems(scan);
     560         108 :             BTScanPosUnpinIfPinned(so->currPos);
     561             :         }
     562             : 
     563         108 :         if (BTScanPosIsValid(so->markPos))
     564             :         {
     565             :             /* bump pin on mark buffer for assignment to current buffer */
     566         108 :             if (BTScanPosIsPinned(so->markPos))
     567           0 :                 IncrBufferRefCount(so->markPos.buf);
     568         108 :             memcpy(&so->currPos, &so->markPos,
     569             :                    offsetof(BTScanPosData, items[1]) +
     570         108 :                    so->markPos.lastItem * sizeof(BTScanPosItem));
     571         108 :             if (so->currTuples)
     572           0 :                 memcpy(so->currTuples, so->markTuples,
     573           0 :                        so->markPos.nextTupleOffset);
     574             :             /* Reset the scan's array keys (see _bt_steppage for why) */
     575         108 :             if (so->numArrayKeys)
     576             :             {
     577           0 :                 _bt_start_array_keys(scan, so->currPos.dir);
     578           0 :                 so->needPrimScan = false;
     579             :             }
     580             :         }
     581             :         else
     582           0 :             BTScanPosInvalidate(so->currPos);
     583             :     }
     584       54066 : }
     585             : 
     586             : /*
     587             :  * btestimateparallelscan -- estimate storage for BTParallelScanDescData
     588             :  */
     589             : Size
     590          64 : btestimateparallelscan(Relation rel, int nkeys, int norderbys)
     591             : {
     592          64 :     int16       nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
     593             :     Size        estnbtreeshared,
     594             :                 genericattrspace;
     595             : 
     596             :     /*
     597             :      * Pessimistically assume that every input scan key will be output with
     598             :      * its own SAOP array
     599             :      */
     600          64 :     estnbtreeshared = offsetof(BTParallelScanDescData, btps_arrElems) +
     601             :         sizeof(int) * nkeys;
     602             : 
     603             :     /* Single column indexes cannot possibly use a skip array */
     604          64 :     if (nkeyatts == 1)
     605          46 :         return estnbtreeshared;
     606             : 
     607             :     /*
     608             :      * Pessimistically assume that all attributes prior to the least
     609             :      * significant attribute require a skip array (and an associated key)
     610             :      */
     611          18 :     genericattrspace = datumEstimateSpace((Datum) 0, false, true,
     612             :                                           sizeof(Datum));
     613          36 :     for (int attnum = 1; attnum < nkeyatts; attnum++)
     614             :     {
     615             :         CompactAttribute *attr;
     616             : 
     617             :         /*
     618             :          * We make the conservative assumption that every index column will
     619             :          * also require a skip array.
     620             :          *
     621             :          * Every skip array must have space to store its scan key's sk_flags.
     622             :          */
     623          18 :         estnbtreeshared = add_size(estnbtreeshared, sizeof(int));
     624             : 
     625             :         /* Consider space required to store a datum of opclass input type */
     626          18 :         attr = TupleDescCompactAttr(rel->rd_att, attnum - 1);
     627          18 :         if (attr->attbyval)
     628          18 :         {
     629             :             /* This index attribute stores pass-by-value datums */
     630          18 :             Size        estfixed = datumEstimateSpace((Datum) 0, false,
     631          18 :                                                       true, attr->attlen);
     632             : 
     633          18 :             estnbtreeshared = add_size(estnbtreeshared, estfixed);
     634          18 :             continue;
     635             :         }
     636             : 
     637             :         /*
     638             :          * This index attribute stores pass-by-reference datums.
     639             :          *
     640             :          * Assume that serializing this array will use just as much space as a
     641             :          * pass-by-value datum, in addition to space for the largest possible
     642             :          * whole index tuple (this is not just a per-datum portion of the
     643             :          * largest possible tuple because that'd be almost as large anyway).
     644             :          *
     645             :          * This is quite conservative, but it's not clear how we could do much
     646             :          * better.  The executor requires an up-front storage request size
     647             :          * that reliably covers the scan's high watermark memory usage.  We
     648             :          * can't be sure of the real high watermark until the scan is over.
     649             :          */
     650           0 :         estnbtreeshared = add_size(estnbtreeshared, genericattrspace);
     651           0 :         estnbtreeshared = add_size(estnbtreeshared, BTMaxItemSize);
     652             :     }
     653             : 
     654          18 :     return estnbtreeshared;
     655             : }
     656             : 
     657             : /*
     658             :  * _bt_parallel_serialize_arrays() -- Serialize parallel array state.
     659             :  *
     660             :  * Caller must have exclusively locked btscan->btps_lock when called.
     661             :  */
     662             : static void
     663          36 : _bt_parallel_serialize_arrays(Relation rel, BTParallelScanDesc btscan,
     664             :                               BTScanOpaque so)
     665             : {
     666             :     char       *datumshared;
     667             : 
     668             :     /* Space for serialized datums begins immediately after btps_arrElems[] */
     669          36 :     datumshared = ((char *) &btscan->btps_arrElems[so->numArrayKeys]);
     670          72 :     for (int i = 0; i < so->numArrayKeys; i++)
     671             :     {
     672          36 :         BTArrayKeyInfo *array = &so->arrayKeys[i];
     673          36 :         ScanKey     skey = &so->keyData[array->scan_key];
     674             : 
     675          36 :         if (array->num_elems != -1)
     676             :         {
     677             :             /* Save SAOP array's cur_elem (no need to copy key/datum) */
     678             :             Assert(!(skey->sk_flags & SK_BT_SKIP));
     679          36 :             btscan->btps_arrElems[i] = array->cur_elem;
     680          36 :             continue;
     681             :         }
     682             : 
     683             :         /* Save all mutable state associated with skip array's key */
     684             :         Assert(skey->sk_flags & SK_BT_SKIP);
     685           0 :         memcpy(datumshared, &skey->sk_flags, sizeof(int));
     686           0 :         datumshared += sizeof(int);
     687             : 
     688           0 :         if (skey->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL))
     689             :         {
     690             :             /* No sk_argument datum to serialize */
     691             :             Assert(skey->sk_argument == 0);
     692           0 :             continue;
     693             :         }
     694             : 
     695           0 :         datumSerialize(skey->sk_argument, (skey->sk_flags & SK_ISNULL) != 0,
     696           0 :                        array->attbyval, array->attlen, &datumshared);
     697             :     }
     698          36 : }
     699             : 
     700             : /*
     701             :  * _bt_parallel_restore_arrays() -- Restore serialized parallel array state.
     702             :  *
     703             :  * Caller must have exclusively locked btscan->btps_lock when called.
     704             :  */
     705             : static void
     706          36 : _bt_parallel_restore_arrays(Relation rel, BTParallelScanDesc btscan,
     707             :                             BTScanOpaque so)
     708             : {
     709             :     char       *datumshared;
     710             : 
     711             :     /* Space for serialized datums begins immediately after btps_arrElems[] */
     712          36 :     datumshared = ((char *) &btscan->btps_arrElems[so->numArrayKeys]);
     713          72 :     for (int i = 0; i < so->numArrayKeys; i++)
     714             :     {
     715          36 :         BTArrayKeyInfo *array = &so->arrayKeys[i];
     716          36 :         ScanKey     skey = &so->keyData[array->scan_key];
     717             :         bool        isnull;
     718             : 
     719          36 :         if (array->num_elems != -1)
     720             :         {
     721             :             /* Restore SAOP array using its saved cur_elem */
     722             :             Assert(!(skey->sk_flags & SK_BT_SKIP));
     723          36 :             array->cur_elem = btscan->btps_arrElems[i];
     724          36 :             skey->sk_argument = array->elem_values[array->cur_elem];
     725          36 :             continue;
     726             :         }
     727             : 
     728             :         /* Restore skip array by restoring its key directly */
     729           0 :         if (!array->attbyval && skey->sk_argument)
     730           0 :             pfree(DatumGetPointer(skey->sk_argument));
     731           0 :         skey->sk_argument = (Datum) 0;
     732           0 :         memcpy(&skey->sk_flags, datumshared, sizeof(int));
     733           0 :         datumshared += sizeof(int);
     734             : 
     735             :         Assert(skey->sk_flags & SK_BT_SKIP);
     736             : 
     737           0 :         if (skey->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL))
     738             :         {
     739             :             /* No sk_argument datum to restore */
     740           0 :             continue;
     741             :         }
     742             : 
     743           0 :         skey->sk_argument = datumRestore(&datumshared, &isnull);
     744           0 :         if (isnull)
     745             :         {
     746             :             Assert(skey->sk_argument == 0);
     747             :             Assert(skey->sk_flags & SK_SEARCHNULL);
     748             :             Assert(skey->sk_flags & SK_ISNULL);
     749             :         }
     750             :     }
     751          36 : }
     752             : 
     753             : /*
     754             :  * btinitparallelscan -- initialize BTParallelScanDesc for parallel btree scan
     755             :  */
     756             : void
     757          64 : btinitparallelscan(void *target)
     758             : {
     759          64 :     BTParallelScanDesc bt_target = (BTParallelScanDesc) target;
     760             : 
     761          64 :     LWLockInitialize(&bt_target->btps_lock,
     762             :                      LWTRANCHE_PARALLEL_BTREE_SCAN);
     763          64 :     bt_target->btps_nextScanPage = InvalidBlockNumber;
     764          64 :     bt_target->btps_lastCurrPage = InvalidBlockNumber;
     765          64 :     bt_target->btps_pageStatus = BTPARALLEL_NOT_INITIALIZED;
     766          64 :     ConditionVariableInit(&bt_target->btps_cv);
     767          64 : }
     768             : 
     769             : /*
     770             :  *  btparallelrescan() -- reset parallel scan
     771             :  */
     772             : void
     773          24 : btparallelrescan(IndexScanDesc scan)
     774             : {
     775             :     BTParallelScanDesc btscan;
     776          24 :     ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
     777             : 
     778             :     Assert(parallel_scan);
     779             : 
     780          24 :     btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
     781             :                                                   parallel_scan->ps_offset_am);
     782             : 
     783             :     /*
     784             :      * In theory, we don't need to acquire the LWLock here, because there
     785             :      * shouldn't be any other workers running at this point, but we do so for
     786             :      * consistency.
     787             :      */
     788          24 :     LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
     789          24 :     btscan->btps_nextScanPage = InvalidBlockNumber;
     790          24 :     btscan->btps_lastCurrPage = InvalidBlockNumber;
     791          24 :     btscan->btps_pageStatus = BTPARALLEL_NOT_INITIALIZED;
     792          24 :     LWLockRelease(&btscan->btps_lock);
     793          24 : }
     794             : 
     795             : /*
     796             :  * _bt_parallel_seize() -- Begin the process of advancing the scan to a new
     797             :  *      page.  Other scans must wait until we call _bt_parallel_release()
     798             :  *      or _bt_parallel_done().
     799             :  *
     800             :  * The return value is true if we successfully seized the scan and false
     801             :  * if we did not.  The latter case occurs when no pages remain, or when
     802             :  * another primitive index scan is scheduled that caller's backend cannot
     803             :  * start just yet (only backends that call from _bt_first are capable of
     804             :  * starting primitive index scans, which they indicate by passing first=true).
     805             :  *
     806             :  * If the return value is true, *next_scan_page returns the next page of the
     807             :  * scan, and *last_curr_page returns the page that *next_scan_page came from.
     808             :  * An invalid *next_scan_page means the scan hasn't yet started, or that
     809             :  * caller needs to start the next primitive index scan (if it's the latter
     810             :  * case we'll set so.needPrimScan).
     811             :  *
     812             :  * Callers should ignore the value of *next_scan_page and *last_curr_page if
     813             :  * the return value is false.
     814             :  */
     815             : bool
     816        1658 : _bt_parallel_seize(IndexScanDesc scan, BlockNumber *next_scan_page,
     817             :                    BlockNumber *last_curr_page, bool first)
     818             : {
     819        1658 :     Relation    rel = scan->indexRelation;
     820        1658 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     821        1658 :     bool        exit_loop = false,
     822        1658 :                 status = true,
     823        1658 :                 endscan = false;
     824        1658 :     ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
     825             :     BTParallelScanDesc btscan;
     826             : 
     827        1658 :     *next_scan_page = InvalidBlockNumber;
     828        1658 :     *last_curr_page = InvalidBlockNumber;
     829             : 
     830             :     /*
     831             :      * Reset so->currPos, and initialize moreLeft/moreRight such that the next
     832             :      * call to _bt_readnextpage treats this backend similarly to a serial
     833             :      * backend that steps from *last_curr_page to *next_scan_page (unless this
     834             :      * backend's so->currPos is initialized by _bt_readfirstpage before then).
     835             :      */
     836        1658 :     BTScanPosInvalidate(so->currPos);
     837        1658 :     so->currPos.moreLeft = so->currPos.moreRight = true;
     838             : 
     839        1658 :     if (first)
     840             :     {
     841             :         /*
     842             :          * Initialize array related state when called from _bt_first, assuming
     843             :          * that this will be the first primitive index scan for the scan
     844             :          */
     845         446 :         so->needPrimScan = false;
     846         446 :         so->scanBehind = false;
     847         446 :         so->oppositeDirCheck = false;
     848             :     }
     849             :     else
     850             :     {
     851             :         /*
     852             :          * Don't attempt to seize the scan when it requires another primitive
     853             :          * index scan, since caller's backend cannot start it right now
     854             :          */
     855        1212 :         if (so->needPrimScan)
     856           0 :             return false;
     857             :     }
     858             : 
     859        1658 :     btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
     860             :                                                   parallel_scan->ps_offset_am);
     861             : 
     862             :     while (1)
     863             :     {
     864        1686 :         LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
     865             : 
     866        1686 :         if (btscan->btps_pageStatus == BTPARALLEL_DONE)
     867             :         {
     868             :             /* We're done with this parallel index scan */
     869         306 :             status = false;
     870             :         }
     871        1380 :         else if (btscan->btps_pageStatus == BTPARALLEL_IDLE &&
     872        1228 :                  btscan->btps_nextScanPage == P_NONE)
     873             :         {
     874             :             /* End this parallel index scan */
     875          16 :             status = false;
     876          16 :             endscan = true;
     877             :         }
     878        1364 :         else if (btscan->btps_pageStatus == BTPARALLEL_NEED_PRIMSCAN)
     879             :         {
     880             :             Assert(so->numArrayKeys);
     881             : 
     882          36 :             if (first)
     883             :             {
     884             :                 /* Can start scheduled primitive scan right away, so do so */
     885          36 :                 btscan->btps_pageStatus = BTPARALLEL_ADVANCING;
     886             : 
     887             :                 /* Restore scan's array keys from serialized values */
     888          36 :                 _bt_parallel_restore_arrays(rel, btscan, so);
     889          36 :                 exit_loop = true;
     890             :             }
     891             :             else
     892             :             {
     893             :                 /*
     894             :                  * Don't attempt to seize the scan when it requires another
     895             :                  * primitive index scan, since caller's backend cannot start
     896             :                  * it right now
     897             :                  */
     898           0 :                 status = false;
     899             :             }
     900             : 
     901             :             /*
     902             :              * Either way, update backend local state to indicate that a
     903             :              * pending primitive scan is required
     904             :              */
     905          36 :             so->needPrimScan = true;
     906          36 :             so->scanBehind = false;
     907          36 :             so->oppositeDirCheck = false;
     908             :         }
     909        1328 :         else if (btscan->btps_pageStatus != BTPARALLEL_ADVANCING)
     910             :         {
     911             :             /*
     912             :              * We have successfully seized control of the scan for the purpose
     913             :              * of advancing it to a new page!
     914             :              */
     915        1300 :             btscan->btps_pageStatus = BTPARALLEL_ADVANCING;
     916             :             Assert(btscan->btps_nextScanPage != P_NONE);
     917        1300 :             *next_scan_page = btscan->btps_nextScanPage;
     918        1300 :             *last_curr_page = btscan->btps_lastCurrPage;
     919        1300 :             exit_loop = true;
     920             :         }
     921        1686 :         LWLockRelease(&btscan->btps_lock);
     922        1686 :         if (exit_loop || !status)
     923             :             break;
     924          28 :         ConditionVariableSleep(&btscan->btps_cv, WAIT_EVENT_BTREE_PAGE);
     925             :     }
     926        1658 :     ConditionVariableCancelSleep();
     927             : 
     928             :     /* When the scan has reached the rightmost (or leftmost) page, end it */
     929        1658 :     if (endscan)
     930          16 :         _bt_parallel_done(scan);
     931             : 
     932        1658 :     return status;
     933             : }
     934             : 
     935             : /*
     936             :  * _bt_parallel_release() -- Complete the process of advancing the scan to a
     937             :  *      new page.  We now have the new value btps_nextScanPage; another backend
     938             :  *      can now begin advancing the scan.
     939             :  *
     940             :  * Callers whose scan uses array keys must save their curr_page argument so
     941             :  * that it can be passed to _bt_parallel_primscan_schedule, should caller
     942             :  * determine that another primitive index scan is required.
     943             :  *
     944             :  * If caller's next_scan_page is P_NONE, the scan has reached the index's
     945             :  * rightmost/leftmost page.  This is treated as reaching the end of the scan
     946             :  * within _bt_parallel_seize.
     947             :  *
     948             :  * Note: unlike the serial case, parallel scans don't need to remember both
     949             :  * sibling links.  next_scan_page is whichever link is next given the scan's
     950             :  * direction.  That's all we'll ever need, since the direction of a parallel
     951             :  * scan can never change.
     952             :  */
     953             : void
     954        1336 : _bt_parallel_release(IndexScanDesc scan, BlockNumber next_scan_page,
     955             :                      BlockNumber curr_page)
     956             : {
     957        1336 :     ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
     958             :     BTParallelScanDesc btscan;
     959             : 
     960             :     Assert(BlockNumberIsValid(next_scan_page));
     961             : 
     962        1336 :     btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
     963             :                                                   parallel_scan->ps_offset_am);
     964             : 
     965        1336 :     LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
     966        1336 :     btscan->btps_nextScanPage = next_scan_page;
     967        1336 :     btscan->btps_lastCurrPage = curr_page;
     968        1336 :     btscan->btps_pageStatus = BTPARALLEL_IDLE;
     969        1336 :     LWLockRelease(&btscan->btps_lock);
     970        1336 :     ConditionVariableSignal(&btscan->btps_cv);
     971        1336 : }
     972             : 
     973             : /*
     974             :  * _bt_parallel_done() -- Mark the parallel scan as complete.
     975             :  *
     976             :  * When there are no pages left to scan, this function should be called to
     977             :  * notify other workers.  Otherwise, they might wait forever for the scan to
     978             :  * advance to the next page.
     979             :  */
     980             : void
     981     7067404 : _bt_parallel_done(IndexScanDesc scan)
     982             : {
     983     7067404 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     984     7067404 :     ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
     985             :     BTParallelScanDesc btscan;
     986     7067404 :     bool        status_changed = false;
     987             : 
     988             :     Assert(!BTScanPosIsValid(so->currPos));
     989             : 
     990             :     /* Do nothing, for non-parallel scans */
     991     7067404 :     if (parallel_scan == NULL)
     992     7067240 :         return;
     993             : 
     994             :     /*
     995             :      * Should not mark parallel scan done when there's still a pending
     996             :      * primitive index scan
     997             :      */
     998         164 :     if (so->needPrimScan)
     999          36 :         return;
    1000             : 
    1001         128 :     btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
    1002             :                                                   parallel_scan->ps_offset_am);
    1003             : 
    1004             :     /*
    1005             :      * Mark the parallel scan as done, unless some other process did so
    1006             :      * already
    1007             :      */
    1008         128 :     LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
    1009             :     Assert(btscan->btps_pageStatus != BTPARALLEL_NEED_PRIMSCAN);
    1010         128 :     if (btscan->btps_pageStatus != BTPARALLEL_DONE)
    1011             :     {
    1012          88 :         btscan->btps_pageStatus = BTPARALLEL_DONE;
    1013          88 :         status_changed = true;
    1014             :     }
    1015         128 :     LWLockRelease(&btscan->btps_lock);
    1016             : 
    1017             :     /* wake up all the workers associated with this parallel scan */
    1018         128 :     if (status_changed)
    1019          88 :         ConditionVariableBroadcast(&btscan->btps_cv);
    1020             : }
    1021             : 
    1022             : /*
    1023             :  * _bt_parallel_primscan_schedule() -- Schedule another primitive index scan.
    1024             :  *
    1025             :  * Caller passes the curr_page most recently passed to _bt_parallel_release
    1026             :  * by its backend.  Caller successfully schedules the next primitive index scan
    1027             :  * if the shared parallel state hasn't been seized since caller's backend last
    1028             :  * advanced the scan.
    1029             :  */
    1030             : void
    1031          36 : _bt_parallel_primscan_schedule(IndexScanDesc scan, BlockNumber curr_page)
    1032             : {
    1033          36 :     Relation    rel = scan->indexRelation;
    1034          36 :     BTScanOpaque so = (BTScanOpaque) scan->opaque;
    1035          36 :     ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
    1036             :     BTParallelScanDesc btscan;
    1037             : 
    1038             :     Assert(so->numArrayKeys);
    1039             : 
    1040          36 :     btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
    1041             :                                                   parallel_scan->ps_offset_am);
    1042             : 
    1043          36 :     LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
    1044          36 :     if (btscan->btps_lastCurrPage == curr_page &&
    1045          36 :         btscan->btps_pageStatus == BTPARALLEL_IDLE)
    1046             :     {
    1047          36 :         btscan->btps_nextScanPage = InvalidBlockNumber;
    1048          36 :         btscan->btps_lastCurrPage = InvalidBlockNumber;
    1049          36 :         btscan->btps_pageStatus = BTPARALLEL_NEED_PRIMSCAN;
    1050             : 
    1051             :         /* Serialize scan's current array keys */
    1052          36 :         _bt_parallel_serialize_arrays(rel, btscan, so);
    1053             :     }
    1054          36 :     LWLockRelease(&btscan->btps_lock);
    1055          36 : }
    1056             : 
    1057             : /*
    1058             :  * Bulk deletion of all index entries pointing to a set of heap tuples.
    1059             :  * The set of target tuples is specified via a callback routine that tells
    1060             :  * whether any given heap tuple (identified by ItemPointer) is being deleted.
    1061             :  *
    1062             :  * Result: a palloc'd struct containing statistical info for VACUUM displays.
    1063             :  */
    1064             : IndexBulkDeleteResult *
    1065        2850 : btbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
    1066             :              IndexBulkDeleteCallback callback, void *callback_state)
    1067             : {
    1068        2850 :     Relation    rel = info->index;
    1069             :     BTCycleId   cycleid;
    1070             : 
    1071             :     /* allocate stats if first time through, else re-use existing struct */
    1072        2850 :     if (stats == NULL)
    1073        2846 :         stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
    1074             : 
    1075             :     /* Establish the vacuum cycle ID to use for this scan */
    1076             :     /* The ENSURE stuff ensures we clean up shared memory on failure */
    1077        2850 :     PG_ENSURE_ERROR_CLEANUP(_bt_end_vacuum_callback, PointerGetDatum(rel));
    1078             :     {
    1079        2850 :         cycleid = _bt_start_vacuum(rel);
    1080             : 
    1081        2850 :         btvacuumscan(info, stats, callback, callback_state, cycleid);
    1082             :     }
    1083        2850 :     PG_END_ENSURE_ERROR_CLEANUP(_bt_end_vacuum_callback, PointerGetDatum(rel));
    1084        2850 :     _bt_end_vacuum(rel);
    1085             : 
    1086        2850 :     return stats;
    1087             : }
    1088             : 
    1089             : /*
    1090             :  * Post-VACUUM cleanup.
    1091             :  *
    1092             :  * Result: a palloc'd struct containing statistical info for VACUUM displays.
    1093             :  */
    1094             : IndexBulkDeleteResult *
    1095      227742 : btvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
    1096             : {
    1097             :     BlockNumber num_delpages;
    1098             : 
    1099             :     /* No-op in ANALYZE ONLY mode */
    1100      227742 :     if (info->analyze_only)
    1101       17622 :         return stats;
    1102             : 
    1103             :     /*
    1104             :      * If btbulkdelete was called, we need not do anything (we just maintain
    1105             :      * the information used within _bt_vacuum_needs_cleanup() by calling
    1106             :      * _bt_set_cleanup_info() below).
    1107             :      *
    1108             :      * If btbulkdelete was _not_ called, then we have a choice to make: we
    1109             :      * must decide whether or not a btvacuumscan() call is needed now (i.e.
    1110             :      * whether the ongoing VACUUM operation can entirely avoid a physical scan
    1111             :      * of the index).  A call to _bt_vacuum_needs_cleanup() decides it for us
    1112             :      * now.
    1113             :      */
    1114      210120 :     if (stats == NULL)
    1115             :     {
    1116             :         /* Check if VACUUM operation can entirely avoid btvacuumscan() call */
    1117      207870 :         if (!_bt_vacuum_needs_cleanup(info->index))
    1118      207860 :             return NULL;
    1119             : 
    1120             :         /*
    1121             :          * Since we aren't going to actually delete any leaf items, there's no
    1122             :          * need to go through all the vacuum-cycle-ID pushups here.
    1123             :          *
    1124             :          * Posting list tuples are a source of inaccuracy for cleanup-only
    1125             :          * scans.  btvacuumscan() will assume that the number of index tuples
    1126             :          * from each page can be used as num_index_tuples, even though
    1127             :          * num_index_tuples is supposed to represent the number of TIDs in the
    1128             :          * index.  This naive approach can underestimate the number of tuples
    1129             :          * in the index significantly.
    1130             :          *
    1131             :          * We handle the problem by making num_index_tuples an estimate in
    1132             :          * cleanup-only case.
    1133             :          */
    1134          10 :         stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
    1135          10 :         btvacuumscan(info, stats, NULL, NULL, 0);
    1136          10 :         stats->estimated_count = true;
    1137             :     }
    1138             : 
    1139             :     /*
    1140             :      * Maintain num_delpages value in metapage for _bt_vacuum_needs_cleanup().
    1141             :      *
    1142             :      * num_delpages is the number of deleted pages now in the index that were
    1143             :      * not safe to place in the FSM to be recycled just yet.  num_delpages is
    1144             :      * greater than 0 only when _bt_pagedel() actually deleted pages during
    1145             :      * our call to btvacuumscan().  Even then, _bt_pendingfsm_finalize() must
    1146             :      * have failed to place any newly deleted pages in the FSM just moments
    1147             :      * ago.  (Actually, there are edge cases where recycling of the current
    1148             :      * VACUUM's newly deleted pages does not even become safe by the time the
    1149             :      * next VACUUM comes around.  See nbtree/README.)
    1150             :      */
    1151             :     Assert(stats->pages_deleted >= stats->pages_free);
    1152        2260 :     num_delpages = stats->pages_deleted - stats->pages_free;
    1153        2260 :     _bt_set_cleanup_info(info->index, num_delpages);
    1154             : 
    1155             :     /*
    1156             :      * It's quite possible for us to be fooled by concurrent page splits into
    1157             :      * double-counting some index tuples, so disbelieve any total that exceeds
    1158             :      * the underlying heap's count ... if we know that accurately.  Otherwise
    1159             :      * this might just make matters worse.
    1160             :      */
    1161        2260 :     if (!info->estimated_count)
    1162             :     {
    1163        2192 :         if (stats->num_index_tuples > info->num_heap_tuples)
    1164          38 :             stats->num_index_tuples = info->num_heap_tuples;
    1165             :     }
    1166             : 
    1167        2260 :     return stats;
    1168             : }
    1169             : 
    1170             : /*
    1171             :  * btvacuumscan --- scan the index for VACUUMing purposes
    1172             :  *
    1173             :  * This combines the functions of looking for leaf tuples that are deletable
    1174             :  * according to the vacuum callback, looking for empty pages that can be
    1175             :  * deleted, and looking for old deleted pages that can be recycled.  Both
    1176             :  * btbulkdelete and btvacuumcleanup invoke this (the latter only if no
    1177             :  * btbulkdelete call occurred and _bt_vacuum_needs_cleanup returned true).
    1178             :  *
    1179             :  * The caller is responsible for initially allocating/zeroing a stats struct
    1180             :  * and for obtaining a vacuum cycle ID if necessary.
    1181             :  */
    1182             : static void
    1183        2860 : btvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
    1184             :              IndexBulkDeleteCallback callback, void *callback_state,
    1185             :              BTCycleId cycleid)
    1186             : {
    1187        2860 :     Relation    rel = info->index;
    1188             :     BTVacState  vstate;
    1189             :     BlockNumber num_pages;
    1190             :     bool        needLock;
    1191             :     BlockRangeReadStreamPrivate p;
    1192        2860 :     ReadStream *stream = NULL;
    1193             : 
    1194             :     /*
    1195             :      * Reset fields that track information about the entire index now.  This
    1196             :      * avoids double-counting in the case where a single VACUUM command
    1197             :      * requires multiple scans of the index.
    1198             :      *
    1199             :      * Avoid resetting the tuples_removed and pages_newly_deleted fields here,
    1200             :      * since they track information about the VACUUM command, and so must last
    1201             :      * across each call to btvacuumscan().
    1202             :      *
    1203             :      * (Note that pages_free is treated as state about the whole index, not
    1204             :      * the current VACUUM.  This is appropriate because RecordFreeIndexPage()
    1205             :      * calls are idempotent, and get repeated for the same deleted pages in
    1206             :      * some scenarios.  The point for us is to track the number of recyclable
    1207             :      * pages in the index at the end of the VACUUM command.)
    1208             :      */
    1209        2860 :     stats->num_pages = 0;
    1210        2860 :     stats->num_index_tuples = 0;
    1211        2860 :     stats->pages_deleted = 0;
    1212        2860 :     stats->pages_free = 0;
    1213             : 
    1214             :     /* Set up info to pass down to btvacuumpage */
    1215        2860 :     vstate.info = info;
    1216        2860 :     vstate.stats = stats;
    1217        2860 :     vstate.callback = callback;
    1218        2860 :     vstate.callback_state = callback_state;
    1219        2860 :     vstate.cycleid = cycleid;
    1220             : 
    1221             :     /* Create a temporary memory context to run _bt_pagedel in */
    1222        2860 :     vstate.pagedelcontext = AllocSetContextCreate(CurrentMemoryContext,
    1223             :                                                   "_bt_pagedel",
    1224             :                                                   ALLOCSET_DEFAULT_SIZES);
    1225             : 
    1226             :     /* Initialize vstate fields used by _bt_pendingfsm_finalize */
    1227        2860 :     vstate.bufsize = 0;
    1228        2860 :     vstate.maxbufsize = 0;
    1229        2860 :     vstate.pendingpages = NULL;
    1230        2860 :     vstate.npendingpages = 0;
    1231             :     /* Consider applying _bt_pendingfsm_finalize optimization */
    1232        2860 :     _bt_pendingfsm_init(rel, &vstate, (callback == NULL));
    1233             : 
    1234             :     /*
    1235             :      * The outer loop iterates over all index pages except the metapage, in
    1236             :      * physical order (we hope the kernel will cooperate in providing
    1237             :      * read-ahead for speed).  It is critical that we visit all leaf pages,
    1238             :      * including ones added after we start the scan, else we might fail to
    1239             :      * delete some deletable tuples.  Hence, we must repeatedly check the
    1240             :      * relation length.  We must acquire the relation-extension lock while
    1241             :      * doing so to avoid a race condition: if someone else is extending the
    1242             :      * relation, there is a window where bufmgr/smgr have created a new
    1243             :      * all-zero page but it hasn't yet been write-locked by _bt_getbuf(). If
    1244             :      * we manage to scan such a page here, we'll improperly assume it can be
    1245             :      * recycled.  Taking the lock synchronizes things enough to prevent a
    1246             :      * problem: either num_pages won't include the new page, or _bt_getbuf
    1247             :      * already has write lock on the buffer and it will be fully initialized
    1248             :      * before we can examine it.  Also, we need not worry if a page is added
    1249             :      * immediately after we look; the page splitting code already has
    1250             :      * write-lock on the left page before it adds a right page, so we must
    1251             :      * already have processed any tuples due to be moved into such a page.
    1252             :      *
    1253             :      * XXX: Now that new pages are locked with RBM_ZERO_AND_LOCK, I don't
    1254             :      * think the use of the extension lock is still required.
    1255             :      *
    1256             :      * We can skip locking for new or temp relations, however, since no one
    1257             :      * else could be accessing them.
    1258             :      */
    1259        2860 :     needLock = !RELATION_IS_LOCAL(rel);
    1260             : 
    1261        2860 :     p.current_blocknum = BTREE_METAPAGE + 1;
    1262             : 
    1263             :     /*
    1264             :      * It is safe to use batchmode as block_range_read_stream_cb takes no
    1265             :      * locks.
    1266             :      */
    1267        2860 :     stream = read_stream_begin_relation(READ_STREAM_MAINTENANCE |
    1268             :                                         READ_STREAM_FULL |
    1269             :                                         READ_STREAM_USE_BATCHING,
    1270             :                                         info->strategy,
    1271             :                                         rel,
    1272             :                                         MAIN_FORKNUM,
    1273             :                                         block_range_read_stream_cb,
    1274             :                                         &p,
    1275             :                                         0);
    1276             :     for (;;)
    1277             :     {
    1278             :         /* Get the current relation length */
    1279        5446 :         if (needLock)
    1280        5442 :             LockRelationForExtension(rel, ExclusiveLock);
    1281        5446 :         num_pages = RelationGetNumberOfBlocks(rel);
    1282        5446 :         if (needLock)
    1283        5442 :             UnlockRelationForExtension(rel, ExclusiveLock);
    1284             : 
    1285        5446 :         if (info->report_progress)
    1286         918 :             pgstat_progress_update_param(PROGRESS_SCAN_BLOCKS_TOTAL,
    1287             :                                          num_pages);
    1288             : 
    1289             :         /* Quit if we've scanned the whole relation */
    1290        5446 :         if (p.current_blocknum >= num_pages)
    1291        2860 :             break;
    1292             : 
    1293        2586 :         p.last_exclusive = num_pages;
    1294             : 
    1295             :         /* Iterate over pages, then loop back to recheck relation length */
    1296             :         while (true)
    1297       24810 :         {
    1298             :             BlockNumber current_block;
    1299             :             Buffer      buf;
    1300             : 
    1301             :             /* call vacuum_delay_point while not holding any buffer lock */
    1302       27396 :             vacuum_delay_point(false);
    1303             : 
    1304       27396 :             buf = read_stream_next_buffer(stream, NULL);
    1305             : 
    1306       27396 :             if (!BufferIsValid(buf))
    1307        2586 :                 break;
    1308             : 
    1309       24810 :             current_block = btvacuumpage(&vstate, buf);
    1310             : 
    1311       24810 :             if (info->report_progress)
    1312         964 :                 pgstat_progress_update_param(PROGRESS_SCAN_BLOCKS_DONE,
    1313             :                                              current_block);
    1314             :         }
    1315             : 
    1316             :         /*
    1317             :          * We have to reset the read stream to use it again. After returning
    1318             :          * InvalidBuffer, the read stream API won't invoke our callback again
    1319             :          * until the stream has been reset.
    1320             :          */
    1321        2586 :         read_stream_reset(stream);
    1322             :     }
    1323             : 
    1324        2860 :     read_stream_end(stream);
    1325             : 
    1326             :     /* Set statistics num_pages field to final size of index */
    1327        2860 :     stats->num_pages = num_pages;
    1328             : 
    1329        2860 :     MemoryContextDelete(vstate.pagedelcontext);
    1330             : 
    1331             :     /*
    1332             :      * If there were any calls to _bt_pagedel() during scan of the index then
    1333             :      * see if any of the resulting pages can be placed in the FSM now.  When
    1334             :      * it's not safe we'll have to leave it up to a future VACUUM operation.
    1335             :      *
    1336             :      * Finally, if we placed any pages in the FSM (either just now or during
    1337             :      * the scan), forcibly update the upper-level FSM pages to ensure that
    1338             :      * searchers can find them.
    1339             :      */
    1340        2860 :     _bt_pendingfsm_finalize(rel, &vstate);
    1341        2860 :     if (stats->pages_free > 0)
    1342          48 :         IndexFreeSpaceMapVacuum(rel);
    1343        2860 : }
    1344             : 
    1345             : /*
    1346             :  * btvacuumpage --- VACUUM one page
    1347             :  *
    1348             :  * This processes a single page for btvacuumscan().  In some cases we must
    1349             :  * backtrack to re-examine and VACUUM pages that were on buf's page during
    1350             :  * a previous call here.  This is how we handle page splits (that happened
    1351             :  * after our cycleid was acquired) whose right half page happened to reuse
    1352             :  * a block that we might have processed at some point before it was
    1353             :  * recycled (i.e. before the page split).
    1354             :  *
    1355             :  * Returns BlockNumber of a scanned page (not backtracked).
    1356             :  */
    1357             : static BlockNumber
    1358       24810 : btvacuumpage(BTVacState *vstate, Buffer buf)
    1359             : {
    1360       24810 :     IndexVacuumInfo *info = vstate->info;
    1361       24810 :     IndexBulkDeleteResult *stats = vstate->stats;
    1362       24810 :     IndexBulkDeleteCallback callback = vstate->callback;
    1363       24810 :     void       *callback_state = vstate->callback_state;
    1364       24810 :     Relation    rel = info->index;
    1365       24810 :     Relation    heaprel = info->heaprel;
    1366             :     bool        attempt_pagedel;
    1367             :     BlockNumber blkno,
    1368             :                 backtrack_to;
    1369       24810 :     BlockNumber scanblkno = BufferGetBlockNumber(buf);
    1370             :     Page        page;
    1371             :     BTPageOpaque opaque;
    1372             : 
    1373       24810 :     blkno = scanblkno;
    1374             : 
    1375       24810 : backtrack:
    1376             : 
    1377       24810 :     attempt_pagedel = false;
    1378       24810 :     backtrack_to = P_NONE;
    1379             : 
    1380       24810 :     _bt_lockbuf(rel, buf, BT_READ);
    1381       24810 :     page = BufferGetPage(buf);
    1382       24810 :     opaque = NULL;
    1383       24810 :     if (!PageIsNew(page))
    1384             :     {
    1385       24810 :         _bt_checkpage(rel, buf);
    1386       24810 :         opaque = BTPageGetOpaque(page);
    1387             :     }
    1388             : 
    1389             :     Assert(blkno <= scanblkno);
    1390       24810 :     if (blkno != scanblkno)
    1391             :     {
    1392             :         /*
    1393             :          * We're backtracking.
    1394             :          *
    1395             :          * We followed a right link to a sibling leaf page (a page that
    1396             :          * happens to be from a block located before scanblkno).  The only
    1397             :          * case we want to do anything with is a live leaf page having the
    1398             :          * current vacuum cycle ID.
    1399             :          *
    1400             :          * The page had better be in a state that's consistent with what we
    1401             :          * expect.  Check for conditions that imply corruption in passing.  It
    1402             :          * can't be half-dead because only an interrupted VACUUM process can
    1403             :          * leave pages in that state, so we'd definitely have dealt with it
    1404             :          * back when the page was the scanblkno page (half-dead pages are
    1405             :          * always marked fully deleted by _bt_pagedel(), barring corruption).
    1406             :          */
    1407           0 :         if (!opaque || !P_ISLEAF(opaque) || P_ISHALFDEAD(opaque))
    1408             :         {
    1409             :             Assert(false);
    1410           0 :             ereport(LOG,
    1411             :                     (errcode(ERRCODE_INDEX_CORRUPTED),
    1412             :                      errmsg_internal("right sibling %u of scanblkno %u unexpectedly in an inconsistent state in index \"%s\"",
    1413             :                                      blkno, scanblkno, RelationGetRelationName(rel))));
    1414           0 :             _bt_relbuf(rel, buf);
    1415           0 :             return scanblkno;
    1416             :         }
    1417             : 
    1418             :         /*
    1419             :          * We may have already processed the page in an earlier call, when the
    1420             :          * page was scanblkno.  This happens when the leaf page split occurred
    1421             :          * after the scan began, but before the right sibling page became the
    1422             :          * scanblkno.
    1423             :          *
    1424             :          * Page may also have been deleted by current btvacuumpage() call,
    1425             :          * since _bt_pagedel() sometimes deletes the right sibling page of
    1426             :          * scanblkno in passing (it does so after we decided where to
    1427             :          * backtrack to).  We don't need to process this page as a deleted
    1428             :          * page a second time now (in fact, it would be wrong to count it as a
    1429             :          * deleted page in the bulk delete statistics a second time).
    1430             :          */
    1431           0 :         if (opaque->btpo_cycleid != vstate->cycleid || P_ISDELETED(opaque))
    1432             :         {
    1433             :             /* Done with current scanblkno (and all lower split pages) */
    1434           0 :             _bt_relbuf(rel, buf);
    1435           0 :             return scanblkno;
    1436             :         }
    1437             :     }
    1438             : 
    1439       24810 :     if (!opaque || BTPageIsRecyclable(page, heaprel))
    1440             :     {
    1441             :         /* Okay to recycle this page (which could be leaf or internal) */
    1442         278 :         RecordFreeIndexPage(rel, blkno);
    1443         278 :         stats->pages_deleted++;
    1444         278 :         stats->pages_free++;
    1445             :     }
    1446       24532 :     else if (P_ISDELETED(opaque))
    1447             :     {
    1448             :         /*
    1449             :          * Already deleted page (which could be leaf or internal).  Can't
    1450             :          * recycle yet.
    1451             :          */
    1452          38 :         stats->pages_deleted++;
    1453             :     }
    1454       24494 :     else if (P_ISHALFDEAD(opaque))
    1455             :     {
    1456             :         /* Half-dead leaf page (from interrupted VACUUM) -- finish deleting */
    1457           0 :         attempt_pagedel = true;
    1458             : 
    1459             :         /*
    1460             :          * _bt_pagedel() will increment both pages_newly_deleted and
    1461             :          * pages_deleted stats in all cases (barring corruption)
    1462             :          */
    1463             :     }
    1464       24494 :     else if (P_ISLEAF(opaque))
    1465             :     {
    1466             :         OffsetNumber deletable[MaxIndexTuplesPerPage];
    1467             :         int         ndeletable;
    1468             :         BTVacuumPosting updatable[MaxIndexTuplesPerPage];
    1469             :         int         nupdatable;
    1470             :         OffsetNumber offnum,
    1471             :                     minoff,
    1472             :                     maxoff;
    1473             :         int         nhtidsdead,
    1474             :                     nhtidslive;
    1475             : 
    1476             :         /*
    1477             :          * Trade in the initial read lock for a full cleanup lock on this
    1478             :          * page.  We must get such a lock on every leaf page over the course
    1479             :          * of the vacuum scan, whether or not it actually contains any
    1480             :          * deletable tuples --- see nbtree/README.
    1481             :          */
    1482       22986 :         _bt_upgradelockbufcleanup(rel, buf);
    1483             : 
    1484             :         /*
    1485             :          * Check whether we need to backtrack to earlier pages.  What we are
    1486             :          * concerned about is a page split that happened since we started the
    1487             :          * vacuum scan.  If the split moved tuples on the right half of the
    1488             :          * split (i.e. the tuples that sort high) to a block that we already
    1489             :          * passed over, then we might have missed the tuples.  We need to
    1490             :          * backtrack now.  (Must do this before possibly clearing btpo_cycleid
    1491             :          * or deleting scanblkno page below!)
    1492             :          */
    1493       22986 :         if (vstate->cycleid != 0 &&
    1494       22870 :             opaque->btpo_cycleid == vstate->cycleid &&
    1495           0 :             !(opaque->btpo_flags & BTP_SPLIT_END) &&
    1496           0 :             !P_RIGHTMOST(opaque) &&
    1497           0 :             opaque->btpo_next < scanblkno)
    1498           0 :             backtrack_to = opaque->btpo_next;
    1499             : 
    1500       22986 :         ndeletable = 0;
    1501       22986 :         nupdatable = 0;
    1502       22986 :         minoff = P_FIRSTDATAKEY(opaque);
    1503       22986 :         maxoff = PageGetMaxOffsetNumber(page);
    1504       22986 :         nhtidsdead = 0;
    1505       22986 :         nhtidslive = 0;
    1506       22986 :         if (callback)
    1507             :         {
    1508             :             /* btbulkdelete callback tells us what to delete (or update) */
    1509       22870 :             for (offnum = minoff;
    1510     4473482 :                  offnum <= maxoff;
    1511     4450612 :                  offnum = OffsetNumberNext(offnum))
    1512             :             {
    1513             :                 IndexTuple  itup;
    1514             : 
    1515     4450612 :                 itup = (IndexTuple) PageGetItem(page,
    1516     4450612 :                                                 PageGetItemId(page, offnum));
    1517             : 
    1518             :                 Assert(!BTreeTupleIsPivot(itup));
    1519     4450612 :                 if (!BTreeTupleIsPosting(itup))
    1520             :                 {
    1521             :                     /* Regular tuple, standard table TID representation */
    1522     4310334 :                     if (callback(&itup->t_tid, callback_state))
    1523             :                     {
    1524     1623616 :                         deletable[ndeletable++] = offnum;
    1525     1623616 :                         nhtidsdead++;
    1526             :                     }
    1527             :                     else
    1528     2686718 :                         nhtidslive++;
    1529             :                 }
    1530             :                 else
    1531             :                 {
    1532             :                     BTVacuumPosting vacposting;
    1533             :                     int         nremaining;
    1534             : 
    1535             :                     /* Posting list tuple */
    1536      140278 :                     vacposting = btreevacuumposting(vstate, itup, offnum,
    1537             :                                                     &nremaining);
    1538      140278 :                     if (vacposting == NULL)
    1539             :                     {
    1540             :                         /*
    1541             :                          * All table TIDs from the posting tuple remain, so no
    1542             :                          * delete or update required
    1543             :                          */
    1544             :                         Assert(nremaining == BTreeTupleGetNPosting(itup));
    1545             :                     }
    1546       87042 :                     else if (nremaining > 0)
    1547             :                     {
    1548             : 
    1549             :                         /*
    1550             :                          * Store metadata about posting list tuple in
    1551             :                          * updatable array for entire page.  Existing tuple
    1552             :                          * will be updated during the later call to
    1553             :                          * _bt_delitems_vacuum().
    1554             :                          */
    1555             :                         Assert(nremaining < BTreeTupleGetNPosting(itup));
    1556       39896 :                         updatable[nupdatable++] = vacposting;
    1557       39896 :                         nhtidsdead += BTreeTupleGetNPosting(itup) - nremaining;
    1558             :                     }
    1559             :                     else
    1560             :                     {
    1561             :                         /*
    1562             :                          * All table TIDs from the posting list must be
    1563             :                          * deleted.  We'll delete the index tuple completely
    1564             :                          * (no update required).
    1565             :                          */
    1566             :                         Assert(nremaining == 0);
    1567       47146 :                         deletable[ndeletable++] = offnum;
    1568       47146 :                         nhtidsdead += BTreeTupleGetNPosting(itup);
    1569       47146 :                         pfree(vacposting);
    1570             :                     }
    1571             : 
    1572      140278 :                     nhtidslive += nremaining;
    1573             :                 }
    1574             :             }
    1575             :         }
    1576             : 
    1577             :         /*
    1578             :          * Apply any needed deletes or updates.  We issue just one
    1579             :          * _bt_delitems_vacuum() call per page, so as to minimize WAL traffic.
    1580             :          */
    1581       22986 :         if (ndeletable > 0 || nupdatable > 0)
    1582             :         {
    1583             :             Assert(nhtidsdead >= ndeletable + nupdatable);
    1584       14638 :             _bt_delitems_vacuum(rel, buf, deletable, ndeletable, updatable,
    1585             :                                 nupdatable);
    1586             : 
    1587       14638 :             stats->tuples_removed += nhtidsdead;
    1588             :             /* must recompute maxoff */
    1589       14638 :             maxoff = PageGetMaxOffsetNumber(page);
    1590             : 
    1591             :             /* can't leak memory here */
    1592       54534 :             for (int i = 0; i < nupdatable; i++)
    1593       39896 :                 pfree(updatable[i]);
    1594             :         }
    1595             :         else
    1596             :         {
    1597             :             /*
    1598             :              * If the leaf page has been split during this vacuum cycle, it
    1599             :              * seems worth expending a write to clear btpo_cycleid even if we
    1600             :              * don't have any deletions to do.  (If we do, _bt_delitems_vacuum
    1601             :              * takes care of this.)  This ensures we won't process the page
    1602             :              * again.
    1603             :              *
    1604             :              * We treat this like a hint-bit update because there's no need to
    1605             :              * WAL-log it.
    1606             :              */
    1607             :             Assert(nhtidsdead == 0);
    1608        8348 :             if (vstate->cycleid != 0 &&
    1609        8232 :                 opaque->btpo_cycleid == vstate->cycleid)
    1610             :             {
    1611           0 :                 opaque->btpo_cycleid = 0;
    1612           0 :                 MarkBufferDirtyHint(buf, true);
    1613             :             }
    1614             :         }
    1615             : 
    1616             :         /*
    1617             :          * If the leaf page is now empty, try to delete it; else count the
    1618             :          * live tuples (live table TIDs in posting lists are counted as
    1619             :          * separate live tuples).  We don't delete when backtracking, though,
    1620             :          * since that would require teaching _bt_pagedel() about backtracking
    1621             :          * (doesn't seem worth adding more complexity to deal with that).
    1622             :          *
    1623             :          * We don't count the number of live TIDs during cleanup-only calls to
    1624             :          * btvacuumscan (i.e. when callback is not set).  We count the number
    1625             :          * of index tuples directly instead.  This avoids the expense of
    1626             :          * directly examining all of the tuples on each page.  VACUUM will
    1627             :          * treat num_index_tuples as an estimate in cleanup-only case, so it
    1628             :          * doesn't matter that this underestimates num_index_tuples
    1629             :          * significantly in some cases.
    1630             :          */
    1631       22986 :         if (minoff > maxoff)
    1632        5646 :             attempt_pagedel = (blkno == scanblkno);
    1633       17340 :         else if (callback)
    1634       17232 :             stats->num_index_tuples += nhtidslive;
    1635             :         else
    1636         108 :             stats->num_index_tuples += maxoff - minoff + 1;
    1637             : 
    1638             :         Assert(!attempt_pagedel || nhtidslive == 0);
    1639             :     }
    1640             : 
    1641       24810 :     if (attempt_pagedel)
    1642             :     {
    1643             :         MemoryContext oldcontext;
    1644             : 
    1645             :         /* Run pagedel in a temp context to avoid memory leakage */
    1646        5646 :         MemoryContextReset(vstate->pagedelcontext);
    1647        5646 :         oldcontext = MemoryContextSwitchTo(vstate->pagedelcontext);
    1648             : 
    1649             :         /*
    1650             :          * _bt_pagedel maintains the bulk delete stats on our behalf;
    1651             :          * pages_newly_deleted and pages_deleted are likely to be incremented
    1652             :          * during call
    1653             :          */
    1654             :         Assert(blkno == scanblkno);
    1655        5646 :         _bt_pagedel(rel, buf, vstate);
    1656             : 
    1657        5646 :         MemoryContextSwitchTo(oldcontext);
    1658             :         /* pagedel released buffer, so we shouldn't */
    1659             :     }
    1660             :     else
    1661       19164 :         _bt_relbuf(rel, buf);
    1662             : 
    1663       24810 :     if (backtrack_to != P_NONE)
    1664             :     {
    1665           0 :         blkno = backtrack_to;
    1666             : 
    1667             :         /* check for vacuum delay while not holding any buffer lock */
    1668           0 :         vacuum_delay_point(false);
    1669             : 
    1670             :         /*
    1671             :          * We can't use _bt_getbuf() here because it always applies
    1672             :          * _bt_checkpage(), which will barf on an all-zero page. We want to
    1673             :          * recycle all-zero pages, not fail.  Also, we want to use a
    1674             :          * nondefault buffer access strategy.
    1675             :          */
    1676           0 :         buf = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_NORMAL,
    1677             :                                  info->strategy);
    1678           0 :         goto backtrack;
    1679             :     }
    1680             : 
    1681       24810 :     return scanblkno;
    1682             : }
    1683             : 
    1684             : /*
    1685             :  * btreevacuumposting --- determine TIDs still needed in posting list
    1686             :  *
    1687             :  * Returns metadata describing how to build replacement tuple without the TIDs
    1688             :  * that VACUUM needs to delete.  Returned value is NULL in the common case
    1689             :  * where no changes are needed to caller's posting list tuple (we avoid
    1690             :  * allocating memory here as an optimization).
    1691             :  *
    1692             :  * The number of TIDs that should remain in the posting list tuple is set for
    1693             :  * caller in *nremaining.
    1694             :  */
    1695             : static BTVacuumPosting
    1696      140278 : btreevacuumposting(BTVacState *vstate, IndexTuple posting,
    1697             :                    OffsetNumber updatedoffset, int *nremaining)
    1698             : {
    1699      140278 :     int         live = 0;
    1700      140278 :     int         nitem = BTreeTupleGetNPosting(posting);
    1701      140278 :     ItemPointer items = BTreeTupleGetPosting(posting);
    1702      140278 :     BTVacuumPosting vacposting = NULL;
    1703             : 
    1704      787912 :     for (int i = 0; i < nitem; i++)
    1705             :     {
    1706      647634 :         if (!vstate->callback(items + i, vstate->callback_state))
    1707             :         {
    1708             :             /* Live table TID */
    1709      351916 :             live++;
    1710             :         }
    1711      295718 :         else if (vacposting == NULL)
    1712             :         {
    1713             :             /*
    1714             :              * First dead table TID encountered.
    1715             :              *
    1716             :              * It's now clear that we need to delete one or more dead table
    1717             :              * TIDs, so start maintaining metadata describing how to update
    1718             :              * existing posting list tuple.
    1719             :              */
    1720       87042 :             vacposting = palloc(offsetof(BTVacuumPostingData, deletetids) +
    1721             :                                 nitem * sizeof(uint16));
    1722             : 
    1723       87042 :             vacposting->itup = posting;
    1724       87042 :             vacposting->updatedoffset = updatedoffset;
    1725       87042 :             vacposting->ndeletedtids = 0;
    1726       87042 :             vacposting->deletetids[vacposting->ndeletedtids++] = i;
    1727             :         }
    1728             :         else
    1729             :         {
    1730             :             /* Second or subsequent dead table TID */
    1731      208676 :             vacposting->deletetids[vacposting->ndeletedtids++] = i;
    1732             :         }
    1733             :     }
    1734             : 
    1735      140278 :     *nremaining = live;
    1736      140278 :     return vacposting;
    1737             : }
    1738             : 
    1739             : /*
    1740             :  *  btcanreturn() -- Check whether btree indexes support index-only scans.
    1741             :  *
    1742             :  * btrees always do, so this is trivial.
    1743             :  */
    1744             : bool
    1745     1121858 : btcanreturn(Relation index, int attno)
    1746             : {
    1747     1121858 :     return true;
    1748             : }
    1749             : 
    1750             : /*
    1751             :  * btgettreeheight() -- Compute tree height for use by btcostestimate().
    1752             :  */
    1753             : int
    1754      716384 : btgettreeheight(Relation rel)
    1755             : {
    1756      716384 :     return _bt_getrootheight(rel);
    1757             : }
    1758             : 
    1759             : CompareType
    1760           0 : bttranslatestrategy(StrategyNumber strategy, Oid opfamily)
    1761             : {
    1762           0 :     switch (strategy)
    1763             :     {
    1764           0 :         case BTLessStrategyNumber:
    1765           0 :             return COMPARE_LT;
    1766           0 :         case BTLessEqualStrategyNumber:
    1767           0 :             return COMPARE_LE;
    1768           0 :         case BTEqualStrategyNumber:
    1769           0 :             return COMPARE_EQ;
    1770           0 :         case BTGreaterEqualStrategyNumber:
    1771           0 :             return COMPARE_GE;
    1772           0 :         case BTGreaterStrategyNumber:
    1773           0 :             return COMPARE_GT;
    1774           0 :         default:
    1775           0 :             return COMPARE_INVALID;
    1776             :     }
    1777             : }
    1778             : 
    1779             : StrategyNumber
    1780           0 : bttranslatecmptype(CompareType cmptype, Oid opfamily)
    1781             : {
    1782           0 :     switch (cmptype)
    1783             :     {
    1784           0 :         case COMPARE_LT:
    1785           0 :             return BTLessStrategyNumber;
    1786           0 :         case COMPARE_LE:
    1787           0 :             return BTLessEqualStrategyNumber;
    1788           0 :         case COMPARE_EQ:
    1789           0 :             return BTEqualStrategyNumber;
    1790           0 :         case COMPARE_GE:
    1791           0 :             return BTGreaterEqualStrategyNumber;
    1792           0 :         case COMPARE_GT:
    1793           0 :             return BTGreaterStrategyNumber;
    1794           0 :         default:
    1795           0 :             return InvalidStrategy;
    1796             :     }
    1797             : }

Generated by: LCOV version 1.16