#include "access/amapi.h"
#include "access/itup.h"
#include "access/sdir.h"
#include "access/xlogreader.h"
#include "catalog/pg_index.h"
#include "lib/stringinfo.h"
#include "storage/bufmgr.h"
#include "storage/shm_toc.h"

Include dependency graph for nbtree.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	BTPageOpaqueData

struct	BTMetaPageData

struct	BTStackData

struct	BTScanPosItem

struct	BTScanPosData

struct	BTArrayKeyInfo

struct	BTScanOpaqueData

Macros
#define	BTP_LEAF (1 << 0) /* leaf page, i.e. not internal page */

#define	BTP_ROOT (1 << 1) /* root page (has no parent) */

#define	BTP_DELETED (1 << 2) /* page has been deleted from tree */

#define	BTP_META (1 << 3) /* meta-page */

#define	BTP_HALF_DEAD (1 << 4) /* empty, but still in tree */

#define	BTP_SPLIT_END (1 << 5) /* rightmost page of split group */

#define	BTP_HAS_GARBAGE (1 << 6) /* page has LP_DEAD tuples */

#define	BTP_INCOMPLETE_SPLIT (1 << 7) /* right sibling's downlink is missing */

#define	MAX_BT_CYCLE_ID 0xFF7F

#define	BTPageGetMeta(p) ((BTMetaPageData *) PageGetContents(p))

#define	BTREE_METAPAGE 0 /* first page is meta */

#define	BTREE_MAGIC 0x053162 /* magic number of btree pages */

#define	BTREE_VERSION 3 /* current version number */

#define	BTREE_MIN_VERSION 2 /* minimal supported version number */

#define	BTMaxItemSize(page)

#define	BTREE_MIN_FILLFACTOR 10

#define	BTREE_DEFAULT_FILLFACTOR 90

#define	BTREE_NONLEAF_FILLFACTOR 70

#define	P_NONE 0

#define	P_LEFTMOST(opaque) ((opaque)->btpo_prev == P_NONE)

#define	P_RIGHTMOST(opaque) ((opaque)->btpo_next == P_NONE)

#define	P_ISLEAF(opaque) (((opaque)->btpo_flags & BTP_LEAF) != 0)

#define	P_ISROOT(opaque) (((opaque)->btpo_flags & BTP_ROOT) != 0)

#define	P_ISDELETED(opaque) (((opaque)->btpo_flags & BTP_DELETED) != 0)

#define	P_ISMETA(opaque) (((opaque)->btpo_flags & BTP_META) != 0)

#define	P_ISHALFDEAD(opaque) (((opaque)->btpo_flags & BTP_HALF_DEAD) != 0)

#define	P_IGNORE(opaque) (((opaque)->btpo_flags & (BTP_DELETED\|BTP_HALF_DEAD)) != 0)

#define	P_HAS_GARBAGE(opaque) (((opaque)->btpo_flags & BTP_HAS_GARBAGE) != 0)

#define	P_INCOMPLETE_SPLIT(opaque) (((opaque)->btpo_flags & BTP_INCOMPLETE_SPLIT) != 0)

#define	P_HIKEY ((OffsetNumber) 1)

#define	P_FIRSTKEY ((OffsetNumber) 2)

#define	P_FIRSTDATAKEY(opaque) (P_RIGHTMOST(opaque) ? P_HIKEY : P_FIRSTKEY)

#define	INDEX_ALT_TID_MASK INDEX_AM_RESERVED_BIT

#define	BT_RESERVED_OFFSET_MASK 0xF000

#define	BT_N_KEYS_OFFSET_MASK 0x0FFF

#define	BTreeInnerTupleGetDownLink(itup) ItemPointerGetBlockNumberNoCheck(&((itup)->t_tid))

#define	BTreeInnerTupleSetDownLink(itup, blkno) ItemPointerSetBlockNumber(&((itup)->t_tid), (blkno))

#define	BTreeTupleGetTopParent(itup) ItemPointerGetBlockNumberNoCheck(&((itup)->t_tid))

#define	BTreeTupleSetTopParent(itup, blkno)

#define	BTreeTupleGetNAtts(itup, rel)

#define	BTreeTupleSetNAtts(itup, n)

#define	BTCommuteStrategyNumber(strat) (BTMaxStrategyNumber + 1 - (strat))

#define	BTORDER_PROC 1

#define	BTSORTSUPPORT_PROC 2

#define	BTINRANGE_PROC 3

#define	BTNProcs 3

#define	BT_READ BUFFER_LOCK_SHARE

#define	BT_WRITE BUFFER_LOCK_EXCLUSIVE

#define	BTScanPosIsPinned(scanpos)

#define	BTScanPosUnpin(scanpos)

#define	BTScanPosUnpinIfPinned(scanpos)

#define	BTScanPosIsValid(scanpos)

#define	BTScanPosInvalidate(scanpos)

#define	SK_BT_REQFWD 0x00010000 /* required to continue forward scan */

#define	SK_BT_REQBKWD 0x00020000 /* required to continue backward scan */

#define	SK_BT_INDOPTION_SHIFT 24 /* must clear the above bits */

#define	SK_BT_DESC (INDOPTION_DESC << SK_BT_INDOPTION_SHIFT)

#define	SK_BT_NULLS_FIRST (INDOPTION_NULLS_FIRST << SK_BT_INDOPTION_SHIFT)

Typedefs
typedef uint16	BTCycleId

typedef struct BTPageOpaqueData	BTPageOpaqueData

typedef BTPageOpaqueData *	BTPageOpaque

typedef struct BTMetaPageData	BTMetaPageData

typedef struct BTStackData	BTStackData

typedef BTStackData *	BTStack

typedef struct BTScanPosItem	BTScanPosItem

typedef struct BTScanPosData	BTScanPosData

typedef BTScanPosData *	BTScanPos

typedef struct BTArrayKeyInfo	BTArrayKeyInfo

typedef struct BTScanOpaqueData	BTScanOpaqueData

typedef BTScanOpaqueData *	BTScanOpaque

Functions
void	btbuildempty (Relation index)

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

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

Size	btestimateparallelscan (void)

void	btinitparallelscan (void *target)

bool	btgettuple (IndexScanDesc scan, ScanDirection dir)

int64	btgetbitmap (IndexScanDesc scan, TIDBitmap *tbm)

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

void	btparallelrescan (IndexScanDesc scan)

void	btendscan (IndexScanDesc scan)

void	btmarkpos (IndexScanDesc scan)

void	btrestrpos (IndexScanDesc scan)

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

IndexBulkDeleteResult *	btvacuumcleanup (IndexVacuumInfo info, IndexBulkDeleteResult stats)

bool	btcanreturn (Relation index, int attno)

bool	_bt_parallel_seize (IndexScanDesc scan, BlockNumber *pageno)

void	_bt_parallel_release (IndexScanDesc scan, BlockNumber scan_page)

void	_bt_parallel_done (IndexScanDesc scan)

void	_bt_parallel_advance_array_keys (IndexScanDesc scan)

bool	_bt_doinsert (Relation rel, IndexTuple itup, IndexUniqueCheck checkUnique, Relation heapRel)

Buffer	_bt_getstackbuf (Relation rel, BTStack stack, int access)

void	_bt_finish_split (Relation rel, Buffer bbuf, BTStack stack)

void	_bt_initmetapage (Page page, BlockNumber rootbknum, uint32 level)

void	_bt_update_meta_cleanup_info (Relation rel, TransactionId oldestBtpoXact, float8 numHeapTuples)

void	_bt_upgrademetapage (Page page)

Buffer	_bt_getroot (Relation rel, int access)

Buffer	_bt_gettrueroot (Relation rel)

int	_bt_getrootheight (Relation rel)

void	_bt_checkpage (Relation rel, Buffer buf)

Buffer	_bt_getbuf (Relation rel, BlockNumber blkno, int access)

Buffer	_bt_relandgetbuf (Relation rel, Buffer obuf, BlockNumber blkno, int access)

void	_bt_relbuf (Relation rel, Buffer buf)

void	_bt_pageinit (Page page, Size size)

bool	_bt_page_recyclable (Page page)

void	_bt_delitems_delete (Relation rel, Buffer buf, OffsetNumber *itemnos, int nitems, Relation heapRel)

void	_bt_delitems_vacuum (Relation rel, Buffer buf, OffsetNumber *itemnos, int nitems, BlockNumber lastBlockVacuumed)

int	_bt_pagedel (Relation rel, Buffer buf)

BTStack	_bt_search (Relation rel, int keysz, ScanKey scankey, bool nextkey, Buffer *bufP, int access, Snapshot snapshot)

Buffer	_bt_moveright (Relation rel, Buffer buf, int keysz, ScanKey scankey, bool nextkey, bool forupdate, BTStack stack, int access, Snapshot snapshot)

OffsetNumber	_bt_binsrch (Relation rel, Buffer buf, int keysz, ScanKey scankey, bool nextkey)

int32	_bt_compare (Relation rel, int keysz, ScanKey scankey, Page page, OffsetNumber offnum)

bool	_bt_first (IndexScanDesc scan, ScanDirection dir)

bool	_bt_next (IndexScanDesc scan, ScanDirection dir)

Buffer	_bt_get_endpoint (Relation rel, uint32 level, bool rightmost, Snapshot snapshot)

ScanKey	_bt_mkscankey (Relation rel, IndexTuple itup)

ScanKey	_bt_mkscankey_nodata (Relation rel)

void	_bt_freeskey (ScanKey skey)

void	_bt_freestack (BTStack stack)

void	_bt_preprocess_array_keys (IndexScanDesc scan)

void	_bt_start_array_keys (IndexScanDesc scan, ScanDirection dir)

bool	_bt_advance_array_keys (IndexScanDesc scan, ScanDirection dir)

void	_bt_mark_array_keys (IndexScanDesc scan)

void	_bt_restore_array_keys (IndexScanDesc scan)

void	_bt_preprocess_keys (IndexScanDesc scan)

IndexTuple	_bt_checkkeys (IndexScanDesc scan, Page page, OffsetNumber offnum, ScanDirection dir, bool *continuescan)

void	_bt_killitems (IndexScanDesc scan)

BTCycleId	_bt_vacuum_cycleid (Relation rel)

BTCycleId	_bt_start_vacuum (Relation rel)

void	_bt_end_vacuum (Relation rel)

void	_bt_end_vacuum_callback (int code, Datum arg)

Size	BTreeShmemSize (void)

void	BTreeShmemInit (void)

bytea *	btoptions (Datum reloptions, bool validate)

bool	btproperty (Oid index_oid, int attno, IndexAMProperty prop, const char propname, bool res, bool *isnull)

IndexTuple	_bt_nonkey_truncate (Relation rel, IndexTuple itup)

bool	_bt_check_natts (Relation rel, Page page, OffsetNumber offnum)

bool	btvalidate (Oid opclassoid)

IndexBuildResult *	btbuild (Relation heap, Relation index, struct IndexInfo *indexInfo)

void	_bt_parallel_build_main (dsm_segment seg, shm_toc toc)

Macro Definition Documentation

◆ BT_N_KEYS_OFFSET_MASK

#define BT_N_KEYS_OFFSET_MASK 0x0FFF

Definition at line 221 of file nbtree.h.

Referenced by _bt_check_natts().

◆ BT_READ

#define BT_READ BUFFER_LOCK_SHARE

◆ BT_RESERVED_OFFSET_MASK

#define BT_RESERVED_OFFSET_MASK 0xF000

Definition at line 220 of file nbtree.h.

◆ BT_WRITE

#define BT_WRITE BUFFER_LOCK_EXCLUSIVE

Definition at line 301 of file nbtree.h.

Referenced by _bt_doinsert(), _bt_findinsertloc(), _bt_finish_split(), _bt_getbuf(), _bt_getroot(), _bt_getstackbuf(), _bt_insert_parent(), _bt_insertonpg(), _bt_lock_branch_parent(), _bt_moveright(), _bt_newroot(), _bt_pagedel(), _bt_search(), _bt_split(), _bt_unlink_halfdead_page(), and _bt_update_meta_cleanup_info().

◆ BTCommuteStrategyNumber

#define BTCommuteStrategyNumber ( strat ) (BTMaxStrategyNumber + 1 - (strat))

Definition at line 271 of file nbtree.h.

Referenced by _bt_compare_scankey_args(), and _bt_fix_scankey_strategy().

◆ BTINRANGE_PROC

#define BTINRANGE_PROC 3

Definition at line 292 of file nbtree.h.

Referenced by assignProcTypes(), btvalidate(), and transformFrameOffset().

◆ BTMaxItemSize

#define BTMaxItemSize ( page )

Value:

MAXALIGN_DOWN((PageGetPageSize(page) - \
                   MAXALIGN(SizeOfPageHeaderData + 3*sizeof(ItemIdData)) - \
                   MAXALIGN(sizeof(BTPageOpaqueData))) / 3)

Definition at line 126 of file nbtree.h.

Referenced by _bt_buildadd(), and _bt_findinsertloc().

◆ BTNProcs

#define BTNProcs 3

Definition at line 293 of file nbtree.h.

Referenced by bthandler().

◆ BTORDER_PROC

#define BTORDER_PROC 1

Definition at line 290 of file nbtree.h.

Referenced by _bt_first(), _bt_mkscankey(), _bt_mkscankey_nodata(), _bt_sort_array_elements(), assignProcTypes(), btvalidate(), ExecIndexBuildScanKeys(), ExecInitExprRec(), FinishSortSupportFunction(), load_rangetype_info(), lookup_type_cache(), match_clause_to_partition_key(), MJExamineQuals(), and RelationBuildPartitionKey().

◆ BTP_DELETED

#define BTP_DELETED (1 << 2) /* page has been deleted from tree */

Definition at line 73 of file nbtree.h.

Referenced by _bt_unlink_halfdead_page(), and btree_xlog_unlink_page().

◆ BTP_HALF_DEAD

#define BTP_HALF_DEAD (1 << 4) /* empty, but still in tree */

Definition at line 75 of file nbtree.h.

Referenced by _bt_mark_page_halfdead(), _bt_unlink_halfdead_page(), btree_xlog_mark_page_halfdead(), and btree_xlog_unlink_page().

◆ BTP_HAS_GARBAGE

#define BTP_HAS_GARBAGE (1 << 6) /* page has LP_DEAD tuples */

Definition at line 77 of file nbtree.h.

Referenced by _bt_check_unique(), _bt_delitems_delete(), _bt_delitems_vacuum(), _bt_killitems(), _bt_split(), btree_mask(), btree_xlog_delete(), and btree_xlog_vacuum().

◆ BTP_INCOMPLETE_SPLIT

#define BTP_INCOMPLETE_SPLIT (1 << 7) /* right sibling's downlink is missing */

Definition at line 78 of file nbtree.h.

Referenced by _bt_clear_incomplete_split(), _bt_insertonpg(), _bt_newroot(), _bt_split(), and btree_xlog_split().

◆ BTP_LEAF

#define BTP_LEAF (1 << 0) /* leaf page, i.e. not internal page */

Definition at line 71 of file nbtree.h.

Referenced by _bt_blnewpage(), _bt_getroot(), btree_xlog_mark_page_halfdead(), btree_xlog_newroot(), btree_xlog_split(), and btree_xlog_unlink_page().

◆ BTP_META

#define BTP_META (1 << 3) /* meta-page */

Definition at line 74 of file nbtree.h.

Referenced by _bt_initmetapage(), _bt_restore_meta(), and _bt_upgrademetapage().

◆ BTP_ROOT

#define BTP_ROOT (1 << 1) /* root page (has no parent) */

Definition at line 72 of file nbtree.h.

Referenced by _bt_getroot(), _bt_newroot(), _bt_split(), _bt_uppershutdown(), and btree_xlog_newroot().

◆ BTP_SPLIT_END

#define BTP_SPLIT_END (1 << 5) /* rightmost page of split group */

Definition at line 76 of file nbtree.h.

Referenced by _bt_split(), btree_mask(), and btvacuumpage().

◆ BTPageGetMeta

#define BTPageGetMeta ( p ) ((BTMetaPageData *) PageGetContents(p))

Definition at line 112 of file nbtree.h.

Referenced by _bt_finish_split(), _bt_getroot(), _bt_getrootheight(), _bt_gettrueroot(), _bt_initmetapage(), _bt_insertonpg(), _bt_newroot(), _bt_restore_meta(), _bt_unlink_halfdead_page(), _bt_update_meta_cleanup_info(), _bt_upgrademetapage(), _bt_vacuum_needs_cleanup(), bt_check_every_level(), bt_metap(), palloc_btree_page(), and pgstatindex_impl().

◆ BTREE_DEFAULT_FILLFACTOR

#define BTREE_DEFAULT_FILLFACTOR 90

Definition at line 139 of file nbtree.h.

Referenced by _bt_findsplitloc(), and _bt_pagestate().

◆ BTREE_MAGIC

#define BTREE_MAGIC 0x053162 /* magic number of btree pages */

Definition at line 116 of file nbtree.h.

Referenced by _bt_getroot(), _bt_getrootheight(), _bt_gettrueroot(), _bt_initmetapage(), _bt_restore_meta(), and palloc_btree_page().

◆ BTREE_METAPAGE

#define BTREE_METAPAGE 0 /* first page is meta */

Definition at line 115 of file nbtree.h.

Referenced by _bt_finish_split(), _bt_getroot(), _bt_getrootheight(), _bt_gettrueroot(), _bt_insertonpg(), _bt_leafbuild(), _bt_newroot(), _bt_restore_meta(), _bt_unlink_halfdead_page(), _bt_update_meta_cleanup_info(), _bt_uppershutdown(), _bt_vacuum_needs_cleanup(), bt_check_every_level(), btbuildempty(), btvacuumscan(), palloc_btree_page(), and pgstat_relation().

◆ BTREE_MIN_FILLFACTOR

#define BTREE_MIN_FILLFACTOR 10

Definition at line 138 of file nbtree.h.

◆ BTREE_MIN_VERSION

#define BTREE_MIN_VERSION 2 /* minimal supported version number */

Definition at line 118 of file nbtree.h.

Referenced by _bt_cachemetadata(), _bt_getroot(), _bt_getrootheight(), _bt_gettrueroot(), _bt_upgrademetapage(), and palloc_btree_page().

◆ BTREE_NONLEAF_FILLFACTOR

#define BTREE_NONLEAF_FILLFACTOR 70

Definition at line 140 of file nbtree.h.

Referenced by _bt_findsplitloc(), and _bt_pagestate().

◆ BTREE_VERSION

#define BTREE_VERSION 3 /* current version number */

Definition at line 117 of file nbtree.h.

Referenced by _bt_cachemetadata(), _bt_getroot(), _bt_getrootheight(), _bt_gettrueroot(), _bt_initmetapage(), _bt_insertonpg(), _bt_newroot(), _bt_restore_meta(), _bt_unlink_halfdead_page(), _bt_update_meta_cleanup_info(), _bt_upgrademetapage(), _bt_vacuum_needs_cleanup(), bt_metap(), and palloc_btree_page().

◆ BTreeInnerTupleGetDownLink

#define BTreeInnerTupleGetDownLink ( itup ) ItemPointerGetBlockNumberNoCheck(&((itup)->t_tid))

Definition at line 224 of file nbtree.h.

Referenced by _bt_get_endpoint(), _bt_getstackbuf(), _bt_mark_page_halfdead(), _bt_search(), _bt_unlink_halfdead_page(), bt_check_level_from_leftmost(), bt_downlink_missing_check(), bt_target_page_check(), and btree_xlog_mark_page_halfdead().

◆ BTreeInnerTupleSetDownLink

#define BTreeInnerTupleSetDownLink	(	itup,
		blkno
	)	ItemPointerSetBlockNumber(&((itup)->t_tid), (blkno))

Definition at line 226 of file nbtree.h.

Referenced by _bt_buildadd(), _bt_insert_parent(), _bt_mark_page_halfdead(), _bt_newroot(), _bt_uppershutdown(), and btree_xlog_mark_page_halfdead().

◆ BTreeTupleGetNAtts

#define BTreeTupleGetNAtts	(	itup,
		rel
	)

Value:

( \
        (itup)->t_info & INDEX_ALT_TID_MASK ? \
        ( \
            AssertMacro((ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_RESERVED_OFFSET_MASK) == 0), \
            ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_N_KEYS_OFFSET_MASK \
        ) \
        : \
        IndexRelationGetNumberOfAttributes(rel) \
    )

Definition at line 247 of file nbtree.h.

Referenced by _bt_buildadd(), _bt_check_natts(), _bt_checkkeys(), _bt_insertonpg(), _bt_mkscankey(), _bt_newroot(), _bt_nonkey_truncate(), _bt_split(), _bt_uppershutdown(), and bt_target_page_check().

◆ BTreeTupleGetTopParent

#define BTreeTupleGetTopParent ( itup ) ItemPointerGetBlockNumberNoCheck(&((itup)->t_tid))

Definition at line 235 of file nbtree.h.

Referenced by _bt_unlink_halfdead_page(), and bt_downlink_missing_check().

◆ BTreeTupleSetNAtts

#define BTreeTupleSetNAtts	(	itup,
		n
	)

Value:

do { \
        (itup)->t_info |= INDEX_ALT_TID_MASK; \
        Assert(((n) & BT_RESERVED_OFFSET_MASK) == 0); \
        ItemPointerSetOffsetNumber(&(itup)->t_tid, (n) & BT_N_KEYS_OFFSET_MASK); \
    } while(0)

Definition at line 257 of file nbtree.h.

Referenced by _bt_buildadd(), _bt_newroot(), _bt_nonkey_truncate(), _bt_pgaddtup(), and _bt_sortaddtup().

◆ BTreeTupleSetTopParent

#define BTreeTupleSetTopParent	(	itup,
		blkno
	)

Value:

do { \
        ItemPointerSetBlockNumber(&((itup)->t_tid), (blkno)); \
        BTreeTupleSetNAtts((itup), 0); \
    } while(0)

Definition at line 237 of file nbtree.h.

Referenced by _bt_mark_page_halfdead(), _bt_unlink_halfdead_page(), btree_xlog_mark_page_halfdead(), and btree_xlog_unlink_page().

◆ BTScanPosInvalidate

#define BTScanPosInvalidate ( scanpos )

Value:

do { \
        (scanpos).currPage = InvalidBlockNumber; \
        (scanpos).nextPage = InvalidBlockNumber; \
        (scanpos).buf = InvalidBuffer; \
        (scanpos).lsn = InvalidXLogRecPtr; \
        (scanpos).nextTupleOffset = 0; \
    } while (0);

Definition at line 418 of file nbtree.h.

Referenced by _bt_endpoint(), _bt_first(), _bt_readnextpage(), _bt_steppage(), btbeginscan(), btmarkpos(), btrescan(), and btrestrpos().

◆ BTScanPosIsPinned

#define BTScanPosIsPinned ( scanpos )

Value:

( \
    AssertMacro(BlockNumberIsValid((scanpos).currPage) || \
                !BufferIsValid((scanpos).buf)), \
    BufferIsValid((scanpos).buf) \
)

Definition at line 395 of file nbtree.h.

Referenced by _bt_killitems(), _bt_readnextpage(), _bt_readpage(), _bt_steppage(), and btrestrpos().

◆ BTScanPosIsValid

#define BTScanPosIsValid ( scanpos )

Value:

( \
    AssertMacro(BlockNumberIsValid((scanpos).currPage) || \
                !BufferIsValid((scanpos).buf)), \
    BlockNumberIsValid((scanpos).currPage) \
)

Definition at line 412 of file nbtree.h.

Referenced by _bt_first(), _bt_killitems(), _bt_steppage(), btendscan(), btgettuple(), btmarkpos(), btrescan(), and btrestrpos().

◆ BTScanPosUnpin

#define BTScanPosUnpin ( scanpos )

Value:

do { \
        ReleaseBuffer((scanpos).buf); \
        (scanpos).buf = InvalidBuffer; \
    } while (0)

Definition at line 401 of file nbtree.h.

◆ BTScanPosUnpinIfPinned

#define BTScanPosUnpinIfPinned ( scanpos )

Value:

do { \
        if (BTScanPosIsPinned(scanpos)) \
            BTScanPosUnpin(scanpos); \
    } while (0)

Definition at line 406 of file nbtree.h.

Referenced by _bt_readnextpage(), _bt_steppage(), btendscan(), btmarkpos(), btrescan(), and btrestrpos().

◆ BTSORTSUPPORT_PROC

#define BTSORTSUPPORT_PROC 2

Definition at line 291 of file nbtree.h.

Referenced by assignProcTypes(), btvalidate(), FinishSortSupportFunction(), and MJExamineQuals().

◆ INDEX_ALT_TID_MASK

#define INDEX_ALT_TID_MASK INDEX_AM_RESERVED_BIT

Definition at line 219 of file nbtree.h.

Referenced by _bt_check_natts().

◆ MAX_BT_CYCLE_ID

#define MAX_BT_CYCLE_ID 0xFF7F

Definition at line 87 of file nbtree.h.

Referenced by _bt_start_vacuum().

◆ P_FIRSTDATAKEY

#define P_FIRSTDATAKEY ( opaque ) (P_RIGHTMOST(opaque) ? P_HIKEY : P_FIRSTKEY)

◆ P_FIRSTKEY

#define P_FIRSTKEY ((OffsetNumber) 2)

Definition at line 186 of file nbtree.h.

Referenced by _bt_buildadd(), _bt_newroot(), _bt_slideleft(), and _bt_sortaddtup().

◆ P_HAS_GARBAGE

#define P_HAS_GARBAGE ( opaque ) (((opaque)->btpo_flags & BTP_HAS_GARBAGE) != 0)

Definition at line 164 of file nbtree.h.

Referenced by _bt_findinsertloc(), and palloc_btree_page().

◆ P_HIKEY

#define P_HIKEY ((OffsetNumber) 1)

◆ P_IGNORE

#define P_IGNORE ( opaque ) (((opaque)->btpo_flags & (BTP_DELETED|BTP_HALF_DEAD)) != 0)

◆ P_INCOMPLETE_SPLIT

#define P_INCOMPLETE_SPLIT ( opaque ) (((opaque)->btpo_flags & BTP_INCOMPLETE_SPLIT) != 0)

Definition at line 165 of file nbtree.h.

Referenced by _bt_clear_incomplete_split(), _bt_doinsert(), _bt_findinsertloc(), _bt_finish_split(), _bt_getstackbuf(), _bt_insertonpg(), _bt_lock_branch_parent(), _bt_moveright(), _bt_newroot(), _bt_pagedel(), and bt_check_level_from_leftmost().

◆ P_ISDELETED

#define P_ISDELETED ( opaque ) (((opaque)->btpo_flags & BTP_DELETED) != 0)

Definition at line 160 of file nbtree.h.

Referenced by _bt_mark_page_halfdead(), _bt_page_recyclable(), _bt_pagedel(), _bt_unlink_halfdead_page(), _bt_walk_left(), bt_check_level_from_leftmost(), bt_downlink_check(), bt_downlink_missing_check(), bt_page_items(), bt_page_items_bytea(), btree_mask(), btvacuumpage(), GetBTPageStatistics(), palloc_btree_page(), and pgstatindex_impl().

◆ P_ISHALFDEAD

#define P_ISHALFDEAD ( opaque ) (((opaque)->btpo_flags & BTP_HALF_DEAD) != 0)

Definition at line 162 of file nbtree.h.

Referenced by _bt_is_page_halfdead(), _bt_mark_page_halfdead(), _bt_pagedel(), _bt_unlink_halfdead_page(), bt_downlink_missing_check(), btvacuumpage(), and palloc_btree_page().

◆ P_ISLEAF

#define P_ISLEAF ( opaque ) (((opaque)->btpo_flags & BTP_LEAF) != 0)

◆ P_ISMETA

#define P_ISMETA ( opaque ) (((opaque)->btpo_flags & BTP_META) != 0)

Definition at line 161 of file nbtree.h.

Referenced by _bt_getroot(), _bt_getrootheight(), _bt_gettrueroot(), bt_page_items_bytea(), and palloc_btree_page().

◆ P_ISROOT

#define P_ISROOT ( opaque ) (((opaque)->btpo_flags & BTP_ROOT) != 0)

Definition at line 159 of file nbtree.h.

Referenced by _bt_insertonpg(), _bt_lock_branch_parent(), _bt_mark_page_halfdead(), _bt_pagedel(), _bt_unlink_halfdead_page(), bt_check_level_from_leftmost(), bt_downlink_missing_check(), and GetBTPageStatistics().

◆ P_LEFTMOST

#define P_LEFTMOST ( opaque ) ((opaque)->btpo_prev == P_NONE)

Definition at line 156 of file nbtree.h.

Referenced by _bt_buildadd(), _bt_finish_split(), _bt_getroot(), _bt_insertonpg(), _bt_pagedel(), _bt_uppershutdown(), _bt_walk_left(), and bt_check_level_from_leftmost().

◆ P_NONE

#define P_NONE 0

◆ P_RIGHTMOST

#define P_RIGHTMOST ( opaque ) ((opaque)->btpo_next == P_NONE)

◆ SK_BT_DESC

#define SK_BT_DESC (INDOPTION_DESC << SK_BT_INDOPTION_SHIFT)

Definition at line 489 of file nbtree.h.

Referenced by _bt_check_rowcompare(), _bt_compare(), _bt_compare_scankey_args(), _bt_first(), _bt_fix_scankey_strategy(), _bt_load(), tuplesort_begin_cluster(), and tuplesort_begin_index_btree().

◆ SK_BT_INDOPTION_SHIFT

#define SK_BT_INDOPTION_SHIFT 24 /* must clear the above bits */

Definition at line 488 of file nbtree.h.

Referenced by _bt_fix_scankey_strategy(), _bt_mkscankey(), and _bt_mkscankey_nodata().

◆ SK_BT_NULLS_FIRST

#define SK_BT_NULLS_FIRST (INDOPTION_NULLS_FIRST << SK_BT_INDOPTION_SHIFT)

Definition at line 490 of file nbtree.h.

Referenced by _bt_check_rowcompare(), _bt_checkkeys(), _bt_compare(), _bt_compare_scankey_args(), _bt_first(), _bt_fix_scankey_strategy(), _bt_load(), tuplesort_begin_cluster(), and tuplesort_begin_index_btree().

◆ SK_BT_REQBKWD

#define SK_BT_REQBKWD 0x00020000 /* required to continue backward scan */

Definition at line 487 of file nbtree.h.

Referenced by _bt_check_rowcompare(), _bt_checkkeys(), and _bt_mark_scankey_required().

◆ SK_BT_REQFWD

#define SK_BT_REQFWD 0x00010000 /* required to continue forward scan */

Definition at line 486 of file nbtree.h.

Referenced by _bt_check_rowcompare(), _bt_checkkeys(), and _bt_mark_scankey_required().

Typedef Documentation

◆ BTArrayKeyInfo

typedef struct BTArrayKeyInfo BTArrayKeyInfo

◆ BTCycleId

typedef uint16 BTCycleId

Definition at line 27 of file nbtree.h.

◆ BTMetaPageData

typedef struct BTMetaPageData BTMetaPageData

◆ BTPageOpaque

typedef BTPageOpaqueData* BTPageOpaque

Definition at line 68 of file nbtree.h.

◆ BTPageOpaqueData

typedef struct BTPageOpaqueData BTPageOpaqueData

◆ BTScanOpaque

typedef BTScanOpaqueData* BTScanOpaque

Definition at line 479 of file nbtree.h.

◆ BTScanOpaqueData

typedef struct BTScanOpaqueData BTScanOpaqueData

◆ BTScanPos

typedef BTScanPosData* BTScanPos

Definition at line 393 of file nbtree.h.

◆ BTScanPosData

typedef struct BTScanPosData BTScanPosData

◆ BTScanPosItem

typedef struct BTScanPosItem BTScanPosItem

◆ BTStack

typedef BTStackData* BTStack

Definition at line 321 of file nbtree.h.

◆ BTStackData

typedef struct BTStackData BTStackData

Function Documentation

◆ _bt_advance_array_keys()

bool _bt_advance_array_keys	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 558 of file nbtutils.c.

References _bt_parallel_advance_array_keys(), BTScanOpaqueData::arrayKeyData, BTScanOpaqueData::arrayKeys, BTArrayKeyInfo::cur_elem, BTArrayKeyInfo::elem_values, i, BTArrayKeyInfo::num_elems, BTScanOpaqueData::numArrayKeys, IndexScanDescData::opaque, IndexScanDescData::parallel_scan, BTArrayKeyInfo::scan_key, ScanDirectionIsBackward, and ScanKeyData::sk_argument.

Referenced by btgetbitmap(), and btgettuple().

 {
     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     bool        found = false;
     int         i;
 
     /*
      * We must advance the last array key most quickly, since it will
      * correspond to the lowest-order index column among the available
      * qualifications. This is necessary to ensure correct ordering of output
      * when there are multiple array keys.
      */
     for (i = so->numArrayKeys - 1; i >= 0; i--)
     {
         BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
         ScanKey     skey = &so->arrayKeyData[curArrayKey->scan_key];
         int         cur_elem = curArrayKey->cur_elem;
         int         num_elems = curArrayKey->num_elems;
 
         if (ScanDirectionIsBackward(dir))
         {
             if (--cur_elem < 0)
             {
                 cur_elem = num_elems - 1;
                 found = false;  /* need to advance next array key */
             }
             else
                 found = true;
         }
         else
         {
             if (++cur_elem >= num_elems)
             {
                 cur_elem = 0;
                 found = false;  /* need to advance next array key */
             }
             else
                 found = true;
         }
 
         curArrayKey->cur_elem = cur_elem;
         skey->sk_argument = curArrayKey->elem_values[cur_elem];
         if (found)
             break;
     }
 
     /* advance parallel scan */
     if (scan->parallel_scan != NULL)
         _bt_parallel_advance_array_keys(scan);
 
     return found;
 }

◆ _bt_binsrch()

OffsetNumber _bt_binsrch	(	Relation	rel,
		Buffer	buf,
		int	keysz,
		ScanKey	scankey,
		bool	nextkey
	)

Definition at line 323 of file nbtsearch.c.

References _bt_compare(), Assert, BufferGetPage, OffsetNumberPrev, P_FIRSTDATAKEY, P_ISLEAF, PageGetMaxOffsetNumber, and PageGetSpecialPointer.

Referenced by _bt_doinsert(), _bt_findinsertloc(), _bt_first(), and _bt_search().

 {
     Page        page;
     BTPageOpaque opaque;
     OffsetNumber low,
                 high;
     int32       result,
                 cmpval;
 
     page = BufferGetPage(buf);
     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 
     low = P_FIRSTDATAKEY(opaque);
     high = PageGetMaxOffsetNumber(page);
 
     /*
      * If there are no keys on the page, return the first available slot. Note
      * this covers two cases: the page is really empty (no keys), or it
      * contains only a high key.  The latter case is possible after vacuuming.
      * This can never happen on an internal page, however, since they are
      * never empty (an internal page must have children).
      */
     if (high < low)
         return low;
 
     /*
      * Binary search to find the first key on the page >= scan key, or first
      * key > scankey when nextkey is true.
      *
      * For nextkey=false (cmpval=1), the loop invariant is: all slots before
      * 'low' are < scan key, all slots at or after 'high' are >= scan key.
      *
      * For nextkey=true (cmpval=0), the loop invariant is: all slots before
      * 'low' are <= scan key, all slots at or after 'high' are > scan key.
      *
      * We can fall out when high == low.
      */
     high++;                     /* establish the loop invariant for high */
 
     cmpval = nextkey ? 0 : 1;   /* select comparison value */
 
     while (high > low)
     {
         OffsetNumber mid = low + ((high - low) / 2);
 
         /* We have low <= mid < high, so mid points at a real slot */
 
         result = _bt_compare(rel, keysz, scankey, page, mid);
 
         if (result >= cmpval)
             low = mid + 1;
         else
             high = mid;
     }
 
     /*
      * At this point we have high == low, but be careful: they could point
      * past the last slot on the page.
      *
      * On a leaf page, we always return the first key >= scan key (resp. >
      * scan key), which could be the last slot + 1.
      */
     if (P_ISLEAF(opaque))
         return low;
 
     /*
      * On a non-leaf page, return the last key < scan key (resp. <= scan key).
      * There must be one if _bt_compare() is playing by the rules.
      */
     Assert(low > P_FIRSTDATAKEY(opaque));
 
     return OffsetNumberPrev(low);
 }

◆ _bt_check_natts()

bool _bt_check_natts	(	Relation	rel,
		Page	page,
		OffsetNumber	offnum
	)

Definition at line 2134 of file nbtutils.c.

References Assert, BT_N_KEYS_OFFSET_MASK, BTreeTupleGetNAtts, FirstOffsetNumber, INDEX_ALT_TID_MASK, INDEX_MAX_KEYS, IndexRelationGetNumberOfAttributes, IndexRelationGetNumberOfKeyAttributes, ItemPointerGetOffsetNumber, P_FIRSTDATAKEY, P_HIKEY, P_IGNORE, P_ISLEAF, P_RIGHTMOST, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, PageGetSpecialPointer, StaticAssertStmt, IndexTupleData::t_info, and IndexTupleData::t_tid.

Referenced by _bt_compare(), and bt_target_page_check().

 {
     int16       natts = IndexRelationGetNumberOfAttributes(rel);
     int16       nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
     BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
     IndexTuple  itup;
 
     /*
      * We cannot reliably test a deleted or half-deleted page, since they have
      * dummy high keys
      */
     if (P_IGNORE(opaque))
         return true;
 
     Assert(offnum >= FirstOffsetNumber &&
            offnum <= PageGetMaxOffsetNumber(page));
 
     /*
      * Mask allocated for number of keys in index tuple must be able to fit
      * maximum possible number of index attributes
      */
     StaticAssertStmt(BT_N_KEYS_OFFSET_MASK >= INDEX_MAX_KEYS,
                      "BT_N_KEYS_OFFSET_MASK can't fit INDEX_MAX_KEYS");
 
     itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
 
     if (P_ISLEAF(opaque))
     {
         if (offnum >= P_FIRSTDATAKEY(opaque))
         {
             /*
              * Leaf tuples that are not the page high key (non-pivot tuples)
              * should never be truncated
              */
             return BTreeTupleGetNAtts(itup, rel) == natts;
         }
         else
         {
             /*
              * Rightmost page doesn't contain a page high key, so tuple was
              * checked above as ordinary leaf tuple
              */
             Assert(!P_RIGHTMOST(opaque));
 
             /* Page high key tuple contains only key attributes */
             return BTreeTupleGetNAtts(itup, rel) == nkeyatts;
         }
     }
     else                        /* !P_ISLEAF(opaque) */
     {
         if (offnum == P_FIRSTDATAKEY(opaque))
         {
             /*
              * The first tuple on any internal page (possibly the first after
              * its high key) is its negative infinity tuple.  Negative
              * infinity tuples are always truncated to zero attributes.  They
              * are a particular kind of pivot tuple.
              *
              * The number of attributes won't be explicitly represented if the
              * negative infinity tuple was generated during a page split that
              * occurred with a version of Postgres before v11.  There must be
              * a problem when there is an explicit representation that is
              * non-zero, or when there is no explicit representation and the
              * tuple is evidently not a pre-pg_upgrade tuple.
              *
              * Prior to v11, downlinks always had P_HIKEY as their offset.
              * Use that to decide if the tuple is a pre-v11 tuple.
              */
             return BTreeTupleGetNAtts(itup, rel) == 0 ||
                 ((itup->t_info & INDEX_ALT_TID_MASK) == 0 &&
                  ItemPointerGetOffsetNumber(&(itup->t_tid)) == P_HIKEY);
         }
         else
         {
             /*
              * Tuple contains only key attributes despite on is it page high
              * key or not
              */
             return BTreeTupleGetNAtts(itup, rel) == nkeyatts;
         }
 
     }
 }

◆ _bt_checkkeys()

IndexTuple _bt_checkkeys	(	IndexScanDesc	scan,
		Page	page,
		OffsetNumber	offnum,
		ScanDirection	dir,
		bool *	continuescan
	)

Definition at line 1370 of file nbtutils.c.

References _bt_check_rowcompare(), Assert, BTreeTupleGetNAtts, DatumGetBool, FunctionCall2Coll(), IndexScanDescData::ignore_killed_tuples, index_getattr, IndexScanDescData::indexRelation, ItemIdIsDead, BTScanOpaqueData::keyData, BTScanOpaqueData::numberOfKeys, IndexScanDescData::opaque, P_FIRSTDATAKEY, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, PageGetSpecialPointer, RelationGetDescr, ScanDirectionIsBackward, ScanDirectionIsForward, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_NULLS_FIRST, SK_BT_REQBKWD, SK_BT_REQFWD, ScanKeyData::sk_collation, ScanKeyData::sk_flags, ScanKeyData::sk_func, SK_ISNULL, SK_ROW_HEADER, SK_SEARCHNOTNULL, SK_SEARCHNULL, and test().

Referenced by _bt_readpage().

 {
     ItemId      iid = PageGetItemId(page, offnum);
     bool        tuple_alive;
     IndexTuple  tuple;
     TupleDesc   tupdesc;
     BTScanOpaque so;
     int         keysz;
     int         ikey;
     ScanKey     key;
 
     *continuescan = true;       /* default assumption */
 
     /*
      * If the scan specifies not to return killed tuples, then we treat a
      * killed tuple as not passing the qual.  Most of the time, it's a win to
      * not bother examining the tuple's index keys, but just return
      * immediately with continuescan = true to proceed to the next tuple.
      * However, if this is the last tuple on the page, we should check the
      * index keys to prevent uselessly advancing to the next page.
      */
     if (scan->ignore_killed_tuples && ItemIdIsDead(iid))
     {
         /* return immediately if there are more tuples on the page */
         if (ScanDirectionIsForward(dir))
         {
             if (offnum < PageGetMaxOffsetNumber(page))
                 return NULL;
         }
         else
         {
             BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 
             if (offnum > P_FIRSTDATAKEY(opaque))
                 return NULL;
         }
 
         /*
          * OK, we want to check the keys so we can set continuescan correctly,
          * but we'll return NULL even if the tuple passes the key tests.
          */
         tuple_alive = false;
     }
     else
         tuple_alive = true;
 
     tuple = (IndexTuple) PageGetItem(page, iid);
 
     tupdesc = RelationGetDescr(scan->indexRelation);
     so = (BTScanOpaque) scan->opaque;
     keysz = so->numberOfKeys;
 
     for (key = so->keyData, ikey = 0; ikey < keysz; key++, ikey++)
     {
         Datum       datum;
         bool        isNull;
         Datum       test;
 
         Assert(key->sk_attno <= BTreeTupleGetNAtts(tuple, scan->indexRelation));
         /* row-comparison keys need special processing */
         if (key->sk_flags & SK_ROW_HEADER)
         {
             if (_bt_check_rowcompare(key, tuple, tupdesc, dir, continuescan))
                 continue;
             return NULL;
         }
 
         datum = index_getattr(tuple,
                               key->sk_attno,
                               tupdesc,
                               &isNull);
 
         if (key->sk_flags & SK_ISNULL)
         {
             /* Handle IS NULL/NOT NULL tests */
             if (key->sk_flags & SK_SEARCHNULL)
             {
                 if (isNull)
                     continue;   /* tuple satisfies this qual */
             }
             else
             {
                 Assert(key->sk_flags & SK_SEARCHNOTNULL);
                 if (!isNull)
                     continue;   /* tuple satisfies this qual */
             }
 
             /*
              * Tuple fails this qual.  If it's a required qual for the current
              * scan direction, then we can conclude no further tuples will
              * pass, either.
              */
             if ((key->sk_flags & SK_BT_REQFWD) &&
                 ScanDirectionIsForward(dir))
                 *continuescan = false;
             else if ((key->sk_flags & SK_BT_REQBKWD) &&
                      ScanDirectionIsBackward(dir))
                 *continuescan = false;
 
             /*
              * In any case, this indextuple doesn't match the qual.
              */
             return NULL;
         }
 
         if (isNull)
         {
             if (key->sk_flags & SK_BT_NULLS_FIRST)
             {
                 /*
                  * Since NULLs are sorted before non-NULLs, we know we have
                  * reached the lower limit of the range of values for this
                  * index attr.  On a backward scan, we can stop if this qual
                  * is one of the "must match" subset.  We can stop regardless
                  * of whether the qual is > or <, so long as it's required,
                  * because it's not possible for any future tuples to pass. On
                  * a forward scan, however, we must keep going, because we may
                  * have initially positioned to the start of the index.
                  */
                 if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
                     ScanDirectionIsBackward(dir))
                     *continuescan = false;
             }
             else
             {
                 /*
                  * Since NULLs are sorted after non-NULLs, we know we have
                  * reached the upper limit of the range of values for this
                  * index attr.  On a forward scan, we can stop if this qual is
                  * one of the "must match" subset.  We can stop regardless of
                  * whether the qual is > or <, so long as it's required,
                  * because it's not possible for any future tuples to pass. On
                  * a backward scan, however, we must keep going, because we
                  * may have initially positioned to the end of the index.
                  */
                 if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
                     ScanDirectionIsForward(dir))
                     *continuescan = false;
             }
 
             /*
              * In any case, this indextuple doesn't match the qual.
              */
             return NULL;
         }
 
         test = FunctionCall2Coll(&key->sk_func, key->sk_collation,
                                  datum, key->sk_argument);
 
         if (!DatumGetBool(test))
         {
             /*
              * Tuple fails this qual.  If it's a required qual for the current
              * scan direction, then we can conclude no further tuples will
              * pass, either.
              *
              * Note: because we stop the scan as soon as any required equality
              * qual fails, it is critical that equality quals be used for the
              * initial positioning in _bt_first() when they are available. See
              * comments in _bt_first().
              */
             if ((key->sk_flags & SK_BT_REQFWD) &&
                 ScanDirectionIsForward(dir))
                 *continuescan = false;
             else if ((key->sk_flags & SK_BT_REQBKWD) &&
                      ScanDirectionIsBackward(dir))
                 *continuescan = false;
 
             /*
              * In any case, this indextuple doesn't match the qual.
              */
             return NULL;
         }
     }
 
     /* Check for failure due to it being a killed tuple. */
     if (!tuple_alive)
         return NULL;
 
     /* If we get here, the tuple passes all index quals. */
     return tuple;
 }

◆ _bt_checkpage()

void _bt_checkpage	(	Relation	rel,
		Buffer	buf
	)

Definition at line 662 of file nbtpage.c.

References BufferGetBlockNumber(), BufferGetPage, ereport, errcode(), errhint(), errmsg(), ERROR, MAXALIGN, PageGetSpecialSize, PageIsNew, and RelationGetRelationName.

Referenced by _bt_doinsert(), _bt_getbuf(), _bt_relandgetbuf(), btvacuumpage(), btvacuumscan(), and palloc_btree_page().

 {
     Page        page = BufferGetPage(buf);
 
     /*
      * ReadBuffer verifies that every newly-read page passes
      * PageHeaderIsValid, which means it either contains a reasonably sane
      * page header or is all-zero.  We have to defend against the all-zero
      * case, however.
      */
     if (PageIsNew(page))
         ereport(ERROR,
                 (errcode(ERRCODE_INDEX_CORRUPTED),
                  errmsg("index \"%s\" contains unexpected zero page at block %u",
                         RelationGetRelationName(rel),
                         BufferGetBlockNumber(buf)),
                  errhint("Please REINDEX it.")));
 
     /*
      * Additionally check that the special area looks sane.
      */
     if (PageGetSpecialSize(page) != MAXALIGN(sizeof(BTPageOpaqueData)))
         ereport(ERROR,
                 (errcode(ERRCODE_INDEX_CORRUPTED),
                  errmsg("index \"%s\" contains corrupted page at block %u",
                         RelationGetRelationName(rel),
                         BufferGetBlockNumber(buf)),
                  errhint("Please REINDEX it.")));
 }

◆ _bt_compare()

int32 _bt_compare	(	Relation	rel,
		int	keysz,
		ScanKey	scankey,
		Page	page,
		OffsetNumber	offnum
	)

Definition at line 428 of file nbtsearch.c.

References _bt_check_natts(), Assert, DatumGetInt32, FunctionCall2Coll(), i, index_getattr, P_FIRSTDATAKEY, P_ISLEAF, PageGetItem, PageGetItemId, PageGetSpecialPointer, RelationGetDescr, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, ScanKeyData::sk_func, and SK_ISNULL.

Referenced by _bt_binsrch(), _bt_doinsert(), _bt_findinsertloc(), _bt_moveright(), invariant_geq_offset(), invariant_leq_nontarget_offset(), and invariant_leq_offset().

 {
     TupleDesc   itupdesc = RelationGetDescr(rel);
     BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
     IndexTuple  itup;
     int         i;
 
     Assert(_bt_check_natts(rel, page, offnum));
 
     /*
      * Force result ">" if target item is first data item on an internal page
      * --- see NOTE above.
      */
     if (!P_ISLEAF(opaque) && offnum == P_FIRSTDATAKEY(opaque))
         return 1;
 
     itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
 
     /*
      * The scan key is set up with the attribute number associated with each
      * term in the key.  It is important that, if the index is multi-key, the
      * scan contain the first k key attributes, and that they be in order.  If
      * you think about how multi-key ordering works, you'll understand why
      * this is.
      *
      * We don't test for violation of this condition here, however.  The
      * initial setup for the index scan had better have gotten it right (see
      * _bt_first).
      */
 
     for (i = 1; i <= keysz; i++)
     {
         Datum       datum;
         bool        isNull;
         int32       result;
 
         datum = index_getattr(itup, scankey->sk_attno, itupdesc, &isNull);
 
         /* see comments about NULLs handling in btbuild */
         if (scankey->sk_flags & SK_ISNULL)  /* key is NULL */
         {
             if (isNull)
                 result = 0;     /* NULL "=" NULL */
             else if (scankey->sk_flags & SK_BT_NULLS_FIRST)
                 result = -1;    /* NULL "<" NOT_NULL */
             else
                 result = 1;     /* NULL ">" NOT_NULL */
         }
         else if (isNull)        /* key is NOT_NULL and item is NULL */
         {
             if (scankey->sk_flags & SK_BT_NULLS_FIRST)
                 result = 1;     /* NOT_NULL ">" NULL */
             else
                 result = -1;    /* NOT_NULL "<" NULL */
         }
         else
         {
             /*
              * The sk_func needs to be passed the index value as left arg and
              * the sk_argument as right arg (they might be of different
              * types).  Since it is convenient for callers to think of
              * _bt_compare as comparing the scankey to the index item, we have
              * to flip the sign of the comparison result.  (Unless it's a DESC
              * column, in which case we *don't* flip the sign.)
              */
             result = DatumGetInt32(FunctionCall2Coll(&scankey->sk_func,
                                                      scankey->sk_collation,
                                                      datum,
                                                      scankey->sk_argument));
 
             if (!(scankey->sk_flags & SK_BT_DESC))
                 result = -result;
         }
 
         /* if the keys are unequal, return the difference */
         if (result != 0)
             return result;
 
         scankey++;
     }
 
     /* if we get here, the keys are equal */
     return 0;
 }

◆ _bt_delitems_delete()

void _bt_delitems_delete	(	Relation	rel,
		Buffer	buf,
		OffsetNumber *	itemnos,
		int	nitems,
		Relation	heapRel
	)

Definition at line 1021 of file nbtpage.c.

References Assert, BTP_HAS_GARBAGE, BTPageOpaqueData::btpo_flags, BufferGetPage, END_CRIT_SECTION, xl_btree_delete::hnode, MarkBufferDirty(), xl_btree_delete::nitems, PageGetSpecialPointer, PageIndexMultiDelete(), PageSetLSN, RelationData::rd_node, REGBUF_STANDARD, RelationNeedsWAL, SizeOfBtreeDelete, START_CRIT_SECTION, XLOG_BTREE_DELETE, XLogBeginInsert(), XLogInsert(), XLogRegisterBuffer(), and XLogRegisterData().

Referenced by _bt_vacuum_one_page().

 {
     Page        page = BufferGetPage(buf);
     BTPageOpaque opaque;
 
     /* Shouldn't be called unless there's something to do */
     Assert(nitems > 0);
 
     /* No ereport(ERROR) until changes are logged */
     START_CRIT_SECTION();
 
     /* Fix the page */
     PageIndexMultiDelete(page, itemnos, nitems);
 
     /*
      * Unlike _bt_delitems_vacuum, we *must not* clear the vacuum cycle ID,
      * because this is not called by VACUUM.
      */
 
     /*
      * Mark the page as not containing any LP_DEAD items.  This is not
      * certainly true (there might be some that have recently been marked, but
      * weren't included in our target-item list), but it will almost always be
      * true and it doesn't seem worth an additional page scan to check it.
      * Remember that BTP_HAS_GARBAGE is only a hint anyway.
      */
     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
     opaque->btpo_flags &= ~BTP_HAS_GARBAGE;
 
     MarkBufferDirty(buf);
 
     /* XLOG stuff */
     if (RelationNeedsWAL(rel))
     {
         XLogRecPtr  recptr;
         xl_btree_delete xlrec_delete;
 
         xlrec_delete.hnode = heapRel->rd_node;
         xlrec_delete.nitems = nitems;
 
         XLogBeginInsert();
         XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
         XLogRegisterData((char *) &xlrec_delete, SizeOfBtreeDelete);
 
         /*
          * We need the target-offsets array whether or not we store the whole
          * buffer, to allow us to find the latestRemovedXid on a standby
          * server.
          */
         XLogRegisterData((char *) itemnos, nitems * sizeof(OffsetNumber));
 
         recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_DELETE);
 
         PageSetLSN(page, recptr);
     }
 
     END_CRIT_SECTION();
 }

◆ _bt_delitems_vacuum()

void _bt_delitems_vacuum	(	Relation	rel,
		Buffer	buf,
		OffsetNumber *	itemnos,
		int	nitems,
		BlockNumber	lastBlockVacuumed
	)

Definition at line 948 of file nbtpage.c.

References BTP_HAS_GARBAGE, BTPageOpaqueData::btpo_cycleid, BTPageOpaqueData::btpo_flags, BufferGetPage, END_CRIT_SECTION, xl_btree_vacuum::lastBlockVacuumed, MarkBufferDirty(), PageGetSpecialPointer, PageIndexMultiDelete(), PageSetLSN, REGBUF_STANDARD, RelationNeedsWAL, SizeOfBtreeVacuum, START_CRIT_SECTION, XLOG_BTREE_VACUUM, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().

Referenced by btvacuumpage(), and btvacuumscan().

 {
     Page        page = BufferGetPage(buf);
     BTPageOpaque opaque;
 
     /* No ereport(ERROR) until changes are logged */
     START_CRIT_SECTION();
 
     /* Fix the page */
     if (nitems > 0)
         PageIndexMultiDelete(page, itemnos, nitems);
 
     /*
      * We can clear the vacuum cycle ID since this page has certainly been
      * processed by the current vacuum scan.
      */
     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
     opaque->btpo_cycleid = 0;
 
     /*
      * Mark the page as not containing any LP_DEAD items.  This is not
      * certainly true (there might be some that have recently been marked, but
      * weren't included in our target-item list), but it will almost always be
      * true and it doesn't seem worth an additional page scan to check it.
      * Remember that BTP_HAS_GARBAGE is only a hint anyway.
      */
     opaque->btpo_flags &= ~BTP_HAS_GARBAGE;
 
     MarkBufferDirty(buf);
 
     /* XLOG stuff */
     if (RelationNeedsWAL(rel))
     {
         XLogRecPtr  recptr;
         xl_btree_vacuum xlrec_vacuum;
 
         xlrec_vacuum.lastBlockVacuumed = lastBlockVacuumed;
 
         XLogBeginInsert();
         XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
         XLogRegisterData((char *) &xlrec_vacuum, SizeOfBtreeVacuum);
 
         /*
          * The target-offsets array is not in the buffer, but pretend that it
          * is.  When XLogInsert stores the whole buffer, the offsets array
          * need not be stored too.
          */
         if (nitems > 0)
             XLogRegisterBufData(0, (char *) itemnos, nitems * sizeof(OffsetNumber));
 
         recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_VACUUM);
 
         PageSetLSN(page, recptr);
     }
 
     END_CRIT_SECTION();
 }

◆ _bt_doinsert()

bool _bt_doinsert	(	Relation	rel,
		IndexTuple	itup,
		IndexUniqueCheck	checkUnique,
		Relation	heapRel
	)

Definition at line 110 of file nbtinsert.c.

References _bt_binsrch(), _bt_check_unique(), _bt_checkpage(), _bt_compare(), _bt_findinsertloc(), _bt_freeskey(), _bt_freestack(), _bt_insertonpg(), _bt_mkscankey(), _bt_moveright(), _bt_relbuf(), _bt_search(), Assert, BT_WRITE, buf, BUFFER_LOCK_UNLOCK, BufferGetPage, CheckForSerializableConflictIn(), ConditionalLockBuffer(), IndexRelationGetNumberOfKeyAttributes, IndexTupleSize, InvalidBlockNumber, InvalidBuffer, InvalidOffsetNumber, LockBuffer(), MAXALIGN, P_FIRSTDATAKEY, P_IGNORE, P_INCOMPLETE_SPLIT, P_ISLEAF, P_RIGHTMOST, PageGetFreeSpace(), PageGetMaxOffsetNumber, PageGetSpecialPointer, ReadBuffer(), RelationGetTargetBlock, RelationSetTargetBlock, ReleaseBuffer(), SpeculativeInsertionWait(), IndexTupleData::t_tid, TransactionIdIsValid, UNIQUE_CHECK_EXISTING, UNIQUE_CHECK_NO, XactLockTableWait(), and XLTW_InsertIndex.

Referenced by btinsert().

 {
     bool        is_unique = false;
     int         indnkeyatts;
     ScanKey     itup_scankey;
     BTStack     stack = NULL;
     Buffer      buf;
     OffsetNumber offset;
     bool        fastpath;
 
     indnkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
     Assert(indnkeyatts != 0);
 
     /* we need an insertion scan key to do our search, so build one */
     itup_scankey = _bt_mkscankey(rel, itup);
 
     /*
      * It's very common to have an index on an auto-incremented or
      * monotonically increasing value. In such cases, every insertion happens
      * towards the end of the index. We try to optimize that case by caching
      * the right-most leaf of the index. If our cached block is still the
      * rightmost leaf, has enough free space to accommodate a new entry and
      * the insertion key is strictly greater than the first key in this page,
      * then we can safely conclude that the new key will be inserted in the
      * cached block. So we simply search within the cached block and insert
      * the key at the appropriate location. We call it a fastpath.
      *
      * Testing has revealed, though, that the fastpath can result in increased
      * contention on the exclusive-lock on the rightmost leaf page. So we
      * conditionally check if the lock is available. If it's not available
      * then we simply abandon the fastpath and take the regular path. This
      * makes sense because unavailability of the lock also signals that some
      * other backend might be concurrently inserting into the page, thus
      * reducing our chances to finding an insertion place in this page.
      */
 top:
     fastpath = false;
     offset = InvalidOffsetNumber;
     if (RelationGetTargetBlock(rel) != InvalidBlockNumber)
     {
         Size        itemsz;
         Page        page;
         BTPageOpaque lpageop;
 
         /*
          * Conditionally acquire exclusive lock on the buffer before doing any
          * checks. If we don't get the lock, we simply follow slowpath. If we
          * do get the lock, this ensures that the index state cannot change,
          * as far as the rightmost part of the index is concerned.
          */
         buf = ReadBuffer(rel, RelationGetTargetBlock(rel));
 
         if (ConditionalLockBuffer(buf))
         {
             _bt_checkpage(rel, buf);
 
             page = BufferGetPage(buf);
 
             lpageop = (BTPageOpaque) PageGetSpecialPointer(page);
             itemsz = IndexTupleSize(itup);
             itemsz = MAXALIGN(itemsz);  /* be safe, PageAddItem will do this
                                          * but we need to be consistent */
 
             /*
              * Check if the page is still the rightmost leaf page, has enough
              * free space to accommodate the new tuple, and the insertion scan
              * key is strictly greater than the first key on the page.
              */
             if (P_ISLEAF(lpageop) && P_RIGHTMOST(lpageop) &&
                 !P_IGNORE(lpageop) &&
                 (PageGetFreeSpace(page) > itemsz) &&
                 PageGetMaxOffsetNumber(page) >= P_FIRSTDATAKEY(lpageop) &&
                 _bt_compare(rel, indnkeyatts, itup_scankey, page,
                             P_FIRSTDATAKEY(lpageop)) > 0)
             {
                 /*
                  * The right-most block should never have an incomplete split.
                  * But be paranoid and check for it anyway.
                  */
                 Assert(!P_INCOMPLETE_SPLIT(lpageop));
                 fastpath = true;
             }
             else
             {
                 _bt_relbuf(rel, buf);
 
                 /*
                  * Something did not work out. Just forget about the cached
                  * block and follow the normal path. It might be set again if
                  * the conditions are favourable.
                  */
                 RelationSetTargetBlock(rel, InvalidBlockNumber);
             }
         }
         else
         {
             ReleaseBuffer(buf);
 
             /*
              * If someone's holding a lock, it's likely to change anyway, so
              * don't try again until we get an updated rightmost leaf.
              */
             RelationSetTargetBlock(rel, InvalidBlockNumber);
         }
     }
 
     if (!fastpath)
     {
         /* find the first page containing this key */
         stack = _bt_search(rel, indnkeyatts, itup_scankey, false, &buf, BT_WRITE,
                            NULL);
 
         /* trade in our read lock for a write lock */
         LockBuffer(buf, BUFFER_LOCK_UNLOCK);
         LockBuffer(buf, BT_WRITE);
 
         /*
          * If the page was split between the time that we surrendered our read
          * lock and acquired our write lock, then this page may no longer be
          * the right place for the key we want to insert.  In this case, we
          * need to move right in the tree.  See Lehman and Yao for an
          * excruciatingly precise description.
          */
         buf = _bt_moveright(rel, buf, indnkeyatts, itup_scankey, false,
                             true, stack, BT_WRITE, NULL);
     }
 
     /*
      * If we're not allowing duplicates, make sure the key isn't already in
      * the index.
      *
      * NOTE: obviously, _bt_check_unique can only detect keys that are already
      * in the index; so it cannot defend against concurrent insertions of the
      * same key.  We protect against that by means of holding a write lock on
      * the target page.  Any other would-be inserter of the same key must
      * acquire a write lock on the same target page, so only one would-be
      * inserter can be making the check at one time.  Furthermore, once we are
      * past the check we hold write locks continuously until we have performed
      * our insertion, so no later inserter can fail to see our insertion.
      * (This requires some care in _bt_insertonpg.)
      *
      * If we must wait for another xact, we release the lock while waiting,
      * and then must start over completely.
      *
      * For a partial uniqueness check, we don't wait for the other xact. Just
      * let the tuple in and return false for possibly non-unique, or true for
      * definitely unique.
      */
     if (checkUnique != UNIQUE_CHECK_NO)
     {
         TransactionId xwait;
         uint32      speculativeToken;
 
         offset = _bt_binsrch(rel, buf, indnkeyatts, itup_scankey, false);
         xwait = _bt_check_unique(rel, itup, heapRel, buf, offset, itup_scankey,
                                  checkUnique, &is_unique, &speculativeToken);
 
         if (TransactionIdIsValid(xwait))
         {
             /* Have to wait for the other guy ... */
             _bt_relbuf(rel, buf);
 
             /*
              * If it's a speculative insertion, wait for it to finish (ie. to
              * go ahead with the insertion, or kill the tuple).  Otherwise
              * wait for the transaction to finish as usual.
              */
             if (speculativeToken)
                 SpeculativeInsertionWait(xwait, speculativeToken);
             else
                 XactLockTableWait(xwait, rel, &itup->t_tid, XLTW_InsertIndex);
 
             /* start over... */
             if (stack)
                 _bt_freestack(stack);
             goto top;
         }
     }
 
     if (checkUnique != UNIQUE_CHECK_EXISTING)
     {
         /*
          * The only conflict predicate locking cares about for indexes is when
          * an index tuple insert conflicts with an existing lock.  Since the
          * actual location of the insert is hard to predict because of the
          * random search used to prevent O(N^2) performance when there are
          * many duplicate entries, we can just use the "first valid" page.
          * This reasoning also applies to INCLUDE indexes, whose extra
          * attributes are not considered part of the key space.
          */
         CheckForSerializableConflictIn(rel, NULL, buf);
         /* do the insertion */
         _bt_findinsertloc(rel, &buf, &offset, indnkeyatts, itup_scankey, itup,
                           stack, heapRel);
         _bt_insertonpg(rel, buf, InvalidBuffer, stack, itup, offset, false);
     }
     else
     {
         /* just release the buffer */
         _bt_relbuf(rel, buf);
     }
 
     /* be tidy */
     if (stack)
         _bt_freestack(stack);
     _bt_freeskey(itup_scankey);
 
     return is_unique;
 }

◆ _bt_end_vacuum()

void _bt_end_vacuum ( Relation rel )

Definition at line 1976 of file nbtutils.c.

References LockRelId::dbId, i, LockInfoData::lockRelId, LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), BTVacInfo::num_vacuums, RelationData::rd_lockInfo, LockRelId::relId, BTOneVacInfo::relid, and BTVacInfo::vacuums.

Referenced by _bt_end_vacuum_callback(), and btbulkdelete().

 {
     int         i;
 
     LWLockAcquire(BtreeVacuumLock, LW_EXCLUSIVE);
 
     /* Find the array entry */
     for (i = 0; i < btvacinfo->num_vacuums; i++)
     {
         BTOneVacInfo *vac = &btvacinfo->vacuums[i];
 
         if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId &&
             vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId)
         {
             /* Remove it by shifting down the last entry */
             *vac = btvacinfo->vacuums[btvacinfo->num_vacuums - 1];
             btvacinfo->num_vacuums--;
             break;
         }
     }
 
     LWLockRelease(BtreeVacuumLock);
 }

◆ _bt_end_vacuum_callback()

void _bt_end_vacuum_callback	(	int	code,
		Datum	arg
	)

Definition at line 2004 of file nbtutils.c.

References _bt_end_vacuum(), and DatumGetPointer.

Referenced by btbulkdelete().

 {
     _bt_end_vacuum((Relation) DatumGetPointer(arg));
 }

◆ _bt_finish_split()

void _bt_finish_split	(	Relation	rel,
		Buffer	bbuf,
		BTStack	stack
	)

Definition at line 1938 of file nbtinsert.c.

References _bt_getbuf(), _bt_insert_parent(), _bt_relbuf(), Assert, BT_WRITE, BTMetaPageData::btm_root, BTPageGetMeta, BTPageOpaqueData::btpo_next, BTREE_METAPAGE, BufferGetBlockNumber(), BufferGetPage, DEBUG1, elog, P_INCOMPLETE_SPLIT, P_LEFTMOST, P_RIGHTMOST, and PageGetSpecialPointer.

Referenced by _bt_findinsertloc(), _bt_getstackbuf(), and _bt_moveright().

 {
     Page        lpage = BufferGetPage(lbuf);
     BTPageOpaque lpageop = (BTPageOpaque) PageGetSpecialPointer(lpage);
     Buffer      rbuf;
     Page        rpage;
     BTPageOpaque rpageop;
     bool        was_root;
     bool        was_only;
 
     Assert(P_INCOMPLETE_SPLIT(lpageop));
 
     /* Lock right sibling, the one missing the downlink */
     rbuf = _bt_getbuf(rel, lpageop->btpo_next, BT_WRITE);
     rpage = BufferGetPage(rbuf);
     rpageop = (BTPageOpaque) PageGetSpecialPointer(rpage);
 
     /* Could this be a root split? */
     if (!stack)
     {
         Buffer      metabuf;
         Page        metapg;
         BTMetaPageData *metad;
 
         /* acquire lock on the metapage */
         metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_WRITE);
         metapg = BufferGetPage(metabuf);
         metad = BTPageGetMeta(metapg);
 
         was_root = (metad->btm_root == BufferGetBlockNumber(lbuf));
 
         _bt_relbuf(rel, metabuf);
     }
     else
         was_root = false;
 
     /* Was this the only page on the level before split? */
     was_only = (P_LEFTMOST(lpageop) && P_RIGHTMOST(rpageop));
 
     elog(DEBUG1, "finishing incomplete split of %u/%u",
          BufferGetBlockNumber(lbuf), BufferGetBlockNumber(rbuf));
 
     _bt_insert_parent(rel, lbuf, rbuf, stack, was_root, was_only);
 }

◆ _bt_first()

bool _bt_first	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 538 of file nbtsearch.c.

References _bt_binsrch(), _bt_drop_lock_and_maybe_pin(), _bt_endpoint(), _bt_freestack(), _bt_initialize_more_data(), _bt_parallel_done(), _bt_parallel_readpage(), _bt_parallel_seize(), _bt_preprocess_keys(), _bt_readpage(), _bt_search(), _bt_steppage(), Assert, BT_READ, BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, BTORDER_PROC, BTScanPosInvalidate, BTScanPosIsValid, buf, BTScanPosData::buf, BUFFER_LOCK_UNLOCK, BufferGetBlockNumber(), BufferIsValid, cur, BTScanOpaqueData::currPos, BTScanOpaqueData::currTuples, DatumGetPointer, elog, ERROR, get_opfamily_proc(), i, index_getprocinfo(), INDEX_MAX_KEYS, IndexScanDescData::indexRelation, InvalidBlockNumber, InvalidOid, InvalidStrategy, BTScanPosData::itemIndex, BTScanPosData::items, BTScanOpaqueData::keyData, LockBuffer(), BTScanOpaqueData::numberOfKeys, OffsetNumberPrev, IndexScanDescData::opaque, P_NONE, IndexScanDescData::parallel_scan, pgstat_count_index_scan, PredicateLockPage(), PredicateLockRelation(), BTScanOpaqueData::qual_ok, RelationData::rd_opcintype, RelationData::rd_opfamily, RegProcedureIsValid, RelationGetRelationName, ScanDirectionIsBackward, ScanDirectionIsForward, ScanKeyEntryInitialize(), ScanKeyEntryInitializeWithInfo(), ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, SK_ISNULL, SK_ROW_END, SK_ROW_HEADER, SK_ROW_MEMBER, SK_SEARCHNOTNULL, ScanKeyData::sk_strategy, ScanKeyData::sk_subtype, status(), HeapTupleData::t_self, IndexScanDescData::xs_ctup, IndexScanDescData::xs_itup, IndexScanDescData::xs_snapshot, and IndexScanDescData::xs_want_itup.

Referenced by btgetbitmap(), and btgettuple().

 {
     Relation    rel = scan->indexRelation;
     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     Buffer      buf;
     BTStack     stack;
     OffsetNumber offnum;
     StrategyNumber strat;
     bool        nextkey;
     bool        goback;
     ScanKey     startKeys[INDEX_MAX_KEYS];
     ScanKeyData scankeys[INDEX_MAX_KEYS];
     ScanKeyData notnullkeys[INDEX_MAX_KEYS];
     int         keysCount = 0;
     int         i;
     bool        status = true;
     StrategyNumber strat_total;
     BTScanPosItem *currItem;
     BlockNumber blkno;
 
     Assert(!BTScanPosIsValid(so->currPos));
 
     pgstat_count_index_scan(rel);
 
     /*
      * Examine the scan keys and eliminate any redundant keys; also mark the
      * keys that must be matched to continue the scan.
      */
     _bt_preprocess_keys(scan);
 
     /*
      * Quit now if _bt_preprocess_keys() discovered that the scan keys can
      * never be satisfied (eg, x == 1 AND x > 2).
      */
     if (!so->qual_ok)
         return false;
 
     /*
      * For parallel scans, get the starting page from shared state. If the
      * scan has not started, proceed to find out first leaf page in the usual
      * way while keeping other participating processes waiting.  If the scan
      * has already begun, use the page number from the shared structure.
      */
     if (scan->parallel_scan != NULL)
     {
         status = _bt_parallel_seize(scan, &blkno);
         if (!status)
             return false;
         else if (blkno == P_NONE)
         {
             _bt_parallel_done(scan);
             return false;
         }
         else if (blkno != InvalidBlockNumber)
         {
             if (!_bt_parallel_readpage(scan, blkno, dir))
                 return false;
             goto readcomplete;
         }
     }
 
     /*----------
      * Examine the scan keys to discover where we need to start the scan.
      *
      * We want to identify the keys that can be used as starting boundaries;
      * these are =, >, or >= keys for a forward scan or =, <, <= keys for
      * a backwards scan.  We can use keys for multiple attributes so long as
      * the prior attributes had only =, >= (resp. =, <=) keys.  Once we accept
      * a > or < boundary or find an attribute with no boundary (which can be
      * thought of as the same as "> -infinity"), we can't use keys for any
      * attributes to its right, because it would break our simplistic notion
      * of what initial positioning strategy to use.
      *
      * When the scan keys include cross-type operators, _bt_preprocess_keys
      * may not be able to eliminate redundant keys; in such cases we will
      * arbitrarily pick a usable one for each attribute.  This is correct
      * but possibly not optimal behavior.  (For example, with keys like
      * "x >= 4 AND x >= 5" we would elect to scan starting at x=4 when
      * x=5 would be more efficient.)  Since the situation only arises given
      * a poorly-worded query plus an incomplete opfamily, live with it.
      *
      * When both equality and inequality keys appear for a single attribute
      * (again, only possible when cross-type operators appear), we *must*
      * select one of the equality keys for the starting point, because
      * _bt_checkkeys() will stop the scan as soon as an equality qual fails.
      * For example, if we have keys like "x >= 4 AND x = 10" and we elect to
      * start at x=4, we will fail and stop before reaching x=10.  If multiple
      * equality quals survive preprocessing, however, it doesn't matter which
      * one we use --- by definition, they are either redundant or
      * contradictory.
      *
      * Any regular (not SK_SEARCHNULL) key implies a NOT NULL qualifier.
      * If the index stores nulls at the end of the index we'll be starting
      * from, and we have no boundary key for the column (which means the key
      * we deduced NOT NULL from is an inequality key that constrains the other
      * end of the index), then we cons up an explicit SK_SEARCHNOTNULL key to
      * use as a boundary key.  If we didn't do this, we might find ourselves
      * traversing a lot of null entries at the start of the scan.
      *
      * In this loop, row-comparison keys are treated the same as keys on their
      * first (leftmost) columns.  We'll add on lower-order columns of the row
      * comparison below, if possible.
      *
      * The selected scan keys (at most one per index column) are remembered by
      * storing their addresses into the local startKeys[] array.
      *----------
      */
     strat_total = BTEqualStrategyNumber;
     if (so->numberOfKeys > 0)
     {
         AttrNumber  curattr;
         ScanKey     chosen;
         ScanKey     impliesNN;
         ScanKey     cur;
 
         /*
          * chosen is the so-far-chosen key for the current attribute, if any.
          * We don't cast the decision in stone until we reach keys for the
          * next attribute.
          */
         curattr = 1;
         chosen = NULL;
         /* Also remember any scankey that implies a NOT NULL constraint */
         impliesNN = NULL;
 
         /*
          * Loop iterates from 0 to numberOfKeys inclusive; we use the last
          * pass to handle after-last-key processing.  Actual exit from the
          * loop is at one of the "break" statements below.
          */
         for (cur = so->keyData, i = 0;; cur++, i++)
         {
             if (i >= so->numberOfKeys || cur->sk_attno != curattr)
             {
                 /*
                  * Done looking at keys for curattr.  If we didn't find a
                  * usable boundary key, see if we can deduce a NOT NULL key.
                  */
                 if (chosen == NULL && impliesNN != NULL &&
                     ((impliesNN->sk_flags & SK_BT_NULLS_FIRST) ?
                      ScanDirectionIsForward(dir) :
                      ScanDirectionIsBackward(dir)))
                 {
                     /* Yes, so build the key in notnullkeys[keysCount] */
                     chosen = &notnullkeys[keysCount];
                     ScanKeyEntryInitialize(chosen,
                                            (SK_SEARCHNOTNULL | SK_ISNULL |
                                             (impliesNN->sk_flags &
                                              (SK_BT_DESC | SK_BT_NULLS_FIRST))),
                                            curattr,
                                            ((impliesNN->sk_flags & SK_BT_NULLS_FIRST) ?
                                             BTGreaterStrategyNumber :
                                             BTLessStrategyNumber),
                                            InvalidOid,
                                            InvalidOid,
                                            InvalidOid,
                                            (Datum) 0);
                 }
 
                 /*
                  * If we still didn't find a usable boundary key, quit; else
                  * save the boundary key pointer in startKeys.
                  */
                 if (chosen == NULL)
                     break;
                 startKeys[keysCount++] = chosen;
 
                 /*
                  * Adjust strat_total, and quit if we have stored a > or <
                  * key.
                  */
                 strat = chosen->sk_strategy;
                 if (strat != BTEqualStrategyNumber)
                 {
                     strat_total = strat;
                     if (strat == BTGreaterStrategyNumber ||
                         strat == BTLessStrategyNumber)
                         break;
                 }
 
                 /*
                  * Done if that was the last attribute, or if next key is not
                  * in sequence (implying no boundary key is available for the
                  * next attribute).
                  */
                 if (i >= so->numberOfKeys ||
                     cur->sk_attno != curattr + 1)
                     break;
 
                 /*
                  * Reset for next attr.
                  */
                 curattr = cur->sk_attno;
                 chosen = NULL;
                 impliesNN = NULL;
             }
 
             /*
              * Can we use this key as a starting boundary for this attr?
              *
              * If not, does it imply a NOT NULL constraint?  (Because
              * SK_SEARCHNULL keys are always assigned BTEqualStrategyNumber,
              * *any* inequality key works for that; we need not test.)
              */
             switch (cur->sk_strategy)
             {
                 case BTLessStrategyNumber:
                 case BTLessEqualStrategyNumber:
                     if (chosen == NULL)
                     {
                         if (ScanDirectionIsBackward(dir))
                             chosen = cur;
                         else
                             impliesNN = cur;
                     }
                     break;
                 case BTEqualStrategyNumber:
                     /* override any non-equality choice */
                     chosen = cur;
                     break;
                 case BTGreaterEqualStrategyNumber:
                 case BTGreaterStrategyNumber:
                     if (chosen == NULL)
                     {
                         if (ScanDirectionIsForward(dir))
                             chosen = cur;
                         else
                             impliesNN = cur;
                     }
                     break;
             }
         }
     }
 
     /*
      * If we found no usable boundary keys, we have to start from one end of
      * the tree.  Walk down that edge to the first or last key, and scan from
      * there.
      */
     if (keysCount == 0)
     {
         bool        match;
 
         match = _bt_endpoint(scan, dir);
 
         if (!match)
         {
             /* No match, so mark (parallel) scan finished */
             _bt_parallel_done(scan);
         }
 
         return match;
     }
 
     /*
      * We want to start the scan somewhere within the index.  Set up an
      * insertion scankey we can use to search for the boundary point we
      * identified above.  The insertion scankey is built in the local
      * scankeys[] array, using the keys identified by startKeys[].
      */
     Assert(keysCount <= INDEX_MAX_KEYS);
     for (i = 0; i < keysCount; i++)
     {
         ScanKey     cur = startKeys[i];
 
         Assert(cur->sk_attno == i + 1);
 
         if (cur->sk_flags & SK_ROW_HEADER)
         {
             /*
              * Row comparison header: look to the first row member instead.
              *
              * The member scankeys are already in insertion format (ie, they
              * have sk_func = 3-way-comparison function), but we have to watch
              * out for nulls, which _bt_preprocess_keys didn't check. A null
              * in the first row member makes the condition unmatchable, just
              * like qual_ok = false.
              */
             ScanKey     subkey = (ScanKey) DatumGetPointer(cur->sk_argument);
 
             Assert(subkey->sk_flags & SK_ROW_MEMBER);
             if (subkey->sk_flags & SK_ISNULL)
             {
                 _bt_parallel_done(scan);
                 return false;
             }
             memcpy(scankeys + i, subkey, sizeof(ScanKeyData));
 
             /*
              * If the row comparison is the last positioning key we accepted,
              * try to add additional keys from the lower-order row members.
              * (If we accepted independent conditions on additional index
              * columns, we use those instead --- doesn't seem worth trying to
              * determine which is more restrictive.)  Note that this is OK
              * even if the row comparison is of ">" or "<" type, because the
              * condition applied to all but the last row member is effectively
              * ">=" or "<=", and so the extra keys don't break the positioning
              * scheme.  But, by the same token, if we aren't able to use all
              * the row members, then the part of the row comparison that we
              * did use has to be treated as just a ">=" or "<=" condition, and
              * so we'd better adjust strat_total accordingly.
              */
             if (i == keysCount - 1)
             {
                 bool        used_all_subkeys = false;
 
                 Assert(!(subkey->sk_flags & SK_ROW_END));
                 for (;;)
                 {
                     subkey++;
                     Assert(subkey->sk_flags & SK_ROW_MEMBER);
                     if (subkey->sk_attno != keysCount + 1)
                         break;  /* out-of-sequence, can't use it */
                     if (subkey->sk_strategy != cur->sk_strategy)
                         break;  /* wrong direction, can't use it */
                     if (subkey->sk_flags & SK_ISNULL)
                         break;  /* can't use null keys */
                     Assert(keysCount < INDEX_MAX_KEYS);
                     memcpy(scankeys + keysCount, subkey, sizeof(ScanKeyData));
                     keysCount++;
                     if (subkey->sk_flags & SK_ROW_END)
                     {
                         used_all_subkeys = true;
                         break;
                     }
                 }
                 if (!used_all_subkeys)
                 {
                     switch (strat_total)
                     {
                         case BTLessStrategyNumber:
                             strat_total = BTLessEqualStrategyNumber;
                             break;
                         case BTGreaterStrategyNumber:
                             strat_total = BTGreaterEqualStrategyNumber;
                             break;
                     }
                 }
                 break;          /* done with outer loop */
             }
         }
         else
         {
             /*
              * Ordinary comparison key.  Transform the search-style scan key
              * to an insertion scan key by replacing the sk_func with the
              * appropriate btree comparison function.
              *
              * If scankey operator is not a cross-type comparison, we can use
              * the cached comparison function; otherwise gotta look it up in
              * the catalogs.  (That can't lead to infinite recursion, since no
              * indexscan initiated by syscache lookup will use cross-data-type
              * operators.)
              *
              * We support the convention that sk_subtype == InvalidOid means
              * the opclass input type; this is a hack to simplify life for
              * ScanKeyInit().
              */
             if (cur->sk_subtype == rel->rd_opcintype[i] ||
                 cur->sk_subtype == InvalidOid)
             {
                 FmgrInfo   *procinfo;
 
                 procinfo = index_getprocinfo(rel, cur->sk_attno, BTORDER_PROC);
                 ScanKeyEntryInitializeWithInfo(scankeys + i,
                                                cur->sk_flags,
                                                cur->sk_attno,
                                                InvalidStrategy,
                                                cur->sk_subtype,
                                                cur->sk_collation,
                                                procinfo,
                                                cur->sk_argument);
             }
             else
             {
                 RegProcedure cmp_proc;
 
                 cmp_proc = get_opfamily_proc(rel->rd_opfamily[i],
                                              rel->rd_opcintype[i],
                                              cur->sk_subtype,
                                              BTORDER_PROC);
                 if (!RegProcedureIsValid(cmp_proc))
                     elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
                          BTORDER_PROC, rel->rd_opcintype[i], cur->sk_subtype,
                          cur->sk_attno, RelationGetRelationName(rel));
                 ScanKeyEntryInitialize(scankeys + i,
                                        cur->sk_flags,
                                        cur->sk_attno,
                                        InvalidStrategy,
                                        cur->sk_subtype,
                                        cur->sk_collation,
                                        cmp_proc,
                                        cur->sk_argument);
             }
         }
     }
 
     /*----------
      * Examine the selected initial-positioning strategy to determine exactly
      * where we need to start the scan, and set flag variables to control the
      * code below.
      *
      * If nextkey = false, _bt_search and _bt_binsrch will locate the first
      * item >= scan key.  If nextkey = true, they will locate the first
      * item > scan key.
      *
      * If goback = true, we will then step back one item, while if
      * goback = false, we will start the scan on the located item.
      *----------
      */
     switch (strat_total)
     {
         case BTLessStrategyNumber:
 
             /*
              * Find first item >= scankey, then back up one to arrive at last
              * item < scankey.  (Note: this positioning strategy is only used
              * for a backward scan, so that is always the correct starting
              * position.)
              */
             nextkey = false;
             goback = true;
             break;
 
         case BTLessEqualStrategyNumber:
 
             /*
              * Find first item > scankey, then back up one to arrive at last
              * item <= scankey.  (Note: this positioning strategy is only used
              * for a backward scan, so that is always the correct starting
              * position.)
              */
             nextkey = true;
             goback = true;
             break;
 
         case BTEqualStrategyNumber:
 
             /*
              * If a backward scan was specified, need to start with last equal
              * item not first one.
              */
             if (ScanDirectionIsBackward(dir))
             {
                 /*
                  * This is the same as the <= strategy.  We will check at the
                  * end whether the found item is actually =.
                  */
                 nextkey = true;
                 goback = true;
             }
             else
             {
                 /*
                  * This is the same as the >= strategy.  We will check at the
                  * end whether the found item is actually =.
                  */
                 nextkey = false;
                 goback = false;
             }
             break;
 
         case BTGreaterEqualStrategyNumber:
 
             /*
              * Find first item >= scankey.  (This is only used for forward
              * scans.)
              */
             nextkey = false;
             goback = false;
             break;
 
         case BTGreaterStrategyNumber:
 
             /*
              * Find first item > scankey.  (This is only used for forward
              * scans.)
              */
             nextkey = true;
             goback = false;
             break;
 
         default:
             /* can't get here, but keep compiler quiet */
             elog(ERROR, "unrecognized strat_total: %d", (int) strat_total);
             return false;
     }
 
     /*
      * Use the manufactured insertion scan key to descend the tree and
      * position ourselves on the target leaf page.
      */
     stack = _bt_search(rel, keysCount, scankeys, nextkey, &buf, BT_READ,
                        scan->xs_snapshot);
 
     /* don't need to keep the stack around... */
     _bt_freestack(stack);
 
     if (!BufferIsValid(buf))
     {
         /*
          * We only get here if the index is completely empty. Lock relation
          * because nothing finer to lock exists.
          */
         PredicateLockRelation(rel, scan->xs_snapshot);
 
         /*
          * mark parallel scan as done, so that all the workers can finish
          * their scan
          */
         _bt_parallel_done(scan);
         BTScanPosInvalidate(so->currPos);
 
         return false;
     }
     else
         PredicateLockPage(rel, BufferGetBlockNumber(buf),
                           scan->xs_snapshot);
 
     _bt_initialize_more_data(so, dir);
 
     /* position to the precise item on the page */
     offnum = _bt_binsrch(rel, buf, keysCount, scankeys, nextkey);
 
     /*
      * If nextkey = false, we are positioned at the first item >= scan key, or
      * possibly at the end of a page on which all the existing items are less
      * than the scan key and we know that everything on later pages is greater
      * than or equal to scan key.
      *
      * If nextkey = true, we are positioned at the first item > scan key, or
      * possibly at the end of a page on which all the existing items are less
      * than or equal to the scan key and we know that everything on later
      * pages is greater than scan key.
      *
      * The actually desired starting point is either this item or the prior
      * one, or in the end-of-page case it's the first item on the next page or
      * the last item on this page.  Adjust the starting offset if needed. (If
      * this results in an offset before the first item or after the last one,
      * _bt_readpage will report no items found, and then we'll step to the
      * next page as needed.)
      */
     if (goback)
         offnum = OffsetNumberPrev(offnum);
 
     /* remember which buffer we have pinned, if any */
     Assert(!BTScanPosIsValid(so->currPos));
     so->currPos.buf = buf;
 
     /*
      * Now load data from the first page of the scan.
      */
     if (!_bt_readpage(scan, dir, offnum))
     {
         /*
          * There's no actually-matching data on this page.  Try to advance to
          * the next page.  Return false if there's no matching data at all.
          */
         LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);
         if (!_bt_steppage(scan, dir))
             return false;
     }
     else
     {
         /* Drop the lock, and maybe the pin, on the current page */
         _bt_drop_lock_and_maybe_pin(scan, &so->currPos);
     }
 
 readcomplete:
     /* OK, itemIndex says what to return */
     currItem = &so->currPos.items[so->currPos.itemIndex];
     scan->xs_ctup.t_self = currItem->heapTid;
     if (scan->xs_want_itup)
         scan->xs_itup = (IndexTuple) (so->currTuples + currItem->tupleOffset);
 
     return true;
 }

◆ _bt_freeskey()

void _bt_freeskey ( ScanKey skey )

Definition at line 166 of file nbtutils.c.

References pfree().

Referenced by _bt_doinsert(), _bt_load(), tuplesort_begin_cluster(), and tuplesort_begin_index_btree().

 {
     pfree(skey);
 }

◆ _bt_freestack()

void _bt_freestack ( BTStack stack )

Definition at line 175 of file nbtutils.c.

References BTStackData::bts_parent, and pfree().

Referenced by _bt_doinsert(), and _bt_first().

 {
     BTStack     ostack;
 
     while (stack != NULL)
     {
         ostack = stack;
         stack = stack->bts_parent;
         pfree(ostack);
     }
 }

◆ _bt_get_endpoint()

Buffer _bt_get_endpoint	(	Relation	rel,
		uint32	level,
		bool	rightmost,
		Snapshot	snapshot
	)

Definition at line 1776 of file nbtsearch.c.

References _bt_getroot(), _bt_gettrueroot(), _bt_relandgetbuf(), BT_READ, BTPageOpaqueData::btpo, BTPageOpaqueData::btpo_next, BTreeInnerTupleGetDownLink, buf, BufferGetPage, BufferIsValid, elog, ERROR, InvalidBuffer, BTPageOpaqueData::level, P_FIRSTDATAKEY, P_IGNORE, P_NONE, P_RIGHTMOST, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, PageGetSpecialPointer, RelationGetRelationName, and TestForOldSnapshot().

Referenced by _bt_endpoint(), and _bt_insert_parent().

 {
     Buffer      buf;
     Page        page;
     BTPageOpaque opaque;
     OffsetNumber offnum;
     BlockNumber blkno;
     IndexTuple  itup;
 
     /*
      * If we are looking for a leaf page, okay to descend from fast root;
      * otherwise better descend from true root.  (There is no point in being
      * smarter about intermediate levels.)
      */
     if (level == 0)
         buf = _bt_getroot(rel, BT_READ);
     else
         buf = _bt_gettrueroot(rel);
 
     if (!BufferIsValid(buf))
         return InvalidBuffer;
 
     page = BufferGetPage(buf);
     TestForOldSnapshot(snapshot, rel, page);
     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 
     for (;;)
     {
         /*
          * If we landed on a deleted page, step right to find a live page
          * (there must be one).  Also, if we want the rightmost page, step
          * right if needed to get to it (this could happen if the page split
          * since we obtained a pointer to it).
          */
         while (P_IGNORE(opaque) ||
                (rightmost && !P_RIGHTMOST(opaque)))
         {
             blkno = opaque->btpo_next;
             if (blkno == P_NONE)
                 elog(ERROR, "fell off the end of index \"%s\"",
                      RelationGetRelationName(rel));
             buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ);
             page = BufferGetPage(buf);
             TestForOldSnapshot(snapshot, rel, page);
             opaque = (BTPageOpaque) PageGetSpecialPointer(page);
         }
 
         /* Done? */
         if (opaque->btpo.level == level)
             break;
         if (opaque->btpo.level < level)
             elog(ERROR, "btree level %u not found in index \"%s\"",
                  level, RelationGetRelationName(rel));
 
         /* Descend to leftmost or rightmost child page */
         if (rightmost)
             offnum = PageGetMaxOffsetNumber(page);
         else
             offnum = P_FIRSTDATAKEY(opaque);
 
         itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
         blkno = BTreeInnerTupleGetDownLink(itup);
 
         buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ);
         page = BufferGetPage(buf);
         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
     }
 
     return buf;
 }

◆ _bt_getbuf()

Buffer _bt_getbuf	(	Relation	rel,
		BlockNumber	blkno,
		int	access
	)

Definition at line 729 of file nbtpage.c.

References _bt_checkpage(), _bt_log_reuse_page(), _bt_page_recyclable(), _bt_pageinit(), _bt_relbuf(), Assert, BT_WRITE, BTPageOpaqueData::btpo, buf, BufferGetPage, BufferGetPageSize, ConditionalLockBuffer(), DEBUG2, elog, ExclusiveLock, GetFreeIndexPage(), InvalidBlockNumber, LockBuffer(), LockRelationForExtension(), P_NEW, PageGetSpecialPointer, PageIsNew, ReadBuffer(), RELATION_IS_LOCAL, RelationNeedsWAL, ReleaseBuffer(), UnlockRelationForExtension(), BTPageOpaqueData::xact, and XLogStandbyInfoActive.

Referenced by _bt_finish_split(), _bt_getroot(), _bt_getrootheight(), _bt_getstackbuf(), _bt_gettrueroot(), _bt_insertonpg(), _bt_is_page_halfdead(), _bt_killitems(), _bt_lock_branch_parent(), _bt_moveright(), _bt_newroot(), _bt_pagedel(), _bt_readnextpage(), _bt_split(), _bt_unlink_halfdead_page(), _bt_update_meta_cleanup_info(), _bt_vacuum_needs_cleanup(), and _bt_walk_left().

 {
     Buffer      buf;
 
     if (blkno != P_NEW)
     {
         /* Read an existing block of the relation */
         buf = ReadBuffer(rel, blkno);
         LockBuffer(buf, access);
         _bt_checkpage(rel, buf);
     }
     else
     {
         bool        needLock;
         Page        page;
 
         Assert(access == BT_WRITE);
 
         /*
          * First see if the FSM knows of any free pages.
          *
          * We can't trust the FSM's report unreservedly; we have to check that
          * the page is still free.  (For example, an already-free page could
          * have been re-used between the time the last VACUUM scanned it and
          * the time the VACUUM made its FSM updates.)
          *
          * In fact, it's worse than that: we can't even assume that it's safe
          * to take a lock on the reported page.  If somebody else has a lock
          * on it, or even worse our own caller does, we could deadlock.  (The
          * own-caller scenario is actually not improbable. Consider an index
          * on a serial or timestamp column.  Nearly all splits will be at the
          * rightmost page, so it's entirely likely that _bt_split will call us
          * while holding a lock on the page most recently acquired from FSM. A
          * VACUUM running concurrently with the previous split could well have
          * placed that page back in FSM.)
          *
          * To get around that, we ask for only a conditional lock on the
          * reported page.  If we fail, then someone else is using the page,
          * and we may reasonably assume it's not free.  (If we happen to be
          * wrong, the worst consequence is the page will be lost to use till
          * the next VACUUM, which is no big problem.)
          */
         for (;;)
         {
             blkno = GetFreeIndexPage(rel);
             if (blkno == InvalidBlockNumber)
                 break;
             buf = ReadBuffer(rel, blkno);
             if (ConditionalLockBuffer(buf))
             {
                 page = BufferGetPage(buf);
                 if (_bt_page_recyclable(page))
                 {
                     /*
                      * If we are generating WAL for Hot Standby then create a
                      * WAL record that will allow us to conflict with queries
                      * running on standby.
                      */
                     if (XLogStandbyInfoActive() && RelationNeedsWAL(rel))
                     {
                         BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 
                         _bt_log_reuse_page(rel, blkno, opaque->btpo.xact);
                     }
 
                     /* Okay to use page.  Re-initialize and return it */
                     _bt_pageinit(page, BufferGetPageSize(buf));
                     return buf;
                 }
                 elog(DEBUG2, "FSM returned nonrecyclable page");
                 _bt_relbuf(rel, buf);
             }
             else
             {
                 elog(DEBUG2, "FSM returned nonlockable page");
                 /* couldn't get lock, so just drop pin */
                 ReleaseBuffer(buf);
             }
         }
 
         /*
          * Extend the relation by one page.
          *
          * We have to use a lock to ensure no one else is extending the rel at
          * the same time, else we will both try to initialize the same new
          * page.  We can skip locking for new or temp relations, however,
          * since no one else could be accessing them.
          */
         needLock = !RELATION_IS_LOCAL(rel);
 
         if (needLock)
             LockRelationForExtension(rel, ExclusiveLock);
 
         buf = ReadBuffer(rel, P_NEW);
 
         /* Acquire buffer lock on new page */
         LockBuffer(buf, BT_WRITE);
 
         /*
          * Release the file-extension lock; it's now OK for someone else to
          * extend the relation some more.  Note that we cannot release this
          * lock before we have buffer lock on the new page, or we risk a race
          * condition against btvacuumscan --- see comments therein.
          */
         if (needLock)
             UnlockRelationForExtension(rel, ExclusiveLock);
 
         /* Initialize the new page before returning it */
         page = BufferGetPage(buf);
         Assert(PageIsNew(page));
         _bt_pageinit(page, BufferGetPageSize(buf));
     }
 
     /* ref count and lock type are correct */
     return buf;
 }

◆ _bt_getroot()

Buffer _bt_getroot	(	Relation	rel,
		int	access
	)

Definition at line 252 of file nbtpage.c.

Referenced by _bt_get_endpoint(), _bt_getroot(), and _bt_search().

 {
     Buffer      metabuf;
     Page        metapg;
     BTPageOpaque metaopaque;
     Buffer      rootbuf;
     Page        rootpage;
     BTPageOpaque rootopaque;
     BlockNumber rootblkno;
     uint32      rootlevel;
     BTMetaPageData *metad;
 
     /*
      * Try to use previously-cached metapage data to find the root.  This
      * normally saves one buffer access per index search, which is a very
      * helpful savings in bufmgr traffic and hence contention.
      */
     if (rel->rd_amcache != NULL)
     {
         metad = (BTMetaPageData *) rel->rd_amcache;
         /* We shouldn't have cached it if any of these fail */
         Assert(metad->btm_magic == BTREE_MAGIC);
         Assert(metad->btm_version >= BTREE_MIN_VERSION);
         Assert(metad->btm_version <= BTREE_VERSION);
         Assert(metad->btm_root != P_NONE);
 
         rootblkno = metad->btm_fastroot;
         Assert(rootblkno != P_NONE);
         rootlevel = metad->btm_fastlevel;
 
         rootbuf = _bt_getbuf(rel, rootblkno, BT_READ);
         rootpage = BufferGetPage(rootbuf);
         rootopaque = (BTPageOpaque) PageGetSpecialPointer(rootpage);
 
         /*
          * Since the cache might be stale, we check the page more carefully
          * here than normal.  We *must* check that it's not deleted. If it's
          * not alone on its level, then we reject too --- this may be overly
          * paranoid but better safe than sorry.  Note we don't check P_ISROOT,
          * because that's not set in a "fast root".
          */
         if (!P_IGNORE(rootopaque) &&
             rootopaque->btpo.level == rootlevel &&
             P_LEFTMOST(rootopaque) &&
             P_RIGHTMOST(rootopaque))
         {
             /* OK, accept cached page as the root */
             return rootbuf;
         }
         _bt_relbuf(rel, rootbuf);
         /* Cache is stale, throw it away */
         if (rel->rd_amcache)
             pfree(rel->rd_amcache);
         rel->rd_amcache = NULL;
     }
 
     metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
     metapg = BufferGetPage(metabuf);
     metaopaque = (BTPageOpaque) PageGetSpecialPointer(metapg);
     metad = BTPageGetMeta(metapg);
 
     /* sanity-check the metapage */
     if (!P_ISMETA(metaopaque) ||
         metad->btm_magic != BTREE_MAGIC)
         ereport(ERROR,
                 (errcode(ERRCODE_INDEX_CORRUPTED),
                  errmsg("index \"%s\" is not a btree",
                         RelationGetRelationName(rel))));
 
     if (metad->btm_version < BTREE_MIN_VERSION ||
         metad->btm_version > BTREE_VERSION)
         ereport(ERROR,
                 (errcode(ERRCODE_INDEX_CORRUPTED),
                  errmsg("version mismatch in index \"%s\": file version %d, "
                         "current version %d, minimal supported version %d",
                         RelationGetRelationName(rel),
                         metad->btm_version, BTREE_VERSION, BTREE_MIN_VERSION)));
 
     /* if no root page initialized yet, do it */
     if (metad->btm_root == P_NONE)
     {
         /* If access = BT_READ, caller doesn't want us to create root yet */
         if (access == BT_READ)
         {
             _bt_relbuf(rel, metabuf);
             return InvalidBuffer;
         }
 
         /* trade in our read lock for a write lock */
         LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
         LockBuffer(metabuf, BT_WRITE);
 
         /*
          * Race condition:  if someone else initialized the metadata between
          * the time we released the read lock and acquired the write lock, we
          * must avoid doing it again.
          */
         if (metad->btm_root != P_NONE)
         {
             /*
              * Metadata initialized by someone else.  In order to guarantee no
              * deadlocks, we have to release the metadata page and start all
              * over again.  (Is that really true? But it's hardly worth trying
              * to optimize this case.)
              */
             _bt_relbuf(rel, metabuf);
             return _bt_getroot(rel, access);
         }
 
         /*
          * Get, initialize, write, and leave a lock of the appropriate type on
          * the new root page.  Since this is the first page in the tree, it's
          * a leaf as well as the root.
          */
         rootbuf = _bt_getbuf(rel, P_NEW, BT_WRITE);
         rootblkno = BufferGetBlockNumber(rootbuf);
         rootpage = BufferGetPage(rootbuf);
         rootopaque = (BTPageOpaque) PageGetSpecialPointer(rootpage);
         rootopaque->btpo_prev = rootopaque->btpo_next = P_NONE;
         rootopaque->btpo_flags = (BTP_LEAF | BTP_ROOT);
         rootopaque->btpo.level = 0;
         rootopaque->btpo_cycleid = 0;
 
         /* NO ELOG(ERROR) till meta is updated */
         START_CRIT_SECTION();
 
         /* upgrade metapage if needed */
         if (metad->btm_version < BTREE_VERSION)
             _bt_upgrademetapage(metapg);
 
         metad->btm_root = rootblkno;
         metad->btm_level = 0;
         metad->btm_fastroot = rootblkno;
         metad->btm_fastlevel = 0;
         metad->btm_oldest_btpo_xact = InvalidTransactionId;
         metad->btm_last_cleanup_num_heap_tuples = -1.0;
 
         MarkBufferDirty(rootbuf);
         MarkBufferDirty(metabuf);
 
         /* XLOG stuff */
         if (RelationNeedsWAL(rel))
         {
             xl_btree_newroot xlrec;
             XLogRecPtr  recptr;
             xl_btree_metadata md;
 
             XLogBeginInsert();
             XLogRegisterBuffer(0, rootbuf, REGBUF_WILL_INIT);
             XLogRegisterBuffer(2, metabuf, REGBUF_WILL_INIT | REGBUF_STANDARD);
 
             md.root = rootblkno;
             md.level = 0;
             md.fastroot = rootblkno;
             md.fastlevel = 0;
             md.oldest_btpo_xact = InvalidTransactionId;
             md.last_cleanup_num_heap_tuples = -1.0;
 
             XLogRegisterBufData(2, (char *) &md, sizeof(xl_btree_metadata));
 
             xlrec.rootblk = rootblkno;
             xlrec.level = 0;
 
             XLogRegisterData((char *) &xlrec, SizeOfBtreeNewroot);
 
             recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_NEWROOT);
 
             PageSetLSN(rootpage, recptr);
             PageSetLSN(metapg, recptr);
         }
 
         END_CRIT_SECTION();
 
         /*
          * swap root write lock for read lock.  There is no danger of anyone
          * else accessing the new root page while it's unlocked, since no one
          * else knows where it is yet.
          */
         LockBuffer(rootbuf, BUFFER_LOCK_UNLOCK);
         LockBuffer(rootbuf, BT_READ);
 
         /* okay, metadata is correct, release lock on it */
         _bt_relbuf(rel, metabuf);
     }
     else
     {
         rootblkno = metad->btm_fastroot;
         Assert(rootblkno != P_NONE);
         rootlevel = metad->btm_fastlevel;
 
         /*
          * Cache the metapage data for next time
          */
         _bt_cachemetadata(rel, metad);
 
         /*
          * We are done with the metapage; arrange to release it via first
          * _bt_relandgetbuf call
          */
         rootbuf = metabuf;
 
         for (;;)
         {
             rootbuf = _bt_relandgetbuf(rel, rootbuf, rootblkno, BT_READ);
             rootpage = BufferGetPage(rootbuf);
             rootopaque = (BTPageOpaque) PageGetSpecialPointer(rootpage);
 
             if (!P_IGNORE(rootopaque))
                 break;
 
             /* it's dead, Jim.  step right one page */
             if (P_RIGHTMOST(rootopaque))
                 elog(ERROR, "no live root page found in index \"%s\"",
                      RelationGetRelationName(rel));
             rootblkno = rootopaque->btpo_next;
         }
 
         /* Note: can't check btpo.level on deleted pages */
         if (rootopaque->btpo.level != rootlevel)
             elog(ERROR, "root page %u of index \"%s\" has level %u, expected %u",
                  rootblkno, RelationGetRelationName(rel),
                  rootopaque->btpo.level, rootlevel);
     }
 
     /*
      * By here, we have a pin and read lock on the root page, and no lock set
      * on the metadata page.  Return the root page's buffer.
      */
     return rootbuf;
 }

◆ _bt_getrootheight()

int _bt_getrootheight ( Relation rel )

Definition at line 594 of file nbtpage.c.

References _bt_cachemetadata(), _bt_getbuf(), _bt_relbuf(), Assert, BT_READ, BTMetaPageData::btm_fastlevel, BTMetaPageData::btm_fastroot, BTMetaPageData::btm_magic, BTMetaPageData::btm_root, BTMetaPageData::btm_version, BTPageGetMeta, BTREE_MAGIC, BTREE_METAPAGE, BTREE_MIN_VERSION, BTREE_VERSION, BufferGetPage, ereport, errcode(), errmsg(), ERROR, P_ISMETA, P_NONE, PageGetSpecialPointer, RelationData::rd_amcache, and RelationGetRelationName.

Referenced by _bt_insertonpg(), and get_relation_info().

 {
     BTMetaPageData *metad;
 
     /*
      * We can get what we need from the cached metapage data.  If it's not
      * cached yet, load it.  Sanity checks here must match _bt_getroot().
      */
     if (rel->rd_amcache == NULL)
     {
         Buffer      metabuf;
         Page        metapg;
         BTPageOpaque metaopaque;
 
         metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
         metapg = BufferGetPage(metabuf);
         metaopaque = (BTPageOpaque) PageGetSpecialPointer(metapg);
         metad = BTPageGetMeta(metapg);
 
         /* sanity-check the metapage */
         if (!P_ISMETA(metaopaque) ||
             metad->btm_magic != BTREE_MAGIC)
             ereport(ERROR,
                     (errcode(ERRCODE_INDEX_CORRUPTED),
                      errmsg("index \"%s\" is not a btree",
                             RelationGetRelationName(rel))));
 
         if (metad->btm_version < BTREE_MIN_VERSION ||
             metad->btm_version > BTREE_VERSION)
             ereport(ERROR,
                     (errcode(ERRCODE_INDEX_CORRUPTED),
                      errmsg("version mismatch in index \"%s\": file version %d, "
                             "current version %d, minimal supported version %d",
                             RelationGetRelationName(rel),
                             metad->btm_version, BTREE_VERSION, BTREE_MIN_VERSION)));
 
         /*
          * If there's no root page yet, _bt_getroot() doesn't expect a cache
          * to be made, so just stop here and report the index height is zero.
          * (XXX perhaps _bt_getroot() should be changed to allow this case.)
          */
         if (metad->btm_root == P_NONE)
         {
             _bt_relbuf(rel, metabuf);
             return 0;
         }
 
         /*
          * Cache the metapage data for next time
          */
         _bt_cachemetadata(rel, metad);
 
         _bt_relbuf(rel, metabuf);
     }
 
     metad = (BTMetaPageData *) rel->rd_amcache;
     /* We shouldn't have cached it if any of these fail */
     Assert(metad->btm_magic == BTREE_MAGIC);
     Assert(metad->btm_version == BTREE_VERSION);
     Assert(metad->btm_fastroot != P_NONE);
 
     return metad->btm_fastlevel;
 }

◆ _bt_getstackbuf()

Buffer _bt_getstackbuf	(	Relation	rel,
		BTStack	stack,
		int	access
	)

Definition at line 1997 of file nbtinsert.c.

References _bt_finish_split(), _bt_getbuf(), _bt_relbuf(), BT_WRITE, BTPageOpaqueData::btpo_next, BTreeInnerTupleGetDownLink, BTStackData::bts_blkno, BTStackData::bts_btentry, BTStackData::bts_offset, BTStackData::bts_parent, buf, BufferGetPage, InvalidBuffer, InvalidOffsetNumber, OffsetNumberNext, OffsetNumberPrev, P_FIRSTDATAKEY, P_IGNORE, P_INCOMPLETE_SPLIT, P_RIGHTMOST, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, and PageGetSpecialPointer.

Referenced by _bt_insert_parent(), and _bt_lock_branch_parent().

 {
     BlockNumber blkno;
     OffsetNumber start;
 
     blkno = stack->bts_blkno;
     start = stack->bts_offset;
 
     for (;;)
     {
         Buffer      buf;
         Page        page;
         BTPageOpaque opaque;
 
         buf = _bt_getbuf(rel, blkno, access);
         page = BufferGetPage(buf);
         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 
         if (access == BT_WRITE && P_INCOMPLETE_SPLIT(opaque))
         {
             _bt_finish_split(rel, buf, stack->bts_parent);
             continue;
         }
 
         if (!P_IGNORE(opaque))
         {
             OffsetNumber offnum,
                         minoff,
                         maxoff;
             ItemId      itemid;
             IndexTuple  item;
 
             minoff = P_FIRSTDATAKEY(opaque);
             maxoff = PageGetMaxOffsetNumber(page);
 
             /*
              * start = InvalidOffsetNumber means "search the whole page". We
              * need this test anyway due to possibility that page has a high
              * key now when it didn't before.
              */
             if (start < minoff)
                 start = minoff;
 
             /*
              * Need this check too, to guard against possibility that page
              * split since we visited it originally.
              */
             if (start > maxoff)
                 start = OffsetNumberNext(maxoff);
 
             /*
              * These loops will check every item on the page --- but in an
              * order that's attuned to the probability of where it actually
              * is.  Scan to the right first, then to the left.
              */
             for (offnum = start;
                  offnum <= maxoff;
                  offnum = OffsetNumberNext(offnum))
             {
                 itemid = PageGetItemId(page, offnum);
                 item = (IndexTuple) PageGetItem(page, itemid);
 
                 if (BTreeInnerTupleGetDownLink(item) == stack->bts_btentry)
                 {
                     /* Return accurate pointer to where link is now */
                     stack->bts_blkno = blkno;
                     stack->bts_offset = offnum;
                     return buf;
                 }
             }
 
             for (offnum = OffsetNumberPrev(start);
                  offnum >= minoff;
                  offnum = OffsetNumberPrev(offnum))
             {
                 itemid = PageGetItemId(page, offnum);
                 item = (IndexTuple) PageGetItem(page, itemid);
 
                 if (BTreeInnerTupleGetDownLink(item) == stack->bts_btentry)
                 {
                     /* Return accurate pointer to where link is now */
                     stack->bts_blkno = blkno;
                     stack->bts_offset = offnum;
                     return buf;
                 }
             }
         }
 
         /*
          * The item we're looking for moved right at least one page.
          */
         if (P_RIGHTMOST(opaque))
         {
             _bt_relbuf(rel, buf);
             return InvalidBuffer;
         }
         blkno = opaque->btpo_next;
         start = InvalidOffsetNumber;
         _bt_relbuf(rel, buf);
     }
 }

◆ _bt_gettrueroot()

Buffer _bt_gettrueroot ( Relation rel )

Definition at line 498 of file nbtpage.c.

References _bt_getbuf(), _bt_relandgetbuf(), _bt_relbuf(), BT_READ, BTMetaPageData::btm_level, BTMetaPageData::btm_magic, BTMetaPageData::btm_root, BTMetaPageData::btm_version, BTPageGetMeta, BTPageOpaqueData::btpo, BTPageOpaqueData::btpo_next, BTREE_MAGIC, BTREE_METAPAGE, BTREE_MIN_VERSION, BTREE_VERSION, BufferGetPage, elog, ereport, errcode(), errmsg(), ERROR, InvalidBuffer, BTPageOpaqueData::level, P_IGNORE, P_ISMETA, P_NONE, P_RIGHTMOST, PageGetSpecialPointer, pfree(), RelationData::rd_amcache, and RelationGetRelationName.

Referenced by _bt_get_endpoint().

 {
     Buffer      metabuf;
     Page        metapg;
     BTPageOpaque metaopaque;
     Buffer      rootbuf;
     Page        rootpage;
     BTPageOpaque rootopaque;
     BlockNumber rootblkno;
     uint32      rootlevel;
     BTMetaPageData *metad;
 
     /*
      * We don't try to use cached metapage data here, since (a) this path is
      * not performance-critical, and (b) if we are here it suggests our cache
      * is out-of-date anyway.  In light of point (b), it's probably safest to
      * actively flush any cached metapage info.
      */
     if (rel->rd_amcache)
         pfree(rel->rd_amcache);
     rel->rd_amcache = NULL;
 
     metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
     metapg = BufferGetPage(metabuf);
     metaopaque = (BTPageOpaque) PageGetSpecialPointer(metapg);
     metad = BTPageGetMeta(metapg);
 
     if (!P_ISMETA(metaopaque) ||
         metad->btm_magic != BTREE_MAGIC)
         ereport(ERROR,
                 (errcode(ERRCODE_INDEX_CORRUPTED),
                  errmsg("index \"%s\" is not a btree",
                         RelationGetRelationName(rel))));
 
     if (metad->btm_version < BTREE_MIN_VERSION ||
         metad->btm_version > BTREE_VERSION)
         ereport(ERROR,
                 (errcode(ERRCODE_INDEX_CORRUPTED),
                  errmsg("version mismatch in index \"%s\": file version %d, "
                         "current version %d, minimal supported version %d",
                         RelationGetRelationName(rel),
                         metad->btm_version, BTREE_VERSION, BTREE_MIN_VERSION)));
 
     /* if no root page initialized yet, fail */
     if (metad->btm_root == P_NONE)
     {
         _bt_relbuf(rel, metabuf);
         return InvalidBuffer;
     }
 
     rootblkno = metad->btm_root;
     rootlevel = metad->btm_level;
 
     /*
      * We are done with the metapage; arrange to release it via first
      * _bt_relandgetbuf call
      */
     rootbuf = metabuf;
 
     for (;;)
     {
         rootbuf = _bt_relandgetbuf(rel, rootbuf, rootblkno, BT_READ);
         rootpage = BufferGetPage(rootbuf);
         rootopaque = (BTPageOpaque) PageGetSpecialPointer(rootpage);
 
         if (!P_IGNORE(rootopaque))
             break;
 
         /* it's dead, Jim.  step right one page */
         if (P_RIGHTMOST(rootopaque))
             elog(ERROR, "no live root page found in index \"%s\"",
                  RelationGetRelationName(rel));
         rootblkno = rootopaque->btpo_next;
     }
 
     /* Note: can't check btpo.level on deleted pages */
     if (rootopaque->btpo.level != rootlevel)
         elog(ERROR, "root page %u of index \"%s\" has level %u, expected %u",
              rootblkno, RelationGetRelationName(rel),
              rootopaque->btpo.level, rootlevel);
 
     return rootbuf;
 }

◆ _bt_initmetapage()

void _bt_initmetapage	(	Page	page,
		BlockNumber	rootbknum,
		uint32	level
	)

Definition at line 50 of file nbtpage.c.

References _bt_pageinit(), BTMetaPageData::btm_fastlevel, BTMetaPageData::btm_fastroot, BTMetaPageData::btm_last_cleanup_num_heap_tuples, BTMetaPageData::btm_level, BTMetaPageData::btm_magic, BTMetaPageData::btm_oldest_btpo_xact, BTMetaPageData::btm_root, BTMetaPageData::btm_version, BTP_META, BTPageGetMeta, BTPageOpaqueData::btpo_flags, BTREE_MAGIC, BTREE_VERSION, InvalidTransactionId, and PageGetSpecialPointer.

Referenced by _bt_uppershutdown(), and btbuildempty().

 {
     BTMetaPageData *metad;
     BTPageOpaque metaopaque;
 
     _bt_pageinit(page, BLCKSZ);
 
     metad = BTPageGetMeta(page);
     metad->btm_magic = BTREE_MAGIC;
     metad->btm_version = BTREE_VERSION;
     metad->btm_root = rootbknum;
     metad->btm_level = level;
     metad->btm_fastroot = rootbknum;
     metad->btm_fastlevel = level;
     metad->btm_oldest_btpo_xact = InvalidTransactionId;
     metad->btm_last_cleanup_num_heap_tuples = -1.0;
 
     metaopaque = (BTPageOpaque) PageGetSpecialPointer(page);
     metaopaque->btpo_flags = BTP_META;
 
     /*
      * Set pd_lower just past the end of the metadata.  This is essential,
      * because without doing so, metadata will be lost if xlog.c compresses
      * the page.
      */
     ((PageHeader) page)->pd_lower =
         ((char *) metad + sizeof(BTMetaPageData)) - (char *) page;
 }

◆ _bt_killitems()

void _bt_killitems ( IndexScanDesc scan )

Definition at line 1744 of file nbtutils.c.

References _bt_getbuf(), _bt_relbuf(), Assert, BT_READ, BTP_HAS_GARBAGE, BTScanPosIsPinned, BTScanPosIsValid, buf, BTScanPosData::buf, BUFFER_LOCK_UNLOCK, BufferGetLSNAtomic(), BufferGetPage, BufferIsValid, BTScanPosData::currPage, BTScanOpaqueData::currPos, BTScanPosData::firstItem, BTScanPosItem::heapTid, i, BTScanPosItem::indexOffset, IndexScanDescData::indexRelation, ItemIdMarkDead, ItemPointerEquals(), BTScanPosData::items, BTScanOpaqueData::killedItems, LockBuffer(), BTScanPosData::lsn, MarkBufferDirtyHint(), BTScanOpaqueData::numKilled, OffsetNumberNext, IndexScanDescData::opaque, P_FIRSTDATAKEY, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, PageGetSpecialPointer, and IndexTupleData::t_tid.

Referenced by _bt_steppage(), btendscan(), btrescan(), and btrestrpos().

 {
     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     Page        page;
     BTPageOpaque opaque;
     OffsetNumber minoff;
     OffsetNumber maxoff;
     int         i;
     int         numKilled = so->numKilled;
     bool        killedsomething = false;
 
     Assert(BTScanPosIsValid(so->currPos));
 
     /*
      * Always reset the scan state, so we don't look for same items on other
      * pages.
      */
     so->numKilled = 0;
 
     if (BTScanPosIsPinned(so->currPos))
     {
         /*
          * We have held the pin on this page since we read the index tuples,
          * so all we need to do is lock it.  The pin will have prevented
          * re-use of any TID on the page, so there is no need to check the
          * LSN.
          */
         LockBuffer(so->currPos.buf, BT_READ);
 
         page = BufferGetPage(so->currPos.buf);
     }
     else
     {
         Buffer      buf;
 
         /* Attempt to re-read the buffer, getting pin and lock. */
         buf = _bt_getbuf(scan->indexRelation, so->currPos.currPage, BT_READ);
 
         /* It might not exist anymore; in which case we can't hint it. */
         if (!BufferIsValid(buf))
             return;
 
         page = BufferGetPage(buf);
         if (BufferGetLSNAtomic(buf) == so->currPos.lsn)
             so->currPos.buf = buf;
         else
         {
             /* Modified while not pinned means hinting is not safe. */
             _bt_relbuf(scan->indexRelation, buf);
             return;
         }
     }
 
     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
     minoff = P_FIRSTDATAKEY(opaque);
     maxoff = PageGetMaxOffsetNumber(page);
 
     for (i = 0; i < numKilled; i++)
     {
         int         itemIndex = so->killedItems[i];
         BTScanPosItem *kitem = &so->currPos.items[itemIndex];
         OffsetNumber offnum = kitem->indexOffset;
 
         Assert(itemIndex >= so->currPos.firstItem &&
                itemIndex <= so->currPos.lastItem);
         if (offnum < minoff)
             continue;           /* pure paranoia */
         while (offnum <= maxoff)
         {
             ItemId      iid = PageGetItemId(page, offnum);
             IndexTuple  ituple = (IndexTuple) PageGetItem(page, iid);
 
             if (ItemPointerEquals(&ituple->t_tid, &kitem->heapTid))
             {
                 /* found the item */
                 ItemIdMarkDead(iid);
                 killedsomething = true;
                 break;          /* out of inner search loop */
             }
             offnum = OffsetNumberNext(offnum);
         }
     }
 
     /*
      * Since this can be redone later if needed, mark as dirty hint.
      *
      * Whenever we mark anything LP_DEAD, we also set the page's
      * BTP_HAS_GARBAGE flag, which is likewise just a hint.
      */
     if (killedsomething)
     {
         opaque->btpo_flags |= BTP_HAS_GARBAGE;
         MarkBufferDirtyHint(so->currPos.buf, true);
     }
 
     LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);
 }

◆ _bt_mark_array_keys()

void _bt_mark_array_keys ( IndexScanDesc scan )

Definition at line 617 of file nbtutils.c.

References BTScanOpaqueData::arrayKeys, BTArrayKeyInfo::cur_elem, i, BTArrayKeyInfo::mark_elem, BTScanOpaqueData::numArrayKeys, and IndexScanDescData::opaque.

Referenced by btmarkpos().

 {
     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     int         i;
 
     for (i = 0; i < so->numArrayKeys; i++)
     {
         BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
 
         curArrayKey->mark_elem = curArrayKey->cur_elem;
     }
 }

◆ _bt_mkscankey()

ScanKey _bt_mkscankey	(	Relation	rel,
		IndexTuple	itup
	)

Definition at line 62 of file nbtutils.c.

References arg, Assert, BTORDER_PROC, BTreeTupleGetNAtts, i, index_getattr, index_getprocinfo(), IndexRelationGetNumberOfAttributes, IndexRelationGetNumberOfKeyAttributes, InvalidOid, InvalidStrategy, palloc(), PG_USED_FOR_ASSERTS_ONLY, RelationData::rd_indcollation, RelationData::rd_indoption, RelationGetDescr, ScanKeyEntryInitializeWithInfo(), SK_BT_INDOPTION_SHIFT, and SK_ISNULL.

Referenced by _bt_doinsert(), _bt_pagedel(), bt_right_page_check_scankey(), and bt_target_page_check().

 {
     ScanKey     skey;
     TupleDesc   itupdesc;
     int         indnatts PG_USED_FOR_ASSERTS_ONLY;
     int         indnkeyatts;
     int16      *indoption;
     int         i;
 
     itupdesc = RelationGetDescr(rel);
     indnatts = IndexRelationGetNumberOfAttributes(rel);
     indnkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
     indoption = rel->rd_indoption;
 
     Assert(indnkeyatts > 0);
     Assert(indnkeyatts <= indnatts);
     Assert(BTreeTupleGetNAtts(itup, rel) == indnatts ||
            BTreeTupleGetNAtts(itup, rel) == indnkeyatts);
 
     /*
      * We'll execute search using scan key constructed on key columns. Non-key
      * (INCLUDE index) columns are always omitted from scan keys.
      */
     skey = (ScanKey) palloc(indnkeyatts * sizeof(ScanKeyData));
 
     for (i = 0; i < indnkeyatts; i++)
     {
         FmgrInfo   *procinfo;
         Datum       arg;
         bool        null;
         int         flags;
 
         /*
          * We can use the cached (default) support procs since no cross-type
          * comparison can be needed.
          */
         procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
         arg = index_getattr(itup, i + 1, itupdesc, &null);
         flags = (null ? SK_ISNULL : 0) | (indoption[i] << SK_BT_INDOPTION_SHIFT);
         ScanKeyEntryInitializeWithInfo(&skey[i],
                                        flags,
                                        (AttrNumber) (i + 1),
                                        InvalidStrategy,
                                        InvalidOid,
                                        rel->rd_indcollation[i],
                                        procinfo,
                                        arg);
     }
 
     return skey;
 }

◆ _bt_mkscankey_nodata()

ScanKey _bt_mkscankey_nodata ( Relation rel )

Definition at line 126 of file nbtutils.c.

References BTORDER_PROC, i, index_getprocinfo(), IndexRelationGetNumberOfKeyAttributes, InvalidOid, InvalidStrategy, palloc(), RelationData::rd_indcollation, RelationData::rd_indoption, ScanKeyEntryInitializeWithInfo(), SK_BT_INDOPTION_SHIFT, and SK_ISNULL.

Referenced by _bt_load(), tuplesort_begin_cluster(), and tuplesort_begin_index_btree().

 {
     ScanKey     skey;
     int         indnkeyatts;
     int16      *indoption;
     int         i;
 
     indnkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
     indoption = rel->rd_indoption;
 
     skey = (ScanKey) palloc(indnkeyatts * sizeof(ScanKeyData));
 
     for (i = 0; i < indnkeyatts; i++)
     {
         FmgrInfo   *procinfo;
         int         flags;
 
         /*
          * We can use the cached (default) support procs since no cross-type
          * comparison can be needed.
          */
         procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
         flags = SK_ISNULL | (indoption[i] << SK_BT_INDOPTION_SHIFT);
         ScanKeyEntryInitializeWithInfo(&skey[i],
                                        flags,
                                        (AttrNumber) (i + 1),
                                        InvalidStrategy,
                                        InvalidOid,
                                        rel->rd_indcollation[i],
                                        procinfo,
                                        (Datum) 0);
     }
 
     return skey;
 }

◆ _bt_moveright()

Buffer _bt_moveright	(	Relation	rel,
		Buffer	buf,
		int	keysz,
		ScanKey	scankey,
		bool	nextkey,
		bool	forupdate,
		BTStack	stack,
		int	access,
		Snapshot	snapshot
	)

Definition at line 214 of file nbtsearch.c.

References _bt_compare(), _bt_finish_split(), _bt_getbuf(), _bt_relandgetbuf(), _bt_relbuf(), BT_READ, BT_WRITE, BTPageOpaqueData::btpo_next, buf, BUFFER_LOCK_UNLOCK, BufferGetBlockNumber(), BufferGetPage, elog, ERROR, LockBuffer(), P_HIKEY, P_IGNORE, P_INCOMPLETE_SPLIT, P_RIGHTMOST, PageGetSpecialPointer, RelationGetRelationName, and TestForOldSnapshot().

Referenced by _bt_doinsert(), and _bt_search().

 {
     Page        page;
     BTPageOpaque opaque;
     int32       cmpval;
 
     /*
      * When nextkey = false (normal case): if the scan key that brought us to
      * this page is > the high key stored on the page, then the page has split
      * and we need to move right.  (If the scan key is equal to the high key,
      * we might or might not need to move right; have to scan the page first
      * anyway.)
      *
      * When nextkey = true: move right if the scan key is >= page's high key.
      *
      * The page could even have split more than once, so scan as far as
      * needed.
      *
      * We also have to move right if we followed a link that brought us to a
      * dead page.
      */
     cmpval = nextkey ? 0 : 1;
 
     for (;;)
     {
         page = BufferGetPage(buf);
         TestForOldSnapshot(snapshot, rel, page);
         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 
         if (P_RIGHTMOST(opaque))
             break;
 
         /*
          * Finish any incomplete splits we encounter along the way.
          */
         if (forupdate && P_INCOMPLETE_SPLIT(opaque))
         {
             BlockNumber blkno = BufferGetBlockNumber(buf);
 
             /* upgrade our lock if necessary */
             if (access == BT_READ)
             {
                 LockBuffer(buf, BUFFER_LOCK_UNLOCK);
                 LockBuffer(buf, BT_WRITE);
             }
 
             if (P_INCOMPLETE_SPLIT(opaque))
                 _bt_finish_split(rel, buf, stack);
             else
                 _bt_relbuf(rel, buf);
 
             /* re-acquire the lock in the right mode, and re-check */
             buf = _bt_getbuf(rel, blkno, access);
             continue;
         }
 
         if (P_IGNORE(opaque) || _bt_compare(rel, keysz, scankey, page, P_HIKEY) >= cmpval)
         {
             /* step right one page */
             buf = _bt_relandgetbuf(rel, buf, opaque->btpo_next, access);
             continue;
         }
         else
             break;
     }
 
     if (P_IGNORE(opaque))
         elog(ERROR, "fell off the end of index \"%s\"",
              RelationGetRelationName(rel));
 
     return buf;
 }

◆ _bt_next()

bool _bt_next	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 1131 of file nbtsearch.c.

References _bt_steppage(), BTScanOpaqueData::currPos, BTScanOpaqueData::currTuples, BTScanPosData::firstItem, BTScanPosData::itemIndex, BTScanPosData::items, BTScanPosData::lastItem, IndexScanDescData::opaque, ScanDirectionIsForward, HeapTupleData::t_self, IndexScanDescData::xs_ctup, IndexScanDescData::xs_itup, and IndexScanDescData::xs_want_itup.

Referenced by btgetbitmap(), and btgettuple().

 {
     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     BTScanPosItem *currItem;
 
     /*
      * Advance to next tuple on current page; or if there's no more, try to
      * step to the next page with data.
      */
     if (ScanDirectionIsForward(dir))
     {
         if (++so->currPos.itemIndex > so->currPos.lastItem)
         {
             if (!_bt_steppage(scan, dir))
                 return false;
         }
     }
     else
     {
         if (--so->currPos.itemIndex < so->currPos.firstItem)
         {
             if (!_bt_steppage(scan, dir))
                 return false;
         }
     }
 
     /* OK, itemIndex says what to return */
     currItem = &so->currPos.items[so->currPos.itemIndex];
     scan->xs_ctup.t_self = currItem->heapTid;
     if (scan->xs_want_itup)
         scan->xs_itup = (IndexTuple) (so->currTuples + currItem->tupleOffset);
 
     return true;
 }

◆ _bt_nonkey_truncate()

IndexTuple _bt_nonkey_truncate	(	Relation	rel,
		IndexTuple	itup
	)

Definition at line 2102 of file nbtutils.c.

References Assert, BTreeTupleGetNAtts, BTreeTupleSetNAtts, index_truncate_tuple(), IndexRelationGetNumberOfAttributes, IndexRelationGetNumberOfKeyAttributes, and RelationGetDescr.

Referenced by _bt_buildadd(), and _bt_split().

 {
     int         nkeyattrs = IndexRelationGetNumberOfKeyAttributes(rel);
     IndexTuple  truncated;
 
     /*
      * We should only ever truncate leaf index tuples, which must have both
      * key and non-key attributes.  It's never okay to truncate a second time.
      */
     Assert(BTreeTupleGetNAtts(itup, rel) ==
            IndexRelationGetNumberOfAttributes(rel));
 
     truncated = index_truncate_tuple(RelationGetDescr(rel), itup, nkeyattrs);
     BTreeTupleSetNAtts(truncated, nkeyattrs);
 
     return truncated;
 }

◆ _bt_page_recyclable()

bool _bt_page_recyclable ( Page page )

Definition at line 903 of file nbtpage.c.

References BTPageOpaqueData::btpo, P_ISDELETED, PageGetSpecialPointer, PageIsNew, RecentGlobalXmin, TransactionIdPrecedes(), and BTPageOpaqueData::xact.

Referenced by _bt_getbuf(), and btvacuumpage().

 {
     BTPageOpaque opaque;
 
     /*
      * It's possible to find an all-zeroes page in an index --- for example, a
      * backend might successfully extend the relation one page and then crash
      * before it is able to make a WAL entry for adding the page. If we find a
      * zeroed page then reclaim it.
      */
     if (PageIsNew(page))
         return true;
 
     /*
      * Otherwise, recycle if deleted and too old to have any processes
      * interested in it.
      */
     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
     if (P_ISDELETED(opaque) &&
         TransactionIdPrecedes(opaque->btpo.xact, RecentGlobalXmin))
         return true;
     return false;
 }

◆ _bt_pagedel()

int _bt_pagedel	(	Relation	rel,
		Buffer	buf
	)

Definition at line 1268 of file nbtpage.c.

References _bt_getbuf(), _bt_mark_page_halfdead(), _bt_mkscankey(), _bt_relbuf(), _bt_search(), _bt_unlink_halfdead_page(), Assert, BT_READ, BT_WRITE, BTPageOpaqueData::btpo_next, BTPageOpaqueData::btpo_prev, BUFFER_LOCK_UNLOCK, BufferGetBlockNumber(), BufferGetPage, CopyIndexTuple(), ereport, errcode(), errhint(), errmsg(), IndexRelationGetNumberOfKeyAttributes, LockBuffer(), LOG, P_FIRSTDATAKEY, P_HIKEY, P_INCOMPLETE_SPLIT, P_ISDELETED, P_ISHALFDEAD, P_ISLEAF, P_ISROOT, P_LEFTMOST, P_RIGHTMOST, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, PageGetSpecialPointer, RelationGetRelationName, and ReleaseBuffer().

Referenced by btvacuumpage().

 {
     int         ndeleted = 0;
     BlockNumber rightsib;
     bool        rightsib_empty;
     Page        page;
     BTPageOpaque opaque;
 
     /*
      * "stack" is a search stack leading (approximately) to the target page.
      * It is initially NULL, but when iterating, we keep it to avoid
      * duplicated search effort.
      *
      * Also, when "stack" is not NULL, we have already checked that the
      * current page is not the right half of an incomplete split, i.e. the
      * left sibling does not have its INCOMPLETE_SPLIT flag set.
      */
     BTStack     stack = NULL;
 
     for (;;)
     {
         page = BufferGetPage(buf);
         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 
         /*
          * Internal pages are never deleted directly, only as part of deleting
          * the whole branch all the way down to leaf level.
          */
         if (!P_ISLEAF(opaque))
         {
             /*
              * Pre-9.4 page deletion only marked internal pages as half-dead,
              * but now we only use that flag on leaf pages. The old algorithm
              * was never supposed to leave half-dead pages in the tree, it was
              * just a transient state, but it was nevertheless possible in
              * error scenarios. We don't know how to deal with them here. They
              * are harmless as far as searches are considered, but inserts
              * into the deleted keyspace could add out-of-order downlinks in
              * the upper levels. Log a notice, hopefully the admin will notice
              * and reindex.
              */
             if (P_ISHALFDEAD(opaque))
                 ereport(LOG,
                         (errcode(ERRCODE_INDEX_CORRUPTED),
                          errmsg("index \"%s\" contains a half-dead internal page",
                                 RelationGetRelationName(rel)),
                          errhint("This can be caused by an interrupted VACUUM in version 9.3 or older, before upgrade. Please REINDEX it.")));
             _bt_relbuf(rel, buf);
             return ndeleted;
         }
 
         /*
          * We can never delete rightmost pages nor root pages.  While at it,
          * check that page is not already deleted and is empty.
          *
          * To keep the algorithm simple, we also never delete an incompletely
          * split page (they should be rare enough that this doesn't make any
          * meaningful difference to disk usage):
          *
          * The INCOMPLETE_SPLIT flag on the page tells us if the page is the
          * left half of an incomplete split, but ensuring that it's not the
          * right half is more complicated.  For that, we have to check that
          * the left sibling doesn't have its INCOMPLETE_SPLIT flag set.  On
          * the first iteration, we temporarily release the lock on the current
          * page, and check the left sibling and also construct a search stack
          * to.  On subsequent iterations, we know we stepped right from a page
          * that passed these tests, so it's OK.
          */
         if (P_RIGHTMOST(opaque) || P_ISROOT(opaque) || P_ISDELETED(opaque) ||
             P_FIRSTDATAKEY(opaque) <= PageGetMaxOffsetNumber(page) ||
             P_INCOMPLETE_SPLIT(opaque))
         {
             /* Should never fail to delete a half-dead page */
             Assert(!P_ISHALFDEAD(opaque));
 
             _bt_relbuf(rel, buf);
             return ndeleted;
         }
 
         /*
          * First, remove downlink pointing to the page (or a parent of the
          * page, if we are going to delete a taller branch), and mark the page
          * as half-dead.
          */
         if (!P_ISHALFDEAD(opaque))
         {
             /*
              * We need an approximate pointer to the page's parent page.  We
              * use the standard search mechanism to search for the page's high
              * key; this will give us a link to either the current parent or
              * someplace to its left (if there are multiple equal high keys).
              *
              * Also check if this is the right-half of an incomplete split
              * (see comment above).
              */
             if (!stack)
             {
                 ScanKey     itup_scankey;
                 ItemId      itemid;
                 IndexTuple  targetkey;
                 Buffer      lbuf;
                 BlockNumber leftsib;
 
                 itemid = PageGetItemId(page, P_HIKEY);
                 targetkey = CopyIndexTuple((IndexTuple) PageGetItem(page, itemid));
 
                 leftsib = opaque->btpo_prev;
 
                 /*
                  * To avoid deadlocks, we'd better drop the leaf page lock
                  * before going further.
                  */
                 LockBuffer(buf, BUFFER_LOCK_UNLOCK);
 
                 /*
                  * Fetch the left sibling, to check that it's not marked with
                  * INCOMPLETE_SPLIT flag.  That would mean that the page
                  * to-be-deleted doesn't have a downlink, and the page
                  * deletion algorithm isn't prepared to handle that.
                  */
                 if (!P_LEFTMOST(opaque))
                 {
                     BTPageOpaque lopaque;
                     Page        lpage;
 
                     lbuf = _bt_getbuf(rel, leftsib, BT_READ);
                     lpage = BufferGetPage(lbuf);
                     lopaque = (BTPageOpaque) PageGetSpecialPointer(lpage);
 
                     /*
                      * If the left sibling is split again by another backend,
                      * after we released the lock, we know that the first
                      * split must have finished, because we don't allow an
                      * incompletely-split page to be split again.  So we don't
                      * need to walk right here.
                      */
                     if (lopaque->btpo_next == BufferGetBlockNumber(buf) &&
                         P_INCOMPLETE_SPLIT(lopaque))
                     {
                         ReleaseBuffer(buf);
                         _bt_relbuf(rel, lbuf);
                         return ndeleted;
                     }
                     _bt_relbuf(rel, lbuf);
                 }
 
                 /* we need an insertion scan key for the search, so build one */
                 itup_scankey = _bt_mkscankey(rel, targetkey);
                 /* find the leftmost leaf page containing this key */
                 stack = _bt_search(rel,
                                    IndexRelationGetNumberOfKeyAttributes(rel),
                                    itup_scankey, false, &lbuf, BT_READ, NULL);
                 /* don't need a pin on the page */
                 _bt_relbuf(rel, lbuf);
 
                 /*
                  * Re-lock the leaf page, and start over, to re-check that the
                  * page can still be deleted.
                  */
                 LockBuffer(buf, BT_WRITE);
                 continue;
             }
 
             if (!_bt_mark_page_halfdead(rel, buf, stack))
             {
                 _bt_relbuf(rel, buf);
                 return ndeleted;
             }
         }
 
         /*
          * Then unlink it from its siblings.  Each call to
          * _bt_unlink_halfdead_page unlinks the topmost page from the branch,
          * making it shallower.  Iterate until the leaf page is gone.
          */
         rightsib_empty = false;
         while (P_ISHALFDEAD(opaque))
         {
             if (!_bt_unlink_halfdead_page(rel, buf, &rightsib_empty))
             {
                 /* _bt_unlink_halfdead_page already released buffer */
                 return ndeleted;
             }
             ndeleted++;
         }
 
         rightsib = opaque->btpo_next;
 
         _bt_relbuf(rel, buf);
 
         /*
          * The page has now been deleted. If its right sibling is completely
          * empty, it's possible that the reason we haven't deleted it earlier
          * is that it was the rightmost child of the parent. Now that we
          * removed the downlink for this page, the right sibling might now be
          * the only child of the parent, and could be removed. It would be
          * picked up by the next vacuum anyway, but might as well try to
          * remove it now, so loop back to process the right sibling.
          */
         if (!rightsib_empty)
             break;
 
         buf = _bt_getbuf(rel, rightsib, BT_WRITE);
     }
 
     return ndeleted;
 }

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ BT_N_KEYS_OFFSET_MASK

◆ BT_READ

◆ BT_RESERVED_OFFSET_MASK

◆ BT_WRITE

◆ BTCommuteStrategyNumber

◆ BTINRANGE_PROC

◆ BTMaxItemSize

◆ BTNProcs

◆ BTORDER_PROC

◆ BTP_DELETED

◆ BTP_HALF_DEAD

◆ BTP_HAS_GARBAGE

◆ BTP_INCOMPLETE_SPLIT

◆ BTP_LEAF

◆ BTP_META

◆ BTP_ROOT

◆ BTP_SPLIT_END

◆ BTPageGetMeta

◆ BTREE_DEFAULT_FILLFACTOR

◆ BTREE_MAGIC

◆ BTREE_METAPAGE

◆ BTREE_MIN_FILLFACTOR

◆ BTREE_MIN_VERSION

◆ BTREE_NONLEAF_FILLFACTOR

◆ BTREE_VERSION

◆ BTreeInnerTupleGetDownLink

◆ BTreeInnerTupleSetDownLink

◆ BTreeTupleGetNAtts

◆ BTreeTupleGetTopParent

◆ BTreeTupleSetNAtts

◆ BTreeTupleSetTopParent

◆ BTScanPosInvalidate

◆ BTScanPosIsPinned

◆ BTScanPosIsValid

◆ BTScanPosUnpin

◆ BTScanPosUnpinIfPinned

◆ BTSORTSUPPORT_PROC

◆ INDEX_ALT_TID_MASK

◆ MAX_BT_CYCLE_ID

◆ P_FIRSTDATAKEY

◆ P_FIRSTKEY

◆ P_HAS_GARBAGE

◆ P_HIKEY

◆ P_IGNORE

◆ P_INCOMPLETE_SPLIT

◆ P_ISDELETED

◆ P_ISHALFDEAD

◆ P_ISLEAF

◆ P_ISMETA

◆ P_ISROOT

◆ P_LEFTMOST

◆ P_NONE

◆ P_RIGHTMOST

◆ SK_BT_DESC

◆ SK_BT_INDOPTION_SHIFT

◆ SK_BT_NULLS_FIRST

◆ SK_BT_REQBKWD

◆ SK_BT_REQFWD

Typedef Documentation

◆ BTArrayKeyInfo

◆ BTCycleId

◆ BTMetaPageData

◆ BTPageOpaque

◆ BTPageOpaqueData

◆ BTScanOpaque

◆ BTScanOpaqueData

◆ BTScanPos

◆ BTScanPosData

◆ BTScanPosItem

◆ BTStack

◆ BTStackData

Function Documentation

◆ _bt_advance_array_keys()

◆ _bt_binsrch()

◆ _bt_check_natts()