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

Include dependency graph for nbtree.h:

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

Go to the source code of this file.

Data Structures
struct	BTPageOpaqueData

struct	BTMetaPageData

struct	BTStackData

struct	BTScanPosItem

struct	BTScanPosData

struct	BTArrayKeyInfo

struct	BTScanOpaqueData

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

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

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

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

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

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

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

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

#define	MAX_BT_CYCLE_ID 0xFF7F

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

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

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

#define	BTREE_VERSION 2 /* current version number */

#define	BTMaxItemSize(page)

#define	BTREE_MIN_FILLFACTOR 10

#define	BTREE_DEFAULT_FILLFACTOR 90

#define	BTREE_NONLEAF_FILLFACTOR 70

#define	BTTidSame(i1, i2)

#define	BTEntrySame(i1, i2) BTTidSame((i1)->t_tid, (i2)->t_tid)

#define	P_NONE 0

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

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

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

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

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

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

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

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

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

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

#define	P_HIKEY ((OffsetNumber) 1)

#define	P_FIRSTKEY ((OffsetNumber) 2)

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

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

#define	BTORDER_PROC 1

#define	BTSORTSUPPORT_PROC 2

#define	BTNProcs 2

#define	BT_READ BUFFER_LOCK_SHARE

#define	BT_WRITE BUFFER_LOCK_EXCLUSIVE

#define	BTScanPosIsPinned(scanpos)

#define	BTScanPosUnpin(scanpos)

#define	BTScanPosUnpinIfPinned(scanpos)

#define	BTScanPosIsValid(scanpos)

#define	BTScanPosInvalidate(scanpos)

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

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

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

#define	SK_BT_DESC (INDOPTION_DESC << SK_BT_INDOPTION_SHIFT)

#define	SK_BT_NULLS_FIRST (INDOPTION_NULLS_FIRST << SK_BT_INDOPTION_SHIFT)

Typedefs
typedef uint16	BTCycleId

typedef struct BTPageOpaqueData	BTPageOpaqueData

typedef BTPageOpaqueData *	BTPageOpaque

typedef struct BTMetaPageData	BTMetaPageData

typedef struct BTStackData	BTStackData

typedef BTStackData *	BTStack

typedef struct BTScanPosItem	BTScanPosItem

typedef struct BTScanPosData	BTScanPosData

typedef BTScanPosData *	BTScanPos

typedef struct BTArrayKeyInfo	BTArrayKeyInfo

typedef struct BTScanOpaqueData	BTScanOpaqueData

typedef BTScanOpaqueData *	BTScanOpaque

typedef struct BTSpool	BTSpool

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

void	btbuildempty (Relation index)

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

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

Size	btestimateparallelscan (void)

void	btinitparallelscan (void *target)

bool	btgettuple (IndexScanDesc scan, ScanDirection dir)

int64	btgetbitmap (IndexScanDesc scan, TIDBitmap *tbm)

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

void	btparallelrescan (IndexScanDesc scan)

void	btendscan (IndexScanDesc scan)

void	btmarkpos (IndexScanDesc scan)

void	btrestrpos (IndexScanDesc scan)

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

IndexBulkDeleteResult *	btvacuumcleanup (IndexVacuumInfo info, IndexBulkDeleteResult stats)

bool	btcanreturn (Relation index, int attno)

bool	_bt_parallel_seize (IndexScanDesc scan, BlockNumber *pageno)

void	_bt_parallel_release (IndexScanDesc scan, BlockNumber scan_page)

void	_bt_parallel_done (IndexScanDesc scan)

void	_bt_parallel_advance_array_keys (IndexScanDesc scan)

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

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

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

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

Buffer	_bt_getroot (Relation rel, int access)

Buffer	_bt_gettrueroot (Relation rel)

int	_bt_getrootheight (Relation rel)

void	_bt_checkpage (Relation rel, Buffer buf)

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

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

void	_bt_relbuf (Relation rel, Buffer buf)

void	_bt_pageinit (Page page, Size size)

bool	_bt_page_recyclable (Page page)

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

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

int	_bt_pagedel (Relation rel, Buffer buf)

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

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

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

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

bool	_bt_first (IndexScanDesc scan, ScanDirection dir)

bool	_bt_next (IndexScanDesc scan, ScanDirection dir)

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

ScanKey	_bt_mkscankey (Relation rel, IndexTuple itup)

ScanKey	_bt_mkscankey_nodata (Relation rel)

void	_bt_freeskey (ScanKey skey)

void	_bt_freestack (BTStack stack)

void	_bt_preprocess_array_keys (IndexScanDesc scan)

void	_bt_start_array_keys (IndexScanDesc scan, ScanDirection dir)

bool	_bt_advance_array_keys (IndexScanDesc scan, ScanDirection dir)

void	_bt_mark_array_keys (IndexScanDesc scan)

void	_bt_restore_array_keys (IndexScanDesc scan)

void	_bt_preprocess_keys (IndexScanDesc scan)

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

void	_bt_killitems (IndexScanDesc scan)

BTCycleId	_bt_vacuum_cycleid (Relation rel)

BTCycleId	_bt_start_vacuum (Relation rel)

void	_bt_end_vacuum (Relation rel)

void	_bt_end_vacuum_callback (int code, Datum arg)

Size	BTreeShmemSize (void)

void	BTreeShmemInit (void)

bytea *	btoptions (Datum reloptions, bool validate)

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

bool	btvalidate (Oid opclassoid)

BTSpool *	_bt_spoolinit (Relation heap, Relation index, bool isunique, bool isdead)

void	_bt_spooldestroy (BTSpool *btspool)

void	_bt_spool (BTSpool btspool, ItemPointer self, Datum values, bool *isnull)

void	_bt_leafbuild (BTSpool btspool, BTSpool spool2)

Macro Definition Documentation

#define BT_READ BUFFER_LOCK_SHARE

#define BT_WRITE BUFFER_LOCK_EXCLUSIVE

Definition at line 239 of file nbtree.h.

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

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

Definition at line 215 of file nbtree.h.

Referenced by _bt_compare_scankey_args(), and _bt_fix_scankey_strategy().

#define BTEntrySame	(	i1,
		i2
	)	BTTidSame((i1)->t_tid, (i2)->t_tid)

Definition at line 156 of file nbtree.h.

Referenced by _bt_getstackbuf().

#define BTMaxItemSize ( page )

Value:

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

Definition at line 119 of file nbtree.h.

Referenced by _bt_buildadd(), and _bt_findinsertloc().

#define BTNProcs 2

Definition at line 231 of file nbtree.h.

Referenced by bthandler().

#define BTORDER_PROC 1

Definition at line 229 of file nbtree.h.

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

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

Definition at line 72 of file nbtree.h.

Referenced by _bt_unlink_halfdead_page(), and btree_xlog_unlink_page().

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

Definition at line 74 of file nbtree.h.

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

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

Definition at line 76 of file nbtree.h.

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

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

Definition at line 77 of file nbtree.h.

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

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

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

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

Definition at line 73 of file nbtree.h.

Referenced by _bt_initmetapage(), and _bt_restore_meta().

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

Definition at line 71 of file nbtree.h.

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

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

Definition at line 75 of file nbtree.h.

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

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

Definition at line 106 of file nbtree.h.

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

#define BTREE_DEFAULT_FILLFACTOR 90

Definition at line 132 of file nbtree.h.

Referenced by _bt_findsplitloc(), and _bt_pagestate().

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

Definition at line 110 of file nbtree.h.

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

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

Definition at line 109 of file nbtree.h.

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

#define BTREE_MIN_FILLFACTOR 10

Definition at line 131 of file nbtree.h.

#define BTREE_NONLEAF_FILLFACTOR 70

Definition at line 133 of file nbtree.h.

Referenced by _bt_findsplitloc(), and _bt_pagestate().

#define BTREE_VERSION 2 /* current version number */

Definition at line 111 of file nbtree.h.

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

#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 356 of file nbtree.h.

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

#define BTScanPosIsPinned ( scanpos )

Value:

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

Definition at line 333 of file nbtree.h.

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

#define BTScanPosIsValid ( scanpos )

Value:

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

Definition at line 350 of file nbtree.h.

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

#define BTScanPosUnpin ( scanpos )

Value:

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

Definition at line 339 of file nbtree.h.

#define BTScanPosUnpinIfPinned ( scanpos )

Value:

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

Definition at line 344 of file nbtree.h.

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

#define BTSORTSUPPORT_PROC 2

Definition at line 230 of file nbtree.h.

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

#define BTTidSame	(	i1,
		i2
	)

Value:

((ItemPointerGetBlockNumber(&(i1)) == ItemPointerGetBlockNumber(&(i2))) && \

(ItemPointerGetOffsetNumber(&(i1)) == ItemPointerGetOffsetNumber(&(i2))))

ItemPointerGetOffsetNumber

#define ItemPointerGetOffsetNumber(pointer)

Definition: itemptr.h:95

ItemPointerGetBlockNumber

#define ItemPointerGetBlockNumber(pointer)

Definition: itemptr.h:76

Definition at line 153 of file nbtree.h.

#define MAX_BT_CYCLE_ID 0xFF7F

Definition at line 86 of file nbtree.h.

Referenced by _bt_start_vacuum().

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

#define P_FIRSTKEY ((OffsetNumber) 2)

Definition at line 204 of file nbtree.h.

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

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

Definition at line 182 of file nbtree.h.

Referenced by _bt_findinsertloc(), and palloc_btree_page().

#define P_HIKEY ((OffsetNumber) 1)

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

Definition at line 181 of file nbtree.h.

Referenced by _bt_check_unique(), _bt_findinsertloc(), _bt_get_endpoint(), _bt_getroot(), _bt_getstackbuf(), _bt_gettrueroot(), _bt_moveright(), _bt_readnextpage(), bt_check_level_from_leftmost(), bt_right_page_check_scankey(), bt_target_page_check(), btvacuumpage(), GetBTPageStatistics(), pgstat_btree_page(), and pgstatindex_impl().

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

Definition at line 183 of file nbtree.h.

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

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

Definition at line 178 of file nbtree.h.

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

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

Definition at line 180 of file nbtree.h.

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

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

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

Definition at line 179 of file nbtree.h.

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

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

Definition at line 177 of file nbtree.h.

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

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

Definition at line 174 of file nbtree.h.

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

#define P_NONE 0

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

#define SK_BT_DESC (INDOPTION_DESC << SK_BT_INDOPTION_SHIFT)

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

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

Definition at line 426 of file nbtree.h.

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

#define SK_BT_NULLS_FIRST (INDOPTION_NULLS_FIRST << SK_BT_INDOPTION_SHIFT)

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

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

Definition at line 425 of file nbtree.h.

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

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

Definition at line 424 of file nbtree.h.

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

Typedef Documentation

typedef struct BTArrayKeyInfo BTArrayKeyInfo

typedef uint16 BTCycleId

Definition at line 26 of file nbtree.h.

typedef struct BTMetaPageData BTMetaPageData

typedef BTPageOpaqueData* BTPageOpaque

Definition at line 67 of file nbtree.h.

typedef struct BTPageOpaqueData BTPageOpaqueData

typedef BTScanOpaqueData* BTScanOpaque

Definition at line 417 of file nbtree.h.

typedef struct BTScanOpaqueData BTScanOpaqueData

typedef BTScanPosData* BTScanPos

Definition at line 331 of file nbtree.h.

typedef struct BTScanPosData BTScanPosData

typedef struct BTScanPosItem BTScanPosItem

typedef struct BTSpool BTSpool

Definition at line 550 of file nbtree.h.

typedef BTStackData* BTStack

Definition at line 259 of file nbtree.h.

typedef struct BTStackData BTStackData

Function Documentation

bool _bt_advance_array_keys	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 547 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;
 }

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

Definition at line 323 of file nbtsearch.c.

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

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

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

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

Definition at line 1359 of file nbtutils.c.

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

Referenced by _bt_readpage().

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

void _bt_checkpage	(	Relation	rel,
		Buffer	buf
	)

Definition at line 503 of file nbtpage.c.

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

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

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

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

Definition at line 428 of file nbtsearch.c.

References DatumGetInt32, FunctionCall2Coll(), i, index_getattr, P_FIRSTDATAKEY, P_ISLEAF, PageGetItem, PageGetItemId, PageGetSpecialPointer, RelationGetDescr, result, 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_findinsertloc(), _bt_moveright(), invariant_geq_offset(), invariant_leq_nontarget_offset(), and invariant_leq_offset().

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

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

Definition at line 862 of file nbtpage.c.

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

Referenced by _bt_vacuum_one_page().

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

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

Definition at line 789 of file nbtpage.c.

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

Referenced by btvacuumpage(), and btvacuumscan().

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

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

Definition at line 108 of file nbtinsert.c.

References _bt_binsrch(), _bt_check_unique(), _bt_findinsertloc(), _bt_freeskey(), _bt_freestack(), _bt_insertonpg(), _bt_mkscankey(), _bt_moveright(), _bt_relbuf(), _bt_search(), BT_WRITE, buf, BUFFER_LOCK_UNLOCK, CheckForSerializableConflictIn(), InvalidBuffer, InvalidOffsetNumber, LockBuffer(), RelationData::rd_rel, SpeculativeInsertionWait(), IndexTupleData::t_tid, TransactionIdIsValid, UNIQUE_CHECK_EXISTING, UNIQUE_CHECK_NO, XactLockTableWait(), and XLTW_InsertIndex.

Referenced by btinsert().

 {
     bool        is_unique = false;
     int         natts = rel->rd_rel->relnatts;
     ScanKey     itup_scankey;
     BTStack     stack;
     Buffer      buf;
     OffsetNumber offset;
 
     /* we need an insertion scan key to do our search, so build one */
     itup_scankey = _bt_mkscankey(rel, itup);
 
 top:
     /* find the first page containing this key */
     stack = _bt_search(rel, natts, itup_scankey, false, &buf, BT_WRITE, NULL);
 
     offset = InvalidOffsetNumber;
 
     /* trade in our read lock for a write lock */
     LockBuffer(buf, BUFFER_LOCK_UNLOCK);
     LockBuffer(buf, BT_WRITE);
 
     /*
      * If the page was split between the time that we surrendered our read
      * lock and acquired our write lock, then this page may no longer be the
      * right place for the key we want to insert.  In this case, we need to
      * move right in the tree.  See Lehman and Yao for an excruciatingly
      * precise description.
      */
     buf = _bt_moveright(rel, buf, natts, itup_scankey, false,
                         true, stack, BT_WRITE, NULL);
 
     /*
      * If we're not allowing duplicates, make sure the key isn't already in
      * the index.
      *
      * NOTE: obviously, _bt_check_unique can only detect keys that are already
      * in the index; so it cannot defend against concurrent insertions of the
      * same key.  We protect against that by means of holding a write lock on
      * the target page.  Any other would-be inserter of the same key must
      * acquire a write lock on the same target page, so only one would-be
      * inserter can be making the check at one time.  Furthermore, once we are
      * past the check we hold write locks continuously until we have performed
      * our insertion, so no later inserter can fail to see our insertion.
      * (This requires some care in _bt_insertonpg.)
      *
      * If we must wait for another xact, we release the lock while waiting,
      * and then must start over completely.
      *
      * For a partial uniqueness check, we don't wait for the other xact. Just
      * let the tuple in and return false for possibly non-unique, or true for
      * definitely unique.
      */
     if (checkUnique != UNIQUE_CHECK_NO)
     {
         TransactionId xwait;
         uint32      speculativeToken;
 
         offset = _bt_binsrch(rel, buf, natts, itup_scankey, false);
         xwait = _bt_check_unique(rel, itup, heapRel, buf, offset, itup_scankey,
                                  checkUnique, &is_unique, &speculativeToken);
 
         if (TransactionIdIsValid(xwait))
         {
             /* Have to wait for the other guy ... */
             _bt_relbuf(rel, buf);
 
             /*
              * If it's a speculative insertion, wait for it to finish (ie. to
              * go ahead with the insertion, or kill the tuple).  Otherwise
              * wait for the transaction to finish as usual.
              */
             if (speculativeToken)
                 SpeculativeInsertionWait(xwait, speculativeToken);
             else
                 XactLockTableWait(xwait, rel, &itup->t_tid, XLTW_InsertIndex);
 
             /* start over... */
             _bt_freestack(stack);
             goto top;
         }
     }
 
     if (checkUnique != UNIQUE_CHECK_EXISTING)
     {
         /*
          * The only conflict predicate locking cares about for indexes is when
          * an index tuple insert conflicts with an existing lock.  Since the
          * actual location of the insert is hard to predict because of the
          * random search used to prevent O(N^2) performance when there are
          * many duplicate entries, we can just use the "first valid" page.
          */
         CheckForSerializableConflictIn(rel, NULL, buf);
         /* do the insertion */
         _bt_findinsertloc(rel, &buf, &offset, natts, itup_scankey, itup,
                           stack, heapRel);
         _bt_insertonpg(rel, buf, InvalidBuffer, stack, itup, offset, false);
     }
     else
     {
         /* just release the buffer */
         _bt_relbuf(rel, buf);
     }
 
     /* be tidy */
     _bt_freestack(stack);
     _bt_freeskey(itup_scankey);
 
     return is_unique;
 }

void _bt_end_vacuum ( Relation rel )

Definition at line 1964 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);
 }

void _bt_end_vacuum_callback	(	int	code,
		Datum	arg
	)

Definition at line 1992 of file nbtutils.c.

References _bt_end_vacuum(), and DatumGetPointer.

Referenced by btbulkdelete().

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

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

Definition at line 1739 of file nbtinsert.c.

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

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

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

bool _bt_first	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 536 of file nbtsearch.c.

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

Referenced by btgetbitmap(), and btgettuple().

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

void _bt_freeskey ( ScanKey skey )

Definition at line 155 of file nbtutils.c.

References pfree().

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

 {
     pfree(skey);
 }

void _bt_freestack ( BTStack stack )

Definition at line 164 of file nbtutils.c.

References BTStackData::bts_parent, and pfree().

Referenced by _bt_doinsert(), and _bt_first().

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

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

Definition at line 1764 of file nbtsearch.c.

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

Referenced by _bt_endpoint(), and _bt_insert_parent().

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

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

Definition at line 570 of file nbtpage.c.

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

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

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

Buffer _bt_getroot	(	Relation	rel,
		int	access
	)

Definition at line 104 of file nbtpage.c.

References _bt_getbuf(), _bt_getroot(), _bt_relandgetbuf(), _bt_relbuf(), Assert, BT_READ, BT_WRITE, BTMetaPageData::btm_fastlevel, BTMetaPageData::btm_fastroot, BTMetaPageData::btm_level, BTMetaPageData::btm_magic, BTMetaPageData::btm_root, BTMetaPageData::btm_version, BTP_LEAF, BTP_ROOT, BTPageGetMeta, BTPageOpaqueData::btpo, BTPageOpaqueData::btpo_cycleid, BTPageOpaqueData::btpo_flags, BTPageOpaqueData::btpo_next, BTPageOpaqueData::btpo_prev, BTREE_MAGIC, BTREE_METAPAGE, BTREE_VERSION, BUFFER_LOCK_UNLOCK, BufferGetBlockNumber(), BufferGetPage, elog, END_CRIT_SECTION, ereport, errcode(), errmsg(), ERROR, xl_btree_metadata::fastlevel, xl_btree_metadata::fastroot, InvalidBuffer, xl_btree_metadata::level, BTPageOpaqueData::level, xl_btree_newroot::level, LockBuffer(), MarkBufferDirty(), MemoryContextAlloc(), P_IGNORE, P_ISMETA, P_LEFTMOST, P_NEW, P_NONE, P_RIGHTMOST, PageGetSpecialPointer, PageSetLSN, pfree(), RelationData::rd_amcache, RelationData::rd_indexcxt, REGBUF_WILL_INIT, RelationGetRelationName, RelationNeedsWAL, xl_btree_metadata::root, xl_btree_newroot::rootblk, SizeOfBtreeNewroot, START_CRIT_SECTION, XLOG_BTREE_NEWROOT, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().

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

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

int _bt_getrootheight ( Relation rel )

Definition at line 435 of file nbtpage.c.

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

Referenced by get_relation_info().

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

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

Definition at line 1798 of file nbtinsert.c.

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

Referenced by _bt_insert_parent(), and _bt_lock_branch_parent().

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

Buffer _bt_gettrueroot ( Relation rel )

Definition at line 341 of file nbtpage.c.

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

Referenced by _bt_get_endpoint().

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

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

Definition at line 49 of file nbtpage.c.

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

Referenced by _bt_uppershutdown(), and btbuildempty().

 {
     BTMetaPageData *metad;
     BTPageOpaque metaopaque;
 
     _bt_pageinit(page, BLCKSZ);
 
     metad = BTPageGetMeta(page);
     metad->btm_magic = BTREE_MAGIC;
     metad->btm_version = BTREE_VERSION;
     metad->btm_root = rootbknum;
     metad->btm_level = level;
     metad->btm_fastroot = rootbknum;
     metad->btm_fastlevel = level;
 
     metaopaque = (BTPageOpaque) PageGetSpecialPointer(page);
     metaopaque->btpo_flags = BTP_META;
 
     /*
      * Set pd_lower just past the end of the metadata.  This is not essential
      * but it makes the page look compressible to xlog.c.
      */
     ((PageHeader) page)->pd_lower =
         ((char *) metad + sizeof(BTMetaPageData)) - (char *) page;
 }

void _bt_killitems ( IndexScanDesc scan )

Definition at line 1732 of file nbtutils.c.

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

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

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

void _bt_leafbuild	(	BTSpool *	btspool,
		BTSpool *	spool2
	)

Definition at line 201 of file nbtsort.c.

References _bt_load(), BTREE_METAPAGE, BTWriteState::btws_pages_alloced, BTWriteState::btws_pages_written, BTWriteState::btws_use_wal, BTWriteState::btws_zeropage, BTSpool::heap, BTWriteState::heap, BTSpool::index, BTWriteState::index, log_btree_build_stats, RelationNeedsWAL, ResetUsage(), ShowUsage(), BTSpool::sortstate, tuplesort_performsort(), and XLogIsNeeded.

Referenced by btbuild().

 {
     BTWriteState wstate;
 
 #ifdef BTREE_BUILD_STATS
     if (log_btree_build_stats)
     {
         ShowUsage("BTREE BUILD (Spool) STATISTICS");
         ResetUsage();
     }
 #endif                          /* BTREE_BUILD_STATS */
 
     tuplesort_performsort(btspool->sortstate);
     if (btspool2)
         tuplesort_performsort(btspool2->sortstate);
 
     wstate.heap = btspool->heap;
     wstate.index = btspool->index;
 
     /*
      * We need to log index creation in WAL iff WAL archiving/streaming is
      * enabled UNLESS the index isn't WAL-logged anyway.
      */
     wstate.btws_use_wal = XLogIsNeeded() && RelationNeedsWAL(wstate.index);
 
     /* reserve the metapage */
     wstate.btws_pages_alloced = BTREE_METAPAGE + 1;
     wstate.btws_pages_written = 0;
     wstate.btws_zeropage = NULL;    /* until needed */
 
     _bt_load(&wstate, btspool, btspool2);
 }

void _bt_mark_array_keys ( IndexScanDesc scan )

Definition at line 606 of file nbtutils.c.

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

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

ScanKey _bt_mkscankey	(	Relation	rel,
		IndexTuple	itup
	)

Definition at line 62 of file nbtutils.c.

References arg, BTORDER_PROC, i, index_getattr, index_getprocinfo(), InvalidOid, InvalidStrategy, palloc(), RelationData::rd_indcollation, RelationData::rd_indoption, RelationGetDescr, RelationGetNumberOfAttributes, ScanKeyEntryInitializeWithInfo(), SK_BT_INDOPTION_SHIFT, and SK_ISNULL.

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

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

ScanKey _bt_mkscankey_nodata ( Relation rel )

Definition at line 115 of file nbtutils.c.

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

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

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

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

Definition at line 214 of file nbtsearch.c.

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

Referenced by _bt_doinsert(), and _bt_search().

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

bool _bt_next	(	IndexScanDesc	scan,
		ScanDirection	dir
	)

Definition at line 1129 of file nbtsearch.c.

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

Referenced by btgetbitmap(), and btgettuple().

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

bool _bt_page_recyclable ( Page page )

Definition at line 744 of file nbtpage.c.

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

Referenced by _bt_getbuf(), and btvacuumpage().

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

int _bt_pagedel	(	Relation	rel,
		Buffer	buf
	)

Definition at line 1109 of file nbtpage.c.

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

Referenced by btvacuumpage().

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

void _bt_pageinit	(	Page	page,
		Size	size
	)

Definition at line 732 of file nbtpage.c.

References PageInit().

Referenced by _bt_blnewpage(), _bt_getbuf(), _bt_initmetapage(), _bt_restore_meta(), _bt_split(), btree_xlog_mark_page_halfdead(), btree_xlog_newroot(), btree_xlog_split(), and btree_xlog_unlink_page().

 {
     PageInit(page, size, sizeof(BTPageOpaqueData));
 }

void _bt_parallel_advance_array_keys ( IndexScanDesc scan )

Definition at line 888 of file nbtree.c.

References BTScanOpaqueData::arrayKeyCount, BTPARALLEL_DONE, BTPARALLEL_NOT_INITIALIZED, InvalidBlockNumber, OffsetToPointer, IndexScanDescData::opaque, IndexScanDescData::parallel_scan, SpinLockAcquire, and SpinLockRelease.

Referenced by _bt_advance_array_keys().

 {
     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
     BTParallelScanDesc btscan;
 
     btscan = (BTParallelScanDesc) OffsetToPointer((void *) parallel_scan,
                                                   parallel_scan->ps_offset);
 
     so->arrayKeyCount++;
     SpinLockAcquire(&btscan->btps_mutex);
     if (btscan->btps_pageStatus == BTPARALLEL_DONE)
     {
         btscan->btps_scanPage = InvalidBlockNumber;
         btscan->btps_pageStatus = BTPARALLEL_NOT_INITIALIZED;
         btscan->btps_arrayKeyCount++;
     }
     SpinLockRelease(&btscan->btps_mutex);
 }

void _bt_parallel_done ( IndexScanDesc scan )

Definition at line 847 of file nbtree.c.

References BTScanOpaqueData::arrayKeyCount, BTPARALLEL_DONE, ConditionVariableBroadcast(), OffsetToPointer, IndexScanDescData::opaque, IndexScanDescData::parallel_scan, SpinLockAcquire, and SpinLockRelease.

Referenced by _bt_first(), and _bt_readnextpage().

 {
     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
     BTParallelScanDesc btscan;
     bool        status_changed = false;
 
     /* Do nothing, for non-parallel scans */
     if (parallel_scan == NULL)
         return;
 
     btscan = (BTParallelScanDesc) OffsetToPointer((void *) parallel_scan,
                                                   parallel_scan->ps_offset);
 
     /*
      * Mark the parallel scan as done for this combination of scan keys,
      * unless some other process already did so.  See also
      * _bt_advance_array_keys.
      */
     SpinLockAcquire(&btscan->btps_mutex);
     if (so->arrayKeyCount >= btscan->btps_arrayKeyCount &&
         btscan->btps_pageStatus != BTPARALLEL_DONE)
     {
         btscan->btps_pageStatus = BTPARALLEL_DONE;
         status_changed = true;
     }
     SpinLockRelease(&btscan->btps_mutex);
 
     /* wake up all the workers associated with this parallel scan */
     if (status_changed)
         ConditionVariableBroadcast(&btscan->btps_cv);
 }

void _bt_parallel_release	(	IndexScanDesc	scan,
		BlockNumber	scan_page
	)

Definition at line 824 of file nbtree.c.

References BTPARALLEL_IDLE, BTParallelScanDescData::btps_cv, BTParallelScanDescData::btps_mutex, BTParallelScanDescData::btps_pageStatus, BTParallelScanDescData::btps_scanPage, ConditionVariableSignal(), OffsetToPointer, IndexScanDescData::parallel_scan, ParallelIndexScanDescData::ps_offset, SpinLockAcquire, and SpinLockRelease.

Referenced by _bt_readpage().

 {
     ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
     BTParallelScanDesc btscan;
 
     btscan = (BTParallelScanDesc) OffsetToPointer((void *) parallel_scan,
                                                   parallel_scan->ps_offset);
 
     SpinLockAcquire(&btscan->btps_mutex);
     btscan->btps_scanPage = scan_page;
     btscan->btps_pageStatus = BTPARALLEL_IDLE;
     SpinLockRelease(&btscan->btps_mutex);
     ConditionVariableSignal(&btscan->btps_cv);
 }

bool _bt_parallel_seize	(	IndexScanDesc	scan,
		BlockNumber *	pageno
	)

Definition at line 766 of file nbtree.c.

References BTScanOpaqueData::arrayKeyCount, BTPARALLEL_ADVANCING, BTPARALLEL_DONE, ConditionVariableCancelSleep(), ConditionVariableSleep(), OffsetToPointer, IndexScanDescData::opaque, P_NONE, IndexScanDescData::parallel_scan, SpinLockAcquire, SpinLockRelease, status(), and WAIT_EVENT_BTREE_PAGE.

Referenced by _bt_first(), _bt_readnextpage(), and _bt_steppage().

 {
     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     BTPS_State  pageStatus;
     bool        exit_loop = false;
     bool        status = true;
     ParallelIndexScanDesc parallel_scan = scan->parallel_scan;
     BTParallelScanDesc btscan;
 
     *pageno = P_NONE;
 
     btscan = (BTParallelScanDesc) OffsetToPointer((void *) parallel_scan,
                                                   parallel_scan->ps_offset);
 
     while (1)
     {
         SpinLockAcquire(&btscan->btps_mutex);
         pageStatus = btscan->btps_pageStatus;
 
         if (so->arrayKeyCount < btscan->btps_arrayKeyCount)
         {
             /* Parallel scan has already advanced to a new set of scankeys. */
             status = false;
         }
         else if (pageStatus == BTPARALLEL_DONE)
         {
             /*
              * We're done with this set of scankeys.  This may be the end, or
              * there could be more sets to try.
              */
             status = false;
         }
         else if (pageStatus != BTPARALLEL_ADVANCING)
         {
             /*
              * We have successfully seized control of the scan for the purpose
              * of advancing it to a new page!
              */
             btscan->btps_pageStatus = BTPARALLEL_ADVANCING;
             *pageno = btscan->btps_scanPage;
             exit_loop = true;
         }
         SpinLockRelease(&btscan->btps_mutex);
         if (exit_loop || !status)
             break;
         ConditionVariableSleep(&btscan->btps_cv, WAIT_EVENT_BTREE_PAGE);
     }
     ConditionVariableCancelSleep();
 
     return status;
 }

void _bt_preprocess_array_keys ( IndexScanDesc scan )

Definition at line 192 of file nbtutils.c.

References _bt_find_extreme_element(), _bt_sort_array_elements(), ALLOCSET_SMALL_SIZES, AllocSetContextCreate(), ARR_ELEMTYPE, BTScanOpaqueData::arrayContext, BTScanOpaqueData::arrayKeyData, BTScanOpaqueData::arrayKeys, Assert, BTEqualStrategyNumber, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, cur, CurrentMemoryContext, DatumGetArrayTypeP, deconstruct_array(), BTArrayKeyInfo::elem_values, elog, ERROR, get_typlenbyvalalign(), i, IndexScanDescData::indexRelation, INDOPTION_DESC, IndexScanDescData::keyData, MemoryContextReset(), MemoryContextSwitchTo(), BTArrayKeyInfo::num_elems, BTScanOpaqueData::numArrayKeys, IndexScanDescData::numberOfKeys, IndexScanDescData::opaque, palloc(), palloc0(), RelationData::rd_indoption, BTArrayKeyInfo::scan_key, SK_ISNULL, SK_ROW_HEADER, SK_SEARCHARRAY, SK_SEARCHNOTNULL, and SK_SEARCHNULL.

Referenced by btrescan().

 {
     BTScanOpaque so = (BTScanOpaque) scan->opaque;
     int         numberOfKeys = scan->numberOfKeys;
     int16      *indoption = scan->indexRelation->rd_indoption;
     int         numArrayKeys;
     ScanKey     cur;
     int         i;
     MemoryContext oldContext;
 
     /* Quick check to see if there are any array keys */
     numArrayKeys = 0;
     for (i = 0; i < numberOfKeys; i++)
     {
         cur = &scan->keyData[i];
         if (cur->sk_flags & SK_SEARCHARRAY)
         {
             numArrayKeys++;
             Assert(!(cur->sk_flags & (SK_ROW_HEADER | SK_SEARCHNULL | SK_SEARCHNOTNULL)));
             /* If any arrays are null as a whole, we can quit right now. */
             if (cur->sk_flags & SK_ISNULL)
             {
                 so->numArrayKeys = -1;
                 so->arrayKeyData = NULL;
                 return;
             }
         }
     }
 
     /* Quit if nothing to do. */
     if (numArrayKeys == 0)
     {
         so->numArrayKeys = 0;
         so->arrayKeyData = NULL;
         return;
     }
 
     /*
      * Make a scan-lifespan context to hold array-associated data, or reset it
      * if we already have one from a previous rescan cycle.
      */
     if (so->arrayContext == NULL)
         so->arrayContext = AllocSetContextCreate(CurrentMemoryContext,
                                                  "BTree array context",
                                                  ALLOCSET_SMALL_SIZES);
     else
         MemoryContextReset(so->arrayContext);
 
     oldContext = MemoryContextSwitchTo(so->arrayContext);
 
     /* Create modifiable copy of scan->keyData in the workspace context */
     so->arrayKeyData = (ScanKey) palloc(scan->numberOfKeys * sizeof(ScanKeyData));
     memcpy(so->arrayKeyData,
            scan->keyData,
            scan->numberOfKeys * sizeof(ScanKeyData));
 
     /* Allocate space for per-array data in the workspace context */
     so->arrayKeys = (BTArrayKeyInfo *) palloc0(numArrayKeys * sizeof(BTArrayKeyInfo));
 
     /* Now process each array key */
     numArrayKeys = 0;
     for (i = 0; i < numberOfKeys; i++)
     {
         ArrayType  *arrayval;
         int16       elmlen;
         bool        elmbyval;
         char        elmalign;
         int         num_elems;
         Datum      *elem_values;
         bool       *elem_nulls;
         int         num_nonnulls;
         int         j;
 
         cur = &so->arrayKeyData[i];
         if (!(cur->sk_flags & SK_SEARCHARRAY))
             continue;
 
         /*
          * First, deconstruct the array into elements.  Anything allocated
          * here (including a possibly detoasted array value) is in the
          * workspace context.
          */
         arrayval = DatumGetArrayTypeP(cur->sk_argument);
         /* We could cache this data, but not clear it's worth it */
         get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
                              &elmlen, &elmbyval, &elmalign);
         deconstruct_array(arrayval,
                           ARR_ELEMTYPE(arrayval),
                           elmlen, elmbyval, elmalign,
                           &elem_values, &elem_nulls, &num_elems);
 
         /*
          * Compress out any null elements.  We can ignore them since we assume
          * all btree operators are strict.
          */
         num_nonnulls = 0;
         for (j = 0; j < num_elems; j++)
         {
             if (!elem_nulls[j])
                 elem_values[num_nonnulls++] = elem_values[j];
         }
 
         /* We could pfree(elem_nulls) now, but not worth the cycles */
 
         /* If there's no non-nulls, the scan qual is unsatisfiable */
         if (num_nonnulls == 0)
         {
             numArrayKeys = -1;
             break;
         }
 
         /*
          * If the comparison operator is not equality, then the array qual
          * degenerates to a simple comparison against the smallest or largest
          * non-null array element, as appropriate.
          */
         switch (cur->sk_strategy)
         {
             case BTLessStrategyNumber:
             case BTLessEqualStrategyNumber:
                 cur->sk_argument =
                     _bt_find_extreme_element(scan, cur,
                                              BTGreaterStrategyNumber,
                                              elem_values, num_nonnulls);
                 continue;
             case BTEqualStrategyNumber:
                 /* proceed with rest of loop */
                 break;
             case BTGreaterEqualStrategyNumber:
             case BTGreaterStrategyNumber:
                 cur->sk_argument =
                     _bt_find_extreme_element(scan, cur,

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

Typedef Documentation

Function Documentation