1/*-------------------------------------------------------------------------
4 * heap page pruning and HOT-chain management code
6 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * src/backend/access/heap/pruneheap.c
13 *-------------------------------------------------------------------------
32/* Working data for heap_page_prune_and_freeze() and subroutines */
35 /*-------------------------------------------------------
36 * Arguments passed to heap_page_prune_and_freeze()
37 *-------------------------------------------------------
40 /* tuple visibility test, initialized for the relation */
42 /* whether or not dead items can be set LP_UNUSED during pruning */
44 /* whether to attempt freezing tuples */
48 /*-------------------------------------------------------
49 * Fields describing what to do to the page
50 *-------------------------------------------------------
58 /* arrays that accumulate indexes of items to be changed */
64 /*-------------------------------------------------------
65 * Working state for HOT chain processing
66 *-------------------------------------------------------
70 * 'root_items' contains offsets of all LP_REDIRECT line pointers and
71 * normal non-HOT tuples. They can be stand-alone items or the first item
72 * in a HOT chain. 'heaponly_items' contains heap-only tuples which can
73 * only be removed as part of a HOT chain.
81 * processed[offnum] is true if item at offnum has been processed.
83 * This needs to be MaxHeapTuplesPerPage + 1 long as FirstOffsetNumber is
84 * 1. Otherwise every access would need to subtract 1.
89 * Tuple visibility is only computed once for each tuple, for correctness
90 * and efficiency reasons; see comment in heap_page_prune_and_freeze() for
91 * details. This is of type int8[], instead of HTSV_Result[], so we can
92 * use -1 to indicate no visibility has been computed, e.g. for LP_DEAD
95 * This needs to be MaxHeapTuplesPerPage + 1 long as FirstOffsetNumber is
96 * 1. Otherwise every access would need to subtract 1.
101 * Freezing-related state.
105 /*-------------------------------------------------------
106 * Information about what was done
108 * These fields are not used by pruning itself for the most part, but are
109 * used to collect information about what was pruned and what state the
110 * page is in after pruning, for the benefit of the caller. They are
111 * copied to the caller's PruneFreezeResult at the end.
112 * -------------------------------------------------------
115 int ndeleted;
/* Number of tuples deleted from the page */
117 /* Number of live and recently dead tuples, after pruning */
121 /* Whether or not the page makes rel truncation unsafe */
125 * LP_DEAD items on the page after pruning. Includes existing LP_DEAD
132 * all_visible and all_frozen indicate if the all-visible and all-frozen
133 * bits in the visibility map can be set for this page after pruning.
135 * visibility_cutoff_xid is the newest xmin of live tuples on the page.
136 * The caller can use it as the conflict horizon, when setting the VM
137 * bits. It is only valid if we froze some tuples, and all_frozen is
140 * NOTE: all_visible and all_frozen don't include LP_DEAD items. That's
141 * convenient for heap_page_prune_and_freeze(), to use them to decide
142 * whether to freeze the page or not. The all_visible and all_frozen
143 * values returned to the caller are adjusted to include LP_DEAD items at
146 * all_frozen should only be considered valid if all_visible is also set;
147 * we don't bother to clear the all_frozen flag every time we clear the
181 * Optionally prune and repair fragmentation in the specified page.
183 * This is an opportunistic function. It will perform housekeeping
184 * only if the page heuristically looks like a candidate for pruning and we
185 * can acquire buffer cleanup lock without blocking.
187 * Note: this is called quite often. It's important that it fall out quickly
188 * if there's not any use in pruning.
190 * Caller must have pin on the buffer, and must *not* have a lock on it.
201 * We can't write WAL in recovery mode, so there's no point trying to
202 * clean the page. The primary will likely issue a cleaning WAL record
203 * soon anyway, so this is no particular loss.
209 * First check whether there's any chance there's something to prune,
210 * determining the appropriate horizon is a waste if there's no prune_xid
211 * (i.e. no updates/deletes left potentially dead tuples around).
213 prune_xid = ((
PageHeader) page)->pd_prune_xid;
218 * Check whether prune_xid indicates that there may be dead rows that can
227 * We prune when a previous UPDATE failed to find enough space on the page
228 * for a new tuple version, or when free space falls below the relation's
229 * fill-factor target (but not less than 10%).
231 * Checking free space here is questionable since we aren't holding any
232 * lock on the buffer; in the worst case we could get a bogus answer. It's
233 * unlikely to be *seriously* wrong, though, since reading either pd_lower
234 * or pd_upper is probably atomic. Avoiding taking a lock seems more
235 * important than sometimes getting a wrong answer in what is after all
236 * just a heuristic estimate.
240 minfree =
Max(minfree, BLCKSZ / 10);
244 /* OK, try to get exclusive buffer lock */
249 * Now that we have buffer lock, get accurate information about the
250 * page's free space, and recheck the heuristic about whether to
259 * For now, pass mark_unused_now as false regardless of whether or
260 * not the relation has indexes, since we cannot safely determine
261 * that during on-access pruning with the current implementation.
267 * Report the number of tuples reclaimed to pgstats. This is
268 * presult.ndeleted minus the number of newly-LP_DEAD-set items.
270 * We derive the number of dead tuples like this to avoid totally
271 * forgetting about items that were set to LP_DEAD, since they
272 * still need to be cleaned up by VACUUM. We only want to count
273 * heap-only tuples that just became LP_UNUSED in our report,
276 * VACUUM doesn't have to compensate in the same way when it
277 * tracks ndeleted, since it will set the same LP_DEAD items to
278 * LP_UNUSED separately.
285 /* And release buffer lock */
289 * We avoid reuse of any free space created on the page by unrelated
290 * UPDATEs/INSERTs by opting to not update the FSM at this point. The
291 * free space should be reused by UPDATEs to *this* page.
298 * Prune and repair fragmentation and potentially freeze tuples on the
301 * Caller must have pin and buffer cleanup lock on the page. Note that we
302 * don't update the FSM information for page on caller's behalf. Caller might
303 * also need to account for a reduction in the length of the line pointer
304 * array following array truncation by us.
306 * If the HEAP_PRUNE_FREEZE option is set, we will also freeze tuples if it's
307 * required in order to advance relfrozenxid / relminmxid, or if it's
308 * considered advantageous for overall system performance to do so now. The
309 * 'cutoffs', 'presult', 'new_relfrozen_xid' and 'new_relmin_mxid' arguments
310 * are required when freezing. When HEAP_PRUNE_FREEZE option is set, we also
311 * set presult->all_visible and presult->all_frozen on exit, to indicate if
312 * the VM bits can be set. They are always set to false when the
313 * HEAP_PRUNE_FREEZE option is not set, because at the moment only callers
314 * that also freeze need that information.
316 * vistest is used to distinguish whether tuples are DEAD or RECENTLY_DEAD
317 * (see heap_prune_satisfies_vacuum).
320 * MARK_UNUSED_NOW indicates that dead items can be set LP_UNUSED during
323 * FREEZE indicates that we will also freeze tuples, and will return
324 * 'all_visible', 'all_frozen' flags to the caller.
326 * cutoffs contains the freeze cutoffs, established by VACUUM at the beginning
327 * of vacuuming the relation. Required if HEAP_PRUNE_FREEZE option is set.
328 * cutoffs->OldestXmin is also used to determine if dead tuples are
329 * HEAPTUPLE_RECENTLY_DEAD or HEAPTUPLE_DEAD.
331 * presult contains output parameters needed by callers, such as the number of
332 * tuples removed and the offsets of dead items on the page after pruning.
333 * heap_page_prune_and_freeze() is responsible for initializing it. Required
336 * reason indicates why the pruning is performed. It is included in the WAL
337 * record for debugging and analysis purposes, but otherwise has no effect.
339 * off_loc is the offset location required by the caller to use in error
342 * new_relfrozen_xid and new_relmin_mxid must provided by the caller if the
343 * HEAP_PRUNE_FREEZE option is set. On entry, they contain the oldest XID and
344 * multi-XID seen on the relation so far. They will be updated with oldest
345 * values present on the page after pruning. After processing the whole
346 * relation, VACUUM can use these values as the new relfrozenxid/relminmxid
372 /* Copy parameters to prstate */
379 * Our strategy is to scan the page and make lists of items to change,
380 * then apply the changes within a critical section. This keeps as much
381 * logic as possible out of the critical section, and also ensures that
382 * WAL replay will work the same as the normal case.
384 * First, initialize the new pd_prune_xid value to zero (indicating no
385 * prunable tuples). If we find any tuples which may soon become
386 * prunable, we will save the lowest relevant XID in new_prune_xid. Also
387 * initialize the rest of our working state.
395 /* initialize page freezing working state */
399 Assert(new_relfrozen_xid && new_relmin_mxid);
407 Assert(new_relfrozen_xid == NULL && new_relmin_mxid == NULL);
422 * Caller may update the VM after we're done. We can keep track of
423 * whether the page will be all-visible and all-frozen after pruning and
424 * freezing to help the caller to do that.
426 * Currently, only VACUUM sets the VM bits. To save the effort, only do
427 * the bookkeeping if the caller needs it. Currently, that's tied to
428 * HEAP_PAGE_PRUNE_FREEZE, but it could be a separate flag if you wanted
429 * to update the VM bits without also freezing or freeze without also
430 * setting the VM bits.
432 * In addition to telling the caller whether it can set the VM bit, we
433 * also use 'all_visible' and 'all_frozen' for our own decision-making. If
434 * the whole page would become frozen, we consider opportunistically
435 * freezing tuples. We will not be able to freeze the whole page if there
436 * are tuples present that are not visible to everyone or if there are
437 * dead tuples which are not yet removable. However, dead tuples which
438 * will be removed by the end of vacuuming should not preclude us from
439 * opportunistically freezing. Because of that, we do not clear
440 * all_visible when we see LP_DEAD items. We fix that at the end of the
441 * function, when we return the value to the caller, so that the caller
442 * doesn't set the VM bit incorrectly.
452 * Initializing to false allows skipping the work to update them in
453 * heap_prune_record_unchanged_lp_normal().
460 * The visibility cutoff xid is the newest xmin of live tuples on the
461 * page. In the common case, this will be set as the conflict horizon the
462 * caller can use for updating the VM. If, at the end of freezing and
463 * pruning, the page is all-frozen, there is no possibility that any
464 * running transaction on the standby does not see tuples on the page as
465 * all-visible, so the conflict horizon remains InvalidTransactionId.
473 * Determine HTSV for all tuples, and queue them up for processing as HOT
474 * chain roots or as heap-only items.
476 * Determining HTSV only once for each tuple is required for correctness,
477 * to deal with cases where running HTSV twice could result in different
478 * results. For example, RECENTLY_DEAD can turn to DEAD if another
479 * checked item causes GlobalVisTestIsRemovableFullXid() to update the
480 * horizon, or INSERT_IN_PROGRESS can change to DEAD if the inserting
481 * transaction aborts.
483 * It's also good for performance. Most commonly tuples within a page are
484 * stored at decreasing offsets (while the items are stored at increasing
485 * offsets). When processing all tuples on a page this leads to reading
486 * memory at decreasing offsets within a page, with a variable stride.
487 * That's hard for CPU prefetchers to deal with. Processing the items in
488 * reverse order (and thus the tuples in increasing order) increases
489 * prefetching efficiency significantly / decreases the number of cache
492 for (offnum = maxoff;
500 * Set the offset number so that we can display it along with any
501 * error that occurred while processing this tuple.
506 prstate.
htsv[offnum] = -1;
508 /* Nothing to do if slot doesn't contain a tuple */
518 * If the caller set mark_unused_now true, we can set dead line
519 * pointers LP_UNUSED now.
530 /* This is the start of a HOT chain */
538 * Get the tuple's visibility status and queue it up for processing.
555 * If checksums are enabled, heap_prune_satisfies_vacuum() may have caused
556 * an FPI to be emitted.
561 * Process HOT chains.
563 * We added the items to the array starting from 'maxoff', so by
564 * processing the array in reverse order, we process the items in
565 * ascending offset number order. The order doesn't matter for
566 * correctness, but some quick micro-benchmarking suggests that this is
567 * faster. (Earlier PostgreSQL versions, which scanned all the items on
568 * the page instead of using the root_items array, also did it in
569 * ascending offset number order.)
575 /* Ignore items already processed as part of an earlier chain */
579 /* see preceding loop */
582 /* Process this item or chain of items */
587 * Process any heap-only tuples that were not already processed as part of
597 /* see preceding loop */
601 * If the tuple is DEAD and doesn't chain to anything else, mark it
602 * unused. (If it does chain, we can only remove it as part of
603 * pruning its chain.)
605 * We need this primarily to handle aborted HOT updates, that is,
606 * XMIN_INVALID heap-only tuples. Those might not be linked to by any
607 * chain, since the parent tuple might be re-updated before any
608 * pruning occurs. So we have to be able to reap them separately from
609 * chain-pruning. (Note that HeapTupleHeaderIsHotUpdated will never
610 * return true for an XMIN_INVALID tuple, so this code will work even
611 * when there were sequential updates within the aborted transaction.)
627 * This tuple should've been processed and removed as part of
628 * a HOT chain, so something's wrong. To preserve evidence,
629 * we don't dare to remove it. We cannot leave behind a DEAD
630 * tuple either, because that will cause VACUUM to error out.
631 * Throwing an error with a distinct error message seems like
632 * the least bad option.
634 elog(
ERROR,
"dead heap-only tuple (%u, %d) is not linked to from any HOT chain",
642 /* We should now have processed every tuple exactly once */
643#ifdef USE_ASSERT_CHECKING
654 /* Clear the offset information once we have processed the given page. */
662 * Even if we don't prune anything, if we found a new value for the
663 * pd_prune_xid field or the page was marked full, we will update the hint
670 * Decide if we want to go ahead with freezing according to the freeze
671 * plans we prepared, or not.
679 * heap_prepare_freeze_tuple indicated that at least one XID/MXID
680 * from before FreezeLimit/MultiXactCutoff is present. Must
681 * freeze to advance relfrozenxid/relminmxid.
688 * Opportunistically freeze the page if we are generating an FPI
689 * anyway and if doing so means that we can set the page
690 * all-frozen afterwards (might not happen until VACUUM's final
693 * XXX: Previously, we knew if pruning emitted an FPI by checking
694 * pgWalUsage.wal_fpi before and after pruning. Once the freeze
695 * and prune records were combined, this heuristic couldn't be
696 * used anymore. The opportunistic freeze heuristic must be
697 * improved; however, for now, try to approximate the old logic.
702 * Freezing would make the page all-frozen. Have already
703 * emitted an FPI or will do so anyway?
727 * Validate the tuples we will be freezing before entering the
735 * The page contained some tuples that were not already frozen, and we
736 * chose not to freeze them now. The page won't be all-frozen then.
741 prstate.
nfrozen = 0;
/* avoid miscounts in instrumentation */
746 * We have no freeze plans to execute. The page might already be
747 * all-frozen (perhaps only following pruning), though. Such pages
748 * can be marked all-frozen in the VM by our caller, even though none
749 * of its tuples were newly frozen here.
753 /* Any error while applying the changes is critical */
759 * Update the page's pd_prune_xid field to either zero, or the lowest
760 * XID of any soon-prunable tuple.
765 * Also clear the "page is full" flag, since there's no point in
766 * repeating the prune/defrag process until something else happens to
772 * If that's all we had to do to the page, this is a non-WAL-logged
773 * hint. If we are going to freeze or prune the page, we will mark
774 * the buffer dirty below.
776 if (!do_freeze && !do_prune)
780 if (do_prune || do_freeze)
782 /* Apply the planned item changes and repair page fragmentation. */
797 * Emit a WAL XLOG_HEAP2_PRUNE* record showing what we did
802 * The snapshotConflictHorizon for the whole record should be the
803 * most conservative of all the horizons calculated for any of the
804 * possible modifications. If this record will prune tuples, any
805 * transactions on the standby older than the youngest xmax of the
806 * most recently removed tuple this record will prune will
807 * conflict. If this record will freeze tuples, any transactions
808 * on the standby with xids older than the youngest tuple this
809 * record will freeze will conflict.
815 * We can use the visibility_cutoff_xid as our cutoff for
816 * conflicts when the whole page is eligible to become all-frozen
817 * in the VM once we're done with it. Otherwise we generate a
818 * conservative cutoff by stepping back from OldestXmin.
826 /* Avoids false conflicts when hot_standby_feedback in use */
833 conflict_xid = frz_conflict_horizon;
849 /* Copy information back for caller */
857 * It was convenient to ignore LP_DEAD items in all_visible earlier on to
858 * make the choice of whether or not to freeze the page unaffected by the
859 * short-term presence of LP_DEAD items. These LP_DEAD items were
860 * effectively assumed to be LP_UNUSED items in the making. It doesn't
861 * matter which vacuum heap pass (initial pass or final pass) ends up
862 * setting the page all-frozen, as long as the ongoing VACUUM does it.
864 * Now that freezing has been finalized, unset all_visible if there are
865 * any LP_DEAD items on the page. It needs to reflect the present state
866 * of the page, as expected by our caller.
882 * For callers planning to update the visibility map, the conflict horizon
883 * for that record must be the newest xmin on the page. However, if the
884 * page is completely frozen, there can be no conflict and the
885 * vm_conflict_horizon should remain InvalidTransactionId. This includes
886 * the case that we just froze all the tuples; the prune-freeze record
887 * included the conflict XID already so the caller doesn't need it.
895 /* the presult->deadoffsets array was already filled in */
914 * Perform visibility checks for heap pruning.
928 * For VACUUM, we must be sure to prune tuples with xmax older than
929 * OldestXmin -- a visibility cutoff determined at the beginning of
930 * vacuuming the relation. OldestXmin is used for freezing determination
931 * and we cannot freeze dead tuples' xmaxes.
939 * Determine whether or not the tuple is considered dead when compared
940 * with the provided GlobalVisState. On-access pruning does not provide
941 * VacuumCutoffs. And for vacuum, even if the tuple's xmax is not older
942 * than OldestXmin, GlobalVisTestIsRemovableXid() could find the row dead
943 * if the GlobalVisState has been updated since the beginning of vacuuming
954 * Pruning calculates tuple visibility once and saves the results in an array
955 * of int8. See PruneState.htsv for details. This helper function is meant
956 * to guard against examining visibility status array members which have not
968 * Prune specified line pointer or a HOT chain originating at line pointer.
970 * Tuple visibility information is provided in prstate->htsv.
972 * If the item is an index-referenced tuple (i.e. not a heap-only tuple),
973 * the HOT chain is pruned by removing all DEAD tuples at the start of the HOT
974 * chain. We also prune any RECENTLY_DEAD tuples preceding a DEAD tuple.
975 * This is OK because a RECENTLY_DEAD tuple preceding a DEAD tuple is really
976 * DEAD, our visibility test is just too coarse to detect it.
978 * Pruning must never leave behind a DEAD tuple that still has tuple storage.
979 * VACUUM isn't prepared to deal with that case.
981 * The root line pointer is redirected to the tuple immediately after the
982 * latest DEAD tuple. If all tuples in the chain are DEAD, the root line
983 * pointer is marked LP_DEAD. (This includes the case of a DEAD simple
984 * tuple, which we treat as a chain of length 1.)
986 * We don't actually change the page here. We just add entries to the arrays in
987 * prstate showing the changes to be made. Items to be redirected are added
988 * to the redirected[] array (two entries per redirection); items to be set to
989 * LP_DEAD state are added to nowdead[]; and items to be set to LP_UNUSED
990 * state are added to nowunused[]. We perform bookkeeping of live tuples,
991 * visibility etc. based on what the page will look like after the changes
992 * applied. All that bookkeeping is performed in the heap_prune_record_*()
993 * subroutines. The division of labor is that heap_prune_chain() decides the
994 * fate of each tuple, ie. whether it's going to be removed, redirected or
995 * left unchanged, and the heap_prune_record_*() subroutines update PruneState
996 * based on that outcome.
1008 * After traversing the HOT chain, ndeadchain is the index in chainitems
1009 * of the first live successor after the last dead item.
1016 /* Start from the root tuple */
1017 offnum = rootoffnum;
1019 /* while not end of the chain */
1025 /* Sanity check (pure paranoia) */
1030 * An offset past the end of page's line pointer array is possible
1031 * when the array was truncated (original item must have been unused)
1033 if (offnum > maxoff)
1036 /* If item is already processed, stop --- it must not be same chain */
1043 * Unused item obviously isn't part of the chain. Likewise, a dead
1044 * line pointer can't be part of the chain. Both of those cases were
1045 * already marked as processed.
1051 * If we are looking at the redirected root line pointer, jump to the
1052 * first normal tuple in the chain. If we find a redirect somewhere
1053 * else, stop --- it must not be same chain.
1058 break;
/* not at start of chain */
1059 chainitems[nchain++] = offnum;
1069 * Check the tuple XMIN against prior XMAX, if any
1076 * OK, this tuple is indeed a member of the chain.
1078 chainitems[nchain++] = offnum;
1084 /* Remember the last DEAD tuple seen */
1085 ndeadchain = nchain;
1088 /* Advance to next chain member */
1094 * We don't need to advance the conflict horizon for
1095 * RECENTLY_DEAD tuples, even if we are removing them. This
1096 * is because we only remove RECENTLY_DEAD tuples if they
1097 * precede a DEAD tuple, and the DEAD tuple must have been
1098 * inserted by a newer transaction than the RECENTLY_DEAD
1099 * tuple by virtue of being later in the chain. We will have
1100 * advanced the conflict horizon for the DEAD tuple.
1104 * Advance past RECENTLY_DEAD tuples just in case there's a
1105 * DEAD one after them. We have to make sure that we don't
1106 * miss any DEAD tuples, since DEAD tuples that still have
1107 * tuple storage after pruning will confuse VACUUM.
1117 elog(
ERROR,
"unexpected HeapTupleSatisfiesVacuum result");
1122 * If the tuple is not HOT-updated, then we are at the end of this
1128 /* HOT implies it can't have moved to different partition */
1132 * Advance to next chain member.
1142 * We found a redirect item that doesn't point to a valid follow-on
1143 * item. This can happen if the loop in heap_page_prune_and_freeze()
1144 * caused us to visit the dead successor of a redirect item before
1145 * visiting the redirect item. We can clean up by setting the
1146 * redirect item to LP_DEAD state or LP_UNUSED if the caller
1155 if (ndeadchain == 0)
1158 * No DEAD tuple was found, so the chain is entirely composed of
1159 * normal, unchanged tuples. Leave it alone.
1168 for (;
i < nchain;
i++)
1171 else if (ndeadchain == nchain)
1174 * The entire chain is dead. Mark the root line pointer LP_DEAD, and
1175 * fully remove the other tuples in the chain.
1178 for (
int i = 1;
i < nchain;
i++)
1184 * We found a DEAD tuple in the chain. Redirect the root line pointer
1185 * to the first non-DEAD tuple, and mark as unused each intermediate
1186 * item that we are able to remove from the chain.
1190 for (
int i = 1;
i < ndeadchain;
i++)
1193 /* the rest of tuples in the chain are normal, unchanged tuples */
1194 for (
int i = ndeadchain;
i < nchain;
i++)
1199/* Record lowest soon-prunable XID */
1204 * This should exactly match the PageSetPrunable macro. We can't store
1205 * directly into the page header yet, so we update working state.
1213/* Record line pointer to be redirected */
1223 * Do not mark the redirect target here. It needs to be counted
1224 * separately as an unchanged tuple.
1234 * If the root entry had been a normal tuple, we are deleting it, so count
1235 * it in the result. But changing a redirect (even to DEAD state) doesn't
1244/* Record line pointer to be marked dead */
1257 * Deliberately delay unsetting all_visible until later during pruning.
1258 * Removable dead tuples shouldn't preclude freezing the page.
1261 /* Record the dead offset for vacuum */
1265 * If the root entry had been a normal tuple, we are deleting it, so count
1266 * it in the result. But changing a redirect (even to DEAD state) doesn't
1274 * Depending on whether or not the caller set mark_unused_now to true, record that a
1275 * line pointer should be marked LP_DEAD or LP_UNUSED. There are other cases in
1276 * which we will mark line pointers LP_UNUSED, but we will not mark line
1277 * pointers LP_DEAD if mark_unused_now is true.
1284 * If the caller set mark_unused_now to true, we can remove dead tuples
1285 * during pruning instead of marking their line pointers dead. Set this
1286 * tuple's line pointer LP_UNUSED. We hint that this option is less
1295/* Record line pointer to be marked unused */
1307 * If the root entry had been a normal tuple, we are deleting it, so count
1308 * it in the result. But changing a redirect (even to DEAD state) doesn't
1316 * Record an unused line pointer that is left unchanged.
1326 * Record line pointer that is left unchanged. We consider freezing it, and
1327 * update bookkeeping of tuple counts and page visibility.
1337 prstate->
hastup =
true;
/* the page is not empty */
1340 * The criteria for counting a tuple as live in this block need to match
1341 * what analyze.c's acquire_sample_rows() does, otherwise VACUUM and
1342 * ANALYZE may produce wildly different reltuples values, e.g. when there
1343 * are many recently-dead tuples.
1345 * The logic here is a bit simpler than acquire_sample_rows(), as VACUUM
1346 * can't run inside a transaction block, which makes some cases impossible
1347 * (e.g. in-progress insert from the same transaction).
1349 * HEAPTUPLE_DEAD are handled by the other heap_prune_record_*()
1350 * subroutines. They don't count dead items like acquire_sample_rows()
1351 * does, because we assume that all dead items will become LP_UNUSED
1352 * before VACUUM finishes. This difference is only superficial. VACUUM
1353 * effectively agrees with ANALYZE about DEAD items, in the end. VACUUM
1354 * won't remember LP_DEAD items, but only because they're not supposed to
1355 * be left behind when it is done. (Cases where we bypass index vacuuming
1356 * will violate this optimistic assumption, but the overall impact of that
1357 * should be negligible.)
1361 switch (prstate->
htsv[offnum])
1366 * Count it as live. Not only is this natural, but it's also what
1367 * acquire_sample_rows() does.
1372 * Is the tuple definitely visible to all transactions?
1374 * NB: Like with per-tuple hint bits, we can't set the
1375 * PD_ALL_VISIBLE flag if the inserter committed asynchronously.
1376 * See SetHintBits for more info. Check that the tuple is hinted
1377 * xmin-committed because of that.
1390 * The inserter definitely committed. But is it old enough
1391 * that everyone sees it as committed? A FrozenTransactionId
1392 * is seen as committed to everyone. Otherwise, we check if
1393 * there is a snapshot that considers this xid to still be
1394 * running, and if so, we don't consider the page all-visible.
1399 * For now always use prstate->cutoffs for this test, because
1400 * we only update 'all_visible' when freezing is requested. We
1401 * could use GlobalVisTestIsRemovableXid instead, if a
1402 * non-freezing caller wanted to set the VM bit.
1411 /* Track newest xmin on page. */
1423 * This tuple will soon become DEAD. Update the hint field so
1424 * that the page is reconsidered for pruning in future.
1433 * We do not count these rows as live, because we expect the
1434 * inserting transaction to update the counters at commit, and we
1435 * assume that will happen only after we report our results. This
1436 * assumption is a bit shaky, but it is what acquire_sample_rows()
1437 * does, so be consistent.
1442 * If we wanted to optimize for aborts, we might consider marking
1443 * the page prunable when we see INSERT_IN_PROGRESS. But we
1444 * don't. See related decisions about when to mark the page
1445 * prunable in heapam.c.
1452 * This an expected case during concurrent vacuum. Count such
1453 * rows as live. As above, we assume the deleting transaction
1454 * will commit and update the counters after we report.
1460 * This tuple may soon become DEAD. Update the hint field so that
1461 * the page is reconsidered for pruning in future.
1470 * DEAD tuples should've been passed to heap_prune_record_dead()
1471 * or heap_prune_record_unused() instead.
1473 elog(
ERROR,
"unexpected HeapTupleSatisfiesVacuum result %d",
1474 prstate->
htsv[offnum]);
1478 /* Consider freezing any normal tuples which will not be removed */
1481 bool totally_frozen;
1489 /* Save prepared freeze plan for later */
1494 * If any tuple isn't either totally frozen already or eligible to
1495 * become totally frozen (according to its freeze plan), then the page
1496 * definitely cannot be set all-frozen in the visibility map later on.
1498 if (!totally_frozen)
1505 * Record line pointer that was already LP_DEAD and is left unchanged.
1514 * Deliberately don't set hastup for LP_DEAD items. We make the soft
1515 * assumption that any LP_DEAD items encountered here will become
1516 * LP_UNUSED later on, before count_nondeletable_pages is reached. If we
1517 * don't make this assumption then rel truncation will only happen every
1518 * other VACUUM, at most. Besides, VACUUM must treat
1519 * hastup/nonempty_pages as provisional no matter how LP_DEAD items are
1520 * handled (handled here, or handled later on).
1522 * Similarly, don't unset all_visible until later, at the end of
1523 * heap_page_prune_and_freeze(). This will allow us to attempt to freeze
1524 * the page after pruning. As long as we unset it before updating the
1525 * visibility map, this will be correct.
1528 /* Record the dead offset for vacuum */
1533 * Record LP_REDIRECT that is left unchanged.
1539 * A redirect line pointer doesn't count as a live tuple.
1541 * If we leave a redirect line pointer in place, there will be another
1542 * tuple on the page that it points to. We will do the bookkeeping for
1543 * that separately. So we have nothing to do here, except remember that
1544 * we processed this item.
1551 * Perform the actual page changes needed by heap_page_prune_and_freeze().
1553 * If 'lp_truncate_only' is set, we are merely marking LP_DEAD line pointers
1554 * as unused, not redirecting or removing anything else. The
1555 * PageRepairFragmentation() call is skipped in that case.
1557 * If 'lp_truncate_only' is not set, the caller must hold a cleanup lock on
1558 * the buffer. If it is set, an ordinary exclusive lock suffices.
1570 /* Shouldn't be called unless there's something to do */
1571 Assert(nredirected > 0 || ndead > 0 || nunused > 0);
1573 /* If 'lp_truncate_only', we can only remove already-dead line pointers */
1574 Assert(!lp_truncate_only || (nredirected == 0 && ndead == 0));
1576 /* Update all redirected line pointers */
1577 offnum = redirected;
1578 for (
int i = 0;
i < nredirected;
i++)
1585#ifdef USE_ASSERT_CHECKING
1588 * Any existing item that we set as an LP_REDIRECT (any 'from' item)
1589 * must be the first item from a HOT chain. If the item has tuple
1590 * storage then it can't be a heap-only tuple. Otherwise we are just
1591 * maintaining an existing LP_REDIRECT from an existing HOT chain that
1592 * has been pruned at least once before now.
1603 /* We shouldn't need to redundantly set the redirect */
1608 * The item that we're about to set as an LP_REDIRECT (the 'from'
1609 * item) will point to an existing item (the 'to' item) that is
1610 * already a heap-only tuple. There can be at most one LP_REDIRECT
1611 * item per HOT chain.
1613 * We need to keep around an LP_REDIRECT item (after original
1614 * non-heap-only root tuple gets pruned away) so that it's always
1615 * possible for VACUUM to easily figure out what TID to delete from
1616 * indexes when an entire HOT chain becomes dead. A heap-only tuple
1617 * can never become LP_DEAD; an LP_REDIRECT item or a regular heap
1620 * This check may miss problems, e.g. the target of a redirect could
1621 * be marked as unused subsequently. The page_verify_redirects() check
1622 * below will catch such problems.
1633 /* Update all now-dead line pointers */
1635 for (
int i = 0;
i < ndead;
i++)
1640#ifdef USE_ASSERT_CHECKING
1643 * An LP_DEAD line pointer must be left behind when the original item
1644 * (which is dead to everybody) could still be referenced by a TID in
1645 * an index. This should never be necessary with any individual
1646 * heap-only tuple item, though. (It's not clear how much of a problem
1647 * that would be, but there is no reason to allow it.)
1657 /* Whole HOT chain becomes dead */
1665 /* Update all now-unused line pointers */
1667 for (
int i = 0;
i < nunused;
i++)
1672#ifdef USE_ASSERT_CHECKING
1674 if (lp_truncate_only)
1676 /* Setting LP_DEAD to LP_UNUSED in vacuum's second pass */
1682 * When heap_page_prune_and_freeze() was called, mark_unused_now
1683 * may have been passed as true, which allows would-be LP_DEAD
1684 * items to be made LP_UNUSED instead. This is only possible if
1685 * the relation has no indexes. If there are any dead items, then
1686 * mark_unused_now was not true and every item being marked
1687 * LP_UNUSED must refer to a heap-only tuple.
1704 if (lp_truncate_only)
1709 * Finally, repair any fragmentation, and update the page's hint bit
1710 * about whether it has free pointers.
1715 * Now that the page has been modified, assert that redirect items
1716 * still point to valid targets.
1724 * If built with assertions, verify that all LP_REDIRECT items point to a
1727 * One way that bugs related to HOT pruning show is redirect items pointing to
1728 * removed tuples. It's not trivial to reliably check that marking an item
1729 * unused will not orphan a redirect item during heap_prune_chain() /
1730 * heap_page_prune_execute(), so we additionally check the whole page after
1731 * pruning. Without this check such bugs would typically only cause asserts
1732 * later, potentially well after the corruption has been introduced.
1734 * Also check comments in heap_page_prune_execute()'s redirection loop.
1739#ifdef USE_ASSERT_CHECKING
1770 * For all items in this page, find their respective root line pointers.
1771 * If item k is part of a HOT-chain with root at item j, then we set
1772 * root_offsets[k - 1] = j.
1774 * The passed-in root_offsets array must have MaxHeapTuplesPerPage entries.
1775 * Unused entries are filled with InvalidOffsetNumber (zero).
1777 * The function must be called with at least share lock on the buffer, to
1778 * prevent concurrent prune operations.
1780 * Note: The information collected here is valid only as long as the caller
1781 * holds a pin on the buffer. Once pin is released, a tuple might be pruned
1782 * and reused by a completely unrelated tuple.
1801 /* skip unused and dead items */
1810 * Check if this tuple is part of a HOT-chain rooted at some other
1811 * tuple. If so, skip it for now; we'll process it when we find
1818 * This is either a plain tuple or the root of a HOT-chain.
1819 * Remember it in the mapping.
1821 root_offsets[offnum - 1] = offnum;
1823 /* If it's not the start of a HOT-chain, we're done with it */
1827 /* Set up to scan the HOT-chain */
1833 /* Must be a redirect item. We do not set its root_offsets entry */
1835 /* Set up to scan the HOT-chain */
1841 * Now follow the HOT-chain and collect other tuples in the chain.
1843 * Note: Even though this is a nested loop, the complexity of the
1844 * function is O(N) because a tuple in the page should be visited not
1845 * more than twice, once in the outer loop and once in HOT-chain
1850 /* Sanity check (pure paranoia) */
1855 * An offset past the end of page's line pointer array is possible
1856 * when the array was truncated
1858 if (offnum > maxoff)
1863 /* Check for broken chains */
1873 /* Remember the root line pointer for this item */
1874 root_offsets[nextoffnum - 1] = offnum;
1876 /* Advance to next chain member, if any */
1880 /* HOT implies it can't have moved to different partition */
1891 * Compare fields that describe actions required to freeze tuple with caller's
1892 * open plan. If everything matches then the frz tuple plan is equivalent to
1904 /* Caller must call heap_log_freeze_new_plan again for frz */
1909 * Comparator used to deduplicate the freeze plans used in WAL records.
1938 * heap_log_freeze_eq would consider these tuple-wise plans to be equal.
1939 * (So the tuples will share a single canonical freeze plan.)
1941 * We tiebreak on page offset number to keep each freeze plan's page
1942 * offset number array individually sorted. (Unnecessary, but be tidy.)
1954 * Start new plan initialized using tuple-level actions. At least one tuple
1955 * will have steps required to freeze described by caller's plan during REDO.
1964 plan->ntuples = 1;
/* for now */
1968 * Deduplicate tuple-based freeze plans so that each distinct set of
1969 * processing steps is only stored once in the WAL record.
1970 * Called during original execution of freezing (for logged relations).
1972 * Return value is number of plans set in *plans_out for caller. Also writes
1973 * an array of offset numbers into *offsets_out output argument for caller
1974 * (actually there is one array per freeze plan, but that's not of immediate
1975 * concern to our caller).
1984 /* Sort tuple-based freeze plans in the order required to deduplicate */
1987 for (
int i = 0;
i < ntuples;
i++)
1993 /* New canonical freeze plan starting with first tup */
1999 /* tup matches open canonical plan -- include tup in it */
2005 /* Tup doesn't match current plan -- done with it now */
2008 /* New canonical freeze plan starting with this tup */
2014 * Save page offset number in dedicated buffer in passing.
2016 * REDO routine relies on the record's offset numbers array grouping
2017 * offset numbers by freeze plan. The sort order within each grouping
2018 * is ascending offset number order, just to keep things tidy.
2023 Assert(nplans > 0 && nplans <= ntuples);
2029 * Write an XLOG_HEAP2_PRUNE* WAL record
2031 * This is used for several different page maintenance operations:
2033 * - Page pruning, in VACUUM's 1st pass or on access: Some items are
2034 * redirected, some marked dead, and some removed altogether.
2036 * - Freezing: Items are marked as 'frozen'.
2038 * - Vacuum, 2nd pass: Items that are already LP_DEAD are marked as unused.
2040 * They have enough commonalities that we use a single WAL record for them
2043 * If replaying the record requires a cleanup lock, pass cleanup_lock = true.
2044 * Replaying 'redirected' or 'dead' items always requires a cleanup lock, but
2045 * replaying 'unused' items depends on whether they were all previously marked
2048 * Note: This function scribbles on the 'frozen' array.
2050 * Note: This is called in a critical section, so careful what you do here.
2066 /* The following local variables hold data registered in the WAL record: */
2077 * Prepare data for the buffer. The arrays are not actually in the
2078 * buffer, but we pretend that they are. When XLogInsert stores a full
2079 * page image, the arrays can be omitted.
2090 * Prepare deduplicated representation for use in the WAL record. This
2091 * destructively sorts frozen tuples array in-place.
2095 freeze_plans.
nplans = nplans;
2101 if (nredirected > 0)
2105 redirect_items.
ntargets = nredirected;
2136 * Prepare the main xl_heap_prune record. We already set the XLHP_HAS_*
2147 Assert(nredirected == 0 && ndead == 0);
2148 /* also, any items in 'unused' must've been LP_DEAD previously */
2166 elog(
ERROR,
"unrecognized prune reason: %d", (
int) reason);
BlockNumber BufferGetBlockNumber(Buffer buffer)
void MarkBufferDirty(Buffer buffer)
void LockBuffer(Buffer buffer, int mode)
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
bool ConditionalLockBufferForCleanup(Buffer buffer)
#define BUFFER_LOCK_UNLOCK
static Page BufferGetPage(Buffer buffer)
Size PageGetHeapFreeSpace(const PageData *page)
void PageRepairFragmentation(Page page)
void PageTruncateLinePointerArray(Page page)
PageHeaderData * PageHeader
static void PageClearFull(Page page)
static Item PageGetItem(const PageData *page, const ItemIdData *itemId)
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
static void PageSetLSN(Page page, XLogRecPtr lsn)
static bool PageIsFull(const PageData *page)
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
#define PG_USED_FOR_ASSERTS_ONLY
TransactionId MultiXactId
#define MemSet(start, val, len)
Assert(PointerIsAligned(start, uint64))
void HeapTupleHeaderAdvanceConflictHorizon(HeapTupleHeader tuple, TransactionId *snapshotConflictHorizon)
void heap_freeze_prepared_tuples(Buffer buffer, HeapTupleFreeze *tuples, int ntuples)
bool heap_prepare_freeze_tuple(HeapTupleHeader tuple, const struct VacuumCutoffs *cutoffs, HeapPageFreeze *pagefrz, HeapTupleFreeze *frz, bool *totally_frozen)
void heap_pre_freeze_checks(Buffer buffer, HeapTupleFreeze *tuples, int ntuples)
#define HEAP_PAGE_PRUNE_FREEZE
@ HEAPTUPLE_RECENTLY_DEAD
@ HEAPTUPLE_INSERT_IN_PROGRESS
@ HEAPTUPLE_DELETE_IN_PROGRESS
#define HEAP_PAGE_PRUNE_MARK_UNUSED_NOW
HTSV_Result HeapTupleSatisfiesVacuumHorizon(HeapTuple htup, Buffer buffer, TransactionId *dead_after)
#define XLHP_HAS_CONFLICT_HORIZON
#define XLHP_HAS_FREEZE_PLANS
#define XLHP_HAS_NOW_UNUSED_ITEMS
#define XLHP_HAS_REDIRECTIONS
#define XLOG_HEAP2_PRUNE_VACUUM_SCAN
#define XLOG_HEAP2_PRUNE_ON_ACCESS
#define XLHP_CLEANUP_LOCK
#define XLHP_HAS_DEAD_ITEMS
#define XLOG_HEAP2_PRUNE_VACUUM_CLEANUP
#define XLHP_IS_CATALOG_REL
HeapTupleHeaderData * HeapTupleHeader
static bool HeapTupleHeaderIsHeapOnly(const HeapTupleHeaderData *tup)
static TransactionId HeapTupleHeaderGetXmin(const HeapTupleHeaderData *tup)
static bool HeapTupleHeaderIndicatesMovedPartitions(const HeapTupleHeaderData *tup)
static bool HeapTupleHeaderIsHotUpdated(const HeapTupleHeaderData *tup)
static TransactionId HeapTupleHeaderGetUpdateXid(const HeapTupleHeaderData *tup)
#define MaxHeapTuplesPerPage
static bool HeapTupleHeaderXminCommitted(const HeapTupleHeaderData *tup)
#define ItemIdGetLength(itemId)
#define ItemIdSetRedirect(itemId, link)
#define ItemIdIsNormal(itemId)
#define ItemIdGetRedirect(itemId)
#define ItemIdIsDead(itemId)
#define ItemIdSetDead(itemId)
#define ItemIdIsUsed(itemId)
#define ItemIdSetUnused(itemId)
#define ItemIdIsRedirected(itemId)
#define ItemIdHasStorage(itemId)
static void ItemPointerSet(ItemPointerData *pointer, BlockNumber blockNumber, OffsetNumber offNum)
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
#define START_CRIT_SECTION()
#define END_CRIT_SECTION()
#define InvalidMultiXactId
#define InvalidOffsetNumber
#define OffsetNumberNext(offsetNumber)
#define FirstOffsetNumber
#define OffsetNumberPrev(offsetNumber)
void pgstat_update_heap_dead_tuples(Relation rel, int delta)
#define qsort(a, b, c, d)
bool GlobalVisTestIsRemovableXid(GlobalVisState *state, TransactionId xid)
GlobalVisState * GlobalVisTestFor(Relation rel)
static void heap_prune_chain(Page page, BlockNumber blockno, OffsetNumber maxoff, OffsetNumber rootoffnum, PruneState *prstate)
static void heap_prune_record_unchanged_lp_dead(Page page, PruneState *prstate, OffsetNumber offnum)
void heap_get_root_tuples(Page page, OffsetNumber *root_offsets)
void heap_page_prune_opt(Relation relation, Buffer buffer)
void heap_page_prune_and_freeze(Relation relation, Buffer buffer, GlobalVisState *vistest, int options, struct VacuumCutoffs *cutoffs, PruneFreezeResult *presult, PruneReason reason, OffsetNumber *off_loc, TransactionId *new_relfrozen_xid, MultiXactId *new_relmin_mxid)
static HTSV_Result htsv_get_valid_status(int status)
static int heap_log_freeze_plan(HeapTupleFreeze *tuples, int ntuples, xlhp_freeze_plan *plans_out, OffsetNumber *offsets_out)
static void page_verify_redirects(Page page)
static void heap_prune_record_unused(PruneState *prstate, OffsetNumber offnum, bool was_normal)
static void heap_prune_record_redirect(PruneState *prstate, OffsetNumber offnum, OffsetNumber rdoffnum, bool was_normal)
static void heap_prune_record_unchanged_lp_normal(Page page, PruneState *prstate, OffsetNumber offnum)
static int heap_log_freeze_cmp(const void *arg1, const void *arg2)
void log_heap_prune_and_freeze(Relation relation, Buffer buffer, TransactionId conflict_xid, bool cleanup_lock, PruneReason reason, HeapTupleFreeze *frozen, int nfrozen, OffsetNumber *redirected, int nredirected, OffsetNumber *dead, int ndead, OffsetNumber *unused, int nunused)
static void heap_prune_record_dead(PruneState *prstate, OffsetNumber offnum, bool was_normal)
static bool heap_log_freeze_eq(xlhp_freeze_plan *plan, HeapTupleFreeze *frz)
static void heap_prune_record_prunable(PruneState *prstate, TransactionId xid)
static void heap_prune_record_unchanged_lp_unused(Page page, PruneState *prstate, OffsetNumber offnum)
static void heap_log_freeze_new_plan(xlhp_freeze_plan *plan, HeapTupleFreeze *frz)
static HTSV_Result heap_prune_satisfies_vacuum(PruneState *prstate, HeapTuple tup, Buffer buffer)
static void heap_prune_record_dead_or_unused(PruneState *prstate, OffsetNumber offnum, bool was_normal)
void heap_page_prune_execute(Buffer buffer, bool lp_truncate_only, OffsetNumber *redirected, int nredirected, OffsetNumber *nowdead, int ndead, OffsetNumber *nowunused, int nunused)
static void heap_prune_record_unchanged_lp_redirect(PruneState *prstate, OffsetNumber offnum)
#define RelationGetRelid(relation)
#define RelationGetTargetPageFreeSpace(relation, defaultff)
#define RelationIsAccessibleInLogicalDecoding(relation)
#define RelationNeedsWAL(relation)
#define HEAP_DEFAULT_FILLFACTOR
MultiXactId NoFreezePageRelminMxid
TransactionId FreezePageRelfrozenXid
MultiXactId FreezePageRelminMxid
TransactionId NoFreezePageRelfrozenXid
TransactionId vm_conflict_horizon
OffsetNumber deadoffsets[MaxHeapTuplesPerPage]
bool processed[MaxHeapTuplesPerPage+1]
OffsetNumber heaponly_items[MaxHeapTuplesPerPage]
TransactionId new_prune_xid
OffsetNumber nowdead[MaxHeapTuplesPerPage]
OffsetNumber nowunused[MaxHeapTuplesPerPage]
TransactionId visibility_cutoff_xid
struct VacuumCutoffs * cutoffs
HeapTupleFreeze frozen[MaxHeapTuplesPerPage]
OffsetNumber redirected[MaxHeapTuplesPerPage *2]
int8 htsv[MaxHeapTuplesPerPage+1]
TransactionId latest_xid_removed
OffsetNumber root_items[MaxHeapTuplesPerPage]
OffsetNumber * deadoffsets
bool TransactionIdPrecedes(TransactionId id1, TransactionId id2)
bool TransactionIdFollows(TransactionId id1, TransactionId id2)
#define TransactionIdRetreat(dest)
#define InvalidTransactionId
#define TransactionIdEquals(id1, id2)
#define NormalTransactionIdPrecedes(id1, id2)
#define TransactionIdIsValid(xid)
#define TransactionIdIsNormal(xid)
bool RecoveryInProgress(void)
#define XLogHintBitIsNeeded()
XLogRecPtr XLogInsert(RmgrId rmid, uint8 info)
void XLogRegisterBufData(uint8 block_id, const void *data, uint32 len)
bool XLogCheckBufferNeedsBackup(Buffer buffer)
void XLogRegisterData(const void *data, uint32 len)
void XLogRegisterBuffer(uint8 block_id, Buffer buffer, uint8 flags)
void XLogBeginInsert(void)