PostgreSQL Source Code  git master
pruneheap.c File Reference
#include "postgres.h"
#include "access/heapam.h"
#include "access/heapam_xlog.h"
#include "access/htup_details.h"
#include "access/transam.h"
#include "access/xlog.h"
#include "catalog/catalog.h"
#include "miscadmin.h"
#include "pgstat.h"
#include "storage/bufmgr.h"
#include "utils/rel.h"
#include "utils/snapmgr.h"
Include dependency graph for pruneheap.c:

Go to the source code of this file.

Data Structures

struct  PruneState
 

Functions

static int heap_prune_chain (Relation relation, Buffer buffer, OffsetNumber rootoffnum, TransactionId OldestXmin, PruneState *prstate)
 
static void heap_prune_record_prunable (PruneState *prstate, TransactionId xid)
 
static void heap_prune_record_redirect (PruneState *prstate, OffsetNumber offnum, OffsetNumber rdoffnum)
 
static void heap_prune_record_dead (PruneState *prstate, OffsetNumber offnum)
 
static void heap_prune_record_unused (PruneState *prstate, OffsetNumber offnum)
 
void heap_page_prune_opt (Relation relation, Buffer buffer)
 
int heap_page_prune (Relation relation, Buffer buffer, TransactionId OldestXmin, bool report_stats, TransactionId *latestRemovedXid)
 
void heap_page_prune_execute (Buffer buffer, OffsetNumber *redirected, int nredirected, OffsetNumber *nowdead, int ndead, OffsetNumber *nowunused, int nunused)
 
void heap_get_root_tuples (Page page, OffsetNumber *root_offsets)
 

Function Documentation

◆ heap_get_root_tuples()

void heap_get_root_tuples ( Page  page,
OffsetNumber root_offsets 
)

Definition at line 745 of file pruneheap.c.

References Assert, FirstOffsetNumber, HeapTupleHeaderGetUpdateXid, HeapTupleHeaderGetXmin, HeapTupleHeaderIndicatesMovedPartitions, HeapTupleHeaderIsHeapOnly, HeapTupleHeaderIsHotUpdated, InvalidTransactionId, ItemIdGetRedirect, ItemIdIsDead, ItemIdIsNormal, ItemIdIsRedirected, ItemIdIsUsed, ItemPointerGetOffsetNumber, MaxHeapTuplesPerPage, MemSet, OffsetNumberNext, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, HeapTupleHeaderData::t_ctid, TransactionIdEquals, and TransactionIdIsValid.

Referenced by heapam_index_build_range_scan(), and heapam_index_validate_scan().

746 {
747  OffsetNumber offnum,
748  maxoff;
749 
750  MemSet(root_offsets, 0, MaxHeapTuplesPerPage * sizeof(OffsetNumber));
751 
752  maxoff = PageGetMaxOffsetNumber(page);
753  for (offnum = FirstOffsetNumber; offnum <= maxoff; offnum = OffsetNumberNext(offnum))
754  {
755  ItemId lp = PageGetItemId(page, offnum);
756  HeapTupleHeader htup;
757  OffsetNumber nextoffnum;
758  TransactionId priorXmax;
759 
760  /* skip unused and dead items */
761  if (!ItemIdIsUsed(lp) || ItemIdIsDead(lp))
762  continue;
763 
764  if (ItemIdIsNormal(lp))
765  {
766  htup = (HeapTupleHeader) PageGetItem(page, lp);
767 
768  /*
769  * Check if this tuple is part of a HOT-chain rooted at some other
770  * tuple. If so, skip it for now; we'll process it when we find
771  * its root.
772  */
773  if (HeapTupleHeaderIsHeapOnly(htup))
774  continue;
775 
776  /*
777  * This is either a plain tuple or the root of a HOT-chain.
778  * Remember it in the mapping.
779  */
780  root_offsets[offnum - 1] = offnum;
781 
782  /* If it's not the start of a HOT-chain, we're done with it */
783  if (!HeapTupleHeaderIsHotUpdated(htup))
784  continue;
785 
786  /* Set up to scan the HOT-chain */
787  nextoffnum = ItemPointerGetOffsetNumber(&htup->t_ctid);
788  priorXmax = HeapTupleHeaderGetUpdateXid(htup);
789  }
790  else
791  {
792  /* Must be a redirect item. We do not set its root_offsets entry */
794  /* Set up to scan the HOT-chain */
795  nextoffnum = ItemIdGetRedirect(lp);
796  priorXmax = InvalidTransactionId;
797  }
798 
799  /*
800  * Now follow the HOT-chain and collect other tuples in the chain.
801  *
802  * Note: Even though this is a nested loop, the complexity of the
803  * function is O(N) because a tuple in the page should be visited not
804  * more than twice, once in the outer loop and once in HOT-chain
805  * chases.
806  */
807  for (;;)
808  {
809  lp = PageGetItemId(page, nextoffnum);
810 
811  /* Check for broken chains */
812  if (!ItemIdIsNormal(lp))
813  break;
814 
815  htup = (HeapTupleHeader) PageGetItem(page, lp);
816 
817  if (TransactionIdIsValid(priorXmax) &&
818  !TransactionIdEquals(priorXmax, HeapTupleHeaderGetXmin(htup)))
819  break;
820 
821  /* Remember the root line pointer for this item */
822  root_offsets[nextoffnum - 1] = offnum;
823 
824  /* Advance to next chain member, if any */
825  if (!HeapTupleHeaderIsHotUpdated(htup))
826  break;
827 
828  /* HOT implies it can't have moved to different partition */
830 
831  nextoffnum = ItemPointerGetOffsetNumber(&htup->t_ctid);
832  priorXmax = HeapTupleHeaderGetUpdateXid(htup);
833  }
834  }
835 }
#define HeapTupleHeaderGetUpdateXid(tup)
Definition: htup_details.h:365
#define ItemIdIsRedirected(itemId)
Definition: itemid.h:106
#define TransactionIdEquals(id1, id2)
Definition: transam.h:43
uint32 TransactionId
Definition: c.h:514
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
#define ItemIdGetRedirect(itemId)
Definition: itemid.h:78
#define ItemIdIsUsed(itemId)
Definition: itemid.h:92
#define MaxHeapTuplesPerPage
Definition: htup_details.h:574
#define MemSet(start, val, len)
Definition: c.h:962
#define HeapTupleHeaderIndicatesMovedPartitions(tup)
Definition: htup_details.h:445
#define ItemIdIsDead(itemId)
Definition: itemid.h:113
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:357
uint16 OffsetNumber
Definition: off.h:24
#define HeapTupleHeaderIsHeapOnly(tup)
Definition: htup_details.h:501
ItemPointerData t_ctid
Definition: htup_details.h:160
#define FirstOffsetNumber
Definition: off.h:27
#define InvalidTransactionId
Definition: transam.h:31
#define HeapTupleHeaderIsHotUpdated(tup)
Definition: htup_details.h:484
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
#define Assert(condition)
Definition: c.h:739
#define ItemIdIsNormal(itemId)
Definition: itemid.h:99
#define HeapTupleHeaderGetXmin(tup)
Definition: htup_details.h:313
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:117
#define TransactionIdIsValid(xid)
Definition: transam.h:41
#define PageGetItem(page, itemId)
Definition: bufpage.h:340

◆ heap_page_prune()

int heap_page_prune ( Relation  relation,
Buffer  buffer,
TransactionId  OldestXmin,
bool  report_stats,
TransactionId latestRemovedXid 
)

Definition at line 180 of file pruneheap.c.

References BufferGetPage, END_CRIT_SECTION, FirstOffsetNumber, heap_page_prune_execute(), heap_prune_chain(), InvalidTransactionId, ItemIdIsDead, ItemIdIsUsed, PruneState::latestRemovedXid, log_heap_clean(), MarkBufferDirty(), MarkBufferDirtyHint(), PruneState::marked, PruneState::ndead, PruneState::new_prune_xid, PruneState::nowdead, PruneState::nowunused, PruneState::nredirected, PruneState::nunused, OffsetNumberNext, PageClearFull, PageGetItemId, PageGetMaxOffsetNumber, PageIsFull, PageSetLSN, pgstat_update_heap_dead_tuples(), PruneState::redirected, RelationNeedsWAL, and START_CRIT_SECTION.

Referenced by heap_page_prune_opt(), and lazy_scan_heap().

182 {
183  int ndeleted = 0;
184  Page page = BufferGetPage(buffer);
185  OffsetNumber offnum,
186  maxoff;
187  PruneState prstate;
188 
189  /*
190  * Our strategy is to scan the page and make lists of items to change,
191  * then apply the changes within a critical section. This keeps as much
192  * logic as possible out of the critical section, and also ensures that
193  * WAL replay will work the same as the normal case.
194  *
195  * First, initialize the new pd_prune_xid value to zero (indicating no
196  * prunable tuples). If we find any tuples which may soon become
197  * prunable, we will save the lowest relevant XID in new_prune_xid. Also
198  * initialize the rest of our working state.
199  */
201  prstate.latestRemovedXid = *latestRemovedXid;
202  prstate.nredirected = prstate.ndead = prstate.nunused = 0;
203  memset(prstate.marked, 0, sizeof(prstate.marked));
204 
205  /* Scan the page */
206  maxoff = PageGetMaxOffsetNumber(page);
207  for (offnum = FirstOffsetNumber;
208  offnum <= maxoff;
209  offnum = OffsetNumberNext(offnum))
210  {
211  ItemId itemid;
212 
213  /* Ignore items already processed as part of an earlier chain */
214  if (prstate.marked[offnum])
215  continue;
216 
217  /* Nothing to do if slot is empty or already dead */
218  itemid = PageGetItemId(page, offnum);
219  if (!ItemIdIsUsed(itemid) || ItemIdIsDead(itemid))
220  continue;
221 
222  /* Process this item or chain of items */
223  ndeleted += heap_prune_chain(relation, buffer, offnum,
224  OldestXmin,
225  &prstate);
226  }
227 
228  /* Any error while applying the changes is critical */
230 
231  /* Have we found any prunable items? */
232  if (prstate.nredirected > 0 || prstate.ndead > 0 || prstate.nunused > 0)
233  {
234  /*
235  * Apply the planned item changes, then repair page fragmentation, and
236  * update the page's hint bit about whether it has free line pointers.
237  */
239  prstate.redirected, prstate.nredirected,
240  prstate.nowdead, prstate.ndead,
241  prstate.nowunused, prstate.nunused);
242 
243  /*
244  * Update the page's pd_prune_xid field to either zero, or the lowest
245  * XID of any soon-prunable tuple.
246  */
247  ((PageHeader) page)->pd_prune_xid = prstate.new_prune_xid;
248 
249  /*
250  * Also clear the "page is full" flag, since there's no point in
251  * repeating the prune/defrag process until something else happens to
252  * the page.
253  */
254  PageClearFull(page);
255 
256  MarkBufferDirty(buffer);
257 
258  /*
259  * Emit a WAL XLOG_HEAP2_CLEAN record showing what we did
260  */
261  if (RelationNeedsWAL(relation))
262  {
263  XLogRecPtr recptr;
264 
265  recptr = log_heap_clean(relation, buffer,
266  prstate.redirected, prstate.nredirected,
267  prstate.nowdead, prstate.ndead,
268  prstate.nowunused, prstate.nunused,
269  prstate.latestRemovedXid);
270 
271  PageSetLSN(BufferGetPage(buffer), recptr);
272  }
273  }
274  else
275  {
276  /*
277  * If we didn't prune anything, but have found a new value for the
278  * pd_prune_xid field, update it and mark the buffer dirty. This is
279  * treated as a non-WAL-logged hint.
280  *
281  * Also clear the "page is full" flag if it is set, since there's no
282  * point in repeating the prune/defrag process until something else
283  * happens to the page.
284  */
285  if (((PageHeader) page)->pd_prune_xid != prstate.new_prune_xid ||
286  PageIsFull(page))
287  {
288  ((PageHeader) page)->pd_prune_xid = prstate.new_prune_xid;
289  PageClearFull(page);
290  MarkBufferDirtyHint(buffer, true);
291  }
292  }
293 
295 
296  /*
297  * If requested, report the number of tuples reclaimed to pgstats. This is
298  * ndeleted minus ndead, because we don't want to count a now-DEAD root
299  * item as a deletion for this purpose.
300  */
301  if (report_stats && ndeleted > prstate.ndead)
302  pgstat_update_heap_dead_tuples(relation, ndeleted - prstate.ndead);
303 
304  *latestRemovedXid = prstate.latestRemovedXid;
305 
306  /*
307  * XXX Should we update the FSM information of this page ?
308  *
309  * There are two schools of thought here. We may not want to update FSM
310  * information so that the page is not used for unrelated UPDATEs/INSERTs
311  * and any free space in this page will remain available for further
312  * UPDATEs in *this* page, thus improving chances for doing HOT updates.
313  *
314  * But for a large table and where a page does not receive further UPDATEs
315  * for a long time, we might waste this space by not updating the FSM
316  * information. The relation may get extended and fragmented further.
317  *
318  * One possibility is to leave "fillfactor" worth of space in this page
319  * and update FSM with the remaining space.
320  */
321 
322  return ndeleted;
323 }
static int heap_prune_chain(Relation relation, Buffer buffer, OffsetNumber rootoffnum, TransactionId OldestXmin, PruneState *prstate)
Definition: pruneheap.c:352
int nredirected
Definition: pruneheap.c:34
void pgstat_update_heap_dead_tuples(Relation rel, int delta)
Definition: pgstat.c:2076
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
Definition: bufmgr.c:3435
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1458
#define END_CRIT_SECTION()
Definition: miscadmin.h:134
#define ItemIdIsUsed(itemId)
Definition: itemid.h:92
#define START_CRIT_SECTION()
Definition: miscadmin.h:132
OffsetNumber nowdead[MaxHeapTuplesPerPage]
Definition: pruneheap.c:39
#define ItemIdIsDead(itemId)
Definition: itemid.h:113
bool marked[MaxHeapTuplesPerPage+1]
Definition: pruneheap.c:42
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:357
TransactionId new_prune_xid
Definition: pruneheap.c:32
#define PageIsFull(page)
Definition: bufpage.h:378
int nunused
Definition: pruneheap.c:36
uint16 OffsetNumber
Definition: off.h:24
TransactionId latestRemovedXid
Definition: pruneheap.c:33
#define FirstOffsetNumber
Definition: off.h:27
#define InvalidTransactionId
Definition: transam.h:31
static TransactionId OldestXmin
Definition: vacuumlazy.c:145
#define BufferGetPage(buffer)
Definition: bufmgr.h:159
#define PageClearFull(page)
Definition: bufpage.h:382
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
void heap_page_prune_execute(Buffer buffer, OffsetNumber *redirected, int nredirected, OffsetNumber *nowdead, int ndead, OffsetNumber *nowunused, int nunused)
Definition: pruneheap.c:681
PageHeaderData * PageHeader
Definition: bufpage.h:166
uint64 XLogRecPtr
Definition: xlogdefs.h:21
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
OffsetNumber nowunused[MaxHeapTuplesPerPage]
Definition: pruneheap.c:40
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:7177
#define RelationNeedsWAL(relation)
Definition: rel.h:524
OffsetNumber redirected[MaxHeapTuplesPerPage *2]
Definition: pruneheap.c:38
int ndead
Definition: pruneheap.c:35
#define PageSetLSN(page, lsn)
Definition: bufpage.h:368
Pointer Page
Definition: bufpage.h:78

◆ heap_page_prune_execute()

void heap_page_prune_execute ( Buffer  buffer,
OffsetNumber redirected,
int  nredirected,
OffsetNumber nowdead,
int  ndead,
OffsetNumber nowunused,
int  nunused 
)

Definition at line 681 of file pruneheap.c.

References BufferGetPage, i, ItemIdSetDead, ItemIdSetRedirect, ItemIdSetUnused, PageGetItemId, and PageRepairFragmentation().

Referenced by heap_page_prune(), and heap_xlog_clean().

685 {
686  Page page = (Page) BufferGetPage(buffer);
687  OffsetNumber *offnum;
688  int i;
689 
690  /* Update all redirected line pointers */
691  offnum = redirected;
692  for (i = 0; i < nredirected; i++)
693  {
694  OffsetNumber fromoff = *offnum++;
695  OffsetNumber tooff = *offnum++;
696  ItemId fromlp = PageGetItemId(page, fromoff);
697 
698  ItemIdSetRedirect(fromlp, tooff);
699  }
700 
701  /* Update all now-dead line pointers */
702  offnum = nowdead;
703  for (i = 0; i < ndead; i++)
704  {
705  OffsetNumber off = *offnum++;
706  ItemId lp = PageGetItemId(page, off);
707 
708  ItemIdSetDead(lp);
709  }
710 
711  /* Update all now-unused line pointers */
712  offnum = nowunused;
713  for (i = 0; i < nunused; i++)
714  {
715  OffsetNumber off = *offnum++;
716  ItemId lp = PageGetItemId(page, off);
717 
718  ItemIdSetUnused(lp);
719  }
720 
721  /*
722  * Finally, repair any fragmentation, and update the page's hint bit about
723  * whether it has free pointers.
724  */
726 }
uint16 OffsetNumber
Definition: off.h:24
#define ItemIdSetRedirect(itemId, link)
Definition: itemid.h:152
#define BufferGetPage(buffer)
Definition: bufmgr.h:159
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
void PageRepairFragmentation(Page page)
Definition: bufpage.c:482
int i
#define ItemIdSetDead(itemId)
Definition: itemid.h:164
#define ItemIdSetUnused(itemId)
Definition: itemid.h:128
Pointer Page
Definition: bufpage.h:78

◆ heap_page_prune_opt()

void heap_page_prune_opt ( Relation  relation,
Buffer  buffer 
)

Definition at line 73 of file pruneheap.c.

References Assert, BUFFER_LOCK_UNLOCK, BufferGetPage, ConditionalLockBufferForCleanup(), HEAP_DEFAULT_FILLFACTOR, heap_page_prune(), InvalidTransactionId, IsCatalogRelation(), LockBuffer(), Max, OldestXmin, PageGetHeapFreeSpace(), PageIsFull, PageIsPrunable, RecentGlobalDataXmin, RecentGlobalXmin, RecoveryInProgress(), RelationGetTargetPageFreeSpace, RelationIsAccessibleInLogicalDecoding, TransactionIdIsValid, and TransactionIdLimitedForOldSnapshots().

Referenced by heapam_index_fetch_tuple(), heapam_scan_bitmap_next_block(), and heapgetpage().

74 {
75  Page page = BufferGetPage(buffer);
76  Size minfree;
78 
79  /*
80  * We can't write WAL in recovery mode, so there's no point trying to
81  * clean the page. The master will likely issue a cleaning WAL record soon
82  * anyway, so this is no particular loss.
83  */
84  if (RecoveryInProgress())
85  return;
86 
87  /*
88  * Use the appropriate xmin horizon for this relation. If it's a proper
89  * catalog relation or a user defined, additional, catalog relation, we
90  * need to use the horizon that includes slots, otherwise the data-only
91  * horizon can be used. Note that the toast relation of user defined
92  * relations are *not* considered catalog relations.
93  *
94  * It is OK to apply the old snapshot limit before acquiring the cleanup
95  * lock because the worst that can happen is that we are not quite as
96  * aggressive about the cleanup (by however many transaction IDs are
97  * consumed between this point and acquiring the lock). This allows us to
98  * save significant overhead in the case where the page is found not to be
99  * prunable.
100  */
101  if (IsCatalogRelation(relation) ||
103  OldestXmin = RecentGlobalXmin;
104  else
105  OldestXmin =
107  relation);
108 
109  Assert(TransactionIdIsValid(OldestXmin));
110 
111  /*
112  * Let's see if we really need pruning.
113  *
114  * Forget it if page is not hinted to contain something prunable that's
115  * older than OldestXmin.
116  */
117  if (!PageIsPrunable(page, OldestXmin))
118  return;
119 
120  /*
121  * We prune when a previous UPDATE failed to find enough space on the page
122  * for a new tuple version, or when free space falls below the relation's
123  * fill-factor target (but not less than 10%).
124  *
125  * Checking free space here is questionable since we aren't holding any
126  * lock on the buffer; in the worst case we could get a bogus answer. It's
127  * unlikely to be *seriously* wrong, though, since reading either pd_lower
128  * or pd_upper is probably atomic. Avoiding taking a lock seems more
129  * important than sometimes getting a wrong answer in what is after all
130  * just a heuristic estimate.
131  */
132  minfree = RelationGetTargetPageFreeSpace(relation,
134  minfree = Max(minfree, BLCKSZ / 10);
135 
136  if (PageIsFull(page) || PageGetHeapFreeSpace(page) < minfree)
137  {
138  /* OK, try to get exclusive buffer lock */
139  if (!ConditionalLockBufferForCleanup(buffer))
140  return;
141 
142  /*
143  * Now that we have buffer lock, get accurate information about the
144  * page's free space, and recheck the heuristic about whether to
145  * prune. (We needn't recheck PageIsPrunable, since no one else could
146  * have pruned while we hold pin.)
147  */
148  if (PageIsFull(page) || PageGetHeapFreeSpace(page) < minfree)
149  {
150  TransactionId ignore = InvalidTransactionId; /* return value not
151  * needed */
152 
153  /* OK to prune */
154  (void) heap_page_prune(relation, buffer, OldestXmin, true, &ignore);
155  }
156 
157  /* And release buffer lock */
159  }
160 }
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:86
int heap_page_prune(Relation relation, Buffer buffer, TransactionId OldestXmin, bool report_stats, TransactionId *latestRemovedXid)
Definition: pruneheap.c:180
bool IsCatalogRelation(Relation relation)
Definition: catalog.c:99
uint32 TransactionId
Definition: c.h:514
TransactionId TransactionIdLimitedForOldSnapshots(TransactionId recentXmin, Relation relation)
Definition: snapmgr.c:1775
bool RecoveryInProgress(void)
Definition: xlog.c:7935
#define PageIsFull(page)
Definition: bufpage.h:378
bool ConditionalLockBufferForCleanup(Buffer buffer)
Definition: bufmgr.c:3774
Size PageGetHeapFreeSpace(Page page)
Definition: bufpage.c:665
TransactionId RecentGlobalXmin
Definition: snapmgr.c:168
#define InvalidTransactionId
Definition: transam.h:31
static TransactionId OldestXmin
Definition: vacuumlazy.c:145
#define BufferGetPage(buffer)
Definition: bufmgr.h:159
TransactionId RecentGlobalDataXmin
Definition: snapmgr.c:169
#define RelationGetTargetPageFreeSpace(relation, defaultff)
Definition: rel.h:306
#define RelationIsAccessibleInLogicalDecoding(relation)
Definition: rel.h:578
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3602
#define Max(x, y)
Definition: c.h:905
#define Assert(condition)
Definition: c.h:739
size_t Size
Definition: c.h:467
#define PageIsPrunable(page, oldestxmin)
Definition: bufpage.h:392
#define HEAP_DEFAULT_FILLFACTOR
Definition: rel.h:277
#define TransactionIdIsValid(xid)
Definition: transam.h:41
Pointer Page
Definition: bufpage.h:78

◆ heap_prune_chain()

static int heap_prune_chain ( Relation  relation,
Buffer  buffer,
OffsetNumber  rootoffnum,
TransactionId  OldestXmin,
PruneState prstate 
)
static

Definition at line 352 of file pruneheap.c.

References Assert, BufferGetBlockNumber(), BufferGetPage, elog, ERROR, heap_prune_record_dead(), heap_prune_record_prunable(), heap_prune_record_redirect(), heap_prune_record_unused(), HEAPTUPLE_DEAD, HEAPTUPLE_DELETE_IN_PROGRESS, HEAPTUPLE_INSERT_IN_PROGRESS, HEAPTUPLE_LIVE, HEAPTUPLE_RECENTLY_DEAD, HeapTupleHeaderAdvanceLatestRemovedXid(), HeapTupleHeaderGetUpdateXid, HeapTupleHeaderGetXmin, HeapTupleHeaderIndicatesMovedPartitions, HeapTupleHeaderIsHeapOnly, HeapTupleHeaderIsHotUpdated, HeapTupleSatisfiesVacuum(), i, InvalidOffsetNumber, InvalidTransactionId, ItemIdGetLength, ItemIdGetRedirect, ItemIdIsDead, ItemIdIsNormal, ItemIdIsRedirected, ItemIdIsUsed, ItemPointerGetBlockNumber, ItemPointerGetOffsetNumber, ItemPointerSet, PruneState::latestRemovedXid, PruneState::marked, MaxHeapTuplesPerPage, OffsetNumberIsValid, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, RelationGetRelid, HeapTupleHeaderData::t_ctid, HeapTupleData::t_data, HeapTupleData::t_len, HeapTupleData::t_self, HeapTupleData::t_tableOid, TransactionIdEquals, and TransactionIdIsValid.

Referenced by heap_page_prune().

355 {
356  int ndeleted = 0;
357  Page dp = (Page) BufferGetPage(buffer);
359  ItemId rootlp;
360  HeapTupleHeader htup;
361  OffsetNumber latestdead = InvalidOffsetNumber,
362  maxoff = PageGetMaxOffsetNumber(dp),
363  offnum;
365  int nchain = 0,
366  i;
367  HeapTupleData tup;
368 
369  tup.t_tableOid = RelationGetRelid(relation);
370 
371  rootlp = PageGetItemId(dp, rootoffnum);
372 
373  /*
374  * If it's a heap-only tuple, then it is not the start of a HOT chain.
375  */
376  if (ItemIdIsNormal(rootlp))
377  {
378  htup = (HeapTupleHeader) PageGetItem(dp, rootlp);
379 
380  tup.t_data = htup;
381  tup.t_len = ItemIdGetLength(rootlp);
382  ItemPointerSet(&(tup.t_self), BufferGetBlockNumber(buffer), rootoffnum);
383 
384  if (HeapTupleHeaderIsHeapOnly(htup))
385  {
386  /*
387  * If the tuple is DEAD and doesn't chain to anything else, mark
388  * it unused immediately. (If it does chain, we can only remove
389  * it as part of pruning its chain.)
390  *
391  * We need this primarily to handle aborted HOT updates, that is,
392  * XMIN_INVALID heap-only tuples. Those might not be linked to by
393  * any chain, since the parent tuple might be re-updated before
394  * any pruning occurs. So we have to be able to reap them
395  * separately from chain-pruning. (Note that
396  * HeapTupleHeaderIsHotUpdated will never return true for an
397  * XMIN_INVALID tuple, so this code will work even when there were
398  * sequential updates within the aborted transaction.)
399  *
400  * Note that we might first arrive at a dead heap-only tuple
401  * either here or while following a chain below. Whichever path
402  * gets there first will mark the tuple unused.
403  */
404  if (HeapTupleSatisfiesVacuum(&tup, OldestXmin, buffer)
406  {
407  heap_prune_record_unused(prstate, rootoffnum);
409  &prstate->latestRemovedXid);
410  ndeleted++;
411  }
412 
413  /* Nothing more to do */
414  return ndeleted;
415  }
416  }
417 
418  /* Start from the root tuple */
419  offnum = rootoffnum;
420 
421  /* while not end of the chain */
422  for (;;)
423  {
424  ItemId lp;
425  bool tupdead,
426  recent_dead;
427 
428  /* Some sanity checks */
429  if (offnum < FirstOffsetNumber || offnum > maxoff)
430  break;
431 
432  /* If item is already processed, stop --- it must not be same chain */
433  if (prstate->marked[offnum])
434  break;
435 
436  lp = PageGetItemId(dp, offnum);
437 
438  /* Unused item obviously isn't part of the chain */
439  if (!ItemIdIsUsed(lp))
440  break;
441 
442  /*
443  * If we are looking at the redirected root line pointer, jump to the
444  * first normal tuple in the chain. If we find a redirect somewhere
445  * else, stop --- it must not be same chain.
446  */
447  if (ItemIdIsRedirected(lp))
448  {
449  if (nchain > 0)
450  break; /* not at start of chain */
451  chainitems[nchain++] = offnum;
452  offnum = ItemIdGetRedirect(rootlp);
453  continue;
454  }
455 
456  /*
457  * Likewise, a dead line pointer can't be part of the chain. (We
458  * already eliminated the case of dead root tuple outside this
459  * function.)
460  */
461  if (ItemIdIsDead(lp))
462  break;
463 
464  Assert(ItemIdIsNormal(lp));
465  htup = (HeapTupleHeader) PageGetItem(dp, lp);
466 
467  tup.t_data = htup;
468  tup.t_len = ItemIdGetLength(lp);
469  ItemPointerSet(&(tup.t_self), BufferGetBlockNumber(buffer), offnum);
470 
471  /*
472  * Check the tuple XMIN against prior XMAX, if any
473  */
474  if (TransactionIdIsValid(priorXmax) &&
475  !TransactionIdEquals(HeapTupleHeaderGetXmin(htup), priorXmax))
476  break;
477 
478  /*
479  * OK, this tuple is indeed a member of the chain.
480  */
481  chainitems[nchain++] = offnum;
482 
483  /*
484  * Check tuple's visibility status.
485  */
486  tupdead = recent_dead = false;
487 
488  switch (HeapTupleSatisfiesVacuum(&tup, OldestXmin, buffer))
489  {
490  case HEAPTUPLE_DEAD:
491  tupdead = true;
492  break;
493 
495  recent_dead = true;
496 
497  /*
498  * This tuple may soon become DEAD. Update the hint field so
499  * that the page is reconsidered for pruning in future.
500  */
503  break;
504 
506 
507  /*
508  * This tuple may soon become DEAD. Update the hint field so
509  * that the page is reconsidered for pruning in future.
510  */
513  break;
514 
515  case HEAPTUPLE_LIVE:
517 
518  /*
519  * If we wanted to optimize for aborts, we might consider
520  * marking the page prunable when we see INSERT_IN_PROGRESS.
521  * But we don't. See related decisions about when to mark the
522  * page prunable in heapam.c.
523  */
524  break;
525 
526  default:
527  elog(ERROR, "unexpected HeapTupleSatisfiesVacuum result");
528  break;
529  }
530 
531  /*
532  * Remember the last DEAD tuple seen. We will advance past
533  * RECENTLY_DEAD tuples just in case there's a DEAD one after them;
534  * but we can't advance past anything else. (XXX is it really worth
535  * continuing to scan beyond RECENTLY_DEAD? The case where we will
536  * find another DEAD tuple is a fairly unusual corner case.)
537  */
538  if (tupdead)
539  {
540  latestdead = offnum;
542  &prstate->latestRemovedXid);
543  }
544  else if (!recent_dead)
545  break;
546 
547  /*
548  * If the tuple is not HOT-updated, then we are at the end of this
549  * HOT-update chain.
550  */
551  if (!HeapTupleHeaderIsHotUpdated(htup))
552  break;
553 
554  /* HOT implies it can't have moved to different partition */
556 
557  /*
558  * Advance to next chain member.
559  */
561  BufferGetBlockNumber(buffer));
562  offnum = ItemPointerGetOffsetNumber(&htup->t_ctid);
563  priorXmax = HeapTupleHeaderGetUpdateXid(htup);
564  }
565 
566  /*
567  * If we found a DEAD tuple in the chain, adjust the HOT chain so that all
568  * the DEAD tuples at the start of the chain are removed and the root line
569  * pointer is appropriately redirected.
570  */
571  if (OffsetNumberIsValid(latestdead))
572  {
573  /*
574  * Mark as unused each intermediate item that we are able to remove
575  * from the chain.
576  *
577  * When the previous item is the last dead tuple seen, we are at the
578  * right candidate for redirection.
579  */
580  for (i = 1; (i < nchain) && (chainitems[i - 1] != latestdead); i++)
581  {
582  heap_prune_record_unused(prstate, chainitems[i]);
583  ndeleted++;
584  }
585 
586  /*
587  * If the root entry had been a normal tuple, we are deleting it, so
588  * count it in the result. But changing a redirect (even to DEAD
589  * state) doesn't count.
590  */
591  if (ItemIdIsNormal(rootlp))
592  ndeleted++;
593 
594  /*
595  * If the DEAD tuple is at the end of the chain, the entire chain is
596  * dead and the root line pointer can be marked dead. Otherwise just
597  * redirect the root to the correct chain member.
598  */
599  if (i >= nchain)
600  heap_prune_record_dead(prstate, rootoffnum);
601  else
602  heap_prune_record_redirect(prstate, rootoffnum, chainitems[i]);
603  }
604  else if (nchain < 2 && ItemIdIsRedirected(rootlp))
605  {
606  /*
607  * We found a redirect item that doesn't point to a valid follow-on
608  * item. This can happen if the loop in heap_page_prune caused us to
609  * visit the dead successor of a redirect item before visiting the
610  * redirect item. We can clean up by setting the redirect item to
611  * DEAD state.
612  */
613  heap_prune_record_dead(prstate, rootoffnum);
614  }
615 
616  return ndeleted;
617 }
#define HeapTupleHeaderGetUpdateXid(tup)
Definition: htup_details.h:365
void HeapTupleHeaderAdvanceLatestRemovedXid(HeapTupleHeader tuple, TransactionId *latestRemovedXid)
Definition: heapam.c:6895
#define ItemIdIsRedirected(itemId)
Definition: itemid.h:106
#define TransactionIdEquals(id1, id2)
Definition: transam.h:43
uint32 TransactionId
Definition: c.h:514
HeapTupleHeaderData * HeapTupleHeader
Definition: htup.h:23
#define ItemIdGetRedirect(itemId)
Definition: itemid.h:78
#define ItemIdIsUsed(itemId)
Definition: itemid.h:92
#define MaxHeapTuplesPerPage
Definition: htup_details.h:574
static void heap_prune_record_dead(PruneState *prstate, OffsetNumber offnum)
Definition: pruneheap.c:650
#define HeapTupleHeaderIndicatesMovedPartitions(tup)
Definition: htup_details.h:445
#define ItemIdIsDead(itemId)
Definition: itemid.h:113
bool marked[MaxHeapTuplesPerPage+1]
Definition: pruneheap.c:42
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:357
uint16 OffsetNumber
Definition: off.h:24
HeapTupleHeader t_data
Definition: htup.h:68
#define HeapTupleHeaderIsHeapOnly(tup)
Definition: htup_details.h:501
#define ItemIdGetLength(itemId)
Definition: itemid.h:59
#define ERROR
Definition: elog.h:43
ItemPointerData t_ctid
Definition: htup_details.h:160
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:621
TransactionId latestRemovedXid
Definition: pruneheap.c:33
#define InvalidTransactionId
Definition: transam.h:31
static TransactionId OldestXmin
Definition: vacuumlazy.c:145
Oid t_tableOid
Definition: htup.h:66
#define BufferGetPage(buffer)
Definition: bufmgr.h:159
HTSV_Result HeapTupleSatisfiesVacuum(HeapTuple htup, TransactionId OldestXmin, Buffer buffer)
#define HeapTupleHeaderIsHotUpdated(tup)
Definition: htup_details.h:484
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
#define InvalidOffsetNumber
Definition: off.h:26
#define Assert(condition)
Definition: c.h:739
static void heap_prune_record_redirect(PruneState *prstate, OffsetNumber offnum, OffsetNumber rdoffnum)
Definition: pruneheap.c:635
#define ItemIdIsNormal(itemId)
Definition: itemid.h:99
#define HeapTupleHeaderGetXmin(tup)
Definition: htup_details.h:313
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:117
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2613
#define elog(elevel,...)
Definition: elog.h:228
int i
#define OffsetNumberIsValid(offsetNumber)
Definition: off.h:39
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:98
#define TransactionIdIsValid(xid)
Definition: transam.h:41
#define RelationGetRelid(relation)
Definition: rel.h:422
#define PageGetItem(page, itemId)
Definition: bufpage.h:340
Pointer Page
Definition: bufpage.h:78
#define ItemPointerSet(pointer, blockNumber, offNum)
Definition: itemptr.h:127
static void heap_prune_record_unused(PruneState *prstate, OffsetNumber offnum)
Definition: pruneheap.c:661

◆ heap_prune_record_dead()

static void heap_prune_record_dead ( PruneState prstate,
OffsetNumber  offnum 
)
static

Definition at line 650 of file pruneheap.c.

References Assert, PruneState::marked, MaxHeapTuplesPerPage, PruneState::ndead, and PruneState::nowdead.

Referenced by heap_prune_chain().

651 {
652  Assert(prstate->ndead < MaxHeapTuplesPerPage);
653  prstate->nowdead[prstate->ndead] = offnum;
654  prstate->ndead++;
655  Assert(!prstate->marked[offnum]);
656  prstate->marked[offnum] = true;
657 }
#define MaxHeapTuplesPerPage
Definition: htup_details.h:574
OffsetNumber nowdead[MaxHeapTuplesPerPage]
Definition: pruneheap.c:39
bool marked[MaxHeapTuplesPerPage+1]
Definition: pruneheap.c:42
#define Assert(condition)
Definition: c.h:739
int ndead
Definition: pruneheap.c:35

◆ heap_prune_record_prunable()

static void heap_prune_record_prunable ( PruneState prstate,
TransactionId  xid 
)
static

Definition at line 621 of file pruneheap.c.

References Assert, PruneState::new_prune_xid, TransactionIdIsNormal, TransactionIdIsValid, and TransactionIdPrecedes().

Referenced by heap_prune_chain().

622 {
623  /*
624  * This should exactly match the PageSetPrunable macro. We can't store
625  * directly into the page header yet, so we update working state.
626  */
628  if (!TransactionIdIsValid(prstate->new_prune_xid) ||
629  TransactionIdPrecedes(xid, prstate->new_prune_xid))
630  prstate->new_prune_xid = xid;
631 }
TransactionId new_prune_xid
Definition: pruneheap.c:32
bool TransactionIdPrecedes(TransactionId id1, TransactionId id2)
Definition: transam.c:300
#define Assert(condition)
Definition: c.h:739
#define TransactionIdIsValid(xid)
Definition: transam.h:41
#define TransactionIdIsNormal(xid)
Definition: transam.h:42

◆ heap_prune_record_redirect()

static void heap_prune_record_redirect ( PruneState prstate,
OffsetNumber  offnum,
OffsetNumber  rdoffnum 
)
static

Definition at line 635 of file pruneheap.c.

References Assert, PruneState::marked, MaxHeapTuplesPerPage, PruneState::nredirected, and PruneState::redirected.

Referenced by heap_prune_chain().

637 {
639  prstate->redirected[prstate->nredirected * 2] = offnum;
640  prstate->redirected[prstate->nredirected * 2 + 1] = rdoffnum;
641  prstate->nredirected++;
642  Assert(!prstate->marked[offnum]);
643  prstate->marked[offnum] = true;
644  Assert(!prstate->marked[rdoffnum]);
645  prstate->marked[rdoffnum] = true;
646 }
int nredirected
Definition: pruneheap.c:34
#define MaxHeapTuplesPerPage
Definition: htup_details.h:574
bool marked[MaxHeapTuplesPerPage+1]
Definition: pruneheap.c:42
#define Assert(condition)
Definition: c.h:739
OffsetNumber redirected[MaxHeapTuplesPerPage *2]
Definition: pruneheap.c:38

◆ heap_prune_record_unused()

static void heap_prune_record_unused ( PruneState prstate,
OffsetNumber  offnum 
)
static

Definition at line 661 of file pruneheap.c.

References Assert, PruneState::marked, MaxHeapTuplesPerPage, PruneState::nowunused, and PruneState::nunused.

Referenced by heap_prune_chain().

662 {
663  Assert(prstate->nunused < MaxHeapTuplesPerPage);
664  prstate->nowunused[prstate->nunused] = offnum;
665  prstate->nunused++;
666  Assert(!prstate->marked[offnum]);
667  prstate->marked[offnum] = true;
668 }
#define MaxHeapTuplesPerPage
Definition: htup_details.h:574
bool marked[MaxHeapTuplesPerPage+1]
Definition: pruneheap.c:42
int nunused
Definition: pruneheap.c:36
#define Assert(condition)
Definition: c.h:739
OffsetNumber nowunused[MaxHeapTuplesPerPage]
Definition: pruneheap.c:40