PostgreSQL Source Code  git master
pruneheap.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * pruneheap.c
4  * heap page pruning and HOT-chain management code
5  *
6  * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  *
10  * IDENTIFICATION
11  * src/backend/access/heap/pruneheap.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 #include "postgres.h"
16 
17 #include "access/heapam.h"
18 #include "access/heapam_xlog.h"
19 #include "access/transam.h"
20 #include "access/htup_details.h"
21 #include "access/xlog.h"
22 #include "catalog/catalog.h"
23 #include "miscadmin.h"
24 #include "pgstat.h"
25 #include "storage/bufmgr.h"
26 #include "utils/snapmgr.h"
27 #include "utils/rel.h"
28 #include "utils/tqual.h"
29 
30 /* Working data for heap_page_prune and subroutines */
31 typedef struct
32 {
33  TransactionId new_prune_xid; /* new prune hint value for page */
34  TransactionId latestRemovedXid; /* latest xid to be removed by this prune */
35  int nredirected; /* numbers of entries in arrays below */
36  int ndead;
37  int nunused;
38  /* arrays that accumulate indexes of items to be changed */
42  /* marked[i] is true if item i is entered in one of the above arrays */
43  bool marked[MaxHeapTuplesPerPage + 1];
44 } PruneState;
45 
46 /* Local functions */
47 static int heap_prune_chain(Relation relation, Buffer buffer,
48  OffsetNumber rootoffnum,
50  PruneState *prstate);
51 static void heap_prune_record_prunable(PruneState *prstate, TransactionId xid);
52 static void heap_prune_record_redirect(PruneState *prstate,
53  OffsetNumber offnum, OffsetNumber rdoffnum);
54 static void heap_prune_record_dead(PruneState *prstate, OffsetNumber offnum);
55 static void heap_prune_record_unused(PruneState *prstate, OffsetNumber offnum);
56 
57 
58 /*
59  * Optionally prune and repair fragmentation in the specified page.
60  *
61  * This is an opportunistic function. It will perform housekeeping
62  * only if the page heuristically looks like a candidate for pruning and we
63  * can acquire buffer cleanup lock without blocking.
64  *
65  * Note: this is called quite often. It's important that it fall out quickly
66  * if there's not any use in pruning.
67  *
68  * Caller must have pin on the buffer, and must *not* have a lock on it.
69  *
70  * OldestXmin is the cutoff XID used to distinguish whether tuples are DEAD
71  * or RECENTLY_DEAD (see HeapTupleSatisfiesVacuum).
72  */
73 void
75 {
76  Page page = BufferGetPage(buffer);
77  Size minfree;
79 
80  /*
81  * We can't write WAL in recovery mode, so there's no point trying to
82  * clean the page. The master will likely issue a cleaning WAL record soon
83  * anyway, so this is no particular loss.
84  */
85  if (RecoveryInProgress())
86  return;
87 
88  /*
89  * Use the appropriate xmin horizon for this relation. If it's a proper
90  * catalog relation or a user defined, additional, catalog relation, we
91  * need to use the horizon that includes slots, otherwise the data-only
92  * horizon can be used. Note that the toast relation of user defined
93  * relations are *not* considered catalog relations.
94  *
95  * It is OK to apply the old snapshot limit before acquiring the cleanup
96  * lock because the worst that can happen is that we are not quite as
97  * aggressive about the cleanup (by however many transaction IDs are
98  * consumed between this point and acquiring the lock). This allows us to
99  * save significant overhead in the case where the page is found not to be
100  * prunable.
101  */
102  if (IsCatalogRelation(relation) ||
104  OldestXmin = RecentGlobalXmin;
105  else
106  OldestXmin =
108  relation);
109 
110  Assert(TransactionIdIsValid(OldestXmin));
111 
112  /*
113  * Let's see if we really need pruning.
114  *
115  * Forget it if page is not hinted to contain something prunable that's
116  * older than OldestXmin.
117  */
118  if (!PageIsPrunable(page, OldestXmin))
119  return;
120 
121  /*
122  * We prune when a previous UPDATE failed to find enough space on the page
123  * for a new tuple version, or when free space falls below the relation's
124  * fill-factor target (but not less than 10%).
125  *
126  * Checking free space here is questionable since we aren't holding any
127  * lock on the buffer; in the worst case we could get a bogus answer. It's
128  * unlikely to be *seriously* wrong, though, since reading either pd_lower
129  * or pd_upper is probably atomic. Avoiding taking a lock seems more
130  * important than sometimes getting a wrong answer in what is after all
131  * just a heuristic estimate.
132  */
133  minfree = RelationGetTargetPageFreeSpace(relation,
135  minfree = Max(minfree, BLCKSZ / 10);
136 
137  if (PageIsFull(page) || PageGetHeapFreeSpace(page) < minfree)
138  {
139  /* OK, try to get exclusive buffer lock */
140  if (!ConditionalLockBufferForCleanup(buffer))
141  return;
142 
143  /*
144  * Now that we have buffer lock, get accurate information about the
145  * page's free space, and recheck the heuristic about whether to
146  * prune. (We needn't recheck PageIsPrunable, since no one else could
147  * have pruned while we hold pin.)
148  */
149  if (PageIsFull(page) || PageGetHeapFreeSpace(page) < minfree)
150  {
151  TransactionId ignore = InvalidTransactionId; /* return value not
152  * needed */
153 
154  /* OK to prune */
155  (void) heap_page_prune(relation, buffer, OldestXmin, true, &ignore);
156  }
157 
158  /* And release buffer lock */
160  }
161 }
162 
163 
164 /*
165  * Prune and repair fragmentation in the specified page.
166  *
167  * Caller must have pin and buffer cleanup lock on the page.
168  *
169  * OldestXmin is the cutoff XID used to distinguish whether tuples are DEAD
170  * or RECENTLY_DEAD (see HeapTupleSatisfiesVacuum).
171  *
172  * If report_stats is true then we send the number of reclaimed heap-only
173  * tuples to pgstats. (This must be false during vacuum, since vacuum will
174  * send its own new total to pgstats, and we don't want this delta applied
175  * on top of that.)
176  *
177  * Returns the number of tuples deleted from the page and sets
178  * latestRemovedXid.
179  */
180 int
182  bool report_stats, TransactionId *latestRemovedXid)
183 {
184  int ndeleted = 0;
185  Page page = BufferGetPage(buffer);
186  OffsetNumber offnum,
187  maxoff;
188  PruneState prstate;
189 
190  /*
191  * Our strategy is to scan the page and make lists of items to change,
192  * then apply the changes within a critical section. This keeps as much
193  * logic as possible out of the critical section, and also ensures that
194  * WAL replay will work the same as the normal case.
195  *
196  * First, initialize the new pd_prune_xid value to zero (indicating no
197  * prunable tuples). If we find any tuples which may soon become
198  * prunable, we will save the lowest relevant XID in new_prune_xid. Also
199  * initialize the rest of our working state.
200  */
202  prstate.latestRemovedXid = *latestRemovedXid;
203  prstate.nredirected = prstate.ndead = prstate.nunused = 0;
204  memset(prstate.marked, 0, sizeof(prstate.marked));
205 
206  /* Scan the page */
207  maxoff = PageGetMaxOffsetNumber(page);
208  for (offnum = FirstOffsetNumber;
209  offnum <= maxoff;
210  offnum = OffsetNumberNext(offnum))
211  {
212  ItemId itemid;
213 
214  /* Ignore items already processed as part of an earlier chain */
215  if (prstate.marked[offnum])
216  continue;
217 
218  /* Nothing to do if slot is empty or already dead */
219  itemid = PageGetItemId(page, offnum);
220  if (!ItemIdIsUsed(itemid) || ItemIdIsDead(itemid))
221  continue;
222 
223  /* Process this item or chain of items */
224  ndeleted += heap_prune_chain(relation, buffer, offnum,
225  OldestXmin,
226  &prstate);
227  }
228 
229  /* Any error while applying the changes is critical */
231 
232  /* Have we found any prunable items? */
233  if (prstate.nredirected > 0 || prstate.ndead > 0 || prstate.nunused > 0)
234  {
235  /*
236  * Apply the planned item changes, then repair page fragmentation, and
237  * update the page's hint bit about whether it has free line pointers.
238  */
240  prstate.redirected, prstate.nredirected,
241  prstate.nowdead, prstate.ndead,
242  prstate.nowunused, prstate.nunused);
243 
244  /*
245  * Update the page's pd_prune_xid field to either zero, or the lowest
246  * XID of any soon-prunable tuple.
247  */
248  ((PageHeader) page)->pd_prune_xid = prstate.new_prune_xid;
249 
250  /*
251  * Also clear the "page is full" flag, since there's no point in
252  * repeating the prune/defrag process until something else happens to
253  * the page.
254  */
255  PageClearFull(page);
256 
257  MarkBufferDirty(buffer);
258 
259  /*
260  * Emit a WAL HEAP_CLEAN record showing what we did
261  */
262  if (RelationNeedsWAL(relation))
263  {
264  XLogRecPtr recptr;
265 
266  recptr = log_heap_clean(relation, buffer,
267  prstate.redirected, prstate.nredirected,
268  prstate.nowdead, prstate.ndead,
269  prstate.nowunused, prstate.nunused,
270  prstate.latestRemovedXid);
271 
272  PageSetLSN(BufferGetPage(buffer), recptr);
273  }
274  }
275  else
276  {
277  /*
278  * If we didn't prune anything, but have found a new value for the
279  * pd_prune_xid field, update it and mark the buffer dirty. This is
280  * treated as a non-WAL-logged hint.
281  *
282  * Also clear the "page is full" flag if it is set, since there's no
283  * point in repeating the prune/defrag process until something else
284  * happens to the page.
285  */
286  if (((PageHeader) page)->pd_prune_xid != prstate.new_prune_xid ||
287  PageIsFull(page))
288  {
289  ((PageHeader) page)->pd_prune_xid = prstate.new_prune_xid;
290  PageClearFull(page);
291  MarkBufferDirtyHint(buffer, true);
292  }
293  }
294 
296 
297  /*
298  * If requested, report the number of tuples reclaimed to pgstats. This is
299  * ndeleted minus ndead, because we don't want to count a now-DEAD root
300  * item as a deletion for this purpose.
301  */
302  if (report_stats && ndeleted > prstate.ndead)
303  pgstat_update_heap_dead_tuples(relation, ndeleted - prstate.ndead);
304 
305  *latestRemovedXid = prstate.latestRemovedXid;
306 
307  /*
308  * XXX Should we update the FSM information of this page ?
309  *
310  * There are two schools of thought here. We may not want to update FSM
311  * information so that the page is not used for unrelated UPDATEs/INSERTs
312  * and any free space in this page will remain available for further
313  * UPDATEs in *this* page, thus improving chances for doing HOT updates.
314  *
315  * But for a large table and where a page does not receive further UPDATEs
316  * for a long time, we might waste this space by not updating the FSM
317  * information. The relation may get extended and fragmented further.
318  *
319  * One possibility is to leave "fillfactor" worth of space in this page
320  * and update FSM with the remaining space.
321  */
322 
323  return ndeleted;
324 }
325 
326 
327 /*
328  * Prune specified item pointer or a HOT chain originating at that item.
329  *
330  * If the item is an index-referenced tuple (i.e. not a heap-only tuple),
331  * the HOT chain is pruned by removing all DEAD tuples at the start of the HOT
332  * chain. We also prune any RECENTLY_DEAD tuples preceding a DEAD tuple.
333  * This is OK because a RECENTLY_DEAD tuple preceding a DEAD tuple is really
334  * DEAD, the OldestXmin test is just too coarse to detect it.
335  *
336  * The root line pointer is redirected to the tuple immediately after the
337  * latest DEAD tuple. If all tuples in the chain are DEAD, the root line
338  * pointer is marked LP_DEAD. (This includes the case of a DEAD simple
339  * tuple, which we treat as a chain of length 1.)
340  *
341  * OldestXmin is the cutoff XID used to identify dead tuples.
342  *
343  * We don't actually change the page here, except perhaps for hint-bit updates
344  * caused by HeapTupleSatisfiesVacuum. We just add entries to the arrays in
345  * prstate showing the changes to be made. Items to be redirected are added
346  * to the redirected[] array (two entries per redirection); items to be set to
347  * LP_DEAD state are added to nowdead[]; and items to be set to LP_UNUSED
348  * state are added to nowunused[].
349  *
350  * Returns the number of tuples (to be) deleted from the page.
351  */
352 static int
355  PruneState *prstate)
356 {
357  int ndeleted = 0;
358  Page dp = (Page) BufferGetPage(buffer);
360  ItemId rootlp;
361  HeapTupleHeader htup;
362  OffsetNumber latestdead = InvalidOffsetNumber,
363  maxoff = PageGetMaxOffsetNumber(dp),
364  offnum;
366  int nchain = 0,
367  i;
368  HeapTupleData tup;
369 
370  tup.t_tableOid = RelationGetRelid(relation);
371 
372  rootlp = PageGetItemId(dp, rootoffnum);
373 
374  /*
375  * If it's a heap-only tuple, then it is not the start of a HOT chain.
376  */
377  if (ItemIdIsNormal(rootlp))
378  {
379  htup = (HeapTupleHeader) PageGetItem(dp, rootlp);
380 
381  tup.t_data = htup;
382  tup.t_len = ItemIdGetLength(rootlp);
383  ItemPointerSet(&(tup.t_self), BufferGetBlockNumber(buffer), rootoffnum);
384 
385  if (HeapTupleHeaderIsHeapOnly(htup))
386  {
387  /*
388  * If the tuple is DEAD and doesn't chain to anything else, mark
389  * it unused immediately. (If it does chain, we can only remove
390  * it as part of pruning its chain.)
391  *
392  * We need this primarily to handle aborted HOT updates, that is,
393  * XMIN_INVALID heap-only tuples. Those might not be linked to by
394  * any chain, since the parent tuple might be re-updated before
395  * any pruning occurs. So we have to be able to reap them
396  * separately from chain-pruning. (Note that
397  * HeapTupleHeaderIsHotUpdated will never return true for an
398  * XMIN_INVALID tuple, so this code will work even when there were
399  * sequential updates within the aborted transaction.)
400  *
401  * Note that we might first arrive at a dead heap-only tuple
402  * either here or while following a chain below. Whichever path
403  * gets there first will mark the tuple unused.
404  */
405  if (HeapTupleSatisfiesVacuum(&tup, OldestXmin, buffer)
407  {
408  heap_prune_record_unused(prstate, rootoffnum);
410  &prstate->latestRemovedXid);
411  ndeleted++;
412  }
413 
414  /* Nothing more to do */
415  return ndeleted;
416  }
417  }
418 
419  /* Start from the root tuple */
420  offnum = rootoffnum;
421 
422  /* while not end of the chain */
423  for (;;)
424  {
425  ItemId lp;
426  bool tupdead,
427  recent_dead;
428 
429  /* Some sanity checks */
430  if (offnum < FirstOffsetNumber || offnum > maxoff)
431  break;
432 
433  /* If item is already processed, stop --- it must not be same chain */
434  if (prstate->marked[offnum])
435  break;
436 
437  lp = PageGetItemId(dp, offnum);
438 
439  /* Unused item obviously isn't part of the chain */
440  if (!ItemIdIsUsed(lp))
441  break;
442 
443  /*
444  * If we are looking at the redirected root line pointer, jump to the
445  * first normal tuple in the chain. If we find a redirect somewhere
446  * else, stop --- it must not be same chain.
447  */
448  if (ItemIdIsRedirected(lp))
449  {
450  if (nchain > 0)
451  break; /* not at start of chain */
452  chainitems[nchain++] = offnum;
453  offnum = ItemIdGetRedirect(rootlp);
454  continue;
455  }
456 
457  /*
458  * Likewise, a dead item pointer can't be part of the chain. (We
459  * already eliminated the case of dead root tuple outside this
460  * function.)
461  */
462  if (ItemIdIsDead(lp))
463  break;
464 
465  Assert(ItemIdIsNormal(lp));
466  htup = (HeapTupleHeader) PageGetItem(dp, lp);
467 
468  tup.t_data = htup;
469  tup.t_len = ItemIdGetLength(lp);
470  ItemPointerSet(&(tup.t_self), BufferGetBlockNumber(buffer), offnum);
471 
472  /*
473  * Check the tuple XMIN against prior XMAX, if any
474  */
475  if (TransactionIdIsValid(priorXmax) &&
476  !TransactionIdEquals(HeapTupleHeaderGetXmin(htup), priorXmax))
477  break;
478 
479  /*
480  * OK, this tuple is indeed a member of the chain.
481  */
482  chainitems[nchain++] = offnum;
483 
484  /*
485  * Check tuple's visibility status.
486  */
487  tupdead = recent_dead = false;
488 
489  switch (HeapTupleSatisfiesVacuum(&tup, OldestXmin, buffer))
490  {
491  case HEAPTUPLE_DEAD:
492  tupdead = true;
493  break;
494 
496  recent_dead = true;
497 
498  /*
499  * This tuple may soon become DEAD. Update the hint field so
500  * that the page is reconsidered for pruning in future.
501  */
504  break;
505 
507 
508  /*
509  * This tuple may soon become DEAD. Update the hint field so
510  * that the page is reconsidered for pruning in future.
511  */
514  break;
515 
516  case HEAPTUPLE_LIVE:
518 
519  /*
520  * If we wanted to optimize for aborts, we might consider
521  * marking the page prunable when we see INSERT_IN_PROGRESS.
522  * But we don't. See related decisions about when to mark the
523  * page prunable in heapam.c.
524  */
525  break;
526 
527  default:
528  elog(ERROR, "unexpected HeapTupleSatisfiesVacuum result");
529  break;
530  }
531 
532  /*
533  * Remember the last DEAD tuple seen. We will advance past
534  * RECENTLY_DEAD tuples just in case there's a DEAD one after them;
535  * but we can't advance past anything else. (XXX is it really worth
536  * continuing to scan beyond RECENTLY_DEAD? The case where we will
537  * find another DEAD tuple is a fairly unusual corner case.)
538  */
539  if (tupdead)
540  {
541  latestdead = offnum;
543  &prstate->latestRemovedXid);
544  }
545  else if (!recent_dead)
546  break;
547 
548  /*
549  * If the tuple is not HOT-updated, then we are at the end of this
550  * HOT-update chain.
551  */
552  if (!HeapTupleHeaderIsHotUpdated(htup))
553  break;
554 
555  /* HOT implies it can't have moved to different partition */
557 
558  /*
559  * Advance to next chain member.
560  */
562  BufferGetBlockNumber(buffer));
563  offnum = ItemPointerGetOffsetNumber(&htup->t_ctid);
564  priorXmax = HeapTupleHeaderGetUpdateXid(htup);
565  }
566 
567  /*
568  * If we found a DEAD tuple in the chain, adjust the HOT chain so that all
569  * the DEAD tuples at the start of the chain are removed and the root line
570  * pointer is appropriately redirected.
571  */
572  if (OffsetNumberIsValid(latestdead))
573  {
574  /*
575  * Mark as unused each intermediate item that we are able to remove
576  * from the chain.
577  *
578  * When the previous item is the last dead tuple seen, we are at the
579  * right candidate for redirection.
580  */
581  for (i = 1; (i < nchain) && (chainitems[i - 1] != latestdead); i++)
582  {
583  heap_prune_record_unused(prstate, chainitems[i]);
584  ndeleted++;
585  }
586 
587  /*
588  * If the root entry had been a normal tuple, we are deleting it, so
589  * count it in the result. But changing a redirect (even to DEAD
590  * state) doesn't count.
591  */
592  if (ItemIdIsNormal(rootlp))
593  ndeleted++;
594 
595  /*
596  * If the DEAD tuple is at the end of the chain, the entire chain is
597  * dead and the root line pointer can be marked dead. Otherwise just
598  * redirect the root to the correct chain member.
599  */
600  if (i >= nchain)
601  heap_prune_record_dead(prstate, rootoffnum);
602  else
603  heap_prune_record_redirect(prstate, rootoffnum, chainitems[i]);
604  }
605  else if (nchain < 2 && ItemIdIsRedirected(rootlp))
606  {
607  /*
608  * We found a redirect item that doesn't point to a valid follow-on
609  * item. This can happen if the loop in heap_page_prune caused us to
610  * visit the dead successor of a redirect item before visiting the
611  * redirect item. We can clean up by setting the redirect item to
612  * DEAD state.
613  */
614  heap_prune_record_dead(prstate, rootoffnum);
615  }
616 
617  return ndeleted;
618 }
619 
620 /* Record lowest soon-prunable XID */
621 static void
623 {
624  /*
625  * This should exactly match the PageSetPrunable macro. We can't store
626  * directly into the page header yet, so we update working state.
627  */
629  if (!TransactionIdIsValid(prstate->new_prune_xid) ||
630  TransactionIdPrecedes(xid, prstate->new_prune_xid))
631  prstate->new_prune_xid = xid;
632 }
633 
634 /* Record item pointer to be redirected */
635 static void
637  OffsetNumber offnum, OffsetNumber rdoffnum)
638 {
640  prstate->redirected[prstate->nredirected * 2] = offnum;
641  prstate->redirected[prstate->nredirected * 2 + 1] = rdoffnum;
642  prstate->nredirected++;
643  Assert(!prstate->marked[offnum]);
644  prstate->marked[offnum] = true;
645  Assert(!prstate->marked[rdoffnum]);
646  prstate->marked[rdoffnum] = true;
647 }
648 
649 /* Record item pointer to be marked dead */
650 static void
652 {
653  Assert(prstate->ndead < MaxHeapTuplesPerPage);
654  prstate->nowdead[prstate->ndead] = offnum;
655  prstate->ndead++;
656  Assert(!prstate->marked[offnum]);
657  prstate->marked[offnum] = true;
658 }
659 
660 /* Record item pointer to be marked unused */
661 static void
663 {
664  Assert(prstate->nunused < MaxHeapTuplesPerPage);
665  prstate->nowunused[prstate->nunused] = offnum;
666  prstate->nunused++;
667  Assert(!prstate->marked[offnum]);
668  prstate->marked[offnum] = true;
669 }
670 
671 
672 /*
673  * Perform the actual page changes needed by heap_page_prune.
674  * It is expected that the caller has suitable pin and lock on the
675  * buffer, and is inside a critical section.
676  *
677  * This is split out because it is also used by heap_xlog_clean()
678  * to replay the WAL record when needed after a crash. Note that the
679  * arguments are identical to those of log_heap_clean().
680  */
681 void
683  OffsetNumber *redirected, int nredirected,
684  OffsetNumber *nowdead, int ndead,
685  OffsetNumber *nowunused, int nunused)
686 {
687  Page page = (Page) BufferGetPage(buffer);
688  OffsetNumber *offnum;
689  int i;
690 
691  /* Update all redirected line pointers */
692  offnum = redirected;
693  for (i = 0; i < nredirected; i++)
694  {
695  OffsetNumber fromoff = *offnum++;
696  OffsetNumber tooff = *offnum++;
697  ItemId fromlp = PageGetItemId(page, fromoff);
698 
699  ItemIdSetRedirect(fromlp, tooff);
700  }
701 
702  /* Update all now-dead line pointers */
703  offnum = nowdead;
704  for (i = 0; i < ndead; i++)
705  {
706  OffsetNumber off = *offnum++;
707  ItemId lp = PageGetItemId(page, off);
708 
709  ItemIdSetDead(lp);
710  }
711 
712  /* Update all now-unused line pointers */
713  offnum = nowunused;
714  for (i = 0; i < nunused; i++)
715  {
716  OffsetNumber off = *offnum++;
717  ItemId lp = PageGetItemId(page, off);
718 
719  ItemIdSetUnused(lp);
720  }
721 
722  /*
723  * Finally, repair any fragmentation, and update the page's hint bit about
724  * whether it has free pointers.
725  */
727 }
728 
729 
730 /*
731  * For all items in this page, find their respective root line pointers.
732  * If item k is part of a HOT-chain with root at item j, then we set
733  * root_offsets[k - 1] = j.
734  *
735  * The passed-in root_offsets array must have MaxHeapTuplesPerPage entries.
736  * We zero out all unused entries.
737  *
738  * The function must be called with at least share lock on the buffer, to
739  * prevent concurrent prune operations.
740  *
741  * Note: The information collected here is valid only as long as the caller
742  * holds a pin on the buffer. Once pin is released, a tuple might be pruned
743  * and reused by a completely unrelated tuple.
744  */
745 void
747 {
748  OffsetNumber offnum,
749  maxoff;
750 
751  MemSet(root_offsets, 0, MaxHeapTuplesPerPage * sizeof(OffsetNumber));
752 
753  maxoff = PageGetMaxOffsetNumber(page);
754  for (offnum = FirstOffsetNumber; offnum <= maxoff; offnum = OffsetNumberNext(offnum))
755  {
756  ItemId lp = PageGetItemId(page, offnum);
757  HeapTupleHeader htup;
758  OffsetNumber nextoffnum;
759  TransactionId priorXmax;
760 
761  /* skip unused and dead items */
762  if (!ItemIdIsUsed(lp) || ItemIdIsDead(lp))
763  continue;
764 
765  if (ItemIdIsNormal(lp))
766  {
767  htup = (HeapTupleHeader) PageGetItem(page, lp);
768 
769  /*
770  * Check if this tuple is part of a HOT-chain rooted at some other
771  * tuple. If so, skip it for now; we'll process it when we find
772  * its root.
773  */
774  if (HeapTupleHeaderIsHeapOnly(htup))
775  continue;
776 
777  /*
778  * This is either a plain tuple or the root of a HOT-chain.
779  * Remember it in the mapping.
780  */
781  root_offsets[offnum - 1] = offnum;
782 
783  /* If it's not the start of a HOT-chain, we're done with it */
784  if (!HeapTupleHeaderIsHotUpdated(htup))
785  continue;
786 
787  /* Set up to scan the HOT-chain */
788  nextoffnum = ItemPointerGetOffsetNumber(&htup->t_ctid);
789  priorXmax = HeapTupleHeaderGetUpdateXid(htup);
790  }
791  else
792  {
793  /* Must be a redirect item. We do not set its root_offsets entry */
795  /* Set up to scan the HOT-chain */
796  nextoffnum = ItemIdGetRedirect(lp);
797  priorXmax = InvalidTransactionId;
798  }
799 
800  /*
801  * Now follow the HOT-chain and collect other tuples in the chain.
802  *
803  * Note: Even though this is a nested loop, the complexity of the
804  * function is O(N) because a tuple in the page should be visited not
805  * more than twice, once in the outer loop and once in HOT-chain
806  * chases.
807  */
808  for (;;)
809  {
810  lp = PageGetItemId(page, nextoffnum);
811 
812  /* Check for broken chains */
813  if (!ItemIdIsNormal(lp))
814  break;
815 
816  htup = (HeapTupleHeader) PageGetItem(page, lp);
817 
818  if (TransactionIdIsValid(priorXmax) &&
819  !TransactionIdEquals(priorXmax, HeapTupleHeaderGetXmin(htup)))
820  break;
821 
822  /* Remember the root line pointer for this item */
823  root_offsets[nextoffnum - 1] = offnum;
824 
825  /* Advance to next chain member, if any */
826  if (!HeapTupleHeaderIsHotUpdated(htup))
827  break;
828 
829  /* HOT implies it can't have moved to different partition */
831 
832  nextoffnum = ItemPointerGetOffsetNumber(&htup->t_ctid);
833  priorXmax = HeapTupleHeaderGetUpdateXid(htup);
834  }
835  }
836 }
#define HeapTupleHeaderGetUpdateXid(tup)
Definition: htup_details.h:364
void HeapTupleHeaderAdvanceLatestRemovedXid(HeapTupleHeader tuple, TransactionId *latestRemovedXid)
Definition: heapam.c:7557
static int heap_prune_chain(Relation relation, Buffer buffer, OffsetNumber rootoffnum, TransactionId OldestXmin, PruneState *prstate)
Definition: pruneheap.c:353
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:87
int heap_page_prune(Relation relation, Buffer buffer, TransactionId OldestXmin, bool report_stats, TransactionId *latestRemovedXid)
Definition: pruneheap.c:181
bool IsCatalogRelation(Relation relation)
Definition: catalog.c:92
int nredirected
Definition: pruneheap.c:35
#define ItemIdIsRedirected(itemId)
Definition: itemid.h:105
#define TransactionIdEquals(id1, id2)
Definition: transam.h:43
void pgstat_update_heap_dead_tuples(Relation rel, int delta)
Definition: pgstat.c:2037
uint32 TransactionId
Definition: c.h:474
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
Definition: bufmgr.c:3379
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1450
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
#define ItemIdGetRedirect(itemId)
Definition: itemid.h:77
#define END_CRIT_SECTION()
Definition: miscadmin.h:133
#define ItemIdIsUsed(itemId)
Definition: itemid.h:91
TransactionId TransactionIdLimitedForOldSnapshots(TransactionId recentXmin, Relation relation)
Definition: snapmgr.c:1741
#define MaxHeapTuplesPerPage
Definition: htup_details.h:587
HTSV_Result HeapTupleSatisfiesVacuum(HeapTuple htup, TransactionId OldestXmin, Buffer buffer)
Definition: tqual.c:1164
static void heap_prune_record_dead(PruneState *prstate, OffsetNumber offnum)
Definition: pruneheap.c:651
#define START_CRIT_SECTION()
Definition: miscadmin.h:131
#define MemSet(start, val, len)
Definition: c.h:908
#define HeapTupleHeaderIndicatesMovedPartitions(tup)
Definition: htup_details.h:444
OffsetNumber nowdead[MaxHeapTuplesPerPage]
Definition: pruneheap.c:40
bool RecoveryInProgress(void)
Definition: xlog.c:7949
#define ItemIdIsDead(itemId)
Definition: itemid.h:112
bool marked[MaxHeapTuplesPerPage+1]
Definition: pruneheap.c:43
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:353
TransactionId new_prune_xid
Definition: pruneheap.c:33
#define PageIsFull(page)
Definition: bufpage.h:374
int nunused
Definition: pruneheap.c:37
uint16 OffsetNumber
Definition: off.h:24
HeapTupleHeader t_data
Definition: htup.h:68
#define HeapTupleHeaderIsHeapOnly(tup)
Definition: htup_details.h:514
#define ItemIdGetLength(itemId)
Definition: itemid.h:58
bool ConditionalLockBufferForCleanup(Buffer buffer)
Definition: bufmgr.c:3718
#define ERROR
Definition: elog.h:43
Size PageGetHeapFreeSpace(Page page)
Definition: bufpage.c:662
ItemPointerData t_ctid
Definition: htup_details.h:159
ItemPointerData t_self
Definition: htup.h:65
uint32 t_len
Definition: htup.h:64
static void heap_prune_record_prunable(PruneState *prstate, TransactionId xid)
Definition: pruneheap.c:622
TransactionId RecentGlobalXmin
Definition: snapmgr.c:166
TransactionId latestRemovedXid
Definition: pruneheap.c:34
#define ItemIdSetRedirect(itemId, link)
Definition: itemid.h:151
#define FirstOffsetNumber
Definition: off.h:27
#define InvalidTransactionId
Definition: transam.h:31
static TransactionId OldestXmin
Definition: vacuumlazy.c:146
Oid t_tableOid
Definition: htup.h:66
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
TransactionId RecentGlobalDataXmin
Definition: snapmgr.c:167
void heap_get_root_tuples(Page page, OffsetNumber *root_offsets)
Definition: pruneheap.c:746
#define PageClearFull(page)
Definition: bufpage.h:378
bool TransactionIdPrecedes(TransactionId id1, TransactionId id2)
Definition: transam.c:300
#define RelationGetTargetPageFreeSpace(relation, defaultff)
Definition: rel.h:298
#define HeapTupleHeaderIsHotUpdated(tup)
Definition: htup_details.h:497
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:231
#define RelationIsAccessibleInLogicalDecoding(relation)
Definition: rel.h:564
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3546
#define InvalidOffsetNumber
Definition: off.h:26
void heap_page_prune_execute(Buffer buffer, OffsetNumber *redirected, int nredirected, OffsetNumber *nowdead, int ndead, OffsetNumber *nowunused, int nunused)
Definition: pruneheap.c:682
#define Max(x, y)
Definition: c.h:851
PageHeaderData * PageHeader
Definition: bufpage.h:162
uint64 XLogRecPtr
Definition: xlogdefs.h:21
#define Assert(condition)
Definition: c.h:699
static void heap_prune_record_redirect(PruneState *prstate, OffsetNumber offnum, OffsetNumber rdoffnum)
Definition: pruneheap.c:636
#define ItemIdIsNormal(itemId)
Definition: itemid.h:98
WalTimeSample buffer[LAG_TRACKER_BUFFER_SIZE]
Definition: walsender.c:215
#define HeapTupleHeaderGetXmin(tup)
Definition: htup_details.h:312
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
size_t Size
Definition: c.h:433
OffsetNumber nowunused[MaxHeapTuplesPerPage]
Definition: pruneheap.c:41
XLogRecPtr log_heap_clean(Relation reln, Buffer buffer, OffsetNumber *redirected, int nredirected, OffsetNumber *nowdead, int ndead, OffsetNumber *nowunused, int nunused, TransactionId latestRemovedXid)
Definition: heapam.c:7625
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:117
#define RelationNeedsWAL(relation)
Definition: rel.h:510
#define PageIsPrunable(page, oldestxmin)
Definition: bufpage.h:388
OffsetNumber redirected[MaxHeapTuplesPerPage *2]
Definition: pruneheap.c:39
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2605
int ndead
Definition: pruneheap.c:36
void PageRepairFragmentation(Page page)
Definition: bufpage.c:479
int i
#define OffsetNumberIsValid(offsetNumber)
Definition: off.h:40
#define ItemIdSetDead(itemId)
Definition: itemid.h:163
#define elog
Definition: elog.h:219
void heap_page_prune_opt(Relation relation, Buffer buffer)
Definition: pruneheap.c:74
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:98
#define HEAP_DEFAULT_FILLFACTOR
Definition: rel.h:269
#define TransactionIdIsValid(xid)
Definition: transam.h:41
#define ItemIdSetUnused(itemId)
Definition: itemid.h:127
#define TransactionIdIsNormal(xid)
Definition: transam.h:42
#define PageSetLSN(page, lsn)
Definition: bufpage.h:364
int Buffer
Definition: buf.h:23
#define RelationGetRelid(relation)
Definition: rel.h:407
#define PageGetItem(page, itemId)
Definition: bufpage.h:336
Pointer Page
Definition: bufpage.h:74
#define ItemPointerSet(pointer, blockNumber, offNum)
Definition: itemptr.h:127
static void heap_prune_record_unused(PruneState *prstate, OffsetNumber offnum)
Definition: pruneheap.c:662