Loading...
Searching...
No Matches
#include "postgres.h"#include "access/nbtree.h"#include "access/nbtxlog.h"#include "access/tableam.h"#include "access/transam.h"#include "access/xloginsert.h"#include "common/int.h"#include "common/pg_prng.h"#include "lib/qunique.h"#include "miscadmin.h"#include "storage/lmgr.h"#include "storage/predicate.h"#include "utils/injection_point.h"
Include dependency graph for nbtinsert.c:
Go to the source code of this file.
Macros | |
| #define | BTREE_FASTPATH_MIN_LEVEL 2 |
Macro Definition Documentation
◆ BTREE_FASTPATH_MIN_LEVEL
| #define BTREE_FASTPATH_MIN_LEVEL 2 |
Definition at line 32 of file nbtinsert.c.
Function Documentation
◆ _bt_blk_cmp()
Definition at line 3024 of file nbtinsert.c.
3025{
3028
3030}
References fb(), and pg_cmp_u32().
Referenced by _bt_deadblocks(), and _bt_simpledel_pass().
◆ _bt_check_unique()
|
static |
Definition at line 410 of file nbtinsert.c.
413{
419 OffsetNumber offset;
420 OffsetNumber maxoff;
421 Page page;
422 BTPageOpaque opaque;
424 bool found = false;
428
429 /* Assume unique until we find a duplicate */
431
433
435 opaque = BTPageGetOpaque(page);
436 maxoff = PageGetMaxOffsetNumber(page);
437
438 /*
439 * Find the first tuple with the same key.
440 *
441 * This also saves the binary search bounds in insertstate. We use them
442 * in the fastpath below, but also in the _bt_findinsertloc() call later.
443 */
446
447 /*
448 * Scan over all equal tuples, looking for live conflicts.
449 */
453 for (;;)
454 {
455 /*
456 * Each iteration of the loop processes one heap TID, not one index
457 * tuple. Current offset number for page isn't usually advanced on
458 * iterations that process heap TIDs from posting list tuples.
459 *
460 * "inposting" state is set when _inside_ a posting list --- not when
461 * we're at the start (or end) of a posting list. We advance curposti
462 * at the end of the iteration when inside a posting list tuple. In
463 * general, every loop iteration either advances the page offset or
464 * advances curposti --- an iteration that handles the rightmost/max
465 * heap TID in a posting list finally advances the page offset (and
466 * unsets "inposting").
467 *
468 * Make sure the offset points to an actual index tuple before trying
469 * to examine it...
470 */
471 if (offset <= maxoff)
472 {
473 /*
474 * Fastpath: In most cases, we can use cached search bounds to
475 * limit our consideration to items that are definitely
476 * duplicates. This fastpath doesn't apply when the original page
477 * is empty, or when initial offset is past the end of the
478 * original page, which may indicate that we need to examine a
479 * second or subsequent page.
480 *
481 * Note that this optimization allows us to avoid calling
482 * _bt_compare() directly when there are no duplicates, as long as
483 * the offset where the key will go is not at the end of the page.
484 */
486 {
491 break;
492 }
493
494 /*
495 * We can skip items that are already marked killed.
496 *
497 * In the presence of heavy update activity an index may contain
498 * many killed items with the same key; running _bt_compare() on
499 * each killed item gets expensive. Just advance over killed
500 * items as quickly as we can. We only apply _bt_compare() when
501 * we get to a non-killed item. We could reuse the bounds to
502 * avoid _bt_compare() calls for known equal tuples, but it
503 * doesn't seem worth it.
504 */
508 {
511
513 {
514 /* Plain tuple, or first TID in posting list tuple */
516 break; /* we're past all the equal tuples */
517
518 /* Advanced curitup */
521 }
522
523 /* okay, we gotta fetch the heap tuple using htid ... */
525 {
526 /* ... htid is from simple non-pivot tuple */
529 }
531 {
532 /* ... htid is first TID in new posting list */
535 curposti = 0;
537 }
538 else
539 {
540 /* ... htid is second or subsequent TID in posting list */
543 }
544
545 /*
546 * If we are doing a recheck, we expect to find the tuple we
547 * are rechecking. It's not a duplicate, but we have to keep
548 * scanning.
549 */
552 {
553 found = true;
554 }
555
556 /*
557 * Check if there's any table tuples for this index entry
558 * satisfying SnapshotDirty. This is necessary because for AMs
559 * with optimizations like heap's HOT, we have just a single
560 * index entry for the entire chain.
561 */
563 &SnapshotDirty,
564 &all_dead))
565 {
567
568 /*
569 * It is a duplicate. If we are only doing a partial
570 * check, then don't bother checking if the tuple is being
571 * updated in another transaction. Just return the fact
572 * that it is a potential conflict and leave the full
573 * check till later. Don't invalidate binary search
574 * bounds.
575 */
577 {
582 }
583
584 /*
585 * If this tuple is being updated by other transaction
586 * then we have to wait for its commit/abort.
587 */
590
592 {
595 /* Tell _bt_doinsert to wait... */
596 *speculativeToken = SnapshotDirty.speculativeToken;
597 /* Caller releases lock on buf immediately */
600 }
601
602 /*
603 * Otherwise we have a definite conflict. But before
604 * complaining, look to see if the tuple we want to insert
605 * is itself now committed dead --- if so, don't complain.
606 * This is a waste of time in normal scenarios but we must
607 * do it to support CREATE INDEX CONCURRENTLY.
608 *
609 * We must follow HOT-chains here because during
610 * concurrent index build, we insert the root TID though
611 * the actual tuple may be somewhere in the HOT-chain.
612 * While following the chain we might not stop at the
613 * exact tuple which triggered the insert, but that's OK
614 * because if we find a live tuple anywhere in this chain,
615 * we have a unique key conflict. The other live tuple is
616 * not part of this chain because it had a different index
617 * entry.
618 */
622 {
623 /* Normal case --- it's still live */
624 }
625 else
626 {
627 /*
628 * It's been deleted, so no error, and no need to
629 * continue searching
630 */
631 break;
632 }
633
634 /*
635 * Check for a conflict-in as we would if we were going to
636 * write to this page. We aren't actually going to write,
637 * but we want a chance to report SSI conflicts that would
638 * otherwise be masked by this unique constraint
639 * violation.
640 */
642
643 /*
644 * This is a definite conflict. Break the tuple down into
645 * datums and report the error. But first, make sure we
646 * release the buffer locks we're holding ---
647 * BuildIndexValueDescription could make catalog accesses,
648 * which in the worst case might touch this same index and
649 * cause deadlocks.
650 */
656
657 {
661
663 values, isnull);
664
666 isnull);
667
671 RelationGetRelationName(rel)),
673 key_desc) : 0,
674 errtableconstraint(heapRel,
675 RelationGetRelationName(rel))));
676 }
677 }
679 (prevalldead &&
681 {
682 /*
683 * The conflicting tuple (or all HOT chains pointed to by
684 * all posting list TIDs) is dead to everyone, so mark the
685 * index entry killed.
686 */
689
690 /*
691 * Mark buffer with a dirty hint, since state is not
692 * crucial. Be sure to mark the proper buffer dirty.
693 */
696 else
698 }
699
700 /*
701 * Remember if posting list tuple has even a single HOT chain
702 * whose members are not all dead
703 */
706 }
707 }
708
710 {
711 /* Advance to next TID in same posting list */
712 curposti++;
713 continue;
714 }
715 else if (offset < maxoff)
716 {
717 /* Advance to next tuple */
718 curposti = 0;
720 offset = OffsetNumberNext(offset);
721 }
722 else
723 {
725
726 /* If scankey == hikey we gotta check the next page too */
728 break;
732 break;
733 /* Advance to next non-dead page --- there must be one */
734 for (;;)
735 {
737
740 opaque = BTPageGetOpaque(page);
742 break;
745 RelationGetRelationName(rel));
746 }
747 /* Will also advance to next tuple */
748 curposti = 0;
750 maxoff = PageGetMaxOffsetNumber(page);
751 offset = P_FIRSTDATAKEY(opaque);
752 /* Don't invalidate binary search bounds */
753 }
754 }
755
756 /*
757 * If we are doing a recheck then we should have found the tuple we are
758 * checking. Otherwise there's something very wrong --- probably, the
759 * index is on a non-immutable expression.
760 */
765 RelationGetRelationName(rel)),
767 errtableconstraint(heapRel,
768 RelationGetRelationName(rel))));
769
772
774}
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition bufpage.h:243
static void * PageGetItem(PageData *page, const ItemIdData *itemId)
Definition bufpage.h:353
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
Definition bufpage.h:371
char * BuildIndexValueDescription(Relation indexRelation, const Datum *values, const bool *isnull)
Definition genam.c:178
void index_deform_tuple(IndexTuple tup, TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition indextuple.c:456
int32 ItemPointerCompare(const ItemPointerData *arg1, const ItemPointerData *arg2)
Definition itemptr.c:51
Buffer _bt_relandgetbuf(Relation rel, Buffer obuf, BlockNumber blkno, int access)
Definition nbtpage.c:1004
static ItemPointer BTreeTupleGetPostingN(IndexTuple posting, int n)
Definition nbtree.h:545
OffsetNumber _bt_binsrch_insert(Relation rel, BTInsertState insertstate)
Definition nbtsearch.c:470
int32 _bt_compare(Relation rel, BTScanInsert key, Page page, OffsetNumber offnum)
Definition nbtsearch.c:684
void CheckForSerializableConflictIn(Relation relation, const ItemPointerData *tid, BlockNumber blkno)
Definition predicate.c:4334
int errtableconstraint(Relation rel, const char *conname)
Definition relcache.c:6098
Definition nbtree.h:64
Definition nbtree.h:796
Definition itup.h:36
Definition itemid.h:26
Definition itemptr.h:37
Definition snapshot.h:139
bool table_index_fetch_tuple_check(Relation rel, ItemPointer tid, Snapshot snapshot, bool *all_dead)
Definition tableam.c:240
References _bt_binsrch_insert(), _bt_compare(), _bt_relandgetbuf(), _bt_relbuf(), BTScanInsertData::anynullkeys, Assert, BT_READ, BTP_HAS_GARBAGE, BTPageGetOpaque, BTPageOpaqueData::btpo_flags, BTPageOpaqueData::btpo_next, BTreeTupleGetNPosting(), BTreeTupleGetPostingN(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), BufferGetBlockNumber(), BufferGetPage(), BuildIndexValueDescription(), CheckForSerializableConflictIn(), elog, ereport, errcode(), errdetail(), errhint(), errmsg(), ERROR, errtableconstraint(), fb(), index_deform_tuple(), INDEX_MAX_KEYS, InitDirtySnapshot, InvalidBuffer, InvalidTransactionId, ItemIdIsDead, ItemIdMarkDead, ItemPointerCompare(), MarkBufferDirtyHint(), OffsetNumberNext, P_FIRSTDATAKEY, P_HIKEY, P_IGNORE, P_RIGHTMOST, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), RelationGetDescr, RelationGetRelationName, BTScanInsertData::scantid, SnapshotSelf, IndexTupleData::t_tid, table_index_fetch_tuple_check(), TransactionIdIsValid, UNIQUE_CHECK_EXISTING, UNIQUE_CHECK_PARTIAL, and values.
Referenced by _bt_doinsert().
◆ _bt_deadblocks()
|
static |
Definition at line 2951 of file nbtinsert.c.
2953{
2955 ntids;
2957
2958 /*
2959 * Accumulate each TID's block in array whose initial size has space for
2960 * one table block per LP_DEAD-set tuple (plus space for the newitem table
2961 * block). Array will only need to grow when there are LP_DEAD-marked
2962 * posting list tuples (which is not that common).
2963 */
2965 ntids = 0;
2967
2968 /*
2969 * First add the table block for the incoming newitem. This is the one
2970 * case where simple deletion can visit a table block that doesn't have
2971 * any known deletable items.
2972 */
2975
2977 {
2980
2982
2984 {
2986 {
2987 spacentids *= 2;
2990 }
2991
2993 }
2994 else
2995 {
2997
2999 {
3003 }
3004
3006 {
3008
3010 }
3011 }
3012 }
3013
3016
3018}
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition itemptr.h:103
static size_t qunique(void *array, size_t elements, size_t width, int(*compare)(const void *, const void *))
Definition qunique.h:21
References _bt_blk_cmp(), Assert, BTreeTupleGetNPosting(), BTreeTupleGetPostingN(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), fb(), i, ItemIdIsDead, ItemPointerGetBlockNumber(), j, Max, PageGetItem(), PageGetItemId(), palloc_array, qsort, qunique(), repalloc(), and IndexTupleData::t_tid.
Referenced by _bt_simpledel_pass().
◆ _bt_delete_or_dedup_one_page()
|
static |
Definition at line 2696 of file nbtinsert.c.
2700{
2703 OffsetNumber offnum,
2704 minoff,
2705 maxoff;
2710
2714
2715 /*
2716 * Scan over all items to see which ones need to be deleted according to
2717 * LP_DEAD flags. We'll usually manage to delete a few extra items that
2718 * are not marked LP_DEAD in passing. Often the extra items that actually
2719 * end up getting deleted are items that would have had their LP_DEAD bit
2720 * set before long anyway (if we opted not to include them as extras).
2721 */
2722 minoff = P_FIRSTDATAKEY(opaque);
2723 maxoff = PageGetMaxOffsetNumber(page);
2724 for (offnum = minoff;
2725 offnum <= maxoff;
2726 offnum = OffsetNumberNext(offnum))
2727 {
2729
2732 }
2733
2735 {
2737 insertstate->itup, minoff, maxoff);
2739
2740 /* Return when a page split has already been avoided */
2742 return;
2743
2744 /* Might as well assume duplicates (if checkingunique) */
2746 }
2747
2748 /*
2749 * We're done with simple deletion. Return early with callers that only
2750 * call here so that simple deletion can be considered. This includes
2751 * callers that explicitly ask for this and checkingunique callers that
2752 * probably don't have any version churn duplicates on the page.
2753 *
2754 * Note: The page's BTP_HAS_GARBAGE hint flag may still be set when we
2755 * return at this point (or when we go on the try either or both of our
2756 * other strategies and they also fail). We do not bother expending a
2757 * separate write to clear it, however. Caller will definitely clear it
2758 * when it goes on to split the page (note also that the deduplication
2759 * process will clear the flag in passing, just to keep things tidy).
2760 */
2762 {
2764 return;
2765 }
2766
2767 /* Assume bounds about to be invalidated (this is almost certain now) */
2769
2770 /*
2771 * Perform bottom-up index deletion pass when executor hint indicated that
2772 * incoming item is logically unchanged, or for a unique index that is
2773 * known to have physical duplicates for some other reason. (There is a
2774 * large overlap between these two cases for a unique index. It's worth
2775 * having both triggering conditions in order to apply the optimization in
2776 * the event of successive related INSERT and DELETE statements.)
2777 *
2778 * We'll go on to do a deduplication pass when a bottom-up pass fails to
2779 * delete an acceptable amount of free space (a significant fraction of
2780 * the page, or space for the new item, whichever is greater).
2781 *
2782 * Note: Bottom-up index deletion uses the same equality/equivalence
2783 * routines as deduplication internally. However, it does not merge
2784 * together index tuples, so the same correctness considerations do not
2785 * apply. We deliberately omit an index-is-allequalimage test here.
2786 */
2789 return;
2790
2791 /* Perform deduplication pass (when enabled and index-is-allequalimage) */
2795}
void _bt_dedup_pass(Relation rel, Buffer buf, IndexTuple newitem, Size newitemsz, bool bottomupdedup)
Definition nbtdedup.c:59
bool _bt_bottomupdel_pass(Relation rel, Buffer buf, Relation heapRel, Size newitemsz)
Definition nbtdedup.c:307
static void _bt_simpledel_pass(Relation rel, Buffer buffer, Relation heapRel, OffsetNumber *deletable, int ndeletable, IndexTuple newitem, OffsetNumber minoff, OffsetNumber maxoff)
Definition nbtinsert.c:2825
References _bt_bottomupdel_pass(), _bt_dedup_pass(), _bt_simpledel_pass(), BTScanInsertData::allequalimage, Assert, BTGetDeduplicateItems, BTPageGetOpaque, BufferGetPage(), fb(), BTScanInsertData::heapkeyspace, ItemIdIsDead, MaxIndexTuplesPerPage, OffsetNumberNext, P_FIRSTDATAKEY, P_ISLEAF, PageGetFreeSpace(), PageGetItemId(), and PageGetMaxOffsetNumber().
Referenced by _bt_findinsertloc().
◆ _bt_doinsert()
| bool _bt_doinsert | ( | Relation | rel, |
| IndexTuple | itup, | ||
| IndexUniqueCheck | checkUnique, | ||
| bool | indexUnchanged, | ||
| Relation | heapRel | ||
| ) |
Definition at line 104 of file nbtinsert.c.
107{
110 BTScanInsert itup_key;
111 BTStack stack;
113
114 /* we need an insertion scan key to do our search, so build one */
115 itup_key = _bt_mkscankey(rel, itup);
116
118 {
120 {
121 /* No (heapkeyspace) scantid until uniqueness established */
123 }
124 else
125 {
126 /*
127 * Scan key for new tuple contains NULL key values. Bypass
128 * checkingunique steps. They are unnecessary because core code
129 * considers NULL unequal to every value, including NULL.
130 *
131 * This optimization avoids O(N^2) behavior within the
132 * _bt_findinsertloc() heapkeyspace path when a unique index has a
133 * large number of "duplicates" with NULL key values.
134 */
136 /* Tuple is unique in the sense that core code cares about */
139 }
140 }
141
142 /*
143 * Fill in the BTInsertState working area, to track the current page and
144 * position within the page to insert on.
145 *
146 * Note that itemsz is passed down to lower level code that deals with
147 * inserting the item. It must be MAXALIGN()'d. This ensures that space
148 * accounting code consistently considers the alignment overhead that we
149 * expect PageAddItem() will add later. (Actually, index_form_tuple() is
150 * already conservative about alignment, but we don't rely on that from
151 * this distance. Besides, preserving the "true" tuple size in index
152 * tuple headers for the benefit of nbtsplitloc.c might happen someday.
153 * Note that heapam does not MAXALIGN() each heap tuple's lp_len field.)
154 */
155 insertstate.itup = itup;
157 insertstate.itup_key = itup_key;
160 insertstate.postingoff = 0;
161
162search:
163
164 /*
165 * Find and lock the leaf page that the tuple should be added to by
166 * searching from the root page. insertstate.buf will hold a buffer that
167 * is locked in exclusive mode afterwards.
168 */
170
171 /*
172 * checkingunique inserts are not allowed to go ahead when two tuples with
173 * equal key attribute values would be visible to new MVCC snapshots once
174 * the xact commits. Check for conflicts in the locked page/buffer (if
175 * needed) here.
176 *
177 * It might be necessary to check a page to the right in _bt_check_unique,
178 * though that should be very rare. In practice the first page the value
179 * could be on (with scantid omitted) is almost always also the only page
180 * that a matching tuple might be found on. This is due to the behavior
181 * of _bt_findsplitloc with duplicate tuples -- a group of duplicates can
182 * only be allowed to cross a page boundary when there is no candidate
183 * leaf page split point that avoids it. Also, _bt_check_unique can use
184 * the leaf page high key to determine that there will be no duplicates on
185 * the right sibling without actually visiting it (it uses the high key in
186 * cases where the new item happens to belong at the far right of the leaf
187 * page).
188 *
189 * NOTE: obviously, _bt_check_unique can only detect keys that are already
190 * in the index; so it cannot defend against concurrent insertions of the
191 * same key. We protect against that by means of holding a write lock on
192 * the first page the value could be on, with omitted/-inf value for the
193 * implicit heap TID tiebreaker attribute. Any other would-be inserter of
194 * the same key must acquire a write lock on the same page, so only one
195 * would-be inserter can be making the check at one time. Furthermore,
196 * once we are past the check we hold write locks continuously until we
197 * have performed our insertion, so no later inserter can fail to see our
198 * insertion. (This requires some care in _bt_findinsertloc.)
199 *
200 * If we must wait for another xact, we release the lock while waiting,
201 * and then must perform a new search.
202 *
203 * For a partial uniqueness check, we don't wait for the other xact. Just
204 * let the tuple in and return false for possibly non-unique, or true for
205 * definitely unique.
206 */
208 {
210 uint32 speculativeToken;
211
213 &is_unique, &speculativeToken);
214
216 {
217 /* Have to wait for the other guy ... */
220
221 /*
222 * If it's a speculative insertion, wait for it to finish (ie. to
223 * go ahead with the insertion, or kill the tuple). Otherwise
224 * wait for the transaction to finish as usual.
225 */
226 if (speculativeToken)
228 else
230
231 /* start over... */
232 if (stack)
233 _bt_freestack(stack);
234 goto search;
235 }
236
237 /* Uniqueness is established -- restore heap tid as scantid */
240 }
241
243 {
244 OffsetNumber newitemoff;
245
246 /*
247 * The only conflict predicate locking cares about for indexes is when
248 * an index tuple insert conflicts with an existing lock. We don't
249 * know the actual page we're going to insert on for sure just yet in
250 * checkingunique and !heapkeyspace cases, but it's okay to use the
251 * first page the value could be on (with scantid omitted) instead.
252 */
254
255 /*
256 * Do the insertion. Note that insertstate contains cached binary
257 * search bounds established within _bt_check_unique when insertion is
258 * checkingunique.
259 */
261 indexUnchanged, stack, heapRel);
263 stack, itup, insertstate.itemsz, newitemoff,
265 }
266 else
267 {
268 /* just release the buffer */
270 }
271
272 /* be tidy */
273 if (stack)
274 _bt_freestack(stack);
275 pfree(itup_key);
276
278}
void SpeculativeInsertionWait(TransactionId xid, uint32 token)
Definition lmgr.c:828
void XactLockTableWait(TransactionId xid, Relation rel, const ItemPointerData *ctid, XLTW_Oper oper)
Definition lmgr.c:663
static BTStack _bt_search_insert(Relation rel, Relation heaprel, BTInsertState insertstate)
Definition nbtinsert.c:319
static OffsetNumber _bt_findinsertloc(Relation rel, BTInsertState insertstate, bool checkingunique, bool indexUnchanged, BTStack stack, Relation heapRel)
Definition nbtinsert.c:817
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)
Definition nbtinsert.c:1107
static TransactionId _bt_check_unique(Relation rel, BTInsertState insertstate, Relation heapRel, IndexUniqueCheck checkUnique, bool *is_unique, uint32 *speculativeToken)
Definition nbtinsert.c:410
Definition nbtree.h:821
Definition nbtree.h:744
References _bt_check_unique(), _bt_findinsertloc(), _bt_freestack(), _bt_insertonpg(), _bt_mkscankey(), _bt_relbuf(), _bt_search_insert(), BTScanInsertData::anynullkeys, Assert, BufferGetBlockNumber(), CheckForSerializableConflictIn(), fb(), BTScanInsertData::heapkeyspace, IndexTupleSize(), InvalidBuffer, MAXALIGN, pfree(), BTScanInsertData::scantid, SpeculativeInsertionWait(), IndexTupleData::t_tid, TransactionIdIsValid, UNIQUE_CHECK_EXISTING, UNIQUE_CHECK_NO, unlikely, XactLockTableWait(), and XLTW_InsertIndex.
Referenced by btinsert().
◆ _bt_findinsertloc()
|
static |
Definition at line 817 of file nbtinsert.c.
823{
826 BTPageOpaque opaque;
827 OffsetNumber newitemoff;
828
829 opaque = BTPageGetOpaque(page);
830
831 /* Check 1/3 of a page restriction */
834 insertstate->itup);
835
841
843 {
844 /* Keep track of whether checkingunique duplicate seen */
846
847 /*
848 * If we're inserting into a unique index, we may have to walk right
849 * through leaf pages to find the one leaf page that we must insert on
850 * to.
851 *
852 * This is needed for checkingunique callers because a scantid was not
853 * used when we called _bt_search(). scantid can only be set after
854 * _bt_check_unique() has checked for duplicates. The buffer
855 * initially stored in insertstate->buf has the page where the first
856 * duplicate key might be found, which isn't always the page that new
857 * tuple belongs on. The heap TID attribute for new tuple (scantid)
858 * could force us to insert on a sibling page, though that should be
859 * very rare in practice.
860 */
862 {
864 {
865 /* Encountered a duplicate in _bt_check_unique() */
868 }
869
870 for (;;)
871 {
872 /*
873 * Does the new tuple belong on this page?
874 *
875 * The earlier _bt_check_unique() call may well have
876 * established a strict upper bound on the offset for the new
877 * item. If it's not the last item of the page (i.e. if there
878 * is at least one tuple on the page that goes after the tuple
879 * we're inserting) then we know that the tuple belongs on
880 * this page. We can skip the high key check.
881 */
885 break;
886
887 /* Test '<=', not '!=', since scantid is set now */
890 break;
891
893 /* Update local state after stepping right */
895 opaque = BTPageGetOpaque(page);
896 /* Assume duplicates (if checkingunique) */
898 }
899 }
900
901 /*
902 * If the target page cannot fit newitem, try to avoid splitting the
903 * page on insert by performing deletion or deduplication now
904 */
908 indexUnchanged);
909 }
910 else
911 {
912 /*----------
913 * This is a !heapkeyspace (version 2 or 3) index. The current page
914 * is the first page that we could insert the new tuple to, but there
915 * may be other pages to the right that we could opt to use instead.
916 *
917 * If the new key is equal to one or more existing keys, we can
918 * legitimately place it anywhere in the series of equal keys. In
919 * fact, if the new key is equal to the page's "high key" we can place
920 * it on the next page. If it is equal to the high key, and there's
921 * not room to insert the new tuple on the current page without
922 * splitting, then we move right hoping to find more free space and
923 * avoid a split.
924 *
925 * Keep scanning right until we
926 * (a) find a page with enough free space,
927 * (b) reach the last page where the tuple can legally go, or
928 * (c) get tired of searching.
929 * (c) is not flippant; it is important because if there are many
930 * pages' worth of equal keys, it's better to split one of the early
931 * pages than to scan all the way to the end of the run of equal keys
932 * on every insert. We implement "get tired" as a random choice,
933 * since stopping after scanning a fixed number of pages wouldn't work
934 * well (we'd never reach the right-hand side of previously split
935 * pages). The probability of moving right is set at 0.99, which may
936 * seem too high to change the behavior much, but it does an excellent
937 * job of preventing O(N^2) behavior with many equal keys.
938 *----------
939 */
941 {
942 /*
943 * Before considering moving right, see if we can obtain enough
944 * space by erasing LP_DEAD items
945 */
947 {
948 /* Perform simple deletion */
950 false, false, false);
951
953 break; /* OK, now we have enough space */
954 }
955
956 /*
957 * Nope, so check conditions (b) and (c) enumerated above
958 *
959 * The earlier _bt_check_unique() call may well have established a
960 * strict upper bound on the offset for the new item. If it's not
961 * the last item of the page (i.e. if there is at least one tuple
962 * on the page that's greater than the tuple we're inserting to)
963 * then we know that the tuple belongs on this page. We can skip
964 * the high key check.
965 */
969 break;
970
974 break;
975
977 /* Update local state after stepping right */
979 opaque = BTPageGetOpaque(page);
980 }
981 }
982
983 /*
984 * We should now be on the correct page. Find the offset within the page
985 * for the new tuple. (Possibly reusing earlier search bounds.)
986 */
989
991
993 {
994 /*
995 * There is an overlapping posting list tuple with its LP_DEAD bit
996 * set. We don't want to unnecessarily unset its LP_DEAD bit while
997 * performing a posting list split, so perform simple index tuple
998 * deletion early.
999 */
1001 false, false, false);
1002
1003 /*
1004 * Do new binary search. New insert location cannot overlap with any
1005 * posting list now.
1006 */
1008 insertstate->postingoff = 0;
1011 }
1012
1013 return newitemoff;
1014}
static void _bt_delete_or_dedup_one_page(Relation rel, Relation heapRel, BTInsertState insertstate, bool simpleonly, bool checkingunique, bool uniquedup, bool indexUnchanged)
Definition nbtinsert.c:2696
static void _bt_stepright(Relation rel, Relation heaprel, BTInsertState insertstate, BTStack stack)
Definition nbtinsert.c:1029
void _bt_check_third_page(Relation rel, Relation heap, bool needheaptidspace, Page page, IndexTuple newtup)
Definition nbtutils.c:1124
References _bt_binsrch_insert(), _bt_check_third_page(), _bt_compare(), _bt_delete_or_dedup_one_page(), _bt_stepright(), BTScanInsertData::allequalimage, Assert, BTMaxItemSize, BTPageGetOpaque, BufferGetPage(), fb(), BTScanInsertData::heapkeyspace, P_HAS_GARBAGE, P_HIKEY, P_INCOMPLETE_SPLIT, P_ISLEAF, P_RIGHTMOST, PageGetFreeSpace(), PageGetMaxOffsetNumber(), pg_global_prng_state, pg_prng_uint32(), PG_UINT32_MAX, BTScanInsertData::scantid, and unlikely.
Referenced by _bt_doinsert().
◆ _bt_finish_split()
Definition at line 2256 of file nbtinsert.c.
2257{
2265
2268
2269 /* Lock right sibling, the one missing the downlink */
2273
2274 /* Could this be a root split? */
2275 if (!stack)
2276 {
2280
2281 /* acquire lock on the metapage */
2285
2287
2289 }
2290 else
2292
2293 /* Was this the only page on the level before split? */
2295
2299
2301}
static void _bt_insert_parent(Relation rel, Relation heaprel, Buffer buf, Buffer rbuf, BTStack stack, bool isroot, bool isonly)
Definition nbtinsert.c:2114
Definition nbtree.h:105
References _bt_getbuf(), _bt_insert_parent(), _bt_relbuf(), Assert, BT_WRITE, BTPageGetMeta, BTPageGetOpaque, BTREE_METAPAGE, BufferGetBlockNumber(), BufferGetPage(), DEBUG1, elog, fb(), INJECTION_POINT, P_INCOMPLETE_SPLIT, P_LEFTMOST, and P_RIGHTMOST.
Referenced by _bt_getstackbuf(), _bt_moveright(), and _bt_stepright().
◆ _bt_getstackbuf()
| Buffer _bt_getstackbuf | ( | Relation | rel, |
| Relation | heaprel, | ||
| BTStack | stack, | ||
| BlockNumber | child | ||
| ) |
Definition at line 2335 of file nbtinsert.c.
2336{
2337 BlockNumber blkno;
2339
2340 blkno = stack->bts_blkno;
2342
2343 for (;;)
2344 {
2346 Page page;
2347 BTPageOpaque opaque;
2348
2351 opaque = BTPageGetOpaque(page);
2352
2355 {
2357 continue;
2358 }
2359
2361 {
2362 OffsetNumber offnum,
2363 minoff,
2364 maxoff;
2365 ItemId itemid;
2366 IndexTuple item;
2367
2368 minoff = P_FIRSTDATAKEY(opaque);
2369 maxoff = PageGetMaxOffsetNumber(page);
2370
2371 /*
2372 * start = InvalidOffsetNumber means "search the whole page". We
2373 * need this test anyway due to possibility that page has a high
2374 * key now when it didn't before.
2375 */
2377 start = minoff;
2378
2379 /*
2380 * Need this check too, to guard against possibility that page
2381 * split since we visited it originally.
2382 */
2385
2386 /*
2387 * These loops will check every item on the page --- but in an
2388 * order that's attuned to the probability of where it actually
2389 * is. Scan to the right first, then to the left.
2390 */
2392 offnum <= maxoff;
2393 offnum = OffsetNumberNext(offnum))
2394 {
2395 itemid = PageGetItemId(page, offnum);
2397
2399 {
2400 /* Return accurate pointer to where link is now */
2401 stack->bts_blkno = blkno;
2402 stack->bts_offset = offnum;
2404 }
2405 }
2406
2408 offnum >= minoff;
2409 offnum = OffsetNumberPrev(offnum))
2410 {
2411 itemid = PageGetItemId(page, offnum);
2413
2415 {
2416 /* Return accurate pointer to where link is now */
2417 stack->bts_blkno = blkno;
2418 stack->bts_offset = offnum;
2420 }
2421 }
2422 }
2423
2424 /*
2425 * The item we're looking for moved right at least one page.
2426 *
2427 * Lehman and Yao couple/chain locks when moving right here, which we
2428 * can avoid. See nbtree/README.
2429 */
2431 {
2434 }
2435 blkno = opaque->btpo_next;
2438 }
2439}
void _bt_finish_split(Relation rel, Relation heaprel, Buffer lbuf, BTStack stack)
Definition nbtinsert.c:2256
static BlockNumber BTreeTupleGetDownLink(IndexTuple pivot)
Definition nbtree.h:557
References _bt_finish_split(), _bt_getbuf(), _bt_relbuf(), Assert, BT_WRITE, BTPageGetOpaque, BTPageOpaqueData::btpo_next, BTreeTupleGetDownLink(), BTStackData::bts_blkno, BTStackData::bts_offset, BTStackData::bts_parent, buf, BufferGetPage(), fb(), InvalidBuffer, InvalidOffsetNumber, OffsetNumberNext, OffsetNumberPrev, P_FIRSTDATAKEY, P_IGNORE, P_INCOMPLETE_SPLIT, P_RIGHTMOST, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), and start.
Referenced by _bt_insert_parent(), and _bt_lock_subtree_parent().
◆ _bt_insert_parent()
|
static |
Definition at line 2114 of file nbtinsert.c.
2121{
2123
2124 /*
2125 * Here we have to do something Lehman and Yao don't talk about: deal with
2126 * a root split and construction of a new root. If our stack is empty
2127 * then we have just split a node on what had been the root level when we
2128 * descended the tree. If it was still the root then we perform a
2129 * new-root construction. If it *wasn't* the root anymore, search to find
2130 * the next higher level that someone constructed meanwhile, and find the
2131 * right place to insert as for the normal case.
2132 *
2133 * If we have to search for the parent level, we do so by re-descending
2134 * from the root. This is not super-efficient, but it's rare enough not
2135 * to matter.
2136 */
2138 {
2140
2143 /* create a new root node one level up and update the metapage */
2145 /* release the split buffers */
2149 }
2150 else
2151 {
2159
2161 {
2162 BTPageOpaque opaque;
2163
2165 opaque = BTPageGetOpaque(page);
2166
2167 /*
2168 * We should never reach here when a leaf page split takes place
2169 * despite the insert of newitem being able to apply the fastpath
2170 * optimization. Make sure of that with an assertion.
2171 *
2172 * This is more of a performance issue than a correctness issue.
2173 * The fastpath won't have a descent stack. Using a phony stack
2174 * here works, but never rely on that. The fastpath should be
2175 * rejected within _bt_search_insert() when the rightmost leaf
2176 * page will split, since it's faster to go through _bt_search()
2177 * and get a stack in the usual way.
2178 */
2181
2182 /* Find the leftmost page at the next level up */
2184 /* Set up a phony stack entry pointing there */
2185 stack = &fakestack;
2190 }
2191
2192 /* get high key from left, a strict lower bound for new right page */
2195
2196 /* form an index tuple that points at the new right page */
2199
2200 /*
2201 * Re-find and write lock the parent of buf.
2202 *
2203 * It's possible that the location of buf's downlink has changed since
2204 * our initial _bt_search() descent. _bt_getstackbuf() will detect
2205 * and recover from this, updating the stack, which ensures that the
2206 * new downlink will be inserted at the correct offset. Even buf's
2207 * parent may have changed.
2208 */
2210
2211 /*
2212 * Unlock the right child. The left child will be unlocked in
2213 * _bt_insertonpg().
2214 *
2215 * Unlocking the right child must be delayed until here to ensure that
2216 * no concurrent VACUUM operation can become confused. Page deletion
2217 * cannot be allowed to fail to re-find a downlink for the rbuf page.
2218 * (Actually, this is just a vestige of how things used to work. The
2219 * page deletion code is expected to check for the INCOMPLETE_SPLIT
2220 * flag on the left child. It won't attempt deletion of the right
2221 * child until the split is complete. Despite all this, we opt to
2222 * conservatively delay unlocking the right child until here.)
2223 */
2225
2231
2232 /* Recursively insert into the parent */
2236
2237 /* be tidy */
2239 }
2240}
Buffer _bt_getstackbuf(Relation rel, Relation heaprel, BTStack stack, BlockNumber child)
Definition nbtinsert.c:2335
static Buffer _bt_newlevel(Relation rel, Relation heaprel, Buffer lbuf, Buffer rbuf)
Definition nbtinsert.c:2460
static void BTreeTupleSetDownLink(IndexTuple pivot, BlockNumber blkno)
Definition nbtree.h:563
Buffer _bt_get_endpoint(Relation rel, uint32 level, bool rightmost)
Definition nbtsearch.c:2092
References _bt_get_endpoint(), _bt_getstackbuf(), _bt_insertonpg(), _bt_newlevel(), _bt_relbuf(), Assert, BlockNumberIsValid(), BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTreeTupleSetDownLink(), BTStackData::bts_blkno, BTStackData::bts_offset, BTStackData::bts_parent, buf, BufferGetBlockNumber(), BufferGetPage(), CopyIndexTuple(), DEBUG2, elog, ereport, errcode(), errmsg_internal(), ERROR, fb(), IndexTupleSize(), InvalidBuffer, InvalidOffsetNumber, MAXALIGN, P_HIKEY, P_ISLEAF, PageGetItem(), PageGetItemId(), pfree(), RelationGetRelationName, and RelationGetTargetBlock.
Referenced by _bt_finish_split(), and _bt_insertonpg().
◆ _bt_insertonpg()
|
static |
Definition at line 1107 of file nbtinsert.c.
1118{
1119 Page page;
1120 BTPageOpaque opaque;
1122 isroot,
1123 isrightmost,
1124 isonly;
1128
1130 opaque = BTPageGetOpaque(page);
1135
1136 /* child buffer must be given iff inserting on an internal page */
1138 /* tuple must have appropriate number of attributes */
1140 BTreeTupleGetNAtts(itup, rel) ==
1141 IndexRelationGetNumberOfAttributes(rel));
1143 BTreeTupleGetNAtts(itup, rel) <=
1144 IndexRelationGetNumberOfKeyAttributes(rel));
1147 /* Caller must always finish incomplete split for us */
1149
1150 /*
1151 * Every internal page should have exactly one negative infinity item at
1152 * all times. Only _bt_split() and _bt_newlevel() should add items that
1153 * become negative infinity items through truncation, since they're the
1154 * only routines that allocate new internal pages.
1155 */
1157
1158 /*
1159 * Do we need to split an existing posting list item?
1160 */
1161 if (postingoff != 0)
1162 {
1164
1165 /*
1166 * The new tuple is a duplicate with a heap TID that falls inside the
1167 * range of an existing posting list tuple on a leaf page. Prepare to
1168 * split an existing posting list. Overwriting the posting list with
1169 * its post-split version is treated as an extra step in either the
1170 * insert or page split critical section.
1171 */
1174
1175 /*
1176 * postingoff value comes from earlier call to _bt_binsrch_posting().
1177 * Its binary search might think that a plain tuple must be a posting
1178 * list tuple that needs to be split. This can happen with corruption
1179 * involving an existing plain tuple that is a duplicate of the new
1180 * item, up to and including its table TID. Check for that here in
1181 * passing.
1182 *
1183 * Also verify that our caller has made sure that the existing posting
1184 * list tuple does not have its LP_DEAD bit set.
1185 */
1189 errmsg_internal("table tid from new index tuple (%u,%u) overlaps with invalid duplicate tuple at offset %u of block %u in index \"%s\"",
1193 RelationGetRelationName(rel))));
1194
1195 /* use a mutable copy of itup as our itup from here on */
1196 origitup = itup;
1199 /* itup now contains rightmost/max TID from oposting */
1200
1201 /* Alter offset so that newitem goes after posting list */
1202 newitemoff = OffsetNumberNext(newitemoff);
1203 }
1204
1205 /*
1206 * Do we need to split the page to fit the item on it?
1207 *
1208 * Note: PageGetFreeSpace() subtracts sizeof(ItemIdData) from its result,
1209 * so this comparison is correct even though we appear to be accounting
1210 * only for the item and not for its line pointer.
1211 */
1213 {
1215
1217
1218 /* split the buffer into left and right halves */
1221 PredicateLockPageSplit(rel,
1224
1225 /*----------
1226 * By here,
1227 *
1228 * + our target page has been split;
1229 * + the original tuple has been inserted;
1230 * + we have write locks on both the old (left half)
1231 * and new (right half) buffers, after the split; and
1232 * + we know the key we want to insert into the parent
1233 * (it's the "high key" on the left child page).
1234 *
1235 * We're ready to do the parent insertion. We need to hold onto the
1236 * locks for the child pages until we locate the parent, but we can
1237 * at least release the lock on the right child before doing the
1238 * actual insertion. The lock on the left child will be released
1239 * last of all by parent insertion, where it is the 'cbuf' of parent
1240 * page.
1241 *----------
1242 */
1243#ifdef USE_INJECTION_POINTS
1246 else
1248#endif
1249
1251 }
1252 else
1253 {
1258
1259 /*
1260 * If we are doing this insert because we split a page that was the
1261 * only one on its tree level, but was not the root, it may have been
1262 * the "fast root". We need to ensure that the fast root link points
1263 * at or above the current page. We can safely acquire a lock on the
1264 * metapage here --- see comments for _bt_newlevel().
1265 */
1267 {
1270
1274
1276 {
1277 /* no update wanted */
1280 }
1281 }
1282
1283 /* Do the update. No ereport(ERROR) until changes are logged */
1284 START_CRIT_SECTION();
1285
1286 if (postingoff != 0)
1288
1292
1294
1296 {
1297 /* upgrade meta-page if needed */
1303 }
1304
1305 /*
1306 * Clear INCOMPLETE_SPLIT flag on child if inserting the new item
1307 * finishes a split
1308 */
1310 {
1313
1317 }
1318
1319 /* XLOG stuff */
1321 {
1327
1328 xlrec.offnum = newitemoff;
1329
1330 XLogBeginInsert();
1332
1334 {
1335 /* Simple leaf insert */
1337 }
1338 else if (postingoff != 0)
1339 {
1340 /*
1341 * Leaf insert with posting list split. Must include
1342 * postingoff field before newitem/orignewitem.
1343 */
1346 }
1347 else
1348 {
1349 /* Internal page insert, which finishes a split on cbuf */
1352
1354 {
1355 /* Actually, it's an internal page insert + meta update */
1357
1366
1371 }
1372 }
1373
1375 if (postingoff == 0)
1376 {
1377 /* Just log itup from caller */
1379 }
1380 else
1381 {
1382 /*
1383 * Insert with posting list split (XLOG_BTREE_INSERT_POST
1384 * record) case.
1385 *
1386 * Log postingoff. Also log origitup, not itup. REDO routine
1387 * must reconstruct final itup (as well as nposting) using
1388 * _bt_swap_posting().
1389 */
1390 upostingoff = postingoff;
1391
1395 }
1396
1398
1403
1405 }
1406
1407 END_CRIT_SECTION();
1408
1409 /* Release subsidiary buffers */
1414
1415 /*
1416 * Cache the block number if this is the rightmost leaf page. Cache
1417 * may be used by a future inserter within _bt_search_insert().
1418 */
1422
1423 /* Release buffer for insertion target block */
1425
1426 /*
1427 * If we decided to cache the insertion target block before releasing
1428 * its buffer lock, then cache it now. Check the height of the tree
1429 * first, though. We don't go for the optimization with small
1430 * indexes. Defer final check to this point to ensure that we don't
1431 * call _bt_getrootheight while holding a buffer lock.
1432 */
1436 }
1437
1438 /* be tidy */
1439 if (postingoff != 0)
1440 {
1441 /* itup is actually a modified copy of caller's original */
1443 pfree(itup);
1444 }
1445}
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
Definition bufpage.h:471
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
Definition itemptr.h:124
IndexTuple _bt_swap_posting(IndexTuple newitem, IndexTuple oposting, int postingoff)
Definition nbtdedup.c:1020
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)
Definition nbtinsert.c:1475
void PredicateLockPageSplit(Relation relation, BlockNumber oldblkno, BlockNumber newblkno)
Definition predicate.c:3142
#define IndexRelationGetNumberOfAttributes(relation)
Definition rel.h:526
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition rel.h:533
Definition nbtxlog.h:77
Definition nbtxlog.h:47
void XLogRegisterBufData(uint8 block_id, const void *data, uint32 len)
Definition xloginsert.c:409
void XLogRegisterBuffer(uint8 block_id, Buffer buffer, uint8 flags)
Definition xloginsert.c:245
References _bt_getbuf(), _bt_getrootheight(), _bt_insert_parent(), _bt_relbuf(), _bt_split(), _bt_swap_posting(), _bt_upgrademetapage(), BTScanInsertData::allequalimage, Assert, BlockNumberIsValid(), BT_WRITE, BTPageGetMeta, BTPageGetOpaque, BTPageOpaqueData::btpo_level, BTREE_FASTPATH_MIN_LEVEL, BTREE_METAPAGE, BTREE_NOVAC_VERSION, BTreeTupleGetNAtts, BTreeTupleIsPosting(), buf, BufferGetBlockNumber(), BufferGetPage(), BufferIsValid(), CopyIndexTuple(), elog, END_CRIT_SECTION, ereport, errcode(), errmsg_internal(), ERROR, fb(), BTScanInsertData::heapkeyspace, IndexRelationGetNumberOfAttributes, IndexRelationGetNumberOfKeyAttributes, IndexTupleSize(), INJECTION_POINT, InvalidBlockNumber, InvalidBuffer, InvalidOffsetNumber, ItemIdIsDead, ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), MarkBufferDirty(), MAXALIGN, OffsetNumberNext, P_FIRSTDATAKEY, P_INCOMPLETE_SPLIT, P_ISLEAF, P_ISROOT, P_LEFTMOST, P_RIGHTMOST, PageAddItem, PageGetFreeSpace(), PageGetItem(), PageGetItemId(), PageSetLSN(), PANIC, pfree(), PredicateLockPageSplit(), REGBUF_STANDARD, REGBUF_WILL_INIT, RelationGetRelationName, RelationNeedsWAL, RelationSetTargetBlock, SizeOfBtreeInsert, START_CRIT_SECTION, IndexTupleData::t_tid, unlikely, XLOG_BTREE_INSERT_LEAF, XLOG_BTREE_INSERT_META, XLOG_BTREE_INSERT_POST, XLOG_BTREE_INSERT_UPPER, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().
Referenced by _bt_doinsert(), and _bt_insert_parent().
◆ _bt_newlevel()
Definition at line 2460 of file nbtinsert.c.
2461{
2464 rootpage;
2466 rbkno;
2470 ItemId itemid;
2471 IndexTuple item;
2479
2484
2485 /* get a new root page */
2489
2490 /* acquire lock on the metapage */
2494
2495 /*
2496 * Create downlink item for left page (old root). The key value used is
2497 * "minus infinity", a sentinel value that's reliably less than any real
2498 * key value that could appear in the left page.
2499 */
2505
2506 /*
2507 * Create downlink item for right page. The key for it is obtained from
2508 * the "high key" position in the left page.
2509 */
2515
2516 /* NO EREPORT(ERROR) from here till newroot op is logged */
2517 START_CRIT_SECTION();
2518
2519 /* upgrade metapage if needed */
2522
2523 /* set btree special data */
2527 rootopaque->btpo_level =
2529 rootopaque->btpo_cycleid = 0;
2530
2531 /* update metapage data */
2536
2537 /*
2538 * Insert the left page pointer into the new root page. The root page is
2539 * the rightmost page on its level so there is no "high key" in it; the
2540 * two items will go into positions P_HIKEY and P_FIRSTKEY.
2541 *
2542 * Note: we *must* insert the two items in item-number order, for the
2543 * benefit of _bt_restore_page().
2544 */
2546 if (PageAddItem(rootpage, left_item, left_item_sz, P_HIKEY, false, false) == InvalidOffsetNumber)
2548 " while splitting block %u of index \"%s\"",
2550
2551 /*
2552 * insert the right page pointer into the new root page.
2553 */
2556 IndexRelationGetNumberOfKeyAttributes(rel));
2557 if (PageAddItem(rootpage, right_item, right_item_sz, P_FIRSTKEY, false, false) == InvalidOffsetNumber)
2559 " while splitting block %u of index \"%s\"",
2561
2562 /* Clear the incomplete-split flag in the left child */
2566
2569
2570 /* XLOG stuff */
2572 {
2575 xl_btree_metadata md;
2576
2579
2580 XLogBeginInsert();
2582
2586
2595
2597
2598 /*
2599 * Direct access to page is not good but faster - we should implement
2600 * some new func in page API.
2601 */
2602 XLogRegisterBufData(0,
2606
2608
2612 }
2613
2614 END_CRIT_SECTION();
2615
2616 /* done with metapage */
2618
2621
2623}
static void BTreeTupleSetNAtts(IndexTuple itup, uint16 nkeyatts, bool heaptid)
Definition nbtree.h:596
Definition bufpage.h:159
Definition nbtxlog.h:342
References _bt_allocbuf(), _bt_getbuf(), _bt_relbuf(), _bt_upgrademetapage(), xl_btree_metadata::allequalimage, Assert, BT_WRITE, BTP_ROOT, BTPageGetMeta, BTPageGetOpaque, BTREE_METAPAGE, BTREE_NOVAC_VERSION, BTreeTupleGetNAtts, BTreeTupleSetDownLink(), BTreeTupleSetNAtts(), BufferGetBlockNumber(), BufferGetPage(), CopyIndexTuple(), elog, END_CRIT_SECTION, xl_btree_metadata::fastlevel, xl_btree_metadata::fastroot, fb(), IndexRelationGetNumberOfKeyAttributes, InvalidOffsetNumber, ItemIdGetLength, xl_btree_metadata::last_cleanup_num_delpages, xl_btree_metadata::level, MarkBufferDirty(), P_FIRSTKEY, P_HIKEY, P_INCOMPLETE_SPLIT, P_NONE, PageAddItem, PageGetItem(), PageGetItemId(), PageSetLSN(), palloc(), PANIC, pfree(), REGBUF_STANDARD, REGBUF_WILL_INIT, RelationGetRelationName, RelationNeedsWAL, xl_btree_metadata::root, SizeOfBtreeNewroot, START_CRIT_SECTION, xl_btree_metadata::version, XLOG_BTREE_NEWROOT, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().
Referenced by _bt_insert_parent().
◆ _bt_pgaddtup()
|
inlinestatic |
Definition at line 2644 of file nbtinsert.c.
2649{
2651
2653 {
2654 trunctuple = *itup;
2657 itup = &trunctuple;
2659 }
2660
2661 if (unlikely(PageAddItem(page, itup, itemsize, itup_off, false, false) == InvalidOffsetNumber))
2662 return false;
2663
2664 return true;
2665}
References BTreeTupleSetNAtts(), fb(), InvalidOffsetNumber, PageAddItem, IndexTupleData::t_info, and unlikely.
Referenced by _bt_split().
◆ _bt_search_insert()
|
static |
Definition at line 319 of file nbtinsert.c.
320{
324
326 {
327 /* Simulate a _bt_getbuf() call with conditional locking */
330 {
331 Page page;
332 BTPageOpaque opaque;
333
336 opaque = BTPageGetOpaque(page);
337
338 /*
339 * Check if the page is still the rightmost leaf page and has
340 * enough free space to accommodate the new tuple. Also check
341 * that the insertion scan key is strictly greater than the first
342 * non-pivot tuple on the page. (Note that we expect itup_key's
343 * scantid to be unset when our caller is a checkingunique
344 * inserter.)
345 */
347 P_ISLEAF(opaque) &&
348 !P_IGNORE(opaque) &&
352 {
353 /*
354 * Caller can use the fastpath optimization because cached
355 * block is still rightmost leaf page, which can fit caller's
356 * new tuple without splitting. Keep block in local cache for
357 * next insert, and have caller use NULL stack.
358 *
359 * Note that _bt_insert_parent() has an assertion that catches
360 * leaf page splits that somehow follow from a fastpath insert
361 * (it should only be passed a NULL stack when it must deal
362 * with a concurrent root page split, and never because a NULL
363 * stack was returned here).
364 */
366 }
367
368 /* Page unsuitable for caller, drop lock and pin */
370 }
371 else
372 {
373 /* Lock unavailable, drop pin */
375 }
376
377 /* Forget block, since cache doesn't appear to be useful */
379 }
380
381 /* Cannot use optimization -- descend tree, return proper descent stack */
383 BT_WRITE);
384}
bool _bt_conditionallockbuf(Relation rel, Buffer buf)
Definition nbtpage.c:1094
BTStack _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP, int access)
Definition nbtsearch.c:98
References _bt_checkpage(), _bt_compare(), _bt_conditionallockbuf(), _bt_relbuf(), _bt_search(), Assert, BT_WRITE, BTPageGetOpaque, BufferGetPage(), fb(), InvalidBlockNumber, InvalidBuffer, P_HIKEY, P_IGNORE, P_ISLEAF, P_RIGHTMOST, PageGetFreeSpace(), PageGetMaxOffsetNumber(), ReadBuffer(), RelationGetTargetBlock, RelationSetTargetBlock, and ReleaseBuffer().
Referenced by _bt_doinsert().
◆ _bt_simpledel_pass()
|
static |
Definition at line 2825 of file nbtinsert.c.
2828{
2833 OffsetNumber offnum;
2834
2835 /* Get array of table blocks pointed to by LP_DEAD-set tuples */
2837 &ndeadblocks);
2838
2839 /* Initialize tableam state that describes index deletion operation */
2840 delstate.irel = rel;
2843 delstate.bottomupfreespace = 0;
2844 delstate.ndeltids = 0;
2847
2848 for (offnum = minoff;
2849 offnum <= maxoff;
2850 offnum = OffsetNumberNext(offnum))
2851 {
2857 void *match;
2858
2860 {
2864
2865 if (!match)
2866 {
2868 continue;
2869 }
2870
2871 /*
2872 * TID's table block is among those pointed to by the TIDs from
2873 * LP_DEAD-bit set tuples on page -- add TID to deltids
2874 */
2877 ostatus->idxoffnum = offnum;
2881
2882 delstate.ndeltids++;
2883 }
2884 else
2885 {
2887
2888 for (int p = 0; p < nitem; p++)
2889 {
2891
2895
2896 if (!match)
2897 {
2899 continue;
2900 }
2901
2902 /*
2903 * TID's table block is among those pointed to by the TIDs
2904 * from LP_DEAD-bit set tuples on page -- add TID to deltids
2905 */
2906 odeltid->tid = *tid;
2908 ostatus->idxoffnum = offnum;
2912
2913 odeltid++;
2914 ostatus++;
2915 delstate.ndeltids++;
2916 }
2917 }
2918 }
2919
2921
2923
2924 /* Physically delete LP_DEAD tuples (plus any delete-safe extra TIDs) */
2926
2929}
static BlockNumber * _bt_deadblocks(Page page, OffsetNumber *deletable, int ndeletable, IndexTuple newitem, int *nblocks)
Definition nbtinsert.c:2951
void _bt_delitems_delete_check(Relation rel, Buffer buf, Relation heapRel, TM_IndexDeleteOp *delstate)
Definition nbtpage.c:1512
Definition tableam.h:245
Definition tableam.h:211
Definition tableam.h:217
References _bt_blk_cmp(), _bt_deadblocks(), _bt_delitems_delete_check(), Assert, BTreeTupleGetNPosting(), BTreeTupleGetPostingN(), BTreeTupleIsPosting(), BufferGetBlockNumber(), BufferGetPage(), fb(), ItemIdIsDead, ItemPointerGetBlockNumber(), MaxTIDsPerBTreePage, OffsetNumberNext, PageGetItem(), PageGetItemId(), palloc(), pfree(), and IndexTupleData::t_tid.
Referenced by _bt_delete_or_dedup_one_page().
◆ _bt_split()
|
static |
Definition at line 1475 of file nbtinsert.c.
1478{
1480 Page origpage;
1482 rightpage;
1484 rightpage_buf;
1486 rightpagenumber;
1488 lopaque,
1489 oopaque;
1493 Size itemsz;
1494 ItemId itemid;
1496 lefthighkey;
1497 OffsetNumber firstrightoff;
1499 afterrightoff,
1500 minusinfoff;
1502 OffsetNumber maxoff;
1504 bool newitemonleft,
1505 isleaf,
1506 isrightmost;
1507
1508 /*
1509 * origpage is the original page to be split. leftpage is a temporary
1510 * buffer that receives the left-sibling data, which will be copied back
1511 * into origpage on success. rightpage is the new page that will receive
1512 * the right-sibling data.
1513 *
1514 * leftpage is allocated after choosing a split point. rightpage's new
1515 * buffer isn't acquired until after leftpage is initialized and has new
1516 * high key, the last point where splitting the page may fail (barring
1517 * corruption). Failing before acquiring new buffer won't have lasting
1518 * consequences, since origpage won't have been modified and leftpage is
1519 * only workspace.
1520 */
1525 maxoff = PageGetMaxOffsetNumber(origpage);
1527
1528 /*
1529 * Choose a point to split origpage at.
1530 *
1531 * A split point can be thought of as a point _between_ two existing data
1532 * items on origpage (the lastleft and firstright tuples), provided you
1533 * pretend that the new item that didn't fit is already on origpage.
1534 *
1535 * Since origpage does not actually contain newitem, the representation of
1536 * split points needs to work with two boundary cases: splits where
1537 * newitem is lastleft, and splits where newitem is firstright.
1538 * newitemonleft resolves the ambiguity that would otherwise exist when
1539 * newitemoff == firstrightoff. In all other cases it's clear which side
1540 * of the split every tuple goes on from context. newitemonleft is
1541 * usually (but not always) redundant information.
1542 *
1543 * firstrightoff is supposed to be an origpage offset number, but it's
1544 * possible that its value will be maxoff+1, which is "past the end" of
1545 * origpage. This happens in the rare case where newitem goes after all
1546 * existing items (i.e. newitemoff is maxoff+1) and we end up splitting
1547 * origpage at the point that leaves newitem alone on new right page. Any
1548 * "!newitemonleft && newitemoff == firstrightoff" split point makes
1549 * newitem the firstright tuple, though, so this case isn't a special
1550 * case.
1551 */
1552 firstrightoff = _bt_findsplitloc(rel, origpage, newitemoff, newitemsz,
1553 newitem, &newitemonleft);
1554
1555 /* Use temporary buffer for leftpage */
1559
1560 /*
1561 * leftpage won't be the root when we're done. Also, clear the SPLIT_END
1562 * and HAS_GARBAGE flags.
1563 */
1566 /* set flag in leftpage indicating that rightpage has no downlink yet */
1569 /* handle btpo_next after rightpage buffer acquired */
1571 /* handle btpo_cycleid after rightpage buffer acquired */
1572
1573 /*
1574 * Copy the original page's LSN into leftpage, which will become the
1575 * updated version of the page. We need this because XLogInsert will
1576 * examine the LSN and possibly dump it in a page image.
1577 */
1579
1580 /*
1581 * Determine page offset number of existing overlapped-with-orignewitem
1582 * posting list when it is necessary to perform a posting list split in
1583 * passing. Note that newitem was already changed by caller (newitem no
1584 * longer has the orignewitem TID).
1585 *
1586 * This page offset number (origpagepostingoff) will be used to pretend
1587 * that the posting split has already taken place, even though the
1588 * required modifications to origpage won't occur until we reach the
1589 * critical section. The lastleft and firstright tuples of our page split
1590 * point should, in effect, come from an imaginary version of origpage
1591 * that has the nposting tuple instead of the original posting list tuple.
1592 *
1593 * Note: _bt_findsplitloc() should have compensated for coinciding posting
1594 * list splits in just the same way, at least in theory. It doesn't
1595 * bother with that, though. In practice it won't affect its choice of
1596 * split point.
1597 */
1599 if (postingoff != 0)
1600 {
1603 &newitem->t_tid) < 0);
1606 }
1607
1608 /*
1609 * The high key for the new left page is a possibly-truncated copy of
1610 * firstright on the leaf level (it's "firstright itself" on internal
1611 * pages; see !isleaf comments below). This may seem to be contrary to
1612 * Lehman & Yao's approach of using a copy of lastleft as the new high key
1613 * when splitting on the leaf level. It isn't, though.
1614 *
1615 * Suffix truncation will leave the left page's high key fully equal to
1616 * lastleft when lastleft and firstright are equal prior to heap TID (that
1617 * is, the tiebreaker TID value comes from lastleft). It isn't actually
1618 * necessary for a new leaf high key to be a copy of lastleft for the L&Y
1619 * "subtree" invariant to hold. It's sufficient to make sure that the new
1620 * leaf high key is strictly less than firstright, and greater than or
1621 * equal to (not necessarily equal to) lastleft. In other words, when
1622 * suffix truncation isn't possible during a leaf page split, we take
1623 * L&Y's exact approach to generating a new high key for the left page.
1624 * (Actually, that is slightly inaccurate. We don't just use a copy of
1625 * lastleft. A tuple with all the keys from firstright but the max heap
1626 * TID from lastleft is used, to avoid introducing a special case.)
1627 */
1628 if (!newitemonleft && newitemoff == firstrightoff)
1629 {
1630 /* incoming tuple becomes firstright */
1631 itemsz = newitemsz;
1632 firstright = newitem;
1633 }
1634 else
1635 {
1636 /* existing item at firstrightoff becomes firstright */
1637 itemid = PageGetItemId(origpage, firstrightoff);
1638 itemsz = ItemIdGetLength(itemid);
1642 }
1643
1645 {
1646 IndexTuple lastleft;
1647
1648 /* Attempt suffix truncation for leaf page splits */
1649 if (newitemonleft && newitemoff == firstrightoff)
1650 {
1651 /* incoming tuple becomes lastleft */
1652 lastleft = newitem;
1653 }
1654 else
1655 {
1657
1658 /* existing item before firstrightoff becomes lastleft */
1664 lastleft = nposting;
1665 }
1666
1669 }
1670 else
1671 {
1672 /*
1673 * Don't perform suffix truncation on a copy of firstright to make
1674 * left page high key for internal page splits. Must use firstright
1675 * as new high key directly.
1676 *
1677 * Each distinct separator key value originates as a leaf level high
1678 * key; all other separator keys/pivot tuples are copied from one
1679 * level down. A separator key in a grandparent page must be
1680 * identical to high key in rightmost parent page of the subtree to
1681 * its left, which must itself be identical to high key in rightmost
1682 * child page of that same subtree (this even applies to separator
1683 * from grandparent's high key). There must always be an unbroken
1684 * "seam" of identical separator keys that guide index scans at every
1685 * level, starting from the grandparent. That's why suffix truncation
1686 * is unsafe here.
1687 *
1688 * Internal page splits will truncate firstright into a "negative
1689 * infinity" data item when it gets inserted on the new right page
1690 * below, though. This happens during the call to _bt_pgaddtup() for
1691 * the new first data item for right page. Do not confuse this
1692 * mechanism with suffix truncation. It is just a convenient way of
1693 * implementing page splits that split the internal page "inside"
1694 * firstright. The lefthighkey separator key cannot appear a second
1695 * time in the right page (only firstright's downlink goes in right
1696 * page).
1697 */
1699 }
1700
1701 /*
1702 * Add new high key to leftpage
1703 */
1705
1708 IndexRelationGetNumberOfKeyAttributes(rel));
1710 if (PageAddItem(leftpage, lefthighkey, itemsz, afterleftoff, false, false) == InvalidOffsetNumber)
1712 " while splitting block %u of index \"%s\"",
1715
1716 /*
1717 * Acquire a new right page to split into, now that left page has a new
1718 * high key.
1719 *
1720 * To not confuse future VACUUM operations, we zero the right page and
1721 * work on an in-memory copy of it before writing WAL, then copy its
1722 * contents back to the actual page once we start the critical section
1723 * work. This simplifies the split work, so as there is no need to zero
1724 * the right page before throwing an error.
1725 */
1728
1729 /*
1730 * Copy the contents of the right page into its temporary location, and
1731 * zero the original space.
1732 */
1736 /* rightpage was initialized by _bt_allocbuf */
1738
1739 /*
1740 * Finish off remaining leftpage special area fields. They cannot be set
1741 * before both origpage (leftpage) and rightpage buffers are acquired and
1742 * locked.
1743 *
1744 * btpo_cycleid is only used with leaf pages, though we set it here in all
1745 * cases just to be consistent.
1746 */
1749
1750 /*
1751 * rightpage won't be the root when we're done. Also, clear the SPLIT_END
1752 * and HAS_GARBAGE flags.
1753 */
1760
1761 /*
1762 * Add new high key to rightpage where necessary.
1763 *
1764 * If the page we're splitting is not the rightmost page at its level in
1765 * the tree, then the first entry on the page is the high key from
1766 * origpage.
1767 */
1769
1771 {
1773
1775 itemsz = ItemIdGetLength(itemid);
1779 IndexRelationGetNumberOfKeyAttributes(rel));
1780 if (PageAddItem(rightpage, righthighkey, itemsz, afterrightoff, false, false) == InvalidOffsetNumber)
1781 {
1783 " while splitting block %u of index \"%s\"",
1785 }
1787 }
1788
1789 /*
1790 * Internal page splits truncate first data item on right page -- it
1791 * becomes "minus infinity" item for the page. Set this up here.
1792 */
1796
1797 /*
1798 * Now transfer all the data items (non-pivot tuples in isleaf case, or
1799 * additional pivot tuples in !isleaf case) to the appropriate page.
1800 *
1801 * Note: we *must* insert at least the right page's items in item-number
1802 * order, for the benefit of _bt_restore_page().
1803 */
1805 {
1807
1809 itemsz = ItemIdGetLength(itemid);
1811
1812 /* replace original item with nposting due to posting split? */
1814 {
1818 }
1819
1820 /* does new item belong before this one? */
1822 {
1823 if (newitemonleft)
1824 {
1825 Assert(newitemoff <= firstrightoff);
1827 false))
1828 {
1830 " while splitting block %u of index \"%s\"",
1832 }
1834 }
1835 else
1836 {
1837 Assert(newitemoff >= firstrightoff);
1840 {
1842 " while splitting block %u of index \"%s\"",
1844 }
1846 }
1847 }
1848
1849 /* decide which page to put it on */
1851 {
1853 {
1855 " while splitting block %u of index \"%s\"",
1857 }
1859 }
1860 else
1861 {
1864 {
1866 " while splitting block %u of index \"%s\"",
1868 }
1870 }
1871 }
1872
1873 /* Handle case where newitem goes at the end of rightpage */
1875 {
1876 /*
1877 * Can't have newitemonleft here; that would imply we were told to put
1878 * *everything* on the left page, which cannot fit (if it could, we'd
1879 * not be splitting the page).
1880 */
1881 Assert(!newitemonleft && newitemoff == maxoff + 1);
1884 {
1886 " while splitting block %u of index \"%s\"",
1888 }
1890 }
1891
1892 /*
1893 * We have to grab the original right sibling (if any) and update its prev
1894 * link. We are guaranteed that this is deadlock-free, since we couple
1895 * the locks in the standard order: left to right.
1896 */
1898 {
1903 {
1907 "block %u links to %u instead of expected %u in index \"%s\"",
1909 RelationGetRelationName(rel))));
1910 }
1911
1912 /*
1913 * Check to see if we can set the SPLIT_END flag in the right-hand
1914 * split page; this can save some I/O for vacuum since it need not
1915 * proceed to the right sibling. We can set the flag if the right
1916 * sibling has a different cycleid: that means it could not be part of
1917 * a group of pages that were all split off from the same ancestor
1918 * page. If you're confused, imagine that page A splits to A B and
1919 * then again, yielding A C B, while vacuum is in progress. Tuples
1920 * originally in A could now be in either B or C, hence vacuum must
1921 * examine both pages. But if D, our right sibling, has a different
1922 * cycleid then it could not contain any tuples that were in A when
1923 * the vacuum started.
1924 */
1927 }
1928
1929 /*
1930 * Right sibling is locked, new siblings are prepared, but original page
1931 * is not updated yet.
1932 *
1933 * NO EREPORT(ERROR) till right sibling is updated. We can get away with
1934 * not starting the critical section till here because we haven't been
1935 * scribbling on the original page yet; see comments above.
1936 */
1937 START_CRIT_SECTION();
1938
1939 /*
1940 * By here, the original data page has been split into two new halves, and
1941 * these are correct. The algorithm requires that the left page never
1942 * move during a split, so we copy the new left page back on top of the
1943 * original. We need to do this before writing the WAL record, so that
1944 * XLogInsert can WAL log an image of the page if necessary.
1945 */
1947 /* leftpage, lopaque must not be used below here */
1948
1949 /*
1950 * Move the contents of the right page from its temporary location to the
1951 * destination buffer, before writing the WAL record. Unlike the left
1952 * page, the right page and its opaque area are still needed to complete
1953 * the update of the page, so reinitialize them.
1954 */
1958
1961
1963 {
1966 }
1967
1968 /*
1969 * Clear INCOMPLETE_SPLIT flag on child if inserting the new item finishes
1970 * a split
1971 */
1973 {
1976
1979 }
1980
1981 /* XLOG stuff */
1983 {
1987
1989 /* See comments below on newitem, orignewitem, and posting lists */
1990 xlrec.firstrightoff = firstrightoff;
1991 xlrec.newitemoff = newitemoff;
1992 xlrec.postingoff = 0;
1994 xlrec.postingoff = postingoff;
1995
1996 XLogBeginInsert();
1998
2001 /* Log original right sibling, since we've changed its prev-pointer */
2006
2007 /*
2008 * Log the new item, if it was inserted on the left page. (If it was
2009 * put on the right page, we don't need to explicitly WAL log it
2010 * because it's included with all the other items on the right page.)
2011 * Show the new item as belonging to the left page buffer, so that it
2012 * is not stored if XLogInsert decides it needs a full-page image of
2013 * the left page. We always store newitemoff in the record, though.
2014 *
2015 * The details are sometimes slightly different for page splits that
2016 * coincide with a posting list split. If both the replacement
2017 * posting list and newitem go on the right page, then we don't need
2018 * to log anything extra, just like the simple !newitemonleft
2019 * no-posting-split case (postingoff is set to zero in the WAL record,
2020 * so recovery doesn't need to process a posting list split at all).
2021 * Otherwise, we set postingoff and log orignewitem instead of
2022 * newitem, despite having actually inserted newitem. REDO routine
2023 * must reconstruct nposting and newitem using _bt_swap_posting().
2024 *
2025 * Note: It's possible that our page split point is the point that
2026 * makes the posting list lastleft and newitem firstright. This is
2027 * the only case where we log orignewitem/newitem despite newitem
2028 * going on the right page. If XLogInsert decides that it can omit
2029 * orignewitem due to logging a full-page image of the left page,
2030 * everything still works out, since recovery only needs to log
2031 * orignewitem for items on the left page (just like the regular
2032 * newitem-logged case).
2033 */
2035 XLogRegisterBufData(0, newitem, newitemsz);
2037 {
2039 Assert(newitemonleft || firstrightoff == newitemoff);
2042 }
2043
2044 /* Log the left page's new high key */
2046 {
2047 /* lefthighkey isn't local copy, get current pointer */
2050 }
2053
2054 /*
2055 * Log the contents of the right page in the format understood by
2056 * _bt_restore_page(). The whole right page will be recreated.
2057 *
2058 * Direct access to page is not good but faster - we should implement
2059 * some new func in page API. Note we only store the tuples
2060 * themselves, knowing that they were inserted in item-number order
2061 * and so the line pointers can be reconstructed. See comments for
2062 * _bt_restore_page().
2063 */
2064 XLogRegisterBufData(1,
2067
2070
2077 }
2078
2079 END_CRIT_SECTION();
2080
2081 /* release the old right sibling */
2084
2085 /* release the child */
2088
2089 /* be tidy */
2092
2093 /* split's done */
2095}
static bool _bt_pgaddtup(Page page, Size itemsize, const IndexTupleData *itup, OffsetNumber itup_off, bool newfirstdataitem)
Definition nbtinsert.c:2644
OffsetNumber _bt_findsplitloc(Relation rel, Page origpage, OffsetNumber newitemoff, Size newitemsz, IndexTuple newitem, bool *newitemonleft)
Definition nbtsplitloc.c:130
IndexTuple _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright, BTScanInsert itup_key)
Definition nbtutils.c:698
Definition c.h:1109
Definition nbtxlog.h:151
References _bt_allocbuf(), _bt_findsplitloc(), _bt_getbuf(), _bt_pageinit(), _bt_pgaddtup(), _bt_relbuf(), _bt_truncate(), _bt_vacuum_cycleid(), Assert, BT_WRITE, BTP_HAS_GARBAGE, BTP_INCOMPLETE_SPLIT, BTP_ROOT, BTP_SPLIT_END, BTPageGetOpaque, BTreeTupleGetNAtts, BTreeTupleIsPosting(), buf, BufferGetBlockNumber(), BufferGetPage(), BufferGetPageSize(), elog, END_CRIT_SECTION, ereport, errcode(), errmsg_internal(), ERROR, fb(), i, IndexRelationGetNumberOfKeyAttributes, IndexTupleSize(), InvalidBuffer, InvalidOffsetNumber, ItemIdGetLength, ItemPointerCompare(), xl_btree_split::level, MarkBufferDirty(), MAXALIGN, OffsetNumberNext, OffsetNumberPrev, P_FIRSTDATAKEY, P_HIKEY, P_ISLEAF, P_RIGHTMOST, PageAddItem, PageGetItem(), PageGetItemId(), PageGetLSN(), PageGetMaxOffsetNumber(), PageSetLSN(), pfree(), REGBUF_STANDARD, REGBUF_WILL_INIT, RelationGetRelationName, RelationNeedsWAL, SizeOfBtreeSplit, START_CRIT_SECTION, IndexTupleData::t_tid, XLOG_BTREE_SPLIT_L, XLOG_BTREE_SPLIT_R, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().
Referenced by _bt_insertonpg().
◆ _bt_stepright()
|
static |
Definition at line 1029 of file nbtinsert.c.
1031{
1032 Page page;
1033 BTPageOpaque opaque;
1036
1039 opaque = BTPageGetOpaque(page);
1040
1043 for (;;)
1044 {
1047 opaque = BTPageGetOpaque(page);
1048
1049 /*
1050 * If this page was incompletely split, finish the split now. We do
1051 * this while holding a lock on the left sibling, which is not good
1052 * because finishing the split could be a fairly lengthy operation.
1053 * But this should happen very seldom.
1054 */
1056 {
1059 continue;
1060 }
1061
1063 break;
1066 RelationGetRelationName(rel));
1067
1069 }
1070 /* rbuf locked; unlock buf, update state for caller */
1074}
References _bt_finish_split(), _bt_relandgetbuf(), _bt_relbuf(), Assert, BT_WRITE, BTPageGetOpaque, BTPageOpaqueData::btpo_next, BufferGetPage(), elog, ERROR, fb(), InvalidBuffer, P_IGNORE, P_INCOMPLETE_SPLIT, P_RIGHTMOST, and RelationGetRelationName.
Referenced by _bt_findinsertloc().
