#include "access/amapi.h"
#include "access/itup.h"
#include "access/sdir.h"
#include "access/tableam.h"
#include "access/xlogreader.h"
#include "catalog/pg_am_d.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	BTDeletedPageData

struct	BTPendingFSM

struct	BTVacState

struct	BTStackData

struct	BTScanInsertData

struct	BTInsertStateData

struct	BTDedupInterval

struct	BTDedupStateData

struct	BTVacuumPostingData

struct	BTScanPosItem

struct	BTScanPosData

struct	BTArrayKeyInfo

struct	BTScanOpaqueData

struct	BTOptions

Macros
#define	BTPageGetOpaque(page) ((BTPageOpaque) PageGetSpecialPointer(page))

#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 (deprecated) */

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

#define	BTP_HAS_FULLXID (1 << 8) /* contains BTDeletedPageData */

#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 /* minimum supported version */

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

#define	BTMaxItemSize(page)

#define	BTMaxItemSizeNoHeapTid(page)

#define	MaxTIDsPerBTreePage

#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_HAS_FULLXID(opaque) (((opaque)->btpo_flags & BTP_HAS_FULLXID) != 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_OFFSET_MASK 0x0FFF

#define	BT_STATUS_OFFSET_MASK 0xF000

#define	BT_PIVOT_HEAP_TID_ATTR 0x1000

#define	BT_IS_POSTING 0x2000

#define	BTreeTupleGetNAtts(itup, rel)

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

#define	BTORDER_PROC 1

#define	BTSORTSUPPORT_PROC 2

#define	BTINRANGE_PROC 3

#define	BTEQUALIMAGE_PROC 4

#define	BTOPTIONS_PROC 5

#define	BTNProcs 5

#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	BTGetFillFactor(relation)

#define	BTGetTargetPageFreeSpace(relation) (BLCKSZ * (100 - BTGetFillFactor(relation)) / 100)

#define	BTGetDeduplicateItems(relation)

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

typedef struct BTPendingFSM	BTPendingFSM

typedef struct BTVacState	BTVacState

typedef struct BTStackData	BTStackData

typedef BTStackData *	BTStack

typedef struct BTScanInsertData	BTScanInsertData

typedef BTScanInsertData *	BTScanInsert

typedef struct BTInsertStateData	BTInsertStateData

typedef BTInsertStateData *	BTInsertState

typedef struct BTDedupInterval	BTDedupInterval

typedef struct BTDedupStateData	BTDedupStateData

typedef BTDedupStateData *	BTDedupState

typedef struct BTVacuumPostingData	BTVacuumPostingData

typedef BTVacuumPostingData *	BTVacuumPosting

typedef struct BTScanPosItem	BTScanPosItem

typedef struct BTScanPosData	BTScanPosData

typedef BTScanPosData *	BTScanPos

typedef struct BTArrayKeyInfo	BTArrayKeyInfo

typedef struct BTScanOpaqueData	BTScanOpaqueData

typedef BTScanOpaqueData *	BTScanOpaque

typedef struct BTOptions	BTOptions

Functions
static void	BTPageSetDeleted (Page page, FullTransactionId safexid)

static FullTransactionId	BTPageGetDeleteXid (Page page)

static bool	BTPageIsRecyclable (Page page, Relation heaprel)

	StaticAssertDecl (BT_OFFSET_MASK >=INDEX_MAX_KEYS, "BT_OFFSET_MASK can't fit INDEX_MAX_KEYS")

static bool	BTreeTupleIsPivot (IndexTuple itup)

static bool	BTreeTupleIsPosting (IndexTuple itup)

static void	BTreeTupleSetPosting (IndexTuple itup, uint16 nhtids, int postingoffset)

static uint16	BTreeTupleGetNPosting (IndexTuple posting)

static uint32	BTreeTupleGetPostingOffset (IndexTuple posting)

static ItemPointer	BTreeTupleGetPosting (IndexTuple posting)

static ItemPointer	BTreeTupleGetPostingN (IndexTuple posting, int n)

static BlockNumber	BTreeTupleGetDownLink (IndexTuple pivot)

static void	BTreeTupleSetDownLink (IndexTuple pivot, BlockNumber blkno)

static void	BTreeTupleSetNAtts (IndexTuple itup, uint16 nkeyatts, bool heaptid)

static BlockNumber	BTreeTupleGetTopParent (IndexTuple leafhikey)

static void	BTreeTupleSetTopParent (IndexTuple leafhikey, BlockNumber blkno)

static ItemPointer	BTreeTupleGetHeapTID (IndexTuple itup)

static ItemPointer	BTreeTupleGetMaxHeapTID (IndexTuple itup)

void	btbuildempty (Relation index)

bool	btinsert (Relation rel, Datum values, bool isnull, ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique, bool indexUnchanged, 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)

void	_bt_dedup_pass (Relation rel, Buffer buf, IndexTuple newitem, Size newitemsz, bool bottomupdedup)

bool	_bt_bottomupdel_pass (Relation rel, Buffer buf, Relation heapRel, Size newitemsz)

void	_bt_dedup_start_pending (BTDedupState state, IndexTuple base, OffsetNumber baseoff)

bool	_bt_dedup_save_htid (BTDedupState state, IndexTuple itup)

Size	_bt_dedup_finish_pending (Page newpage, BTDedupState state)

IndexTuple	_bt_form_posting (IndexTuple base, ItemPointer htids, int nhtids)

void	_bt_update_posting (BTVacuumPosting vacposting)

IndexTuple	_bt_swap_posting (IndexTuple newitem, IndexTuple oposting, int postingoff)

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

void	_bt_finish_split (Relation rel, Relation heaprel, Buffer lbuf, BTStack stack)

Buffer	_bt_getstackbuf (Relation rel, Relation heaprel, BTStack stack, BlockNumber child)

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

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

bool	_bt_vacuum_needs_cleanup (Relation rel)

void	_bt_set_cleanup_info (Relation rel, BlockNumber num_delpages)

void	_bt_upgrademetapage (Page page)

Buffer	_bt_getroot (Relation rel, Relation heaprel, int access)

Buffer	_bt_gettrueroot (Relation rel)

int	_bt_getrootheight (Relation rel)

void	_bt_metaversion (Relation rel, bool heapkeyspace, bool allequalimage)

void	_bt_checkpage (Relation rel, Buffer buf)

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

Buffer	_bt_allocbuf (Relation rel, Relation heaprel)

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

void	_bt_relbuf (Relation rel, Buffer buf)

void	_bt_lockbuf (Relation rel, Buffer buf, int access)

void	_bt_unlockbuf (Relation rel, Buffer buf)

bool	_bt_conditionallockbuf (Relation rel, Buffer buf)

void	_bt_upgradelockbufcleanup (Relation rel, Buffer buf)

void	_bt_pageinit (Page page, Size size)

void	_bt_delitems_vacuum (Relation rel, Buffer buf, OffsetNumber deletable, int ndeletable, BTVacuumPosting updatable, int nupdatable)

void	_bt_delitems_delete_check (Relation rel, Buffer buf, Relation heapRel, TM_IndexDeleteOp *delstate)

void	_bt_pagedel (Relation rel, Buffer leafbuf, BTVacState *vstate)

void	_bt_pendingfsm_init (Relation rel, BTVacState *vstate, bool cleanuponly)

void	_bt_pendingfsm_finalize (Relation rel, BTVacState *vstate)

BTStack	_bt_search (Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP, int access)

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

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)

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, bool requiredMatchedByPrecheck)

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	_bt_allequalimage (Relation rel, bool debugmessage)

bool	btvalidate (Oid opclassoid)

void	btadjustmembers (Oid opfamilyoid, Oid opclassoid, List operators, List functions)

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

void	_bt_parallel_build_main (dsm_segment seg, shm_toc toc)

Macro Definition Documentation

◆ BT_IS_POSTING

#define BT_IS_POSTING 0x2000

Definition at line 466 of file nbtree.h.

◆ BT_OFFSET_MASK

#define BT_OFFSET_MASK 0x0FFF

Definition at line 462 of file nbtree.h.

◆ BT_PIVOT_HEAP_TID_ATTR

#define BT_PIVOT_HEAP_TID_ATTR 0x1000

Definition at line 465 of file nbtree.h.

◆ BT_READ

#define BT_READ BUFFER_LOCK_SHARE

Definition at line 719 of file nbtree.h.

◆ BT_STATUS_OFFSET_MASK

#define BT_STATUS_OFFSET_MASK 0xF000

Definition at line 463 of file nbtree.h.

◆ BT_WRITE

#define BT_WRITE BUFFER_LOCK_EXCLUSIVE

Definition at line 720 of file nbtree.h.

◆ BTCommuteStrategyNumber

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

Definition at line 685 of file nbtree.h.

◆ BTEQUALIMAGE_PROC

#define BTEQUALIMAGE_PROC 4

Definition at line 710 of file nbtree.h.

◆ BTGetDeduplicateItems

#define BTGetDeduplicateItems ( relation )

Value:

    (AssertMacro(relation->rd_rel->relkind == RELKIND_INDEX && \
                 relation->rd_rel->relam == BTREE_AM_OID), \
    ((relation)->rd_options ? \
     ((BTOptions *) (relation)->rd_options)->deduplicate_items : true))

Definition at line 1113 of file nbtree.h.

◆ BTGetFillFactor

#define BTGetFillFactor ( relation )

Value:

    (AssertMacro(relation->rd_rel->relkind == RELKIND_INDEX && \
                 relation->rd_rel->relam == BTREE_AM_OID), \
     (relation)->rd_options ? \
     ((BTOptions *) (relation)->rd_options)->fillfactor : \
     BTREE_DEFAULT_FILLFACTOR)

Definition at line 1105 of file nbtree.h.

◆ BTGetTargetPageFreeSpace

#define BTGetTargetPageFreeSpace ( relation ) (BLCKSZ * (100 - BTGetFillFactor(relation)) / 100)

Definition at line 1111 of file nbtree.h.

◆ BTINRANGE_PROC

#define BTINRANGE_PROC 3

Definition at line 709 of file nbtree.h.

◆ BTMaxItemSize

#define BTMaxItemSize ( page )

Value:

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

Definition at line 164 of file nbtree.h.

◆ BTMaxItemSizeNoHeapTid

#define BTMaxItemSizeNoHeapTid ( page )

Value:

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

Definition at line 169 of file nbtree.h.

◆ BTNProcs

#define BTNProcs 5

Definition at line 712 of file nbtree.h.

◆ BTOPTIONS_PROC

#define BTOPTIONS_PROC 5

Definition at line 711 of file nbtree.h.

◆ BTORDER_PROC

#define BTORDER_PROC 1

Definition at line 707 of file nbtree.h.

◆ BTP_DELETED

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

Definition at line 78 of file nbtree.h.

◆ BTP_HALF_DEAD

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

Definition at line 80 of file nbtree.h.

◆ BTP_HAS_FULLXID

#define BTP_HAS_FULLXID (1 << 8) /* contains BTDeletedPageData */

Definition at line 84 of file nbtree.h.

◆ BTP_HAS_GARBAGE

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

Definition at line 82 of file nbtree.h.

◆ BTP_INCOMPLETE_SPLIT

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

Definition at line 83 of file nbtree.h.

◆ BTP_LEAF

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

Definition at line 76 of file nbtree.h.

◆ BTP_META

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

Definition at line 79 of file nbtree.h.

◆ BTP_ROOT

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

Definition at line 77 of file nbtree.h.

◆ BTP_SPLIT_END

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

Definition at line 81 of file nbtree.h.

◆ BTPageGetMeta

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

Definition at line 121 of file nbtree.h.

◆ BTPageGetOpaque

#define BTPageGetOpaque ( page ) ((BTPageOpaque) PageGetSpecialPointer(page))

Definition at line 73 of file nbtree.h.

◆ BTREE_DEFAULT_FILLFACTOR

#define BTREE_DEFAULT_FILLFACTOR 90

Definition at line 200 of file nbtree.h.

◆ BTREE_MAGIC

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

Definition at line 149 of file nbtree.h.

◆ BTREE_METAPAGE

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

Definition at line 148 of file nbtree.h.

◆ BTREE_MIN_FILLFACTOR

#define BTREE_MIN_FILLFACTOR 10

Definition at line 199 of file nbtree.h.

◆ BTREE_MIN_VERSION

#define BTREE_MIN_VERSION 2 /* minimum supported version */

Definition at line 151 of file nbtree.h.

◆ BTREE_NONLEAF_FILLFACTOR

#define BTREE_NONLEAF_FILLFACTOR 70

Definition at line 201 of file nbtree.h.

◆ BTREE_NOVAC_VERSION

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

Definition at line 152 of file nbtree.h.

◆ BTREE_SINGLEVAL_FILLFACTOR

#define BTREE_SINGLEVAL_FILLFACTOR 96

Definition at line 202 of file nbtree.h.

◆ BTREE_VERSION

#define BTREE_VERSION 4 /* current version number */

Definition at line 150 of file nbtree.h.

◆ BTreeTupleGetNAtts

#define BTreeTupleGetNAtts	(	itup,
		rel
	)

Value:

    ( \
        (BTreeTupleIsPivot(itup)) ? \
        ( \
            ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_OFFSET_MASK \
        ) \
        : \
        IndexRelationGetNumberOfAttributes(rel) \
    )

Definition at line 577 of file nbtree.h.

◆ 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 1018 of file nbtree.h.

◆ BTScanPosIsPinned

#define BTScanPosIsPinned ( scanpos )

Value:

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

Definition at line 995 of file nbtree.h.

◆ BTScanPosIsValid

#define BTScanPosIsValid ( scanpos )

Value:

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

Definition at line 1012 of file nbtree.h.

◆ BTScanPosUnpin

#define BTScanPosUnpin ( scanpos )

Value:

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

Definition at line 1001 of file nbtree.h.

◆ BTScanPosUnpinIfPinned

#define BTScanPosUnpinIfPinned ( scanpos )

Value:

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

Definition at line 1006 of file nbtree.h.

◆ BTSORTSUPPORT_PROC

#define BTSORTSUPPORT_PROC 2

Definition at line 708 of file nbtree.h.

◆ INDEX_ALT_TID_MASK

#define INDEX_ALT_TID_MASK INDEX_AM_RESERVED_BIT

Definition at line 459 of file nbtree.h.

◆ MAX_BT_CYCLE_ID

#define MAX_BT_CYCLE_ID 0xFF7F

Definition at line 93 of file nbtree.h.

◆ MaxTIDsPerBTreePage

#define MaxTIDsPerBTreePage

Value:

(int) ((BLCKSZ - SizeOfPageHeaderData - sizeof(BTPageOpaqueData)) / \

sizeof(ItemPointerData))

Definition at line 185 of file nbtree.h.

◆ P_FIRSTDATAKEY

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

Definition at line 369 of file nbtree.h.

◆ P_FIRSTKEY

#define P_FIRSTKEY ((OffsetNumber) 2)

Definition at line 368 of file nbtree.h.

◆ P_HAS_FULLXID

#define P_HAS_FULLXID ( opaque ) (((opaque)->btpo_flags & BTP_HAS_FULLXID) != 0)

Definition at line 228 of file nbtree.h.

◆ P_HAS_GARBAGE

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

Definition at line 226 of file nbtree.h.

◆ P_HIKEY

#define P_HIKEY ((OffsetNumber) 1)

Definition at line 367 of file nbtree.h.

◆ P_IGNORE

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

Definition at line 225 of file nbtree.h.

◆ P_INCOMPLETE_SPLIT

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

Definition at line 227 of file nbtree.h.

◆ P_ISDELETED

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

Definition at line 222 of file nbtree.h.

◆ P_ISHALFDEAD

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

Definition at line 224 of file nbtree.h.

◆ P_ISLEAF

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

Definition at line 220 of file nbtree.h.

◆ P_ISMETA

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

Definition at line 223 of file nbtree.h.

◆ P_ISROOT

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

Definition at line 221 of file nbtree.h.

◆ P_LEFTMOST

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

Definition at line 218 of file nbtree.h.

◆ P_NONE

#define P_NONE 0

Definition at line 212 of file nbtree.h.

◆ P_RIGHTMOST

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

Definition at line 219 of file nbtree.h.

◆ PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN

#define PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN 2

Definition at line 1124 of file nbtree.h.

◆ PROGRESS_BTREE_PHASE_LEAF_LOAD

#define PROGRESS_BTREE_PHASE_LEAF_LOAD 5

Definition at line 1127 of file nbtree.h.

◆ PROGRESS_BTREE_PHASE_PERFORMSORT_1

#define PROGRESS_BTREE_PHASE_PERFORMSORT_1 3

Definition at line 1125 of file nbtree.h.

◆ PROGRESS_BTREE_PHASE_PERFORMSORT_2

#define PROGRESS_BTREE_PHASE_PERFORMSORT_2 4

Definition at line 1126 of file nbtree.h.

◆ SK_BT_DESC

#define SK_BT_DESC (INDOPTION_DESC << SK_BT_INDOPTION_SHIFT)

Definition at line 1094 of file nbtree.h.

◆ SK_BT_INDOPTION_SHIFT

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

Definition at line 1093 of file nbtree.h.

◆ SK_BT_NULLS_FIRST

#define SK_BT_NULLS_FIRST (INDOPTION_NULLS_FIRST << SK_BT_INDOPTION_SHIFT)

Definition at line 1095 of file nbtree.h.

◆ SK_BT_REQBKWD

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

Definition at line 1092 of file nbtree.h.

◆ SK_BT_REQFWD

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

Definition at line 1091 of file nbtree.h.

Typedef Documentation

◆ BTArrayKeyInfo

typedef struct BTArrayKeyInfo BTArrayKeyInfo

◆ BTCycleId

typedef uint16 BTCycleId

Definition at line 29 of file nbtree.h.

◆ BTDedupInterval

typedef struct BTDedupInterval BTDedupInterval

◆ BTDedupState

typedef BTDedupStateData* BTDedupState

Definition at line 898 of file nbtree.h.

◆ BTDedupStateData

typedef struct BTDedupStateData BTDedupStateData

◆ BTDeletedPageData

typedef struct BTDeletedPageData BTDeletedPageData

◆ BTInsertState

typedef BTInsertStateData* BTInsertState

Definition at line 840 of file nbtree.h.

◆ BTInsertStateData

typedef struct BTInsertStateData BTInsertStateData

◆ BTMetaPageData

typedef struct BTMetaPageData BTMetaPageData

◆ BTOptions

typedef struct BTOptions BTOptions

◆ BTPageOpaque

typedef BTPageOpaqueData* BTPageOpaque

Definition at line 71 of file nbtree.h.

◆ BTPageOpaqueData

typedef struct BTPageOpaqueData BTPageOpaqueData

◆ BTPendingFSM

typedef struct BTPendingFSM BTPendingFSM

◆ BTScanInsert

typedef BTScanInsertData* BTScanInsert

Definition at line 801 of file nbtree.h.

◆ BTScanInsertData

typedef struct BTScanInsertData BTScanInsertData

◆ BTScanOpaque

typedef BTScanOpaqueData* BTScanOpaque

Definition at line 1084 of file nbtree.h.

◆ BTScanOpaqueData

typedef struct BTScanOpaqueData BTScanOpaqueData

◆ BTScanPos

typedef BTScanPosData* BTScanPos

Definition at line 993 of file nbtree.h.

◆ BTScanPosData

typedef struct BTScanPosData BTScanPosData

◆ BTScanPosItem

typedef struct BTScanPosItem BTScanPosItem

◆ BTStack

typedef BTStackData* BTStack

Definition at line 739 of file nbtree.h.

◆ BTStackData

typedef struct BTStackData BTStackData

◆ BTVacState

typedef struct BTVacState BTVacState

◆ BTVacuumPosting

typedef BTVacuumPostingData* BTVacuumPosting

Definition at line 919 of file nbtree.h.

◆ BTVacuumPostingData

typedef struct BTVacuumPostingData BTVacuumPostingData

Function Documentation

◆ _bt_advance_array_keys()

bool _bt_advance_array_keys	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 553 of file nbtutils.c.

 {
     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);
  
     /*
      * When no new array keys were found, the scan is "past the end" of the
      * array keys.  _bt_start_array_keys can still "restart" the array keys if
      * a rescan is required.
      */
     if (!found)
         so->arraysStarted = false;
  
     return found;
 }

References _bt_parallel_advance_array_keys(), BTScanOpaqueData::arrayKeyData, BTScanOpaqueData::arrayKeys, BTScanOpaqueData::arraysStarted, 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().

◆ _bt_allequalimage()

bool _bt_allequalimage	(	Relation	rel,
		bool	debugmessage
	)

Definition at line 2737 of file nbtutils.c.

 {
     bool        allequalimage = true;
  
     /* INCLUDE indexes can never support deduplication */
     if (IndexRelationGetNumberOfAttributes(rel) !=
         IndexRelationGetNumberOfKeyAttributes(rel))
         return false;
  
     for (int i = 0; i < IndexRelationGetNumberOfKeyAttributes(rel); i++)
     {
         Oid         opfamily = rel->rd_opfamily[i];
         Oid         opcintype = rel->rd_opcintype[i];
         Oid         collation = rel->rd_indcollation[i];
         Oid         equalimageproc;
  
         equalimageproc = get_opfamily_proc(opfamily, opcintype, opcintype,
                                            BTEQUALIMAGE_PROC);
  
         /*
          * If there is no BTEQUALIMAGE_PROC then deduplication is assumed to
          * be unsafe.  Otherwise, actually call proc and see what it says.
          */
         if (!OidIsValid(equalimageproc) ||
             !DatumGetBool(OidFunctionCall1Coll(equalimageproc, collation,
                                                ObjectIdGetDatum(opcintype))))
         {
             allequalimage = false;
             break;
         }
     }
  
     if (debugmessage)
     {
         if (allequalimage)
             elog(DEBUG1, "index \"%s\" can safely use deduplication",
                  RelationGetRelationName(rel));
         else
             elog(DEBUG1, "index \"%s\" cannot use deduplication",
                  RelationGetRelationName(rel));
     }
  
     return allequalimage;
 }

References BTEQUALIMAGE_PROC, DatumGetBool(), DEBUG1, elog(), get_opfamily_proc(), i, IndexRelationGetNumberOfAttributes, IndexRelationGetNumberOfKeyAttributes, ObjectIdGetDatum(), OidFunctionCall1Coll(), OidIsValid, RelationData::rd_indcollation, RelationData::rd_opcintype, RelationData::rd_opfamily, and RelationGetRelationName.

Referenced by _bt_leafbuild(), bt_index_check_internal(), and btbuildempty().

◆ _bt_allocbuf()

Buffer _bt_allocbuf	(	Relation	rel,
		Relation	heaprel
	)

Definition at line 869 of file nbtpage.c.

 {
     Buffer      buf;
     BlockNumber blkno;
     Page        page;
  
     Assert(heaprel != NULL);
  
     /*
      * 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 (_bt_conditionallockbuf(rel, buf))
         {
             page = BufferGetPage(buf);
  
             /*
              * It's possible to find an all-zeroes page in an index.  For
              * example, a backend might successfully extend the relation one
              * page and then crash before it is able to make a WAL entry for
              * adding the page.  If we find a zeroed page then reclaim it
              * immediately.
              */
             if (PageIsNew(page))
             {
                 /* Okay to use page.  Initialize and return it. */
                 _bt_pageinit(page, BufferGetPageSize(buf));
                 return buf;
             }
  
             if (BTPageIsRecyclable(page, heaprel))
             {
                 /*
                  * 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 safexid
                  * value
                  */
                 if (RelationNeedsWAL(rel) && XLogStandbyInfoActive())
                 {
                     xl_btree_reuse_page xlrec_reuse;
  
                     /*
                      * Note that we don't register the buffer with the record,
                      * because this operation doesn't modify the page (that
                      * already happened, back when VACUUM deleted the page).
                      * This record only exists to provide a conflict point for
                      * Hot Standby.  See record REDO routine comments.
                      */
                     xlrec_reuse.locator = rel->rd_locator;
                     xlrec_reuse.block = blkno;
                     xlrec_reuse.snapshotConflictHorizon = BTPageGetDeleteXid(page);
                     xlrec_reuse.isCatalogRel =
                         RelationIsAccessibleInLogicalDecoding(heaprel);
  
                     XLogBeginInsert();
                     XLogRegisterData((char *) &xlrec_reuse, SizeOfBtreeReusePage);
  
                     XLogInsert(RM_BTREE_ID, XLOG_BTREE_REUSE_PAGE);
                 }
  
                 /* 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. Need to use RBM_ZERO_AND_LOCK or we
      * risk a race condition against btvacuumscan --- see comments therein.
      * This forces us to repeat the valgrind request that _bt_lockbuf()
      * otherwise would make, as we can't use _bt_lockbuf() without introducing
      * a race.
      */
     buf = ExtendBufferedRel(BMR_REL(rel), MAIN_FORKNUM, NULL, EB_LOCK_FIRST);
     if (!RelationUsesLocalBuffers(rel))
         VALGRIND_MAKE_MEM_DEFINED(BufferGetPage(buf), BLCKSZ);
  
     /* Initialize the new page before returning it */
     page = BufferGetPage(buf);
     Assert(PageIsNew(page));
     _bt_pageinit(page, BufferGetPageSize(buf));
  
     return buf;
 }

References _bt_conditionallockbuf(), _bt_pageinit(), _bt_relbuf(), Assert(), xl_btree_reuse_page::block, BMR_REL, BTPageGetDeleteXid(), BTPageIsRecyclable(), buf, BufferGetPage(), BufferGetPageSize(), DEBUG2, EB_LOCK_FIRST, elog(), ExtendBufferedRel(), GetFreeIndexPage(), InvalidBlockNumber, xl_btree_reuse_page::isCatalogRel, xl_btree_reuse_page::locator, MAIN_FORKNUM, PageIsNew(), RelationData::rd_locator, ReadBuffer(), RelationIsAccessibleInLogicalDecoding, RelationNeedsWAL, RelationUsesLocalBuffers, ReleaseBuffer(), SizeOfBtreeReusePage, xl_btree_reuse_page::snapshotConflictHorizon, VALGRIND_MAKE_MEM_DEFINED, XLOG_BTREE_REUSE_PAGE, XLogBeginInsert(), XLogInsert(), XLogRegisterData(), and XLogStandbyInfoActive.

Referenced by _bt_getroot(), _bt_newlevel(), and _bt_split().

◆ _bt_binsrch_insert()

OffsetNumber _bt_binsrch_insert	(	Relation	rel,
		BTInsertState	insertstate
	)

Definition at line 442 of file nbtsearch.c.

 {
     BTScanInsert key = insertstate->itup_key;
     Page        page;
     BTPageOpaque opaque;
     OffsetNumber low,
                 high,
                 stricthigh;
     int32       result,
                 cmpval;
  
     page = BufferGetPage(insertstate->buf);
     opaque = BTPageGetOpaque(page);
  
     Assert(P_ISLEAF(opaque));
     Assert(!key->nextkey);
     Assert(insertstate->postingoff == 0);
  
     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;
         }
  
         /*
          * If tuple at offset located by binary search is a posting list whose
          * TID range overlaps with caller's scantid, perform posting list
          * binary search to set postingoff for caller.  Caller must split the
          * posting list when postingoff is set.  This should happen
          * infrequently.
          */
         if (unlikely(result == 0 && key->scantid != NULL))
         {
             /*
              * postingoff should never be set more than once per leaf page
              * binary search.  That would mean that there are duplicate table
              * TIDs in the index, which is never okay.  Check for that here.
              */
             if (insertstate->postingoff != 0)
                 ereport(ERROR,
                         (errcode(ERRCODE_INDEX_CORRUPTED),
                          errmsg_internal("table tid from new index tuple (%u,%u) cannot find insert offset between offsets %u and %u of block %u in index \"%s\"",
                                          ItemPointerGetBlockNumber(key->scantid),
                                          ItemPointerGetOffsetNumber(key->scantid),
                                          low, stricthigh,
                                          BufferGetBlockNumber(insertstate->buf),
                                          RelationGetRelationName(rel))));
  
             insertstate->postingoff = _bt_binsrch_posting(key, page, mid);
         }
     }
  
     /*
      * 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;
 }

References _bt_binsrch_posting(), _bt_compare(), Assert(), BTInsertStateData::bounds_valid, BTPageGetOpaque, BTInsertStateData::buf, BufferGetBlockNumber(), BufferGetPage(), ereport, errcode(), errmsg_internal(), ERROR, InvalidOffsetNumber, ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), BTInsertStateData::itup_key, sort-test::key, BTInsertStateData::low, P_FIRSTDATAKEY, P_ISLEAF, PageGetMaxOffsetNumber(), BTInsertStateData::postingoff, RelationGetRelationName, BTInsertStateData::stricthigh, and unlikely.

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

◆ _bt_bottomupdel_pass()

bool _bt_bottomupdel_pass	(	Relation	rel,
		Buffer	buf,
		Relation	heapRel,
		Size	newitemsz
	)

Definition at line 307 of file nbtdedup.c.

 {
     OffsetNumber offnum,
                 minoff,
                 maxoff;
     Page        page = BufferGetPage(buf);
     BTPageOpaque opaque = BTPageGetOpaque(page);
     BTDedupState state;
     TM_IndexDeleteOp delstate;
     bool        neverdedup;
     int         nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
  
     /* Passed-in newitemsz is MAXALIGNED but does not include line pointer */
     newitemsz += sizeof(ItemIdData);
  
     /* Initialize deduplication state */
     state = (BTDedupState) palloc(sizeof(BTDedupStateData));
     state->deduplicate = true;
     state->nmaxitems = 0;
     state->maxpostingsize = BLCKSZ; /* We're not really deduplicating */
     state->base = NULL;
     state->baseoff = InvalidOffsetNumber;
     state->basetupsize = 0;
     state->htids = palloc(state->maxpostingsize);
     state->nhtids = 0;
     state->nitems = 0;
     state->phystupsize = 0;
     state->nintervals = 0;
  
     /*
      * Initialize tableam state that describes bottom-up index deletion
      * operation.
      *
      * We'll go on to ask the tableam to search for TIDs whose index tuples we
      * can safely delete.  The tableam will search until our leaf page space
      * target is satisfied, or until the cost of continuing with the tableam
      * operation seems too high.  It focuses its efforts on TIDs associated
      * with duplicate index tuples that we mark "promising".
      *
      * This space target is a little arbitrary.  The tableam must be able to
      * keep the costs and benefits in balance.  We provide the tableam with
      * exhaustive information about what might work, without directly
      * concerning ourselves with avoiding work during the tableam call.  Our
      * role in costing the bottom-up deletion process is strictly advisory.
      */
     delstate.irel = rel;
     delstate.iblknum = BufferGetBlockNumber(buf);
     delstate.bottomup = true;
     delstate.bottomupfreespace = Max(BLCKSZ / 16, newitemsz);
     delstate.ndeltids = 0;
     delstate.deltids = palloc(MaxTIDsPerBTreePage * sizeof(TM_IndexDelete));
     delstate.status = palloc(MaxTIDsPerBTreePage * sizeof(TM_IndexStatus));
  
     minoff = P_FIRSTDATAKEY(opaque);
     maxoff = PageGetMaxOffsetNumber(page);
     for (offnum = minoff;
          offnum <= maxoff;
          offnum = OffsetNumberNext(offnum))
     {
         ItemId      itemid = PageGetItemId(page, offnum);
         IndexTuple  itup = (IndexTuple) PageGetItem(page, itemid);
  
         Assert(!ItemIdIsDead(itemid));
  
         if (offnum == minoff)
         {
             /* itup starts first pending interval */
             _bt_dedup_start_pending(state, itup, offnum);
         }
         else if (_bt_keep_natts_fast(rel, state->base, itup) > nkeyatts &&
                  _bt_dedup_save_htid(state, itup))
         {
             /* Tuple is equal; just added its TIDs to pending interval */
         }
         else
         {
             /* Finalize interval -- move its TIDs to delete state */
             _bt_bottomupdel_finish_pending(page, state, &delstate);
  
             /* itup starts new pending interval */
             _bt_dedup_start_pending(state, itup, offnum);
         }
     }
     /* Finalize final interval -- move its TIDs to delete state */
     _bt_bottomupdel_finish_pending(page, state, &delstate);
  
     /*
      * We don't give up now in the event of having few (or even zero)
      * promising tuples for the tableam because it's not up to us as the index
      * AM to manage costs (note that the tableam might have heuristics of its
      * own that work out what to do).  We should at least avoid having our
      * caller do a useless deduplication pass after we return in the event of
      * zero promising tuples, though.
      */
     neverdedup = false;
     if (state->nintervals == 0)
         neverdedup = true;
  
     pfree(state->htids);
     pfree(state);
  
     /* Ask tableam which TIDs are deletable, then physically delete them */
     _bt_delitems_delete_check(rel, buf, heapRel, &delstate);
  
     pfree(delstate.deltids);
     pfree(delstate.status);
  
     /* Report "success" to caller unconditionally to avoid deduplication */
     if (neverdedup)
         return true;
  
     /* Don't dedup when we won't end up back here any time soon anyway */
     return PageGetExactFreeSpace(page) >= Max(BLCKSZ / 24, newitemsz);
 }

References _bt_bottomupdel_finish_pending(), _bt_dedup_save_htid(), _bt_dedup_start_pending(), _bt_delitems_delete_check(), _bt_keep_natts_fast(), Assert(), TM_IndexDeleteOp::bottomup, TM_IndexDeleteOp::bottomupfreespace, BTPageGetOpaque, buf, BufferGetBlockNumber(), BufferGetPage(), TM_IndexDeleteOp::deltids, TM_IndexDeleteOp::iblknum, IndexRelationGetNumberOfKeyAttributes, InvalidOffsetNumber, TM_IndexDeleteOp::irel, ItemIdIsDead, Max, MaxTIDsPerBTreePage, TM_IndexDeleteOp::ndeltids, OffsetNumberNext, P_FIRSTDATAKEY, PageGetExactFreeSpace(), PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), palloc(), pfree(), and TM_IndexDeleteOp::status.

Referenced by _bt_delete_or_dedup_one_page().

◆ _bt_check_natts()

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

Definition at line 2519 of file nbtutils.c.

 {
     int16       natts = IndexRelationGetNumberOfAttributes(rel);
     int16       nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
     BTPageOpaque opaque = BTPageGetOpaque(page);
     IndexTuple  itup;
     int         tupnatts;
  
     /*
      * We cannot reliably test a deleted or half-dead page, since they have
      * dummy high keys
      */
     if (P_IGNORE(opaque))
         return true;
  
     Assert(offnum >= FirstOffsetNumber &&
            offnum <= PageGetMaxOffsetNumber(page));
  
     itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
     tupnatts = BTreeTupleGetNAtts(itup, rel);
  
     /* !heapkeyspace indexes do not support deduplication */
     if (!heapkeyspace && BTreeTupleIsPosting(itup))
         return false;
  
     /* Posting list tuples should never have "pivot heap TID" bit set */
     if (BTreeTupleIsPosting(itup) &&
         (ItemPointerGetOffsetNumberNoCheck(&itup->t_tid) &
          BT_PIVOT_HEAP_TID_ATTR) != 0)
         return false;
  
     /* INCLUDE indexes do not support deduplication */
     if (natts != nkeyatts && BTreeTupleIsPosting(itup))
         return false;
  
     if (P_ISLEAF(opaque))
     {
         if (offnum >= P_FIRSTDATAKEY(opaque))
         {
             /*
              * Non-pivot tuple should never be explicitly marked as a pivot
              * tuple
              */
             if (BTreeTupleIsPivot(itup))
                 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, even with a posting list tuple, because only pivot
              * tuples store tupnatts directly.)
              */
             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.
              * Accept that as an alternative indication of a valid
              * !heapkeyspace negative infinity tuple.
              */
             return tupnatts == 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 (!BTreeTupleIsPivot(itup))
         return false;
  
     /* Pivot tuple should not use posting list representation (redundant) */
     if (BTreeTupleIsPosting(itup))
         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;
 }

References Assert(), BT_PIVOT_HEAP_TID_ATTR, BTPageGetOpaque, BTreeTupleGetHeapTID(), BTreeTupleGetNAtts, BTreeTupleIsPivot(), BTreeTupleIsPosting(), FirstOffsetNumber, IndexRelationGetNumberOfAttributes, IndexRelationGetNumberOfKeyAttributes, ItemPointerGetOffsetNumber(), ItemPointerGetOffsetNumberNoCheck(), P_FIRSTDATAKEY, P_HIKEY, P_IGNORE, P_ISLEAF, P_RIGHTMOST, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), and IndexTupleData::t_tid.

Referenced by _bt_compare(), and bt_target_page_check().

◆ _bt_check_third_page()

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

Definition at line 2679 of file nbtutils.c.

 {
     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 = BTPageGetOpaque(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(BTreeTupleGetHeapTID(newtup)),
                        ItemPointerGetOffsetNumber(BTreeTupleGetHeapTID(newtup)),
                        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))));
 }

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

Referenced by _bt_buildadd(), and _bt_findinsertloc().

◆ _bt_checkkeys()

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

Definition at line 1379 of file nbtutils.c.

 {
     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;
         bool        requiredSameDir = false,
                     requiredOppositeDir = false;
  
         /*
          * Check if the key is required for ordered scan in the same or
          * opposite direction.  Save as flag variables for future usage.
          */
         if (((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsForward(dir)) ||
             ((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsBackward(dir)))
             requiredSameDir = true;
         else if (((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsBackward(dir)) ||
                  ((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsForward(dir)))
             requiredOppositeDir = true;
  
         /*
          * Is the key required for scanning for either forward or backward
          * direction?  If so and caller told us that these types of keys are
          * known to be matched, skip the check.  Except for the row keys,
          * where NULLs could be found in the middle of matching values.
          */
         if ((requiredSameDir || requiredOppositeDir) &&
             !(key->sk_flags & SK_ROW_HEADER) && requiredMatchedByPrecheck)
             continue;
  
         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));
             Assert(BTreeTupleIsPivot(tuple));
             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 (requiredSameDir)
                 *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;
         }
  
         /*
          * Apply the key checking function.  When the key is required for
          * opposite direction scan, it must be already satisfied by
          * _bt_first() except for the NULLs checking, which have already done
          * above.
          */
         if (!requiredOppositeDir)
         {
             test = FunctionCall2Coll(&key->sk_func, key->sk_collation,
                                      datum, key->sk_argument);
         }
         else
         {
             test = true;
             Assert(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 (requiredSameDir)
                 *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;
 }

References _bt_check_rowcompare(), Assert(), BTreeTupleGetNAtts, BTreeTupleIsPivot(), DatumGetBool(), FunctionCall2Coll(), index_getattr(), IndexScanDescData::indexRelation, sort-test::key, BTScanOpaqueData::keyData, BTScanOpaqueData::numberOfKeys, IndexScanDescData::opaque, RelationGetDescr, ScanDirectionIsBackward, ScanDirectionIsForward, SK_BT_NULLS_FIRST, SK_BT_REQBKWD, SK_BT_REQFWD, SK_ISNULL, SK_ROW_HEADER, SK_SEARCHNOTNULL, SK_SEARCHNULL, and test().

Referenced by _bt_readpage().

◆ _bt_checkpage()

void _bt_checkpage	(	Relation	rel,
		Buffer	buf
	)

Definition at line 797 of file nbtpage.c.

 {
     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.")));
 }

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

Referenced by _bt_getbuf(), _bt_relandgetbuf(), _bt_search_insert(), bt_recheck_sibling_links(), btvacuumpage(), and palloc_btree_page().

◆ _bt_compare()

int32 _bt_compare	(	Relation	rel,
		BTScanInsert	key,
		Page	page,
		OffsetNumber	offnum
	)

Definition at line 656 of file nbtsearch.c.

 {
     TupleDesc   itupdesc = RelationGetDescr(rel);
     BTPageOpaque opaque = BTPageGetOpaque(page);
     IndexTuple  itup;
     ItemPointer heapTid;
     ScanKey     scankey;
     int         ncmpkey;
     int         ntupatts;
     int32       result;
  
     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);
     Assert(!BTreeTupleIsPosting(itup) || key->allequalimage);
     scankey = key->scankeys;
     for (int i = 1; i <= ncmpkey; i++)
     {
         Datum       datum;
         bool        isNull;
  
         datum = index_getattr(itup, scankey->sk_attno, itupdesc, &isNull);
  
         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;
  
     /*
      * Scankey must be treated as equal to a posting list tuple if its scantid
      * value falls within the range of the posting list.  In all other cases
      * there can only be a single heap TID value, which is compared directly
      * with scantid.
      */
     Assert(ntupatts >= IndexRelationGetNumberOfKeyAttributes(rel));
     result = ItemPointerCompare(key->scantid, heapTid);
     if (result <= 0 || !BTreeTupleIsPosting(itup))
         return result;
     else
     {
         result = ItemPointerCompare(key->scantid,
                                     BTreeTupleGetMaxHeapTID(itup));
         if (result > 0)
             return 1;
     }
  
     return 0;
 }

References _bt_check_natts(), Assert(), BTPageGetOpaque, BTreeTupleGetHeapTID(), BTreeTupleGetMaxHeapTID(), BTreeTupleGetNAtts, BTreeTupleIsPosting(), DatumGetInt32(), FunctionCall2Coll(), i, index_getattr(), IndexRelationGetNumberOfKeyAttributes, INVERT_COMPARE_RESULT, ItemPointerCompare(), sort-test::key, Min, P_FIRSTDATAKEY, P_ISLEAF, PageGetItem(), PageGetItemId(), RelationGetDescr, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, ScanKeyData::sk_func, and SK_ISNULL.

Referenced by _bt_binsrch(), _bt_binsrch_insert(), _bt_check_unique(), _bt_findinsertloc(), _bt_moveright(), _bt_search_insert(), bt_rootdescend(), bt_target_page_check(), invariant_g_offset(), invariant_l_nontarget_offset(), invariant_l_offset(), and invariant_leq_offset().

◆ _bt_conditionallockbuf()

bool _bt_conditionallockbuf	(	Relation	rel,
		Buffer	buf
	)

Definition at line 1093 of file nbtpage.c.

 {
     /* ConditionalLockBuffer() asserts that pin is held by this backend */
     if (!ConditionalLockBuffer(buf))
         return false;
  
     if (!RelationUsesLocalBuffers(rel))
         VALGRIND_MAKE_MEM_DEFINED(BufferGetPage(buf), BLCKSZ);
  
     return true;
 }

References buf, BufferGetPage(), ConditionalLockBuffer(), RelationUsesLocalBuffers, and VALGRIND_MAKE_MEM_DEFINED.

Referenced by _bt_allocbuf(), and _bt_search_insert().

◆ _bt_dedup_finish_pending()

Size _bt_dedup_finish_pending	(	Page	newpage,
		BTDedupState	state
	)

Definition at line 555 of file nbtdedup.c.

 {
     OffsetNumber tupoff;
     Size        tuplesz;
     Size        spacesaving;
  
     Assert(state->nitems > 0);
     Assert(state->nitems <= state->nhtids);
     Assert(state->intervals[state->nintervals].baseoff == state->baseoff);
  
     tupoff = OffsetNumberNext(PageGetMaxOffsetNumber(newpage));
     if (state->nitems == 1)
     {
         /* Use original, unchanged base tuple */
         tuplesz = IndexTupleSize(state->base);
         Assert(tuplesz == MAXALIGN(IndexTupleSize(state->base)));
         Assert(tuplesz <= BTMaxItemSize(newpage));
         if (PageAddItem(newpage, (Item) state->base, tuplesz, tupoff,
                         false, false) == InvalidOffsetNumber)
             elog(ERROR, "deduplication failed to add tuple to page");
  
         spacesaving = 0;
     }
     else
     {
         IndexTuple  final;
  
         /* Form a tuple with a posting list */
         final = _bt_form_posting(state->base, state->htids, state->nhtids);
         tuplesz = IndexTupleSize(final);
         Assert(tuplesz <= state->maxpostingsize);
  
         /* Save final number of items for posting list */
         state->intervals[state->nintervals].nitems = state->nitems;
  
         Assert(tuplesz == MAXALIGN(IndexTupleSize(final)));
         Assert(tuplesz <= BTMaxItemSize(newpage));
         if (PageAddItem(newpage, (Item) final, tuplesz, tupoff, false,
                         false) == InvalidOffsetNumber)
             elog(ERROR, "deduplication failed to add tuple to page");
  
         pfree(final);
         spacesaving = state->phystupsize - (tuplesz + sizeof(ItemIdData));
         /* Increment nintervals, since we wrote a new posting list tuple */
         state->nintervals++;
         Assert(spacesaving > 0 && spacesaving < BLCKSZ);
     }
  
     /* Reset state for next pending posting list */
     state->nhtids = 0;
     state->nitems = 0;
     state->phystupsize = 0;
  
     return spacesaving;
 }

References _bt_form_posting(), Assert(), BTMaxItemSize, elog(), ERROR, IndexTupleSize, InvalidOffsetNumber, MAXALIGN, OffsetNumberNext, PageAddItem, PageGetMaxOffsetNumber(), and pfree().

Referenced by _bt_dedup_pass(), and btree_xlog_dedup().

◆ _bt_dedup_pass()

void _bt_dedup_pass	(	Relation	rel,
		Buffer	buf,
		IndexTuple	newitem,
		Size	newitemsz,
		bool	bottomupdedup
	)

Definition at line 58 of file nbtdedup.c.

 {
     OffsetNumber offnum,
                 minoff,
                 maxoff;
     Page        page = BufferGetPage(buf);
     BTPageOpaque opaque = BTPageGetOpaque(page);
     Page        newpage;
     BTDedupState state;
     Size        pagesaving PG_USED_FOR_ASSERTS_ONLY = 0;
     bool        singlevalstrat = false;
     int         nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
  
     /* Passed-in newitemsz is MAXALIGNED but does not include line pointer */
     newitemsz += sizeof(ItemIdData);
  
     /*
      * Initialize deduplication state.
      *
      * It would be possible for maxpostingsize (limit on posting list tuple
      * size) to be set to one third of the page.  However, it seems like a
      * good idea to limit the size of posting lists to one sixth of a page.
      * That ought to leave us with a good split point when pages full of
      * duplicates can be split several times.
      */
     state = (BTDedupState) palloc(sizeof(BTDedupStateData));
     state->deduplicate = true;
     state->nmaxitems = 0;
     state->maxpostingsize = Min(BTMaxItemSize(page) / 2, INDEX_SIZE_MASK);
     /* Metadata about base tuple of current pending posting list */
     state->base = NULL;
     state->baseoff = InvalidOffsetNumber;
     state->basetupsize = 0;
     /* Metadata about current pending posting list TIDs */
     state->htids = palloc(state->maxpostingsize);
     state->nhtids = 0;
     state->nitems = 0;
     /* Size of all physical tuples to be replaced by pending posting list */
     state->phystupsize = 0;
     /* nintervals should be initialized to zero */
     state->nintervals = 0;
  
     minoff = P_FIRSTDATAKEY(opaque);
     maxoff = PageGetMaxOffsetNumber(page);
  
     /*
      * Consider applying "single value" strategy, though only if the page
      * seems likely to be split in the near future
      */
     if (!bottomupdedup)
         singlevalstrat = _bt_do_singleval(rel, page, state, minoff, newitem);
  
     /*
      * Deduplicate items from page, and write them to newpage.
      *
      * Copy the original page's LSN into newpage copy.  This will become the
      * updated version of the page.  We need this because XLogInsert will
      * examine the LSN and possibly dump it in a page image.
      */
     newpage = PageGetTempPageCopySpecial(page);
     PageSetLSN(newpage, PageGetLSN(page));
  
     /* Copy high key, if any */
     if (!P_RIGHTMOST(opaque))
     {
         ItemId      hitemid = PageGetItemId(page, P_HIKEY);
         Size        hitemsz = ItemIdGetLength(hitemid);
         IndexTuple  hitem = (IndexTuple) PageGetItem(page, hitemid);
  
         if (PageAddItem(newpage, (Item) hitem, hitemsz, P_HIKEY,
                         false, false) == InvalidOffsetNumber)
             elog(ERROR, "deduplication failed to add highkey");
     }
  
     for (offnum = minoff;
          offnum <= maxoff;
          offnum = OffsetNumberNext(offnum))
     {
         ItemId      itemid = PageGetItemId(page, offnum);
         IndexTuple  itup = (IndexTuple) PageGetItem(page, itemid);
  
         Assert(!ItemIdIsDead(itemid));
  
         if (offnum == minoff)
         {
             /*
              * No previous/base tuple for the data item -- use the data item
              * as base tuple of pending posting list
              */
             _bt_dedup_start_pending(state, itup, offnum);
         }
         else if (state->deduplicate &&
                  _bt_keep_natts_fast(rel, state->base, itup) > nkeyatts &&
                  _bt_dedup_save_htid(state, itup))
         {
             /*
              * Tuple is equal to base tuple of pending posting list.  Heap
              * TID(s) for itup have been saved in state.
              */
         }
         else
         {
             /*
              * Tuple is not equal to pending posting list tuple, or
              * _bt_dedup_save_htid() opted to not merge current item into
              * pending posting list for some other reason (e.g., adding more
              * TIDs would have caused posting list to exceed current
              * maxpostingsize).
              *
              * If state contains pending posting list with more than one item,
              * form new posting tuple and add it to our temp page (newpage).
              * Else add pending interval's base tuple to the temp page as-is.
              */
             pagesaving += _bt_dedup_finish_pending(newpage, state);
  
             if (singlevalstrat)
             {
                 /*
                  * Single value strategy's extra steps.
                  *
                  * Lower maxpostingsize for sixth and final large posting list
                  * tuple at the point where 5 maxpostingsize-capped tuples
                  * have either been formed or observed.
                  *
                  * When a sixth maxpostingsize-capped item is formed/observed,
                  * stop merging together tuples altogether.  The few tuples
                  * that remain at the end of the page won't be merged together
                  * at all (at least not until after a future page split takes
                  * place, when this page's newly allocated right sibling page
                  * gets its first deduplication pass).
                  */
                 if (state->nmaxitems == 5)
                     _bt_singleval_fillfactor(page, state, newitemsz);
                 else if (state->nmaxitems == 6)
                 {
                     state->deduplicate = false;
                     singlevalstrat = false; /* won't be back here */
                 }
             }
  
             /* itup starts new pending posting list */
             _bt_dedup_start_pending(state, itup, offnum);
         }
     }
  
     /* Handle the last item */
     pagesaving += _bt_dedup_finish_pending(newpage, state);
  
     /*
      * If no items suitable for deduplication were found, newpage must be
      * exactly the same as the original page, so just return from function.
      *
      * We could determine whether or not to proceed on the basis the space
      * savings being sufficient to avoid an immediate page split instead.  We
      * don't do that because there is some small value in nbtsplitloc.c always
      * operating against a page that is fully deduplicated (apart from
      * newitem).  Besides, most of the cost has already been paid.
      */
     if (state->nintervals == 0)
     {
         /* cannot leak memory here */
         pfree(newpage);
         pfree(state->htids);
         pfree(state);
         return;
     }
  
     /*
      * By here, it's clear that deduplication will definitely go ahead.
      *
      * Clear the BTP_HAS_GARBAGE page flag.  The index must be a heapkeyspace
      * index, and as such we'll never pay attention to BTP_HAS_GARBAGE anyway.
      * But keep things tidy.
      */
     if (P_HAS_GARBAGE(opaque))
     {
         BTPageOpaque nopaque = BTPageGetOpaque(newpage);
  
         nopaque->btpo_flags &= ~BTP_HAS_GARBAGE;
     }
  
     START_CRIT_SECTION();
  
     PageRestoreTempPage(newpage, page);
     MarkBufferDirty(buf);
  
     /* XLOG stuff */
     if (RelationNeedsWAL(rel))
     {
         XLogRecPtr  recptr;
         xl_btree_dedup xlrec_dedup;
  
         xlrec_dedup.nintervals = state->nintervals;
  
         XLogBeginInsert();
         XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
         XLogRegisterData((char *) &xlrec_dedup, SizeOfBtreeDedup);
  
         /*
          * The intervals array is not in the buffer, but pretend that it is.
          * When XLogInsert stores the whole buffer, the array need not be
          * stored too.
          */
         XLogRegisterBufData(0, (char *) state->intervals,
                             state->nintervals * sizeof(BTDedupInterval));
  
         recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_DEDUP);
  
         PageSetLSN(page, recptr);
     }
  
     END_CRIT_SECTION();
  
     /* Local space accounting should agree with page accounting */
     Assert(pagesaving < newitemsz || PageGetExactFreeSpace(page) >= newitemsz);
  
     /* cannot leak memory here */
     pfree(state->htids);
     pfree(state);
 }

References _bt_dedup_finish_pending(), _bt_dedup_save_htid(), _bt_dedup_start_pending(), _bt_do_singleval(), _bt_keep_natts_fast(), _bt_singleval_fillfactor(), Assert(), BTMaxItemSize, BTP_HAS_GARBAGE, BTPageGetOpaque, BTPageOpaqueData::btpo_flags, buf, BufferGetPage(), elog(), END_CRIT_SECTION, ERROR, INDEX_SIZE_MASK, IndexRelationGetNumberOfKeyAttributes, InvalidOffsetNumber, ItemIdGetLength, ItemIdIsDead, MarkBufferDirty(), Min, xl_btree_dedup::nintervals, OffsetNumberNext, P_FIRSTDATAKEY, P_HAS_GARBAGE, P_HIKEY, P_RIGHTMOST, PageAddItem, PageGetExactFreeSpace(), PageGetItem(), PageGetItemId(), PageGetLSN(), PageGetMaxOffsetNumber(), PageGetTempPageCopySpecial(), PageRestoreTempPage(), PageSetLSN(), palloc(), pfree(), PG_USED_FOR_ASSERTS_ONLY, REGBUF_STANDARD, RelationNeedsWAL, SizeOfBtreeDedup, START_CRIT_SECTION, XLOG_BTREE_DEDUP, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().

Referenced by _bt_delete_or_dedup_one_page().

◆ _bt_dedup_save_htid()

bool _bt_dedup_save_htid	(	BTDedupState	state,
		IndexTuple	itup
	)

Definition at line 484 of file nbtdedup.c.

 {
     int         nhtids;
     ItemPointer htids;
     Size        mergedtupsz;
  
     Assert(!BTreeTupleIsPivot(itup));
  
     if (!BTreeTupleIsPosting(itup))
     {
         nhtids = 1;
         htids = &itup->t_tid;
     }
     else
     {
         nhtids = BTreeTupleGetNPosting(itup);
         htids = BTreeTupleGetPosting(itup);
     }
  
     /*
      * Don't append (have caller finish pending posting list as-is) if
      * appending heap TID(s) from itup would put us over maxpostingsize limit.
      *
      * This calculation needs to match the code used within _bt_form_posting()
      * for new posting list tuples.
      */
     mergedtupsz = MAXALIGN(state->basetupsize +
                            (state->nhtids + nhtids) * sizeof(ItemPointerData));
  
     if (mergedtupsz > state->maxpostingsize)
     {
         /*
          * Count this as an oversized item for single value strategy, though
          * only when there are 50 TIDs in the final posting list tuple.  This
          * limit (which is fairly arbitrary) avoids confusion about how many
          * 1/6 of a page tuples have been encountered/created by the current
          * deduplication pass.
          *
          * Note: We deliberately don't consider which deduplication pass
          * merged together tuples to create this item (could be a previous
          * deduplication pass, or current pass).  See _bt_do_singleval()
          * comments.
          */
         if (state->nhtids > 50)
             state->nmaxitems++;
  
         return false;
     }
  
     /*
      * Save heap TIDs to pending posting list tuple -- itup can be merged into
      * pending posting list
      */
     state->nitems++;
     memcpy(state->htids + state->nhtids, htids,
            sizeof(ItemPointerData) * nhtids);
     state->nhtids += nhtids;
     state->phystupsize += MAXALIGN(IndexTupleSize(itup)) + sizeof(ItemIdData);
  
     return true;
 }

References Assert(), BTreeTupleGetNPosting(), BTreeTupleGetPosting(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), IndexTupleSize, MAXALIGN, and IndexTupleData::t_tid.

Referenced by _bt_bottomupdel_pass(), _bt_dedup_pass(), _bt_load(), and btree_xlog_dedup().

◆ _bt_dedup_start_pending()

void _bt_dedup_start_pending	(	BTDedupState	state,
		IndexTuple	base,
		OffsetNumber	baseoff
	)

Definition at line 433 of file nbtdedup.c.

 {
     Assert(state->nhtids == 0);
     Assert(state->nitems == 0);
     Assert(!BTreeTupleIsPivot(base));
  
     /*
      * Copy heap TID(s) from new base tuple for new candidate posting list
      * into working state's array
      */
     if (!BTreeTupleIsPosting(base))
     {
         memcpy(state->htids, &base->t_tid, sizeof(ItemPointerData));
         state->nhtids = 1;
         state->basetupsize = IndexTupleSize(base);
     }
     else
     {
         int         nposting;
  
         nposting = BTreeTupleGetNPosting(base);
         memcpy(state->htids, BTreeTupleGetPosting(base),
                sizeof(ItemPointerData) * nposting);
         state->nhtids = nposting;
         /* basetupsize should not include existing posting list */
         state->basetupsize = BTreeTupleGetPostingOffset(base);
     }
  
     /*
      * Save new base tuple itself -- it'll be needed if we actually create a
      * new posting list from new pending posting list.
      *
      * Must maintain physical size of all existing tuples (including line
      * pointer overhead) so that we can calculate space savings on page.
      */
     state->nitems = 1;
     state->base = base;
     state->baseoff = baseoff;
     state->phystupsize = MAXALIGN(IndexTupleSize(base)) + sizeof(ItemIdData);
     /* Also save baseoff in pending state for interval */
     state->intervals[state->nintervals].baseoff = state->baseoff;
 }

References Assert(), BTreeTupleGetNPosting(), BTreeTupleGetPosting(), BTreeTupleGetPostingOffset(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), IndexTupleSize, MAXALIGN, and IndexTupleData::t_tid.

Referenced by _bt_bottomupdel_pass(), _bt_dedup_pass(), _bt_load(), and btree_xlog_dedup().

◆ _bt_delitems_delete_check()

void _bt_delitems_delete_check	(	Relation	rel,
		Buffer	buf,
		Relation	heapRel,
		TM_IndexDeleteOp *	delstate
	)

Definition at line 1518 of file nbtpage.c.

 {
     Page        page = BufferGetPage(buf);
     TransactionId snapshotConflictHorizon;
     bool        isCatalogRel;
     OffsetNumber postingidxoffnum = InvalidOffsetNumber;
     int         ndeletable = 0,
                 nupdatable = 0;
     OffsetNumber deletable[MaxIndexTuplesPerPage];
     BTVacuumPosting updatable[MaxIndexTuplesPerPage];
  
     /* Use tableam interface to determine which tuples to delete first */
     snapshotConflictHorizon = table_index_delete_tuples(heapRel, delstate);
     isCatalogRel = RelationIsAccessibleInLogicalDecoding(heapRel);
  
     /* Should not WAL-log snapshotConflictHorizon unless it's required */
     if (!XLogStandbyInfoActive())
         snapshotConflictHorizon = InvalidTransactionId;
  
     /*
      * Construct a leaf-page-wise description of what _bt_delitems_delete()
      * needs to do to physically delete index tuples from the page.
      *
      * Must sort deltids array to restore leaf-page-wise order (original order
      * before call to tableam).  This is the order that the loop expects.
      *
      * Note that deltids array might be a lot smaller now.  It might even have
      * no entries at all (with bottom-up deletion caller), in which case there
      * is nothing left to do.
      */
     qsort(delstate->deltids, delstate->ndeltids, sizeof(TM_IndexDelete),
           _bt_delitems_cmp);
     if (delstate->ndeltids == 0)
     {
         Assert(delstate->bottomup);
         return;
     }
  
     /* We definitely have to delete at least one index tuple (or one TID) */
     for (int i = 0; i < delstate->ndeltids; i++)
     {
         TM_IndexStatus *dstatus = delstate->status + delstate->deltids[i].id;
         OffsetNumber idxoffnum = dstatus->idxoffnum;
         ItemId      itemid = PageGetItemId(page, idxoffnum);
         IndexTuple  itup = (IndexTuple) PageGetItem(page, itemid);
         int         nestedi,
                     nitem;
         BTVacuumPosting vacposting;
  
         Assert(OffsetNumberIsValid(idxoffnum));
  
         if (idxoffnum == postingidxoffnum)
         {
             /*
              * This deltid entry is a TID from a posting list tuple that has
              * already been completely processed
              */
             Assert(BTreeTupleIsPosting(itup));
             Assert(ItemPointerCompare(BTreeTupleGetHeapTID(itup),
                                       &delstate->deltids[i].tid) < 0);
             Assert(ItemPointerCompare(BTreeTupleGetMaxHeapTID(itup),
                                       &delstate->deltids[i].tid) >= 0);
             continue;
         }
  
         if (!BTreeTupleIsPosting(itup))
         {
             /* Plain non-pivot tuple */
             Assert(ItemPointerEquals(&itup->t_tid, &delstate->deltids[i].tid));
             if (dstatus->knowndeletable)
                 deletable[ndeletable++] = idxoffnum;
             continue;
         }
  
         /*
          * itup is a posting list tuple whose lowest deltids entry (which may
          * or may not be for the first TID from itup) is considered here now.
          * We should process all of the deltids entries for the posting list
          * together now, though (not just the lowest).  Remember to skip over
          * later itup-related entries during later iterations of outermost
          * loop.
          */
         postingidxoffnum = idxoffnum;   /* Remember work in outermost loop */
         nestedi = i;            /* Initialize for first itup deltids entry */
         vacposting = NULL;      /* Describes final action for itup */
         nitem = BTreeTupleGetNPosting(itup);
         for (int p = 0; p < nitem; p++)
         {
             ItemPointer ptid = BTreeTupleGetPostingN(itup, p);
             int         ptidcmp = -1;
  
             /*
              * This nested loop reuses work across ptid TIDs taken from itup.
              * We take advantage of the fact that both itup's TIDs and deltids
              * entries (within a single itup/posting list grouping) must both
              * be in ascending TID order.
              */
             for (; nestedi < delstate->ndeltids; nestedi++)
             {
                 TM_IndexDelete *tcdeltid = &delstate->deltids[nestedi];
                 TM_IndexStatus *tdstatus = (delstate->status + tcdeltid->id);
  
                 /* Stop once we get past all itup related deltids entries */
                 Assert(tdstatus->idxoffnum >= idxoffnum);
                 if (tdstatus->idxoffnum != idxoffnum)
                     break;
  
                 /* Skip past non-deletable itup related entries up front */
                 if (!tdstatus->knowndeletable)
                     continue;
  
                 /* Entry is first partial ptid match (or an exact match)? */
                 ptidcmp = ItemPointerCompare(&tcdeltid->tid, ptid);
                 if (ptidcmp >= 0)
                 {
                     /* Greater than or equal (partial or exact) match... */
                     break;
                 }
             }
  
             /* ...exact ptid match to a deletable deltids entry? */
             if (ptidcmp != 0)
                 continue;
  
             /* Exact match for deletable deltids entry -- ptid gets deleted */
             if (vacposting == NULL)
             {
                 vacposting = palloc(offsetof(BTVacuumPostingData, deletetids) +
                                     nitem * sizeof(uint16));
                 vacposting->itup = itup;
                 vacposting->updatedoffset = idxoffnum;
                 vacposting->ndeletedtids = 0;
             }
             vacposting->deletetids[vacposting->ndeletedtids++] = p;
         }
  
         /* Final decision on itup, a posting list tuple */
  
         if (vacposting == NULL)
         {
             /* No TIDs to delete from itup -- do nothing */
         }
         else if (vacposting->ndeletedtids == nitem)
         {
             /* Straight delete of itup (to delete all TIDs) */
             deletable[ndeletable++] = idxoffnum;
             /* Turns out we won't need granular information */
             pfree(vacposting);
         }
         else
         {
             /* Delete some (but not all) TIDs from itup */
             Assert(vacposting->ndeletedtids > 0 &&
                    vacposting->ndeletedtids < nitem);
             updatable[nupdatable++] = vacposting;
         }
     }
  
     /* Physically delete tuples (or TIDs) using deletable (or updatable) */
     _bt_delitems_delete(rel, buf, snapshotConflictHorizon, isCatalogRel,
                         deletable, ndeletable, updatable, nupdatable);
  
     /* be tidy */
     for (int i = 0; i < nupdatable; i++)
         pfree(updatable[i]);
 }

References _bt_delitems_cmp(), _bt_delitems_delete(), Assert(), TM_IndexDeleteOp::bottomup, BTreeTupleGetHeapTID(), BTreeTupleGetMaxHeapTID(), BTreeTupleGetNPosting(), BTreeTupleGetPostingN(), BTreeTupleIsPosting(), buf, BufferGetPage(), BTVacuumPostingData::deletetids, TM_IndexDeleteOp::deltids, i, TM_IndexDelete::id, TM_IndexStatus::idxoffnum, InvalidOffsetNumber, InvalidTransactionId, ItemPointerCompare(), ItemPointerEquals(), BTVacuumPostingData::itup, TM_IndexStatus::knowndeletable, MaxIndexTuplesPerPage, BTVacuumPostingData::ndeletedtids, TM_IndexDeleteOp::ndeltids, OffsetNumberIsValid, PageGetItem(), PageGetItemId(), palloc(), pfree(), qsort, RelationIsAccessibleInLogicalDecoding, TM_IndexDeleteOp::status, IndexTupleData::t_tid, table_index_delete_tuples(), TM_IndexDelete::tid, BTVacuumPostingData::updatedoffset, and XLogStandbyInfoActive.

Referenced by _bt_bottomupdel_pass(), and _bt_simpledel_pass().

◆ _bt_delitems_vacuum()

void _bt_delitems_vacuum	(	Relation	rel,
		Buffer	buf,
		OffsetNumber *	deletable,
		int	ndeletable,
		BTVacuumPosting *	updatable,
		int	nupdatable
	)

Definition at line 1154 of file nbtpage.c.

 {
     Page        page = BufferGetPage(buf);
     BTPageOpaque opaque;
     bool        needswal = RelationNeedsWAL(rel);
     char       *updatedbuf = NULL;
     Size        updatedbuflen = 0;
     OffsetNumber updatedoffsets[MaxIndexTuplesPerPage];
  
     /* Shouldn't be called unless there's something to do */
     Assert(ndeletable > 0 || nupdatable > 0);
  
     /* Generate new version of posting lists without deleted TIDs */
     if (nupdatable > 0)
         updatedbuf = _bt_delitems_update(updatable, nupdatable,
                                          updatedoffsets, &updatedbuflen,
                                          needswal);
  
     /* No ereport(ERROR) until changes are logged */
     START_CRIT_SECTION();
  
     /*
      * Handle posting tuple updates.
      *
      * Deliberately do this before handling simple deletes.  If we did it the
      * other way around (i.e. WAL record order -- simple deletes before
      * updates) then we'd have to make compensating changes to the 'updatable'
      * array of offset numbers.
      *
      * PageIndexTupleOverwrite() won't unset each item's LP_DEAD bit when it
      * happens to already be set.  It's important that we not interfere with
      * any future simple index tuple deletion operations.
      */
     for (int i = 0; i < nupdatable; i++)
     {
         OffsetNumber updatedoffset = updatedoffsets[i];
         IndexTuple  itup;
         Size        itemsz;
  
         itup = updatable[i]->itup;
         itemsz = MAXALIGN(IndexTupleSize(itup));
         if (!PageIndexTupleOverwrite(page, updatedoffset, (Item) itup,
                                      itemsz))
             elog(PANIC, "failed to update partially dead item in block %u of index \"%s\"",
                  BufferGetBlockNumber(buf), RelationGetRelationName(rel));
     }
  
     /* Now handle simple deletes of entire tuples */
     if (ndeletable > 0)
         PageIndexMultiDelete(page, deletable, ndeletable);
  
     /*
      * We can clear the vacuum cycle ID since this page has certainly been
      * processed by the current vacuum scan.
      */
     opaque = BTPageGetOpaque(page);
     opaque->btpo_cycleid = 0;
  
     /*
      * Clear the BTP_HAS_GARBAGE page flag.
      *
      * This flag indicates the presence of LP_DEAD items on the page (though
      * not reliably).  Note that we only rely on it with pg_upgrade'd
      * !heapkeyspace indexes.  That's why clearing it here won't usually
      * interfere with simple index tuple deletion.
      */
     opaque->btpo_flags &= ~BTP_HAS_GARBAGE;
  
     MarkBufferDirty(buf);
  
     /* XLOG stuff */
     if (needswal)
     {
         XLogRecPtr  recptr;
         xl_btree_vacuum xlrec_vacuum;
  
         xlrec_vacuum.ndeleted = ndeletable;
         xlrec_vacuum.nupdated = nupdatable;
  
         XLogBeginInsert();
         XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
         XLogRegisterData((char *) &xlrec_vacuum, SizeOfBtreeVacuum);
  
         if (ndeletable > 0)
             XLogRegisterBufData(0, (char *) deletable,
                                 ndeletable * sizeof(OffsetNumber));
  
         if (nupdatable > 0)
         {
             XLogRegisterBufData(0, (char *) updatedoffsets,
                                 nupdatable * sizeof(OffsetNumber));
             XLogRegisterBufData(0, updatedbuf, updatedbuflen);
         }
  
         recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_VACUUM);
  
         PageSetLSN(page, recptr);
     }
  
     END_CRIT_SECTION();
  
     /* can't leak memory here */
     if (updatedbuf != NULL)
         pfree(updatedbuf);
     /* free tuples allocated within _bt_delitems_update() */
     for (int i = 0; i < nupdatable; i++)
         pfree(updatable[i]->itup);
 }

References _bt_delitems_update(), Assert(), BTP_HAS_GARBAGE, BTPageGetOpaque, BTPageOpaqueData::btpo_cycleid, BTPageOpaqueData::btpo_flags, buf, BufferGetBlockNumber(), BufferGetPage(), elog(), END_CRIT_SECTION, i, IndexTupleSize, BTVacuumPostingData::itup, MarkBufferDirty(), MAXALIGN, MaxIndexTuplesPerPage, xl_btree_vacuum::ndeleted, xl_btree_vacuum::nupdated, PageIndexMultiDelete(), PageIndexTupleOverwrite(), PageSetLSN(), PANIC, pfree(), REGBUF_STANDARD, RelationGetRelationName, RelationNeedsWAL, SizeOfBtreeVacuum, START_CRIT_SECTION, XLOG_BTREE_VACUUM, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().

Referenced by btvacuumpage().

◆ _bt_doinsert()

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

Definition at line 102 of file nbtinsert.c.

 {
     bool        is_unique = false;
     BTInsertStateData insertstate;
     BTScanInsert itup_key;
     BTStack     stack;
     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.
      *
      * Note that itemsz is passed down to lower level code that deals with
      * inserting the item.  It must be MAXALIGN()'d.  This ensures that space
      * accounting code consistently considers the alignment overhead that we
      * expect PageAddItem() will add later.  (Actually, index_form_tuple() is
      * already conservative about alignment, but we don't rely on that from
      * this distance.  Besides, preserving the "true" tuple size in index
      * tuple headers for the benefit of nbtsplitloc.c might happen someday.
      * Note that heapam does not MAXALIGN() each heap tuple's lp_len field.)
      */
     insertstate.itup = itup;
     insertstate.itemsz = MAXALIGN(IndexTupleSize(itup));
     insertstate.itup_key = itup_key;
     insertstate.bounds_valid = false;
     insertstate.buf = InvalidBuffer;
     insertstate.postingoff = 0;
  
 search:
  
     /*
      * Find and lock the leaf page that the tuple should be added to by
      * searching from the root page.  insertstate.buf will hold a buffer that
      * is locked in exclusive mode afterwards.
      */
     stack = _bt_search_insert(rel, heapRel, &insertstate);
  
     /*
      * checkingunique inserts are not allowed to go ahead when two tuples with
      * equal key attribute values would be visible to new MVCC snapshots once
      * the xact commits.  Check for conflicts in the locked page/buffer (if
      * needed) here.
      *
      * It might be necessary to check a page to the right in _bt_check_unique,
      * though that should be very rare.  In practice the first page the value
      * could be on (with scantid omitted) is almost always also the only page
      * that a matching tuple might be found on.  This is due to the behavior
      * of _bt_findsplitloc with duplicate tuples -- a group of duplicates can
      * only be allowed to cross a page boundary when there is no candidate
      * leaf page split point that avoids it.  Also, _bt_check_unique can use
      * the leaf page high key to determine that there will be no duplicates on
      * the right sibling without actually visiting it (it uses the high key in
      * cases where the new item happens to belong at the far right of the leaf
      * page).
      *
      * 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 perform a new search.
      *
      * 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 (unlikely(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 search;
         }
  
         /* 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, BufferGetBlockNumber(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,
                                        indexUnchanged, stack, heapRel);
         _bt_insertonpg(rel, heapRel, itup_key, insertstate.buf, InvalidBuffer,
                        stack, itup, insertstate.itemsz, newitemoff,
                        insertstate.postingoff, false);
     }
     else
     {
         /* just release the buffer */
         _bt_relbuf(rel, insertstate.buf);
     }
  
     /* be tidy */
     if (stack)
         _bt_freestack(stack);
     pfree(itup_key);
  
     return is_unique;
 }

References _bt_check_unique(), _bt_findinsertloc(), _bt_freestack(), _bt_insertonpg(), _bt_mkscankey(), _bt_relbuf(), _bt_search_insert(), BTScanInsertData::anynullkeys, Assert(), BTInsertStateData::bounds_valid, BTInsertStateData::buf, BufferGetBlockNumber(), CheckForSerializableConflictIn(), BTScanInsertData::heapkeyspace, IndexTupleSize, InvalidBuffer, BTInsertStateData::itemsz, BTInsertStateData::itup, BTInsertStateData::itup_key, MAXALIGN, pfree(), BTInsertStateData::postingoff, BTScanInsertData::scantid, SpeculativeInsertionWait(), IndexTupleData::t_tid, TransactionIdIsValid, UNIQUE_CHECK_EXISTING, UNIQUE_CHECK_NO, unlikely, XactLockTableWait(), and XLTW_InsertIndex.

Referenced by btinsert().

◆ _bt_end_vacuum()

void _bt_end_vacuum ( Relation rel )

Definition at line 2081 of file nbtutils.c.

 {
     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);
 }

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

Referenced by _bt_end_vacuum_callback(), and btbulkdelete().

◆ _bt_end_vacuum_callback()

void _bt_end_vacuum_callback	(	int	code,
		Datum	arg
	)

Definition at line 2109 of file nbtutils.c.

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

References _bt_end_vacuum(), arg, and DatumGetPointer().

Referenced by btbulkdelete().

◆ _bt_findsplitloc()

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

Definition at line 129 of file nbtsplitloc.c.

 {
     BTPageOpaque opaque;
     int         leftspace,
                 rightspace,
                 olddataitemstotal,
                 olddataitemstoleft,
                 perfectpenalty,
                 leaffillfactor;
     FindSplitData state;
     FindSplitStrat strategy;
     ItemId      itemid;
     OffsetNumber offnum,
                 maxoff,
                 firstrightoff;
     double      fillfactormult;
     bool        usemult;
     SplitPoint  leftpage,
                 rightpage;
  
     opaque = BTPageGetOpaque(origpage);
     maxoff = PageGetMaxOffsetNumber(origpage);
  
     /* Total free space available on a btree page, after fixed overhead */
     leftspace = rightspace =
         PageGetPageSize(origpage) - SizeOfPageHeaderData -
         MAXALIGN(sizeof(BTPageOpaqueData));
  
     /* The right page will have the same high key as the old page */
     if (!P_RIGHTMOST(opaque))
     {
         itemid = PageGetItemId(origpage, P_HIKEY);
         rightspace -= (int) (MAXALIGN(ItemIdGetLength(itemid)) +
                              sizeof(ItemIdData));
     }
  
     /* Count up total space in data items before actually scanning 'em */
     olddataitemstotal = rightspace - (int) PageGetExactFreeSpace(origpage);
     leaffillfactor = BTGetFillFactor(rel);
  
     /* Passed-in newitemsz is MAXALIGNED but does not include line pointer */
     newitemsz += sizeof(ItemIdData);
     state.rel = rel;
     state.origpage = origpage;
     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;
  
     /* newitem cannot be a posting list item */
     Assert(!BTreeTupleIsPosting(newitem));
  
     /*
      * nsplits 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(origpage, 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.  See _bt_defaultinterval().
      */
     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 newitem as lastleft. (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->firstrightoff)
                 {
                     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;
     }
  
     /*
      * 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 split interval for default strategy */
     state.interval = _bt_defaultinterval(&state);
  
     /*
      * 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.
      */
     firstrightoff = _bt_bestsplitloc(&state, perfectpenalty, newitemonleft,
                                      strategy);
     pfree(state.splits);
  
     return firstrightoff;
 }

References _bt_afternewitemoff(), _bt_bestsplitloc(), _bt_defaultinterval(), _bt_deltasortsplits(), _bt_recsplitloc(), _bt_strategy(), Assert(), BTGetFillFactor, BTPageGetOpaque, BTREE_NONLEAF_FILLFACTOR, BTREE_SINGLEVAL_FILLFACTOR, BTreeTupleIsPosting(), elog(), ERROR, SplitPoint::firstrightoff, i, IndexRelationGetNumberOfKeyAttributes, ItemIdGetLength, MAXALIGN, SplitPoint::newitemonleft, OffsetNumberNext, P_FIRSTDATAKEY, P_HIKEY, P_ISLEAF, P_RIGHTMOST, PageGetExactFreeSpace(), PageGetItemId(), PageGetMaxOffsetNumber(), PageGetPageSize(), palloc(), pfree(), RelationGetRelationName, SizeOfPageHeaderData, SPLIT_DEFAULT, SPLIT_MANY_DUPLICATES, and SPLIT_SINGLE_VALUE.

Referenced by _bt_split().

◆ _bt_finish_split()

void _bt_finish_split	(	Relation	rel,
		Relation	heaprel,
		Buffer	lbuf,
		BTStack	stack
	)

Definition at line 2241 of file nbtinsert.c.

 {
     Page        lpage = BufferGetPage(lbuf);
     BTPageOpaque lpageop = BTPageGetOpaque(lpage);
     Buffer      rbuf;
     Page        rpage;
     BTPageOpaque rpageop;
     bool        wasroot;
     bool        wasonly;
  
     Assert(P_INCOMPLETE_SPLIT(lpageop));
     Assert(heaprel != NULL);
  
     /* Lock right sibling, the one missing the downlink */
     rbuf = _bt_getbuf(rel, lpageop->btpo_next, BT_WRITE);
     rpage = BufferGetPage(rbuf);
     rpageop = BTPageGetOpaque(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);
  
         wasroot = (metad->btm_root == BufferGetBlockNumber(lbuf));
  
         _bt_relbuf(rel, metabuf);
     }
     else
         wasroot = false;
  
     /* Was this the only page on the level before split? */
     wasonly = (P_LEFTMOST(lpageop) && P_RIGHTMOST(rpageop));
  
     elog(DEBUG1, "finishing incomplete split of %u/%u",
          BufferGetBlockNumber(lbuf), BufferGetBlockNumber(rbuf));
  
     _bt_insert_parent(rel, heaprel, lbuf, rbuf, stack, wasroot, wasonly);
 }

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

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

◆ _bt_first()

bool _bt_first	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 860 of file nbtsearch.c.

 {
     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;
     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)
     {
         /* Notify any other workers that we're done with this scan key. */
         _bt_parallel_done(scan);
         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 */
     _bt_metaversion(rel, &inskey.heapkeyspace, &inskey.allequalimage);
     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, NULL, &inskey, &buf, BT_READ);
  
     /* 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.  Without a buffer lock, it's
          * possible for another transaction to insert data between
          * _bt_search() and PredicateLockRelation().  We have to try again
          * after taking the relation-level predicate lock, to close a narrow
          * window where we wouldn't scan concurrently inserted tuples, but the
          * writer wouldn't see our predicate lock.
          */
         if (IsolationIsSerializable())
         {
             PredicateLockRelation(rel, scan->xs_snapshot);
             stack = _bt_search(rel, NULL, &inskey, &buf, BT_READ);
             _bt_freestack(stack);
         }
  
         if (!BufferIsValid(buf))
         {
             /*
              * Mark parallel scan as done, so that all the workers can finish
              * their scan.
              */
             _bt_parallel_done(scan);
             BTScanPosInvalidate(so->currPos);
             return false;
         }
     }
  
     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;
     so->firstPage = true;
  
     /*
      * 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.
          */
         _bt_unlockbuf(scan->indexRelation, so->currPos.buf);
         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;
 }

References _bt_binsrch(), _bt_drop_lock_and_maybe_pin(), _bt_endpoint(), _bt_freestack(), _bt_initialize_more_data(), _bt_metaversion(), _bt_parallel_done(), _bt_parallel_readpage(), _bt_parallel_seize(), _bt_preprocess_keys(), _bt_readpage(), _bt_search(), _bt_steppage(), _bt_unlockbuf(), Assert(), BT_READ, BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, BTORDER_PROC, BTScanPosInvalidate, BTScanPosIsValid, buf, BTScanPosData::buf, BufferGetBlockNumber(), BufferIsValid(), cur, BTScanOpaqueData::currPos, BTScanOpaqueData::currTuples, DatumGetPointer(), elog(), ERROR, BTScanOpaqueData::firstPage, get_opfamily_proc(), i, index_getprocinfo(), INDEX_MAX_KEYS, IndexScanDescData::indexRelation, InvalidBlockNumber, InvalidOid, InvalidStrategy, IsolationIsSerializable, BTScanPosData::itemIndex, BTScanPosData::items, BTScanOpaqueData::keyData, 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_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_flags, SK_ISNULL, SK_ROW_END, SK_ROW_HEADER, SK_ROW_MEMBER, SK_SEARCHNOTNULL, ScanKeyData::sk_strategy, IndexScanDescData::xs_heaptid, IndexScanDescData::xs_itup, IndexScanDescData::xs_snapshot, and IndexScanDescData::xs_want_itup.

Referenced by btgetbitmap(), and btgettuple().

◆ _bt_form_posting()

IndexTuple _bt_form_posting	(	IndexTuple	base,
		ItemPointer	htids,
		int	nhtids
	)

Definition at line 864 of file nbtdedup.c.

 {
     uint32      keysize,
                 newsize;
     IndexTuple  itup;
  
     if (BTreeTupleIsPosting(base))
         keysize = BTreeTupleGetPostingOffset(base);
     else
         keysize = IndexTupleSize(base);
  
     Assert(!BTreeTupleIsPivot(base));
     Assert(nhtids > 0 && nhtids <= PG_UINT16_MAX);
     Assert(keysize == MAXALIGN(keysize));
  
     /* Determine final size of new tuple */
     if (nhtids > 1)
         newsize = MAXALIGN(keysize +
                            nhtids * sizeof(ItemPointerData));
     else
         newsize = keysize;
  
     Assert(newsize <= INDEX_SIZE_MASK);
     Assert(newsize == MAXALIGN(newsize));
  
     /* Allocate memory using palloc0() (matches index_form_tuple()) */
     itup = palloc0(newsize);
     memcpy(itup, base, keysize);
     itup->t_info &= ~INDEX_SIZE_MASK;
     itup->t_info |= newsize;
     if (nhtids > 1)
     {
         /* Form posting list tuple */
         BTreeTupleSetPosting(itup, nhtids, keysize);
         memcpy(BTreeTupleGetPosting(itup), htids,
                sizeof(ItemPointerData) * nhtids);
         Assert(_bt_posting_valid(itup));
     }
     else
     {
         /* Form standard non-pivot tuple */
         itup->t_info &= ~INDEX_ALT_TID_MASK;
         ItemPointerCopy(htids, &itup->t_tid);
         Assert(ItemPointerIsValid(&itup->t_tid));
     }
  
     return itup;
 }

References Assert(), BTreeTupleGetPosting(), BTreeTupleGetPostingOffset(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), BTreeTupleSetPosting(), INDEX_ALT_TID_MASK, INDEX_SIZE_MASK, IndexTupleSize, ItemPointerCopy(), ItemPointerIsValid(), MAXALIGN, palloc0(), PG_UINT16_MAX, IndexTupleData::t_info, and IndexTupleData::t_tid.

Referenced by _bt_dedup_finish_pending(), _bt_sort_dedup_finish_pending(), and bt_posting_plain_tuple().

◆ _bt_freestack()

void _bt_freestack ( BTStack stack )

Definition at line 182 of file nbtutils.c.

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

References BTStackData::bts_parent, and pfree().

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

◆ _bt_get_endpoint()

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

Definition at line 2374 of file nbtsearch.c.

 {
     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, NULL, BT_READ);
     else
         buf = _bt_gettrueroot(rel);
  
     if (!BufferIsValid(buf))
         return InvalidBuffer;
  
     page = BufferGetPage(buf);
     opaque = BTPageGetOpaque(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);
             opaque = BTPageGetOpaque(page);
         }
  
         /* Done? */
         if (opaque->btpo_level == level)
             break;
         if (opaque->btpo_level < level)
             ereport(ERROR,
                     (errcode(ERRCODE_INDEX_CORRUPTED),
                      errmsg_internal("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 = BTreeTupleGetDownLink(itup);
  
         buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ);
         page = BufferGetPage(buf);
         opaque = BTPageGetOpaque(page);
     }
  
     return buf;
 }

References _bt_getroot(), _bt_gettrueroot(), _bt_relandgetbuf(), BT_READ, BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTPageOpaqueData::btpo_next, BTreeTupleGetDownLink(), buf, BufferGetPage(), BufferIsValid(), elog(), ereport, errcode(), errmsg_internal(), ERROR, InvalidBuffer, P_FIRSTDATAKEY, P_IGNORE, P_NONE, P_RIGHTMOST, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), and RelationGetRelationName.

Referenced by _bt_endpoint(), and _bt_insert_parent().

◆ _bt_getbuf()

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

Definition at line 845 of file nbtpage.c.

 {
     Buffer      buf;
  
     Assert(BlockNumberIsValid(blkno));
  
     /* Read an existing block of the relation */
     buf = ReadBuffer(rel, blkno);
     _bt_lockbuf(rel, buf, access);
     _bt_checkpage(rel, buf);
  
     return buf;
 }

References _bt_checkpage(), _bt_lockbuf(), Assert(), BlockNumberIsValid(), buf, and ReadBuffer().

Referenced by _bt_finish_split(), _bt_getroot(), _bt_getrootheight(), _bt_getstackbuf(), _bt_gettrueroot(), _bt_insertonpg(), _bt_killitems(), _bt_leftsib_splitflag(), _bt_metaversion(), _bt_moveright(), _bt_newlevel(), _bt_pagedel(), _bt_readnextpage(), _bt_rightsib_halfdeadflag(), _bt_set_cleanup_info(), _bt_split(), _bt_unlink_halfdead_page(), _bt_vacuum_needs_cleanup(), and _bt_walk_left().

◆ _bt_getroot()

Buffer _bt_getroot	(	Relation	rel,
		Relation	heaprel,
		int	access
	)

Definition at line 344 of file nbtpage.c.

 {
     Buffer      metabuf;
     Buffer      rootbuf;
     Page        rootpage;
     BTPageOpaque rootopaque;
     BlockNumber rootblkno;
     uint32      rootlevel;
     BTMetaPageData *metad;
  
     Assert(access == BT_READ || heaprel != NULL);
  
     /*
      * 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_allequalimage ||
                metad->btm_version > BTREE_NOVAC_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 = BTPageGetOpaque(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);
     metad = _bt_getmeta(rel, metabuf);
  
     /* if no root page initialized yet, do it */
     if (metad->btm_root == P_NONE)
     {
         Page        metapg;
  
         /* 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 */
         _bt_unlockbuf(rel, metabuf);
         _bt_lockbuf(rel, 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, heaprel, 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_allocbuf(rel, heaprel);
         rootblkno = BufferGetBlockNumber(rootbuf);
         rootpage = BufferGetPage(rootbuf);
         rootopaque = BTPageGetOpaque(rootpage);
         rootopaque->btpo_prev = rootopaque->btpo_next = P_NONE;
         rootopaque->btpo_flags = (BTP_LEAF | BTP_ROOT);
         rootopaque->btpo_level = 0;
         rootopaque->btpo_cycleid = 0;
         /* Get raw page pointer for metapage */
         metapg = BufferGetPage(metabuf);
  
         /* 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_last_cleanup_num_delpages = 0;
         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.last_cleanup_num_delpages = 0;
             md.allequalimage = metad->btm_allequalimage;
  
             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.
          */
         _bt_unlockbuf(rel, rootbuf);
         _bt_lockbuf(rel, rootbuf, BT_READ);
  
         /* okay, metadata is correct, release lock on it without caching */
         _bt_relbuf(rel, metabuf);
     }
     else
     {
         rootblkno = metad->btm_fastroot;
         Assert(rootblkno != P_NONE);
         rootlevel = metad->btm_fastlevel;
  
         /*
          * Cache the metapage data for next time
          */
         rel->rd_amcache = MemoryContextAlloc(rel->rd_indexcxt,
                                              sizeof(BTMetaPageData));
         memcpy(rel->rd_amcache, metad, sizeof(BTMetaPageData));
  
         /*
          * 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 = BTPageGetOpaque(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;
         }
  
         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;
 }

Referenced by _bt_get_endpoint(), and _bt_search().

◆ _bt_getrootheight()

int _bt_getrootheight ( Relation rel )

Definition at line 675 of file nbtpage.c.

 {
     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
          */
         rel->rd_amcache = MemoryContextAlloc(rel->rd_indexcxt,
                                              sizeof(BTMetaPageData));
         memcpy(rel->rd_amcache, metad, sizeof(BTMetaPageData));
         _bt_relbuf(rel, metabuf);
     }
  
     /* Get cached page */
     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_allequalimage ||
            metad->btm_version > BTREE_NOVAC_VERSION);
     Assert(metad->btm_fastroot != P_NONE);
  
     return metad->btm_fastlevel;
 }

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

Referenced by _bt_insertonpg(), and get_relation_info().

◆ _bt_getstackbuf()

Buffer _bt_getstackbuf	(	Relation	rel,
		Relation	heaprel,
		BTStack	stack,
		BlockNumber	child
	)

Definition at line 2319 of file nbtinsert.c.

 {
     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 = BTPageGetOpaque(page);
  
         Assert(heaprel != NULL);
         if (P_INCOMPLETE_SPLIT(opaque))
         {
             _bt_finish_split(rel, heaprel, 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 (BTreeTupleGetDownLink(item) == child)
                 {
                     /* 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 (BTreeTupleGetDownLink(item) == child)
                 {
                     /* 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.
          *
          * Lehman and Yao couple/chain locks when moving right here, which we
          * can avoid.  See nbtree/README.
          */
         if (P_RIGHTMOST(opaque))
         {
             _bt_relbuf(rel, buf);
             return InvalidBuffer;
         }
         blkno = opaque->btpo_next;
         start = InvalidOffsetNumber;
         _bt_relbuf(rel, buf);
     }
 }

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

Referenced by _bt_insert_parent(), and _bt_lock_subtree_parent().

◆ _bt_gettrueroot()

Buffer _bt_gettrueroot ( Relation rel )

Definition at line 580 of file nbtpage.c.

 {
     Buffer      metabuf;
     Page        metapg;
     BTPageOpaque metaopaque;
     Buffer      rootbuf;
     Page        rootpage;
     BTPageOpaque rootopaque;
     BlockNumber rootblkno;
     uint32      rootlevel;

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ BT_IS_POSTING

◆ BT_OFFSET_MASK

◆ BT_PIVOT_HEAP_TID_ATTR

◆ BT_READ

◆ BT_STATUS_OFFSET_MASK

◆ BT_WRITE

◆ BTCommuteStrategyNumber

◆ BTEQUALIMAGE_PROC

◆ BTGetDeduplicateItems

◆ BTGetFillFactor

◆ BTGetTargetPageFreeSpace

◆ BTINRANGE_PROC

◆ BTMaxItemSize

◆ BTMaxItemSizeNoHeapTid

◆ BTNProcs

◆ BTOPTIONS_PROC

◆ BTORDER_PROC

◆ BTP_DELETED

◆ BTP_HALF_DEAD

◆ BTP_HAS_FULLXID

◆ BTP_HAS_GARBAGE

◆ BTP_INCOMPLETE_SPLIT

◆ BTP_LEAF

◆ BTP_META

◆ BTP_ROOT

◆ BTP_SPLIT_END

◆ BTPageGetMeta

◆ BTPageGetOpaque

◆ BTREE_DEFAULT_FILLFACTOR

◆ BTREE_MAGIC

◆ BTREE_METAPAGE

◆ BTREE_MIN_FILLFACTOR

◆ BTREE_MIN_VERSION

◆ BTREE_NONLEAF_FILLFACTOR

◆ BTREE_NOVAC_VERSION

◆ BTREE_SINGLEVAL_FILLFACTOR

◆ BTREE_VERSION

◆ BTreeTupleGetNAtts

◆ BTScanPosInvalidate

◆ BTScanPosIsPinned

◆ BTScanPosIsValid

◆ BTScanPosUnpin

◆ BTScanPosUnpinIfPinned

◆ BTSORTSUPPORT_PROC

◆ INDEX_ALT_TID_MASK

◆ MAX_BT_CYCLE_ID

◆ MaxTIDsPerBTreePage

◆ P_FIRSTDATAKEY

◆ P_FIRSTKEY

◆ P_HAS_FULLXID

◆ 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

◆ BTDedupInterval