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