nbtree.c File Reference

#include "postgres.h"
#include "access/nbtree.h"
#include "access/relscan.h"
#include "access/stratnum.h"
#include "commands/progress.h"
#include "commands/vacuum.h"
#include "nodes/execnodes.h"
#include "pgstat.h"
#include "storage/bulk_write.h"
#include "storage/condition_variable.h"
#include "storage/indexfsm.h"
#include "storage/ipc.h"
#include "storage/lmgr.h"
#include "storage/lwlock.h"
#include "storage/read_stream.h"
#include "utils/datum.h"
#include "utils/fmgrprotos.h"
#include "utils/index_selfuncs.h"
#include "utils/memutils.h"
#include "utils/wait_event.h"

Include dependency graph for nbtree.c:

Go to the source code of this file.

Data Structures
struct	BTParallelScanDescData

Typedefs
typedef struct BTParallelScanDescData	BTParallelScanDescData
typedef struct BTParallelScanDescData *	BTParallelScanDesc

Enumerations
enum	BTPS_State {   BTPARALLEL_NOT_INITIALIZED , BTPARALLEL_NEED_PRIMSCAN , BTPARALLEL_ADVANCING , BTPARALLEL_IDLE ,   BTPARALLEL_DONE }

Functions
static bool	_bt_start_prim_scan (IndexScanDesc scan)
static void	_bt_parallel_serialize_arrays (Relation rel, BTParallelScanDesc btscan, BTScanOpaque so)
static void	_bt_parallel_restore_arrays (Relation rel, BTParallelScanDesc btscan, BTScanOpaque so)
static void	btvacuumscan (IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, void *callback_state, BTCycleId cycleid)
static BlockNumber	btvacuumpage (BTVacState *vstate, Buffer buf)
static BTVacuumPosting	btreevacuumposting (BTVacState *vstate, IndexTuple posting, OffsetNumber updatedoffset, int *nremaining)
Datum	bthandler (PG_FUNCTION_ARGS)
void	btbuildempty (Relation index)
bool	btinsert (Relation rel, Datum *values, bool *isnull, ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique, bool indexUnchanged, IndexInfo *indexInfo)
bool	btgettuple (IndexScanDesc scan, ScanDirection dir)
int64	btgetbitmap (IndexScanDesc scan, TIDBitmap *tbm)
IndexScanDesc	btbeginscan (Relation rel, int nkeys, int norderbys)
void	btrescan (IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys)
void	btendscan (IndexScanDesc scan)
void	btmarkpos (IndexScanDesc scan)
void	btrestrpos (IndexScanDesc scan)
Size	btestimateparallelscan (Relation rel, int nkeys, int norderbys)
void	btinitparallelscan (void *target)
void	btparallelrescan (IndexScanDesc scan)
bool	_bt_parallel_seize (IndexScanDesc scan, BlockNumber *next_scan_page, BlockNumber *last_curr_page, bool first)
void	_bt_parallel_release (IndexScanDesc scan, BlockNumber next_scan_page, BlockNumber curr_page)
void	_bt_parallel_done (IndexScanDesc scan)
void	_bt_parallel_primscan_schedule (IndexScanDesc scan, BlockNumber curr_page)
IndexBulkDeleteResult *	btbulkdelete (IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, void *callback_state)
IndexBulkDeleteResult *	btvacuumcleanup (IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
bool	btcanreturn (Relation index, int attno)
int	btgettreeheight (Relation rel)
CompareType	bttranslatestrategy (StrategyNumber strategy, Oid opfamily)
StrategyNumber	bttranslatecmptype (CompareType cmptype, Oid opfamily)

Typedef Documentation

BTParallelScanDesc

typedef struct BTParallelScanDescData* BTParallelScanDesc

Definition at line 95 of file nbtree.c.

BTParallelScanDescData

typedef struct BTParallelScanDescData BTParallelScanDescData

Enumeration Type Documentation

BTPS_State

enum BTPS_State

Enumerator
BTPARALLEL_NOT_INITIALIZED
BTPARALLEL_NEED_PRIMSCAN
BTPARALLEL_ADVANCING
BTPARALLEL_IDLE
BTPARALLEL_DONE

Definition at line 56 of file nbtree.c.

{
    BTPARALLEL_NOT_INITIALIZED,
    BTPARALLEL_NEED_PRIMSCAN,
    BTPARALLEL_ADVANCING,
    BTPARALLEL_IDLE,
    BTPARALLEL_DONE,
} BTPS_State;

Function Documentation

_bt_parallel_done()

void _bt_parallel_done

(

IndexScanDesc

scan

)

Definition at line 1038 of file nbtree.c.

{
    BTScanOpaque so = (BTScanOpaque) scan->opaque;
    ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
    BTParallelScanDesc btscan;
    bool        status_changed = false;
 
    Assert(!BTScanPosIsValid(so->currPos));
 
    /* Do nothing, for non-parallel scans */
    if (parallel_scan == NULL)
        return;
 
    /*
     * Should not mark parallel scan done when there's still a pending
     * primitive index scan
     */
    if (so->needPrimScan)
        return;
 
    btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
                                                  parallel_scan->ps_offset_am);
 
    /*
     * Mark the parallel scan as done, unless some other process did so
     * already
     */
    LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
    Assert(btscan->btps_pageStatus != BTPARALLEL_NEED_PRIMSCAN);
    if (btscan->btps_pageStatus != BTPARALLEL_DONE)
    {
        btscan->btps_pageStatus = BTPARALLEL_DONE;
        status_changed = true;
    }
    LWLockRelease(&btscan->btps_lock);
 
    /* wake up all the workers associated with this parallel scan */
    if (status_changed)
        ConditionVariableBroadcast(&btscan->btps_cv);
}

References Assert, BTPARALLEL_DONE, BTPARALLEL_NEED_PRIMSCAN, BTScanPosIsValid, ConditionVariableBroadcast(), fb(), LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), OffsetToPointer, IndexScanDescData::opaque, IndexScanDescData::parallel_scan, and ParallelIndexScanDescData::ps_offset_am.

Referenced by _bt_endpoint(), _bt_first(), _bt_parallel_seize(), _bt_readnextpage(), and _bt_start_prim_scan().

_bt_parallel_primscan_schedule()

void _bt_parallel_primscan_schedule	(	IndexScanDesc	scan,
		BlockNumber	curr_page
	)

Definition at line 1088 of file nbtree.c.

{
    Relation    rel = scan->indexRelation;
    BTScanOpaque so = (BTScanOpaque) scan->opaque;
    ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
    BTParallelScanDesc btscan;
 
    Assert(so->numArrayKeys);
 
    btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
                                                  parallel_scan->ps_offset_am);
 
    LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
    if (btscan->btps_lastCurrPage == curr_page &&
        btscan->btps_pageStatus == BTPARALLEL_IDLE)
    {
        btscan->btps_nextScanPage = InvalidBlockNumber;
        btscan->btps_lastCurrPage = InvalidBlockNumber;
        btscan->btps_pageStatus = BTPARALLEL_NEED_PRIMSCAN;
 
        /* Serialize scan's current array keys */
        _bt_parallel_serialize_arrays(rel, btscan, so);
    }
    LWLockRelease(&btscan->btps_lock);
}

References _bt_parallel_serialize_arrays(), Assert, BTPARALLEL_IDLE, BTPARALLEL_NEED_PRIMSCAN, fb(), IndexScanDescData::indexRelation, InvalidBlockNumber, LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), OffsetToPointer, IndexScanDescData::opaque, IndexScanDescData::parallel_scan, and ParallelIndexScanDescData::ps_offset_am.

Referenced by _bt_advance_array_keys(), and _bt_readpage().

_bt_parallel_release()

void _bt_parallel_release	(	IndexScanDesc	scan,
		BlockNumber	next_scan_page,
		BlockNumber	curr_page
	)

Definition at line 1011 of file nbtree.c.

{
    ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
    BTParallelScanDesc btscan;
 
    Assert(BlockNumberIsValid(next_scan_page));
 
    btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
                                                  parallel_scan->ps_offset_am);
 
    LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
    btscan->btps_nextScanPage = next_scan_page;
    btscan->btps_lastCurrPage = curr_page;
    btscan->btps_pageStatus = BTPARALLEL_IDLE;
    LWLockRelease(&btscan->btps_lock);
    ConditionVariableSignal(&btscan->btps_cv);
}

References Assert, BlockNumberIsValid(), BTPARALLEL_IDLE, ConditionVariableSignal(), fb(), LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), OffsetToPointer, IndexScanDescData::parallel_scan, and ParallelIndexScanDescData::ps_offset_am.

Referenced by _bt_readnextpage(), and _bt_readpage().

_bt_parallel_restore_arrays()

static void _bt_parallel_restore_arrays ( Relation  rel, BTParallelScanDesc  btscan, BTScanOpaque  so  )

static

Definition at line 763 of file nbtree.c.

{
    char       *datumshared;
 
    /* Space for serialized datums begins immediately after btps_arrElems[] */
    datumshared = ((char *) &btscan->btps_arrElems[so->numArrayKeys]);
    for (int i = 0; i < so->numArrayKeys; i++)
    {
        BTArrayKeyInfo *array = &so->arrayKeys[i];
        ScanKey     skey = &so->keyData[array->scan_key];
        bool        isnull;
 
        if (array->num_elems != -1)
        {
            /* Restore SAOP array using its saved cur_elem */
            Assert(!(skey->sk_flags & SK_BT_SKIP));
            array->cur_elem = btscan->btps_arrElems[i];
            skey->sk_argument = array->elem_values[array->cur_elem];
            continue;
        }
 
        /* Restore skip array by restoring its key directly */
        if (!array->attbyval && skey->sk_argument)
            pfree(DatumGetPointer(skey->sk_argument));
        skey->sk_argument = (Datum) 0;
        memcpy(&skey->sk_flags, datumshared, sizeof(int));
        datumshared += sizeof(int);
 
        Assert(skey->sk_flags & SK_BT_SKIP);
 
        if (skey->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL))
        {
            /* No sk_argument datum to restore */
            continue;
        }
 
        skey->sk_argument = datumRestore(&datumshared, &isnull);
        if (isnull)
        {
            Assert(skey->sk_argument == 0);
            Assert(skey->sk_flags & SK_SEARCHNULL);
            Assert(skey->sk_flags & SK_ISNULL);
        }
    }
}

References Assert, BTArrayKeyInfo::attbyval, BTArrayKeyInfo::cur_elem, DatumGetPointer(), datumRestore(), BTArrayKeyInfo::elem_values, fb(), i, memcpy(), BTArrayKeyInfo::num_elems, pfree(), BTArrayKeyInfo::scan_key, SK_BT_MAXVAL, SK_BT_MINVAL, SK_BT_SKIP, SK_ISNULL, and SK_SEARCHNULL.

Referenced by _bt_parallel_seize().

_bt_parallel_seize()

bool _bt_parallel_seize	(	IndexScanDesc	scan,
		BlockNumber *	next_scan_page,
		BlockNumber *	last_curr_page,
		bool	first
	)

Definition at line 873 of file nbtree.c.

{
    Relation    rel = scan->indexRelation;
    BTScanOpaque so = (BTScanOpaque) scan->opaque;
    bool        exit_loop = false,
                status = true,
                endscan = false;
    ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
    BTParallelScanDesc btscan;
 
    *next_scan_page = InvalidBlockNumber;
    *last_curr_page = InvalidBlockNumber;
 
    /*
     * Reset so->currPos, and initialize moreLeft/moreRight such that the next
     * call to _bt_readnextpage treats this backend similarly to a serial
     * backend that steps from *last_curr_page to *next_scan_page (unless this
     * backend's so->currPos is initialized by _bt_readfirstpage before then).
     */
    BTScanPosInvalidate(so->currPos);
    so->currPos.moreLeft = so->currPos.moreRight = true;
 
    if (first)
    {
        /*
         * Initialize array related state when called from _bt_first, assuming
         * that this will be the first primitive index scan for the scan
         */
        so->needPrimScan = false;
        so->scanBehind = false;
        so->oppositeDirCheck = false;
    }
    else
    {
        /*
         * Don't attempt to seize the scan when it requires another primitive
         * index scan, since caller's backend cannot start it right now
         */
        if (so->needPrimScan)
            return false;
    }
 
    btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
                                                  parallel_scan->ps_offset_am);
 
    while (1)
    {
        LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
 
        if (btscan->btps_pageStatus == BTPARALLEL_DONE)
        {
            /* We're done with this parallel index scan */
            status = false;
        }
        else if (btscan->btps_pageStatus == BTPARALLEL_IDLE &&
                 btscan->btps_nextScanPage == P_NONE)
        {
            /* End this parallel index scan */
            status = false;
            endscan = true;
        }
        else if (btscan->btps_pageStatus == BTPARALLEL_NEED_PRIMSCAN)
        {
            Assert(so->numArrayKeys);
 
            if (first)
            {
                /* Can start scheduled primitive scan right away, so do so */
                btscan->btps_pageStatus = BTPARALLEL_ADVANCING;
 
                /* Restore scan's array keys from serialized values */
                _bt_parallel_restore_arrays(rel, btscan, so);
                exit_loop = true;
            }
            else
            {
                /*
                 * Don't attempt to seize the scan when it requires another
                 * primitive index scan, since caller's backend cannot start
                 * it right now
                 */
                status = false;
            }
 
            /*
             * Either way, update backend local state to indicate that a
             * pending primitive scan is required
             */
            so->needPrimScan = true;
            so->scanBehind = false;
            so->oppositeDirCheck = false;
        }
        else if (btscan->btps_pageStatus != BTPARALLEL_ADVANCING)
        {
            /*
             * We have successfully seized control of the scan for the purpose
             * of advancing it to a new page!
             */
            btscan->btps_pageStatus = BTPARALLEL_ADVANCING;
            Assert(btscan->btps_nextScanPage != P_NONE);
            *next_scan_page = btscan->btps_nextScanPage;
            *last_curr_page = btscan->btps_lastCurrPage;
            exit_loop = true;
        }
        LWLockRelease(&btscan->btps_lock);
        if (exit_loop || !status)
            break;
        ConditionVariableSleep(&btscan->btps_cv, WAIT_EVENT_BTREE_PAGE);
    }
    ConditionVariableCancelSleep();
 
    /* When the scan has reached the rightmost (or leftmost) page, end it */
    if (endscan)
        _bt_parallel_done(scan);
 
    return status;
}

References _bt_parallel_done(), _bt_parallel_restore_arrays(), Assert, BTPARALLEL_ADVANCING, BTPARALLEL_DONE, BTPARALLEL_IDLE, BTPARALLEL_NEED_PRIMSCAN, BTScanPosInvalidate, ConditionVariableCancelSleep(), ConditionVariableSleep(), fb(), IndexScanDescData::indexRelation, InvalidBlockNumber, LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), OffsetToPointer, IndexScanDescData::opaque, P_NONE, IndexScanDescData::parallel_scan, and ParallelIndexScanDescData::ps_offset_am.

Referenced by _bt_first(), and _bt_readnextpage().

_bt_parallel_serialize_arrays()

static void _bt_parallel_serialize_arrays ( Relation  rel, BTParallelScanDesc  btscan, BTScanOpaque  so  )

static

Definition at line 720 of file nbtree.c.

{
    char       *datumshared;
 
    /* Space for serialized datums begins immediately after btps_arrElems[] */
    datumshared = ((char *) &btscan->btps_arrElems[so->numArrayKeys]);
    for (int i = 0; i < so->numArrayKeys; i++)
    {
        BTArrayKeyInfo *array = &so->arrayKeys[i];
        ScanKey     skey = &so->keyData[array->scan_key];
 
        if (array->num_elems != -1)
        {
            /* Save SAOP array's cur_elem (no need to copy key/datum) */
            Assert(!(skey->sk_flags & SK_BT_SKIP));
            btscan->btps_arrElems[i] = array->cur_elem;
            continue;
        }
 
        /* Save all mutable state associated with skip array's key */
        Assert(skey->sk_flags & SK_BT_SKIP);
        memcpy(datumshared, &skey->sk_flags, sizeof(int));
        datumshared += sizeof(int);
 
        if (skey->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL))
        {
            /* No sk_argument datum to serialize */
            Assert(skey->sk_argument == 0);
            continue;
        }
 
        datumSerialize(skey->sk_argument, (skey->sk_flags & SK_ISNULL) != 0,
                       array->attbyval, array->attlen, &datumshared);
    }
}

References Assert, BTArrayKeyInfo::attbyval, BTArrayKeyInfo::attlen, BTArrayKeyInfo::cur_elem, datumSerialize(), fb(), i, memcpy(), BTArrayKeyInfo::num_elems, BTArrayKeyInfo::scan_key, SK_BT_MAXVAL, SK_BT_MINVAL, SK_BT_SKIP, and SK_ISNULL.

Referenced by _bt_parallel_primscan_schedule().

_bt_start_prim_scan()

static bool _bt_start_prim_scan ( IndexScanDesc  scan )

static

Definition at line 656 of file nbtree.c.

{
    BTScanOpaque so = (BTScanOpaque) scan->opaque;
 
    Assert(so->numArrayKeys);
 
    so->scanBehind = so->oppositeDirCheck = false;  /* reset */
 
    /*
     * Array keys are advanced within _bt_checkkeys when the scan reaches the
     * leaf level (more precisely, they're advanced when the scan reaches the
     * end of each distinct set of array elements).  This process avoids
     * repeat access to leaf pages (across multiple primitive index scans) by
     * advancing the scan's array keys when it allows the primitive index scan
     * to find nearby matching tuples (or when it eliminates ranges of array
     * key space that can't possibly be satisfied by any index tuple).
     *
     * _bt_checkkeys sets a simple flag variable to schedule another primitive
     * index scan.  The flag tells us what to do.
     *
     * We cannot rely on _bt_first always reaching _bt_checkkeys.  There are
     * various cases where that won't happen.  For example, if the index is
     * completely empty, then _bt_first won't call _bt_readpage/_bt_checkkeys.
     * We also don't expect a call to _bt_checkkeys during searches for a
     * non-existent value that happens to be lower/higher than any existing
     * value in the index.
     *
     * We don't require special handling for these cases -- we don't need to
     * be explicitly instructed to _not_ perform another primitive index scan.
     * It's up to code under the control of _bt_first to always set the flag
     * when another primitive index scan will be required.
     *
     * This works correctly, even with the tricky cases listed above, which
     * all involve access to leaf pages "near the boundaries of the key space"
     * (whether it's from a leftmost/rightmost page, or an imaginary empty
     * leaf root page).  If _bt_checkkeys cannot be reached by a primitive
     * index scan for one set of array keys, then it also won't be reached for
     * any later set ("later" in terms of the direction that we scan the index
     * and advance the arrays).  The array keys won't have advanced in these
     * cases, but that's the correct behavior (even _bt_advance_array_keys
     * won't always advance the arrays at the point they become "exhausted").
     */
    if (so->needPrimScan)
    {
        /*
         * Flag was set -- must call _bt_first again, which will reset the
         * scan's needPrimScan flag
         */
        return true;
    }
 
    /* The top-level index scan ran out of tuples in this scan direction */
    if (scan->parallel_scan != NULL)
        _bt_parallel_done(scan);
 
    return false;
}

References _bt_parallel_done(), Assert, fb(), IndexScanDescData::opaque, and IndexScanDescData::parallel_scan.

Referenced by btgetbitmap(), and btgettuple().

btbeginscan()

IndexScanDesc btbeginscan	(	Relation	rel,
		int	nkeys,
		int	norderbys
	)

Definition at line 339 of file nbtree.c.

{
    IndexScanDesc scan;
    BTScanOpaque so;
 
    /* no order by operators allowed */
    Assert(norderbys == 0);
 
    /* get the scan */
    scan = RelationGetIndexScan(rel, nkeys, norderbys);
 
    /* allocate private workspace */
    so = palloc_object(BTScanOpaqueData);
    BTScanPosInvalidate(so->currPos);
    BTScanPosInvalidate(so->markPos);
    if (scan->numberOfKeys > 0)
        so->keyData = (ScanKey) palloc(scan->numberOfKeys * sizeof(ScanKeyData));
    else
        so->keyData = NULL;
 
    so->skipScan = false;
    so->needPrimScan = false;
    so->scanBehind = false;
    so->oppositeDirCheck = false;
    so->arrayKeys = NULL;
    so->orderProcs = NULL;
    so->arrayContext = NULL;
 
    so->killedItems = NULL;     /* until needed */
    so->numKilled = 0;
 
    /*
     * We don't know yet whether the scan will be index-only, so we do not
     * allocate the tuple workspace arrays until btrescan.  However, we set up
     * scan->xs_itupdesc whether we'll need it or not, since that's so cheap.
     */
    so->currTuples = so->markTuples = NULL;
 
    scan->xs_itupdesc = RelationGetDescr(rel);
 
    scan->opaque = so;
 
    return scan;
}

References Assert, BTScanPosInvalidate, fb(), IndexScanDescData::numberOfKeys, IndexScanDescData::opaque, palloc(), palloc_object, RelationGetDescr, RelationGetIndexScan(), and IndexScanDescData::xs_itupdesc.

Referenced by bthandler().

btbuildempty()

void btbuildempty

(

Relation

index

)

Definition at line 183 of file nbtree.c.

{
    bool        allequalimage = _bt_allequalimage(index, false);
    BulkWriteState *bulkstate;
    BulkWriteBuffer metabuf;
 
    bulkstate = smgr_bulk_start_rel(index, INIT_FORKNUM);
 
    /* Construct metapage. */
    metabuf = smgr_bulk_get_buf(bulkstate);
    _bt_initmetapage((Page) metabuf, P_NONE, 0, allequalimage);
    smgr_bulk_write(bulkstate, BTREE_METAPAGE, metabuf, true);
 
    smgr_bulk_finish(bulkstate);
}

References _bt_allequalimage(), _bt_initmetapage(), BTREE_METAPAGE, fb(), INIT_FORKNUM, P_NONE, smgr_bulk_finish(), smgr_bulk_get_buf(), smgr_bulk_start_rel(), and smgr_bulk_write().

Referenced by bthandler().

btbulkdelete()

IndexBulkDeleteResult * btbulkdelete	(	IndexVacuumInfo *	info,
		IndexBulkDeleteResult *	stats,
		IndexBulkDeleteCallback	callback,
		void *	callback_state
	)

Definition at line 1122 of file nbtree.c.

{
    Relation    rel = info->index;
    BTCycleId   cycleid;
 
    /* allocate stats if first time through, else re-use existing struct */
    if (stats == NULL)
        stats = palloc0_object(IndexBulkDeleteResult);
 
    /* Establish the vacuum cycle ID to use for this scan */
    /* The ENSURE stuff ensures we clean up shared memory on failure */
    PG_ENSURE_ERROR_CLEANUP(_bt_end_vacuum_callback, PointerGetDatum(rel));
    {
        cycleid = _bt_start_vacuum(rel);
 
        btvacuumscan(info, stats, callback, callback_state, cycleid);
    }
    PG_END_ENSURE_ERROR_CLEANUP(_bt_end_vacuum_callback, PointerGetDatum(rel));
    _bt_end_vacuum(rel);
 
    return stats;
}

References _bt_end_vacuum(), _bt_end_vacuum_callback(), _bt_start_vacuum(), btvacuumscan(), callback(), fb(), IndexVacuumInfo::index, palloc0_object, PG_END_ENSURE_ERROR_CLEANUP, PG_ENSURE_ERROR_CLEANUP, and PointerGetDatum.

Referenced by bthandler().

btcanreturn()

bool btcanreturn	(	Relation	index,
		int	attno
	)

Definition at line 1802 of file nbtree.c.

{
    return true;
}

Referenced by bthandler().

btendscan()

void btendscan

(

IndexScanDesc

scan

)

Definition at line 455 of file nbtree.c.

{
    BTScanOpaque so = (BTScanOpaque) scan->opaque;
 
    /* we aren't holding any read locks, but gotta drop the pins */
    if (BTScanPosIsValid(so->currPos))
    {
        /* Before leaving current page, deal with any killed items */
        if (so->numKilled > 0)
            _bt_killitems(scan);
        BTScanPosUnpinIfPinned(so->currPos);
    }
 
    so->markItemIndex = -1;
    BTScanPosUnpinIfPinned(so->markPos);
 
    /* No need to invalidate positions, the RAM is about to be freed. */
 
    /* Release storage */
    if (so->keyData != NULL)
        pfree(so->keyData);
    /* so->arrayKeys and so->orderProcs are in arrayContext */
    if (so->arrayContext != NULL)
        MemoryContextDelete(so->arrayContext);
    if (so->killedItems != NULL)
        pfree(so->killedItems);
    if (so->currTuples != NULL)
        pfree(so->currTuples);
    /* so->markTuples should not be pfree'd, see btrescan */
    pfree(so);
}

References _bt_killitems(), BTScanPosIsValid, BTScanPosUnpinIfPinned, fb(), MemoryContextDelete(), IndexScanDescData::opaque, and pfree().

Referenced by bthandler().

btestimateparallelscan()

Size btestimateparallelscan	(	Relation	rel,
		int	nkeys,
		int	norderbys
	)

Definition at line 575 of file nbtree.c.

{
    int16       nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
    Size        estnbtreeshared,
                genericattrspace;
 
    /*
     * Pessimistically assume that every input scan key will be output with
     * its own SAOP array
     */
    estnbtreeshared = offsetof(BTParallelScanDescData, btps_arrElems) +
        sizeof(int) * nkeys;
 
    /* Single column indexes cannot possibly use a skip array */
    if (nkeyatts == 1)
        return estnbtreeshared;
 
    /*
     * Pessimistically assume that all attributes prior to the least
     * significant attribute require a skip array (and an associated key)
     */
    genericattrspace = datumEstimateSpace((Datum) 0, false, true,
                                          sizeof(Datum));
    for (int attnum = 1; attnum < nkeyatts; attnum++)
    {
        CompactAttribute *attr;
 
        /*
         * We make the conservative assumption that every index column will
         * also require a skip array.
         *
         * Every skip array must have space to store its scan key's sk_flags.
         * We also need space for each skip array's unused btps_arrElems slot
         * (we need to be able to subscript btps_arrElems using a simple
         * so->arrayKeys[]-wise offset for any subsequent SAOP arrays).
         */
        estnbtreeshared = add_size(estnbtreeshared, sizeof(int) * 2);
 
        /* Consider space required to store a datum of opclass input type */
        attr = TupleDescCompactAttr(rel->rd_att, attnum - 1);
        if (attr->attbyval)
        {
            /* This index attribute stores pass-by-value datums */
            Size        estfixed = datumEstimateSpace((Datum) 0, false,
                                                      true, attr->attlen);
 
            estnbtreeshared = add_size(estnbtreeshared, estfixed);
            continue;
        }
 
        /*
         * This index attribute stores pass-by-reference datums.
         *
         * Assume that serializing this array will use just as much space as a
         * pass-by-value datum, in addition to space for the largest possible
         * whole index tuple (this is not just a per-datum portion of the
         * largest possible tuple because that'd be almost as large anyway).
         *
         * This is quite conservative, but it's not clear how we could do much
         * better.  The executor requires an up-front storage request size
         * that reliably covers the scan's high watermark memory usage.  We
         * can't be sure of the real high watermark until the scan is over.
         */
        estnbtreeshared = add_size(estnbtreeshared, genericattrspace);
        estnbtreeshared = add_size(estnbtreeshared, BTMaxItemSize);
    }
 
    return estnbtreeshared;
}

References add_size(), CompactAttribute::attbyval, CompactAttribute::attlen, attnum, BTMaxItemSize, BTParallelScanDescData::btps_arrElems, datumEstimateSpace(), fb(), IndexRelationGetNumberOfKeyAttributes, RelationData::rd_att, and TupleDescCompactAttr().

Referenced by bthandler().

btgetbitmap()

int64 btgetbitmap	(	IndexScanDesc	scan,
		TIDBitmap *	tbm
	)

Definition at line 291 of file nbtree.c.

{
    BTScanOpaque so = (BTScanOpaque) scan->opaque;
    int64       ntids = 0;
    ItemPointer heapTid;
 
    Assert(scan->heapRelation == NULL);
 
    /* Each loop iteration performs another primitive index scan */
    do
    {
        /* Fetch the first page & tuple */
        if (_bt_first(scan, ForwardScanDirection))
        {
            /* Save tuple ID, and continue scanning */
            heapTid = &scan->xs_heaptid;
            tbm_add_tuples(tbm, heapTid, 1, false);
            ntids++;
 
            for (;;)
            {
                /*
                 * Advance to next tuple within page.  This is the same as the
                 * easy case in _bt_next().
                 */
                if (++so->currPos.itemIndex > so->currPos.lastItem)
                {
                    /* let _bt_next do the heavy lifting */
                    if (!_bt_next(scan, ForwardScanDirection))
                        break;
                }
 
                /* Save tuple ID, and continue scanning */
                heapTid = &so->currPos.items[so->currPos.itemIndex].heapTid;
                tbm_add_tuples(tbm, heapTid, 1, false);
                ntids++;
            }
        }
        /* Now see if we need another primitive index scan */
    } while (so->numArrayKeys && _bt_start_prim_scan(scan));
 
    return ntids;
}

References _bt_first(), _bt_next(), _bt_start_prim_scan(), Assert, fb(), ForwardScanDirection, IndexScanDescData::heapRelation, IndexScanDescData::opaque, tbm_add_tuples(), and IndexScanDescData::xs_heaptid.

Referenced by bthandler().

btgettreeheight()

int btgettreeheight

(

Relation

rel

)

Definition at line 1811 of file nbtree.c.

{
    return _bt_getrootheight(rel);
}

References _bt_getrootheight().

Referenced by bthandler().

btgettuple()

bool btgettuple	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 230 of file nbtree.c.

{
    BTScanOpaque so = (BTScanOpaque) scan->opaque;
    bool        res;
 
    Assert(scan->heapRelation != NULL);
 
    /* btree indexes are never lossy */
    scan->xs_recheck = false;
 
    /* Each loop iteration performs another primitive index scan */
    do
    {
        /*
         * If we've already initialized this scan, we can just advance it in
         * the appropriate direction.  If we haven't done so yet, we call
         * _bt_first() to get the first item in the scan.
         */
        if (!BTScanPosIsValid(so->currPos))
            res = _bt_first(scan, dir);
        else
        {
            /*
             * Check to see if we should kill the previously-fetched tuple.
             */
            if (scan->kill_prior_tuple)
            {
                /*
                 * Yes, remember it for later. (We'll deal with all such
                 * tuples at once right before leaving the index page.)  The
                 * test for numKilled overrun is not just paranoia: if the
                 * caller reverses direction in the indexscan then the same
                 * item might get entered multiple times. It's not worth
                 * trying to optimize that, so we don't detect it, but instead
                 * just forget any excess entries.
                 */
                if (so->killedItems == NULL)
                    so->killedItems = palloc_array(int, MaxTIDsPerBTreePage);
                if (so->numKilled < MaxTIDsPerBTreePage)
                    so->killedItems[so->numKilled++] = so->currPos.itemIndex;
            }
 
            /*
             * Now continue the scan.
             */
            res = _bt_next(scan, dir);
        }
 
        /* If we have a tuple, return it ... */
        if (res)
            break;
        /* ... otherwise see if we need another primitive index scan */
    } while (so->numArrayKeys && _bt_start_prim_scan(scan));
 
    return res;
}

References _bt_first(), _bt_next(), _bt_start_prim_scan(), Assert, BTScanPosIsValid, fb(), IndexScanDescData::heapRelation, IndexScanDescData::kill_prior_tuple, MaxTIDsPerBTreePage, IndexScanDescData::opaque, palloc_array, and IndexScanDescData::xs_recheck.

Referenced by bthandler().

bthandler()

Datum bthandler

(

PG_FUNCTION_ARGS

)

Definition at line 118 of file nbtree.c.

{
    static const IndexAmRoutine amroutine = {
        .type = T_IndexAmRoutine,
        .amstrategies = BTMaxStrategyNumber,
        .amsupport = BTNProcs,
        .amoptsprocnum = BTOPTIONS_PROC,
        .amcanorder = true,
        .amcanorderbyop = false,
        .amcanhash = false,
        .amconsistentequality = true,
        .amconsistentordering = true,
        .amcanbackward = true,
        .amcanunique = true,
        .amcanmulticol = true,
        .amoptionalkey = true,
        .amsearcharray = true,
        .amsearchnulls = true,
        .amstorage = false,
        .amclusterable = true,
        .ampredlocks = true,
        .amcanparallel = true,
        .amcanbuildparallel = true,
        .amcaninclude = true,
        .amusemaintenanceworkmem = false,
        .amsummarizing = false,
        .amparallelvacuumoptions =
        VACUUM_OPTION_PARALLEL_BULKDEL | VACUUM_OPTION_PARALLEL_COND_CLEANUP,
        .amkeytype = InvalidOid,
 
        .ambuild = btbuild,
        .ambuildempty = btbuildempty,
        .aminsert = btinsert,
        .aminsertcleanup = NULL,
        .ambulkdelete = btbulkdelete,
        .amvacuumcleanup = btvacuumcleanup,
        .amcanreturn = btcanreturn,
        .amcostestimate = btcostestimate,
        .amgettreeheight = btgettreeheight,
        .amoptions = btoptions,
        .amproperty = btproperty,
        .ambuildphasename = btbuildphasename,
        .amvalidate = btvalidate,
        .amadjustmembers = btadjustmembers,
        .ambeginscan = btbeginscan,
        .amrescan = btrescan,
        .amgettuple = btgettuple,
        .amgetbitmap = btgetbitmap,
        .amendscan = btendscan,
        .ammarkpos = btmarkpos,
        .amrestrpos = btrestrpos,
        .amestimateparallelscan = btestimateparallelscan,
        .aminitparallelscan = btinitparallelscan,
        .amparallelrescan = btparallelrescan,
        .amtranslatestrategy = bttranslatestrategy,
        .amtranslatecmptype = bttranslatecmptype,
    };
 
    PG_RETURN_POINTER(&amroutine);
}

References btadjustmembers(), btbeginscan(), btbuild(), btbuildempty(), btbuildphasename(), btbulkdelete(), btcanreturn(), btcostestimate(), btendscan(), btestimateparallelscan(), btgetbitmap(), btgettreeheight(), btgettuple(), btinitparallelscan(), btinsert(), btmarkpos(), BTMaxStrategyNumber, BTNProcs, btoptions(), BTOPTIONS_PROC, btparallelrescan(), btproperty(), btrescan(), btrestrpos(), bttranslatecmptype(), bttranslatestrategy(), btvacuumcleanup(), btvalidate(), fb(), InvalidOid, PG_RETURN_POINTER, IndexAmRoutine::type, VACUUM_OPTION_PARALLEL_BULKDEL, and VACUUM_OPTION_PARALLEL_COND_CLEANUP.

btinitparallelscan()

void btinitparallelscan

(

void *

target

)

Definition at line 814 of file nbtree.c.

{
    BTParallelScanDesc bt_target = (BTParallelScanDesc) target;
 
    LWLockInitialize(&bt_target->btps_lock,
                     LWTRANCHE_PARALLEL_BTREE_SCAN);
    bt_target->btps_nextScanPage = InvalidBlockNumber;
    bt_target->btps_lastCurrPage = InvalidBlockNumber;
    bt_target->btps_pageStatus = BTPARALLEL_NOT_INITIALIZED;
    ConditionVariableInit(&bt_target->btps_cv);
}

References BTPARALLEL_NOT_INITIALIZED, ConditionVariableInit(), fb(), InvalidBlockNumber, and LWLockInitialize().

Referenced by bthandler().

btinsert()

bool btinsert	(	Relation	rel,
		Datum *	values,
		bool *	isnull,
		ItemPointer	ht_ctid,
		Relation	heapRel,
		IndexUniqueCheck	checkUnique,
		bool	indexUnchanged,
		IndexInfo *	indexInfo
	)

Definition at line 206 of file nbtree.c.

{
    bool        result;
    IndexTuple  itup;
 
    /* generate an index tuple */
    itup = index_form_tuple(RelationGetDescr(rel), values, isnull);
    itup->t_tid = *ht_ctid;
 
    result = _bt_doinsert(rel, itup, checkUnique, indexUnchanged, heapRel);
 
    pfree(itup);
 
    return result;
}

References _bt_doinsert(), fb(), index_form_tuple(), pfree(), RelationGetDescr, result, IndexTupleData::t_tid, and values.

Referenced by bthandler().

btmarkpos()

void btmarkpos

(

IndexScanDesc

scan

)

Definition at line 491 of file nbtree.c.

{
    BTScanOpaque so = (BTScanOpaque) scan->opaque;
 
    /* There may be an old mark with a pin (but no lock). */
    BTScanPosUnpinIfPinned(so->markPos);
 
    /*
     * Just record the current itemIndex.  If we later step to next page
     * before releasing the marked position, _bt_steppage makes a full copy of
     * the currPos struct in markPos.  If (as often happens) the mark is moved
     * before we leave the page, we don't have to do that work.
     */
    if (BTScanPosIsValid(so->currPos))
        so->markItemIndex = so->currPos.itemIndex;
    else
    {
        BTScanPosInvalidate(so->markPos);
        so->markItemIndex = -1;
    }
}

References BTScanPosInvalidate, BTScanPosIsValid, BTScanPosUnpinIfPinned, fb(), and IndexScanDescData::opaque.

Referenced by bthandler().

btparallelrescan()

void btparallelrescan

(

IndexScanDesc

scan

)

Definition at line 830 of file nbtree.c.

{
    BTParallelScanDesc btscan;
    ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
 
    Assert(parallel_scan);
 
    btscan = (BTParallelScanDesc) OffsetToPointer(parallel_scan,
                                                  parallel_scan->ps_offset_am);
 
    /*
     * In theory, we don't need to acquire the LWLock here, because there
     * shouldn't be any other workers running at this point, but we do so for
     * consistency.
     */
    LWLockAcquire(&btscan->btps_lock, LW_EXCLUSIVE);
    btscan->btps_nextScanPage = InvalidBlockNumber;
    btscan->btps_lastCurrPage = InvalidBlockNumber;
    btscan->btps_pageStatus = BTPARALLEL_NOT_INITIALIZED;
    LWLockRelease(&btscan->btps_lock);
}

References Assert, BTPARALLEL_NOT_INITIALIZED, fb(), InvalidBlockNumber, LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), OffsetToPointer, IndexScanDescData::parallel_scan, and ParallelIndexScanDescData::ps_offset_am.

Referenced by bthandler().

btreevacuumposting()

static BTVacuumPosting btreevacuumposting ( BTVacState *  vstate, IndexTuple  posting, OffsetNumber  updatedoffset, int *  nremaining  )

static

Definition at line 1753 of file nbtree.c.

{
    int         live = 0;
    int         nitem = BTreeTupleGetNPosting(posting);
    ItemPointer items = BTreeTupleGetPosting(posting);
    BTVacuumPosting vacposting = NULL;
 
    for (int i = 0; i < nitem; i++)
    {
        if (!vstate->callback(items + i, vstate->callback_state))
        {
            /* Live table TID */
            live++;
        }
        else if (vacposting == NULL)
        {
            /*
             * First dead table TID encountered.
             *
             * It's now clear that we need to delete one or more dead table
             * TIDs, so start maintaining metadata describing how to update
             * existing posting list tuple.
             */
            vacposting = palloc(offsetof(BTVacuumPostingData, deletetids) +
                                nitem * sizeof(uint16));
 
            vacposting->itup = posting;
            vacposting->updatedoffset = updatedoffset;
            vacposting->ndeletedtids = 0;
            vacposting->deletetids[vacposting->ndeletedtids++] = i;
        }
        else
        {
            /* Second or subsequent dead table TID */
            vacposting->deletetids[vacposting->ndeletedtids++] = i;
        }
    }
 
    *nremaining = live;
    return vacposting;
}

References BTreeTupleGetNPosting(), BTreeTupleGetPosting(), fb(), i, items, and palloc().

Referenced by btvacuumpage().

btrescan()

void btrescan	(	IndexScanDesc	scan,
		ScanKey	scankey,
		int	nscankeys,
		ScanKey	orderbys,
		int	norderbys
	)

Definition at line 388 of file nbtree.c.

{
    BTScanOpaque so = (BTScanOpaque) scan->opaque;
 
    /* we aren't holding any read locks, but gotta drop the pins */
    if (BTScanPosIsValid(so->currPos))
    {
        /* Before leaving current page, deal with any killed items */
        if (so->numKilled > 0)
            _bt_killitems(scan);
        BTScanPosUnpinIfPinned(so->currPos);
        BTScanPosInvalidate(so->currPos);
    }
 
    /*
     * We prefer to eagerly drop leaf page pins before btgettuple returns.
     * This avoids making VACUUM wait to acquire a cleanup lock on the page.
     *
     * We cannot safely drop leaf page pins during index-only scans due to a
     * race condition involving VACUUM setting pages all-visible in the VM.
     * It's also unsafe for plain index scans that use a non-MVCC snapshot.
     *
     * Also opt out of dropping leaf page pins eagerly during bitmap scans.
     * Pins cannot be held for more than an instant during bitmap scans either
     * way, so we might as well avoid wasting cycles on acquiring page LSNs.
     *
     * See nbtree/README section on making concurrent TID recycling safe.
     *
     * Note: so->dropPin should never change across rescans.
     */
    so->dropPin = (!scan->xs_want_itup &&
                   IsMVCCLikeSnapshot(scan->xs_snapshot) &&
                   scan->heapRelation != NULL);
 
    so->markItemIndex = -1;
    so->needPrimScan = false;
    so->scanBehind = false;
    so->oppositeDirCheck = false;
    BTScanPosUnpinIfPinned(so->markPos);
    BTScanPosInvalidate(so->markPos);
 
    /*
     * Allocate tuple workspace arrays, if needed for an index-only scan and
     * not already done in a previous rescan call.  To save on palloc
     * overhead, both workspaces are allocated as one palloc block; only this
     * function and btendscan know that.
     */
    if (scan->xs_want_itup && so->currTuples == NULL)
    {
        so->currTuples = (char *) palloc(BLCKSZ * 2);
        so->markTuples = so->currTuples + BLCKSZ;
    }
 
    /*
     * Reset the scan keys
     */
    if (scankey && scan->numberOfKeys > 0)
        memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
    so->numberOfKeys = 0;       /* until _bt_preprocess_keys sets it */
    so->numArrayKeys = 0;       /* ditto */
}

References _bt_killitems(), BTScanPosInvalidate, BTScanPosIsValid, BTScanPosUnpinIfPinned, fb(), IndexScanDescData::heapRelation, IsMVCCLikeSnapshot, IndexScanDescData::keyData, memcpy(), IndexScanDescData::numberOfKeys, IndexScanDescData::opaque, palloc(), IndexScanDescData::xs_snapshot, and IndexScanDescData::xs_want_itup.

Referenced by bthandler().

btrestrpos()

void btrestrpos

(

IndexScanDesc

scan

)

Definition at line 517 of file nbtree.c.

{
    BTScanOpaque so = (BTScanOpaque) scan->opaque;
 
    if (so->markItemIndex >= 0)
    {
        /*
         * The scan has never moved to a new page since the last mark.  Just
         * restore the itemIndex.
         *
         * NB: In this case we can't count on anything in so->markPos to be
         * accurate.
         */
        so->currPos.itemIndex = so->markItemIndex;
    }
    else
    {
        /*
         * The scan moved to a new page after last mark or restore, and we are
         * now restoring to the marked page.  We aren't holding any read
         * locks, but if we're still holding the pin for the current position,
         * we must drop it.
         */
        if (BTScanPosIsValid(so->currPos))
        {
            /* Before leaving current page, deal with any killed items */
            if (so->numKilled > 0)
                _bt_killitems(scan);
            BTScanPosUnpinIfPinned(so->currPos);
        }
 
        if (BTScanPosIsValid(so->markPos))
        {
            /* bump pin on mark buffer for assignment to current buffer */
            if (BTScanPosIsPinned(so->markPos))
                IncrBufferRefCount(so->markPos.buf);
            memcpy(&so->currPos, &so->markPos,
                   offsetof(BTScanPosData, items[1]) +
                   so->markPos.lastItem * sizeof(BTScanPosItem));
            if (so->currTuples)
                memcpy(so->currTuples, so->markTuples,
                       so->markPos.nextTupleOffset);
            /* Reset the scan's array keys (see _bt_steppage for why) */
            if (so->numArrayKeys)
            {
                _bt_start_array_keys(scan, so->currPos.dir);
                so->needPrimScan = false;
            }
        }
        else
            BTScanPosInvalidate(so->currPos);
    }
}

References _bt_killitems(), _bt_start_array_keys(), BTScanPosInvalidate, BTScanPosIsPinned, BTScanPosIsValid, BTScanPosUnpinIfPinned, fb(), IncrBufferRefCount(), items, memcpy(), and IndexScanDescData::opaque.

Referenced by bthandler().

bttranslatecmptype()

StrategyNumber bttranslatecmptype	(	CompareType	cmptype,
		Oid	opfamily
	)

Definition at line 1837 of file nbtree.c.

{
    switch (cmptype)
    {
        case COMPARE_LT:
            return BTLessStrategyNumber;
        case COMPARE_LE:
            return BTLessEqualStrategyNumber;
        case COMPARE_EQ:
            return BTEqualStrategyNumber;
        case COMPARE_GE:
            return BTGreaterEqualStrategyNumber;
        case COMPARE_GT:
            return BTGreaterStrategyNumber;
        default:
            return InvalidStrategy;
    }
}

References BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, COMPARE_EQ, COMPARE_GE, COMPARE_GT, COMPARE_LE, COMPARE_LT, and InvalidStrategy.

Referenced by bthandler().

bttranslatestrategy()

CompareType bttranslatestrategy	(	StrategyNumber	strategy,
		Oid	opfamily
	)

Definition at line 1817 of file nbtree.c.

{
    switch (strategy)
    {
        case BTLessStrategyNumber:
            return COMPARE_LT;
        case BTLessEqualStrategyNumber:
            return COMPARE_LE;
        case BTEqualStrategyNumber:
            return COMPARE_EQ;
        case BTGreaterEqualStrategyNumber:
            return COMPARE_GE;
        case BTGreaterStrategyNumber:
            return COMPARE_GT;
        default:
            return COMPARE_INVALID;
    }
}

References BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, COMPARE_EQ, COMPARE_GE, COMPARE_GT, COMPARE_INVALID, COMPARE_LE, and COMPARE_LT.

Referenced by bthandler().

btvacuumcleanup()

IndexBulkDeleteResult * btvacuumcleanup	(	IndexVacuumInfo *	info,
		IndexBulkDeleteResult *	stats
	)

Definition at line 1152 of file nbtree.c.

{
    BlockNumber num_delpages;
 
    /* No-op in ANALYZE ONLY mode */
    if (info->analyze_only)
        return stats;
 
    /*
     * If btbulkdelete was called, we need not do anything (we just maintain
     * the information used within _bt_vacuum_needs_cleanup() by calling
     * _bt_set_cleanup_info() below).
     *
     * If btbulkdelete was _not_ called, then we have a choice to make: we
     * must decide whether or not a btvacuumscan() call is needed now (i.e.
     * whether the ongoing VACUUM operation can entirely avoid a physical scan
     * of the index).  A call to _bt_vacuum_needs_cleanup() decides it for us
     * now.
     */
    if (stats == NULL)
    {
        /* Check if VACUUM operation can entirely avoid btvacuumscan() call */
        if (!_bt_vacuum_needs_cleanup(info->index))
            return NULL;
 
        /*
         * Since we aren't going to actually delete any leaf items, there's no
         * need to go through all the vacuum-cycle-ID pushups here.
         *
         * Posting list tuples are a source of inaccuracy for cleanup-only
         * scans.  btvacuumscan() will assume that the number of index tuples
         * from each page can be used as num_index_tuples, even though
         * num_index_tuples is supposed to represent the number of TIDs in the
         * index.  This naive approach can underestimate the number of tuples
         * in the index significantly.
         *
         * We handle the problem by making num_index_tuples an estimate in
         * cleanup-only case.
         */
        stats = palloc0_object(IndexBulkDeleteResult);
        btvacuumscan(info, stats, NULL, NULL, 0);
        stats->estimated_count = true;
    }
 
    /*
     * Maintain num_delpages value in metapage for _bt_vacuum_needs_cleanup().
     *
     * num_delpages is the number of deleted pages now in the index that were
     * not safe to place in the FSM to be recycled just yet.  num_delpages is
     * greater than 0 only when _bt_pagedel() actually deleted pages during
     * our call to btvacuumscan().  Even then, _bt_pendingfsm_finalize() must
     * have failed to place any newly deleted pages in the FSM just moments
     * ago.  (Actually, there are edge cases where recycling of the current
     * VACUUM's newly deleted pages does not even become safe by the time the
     * next VACUUM comes around.  See nbtree/README.)
     */
    Assert(stats->pages_deleted >= stats->pages_free);
    num_delpages = stats->pages_deleted - stats->pages_free;
    _bt_set_cleanup_info(info->index, num_delpages);
 
    /*
     * It's quite possible for us to be fooled by concurrent page splits into
     * double-counting some index tuples, so disbelieve any total that exceeds
     * the underlying heap's count ... if we know that accurately.  Otherwise
     * this might just make matters worse.
     */
    if (!info->estimated_count)
    {
        if (stats->num_index_tuples > info->num_heap_tuples)
            stats->num_index_tuples = info->num_heap_tuples;
    }
 
    return stats;
}

References _bt_set_cleanup_info(), _bt_vacuum_needs_cleanup(), IndexVacuumInfo::analyze_only, Assert, btvacuumscan(), IndexVacuumInfo::estimated_count, IndexBulkDeleteResult::estimated_count, fb(), IndexVacuumInfo::index, IndexVacuumInfo::num_heap_tuples, IndexBulkDeleteResult::num_index_tuples, IndexBulkDeleteResult::pages_deleted, IndexBulkDeleteResult::pages_free, and palloc0_object.

Referenced by bthandler().

btvacuumpage()

static BlockNumber btvacuumpage ( BTVacState *  vstate, Buffer  buf  )

static

Definition at line 1415 of file nbtree.c.

{
    IndexVacuumInfo *info = vstate->info;
    IndexBulkDeleteResult *stats = vstate->stats;
    IndexBulkDeleteCallback callback = vstate->callback;
    void       *callback_state = vstate->callback_state;
    Relation    rel = info->index;
    Relation    heaprel = info->heaprel;
    bool        attempt_pagedel;
    BlockNumber blkno,
                backtrack_to;
    BlockNumber scanblkno = BufferGetBlockNumber(buf);
    Page        page;
    BTPageOpaque opaque;
 
    blkno = scanblkno;
 
backtrack:
 
    attempt_pagedel = false;
    backtrack_to = P_NONE;
 
    _bt_lockbuf(rel, buf, BT_READ);
    page = BufferGetPage(buf);
    opaque = NULL;
    if (!PageIsNew(page))
    {
        _bt_checkpage(rel, buf);
        opaque = BTPageGetOpaque(page);
    }
 
    Assert(blkno <= scanblkno);
    if (blkno != scanblkno)
    {
        /*
         * We're backtracking.
         *
         * We followed a right link to a sibling leaf page (a page that
         * happens to be from a block located before scanblkno).  The only
         * case we want to do anything with is a live leaf page having the
         * current vacuum cycle ID.
         *
         * The page had better be in a state that's consistent with what we
         * expect.  Check for conditions that imply corruption in passing.  It
         * can't be half-dead because only an interrupted VACUUM process can
         * leave pages in that state, so we'd definitely have dealt with it
         * back when the page was the scanblkno page (half-dead pages are
         * always marked fully deleted by _bt_pagedel(), barring corruption).
         */
        if (!opaque || !P_ISLEAF(opaque) || P_ISHALFDEAD(opaque))
        {
            Assert(false);
            ereport(LOG,
                    (errcode(ERRCODE_INDEX_CORRUPTED),
                     errmsg_internal("right sibling %u of scanblkno %u unexpectedly in an inconsistent state in index \"%s\"",
                                     blkno, scanblkno, RelationGetRelationName(rel))));
            _bt_relbuf(rel, buf);
            return scanblkno;
        }
 
        /*
         * We may have already processed the page in an earlier call, when the
         * page was scanblkno.  This happens when the leaf page split occurred
         * after the scan began, but before the right sibling page became the
         * scanblkno.
         *
         * Page may also have been deleted by current btvacuumpage() call,
         * since _bt_pagedel() sometimes deletes the right sibling page of
         * scanblkno in passing (it does so after we decided where to
         * backtrack to).  We don't need to process this page as a deleted
         * page a second time now (in fact, it would be wrong to count it as a
         * deleted page in the bulk delete statistics a second time).
         */
        if (opaque->btpo_cycleid != vstate->cycleid || P_ISDELETED(opaque))
        {
            /* Done with current scanblkno (and all lower split pages) */
            _bt_relbuf(rel, buf);
            return scanblkno;
        }
    }
 
    if (!opaque || BTPageIsRecyclable(page, heaprel))
    {
        /* Okay to recycle this page (which could be leaf or internal) */
        RecordFreeIndexPage(rel, blkno);
        stats->pages_deleted++;
        stats->pages_free++;
    }
    else if (P_ISDELETED(opaque))
    {
        /*
         * Already deleted page (which could be leaf or internal).  Can't
         * recycle yet.
         */
        stats->pages_deleted++;
    }
    else if (P_ISHALFDEAD(opaque))
    {
        /* Half-dead leaf page (from interrupted VACUUM) -- finish deleting */
        attempt_pagedel = true;
 
        /*
         * _bt_pagedel() will increment both pages_newly_deleted and
         * pages_deleted stats in all cases (barring corruption)
         */
    }
    else if (P_ISLEAF(opaque))
    {
        OffsetNumber deletable[MaxIndexTuplesPerPage];
        int         ndeletable;
        BTVacuumPosting updatable[MaxIndexTuplesPerPage];
        int         nupdatable;
        OffsetNumber offnum,
                    minoff,
                    maxoff;
        int         nhtidsdead,
                    nhtidslive;
 
        /*
         * Trade in the initial read lock for a full cleanup lock on this
         * page.  We must get such a lock on every leaf page over the course
         * of the vacuum scan, whether or not it actually contains any
         * deletable tuples --- see nbtree/README.
         */
        _bt_upgradelockbufcleanup(rel, buf);
 
        /*
         * Check whether we need to backtrack to earlier pages.  What we are
         * concerned about is a page split that happened since we started the
         * vacuum scan.  If the split moved tuples on the right half of the
         * split (i.e. the tuples that sort high) to a block that we already
         * passed over, then we might have missed the tuples.  We need to
         * backtrack now.  (Must do this before possibly clearing btpo_cycleid
         * or deleting scanblkno page below!)
         */
        if (vstate->cycleid != 0 &&
            opaque->btpo_cycleid == vstate->cycleid &&
            !(opaque->btpo_flags & BTP_SPLIT_END) &&
            !P_RIGHTMOST(opaque) &&
            opaque->btpo_next < scanblkno)
            backtrack_to = opaque->btpo_next;
 
        ndeletable = 0;
        nupdatable = 0;
        minoff = P_FIRSTDATAKEY(opaque);
        maxoff = PageGetMaxOffsetNumber(page);
        nhtidsdead = 0;
        nhtidslive = 0;
        if (callback)
        {
            /* btbulkdelete callback tells us what to delete (or update) */
            for (offnum = minoff;
                 offnum <= maxoff;
                 offnum = OffsetNumberNext(offnum))
            {
                IndexTuple  itup;
 
                itup = (IndexTuple) PageGetItem(page,
                                                PageGetItemId(page, offnum));
 
                Assert(!BTreeTupleIsPivot(itup));
                if (!BTreeTupleIsPosting(itup))
                {
                    /* Regular tuple, standard table TID representation */
                    if (callback(&itup->t_tid, callback_state))
                    {
                        deletable[ndeletable++] = offnum;
                        nhtidsdead++;
                    }
                    else
                        nhtidslive++;
                }
                else
                {
                    BTVacuumPosting vacposting;
                    int         nremaining;
 
                    /* Posting list tuple */
                    vacposting = btreevacuumposting(vstate, itup, offnum,
                                                    &nremaining);
                    if (vacposting == NULL)
                    {
                        /*
                         * All table TIDs from the posting tuple remain, so no
                         * delete or update required
                         */
                        Assert(nremaining == BTreeTupleGetNPosting(itup));
                    }
                    else if (nremaining > 0)
                    {
 
                        /*
                         * Store metadata about posting list tuple in
                         * updatable array for entire page.  Existing tuple
                         * will be updated during the later call to
                         * _bt_delitems_vacuum().
                         */
                        Assert(nremaining < BTreeTupleGetNPosting(itup));
                        updatable[nupdatable++] = vacposting;
                        nhtidsdead += BTreeTupleGetNPosting(itup) - nremaining;
                    }
                    else
                    {
                        /*
                         * All table TIDs from the posting list must be
                         * deleted.  We'll delete the index tuple completely
                         * (no update required).
                         */
                        Assert(nremaining == 0);
                        deletable[ndeletable++] = offnum;
                        nhtidsdead += BTreeTupleGetNPosting(itup);
                        pfree(vacposting);
                    }
 
                    nhtidslive += nremaining;
                }
            }
        }
 
        /*
         * Apply any needed deletes or updates.  We issue just one
         * _bt_delitems_vacuum() call per page, so as to minimize WAL traffic.
         */
        if (ndeletable > 0 || nupdatable > 0)
        {
            Assert(nhtidsdead >= ndeletable + nupdatable);
            _bt_delitems_vacuum(rel, buf, deletable, ndeletable, updatable,
                                nupdatable);
 
            stats->tuples_removed += nhtidsdead;
            /* must recompute maxoff */
            maxoff = PageGetMaxOffsetNumber(page);
 
            /* can't leak memory here */
            for (int i = 0; i < nupdatable; i++)
                pfree(updatable[i]);
        }
        else
        {
            /*
             * If the leaf page has been split during this vacuum cycle, it
             * seems worth expending a write to clear btpo_cycleid even if we
             * don't have any deletions to do.  (If we do, _bt_delitems_vacuum
             * takes care of this.)  This ensures we won't process the page
             * again.
             *
             * We treat this like a hint-bit update because there's no need to
             * WAL-log it.
             */
            Assert(nhtidsdead == 0);
            if (vstate->cycleid != 0 &&
                opaque->btpo_cycleid == vstate->cycleid)
            {
                opaque->btpo_cycleid = 0;
                MarkBufferDirtyHint(buf, true);
            }
        }
 
        /*
         * If the leaf page is now empty, try to delete it; else count the
         * live tuples (live table TIDs in posting lists are counted as
         * separate live tuples).  We don't delete when backtracking, though,
         * since that would require teaching _bt_pagedel() about backtracking
         * (doesn't seem worth adding more complexity to deal with that).
         *
         * We don't count the number of live TIDs during cleanup-only calls to
         * btvacuumscan (i.e. when callback is not set).  We count the number
         * of index tuples directly instead.  This avoids the expense of
         * directly examining all of the tuples on each page.  VACUUM will
         * treat num_index_tuples as an estimate in cleanup-only case, so it
         * doesn't matter that this underestimates num_index_tuples
         * significantly in some cases.
         */
        if (minoff > maxoff)
            attempt_pagedel = (blkno == scanblkno);
        else if (callback)
            stats->num_index_tuples += nhtidslive;
        else
            stats->num_index_tuples += maxoff - minoff + 1;
 
        Assert(!attempt_pagedel || nhtidslive == 0);
    }
 
    if (attempt_pagedel)
    {
        MemoryContext oldcontext;
 
        /* Run pagedel in a temp context to avoid memory leakage */
        MemoryContextReset(vstate->pagedelcontext);
        oldcontext = MemoryContextSwitchTo(vstate->pagedelcontext);
 
        /*
         * _bt_pagedel maintains the bulk delete stats on our behalf;
         * pages_newly_deleted and pages_deleted are likely to be incremented
         * during call
         */
        Assert(blkno == scanblkno);
        _bt_pagedel(rel, buf, vstate);
 
        MemoryContextSwitchTo(oldcontext);
        /* pagedel released buffer, so we shouldn't */
    }
    else
        _bt_relbuf(rel, buf);
 
    if (backtrack_to != P_NONE)
    {
        blkno = backtrack_to;
 
        /* check for vacuum delay while not holding any buffer lock */
        vacuum_delay_point(false);
 
        /*
         * We can't use _bt_getbuf() here because it always applies
         * _bt_checkpage(), which will barf on an all-zero page. We want to
         * recycle all-zero pages, not fail.  Also, we want to use a
         * nondefault buffer access strategy.
         */
        buf = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_NORMAL,
                                 info->strategy);
        goto backtrack;
    }
 
    return scanblkno;
}

References _bt_checkpage(), _bt_delitems_vacuum(), _bt_lockbuf(), _bt_pagedel(), _bt_relbuf(), _bt_upgradelockbufcleanup(), Assert, BT_READ, BTP_SPLIT_END, BTPageGetOpaque, BTPageIsRecyclable(), BTPageOpaqueData::btpo_cycleid, BTPageOpaqueData::btpo_flags, BTPageOpaqueData::btpo_next, BTreeTupleGetNPosting(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), btreevacuumposting(), buf, BufferGetBlockNumber(), BufferGetPage(), callback(), ereport, errcode(), errmsg_internal(), fb(), IndexVacuumInfo::heaprel, i, IndexVacuumInfo::index, LOG, MAIN_FORKNUM, MarkBufferDirtyHint(), MaxIndexTuplesPerPage, MemoryContextReset(), MemoryContextSwitchTo(), IndexBulkDeleteResult::num_index_tuples, OffsetNumberNext, P_FIRSTDATAKEY, P_ISDELETED, P_ISHALFDEAD, P_ISLEAF, P_NONE, P_RIGHTMOST, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), PageIsNew(), IndexBulkDeleteResult::pages_deleted, IndexBulkDeleteResult::pages_free, pfree(), RBM_NORMAL, ReadBufferExtended(), RecordFreeIndexPage(), RelationGetRelationName, IndexVacuumInfo::strategy, IndexTupleData::t_tid, IndexBulkDeleteResult::tuples_removed, and vacuum_delay_point().

Referenced by btvacuumscan().

btvacuumscan()

static void btvacuumscan ( IndexVacuumInfo *  info, IndexBulkDeleteResult *  stats, IndexBulkDeleteCallback  callback, void *  callback_state, BTCycleId  cycleid  )

static

Definition at line 1240 of file nbtree.c.

{
    Relation    rel = info->index;
    BTVacState  vstate;
    BlockNumber num_pages;
    bool        needLock;
    BlockRangeReadStreamPrivate p;
    ReadStream *stream = NULL;
 
    /*
     * Reset fields that track information about the entire index now.  This
     * avoids double-counting in the case where a single VACUUM command
     * requires multiple scans of the index.
     *
     * Avoid resetting the tuples_removed and pages_newly_deleted fields here,
     * since they track information about the VACUUM command, and so must last
     * across each call to btvacuumscan().
     *
     * (Note that pages_free is treated as state about the whole index, not
     * the current VACUUM.  This is appropriate because RecordFreeIndexPage()
     * calls are idempotent, and get repeated for the same deleted pages in
     * some scenarios.  The point for us is to track the number of recyclable
     * pages in the index at the end of the VACUUM command.)
     */
    stats->num_pages = 0;
    stats->num_index_tuples = 0;
    stats->pages_deleted = 0;
    stats->pages_free = 0;
 
    /* Set up info to pass down to btvacuumpage */
    vstate.info = info;
    vstate.stats = stats;
    vstate.callback = callback;
    vstate.callback_state = callback_state;
    vstate.cycleid = cycleid;
 
    /* Create a temporary memory context to run _bt_pagedel in */
    vstate.pagedelcontext = AllocSetContextCreate(CurrentMemoryContext,
                                                  "_bt_pagedel",
                                                  ALLOCSET_DEFAULT_SIZES);
 
    /* Initialize vstate fields used by _bt_pendingfsm_finalize */
    vstate.bufsize = 0;
    vstate.maxbufsize = 0;
    vstate.pendingpages = NULL;
    vstate.npendingpages = 0;
    /* Consider applying _bt_pendingfsm_finalize optimization */
    _bt_pendingfsm_init(rel, &vstate, (callback == NULL));
 
    /*
     * The outer loop iterates over all index pages except the metapage, in
     * physical order (we hope the kernel will cooperate in providing
     * read-ahead for speed).  It is critical that we visit all leaf pages,
     * including ones added after we start the scan, else we might fail to
     * delete some deletable tuples.  Hence, we must repeatedly check the
     * relation length.  We must acquire the relation-extension lock while
     * doing so to avoid a race condition: if someone else is extending the
     * relation, there is a window where bufmgr/smgr have created a new
     * all-zero page but it hasn't yet been write-locked by _bt_getbuf(). If
     * we manage to scan such a page here, we'll improperly assume it can be
     * recycled.  Taking the lock synchronizes things enough to prevent a
     * problem: either num_pages won't include the new page, or _bt_getbuf
     * already has write lock on the buffer and it will be fully initialized
     * before we can examine it.  Also, we need not worry if a page is added
     * immediately after we look; the page splitting code already has
     * write-lock on the left page before it adds a right page, so we must
     * already have processed any tuples due to be moved into such a page.
     *
     * XXX: Now that new pages are locked with RBM_ZERO_AND_LOCK, I don't
     * think the use of the extension lock is still required.
     *
     * We can skip locking for new or temp relations, however, since no one
     * else could be accessing them.
     */
    needLock = !RELATION_IS_LOCAL(rel);
 
    p.current_blocknum = BTREE_METAPAGE + 1;
 
    /*
     * It is safe to use batchmode as block_range_read_stream_cb takes no
     * locks.
     */
    stream = read_stream_begin_relation(READ_STREAM_MAINTENANCE |
                                        READ_STREAM_FULL |
                                        READ_STREAM_USE_BATCHING,
                                        info->strategy,
                                        rel,
                                        MAIN_FORKNUM,
                                        block_range_read_stream_cb,
                                        &p,
                                        0);
    for (;;)
    {
        /* Get the current relation length */
        if (needLock)
            LockRelationForExtension(rel, ExclusiveLock);
        num_pages = RelationGetNumberOfBlocks(rel);
        if (needLock)
            UnlockRelationForExtension(rel, ExclusiveLock);
 
        if (info->report_progress)
            pgstat_progress_update_param(PROGRESS_SCAN_BLOCKS_TOTAL,
                                         num_pages);
 
        /* Quit if we've scanned the whole relation */
        if (p.current_blocknum >= num_pages)
            break;
 
        p.last_exclusive = num_pages;
 
        /* Iterate over pages, then loop back to recheck relation length */
        while (true)
        {
            BlockNumber current_block;
            Buffer      buf;
 
            /* call vacuum_delay_point while not holding any buffer lock */
            vacuum_delay_point(false);
 
            buf = read_stream_next_buffer(stream, NULL);
 
            if (!BufferIsValid(buf))
                break;
 
            current_block = btvacuumpage(&vstate, buf);
 
            if (info->report_progress)
                pgstat_progress_update_param(PROGRESS_SCAN_BLOCKS_DONE,
                                             current_block);
        }
 
        /*
         * We have to reset the read stream to use it again. After returning
         * InvalidBuffer, the read stream API won't invoke our callback again
         * until the stream has been reset.
         */
        read_stream_reset(stream);
    }
 
    read_stream_end(stream);
 
    /* Set statistics num_pages field to final size of index */
    stats->num_pages = num_pages;
 
    MemoryContextDelete(vstate.pagedelcontext);
 
    /*
     * If there were any calls to _bt_pagedel() during scan of the index then
     * see if any of the resulting pages can be placed in the FSM now.  When
     * it's not safe we'll have to leave it up to a future VACUUM operation.
     *
     * Finally, if we placed any pages in the FSM (either just now or during
     * the scan), forcibly update the upper-level FSM pages to ensure that
     * searchers can find them.
     */
    _bt_pendingfsm_finalize(rel, &vstate);
    if (stats->pages_free > 0)
        IndexFreeSpaceMapVacuum(rel);
}

References _bt_pendingfsm_finalize(), _bt_pendingfsm_init(), ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, block_range_read_stream_cb(), BTREE_METAPAGE, btvacuumpage(), buf, BufferIsValid(), callback(), BlockRangeReadStreamPrivate::current_blocknum, CurrentMemoryContext, ExclusiveLock, fb(), IndexVacuumInfo::index, IndexFreeSpaceMapVacuum(), BlockRangeReadStreamPrivate::last_exclusive, LockRelationForExtension(), MAIN_FORKNUM, MemoryContextDelete(), IndexBulkDeleteResult::num_index_tuples, IndexBulkDeleteResult::num_pages, IndexBulkDeleteResult::pages_deleted, IndexBulkDeleteResult::pages_free, pgstat_progress_update_param(), PROGRESS_SCAN_BLOCKS_DONE, PROGRESS_SCAN_BLOCKS_TOTAL, read_stream_begin_relation(), read_stream_end(), READ_STREAM_FULL, READ_STREAM_MAINTENANCE, read_stream_next_buffer(), read_stream_reset(), READ_STREAM_USE_BATCHING, RELATION_IS_LOCAL, RelationGetNumberOfBlocks, IndexVacuumInfo::report_progress, IndexVacuumInfo::strategy, UnlockRelationForExtension(), and vacuum_delay_point().

Referenced by btbulkdelete(), and btvacuumcleanup().