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

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, Relation heapRel, 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, Buffer lbuf, BTStack stack)

Buffer	_bt_getstackbuf (Relation rel, 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, 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_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, BTScanInsert key, Buffer *bufP, int access, Snapshot snapshot)

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

OffsetNumber	_bt_binsrch_insert (Relation rel, BTInsertState insertstate)

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

bool	_bt_first (IndexScanDesc scan, ScanDirection dir)

bool	_bt_next (IndexScanDesc scan, ScanDirection dir)

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

BTScanInsert	_bt_mkscankey (Relation rel, IndexTuple itup)

void	_bt_freestack (BTStack stack)

void	_bt_preprocess_array_keys (IndexScanDesc scan)

void	_bt_start_array_keys (IndexScanDesc scan, ScanDirection dir)

bool	_bt_advance_array_keys (IndexScanDesc scan, ScanDirection dir)

void	_bt_mark_array_keys (IndexScanDesc scan)

void	_bt_restore_array_keys (IndexScanDesc scan)

void	_bt_preprocess_keys (IndexScanDesc scan)

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

void	_bt_killitems (IndexScanDesc scan)

BTCycleId	_bt_vacuum_cycleid (Relation rel)

BTCycleId	_bt_start_vacuum (Relation rel)

void	_bt_end_vacuum (Relation rel)

void	_bt_end_vacuum_callback (int code, Datum arg)

Size	BTreeShmemSize (void)

void	BTreeShmemInit (void)

bytea *	btoptions (Datum reloptions, bool validate)

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

char *	btbuildphasename (int64 phasenum)

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

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

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

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

bool	_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.

Referenced by BTreeTupleIsPivot(), BTreeTupleIsPosting(), and BTreeTupleSetPosting().

◆ BT_OFFSET_MASK

#define BT_OFFSET_MASK 0x0FFF

Definition at line 462 of file nbtree.h.

Referenced by _bt_check_natts(), and BTreeTupleGetNPosting().

◆ BT_PIVOT_HEAP_TID_ATTR

#define BT_PIVOT_HEAP_TID_ATTR 0x1000

Definition at line 465 of file nbtree.h.

Referenced by _bt_check_natts(), BTreeTupleGetHeapTID(), and BTreeTupleSetNAtts().

◆ BT_READ

#define BT_READ BUFFER_LOCK_SHARE

◆ BT_STATUS_OFFSET_MASK

#define BT_STATUS_OFFSET_MASK 0xF000

Definition at line 463 of file nbtree.h.

Referenced by BTreeTupleSetNAtts(), and BTreeTupleSetPosting().

◆ BT_WRITE

#define BT_WRITE BUFFER_LOCK_EXCLUSIVE

Definition at line 713 of file nbtree.h.

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

◆ BTCommuteStrategyNumber

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

Definition at line 678 of file nbtree.h.

Referenced by _bt_compare_scankey_args(), and _bt_fix_scankey_strategy().

◆ BTEQUALIMAGE_PROC

#define BTEQUALIMAGE_PROC 4

Definition at line 703 of file nbtree.h.

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

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

Referenced by _bt_delete_or_dedup_one_page(), and _bt_load().

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

Referenced by _bt_findsplitloc().

◆ BTGetTargetPageFreeSpace

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

Definition at line 1099 of file nbtree.h.

Referenced by _bt_pagestate().

◆ BTINRANGE_PROC

#define BTINRANGE_PROC 3

Definition at line 702 of file nbtree.h.

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

◆ BTMaxItemSize

#define BTMaxItemSize ( page )

Value:

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

Definition at line 162 of file nbtree.h.

Referenced by _bt_buildadd(), _bt_check_third_page(), _bt_dedup_pass(), _bt_findinsertloc(), _bt_load(), bt_target_page_check(), and btree_xlog_dedup().

◆ BTMaxItemSizeNoHeapTid

#define BTMaxItemSizeNoHeapTid ( page )

Value:

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

Definition at line 168 of file nbtree.h.

Referenced by _bt_check_third_page(), and bt_target_page_check().

◆ BTNProcs

#define BTNProcs 5

Definition at line 705 of file nbtree.h.

Referenced by bthandler().

◆ BTOPTIONS_PROC

#define BTOPTIONS_PROC 5

Definition at line 704 of file nbtree.h.

Referenced by bthandler(), and btvalidate().

◆ BTORDER_PROC

#define BTORDER_PROC 1

Definition at line 700 of file nbtree.h.

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

◆ BTP_DELETED

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

Definition at line 76 of file nbtree.h.

Referenced by BTPageSetDeleted().

◆ BTP_HALF_DEAD

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

Definition at line 78 of file nbtree.h.

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

◆ BTP_HAS_FULLXID

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

Definition at line 82 of file nbtree.h.

Referenced by BTPageSetDeleted().

◆ BTP_HAS_GARBAGE

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

Definition at line 80 of file nbtree.h.

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

◆ BTP_INCOMPLETE_SPLIT

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

Definition at line 81 of file nbtree.h.

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

◆ BTP_LEAF

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

Definition at line 74 of file nbtree.h.

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

◆ BTP_META

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

Definition at line 77 of file nbtree.h.

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

◆ BTP_ROOT

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

Definition at line 75 of file nbtree.h.

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

◆ BTP_SPLIT_END

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

Definition at line 79 of file nbtree.h.

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

◆ BTPageGetMeta

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

Definition at line 119 of file nbtree.h.

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

◆ BTREE_DEFAULT_FILLFACTOR

#define BTREE_DEFAULT_FILLFACTOR 90

Definition at line 199 of file nbtree.h.

◆ BTREE_MAGIC

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

Definition at line 147 of file nbtree.h.

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

◆ BTREE_METAPAGE

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

Definition at line 146 of file nbtree.h.

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

◆ BTREE_MIN_FILLFACTOR

#define BTREE_MIN_FILLFACTOR 10

Definition at line 198 of file nbtree.h.

◆ BTREE_MIN_VERSION

#define BTREE_MIN_VERSION 2 /* minimum supported version */

Definition at line 149 of file nbtree.h.

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

◆ BTREE_NONLEAF_FILLFACTOR

#define BTREE_NONLEAF_FILLFACTOR 70

Definition at line 200 of file nbtree.h.

Referenced by _bt_findsplitloc(), and _bt_pagestate().

◆ BTREE_NOVAC_VERSION

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

Definition at line 150 of file nbtree.h.

Referenced by _bt_check_third_page(), _bt_getroot(), _bt_getrootheight(), _bt_insertonpg(), _bt_metaversion(), _bt_newroot(), _bt_restore_meta(), _bt_set_cleanup_info(), _bt_unlink_halfdead_page(), _bt_upgrademetapage(), _bt_vacuum_needs_cleanup(), and bt_metap().

◆ BTREE_SINGLEVAL_FILLFACTOR

#define BTREE_SINGLEVAL_FILLFACTOR 96

Definition at line 201 of file nbtree.h.

Referenced by _bt_findsplitloc(), and _bt_singleval_fillfactor().

◆ BTREE_VERSION

#define BTREE_VERSION 4 /* current version number */

Definition at line 148 of file nbtree.h.

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

◆ BTreeTupleGetNAtts

#define BTreeTupleGetNAtts	(	itup,
		rel
	)

Value:

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

Definition at line 570 of file nbtree.h.

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

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

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

◆ BTScanPosIsPinned

#define BTScanPosIsPinned ( scanpos )

Value:

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

Definition at line 988 of file nbtree.h.

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

◆ BTScanPosIsValid

#define BTScanPosIsValid ( scanpos )

Value:

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

Definition at line 1005 of file nbtree.h.

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

◆ BTScanPosUnpin

#define BTScanPosUnpin ( scanpos )

Value:

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

Definition at line 994 of file nbtree.h.

◆ BTScanPosUnpinIfPinned

#define BTScanPosUnpinIfPinned ( scanpos )

Value:

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

Definition at line 999 of file nbtree.h.

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

◆ BTSORTSUPPORT_PROC

#define BTSORTSUPPORT_PROC 2

Definition at line 701 of file nbtree.h.

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

◆ INDEX_ALT_TID_MASK

#define INDEX_ALT_TID_MASK INDEX_AM_RESERVED_BIT

Definition at line 459 of file nbtree.h.

Referenced by _bt_form_posting(), _bt_update_posting(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), BTreeTupleSetNAtts(), and BTreeTupleSetPosting().

◆ MAX_BT_CYCLE_ID

#define MAX_BT_CYCLE_ID 0xFF7F

Definition at line 91 of file nbtree.h.

Referenced by _bt_start_vacuum().

◆ MaxTIDsPerBTreePage

#define MaxTIDsPerBTreePage

Value:

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

sizeof(ItemPointerData))

BTPageOpaqueData

Definition: nbtree.h:62

ItemPointerData

Definition: itemptr.h:36

SizeOfPageHeaderData

#define SizeOfPageHeaderData

Definition: bufpage.h:216

Definition at line 184 of file nbtree.h.

Referenced by _bt_bottomupdel_pass(), _bt_readpage(), _bt_simpledel_pass(), bt_check_every_level(), and btgettuple().

◆ P_FIRSTDATAKEY

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

◆ P_FIRSTKEY

#define P_FIRSTKEY ((OffsetNumber) 2)

Definition at line 368 of file nbtree.h.

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

◆ P_HAS_FULLXID

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

Definition at line 227 of file nbtree.h.

Referenced by bt_child_highkey_check(), BTPageGetDeleteXid(), GetBTPageStatistics(), and palloc_btree_page().

◆ P_HAS_GARBAGE

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

Definition at line 225 of file nbtree.h.

Referenced by _bt_dedup_pass(), _bt_findinsertloc(), btree_xlog_dedup(), and palloc_btree_page().

◆ P_HIKEY

◆ P_IGNORE

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

◆ P_INCOMPLETE_SPLIT

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

Definition at line 226 of file nbtree.h.

Referenced by _bt_clear_incomplete_split(), _bt_findinsertloc(), _bt_finish_split(), _bt_getstackbuf(), _bt_insertonpg(), _bt_leftsib_splitflag(), _bt_lock_subtree_parent(), _bt_moveright(), _bt_newroot(), _bt_pagedel(), _bt_stepright(), and bt_child_highkey_check().

◆ P_ISDELETED

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

Definition at line 221 of file nbtree.h.

Referenced by _bt_pagedel(), _bt_rightsib_halfdeadflag(), _bt_unlink_halfdead_page(), _bt_walk_left(), bt_check_level_from_leftmost(), bt_child_check(), bt_child_highkey_check(), bt_downlink_missing_check(), bt_page_items_bytea(), bt_page_items_internal(), bt_recheck_sibling_links(), BTPageGetDeleteXid(), BTPageIsRecyclable(), btvacuumpage(), GetBTPageStatistics(), palloc_btree_page(), and pgstatindex_impl().

◆ P_ISHALFDEAD

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

Definition at line 223 of file nbtree.h.

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

◆ P_ISLEAF

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

◆ P_ISMETA

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

Definition at line 222 of file nbtree.h.

Referenced by _bt_getmeta(), _bt_gettrueroot(), bt_page_items_bytea(), and palloc_btree_page().

◆ P_ISROOT

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

Definition at line 220 of file nbtree.h.

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

◆ P_LEFTMOST

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

Definition at line 217 of file nbtree.h.

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

◆ P_NONE

◆ P_RIGHTMOST

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

◆ PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN

#define PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN 2

Definition at line 1112 of file nbtree.h.

Referenced by _bt_spools_heapscan(), and btbuildphasename().

◆ PROGRESS_BTREE_PHASE_LEAF_LOAD

#define PROGRESS_BTREE_PHASE_LEAF_LOAD 5

Definition at line 1115 of file nbtree.h.

Referenced by _bt_leafbuild(), and btbuildphasename().

◆ PROGRESS_BTREE_PHASE_PERFORMSORT_1

#define PROGRESS_BTREE_PHASE_PERFORMSORT_1 3

Definition at line 1113 of file nbtree.h.

Referenced by _bt_leafbuild(), _bt_parallel_scan_and_sort(), and btbuildphasename().

◆ PROGRESS_BTREE_PHASE_PERFORMSORT_2

#define PROGRESS_BTREE_PHASE_PERFORMSORT_2 4

Definition at line 1114 of file nbtree.h.

Referenced by _bt_leafbuild(), _bt_parallel_scan_and_sort(), and btbuildphasename().

◆ SK_BT_DESC

#define SK_BT_DESC (INDOPTION_DESC << SK_BT_INDOPTION_SHIFT)

Definition at line 1082 of file nbtree.h.

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

◆ SK_BT_INDOPTION_SHIFT

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

Definition at line 1081 of file nbtree.h.

Referenced by _bt_fix_scankey_strategy(), and _bt_mkscankey().

◆ SK_BT_NULLS_FIRST

#define SK_BT_NULLS_FIRST (INDOPTION_NULLS_FIRST << SK_BT_INDOPTION_SHIFT)

Definition at line 1083 of file nbtree.h.

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

◆ SK_BT_REQBKWD

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

Definition at line 1080 of file nbtree.h.

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

◆ SK_BT_REQFWD

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

Definition at line 1079 of file nbtree.h.

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

Typedef Documentation

◆ BTArrayKeyInfo

typedef struct BTArrayKeyInfo BTArrayKeyInfo

◆ BTCycleId

typedef uint16 BTCycleId

Definition at line 29 of file nbtree.h.

◆ BTDedupInterval

typedef struct BTDedupInterval BTDedupInterval

◆ BTDedupState

typedef BTDedupStateData* BTDedupState

Definition at line 891 of file nbtree.h.

◆ BTDedupStateData

typedef struct BTDedupStateData BTDedupStateData

◆ BTDeletedPageData

typedef struct BTDeletedPageData BTDeletedPageData

◆ BTInsertState

typedef BTInsertStateData* BTInsertState

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

◆ BTScanInsertData

typedef struct BTScanInsertData BTScanInsertData

◆ BTScanOpaque

typedef BTScanOpaqueData* BTScanOpaque

Definition at line 1072 of file nbtree.h.

◆ BTScanOpaqueData

typedef struct BTScanOpaqueData BTScanOpaqueData

◆ BTScanPos

typedef BTScanPosData* BTScanPos

Definition at line 986 of file nbtree.h.

◆ BTScanPosData

typedef struct BTScanPosData BTScanPosData

◆ BTScanPosItem

typedef struct BTScanPosItem BTScanPosItem

◆ BTStack

typedef BTStackData* BTStack

Definition at line 732 of file nbtree.h.

◆ BTStackData

typedef struct BTStackData BTStackData

◆ BTVacState

typedef struct BTVacState BTVacState

◆ BTVacuumPosting

typedef BTVacuumPostingData* BTVacuumPosting

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

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

Referenced by btgetbitmap(), and btgettuple().

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

◆ _bt_allequalimage()

bool _bt_allequalimage	(	Relation	rel,
		bool	debugmessage
	)

Definition at line 2692 of file nbtutils.c.

References BTEQUALIMAGE_PROC, BTSortArrayContext::collation, 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().

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

◆ _bt_binsrch_insert()

OffsetNumber _bt_binsrch_insert	(	Relation	rel,
		BTInsertState	insertstate
	)

Definition at line 447 of file nbtsearch.c.

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

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

 {
     BTScanInsert key = insertstate->itup_key;
     Page        page;
     BTPageOpaque opaque;
     OffsetNumber low,
                 high,
                 stricthigh;
     int32       result,
                 cmpval;
 
     page = BufferGetPage(insertstate->buf);
     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 
     Assert(P_ISLEAF(opaque));
     Assert(!key->nextkey);
     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))
             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;
 }

◆ _bt_bottomupdel_pass()

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

Definition at line 305 of file nbtdedup.c.

Referenced by _bt_delete_or_dedup_one_page().

 {
     OffsetNumber offnum,
                 minoff,
                 maxoff;
     Page        page = BufferGetPage(buf);
     BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(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.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);
 }

◆ _bt_check_natts()

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

Definition at line 2466 of file nbtutils.c.

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

Referenced by _bt_compare(), and bt_target_page_check().

 {
     int16       natts = IndexRelationGetNumberOfAttributes(rel);
     int16       nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
     BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
     IndexTuple  itup;
     int         tupnatts;
 
     /*
      * We cannot reliably test a deleted or half-dead page, since they have
      * dummy high keys
      */
     if (P_IGNORE(opaque))
         return true;
 
     Assert(offnum >= FirstOffsetNumber &&
            offnum <= PageGetMaxOffsetNumber(page));
 
     /*
      * Mask allocated for number of keys in index tuple must be able to fit
      * maximum possible number of index attributes
      */
     StaticAssertStmt(BT_OFFSET_MASK >= INDEX_MAX_KEYS,
                      "BT_OFFSET_MASK can't fit INDEX_MAX_KEYS");
 
     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;
 }

◆ _bt_check_third_page()

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

Definition at line 2634 of file nbtutils.c.

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

Referenced by _bt_buildadd(), and _bt_findinsertloc().

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

◆ _bt_checkkeys()

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

Definition at line 1355 of file nbtutils.c.

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, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_NULLS_FIRST, SK_BT_REQBKWD, SK_BT_REQFWD, ScanKeyData::sk_collation, ScanKeyData::sk_flags, ScanKeyData::sk_func, SK_ISNULL, SK_ROW_HEADER, SK_SEARCHNOTNULL, SK_SEARCHNULL, and test().

Referenced by _bt_readpage().

 {
     TupleDesc   tupdesc;
     BTScanOpaque so;
     int         keysz;
     int         ikey;
     ScanKey     key;
 
     Assert(BTreeTupleGetNAtts(tuple, scan->indexRelation) == tupnatts);
 
     *continuescan = true;       /* default assumption */
 
     tupdesc = RelationGetDescr(scan->indexRelation);
     so = (BTScanOpaque) scan->opaque;
     keysz = so->numberOfKeys;
 
     for (key = so->keyData, ikey = 0; ikey < keysz; key++, ikey++)
     {
         Datum       datum;
         bool        isNull;
         Datum       test;
 
         if (key->sk_attno > tupnatts)
         {
             /*
              * This attribute is truncated (must be high key).  The value for
              * this attribute in the first non-pivot tuple on the page to the
              * right could be any possible value.  Assume that truncated
              * attribute passes the qual.
              */
             Assert(ScanDirectionIsForward(dir));
             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 ((key->sk_flags & SK_BT_REQFWD) &&
                 ScanDirectionIsForward(dir))
                 *continuescan = false;
             else if ((key->sk_flags & SK_BT_REQBKWD) &&
                      ScanDirectionIsBackward(dir))
                 *continuescan = false;
 
             /*
              * In any case, this indextuple doesn't match the qual.
              */
             return false;
         }
 
         if (isNull)
         {
             if (key->sk_flags & SK_BT_NULLS_FIRST)
             {
                 /*
                  * Since NULLs are sorted before non-NULLs, we know we have
                  * reached the lower limit of the range of values for this
                  * index attr.  On a backward scan, we can stop if this qual
                  * is one of the "must match" subset.  We can stop regardless
                  * of whether the qual is > or <, so long as it's required,
                  * because it's not possible for any future tuples to pass. On
                  * a forward scan, however, we must keep going, because we may
                  * have initially positioned to the start of the index.
                  */
                 if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
                     ScanDirectionIsBackward(dir))
                     *continuescan = false;
             }
             else
             {
                 /*
                  * Since NULLs are sorted after non-NULLs, we know we have
                  * reached the upper limit of the range of values for this
                  * index attr.  On a forward scan, we can stop if this qual is
                  * one of the "must match" subset.  We can stop regardless of
                  * whether the qual is > or <, so long as it's required,
                  * because it's not possible for any future tuples to pass. On
                  * a backward scan, however, we must keep going, because we
                  * may have initially positioned to the end of the index.
                  */
                 if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
                     ScanDirectionIsForward(dir))
                     *continuescan = false;
             }
 
             /*
              * In any case, this indextuple doesn't match the qual.
              */
             return false;
         }
 
         test = FunctionCall2Coll(&key->sk_func, key->sk_collation,
                                  datum, key->sk_argument);
 
         if (!DatumGetBool(test))
         {
             /*
              * Tuple fails this qual.  If it's a required qual for the current
              * scan direction, then we can conclude no further tuples will
              * pass, either.
              *
              * Note: because we stop the scan as soon as any required equality
              * qual fails, it is critical that equality quals be used for the
              * initial positioning in _bt_first() when they are available. See
              * comments in _bt_first().
              */
             if ((key->sk_flags & SK_BT_REQFWD) &&
                 ScanDirectionIsForward(dir))
                 *continuescan = false;
             else if ((key->sk_flags & SK_BT_REQBKWD) &&
                      ScanDirectionIsBackward(dir))
                 *continuescan = false;
 
             /*
              * In any case, this indextuple doesn't match the qual.
              */
             return false;
         }
     }
 
     /* If we get here, the tuple passes all index quals. */
     return true;
 }

◆ _bt_checkpage()

void _bt_checkpage	(	Relation	rel,
		Buffer	buf
	)

Definition at line 794 of file nbtpage.c.

References 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().

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

◆ _bt_compare()

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

Definition at line 644 of file nbtsearch.c.

References _bt_check_natts(), BTScanInsertData::allequalimage, Assert, BTreeTupleGetHeapTID(), BTreeTupleGetMaxHeapTID(), BTreeTupleGetNAtts, BTreeTupleIsPosting(), DatumGetInt32, FunctionCall2Coll(), BTScanInsertData::heapkeyspace, i, index_getattr, IndexRelationGetNumberOfKeyAttributes, INVERT_COMPARE_RESULT, ItemPointerCompare(), BTScanInsertData::keysz, Min, P_FIRSTDATAKEY, P_ISLEAF, PageGetItem, PageGetItemId, PageGetSpecialPointer, BTScanInsertData::pivotsearch, RelationGetDescr, BTScanInsertData::scankeys, BTScanInsertData::scantid, ScanKeyData::sk_argument, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, ScanKeyData::sk_func, and SK_ISNULL.

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

 {
     TupleDesc   itupdesc = RelationGetDescr(rel);
     BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
     IndexTuple  itup;
     ItemPointer heapTid;
     ScanKey     scankey;
     int         ncmpkey;
     int         ntupatts;
     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;
 }

◆ _bt_conditionallockbuf()

bool _bt_conditionallockbuf	(	Relation	rel,
		Buffer	buf
	)

Definition at line 1105 of file nbtpage.c.

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

Referenced by _bt_getbuf(), and _bt_search_insert().

 {
     /* 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;
 }

◆ _bt_dedup_finish_pending()

Size _bt_dedup_finish_pending	(	Page	newpage,
		BTDedupState	state
	)

Definition at line 551 of file nbtdedup.c.

References _bt_form_posting(), Assert, BTDedupStateData::base, BTDedupInterval::baseoff, BTDedupStateData::baseoff, elog, ERROR, BTDedupStateData::htids, IndexTupleSize, BTDedupStateData::intervals, InvalidOffsetNumber, MAXALIGN, BTDedupStateData::nhtids, BTDedupStateData::nintervals, BTDedupInterval::nitems, BTDedupStateData::nitems, OffsetNumberNext, PageAddItem, PageGetMaxOffsetNumber, pfree(), and BTDedupStateData::phystupsize.

Referenced by _bt_dedup_pass(), and btree_xlog_dedup().

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

◆ _bt_dedup_pass()

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

Definition at line 57 of file nbtdedup.c.

Referenced by _bt_delete_or_dedup_one_page().

 {
     OffsetNumber offnum,
                 minoff,
                 maxoff;
     Page        page = BufferGetPage(buf);
     BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
     Page        newpage;
     BTDedupState state;
     Size        pagesaving = 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 actually update the page.  Else
              * reset the state and move on without modifying the page.
              */
             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).
                  */
                 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 = (BTPageOpaque) PageGetSpecialPointer(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);
 }

◆ _bt_dedup_save_htid()

bool _bt_dedup_save_htid	(	BTDedupState	state,
		IndexTuple	itup
	)

Definition at line 480 of file nbtdedup.c.

References Assert, BTDedupStateData::basetupsize, BTreeTupleGetNPosting(), BTreeTupleGetPosting(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), BTDedupStateData::htids, IndexTupleSize, MAXALIGN, BTDedupStateData::maxpostingsize, BTDedupStateData::nhtids, BTDedupStateData::nitems, BTDedupStateData::nmaxitems, BTDedupStateData::phystupsize, and IndexTupleData::t_tid.

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

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

◆ _bt_dedup_start_pending()

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

Definition at line 429 of file nbtdedup.c.

References Assert, BTDedupStateData::base, BTDedupInterval::baseoff, BTDedupStateData::baseoff, BTDedupStateData::basetupsize, BTreeTupleGetNPosting(), BTreeTupleGetPosting(), BTreeTupleGetPostingOffset(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), BTDedupStateData::htids, IndexTupleSize, BTDedupStateData::intervals, MAXALIGN, BTDedupStateData::nhtids, BTDedupStateData::nintervals, BTDedupStateData::nitems, BTDedupStateData::phystupsize, and IndexTupleData::t_tid.

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

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

◆ _bt_delitems_delete_check()

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

Definition at line 1529 of file nbtpage.c.

References _bt_delitems_cmp(), _bt_delitems_delete(), Assert, TM_IndexDeleteOp::bottomup, BTreeTupleGetHeapTID(), BTreeTupleGetMaxHeapTID(), BTreeTupleGetNPosting(), BTreeTupleGetPostingN(), BTreeTupleIsPosting(), 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, offsetof, PageGetItem, PageGetItemId, palloc(), pfree(), qsort, RelationNeedsWAL, 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().

 {
     Page        page = BufferGetPage(buf);
     TransactionId latestRemovedXid;
     OffsetNumber postingidxoffnum = InvalidOffsetNumber;
     int         ndeletable = 0,
                 nupdatable = 0;
     OffsetNumber deletable[MaxIndexTuplesPerPage];
     BTVacuumPosting updatable[MaxIndexTuplesPerPage];
 
     /* Use tableam interface to determine which tuples to delete first */
     latestRemovedXid = table_index_delete_tuples(heapRel, delstate);
 
     /* Should not WAL-log latestRemovedXid unless it's required */
     if (!XLogStandbyInfoActive() || !RelationNeedsWAL(rel))
         latestRemovedXid = 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, latestRemovedXid, deletable, ndeletable,
                         updatable, nupdatable);
 
     /* be tidy */
     for (int i = 0; i < nupdatable; i++)
         pfree(updatable[i]);
 }

◆ _bt_delitems_vacuum()

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

Definition at line 1167 of file nbtpage.c.

References _bt_delitems_update(), Assert, BTP_HAS_GARBAGE, BTPageOpaqueData::btpo_cycleid, BTPageOpaqueData::btpo_flags, BufferGetBlockNumber(), BufferGetPage, elog, END_CRIT_SECTION, i, IndexTupleSize, BTVacuumPostingData::itup, MarkBufferDirty(), MAXALIGN, MaxIndexTuplesPerPage, xl_btree_vacuum::ndeleted, xl_btree_vacuum::nupdated, PageGetSpecialPointer, 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().

 {
     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 = (BTPageOpaque) PageGetSpecialPointer(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);
 }

◆ _bt_doinsert()

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

Definition at line 99 of file nbtinsert.c.

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().

 {
     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, &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, 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;
 }

◆ _bt_end_vacuum()

void _bt_end_vacuum ( Relation rel )

Definition at line 2026 of file nbtutils.c.

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

Referenced by _bt_end_vacuum_callback(), and btbulkdelete().

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

◆ _bt_end_vacuum_callback()

void _bt_end_vacuum_callback	(	int	code,
		Datum	arg
	)

Definition at line 2054 of file nbtutils.c.

References _bt_end_vacuum(), and DatumGetPointer.

Referenced by btbulkdelete().

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

◆ _bt_findsplitloc()

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

Definition at line 130 of file nbtsplitloc.c.

References _bt_afternewitemoff(), _bt_bestsplitloc(), _bt_defaultinterval(), _bt_deltasortsplits(), _bt_recsplitloc(), _bt_strategy(), Assert, BTGetFillFactor, BTREE_NONLEAF_FILLFACTOR, BTREE_SINGLEVAL_FILLFACTOR, BTreeTupleIsPosting(), elog, ERROR, SplitPoint::firstrightoff, i, IndexRelationGetNumberOfKeyAttributes, FindSplitData::interval, FindSplitData::is_leaf, FindSplitData::is_rightmost, ItemIdGetLength, FindSplitData::leftspace, MAXALIGN, FindSplitData::maxsplits, FindSplitData::minfirstrightsz, FindSplitData::newitem, FindSplitData::newitemoff, SplitPoint::newitemonleft, FindSplitData::newitemsz, FindSplitData::nsplits, OffsetNumberNext, FindSplitData::olddataitemstotal, FindSplitData::origpage, P_FIRSTDATAKEY, P_HIKEY, P_ISLEAF, P_RIGHTMOST, PageGetExactFreeSpace(), PageGetItemId, PageGetMaxOffsetNumber, PageGetPageSize, PageGetSpecialPointer, palloc(), pfree(), FindSplitData::rel, RelationGetRelationName, FindSplitData::rightspace, SizeOfPageHeaderData, SPLIT_DEFAULT, SPLIT_MANY_DUPLICATES, SPLIT_SINGLE_VALUE, and FindSplitData::splits.

Referenced by _bt_split().

 {
     BTPageOpaque opaque;
     int         leftspace,
                 rightspace,
                 olddataitemstotal,
                 olddataitemstoleft,
                 perfectpenalty,
                 leaffillfactor;
     FindSplitData state;
     FindSplitStrat strategy;
     ItemId      itemid;
     OffsetNumber offnum,
                 maxoff,
                 firstrightoff;
     double      fillfactormult;
     bool        usemult;
     SplitPoint  leftpage,
                 rightpage;
 
     opaque = (BTPageOpaque) PageGetSpecialPointer(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;
 }

◆ _bt_finish_split()

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

Definition at line 2213 of file nbtinsert.c.

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

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

 {
     Page        lpage = BufferGetPage(lbuf);
     BTPageOpaque lpageop = (BTPageOpaque) PageGetSpecialPointer(lpage);
     Buffer      rbuf;
     Page        rpage;
     BTPageOpaque rpageop;
     bool        wasroot;
     bool        wasonly;
 
     Assert(P_INCOMPLETE_SPLIT(lpageop));
 
     /* Lock right sibling, the one missing the downlink */
     rbuf = _bt_getbuf(rel, lpageop->btpo_next, BT_WRITE);
     rpage = BufferGetPage(rbuf);
     rpageop = (BTPageOpaque) PageGetSpecialPointer(rpage);
 
     /* Could this be a root split? */
     if (!stack)
     {
         Buffer      metabuf;
         Page        metapg;
         BTMetaPageData *metad;
 
         /* acquire lock on the metapage */
         metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_WRITE);
         metapg = BufferGetPage(metabuf);
         metad = BTPageGetMeta(metapg);
 
         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, lbuf, rbuf, stack, wasroot, wasonly);
 }

◆ _bt_first()

bool _bt_first	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 848 of file nbtsearch.c.

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, get_opfamily_proc(), i, index_getprocinfo(), INDEX_MAX_KEYS, IndexScanDescData::indexRelation, InvalidBlockNumber, InvalidOid, InvalidStrategy, 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_argument, ScanKeyData::sk_attno, SK_BT_DESC, SK_BT_NULLS_FIRST, ScanKeyData::sk_collation, ScanKeyData::sk_flags, SK_ISNULL, SK_ROW_END, SK_ROW_HEADER, SK_ROW_MEMBER, SK_SEARCHNOTNULL, ScanKeyData::sk_strategy, ScanKeyData::sk_subtype, status(), IndexScanDescData::xs_heaptid, IndexScanDescData::xs_itup, IndexScanDescData::xs_snapshot, and IndexScanDescData::xs_want_itup.

Referenced by btgetbitmap(), and btgettuple().

 {
     Relation    rel = scan->indexRelation;
     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     Buffer      buf;
     BTStack     stack;
     OffsetNumber offnum;
     StrategyNumber strat;
     bool        nextkey;
     bool        goback;
     BTScanInsertData inskey;
     ScanKey     startKeys[INDEX_MAX_KEYS];
     ScanKeyData notnullkeys[INDEX_MAX_KEYS];
     int         keysCount = 0;
     int         i;
     bool        status;
     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, &inskey, &buf, BT_READ, scan->xs_snapshot);
 
     /* don't need to keep the stack around... */
     _bt_freestack(stack);
 
     if (!BufferIsValid(buf))
     {
         /*
          * We only get here if the index is completely empty. Lock relation
          * because nothing finer to lock exists.
          */
         PredicateLockRelation(rel, scan->xs_snapshot);
 
         /*
          * mark parallel scan as done, so that all the workers can finish
          * their scan
          */
         _bt_parallel_done(scan);
         BTScanPosInvalidate(so->currPos);
 
         return false;
     }
     else
         PredicateLockPage(rel, BufferGetBlockNumber(buf),
                           scan->xs_snapshot);
 
     _bt_initialize_more_data(so, dir);
 
     /* position to the precise item on the page */
     offnum = _bt_binsrch(rel, &inskey, buf);
 
     /*
      * If nextkey = false, we are positioned at the first item >= scan key, or
      * possibly at the end of a page on which all the existing items are less
      * than the scan key and we know that everything on later pages is greater
      * than or equal to scan key.
      *
      * If nextkey = true, we are positioned at the first item > scan key, or
      * possibly at the end of a page on which all the existing items are less
      * than or equal to the scan key and we know that everything on later
      * pages is greater than scan key.
      *
      * The actually desired starting point is either this item or the prior
      * one, or in the end-of-page case it's the first item on the next page or
      * the last item on this page.  Adjust the starting offset if needed. (If
      * this results in an offset before the first item or after the last one,
      * _bt_readpage will report no items found, and then we'll step to the
      * next page as needed.)
      */
     if (goback)
         offnum = OffsetNumberPrev(offnum);
 
     /* remember which buffer we have pinned, if any */
     Assert(!BTScanPosIsValid(so->currPos));
     so->currPos.buf = buf;
 
     /*
      * Now load data from the first page of the scan.
      */
     if (!_bt_readpage(scan, dir, offnum))
     {
         /*
          * There's no actually-matching data on this page.  Try to advance to
          * the next page.  Return false if there's no matching data at all.
          */
         _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;
 }

◆ _bt_form_posting()

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

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

◆ 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

◆ BTDedupState