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