#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	BTScanInsertData

struct	BTInsertStateData

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 in metapage */

#define	BTREE_VERSION 4 /* current version number */

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

#define	BTREE_NOVAC_VERSION 3 /* minimal version with all meta fields */

#define	BTMaxItemSize(page)

#define	BTMaxItemSizeNoHeapTid(page)

#define	BTREE_MIN_FILLFACTOR 10

#define	BTREE_DEFAULT_FILLFACTOR 90

#define	BTREE_NONLEAF_FILLFACTOR 70

#define	BTREE_SINGLEVAL_FILLFACTOR 96

#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	BT_HEAP_TID_ATTR 0x1000

#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	BTreeTupleGetHeapTID(itup)

#define	BTreeTupleSetAltHeapTID(itup)

#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)

#define	PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN 2

#define	PROGRESS_BTREE_PHASE_PERFORMSORT_1 3

#define	PROGRESS_BTREE_PHASE_PERFORMSORT_2 4

#define	PROGRESS_BTREE_PHASE_LEAF_LOAD 5

Typedefs
typedef uint16	BTCycleId

typedef struct BTPageOpaqueData	BTPageOpaqueData

typedef BTPageOpaqueData *	BTPageOpaque

typedef struct BTMetaPageData	BTMetaPageData

typedef struct BTStackData	BTStackData

typedef BTStackData *	BTStack

typedef struct BTScanInsertData	BTScanInsertData

typedef BTScanInsertData *	BTScanInsert

typedef struct BTInsertStateData	BTInsertStateData

typedef BTInsertStateData *	BTInsertState

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)

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

OffsetNumber	_bt_findsplitloc (Relation rel, Page page, OffsetNumber newitemoff, Size newitemsz, IndexTuple newitem, bool *newitemonleft)

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)

bool	_bt_heapkeyspace (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, BTScanInsert key, Buffer *bufP, int access, Snapshot snapshot)

Buffer	_bt_moveright (Relation rel, BTScanInsert key, Buffer buf, bool forupdate, BTStack stack, int access, Snapshot snapshot)

OffsetNumber	_bt_binsrch_insert (Relation rel, BTInsertState insertstate)

int32	_bt_compare (Relation rel, BTScanInsert key, 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)

BTScanInsert	_bt_mkscankey (Relation rel, IndexTuple itup)

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)

bool	_bt_checkkeys (IndexScanDesc scan, IndexTuple tuple, int tupnatts, 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)

char *	btbuildphasename (int64 phasenum)

IndexTuple	_bt_truncate (Relation rel, IndexTuple lastleft, IndexTuple firstright, BTScanInsert itup_key)

int	_bt_keep_natts_fast (Relation rel, IndexTuple lastleft, IndexTuple firstright)

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

void	_bt_check_third_page (Relation rel, Relation heap, bool needheaptidspace, Page page, IndexTuple newtup)

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_HEAP_TID_ATTR

#define BT_HEAP_TID_ATTR 0x1000

Definition at line 298 of file nbtree.h.

◆ BT_N_KEYS_OFFSET_MASK

#define BT_N_KEYS_OFFSET_MASK 0x0FFF

Definition at line 297 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 296 of file nbtree.h.

◆ BT_WRITE

#define BT_WRITE BUFFER_LOCK_EXCLUSIVE

Definition at line 403 of file nbtree.h.

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

◆ BTCommuteStrategyNumber

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

Definition at line 374 of file nbtree.h.

Referenced by _bt_compare_scankey_args(), and _bt_fix_scankey_strategy().

◆ BTINRANGE_PROC

#define BTINRANGE_PROC 3

Definition at line 394 of file nbtree.h.

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

◆ BTMaxItemSize

#define BTMaxItemSize ( page )

Value:

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

Definition at line 147 of file nbtree.h.

Referenced by _bt_buildadd(), _bt_check_third_page(), _bt_findinsertloc(), and bt_target_page_check().

◆ BTMaxItemSizeNoHeapTid

#define BTMaxItemSizeNoHeapTid ( page )

Value:

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

Definition at line 153 of file nbtree.h.

Referenced by _bt_check_third_page(), and bt_target_page_check().

◆ BTNProcs

#define BTNProcs 3

Definition at line 395 of file nbtree.h.

Referenced by bthandler().

◆ BTORDER_PROC

#define BTORDER_PROC 1

Definition at line 392 of file nbtree.h.

Referenced by _bt_first(), _bt_mkscankey(), _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_getmeta(), _bt_getroot(), _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 169 of file nbtree.h.

Referenced by _bt_findsplitloc(), and _bt_pagestate().

◆ BTREE_MAGIC

#define BTREE_MAGIC 0x053162 /* magic number in metapage */

Definition at line 132 of file nbtree.h.

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

◆ BTREE_METAPAGE

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

◆ BTREE_MIN_FILLFACTOR

#define BTREE_MIN_FILLFACTOR 10

Definition at line 168 of file nbtree.h.

◆ BTREE_MIN_VERSION

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

Definition at line 134 of file nbtree.h.

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

◆ BTREE_NONLEAF_FILLFACTOR

#define BTREE_NONLEAF_FILLFACTOR 70

Definition at line 170 of file nbtree.h.

Referenced by _bt_findsplitloc(), and _bt_pagestate().

◆ BTREE_NOVAC_VERSION

#define BTREE_NOVAC_VERSION 3 /* minimal version with all meta fields */

Definition at line 135 of file nbtree.h.

Referenced by _bt_cachemetadata(), _bt_check_third_page(), _bt_getroot(), _bt_getrootheight(), _bt_heapkeyspace(), _bt_insertonpg(), _bt_newroot(), _bt_unlink_halfdead_page(), _bt_update_meta_cleanup_info(), _bt_upgrademetapage(), _bt_vacuum_needs_cleanup(), and bt_metap().

◆ BTREE_SINGLEVAL_FILLFACTOR

#define BTREE_SINGLEVAL_FILLFACTOR 96

Definition at line 171 of file nbtree.h.

Referenced by _bt_findsplitloc().

◆ BTREE_VERSION

#define BTREE_VERSION 4 /* current version number */

Definition at line 133 of file nbtree.h.

Referenced by _bt_cachemetadata(), _bt_check_third_page(), _bt_getmeta(), _bt_getroot(), _bt_gettrueroot(), _bt_initmetapage(), and palloc_btree_page().

◆ BTreeInnerTupleGetDownLink

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

Definition at line 301 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 303 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().

◆ BTreeTupleGetHeapTID

#define BTreeTupleGetHeapTID ( itup )

Value:

( \
      (itup)->t_info & INDEX_ALT_TID_MASK && \
      (ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_HEAP_TID_ATTR) != 0 ? \
      ( \
        (ItemPointer) (((char *) (itup) + IndexTupleSize(itup)) - \
                       sizeof(ItemPointerData)) \
      ) \
      : (itup)->t_info & INDEX_ALT_TID_MASK ? NULL : (ItemPointer) &((itup)->t_tid) \
    )

Definition at line 346 of file nbtree.h.

Referenced by _bt_check_natts(), _bt_compare(), _bt_mkscankey(), bt_target_page_check(), and BTreeTupleGetHeapTIDCareful().

◆ BTreeTupleGetNAtts

#define BTreeTupleGetNAtts	(	itup,
		rel
	)

Value:

( \
        (itup)->t_info & INDEX_ALT_TID_MASK ? \
        ( \
            ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_N_KEYS_OFFSET_MASK \
        ) \
        : \
        IndexRelationGetNumberOfAttributes(rel) \
    )

Definition at line 327 of file nbtree.h.

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

◆ BTreeTupleGetTopParent

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

Definition at line 312 of file nbtree.h.

Referenced by _bt_unlink_halfdead_page(), and bt_downlink_missing_check().

◆ BTreeTupleSetAltHeapTID

#define BTreeTupleSetAltHeapTID ( itup )

Value:

do { \
        Assert((itup)->t_info & INDEX_ALT_TID_MASK); \
        ItemPointerSetOffsetNumber(&(itup)->t_tid, \
                                   ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) | BT_HEAP_TID_ATTR); \
    } while(0)

Definition at line 360 of file nbtree.h.

Referenced by _bt_truncate().

◆ BTreeTupleSetNAtts

#define BTreeTupleSetNAtts	(	itup,
		n
	)

Value:

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

Definition at line 336 of file nbtree.h.

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

◆ BTreeTupleSetTopParent

#define BTreeTupleSetTopParent	(	itup,
		blkno
	)

Value:

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

Definition at line 314 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 610 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 587 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 604 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 593 of file nbtree.h.

◆ BTScanPosUnpinIfPinned

#define BTScanPosUnpinIfPinned ( scanpos )

Value:

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

Definition at line 598 of file nbtree.h.

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

◆ BTSORTSUPPORT_PROC

#define BTSORTSUPPORT_PROC 2

Definition at line 393 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 293 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 218 of file nbtree.h.

Referenced by _bt_afternewitemoff(), _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 195 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 196 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(), _bt_stepright(), and bt_check_level_from_leftmost().

◆ P_ISDELETED

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

Definition at line 191 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 193 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 192 of file nbtree.h.

Referenced by _bt_getmeta(), _bt_getroot(), _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 190 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 187 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)

◆ PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN

#define PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN 2

Definition at line 689 of file nbtree.h.

Referenced by _bt_spools_heapscan(), and btbuildphasename().

◆ PROGRESS_BTREE_PHASE_LEAF_LOAD

#define PROGRESS_BTREE_PHASE_LEAF_LOAD 5

Definition at line 692 of file nbtree.h.

Referenced by _bt_leafbuild(), and btbuildphasename().

◆ PROGRESS_BTREE_PHASE_PERFORMSORT_1

#define PROGRESS_BTREE_PHASE_PERFORMSORT_1 3

Definition at line 690 of file nbtree.h.

Referenced by _bt_leafbuild(), and btbuildphasename().

◆ PROGRESS_BTREE_PHASE_PERFORMSORT_2

#define PROGRESS_BTREE_PHASE_PERFORMSORT_2 4

Definition at line 691 of file nbtree.h.

Referenced by _bt_leafbuild(), and btbuildphasename().

◆ SK_BT_DESC

#define SK_BT_DESC (INDOPTION_DESC << SK_BT_INDOPTION_SHIFT)

Definition at line 681 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 680 of file nbtree.h.

Referenced by _bt_fix_scankey_strategy(), and _bt_mkscankey().

◆ SK_BT_NULLS_FIRST

#define SK_BT_NULLS_FIRST (INDOPTION_NULLS_FIRST << SK_BT_INDOPTION_SHIFT)

Definition at line 682 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 679 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 678 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.

◆ BTInsertState

typedef BTInsertStateData* BTInsertState

Definition at line 513 of file nbtree.h.

◆ BTInsertStateData

typedef struct BTInsertStateData BTInsertStateData

◆ BTMetaPageData

typedef struct BTMetaPageData BTMetaPageData

◆ BTPageOpaque

typedef BTPageOpaqueData* BTPageOpaque

Definition at line 68 of file nbtree.h.

◆ BTPageOpaqueData

typedef struct BTPageOpaqueData BTPageOpaqueData

◆ BTScanInsert

typedef BTScanInsertData* BTScanInsert

Definition at line 481 of file nbtree.h.

◆ BTScanInsertData

typedef struct BTScanInsertData BTScanInsertData

◆ BTScanOpaque

typedef BTScanOpaqueData* BTScanOpaque

Definition at line 671 of file nbtree.h.

◆ BTScanOpaqueData

typedef struct BTScanOpaqueData BTScanOpaqueData

◆ BTScanPos

typedef BTScanPosData* BTScanPos

Definition at line 585 of file nbtree.h.

◆ BTScanPosData

typedef struct BTScanPosData BTScanPosData

◆ BTScanPosItem

typedef struct BTScanPosItem BTScanPosItem

◆ BTStack

typedef BTStackData* BTStack

Definition at line 423 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 546 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_insert()

OffsetNumber _bt_binsrch_insert	(	Relation	rel,
		BTInsertState	insertstate
	)

Definition at line 445 of file nbtsearch.c.

References _bt_compare(), Assert, BTInsertStateData::bounds_valid, BTInsertStateData::buf, BufferGetPage, InvalidOffsetNumber, BTInsertStateData::itup_key, sort-test::key, BTInsertStateData::low, BTScanInsertData::nextkey, P_FIRSTDATAKEY, P_ISLEAF, PageGetMaxOffsetNumber, PageGetSpecialPointer, BTInsertStateData::stricthigh, and unlikely.

Referenced by _bt_check_unique(), _bt_findinsertloc(), and bt_rootdescend().

 {
     BTScanInsert key = insertstate->itup_key;
     Page        page;
     BTPageOpaque opaque;
     OffsetNumber low,
                 high,
                 stricthigh;
     int32       result,
                 cmpval;
 
     page = BufferGetPage(insertstate->buf);
     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 
     Assert(P_ISLEAF(opaque));
     Assert(!key->nextkey);
 
     if (!insertstate->bounds_valid)
     {
         /* Start new binary search */
         low = P_FIRSTDATAKEY(opaque);
         high = PageGetMaxOffsetNumber(page);
     }
     else
     {
         /* Restore result of previous binary search against same page */
         low = insertstate->low;
         high = insertstate->stricthigh;
     }
 
     /* If there are no keys on the page, return the first available slot */
     if (unlikely(high < low))
     {
         /* Caller can't reuse bounds */
         insertstate->low = InvalidOffsetNumber;
         insertstate->stricthigh = InvalidOffsetNumber;
         insertstate->bounds_valid = false;
         return low;
     }
 
     /*
      * Binary search to find the first key on the page >= scan key. (nextkey
      * is always false when inserting).
      *
      * The loop invariant is: all slots before 'low' are < scan key, all slots
      * at or after 'high' are >= scan key.  'stricthigh' is > scan key, and is
      * maintained to save additional search effort for caller.
      *
      * We can fall out when high == low.
      */
     if (!insertstate->bounds_valid)
         high++;                 /* establish the loop invariant for high */
     stricthigh = high;          /* high initially strictly higher */
 
     cmpval = 1;                 /* !nextkey 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, key, page, mid);
 
         if (result >= cmpval)
             low = mid + 1;
         else
         {
             high = mid;
             if (result != 0)
                 stricthigh = high;
         }
     }
 
     /*
      * On a leaf page, a binary search always returns the first key >= scan
      * key (at least in !nextkey case), which could be the last slot + 1. This
      * is also the lower bound of cached search.
      *
      * stricthigh may also be the last slot + 1, which prevents caller from
      * using bounds directly, but is still useful to us if we're called a
      * second time with cached bounds (cached low will be < stricthigh when
      * that happens).
      */
     insertstate->low = low;
     insertstate->stricthigh = stricthigh;
     insertstate->bounds_valid = true;
 
     return low;
 }

◆ _bt_check_natts()

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

Definition at line 2382 of file nbtutils.c.

References Assert, BT_N_KEYS_OFFSET_MASK, BTreeTupleGetHeapTID, 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;
     int         tupnatts;
 
     /*
      * 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));
     tupnatts = BTreeTupleGetNAtts(itup, rel);
 
     if (P_ISLEAF(opaque))
     {
         if (offnum >= P_FIRSTDATAKEY(opaque))
         {
             /*
              * Non-pivot tuples currently never use alternative heap TID
              * representation -- even those within heapkeyspace indexes
              */
             if ((itup->t_info & INDEX_ALT_TID_MASK) != 0)
                 return false;
 
             /*
              * Leaf tuples that are not the page high key (non-pivot tuples)
              * should never be truncated.  (Note that tupnatts must have been
              * inferred, rather than coming from an explicit on-disk
              * representation.)
              */
             return tupnatts == natts;
         }
         else
         {
             /*
              * Rightmost page doesn't contain a page high key, so tuple was
              * checked above as ordinary leaf tuple
              */
             Assert(!P_RIGHTMOST(opaque));
 
             /*
              * !heapkeyspace high key tuple contains only key attributes. Note
              * that tupnatts will only have been explicitly represented in
              * !heapkeyspace indexes that happen to have non-key attributes.
              */
             if (!heapkeyspace)
                 return tupnatts == nkeyatts;
 
             /* Use generic heapkeyspace pivot tuple handling */
         }
     }
     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.
              */
             if (heapkeyspace)
                 return tupnatts == 0;
 
             /*
              * 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 tupnatts == 0 ||
                 ((itup->t_info & INDEX_ALT_TID_MASK) == 0 &&
                  ItemPointerGetOffsetNumber(&(itup->t_tid)) == P_HIKEY);
         }
         else
         {
             /*
              * !heapkeyspace downlink tuple with separator key contains only
              * key attributes.  Note that tupnatts will only have been
              * explicitly represented in !heapkeyspace indexes that happen to
              * have non-key attributes.
              */
             if (!heapkeyspace)
                 return tupnatts == nkeyatts;
 
             /* Use generic heapkeyspace pivot tuple handling */
         }
 
     }
 
     /* Handle heapkeyspace pivot tuples (excluding minus infinity items) */
     Assert(heapkeyspace);
 
     /*
      * Explicit representation of the number of attributes is mandatory with
      * heapkeyspace index pivot tuples, regardless of whether or not there are
      * non-key attributes.
      */
     if ((itup->t_info & INDEX_ALT_TID_MASK) == 0)
         return false;
 
     /*
      * Heap TID is a tiebreaker key attribute, so it cannot be untruncated
      * when any other key attribute is truncated
      */
     if (BTreeTupleGetHeapTID(itup) != NULL && tupnatts != nkeyatts)
         return false;
 
     /*
      * Pivot tuple must have at least one untruncated key attribute (minus
      * infinity pivot tuples are the only exception).  Pivot tuples can never
      * represent that there is a value present for a key attribute that
      * exceeds pg_index.indnkeyatts for the index.
      */
     return tupnatts > 0 && tupnatts <= nkeyatts;
 }

◆ _bt_check_third_page()

void _bt_check_third_page	(	Relation	rel,
		Relation	heap,
		bool	needheaptidspace,
		Page	page,
		IndexTuple	newtup
	)

Definition at line 2532 of file nbtutils.c.

References BTMaxItemSize, BTMaxItemSizeNoHeapTid, BTREE_NOVAC_VERSION, BTREE_VERSION, elog, ereport, errcode(), errdetail(), errhint(), errmsg(), ERROR, errtableconstraint(), IndexTupleSize, ItemPointerGetBlockNumber, ItemPointerGetOffsetNumber, MAXALIGN, P_ISLEAF, PageGetSpecialPointer, RelationGetRelationName, and IndexTupleData::t_tid.

Referenced by _bt_buildadd(), and _bt_findinsertloc().

 {
     Size        itemsz;
     BTPageOpaque opaque;
 
     itemsz = MAXALIGN(IndexTupleSize(newtup));
 
     /* Double check item size against limit */
     if (itemsz <= BTMaxItemSize(page))
         return;
 
     /*
      * Tuple is probably too large to fit on page, but it's possible that the
      * index uses version 2 or version 3, or that page is an internal page, in
      * which case a slightly higher limit applies.
      */
     if (!needheaptidspace && itemsz <= BTMaxItemSizeNoHeapTid(page))
         return;
 
     /*
      * Internal page insertions cannot fail here, because that would mean that
      * an earlier leaf level insertion that should have failed didn't
      */
     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
     if (!P_ISLEAF(opaque))
         elog(ERROR, "cannot insert oversized tuple of size %zu on internal page of index \"%s\"",
              itemsz, RelationGetRelationName(rel));
 
     ereport(ERROR,
             (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
              errmsg("index row size %zu exceeds btree version %u maximum %zu for index \"%s\"",
                     itemsz,
                     needheaptidspace ? BTREE_VERSION : BTREE_NOVAC_VERSION,
                     needheaptidspace ? BTMaxItemSize(page) :
                     BTMaxItemSizeNoHeapTid(page),
                     RelationGetRelationName(rel)),
              errdetail("Index row references tuple (%u,%u) in relation \"%s\".",
                        ItemPointerGetBlockNumber(&newtup->t_tid),
                        ItemPointerGetOffsetNumber(&newtup->t_tid),
                        RelationGetRelationName(heap)),
              errhint("Values larger than 1/3 of a buffer page cannot be indexed.\n"
                      "Consider a function index of an MD5 hash of the value, "
                      "or use full text indexing."),
              errtableconstraint(heap, RelationGetRelationName(rel))));
 }

◆ _bt_checkkeys()

bool _bt_checkkeys	(	IndexScanDesc	scan,
		IndexTuple	tuple,
		int	tupnatts,
		ScanDirection	dir,
		bool *	continuescan
	)

Definition at line 1357 of file nbtutils.c.

References _bt_check_rowcompare(), Assert, BTreeTupleGetNAtts, DatumGetBool, FunctionCall2Coll(), index_getattr, IndexScanDescData::indexRelation, sort-test::key, BTScanOpaqueData::keyData, BTScanOpaqueData::numberOfKeys, IndexScanDescData::opaque, 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().

 {
     TupleDesc   tupdesc;
     BTScanOpaque so;
     int         keysz;
     int         ikey;
     ScanKey     key;
 
     Assert(BTreeTupleGetNAtts(tuple, scan->indexRelation) == tupnatts);
 
     *continuescan = true;       /* default assumption */
 
     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;
 
         if (key->sk_attno > tupnatts)
         {
             /*
              * This attribute is truncated (must be high key).  The value for
              * this attribute in the first non-pivot tuple on the page to the
              * right could be any possible value.  Assume that truncated
              * attribute passes the qual.
              */
             Assert(ScanDirectionIsForward(dir));
             continue;
         }
 
         /* row-comparison keys need special processing */
         if (key->sk_flags & SK_ROW_HEADER)
         {
             if (_bt_check_rowcompare(key, tuple, tupnatts, tupdesc, dir,
                                      continuescan))
                 continue;
             return false;
         }
 
         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 false;
         }
 
         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 false;
         }
 
         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 false;
         }
     }
 
     /* If we get here, the tuple passes all index quals. */
     return true;
 }

◆ _bt_checkpage()

void _bt_checkpage	(	Relation	rel,
		Buffer	buf
	)

Definition at line 729 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,
		BTScanInsert	key,
		Page	page,
		OffsetNumber	offnum
	)

Definition at line 559 of file nbtsearch.c.

References _bt_check_natts(), Assert, BTreeTupleGetHeapTID, BTreeTupleGetNAtts, DatumGetInt32, FunctionCall2Coll(), BTScanInsertData::heapkeyspace, i, index_getattr, IndexRelationGetNumberOfKeyAttributes, INVERT_COMPARE_RESULT, ItemPointerCompare(), BTScanInsertData::keysz, Min, P_FIRSTDATAKEY, P_ISLEAF, PageGetItem, PageGetItemId, PageGetSpecialPointer, BTScanInsertData::pivotsearch, RelationGetDescr, BTScanInsertData::scankeys, BTScanInsertData::scantid, 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_binsrch_insert(), _bt_check_unique(), _bt_doinsert(), _bt_findinsertloc(), _bt_moveright(), bt_rootdescend(), invariant_g_offset(), invariant_l_nontarget_offset(), invariant_l_offset(), and invariant_leq_offset().

 {
     TupleDesc   itupdesc = RelationGetDescr(rel);
     BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
     IndexTuple  itup;
     ItemPointer heapTid;
     ScanKey     scankey;
     int         ncmpkey;
     int         ntupatts;
 
     Assert(_bt_check_natts(rel, key->heapkeyspace, page, offnum));
     Assert(key->keysz <= IndexRelationGetNumberOfKeyAttributes(rel));
     Assert(key->heapkeyspace || key->scantid == NULL);
 
     /*
      * 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));
     ntupatts = BTreeTupleGetNAtts(itup, rel);
 
     /*
      * 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).
      */
 
     ncmpkey = Min(ntupatts, key->keysz);
     Assert(key->heapkeyspace || ncmpkey == key->keysz);
     scankey = key->scankeys;
     for (int i = 1; i <= ncmpkey; 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))
                 INVERT_COMPARE_RESULT(result);
         }
 
         /* if the keys are unequal, return the difference */
         if (result != 0)
             return result;
 
         scankey++;
     }
 
     /*
      * All non-truncated attributes (other than heap TID) were found to be
      * equal.  Treat truncated attributes as minus infinity when scankey has a
      * key attribute value that would otherwise be compared directly.
      *
      * Note: it doesn't matter if ntupatts includes non-key attributes;
      * scankey won't, so explicitly excluding non-key attributes isn't
      * necessary.
      */
     if (key->keysz > ntupatts)
         return 1;
 
     /*
      * Use the heap TID attribute and scantid to try to break the tie.  The
      * rules are the same as any other key attribute -- only the
      * representation differs.
      */
     heapTid = BTreeTupleGetHeapTID(itup);
     if (key->scantid == NULL)
     {
         /*
          * Most searches have a scankey that is considered greater than a
          * truncated pivot tuple if and when the scankey has equal values for
          * attributes up to and including the least significant untruncated
          * attribute in tuple.
          *
          * For example, if an index has the minimum two attributes (single
          * user key attribute, plus heap TID attribute), and a page's high key
          * is ('foo', -inf), and scankey is ('foo', <omitted>), the search
          * will not descend to the page to the left.  The search will descend
          * right instead.  The truncated attribute in pivot tuple means that
          * all non-pivot tuples on the page to the left are strictly < 'foo',
          * so it isn't necessary to descend left.  In other words, search
          * doesn't have to descend left because it isn't interested in a match
          * that has a heap TID value of -inf.
          *
          * However, some searches (pivotsearch searches) actually require that
          * we descend left when this happens.  -inf is treated as a possible
          * match for omitted scankey attribute(s).  This is needed by page
          * deletion, which must re-find leaf pages that are targets for
          * deletion using their high keys.
          *
          * Note: the heap TID part of the test ensures that scankey is being
          * compared to a pivot tuple with one or more truncated key
          * attributes.
          *
          * Note: pg_upgrade'd !heapkeyspace indexes must always descend to the
          * left here, since they have no heap TID attribute (and cannot have
          * any -inf key values in any case, since truncation can only remove
          * non-key attributes).  !heapkeyspace searches must always be
          * prepared to deal with matches on both sides of the pivot once the
          * leaf level is reached.
          */
         if (key->heapkeyspace && !key->pivotsearch &&
             key->keysz == ntupatts && heapTid == NULL)
             return 1;
 
         /* All provided scankey arguments found to be equal */
         return 0;
     }
 
     /*
      * Treat truncated heap TID as minus infinity, since scankey has a key
      * attribute value (scantid) that would otherwise be compared directly
      */
     Assert(key->keysz == IndexRelationGetNumberOfKeyAttributes(rel));
     if (heapTid == NULL)
         return 1;
 
     Assert(ntupatts >= IndexRelationGetNumberOfKeyAttributes(rel));
     return ItemPointerCompare(key->scantid, heapTid);
 }

◆ _bt_delitems_delete()

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

Definition at line 1096 of file nbtpage.c.

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

Referenced by _bt_vacuum_one_page().

 {
     Page        page = BufferGetPage(buf);
     BTPageOpaque opaque;
     TransactionId latestRemovedXid = InvalidTransactionId;
 
     /* Shouldn't be called unless there's something to do */
     Assert(nitems > 0);
 
     if (XLogStandbyInfoActive() && RelationNeedsWAL(rel))
         latestRemovedXid =
             index_compute_xid_horizon_for_tuples(rel, heapRel, buf,
                                                  itemnos, nitems);
 
     /* 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.latestRemovedXid = latestRemovedXid;
         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 1023 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 79 of file nbtinsert.c.

References _bt_check_unique(), _bt_checkpage(), _bt_compare(), _bt_findinsertloc(), _bt_freestack(), _bt_insertonpg(), _bt_mkscankey(), _bt_relbuf(), _bt_search(), BTScanInsertData::anynullkeys, Assert, BTInsertStateData::bounds_valid, BT_WRITE, buf, BTInsertStateData::buf, BufferGetPage, CheckForSerializableConflictIn(), ConditionalLockBuffer(), BTScanInsertData::heapkeyspace, IndexTupleSize, InvalidBlockNumber, InvalidBuffer, BTInsertStateData::itemsz, BTInsertStateData::itup, BTInsertStateData::itup_key, MAXALIGN, P_FIRSTDATAKEY, P_IGNORE, P_INCOMPLETE_SPLIT, P_ISLEAF, P_RIGHTMOST, PageGetFreeSpace(), PageGetMaxOffsetNumber, PageGetSpecialPointer, pfree(), ReadBuffer(), RelationGetTargetBlock, RelationSetTargetBlock, ReleaseBuffer(), BTScanInsertData::scantid, SpeculativeInsertionWait(), IndexTupleData::t_tid, TransactionIdIsValid, UNIQUE_CHECK_EXISTING, UNIQUE_CHECK_NO, XactLockTableWait(), and XLTW_InsertIndex.

Referenced by btinsert().

 {
     bool        is_unique = false;
     BTInsertStateData insertstate;
     BTScanInsert itup_key;
     BTStack     stack = NULL;
     Buffer      buf;
     bool        fastpath;
     bool        checkingunique = (checkUnique != UNIQUE_CHECK_NO);
 
     /* we need an insertion scan key to do our search, so build one */
     itup_key = _bt_mkscankey(rel, itup);
 
     if (checkingunique)
     {
         if (!itup_key->anynullkeys)
         {
             /* No (heapkeyspace) scantid until uniqueness established */
             itup_key->scantid = NULL;
         }
         else
         {
             /*
              * Scan key for new tuple contains NULL key values.  Bypass
              * checkingunique steps.  They are unnecessary because core code
              * considers NULL unequal to every value, including NULL.
              *
              * This optimization avoids O(N^2) behavior within the
              * _bt_findinsertloc() heapkeyspace path when a unique index has a
              * large number of "duplicates" with NULL key values.
              */
             checkingunique = false;
             /* Tuple is unique in the sense that core code cares about */
             Assert(checkUnique != UNIQUE_CHECK_EXISTING);
             is_unique = true;
         }
     }
 
     /*
      * Fill in the BTInsertState working area, to track the current page and
      * position within the page to insert on
      */
     insertstate.itup = itup;
     /* PageAddItem will MAXALIGN(), but be consistent */
     insertstate.itemsz = MAXALIGN(IndexTupleSize(itup));
     insertstate.itup_key = itup_key;
     insertstate.bounds_valid = false;
     insertstate.buf = InvalidBuffer;
 
     /*
      * 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;
     if (RelationGetTargetBlock(rel) != InvalidBlockNumber)
     {
         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);
 
             /*
              * 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) > insertstate.itemsz) &&
                 PageGetMaxOffsetNumber(page) >= P_FIRSTDATAKEY(lpageop) &&
                 _bt_compare(rel, itup_key, 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.  Buffer returned by
          * _bt_search() is locked in exclusive mode.
          */
         stack = _bt_search(rel, itup_key, &buf, BT_WRITE, NULL);
     }
 
     insertstate.buf = buf;
     buf = InvalidBuffer;        /* insertstate.buf now owns the buffer */
 
     /*
      * 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 first page the value could be on, with omitted/-inf value for the
      * implicit heap TID tiebreaker attribute.  Any other would-be inserter of
      * the same key must acquire a write lock on the same 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_findinsertloc.)
      *
      * 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 (checkingunique)
     {
         TransactionId xwait;
         uint32      speculativeToken;
 
         xwait = _bt_check_unique(rel, &insertstate, heapRel, checkUnique,
                                  &is_unique, &speculativeToken);
 
         if (TransactionIdIsValid(xwait))
         {
             /* Have to wait for the other guy ... */
             _bt_relbuf(rel, insertstate.buf);
             insertstate.buf = InvalidBuffer;
 
             /*
              * 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;
         }
 
         /* Uniqueness is established -- restore heap tid as scantid */
         if (itup_key->heapkeyspace)
             itup_key->scantid = &itup->t_tid;
     }
 
     if (checkUnique != UNIQUE_CHECK_EXISTING)
     {
         OffsetNumber newitemoff;
 
         /*
          * The only conflict predicate locking cares about for indexes is when
          * an index tuple insert conflicts with an existing lock.  We don't
          * know the actual page we're going to insert on for sure just yet in
          * checkingunique and !heapkeyspace cases, but it's okay to use the
          * first page the value could be on (with scantid omitted) instead.
          */
         CheckForSerializableConflictIn(rel, NULL, insertstate.buf);
 
         /*
          * Do the insertion.  Note that insertstate contains cached binary
          * search bounds established within _bt_check_unique when insertion is
          * checkingunique.
          */
         newitemoff = _bt_findinsertloc(rel, &insertstate, checkingunique,
                                        stack, heapRel);
         _bt_insertonpg(rel, itup_key, insertstate.buf, InvalidBuffer, stack,
                        itup, newitemoff, false);
     }
     else
     {
         /* just release the buffer */
         _bt_relbuf(rel, insertstate.buf);
     }
 
     /* be tidy */
     if (stack)
         _bt_freestack(stack);
     pfree(itup_key);
 
     return is_unique;
 }

◆ _bt_end_vacuum()

void _bt_end_vacuum ( Relation rel )

Definition at line 1950 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 1978 of file nbtutils.c.

References _bt_end_vacuum(), and DatumGetPointer.

Referenced by btbulkdelete().

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

◆ _bt_findsplitloc()

OffsetNumber _bt_findsplitloc	(	Relation	rel,
		Page	page,
		OffsetNumber	newitemoff,
		Size	newitemsz,
		IndexTuple	newitem,
		bool *	newitemonleft
	)

Definition at line 127 of file nbtsplitloc.c.

References _bt_afternewitemoff(), _bt_bestsplitloc(), _bt_deltasortsplits(), _bt_recsplitloc(), _bt_strategy(), Assert, BTREE_DEFAULT_FILLFACTOR, BTREE_NONLEAF_FILLFACTOR, BTREE_SINGLEVAL_FILLFACTOR, elog, ERROR, SplitPoint::firstoldonright, i, IndexRelationGetNumberOfKeyAttributes, FindSplitData::interval, FindSplitData::is_leaf, FindSplitData::is_rightmost, ItemIdGetLength, FindSplitData::leftspace, Max, MAX_INTERNAL_INTERVAL, MAX_LEAF_INTERVAL, MAXALIGN, FindSplitData::maxsplits, Min, FindSplitData::minfirstrightsz, FindSplitData::newitem, FindSplitData::newitemoff, SplitPoint::newitemonleft, FindSplitData::newitemsz, FindSplitData::nsplits, OffsetNumberNext, FindSplitData::olddataitemstotal, P_FIRSTDATAKEY, P_HIKEY, P_ISLEAF, P_RIGHTMOST, FindSplitData::page, PageGetExactFreeSpace(), PageGetItemId, PageGetMaxOffsetNumber, PageGetPageSize, PageGetSpecialPointer, palloc(), pfree(), FindSplitData::rel, RelationGetFillFactor, RelationGetRelationName, FindSplitData::rightspace, SIZE_MAX, SizeOfPageHeaderData, SPLIT_DEFAULT, SPLIT_MANY_DUPLICATES, SPLIT_SINGLE_VALUE, and FindSplitData::splits.

Referenced by _bt_split().

 {
     BTPageOpaque opaque;
     int         leftspace,
                 rightspace,
                 olddataitemstotal,
                 olddataitemstoleft,
                 perfectpenalty,
                 leaffillfactor;
     FindSplitData state;
     FindSplitStrat strategy;
     ItemId      itemid;
     OffsetNumber offnum,
                 maxoff,
                 foundfirstright;
     double      fillfactormult;
     bool        usemult;
     SplitPoint  leftpage,
                 rightpage;
 
     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
     maxoff = PageGetMaxOffsetNumber(page);
 
     /* Total free space available on a btree page, after fixed overhead */
     leftspace = rightspace =
         PageGetPageSize(page) - SizeOfPageHeaderData -
         MAXALIGN(sizeof(BTPageOpaqueData));
 
     /* The right page will have the same high key as the old page */
     if (!P_RIGHTMOST(opaque))
     {
         itemid = PageGetItemId(page, P_HIKEY);
         rightspace -= (int) (MAXALIGN(ItemIdGetLength(itemid)) +
                              sizeof(ItemIdData));
     }
 
     /* Count up total space in data items before actually scanning 'em */
     olddataitemstotal = rightspace - (int) PageGetExactFreeSpace(page);
     leaffillfactor = RelationGetFillFactor(rel, BTREE_DEFAULT_FILLFACTOR);
 
     /* Passed-in newitemsz is MAXALIGNED but does not include line pointer */
     newitemsz += sizeof(ItemIdData);
     state.rel = rel;
     state.page = page;
     state.newitem = newitem;
     state.newitemsz = newitemsz;
     state.is_leaf = P_ISLEAF(opaque);
     state.is_rightmost = P_RIGHTMOST(opaque);
     state.leftspace = leftspace;
     state.rightspace = rightspace;
     state.olddataitemstotal = olddataitemstotal;
     state.minfirstrightsz = SIZE_MAX;
     state.newitemoff = newitemoff;
 
     /*
      * maxsplits should never exceed maxoff because there will be at most as
      * many candidate split points as there are points _between_ tuples, once
      * you imagine that the new item is already on the original page (the
      * final number of splits may be slightly lower because not all points
      * between tuples will be legal).
      */
     state.maxsplits = maxoff;
     state.splits = palloc(sizeof(SplitPoint) * state.maxsplits);
     state.nsplits = 0;
 
     /*
      * Scan through the data items and calculate space usage for a split at
      * each possible position
      */
     olddataitemstoleft = 0;
 
     for (offnum = P_FIRSTDATAKEY(opaque);
          offnum <= maxoff;
          offnum = OffsetNumberNext(offnum))
     {
         Size        itemsz;
 
         itemid = PageGetItemId(page, offnum);
         itemsz = MAXALIGN(ItemIdGetLength(itemid)) + sizeof(ItemIdData);
 
         /*
          * When item offset number is not newitemoff, neither side of the
          * split can be newitem.  Record a split after the previous data item
          * from original page, but before the current data item from original
          * page. (_bt_recsplitloc() will reject the split when there are no
          * previous items, which we rely on.)
          */
         if (offnum < newitemoff)
             _bt_recsplitloc(&state, offnum, false, olddataitemstoleft, itemsz);
         else if (offnum > newitemoff)
             _bt_recsplitloc(&state, offnum, true, olddataitemstoleft, itemsz);
         else
         {
             /*
              * Record a split after all "offnum < newitemoff" original page
              * data items, but before newitem
              */
             _bt_recsplitloc(&state, offnum, false, olddataitemstoleft, itemsz);
 
             /*
              * Record a split after newitem, but before data item from
              * original page at offset newitemoff/current offset
              */
             _bt_recsplitloc(&state, offnum, true, olddataitemstoleft, itemsz);
         }
 
         olddataitemstoleft += itemsz;
     }
 
     /*
      * Record a split after all original page data items, but before newitem.
      * (Though only when it's possible that newitem will end up alone on new
      * right page.)
      */
     Assert(olddataitemstoleft == olddataitemstotal);
     if (newitemoff > maxoff)
         _bt_recsplitloc(&state, newitemoff, false, olddataitemstotal, 0);
 
     /*
      * I believe it is not possible to fail to find a feasible split, but just
      * in case ...
      */
     if (state.nsplits == 0)
         elog(ERROR, "could not find a feasible split point for index \"%s\"",
              RelationGetRelationName(rel));
 
     /*
      * Start search for a split point among list of legal split points.  Give
      * primary consideration to equalizing available free space in each half
      * of the split initially (start with default strategy), while applying
      * rightmost and split-after-new-item optimizations where appropriate.
      * Either of the two other fallback strategies may be required for cases
      * with a large number of duplicates around the original/space-optimal
      * split point.
      *
      * Default strategy gives some weight to suffix truncation in deciding a
      * split point on leaf pages.  It attempts to select a split point where a
      * distinguishing attribute appears earlier in the new high key for the
      * left side of the split, in order to maximize the number of trailing
      * attributes that can be truncated away.  Only candidate split points
      * that imply an acceptable balance of free space on each side are
      * considered.
      */
     if (!state.is_leaf)
     {
         /* fillfactormult only used on rightmost page */
         usemult = state.is_rightmost;
         fillfactormult = BTREE_NONLEAF_FILLFACTOR / 100.0;
     }
     else if (state.is_rightmost)
     {
         /* Rightmost leaf page --  fillfactormult always used */
         usemult = true;
         fillfactormult = leaffillfactor / 100.0;
     }
     else if (_bt_afternewitemoff(&state, maxoff, leaffillfactor, &usemult))
     {
         /*
          * New item inserted at rightmost point among a localized grouping on
          * a leaf page -- apply "split after new item" optimization, either by
          * applying leaf fillfactor multiplier, or by choosing the exact split
          * point that leaves the new item as last on the left. (usemult is set
          * for us.)
          */
         if (usemult)
         {
             /* fillfactormult should be set based on leaf fillfactor */
             fillfactormult = leaffillfactor / 100.0;
         }
         else
         {
             /* find precise split point after newitemoff */
             for (int i = 0; i < state.nsplits; i++)
             {
                 SplitPoint *split = state.splits + i;
 
                 if (split->newitemonleft &&
                     newitemoff == split->firstoldonright)
                 {
                     pfree(state.splits);
                     *newitemonleft = true;
                     return newitemoff;
                 }
             }
 
             /*
              * Cannot legally split after newitemoff; proceed with split
              * without using fillfactor multiplier.  This is defensive, and
              * should never be needed in practice.
              */
             fillfactormult = 0.50;
         }
     }
     else
     {
         /* Other leaf page.  50:50 page split. */
         usemult = false;
         /* fillfactormult not used, but be tidy */
         fillfactormult = 0.50;
     }
 
     /*
      * Set an initial limit on the split interval/number of candidate split
      * points as appropriate.  The "Prefix B-Trees" paper refers to this as
      * sigma l for leaf splits and sigma b for internal ("branch") splits.
      * It's hard to provide a theoretical justification for the initial size
      * of the split interval, though it's clear that a small split interval
      * makes suffix truncation much more effective without noticeably
      * affecting space utilization over time.
      */
     state.interval = Min(Max(1, state.nsplits * 0.05),
                          state.is_leaf ? MAX_LEAF_INTERVAL :
                          MAX_INTERNAL_INTERVAL);
 
     /*
      * Save leftmost and rightmost splits for page before original ordinal
      * sort order is lost by delta/fillfactormult sort
      */
     leftpage = state.splits[0];
     rightpage = state.splits[state.nsplits - 1];
 
     /* Give split points a fillfactormult-wise delta, and sort on deltas */
     _bt_deltasortsplits(&state, fillfactormult, usemult);
 
     /*
      * Determine if default strategy/split interval will produce a
      * sufficiently distinguishing split, or if we should change strategies.
      * Alternative strategies change the range of split points that are
      * considered acceptable (split interval), and possibly change
      * fillfactormult, in order to deal with pages with a large number of
      * duplicates gracefully.
      *
      * Pass low and high splits for the entire page (actually, they're for an
      * imaginary version of the page that includes newitem).  These are used
      * when the initial split interval encloses split points that are full of
      * duplicates, and we need to consider if it's even possible to avoid
      * appending a heap TID.
      */
     perfectpenalty = _bt_strategy(&state, &leftpage, &rightpage, &strategy);
 
     if (strategy == SPLIT_DEFAULT)
     {
         /*
          * Default strategy worked out (always works out with internal page).
          * Original split interval still stands.
          */
     }
 
     /*
      * Many duplicates strategy is used when a heap TID would otherwise be
      * appended, but the page isn't completely full of logical duplicates.
      *
      * The split interval is widened to include all legal candidate split
      * points.  There might be a few as two distinct values in the whole-page
      * split interval, though it's also possible that most of the values on
      * the page are unique.  The final split point will either be to the
      * immediate left or to the immediate right of the group of duplicate
      * tuples that enclose the first/delta-optimal split point (perfect
      * penalty was set so that the lowest delta split point that avoids
      * appending a heap TID will be chosen).  Maximizing the number of
      * attributes that can be truncated away is not a goal of the many
      * duplicates strategy.
      *
      * Single value strategy is used when it is impossible to avoid appending
      * a heap TID.  It arranges to leave the left page very full.  This
      * maximizes space utilization in cases where tuples with the same
      * attribute values span many pages.  Newly inserted duplicates will tend
      * to have higher heap TID values, so we'll end up splitting to the right
      * consistently.  (Single value strategy is harmless though not
      * particularly useful with !heapkeyspace indexes.)
      */
     else if (strategy == SPLIT_MANY_DUPLICATES)
     {
         Assert(state.is_leaf);
         /* Shouldn't try to truncate away extra user attributes */
         Assert(perfectpenalty ==
                IndexRelationGetNumberOfKeyAttributes(state.rel));
         /* No need to resort splits -- no change in fillfactormult/deltas */
         state.interval = state.nsplits;
     }
     else if (strategy == SPLIT_SINGLE_VALUE)
     {
         Assert(state.is_leaf);
         /* Split near the end of the page */
         usemult = true;
         fillfactormult = BTREE_SINGLEVAL_FILLFACTOR / 100.0;
         /* Resort split points with new delta */
         _bt_deltasortsplits(&state, fillfactormult, usemult);
         /* Appending a heap TID is unavoidable, so interval of 1 is fine */
         state.interval = 1;
     }
 
     /*
      * Search among acceptable split points (using final split interval) for
      * the entry that has the lowest penalty, and is therefore expected to
      * maximize fan-out.  Sets *newitemonleft for us.
      */
     foundfirstright = _bt_bestsplitloc(&state, perfectpenalty, newitemonleft,
                                        strategy);
     pfree(state.splits);
 
     return foundfirstright;
 }

◆ _bt_finish_split()

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

Definition at line 1854 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_getstackbuf(), _bt_moveright(), and _bt_stepright().

 {
     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 746 of file nbtsearch.c.

References _bt_binsrch(), _bt_drop_lock_and_maybe_pin(), _bt_endpoint(), _bt_freestack(), _bt_heapkeyspace(), _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(), IndexScanDescData::xs_heaptid, 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;
     BTScanInsertData inskey;
     ScanKey     startKeys[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 using the keys
      * identified by startKeys[].  (Remaining insertion scankey fields are
      * initialized after initial-positioning strategy is finalized.)
      */
     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(inskey.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(inskey.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(inskey.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(inskey.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;
     }
 
     /* Initialize remaining insertion scan key fields */
     inskey.heapkeyspace = _bt_heapkeyspace(rel);
     inskey.anynullkeys = false; /* unused */
     inskey.nextkey = nextkey;
     inskey.pivotsearch = false;
     inskey.scantid = NULL;
     inskey.keysz = keysCount;
 
     /*
      * Use the manufactured insertion scan key to descend the tree and
      * position ourselves on the target leaf page.
      */
     stack = _bt_search(rel, &inskey, &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, &inskey, buf);
 
     /*
      * 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_heaptid = currItem->heapTid;
     if (scan->xs_want_itup)
         scan->xs_itup = (IndexTuple) (so->currTuples + currItem->tupleOffset);
 
     return true;
 }

◆ _bt_freestack()

void _bt_freestack ( BTStack stack )

Definition at line 163 of file nbtutils.c.

References BTStackData::bts_parent, and pfree().

Referenced by _bt_doinsert(), _bt_first(), and bt_rootdescend().

 {
     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 2064 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 796 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_heapkeyspace(), _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, in case they have snapshots older
                      * than btpo.xact.  This can only apply if the page does
                      * have a valid btpo.xact value, ie not if it's new.  (We
                      * must check that because an all-zero page has no special
                      * space.)
                      */
                     if (XLogStandbyInfoActive() && RelationNeedsWAL(rel) &&
                         !PageIsNew(page))
                     {
                         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 291 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_NOVAC_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);
 
             Assert(metad->btm_version >= BTREE_NOVAC_VERSION);
             md.version = metad->btm_version;
             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 635 of file nbtpage.c.

References _bt_cachemetadata(), _bt_getbuf(), _bt_getmeta(), _bt_relbuf(), Assert, BT_READ, BTMetaPageData::btm_fastlevel, BTMetaPageData::btm_fastroot, BTMetaPageData::btm_magic, BTMetaPageData::btm_root, BTMetaPageData::btm_version, BTREE_MAGIC, BTREE_METAPAGE, BTREE_NOVAC_VERSION, P_NONE, and RelationData::rd_amcache.

Referenced by _bt_insertonpg(), and get_relation_info().

 {
     BTMetaPageData *metad;
 
     if (rel->rd_amcache == NULL)
     {
         Buffer      metabuf;
 
         metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
         metad = _bt_getmeta(rel, metabuf);
 
         /*
          * 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);
         /* We shouldn't have cached it if any of these fail */
         Assert(metad->btm_magic == BTREE_MAGIC);
         Assert(metad->btm_version >= BTREE_NOVAC_VERSION);
         Assert(metad->btm_fastroot != P_NONE);
         _bt_relbuf(rel, metabuf);
     }
 
     /* Get cached page */
     metad = (BTMetaPageData *) rel->rd_amcache;
 
     return metad->btm_fastlevel;
 }

◆ _bt_getstackbuf()

Buffer _bt_getstackbuf	(	Relation	rel,
		BTStack	stack
	)

Definition at line 1914 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, BT_WRITE);
         page = BufferGetPage(buf);
         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 
         if (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 539 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_heapkeyspace()

bool _bt_heapkeyspace ( Relation rel )

Definition at line 684 of file nbtpage.c.

References _bt_cachemetadata(), _bt_getbuf(), _bt_getmeta(), _bt_relbuf(), Assert, BT_READ, BTMetaPageData::btm_fastroot, BTMetaPageData::btm_magic, BTMetaPageData::btm_root, BTMetaPageData::btm_version, BTREE_MAGIC, BTREE_METAPAGE, BTREE_NOVAC_VERSION, P_NONE, and RelationData::rd_amcache.

Referenced by _bt_first(), _bt_mkscankey(), and bt_index_check_internal().

 {
     BTMetaPageData *metad;
 
     if (rel->rd_amcache == NULL)
     {
         Buffer      metabuf;
 
         metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_READ);
         metad = _bt_getmeta(rel, metabuf);
 
         /*
          * If there's no root page yet, _bt_getroot() doesn't expect a cache
          * to be made, so just stop here.  (XXX perhaps _bt_getroot() should
          * be changed to allow this case.)
          */
         if (metad->btm_root == P_NONE)
         {
             uint32      btm_version = metad->btm_version;
 
             _bt_relbuf(rel, metabuf);
             return btm_version > BTREE_NOVAC_VERSION;
         }
 
         /*
          * Cache the metapage data for next time
          */
         _bt_cachemetadata(rel, metad);
         /* We shouldn't have cached it if any of these fail */
         Assert(metad->btm_magic == BTREE_MAGIC);
         Assert(metad->btm_version >= BTREE_NOVAC_VERSION);
         Assert(metad->btm_fastroot != P_NONE);
         _bt_relbuf(rel, metabuf);
     }
 
     /* Get cached page */
     metad = (BTMetaPageData *) rel->rd_amcache;
 
     return metad->btm_version > BTREE_NOVAC_VERSION;
 }

◆ _bt_initmetapage()

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

Definition at line 51 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_keep_natts_fast()

int _bt_keep_natts_fast	(	Relation	rel,
		IndexTuple	lastleft,
		IndexTuple	firstright
	)

Definition at line 2335 of file nbtutils.c.

References attnum, datumIsEqual(), index_getattr, IndexRelationGetNumberOfKeyAttributes, RelationGetDescr, and TupleDescAttr.

Referenced by _bt_afternewitemoff(), _bt_split_penalty(), and _bt_strategy().

 {
     TupleDesc   itupdesc = RelationGetDescr(rel);
     int         keysz = IndexRelationGetNumberOfKeyAttributes(rel);
     int         keepnatts;
 
     keepnatts = 1;
     for (int attnum = 1; attnum <= keysz; attnum++)
     {
         Datum       datum1,
                     datum2;
         bool        isNull1,
                     isNull2;
         Form_pg_attribute att;
 
         datum1 = index_getattr(lastleft, attnum, itupdesc, &isNull1);
         datum2 = index_getattr(firstright, attnum, itupdesc, &isNull2);
         att = TupleDescAttr(itupdesc, attnum - 1);
 
         if (isNull1 != isNull2)
             break;
 
         if (!isNull1 &&
             !datumIsEqual(datum1, datum2, att->attbyval, att->attlen))
             break;
 
         keepnatts++;
     }
 
     return keepnatts;
 }

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ BT_HEAP_TID_ATTR

◆ BT_N_KEYS_OFFSET_MASK

◆ BT_READ

◆ BT_RESERVED_OFFSET_MASK

◆ BT_WRITE

◆ BTCommuteStrategyNumber

◆ BTINRANGE_PROC

◆ BTMaxItemSize

◆ BTMaxItemSizeNoHeapTid

◆ 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_NOVAC_VERSION

◆ BTREE_SINGLEVAL_FILLFACTOR

◆ BTREE_VERSION

◆ BTreeInnerTupleGetDownLink

◆ BTreeInnerTupleSetDownLink

◆ BTreeTupleGetHeapTID

◆ BTreeTupleGetNAtts

◆ BTreeTupleGetTopParent

◆ BTreeTupleSetAltHeapTID

◆ 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

◆ PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN

◆ PROGRESS_BTREE_PHASE_LEAF_LOAD

◆ PROGRESS_BTREE_PHASE_PERFORMSORT_1

◆ PROGRESS_BTREE_PHASE_PERFORMSORT_2

◆ SK_BT_DESC

◆ SK_BT_INDOPTION_SHIFT

◆ SK_BT_NULLS_FIRST

◆ SK_BT_REQBKWD

◆ SK_BT_REQFWD

Typedef Documentation

◆ BTArrayKeyInfo

◆ BTCycleId

◆ BTInsertState

◆ BTInsertStateData

◆ BTMetaPageData

◆ BTPageOpaque