30 #define BTREE_FASTPATH_MIN_LEVEL 2
53 bool split_only_page);
59 BTStack stack,
bool isroot,
bool isonly);
65 bool simpleonly,
bool checkingunique,
66 bool uniquedup,
bool indexUnchanged);
74 static inline int _bt_blk_cmp(
const void *arg1,
const void *arg2);
104 bool is_unique =
false;
131 checkingunique =
false;
151 insertstate.
itup = itup;
209 &is_unique, &speculativeToken);
222 if (speculativeToken)
257 indexUnchanged, stack, heapRel);
259 itup, insertstate.
itemsz, newitemoff,
421 bool inposting =
false;
422 bool prevalldead =
true;
467 if (offset <= maxoff)
506 bool all_dead =
false;
524 htid = curitup->
t_tid;
585 SnapshotDirty.
xmin : SnapshotDirty.
xmax;
665 (
errcode(ERRCODE_UNIQUE_VIOLATION),
666 errmsg(
"duplicate key value violates unique constraint \"%s\"",
668 key_desc ?
errdetail(
"Key %s already exists.",
674 else if (all_dead && (!inposting ||
700 if (!all_dead && inposting)
711 else if (offset < maxoff)
740 elog(
ERROR,
"fell off the end of index \"%s\"",
759 (
errcode(ERRCODE_INTERNAL_ERROR),
760 errmsg(
"failed to re-find tuple within index \"%s\"",
762 errhint(
"This may be because of a non-immutable index expression."),
841 bool uniquedup = indexUnchanged;
903 checkingunique, uniquedup,
946 false,
false,
false);
997 false,
false,
false);
1059 elog(
ERROR,
"fell off the end of index \"%s\"",
1066 insertstate->
buf = rbuf;
1110 bool split_only_page)
1154 if (postingoff != 0)
1181 (
errcode(ERRCODE_INDEX_CORRUPTED),
1182 errmsg_internal(
"table tid from new index tuple (%u,%u) overlaps with invalid duplicate tuple at offset %u of block %u in index \"%s\"",
1209 Assert(!split_only_page);
1212 rbuf =
_bt_split(rel, itup_key,
buf, cbuf, newitemoff, itemsz, itup,
1213 origitup, nposting, postingoff);
1272 if (postingoff != 0)
1277 elog(
PANIC,
"failed to add new item to block %u in index \"%s\"",
1315 xlrec.
offnum = newitemoff;
1320 if (isleaf && postingoff == 0)
1325 else if (postingoff != 0)
1362 if (postingoff == 0)
1377 upostingoff = postingoff;
1407 if (isrightmost && isleaf && !isroot)
1426 if (postingoff != 0)
1538 newitem, &newitemonleft);
1584 if (postingoff != 0)
1588 &newitem->
t_tid) < 0);
1613 if (!newitemonleft && newitemoff == firstrightoff)
1617 firstright = newitem;
1625 if (firstrightoff == origpagepostingoff)
1626 firstright = nposting;
1634 if (newitemonleft && newitemoff == firstrightoff)
1648 if (lastleftoff == origpagepostingoff)
1649 lastleft = nposting;
1652 lefthighkey =
_bt_truncate(rel, lastleft, firstright, itup_key);
1683 lefthighkey = firstright;
1695 if (
PageAddItem(leftpage, (
Item) lefthighkey, itemsz, afterleftoff,
false,
1697 elog(
ERROR,
"failed to add high key to the left sibling"
1698 " while splitting block %u of index \"%s\"",
1762 if (
PageAddItem(rightpage, (
Item) righthighkey, itemsz, afterrightoff,
1766 elog(
ERROR,
"failed to add high key to the right sibling"
1767 " while splitting block %u of index \"%s\"",
1779 minusinfoff = afterrightoff;
1797 if (
i == origpagepostingoff)
1801 dataitem = nposting;
1805 else if (
i == newitemoff)
1809 Assert(newitemoff <= firstrightoff);
1810 if (!
_bt_pgaddtup(leftpage, newitemsz, newitem, afterleftoff,
1814 elog(
ERROR,
"failed to add new item to the left sibling"
1815 " while splitting block %u of index \"%s\"",
1822 Assert(newitemoff >= firstrightoff);
1823 if (!
_bt_pgaddtup(rightpage, newitemsz, newitem, afterrightoff,
1824 afterrightoff == minusinfoff))
1827 elog(
ERROR,
"failed to add new item to the right sibling"
1828 " while splitting block %u of index \"%s\"",
1836 if (
i < firstrightoff)
1838 if (!
_bt_pgaddtup(leftpage, itemsz, dataitem, afterleftoff,
false))
1841 elog(
ERROR,
"failed to add old item to the left sibling"
1842 " while splitting block %u of index \"%s\"",
1849 if (!
_bt_pgaddtup(rightpage, itemsz, dataitem, afterrightoff,
1850 afterrightoff == minusinfoff))
1853 elog(
ERROR,
"failed to add old item to the right sibling"
1854 " while splitting block %u of index \"%s\"",
1862 if (
i <= newitemoff)
1869 Assert(!newitemonleft && newitemoff == maxoff + 1);
1870 if (!
_bt_pgaddtup(rightpage, newitemsz, newitem, afterrightoff,
1871 afterrightoff == minusinfoff))
1874 elog(
ERROR,
"failed to add new item to the right sibling"
1875 " while splitting block %u of index \"%s\"",
1891 if (sopaque->
btpo_prev != origpagenumber)
1895 (
errcode(ERRCODE_INDEX_CORRUPTED),
1897 "block %u links to %u instead of expected %u in index \"%s\"",
1973 if (postingoff != 0 && origpagepostingoff < firstrightoff)
2019 Assert(newitemonleft || firstrightoff == newitemoff);
2045 (
char *) rightpage + ((
PageHeader) rightpage)->pd_upper,
2205 (
errcode(ERRCODE_INDEX_CORRUPTED),
2206 errmsg_internal(
"failed to re-find parent key in index \"%s\" for split pages %u/%u",
2269 elog(
DEBUG1,
"finishing incomplete split of %u/%u",
2362 for (offnum = start;
2473 left_item->
t_info = left_item_sz;
2519 elog(
PANIC,
"failed to add leftkey to new root page"
2520 " while splitting block %u of index \"%s\"",
2531 elog(
PANIC,
"failed to add rightkey to new root page"
2532 " while splitting block %u of index \"%s\"",
2562 md.
root = rootblknum;
2576 (
char *) rootpage + ((
PageHeader) rootpage)->pd_upper,
2621 bool newfirstdataitem)
2625 if (newfirstdataitem)
2672 bool simpleonly,
bool checkingunique,
2673 bool uniquedup,
bool indexUnchanged)
2687 Assert(!simpleonly || (!checkingunique && !uniquedup && !indexUnchanged));
2698 for (offnum = minoff;
2705 deletable[ndeletable++] = offnum;
2711 insertstate->
itup, minoff, maxoff);
2735 if (simpleonly || (checkingunique && !uniquedup))
2761 if ((indexUnchanged || uniquedup) &&
2768 insertstate->
itemsz, (indexUnchanged || uniquedup));
2810 deadblocks =
_bt_deadblocks(page, deletable, ndeletable, newitem,
2814 delstate.
irel = rel;
2822 for (offnum = minoff;
2836 match = bsearch(&tidblock, deadblocks, ndeadblocks,
2862 for (
int p = 0; p < nitem; p++)
2867 match = bsearch(&tidblock, deadblocks, ndeadblocks,
2880 odeltid->
tid = *tid;
2938 spacentids = ndeletable + 1;
2950 for (
int i = 0;
i < ndeletable;
i++)
2959 if (ntids + 1 > spacentids)
2972 if (ntids + nposting > spacentids)
2974 spacentids =
Max(spacentids * 2, ntids + nposting);
2979 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)
void PageRestoreTempPage(Page tempPage, Page oldPage)
Page PageGetTempPage(Page page)
Size PageGetFreeSpace(Page page)
static Item PageGetItem(Page page, ItemId itemId)
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
static void PageSetLSN(Page page, XLogRecPtr lsn)
static XLogRecPtr PageGetLSN(Page page)
static OffsetNumber PageGetMaxOffsetNumber(Page page)
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
elog(ERROR, "%s: %s", p2, msg)
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, Datum *values, bool *isnull)
void index_deform_tuple(IndexTuple tup, TupleDesc tupleDescriptor, Datum *values, bool *isnull)
IndexTuple CopyIndexTuple(IndexTuple source)
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
#define IndexTupleSize(itup)
struct IndexTupleData IndexTupleData
#define MaxIndexTuplesPerPage
Assert(fmt[strlen(fmt) - 1] !='\n')
void XactLockTableWait(TransactionId xid, Relation rel, ItemPointer ctid, XLTW_Oper oper)
void SpeculativeInsertionWait(TransactionId xid, uint32 token)
void pfree(void *pointer)
void * repalloc(void *pointer, Size size)
#define START_CRIT_SECTION()
#define END_CRIT_SECTION()
IndexTuple _bt_swap_posting(IndexTuple newitem, IndexTuple oposting, int postingoff)
bool _bt_bottomupdel_pass(Relation rel, Buffer buf, Relation heapRel, Size newitemsz)
void _bt_dedup_pass(Relation rel, Buffer buf, Relation heapRel, IndexTuple newitem, Size newitemsz, bool bottomupdedup)
static Buffer _bt_newroot(Relation rel, Buffer lbuf, Buffer rbuf)
#define BTREE_FASTPATH_MIN_LEVEL
static OffsetNumber _bt_findinsertloc(Relation rel, BTInsertState insertstate, bool checkingunique, bool indexUnchanged, BTStack stack, Relation heapRel)
static void _bt_simpledel_pass(Relation rel, Buffer buffer, Relation heapRel, OffsetNumber *deletable, int ndeletable, IndexTuple newitem, OffsetNumber minoff, OffsetNumber maxoff)
static void _bt_insert_parent(Relation rel, Buffer buf, Buffer rbuf, BTStack stack, bool isroot, bool isonly)
static BTStack _bt_search_insert(Relation rel, BTInsertState insertstate)
bool _bt_doinsert(Relation rel, IndexTuple itup, IndexUniqueCheck checkUnique, bool indexUnchanged, Relation heapRel)
void _bt_finish_split(Relation rel, Buffer lbuf, BTStack stack)
static bool _bt_pgaddtup(Page page, Size itemsize, IndexTuple itup, OffsetNumber itup_off, bool newfirstdataitem)
static void _bt_stepright(Relation rel, BTInsertState insertstate, BTStack stack)
static void _bt_insertonpg(Relation rel, BTScanInsert itup_key, Buffer buf, Buffer cbuf, BTStack stack, IndexTuple itup, Size itemsz, OffsetNumber newitemoff, int postingoff, bool split_only_page)
static void _bt_delete_or_dedup_one_page(Relation rel, Relation heapRel, BTInsertState insertstate, bool simpleonly, bool checkingunique, bool uniquedup, bool indexUnchanged)
static int _bt_blk_cmp(const void *arg1, const void *arg2)
Buffer _bt_getstackbuf(Relation rel, BTStack stack, BlockNumber child)
static Buffer _bt_split(Relation rel, BTScanInsert itup_key, Buffer buf, Buffer cbuf, OffsetNumber newitemoff, Size newitemsz, IndexTuple newitem, IndexTuple orignewitem, IndexTuple nposting, uint16 postingoff)
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)
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)
OffsetNumber _bt_binsrch_insert(Relation rel, BTInsertState insertstate)
int32 _bt_compare(Relation rel, BTScanInsert key, Page page, OffsetNumber offnum)
Buffer _bt_get_endpoint(Relation rel, uint32 level, bool rightmost, Snapshot snapshot)
BTStack _bt_search(Relation rel, BTScanInsert key, Buffer *bufP, int access, Snapshot snapshot)
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)
void XLogRegisterData(char *data, uint32 len)
XLogRecPtr XLogInsert(RmgrId rmid, uint8 info)
void XLogRegisterBufData(uint8 block_id, char *data, uint32 len)
void XLogRegisterBuffer(uint8 block_id, Buffer buffer, uint8 flags)
void XLogBeginInsert(void)