Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * nbtinsert.c
4 : : * Item insertion in Lehman and Yao btrees for Postgres.
5 : : *
6 : : * Portions Copyright (c) 1996-2026, 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 : : */
15 : :
16 : : #include "postgres.h"
17 : :
18 : : #include "access/nbtree.h"
19 : : #include "access/nbtxlog.h"
20 : : #include "access/tableam.h"
21 : : #include "access/transam.h"
22 : : #include "access/xloginsert.h"
23 : : #include "common/int.h"
24 : : #include "common/pg_prng.h"
25 : : #include "lib/qunique.h"
26 : : #include "miscadmin.h"
27 : : #include "storage/lmgr.h"
28 : : #include "storage/predicate.h"
29 : : #include "utils/injection_point.h"
30 : :
31 : : /* Minimum tree height for application of fastpath optimization */
32 : : #define BTREE_FASTPATH_MIN_LEVEL 2
33 : :
34 : :
35 : : static BTStack _bt_search_insert(Relation rel, Relation heaprel,
36 : : BTInsertState insertstate);
37 : : static TransactionId _bt_check_unique(Relation rel, BTInsertState insertstate,
38 : : Relation heapRel,
39 : : IndexUniqueCheck checkUnique, bool *is_unique,
40 : : uint32 *speculativeToken);
41 : : static OffsetNumber _bt_findinsertloc(Relation rel,
42 : : BTInsertState insertstate,
43 : : bool checkingunique,
44 : : bool indexUnchanged,
45 : : BTStack stack,
46 : : Relation heapRel);
47 : : static void _bt_stepright(Relation rel, Relation heaprel,
48 : : BTInsertState insertstate, BTStack stack);
49 : : static void _bt_insertonpg(Relation rel, Relation heaprel, BTScanInsert itup_key,
50 : : Buffer buf,
51 : : Buffer cbuf,
52 : : BTStack stack,
53 : : IndexTuple itup,
54 : : Size itemsz,
55 : : OffsetNumber newitemoff,
56 : : int postingoff,
57 : : bool split_only_page);
58 : : static Buffer _bt_split(Relation rel, Relation heaprel, BTScanInsert itup_key,
59 : : Buffer buf, Buffer cbuf, OffsetNumber newitemoff,
60 : : Size newitemsz, IndexTuple newitem, IndexTuple orignewitem,
61 : : IndexTuple nposting, uint16 postingoff);
62 : : static void _bt_insert_parent(Relation rel, Relation heaprel, Buffer buf,
63 : : Buffer rbuf, BTStack stack, bool isroot, bool isonly);
64 : : static void _bt_freestack(BTStack stack);
65 : : static Buffer _bt_newlevel(Relation rel, Relation heaprel, Buffer lbuf, Buffer rbuf);
66 : : static inline bool _bt_pgaddtup(Page page, Size itemsize, const IndexTupleData *itup,
67 : : OffsetNumber itup_off, bool newfirstdataitem);
68 : : static void _bt_delete_or_dedup_one_page(Relation rel, Relation heapRel,
69 : : BTInsertState insertstate,
70 : : bool simpleonly, bool checkingunique,
71 : : bool uniquedup, bool indexUnchanged);
72 : : static void _bt_simpledel_pass(Relation rel, Buffer buffer, Relation heapRel,
73 : : OffsetNumber *deletable, int ndeletable,
74 : : IndexTuple newitem, OffsetNumber minoff,
75 : : OffsetNumber maxoff);
76 : : static BlockNumber *_bt_deadblocks(Page page, OffsetNumber *deletable,
77 : : int ndeletable, IndexTuple newitem,
78 : : int *nblocks);
79 : : static inline int _bt_blk_cmp(const void *arg1, const void *arg2);
80 : :
81 : : /*
82 : : * _bt_doinsert() -- Handle insertion of a single index tuple in the tree.
83 : : *
84 : : * This routine is called by the public interface routine, btinsert.
85 : : * By here, itup is filled in, including the TID.
86 : : *
87 : : * If checkUnique is UNIQUE_CHECK_NO or UNIQUE_CHECK_PARTIAL, this
88 : : * will allow duplicates. Otherwise (UNIQUE_CHECK_YES or
89 : : * UNIQUE_CHECK_EXISTING) it will throw error for a duplicate.
90 : : * For UNIQUE_CHECK_EXISTING we merely run the duplicate check, and
91 : : * don't actually insert.
92 : : *
93 : : * indexUnchanged executor hint indicates if itup is from an
94 : : * UPDATE that didn't logically change the indexed value, but
95 : : * must nevertheless have a new entry to point to a successor
96 : : * version.
97 : : *
98 : : * The result value is only significant for UNIQUE_CHECK_PARTIAL:
99 : : * it must be true if the entry is known unique, else false.
100 : : * (In the current implementation we'll also return true after a
101 : : * successful UNIQUE_CHECK_YES or UNIQUE_CHECK_EXISTING call, but
102 : : * that's just a coding artifact.)
103 : : */
104 : : bool
7543 tgl@sss.pgh.pa.us 105 :CBC 5134824 : _bt_doinsert(Relation rel, IndexTuple itup,
106 : : IndexUniqueCheck checkUnique, bool indexUnchanged,
107 : : Relation heapRel)
108 : : {
6262 109 : 5134824 : bool is_unique = false;
110 : : BTInsertStateData insertstate;
111 : : BTScanInsert itup_key;
112 : : BTStack stack;
2741 pg@bowt.ie 113 : 5134824 : bool checkingunique = (checkUnique != UNIQUE_CHECK_NO);
114 : :
115 : : /* we need an insertion scan key to do our search, so build one */
1198 116 : 5134824 : itup_key = _bt_mkscankey(rel, itup);
117 : :
2707 118 [ + + ]: 5134824 : if (checkingunique)
119 : : {
120 [ + + ]: 3456690 : if (!itup_key->anynullkeys)
121 : : {
122 : : /* No (heapkeyspace) scantid until uniqueness established */
123 : 3446556 : itup_key->scantid = NULL;
124 : : }
125 : : else
126 : : {
127 : : /*
128 : : * Scan key for new tuple contains NULL key values. Bypass
129 : : * checkingunique steps. They are unnecessary because core code
130 : : * considers NULL unequal to every value, including NULL.
131 : : *
132 : : * This optimization avoids O(N^2) behavior within the
133 : : * _bt_findinsertloc() heapkeyspace path when a unique index has a
134 : : * large number of "duplicates" with NULL key values.
135 : : */
136 : 10134 : checkingunique = false;
137 : : /* Tuple is unique in the sense that core code cares about */
138 [ - + ]: 10134 : Assert(checkUnique != UNIQUE_CHECK_EXISTING);
139 : 10134 : is_unique = true;
140 : : }
141 : : }
142 : :
143 : : /*
144 : : * Fill in the BTInsertState working area, to track the current page and
145 : : * position within the page to insert on.
146 : : *
147 : : * Note that itemsz is passed down to lower level code that deals with
148 : : * inserting the item. It must be MAXALIGN()'d. This ensures that space
149 : : * accounting code consistently considers the alignment overhead that we
150 : : * expect PageAddItem() will add later. (Actually, index_form_tuple() is
151 : : * already conservative about alignment, but we don't rely on that from
152 : : * this distance. Besides, preserving the "true" tuple size in index
153 : : * tuple headers for the benefit of nbtsplitloc.c might happen someday.
154 : : * Note that heapam does not MAXALIGN() each heap tuple's lp_len field.)
155 : : */
2741 156 : 5134824 : insertstate.itup = itup;
157 : 5134824 : insertstate.itemsz = MAXALIGN(IndexTupleSize(itup));
158 : 5134824 : insertstate.itup_key = itup_key;
159 : 5134824 : insertstate.bounds_valid = false;
160 : 5134824 : insertstate.buf = InvalidBuffer;
2398 161 : 5134824 : insertstate.postingoff = 0;
162 : :
2377 163 : 5134836 : search:
164 : :
165 : : /*
166 : : * Find and lock the leaf page that the tuple should be added to by
167 : : * searching from the root page. insertstate.buf will hold a buffer that
168 : : * is locked in exclusive mode afterwards.
169 : : */
1268 andres@anarazel.de 170 : 5134836 : stack = _bt_search_insert(rel, heapRel, &insertstate);
171 : :
172 : : /*
173 : : * checkingunique inserts are not allowed to go ahead when two tuples with
174 : : * equal key attribute values would be visible to new MVCC snapshots once
175 : : * the xact commits. Check for conflicts in the locked page/buffer (if
176 : : * needed) here.
177 : : *
178 : : * It might be necessary to check a page to the right in _bt_check_unique,
179 : : * though that should be very rare. In practice the first page the value
180 : : * could be on (with scantid omitted) is almost always also the only page
181 : : * that a matching tuple might be found on. This is due to the behavior
182 : : * of _bt_findsplitloc with duplicate tuples -- a group of duplicates can
183 : : * only be allowed to cross a page boundary when there is no candidate
184 : : * leaf page split point that avoids it. Also, _bt_check_unique can use
185 : : * the leaf page high key to determine that there will be no duplicates on
186 : : * the right sibling without actually visiting it (it uses the high key in
187 : : * cases where the new item happens to belong at the far right of the leaf
188 : : * page).
189 : : *
190 : : * NOTE: obviously, _bt_check_unique can only detect keys that are already
191 : : * in the index; so it cannot defend against concurrent insertions of the
192 : : * same key. We protect against that by means of holding a write lock on
193 : : * the first page the value could be on, with omitted/-inf value for the
194 : : * implicit heap TID tiebreaker attribute. Any other would-be inserter of
195 : : * the same key must acquire a write lock on the same page, so only one
196 : : * would-be inserter can be making the check at one time. Furthermore,
197 : : * once we are past the check we hold write locks continuously until we
198 : : * have performed our insertion, so no later inserter can fail to see our
199 : : * insertion. (This requires some care in _bt_findinsertloc.)
200 : : *
201 : : * If we must wait for another xact, we release the lock while waiting,
202 : : * and then must perform a new search.
203 : : *
204 : : * For a partial uniqueness check, we don't wait for the other xact. Just
205 : : * let the tuple in and return false for possibly non-unique, or true for
206 : : * definitely unique.
207 : : */
2741 pg@bowt.ie 208 [ + + ]: 5134836 : if (checkingunique)
209 : : {
210 : : TransactionId xwait;
211 : : uint32 speculativeToken;
212 : :
213 : 3446568 : xwait = _bt_check_unique(rel, &insertstate, heapRel, checkUnique,
214 : : &is_unique, &speculativeToken);
215 : :
2377 216 [ + + ]: 3446189 : if (unlikely(TransactionIdIsValid(xwait)))
217 : : {
218 : : /* Have to wait for the other guy ... */
2741 219 : 12 : _bt_relbuf(rel, insertstate.buf);
220 : 12 : insertstate.buf = InvalidBuffer;
221 : :
222 : : /*
223 : : * If it's a speculative insertion, wait for it to finish (ie. to
224 : : * go ahead with the insertion, or kill the tuple). Otherwise
225 : : * wait for the transaction to finish as usual.
226 : : */
4153 andres@anarazel.de 227 [ - + ]: 12 : if (speculativeToken)
4153 andres@anarazel.de 228 :UBC 0 : SpeculativeInsertionWait(xwait, speculativeToken);
229 : : else
4153 andres@anarazel.de 230 :CBC 12 : XactLockTableWait(xwait, rel, &itup->t_tid, XLTW_InsertIndex);
231 : :
232 : : /* start over... */
3100 andrew@dunslane.net 233 [ - + ]: 12 : if (stack)
3100 andrew@dunslane.net 234 :UBC 0 : _bt_freestack(stack);
2377 pg@bowt.ie 235 :CBC 12 : goto search;
236 : : }
237 : :
238 : : /* Uniqueness is established -- restore heap tid as scantid */
2741 239 [ + - ]: 3446177 : if (itup_key->heapkeyspace)
240 : 3446177 : itup_key->scantid = &itup->t_tid;
241 : : }
242 : :
6262 tgl@sss.pgh.pa.us 243 [ + + ]: 5134445 : if (checkUnique != UNIQUE_CHECK_EXISTING)
244 : : {
245 : : OffsetNumber newitemoff;
246 : :
247 : : /*
248 : : * The only conflict predicate locking cares about for indexes is when
249 : : * an index tuple insert conflicts with an existing lock. We don't
250 : : * know the actual page we're going to insert on for sure just yet in
251 : : * checkingunique and !heapkeyspace cases, but it's okay to use the
252 : : * first page the value could be on (with scantid omitted) instead.
253 : : */
2427 tmunro@postgresql.or 254 : 5134409 : CheckForSerializableConflictIn(rel, NULL, BufferGetBlockNumber(insertstate.buf));
255 : :
256 : : /*
257 : : * Do the insertion. Note that insertstate contains cached binary
258 : : * search bounds established within _bt_check_unique when insertion is
259 : : * checkingunique.
260 : : */
2741 pg@bowt.ie 261 : 5134406 : newitemoff = _bt_findinsertloc(rel, &insertstate, checkingunique,
262 : : indexUnchanged, stack, heapRel);
1268 andres@anarazel.de 263 : 5134406 : _bt_insertonpg(rel, heapRel, itup_key, insertstate.buf, InvalidBuffer,
264 : : stack, itup, insertstate.itemsz, newitemoff,
265 : : insertstate.postingoff, false);
266 : : }
267 : : else
268 : : {
269 : : /* just release the buffer */
2741 pg@bowt.ie 270 : 36 : _bt_relbuf(rel, insertstate.buf);
271 : : }
272 : :
273 : : /* be tidy */
3100 andrew@dunslane.net 274 [ + + ]: 5134440 : if (stack)
275 : 4522595 : _bt_freestack(stack);
2741 pg@bowt.ie 276 : 5134440 : pfree(itup_key);
277 : :
6262 tgl@sss.pgh.pa.us 278 : 5134440 : return is_unique;
279 : : }
280 : :
281 : : /*
282 : : * _bt_search_insert() -- _bt_search() wrapper for inserts
283 : : *
284 : : * Search the tree for a particular scankey, or more precisely for the first
285 : : * leaf page it could be on. Try to make use of the fastpath optimization's
286 : : * rightmost leaf page cache before actually searching the tree from the root
287 : : * page, though.
288 : : *
289 : : * Return value is a stack of parent-page pointers (though see notes about
290 : : * fastpath optimization and page splits below). insertstate->buf is set to
291 : : * the address of the leaf-page buffer, which is write-locked and pinned in
292 : : * all cases (if necessary by creating a new empty root page for caller).
293 : : *
294 : : * The fastpath optimization avoids most of the work of searching the tree
295 : : * repeatedly when a single backend inserts successive new tuples on the
296 : : * rightmost leaf page of an index. A backend cache of the rightmost leaf
297 : : * page is maintained within _bt_insertonpg(), and used here. The cache is
298 : : * invalidated here when an insert of a non-pivot tuple must take place on a
299 : : * non-rightmost leaf page.
300 : : *
301 : : * The optimization helps with indexes on an auto-incremented field. It also
302 : : * helps with indexes on datetime columns, as well as indexes with lots of
303 : : * NULL values. (NULLs usually get inserted in the rightmost page for single
304 : : * column indexes, since they usually get treated as coming after everything
305 : : * else in the key space. Individual NULL tuples will generally be placed on
306 : : * the rightmost leaf page due to the influence of the heap TID column.)
307 : : *
308 : : * Note that we avoid applying the optimization when there is insufficient
309 : : * space on the rightmost page to fit caller's new item. This is necessary
310 : : * because we'll need to return a real descent stack when a page split is
311 : : * expected (actually, caller can cope with a leaf page split that uses a NULL
312 : : * stack, but that's very slow and so must be avoided). Note also that the
313 : : * fastpath optimization acquires the lock on the page conditionally as a way
314 : : * of reducing extra contention when there are concurrent insertions into the
315 : : * rightmost page (we give up if we'd have to wait for the lock). We assume
316 : : * that it isn't useful to apply the optimization when there is contention,
317 : : * since each per-backend cache won't stay valid for long.
318 : : */
319 : : static BTStack
1268 andres@anarazel.de 320 : 5134836 : _bt_search_insert(Relation rel, Relation heaprel, BTInsertState insertstate)
321 : : {
2377 pg@bowt.ie 322 [ - + ]: 5134836 : Assert(insertstate->buf == InvalidBuffer);
323 [ - + ]: 5134836 : Assert(!insertstate->bounds_valid);
324 [ - + ]: 5134836 : Assert(insertstate->postingoff == 0);
325 : :
326 [ + - + + ]: 5134836 : if (RelationGetTargetBlock(rel) != InvalidBlockNumber)
327 : : {
328 : : /* Simulate a _bt_getbuf() call with conditional locking */
329 [ + - ]: 35493 : insertstate->buf = ReadBuffer(rel, RelationGetTargetBlock(rel));
2252 330 [ + + ]: 35493 : if (_bt_conditionallockbuf(rel, insertstate->buf))
331 : : {
332 : : Page page;
333 : : BTPageOpaque opaque;
334 : :
2377 335 : 33900 : _bt_checkpage(rel, insertstate->buf);
336 : 33900 : page = BufferGetPage(insertstate->buf);
1633 michael@paquier.xyz 337 : 33900 : opaque = BTPageGetOpaque(page);
338 : :
339 : : /*
340 : : * Check if the page is still the rightmost leaf page and has
341 : : * enough free space to accommodate the new tuple. Also check
342 : : * that the insertion scan key is strictly greater than the first
343 : : * non-pivot tuple on the page. (Note that we expect itup_key's
344 : : * scantid to be unset when our caller is a checkingunique
345 : : * inserter.)
346 : : */
2133 pg@bowt.ie 347 [ + + ]: 33900 : if (P_RIGHTMOST(opaque) &&
348 [ + - ]: 33879 : P_ISLEAF(opaque) &&
349 [ + - ]: 33879 : !P_IGNORE(opaque) &&
2377 350 [ + + + - ]: 67538 : PageGetFreeSpace(page) > insertstate->itemsz &&
351 [ + + ]: 67318 : PageGetMaxOffsetNumber(page) >= P_HIKEY &&
352 : 33659 : _bt_compare(rel, insertstate->itup_key, page, P_HIKEY) > 0)
353 : : {
354 : : /*
355 : : * Caller can use the fastpath optimization because cached
356 : : * block is still rightmost leaf page, which can fit caller's
357 : : * new tuple without splitting. Keep block in local cache for
358 : : * next insert, and have caller use NULL stack.
359 : : *
360 : : * Note that _bt_insert_parent() has an assertion that catches
361 : : * leaf page splits that somehow follow from a fastpath insert
362 : : * (it should only be passed a NULL stack when it must deal
363 : : * with a concurrent root page split, and never because a NULL
364 : : * stack was returned here).
365 : : */
366 : 33640 : return NULL;
367 : : }
368 : :
369 : : /* Page unsuitable for caller, drop lock and pin */
370 : 260 : _bt_relbuf(rel, insertstate->buf);
371 : : }
372 : : else
373 : : {
374 : : /* Lock unavailable, drop pin */
375 : 1593 : ReleaseBuffer(insertstate->buf);
376 : : }
377 : :
378 : : /* Forget block, since cache doesn't appear to be useful */
379 : 1853 : RelationSetTargetBlock(rel, InvalidBlockNumber);
380 : : }
381 : :
382 : : /* Cannot use optimization -- descend tree, return proper descent stack */
1268 andres@anarazel.de 383 : 5101196 : return _bt_search(rel, heaprel, insertstate->itup_key, &insertstate->buf,
384 : : BT_WRITE, true);
385 : : }
386 : :
387 : : /*
388 : : * _bt_check_unique() -- Check for violation of unique index constraint
389 : : *
390 : : * Returns InvalidTransactionId if there is no conflict, else an xact ID
391 : : * we must wait for to see if it commits a conflicting tuple. If an actual
392 : : * conflict is detected, no return --- just ereport(). If an xact ID is
393 : : * returned, and the conflicting tuple still has a speculative insertion in
394 : : * progress, *speculativeToken is set to non-zero, and the caller can wait for
395 : : * the verdict on the insertion using SpeculativeInsertionWait().
396 : : *
397 : : * However, if checkUnique == UNIQUE_CHECK_PARTIAL, we always return
398 : : * InvalidTransactionId because we don't want to wait. In this case we
399 : : * set *is_unique to false if there is a potential conflict, and the
400 : : * core code must redo the uniqueness check later.
401 : : *
402 : : * As a side-effect, sets state in insertstate that can later be used by
403 : : * _bt_findinsertloc() to reuse most of the binary search work we do
404 : : * here.
405 : : *
406 : : * This code treats NULLs as equal, unlike the default semantics for unique
407 : : * indexes. So do not call here when there are NULL values in scan key and
408 : : * the index uses the default NULLS DISTINCT mode.
409 : : */
410 : : static TransactionId
2741 pg@bowt.ie 411 : 3446568 : _bt_check_unique(Relation rel, BTInsertState insertstate, Relation heapRel,
412 : : IndexUniqueCheck checkUnique, bool *is_unique,
413 : : uint32 *speculativeToken)
414 : : {
415 : 3446568 : IndexTuple itup = insertstate->itup;
2290 416 : 3446568 : IndexTuple curitup = NULL;
1991 417 : 3446568 : ItemId curitemid = NULL;
2741 418 : 3446568 : BTScanInsert itup_key = insertstate->itup_key;
419 : : SnapshotData SnapshotDirty;
420 : : OffsetNumber offset;
421 : : OffsetNumber maxoff;
422 : : Page page;
423 : : BTPageOpaque opaque;
9557 tgl@sss.pgh.pa.us 424 : 3446568 : Buffer nbuf = InvalidBuffer;
6262 425 : 3446568 : bool found = false;
2398 pg@bowt.ie 426 : 3446568 : bool inposting = false;
427 : 3446568 : bool prevalldead = true;
428 : 3446568 : int curposti = 0;
429 : :
430 : : /* Assume unique until we find a duplicate */
6262 tgl@sss.pgh.pa.us 431 : 3446568 : *is_unique = true;
432 : :
7119 433 : 3446568 : InitDirtySnapshot(SnapshotDirty);
434 : :
2741 pg@bowt.ie 435 : 3446568 : page = BufferGetPage(insertstate->buf);
1633 michael@paquier.xyz 436 : 3446568 : opaque = BTPageGetOpaque(page);
9557 tgl@sss.pgh.pa.us 437 : 3446568 : maxoff = PageGetMaxOffsetNumber(page);
438 : :
439 : : /*
440 : : * Find the first tuple with the same key.
441 : : *
442 : : * This also saves the binary search bounds in insertstate. We use them
443 : : * in the fastpath below, but also in the _bt_findinsertloc() call later.
444 : : */
2726 pg@bowt.ie 445 [ - + ]: 3446568 : Assert(!insertstate->bounds_valid);
2741 446 : 3446568 : offset = _bt_binsrch_insert(rel, insertstate);
447 : :
448 : : /*
449 : : * Scan over all equal tuples, looking for live conflicts.
450 : : */
451 [ + + - + ]: 3446568 : Assert(!insertstate->bounds_valid || insertstate->low == offset);
2707 452 [ - + ]: 3446568 : Assert(!itup_key->anynullkeys);
2741 453 [ + - ]: 3446568 : Assert(itup_key->scantid == NULL);
454 : : for (;;)
455 : : {
456 : : /*
457 : : * Each iteration of the loop processes one heap TID, not one index
458 : : * tuple. Current offset number for page isn't usually advanced on
459 : : * iterations that process heap TIDs from posting list tuples.
460 : : *
461 : : * "inposting" state is set when _inside_ a posting list --- not when
462 : : * we're at the start (or end) of a posting list. We advance curposti
463 : : * at the end of the iteration when inside a posting list tuple. In
464 : : * general, every loop iteration either advances the page offset or
465 : : * advances curposti --- an iteration that handles the rightmost/max
466 : : * heap TID in a posting list finally advances the page offset (and
467 : : * unsets "inposting").
468 : : *
469 : : * Make sure the offset points to an actual index tuple before trying
470 : : * to examine it...
471 : : */
9557 tgl@sss.pgh.pa.us 472 [ + + ]: 11375161 : if (offset <= maxoff)
473 : : {
474 : : /*
475 : : * Fastpath: In most cases, we can use cached search bounds to
476 : : * limit our consideration to items that are definitely
477 : : * duplicates. This fastpath doesn't apply when the original page
478 : : * is empty, or when initial offset is past the end of the
479 : : * original page, which may indicate that we need to examine a
480 : : * second or subsequent page.
481 : : *
482 : : * Note that this optimization allows us to avoid calling
483 : : * _bt_compare() directly when there are no duplicates, as long as
484 : : * the offset where the key will go is not at the end of the page.
485 : : */
2741 pg@bowt.ie 486 [ + + + + ]: 9325346 : if (nbuf == InvalidBuffer && offset == insertstate->stricthigh)
487 : : {
488 [ - + ]: 1253916 : Assert(insertstate->bounds_valid);
489 [ + + - + ]: 1253916 : Assert(insertstate->low >= P_FIRSTDATAKEY(opaque));
490 [ - + ]: 1253916 : Assert(insertstate->low <= insertstate->stricthigh);
2707 491 [ - + ]: 1253916 : Assert(_bt_compare(rel, itup_key, page, offset) < 0);
2741 492 : 1253916 : break;
493 : : }
494 : :
495 : : /*
496 : : * We can skip items that are already marked killed.
497 : : *
498 : : * In the presence of heavy update activity an index may contain
499 : : * many killed items with the same key; running _bt_compare() on
500 : : * each killed item gets expensive. Just advance over killed
501 : : * items as quickly as we can. We only apply _bt_compare() when
502 : : * we get to a non-killed item. We could reuse the bounds to
503 : : * avoid _bt_compare() calls for known equal tuples, but it
504 : : * doesn't seem worth it.
505 : : */
2398 506 [ + + ]: 8071430 : if (!inposting)
507 : 5064016 : curitemid = PageGetItemId(page, offset);
508 [ + + + + ]: 8071430 : if (inposting || !ItemIdIsDead(curitemid))
509 : : {
510 : : ItemPointerData htid;
511 : 7734853 : bool all_dead = false;
512 : :
513 [ + + ]: 7734853 : if (!inposting)
514 : : {
515 : : /* Plain tuple, or first TID in posting list tuple */
516 [ + + ]: 4727439 : if (_bt_compare(rel, itup_key, page, offset) != 0)
517 : 125229 : break; /* we're past all the equal tuples */
518 : :
519 : : /* Advanced curitup */
520 : 4602210 : curitup = (IndexTuple) PageGetItem(page, curitemid);
521 [ - + ]: 4602210 : Assert(!BTreeTupleIsPivot(curitup));
522 : : }
523 : :
524 : : /* okay, we gotta fetch the heap tuple using htid ... */
525 [ + + ]: 7609624 : if (!BTreeTupleIsPosting(curitup))
526 : : {
527 : : /* ... htid is from simple non-pivot tuple */
528 [ - + ]: 4572703 : Assert(!inposting);
529 : 4572703 : htid = curitup->t_tid;
530 : : }
531 [ + + ]: 3036921 : else if (!inposting)
532 : : {
533 : : /* ... htid is first TID in new posting list */
534 : 29507 : inposting = true;
535 : 29507 : prevalldead = true;
536 : 29507 : curposti = 0;
537 : 29507 : htid = *BTreeTupleGetPostingN(curitup, 0);
538 : : }
539 : : else
540 : : {
541 : : /* ... htid is second or subsequent TID in posting list */
542 [ - + ]: 3007414 : Assert(curposti > 0);
543 : 3007414 : htid = *BTreeTupleGetPostingN(curitup, curposti);
544 : : }
545 : :
546 : : /*
547 : : * If we are doing a recheck, we expect to find the tuple we
548 : : * are rechecking. It's not a duplicate, but we have to keep
549 : : * scanning.
550 : : */
6262 tgl@sss.pgh.pa.us 551 [ + + + + ]: 7609807 : if (checkUnique == UNIQUE_CHECK_EXISTING &&
552 : 183 : ItemPointerCompare(&htid, &itup->t_tid) == 0)
553 : : {
554 : 36 : found = true;
555 : : }
556 : :
557 : : /*
558 : : * Check if there's any table tuples for this index entry
559 : : * satisfying SnapshotDirty. This is necessary because for AMs
560 : : * with optimizations like heap's HOT, we have just a single
561 : : * index entry for the entire chain.
562 : : */
5 pg@bowt.ie 563 [ + + ]:GNC 7609588 : else if (table_fetch_tid(heapRel, &htid, &SnapshotDirty,
564 : : &all_dead))
565 : : {
566 : : TransactionId xwait;
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 : : */
6262 tgl@sss.pgh.pa.us 576 [ + + ]:CBC 614 : if (checkUnique == UNIQUE_CHECK_PARTIAL)
577 : : {
578 [ - + ]: 223 : if (nbuf != InvalidBuffer)
6262 tgl@sss.pgh.pa.us 579 :UBC 0 : _bt_relbuf(rel, nbuf);
6262 tgl@sss.pgh.pa.us 580 :CBC 223 : *is_unique = false;
581 : 235 : return InvalidTransactionId;
582 : : }
583 : :
584 : : /*
585 : : * If this tuple is being updated by other transaction
586 : : * then we have to wait for its commit/abort.
587 : : */
588 : 782 : xwait = (TransactionIdIsValid(SnapshotDirty.xmin)) ?
589 [ + + ]: 391 : SnapshotDirty.xmin : SnapshotDirty.xmax;
590 : :
8885 591 [ + + ]: 391 : if (TransactionIdIsValid(xwait))
592 : : {
593 [ - + ]: 12 : if (nbuf != InvalidBuffer)
8885 tgl@sss.pgh.pa.us 594 :UBC 0 : _bt_relbuf(rel, nbuf);
595 : : /* Tell _bt_doinsert to wait... */
4153 andres@anarazel.de 596 :CBC 12 : *speculativeToken = SnapshotDirty.speculativeToken;
597 : : /* Caller releases lock on buf immediately */
2726 pg@bowt.ie 598 : 12 : insertstate->bounds_valid = false;
8885 tgl@sss.pgh.pa.us 599 : 12 : return xwait;
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 : : */
2278 pg@bowt.ie 619 : 379 : htid = itup->t_tid;
5 pg@bowt.ie 620 [ - + ]:GNC 379 : if (table_fetch_tid(heapRel, &htid, SnapshotSelf, NULL))
621 : : {
622 : : /* Normal case --- it's still live */
623 : : }
624 : : else
625 : : {
626 : : /*
627 : : * It's been deleted, so no error, and no need to
628 : : * continue searching
629 : : */
7331 tgl@sss.pgh.pa.us 630 :UBC 0 : break;
631 : : }
632 : :
633 : : /*
634 : : * Check for a conflict-in as we would if we were going to
635 : : * write to this page. We aren't actually going to write,
636 : : * but we want a chance to report SSI conflicts that would
637 : : * otherwise be masked by this unique constraint
638 : : * violation.
639 : : */
2427 tmunro@postgresql.or 640 :CBC 379 : CheckForSerializableConflictIn(rel, NULL, BufferGetBlockNumber(insertstate->buf));
641 : :
642 : : /*
643 : : * This is a definite conflict. Break the tuple down into
644 : : * datums and report the error. But first, make sure we
645 : : * release the buffer locks we're holding ---
646 : : * BuildIndexValueDescription could make catalog accesses,
647 : : * which in the worst case might touch this same index and
648 : : * cause deadlocks.
649 : : */
6259 tgl@sss.pgh.pa.us 650 [ - + ]: 375 : if (nbuf != InvalidBuffer)
6259 tgl@sss.pgh.pa.us 651 :UBC 0 : _bt_relbuf(rel, nbuf);
2741 pg@bowt.ie 652 :CBC 375 : _bt_relbuf(rel, insertstate->buf);
653 : 375 : insertstate->buf = InvalidBuffer;
2726 654 : 375 : insertstate->bounds_valid = false;
655 : :
656 : : {
657 : : Datum values[INDEX_MAX_KEYS];
658 : : bool isnull[INDEX_MAX_KEYS];
659 : : char *key_desc;
660 : :
6259 tgl@sss.pgh.pa.us 661 : 375 : index_deform_tuple(itup, RelationGetDescr(rel),
662 : : values, isnull);
663 : :
4269 sfrost@snowman.net 664 : 375 : key_desc = BuildIndexValueDescription(rel, values,
665 : : isnull);
666 : :
6259 tgl@sss.pgh.pa.us 667 [ + - + + ]: 375 : ereport(ERROR,
668 : : (errcode(ERRCODE_UNIQUE_VIOLATION),
669 : : errmsg("duplicate key value violates unique constraint \"%s\"",
670 : : RelationGetRelationName(rel)),
671 : : key_desc ? errdetail("Key %s already exists.",
672 : : key_desc) : 0,
673 : : errtableconstraint(heapRel,
674 : : RelationGetRelationName(rel))));
675 : : }
676 : : }
2398 pg@bowt.ie 677 [ + + + + : 7608974 : else if (all_dead && (!inposting ||
+ + ]
678 : 21266 : (prevalldead &&
679 [ + + ]: 21266 : curposti == BTreeTupleGetNPosting(curitup) - 1)))
680 : : {
681 : : /*
682 : : * The conflicting tuple (or all HOT chains pointed to by
683 : : * all posting list TIDs) is dead to everyone, so try to
684 : : * mark the index entry killed. It's ok if we're not
685 : : * allowed to, this isn't required for correctness.
686 : : */
687 : : Buffer buf;
688 : :
689 : : /* Be sure to operate on the proper buffer */
6940 tgl@sss.pgh.pa.us 690 [ + + ]: 51624 : if (nbuf != InvalidBuffer)
194 andres@anarazel.de 691 : 4 : buf = nbuf;
692 : : else
693 : 51620 : buf = insertstate->buf;
694 : :
695 : : /*
696 : : * Use the hint bit infrastructure to check if we can
697 : : * update the page while just holding a share lock.
698 : : *
699 : : * Can't use BufferSetHintBits16() here as we update two
700 : : * different locations.
701 : : */
702 [ + - ]: 51624 : if (BufferBeginSetHintBits(buf))
703 : : {
704 : 51624 : ItemIdMarkDead(curitemid);
705 : 51624 : opaque->btpo_flags |= BTP_HAS_GARBAGE;
706 : 51624 : BufferFinishSetHintBits(buf, true, true);
707 : : }
708 : : }
709 : :
710 : : /*
711 : : * Remember if posting list tuple has even a single HOT chain
712 : : * whose members are not all dead
713 : : */
2398 pg@bowt.ie 714 [ + + + + ]: 7609010 : if (!all_dead && inposting)
715 : 3015281 : prevalldead = false;
716 : : }
717 : : }
718 : :
719 [ + + + + ]: 9995402 : if (inposting && curposti < BTreeTupleGetNPosting(curitup) - 1)
720 : : {
721 : : /* Advance to next TID in same posting list */
722 : 3007414 : curposti++;
723 : 3007414 : continue;
724 : : }
725 [ + + ]: 6987988 : else if (offset < maxoff)
726 : : {
727 : : /* Advance to next tuple */
728 : 4914483 : curposti = 0;
729 : 4914483 : inposting = false;
9557 tgl@sss.pgh.pa.us 730 : 4914483 : offset = OffsetNumberNext(offset);
731 : : }
732 : : else
733 : : {
734 : : int highkeycmp;
735 : :
736 : : /* If scankey == hikey we gotta check the next page too */
737 [ + + ]: 2073505 : if (P_RIGHTMOST(opaque))
738 : 1996063 : break;
2741 pg@bowt.ie 739 : 77442 : highkeycmp = _bt_compare(rel, itup_key, page, P_HIKEY);
740 [ - + ]: 77442 : Assert(highkeycmp <= 0);
741 [ + + ]: 77442 : if (highkeycmp != 0)
9557 tgl@sss.pgh.pa.us 742 : 70746 : break;
743 : : /* Advance to next non-dead page --- there must be one */
744 : : for (;;)
8611 tgl@sss.pgh.pa.us 745 :UBC 0 : {
2398 pg@bowt.ie 746 :CBC 6696 : BlockNumber nblkno = opaque->btpo_next;
747 : :
8187 tgl@sss.pgh.pa.us 748 : 6696 : nbuf = _bt_relandgetbuf(rel, nbuf, nblkno, BT_READ);
3805 kgrittn@postgresql.o 749 : 6696 : page = BufferGetPage(nbuf);
1633 michael@paquier.xyz 750 : 6696 : opaque = BTPageGetOpaque(page);
8611 tgl@sss.pgh.pa.us 751 [ + - ]: 6696 : if (!P_IGNORE(opaque))
752 : 6696 : break;
8611 tgl@sss.pgh.pa.us 753 [ # # ]:UBC 0 : if (P_RIGHTMOST(opaque))
6838 754 [ # # ]: 0 : elog(ERROR, "fell off the end of index \"%s\"",
755 : : RelationGetRelationName(rel));
756 : : }
757 : : /* Will also advance to next tuple */
2398 pg@bowt.ie 758 :CBC 6696 : curposti = 0;
759 : 6696 : inposting = false;
9557 tgl@sss.pgh.pa.us 760 : 6696 : maxoff = PageGetMaxOffsetNumber(page);
761 [ + + ]: 6696 : offset = P_FIRSTDATAKEY(opaque);
762 : : /* Don't invalidate binary search bounds */
763 : : }
764 : : }
765 : :
766 : : /*
767 : : * If we are doing a recheck then we should have found the tuple we are
768 : : * checking. Otherwise there's something very wrong --- probably, the
769 : : * index is on a non-immutable expression.
770 : : */
6262 771 [ + + - + ]: 3445954 : if (checkUnique == UNIQUE_CHECK_EXISTING && !found)
6262 tgl@sss.pgh.pa.us 772 [ # # ]:UBC 0 : ereport(ERROR,
773 : : (errcode(ERRCODE_INTERNAL_ERROR),
774 : : errmsg("failed to re-find tuple within index \"%s\"",
775 : : RelationGetRelationName(rel)),
776 : : errhint("This may be because of a non-immutable index expression."),
777 : : errtableconstraint(heapRel,
778 : : RelationGetRelationName(rel))));
779 : :
9557 tgl@sss.pgh.pa.us 780 [ + + ]:CBC 3445954 : if (nbuf != InvalidBuffer)
9198 781 : 3840 : _bt_relbuf(rel, nbuf);
782 : :
9159 783 : 3445954 : return InvalidTransactionId;
784 : : }
785 : :
786 : :
787 : : /*
788 : : * _bt_findinsertloc() -- Finds an insert location for a tuple
789 : : *
790 : : * On entry, insertstate buffer contains the page the new tuple belongs
791 : : * on. It is exclusive-locked and pinned by the caller.
792 : : *
793 : : * If 'checkingunique' is true, the buffer on entry is the first page
794 : : * that contains duplicates of the new key. If there are duplicates on
795 : : * multiple pages, the correct insertion position might be some page to
796 : : * the right, rather than the first page. In that case, this function
797 : : * moves right to the correct target page.
798 : : *
799 : : * (In a !heapkeyspace index, there can be multiple pages with the same
800 : : * high key, where the new tuple could legitimately be placed on. In
801 : : * that case, the caller passes the first page containing duplicates,
802 : : * just like when checkingunique=true. If that page doesn't have enough
803 : : * room for the new tuple, this function moves right, trying to find a
804 : : * legal page that does.)
805 : : *
806 : : * If 'indexUnchanged' is true, this is for an UPDATE that didn't
807 : : * logically change the indexed value, but must nevertheless have a new
808 : : * entry to point to a successor version. This hint from the executor
809 : : * will influence our behavior when the page might have to be split and
810 : : * we must consider our options. Bottom-up index deletion can avoid
811 : : * pathological version-driven page splits, but we only want to go to the
812 : : * trouble of trying it when we already have moderate confidence that
813 : : * it's appropriate. The hint should not significantly affect our
814 : : * behavior over time unless practically all inserts on to the leaf page
815 : : * get the hint.
816 : : *
817 : : * On exit, insertstate buffer contains the chosen insertion page, and
818 : : * the offset within that page is returned. If _bt_findinsertloc needed
819 : : * to move right, the lock and pin on the original page are released, and
820 : : * the new buffer is exclusively locked and pinned instead.
821 : : *
822 : : * If insertstate contains cached binary search bounds, we will take
823 : : * advantage of them. This avoids repeating comparisons that we made in
824 : : * _bt_check_unique() already.
825 : : */
826 : : static OffsetNumber
7141 bruce@momjian.us 827 : 5134406 : _bt_findinsertloc(Relation rel,
828 : : BTInsertState insertstate,
829 : : bool checkingunique,
830 : : bool indexUnchanged,
831 : : BTStack stack,
832 : : Relation heapRel)
833 : : {
2741 pg@bowt.ie 834 : 5134406 : BTScanInsert itup_key = insertstate->itup_key;
835 : 5134406 : Page page = BufferGetPage(insertstate->buf);
836 : : BTPageOpaque opaque;
837 : : OffsetNumber newitemoff;
838 : :
1633 michael@paquier.xyz 839 : 5134406 : opaque = BTPageGetOpaque(page);
840 : :
841 : : /* Check 1/3 of a page restriction */
558 pg@bowt.ie 842 [ - + ]: 5134406 : if (unlikely(insertstate->itemsz > BTMaxItemSize))
2741 pg@bowt.ie 843 :UBC 0 : _bt_check_third_page(rel, heapRel, itup_key->heapkeyspace, page,
844 : : insertstate->itup);
845 : :
2133 pg@bowt.ie 846 [ + - - + ]:CBC 5134406 : Assert(P_ISLEAF(opaque) && !P_INCOMPLETE_SPLIT(opaque));
2741 847 [ + + - + ]: 5134406 : Assert(!insertstate->bounds_valid || checkingunique);
848 [ + - - + ]: 5134406 : Assert(!itup_key->heapkeyspace || itup_key->scantid != NULL);
849 [ - + - - ]: 5134406 : Assert(itup_key->heapkeyspace || itup_key->scantid == NULL);
2398 850 [ + + - + ]: 5134406 : Assert(!itup_key->allequalimage || itup_key->heapkeyspace);
851 : :
2741 852 [ + - ]: 5134406 : if (itup_key->heapkeyspace)
853 : : {
854 : : /* Keep track of whether checkingunique duplicate seen */
2076 855 : 5134406 : bool uniquedup = indexUnchanged;
856 : :
857 : : /*
858 : : * If we're inserting into a unique index, we may have to walk right
859 : : * through leaf pages to find the one leaf page that we must insert on
860 : : * to.
861 : : *
862 : : * This is needed for checkingunique callers because a scantid was not
863 : : * used when we called _bt_search(). scantid can only be set after
864 : : * _bt_check_unique() has checked for duplicates. The buffer
865 : : * initially stored in insertstate->buf has the page where the first
866 : : * duplicate key might be found, which isn't always the page that new
867 : : * tuple belongs on. The heap TID attribute for new tuple (scantid)
868 : : * could force us to insert on a sibling page, though that should be
869 : : * very rare in practice.
870 : : */
2741 871 [ + + ]: 5134406 : if (checkingunique)
872 : : {
2398 873 [ + + ]: 3446138 : if (insertstate->low < insertstate->stricthigh)
874 : : {
875 : : /* Encountered a duplicate in _bt_check_unique() */
876 [ - + ]: 278121 : Assert(insertstate->bounds_valid);
877 : 278121 : uniquedup = true;
878 : : }
879 : :
880 : : for (;;)
881 : : {
882 : : /*
883 : : * Does the new tuple belong on this page?
884 : : *
885 : : * The earlier _bt_check_unique() call may well have
886 : : * established a strict upper bound on the offset for the new
887 : : * item. If it's not the last item of the page (i.e. if there
888 : : * is at least one tuple on the page that goes after the tuple
889 : : * we're inserting) then we know that the tuple belongs on
890 : : * this page. We can skip the high key check.
891 : : */
2741 892 [ + + ]: 3452834 : if (insertstate->bounds_valid &&
893 [ + - + + ]: 6879432 : insertstate->low <= insertstate->stricthigh &&
894 : 3439716 : insertstate->stricthigh <= PageGetMaxOffsetNumber(page))
895 : 1362500 : break;
896 : :
897 : : /* Test '<=', not '!=', since scantid is set now */
2133 898 [ + + + + ]: 2177399 : if (P_RIGHTMOST(opaque) ||
2741 899 : 87065 : _bt_compare(rel, itup_key, page, P_HIKEY) <= 0)
900 : : break;
901 : :
1268 andres@anarazel.de 902 : 6696 : _bt_stepright(rel, heapRel, insertstate, stack);
903 : : /* Update local state after stepping right */
2741 pg@bowt.ie 904 : 6696 : page = BufferGetPage(insertstate->buf);
1633 michael@paquier.xyz 905 : 6696 : opaque = BTPageGetOpaque(page);
906 : : /* Assume duplicates (if checkingunique) */
2398 pg@bowt.ie 907 : 6696 : uniquedup = true;
908 : : }
909 : : }
910 : :
911 : : /*
912 : : * If the target page cannot fit newitem, try to avoid splitting the
913 : : * page on insert by performing deletion or deduplication now
914 : : */
915 [ + + ]: 5134406 : if (PageGetFreeSpace(page) < insertstate->itemsz)
2133 916 : 33356 : _bt_delete_or_dedup_one_page(rel, heapRel, insertstate, false,
917 : : checkingunique, uniquedup,
918 : : indexUnchanged);
919 : : }
920 : : else
921 : : {
922 : : /*----------
923 : : * This is a !heapkeyspace (version 2 or 3) index. The current page
924 : : * is the first page that we could insert the new tuple to, but there
925 : : * may be other pages to the right that we could opt to use instead.
926 : : *
927 : : * If the new key is equal to one or more existing keys, we can
928 : : * legitimately place it anywhere in the series of equal keys. In
929 : : * fact, if the new key is equal to the page's "high key" we can place
930 : : * it on the next page. If it is equal to the high key, and there's
931 : : * not room to insert the new tuple on the current page without
932 : : * splitting, then we move right hoping to find more free space and
933 : : * avoid a split.
934 : : *
935 : : * Keep scanning right until we
936 : : * (a) find a page with enough free space,
937 : : * (b) reach the last page where the tuple can legally go, or
938 : : * (c) get tired of searching.
939 : : * (c) is not flippant; it is important because if there are many
940 : : * pages' worth of equal keys, it's better to split one of the early
941 : : * pages than to scan all the way to the end of the run of equal keys
942 : : * on every insert. We implement "get tired" as a random choice,
943 : : * since stopping after scanning a fixed number of pages wouldn't work
944 : : * well (we'd never reach the right-hand side of previously split
945 : : * pages). The probability of moving right is set at 0.99, which may
946 : : * seem too high to change the behavior much, but it does an excellent
947 : : * job of preventing O(N^2) behavior with many equal keys.
948 : : *----------
949 : : */
2741 pg@bowt.ie 950 [ # # ]:UBC 0 : while (PageGetFreeSpace(page) < insertstate->itemsz)
951 : : {
952 : : /*
953 : : * Before considering moving right, see if we can obtain enough
954 : : * space by erasing LP_DEAD items
955 : : */
2133 956 [ # # ]: 0 : if (P_HAS_GARBAGE(opaque))
957 : : {
958 : : /* Perform simple deletion */
959 : 0 : _bt_delete_or_dedup_one_page(rel, heapRel, insertstate, true,
960 : : false, false, false);
961 : :
2741 962 [ # # ]: 0 : if (PageGetFreeSpace(page) >= insertstate->itemsz)
963 : 0 : break; /* OK, now we have enough space */
964 : : }
965 : :
966 : : /*
967 : : * Nope, so check conditions (b) and (c) enumerated above
968 : : *
969 : : * The earlier _bt_check_unique() call may well have established a
970 : : * strict upper bound on the offset for the new item. If it's not
971 : : * the last item of the page (i.e. if there is at least one tuple
972 : : * on the page that's greater than the tuple we're inserting to)
973 : : * then we know that the tuple belongs on this page. We can skip
974 : : * the high key check.
975 : : */
976 [ # # ]: 0 : if (insertstate->bounds_valid &&
977 [ # # # # ]: 0 : insertstate->low <= insertstate->stricthigh &&
978 : 0 : insertstate->stricthigh <= PageGetMaxOffsetNumber(page))
979 : 0 : break;
980 : :
2133 981 [ # # # # ]: 0 : if (P_RIGHTMOST(opaque) ||
2741 982 [ # # ]: 0 : _bt_compare(rel, itup_key, page, P_HIKEY) != 0 ||
1757 tgl@sss.pgh.pa.us 983 : 0 : pg_prng_uint32(&pg_global_prng_state) <= (PG_UINT32_MAX / 100))
984 : : break;
985 : :
1268 andres@anarazel.de 986 : 0 : _bt_stepright(rel, heapRel, insertstate, stack);
987 : : /* Update local state after stepping right */
2741 pg@bowt.ie 988 : 0 : page = BufferGetPage(insertstate->buf);
1633 michael@paquier.xyz 989 : 0 : opaque = BTPageGetOpaque(page);
990 : : }
991 : : }
992 : :
993 : : /*
994 : : * We should now be on the correct page. Find the offset within the page
995 : : * for the new tuple. (Possibly reusing earlier search bounds.)
996 : : */
2133 pg@bowt.ie 997 [ + + - + ]:CBC 5134406 : Assert(P_RIGHTMOST(opaque) ||
998 : : _bt_compare(rel, itup_key, page, P_HIKEY) <= 0);
999 : :
2398 1000 : 5134406 : newitemoff = _bt_binsrch_insert(rel, insertstate);
1001 : :
1002 [ + + ]: 5134406 : if (insertstate->postingoff == -1)
1003 : : {
1004 : : /*
1005 : : * There is an overlapping posting list tuple with its LP_DEAD bit
1006 : : * set. We don't want to unnecessarily unset its LP_DEAD bit while
1007 : : * performing a posting list split, so perform simple index tuple
1008 : : * deletion early.
1009 : : */
2133 1010 : 3 : _bt_delete_or_dedup_one_page(rel, heapRel, insertstate, true,
1011 : : false, false, false);
1012 : :
1013 : : /*
1014 : : * Do new binary search. New insert location cannot overlap with any
1015 : : * posting list now.
1016 : : */
1017 [ - + ]: 3 : Assert(!insertstate->bounds_valid);
2398 1018 : 3 : insertstate->postingoff = 0;
1019 : 3 : newitemoff = _bt_binsrch_insert(rel, insertstate);
1020 [ - + ]: 3 : Assert(insertstate->postingoff == 0);
1021 : : }
1022 : :
1023 : 5134406 : return newitemoff;
1024 : : }
1025 : :
1026 : : /*
1027 : : * Step right to next non-dead page, during insertion.
1028 : : *
1029 : : * This is a bit more complicated than moving right in a search. We must
1030 : : * write-lock the target page before releasing write lock on current page;
1031 : : * else someone else's _bt_check_unique scan could fail to see our insertion.
1032 : : * Write locks on intermediate dead pages won't do because we don't know when
1033 : : * they will get de-linked from the tree.
1034 : : *
1035 : : * This is more aggressive than it needs to be for non-unique !heapkeyspace
1036 : : * indexes.
1037 : : */
1038 : : static void
1198 1039 : 6696 : _bt_stepright(Relation rel, Relation heaprel, BTInsertState insertstate,
1040 : : BTStack stack)
1041 : : {
1042 : : Page page;
1043 : : BTPageOpaque opaque;
1044 : : Buffer rbuf;
1045 : : BlockNumber rblkno;
1046 : :
1047 [ - + ]: 6696 : Assert(heaprel != NULL);
2741 1048 : 6696 : page = BufferGetPage(insertstate->buf);
1633 michael@paquier.xyz 1049 : 6696 : opaque = BTPageGetOpaque(page);
1050 : :
2741 pg@bowt.ie 1051 : 6696 : rbuf = InvalidBuffer;
2133 1052 : 6696 : rblkno = opaque->btpo_next;
1053 : : for (;;)
1054 : : {
2741 1055 : 6696 : rbuf = _bt_relandgetbuf(rel, rbuf, rblkno, BT_WRITE);
1056 : 6696 : page = BufferGetPage(rbuf);
1633 michael@paquier.xyz 1057 : 6696 : opaque = BTPageGetOpaque(page);
1058 : :
1059 : : /*
1060 : : * If this page was incompletely split, finish the split now. We do
1061 : : * this while holding a lock on the left sibling, which is not good
1062 : : * because finishing the split could be a fairly lengthy operation.
1063 : : * But this should happen very seldom.
1064 : : */
2133 pg@bowt.ie 1065 [ - + ]: 6696 : if (P_INCOMPLETE_SPLIT(opaque))
1066 : : {
1268 andres@anarazel.de 1067 :UBC 0 : _bt_finish_split(rel, heaprel, rbuf, stack);
2741 pg@bowt.ie 1068 : 0 : rbuf = InvalidBuffer;
1069 : 0 : continue;
1070 : : }
1071 : :
2133 pg@bowt.ie 1072 [ + - ]:CBC 6696 : if (!P_IGNORE(opaque))
2741 1073 : 6696 : break;
2133 pg@bowt.ie 1074 [ # # ]:UBC 0 : if (P_RIGHTMOST(opaque))
2741 1075 [ # # ]: 0 : elog(ERROR, "fell off the end of index \"%s\"",
1076 : : RelationGetRelationName(rel));
1077 : :
2133 1078 : 0 : rblkno = opaque->btpo_next;
1079 : : }
1080 : : /* rbuf locked; unlock buf, update state for caller */
2741 pg@bowt.ie 1081 :CBC 6696 : _bt_relbuf(rel, insertstate->buf);
1082 : 6696 : insertstate->buf = rbuf;
1083 : 6696 : insertstate->bounds_valid = false;
7141 bruce@momjian.us 1084 : 6696 : }
1085 : :
1086 : : /*----------
1087 : : * _bt_insertonpg() -- Insert a tuple on a particular page in the index.
1088 : : *
1089 : : * This recursive procedure does the following things:
1090 : : *
1091 : : * + if postingoff != 0, splits existing posting list tuple
1092 : : * (since it overlaps with new 'itup' tuple).
1093 : : * + if necessary, splits the target page, using 'itup_key' for
1094 : : * suffix truncation on leaf pages (caller passes NULL for
1095 : : * non-leaf pages).
1096 : : * + inserts the new tuple (might be split from posting list).
1097 : : * + if the page was split, pops the parent stack, and finds the
1098 : : * right place to insert the new child pointer (by walking
1099 : : * right using information stored in the parent stack).
1100 : : * + invokes itself with the appropriate tuple for the right
1101 : : * child page on the parent.
1102 : : * + updates the metapage if a true root or fast root is split.
1103 : : *
1104 : : * On entry, we must have the correct buffer in which to do the
1105 : : * insertion, and the buffer must be pinned and write-locked. On return,
1106 : : * we will have dropped both the pin and the lock on the buffer.
1107 : : *
1108 : : * This routine only performs retail tuple insertions. 'itup' should
1109 : : * always be either a non-highkey leaf item, or a downlink (new high
1110 : : * key items are created indirectly, when a page is split). When
1111 : : * inserting to a non-leaf page, 'cbuf' is the left-sibling of the page
1112 : : * we're inserting the downlink for. This function will clear the
1113 : : * INCOMPLETE_SPLIT flag on it, and release the buffer.
1114 : : *----------
1115 : : */
1116 : : static void
1117 : 5148716 : _bt_insertonpg(Relation rel,
1118 : : Relation heaprel,
1119 : : BTScanInsert itup_key,
1120 : : Buffer buf,
1121 : : Buffer cbuf,
1122 : : BTStack stack,
1123 : : IndexTuple itup,
1124 : : Size itemsz,
1125 : : OffsetNumber newitemoff,
1126 : : int postingoff,
1127 : : bool split_only_page)
1128 : : {
1129 : : Page page;
1130 : : BTPageOpaque opaque;
1131 : : bool isleaf,
1132 : : isroot,
1133 : : isrightmost,
1134 : : isonly;
2398 pg@bowt.ie 1135 : 5148716 : IndexTuple oposting = NULL;
1136 : 5148716 : IndexTuple origitup = NULL;
1137 : 5148716 : IndexTuple nposting = NULL;
1138 : : XLogRecPtr recptr;
1139 : :
3805 kgrittn@postgresql.o 1140 : 5148716 : page = BufferGetPage(buf);
1633 michael@paquier.xyz 1141 : 5148716 : opaque = BTPageGetOpaque(page);
2133 pg@bowt.ie 1142 : 5148716 : isleaf = P_ISLEAF(opaque);
1143 : 5148716 : isroot = P_ISROOT(opaque);
1144 : 5148716 : isrightmost = P_RIGHTMOST(opaque);
1145 [ + + + + ]: 5148716 : isonly = P_LEFTMOST(opaque) && P_RIGHTMOST(opaque);
1146 : :
1147 : : /* child buffer must be given iff inserting on an internal page */
1148 [ - + ]: 5148716 : Assert(isleaf == !BufferIsValid(cbuf));
1149 : : /* tuple must have appropriate number of attributes */
1150 [ + + - + : 5148716 : Assert(!isleaf ||
- - ]
1151 : : BTreeTupleGetNAtts(itup, rel) ==
1152 : : IndexRelationGetNumberOfAttributes(rel));
1153 [ + + + - : 5148716 : Assert(isleaf ||
- + ]
1154 : : BTreeTupleGetNAtts(itup, rel) <=
1155 : : IndexRelationGetNumberOfKeyAttributes(rel));
2398 1156 [ - + ]: 5148716 : Assert(!BTreeTupleIsPosting(itup));
2379 1157 [ - + ]: 5148716 : Assert(MAXALIGN(IndexTupleSize(itup)) == itemsz);
1158 : : /* Caller must always finish incomplete split for us */
2133 1159 [ - + ]: 5148716 : Assert(!P_INCOMPLETE_SPLIT(opaque));
1160 : :
1161 : : /*
1162 : : * Every internal page should have exactly one negative infinity item at
1163 : : * all times. Only _bt_split() and _bt_newlevel() should add items that
1164 : : * become negative infinity items through truncation, since they're the
1165 : : * only routines that allocate new internal pages.
1166 : : */
1167 [ + + + + : 5148716 : Assert(isleaf || newitemoff > P_FIRSTDATAKEY(opaque));
- + ]
1168 : :
1169 : : /*
1170 : : * Do we need to split an existing posting list item?
1171 : : */
2398 1172 [ + + ]: 5148716 : if (postingoff != 0)
1173 : : {
1174 : 24534 : ItemId itemid = PageGetItemId(page, newitemoff);
1175 : :
1176 : : /*
1177 : : * The new tuple is a duplicate with a heap TID that falls inside the
1178 : : * range of an existing posting list tuple on a leaf page. Prepare to
1179 : : * split an existing posting list. Overwriting the posting list with
1180 : : * its post-split version is treated as an extra step in either the
1181 : : * insert or page split critical section.
1182 : : */
1789 1183 [ + - + - : 24534 : Assert(isleaf && itup_key->heapkeyspace && itup_key->allequalimage);
- + ]
2398 1184 : 24534 : oposting = (IndexTuple) PageGetItem(page, itemid);
1185 : :
1186 : : /*
1187 : : * postingoff value comes from earlier call to _bt_binsrch_posting().
1188 : : * Its binary search might think that a plain tuple must be a posting
1189 : : * list tuple that needs to be split. This can happen with corruption
1190 : : * involving an existing plain tuple that is a duplicate of the new
1191 : : * item, up to and including its table TID. Check for that here in
1192 : : * passing.
1193 : : *
1194 : : * Also verify that our caller has made sure that the existing posting
1195 : : * list tuple does not have its LP_DEAD bit set.
1196 : : */
1789 1197 [ + - - + ]: 24534 : if (!BTreeTupleIsPosting(oposting) || ItemIdIsDead(itemid))
1789 pg@bowt.ie 1198 [ # # ]:UBC 0 : ereport(ERROR,
1199 : : (errcode(ERRCODE_INDEX_CORRUPTED),
1200 : : errmsg_internal("table tid from new index tuple (%u,%u) overlaps with invalid duplicate tuple at offset %u of block %u in index \"%s\"",
1201 : : ItemPointerGetBlockNumber(&itup->t_tid),
1202 : : ItemPointerGetOffsetNumber(&itup->t_tid),
1203 : : newitemoff, BufferGetBlockNumber(buf),
1204 : : RelationGetRelationName(rel))));
1205 : :
1206 : : /* use a mutable copy of itup as our itup from here on */
2398 pg@bowt.ie 1207 :CBC 24534 : origitup = itup;
1208 : 24534 : itup = CopyIndexTuple(origitup);
1209 : 24534 : nposting = _bt_swap_posting(itup, oposting, postingoff);
1210 : : /* itup now contains rightmost/max TID from oposting */
1211 : :
1212 : : /* Alter offset so that newitem goes after posting list */
1213 : 24534 : newitemoff = OffsetNumberNext(newitemoff);
1214 : : }
1215 : :
1216 : : /*
1217 : : * Do we need to split the page to fit the item on it?
1218 : : *
1219 : : * Note: PageGetFreeSpace() subtracts sizeof(ItemIdData) from its result,
1220 : : * so this comparison is correct even though we appear to be accounting
1221 : : * only for the item and not for its line pointer.
1222 : : */
9557 tgl@sss.pgh.pa.us 1223 [ + + ]: 5148716 : if (PageGetFreeSpace(page) < itemsz)
1224 : : {
1225 : : Buffer rbuf;
1226 : :
2351 pg@bowt.ie 1227 [ - + ]: 15140 : Assert(!split_only_page);
1228 : :
1229 : : /* split the buffer into left and right halves */
1268 andres@anarazel.de 1230 : 15140 : rbuf = _bt_split(rel, heaprel, itup_key, buf, cbuf, newitemoff, itemsz,
1231 : : itup, origitup, nposting, postingoff);
5704 heikki.linnakangas@i 1232 : 15140 : PredicateLockPageSplit(rel,
1233 : : BufferGetBlockNumber(buf),
1234 : : BufferGetBlockNumber(rbuf));
1235 : :
1236 : : /*----------
1237 : : * By here,
1238 : : *
1239 : : * + our target page has been split;
1240 : : * + the original tuple has been inserted;
1241 : : * + we have write locks on both the old (left half)
1242 : : * and new (right half) buffers, after the split; and
1243 : : * + we know the key we want to insert into the parent
1244 : : * (it's the "high key" on the left child page).
1245 : : *
1246 : : * We're ready to do the parent insertion. We need to hold onto the
1247 : : * locks for the child pages until we locate the parent, but we can
1248 : : * at least release the lock on the right child before doing the
1249 : : * actual insertion. The lock on the left child will be released
1250 : : * last of all by parent insertion, where it is the 'cbuf' of parent
1251 : : * page.
1252 : : *----------
1253 : : */
1254 : : #ifdef USE_INJECTION_POINTS
292 1255 [ + + ]: 15140 : if (P_ISLEAF(opaque))
1256 : 14959 : INJECTION_POINT("nbtree-leave-leaf-split-incomplete", NULL);
1257 : : else
1258 : 181 : INJECTION_POINT("nbtree-leave-internal-split-incomplete", NULL);
1259 : : #endif
1260 : :
1268 andres@anarazel.de 1261 : 15138 : _bt_insert_parent(rel, heaprel, buf, rbuf, stack, isroot, isonly);
1262 : : }
1263 : : else
1264 : : {
8612 tgl@sss.pgh.pa.us 1265 : 5133576 : Buffer metabuf = InvalidBuffer;
1266 : 5133576 : Page metapg = NULL;
1267 : 5133576 : BTMetaPageData *metad = NULL;
1268 : : BlockNumber blockcache;
1269 : :
1270 : : /*
1271 : : * If we are doing this insert because we split a page that was the
1272 : : * only one on its tree level, but was not the root, it may have been
1273 : : * the "fast root". We need to ensure that the fast root link points
1274 : : * at or above the current page. We can safely acquire a lock on the
1275 : : * metapage here --- see comments for _bt_newlevel().
1276 : : */
2133 pg@bowt.ie 1277 [ + + ]: 5133576 : if (unlikely(split_only_page))
1278 : : {
2377 1279 [ - + ]: 16 : Assert(!isleaf);
1280 [ - + ]: 16 : Assert(BufferIsValid(cbuf));
1281 : :
1198 1282 : 16 : metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_WRITE);
3805 kgrittn@postgresql.o 1283 : 16 : metapg = BufferGetPage(metabuf);
8612 tgl@sss.pgh.pa.us 1284 : 16 : metad = BTPageGetMeta(metapg);
1285 : :
2034 pg@bowt.ie 1286 [ - + ]: 16 : if (metad->btm_fastlevel >= opaque->btpo_level)
1287 : : {
1288 : : /* no update wanted */
8612 tgl@sss.pgh.pa.us 1289 :UBC 0 : _bt_relbuf(rel, metabuf);
1290 : 0 : metabuf = InvalidBuffer;
1291 : : }
1292 : : }
1293 : :
1294 : : /* Do the update. No ereport(ERROR) until changes are logged */
8612 tgl@sss.pgh.pa.us 1295 :CBC 5133576 : START_CRIT_SECTION();
1296 : :
2398 pg@bowt.ie 1297 [ + + ]: 5133576 : if (postingoff != 0)
1298 : 24508 : memcpy(oposting, nposting, MAXALIGN(IndexTupleSize(nposting)));
1299 : :
328 peter@eisentraut.org 1300 [ - + ]: 5133576 : if (PageAddItem(page, itup, itemsz, newitemoff, false, false) == InvalidOffsetNumber)
5866 tgl@sss.pgh.pa.us 1301 [ # # ]:UBC 0 : elog(PANIC, "failed to add new item to block %u in index \"%s\"",
1302 : : BufferGetBlockNumber(buf), RelationGetRelationName(rel));
1303 : :
7478 tgl@sss.pgh.pa.us 1304 :CBC 5133576 : MarkBufferDirty(buf);
1305 : :
8612 1306 [ + + ]: 5133576 : if (BufferIsValid(metabuf))
1307 : : {
1308 : : /* upgrade meta-page if needed */
2741 pg@bowt.ie 1309 [ - + ]: 16 : if (metad->btm_version < BTREE_NOVAC_VERSION)
3091 teodor@sigaev.ru 1310 :UBC 0 : _bt_upgrademetapage(metapg);
2378 pg@bowt.ie 1311 :CBC 16 : metad->btm_fastroot = BufferGetBlockNumber(buf);
2034 1312 : 16 : metad->btm_fastlevel = opaque->btpo_level;
7478 tgl@sss.pgh.pa.us 1313 : 16 : MarkBufferDirty(metabuf);
1314 : : }
1315 : :
1316 : : /*
1317 : : * Clear INCOMPLETE_SPLIT flag on child if inserting the new item
1318 : : * finishes a split
1319 : : */
2351 pg@bowt.ie 1320 [ + + ]: 5133576 : if (!isleaf)
1321 : : {
3805 kgrittn@postgresql.o 1322 : 14129 : Page cpage = BufferGetPage(cbuf);
1633 michael@paquier.xyz 1323 : 14129 : BTPageOpaque cpageop = BTPageGetOpaque(cpage);
1324 : :
4569 heikki.linnakangas@i 1325 [ - + ]: 14129 : Assert(P_INCOMPLETE_SPLIT(cpageop));
1326 : 14129 : cpageop->btpo_flags &= ~BTP_INCOMPLETE_SPLIT;
1327 : 14129 : MarkBufferDirty(cbuf);
1328 : : }
1329 : :
1330 : : /* XLOG stuff */
5760 rhaas@postgresql.org 1331 [ + + + + : 5133576 : if (RelationNeedsWAL(rel))
+ + + + ]
8612 tgl@sss.pgh.pa.us 1332 : 4878622 : {
1333 : : xl_btree_insert xlrec;
1334 : : xl_btree_metadata xlmeta;
1335 : : uint8 xlinfo;
1336 : : uint16 upostingoff;
1337 : :
2378 pg@bowt.ie 1338 : 4878622 : xlrec.offnum = newitemoff;
1339 : :
4322 heikki.linnakangas@i 1340 : 4878622 : XLogBeginInsert();
586 peter@eisentraut.org 1341 : 4878622 : XLogRegisterData(&xlrec, SizeOfBtreeInsert);
1342 : :
2377 pg@bowt.ie 1343 [ + + + + ]: 4878622 : if (isleaf && postingoff == 0)
1344 : : {
1345 : : /* Simple leaf insert */
7465 tgl@sss.pgh.pa.us 1346 : 4840639 : xlinfo = XLOG_BTREE_INSERT_LEAF;
1347 : : }
2398 pg@bowt.ie 1348 [ + + ]: 37983 : else if (postingoff != 0)
1349 : : {
1350 : : /*
1351 : : * Leaf insert with posting list split. Must include
1352 : : * postingoff field before newitem/orignewitem.
1353 : : */
2350 1354 [ - + ]: 24508 : Assert(isleaf);
2398 1355 : 24508 : xlinfo = XLOG_BTREE_INSERT_POST;
1356 : : }
1357 : : else
1358 : : {
1359 : : /* Internal page insert, which finishes a split on cbuf */
7465 tgl@sss.pgh.pa.us 1360 : 13475 : xlinfo = XLOG_BTREE_INSERT_UPPER;
2351 pg@bowt.ie 1361 : 13475 : XLogRegisterBuffer(1, cbuf, REGBUF_STANDARD);
1362 : :
2350 1363 [ + + ]: 13475 : if (BufferIsValid(metabuf))
1364 : : {
1365 : : /* Actually, it's an internal page insert + meta update */
1366 : 16 : xlinfo = XLOG_BTREE_INSERT_META;
1367 : :
1368 [ - + ]: 16 : Assert(metad->btm_version >= BTREE_NOVAC_VERSION);
1369 : 16 : xlmeta.version = metad->btm_version;
1370 : 16 : xlmeta.root = metad->btm_root;
1371 : 16 : xlmeta.level = metad->btm_level;
1372 : 16 : xlmeta.fastroot = metad->btm_fastroot;
1373 : 16 : xlmeta.fastlevel = metad->btm_fastlevel;
2034 1374 : 16 : xlmeta.last_cleanup_num_delpages = metad->btm_last_cleanup_num_delpages;
2350 1375 : 16 : xlmeta.allequalimage = metad->btm_allequalimage;
1376 : :
1377 : 16 : XLogRegisterBuffer(2, metabuf,
1378 : : REGBUF_WILL_INIT | REGBUF_STANDARD);
586 peter@eisentraut.org 1379 : 16 : XLogRegisterBufData(2, &xlmeta,
1380 : : sizeof(xl_btree_metadata));
1381 : : }
1382 : : }
1383 : :
4322 heikki.linnakangas@i 1384 : 4878622 : XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
2398 pg@bowt.ie 1385 [ + + ]: 4878622 : if (postingoff == 0)
1386 : : {
1387 : : /* Just log itup from caller */
586 peter@eisentraut.org 1388 : 4854114 : XLogRegisterBufData(0, itup, IndexTupleSize(itup));
1389 : : }
1390 : : else
1391 : : {
1392 : : /*
1393 : : * Insert with posting list split (XLOG_BTREE_INSERT_POST
1394 : : * record) case.
1395 : : *
1396 : : * Log postingoff. Also log origitup, not itup. REDO routine
1397 : : * must reconstruct final itup (as well as nposting) using
1398 : : * _bt_swap_posting().
1399 : : */
2334 pg@bowt.ie 1400 : 24508 : upostingoff = postingoff;
1401 : :
586 peter@eisentraut.org 1402 : 24508 : XLogRegisterBufData(0, &upostingoff, sizeof(uint16));
1403 : 24508 : XLogRegisterBufData(0, origitup,
2398 pg@bowt.ie 1404 : 24508 : IndexTupleSize(origitup));
1405 : : }
1406 : :
4322 heikki.linnakangas@i 1407 : 4878622 : recptr = XLogInsert(RM_BTREE_ID, xlinfo);
1408 : : }
1409 : : else
191 pg@bowt.ie 1410 : 254954 : recptr = XLogGetFakeLSN(rel);
1411 : :
1412 [ + + ]: 5133576 : if (BufferIsValid(metabuf))
1413 : 16 : PageSetLSN(metapg, recptr);
1414 [ + + ]: 5133576 : if (!isleaf)
1415 : 14129 : PageSetLSN(BufferGetPage(cbuf), recptr);
1416 : :
1417 : 5133576 : PageSetLSN(page, recptr);
1418 : :
8612 tgl@sss.pgh.pa.us 1419 [ - + ]: 5133576 : END_CRIT_SECTION();
1420 : :
1421 : : /* Release subsidiary buffers */
1422 [ + + ]: 5133576 : if (BufferIsValid(metabuf))
7478 1423 : 16 : _bt_relbuf(rel, metabuf);
2351 pg@bowt.ie 1424 [ + + ]: 5133576 : if (!isleaf)
4569 heikki.linnakangas@i 1425 : 14129 : _bt_relbuf(rel, cbuf);
1426 : :
1427 : : /*
1428 : : * Cache the block number if this is the rightmost leaf page. Cache
1429 : : * may be used by a future inserter within _bt_search_insert().
1430 : : */
2377 pg@bowt.ie 1431 : 5133576 : blockcache = InvalidBlockNumber;
2133 1432 [ + + + + : 5133576 : if (isrightmost && isleaf && !isroot)
+ + ]
2377 1433 : 3068812 : blockcache = BufferGetBlockNumber(buf);
1434 : :
1435 : : /* Release buffer for insertion target block */
7478 tgl@sss.pgh.pa.us 1436 : 5133576 : _bt_relbuf(rel, buf);
1437 : :
1438 : : /*
1439 : : * If we decided to cache the insertion target block before releasing
1440 : : * its buffer lock, then cache it now. Check the height of the tree
1441 : : * first, though. We don't go for the optimization with small
1442 : : * indexes. Defer final check to this point to ensure that we don't
1443 : : * call _bt_getrootheight while holding a buffer lock.
1444 : : */
2377 pg@bowt.ie 1445 [ + + + + ]: 8202388 : if (BlockNumberIsValid(blockcache) &&
1198 1446 : 3068812 : _bt_getrootheight(rel) >= BTREE_FASTPATH_MIN_LEVEL)
2377 1447 : 35507 : RelationSetTargetBlock(rel, blockcache);
1448 : : }
1449 : :
1450 : : /* be tidy */
2398 1451 [ + + ]: 5148713 : if (postingoff != 0)
1452 : : {
1453 : : /* itup is actually a modified copy of caller's original */
1454 : 24534 : pfree(nposting);
1455 : 24534 : pfree(itup);
1456 : : }
11030 scrappy@hub.org 1457 : 5148713 : }
1458 : :
1459 : : /*
1460 : : * _bt_split() -- split a page in the btree.
1461 : : *
1462 : : * On entry, buf is the page to split, and is pinned and write-locked.
1463 : : * newitemoff etc. tell us about the new item that must be inserted
1464 : : * along with the data from the original page.
1465 : : *
1466 : : * itup_key is used for suffix truncation on leaf pages (internal
1467 : : * page callers pass NULL). When splitting a non-leaf page, 'cbuf'
1468 : : * is the left-sibling of the page we're inserting the downlink for.
1469 : : * This function will clear the INCOMPLETE_SPLIT flag on it, and
1470 : : * release the buffer.
1471 : : *
1472 : : * orignewitem, nposting, and postingoff are needed when an insert of
1473 : : * orignewitem results in both a posting list split and a page split.
1474 : : * These extra posting list split details are used here in the same
1475 : : * way as they are used in the more common case where a posting list
1476 : : * split does not coincide with a page split. We need to deal with
1477 : : * posting list splits directly in order to ensure that everything
1478 : : * that follows from the insert of orignewitem is handled as a single
1479 : : * atomic operation (though caller's insert of a new pivot/downlink
1480 : : * into parent page will still be a separate operation). See
1481 : : * nbtree/README for details on the design of posting list splits.
1482 : : *
1483 : : * Returns the new right sibling of buf, pinned and write-locked.
1484 : : * The pin and lock on buf are maintained.
1485 : : */
1486 : : static Buffer
1268 andres@anarazel.de 1487 : 15140 : _bt_split(Relation rel, Relation heaprel, BTScanInsert itup_key, Buffer buf,
1488 : : Buffer cbuf, OffsetNumber newitemoff, Size newitemsz, IndexTuple newitem,
1489 : : IndexTuple orignewitem, IndexTuple nposting, uint16 postingoff)
1490 : : {
1491 : : Buffer rbuf;
1492 : : Page origpage;
1493 : : Page leftpage,
1494 : : rightpage;
1495 : : PGAlignedBlock leftpage_buf,
1496 : : rightpage_buf;
1497 : : BlockNumber origpagenumber,
1498 : : rightpagenumber;
1499 : : BTPageOpaque ropaque,
1500 : : lopaque,
1501 : : oopaque;
8611 tgl@sss.pgh.pa.us 1502 : 15140 : Buffer sbuf = InvalidBuffer;
1503 : 15140 : Page spage = NULL;
1504 : 15140 : BTPageOpaque sopaque = NULL;
1505 : : Size itemsz;
1506 : : ItemId itemid;
1507 : : IndexTuple firstright,
1508 : : lefthighkey;
1509 : : OffsetNumber firstrightoff;
1510 : : OffsetNumber afterleftoff,
1511 : : afterrightoff,
1512 : : minusinfoff;
1513 : : OffsetNumber origpagepostingoff;
1514 : : OffsetNumber maxoff;
1515 : : OffsetNumber i;
1516 : : bool newitemonleft,
1517 : : isleaf,
1518 : : isrightmost;
1519 : : XLogRecPtr recptr;
1520 : :
1521 : : /*
1522 : : * origpage is the original page to be split. leftpage is a temporary
1523 : : * buffer that receives the left-sibling data, which will be copied back
1524 : : * into origpage on success. rightpage is the new page that will receive
1525 : : * the right-sibling data.
1526 : : *
1527 : : * leftpage is allocated after choosing a split point. rightpage's new
1528 : : * buffer isn't acquired until after leftpage is initialized and has new
1529 : : * high key, the last point where splitting the page may fail (barring
1530 : : * corruption). Failing before acquiring new buffer won't have lasting
1531 : : * consequences, since origpage won't have been modified and leftpage is
1532 : : * only workspace.
1533 : : */
3805 kgrittn@postgresql.o 1534 : 15140 : origpage = BufferGetPage(buf);
1633 michael@paquier.xyz 1535 : 15140 : oopaque = BTPageGetOpaque(origpage);
2351 pg@bowt.ie 1536 : 15140 : isleaf = P_ISLEAF(oopaque);
1537 : 15140 : isrightmost = P_RIGHTMOST(oopaque);
1538 : 15140 : maxoff = PageGetMaxOffsetNumber(origpage);
5866 tgl@sss.pgh.pa.us 1539 : 15140 : origpagenumber = BufferGetBlockNumber(buf);
1540 : :
1541 : : /*
1542 : : * Choose a point to split origpage at.
1543 : : *
1544 : : * A split point can be thought of as a point _between_ two existing data
1545 : : * items on origpage (the lastleft and firstright tuples), provided you
1546 : : * pretend that the new item that didn't fit is already on origpage.
1547 : : *
1548 : : * Since origpage does not actually contain newitem, the representation of
1549 : : * split points needs to work with two boundary cases: splits where
1550 : : * newitem is lastleft, and splits where newitem is firstright.
1551 : : * newitemonleft resolves the ambiguity that would otherwise exist when
1552 : : * newitemoff == firstrightoff. In all other cases it's clear which side
1553 : : * of the split every tuple goes on from context. newitemonleft is
1554 : : * usually (but not always) redundant information.
1555 : : *
1556 : : * firstrightoff is supposed to be an origpage offset number, but it's
1557 : : * possible that its value will be maxoff+1, which is "past the end" of
1558 : : * origpage. This happens in the rare case where newitem goes after all
1559 : : * existing items (i.e. newitemoff is maxoff+1) and we end up splitting
1560 : : * origpage at the point that leaves newitem alone on new right page. Any
1561 : : * "!newitemonleft && newitemoff == firstrightoff" split point makes
1562 : : * newitem the firstright tuple, though, so this case isn't a special
1563 : : * case.
1564 : : */
2351 pg@bowt.ie 1565 : 15140 : firstrightoff = _bt_findsplitloc(rel, origpage, newitemoff, newitemsz,
1566 : : newitem, &newitemonleft);
1567 : :
1568 : : /* Use temporary buffer for leftpage */
359 michael@paquier.xyz 1569 : 15140 : leftpage = leftpage_buf.data;
2687 pg@bowt.ie 1570 : 15140 : _bt_pageinit(leftpage, BufferGetPageSize(buf));
1633 michael@paquier.xyz 1571 : 15140 : lopaque = BTPageGetOpaque(leftpage);
1572 : :
1573 : : /*
1574 : : * leftpage won't be the root when we're done. Also, clear the SPLIT_END
1575 : : * and HAS_GARBAGE flags.
1576 : : */
9482 vadim4o@yahoo.com 1577 : 15140 : lopaque->btpo_flags = oopaque->btpo_flags;
7362 tgl@sss.pgh.pa.us 1578 : 15140 : lopaque->btpo_flags &= ~(BTP_ROOT | BTP_SPLIT_END | BTP_HAS_GARBAGE);
1579 : : /* set flag in leftpage indicating that rightpage has no downlink yet */
4569 heikki.linnakangas@i 1580 : 15140 : lopaque->btpo_flags |= BTP_INCOMPLETE_SPLIT;
10605 bruce@momjian.us 1581 : 15140 : lopaque->btpo_prev = oopaque->btpo_prev;
1582 : : /* handle btpo_next after rightpage buffer acquired */
2034 pg@bowt.ie 1583 : 15140 : lopaque->btpo_level = oopaque->btpo_level;
1584 : : /* handle btpo_cycleid after rightpage buffer acquired */
1585 : :
1586 : : /*
1587 : : * Copy the original page's LSN into leftpage, which will become the
1588 : : * updated version of the page. We need this because XLogInsert will
1589 : : * examine the LSN and possibly dump it in a page image.
1590 : : */
2687 1591 : 15140 : PageSetLSN(leftpage, PageGetLSN(origpage));
1592 : :
1593 : : /*
1594 : : * Determine page offset number of existing overlapped-with-orignewitem
1595 : : * posting list when it is necessary to perform a posting list split in
1596 : : * passing. Note that newitem was already changed by caller (newitem no
1597 : : * longer has the orignewitem TID).
1598 : : *
1599 : : * This page offset number (origpagepostingoff) will be used to pretend
1600 : : * that the posting split has already taken place, even though the
1601 : : * required modifications to origpage won't occur until we reach the
1602 : : * critical section. The lastleft and firstright tuples of our page split
1603 : : * point should, in effect, come from an imaginary version of origpage
1604 : : * that has the nposting tuple instead of the original posting list tuple.
1605 : : *
1606 : : * Note: _bt_findsplitloc() should have compensated for coinciding posting
1607 : : * list splits in just the same way, at least in theory. It doesn't
1608 : : * bother with that, though. In practice it won't affect its choice of
1609 : : * split point.
1610 : : */
2398 1611 : 15140 : origpagepostingoff = InvalidOffsetNumber;
1612 [ + + ]: 15140 : if (postingoff != 0)
1613 : : {
1614 [ - + ]: 26 : Assert(isleaf);
1615 [ - + ]: 26 : Assert(ItemPointerCompare(&orignewitem->t_tid,
1616 : : &newitem->t_tid) < 0);
1617 [ - + ]: 26 : Assert(BTreeTupleIsPosting(nposting));
1618 : 26 : origpagepostingoff = OffsetNumberPrev(newitemoff);
1619 : : }
1620 : :
1621 : : /*
1622 : : * The high key for the new left page is a possibly-truncated copy of
1623 : : * firstright on the leaf level (it's "firstright itself" on internal
1624 : : * pages; see !isleaf comments below). This may seem to be contrary to
1625 : : * Lehman & Yao's approach of using a copy of lastleft as the new high key
1626 : : * when splitting on the leaf level. It isn't, though.
1627 : : *
1628 : : * Suffix truncation will leave the left page's high key fully equal to
1629 : : * lastleft when lastleft and firstright are equal prior to heap TID (that
1630 : : * is, the tiebreaker TID value comes from lastleft). It isn't actually
1631 : : * necessary for a new leaf high key to be a copy of lastleft for the L&Y
1632 : : * "subtree" invariant to hold. It's sufficient to make sure that the new
1633 : : * leaf high key is strictly less than firstright, and greater than or
1634 : : * equal to (not necessarily equal to) lastleft. In other words, when
1635 : : * suffix truncation isn't possible during a leaf page split, we take
1636 : : * L&Y's exact approach to generating a new high key for the left page.
1637 : : * (Actually, that is slightly inaccurate. We don't just use a copy of
1638 : : * lastleft. A tuple with all the keys from firstright but the max heap
1639 : : * TID from lastleft is used, to avoid introducing a special case.)
1640 : : */
2351 1641 [ + + + + ]: 15140 : if (!newitemonleft && newitemoff == firstrightoff)
1642 : : {
1643 : : /* incoming tuple becomes firstright */
9557 tgl@sss.pgh.pa.us 1644 : 25 : itemsz = newitemsz;
2351 pg@bowt.ie 1645 : 25 : firstright = newitem;
1646 : : }
1647 : : else
1648 : : {
1649 : : /* existing item at firstrightoff becomes firstright */
1650 : 15115 : itemid = PageGetItemId(origpage, firstrightoff);
9557 tgl@sss.pgh.pa.us 1651 : 15115 : itemsz = ItemIdGetLength(itemid);
2351 pg@bowt.ie 1652 : 15115 : firstright = (IndexTuple) PageGetItem(origpage, itemid);
1653 [ + + ]: 15115 : if (firstrightoff == origpagepostingoff)
1654 : 2 : firstright = nposting;
1655 : : }
1656 : :
1657 [ + + ]: 15140 : if (isleaf)
1658 : : {
1659 : : IndexTuple lastleft;
1660 : :
1661 : : /* Attempt suffix truncation for leaf page splits */
1662 [ + + + + ]: 14959 : if (newitemonleft && newitemoff == firstrightoff)
1663 : : {
1664 : : /* incoming tuple becomes lastleft */
2741 1665 : 256 : lastleft = newitem;
1666 : : }
1667 : : else
1668 : : {
1669 : : OffsetNumber lastleftoff;
1670 : :
1671 : : /* existing item before firstrightoff becomes lastleft */
2351 1672 : 14703 : lastleftoff = OffsetNumberPrev(firstrightoff);
2741 1673 [ + + - + ]: 14703 : Assert(lastleftoff >= P_FIRSTDATAKEY(oopaque));
1674 : 14703 : itemid = PageGetItemId(origpage, lastleftoff);
1675 : 14703 : lastleft = (IndexTuple) PageGetItem(origpage, itemid);
2398 1676 [ + + ]: 14703 : if (lastleftoff == origpagepostingoff)
1677 : 3 : lastleft = nposting;
1678 : : }
1679 : :
2351 1680 : 14959 : lefthighkey = _bt_truncate(rel, lastleft, firstright, itup_key);
1681 : 14959 : itemsz = IndexTupleSize(lefthighkey);
1682 : : }
1683 : : else
1684 : : {
1685 : : /*
1686 : : * Don't perform suffix truncation on a copy of firstright to make
1687 : : * left page high key for internal page splits. Must use firstright
1688 : : * as new high key directly.
1689 : : *
1690 : : * Each distinct separator key value originates as a leaf level high
1691 : : * key; all other separator keys/pivot tuples are copied from one
1692 : : * level down. A separator key in a grandparent page must be
1693 : : * identical to high key in rightmost parent page of the subtree to
1694 : : * its left, which must itself be identical to high key in rightmost
1695 : : * child page of that same subtree (this even applies to separator
1696 : : * from grandparent's high key). There must always be an unbroken
1697 : : * "seam" of identical separator keys that guide index scans at every
1698 : : * level, starting from the grandparent. That's why suffix truncation
1699 : : * is unsafe here.
1700 : : *
1701 : : * Internal page splits will truncate firstright into a "negative
1702 : : * infinity" data item when it gets inserted on the new right page
1703 : : * below, though. This happens during the call to _bt_pgaddtup() for
1704 : : * the new first data item for right page. Do not confuse this
1705 : : * mechanism with suffix truncation. It is just a convenient way of
1706 : : * implementing page splits that split the internal page "inside"
1707 : : * firstright. The lefthighkey separator key cannot appear a second
1708 : : * time in the right page (only firstright's downlink goes in right
1709 : : * page).
1710 : : */
1711 : 181 : lefthighkey = firstright;
1712 : : }
1713 : :
1714 : : /*
1715 : : * Add new high key to leftpage
1716 : : */
1717 : 15140 : afterleftoff = P_HIKEY;
1718 : :
1719 [ + - - + ]: 15140 : Assert(BTreeTupleGetNAtts(lefthighkey, rel) > 0);
1720 [ + - - + ]: 15140 : Assert(BTreeTupleGetNAtts(lefthighkey, rel) <=
1721 : : IndexRelationGetNumberOfKeyAttributes(rel));
1722 [ - + ]: 15140 : Assert(itemsz == MAXALIGN(IndexTupleSize(lefthighkey)));
328 peter@eisentraut.org 1723 [ - + ]: 15140 : if (PageAddItem(leftpage, lefthighkey, itemsz, afterleftoff, false, false) == InvalidOffsetNumber)
2351 pg@bowt.ie 1724 [ # # ]:UBC 0 : elog(ERROR, "failed to add high key to the left sibling"
1725 : : " while splitting block %u of index \"%s\"",
1726 : : origpagenumber, RelationGetRelationName(rel));
2351 pg@bowt.ie 1727 :CBC 15140 : afterleftoff = OffsetNumberNext(afterleftoff);
1728 : :
1729 : : /*
1730 : : * Acquire a new right page to split into, now that left page has a new
1731 : : * high key.
1732 : : *
1733 : : * To not confuse future VACUUM operations, we zero the right page and
1734 : : * work on an in-memory copy of it before writing WAL, then copy its
1735 : : * contents back to the actual page once we start the critical section
1736 : : * work. This simplifies the split work, so as there is no need to zero
1737 : : * the right page before throwing an error.
1738 : : */
1198 1739 : 15140 : rbuf = _bt_allocbuf(rel, heaprel);
359 michael@paquier.xyz 1740 : 15140 : rightpage = rightpage_buf.data;
1741 : :
1742 : : /*
1743 : : * Copy the contents of the right page into its temporary location, and
1744 : : * zero the original space.
1745 : : */
1746 : 15140 : memcpy(rightpage, BufferGetPage(rbuf), BLCKSZ);
1747 : 15140 : memset(BufferGetPage(rbuf), 0, BLCKSZ);
2687 pg@bowt.ie 1748 : 15140 : rightpagenumber = BufferGetBlockNumber(rbuf);
1749 : : /* rightpage was initialized by _bt_allocbuf */
1633 michael@paquier.xyz 1750 : 15140 : ropaque = BTPageGetOpaque(rightpage);
1751 : :
1752 : : /*
1753 : : * Finish off remaining leftpage special area fields. They cannot be set
1754 : : * before both origpage (leftpage) and rightpage buffers are acquired and
1755 : : * locked.
1756 : : *
1757 : : * btpo_cycleid is only used with leaf pages, though we set it here in all
1758 : : * cases just to be consistent.
1759 : : */
2687 pg@bowt.ie 1760 : 15140 : lopaque->btpo_next = rightpagenumber;
1761 : 15140 : lopaque->btpo_cycleid = _bt_vacuum_cycleid(rel);
1762 : :
1763 : : /*
1764 : : * rightpage won't be the root when we're done. Also, clear the SPLIT_END
1765 : : * and HAS_GARBAGE flags.
1766 : : */
1767 : 15140 : ropaque->btpo_flags = oopaque->btpo_flags;
1768 : 15140 : ropaque->btpo_flags &= ~(BTP_ROOT | BTP_SPLIT_END | BTP_HAS_GARBAGE);
1769 : 15140 : ropaque->btpo_prev = origpagenumber;
1770 : 15140 : ropaque->btpo_next = oopaque->btpo_next;
2034 1771 : 15140 : ropaque->btpo_level = oopaque->btpo_level;
2687 1772 : 15140 : ropaque->btpo_cycleid = lopaque->btpo_cycleid;
1773 : :
1774 : : /*
1775 : : * Add new high key to rightpage where necessary.
1776 : : *
1777 : : * If the page we're splitting is not the rightmost page at its level in
1778 : : * the tree, then the first entry on the page is the high key from
1779 : : * origpage.
1780 : : */
2351 1781 : 15140 : afterrightoff = P_HIKEY;
1782 : :
1783 [ + + ]: 15140 : if (!isrightmost)
1784 : : {
1785 : : IndexTuple righthighkey;
1786 : :
2687 1787 : 5721 : itemid = PageGetItemId(origpage, P_HIKEY);
1788 : 5721 : itemsz = ItemIdGetLength(itemid);
2351 1789 : 5721 : righthighkey = (IndexTuple) PageGetItem(origpage, itemid);
1790 [ + - - + ]: 5721 : Assert(BTreeTupleGetNAtts(righthighkey, rel) > 0);
1791 [ + - - + ]: 5721 : Assert(BTreeTupleGetNAtts(righthighkey, rel) <=
1792 : : IndexRelationGetNumberOfKeyAttributes(rel));
328 peter@eisentraut.org 1793 [ - + ]: 5721 : if (PageAddItem(rightpage, righthighkey, itemsz, afterrightoff, false, false) == InvalidOffsetNumber)
1794 : : {
2351 pg@bowt.ie 1795 [ # # ]:UBC 0 : elog(ERROR, "failed to add high key to the right sibling"
1796 : : " while splitting block %u of index \"%s\"",
1797 : : origpagenumber, RelationGetRelationName(rel));
1798 : : }
2351 pg@bowt.ie 1799 :CBC 5721 : afterrightoff = OffsetNumberNext(afterrightoff);
1800 : : }
1801 : :
1802 : : /*
1803 : : * Internal page splits truncate first data item on right page -- it
1804 : : * becomes "minus infinity" item for the page. Set this up here.
1805 : : */
1806 : 15140 : minusinfoff = InvalidOffsetNumber;
1807 [ + + ]: 15140 : if (!isleaf)
1808 : 181 : minusinfoff = afterrightoff;
1809 : :
1810 : : /*
1811 : : * Now transfer all the data items (non-pivot tuples in isleaf case, or
1812 : : * additional pivot tuples in !isleaf case) to the appropriate page.
1813 : : *
1814 : : * Note: we *must* insert at least the right page's items in item-number
1815 : : * order, for the benefit of _bt_restore_page().
1816 : : */
9557 tgl@sss.pgh.pa.us 1817 [ + + + + ]: 4737945 : for (i = P_FIRSTDATAKEY(oopaque); i <= maxoff; i = OffsetNumberNext(i))
1818 : : {
1819 : : IndexTuple dataitem;
1820 : :
10605 bruce@momjian.us 1821 : 4722805 : itemid = PageGetItemId(origpage, i);
1822 : 4722805 : itemsz = ItemIdGetLength(itemid);
2351 pg@bowt.ie 1823 : 4722805 : dataitem = (IndexTuple) PageGetItem(origpage, itemid);
1824 : :
1825 : : /* replace original item with nposting due to posting split? */
2398 1826 [ + + ]: 4722805 : if (i == origpagepostingoff)
1827 : : {
2351 1828 [ - + ]: 26 : Assert(BTreeTupleIsPosting(dataitem));
2398 1829 [ - + ]: 26 : Assert(itemsz == MAXALIGN(IndexTupleSize(nposting)));
2351 1830 : 26 : dataitem = nposting;
1831 : : }
1832 : :
1833 : : /* does new item belong before this one? */
2398 1834 [ + + ]: 4722779 : else if (i == newitemoff)
1835 : : {
9557 tgl@sss.pgh.pa.us 1836 [ + + ]: 8004 : if (newitemonleft)
1837 : : {
2351 pg@bowt.ie 1838 [ - + ]: 2214 : Assert(newitemoff <= firstrightoff);
1839 [ - + ]: 2214 : if (!_bt_pgaddtup(leftpage, newitemsz, newitem, afterleftoff,
1840 : : false))
1841 : : {
5866 tgl@sss.pgh.pa.us 1842 [ # # ]:UBC 0 : elog(ERROR, "failed to add new item to the left sibling"
1843 : : " while splitting block %u of index \"%s\"",
1844 : : origpagenumber, RelationGetRelationName(rel));
1845 : : }
2351 pg@bowt.ie 1846 :CBC 2214 : afterleftoff = OffsetNumberNext(afterleftoff);
1847 : : }
1848 : : else
1849 : : {
1850 [ - + ]: 5790 : Assert(newitemoff >= firstrightoff);
1851 [ - + ]: 5790 : if (!_bt_pgaddtup(rightpage, newitemsz, newitem, afterrightoff,
1852 : : afterrightoff == minusinfoff))
1853 : : {
5866 tgl@sss.pgh.pa.us 1854 [ # # ]:UBC 0 : elog(ERROR, "failed to add new item to the right sibling"
1855 : : " while splitting block %u of index \"%s\"",
1856 : : origpagenumber, RelationGetRelationName(rel));
1857 : : }
2351 pg@bowt.ie 1858 :CBC 5790 : afterrightoff = OffsetNumberNext(afterrightoff);
1859 : : }
1860 : : }
1861 : :
1862 : : /* decide which page to put it on */
1863 [ + + ]: 4722805 : if (i < firstrightoff)
1864 : : {
1865 [ - + ]: 3691675 : if (!_bt_pgaddtup(leftpage, itemsz, dataitem, afterleftoff, false))
1866 : : {
5866 tgl@sss.pgh.pa.us 1867 [ # # ]:UBC 0 : elog(ERROR, "failed to add old item to the left sibling"
1868 : : " while splitting block %u of index \"%s\"",
1869 : : origpagenumber, RelationGetRelationName(rel));
1870 : : }
2351 pg@bowt.ie 1871 :CBC 3691675 : afterleftoff = OffsetNumberNext(afterleftoff);
1872 : : }
1873 : : else
1874 : : {
1875 [ - + ]: 1031130 : if (!_bt_pgaddtup(rightpage, itemsz, dataitem, afterrightoff,
1876 : : afterrightoff == minusinfoff))
1877 : : {
5866 tgl@sss.pgh.pa.us 1878 [ # # ]:UBC 0 : elog(ERROR, "failed to add old item to the right sibling"
1879 : : " while splitting block %u of index \"%s\"",
1880 : : origpagenumber, RelationGetRelationName(rel));
1881 : : }
2351 pg@bowt.ie 1882 :CBC 1031130 : afterrightoff = OffsetNumberNext(afterrightoff);
1883 : : }
1884 : : }
1885 : :
1886 : : /* Handle case where newitem goes at the end of rightpage */
9557 tgl@sss.pgh.pa.us 1887 [ + + ]: 15140 : if (i <= newitemoff)
1888 : : {
1889 : : /*
1890 : : * Can't have newitemonleft here; that would imply we were told to put
1891 : : * *everything* on the left page, which cannot fit (if it could, we'd
1892 : : * not be splitting the page).
1893 : : */
2351 pg@bowt.ie 1894 [ + - - + ]: 7136 : Assert(!newitemonleft && newitemoff == maxoff + 1);
1895 [ - + ]: 7136 : if (!_bt_pgaddtup(rightpage, newitemsz, newitem, afterrightoff,
1896 : : afterrightoff == minusinfoff))
1897 : : {
5866 tgl@sss.pgh.pa.us 1898 [ # # ]:UBC 0 : elog(ERROR, "failed to add new item to the right sibling"
1899 : : " while splitting block %u of index \"%s\"",
1900 : : origpagenumber, RelationGetRelationName(rel));
1901 : : }
2351 pg@bowt.ie 1902 :CBC 7136 : afterrightoff = OffsetNumberNext(afterrightoff);
1903 : : }
1904 : :
1905 : : /*
1906 : : * We have to grab the original right sibling (if any) and update its prev
1907 : : * link. We are guaranteed that this is deadlock-free, since we couple
1908 : : * the locks in the standard order: left to right.
1909 : : */
1910 [ + + ]: 15140 : if (!isrightmost)
1911 : : {
1198 1912 : 5721 : sbuf = _bt_getbuf(rel, oopaque->btpo_next, BT_WRITE);
3805 kgrittn@postgresql.o 1913 : 5721 : spage = BufferGetPage(sbuf);
1633 michael@paquier.xyz 1914 : 5721 : sopaque = BTPageGetOpaque(spage);
5866 tgl@sss.pgh.pa.us 1915 [ - + ]: 5721 : if (sopaque->btpo_prev != origpagenumber)
1916 : : {
2607 peter@eisentraut.org 1917 [ # # ]:UBC 0 : ereport(ERROR,
1918 : : (errcode(ERRCODE_INDEX_CORRUPTED),
1919 : : errmsg_internal("right sibling's left-link doesn't match: "
1920 : : "block %u links to %u instead of expected %u in index \"%s\"",
1921 : : oopaque->btpo_next, sopaque->btpo_prev, origpagenumber,
1922 : : RelationGetRelationName(rel))));
1923 : : }
1924 : :
1925 : : /*
1926 : : * Check to see if we can set the SPLIT_END flag in the right-hand
1927 : : * split page; this can save some I/O for vacuum since it need not
1928 : : * proceed to the right sibling. We can set the flag if the right
1929 : : * sibling has a different cycleid: that means it could not be part of
1930 : : * a group of pages that were all split off from the same ancestor
1931 : : * page. If you're confused, imagine that page A splits to A B and
1932 : : * then again, yielding A C B, while vacuum is in progress. Tuples
1933 : : * originally in A could now be in either B or C, hence vacuum must
1934 : : * examine both pages. But if D, our right sibling, has a different
1935 : : * cycleid then it could not contain any tuples that were in A when
1936 : : * the vacuum started.
1937 : : */
7440 tgl@sss.pgh.pa.us 1938 [ + + ]:CBC 5721 : if (sopaque->btpo_cycleid != ropaque->btpo_cycleid)
1939 : 1 : ropaque->btpo_flags |= BTP_SPLIT_END;
1940 : : }
1941 : :
1942 : : /*
1943 : : * Right sibling is locked, new siblings are prepared, but original page
1944 : : * is not updated yet.
1945 : : *
1946 : : * NO EREPORT(ERROR) till right sibling is updated. We can get away with
1947 : : * not starting the critical section till here because we haven't been
1948 : : * scribbling on the original page yet; see comments above.
1949 : : */
9382 1950 : 15140 : START_CRIT_SECTION();
1951 : :
1952 : : /*
1953 : : * By here, the original data page has been split into two new halves, and
1954 : : * these are correct. The algorithm requires that the left page never
1955 : : * move during a split, so we copy the new left page back on top of the
1956 : : * original. We need to do this before writing the WAL record, so that
1957 : : * XLogInsert can WAL log an image of the page if necessary.
1958 : : */
359 michael@paquier.xyz 1959 : 15140 : memcpy(origpage, leftpage, BLCKSZ);
1960 : : /* leftpage, lopaque must not be used below here */
1961 : :
1962 : : /*
1963 : : * Move the contents of the right page from its temporary location to the
1964 : : * destination buffer, before writing the WAL record. Unlike the left
1965 : : * page, the right page and its opaque area are still needed to complete
1966 : : * the update of the page, so reinitialize them.
1967 : : */
1968 : 15140 : rightpage = BufferGetPage(rbuf);
1969 : 15140 : memcpy(rightpage, rightpage_buf.data, BLCKSZ);
1970 : 15140 : ropaque = BTPageGetOpaque(rightpage);
1971 : :
7102 tgl@sss.pgh.pa.us 1972 : 15140 : MarkBufferDirty(buf);
1973 : 15140 : MarkBufferDirty(rbuf);
1974 : :
2351 pg@bowt.ie 1975 [ + + ]: 15140 : if (!isrightmost)
1976 : : {
5866 tgl@sss.pgh.pa.us 1977 : 5721 : sopaque->btpo_prev = rightpagenumber;
7102 1978 : 5721 : MarkBufferDirty(sbuf);
1979 : : }
1980 : :
1981 : : /*
1982 : : * Clear INCOMPLETE_SPLIT flag on child if inserting the new item finishes
1983 : : * a split
1984 : : */
4569 heikki.linnakangas@i 1985 [ + + ]: 15140 : if (!isleaf)
1986 : : {
3805 kgrittn@postgresql.o 1987 : 181 : Page cpage = BufferGetPage(cbuf);
1633 michael@paquier.xyz 1988 : 181 : BTPageOpaque cpageop = BTPageGetOpaque(cpage);
1989 : :
4569 heikki.linnakangas@i 1990 : 181 : cpageop->btpo_flags &= ~BTP_INCOMPLETE_SPLIT;
1991 : 181 : MarkBufferDirty(cbuf);
1992 : : }
1993 : :
1994 : : /* XLOG stuff */
5760 rhaas@postgresql.org 1995 [ + + + + : 15140 : if (RelationNeedsWAL(rel))
+ - + - ]
9482 vadim4o@yahoo.com 1996 : 14467 : {
1997 : : xl_btree_split xlrec;
1998 : : uint8 xlinfo;
1999 : :
2034 pg@bowt.ie 2000 : 14467 : xlrec.level = ropaque->btpo_level;
2001 : : /* See comments below on newitem, orignewitem, and posting lists */
2351 2002 : 14467 : xlrec.firstrightoff = firstrightoff;
4322 heikki.linnakangas@i 2003 : 14467 : xlrec.newitemoff = newitemoff;
2398 pg@bowt.ie 2004 : 14467 : xlrec.postingoff = 0;
2351 2005 [ + + + + ]: 14467 : if (postingoff != 0 && origpagepostingoff < firstrightoff)
2398 2006 : 10 : xlrec.postingoff = postingoff;
2007 : :
4322 heikki.linnakangas@i 2008 : 14467 : XLogBeginInsert();
586 peter@eisentraut.org 2009 : 14467 : XLogRegisterData(&xlrec, SizeOfBtreeSplit);
2010 : :
4322 heikki.linnakangas@i 2011 : 14467 : XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
2012 : 14467 : XLogRegisterBuffer(1, rbuf, REGBUF_WILL_INIT);
2013 : : /* Log original right sibling, since we've changed its prev-pointer */
2351 pg@bowt.ie 2014 [ + + ]: 14467 : if (!isrightmost)
4322 heikki.linnakangas@i 2015 : 5713 : XLogRegisterBuffer(2, sbuf, REGBUF_STANDARD);
2351 pg@bowt.ie 2016 [ + + ]: 14467 : if (!isleaf)
4322 heikki.linnakangas@i 2017 : 181 : XLogRegisterBuffer(3, cbuf, REGBUF_STANDARD);
2018 : :
2019 : : /*
2020 : : * Log the new item, if it was inserted on the left page. (If it was
2021 : : * put on the right page, we don't need to explicitly WAL log it
2022 : : * because it's included with all the other items on the right page.)
2023 : : * Show the new item as belonging to the left page buffer, so that it
2024 : : * is not stored if XLogInsert decides it needs a full-page image of
2025 : : * the left page. We always store newitemoff in the record, though.
2026 : : *
2027 : : * The details are sometimes slightly different for page splits that
2028 : : * coincide with a posting list split. If both the replacement
2029 : : * posting list and newitem go on the right page, then we don't need
2030 : : * to log anything extra, just like the simple !newitemonleft
2031 : : * no-posting-split case (postingoff is set to zero in the WAL record,
2032 : : * so recovery doesn't need to process a posting list split at all).
2033 : : * Otherwise, we set postingoff and log orignewitem instead of
2034 : : * newitem, despite having actually inserted newitem. REDO routine
2035 : : * must reconstruct nposting and newitem using _bt_swap_posting().
2036 : : *
2037 : : * Note: It's possible that our page split point is the point that
2038 : : * makes the posting list lastleft and newitem firstright. This is
2039 : : * the only case where we log orignewitem/newitem despite newitem
2040 : : * going on the right page. If XLogInsert decides that it can omit
2041 : : * orignewitem due to logging a full-page image of the left page,
2042 : : * everything still works out, since recovery only needs to log
2043 : : * orignewitem for items on the left page (just like the regular
2044 : : * newitem-logged case).
2045 : : */
2398 pg@bowt.ie 2046 [ + + + + ]: 14467 : if (newitemonleft && xlrec.postingoff == 0)
586 peter@eisentraut.org 2047 : 2203 : XLogRegisterBufData(0, newitem, newitemsz);
2398 pg@bowt.ie 2048 [ + + ]: 12264 : else if (xlrec.postingoff != 0)
2049 : : {
2351 2050 [ - + ]: 10 : Assert(isleaf);
2051 [ + + - + ]: 10 : Assert(newitemonleft || firstrightoff == newitemoff);
2052 [ - + ]: 10 : Assert(newitemsz == IndexTupleSize(orignewitem));
586 peter@eisentraut.org 2053 : 10 : XLogRegisterBufData(0, orignewitem, newitemsz);
2054 : : }
2055 : :
2056 : : /* Log the left page's new high key */
2351 pg@bowt.ie 2057 [ + + ]: 14467 : if (!isleaf)
2058 : : {
2059 : : /* lefthighkey isn't local copy, get current pointer */
2060 : 181 : itemid = PageGetItemId(origpage, P_HIKEY);
2061 : 181 : lefthighkey = (IndexTuple) PageGetItem(origpage, itemid);
2062 : : }
586 peter@eisentraut.org 2063 : 14467 : XLogRegisterBufData(0, lefthighkey,
2351 pg@bowt.ie 2064 : 14467 : MAXALIGN(IndexTupleSize(lefthighkey)));
2065 : :
2066 : : /*
2067 : : * Log the contents of the right page in the format understood by
2068 : : * _bt_restore_page(). The whole right page will be recreated.
2069 : : *
2070 : : * Direct access to page is not good but faster - we should implement
2071 : : * some new func in page API. Note we only store the tuples
2072 : : * themselves, knowing that they were inserted in item-number order
2073 : : * and so the line pointers can be reconstructed. See comments for
2074 : : * _bt_restore_page().
2075 : : */
4322 heikki.linnakangas@i 2076 : 14467 : XLogRegisterBufData(1,
3378 tgl@sss.pgh.pa.us 2077 : 14467 : (char *) rightpage + ((PageHeader) rightpage)->pd_upper,
4322 heikki.linnakangas@i 2078 : 14467 : ((PageHeader) rightpage)->pd_special - ((PageHeader) rightpage)->pd_upper);
2079 : :
2741 pg@bowt.ie 2080 [ + + ]: 14467 : xlinfo = newitemonleft ? XLOG_BTREE_SPLIT_L : XLOG_BTREE_SPLIT_R;
4322 heikki.linnakangas@i 2081 : 14467 : recptr = XLogInsert(RM_BTREE_ID, xlinfo);
2082 : : }
2083 : : else
191 pg@bowt.ie 2084 : 673 : recptr = XLogGetFakeLSN(rel);
2085 : :
2086 : 15140 : PageSetLSN(origpage, recptr);
2087 : 15140 : PageSetLSN(rightpage, recptr);
2088 [ + + ]: 15140 : if (!isrightmost)
2089 : 5721 : PageSetLSN(spage, recptr);
2090 [ + + ]: 15140 : if (!isleaf)
2091 : 181 : PageSetLSN(BufferGetPage(cbuf), recptr);
2092 : :
9371 tgl@sss.pgh.pa.us 2093 [ - + ]: 15140 : END_CRIT_SECTION();
2094 : :
2095 : : /* release the old right sibling */
2351 pg@bowt.ie 2096 [ + + ]: 15140 : if (!isrightmost)
7478 tgl@sss.pgh.pa.us 2097 : 5721 : _bt_relbuf(rel, sbuf);
2098 : :
2099 : : /* release the child */
4569 heikki.linnakangas@i 2100 [ + + ]: 15140 : if (!isleaf)
2101 : 181 : _bt_relbuf(rel, cbuf);
2102 : :
2103 : : /* be tidy */
2351 pg@bowt.ie 2104 [ + + ]: 15140 : if (isleaf)
2105 : 14959 : pfree(lefthighkey);
2106 : :
2107 : : /* split's done */
10246 bruce@momjian.us 2108 : 15140 : return rbuf;
2109 : : }
2110 : :
2111 : : /*
2112 : : * _bt_insert_parent() -- Insert downlink into parent, completing split.
2113 : : *
2114 : : * On entry, buf and rbuf are the left and right split pages, which we
2115 : : * still hold write locks on. Both locks will be released here. We
2116 : : * release the rbuf lock once we have a write lock on the page that we
2117 : : * intend to insert a downlink to rbuf on (i.e. buf's current parent page).
2118 : : * The lock on buf is released at the same point as the lock on the parent
2119 : : * page, since buf's INCOMPLETE_SPLIT flag must be cleared by the same
2120 : : * atomic operation that completes the split by inserting a new downlink.
2121 : : *
2122 : : * stack - stack showing how we got here. Will be NULL when splitting true
2123 : : * root, or during concurrent root split, where we can be inefficient
2124 : : * isroot - we split the true root
2125 : : * isonly - we split a page alone on its level (might have been fast root)
2126 : : */
2127 : : static void
8612 tgl@sss.pgh.pa.us 2128 : 15140 : _bt_insert_parent(Relation rel,
2129 : : Relation heaprel,
2130 : : Buffer buf,
2131 : : Buffer rbuf,
2132 : : BTStack stack,
2133 : : bool isroot,
2134 : : bool isonly)
2135 : : {
1198 pg@bowt.ie 2136 [ - + ]: 15140 : Assert(heaprel != NULL);
2137 : :
2138 : : /*
2139 : : * Here we have to do something Lehman and Yao don't talk about: deal with
2140 : : * a root split and construction of a new root. If our stack is empty
2141 : : * then we have just split a node on what had been the root level when we
2142 : : * descended the tree. If it was still the root then we perform a
2143 : : * new-root construction. If it *wasn't* the root anymore, search to find
2144 : : * the next higher level that someone constructed meanwhile, and find the
2145 : : * right place to insert as for the normal case.
2146 : : *
2147 : : * If we have to search for the parent level, we do so by re-descending
2148 : : * from the root. This is not super-efficient, but it's rare enough not
2149 : : * to matter.
2150 : : */
2133 2151 [ + + ]: 15140 : if (isroot)
2152 : : {
2153 : : Buffer rootbuf;
2154 : :
8292 neilc@samurai.com 2155 [ - + ]: 830 : Assert(stack == NULL);
2133 pg@bowt.ie 2156 [ - + ]: 830 : Assert(isonly);
2157 : : /* create a new root node one level up and update the metapage */
1198 2158 : 830 : rootbuf = _bt_newlevel(rel, heaprel, buf, rbuf);
2159 : : /* release the split buffers */
7478 tgl@sss.pgh.pa.us 2160 : 830 : _bt_relbuf(rel, rootbuf);
2161 : 830 : _bt_relbuf(rel, rbuf);
2162 : 830 : _bt_relbuf(rel, buf);
2163 : : }
2164 : : else
2165 : : {
8612 2166 : 14310 : BlockNumber bknum = BufferGetBlockNumber(buf);
2167 : 14310 : BlockNumber rbknum = BufferGetBlockNumber(rbuf);
3805 kgrittn@postgresql.o 2168 : 14310 : Page page = BufferGetPage(buf);
2169 : : IndexTuple new_item;
2170 : : BTStackData fakestack;
2171 : : IndexTuple ritem;
2172 : : Buffer pbuf;
2173 : :
8292 neilc@samurai.com 2174 [ + + ]: 14310 : if (stack == NULL)
2175 : : {
2176 : : BTPageOpaque opaque;
2177 : :
4392 heikki.linnakangas@i 2178 [ - + ]: 16 : elog(DEBUG2, "concurrent ROOT page split");
1633 michael@paquier.xyz 2179 : 16 : opaque = BTPageGetOpaque(page);
2180 : :
2181 : : /*
2182 : : * We should never reach here when a leaf page split takes place
2183 : : * despite the insert of newitem being able to apply the fastpath
2184 : : * optimization. Make sure of that with an assertion.
2185 : : *
2186 : : * This is more of a performance issue than a correctness issue.
2187 : : * The fastpath won't have a descent stack. Using a phony stack
2188 : : * here works, but never rely on that. The fastpath should be
2189 : : * rejected within _bt_search_insert() when the rightmost leaf
2190 : : * page will split, since it's faster to go through _bt_search()
2191 : : * and get a stack in the usual way.
2192 : : */
2133 pg@bowt.ie 2193 [ + - + - : 16 : Assert(!(P_ISLEAF(opaque) &&
- + ]
2194 : : BlockNumberIsValid(RelationGetTargetBlock(rel))));
2195 : :
2196 : : /* Find the leftmost page at the next level up */
1108 tmunro@postgresql.or 2197 : 16 : pbuf = _bt_get_endpoint(rel, opaque->btpo_level + 1, false);
2198 : : /* Set up a phony stack entry pointing there */
8612 tgl@sss.pgh.pa.us 2199 : 16 : stack = &fakestack;
2200 : 16 : stack->bts_blkno = BufferGetBlockNumber(pbuf);
2201 : 16 : stack->bts_offset = InvalidOffsetNumber;
2202 : 16 : stack->bts_parent = NULL;
2203 : 16 : _bt_relbuf(rel, pbuf);
2204 : : }
2205 : :
2206 : : /* get high key from left, a strict lower bound for new right page */
7543 2207 : 14310 : ritem = (IndexTuple) PageGetItem(page,
2208 : 14310 : PageGetItemId(page, P_HIKEY));
2209 : :
2210 : : /* form an index tuple that points at the new right page */
2211 : 14310 : new_item = CopyIndexTuple(ritem);
2470 pg@bowt.ie 2212 : 14310 : BTreeTupleSetDownLink(new_item, rbknum);
2213 : :
2214 : : /*
2215 : : * Re-find and write lock the parent of buf.
2216 : : *
2217 : : * It's possible that the location of buf's downlink has changed since
2218 : : * our initial _bt_search() descent. _bt_getstackbuf() will detect
2219 : : * and recover from this, updating the stack, which ensures that the
2220 : : * new downlink will be inserted at the correct offset. Even buf's
2221 : : * parent may have changed.
2222 : : */
1268 andres@anarazel.de 2223 : 14310 : pbuf = _bt_getstackbuf(rel, heaprel, stack, bknum);
2224 : :
2225 : : /*
2226 : : * Unlock the right child. The left child will be unlocked in
2227 : : * _bt_insertonpg().
2228 : : *
2229 : : * Unlocking the right child must be delayed until here to ensure that
2230 : : * no concurrent VACUUM operation can become confused. Page deletion
2231 : : * cannot be allowed to fail to re-find a downlink for the rbuf page.
2232 : : * (Actually, this is just a vestige of how things used to work. The
2233 : : * page deletion code is expected to check for the INCOMPLETE_SPLIT
2234 : : * flag on the left child. It won't attempt deletion of the right
2235 : : * child until the split is complete. Despite all this, we opt to
2236 : : * conservatively delay unlocking the right child until here.)
2237 : : */
7478 tgl@sss.pgh.pa.us 2238 : 14310 : _bt_relbuf(rel, rbuf);
2239 : :
8612 2240 [ - + ]: 14310 : if (pbuf == InvalidBuffer)
2607 peter@eisentraut.org 2241 [ # # ]:UBC 0 : ereport(ERROR,
2242 : : (errcode(ERRCODE_INDEX_CORRUPTED),
2243 : : errmsg_internal("failed to re-find parent key in index \"%s\" for split pages %u/%u",
2244 : : RelationGetRelationName(rel), bknum, rbknum)));
2245 : :
2246 : : /* Recursively insert into the parent */
1268 andres@anarazel.de 2247 :CBC 28620 : _bt_insertonpg(rel, heaprel, NULL, pbuf, buf, stack->bts_parent,
2379 pg@bowt.ie 2248 : 14310 : new_item, MAXALIGN(IndexTupleSize(new_item)),
2133 2249 : 14310 : stack->bts_offset + 1, 0, isonly);
2250 : :
2251 : : /* be tidy */
8612 tgl@sss.pgh.pa.us 2252 : 14309 : pfree(new_item);
2253 : : }
2254 : 15139 : }
2255 : :
2256 : : /*
2257 : : * _bt_finish_split() -- Finish an incomplete split
2258 : : *
2259 : : * A crash or other failure can leave a split incomplete. The insertion
2260 : : * routines won't allow to insert on a page that is incompletely split.
2261 : : * Before inserting on such a page, call _bt_finish_split().
2262 : : *
2263 : : * On entry, 'lbuf' must be locked in write-mode. On exit, it is unlocked
2264 : : * and unpinned.
2265 : : *
2266 : : * Caller must provide a valid heaprel, since finishing a page split requires
2267 : : * allocating a new page if and when the parent page splits in turn.
2268 : : */
2269 : : void
1268 andres@anarazel.de 2270 : 2 : _bt_finish_split(Relation rel, Relation heaprel, Buffer lbuf, BTStack stack)
2271 : : {
3805 kgrittn@postgresql.o 2272 : 2 : Page lpage = BufferGetPage(lbuf);
1633 michael@paquier.xyz 2273 : 2 : BTPageOpaque lpageop = BTPageGetOpaque(lpage);
2274 : : Buffer rbuf;
2275 : : Page rpage;
2276 : : BTPageOpaque rpageop;
2277 : : bool wasroot;
2278 : : bool wasonly;
2279 : :
4569 heikki.linnakangas@i 2280 [ - + ]: 2 : Assert(P_INCOMPLETE_SPLIT(lpageop));
1198 pg@bowt.ie 2281 [ - + ]: 2 : Assert(heaprel != NULL);
2282 : :
2283 : : /* Lock right sibling, the one missing the downlink */
2284 : 2 : rbuf = _bt_getbuf(rel, lpageop->btpo_next, BT_WRITE);
3805 kgrittn@postgresql.o 2285 : 2 : rpage = BufferGetPage(rbuf);
1633 michael@paquier.xyz 2286 : 2 : rpageop = BTPageGetOpaque(rpage);
2287 : :
2288 : : /* Could this be a root split? */
4569 heikki.linnakangas@i 2289 [ + + ]: 2 : if (!stack)
2290 : : {
2291 : : Buffer metabuf;
2292 : : Page metapg;
2293 : : BTMetaPageData *metad;
2294 : :
2295 : : /* acquire lock on the metapage */
1198 pg@bowt.ie 2296 : 1 : metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_WRITE);
3805 kgrittn@postgresql.o 2297 : 1 : metapg = BufferGetPage(metabuf);
4569 heikki.linnakangas@i 2298 : 1 : metad = BTPageGetMeta(metapg);
2299 : :
2133 pg@bowt.ie 2300 : 1 : wasroot = (metad->btm_root == BufferGetBlockNumber(lbuf));
2301 : :
4569 heikki.linnakangas@i 2302 : 1 : _bt_relbuf(rel, metabuf);
2303 : : }
2304 : : else
2133 pg@bowt.ie 2305 : 1 : wasroot = false;
2306 : :
2307 : : /* Was this the only page on the level before split? */
2308 [ + + + - ]: 2 : wasonly = (P_LEFTMOST(lpageop) && P_RIGHTMOST(rpageop));
2309 : :
292 heikki.linnakangas@i 2310 : 2 : INJECTION_POINT("nbtree-finish-incomplete-split", NULL);
4569 2311 [ - + ]: 2 : elog(DEBUG1, "finishing incomplete split of %u/%u",
2312 : : BufferGetBlockNumber(lbuf), BufferGetBlockNumber(rbuf));
2313 : :
1268 andres@anarazel.de 2314 : 2 : _bt_insert_parent(rel, heaprel, lbuf, rbuf, stack, wasroot, wasonly);
4569 heikki.linnakangas@i 2315 : 2 : }
2316 : :
2317 : : /*
2318 : : * _bt_getstackbuf() -- Walk back up the tree one step, and find the pivot
2319 : : * tuple whose downlink points to child page.
2320 : : *
2321 : : * Caller passes child's block number, which is used to identify
2322 : : * associated pivot tuple in parent page using a linear search that
2323 : : * matches on pivot's downlink/block number. The expected location of
2324 : : * the pivot tuple is taken from the stack one level above the child
2325 : : * page. This is used as a starting point. Insertions into the
2326 : : * parent level could cause the pivot tuple to move right; deletions
2327 : : * could cause it to move left, but not left of the page we previously
2328 : : * found it on.
2329 : : *
2330 : : * Caller can use its stack to relocate the pivot tuple/downlink for
2331 : : * any same-level page to the right of the page found by its initial
2332 : : * descent. This is necessary because of the possibility that caller
2333 : : * moved right to recover from a concurrent page split. It's also
2334 : : * convenient for certain callers to be able to step right when there
2335 : : * wasn't a concurrent page split, while still using their original
2336 : : * stack. For example, the checkingunique _bt_doinsert() case may
2337 : : * have to step right when there are many physical duplicates, and its
2338 : : * scantid forces an insertion to the right of the "first page the
2339 : : * value could be on". (This is also relied on by all of our callers
2340 : : * when dealing with !heapkeyspace indexes.)
2341 : : *
2342 : : * Returns write-locked parent page buffer, or InvalidBuffer if pivot
2343 : : * tuple not found (should not happen). Adjusts bts_blkno &
2344 : : * bts_offset if changed. Page split caller should insert its new
2345 : : * pivot tuple for its new right sibling page on parent page, at the
2346 : : * offset number bts_offset + 1.
2347 : : */
2348 : : Buffer
1268 andres@anarazel.de 2349 : 18538 : _bt_getstackbuf(Relation rel, Relation heaprel, BTStack stack, BlockNumber child)
2350 : : {
2351 : : BlockNumber blkno;
2352 : : OffsetNumber start;
2353 : :
9557 tgl@sss.pgh.pa.us 2354 : 18538 : blkno = stack->bts_blkno;
2355 : 18538 : start = stack->bts_offset;
2356 : :
2357 : : for (;;)
2358 : 13 : {
2359 : : Buffer buf;
2360 : : Page page;
2361 : : BTPageOpaque opaque;
2362 : :
1198 pg@bowt.ie 2363 : 18551 : buf = _bt_getbuf(rel, blkno, BT_WRITE);
3805 kgrittn@postgresql.o 2364 : 18551 : page = BufferGetPage(buf);
1633 michael@paquier.xyz 2365 : 18551 : opaque = BTPageGetOpaque(page);
2366 : :
1198 pg@bowt.ie 2367 [ - + ]: 18551 : Assert(heaprel != NULL);
2764 2368 [ - + ]: 18551 : if (P_INCOMPLETE_SPLIT(opaque))
2369 : : {
1268 andres@anarazel.de 2370 :UBC 0 : _bt_finish_split(rel, heaprel, buf, stack->bts_parent);
4569 heikki.linnakangas@i 2371 : 0 : continue;
2372 : : }
2373 : :
8611 tgl@sss.pgh.pa.us 2374 [ + + ]:CBC 18551 : if (!P_IGNORE(opaque))
2375 : : {
2376 : : OffsetNumber offnum,
2377 : : minoff,
2378 : : maxoff;
2379 : : ItemId itemid;
2380 : : IndexTuple item;
2381 : :
2382 [ + + ]: 18540 : minoff = P_FIRSTDATAKEY(opaque);
2383 : 18540 : maxoff = PageGetMaxOffsetNumber(page);
2384 : :
2385 : : /*
2386 : : * start = InvalidOffsetNumber means "search the whole page". We
2387 : : * need this test anyway due to possibility that page has a high
2388 : : * key now when it didn't before.
2389 : : */
2390 [ + + ]: 18540 : if (start < minoff)
2391 : 29 : start = minoff;
2392 : :
2393 : : /*
2394 : : * Need this check too, to guard against possibility that page
2395 : : * split since we visited it originally.
2396 : : */
8069 2397 [ + + ]: 18540 : if (start > maxoff)
2398 : 2 : start = OffsetNumberNext(maxoff);
2399 : :
2400 : : /*
2401 : : * These loops will check every item on the page --- but in an
2402 : : * order that's attuned to the probability of where it actually
2403 : : * is. Scan to the right first, then to the left.
2404 : : */
8611 2405 : 18540 : for (offnum = start;
2406 [ + + ]: 18750 : offnum <= maxoff;
2407 : 210 : offnum = OffsetNumberNext(offnum))
2408 : : {
2409 : 18748 : itemid = PageGetItemId(page, offnum);
7543 2410 : 18748 : item = (IndexTuple) PageGetItem(page, itemid);
2411 : :
2470 pg@bowt.ie 2412 [ + + ]: 18748 : if (BTreeTupleGetDownLink(item) == child)
2413 : : {
2414 : : /* Return accurate pointer to where link is now */
8611 tgl@sss.pgh.pa.us 2415 : 18538 : stack->bts_blkno = blkno;
2416 : 18538 : stack->bts_offset = offnum;
2417 : 18538 : return buf;
2418 : : }
2419 : : }
2420 : :
2421 : 2 : for (offnum = OffsetNumberPrev(start);
2422 [ + + ]: 446 : offnum >= minoff;
8611 tgl@sss.pgh.pa.us 2423 :GBC 444 : offnum = OffsetNumberPrev(offnum))
2424 : : {
8611 tgl@sss.pgh.pa.us 2425 :CBC 444 : itemid = PageGetItemId(page, offnum);
7543 2426 : 444 : item = (IndexTuple) PageGetItem(page, itemid);
2427 : :
2470 pg@bowt.ie 2428 [ - + ]: 444 : if (BTreeTupleGetDownLink(item) == child)
2429 : : {
2430 : : /* Return accurate pointer to where link is now */
8611 tgl@sss.pgh.pa.us 2431 :LBC (1) : stack->bts_blkno = blkno;
2432 : (1) : stack->bts_offset = offnum;
2433 : (1) : return buf;
2434 : : }
2435 : : }
2436 : : }
2437 : :
2438 : : /*
2439 : : * The item we're looking for moved right at least one page.
2440 : : *
2441 : : * Lehman and Yao couple/chain locks when moving right here, which we
2442 : : * can avoid. See nbtree/README.
2443 : : */
9557 tgl@sss.pgh.pa.us 2444 [ - + ]:CBC 13 : if (P_RIGHTMOST(opaque))
2445 : : {
9198 tgl@sss.pgh.pa.us 2446 :UBC 0 : _bt_relbuf(rel, buf);
8187 2447 : 0 : return InvalidBuffer;
2448 : : }
9557 tgl@sss.pgh.pa.us 2449 :CBC 13 : blkno = opaque->btpo_next;
8612 2450 : 13 : start = InvalidOffsetNumber;
9198 2451 : 13 : _bt_relbuf(rel, buf);
2452 : : }
2453 : : }
2454 : :
2455 : : /*
2456 : : * _bt_freestack() -- free a retracement stack made by _bt_search_insert.
2457 : : */
2458 : : static void
192 pg@bowt.ie 2459 : 4522595 : _bt_freestack(BTStack stack)
2460 : : {
2461 : : BTStack ostack;
2462 : :
2463 [ + + ]: 9106527 : while (stack != NULL)
2464 : : {
2465 : 4583932 : ostack = stack;
2466 : 4583932 : stack = stack->bts_parent;
2467 : 4583932 : pfree(ostack);
2468 : : }
2469 : 4522595 : }
2470 : :
2471 : : /*
2472 : : * _bt_newlevel() -- Create a new level above root page.
2473 : : *
2474 : : * We've just split the old root page and need to create a new one.
2475 : : * In order to do this, we add a new root page to the file, then lock
2476 : : * the metadata page and update it. This is guaranteed to be deadlock-
2477 : : * free, because all readers release their locks on the metadata page
2478 : : * before trying to lock the root, and all writers lock the root before
2479 : : * trying to lock the metadata page. We have a write lock on the old
2480 : : * root page, so we have not introduced any cycles into the waits-for
2481 : : * graph.
2482 : : *
2483 : : * On entry, lbuf (the old root) and rbuf (its new peer) are write-
2484 : : * locked. On exit, a new root page exists with entries for the
2485 : : * two new children, metapage is updated and unlocked/unpinned.
2486 : : * The new root buffer is returned to caller which has to unlock/unpin
2487 : : * lbuf, rbuf & rootbuf.
2488 : : */
2489 : : static Buffer
1198 2490 : 830 : _bt_newlevel(Relation rel, Relation heaprel, Buffer lbuf, Buffer rbuf)
2491 : : {
2492 : : Buffer rootbuf;
2493 : : Page lpage,
2494 : : rootpage;
2495 : : BlockNumber lbkno,
2496 : : rbkno;
2497 : : BlockNumber rootblknum;
2498 : : BTPageOpaque rootopaque;
2499 : : BTPageOpaque lopaque;
2500 : : ItemId itemid;
2501 : : IndexTuple item;
2502 : : IndexTuple left_item;
2503 : : Size left_item_sz;
2504 : : IndexTuple right_item;
2505 : : Size right_item_sz;
2506 : : Buffer metabuf;
2507 : : Page metapg;
2508 : : BTMetaPageData *metad;
2509 : : XLogRecPtr recptr;
2510 : :
8612 tgl@sss.pgh.pa.us 2511 : 830 : lbkno = BufferGetBlockNumber(lbuf);
2512 : 830 : rbkno = BufferGetBlockNumber(rbuf);
3805 kgrittn@postgresql.o 2513 : 830 : lpage = BufferGetPage(lbuf);
1633 michael@paquier.xyz 2514 : 830 : lopaque = BTPageGetOpaque(lpage);
2515 : :
2516 : : /* get a new root page */
1198 pg@bowt.ie 2517 : 830 : rootbuf = _bt_allocbuf(rel, heaprel);
3805 kgrittn@postgresql.o 2518 : 830 : rootpage = BufferGetPage(rootbuf);
9482 vadim4o@yahoo.com 2519 : 830 : rootblknum = BufferGetBlockNumber(rootbuf);
2520 : :
2521 : : /* acquire lock on the metapage */
1198 pg@bowt.ie 2522 : 830 : metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_WRITE);
3805 kgrittn@postgresql.o 2523 : 830 : metapg = BufferGetPage(metabuf);
9397 vadim4o@yahoo.com 2524 : 830 : metad = BTPageGetMeta(metapg);
2525 : :
2526 : : /*
2527 : : * Create downlink item for left page (old root). The key value used is
2528 : : * "minus infinity", a sentinel value that's reliably less than any real
2529 : : * key value that could appear in the left page.
2530 : : */
4552 heikki.linnakangas@i 2531 : 830 : left_item_sz = sizeof(IndexTupleData);
2532 : 830 : left_item = (IndexTuple) palloc(left_item_sz);
2533 : 830 : left_item->t_info = left_item_sz;
2470 pg@bowt.ie 2534 : 830 : BTreeTupleSetDownLink(left_item, lbkno);
2357 2535 : 830 : BTreeTupleSetNAtts(left_item, 0, false);
2536 : :
2537 : : /*
2538 : : * Create downlink item for right page. The key for it is obtained from
2539 : : * the "high key" position in the left page.
2540 : : */
4552 heikki.linnakangas@i 2541 : 830 : itemid = PageGetItemId(lpage, P_HIKEY);
2542 : 830 : right_item_sz = ItemIdGetLength(itemid);
2543 : 830 : item = (IndexTuple) PageGetItem(lpage, itemid);
2544 : 830 : right_item = CopyIndexTuple(item);
2470 pg@bowt.ie 2545 : 830 : BTreeTupleSetDownLink(right_item, rbkno);
2546 : :
2547 : : /* NO EREPORT(ERROR) from here till newroot op is logged */
9382 tgl@sss.pgh.pa.us 2548 : 830 : START_CRIT_SECTION();
2549 : :
2550 : : /* upgrade metapage if needed */
2741 pg@bowt.ie 2551 [ - + ]: 830 : if (metad->btm_version < BTREE_NOVAC_VERSION)
3035 teodor@sigaev.ru 2552 :UBC 0 : _bt_upgrademetapage(metapg);
2553 : :
2554 : : /* set btree special data */
1633 michael@paquier.xyz 2555 :CBC 830 : rootopaque = BTPageGetOpaque(rootpage);
10605 bruce@momjian.us 2556 : 830 : rootopaque->btpo_prev = rootopaque->btpo_next = P_NONE;
8612 tgl@sss.pgh.pa.us 2557 : 830 : rootopaque->btpo_flags = BTP_ROOT;
2034 pg@bowt.ie 2558 : 830 : rootopaque->btpo_level =
1633 michael@paquier.xyz 2559 : 830 : (BTPageGetOpaque(lpage))->btpo_level + 1;
7440 tgl@sss.pgh.pa.us 2560 : 830 : rootopaque->btpo_cycleid = 0;
2561 : :
2562 : : /* update metapage data */
8612 2563 : 830 : metad->btm_root = rootblknum;
2034 pg@bowt.ie 2564 : 830 : metad->btm_level = rootopaque->btpo_level;
8612 tgl@sss.pgh.pa.us 2565 : 830 : metad->btm_fastroot = rootblknum;
2034 pg@bowt.ie 2566 : 830 : metad->btm_fastlevel = rootopaque->btpo_level;
2567 : :
2568 : : /*
2569 : : * Insert the left page pointer into the new root page. The root page is
2570 : : * the rightmost page on its level so there is no "high key" in it; the
2571 : : * two items will go into positions P_HIKEY and P_FIRSTKEY.
2572 : : *
2573 : : * Note: we *must* insert the two items in item-number order, for the
2574 : : * benefit of _bt_restore_page().
2575 : : */
3076 teodor@sigaev.ru 2576 [ + - - + ]: 830 : Assert(BTreeTupleGetNAtts(left_item, rel) == 0);
328 peter@eisentraut.org 2577 [ - + ]: 830 : if (PageAddItem(rootpage, left_item, left_item_sz, P_HIKEY, false, false) == InvalidOffsetNumber)
6838 tgl@sss.pgh.pa.us 2578 [ # # ]:UBC 0 : elog(PANIC, "failed to add leftkey to new root page"
2579 : : " while splitting block %u of index \"%s\"",
2580 : : BufferGetBlockNumber(lbuf), RelationGetRelationName(rel));
2581 : :
2582 : : /*
2583 : : * insert the right page pointer into the new root page.
2584 : : */
2741 pg@bowt.ie 2585 [ + - - + ]:CBC 830 : Assert(BTreeTupleGetNAtts(right_item, rel) > 0);
2586 [ + - - + ]: 830 : Assert(BTreeTupleGetNAtts(right_item, rel) <=
2587 : : IndexRelationGetNumberOfKeyAttributes(rel));
328 peter@eisentraut.org 2588 [ - + ]: 830 : if (PageAddItem(rootpage, right_item, right_item_sz, P_FIRSTKEY, false, false) == InvalidOffsetNumber)
6838 tgl@sss.pgh.pa.us 2589 [ # # ]:UBC 0 : elog(PANIC, "failed to add rightkey to new root page"
2590 : : " while splitting block %u of index \"%s\"",
2591 : : BufferGetBlockNumber(lbuf), RelationGetRelationName(rel));
2592 : :
2593 : : /* Clear the incomplete-split flag in the left child */
4569 heikki.linnakangas@i 2594 [ - + ]:CBC 830 : Assert(P_INCOMPLETE_SPLIT(lopaque));
2595 : 830 : lopaque->btpo_flags &= ~BTP_INCOMPLETE_SPLIT;
2596 : 830 : MarkBufferDirty(lbuf);
2597 : :
7478 tgl@sss.pgh.pa.us 2598 : 830 : MarkBufferDirty(rootbuf);
2599 : 830 : MarkBufferDirty(metabuf);
2600 : :
2601 : : /* XLOG stuff */
5760 rhaas@postgresql.org 2602 [ + + + + : 830 : if (RelationNeedsWAL(rel))
+ - + - ]
9482 vadim4o@yahoo.com 2603 : 811 : {
2604 : : xl_btree_newroot xlrec;
2605 : : xl_btree_metadata md;
2606 : :
8612 tgl@sss.pgh.pa.us 2607 : 811 : xlrec.rootblk = rootblknum;
9397 vadim4o@yahoo.com 2608 : 811 : xlrec.level = metad->btm_level;
2609 : :
4322 heikki.linnakangas@i 2610 : 811 : XLogBeginInsert();
586 peter@eisentraut.org 2611 : 811 : XLogRegisterData(&xlrec, SizeOfBtreeNewroot);
2612 : :
4322 heikki.linnakangas@i 2613 : 811 : XLogRegisterBuffer(0, rootbuf, REGBUF_WILL_INIT);
2614 : 811 : XLogRegisterBuffer(1, lbuf, REGBUF_STANDARD);
3243 tgl@sss.pgh.pa.us 2615 : 811 : XLogRegisterBuffer(2, metabuf, REGBUF_WILL_INIT | REGBUF_STANDARD);
2616 : :
2741 pg@bowt.ie 2617 [ - + ]: 811 : Assert(metad->btm_version >= BTREE_NOVAC_VERSION);
2618 : 811 : md.version = metad->btm_version;
4322 heikki.linnakangas@i 2619 : 811 : md.root = rootblknum;
2620 : 811 : md.level = metad->btm_level;
2621 : 811 : md.fastroot = rootblknum;
2622 : 811 : md.fastlevel = metad->btm_level;
2034 pg@bowt.ie 2623 : 811 : md.last_cleanup_num_delpages = metad->btm_last_cleanup_num_delpages;
2398 2624 : 811 : md.allequalimage = metad->btm_allequalimage;
2625 : :
586 peter@eisentraut.org 2626 : 811 : XLogRegisterBufData(2, &md, sizeof(xl_btree_metadata));
2627 : :
2628 : : /*
2629 : : * Direct access to page is not good but faster - we should implement
2630 : : * some new func in page API.
2631 : : */
4322 heikki.linnakangas@i 2632 : 811 : XLogRegisterBufData(0,
3378 tgl@sss.pgh.pa.us 2633 : 811 : (char *) rootpage + ((PageHeader) rootpage)->pd_upper,
4322 heikki.linnakangas@i 2634 : 811 : ((PageHeader) rootpage)->pd_special -
2635 : 811 : ((PageHeader) rootpage)->pd_upper);
2636 : :
2637 : 811 : recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_NEWROOT);
2638 : : }
2639 : : else
191 pg@bowt.ie 2640 : 19 : recptr = XLogGetFakeLSN(rel);
2641 : :
2642 : 830 : PageSetLSN(lpage, recptr);
2643 : 830 : PageSetLSN(rootpage, recptr);
2644 : 830 : PageSetLSN(metapg, recptr);
2645 : :
9382 tgl@sss.pgh.pa.us 2646 [ - + ]: 830 : END_CRIT_SECTION();
2647 : :
2648 : : /* done with metapage */
7478 2649 : 830 : _bt_relbuf(rel, metabuf);
2650 : :
4552 heikki.linnakangas@i 2651 : 830 : pfree(left_item);
2652 : 830 : pfree(right_item);
2653 : :
7557 neilc@samurai.com 2654 : 830 : return rootbuf;
2655 : : }
2656 : :
2657 : : /*
2658 : : * _bt_pgaddtup() -- add a data item to a particular page during split.
2659 : : *
2660 : : * The difference between this routine and a bare PageAddItem call is
2661 : : * that this code can deal with the first data item on an internal btree
2662 : : * page in passing. This data item (which is called "firstright" within
2663 : : * _bt_split()) has a key that must be treated as minus infinity after
2664 : : * the split. Therefore, we truncate away all attributes when caller
2665 : : * specifies it's the first data item on page (downlink is not changed,
2666 : : * though). This extra step is only needed for the right page of an
2667 : : * internal page split. There is no need to do this for the first data
2668 : : * item on the existing/left page, since that will already have been
2669 : : * truncated during an earlier page split.
2670 : : *
2671 : : * See _bt_split() for a high level explanation of why we truncate here.
2672 : : * Note that this routine has nothing to do with suffix truncation,
2673 : : * despite using some of the same infrastructure.
2674 : : */
2675 : : static inline bool
5866 tgl@sss.pgh.pa.us 2676 : 4737945 : _bt_pgaddtup(Page page,
2677 : : Size itemsize,
2678 : : const IndexTupleData *itup,
2679 : : OffsetNumber itup_off,
2680 : : bool newfirstdataitem)
2681 : : {
2682 : : IndexTupleData trunctuple;
2683 : :
2351 pg@bowt.ie 2684 [ + + ]: 4737945 : if (newfirstdataitem)
2685 : : {
7543 tgl@sss.pgh.pa.us 2686 : 181 : trunctuple = *itup;
2687 : 181 : trunctuple.t_info = sizeof(IndexTupleData);
2357 pg@bowt.ie 2688 : 181 : BTreeTupleSetNAtts(&trunctuple, 0, false);
7543 tgl@sss.pgh.pa.us 2689 : 181 : itup = &trunctuple;
2690 : 181 : itemsize = sizeof(IndexTupleData);
2691 : : }
2692 : :
328 peter@eisentraut.org 2693 [ - + ]: 4737945 : if (unlikely(PageAddItem(page, itup, itemsize, itup_off, false, false) == InvalidOffsetNumber))
5866 tgl@sss.pgh.pa.us 2694 :UBC 0 : return false;
2695 : :
5866 tgl@sss.pgh.pa.us 2696 :CBC 4737945 : return true;
2697 : : }
2698 : :
2699 : : /*
2700 : : * _bt_delete_or_dedup_one_page - Try to avoid a leaf page split.
2701 : : *
2702 : : * There are three operations performed here: simple index deletion, bottom-up
2703 : : * index deletion, and deduplication. If all three operations fail to free
2704 : : * enough space for the incoming item then caller will go on to split the
2705 : : * page. We always consider simple deletion first. If that doesn't work out
2706 : : * we consider alternatives. Callers that only want us to consider simple
2707 : : * deletion (without any fallback) ask for that using the 'simpleonly'
2708 : : * argument.
2709 : : *
2710 : : * We usually pick only one alternative "complex" operation when simple
2711 : : * deletion alone won't prevent a page split. The 'checkingunique',
2712 : : * 'uniquedup', and 'indexUnchanged' arguments are used for that.
2713 : : *
2714 : : * Note: We used to only delete LP_DEAD items when the BTP_HAS_GARBAGE page
2715 : : * level flag was found set. The flag was useful back when there wasn't
2716 : : * necessarily one single page for a duplicate tuple to go on (before heap TID
2717 : : * became a part of the key space in version 4 indexes). But we don't
2718 : : * actually look at the flag anymore (it's not a gating condition for our
2719 : : * caller). That would cause us to miss tuples that are safe to delete,
2720 : : * without getting any benefit in return. We know that the alternative is to
2721 : : * split the page; scanning the line pointer array in passing won't have
2722 : : * noticeable overhead. (We still maintain the BTP_HAS_GARBAGE flag despite
2723 : : * all this because !heapkeyspace indexes must still do a "getting tired"
2724 : : * linear search, and so are likely to get some benefit from using it as a
2725 : : * gating condition.)
2726 : : */
2727 : : static void
2133 pg@bowt.ie 2728 : 33359 : _bt_delete_or_dedup_one_page(Relation rel, Relation heapRel,
2729 : : BTInsertState insertstate,
2730 : : bool simpleonly, bool checkingunique,
2731 : : bool uniquedup, bool indexUnchanged)
2732 : : {
2733 : : OffsetNumber deletable[MaxIndexTuplesPerPage];
7291 bruce@momjian.us 2734 : 33359 : int ndeletable = 0;
2735 : : OffsetNumber offnum,
2736 : : minoff,
2737 : : maxoff;
2133 pg@bowt.ie 2738 : 33359 : Buffer buffer = insertstate->buf;
2739 : 33359 : BTScanInsert itup_key = insertstate->itup_key;
3805 kgrittn@postgresql.o 2740 : 33359 : Page page = BufferGetPage(buffer);
1633 michael@paquier.xyz 2741 : 33359 : BTPageOpaque opaque = BTPageGetOpaque(page);
2742 : :
2741 pg@bowt.ie 2743 [ - + ]: 33359 : Assert(P_ISLEAF(opaque));
2076 2744 [ + + - + ]: 33359 : Assert(simpleonly || itup_key->heapkeyspace);
2745 [ + + + - : 33359 : Assert(!simpleonly || (!checkingunique && !uniquedup && !indexUnchanged));
+ - - + ]
2746 : :
2747 : : /*
2748 : : * Scan over all items to see which ones need to be deleted according to
2749 : : * LP_DEAD flags. We'll usually manage to delete a few extra items that
2750 : : * are not marked LP_DEAD in passing. Often the extra items that actually
2751 : : * end up getting deleted are items that would have had their LP_DEAD bit
2752 : : * set before long anyway (if we opted not to include them as extras).
2753 : : */
2754 [ + + ]: 33359 : minoff = P_FIRSTDATAKEY(opaque);
7362 tgl@sss.pgh.pa.us 2755 : 33359 : maxoff = PageGetMaxOffsetNumber(page);
2076 pg@bowt.ie 2756 : 33359 : for (offnum = minoff;
7362 tgl@sss.pgh.pa.us 2757 [ + + ]: 9204854 : offnum <= maxoff;
2758 : 9171495 : offnum = OffsetNumberNext(offnum))
2759 : : {
7291 bruce@momjian.us 2760 : 9171495 : ItemId itemId = PageGetItemId(page, offnum);
2761 : :
6948 tgl@sss.pgh.pa.us 2762 [ + + ]: 9171495 : if (ItemIdIsDead(itemId))
7362 2763 : 145659 : deletable[ndeletable++] = offnum;
2764 : : }
2765 : :
2766 [ + + ]: 33359 : if (ndeletable > 0)
2767 : : {
2076 pg@bowt.ie 2768 : 4585 : _bt_simpledel_pass(rel, buffer, heapRel, deletable, ndeletable,
2769 : : insertstate->itup, minoff, maxoff);
2133 2770 : 4585 : insertstate->bounds_valid = false;
2771 : :
2772 : : /* Return when a page split has already been avoided */
2773 [ + + ]: 4585 : if (PageGetFreeSpace(page) >= insertstate->itemsz)
2774 : 14733 : return;
2775 : :
2776 : : /* Might as well assume duplicates (if checkingunique) */
2777 : 58 : uniquedup = true;
2778 : : }
2779 : :
2780 : : /*
2781 : : * We're done with simple deletion. Return early with callers that only
2782 : : * call here so that simple deletion can be considered. This includes
2783 : : * callers that explicitly ask for this and checkingunique callers that
2784 : : * probably don't have any version churn duplicates on the page.
2785 : : *
2786 : : * Note: The page's BTP_HAS_GARBAGE hint flag may still be set when we
2787 : : * return at this point (or when we go on the try either or both of our
2788 : : * other strategies and they also fail). We do not bother expending a
2789 : : * separate write to clear it, however. Caller will definitely clear it
2790 : : * when it goes on to split the page (note also that the deduplication
2791 : : * process will clear the flag in passing, just to keep things tidy).
2792 : : */
2076 2793 [ + - + + : 28832 : if (simpleonly || (checkingunique && !uniquedup))
+ + ]
2794 : : {
2795 [ - + ]: 9911 : Assert(!indexUnchanged);
2133 2796 : 9911 : return;
2797 : : }
2798 : :
2799 : : /* Assume bounds about to be invalidated (this is almost certain now) */
2800 : 18921 : insertstate->bounds_valid = false;
2801 : :
2802 : : /*
2803 : : * Perform bottom-up index deletion pass when executor hint indicated that
2804 : : * incoming item is logically unchanged, or for a unique index that is
2805 : : * known to have physical duplicates for some other reason. (There is a
2806 : : * large overlap between these two cases for a unique index. It's worth
2807 : : * having both triggering conditions in order to apply the optimization in
2808 : : * the event of successive related INSERT and DELETE statements.)
2809 : : *
2810 : : * We'll go on to do a deduplication pass when a bottom-up pass fails to
2811 : : * delete an acceptable amount of free space (a significant fraction of
2812 : : * the page, or space for the new item, whichever is greater).
2813 : : *
2814 : : * Note: Bottom-up index deletion uses the same equality/equivalence
2815 : : * routines as deduplication internally. However, it does not merge
2816 : : * together index tuples, so the same correctness considerations do not
2817 : : * apply. We deliberately omit an index-is-allequalimage test here.
2818 : : */
2076 2819 [ + + + + : 21903 : if ((indexUnchanged || uniquedup) &&
+ + ]
2820 : 2982 : _bt_bottomupdel_pass(rel, buffer, heapRel, insertstate->itemsz))
2821 : 295 : return;
2822 : :
2823 : : /* Perform deduplication pass (when enabled and index-is-allequalimage) */
2133 2824 [ + - - + : 18626 : if (BTGetDeduplicateItems(rel) && itup_key->allequalimage)
+ + + + +
+ + - ]
1251 2825 : 18591 : _bt_dedup_pass(rel, buffer, insertstate->itup, insertstate->itemsz,
2826 [ + + + + ]: 18591 : (indexUnchanged || uniquedup));
2827 : : }
2828 : :
2829 : : /*
2830 : : * _bt_simpledel_pass - Simple index tuple deletion pass.
2831 : : *
2832 : : * We delete all LP_DEAD-set index tuples on a leaf page. The offset numbers
2833 : : * of all such tuples are determined by caller (caller passes these to us as
2834 : : * its 'deletable' argument).
2835 : : *
2836 : : * We might also delete extra index tuples that turn out to be safe to delete
2837 : : * in passing (though they must be cheap to check in passing to begin with).
2838 : : * There is no certainty that any extra tuples will be deleted, though. The
2839 : : * high level goal of the approach we take is to get the most out of each call
2840 : : * here (without noticeably increasing the per-call overhead compared to what
2841 : : * we need to do just to be able to delete the page's LP_DEAD-marked index
2842 : : * tuples).
2843 : : *
2844 : : * The number of extra index tuples that turn out to be deletable might
2845 : : * greatly exceed the number of LP_DEAD-marked index tuples due to various
2846 : : * locality related effects. For example, it's possible that the total number
2847 : : * of table blocks (pointed to by all TIDs on the leaf page) is naturally
2848 : : * quite low, in which case we might end up checking if it's possible to
2849 : : * delete _most_ index tuples on the page (without the tableam needing to
2850 : : * access additional table blocks). The tableam will sometimes stumble upon
2851 : : * _many_ extra deletable index tuples in indexes where this pattern is
2852 : : * common.
2853 : : *
2854 : : * See nbtree/README for further details on simple index tuple deletion.
2855 : : */
2856 : : static void
2076 2857 : 4585 : _bt_simpledel_pass(Relation rel, Buffer buffer, Relation heapRel,
2858 : : OffsetNumber *deletable, int ndeletable, IndexTuple newitem,
2859 : : OffsetNumber minoff, OffsetNumber maxoff)
2860 : : {
2861 : 4585 : Page page = BufferGetPage(buffer);
2862 : : BlockNumber *deadblocks;
2863 : : int ndeadblocks;
2864 : : TM_IndexDeleteOp delstate;
2865 : : OffsetNumber offnum;
2866 : :
2867 : : /* Get array of table blocks pointed to by LP_DEAD-set tuples */
2868 : 4585 : deadblocks = _bt_deadblocks(page, deletable, ndeletable, newitem,
2869 : : &ndeadblocks);
2870 : :
2871 : : /* Initialize tableam state that describes index deletion operation */
1781 2872 : 4585 : delstate.irel = rel;
2873 : 4585 : delstate.iblknum = BufferGetBlockNumber(buffer);
2076 2874 : 4585 : delstate.bottomup = false;
2875 : 4585 : delstate.bottomupfreespace = 0;
2876 : 4585 : delstate.ndeltids = 0;
34 michael@paquier.xyz 2877 :GNC 4585 : delstate.deltids = palloc_array(TM_IndexDelete, MaxTIDsPerBTreePage);
2878 : 4585 : delstate.status = palloc_array(TM_IndexStatus, MaxTIDsPerBTreePage);
2879 : :
2076 pg@bowt.ie 2880 :CBC 4585 : for (offnum = minoff;
2881 [ + + ]: 1309018 : offnum <= maxoff;
2882 : 1304433 : offnum = OffsetNumberNext(offnum))
2883 : : {
2884 : 1304433 : ItemId itemid = PageGetItemId(page, offnum);
2885 : 1304433 : IndexTuple itup = (IndexTuple) PageGetItem(page, itemid);
2886 : 1304433 : TM_IndexDelete *odeltid = &delstate.deltids[delstate.ndeltids];
2887 : 1304433 : TM_IndexStatus *ostatus = &delstate.status[delstate.ndeltids];
2888 : : BlockNumber tidblock;
2889 : : void *match;
2890 : :
2891 [ + + ]: 1304433 : if (!BTreeTupleIsPosting(itup))
2892 : : {
2893 : 1244138 : tidblock = ItemPointerGetBlockNumber(&itup->t_tid);
2894 : 1244138 : match = bsearch(&tidblock, deadblocks, ndeadblocks,
2895 : : sizeof(BlockNumber), _bt_blk_cmp);
2896 : :
2897 [ + + ]: 1244138 : if (!match)
2898 : : {
2899 [ - + ]: 798031 : Assert(!ItemIdIsDead(itemid));
2900 : 798031 : continue;
2901 : : }
2902 : :
2903 : : /*
2904 : : * TID's table block is among those pointed to by the TIDs from
2905 : : * LP_DEAD-bit set tuples on page -- add TID to deltids
2906 : : */
2907 : 446107 : odeltid->tid = itup->t_tid;
2908 : 446107 : odeltid->id = delstate.ndeltids;
2909 : 446107 : ostatus->idxoffnum = offnum;
2910 : 446107 : ostatus->knowndeletable = ItemIdIsDead(itemid);
2911 : 446107 : ostatus->promising = false; /* unused */
2912 : 446107 : ostatus->freespace = 0; /* unused */
2913 : :
2914 : 446107 : delstate.ndeltids++;
2915 : : }
2916 : : else
2917 : : {
2918 : 60295 : int nitem = BTreeTupleGetNPosting(itup);
2919 : :
2920 [ + + ]: 296055 : for (int p = 0; p < nitem; p++)
2921 : : {
2922 : 235760 : ItemPointer tid = BTreeTupleGetPostingN(itup, p);
2923 : :
2924 : 235760 : tidblock = ItemPointerGetBlockNumber(tid);
2925 : 235760 : match = bsearch(&tidblock, deadblocks, ndeadblocks,
2926 : : sizeof(BlockNumber), _bt_blk_cmp);
2927 : :
2928 [ + + ]: 235760 : if (!match)
2929 : : {
2930 [ - + ]: 208991 : Assert(!ItemIdIsDead(itemid));
2931 : 208991 : continue;
2932 : : }
2933 : :
2934 : : /*
2935 : : * TID's table block is among those pointed to by the TIDs
2936 : : * from LP_DEAD-bit set tuples on page -- add TID to deltids
2937 : : */
2938 : 26769 : odeltid->tid = *tid;
2939 : 26769 : odeltid->id = delstate.ndeltids;
2940 : 26769 : ostatus->idxoffnum = offnum;
2941 : 26769 : ostatus->knowndeletable = ItemIdIsDead(itemid);
2942 : 26769 : ostatus->promising = false; /* unused */
2943 : 26769 : ostatus->freespace = 0; /* unused */
2944 : :
2945 : 26769 : odeltid++;
2946 : 26769 : ostatus++;
2947 : 26769 : delstate.ndeltids++;
2948 : : }
2949 : : }
2950 : : }
2951 : :
2952 : 4585 : pfree(deadblocks);
2953 : :
2954 [ - + ]: 4585 : Assert(delstate.ndeltids >= ndeletable);
2955 : :
2956 : : /* Physically delete LP_DEAD tuples (plus any delete-safe extra TIDs) */
2957 : 4585 : _bt_delitems_delete_check(rel, buffer, heapRel, &delstate);
2958 : :
2959 : 4585 : pfree(delstate.deltids);
2960 : 4585 : pfree(delstate.status);
2961 : 4585 : }
2962 : :
2963 : : /*
2964 : : * _bt_deadblocks() -- Get LP_DEAD related table blocks.
2965 : : *
2966 : : * Builds sorted and unique-ified array of table block numbers from index
2967 : : * tuple TIDs whose line pointers are marked LP_DEAD. Also adds the table
2968 : : * block from incoming newitem just in case it isn't among the LP_DEAD-related
2969 : : * table blocks.
2970 : : *
2971 : : * Always counting the newitem's table block as an LP_DEAD related block makes
2972 : : * sense because the cost is consistently low; it is practically certain that
2973 : : * the table block will not incur a buffer miss in tableam. On the other hand
2974 : : * the benefit is often quite high. There is a decent chance that there will
2975 : : * be some deletable items from this block, since in general most garbage
2976 : : * tuples became garbage in the recent past (in many cases this won't be the
2977 : : * first logical row that core code added to/modified in table block
2978 : : * recently).
2979 : : *
2980 : : * Returns final array, and sets *nblocks to its final size for caller.
2981 : : */
2982 : : static BlockNumber *
2983 : 4585 : _bt_deadblocks(Page page, OffsetNumber *deletable, int ndeletable,
2984 : : IndexTuple newitem, int *nblocks)
2985 : : {
2986 : : int spacentids,
2987 : : ntids;
2988 : : BlockNumber *tidblocks;
2989 : :
2990 : : /*
2991 : : * Accumulate each TID's block in array whose initial size has space for
2992 : : * one table block per LP_DEAD-set tuple (plus space for the newitem table
2993 : : * block). Array will only need to grow when there are LP_DEAD-marked
2994 : : * posting list tuples (which is not that common).
2995 : : */
2996 : 4585 : spacentids = ndeletable + 1;
2997 : 4585 : ntids = 0;
284 michael@paquier.xyz 2998 : 4585 : tidblocks = palloc_array(BlockNumber, spacentids);
2999 : :
3000 : : /*
3001 : : * First add the table block for the incoming newitem. This is the one
3002 : : * case where simple deletion can visit a table block that doesn't have
3003 : : * any known deletable items.
3004 : : */
2076 pg@bowt.ie 3005 [ + - - + ]: 4585 : Assert(!BTreeTupleIsPosting(newitem) && !BTreeTupleIsPivot(newitem));
3006 : 4585 : tidblocks[ntids++] = ItemPointerGetBlockNumber(&newitem->t_tid);
3007 : :
3008 [ + + ]: 150244 : for (int i = 0; i < ndeletable; i++)
3009 : : {
3010 : 145659 : ItemId itemid = PageGetItemId(page, deletable[i]);
3011 : 145659 : IndexTuple itup = (IndexTuple) PageGetItem(page, itemid);
3012 : :
3013 [ - + ]: 145659 : Assert(ItemIdIsDead(itemid));
3014 : :
3015 [ + + ]: 145659 : if (!BTreeTupleIsPosting(itup))
3016 : : {
3017 [ + + ]: 141439 : if (ntids + 1 > spacentids)
3018 : : {
3019 : 112 : spacentids *= 2;
34 michael@paquier.xyz 3020 :GNC 112 : tidblocks = repalloc_array(tidblocks, BlockNumber, spacentids);
3021 : : }
3022 : :
2076 pg@bowt.ie 3023 :CBC 141439 : tidblocks[ntids++] = ItemPointerGetBlockNumber(&itup->t_tid);
3024 : : }
3025 : : else
3026 : : {
3027 : 4220 : int nposting = BTreeTupleGetNPosting(itup);
3028 : :
3029 [ + + ]: 4220 : if (ntids + nposting > spacentids)
3030 : : {
3031 : 100 : spacentids = Max(spacentids * 2, ntids + nposting);
34 michael@paquier.xyz 3032 :GNC 100 : tidblocks = repalloc_array(tidblocks, BlockNumber, spacentids);
3033 : : }
3034 : :
2076 pg@bowt.ie 3035 [ + + ]:CBC 14278 : for (int j = 0; j < nposting; j++)
3036 : : {
3037 : 10058 : ItemPointer tid = BTreeTupleGetPostingN(itup, j);
3038 : :
3039 : 10058 : tidblocks[ntids++] = ItemPointerGetBlockNumber(tid);
3040 : : }
3041 : : }
3042 : : }
3043 : :
3044 : 4585 : qsort(tidblocks, ntids, sizeof(BlockNumber), _bt_blk_cmp);
3045 : 4585 : *nblocks = qunique(tidblocks, ntids, sizeof(BlockNumber), _bt_blk_cmp);
3046 : :
3047 : 4585 : return tidblocks;
3048 : : }
3049 : :
3050 : : /*
3051 : : * _bt_blk_cmp() -- qsort comparison function for _bt_simpledel_pass
3052 : : */
3053 : : static inline int
3054 : 3234777 : _bt_blk_cmp(const void *arg1, const void *arg2)
3055 : : {
237 peter@eisentraut.org 3056 : 3234777 : BlockNumber b1 = *((const BlockNumber *) arg1);
3057 : 3234777 : BlockNumber b2 = *((const BlockNumber *) arg2);
3058 : :
947 nathan@postgresql.or 3059 : 3234777 : return pg_cmp_u32(b1, b2);
3060 : : }
|
