30#define BTREE_FASTPATH_MIN_LEVEL 2
55 bool split_only_page);
67 bool simpleonly,
bool checkingunique,
68 bool uniquedup,
bool indexUnchanged);
76static inline int _bt_blk_cmp(
const void *arg1,
const void *arg2);
106 bool is_unique =
false;
133 checkingunique =
false;
153 insertstate.
itup = itup;
211 &is_unique, &speculativeToken);
224 if (speculativeToken)
259 indexUnchanged, stack, heapRel);
261 stack, itup, insertstate.
itemsz, newitemoff,
423 bool inposting =
false;
424 bool prevalldead =
true;
469 if (offset <= maxoff)
508 bool all_dead =
false;
526 htid = curitup->
t_tid;
587 SnapshotDirty.
xmin : SnapshotDirty.
xmax;
667 (
errcode(ERRCODE_UNIQUE_VIOLATION),
668 errmsg(
"duplicate key value violates unique constraint \"%s\"",
670 key_desc ?
errdetail(
"Key %s already exists.",
676 else if (all_dead && (!inposting ||
702 if (!all_dead && inposting)
713 else if (offset < maxoff)
742 elog(
ERROR,
"fell off the end of index \"%s\"",
761 (
errcode(ERRCODE_INTERNAL_ERROR),
762 errmsg(
"failed to re-find tuple within index \"%s\"",
764 errhint(
"This may be because of a non-immutable index expression."),
843 bool uniquedup = indexUnchanged;
905 checkingunique, uniquedup,
948 false,
false,
false);
999 false,
false,
false);
1063 elog(
ERROR,
"fell off the end of index \"%s\"",
1070 insertstate->
buf = rbuf;
1115 bool split_only_page)
1159 if (postingoff != 0)
1186 (
errcode(ERRCODE_INDEX_CORRUPTED),
1187 errmsg_internal(
"table tid from new index tuple (%u,%u) overlaps with invalid duplicate tuple at offset %u of block %u in index \"%s\"",
1214 Assert(!split_only_page);
1217 rbuf =
_bt_split(rel, heaprel, itup_key,
buf, cbuf, newitemoff, itemsz,
1218 itup, origitup, nposting, postingoff);
1277 if (postingoff != 0)
1282 elog(
PANIC,
"failed to add new item to block %u in index \"%s\"",
1307 cpageop->
btpo_flags &= ~BTP_INCOMPLETE_SPLIT;
1320 xlrec.
offnum = newitemoff;
1325 if (isleaf && postingoff == 0)
1330 else if (postingoff != 0)
1367 if (postingoff == 0)
1382 upostingoff = postingoff;
1412 if (isrightmost && isleaf && !isroot)
1431 if (postingoff != 0)
1543 newitem, &newitemonleft);
1589 if (postingoff != 0)
1593 &newitem->
t_tid) < 0);
1618 if (!newitemonleft && newitemoff == firstrightoff)
1622 firstright = newitem;
1630 if (firstrightoff == origpagepostingoff)
1631 firstright = nposting;
1639 if (newitemonleft && newitemoff == firstrightoff)
1653 if (lastleftoff == origpagepostingoff)
1654 lastleft = nposting;
1657 lefthighkey =
_bt_truncate(rel, lastleft, firstright, itup_key);
1688 lefthighkey = firstright;
1700 if (
PageAddItem(leftpage, (
Item) lefthighkey, itemsz, afterleftoff,
false,
1702 elog(
ERROR,
"failed to add high key to the left sibling"
1703 " while splitting block %u of index \"%s\"",
1767 if (
PageAddItem(rightpage, (
Item) righthighkey, itemsz, afterrightoff,
1771 elog(
ERROR,
"failed to add high key to the right sibling"
1772 " while splitting block %u of index \"%s\"",
1784 minusinfoff = afterrightoff;
1802 if (
i == origpagepostingoff)
1806 dataitem = nposting;
1810 else if (
i == newitemoff)
1814 Assert(newitemoff <= firstrightoff);
1815 if (!
_bt_pgaddtup(leftpage, newitemsz, newitem, afterleftoff,
1819 elog(
ERROR,
"failed to add new item to the left sibling"
1820 " while splitting block %u of index \"%s\"",
1827 Assert(newitemoff >= firstrightoff);
1828 if (!
_bt_pgaddtup(rightpage, newitemsz, newitem, afterrightoff,
1829 afterrightoff == minusinfoff))
1832 elog(
ERROR,
"failed to add new item to the right sibling"
1833 " while splitting block %u of index \"%s\"",
1841 if (
i < firstrightoff)
1843 if (!
_bt_pgaddtup(leftpage, itemsz, dataitem, afterleftoff,
false))
1846 elog(
ERROR,
"failed to add old item to the left sibling"
1847 " while splitting block %u of index \"%s\"",
1854 if (!
_bt_pgaddtup(rightpage, itemsz, dataitem, afterrightoff,
1855 afterrightoff == minusinfoff))
1858 elog(
ERROR,
"failed to add old item to the right sibling"
1859 " while splitting block %u of index \"%s\"",
1867 if (
i <= newitemoff)
1874 Assert(!newitemonleft && newitemoff == maxoff + 1);
1875 if (!
_bt_pgaddtup(rightpage, newitemsz, newitem, afterrightoff,
1876 afterrightoff == minusinfoff))
1879 elog(
ERROR,
"failed to add new item to the right sibling"
1880 " while splitting block %u of index \"%s\"",
1896 if (sopaque->
btpo_prev != origpagenumber)
1900 (
errcode(ERRCODE_INDEX_CORRUPTED),
1902 "block %u links to %u instead of expected %u in index \"%s\"",
1962 cpageop->
btpo_flags &= ~BTP_INCOMPLETE_SPLIT;
1978 if (postingoff != 0 && origpagepostingoff < firstrightoff)
2024 Assert(newitemonleft || firstrightoff == newitemoff);
2050 (
char *) rightpage + ((
PageHeader) rightpage)->pd_upper,
2213 (
errcode(ERRCODE_INDEX_CORRUPTED),
2214 errmsg_internal(
"failed to re-find parent key in index \"%s\" for split pages %u/%u",
2281 elog(
DEBUG1,
"finishing incomplete split of %u/%u",
2375 for (offnum =
start;
2486 left_item->
t_info = left_item_sz;
2532 elog(
PANIC,
"failed to add leftkey to new root page"
2533 " while splitting block %u of index \"%s\"",
2544 elog(
PANIC,
"failed to add rightkey to new root page"
2545 " while splitting block %u of index \"%s\"",
2550 lopaque->
btpo_flags &= ~BTP_INCOMPLETE_SPLIT;
2575 md.
root = rootblknum;
2589 (
char *) rootpage + ((
PageHeader) rootpage)->pd_upper,
2634 bool newfirstdataitem)
2638 if (newfirstdataitem)
2685 bool simpleonly,
bool checkingunique,
2686 bool uniquedup,
bool indexUnchanged)
2700 Assert(!simpleonly || (!checkingunique && !uniquedup && !indexUnchanged));
2711 for (offnum = minoff;
2718 deletable[ndeletable++] = offnum;
2724 insertstate->
itup, minoff, maxoff);
2748 if (simpleonly || (checkingunique && !uniquedup))
2774 if ((indexUnchanged || uniquedup) &&
2781 (indexUnchanged || uniquedup));
2823 deadblocks =
_bt_deadblocks(page, deletable, ndeletable, newitem,
2827 delstate.
irel = rel;
2835 for (offnum = minoff;
2849 match = bsearch(&tidblock, deadblocks, ndeadblocks,
2875 for (
int p = 0; p < nitem; p++)
2880 match = bsearch(&tidblock, deadblocks, ndeadblocks,
2893 odeltid->
tid = *tid;
2951 spacentids = ndeletable + 1;
2963 for (
int i = 0;
i < ndeletable;
i++)
2972 if (ntids + 1 > spacentids)
2985 if (ntids + nposting > spacentids)
2987 spacentids =
Max(spacentids * 2, ntids + nposting);
2992 for (
int j = 0;
j < nposting;
j++)
#define InvalidBlockNumber
static bool BlockNumberIsValid(BlockNumber blockNumber)
static Datum values[MAXATTR]
BlockNumber BufferGetBlockNumber(Buffer buffer)
void ReleaseBuffer(Buffer buffer)
void MarkBufferDirty(Buffer buffer)
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
static Page BufferGetPage(Buffer buffer)
static Size BufferGetPageSize(Buffer buffer)
static bool BufferIsValid(Buffer bufnum)
Size PageGetFreeSpace(const PageData *page)
void PageRestoreTempPage(Page tempPage, Page oldPage)
Page PageGetTempPage(const PageData *page)
static Item PageGetItem(const PageData *page, const ItemIdData *itemId)
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
static void PageSetLSN(Page page, XLogRecPtr lsn)
static XLogRecPtr PageGetLSN(const PageData *page)
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
#define Assert(condition)
int errmsg_internal(const char *fmt,...)
int errdetail(const char *fmt,...)
int errhint(const char *fmt,...)
int errcode(int sqlerrcode)
int errmsg(const char *fmt,...)
#define ereport(elevel,...)
char * BuildIndexValueDescription(Relation indexRelation, const Datum *values, const bool *isnull)
void index_deform_tuple(IndexTuple tup, TupleDesc tupleDescriptor, Datum *values, bool *isnull)
IndexTuple CopyIndexTuple(IndexTuple source)
static int pg_cmp_u32(uint32 a, uint32 b)
if(TABLE==NULL||TABLE_index==NULL)
#define ItemIdMarkDead(itemId)
#define ItemIdGetLength(itemId)
#define ItemIdIsDead(itemId)
int32 ItemPointerCompare(ItemPointer arg1, ItemPointer arg2)
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
IndexTupleData * IndexTuple
struct IndexTupleData IndexTupleData
static Size IndexTupleSize(const IndexTupleData *itup)
#define MaxIndexTuplesPerPage
void XactLockTableWait(TransactionId xid, Relation rel, ItemPointer ctid, XLTW_Oper oper)
void SpeculativeInsertionWait(TransactionId xid, uint32 token)
void * repalloc(void *pointer, Size size)
void pfree(void *pointer)
#define START_CRIT_SECTION()
#define END_CRIT_SECTION()
IndexTuple _bt_swap_posting(IndexTuple newitem, IndexTuple oposting, int postingoff)
void _bt_dedup_pass(Relation rel, Buffer buf, IndexTuple newitem, Size newitemsz, bool bottomupdedup)
bool _bt_bottomupdel_pass(Relation rel, Buffer buf, Relation heapRel, Size newitemsz)
static BTStack _bt_search_insert(Relation rel, Relation heaprel, BTInsertState insertstate)
#define BTREE_FASTPATH_MIN_LEVEL
static OffsetNumber _bt_findinsertloc(Relation rel, BTInsertState insertstate, bool checkingunique, bool indexUnchanged, BTStack stack, Relation heapRel)
Buffer _bt_getstackbuf(Relation rel, Relation heaprel, BTStack stack, BlockNumber child)
static void _bt_simpledel_pass(Relation rel, Buffer buffer, Relation heapRel, OffsetNumber *deletable, int ndeletable, IndexTuple newitem, OffsetNumber minoff, OffsetNumber maxoff)
bool _bt_doinsert(Relation rel, IndexTuple itup, IndexUniqueCheck checkUnique, bool indexUnchanged, Relation heapRel)
static bool _bt_pgaddtup(Page page, Size itemsize, IndexTuple itup, OffsetNumber itup_off, bool newfirstdataitem)
static Buffer _bt_newlevel(Relation rel, Relation heaprel, Buffer lbuf, Buffer rbuf)
static void _bt_insert_parent(Relation rel, Relation heaprel, Buffer buf, Buffer rbuf, BTStack stack, bool isroot, bool isonly)
static void _bt_delete_or_dedup_one_page(Relation rel, Relation heapRel, BTInsertState insertstate, bool simpleonly, bool checkingunique, bool uniquedup, bool indexUnchanged)
void _bt_finish_split(Relation rel, Relation heaprel, Buffer lbuf, BTStack stack)
static Buffer _bt_split(Relation rel, Relation heaprel, BTScanInsert itup_key, Buffer buf, Buffer cbuf, OffsetNumber newitemoff, Size newitemsz, IndexTuple newitem, IndexTuple orignewitem, IndexTuple nposting, uint16 postingoff)
static int _bt_blk_cmp(const void *arg1, const void *arg2)
static void _bt_stepright(Relation rel, Relation heaprel, BTInsertState insertstate, BTStack stack)
static void _bt_insertonpg(Relation rel, Relation heaprel, BTScanInsert itup_key, Buffer buf, Buffer cbuf, BTStack stack, IndexTuple itup, Size itemsz, OffsetNumber newitemoff, int postingoff, bool split_only_page)
static TransactionId _bt_check_unique(Relation rel, BTInsertState insertstate, Relation heapRel, IndexUniqueCheck checkUnique, bool *is_unique, uint32 *speculativeToken)
static BlockNumber * _bt_deadblocks(Page page, OffsetNumber *deletable, int ndeletable, IndexTuple newitem, int *nblocks)
Buffer _bt_relandgetbuf(Relation rel, Buffer obuf, BlockNumber blkno, int access)
void _bt_upgrademetapage(Page page)
void _bt_relbuf(Relation rel, Buffer buf)
int _bt_getrootheight(Relation rel)
void _bt_pageinit(Page page, Size size)
Buffer _bt_allocbuf(Relation rel, Relation heaprel)
void _bt_checkpage(Relation rel, Buffer buf)
bool _bt_conditionallockbuf(Relation rel, Buffer buf)
Buffer _bt_getbuf(Relation rel, BlockNumber blkno, int access)
void _bt_delitems_delete_check(Relation rel, Buffer buf, Relation heapRel, TM_IndexDeleteOp *delstate)
#define BTGetDeduplicateItems(relation)
static uint16 BTreeTupleGetNPosting(IndexTuple posting)
static bool BTreeTupleIsPivot(IndexTuple itup)
#define P_HAS_GARBAGE(opaque)
#define P_LEFTMOST(opaque)
#define BTPageGetOpaque(page)
#define MaxTIDsPerBTreePage
static void BTreeTupleSetDownLink(IndexTuple pivot, BlockNumber blkno)
#define P_FIRSTDATAKEY(opaque)
#define P_RIGHTMOST(opaque)
#define BTMaxItemSize(page)
#define P_INCOMPLETE_SPLIT(opaque)
#define BTP_INCOMPLETE_SPLIT
static ItemPointer BTreeTupleGetPostingN(IndexTuple posting, int n)
static BlockNumber BTreeTupleGetDownLink(IndexTuple pivot)
static bool BTreeTupleIsPosting(IndexTuple itup)
#define BTREE_NOVAC_VERSION
static void BTreeTupleSetNAtts(IndexTuple itup, uint16 nkeyatts, bool heaptid)
#define BTreeTupleGetNAtts(itup, rel)
Buffer _bt_get_endpoint(Relation rel, uint32 level, bool rightmost)
BTStack _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP, int access)
OffsetNumber _bt_binsrch_insert(Relation rel, BTInsertState insertstate)
int32 _bt_compare(Relation rel, BTScanInsert key, Page page, OffsetNumber offnum)
OffsetNumber _bt_findsplitloc(Relation rel, Page origpage, OffsetNumber newitemoff, Size newitemsz, IndexTuple newitem, bool *newitemonleft)
void _bt_check_third_page(Relation rel, Relation heap, bool needheaptidspace, Page page, IndexTuple newtup)
void _bt_freestack(BTStack stack)
BTCycleId _bt_vacuum_cycleid(Relation rel)
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
IndexTuple _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright, BTScanInsert itup_key)
#define XLOG_BTREE_INSERT_POST
#define SizeOfBtreeInsert
#define XLOG_BTREE_SPLIT_R
#define XLOG_BTREE_INSERT_LEAF
#define XLOG_BTREE_INSERT_UPPER
#define SizeOfBtreeNewroot
#define XLOG_BTREE_INSERT_META
#define XLOG_BTREE_SPLIT_L
#define XLOG_BTREE_NEWROOT
#define InvalidOffsetNumber
#define OffsetNumberNext(offsetNumber)
#define OffsetNumberPrev(offsetNumber)
uint32 pg_prng_uint32(pg_prng_state *state)
pg_prng_state pg_global_prng_state
#define qsort(a, b, c, d)
void PredicateLockPageSplit(Relation relation, BlockNumber oldblkno, BlockNumber newblkno)
void CheckForSerializableConflictIn(Relation relation, ItemPointer tid, BlockNumber blkno)
static size_t qunique(void *array, size_t elements, size_t width, int(*compare)(const void *, const void *))
#define RelationGetDescr(relation)
#define RelationGetRelationName(relation)
#define RelationGetTargetBlock(relation)
#define RelationNeedsWAL(relation)
#define RelationSetTargetBlock(relation, targblock)
#define IndexRelationGetNumberOfAttributes(relation)
#define IndexRelationGetNumberOfKeyAttributes(relation)
int errtableconstraint(Relation rel, const char *conname)
#define InitDirtySnapshot(snapshotdata)
uint32 btm_last_cleanup_num_delpages
struct BTStackData * bts_parent
OffsetNumber firstrightoff
bool table_index_fetch_tuple_check(Relation rel, ItemPointer tid, Snapshot snapshot, bool *all_dead)
#define InvalidTransactionId
#define TransactionIdIsValid(xid)
XLogRecPtr XLogInsert(RmgrId rmid, uint8 info)
void XLogRegisterBufData(uint8 block_id, const void *data, uint32 len)
void XLogRegisterData(const void *data, uint32 len)
void XLogRegisterBuffer(uint8 block_id, Buffer buffer, uint8 flags)
void XLogBeginInsert(void)