1 /*-------------------------------------------------------------------------
4 * heap page pruning and HOT-chain management code
6 * Portions Copyright (c) 1996-2010, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * $PostgreSQL: pgsql/src/backend/access/heap/pruneheap.c,v 1.25 2010/07/06 19:18:55 momjian Exp $
13 *-------------------------------------------------------------------------
17 #include "access/heapam.h"
18 #include "access/htup.h"
19 #include "access/transam.h"
20 #include "miscadmin.h"
22 #include "storage/bufmgr.h"
23 #include "storage/off.h"
24 #include "utils/rel.h"
25 #include "utils/tqual.h"
28 /* Working data for heap_page_prune and subroutines */
31 TransactionId new_prune_xid; /* new prune hint value for page */
32 TransactionId latestRemovedXid; /* latest xid to be removed by this
34 int nredirected; /* numbers of entries in arrays below */
37 /* arrays that accumulate indexes of items to be changed */
38 OffsetNumber redirected[MaxHeapTuplesPerPage * 2];
39 OffsetNumber nowdead[MaxHeapTuplesPerPage];
40 OffsetNumber nowunused[MaxHeapTuplesPerPage];
41 /* marked[i] is TRUE if item i is entered in one of the above arrays */
42 bool marked[MaxHeapTuplesPerPage + 1];
46 static int heap_prune_chain(Relation relation, Buffer buffer,
47 OffsetNumber rootoffnum,
48 TransactionId OldestXmin,
50 static void heap_prune_record_prunable(PruneState *prstate, TransactionId xid);
51 static void heap_prune_record_redirect(PruneState *prstate,
52 OffsetNumber offnum, OffsetNumber rdoffnum);
53 static void heap_prune_record_dead(PruneState *prstate, OffsetNumber offnum);
54 static void heap_prune_record_unused(PruneState *prstate, OffsetNumber offnum);
58 * Optionally prune and repair fragmentation in the specified page.
60 * This is an opportunistic function. It will perform housekeeping
61 * only if the page heuristically looks like a candidate for pruning and we
62 * can acquire buffer cleanup lock without blocking.
64 * Note: this is called quite often. It's important that it fall out quickly
65 * if there's not any use in pruning.
67 * Caller must have pin on the buffer, and must *not* have a lock on it.
69 * OldestXmin is the cutoff XID used to distinguish whether tuples are DEAD
70 * or RECENTLY_DEAD (see HeapTupleSatisfiesVacuum).
73 heap_page_prune_opt(Relation relation, Buffer buffer, TransactionId OldestXmin)
75 Page page = BufferGetPage(buffer);
79 * Let's see if we really need pruning.
81 * Forget it if page is not hinted to contain something prunable that's
82 * older than OldestXmin.
84 if (!PageIsPrunable(page, OldestXmin))
88 * We can't write WAL in recovery mode, so there's no point trying to
89 * clean the page. The master will likely issue a cleaning WAL record soon
90 * anyway, so this is no particular loss.
92 if (RecoveryInProgress())
96 * We prune when a previous UPDATE failed to find enough space on the page
97 * for a new tuple version, or when free space falls below the relation's
98 * fill-factor target (but not less than 10%).
100 * Checking free space here is questionable since we aren't holding any
101 * lock on the buffer; in the worst case we could get a bogus answer. It's
102 * unlikely to be *seriously* wrong, though, since reading either pd_lower
103 * or pd_upper is probably atomic. Avoiding taking a lock seems more
104 * important than sometimes getting a wrong answer in what is after all
105 * just a heuristic estimate.
107 minfree = RelationGetTargetPageFreeSpace(relation,
108 HEAP_DEFAULT_FILLFACTOR);
109 minfree = Max(minfree, BLCKSZ / 10);
111 if (PageIsFull(page) || PageGetHeapFreeSpace(page) < minfree)
113 /* OK, try to get exclusive buffer lock */
114 if (!ConditionalLockBufferForCleanup(buffer))
118 * Now that we have buffer lock, get accurate information about the
119 * page's free space, and recheck the heuristic about whether to
120 * prune. (We needn't recheck PageIsPrunable, since no one else could
121 * have pruned while we hold pin.)
123 if (PageIsFull(page) || PageGetHeapFreeSpace(page) < minfree)
125 TransactionId ignore = InvalidTransactionId; /* return value not
129 (void) heap_page_prune(relation, buffer, OldestXmin, true, &ignore);
132 /* And release buffer lock */
133 LockBuffer(buffer, BUFFER_LOCK_UNLOCK);
139 * Prune and repair fragmentation in the specified page.
141 * Caller must have pin and buffer cleanup lock on the page.
143 * OldestXmin is the cutoff XID used to distinguish whether tuples are DEAD
144 * or RECENTLY_DEAD (see HeapTupleSatisfiesVacuum).
146 * If report_stats is true then we send the number of reclaimed heap-only
147 * tuples to pgstats. (This must be FALSE during vacuum, since vacuum will
148 * send its own new total to pgstats, and we don't want this delta applied
151 * Returns the number of tuples deleted from the page and sets
155 heap_page_prune(Relation relation, Buffer buffer, TransactionId OldestXmin,
156 bool report_stats, TransactionId *latestRemovedXid)
159 Page page = BufferGetPage(buffer);
165 * Our strategy is to scan the page and make lists of items to change,
166 * then apply the changes within a critical section. This keeps as much
167 * logic as possible out of the critical section, and also ensures that
168 * WAL replay will work the same as the normal case.
170 * First, initialize the new pd_prune_xid value to zero (indicating no
171 * prunable tuples). If we find any tuples which may soon become
172 * prunable, we will save the lowest relevant XID in new_prune_xid. Also
173 * initialize the rest of our working state.
175 prstate.new_prune_xid = InvalidTransactionId;
176 prstate.latestRemovedXid = InvalidTransactionId;
177 prstate.nredirected = prstate.ndead = prstate.nunused = 0;
178 memset(prstate.marked, 0, sizeof(prstate.marked));
181 maxoff = PageGetMaxOffsetNumber(page);
182 for (offnum = FirstOffsetNumber;
184 offnum = OffsetNumberNext(offnum))
188 /* Ignore items already processed as part of an earlier chain */
189 if (prstate.marked[offnum])
192 /* Nothing to do if slot is empty or already dead */
193 itemid = PageGetItemId(page, offnum);
194 if (!ItemIdIsUsed(itemid) || ItemIdIsDead(itemid))
197 /* Process this item or chain of items */
198 ndeleted += heap_prune_chain(relation, buffer, offnum,
203 /* Any error while applying the changes is critical */
204 START_CRIT_SECTION();
206 /* Have we found any prunable items? */
207 if (prstate.nredirected > 0 || prstate.ndead > 0 || prstate.nunused > 0)
210 * Apply the planned item changes, then repair page fragmentation, and
211 * update the page's hint bit about whether it has free line pointers.
213 heap_page_prune_execute(buffer,
214 prstate.redirected, prstate.nredirected,
215 prstate.nowdead, prstate.ndead,
216 prstate.nowunused, prstate.nunused);
219 * Update the page's pd_prune_xid field to either zero, or the lowest
220 * XID of any soon-prunable tuple.
222 ((PageHeader) page)->pd_prune_xid = prstate.new_prune_xid;
225 * Also clear the "page is full" flag, since there's no point in
226 * repeating the prune/defrag process until something else happens to
231 MarkBufferDirty(buffer);
234 * Emit a WAL HEAP_CLEAN record showing what we did
236 if (!relation->rd_istemp)
240 Assert(TransactionIdIsValid(prstate.latestRemovedXid));
241 recptr = log_heap_clean(relation, buffer,
242 prstate.redirected, prstate.nredirected,
243 prstate.nowdead, prstate.ndead,
244 prstate.nowunused, prstate.nunused,
245 prstate.latestRemovedXid);
247 PageSetLSN(BufferGetPage(buffer), recptr);
248 PageSetTLI(BufferGetPage(buffer), ThisTimeLineID);
254 * If we didn't prune anything, but have found a new value for the
255 * pd_prune_xid field, update it and mark the buffer dirty. This is
256 * treated as a non-WAL-logged hint.
258 * Also clear the "page is full" flag if it is set, since there's no
259 * point in repeating the prune/defrag process until something else
260 * happens to the page.
262 if (((PageHeader) page)->pd_prune_xid != prstate.new_prune_xid ||
265 ((PageHeader) page)->pd_prune_xid = prstate.new_prune_xid;
267 SetBufferCommitInfoNeedsSave(buffer);
274 * If requested, report the number of tuples reclaimed to pgstats. This is
275 * ndeleted minus ndead, because we don't want to count a now-DEAD root
276 * item as a deletion for this purpose.
278 if (report_stats && ndeleted > prstate.ndead)
279 pgstat_update_heap_dead_tuples(relation, ndeleted - prstate.ndead);
281 *latestRemovedXid = prstate.latestRemovedXid;
284 * XXX Should we update the FSM information of this page ?
286 * There are two schools of thought here. We may not want to update FSM
287 * information so that the page is not used for unrelated UPDATEs/INSERTs
288 * and any free space in this page will remain available for further
289 * UPDATEs in *this* page, thus improving chances for doing HOT updates.
291 * But for a large table and where a page does not receive further UPDATEs
292 * for a long time, we might waste this space by not updating the FSM
293 * information. The relation may get extended and fragmented further.
295 * One possibility is to leave "fillfactor" worth of space in this page
296 * and update FSM with the remaining space.
298 * In any case, the current FSM implementation doesn't accept
299 * one-page-at-a-time updates, so this is all academic for now.
307 * Prune specified item pointer or a HOT chain originating at that item.
309 * If the item is an index-referenced tuple (i.e. not a heap-only tuple),
310 * the HOT chain is pruned by removing all DEAD tuples at the start of the HOT
311 * chain. We also prune any RECENTLY_DEAD tuples preceding a DEAD tuple.
312 * This is OK because a RECENTLY_DEAD tuple preceding a DEAD tuple is really
313 * DEAD, the OldestXmin test is just too coarse to detect it.
315 * The root line pointer is redirected to the tuple immediately after the
316 * latest DEAD tuple. If all tuples in the chain are DEAD, the root line
317 * pointer is marked LP_DEAD. (This includes the case of a DEAD simple
318 * tuple, which we treat as a chain of length 1.)
320 * OldestXmin is the cutoff XID used to identify dead tuples.
322 * We don't actually change the page here, except perhaps for hint-bit updates
323 * caused by HeapTupleSatisfiesVacuum. We just add entries to the arrays in
324 * prstate showing the changes to be made. Items to be redirected are added
325 * to the redirected[] array (two entries per redirection); items to be set to
326 * LP_DEAD state are added to nowdead[]; and items to be set to LP_UNUSED
327 * state are added to nowunused[].
329 * Returns the number of tuples (to be) deleted from the page.
332 heap_prune_chain(Relation relation, Buffer buffer, OffsetNumber rootoffnum,
333 TransactionId OldestXmin,
337 Page dp = (Page) BufferGetPage(buffer);
338 TransactionId priorXmax = InvalidTransactionId;
340 HeapTupleHeader htup;
341 OffsetNumber latestdead = InvalidOffsetNumber,
342 maxoff = PageGetMaxOffsetNumber(dp),
344 OffsetNumber chainitems[MaxHeapTuplesPerPage];
348 rootlp = PageGetItemId(dp, rootoffnum);
351 * If it's a heap-only tuple, then it is not the start of a HOT chain.
353 if (ItemIdIsNormal(rootlp))
355 htup = (HeapTupleHeader) PageGetItem(dp, rootlp);
356 if (HeapTupleHeaderIsHeapOnly(htup))
359 * If the tuple is DEAD and doesn't chain to anything else, mark
360 * it unused immediately. (If it does chain, we can only remove
361 * it as part of pruning its chain.)
363 * We need this primarily to handle aborted HOT updates, that is,
364 * XMIN_INVALID heap-only tuples. Those might not be linked to by
365 * any chain, since the parent tuple might be re-updated before
366 * any pruning occurs. So we have to be able to reap them
367 * separately from chain-pruning. (Note that
368 * HeapTupleHeaderIsHotUpdated will never return true for an
369 * XMIN_INVALID tuple, so this code will work even when there were
370 * sequential updates within the aborted transaction.)
372 * Note that we might first arrive at a dead heap-only tuple
373 * either here or while following a chain below. Whichever path
374 * gets there first will mark the tuple unused.
376 if (HeapTupleSatisfiesVacuum(htup, OldestXmin, buffer)
377 == HEAPTUPLE_DEAD && !HeapTupleHeaderIsHotUpdated(htup))
379 heap_prune_record_unused(prstate, rootoffnum);
380 HeapTupleHeaderAdvanceLatestRemovedXid(htup,
381 &prstate->latestRemovedXid);
385 /* Nothing more to do */
390 /* Start from the root tuple */
393 /* while not end of the chain */
400 /* Some sanity checks */
401 if (offnum < FirstOffsetNumber || offnum > maxoff)
404 /* If item is already processed, stop --- it must not be same chain */
405 if (prstate->marked[offnum])
408 lp = PageGetItemId(dp, offnum);
410 /* Unused item obviously isn't part of the chain */
411 if (!ItemIdIsUsed(lp))
415 * If we are looking at the redirected root line pointer, jump to the
416 * first normal tuple in the chain. If we find a redirect somewhere
417 * else, stop --- it must not be same chain.
419 if (ItemIdIsRedirected(lp))
422 break; /* not at start of chain */
423 chainitems[nchain++] = offnum;
424 offnum = ItemIdGetRedirect(rootlp);
429 * Likewise, a dead item pointer can't be part of the chain. (We
430 * already eliminated the case of dead root tuple outside this
433 if (ItemIdIsDead(lp))
436 Assert(ItemIdIsNormal(lp));
437 htup = (HeapTupleHeader) PageGetItem(dp, lp);
440 * Check the tuple XMIN against prior XMAX, if any
442 if (TransactionIdIsValid(priorXmax) &&
443 !TransactionIdEquals(HeapTupleHeaderGetXmin(htup), priorXmax))
447 * OK, this tuple is indeed a member of the chain.
449 chainitems[nchain++] = offnum;
452 * Check tuple's visibility status.
454 tupdead = recent_dead = false;
456 switch (HeapTupleSatisfiesVacuum(htup, OldestXmin, buffer))
462 case HEAPTUPLE_RECENTLY_DEAD:
466 * This tuple may soon become DEAD. Update the hint field so
467 * that the page is reconsidered for pruning in future.
469 heap_prune_record_prunable(prstate,
470 HeapTupleHeaderGetXmax(htup));
473 case HEAPTUPLE_DELETE_IN_PROGRESS:
476 * This tuple may soon become DEAD. Update the hint field so
477 * that the page is reconsidered for pruning in future.
479 heap_prune_record_prunable(prstate,
480 HeapTupleHeaderGetXmax(htup));
484 case HEAPTUPLE_INSERT_IN_PROGRESS:
487 * If we wanted to optimize for aborts, we might consider
488 * marking the page prunable when we see INSERT_IN_PROGRESS.
489 * But we don't. See related decisions about when to mark the
490 * page prunable in heapam.c.
495 elog(ERROR, "unexpected HeapTupleSatisfiesVacuum result");
500 * Remember the last DEAD tuple seen. We will advance past
501 * RECENTLY_DEAD tuples just in case there's a DEAD one after them;
502 * but we can't advance past anything else. (XXX is it really worth
503 * continuing to scan beyond RECENTLY_DEAD? The case where we will
504 * find another DEAD tuple is a fairly unusual corner case.)
509 HeapTupleHeaderAdvanceLatestRemovedXid(htup,
510 &prstate->latestRemovedXid);
512 else if (!recent_dead)
516 * If the tuple is not HOT-updated, then we are at the end of this
519 if (!HeapTupleHeaderIsHotUpdated(htup))
523 * Advance to next chain member.
525 Assert(ItemPointerGetBlockNumber(&htup->t_ctid) ==
526 BufferGetBlockNumber(buffer));
527 offnum = ItemPointerGetOffsetNumber(&htup->t_ctid);
528 priorXmax = HeapTupleHeaderGetXmax(htup);
532 * If we found a DEAD tuple in the chain, adjust the HOT chain so that all
533 * the DEAD tuples at the start of the chain are removed and the root line
534 * pointer is appropriately redirected.
536 if (OffsetNumberIsValid(latestdead))
539 * Mark as unused each intermediate item that we are able to remove
542 * When the previous item is the last dead tuple seen, we are at the
543 * right candidate for redirection.
545 for (i = 1; (i < nchain) && (chainitems[i - 1] != latestdead); i++)
547 heap_prune_record_unused(prstate, chainitems[i]);
552 * If the root entry had been a normal tuple, we are deleting it, so
553 * count it in the result. But changing a redirect (even to DEAD
554 * state) doesn't count.
556 if (ItemIdIsNormal(rootlp))
560 * If the DEAD tuple is at the end of the chain, the entire chain is
561 * dead and the root line pointer can be marked dead. Otherwise just
562 * redirect the root to the correct chain member.
565 heap_prune_record_dead(prstate, rootoffnum);
567 heap_prune_record_redirect(prstate, rootoffnum, chainitems[i]);
569 else if (nchain < 2 && ItemIdIsRedirected(rootlp))
572 * We found a redirect item that doesn't point to a valid follow-on
573 * item. This can happen if the loop in heap_page_prune caused us to
574 * visit the dead successor of a redirect item before visiting the
575 * redirect item. We can clean up by setting the redirect item to
578 heap_prune_record_dead(prstate, rootoffnum);
584 /* Record lowest soon-prunable XID */
586 heap_prune_record_prunable(PruneState *prstate, TransactionId xid)
589 * This should exactly match the PageSetPrunable macro. We can't store
590 * directly into the page header yet, so we update working state.
592 Assert(TransactionIdIsNormal(xid));
593 if (!TransactionIdIsValid(prstate->new_prune_xid) ||
594 TransactionIdPrecedes(xid, prstate->new_prune_xid))
595 prstate->new_prune_xid = xid;
598 /* Record item pointer to be redirected */
600 heap_prune_record_redirect(PruneState *prstate,
601 OffsetNumber offnum, OffsetNumber rdoffnum)
603 Assert(prstate->nredirected < MaxHeapTuplesPerPage);
604 prstate->redirected[prstate->nredirected * 2] = offnum;
605 prstate->redirected[prstate->nredirected * 2 + 1] = rdoffnum;
606 prstate->nredirected++;
607 Assert(!prstate->marked[offnum]);
608 prstate->marked[offnum] = true;
609 Assert(!prstate->marked[rdoffnum]);
610 prstate->marked[rdoffnum] = true;
613 /* Record item pointer to be marked dead */
615 heap_prune_record_dead(PruneState *prstate, OffsetNumber offnum)
617 Assert(prstate->ndead < MaxHeapTuplesPerPage);
618 prstate->nowdead[prstate->ndead] = offnum;
620 Assert(!prstate->marked[offnum]);
621 prstate->marked[offnum] = true;
624 /* Record item pointer to be marked unused */
626 heap_prune_record_unused(PruneState *prstate, OffsetNumber offnum)
628 Assert(prstate->nunused < MaxHeapTuplesPerPage);
629 prstate->nowunused[prstate->nunused] = offnum;
631 Assert(!prstate->marked[offnum]);
632 prstate->marked[offnum] = true;
637 * Perform the actual page changes needed by heap_page_prune.
638 * It is expected that the caller has suitable pin and lock on the
639 * buffer, and is inside a critical section.
641 * This is split out because it is also used by heap_xlog_clean()
642 * to replay the WAL record when needed after a crash. Note that the
643 * arguments are identical to those of log_heap_clean().
646 heap_page_prune_execute(Buffer buffer,
647 OffsetNumber *redirected, int nredirected,
648 OffsetNumber *nowdead, int ndead,
649 OffsetNumber *nowunused, int nunused)
651 Page page = (Page) BufferGetPage(buffer);
652 OffsetNumber *offnum;
655 /* Update all redirected line pointers */
657 for (i = 0; i < nredirected; i++)
659 OffsetNumber fromoff = *offnum++;
660 OffsetNumber tooff = *offnum++;
661 ItemId fromlp = PageGetItemId(page, fromoff);
663 ItemIdSetRedirect(fromlp, tooff);
666 /* Update all now-dead line pointers */
668 for (i = 0; i < ndead; i++)
670 OffsetNumber off = *offnum++;
671 ItemId lp = PageGetItemId(page, off);
676 /* Update all now-unused line pointers */
678 for (i = 0; i < nunused; i++)
680 OffsetNumber off = *offnum++;
681 ItemId lp = PageGetItemId(page, off);
687 * Finally, repair any fragmentation, and update the page's hint bit about
688 * whether it has free pointers.
690 PageRepairFragmentation(page);
695 * For all items in this page, find their respective root line pointers.
696 * If item k is part of a HOT-chain with root at item j, then we set
697 * root_offsets[k - 1] = j.
699 * The passed-in root_offsets array must have MaxHeapTuplesPerPage entries.
700 * We zero out all unused entries.
702 * The function must be called with at least share lock on the buffer, to
703 * prevent concurrent prune operations.
705 * Note: The information collected here is valid only as long as the caller
706 * holds a pin on the buffer. Once pin is released, a tuple might be pruned
707 * and reused by a completely unrelated tuple.
710 heap_get_root_tuples(Page page, OffsetNumber *root_offsets)
715 MemSet(root_offsets, 0, MaxHeapTuplesPerPage * sizeof(OffsetNumber));
717 maxoff = PageGetMaxOffsetNumber(page);
718 for (offnum = FirstOffsetNumber; offnum <= maxoff; offnum = OffsetNumberNext(offnum))
720 ItemId lp = PageGetItemId(page, offnum);
721 HeapTupleHeader htup;
722 OffsetNumber nextoffnum;
723 TransactionId priorXmax;
725 /* skip unused and dead items */
726 if (!ItemIdIsUsed(lp) || ItemIdIsDead(lp))
729 if (ItemIdIsNormal(lp))
731 htup = (HeapTupleHeader) PageGetItem(page, lp);
734 * Check if this tuple is part of a HOT-chain rooted at some other
735 * tuple. If so, skip it for now; we'll process it when we find
738 if (HeapTupleHeaderIsHeapOnly(htup))
742 * This is either a plain tuple or the root of a HOT-chain.
743 * Remember it in the mapping.
745 root_offsets[offnum - 1] = offnum;
747 /* If it's not the start of a HOT-chain, we're done with it */
748 if (!HeapTupleHeaderIsHotUpdated(htup))
751 /* Set up to scan the HOT-chain */
752 nextoffnum = ItemPointerGetOffsetNumber(&htup->t_ctid);
753 priorXmax = HeapTupleHeaderGetXmax(htup);
757 /* Must be a redirect item. We do not set its root_offsets entry */
758 Assert(ItemIdIsRedirected(lp));
759 /* Set up to scan the HOT-chain */
760 nextoffnum = ItemIdGetRedirect(lp);
761 priorXmax = InvalidTransactionId;
765 * Now follow the HOT-chain and collect other tuples in the chain.
767 * Note: Even though this is a nested loop, the complexity of the
768 * function is O(N) because a tuple in the page should be visited not
769 * more than twice, once in the outer loop and once in HOT-chain
774 lp = PageGetItemId(page, nextoffnum);
776 /* Check for broken chains */
777 if (!ItemIdIsNormal(lp))
780 htup = (HeapTupleHeader) PageGetItem(page, lp);
782 if (TransactionIdIsValid(priorXmax) &&
783 !TransactionIdEquals(priorXmax, HeapTupleHeaderGetXmin(htup)))
786 /* Remember the root line pointer for this item */
787 root_offsets[nextoffnum - 1] = offnum;
789 /* Advance to next chain member, if any */
790 if (!HeapTupleHeaderIsHotUpdated(htup))
793 nextoffnum = ItemPointerGetOffsetNumber(&htup->t_ctid);
794 priorXmax = HeapTupleHeaderGetXmax(htup);