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