| blob | d33f814a938acb282f9cd7c8841ad511a75469da |
1 /*-------------------------------------------------------------------------
2 *
3 * nbtinsert.c
4 * Item insertion in Lehman and Yao btrees for Postgres.
5 *
6 * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/access/nbtree/nbtinsert.c
12 *
13 *-------------------------------------------------------------------------
14 */
29 /* Minimum tree height for application of fastpath optimization */
30 #define BTREE_FASTPATH_MIN_LEVEL 2
34 BTInsertState insertstate);
36 Relation heapRel,
40 BTInsertState insertstate,
43 BTStack stack,
44 Relation heapRel);
48 Buffer buf,
49 Buffer cbuf,
50 BTStack stack,
51 IndexTuple itup,
52 Size itemsz,
53 OffsetNumber newitemoff,
66 BTInsertState insertstate,
72 OffsetNumber maxoff);
78 /*
79 * _bt_doinsert() -- Handle insertion of a single index tuple in the tree.
80 *
81 * This routine is called by the public interface routine, btinsert.
82 * By here, itup is filled in, including the TID.
83 *
84 * If checkUnique is UNIQUE_CHECK_NO or UNIQUE_CHECK_PARTIAL, this
85 * will allow duplicates. Otherwise (UNIQUE_CHECK_YES or
86 * UNIQUE_CHECK_EXISTING) it will throw error for a duplicate.
87 * For UNIQUE_CHECK_EXISTING we merely run the duplicate check, and
88 * don't actually insert.
89 *
90 * indexUnchanged executor hint indicates if itup is from an
91 * UPDATE that didn't logically change the indexed value, but
92 * must nevertheless have a new entry to point to a successor
93 * version.
94 *
95 * The result value is only significant for UNIQUE_CHECK_PARTIAL:
96 * it must be true if the entry is known unique, else false.
97 * (In the current implementation we'll also return true after a
98 * successful UNIQUE_CHECK_YES or UNIQUE_CHECK_EXISTING call, but
99 * that's just a coding artifact.)
100 */
101 bool
104 Relation heapRel)
105 {
107 BTInsertStateData insertstate;
108 BTScanInsert itup_key;
109 BTStack stack;
112 /* we need an insertion scan key to do our search, so build one */
116 {
118 {
119 /* No (heapkeyspace) scantid until uniqueness established */
121 }
122 else
123 {
124 /*
125 * Scan key for new tuple contains NULL key values. Bypass
126 * checkingunique steps. They are unnecessary because core code
127 * considers NULL unequal to every value, including NULL.
128 *
129 * This optimization avoids O(N^2) behavior within the
130 * _bt_findinsertloc() heapkeyspace path when a unique index has a
131 * large number of "duplicates" with NULL key values.
132 */
134 /* Tuple is unique in the sense that core code cares about */
137 }
138 }
140 /*
141 * Fill in the BTInsertState working area, to track the current page and
142 * position within the page to insert on.
143 *
144 * Note that itemsz is passed down to lower level code that deals with
145 * inserting the item. It must be MAXALIGN()'d. This ensures that space
146 * accounting code consistently considers the alignment overhead that we
147 * expect PageAddItem() will add later. (Actually, index_form_tuple() is
148 * already conservative about alignment, but we don't rely on that from
149 * this distance. Besides, preserving the "true" tuple size in index
150 * tuple headers for the benefit of nbtsplitloc.c might happen someday.
151 * Note that heapam does not MAXALIGN() each heap tuple's lp_len field.)
152 */
160 search:
162 /*
163 * Find and lock the leaf page that the tuple should be added to by
164 * searching from the root page. insertstate.buf will hold a buffer that
165 * is locked in exclusive mode afterwards.
166 */
169 /*
170 * checkingunique inserts are not allowed to go ahead when two tuples with
171 * equal key attribute values would be visible to new MVCC snapshots once
172 * the xact commits. Check for conflicts in the locked page/buffer (if
173 * needed) here.
174 *
175 * It might be necessary to check a page to the right in _bt_check_unique,
176 * though that should be very rare. In practice the first page the value
177 * could be on (with scantid omitted) is almost always also the only page
178 * that a matching tuple might be found on. This is due to the behavior
179 * of _bt_findsplitloc with duplicate tuples -- a group of duplicates can
180 * only be allowed to cross a page boundary when there is no candidate
181 * leaf page split point that avoids it. Also, _bt_check_unique can use
182 * the leaf page high key to determine that there will be no duplicates on
183 * the right sibling without actually visiting it (it uses the high key in
184 * cases where the new item happens to belong at the far right of the leaf
185 * page).
186 *
187 * NOTE: obviously, _bt_check_unique can only detect keys that are already
188 * in the index; so it cannot defend against concurrent insertions of the
189 * same key. We protect against that by means of holding a write lock on
190 * the first page the value could be on, with omitted/-inf value for the
191 * implicit heap TID tiebreaker attribute. Any other would-be inserter of
192 * the same key must acquire a write lock on the same page, so only one
193 * would-be inserter can be making the check at one time. Furthermore,
194 * once we are past the check we hold write locks continuously until we
195 * have performed our insertion, so no later inserter can fail to see our
196 * insertion. (This requires some care in _bt_findinsertloc.)
197 *
198 * If we must wait for another xact, we release the lock while waiting,
199 * and then must perform a new search.
200 *
201 * For a partial uniqueness check, we don't wait for the other xact. Just
202 * let the tuple in and return false for possibly non-unique, or true for
203 * definitely unique.
204 */
206 {
207 TransactionId xwait;
208 uint32 speculativeToken;
214 {
215 /* Have to wait for the other guy ... */
219 /*
220 * If it's a speculative insertion, wait for it to finish (ie. to
221 * go ahead with the insertion, or kill the tuple). Otherwise
222 * wait for the transaction to finish as usual.
223 */
226 else
229 /* start over... */
233 }
235 /* Uniqueness is established -- restore heap tid as scantid */
238 }
241 {
242 OffsetNumber newitemoff;
244 /*
245 * The only conflict predicate locking cares about for indexes is when
246 * an index tuple insert conflicts with an existing lock. We don't
247 * know the actual page we're going to insert on for sure just yet in
248 * checkingunique and !heapkeyspace cases, but it's okay to use the
249 * first page the value could be on (with scantid omitted) instead.
250 */
253 /*
254 * Do the insertion. Note that insertstate contains cached binary
255 * search bounds established within _bt_check_unique when insertion is
256 * checkingunique.
257 */
263 }
264 else
265 {
266 /* just release the buffer */
268 }
270 /* be tidy */
276 }
278 /*
279 * _bt_search_insert() -- _bt_search() wrapper for inserts
280 *
281 * Search the tree for a particular scankey, or more precisely for the first
282 * leaf page it could be on. Try to make use of the fastpath optimization's
283 * rightmost leaf page cache before actually searching the tree from the root
284 * page, though.
285 *
286 * Return value is a stack of parent-page pointers (though see notes about
287 * fastpath optimization and page splits below). insertstate->buf is set to
288 * the address of the leaf-page buffer, which is write-locked and pinned in
289 * all cases (if necessary by creating a new empty root page for caller).
290 *
291 * The fastpath optimization avoids most of the work of searching the tree
292 * repeatedly when a single backend inserts successive new tuples on the
293 * rightmost leaf page of an index. A backend cache of the rightmost leaf
294 * page is maintained within _bt_insertonpg(), and used here. The cache is
295 * invalidated here when an insert of a non-pivot tuple must take place on a
296 * non-rightmost leaf page.
297 *
298 * The optimization helps with indexes on an auto-incremented field. It also
299 * helps with indexes on datetime columns, as well as indexes with lots of
300 * NULL values. (NULLs usually get inserted in the rightmost page for single
301 * column indexes, since they usually get treated as coming after everything
302 * else in the key space. Individual NULL tuples will generally be placed on
303 * the rightmost leaf page due to the influence of the heap TID column.)
304 *
305 * Note that we avoid applying the optimization when there is insufficient
306 * space on the rightmost page to fit caller's new item. This is necessary
307 * because we'll need to return a real descent stack when a page split is
308 * expected (actually, caller can cope with a leaf page split that uses a NULL
309 * stack, but that's very slow and so must be avoided). Note also that the
310 * fastpath optimization acquires the lock on the page conditionally as a way
311 * of reducing extra contention when there are concurrent insertions into the
312 * rightmost page (we give up if we'd have to wait for the lock). We assume
313 * that it isn't useful to apply the optimization when there is contention,
314 * since each per-backend cache won't stay valid for long.
315 */
316 static BTStack
318 {
324 {
325 /* Simulate a _bt_getbuf() call with conditional locking */
328 {
329 Page page;
330 BTPageOpaque opaque;
336 /*
337 * Check if the page is still the rightmost leaf page and has
338 * enough free space to accommodate the new tuple. Also check
339 * that the insertion scan key is strictly greater than the first
340 * non-pivot tuple on the page. (Note that we expect itup_key's
341 * scantid to be unset when our caller is a checkingunique
342 * inserter.)
343 */
350 {
351 /*
352 * Caller can use the fastpath optimization because cached
353 * block is still rightmost leaf page, which can fit caller's
354 * new tuple without splitting. Keep block in local cache for
355 * next insert, and have caller use NULL stack.
356 *
357 * Note that _bt_insert_parent() has an assertion that catches
358 * leaf page splits that somehow follow from a fastpath insert
359 * (it should only be passed a NULL stack when it must deal
360 * with a concurrent root page split, and never because a NULL
361 * stack was returned here).
362 */
364 }
366 /* Page unsuitable for caller, drop lock and pin */
368 }
369 else
370 {
371 /* Lock unavailable, drop pin */
373 }
375 /* Forget block, since cache doesn't appear to be useful */
377 }
379 /* Cannot use optimization -- descend tree, return proper descent stack */
382 }
384 /*
385 * _bt_check_unique() -- Check for violation of unique index constraint
386 *
387 * Returns InvalidTransactionId if there is no conflict, else an xact ID
388 * we must wait for to see if it commits a conflicting tuple. If an actual
389 * conflict is detected, no return --- just ereport(). If an xact ID is
390 * returned, and the conflicting tuple still has a speculative insertion in
391 * progress, *speculativeToken is set to non-zero, and the caller can wait for
392 * the verdict on the insertion using SpeculativeInsertionWait().
393 *
394 * However, if checkUnique == UNIQUE_CHECK_PARTIAL, we always return
395 * InvalidTransactionId because we don't want to wait. In this case we
396 * set *is_unique to false if there is a potential conflict, and the
397 * core code must redo the uniqueness check later.
398 *
399 * As a side-effect, sets state in insertstate that can later be used by
400 * _bt_findinsertloc() to reuse most of the binary search work we do
401 * here.
402 *
403 * This code treats NULLs as equal, unlike the default semantics for unique
404 * indexes. So do not call here when there are NULL values in scan key and
405 * the index uses the default NULLS DISTINCT mode.
406 */
407 static TransactionId
411 {
416 SnapshotData SnapshotDirty;
417 OffsetNumber offset;
418 OffsetNumber maxoff;
419 Page page;
420 BTPageOpaque opaque;
427 /* Assume unique until we find a duplicate */
436 /*
437 * Find the first tuple with the same key.
438 *
439 * This also saves the binary search bounds in insertstate. We use them
440 * in the fastpath below, but also in the _bt_findinsertloc() call later.
441 */
445 /*
446 * Scan over all equal tuples, looking for live conflicts.
447 */
452 {
453 /*
454 * Each iteration of the loop processes one heap TID, not one index
455 * tuple. Current offset number for page isn't usually advanced on
456 * iterations that process heap TIDs from posting list tuples.
457 *
458 * "inposting" state is set when _inside_ a posting list --- not when
459 * we're at the start (or end) of a posting list. We advance curposti
460 * at the end of the iteration when inside a posting list tuple. In
461 * general, every loop iteration either advances the page offset or
462 * advances curposti --- an iteration that handles the rightmost/max
463 * heap TID in a posting list finally advances the page offset (and
464 * unsets "inposting").
465 *
466 * Make sure the offset points to an actual index tuple before trying
467 * to examine it...
468 */
470 {
471 /*
472 * Fastpath: In most cases, we can use cached search bounds to
473 * limit our consideration to items that are definitely
474 * duplicates. This fastpath doesn't apply when the original page
475 * is empty, or when initial offset is past the end of the
476 * original page, which may indicate that we need to examine a
477 * second or subsequent page.
478 *
479 * Note that this optimization allows us to avoid calling
480 * _bt_compare() directly when there are no duplicates, as long as
481 * the offset where the key will go is not at the end of the page.
482 */
484 {
490 }
492 /*
493 * We can skip items that are already marked killed.
494 *
495 * In the presence of heavy update activity an index may contain
496 * many killed items with the same key; running _bt_compare() on
497 * each killed item gets expensive. Just advance over killed
498 * items as quickly as we can. We only apply _bt_compare() when
499 * we get to a non-killed item. We could reuse the bounds to
500 * avoid _bt_compare() calls for known equal tuples, but it
501 * doesn't seem worth it.
502 */
506 {
507 ItemPointerData htid;
511 {
512 /* Plain tuple, or first TID in posting list tuple */
516 /* Advanced curitup */
519 }
521 /* okay, we gotta fetch the heap tuple using htid ... */
523 {
524 /* ... htid is from simple non-pivot tuple */
527 }
529 {
530 /* ... htid is first TID in new posting list */
535 }
536 else
537 {
538 /* ... htid is second or subsequent TID in posting list */
541 }
543 /*
544 * If we are doing a recheck, we expect to find the tuple we
545 * are rechecking. It's not a duplicate, but we have to keep
546 * scanning.
547 */
550 {
552 }
554 /*
555 * Check if there's any table tuples for this index entry
556 * satisfying SnapshotDirty. This is necessary because for AMs
557 * with optimizations like heap's HOT, we have just a single
558 * index entry for the entire chain.
559 */
563 {
564 TransactionId xwait;
566 /*
567 * It is a duplicate. If we are only doing a partial
568 * check, then don't bother checking if the tuple is being
569 * updated in another transaction. Just return the fact
570 * that it is a potential conflict and leave the full
571 * check till later. Don't invalidate binary search
572 * bounds.
573 */
575 {
580 }
582 /*
583 * If this tuple is being updated by other transaction
584 * then we have to wait for its commit/abort.
585 */
590 {
593 /* Tell _bt_doinsert to wait... */
595 /* Caller releases lock on buf immediately */
598 }
600 /*
601 * Otherwise we have a definite conflict. But before
602 * complaining, look to see if the tuple we want to insert
603 * is itself now committed dead --- if so, don't complain.
604 * This is a waste of time in normal scenarios but we must
605 * do it to support CREATE INDEX CONCURRENTLY.
606 *
607 * We must follow HOT-chains here because during
608 * concurrent index build, we insert the root TID though
609 * the actual tuple may be somewhere in the HOT-chain.
610 * While following the chain we might not stop at the
611 * exact tuple which triggered the insert, but that's OK
612 * because if we find a live tuple anywhere in this chain,
613 * we have a unique key conflict. The other live tuple is
614 * not part of this chain because it had a different index
615 * entry.
616 */
620 {
621 /* Normal case --- it's still live */
622 }
623 else
624 {
625 /*
626 * It's been deleted, so no error, and no need to
627 * continue searching
628 */
630 }
632 /*
633 * Check for a conflict-in as we would if we were going to
634 * write to this page. We aren't actually going to write,
635 * but we want a chance to report SSI conflicts that would
636 * otherwise be masked by this unique constraint
637 * violation.
638 */
641 /*
642 * This is a definite conflict. Break the tuple down into
643 * datums and report the error. But first, make sure we
644 * release the buffer locks we're holding ---
645 * BuildIndexValueDescription could make catalog accesses,
646 * which in the worst case might touch this same index and
647 * cause deadlocks.
648 */
655 {
664 isnull);
674 }
675 }
679 {
680 /*
681 * The conflicting tuple (or all HOT chains pointed to by
682 * all posting list TIDs) is dead to everyone, so mark the
683 * index entry killed.
684 */
688 /*
689 * Mark buffer with a dirty hint, since state is not
690 * crucial. Be sure to mark the proper buffer dirty.
691 */
694 else
696 }
698 /*
699 * Remember if posting list tuple has even a single HOT chain
700 * whose members are not all dead
701 */
704 }
705 }
708 {
709 /* Advance to next TID in same posting list */
710 curposti++;
712 }
714 {
715 /* Advance to next tuple */
719 }
720 else
721 {
724 /* If scankey == hikey we gotta check the next page too */
731 /* Advance to next non-dead page --- there must be one */
733 {
744 }
745 /* Will also advance to next tuple */
750 /* Don't invalidate binary search bounds */
751 }
752 }
754 /*
755 * If we are doing a recheck then we should have found the tuple we are
756 * checking. Otherwise there's something very wrong --- probably, the
757 * index is on a non-immutable expression.
758 */
772 }
775 /*
776 * _bt_findinsertloc() -- Finds an insert location for a tuple
777 *
778 * On entry, insertstate buffer contains the page the new tuple belongs
779 * on. It is exclusive-locked and pinned by the caller.
780 *
781 * If 'checkingunique' is true, the buffer on entry is the first page
782 * that contains duplicates of the new key. If there are duplicates on
783 * multiple pages, the correct insertion position might be some page to
784 * the right, rather than the first page. In that case, this function
785 * moves right to the correct target page.
786 *
787 * (In a !heapkeyspace index, there can be multiple pages with the same
788 * high key, where the new tuple could legitimately be placed on. In
789 * that case, the caller passes the first page containing duplicates,
790 * just like when checkingunique=true. If that page doesn't have enough
791 * room for the new tuple, this function moves right, trying to find a
792 * legal page that does.)
793 *
794 * If 'indexUnchanged' is true, this is for an UPDATE that didn't
795 * logically change the indexed value, but must nevertheless have a new
796 * entry to point to a successor version. This hint from the executor
797 * will influence our behavior when the page might have to be split and
798 * we must consider our options. Bottom-up index deletion can avoid
799 * pathological version-driven page splits, but we only want to go to the
800 * trouble of trying it when we already have moderate confidence that
801 * it's appropriate. The hint should not significantly affect our
802 * behavior over time unless practically all inserts on to the leaf page
803 * get the hint.
804 *
805 * On exit, insertstate buffer contains the chosen insertion page, and
806 * the offset within that page is returned. If _bt_findinsertloc needed
807 * to move right, the lock and pin on the original page are released, and
808 * the new buffer is exclusively locked and pinned instead.
809 *
810 * If insertstate contains cached binary search bounds, we will take
811 * advantage of them. This avoids repeating comparisons that we made in
812 * _bt_check_unique() already.
813 */
814 static OffsetNumber
816 BTInsertState insertstate,
819 BTStack stack,
820 Relation heapRel)
821 {
824 BTPageOpaque opaque;
825 OffsetNumber newitemoff;
829 /* Check 1/3 of a page restriction */
841 {
842 /* Keep track of whether checkingunique duplicate seen */
845 /*
846 * If we're inserting into a unique index, we may have to walk right
847 * through leaf pages to find the one leaf page that we must insert on
848 * to.
849 *
850 * This is needed for checkingunique callers because a scantid was not
851 * used when we called _bt_search(). scantid can only be set after
852 * _bt_check_unique() has checked for duplicates. The buffer
853 * initially stored in insertstate->buf has the page where the first
854 * duplicate key might be found, which isn't always the page that new
855 * tuple belongs on. The heap TID attribute for new tuple (scantid)
856 * could force us to insert on a sibling page, though that should be
857 * very rare in practice.
858 */
860 {
862 {
863 /* Encountered a duplicate in _bt_check_unique() */
866 }
869 {
870 /*
871 * Does the new tuple belong on this page?
872 *
873 * The earlier _bt_check_unique() call may well have
874 * established a strict upper bound on the offset for the new
875 * item. If it's not the last item of the page (i.e. if there
876 * is at least one tuple on the page that goes after the tuple
877 * we're inserting) then we know that the tuple belongs on
878 * this page. We can skip the high key check.
879 */
885 /* Test '<=', not '!=', since scantid is set now */
891 /* Update local state after stepping right */
894 /* Assume duplicates (if checkingunique) */
896 }
897 }
899 /*
900 * If the target page cannot fit newitem, try to avoid splitting the
901 * page on insert by performing deletion or deduplication now
902 */
906 indexUnchanged);
907 }
908 else
909 {
910 /*----------
911 * This is a !heapkeyspace (version 2 or 3) index. The current page
912 * is the first page that we could insert the new tuple to, but there
913 * may be other pages to the right that we could opt to use instead.
914 *
915 * If the new key is equal to one or more existing keys, we can
916 * legitimately place it anywhere in the series of equal keys. In
917 * fact, if the new key is equal to the page's "high key" we can place
918 * it on the next page. If it is equal to the high key, and there's
919 * not room to insert the new tuple on the current page without
920 * splitting, then we move right hoping to find more free space and
921 * avoid a split.
922 *
923 * Keep scanning right until we
924 * (a) find a page with enough free space,
925 * (b) reach the last page where the tuple can legally go, or
926 * (c) get tired of searching.
927 * (c) is not flippant; it is important because if there are many
928 * pages' worth of equal keys, it's better to split one of the early
929 * pages than to scan all the way to the end of the run of equal keys
930 * on every insert. We implement "get tired" as a random choice,
931 * since stopping after scanning a fixed number of pages wouldn't work
932 * well (we'd never reach the right-hand side of previously split
933 * pages). The probability of moving right is set at 0.99, which may
934 * seem too high to change the behavior much, but it does an excellent
935 * job of preventing O(N^2) behavior with many equal keys.
936 *----------
937 */
939 {
940 /*
941 * Before considering moving right, see if we can obtain enough
942 * space by erasing LP_DEAD items
943 */
945 {
946 /* Perform simple deletion */
952 }
954 /*
955 * Nope, so check conditions (b) and (c) enumerated above
956 *
957 * The earlier _bt_check_unique() call may well have established a
958 * strict upper bound on the offset for the new item. If it's not
959 * the last item of the page (i.e. if there is at least one tuple
960 * on the page that's greater than the tuple we're inserting to)
961 * then we know that the tuple belongs on this page. We can skip
962 * the high key check.
963 */
975 /* Update local state after stepping right */
978 }
979 }
981 /*
982 * We should now be on the correct page. Find the offset within the page
983 * for the new tuple. (Possibly reusing earlier search bounds.)
984 */
991 {
992 /*
993 * There is an overlapping posting list tuple with its LP_DEAD bit
994 * set. We don't want to unnecessarily unset its LP_DEAD bit while
995 * performing a posting list split, so perform simple index tuple
996 * deletion early.
997 */
1001 /*
1002 * Do new binary search. New insert location cannot overlap with any
1003 * posting list now.
1004 */
1009 }
1012 }
1014 /*
1015 * Step right to next non-dead page, during insertion.
1016 *
1017 * This is a bit more complicated than moving right in a search. We must
1018 * write-lock the target page before releasing write lock on current page;
1019 * else someone else's _bt_check_unique scan could fail to see our insertion.
1020 * Write locks on intermediate dead pages won't do because we don't know when
1021 * they will get de-linked from the tree.
1022 *
1023 * This is more aggressive than it needs to be for non-unique !heapkeyspace
1024 * indexes.
1025 */
1026 static void
1028 BTStack stack)
1029 {
1030 Page page;
1031 BTPageOpaque opaque;
1032 Buffer rbuf;
1033 BlockNumber rblkno;
1042 {
1047 /*
1048 * If this page was incompletely split, finish the split now. We do
1049 * this while holding a lock on the left sibling, which is not good
1050 * because finishing the split could be a fairly lengthy operation.
1051 * But this should happen very seldom.
1052 */
1054 {
1058 }
1067 }
1068 /* rbuf locked; unlock buf, update state for caller */
1072 }
1074 /*----------
1075 * _bt_insertonpg() -- Insert a tuple on a particular page in the index.
1076 *
1077 * This recursive procedure does the following things:
1078 *
1079 * + if postingoff != 0, splits existing posting list tuple
1080 * (since it overlaps with new 'itup' tuple).
1081 * + if necessary, splits the target page, using 'itup_key' for
1082 * suffix truncation on leaf pages (caller passes NULL for
1083 * non-leaf pages).
1084 * + inserts the new tuple (might be split from posting list).
1085 * + if the page was split, pops the parent stack, and finds the
1086 * right place to insert the new child pointer (by walking
1087 * right using information stored in the parent stack).
1088 * + invokes itself with the appropriate tuple for the right
1089 * child page on the parent.
1090 * + updates the metapage if a true root or fast root is split.
1091 *
1092 * On entry, we must have the correct buffer in which to do the
1093 * insertion, and the buffer must be pinned and write-locked. On return,
1094 * we will have dropped both the pin and the lock on the buffer.
1095 *
1096 * This routine only performs retail tuple insertions. 'itup' should
1097 * always be either a non-highkey leaf item, or a downlink (new high
1098 * key items are created indirectly, when a page is split). When
1099 * inserting to a non-leaf page, 'cbuf' is the left-sibling of the page
1100 * we're inserting the downlink for. This function will clear the
1101 * INCOMPLETE_SPLIT flag on it, and release the buffer.
1102 *----------
1103 */
1104 static void
1106 Relation heaprel,
1107 BTScanInsert itup_key,
1108 Buffer buf,
1109 Buffer cbuf,
1110 BTStack stack,
1111 IndexTuple itup,
1112 Size itemsz,
1113 OffsetNumber newitemoff,
1116 {
1117 Page page;
1118 BTPageOpaque opaque;
1120 isroot,
1121 isrightmost,
1122 isonly;
1134 /* child buffer must be given iff inserting on an internal page */
1136 /* tuple must have appropriate number of attributes */
1145 /* Caller must always finish incomplete split for us */
1148 /*
1149 * Every internal page should have exactly one negative infinity item at
1150 * all times. Only _bt_split() and _bt_newlevel() should add items that
1151 * become negative infinity items through truncation, since they're the
1152 * only routines that allocate new internal pages.
1153 */
1156 /*
1157 * Do we need to split an existing posting list item?
1158 */
1160 {
1163 /*
1164 * The new tuple is a duplicate with a heap TID that falls inside the
1165 * range of an existing posting list tuple on a leaf page. Prepare to
1166 * split an existing posting list. Overwriting the posting list with
1167 * its post-split version is treated as an extra step in either the
1168 * insert or page split critical section.
1169 */
1173 /*
1174 * postingoff value comes from earlier call to _bt_binsrch_posting().
1175 * Its binary search might think that a plain tuple must be a posting
1176 * list tuple that needs to be split. This can happen with corruption
1177 * involving an existing plain tuple that is a duplicate of the new
1178 * item, up to and including its table TID. Check for that here in
1179 * passing.
1180 *
1181 * Also verify that our caller has made sure that the existing posting
1182 * list tuple does not have its LP_DEAD bit set.
1183 */
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\"",
1193 /* use a mutable copy of itup as our itup from here on */
1197 /* itup now contains rightmost/max TID from oposting */
1199 /* Alter offset so that newitem goes after posting list */
1201 }
1203 /*
1204 * Do we need to split the page to fit the item on it?
1205 *
1206 * Note: PageGetFreeSpace() subtracts sizeof(ItemIdData) from its result,
1207 * so this comparison is correct even though we appear to be accounting
1208 * only for the item and not for its line pointer.
1209 */
1211 {
1212 Buffer rbuf;
1216 /* split the buffer into left and right halves */
1223 /*----------
1224 * By here,
1225 *
1226 * + our target page has been split;
1227 * + the original tuple has been inserted;
1228 * + we have write locks on both the old (left half)
1229 * and new (right half) buffers, after the split; and
1230 * + we know the key we want to insert into the parent
1231 * (it's the "high key" on the left child page).
1232 *
1233 * We're ready to do the parent insertion. We need to hold onto the
1234 * locks for the child pages until we locate the parent, but we can
1235 * at least release the lock on the right child before doing the
1236 * actual insertion. The lock on the left child will be released
1237 * last of all by parent insertion, where it is the 'cbuf' of parent
1238 * page.
1239 *----------
1240 */
1242 }
1243 else
1244 {
1248 BlockNumber blockcache;
1250 /*
1251 * If we are doing this insert because we split a page that was the
1252 * only one on its tree level, but was not the root, it may have been
1253 * the "fast root". We need to ensure that the fast root link points
1254 * at or above the current page. We can safely acquire a lock on the
1255 * metapage here --- see comments for _bt_newlevel().
1256 */
1258 {
1267 {
1268 /* no update wanted */
1271 }
1272 }
1274 /* Do the update. No ereport(ERROR) until changes are logged */
1288 {
1289 /* upgrade meta-page if needed */
1295 }
1297 /*
1298 * Clear INCOMPLETE_SPLIT flag on child if inserting the new item
1299 * finishes a split
1300 */
1302 {
1309 }
1311 /* XLOG stuff */
1313 {
1314 xl_btree_insert xlrec;
1315 xl_btree_metadata xlmeta;
1316 uint8 xlinfo;
1317 XLogRecPtr recptr;
1318 uint16 upostingoff;
1326 {
1327 /* Simple leaf insert */
1329 }
1331 {
1332 /*
1333 * Leaf insert with posting list split. Must include
1334 * postingoff field before newitem/orignewitem.
1335 */
1338 }
1339 else
1340 {
1341 /* Internal page insert, which finishes a split on cbuf */
1346 {
1347 /* Actually, it's an internal page insert + meta update */
1363 }
1364 }
1368 {
1369 /* Just log itup from caller */
1371 }
1372 else
1373 {
1374 /*
1375 * Insert with posting list split (XLOG_BTREE_INSERT_POST
1376 * record) case.
1377 *
1378 * Log postingoff. Also log origitup, not itup. REDO routine
1379 * must reconstruct final itup (as well as nposting) using
1380 * _bt_swap_posting().
1381 */
1387 }
1397 }
1401 /* Release subsidiary buffers */
1407 /*
1408 * Cache the block number if this is the rightmost leaf page. Cache
1409 * may be used by a future inserter within _bt_search_insert().
1410 */
1415 /* Release buffer for insertion target block */
1418 /*
1419 * If we decided to cache the insertion target block before releasing
1420 * its buffer lock, then cache it now. Check the height of the tree
1421 * first, though. We don't go for the optimization with small
1422 * indexes. Defer final check to this point to ensure that we don't
1423 * call _bt_getrootheight while holding a buffer lock.
1424 */
1428 }
1430 /* be tidy */
1432 {
1433 /* itup is actually a modified copy of caller's original */
1436 }
1437 }
1439 /*
1440 * _bt_split() -- split a page in the btree.
1441 *
1442 * On entry, buf is the page to split, and is pinned and write-locked.
1443 * newitemoff etc. tell us about the new item that must be inserted
1444 * along with the data from the original page.
1445 *
1446 * itup_key is used for suffix truncation on leaf pages (internal
1447 * page callers pass NULL). When splitting a non-leaf page, 'cbuf'
1448 * is the left-sibling of the page we're inserting the downlink for.
1449 * This function will clear the INCOMPLETE_SPLIT flag on it, and
1450 * release the buffer.
1451 *
1452 * orignewitem, nposting, and postingoff are needed when an insert of
1453 * orignewitem results in both a posting list split and a page split.
1454 * These extra posting list split details are used here in the same
1455 * way as they are used in the more common case where a posting list
1456 * split does not coincide with a page split. We need to deal with
1457 * posting list splits directly in order to ensure that everything
1458 * that follows from the insert of orignewitem is handled as a single
1459 * atomic operation (though caller's insert of a new pivot/downlink
1460 * into parent page will still be a separate operation). See
1461 * nbtree/README for details on the design of posting list splits.
1462 *
1463 * Returns the new right sibling of buf, pinned and write-locked.
1464 * The pin and lock on buf are maintained.
1465 */
1466 static Buffer
1470 {
1471 Buffer rbuf;
1472 Page origpage;
1473 Page leftpage,
1474 rightpage;
1475 BlockNumber origpagenumber,
1476 rightpagenumber;
1477 BTPageOpaque ropaque,
1478 lopaque,
1479 oopaque;
1483 Size itemsz;
1484 ItemId itemid;
1485 IndexTuple firstright,
1486 lefthighkey;
1487 OffsetNumber firstrightoff;
1488 OffsetNumber afterleftoff,
1489 afterrightoff,
1490 minusinfoff;
1491 OffsetNumber origpagepostingoff;
1492 OffsetNumber maxoff;
1493 OffsetNumber i;
1495 isleaf,
1496 isrightmost;
1498 /*
1499 * origpage is the original page to be split. leftpage is a temporary
1500 * buffer that receives the left-sibling data, which will be copied back
1501 * into origpage on success. rightpage is the new page that will receive
1502 * the right-sibling data.
1503 *
1504 * leftpage is allocated after choosing a split point. rightpage's new
1505 * buffer isn't acquired until after leftpage is initialized and has new
1506 * high key, the last point where splitting the page may fail (barring
1507 * corruption). Failing before acquiring new buffer won't have lasting
1508 * consequences, since origpage won't have been modified and leftpage is
1509 * only workspace.
1510 */
1518 /*
1519 * Choose a point to split origpage at.
1520 *
1521 * A split point can be thought of as a point _between_ two existing data
1522 * items on origpage (the lastleft and firstright tuples), provided you
1523 * pretend that the new item that didn't fit is already on origpage.
1524 *
1525 * Since origpage does not actually contain newitem, the representation of
1526 * split points needs to work with two boundary cases: splits where
1527 * newitem is lastleft, and splits where newitem is firstright.
1528 * newitemonleft resolves the ambiguity that would otherwise exist when
1529 * newitemoff == firstrightoff. In all other cases it's clear which side
1530 * of the split every tuple goes on from context. newitemonleft is
1531 * usually (but not always) redundant information.
1532 *
1533 * firstrightoff is supposed to be an origpage offset number, but it's
1534 * possible that its value will be maxoff+1, which is "past the end" of
1535 * origpage. This happens in the rare case where newitem goes after all
1536 * existing items (i.e. newitemoff is maxoff+1) and we end up splitting
1537 * origpage at the point that leaves newitem alone on new right page. Any
1538 * "!newitemonleft && newitemoff == firstrightoff" split point makes
1539 * newitem the firstright tuple, though, so this case isn't a special
1540 * case.
1541 */
1545 /* Allocate temp buffer for leftpage */
1550 /*
1551 * leftpage won't be the root when we're done. Also, clear the SPLIT_END
1552 * and HAS_GARBAGE flags.
1553 */
1556 /* set flag in leftpage indicating that rightpage has no downlink yet */
1559 /* handle btpo_next after rightpage buffer acquired */
1561 /* handle btpo_cycleid after rightpage buffer acquired */
1563 /*
1564 * Copy the original page's LSN into leftpage, which will become the
1565 * updated version of the page. We need this because XLogInsert will
1566 * examine the LSN and possibly dump it in a page image.
1567 */
1570 /*
1571 * Determine page offset number of existing overlapped-with-orignewitem
1572 * posting list when it is necessary to perform a posting list split in
1573 * passing. Note that newitem was already changed by caller (newitem no
1574 * longer has the orignewitem TID).
1575 *
1576 * This page offset number (origpagepostingoff) will be used to pretend
1577 * that the posting split has already taken place, even though the
1578 * required modifications to origpage won't occur until we reach the
1579 * critical section. The lastleft and firstright tuples of our page split
1580 * point should, in effect, come from an imaginary version of origpage
1581 * that has the nposting tuple instead of the original posting list tuple.
1582 *
1583 * Note: _bt_findsplitloc() should have compensated for coinciding posting
1584 * list splits in just the same way, at least in theory. It doesn't
1585 * bother with that, though. In practice it won't affect its choice of
1586 * split point.
1587 */
1590 {
1596 }
1598 /*
1599 * The high key for the new left page is a possibly-truncated copy of
1600 * firstright on the leaf level (it's "firstright itself" on internal
1601 * pages; see !isleaf comments below). This may seem to be contrary to
1602 * Lehman & Yao's approach of using a copy of lastleft as the new high key
1603 * when splitting on the leaf level. It isn't, though.
1604 *
1605 * Suffix truncation will leave the left page's high key fully equal to
1606 * lastleft when lastleft and firstright are equal prior to heap TID (that
1607 * is, the tiebreaker TID value comes from lastleft). It isn't actually
1608 * necessary for a new leaf high key to be a copy of lastleft for the L&Y
1609 * "subtree" invariant to hold. It's sufficient to make sure that the new
1610 * leaf high key is strictly less than firstright, and greater than or
1611 * equal to (not necessarily equal to) lastleft. In other words, when
1612 * suffix truncation isn't possible during a leaf page split, we take
1613 * L&Y's exact approach to generating a new high key for the left page.
1614 * (Actually, that is slightly inaccurate. We don't just use a copy of
1615 * lastleft. A tuple with all the keys from firstright but the max heap
1616 * TID from lastleft is used, to avoid introducing a special case.)
1617 */
1619 {
1620 /* incoming tuple becomes firstright */
1623 }
1624 else
1625 {
1626 /* existing item at firstrightoff becomes firstright */
1632 }
1635 {
1636 IndexTuple lastleft;
1638 /* Attempt suffix truncation for leaf page splits */
1640 {
1641 /* incoming tuple becomes lastleft */
1643 }
1644 else
1645 {
1646 OffsetNumber lastleftoff;
1648 /* existing item before firstrightoff becomes lastleft */
1655 }
1659 }
1660 else
1661 {
1662 /*
1663 * Don't perform suffix truncation on a copy of firstright to make
1664 * left page high key for internal page splits. Must use firstright
1665 * as new high key directly.
1666 *
1667 * Each distinct separator key value originates as a leaf level high
1668 * key; all other separator keys/pivot tuples are copied from one
1669 * level down. A separator key in a grandparent page must be
1670 * identical to high key in rightmost parent page of the subtree to
1671 * its left, which must itself be identical to high key in rightmost
1672 * child page of that same subtree (this even applies to separator
1673 * from grandparent's high key). There must always be an unbroken
1674 * "seam" of identical separator keys that guide index scans at every
1675 * level, starting from the grandparent. That's why suffix truncation
1676 * is unsafe here.
1677 *
1678 * Internal page splits will truncate firstright into a "negative
1679 * infinity" data item when it gets inserted on the new right page
1680 * below, though. This happens during the call to _bt_pgaddtup() for
1681 * the new first data item for right page. Do not confuse this
1682 * mechanism with suffix truncation. It is just a convenient way of
1683 * implementing page splits that split the internal page "inside"
1684 * firstright. The lefthighkey separator key cannot appear a second
1685 * time in the right page (only firstright's downlink goes in right
1686 * page).
1687 */
1689 }
1691 /*
1692 * Add new high key to leftpage
1693 */
1707 /*
1708 * Acquire a new right page to split into, now that left page has a new
1709 * high key. From here on, it's not okay to throw an error without
1710 * zeroing rightpage first. This coding rule ensures that we won't
1711 * confuse future VACUUM operations, which might otherwise try to re-find
1712 * a downlink to a leftover junk page as the page undergoes deletion.
1713 *
1714 * It would be reasonable to start the critical section just after the new
1715 * rightpage buffer is acquired instead; that would allow us to avoid
1716 * leftover junk pages without bothering to zero rightpage. We do it this
1717 * way because it avoids an unnecessary PANIC when either origpage or its
1718 * existing sibling page are corrupt.
1719 */
1723 /* rightpage was initialized by _bt_getbuf */
1726 /*
1727 * Finish off remaining leftpage special area fields. They cannot be set
1728 * before both origpage (leftpage) and rightpage buffers are acquired and
1729 * locked.
1730 *
1731 * btpo_cycleid is only used with leaf pages, though we set it here in all
1732 * cases just to be consistent.
1733 */
1737 /*
1738 * rightpage won't be the root when we're done. Also, clear the SPLIT_END
1739 * and HAS_GARBAGE flags.
1740 */
1748 /*
1749 * Add new high key to rightpage where necessary.
1750 *
1751 * If the page we're splitting is not the rightmost page at its level in
1752 * the tree, then the first entry on the page is the high key from
1753 * origpage.
1754 */
1758 {
1759 IndexTuple righthighkey;
1769 {
1774 }
1776 }
1778 /*
1779 * Internal page splits truncate first data item on right page -- it
1780 * becomes "minus infinity" item for the page. Set this up here.
1781 */
1786 /*
1787 * Now transfer all the data items (non-pivot tuples in isleaf case, or
1788 * additional pivot tuples in !isleaf case) to the appropriate page.
1789 *
1790 * Note: we *must* insert at least the right page's items in item-number
1791 * order, for the benefit of _bt_restore_page().
1792 */
1794 {
1795 IndexTuple dataitem;
1801 /* replace original item with nposting due to posting split? */
1803 {
1807 }
1809 /* does new item belong before this one? */
1811 {
1813 {
1817 {
1822 }
1824 }
1825 else
1826 {
1830 {
1835 }
1837 }
1838 }
1840 /* decide which page to put it on */
1842 {
1844 {
1849 }
1851 }
1852 else
1853 {
1856 {
1861 }
1863 }
1864 }
1866 /* Handle case where newitem goes at the end of rightpage */
1868 {
1869 /*
1870 * Can't have newitemonleft here; that would imply we were told to put
1871 * *everything* on the left page, which cannot fit (if it could, we'd
1872 * not be splitting the page).
1873 */
1877 {
1882 }
1884 }
1886 /*
1887 * We have to grab the original right sibling (if any) and update its prev
1888 * link. We are guaranteed that this is deadlock-free, since we couple
1889 * the locks in the standard order: left to right.
1890 */
1892 {
1897 {
1905 }
1907 /*
1908 * Check to see if we can set the SPLIT_END flag in the right-hand
1909 * split page; this can save some I/O for vacuum since it need not
1910 * proceed to the right sibling. We can set the flag if the right
1911 * sibling has a different cycleid: that means it could not be part of
1912 * a group of pages that were all split off from the same ancestor
1913 * page. If you're confused, imagine that page A splits to A B and
1914 * then again, yielding A C B, while vacuum is in progress. Tuples
1915 * originally in A could now be in either B or C, hence vacuum must
1916 * examine both pages. But if D, our right sibling, has a different
1917 * cycleid then it could not contain any tuples that were in A when
1918 * the vacuum started.
1919 */
1922 }
1924 /*
1925 * Right sibling is locked, new siblings are prepared, but original page
1926 * is not updated yet.
1927 *
1928 * NO EREPORT(ERROR) till right sibling is updated. We can get away with
1929 * not starting the critical section till here because we haven't been
1930 * scribbling on the original page yet; see comments above.
1931 */
1934 /*
1935 * By here, the original data page has been split into two new halves, and
1936 * these are correct. The algorithm requires that the left page never
1937 * move during a split, so we copy the new left page back on top of the
1938 * original. We need to do this before writing the WAL record, so that
1939 * XLogInsert can WAL log an image of the page if necessary.
1940 */
1942 /* leftpage, lopaque must not be used below here */
1948 {
1951 }
1953 /*
1954 * Clear INCOMPLETE_SPLIT flag on child if inserting the new item finishes
1955 * a split
1956 */
1958 {
1964 }
1966 /* XLOG stuff */
1968 {
1969 xl_btree_split xlrec;
1970 uint8 xlinfo;
1971 XLogRecPtr recptr;
1974 /* See comments below on newitem, orignewitem, and posting lists */
1986 /* Log original right sibling, since we've changed its prev-pointer */
1992 /*
1993 * Log the new item, if it was inserted on the left page. (If it was
1994 * put on the right page, we don't need to explicitly WAL log it
1995 * because it's included with all the other items on the right page.)
1996 * Show the new item as belonging to the left page buffer, so that it
1997 * is not stored if XLogInsert decides it needs a full-page image of
1998 * the left page. We always store newitemoff in the record, though.
1999 *
2000 * The details are sometimes slightly different for page splits that
2001 * coincide with a posting list split. If both the replacement
2002 * posting list and newitem go on the right page, then we don't need
2003 * to log anything extra, just like the simple !newitemonleft
2004 * no-posting-split case (postingoff is set to zero in the WAL record,
2005 * so recovery doesn't need to process a posting list split at all).
2006 * Otherwise, we set postingoff and log orignewitem instead of
2007 * newitem, despite having actually inserted newitem. REDO routine
2008 * must reconstruct nposting and newitem using _bt_swap_posting().
2009 *
2010 * Note: It's possible that our page split point is the point that
2011 * makes the posting list lastleft and newitem firstright. This is
2012 * the only case where we log orignewitem/newitem despite newitem
2013 * going on the right page. If XLogInsert decides that it can omit
2014 * orignewitem due to logging a full-page image of the left page,
2015 * everything still works out, since recovery only needs to log
2016 * orignewitem for items on the left page (just like the regular
2017 * newitem-logged case).
2018 */
2022 {
2027 }
2029 /* Log the left page's new high key */
2031 {
2032 /* lefthighkey isn't local copy, get current pointer */
2035 }
2039 /*
2040 * Log the contents of the right page in the format understood by
2041 * _bt_restore_page(). The whole right page will be recreated.
2042 *
2043 * Direct access to page is not good but faster - we should implement
2044 * some new func in page API. Note we only store the tuples
2045 * themselves, knowing that they were inserted in item-number order
2046 * and so the line pointers can be reconstructed. See comments for
2047 * _bt_restore_page().
2048 */
2062 }
2066 /* release the old right sibling */
2070 /* release the child */
2074 /* be tidy */
2078 /* split's done */
2080 }
2082 /*
2083 * _bt_insert_parent() -- Insert downlink into parent, completing split.
2084 *
2085 * On entry, buf and rbuf are the left and right split pages, which we
2086 * still hold write locks on. Both locks will be released here. We
2087 * release the rbuf lock once we have a write lock on the page that we
2088 * intend to insert a downlink to rbuf on (i.e. buf's current parent page).
2089 * The lock on buf is released at the same point as the lock on the parent
2090 * page, since buf's INCOMPLETE_SPLIT flag must be cleared by the same
2091 * atomic operation that completes the split by inserting a new downlink.
2092 *
2093 * stack - stack showing how we got here. Will be NULL when splitting true
2094 * root, or during concurrent root split, where we can be inefficient
2095 * isroot - we split the true root
2096 * isonly - we split a page alone on its level (might have been fast root)
2097 */
2098 static void
2100 Relation heaprel,
2101 Buffer buf,
2102 Buffer rbuf,
2103 BTStack stack,
2106 {
2109 /*
2110 * Here we have to do something Lehman and Yao don't talk about: deal with
2111 * a root split and construction of a new root. If our stack is empty
2112 * then we have just split a node on what had been the root level when we
2113 * descended the tree. If it was still the root then we perform a
2114 * new-root construction. If it *wasn't* the root anymore, search to find
2115 * the next higher level that someone constructed meanwhile, and find the
2116 * right place to insert as for the normal case.
2117 *
2118 * If we have to search for the parent level, we do so by re-descending
2119 * from the root. This is not super-efficient, but it's rare enough not
2120 * to matter.
2121 */
2123 {
2124 Buffer rootbuf;
2128 /* create a new root node one level up and update the metapage */
2130 /* release the split buffers */
2134 }
2135 else
2136 {
2140 IndexTuple new_item;
2141 BTStackData fakestack;
2142 IndexTuple ritem;
2143 Buffer pbuf;
2146 {
2147 BTPageOpaque opaque;
2152 /*
2153 * We should never reach here when a leaf page split takes place
2154 * despite the insert of newitem being able to apply the fastpath
2155 * optimization. Make sure of that with an assertion.
2156 *
2157 * This is more of a performance issue than a correctness issue.
2158 * The fastpath won't have a descent stack. Using a phony stack
2159 * here works, but never rely on that. The fastpath should be
2160 * rejected within _bt_search_insert() when the rightmost leaf
2161 * page will split, since it's faster to go through _bt_search()
2162 * and get a stack in the usual way.
2163 */
2167 /* Find the leftmost page at the next level up */
2169 /* Set up a phony stack entry pointing there */
2175 }
2177 /* get high key from left, a strict lower bound for new right page */
2181 /* form an index tuple that points at the new right page */
2185 /*
2186 * Re-find and write lock the parent of buf.
2187 *
2188 * It's possible that the location of buf's downlink has changed since
2189 * our initial _bt_search() descent. _bt_getstackbuf() will detect
2190 * and recover from this, updating the stack, which ensures that the
2191 * new downlink will be inserted at the correct offset. Even buf's
2192 * parent may have changed.
2193 */
2196 /*
2197 * Unlock the right child. The left child will be unlocked in
2198 * _bt_insertonpg().
2199 *
2200 * Unlocking the right child must be delayed until here to ensure that
2201 * no concurrent VACUUM operation can become confused. Page deletion
2202 * cannot be allowed to fail to re-find a downlink for the rbuf page.
2203 * (Actually, this is just a vestige of how things used to work. The
2204 * page deletion code is expected to check for the INCOMPLETE_SPLIT
2205 * flag on the left child. It won't attempt deletion of the right
2206 * child until the split is complete. Despite all this, we opt to
2207 * conservatively delay unlocking the right child until here.)
2208 */
2217 /* Recursively insert into the parent */
2222 /* be tidy */
2224 }
2225 }
2227 /*
2228 * _bt_finish_split() -- Finish an incomplete split
2229 *
2230 * A crash or other failure can leave a split incomplete. The insertion
2231 * routines won't allow to insert on a page that is incompletely split.
2232 * Before inserting on such a page, call _bt_finish_split().
2233 *
2234 * On entry, 'lbuf' must be locked in write-mode. On exit, it is unlocked
2235 * and unpinned.
2236 *
2237 * Caller must provide a valid heaprel, since finishing a page split requires
2238 * allocating a new page if and when the parent page splits in turn.
2239 */
2240 void
2242 {
2245 Buffer rbuf;
2246 Page rpage;
2247 BTPageOpaque rpageop;
2254 /* Lock right sibling, the one missing the downlink */
2259 /* Could this be a root split? */
2261 {
2262 Buffer metabuf;
2263 Page metapg;
2266 /* acquire lock on the metapage */
2274 }
2275 else
2278 /* Was this the only page on the level before split? */
2285 }
2287 /*
2288 * _bt_getstackbuf() -- Walk back up the tree one step, and find the pivot
2289 * tuple whose downlink points to child page.
2290 *
2291 * Caller passes child's block number, which is used to identify
2292 * associated pivot tuple in parent page using a linear search that
2293 * matches on pivot's downlink/block number. The expected location of
2294 * the pivot tuple is taken from the stack one level above the child
2295 * page. This is used as a starting point. Insertions into the
2296 * parent level could cause the pivot tuple to move right; deletions
2297 * could cause it to move left, but not left of the page we previously
2298 * found it on.
2299 *
2300 * Caller can use its stack to relocate the pivot tuple/downlink for
2301 * any same-level page to the right of the page found by its initial
2302 * descent. This is necessary because of the possibility that caller
2303 * moved right to recover from a concurrent page split. It's also
2304 * convenient for certain callers to be able to step right when there
2305 * wasn't a concurrent page split, while still using their original
2306 * stack. For example, the checkingunique _bt_doinsert() case may
2307 * have to step right when there are many physical duplicates, and its
2308 * scantid forces an insertion to the right of the "first page the
2309 * value could be on". (This is also relied on by all of our callers
2310 * when dealing with !heapkeyspace indexes.)
2311 *
2312 * Returns write-locked parent page buffer, or InvalidBuffer if pivot
2313 * tuple not found (should not happen). Adjusts bts_blkno &
2314 * bts_offset if changed. Page split caller should insert its new
2315 * pivot tuple for its new right sibling page on parent page, at the
2316 * offset number bts_offset + 1.
2317 */
2318 Buffer
2320 {
2321 BlockNumber blkno;
2322 OffsetNumber start;
2328 {
2329 Buffer buf;
2330 Page page;
2331 BTPageOpaque opaque;
2339 {
2342 }
2345 {
2346 OffsetNumber offnum,
2347 minoff,
2348 maxoff;
2349 ItemId itemid;
2350 IndexTuple item;
2355 /*
2356 * start = InvalidOffsetNumber means "search the whole page". We
2357 * need this test anyway due to possibility that page has a high
2358 * key now when it didn't before.
2359 */
2363 /*
2364 * Need this check too, to guard against possibility that page
2365 * split since we visited it originally.
2366 */
2370 /*
2371 * These loops will check every item on the page --- but in an
2372 * order that's attuned to the probability of where it actually
2373 * is. Scan to the right first, then to the left.
2374 */
2378 {
2383 {
2384 /* Return accurate pointer to where link is now */
2388 }
2389 }
2394 {
2399 {
2400 /* Return accurate pointer to where link is now */
2404 }
2405 }
2406 }
2408 /*
2409 * The item we're looking for moved right at least one page.
2410 *
2411 * Lehman and Yao couple/chain locks when moving right here, which we
2412 * can avoid. See nbtree/README.
2413 */
2415 {
2418 }
2422 }
2423 }
2425 /*
2426 * _bt_newlevel() -- Create a new level above root page.
2427 *
2428 * We've just split the old root page and need to create a new one.
2429 * In order to do this, we add a new root page to the file, then lock
2430 * the metadata page and update it. This is guaranteed to be deadlock-
2431 * free, because all readers release their locks on the metadata page
2432 * before trying to lock the root, and all writers lock the root before
2433 * trying to lock the metadata page. We have a write lock on the old
2434 * root page, so we have not introduced any cycles into the waits-for
2435 * graph.
2436 *
2437 * On entry, lbuf (the old root) and rbuf (its new peer) are write-
2438 * locked. On exit, a new root page exists with entries for the
2439 * two new children, metapage is updated and unlocked/unpinned.
2440 * The new root buffer is returned to caller which has to unlock/unpin
2441 * lbuf, rbuf & rootbuf.
2442 */
2443 static Buffer
2445 {
2446 Buffer rootbuf;
2447 Page lpage,
2448 rootpage;
2449 BlockNumber lbkno,
2450 rbkno;
2451 BlockNumber rootblknum;
2452 BTPageOpaque rootopaque;
2453 BTPageOpaque lopaque;
2454 ItemId itemid;
2455 IndexTuple item;
2456 IndexTuple left_item;
2457 Size left_item_sz;
2458 IndexTuple right_item;
2459 Size right_item_sz;
2460 Buffer metabuf;
2461 Page metapg;
2469 /* get a new root page */
2474 /* acquire lock on the metapage */
2479 /*
2480 * Create downlink item for left page (old root). The key value used is
2481 * "minus infinity", a sentinel value that's reliably less than any real
2482 * key value that could appear in the left page.
2483 */
2490 /*
2491 * Create downlink item for right page. The key for it is obtained from
2492 * the "high key" position in the left page.
2493 */
2500 /* NO EREPORT(ERROR) from here till newroot op is logged */
2503 /* upgrade metapage if needed */
2507 /* set btree special data */
2515 /* update metapage data */
2521 /*
2522 * Insert the left page pointer into the new root page. The root page is
2523 * the rightmost page on its level so there is no "high key" in it; the
2524 * two items will go into positions P_HIKEY and P_FIRSTKEY.
2525 *
2526 * Note: we *must* insert the two items in item-number order, for the
2527 * benefit of _bt_restore_page().
2528 */
2536 /*
2537 * insert the right page pointer into the new root page.
2538 */
2548 /* Clear the incomplete-split flag in the left child */
2556 /* XLOG stuff */
2558 {
2559 xl_btree_newroot xlrec;
2560 XLogRecPtr recptr;
2561 xl_btree_metadata md;
2584 /*
2585 * Direct access to page is not good but faster - we should implement
2586 * some new func in page API.
2587 */
2598 }
2602 /* done with metapage */
2609 }
2611 /*
2612 * _bt_pgaddtup() -- add a data item to a particular page during split.
2613 *
2614 * The difference between this routine and a bare PageAddItem call is
2615 * that this code can deal with the first data item on an internal btree
2616 * page in passing. This data item (which is called "firstright" within
2617 * _bt_split()) has a key that must be treated as minus infinity after
2618 * the split. Therefore, we truncate away all attributes when caller
2619 * specifies it's the first data item on page (downlink is not changed,
2620 * though). This extra step is only needed for the right page of an
2621 * internal page split. There is no need to do this for the first data
2622 * item on the existing/left page, since that will already have been
2623 * truncated during an earlier page split.
2624 *
2625 * See _bt_split() for a high level explanation of why we truncate here.
2626 * Note that this routine has nothing to do with suffix truncation,
2627 * despite using some of the same infrastructure.
2628 */
2631 Size itemsize,
2632 IndexTuple itup,
2633 OffsetNumber itup_off,
2635 {
2636 IndexTupleData trunctuple;
2639 {
2645 }
2652 }
2654 /*
2655 * _bt_delete_or_dedup_one_page - Try to avoid a leaf page split.
2656 *
2657 * There are three operations performed here: simple index deletion, bottom-up
2658 * index deletion, and deduplication. If all three operations fail to free
2659 * enough space for the incoming item then caller will go on to split the
2660 * page. We always consider simple deletion first. If that doesn't work out
2661 * we consider alternatives. Callers that only want us to consider simple
2662 * deletion (without any fallback) ask for that using the 'simpleonly'
2663 * argument.
2664 *
2665 * We usually pick only one alternative "complex" operation when simple
2666 * deletion alone won't prevent a page split. The 'checkingunique',
2667 * 'uniquedup', and 'indexUnchanged' arguments are used for that.
2668 *
2669 * Note: We used to only delete LP_DEAD items when the BTP_HAS_GARBAGE page
2670 * level flag was found set. The flag was useful back when there wasn't
2671 * necessarily one single page for a duplicate tuple to go on (before heap TID
2672 * became a part of the key space in version 4 indexes). But we don't
2673 * actually look at the flag anymore (it's not a gating condition for our
2674 * caller). That would cause us to miss tuples that are safe to delete,
2675 * without getting any benefit in return. We know that the alternative is to
2676 * split the page; scanning the line pointer array in passing won't have
2677 * noticeable overhead. (We still maintain the BTP_HAS_GARBAGE flag despite
2678 * all this because !heapkeyspace indexes must still do a "getting tired"
2679 * linear search, and so are likely to get some benefit from using it as a
2680 * gating condition.)
2681 */
2682 static void
2684 BTInsertState insertstate,
2687 {
2690 OffsetNumber offnum,
2691 minoff,
2692 maxoff;
2702 /*
2703 * Scan over all items to see which ones need to be deleted according to
2704 * LP_DEAD flags. We'll usually manage to delete a few extra items that
2705 * are not marked LP_DEAD in passing. Often the extra items that actually
2706 * end up getting deleted are items that would have had their LP_DEAD bit
2707 * set before long anyway (if we opted not to include them as extras).
2708 */
2714 {
2719 }
2722 {
2727 /* Return when a page split has already been avoided */
2731 /* Might as well assume duplicates (if checkingunique) */
2733 }
2735 /*
2736 * We're done with simple deletion. Return early with callers that only
2737 * call here so that simple deletion can be considered. This includes
2738 * callers that explicitly ask for this and checkingunique callers that
2739 * probably don't have any version churn duplicates on the page.
2740 *
2741 * Note: The page's BTP_HAS_GARBAGE hint flag may still be set when we
2742 * return at this point (or when we go on the try either or both of our
2743 * other strategies and they also fail). We do not bother expending a
2744 * separate write to clear it, however. Caller will definitely clear it
2745 * when it goes on to split the page (note also that the deduplication
2746 * process will clear the flag in passing, just to keep things tidy).
2747 */
2749 {
2752 }
2754 /* Assume bounds about to be invalidated (this is almost certain now) */
2757 /*
2758 * Perform bottom-up index deletion pass when executor hint indicated that
2759 * incoming item is logically unchanged, or for a unique index that is
2760 * known to have physical duplicates for some other reason. (There is a
2761 * large overlap between these two cases for a unique index. It's worth
2762 * having both triggering conditions in order to apply the optimization in
2763 * the event of successive related INSERT and DELETE statements.)
2764 *
2765 * We'll go on to do a deduplication pass when a bottom-up pass fails to
2766 * delete an acceptable amount of free space (a significant fraction of
2767 * the page, or space for the new item, whichever is greater).
2768 *
2769 * Note: Bottom-up index deletion uses the same equality/equivalence
2770 * routines as deduplication internally. However, it does not merge
2771 * together index tuples, so the same correctness considerations do not
2772 * apply. We deliberately omit an index-is-allequalimage test here.
2773 */
2778 /* Perform deduplication pass (when enabled and index-is-allequalimage) */
2782 }
2784 /*
2785 * _bt_simpledel_pass - Simple index tuple deletion pass.
2786 *
2787 * We delete all LP_DEAD-set index tuples on a leaf page. The offset numbers
2788 * of all such tuples are determined by caller (caller passes these to us as
2789 * its 'deletable' argument).
2790 *
2791 * We might also delete extra index tuples that turn out to be safe to delete
2792 * in passing (though they must be cheap to check in passing to begin with).
2793 * There is no certainty that any extra tuples will be deleted, though. The
2794 * high level goal of the approach we take is to get the most out of each call
2795 * here (without noticeably increasing the per-call overhead compared to what
2796 * we need to do just to be able to delete the page's LP_DEAD-marked index
2797 * tuples).
2798 *
2799 * The number of extra index tuples that turn out to be deletable might
2800 * greatly exceed the number of LP_DEAD-marked index tuples due to various
2801 * locality related effects. For example, it's possible that the total number
2802 * of table blocks (pointed to by all TIDs on the leaf page) is naturally
2803 * quite low, in which case we might end up checking if it's possible to
2804 * delete _most_ index tuples on the page (without the tableam needing to
2805 * access additional table blocks). The tableam will sometimes stumble upon
2806 * _many_ extra deletable index tuples in indexes where this pattern is
2807 * common.
2808 *
2809 * See nbtree/README for further details on simple index tuple deletion.
2810 */
2811 static void
2815 {
2819 TM_IndexDeleteOp delstate;
2820 OffsetNumber offnum;
2822 /* Get array of table blocks pointed to by LP_DEAD-set tuples */
2826 /* Initialize tableam state that describes index deletion operation */
2838 {
2843 BlockNumber tidblock;
2847 {
2853 {
2856 }
2858 /*
2859 * TID's table block is among those pointed to by the TIDs from
2860 * LP_DEAD-bit set tuples on page -- add TID to deltids
2861 */
2870 }
2871 else
2872 {
2876 {
2884 {
2887 }
2889 /*
2890 * TID's table block is among those pointed to by the TIDs
2891 * from LP_DEAD-bit set tuples on page -- add TID to deltids
2892 */
2900 odeltid++;
2901 ostatus++;
2903 }
2904 }
2905 }
2911 /* Physically delete LP_DEAD tuples (plus any delete-safe extra TIDs) */
2916 }
2918 /*
2919 * _bt_deadblocks() -- Get LP_DEAD related table blocks.
2920 *
2921 * Builds sorted and unique-ified array of table block numbers from index
2922 * tuple TIDs whose line pointers are marked LP_DEAD. Also adds the table
2923 * block from incoming newitem just in case it isn't among the LP_DEAD-related
2924 * table blocks.
2925 *
2926 * Always counting the newitem's table block as an LP_DEAD related block makes
2927 * sense because the cost is consistently low; it is practically certain that
2928 * the table block will not incur a buffer miss in tableam. On the other hand
2929 * the benefit is often quite high. There is a decent chance that there will
2930 * be some deletable items from this block, since in general most garbage
2931 * tuples became garbage in the recent past (in many cases this won't be the
2932 * first logical row that core code added to/modified in table block
2933 * recently).
2934 *
2935 * Returns final array, and sets *nblocks to its final size for caller.
2936 */
2940 {
2942 ntids;
2945 /*
2946 * Accumulate each TID's block in array whose initial size has space for
2947 * one table block per LP_DEAD-set tuple (plus space for the newitem table
2948 * block). Array will only need to grow when there are LP_DEAD-marked
2949 * posting list tuples (which is not that common).
2950 */
2955 /*
2956 * First add the table block for the incoming newitem. This is the one
2957 * case where simple deletion can visit a table block that doesn't have
2958 * any known deletable items.
2959 */
2964 {
2971 {
2973 {
2977 }
2980 }
2981 else
2982 {
2986 {
2990 }
2993 {
2997 }
2998 }
2999 }
3005 }
3007 /*
3008 * _bt_blk_cmp() -- qsort comparison function for _bt_simpledel_pass
3009 */
3012 {
3022 }