Subject: Eagerly scan all-visible pages to amortize aggressive vacuum

From: Melanie Plageman <[email-masked]>
Date: Fri, 1 Nov 2024 19:35:22 -0400

Hi,

An aggressive vacuum of a relation is triggered when its relfrozenxid
is older than vacuum_freeze_table_age XIDs. Aggressive vacuums require
examining every unfrozen tuple in the relation. Normal vacuums can
skip all-visible pages. So a relation with a large number of
all-visible but not all-frozen pages may suddenly have to vacuum an
order of magnitude more pages than the previous vacuum.

In many cases, these all-visible not all-frozen pages are not part of
the working set and must be read in. All of the pages with newly
frozen tuples have to be written out and all of the WAL associated
with freezing and setting the page all-frozen in the VM must be
emitted. This extra I/O can affect performance of the foreground
workload substantially.

The best solution would be to freeze the pages instead of just setting
them all-visible. But we don't want to do this if the page will be
modified again because freezing costs extra I/O.

Last year, I worked on a vacuum patch to try and predict which pages
should be eagerly frozen [1] by building a distribution of page
modification intervals and estimating the probability that a given
page would stay frozen long enough to merit freezing.

While working on it I encountered a problem. Pages set all-visible but
not all-frozen by vacuum and not modified again do not have a
modification interval. As such, the distribution would not account for
an outstanding debt of old, unfrozen pages.

As I thought about the problem more, I realized that even if we could
find a way to include those pages in our model and then predict and
effectively eagerly freeze pages, there will always be pages we miss
and have to be picked up later by an aggressive vacuum.

While it would be best to freeze these pages the first time they are
vacuumed and set all-visible, the write amplification is already being
incurred. This patch proposes to spread it out across multiple
"semi-aggressive" vacuums.

I believe eager scanning is actually a required step toward more
intelligent eager freezing. It is worth noting that eager scanning
should also allow us to lift the restriction on setting pages
all-visible in the VM during on-access pruning. This could enable
index-only scans in more cases.

The approach I take in the attached patch set is built on suggestions
and feedback from both Robert and Andres as well as my own ideas and
research.

It implements a new "semi-aggressive" vacuum. Semi-aggressive vacuums
eagerly scan some number of all-visible but not all-frozen pages in
hopes of freezing them. All-visible pages that are eagerly scanned and
set all-frozen in the visibility map are considered successful eager
scans and those not frozen are considered failed eager scans.

Because we want to amortize our eager scanning across a few vacuums,
we cap the maximum number of successful eager scans to a percentage of
the total number of all-visible but not all-frozen pages in the table
(currently 20%).

We also want to cap the maximum number of failures. We assume that
different areas or "regions" of the relation are likely to contain
similarly aged data. So, if too many blocks are eagerly scanned and
not frozen in a given region of the table, eager scanning is
temporarily suspended.

Since I refer to vacuums that eagerly scan a set number of pages as
"semi-aggressive vacuums," I’ve begun calling those that scan every
unfrozen tuple "fully aggressive vacuums" and those with no eager
scanning, or with permanently disabled eager scanning, "unaggressive
vacuums."

v1 of this feature is attached. The first eight patches in the set are
preliminary.

I've proposed 0001-0003 in this thread [2] -- they boil down to
counting pages set all-frozen in the VM.

0004-0007 are a bit of refactoring to make the code a better shape for
the eager scanning feature.

0008 is a WIP patch to add a more general description of heap
vacuuming to the top of vacuumlazy.c.

0009 is the actual eager scanning feature.

To demonstrate the results, I ran an append-only workload run for over
3 hours on master and with my patch applied. The patched version of
Postgres amortized the work of freezing the all-visible but not
all-frozen pages nicely. The first aggressive vacuum with the patch
was 44 seconds and on master it was 1201 seconds.

patch
  LOG:  automatic aggressive vacuum of table "history": index scans: 0
  vacuum duration: 44 seconds (msecs: 44661).
    pages: 0 removed, 27425085 remain, 1104095 scanned (4.03% of
total), 709889 eagerly scanned
    frozen: 316544 pages from table (1.15% of total) had 17409920
tuples frozen. 316544 pages set all-frozen in the VM
    I/O timings: read: 1160.599 ms, write: 2461.205 ms. approx time
spent in vacuum delay: 16230 ms.
    buffer usage: 1105630 hits, 1111898 reads, 646229 newly dirtied,
1750426 dirtied.
    WAL usage: 1027099 records, 316566 full page images, 276209780 bytes.

master
  LOG:  automatic aggressive vacuum of table "history": index scans: 0
  vacuum duration: 1201 seconds (msecs: 1201487).
    pages: 0 removed, 27515348 remain, 15800948 scanned (57.43% of
total), 15098257 eagerly scanned
    frozen: 15096384 pages from table (54.87% of total) had 830247896
tuples frozen. 15096384 pages set all-frozen in the VM
    I/O timings: read: 246537.348 ms, write: 73000.498 ms. approx time
spent in vacuum delay: 349166 ms.
    buffer usage: 15798343 hits, 15813524 reads, 15097063 newly
dirtied, 31274333 dirtied.
    WAL usage: 30733564 records, 15097073 full page images, 11789257631 bytes.

This is because, with the patch, the freezing work is being off-loaded
to earlier vacuums.

In the attached chart.png, you can see the vm_page_freezes climbing
steadily with the patch, whereas on master, there are sudden spikes
aligned with the aggressive vacuums. You can also see that the number
of pages that are all-visible but not all-frozen grows steadily on
master until the aggressive vacuum. This is vacuum's "backlog" of
freezing work.

In this benchmark, the TPS is rate-limited, but using pgbench
per-statement reports, I calculated that the P99 latency for this
benchmark is 16 ms on master and 1 ms with the patch. Vacuuming pages
sooner decreases vacuum reads and doing the freezing work spread over
more vacuums improves P99 transaction latency.

Below is the comparative WAL volume, checkpointer and background
writer writes, reads and writes done by all other backend types, time
spent vacuuming in milliseconds, and p99 latency. Notice that overall
vacuum IO time is substantially lower with the patch.

   version     wal  cptr_bgwriter_w   other_rw  vac_io_time  p99_lat
    patch   770 GB          5903264  235073744   513722         1
    master  767 GB          5908523  216887764  1003654        16

(Note that the benchmarks were run on Postgres with a few extra
patches applied to both master and the patch to trigger vacuums more
frequently. I've proposed those here [3].)

I've also run the built-in tpcb-like pgbench workload and confirmed
that it improves the vacuuming behavior on pgbench_history but has
little impact on vacuuming of heavy-update tables like
pgbench_accounts -- depending on how aggressively the eager scanning
is tuned. Which brings me to the TODOs.

I need to do further benchmarking and investigation to determine
optimal failure and success caps -- ones that will work well for all
workloads. Perhaps the failure cap per region should be configurable.

I also need to try other scenarios -- like those in which old data is
deleted -- and determine if the region boundaries should change from
run to run to avoid eager scanning and failing to freeze the same
pages each time.

Also, all my benchmarking so far has been done on compressed
timelines. I tuned Postgres to exhibit the behavior it might normally
exhibit over days or a week in a few hours. As such, I need to start
running long benchmarks to observe the behavior in a more natural
environment.

- Melanie

[1] https://www.postgresql.org/message-id/CAAKRu_b3tpbdRPUPh1Q5h35gXhY%3DspH2ssNsEsJ9sDfw6%3DPEAg%40mail.gmail.com
[2] https://www.postgresql.org/message-id/CAAKRu_aJM%2B0Gwoq_%2B-sozMX8QEax4QeDhMvySxRt2ayteXJNCg%40mail.gmail.com
[3] https://www.postgresql.org/message-id/CAAKRu_aj-P7YyBz_cPNwztz6ohP%2BvWis%3Diz3YcomkB3NpYA--w%40mail.gmail.com
From 67781cc2511bb7d62ccc9461f1787272820abcc4 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <[email-masked]>
Date: Mon, 28 Oct 2024 11:07:50 -0400
Subject: [PATCH v1 4/9] Replace uses of blkno local variable in
 lazy_scan_heap()

Progress reporting and free space range vacuuming expects to be passed
rel_pages outside of the main loop in lazy_scan_heap(). We previously
solved this by setting blkno to rel_pages after vacuuming the last block
of the relation.

Change this to use rel_pages. With that, blkno is used only in the main
loop in lazy_scan_heap(), eliminating the requirement that it be set to
rel_pages after vacuuming the last block. This opens up code
simplification opportunities elsewhere in lazy_scan_heap() helpers.
---
 src/backend/access/heap/vacuumlazy.c | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)

diff --git a/src/backend/access/heap/vacuumlazy.c b/src/backend/access/heap/vacuumlazy.c
index d80231fc727..1d922b5a831 100644
--- a/src/backend/access/heap/vacuumlazy.c
+++ b/src/backend/access/heap/vacuumlazy.c
@@ -1042,7 +1042,8 @@ lazy_scan_heap(LVRelState *vacrel)
 		ReleaseBuffer(vmbuffer);
 
 	/* report that everything is now scanned */
-	pgstat_progress_update_param(PROGRESS_VACUUM_HEAP_BLKS_SCANNED, blkno);
+	pgstat_progress_update_param(PROGRESS_VACUUM_HEAP_BLKS_SCANNED,
+								 rel_pages);
 
 	/* now we can compute the new value for pg_class.reltuples */
 	vacrel->new_live_tuples = vac_estimate_reltuples(vacrel->rel, rel_pages,
@@ -1068,11 +1069,13 @@ lazy_scan_heap(LVRelState *vacrel)
 	 * Vacuum the remainder of the Free Space Map.  We must do this whether or
 	 * not there were indexes, and whether or not we bypassed index vacuuming.
 	 */
-	if (blkno > next_fsm_block_to_vacuum)
-		FreeSpaceMapVacuumRange(vacrel->rel, next_fsm_block_to_vacuum, blkno);
+	if (rel_pages > next_fsm_block_to_vacuum)
+		FreeSpaceMapVacuumRange(vacrel->rel, next_fsm_block_to_vacuum,
+								rel_pages);
 
 	/* report all blocks vacuumed */
-	pgstat_progress_update_param(PROGRESS_VACUUM_HEAP_BLKS_VACUUMED, blkno);
+	pgstat_progress_update_param(PROGRESS_VACUUM_HEAP_BLKS_VACUUMED,
+								 rel_pages);
 
 	/* Do final index cleanup (call each index's amvacuumcleanup routine) */
 	if (vacrel->nindexes > 0 && vacrel->do_index_cleanup)
@@ -1114,7 +1117,6 @@ heap_vac_scan_next_block(LVRelState *vacrel, BlockNumber *blkno,
 			ReleaseBuffer(vacrel->next_unskippable_vmbuffer);
 			vacrel->next_unskippable_vmbuffer = InvalidBuffer;
 		}
-		*blkno = vacrel->rel_pages;
 		return false;
 	}
 
-- 
2.34.1

From c317a272713bb833f7f2761a5be1924f8e1bdb4d Mon Sep 17 00:00:00 2001
From: Melanie Plageman <[email-masked]>
Date: Thu, 31 Oct 2024 18:19:18 -0400
Subject: [PATCH v1 3/9] Count pages set all-visible and all-frozen in VM
 during vacuum

Vacuum already counts and logs pages with newly frozen tuples. Count and
log pages set all-frozen in the VM too. This includes pages that are
empty before or after vacuuming.

While we are at it, count and log the number of pages vacuum set
all-visible. Pages that are all-visible but not all-frozen are debt for
future aggressive vacuums. The newly all-visible and all-frozen counts
give us visiblity into the rate at which this debt is being accrued and
paid down.

ci-os-only:
---
 src/backend/access/heap/vacuumlazy.c | 88 ++++++++++++++++++++++++----
 1 file changed, 76 insertions(+), 12 deletions(-)

diff --git a/src/backend/access/heap/vacuumlazy.c b/src/backend/access/heap/vacuumlazy.c
index a74ba75dde1..d80231fc727 100644
--- a/src/backend/access/heap/vacuumlazy.c
+++ b/src/backend/access/heap/vacuumlazy.c
@@ -189,6 +189,8 @@ typedef struct LVRelState
 	BlockNumber scanned_pages;	/* # pages examined (not skipped via VM) */
 	BlockNumber removed_pages;	/* # pages removed by relation truncation */
 	BlockNumber tuple_freeze_pages; /* # pages with newly frozen tuples */
+	BlockNumber vm_page_freezes;	/* # pages newly set all-frozen in VM */
+	BlockNumber vm_page_visibles;	/* # pages newly set all-visible in the VM */
 	BlockNumber lpdead_item_pages;	/* # pages with LP_DEAD items */
 	BlockNumber missed_dead_pages;	/* # pages with missed dead tuples */
 	BlockNumber nonempty_pages; /* actually, last nonempty page + 1 */
@@ -702,6 +704,9 @@ heap_vacuum_rel(Relation rel, VacuumParams *params,
 							 100.0 * vacrel->tuple_freeze_pages /
 							 orig_rel_pages,
 							 (long long) vacrel->tuples_frozen);
+			appendStringInfo(&buf, _("visibility map: %u pages set all-visible, %u pages set all-frozen.\n"),
+							 vacrel->vm_page_visibles,
+							 vacrel->vm_page_freezes);
 			if (vacrel->do_index_vacuuming)
 			{
 				if (vacrel->nindexes == 0 || vacrel->num_index_scans == 0)
@@ -1357,6 +1362,8 @@ lazy_scan_new_or_empty(LVRelState *vacrel, Buffer buf, BlockNumber blkno,
 		 */
 		if (!PageIsAllVisible(page))
 		{
+			uint8		old_vmbits;
+
 			START_CRIT_SECTION();
 
 			/* mark buffer dirty before writing a WAL record */
@@ -1376,10 +1383,22 @@ lazy_scan_new_or_empty(LVRelState *vacrel, Buffer buf, BlockNumber blkno,
 				log_newpage_buffer(buf, true);
 
 			PageSetAllVisible(page);
-			visibilitymap_set(vacrel->rel, blkno, buf, InvalidXLogRecPtr,
-							  vmbuffer, InvalidTransactionId,
-							  VISIBILITYMAP_ALL_VISIBLE | VISIBILITYMAP_ALL_FROZEN);
+			old_vmbits = visibilitymap_set(vacrel->rel, blkno, buf,
+										   InvalidXLogRecPtr,
+										   vmbuffer, InvalidTransactionId,
+										   VISIBILITYMAP_ALL_VISIBLE |
+										   VISIBILITYMAP_ALL_FROZEN);
 			END_CRIT_SECTION();
+
+			/*
+			 * If the page wasn't already set all-visible and all-frozen in
+			 * the VM, count it as newly set for logging.
+			 */
+			if ((old_vmbits & VISIBILITYMAP_ALL_VISIBLE) == 0)
+				vacrel->vm_page_visibles++;
+
+			if ((old_vmbits & VISIBILITYMAP_ALL_FROZEN) == 0)
+				vacrel->vm_page_freezes++;
 		}
 
 		freespace = PageGetHeapFreeSpace(page);
@@ -1533,6 +1552,7 @@ lazy_scan_prune(LVRelState *vacrel,
 	 */
 	if (!all_visible_according_to_vm && presult.all_visible)
 	{
+		uint8		old_vmbits;
 		uint8		flags = VISIBILITYMAP_ALL_VISIBLE;
 
 		if (presult.all_frozen)
@@ -1556,9 +1576,21 @@ lazy_scan_prune(LVRelState *vacrel,
 		 */
 		PageSetAllVisible(page);
 		MarkBufferDirty(buf);
-		visibilitymap_set(vacrel->rel, blkno, buf, InvalidXLogRecPtr,
-						  vmbuffer, presult.vm_conflict_horizon,
-						  flags);
+		old_vmbits = visibilitymap_set(vacrel->rel, blkno, buf, InvalidXLogRecPtr,
+									   vmbuffer,
+									   presult.vm_conflict_horizon,
+									   flags);
+
+		/*
+		 * If the page wasn't already set all-visible and all-frozen in the
+		 * VM, count it as newly set for logging.
+		 */
+		if ((old_vmbits & VISIBILITYMAP_ALL_VISIBLE) == 0)
+			vacrel->vm_page_visibles++;
+
+		if ((old_vmbits & VISIBILITYMAP_ALL_FROZEN) == 0
+			&& presult.all_frozen)
+			vacrel->vm_page_freezes++;
 	}
 
 	/*
@@ -1608,6 +1640,8 @@ lazy_scan_prune(LVRelState *vacrel,
 	else if (all_visible_according_to_vm && presult.all_visible &&
 			 presult.all_frozen && !VM_ALL_FROZEN(vacrel->rel, blkno, &vmbuffer))
 	{
+		uint8		old_vmbits;
+
 		/*
 		 * Avoid relying on all_visible_according_to_vm as a proxy for the
 		 * page-level PD_ALL_VISIBLE bit being set, since it might have become
@@ -1627,10 +1661,26 @@ lazy_scan_prune(LVRelState *vacrel,
 		 * was logged when the page's tuples were frozen.
 		 */
 		Assert(!TransactionIdIsValid(presult.vm_conflict_horizon));
-		visibilitymap_set(vacrel->rel, blkno, buf, InvalidXLogRecPtr,
-						  vmbuffer, InvalidTransactionId,
-						  VISIBILITYMAP_ALL_VISIBLE |
-						  VISIBILITYMAP_ALL_FROZEN);
+		old_vmbits = visibilitymap_set(vacrel->rel, blkno, buf, InvalidXLogRecPtr,
+									   vmbuffer, InvalidTransactionId,
+									   VISIBILITYMAP_ALL_VISIBLE |
+									   VISIBILITYMAP_ALL_FROZEN);
+
+		/*
+		 * The page was likely already set all-visible in the VM. However,
+		 * there is a small chance that it was modified sometime between
+		 * setting all_visible_according_to_vm and checking the visibility
+		 * during pruning. Check old_vmbits anyway to ensure the value of
+		 * vm_page_visibles is accurate.
+		 */
+		if ((old_vmbits & VISIBILITYMAP_ALL_VISIBLE) == 0)
+			vacrel->vm_page_visibles++;
+
+		/*
+		 * We already checked that the page was not set all-frozen in the VM
+		 * above, so we don't need to test old_vmbits.
+		 */
+		vacrel->vm_page_freezes++;
 	}
 }
 
@@ -2276,6 +2326,7 @@ lazy_vacuum_heap_page(LVRelState *vacrel, BlockNumber blkno, Buffer buffer,
 	if (heap_page_is_all_visible(vacrel, buffer, &visibility_cutoff_xid,
 								 &all_frozen))
 	{
+		uint8		old_vmbits;
 		uint8		flags = VISIBILITYMAP_ALL_VISIBLE;
 
 		if (all_frozen)
@@ -2285,8 +2336,21 @@ lazy_vacuum_heap_page(LVRelState *vacrel, BlockNumber blkno, Buffer buffer,
 		}
 
 		PageSetAllVisible(page);
-		visibilitymap_set(vacrel->rel, blkno, buffer, InvalidXLogRecPtr,
-						  vmbuffer, visibility_cutoff_xid, flags);
+		old_vmbits = visibilitymap_set(vacrel->rel, blkno, buffer,
+									   InvalidXLogRecPtr,
+									   vmbuffer, visibility_cutoff_xid,
+									   flags);
+
+		/*
+		 * If the page wasn't already set all-visible and all-frozen in the
+		 * VM, count it as newly set for logging.
+		 */
+		if ((old_vmbits & VISIBILITYMAP_ALL_VISIBLE) == 0)
+			vacrel->vm_page_visibles++;
+
+		if ((old_vmbits & VISIBILITYMAP_ALL_FROZEN) == 0
+			&& all_frozen)
+			vacrel->vm_page_freezes++;
 	}
 
 	/* Revert to the previous phase information for error traceback */
-- 
2.34.1

From 69b517f34caf39ad814691d6412c68d54e852990 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <[email-masked]>
Date: Mon, 28 Oct 2024 10:53:37 -0400
Subject: [PATCH v1 1/9] Rename LVRelState->frozen_pages

Rename frozen_pages to tuple_freeze_pages in LVRelState, the struct used
for tracking state during vacuuming of a heap relation. frozen_pages
sounds like it includes every all-frozen page. That is a misnomer. It
does not include pages with already frozen tuples. It also includes
pages that are not actually all-frozen.
---
 src/backend/access/heap/vacuumlazy.c | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/src/backend/access/heap/vacuumlazy.c b/src/backend/access/heap/vacuumlazy.c
index 793bd33cb4d..a74ba75dde1 100644
--- a/src/backend/access/heap/vacuumlazy.c
+++ b/src/backend/access/heap/vacuumlazy.c
@@ -188,7 +188,7 @@ typedef struct LVRelState
 	BlockNumber rel_pages;		/* total number of pages */
 	BlockNumber scanned_pages;	/* # pages examined (not skipped via VM) */
 	BlockNumber removed_pages;	/* # pages removed by relation truncation */
-	BlockNumber frozen_pages;	/* # pages with newly frozen tuples */
+	BlockNumber tuple_freeze_pages; /* # pages with newly frozen tuples */
 	BlockNumber lpdead_item_pages;	/* # pages with LP_DEAD items */
 	BlockNumber missed_dead_pages;	/* # pages with missed dead tuples */
 	BlockNumber nonempty_pages; /* actually, last nonempty page + 1 */
@@ -407,7 +407,7 @@ heap_vacuum_rel(Relation rel, VacuumParams *params,
 	/* Initialize page counters explicitly (be tidy) */
 	vacrel->scanned_pages = 0;
 	vacrel->removed_pages = 0;
-	vacrel->frozen_pages = 0;
+	vacrel->tuple_freeze_pages = 0;
 	vacrel->lpdead_item_pages = 0;
 	vacrel->missed_dead_pages = 0;
 	vacrel->nonempty_pages = 0;
@@ -663,7 +663,8 @@ heap_vacuum_rel(Relation rel, VacuumParams *params,
 							 new_rel_pages,
 							 vacrel->scanned_pages,
 							 orig_rel_pages == 0 ? 100.0 :
-							 100.0 * vacrel->scanned_pages / orig_rel_pages);
+							 100.0 * vacrel->scanned_pages /
+							 orig_rel_pages);
 			appendStringInfo(&buf,
 							 _("tuples: %lld removed, %lld remain, %lld are dead but not yet removable\n"),
 							 (long long) vacrel->tuples_deleted,
@@ -696,9 +697,10 @@ heap_vacuum_rel(Relation rel, VacuumParams *params,
 								 vacrel->NewRelminMxid, diff);
 			}
 			appendStringInfo(&buf, _("frozen: %u pages from table (%.2f%% of total) had %lld tuples frozen\n"),
-							 vacrel->frozen_pages,
+							 vacrel->tuple_freeze_pages,
 							 orig_rel_pages == 0 ? 100.0 :
-							 100.0 * vacrel->frozen_pages / orig_rel_pages,
+							 100.0 * vacrel->tuple_freeze_pages /
+							 orig_rel_pages,
 							 (long long) vacrel->tuples_frozen);
 			if (vacrel->do_index_vacuuming)
 			{
@@ -1455,11 +1457,11 @@ lazy_scan_prune(LVRelState *vacrel,
 	if (presult.nfrozen > 0)
 	{
 		/*
-		 * We don't increment the frozen_pages instrumentation counter when
-		 * nfrozen == 0, since it only counts pages with newly frozen tuples
-		 * (don't confuse that with pages newly set all-frozen in VM).
+		 * We don't increment the tuple_freeze_pages instrumentation counter
+		 * when nfrozen == 0, since it only counts pages with newly frozen
+		 * tuples (don't confuse that with pages newly set all-frozen in VM).
 		 */
-		vacrel->frozen_pages++;
+		vacrel->tuple_freeze_pages++;
 	}
 
 	/*
-- 
2.34.1

From ee769e8bdba93532f7f9686c4f17fda0279bd8e5 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <[email-masked]>
Date: Mon, 28 Oct 2024 11:02:56 -0400
Subject: [PATCH v1 2/9] Make visibilitymap_set() return previous state of
 vmbits

It can be useful to know the state of a relation's VM bits before
visibilitymap_set(). Because visibilitymap_set() examines the bits
anyway to determine whether or not to set them, returning them is cheap.
This commit does not use the new return value.
---
 src/backend/access/heap/visibilitymap.c | 9 ++++++---
 src/include/access/visibilitymap.h      | 8 +++++---
 2 files changed, 11 insertions(+), 6 deletions(-)

diff --git a/src/backend/access/heap/visibilitymap.c b/src/backend/access/heap/visibilitymap.c
index 8b24e7bc33c..ab616a937d3 100644
--- a/src/backend/access/heap/visibilitymap.c
+++ b/src/backend/access/heap/visibilitymap.c
@@ -238,9 +238,9 @@ visibilitymap_pin_ok(BlockNumber heapBlk, Buffer vmbuf)
  *
  * You must pass a buffer containing the correct map page to this function.
  * Call visibilitymap_pin first to pin the right one. This function doesn't do
- * any I/O.
+ * any I/O. Returns the visibility map status before setting the bits.
  */
-void
+uint8
 visibilitymap_set(Relation rel, BlockNumber heapBlk, Buffer heapBuf,
 				  XLogRecPtr recptr, Buffer vmBuf, TransactionId cutoff_xid,
 				  uint8 flags)
@@ -250,6 +250,7 @@ visibilitymap_set(Relation rel, BlockNumber heapBlk, Buffer heapBuf,
 	uint8		mapOffset = HEAPBLK_TO_OFFSET(heapBlk);
 	Page		page;
 	uint8	   *map;
+	uint8		status;
 
 #ifdef TRACE_VISIBILITYMAP
 	elog(DEBUG1, "vm_set %s %d", RelationGetRelationName(rel), heapBlk);
@@ -274,7 +275,8 @@ visibilitymap_set(Relation rel, BlockNumber heapBlk, Buffer heapBuf,
 	map = (uint8 *) PageGetContents(page);
 	LockBuffer(vmBuf, BUFFER_LOCK_EXCLUSIVE);
 
-	if (flags != (map[mapByte] >> mapOffset & VISIBILITYMAP_VALID_BITS))
+	status = ((map[mapByte] >> mapOffset) & VISIBILITYMAP_VALID_BITS);
+	if (flags != status)
 	{
 		START_CRIT_SECTION();
 
@@ -311,6 +313,7 @@ visibilitymap_set(Relation rel, BlockNumber heapBlk, Buffer heapBuf,
 	}
 
 	LockBuffer(vmBuf, BUFFER_LOCK_UNLOCK);
+	return status;
 }
 
 /*
diff --git a/src/include/access/visibilitymap.h b/src/include/access/visibilitymap.h
index 1a4d467e6f0..0cdfa817071 100644
--- a/src/include/access/visibilitymap.h
+++ b/src/include/access/visibilitymap.h
@@ -31,9 +31,11 @@ extern bool visibilitymap_clear(Relation rel, BlockNumber heapBlk,
 extern void visibilitymap_pin(Relation rel, BlockNumber heapBlk,
 							  Buffer *vmbuf);
 extern bool visibilitymap_pin_ok(BlockNumber heapBlk, Buffer vmbuf);
-extern void visibilitymap_set(Relation rel, BlockNumber heapBlk, Buffer heapBuf,
-							  XLogRecPtr recptr, Buffer vmBuf, TransactionId cutoff_xid,
-							  uint8 flags);
+extern uint8 visibilitymap_set(Relation rel, BlockNumber heapBlk,
+							   Buffer heapBuf,
+							   XLogRecPtr recptr, Buffer vmBuf,
+							   TransactionId cutoff_xid,
+							   uint8 flags);
 extern uint8 visibilitymap_get_status(Relation rel, BlockNumber heapBlk, Buffer *vmbuf);
 extern void visibilitymap_count(Relation rel, BlockNumber *all_visible, BlockNumber *all_frozen);
 extern BlockNumber visibilitymap_prepare_truncate(Relation rel,
-- 
2.34.1

From 67b5565ad57d3b196695f85811dde2044ba79f3e Mon Sep 17 00:00:00 2001
From: Melanie Plageman <[email-masked]>
Date: Mon, 28 Oct 2024 11:14:24 -0400
Subject: [PATCH v1 5/9] Move vacuum VM buffer release

The VM buffer for the next unskippable block can be released after the
main loop in lazy_scan_heap(). Doing so de-clutters
heap_vac_scan_next_block() and opens up more refactoring options.
---
 src/backend/access/heap/vacuumlazy.c | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)

diff --git a/src/backend/access/heap/vacuumlazy.c b/src/backend/access/heap/vacuumlazy.c
index 1d922b5a831..4b1eadea1f2 100644
--- a/src/backend/access/heap/vacuumlazy.c
+++ b/src/backend/access/heap/vacuumlazy.c
@@ -1038,6 +1038,14 @@ lazy_scan_heap(LVRelState *vacrel)
 	}
 
 	vacrel->blkno = InvalidBlockNumber;
+
+	/* Release VM buffers */
+	if (BufferIsValid(vacrel->next_unskippable_vmbuffer))
+	{
+		ReleaseBuffer(vacrel->next_unskippable_vmbuffer);
+		vacrel->next_unskippable_vmbuffer = InvalidBuffer;
+	}
+
 	if (BufferIsValid(vmbuffer))
 		ReleaseBuffer(vmbuffer);
 
@@ -1111,14 +1119,7 @@ heap_vac_scan_next_block(LVRelState *vacrel, BlockNumber *blkno,
 
 	/* Have we reached the end of the relation? */
 	if (next_block >= vacrel->rel_pages)
-	{
-		if (BufferIsValid(vacrel->next_unskippable_vmbuffer))
-		{
-			ReleaseBuffer(vacrel->next_unskippable_vmbuffer);
-			vacrel->next_unskippable_vmbuffer = InvalidBuffer;
-		}
 		return false;
-	}
 
 	/*
 	 * We must be in one of the three following states:
-- 
2.34.1

From 8485dc400b3d4e9f895170af4f5fb1bb959b8495 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <[email-masked]>
Date: Mon, 28 Oct 2024 11:36:58 -0400
Subject: [PATCH v1 6/9] Remove superfluous next_block local variable in vacuum
 code

Reduce the number of block related variables in lazy_scan_heap() and its
helpers by removing the next_block local variable from
heap_vac_scan_next_block().
---
 src/backend/access/heap/vacuumlazy.c | 21 ++++++++++-----------
 1 file changed, 10 insertions(+), 11 deletions(-)

diff --git a/src/backend/access/heap/vacuumlazy.c b/src/backend/access/heap/vacuumlazy.c
index 4b1eadea1f2..52c9d49f2b1 100644
--- a/src/backend/access/heap/vacuumlazy.c
+++ b/src/backend/access/heap/vacuumlazy.c
@@ -1112,19 +1112,17 @@ static bool
 heap_vac_scan_next_block(LVRelState *vacrel, BlockNumber *blkno,
 						 bool *all_visible_according_to_vm)
 {
-	BlockNumber next_block;
-
 	/* relies on InvalidBlockNumber + 1 overflowing to 0 on first call */
-	next_block = vacrel->current_block + 1;
+	vacrel->current_block++;
 
 	/* Have we reached the end of the relation? */
-	if (next_block >= vacrel->rel_pages)
+	if (vacrel->current_block >= vacrel->rel_pages)
 		return false;
 
 	/*
 	 * We must be in one of the three following states:
 	 */
-	if (next_block > vacrel->next_unskippable_block ||
+	if (vacrel->current_block > vacrel->next_unskippable_block ||
 		vacrel->next_unskippable_block == InvalidBlockNumber)
 	{
 		/*
@@ -1151,23 +1149,24 @@ heap_vac_scan_next_block(LVRelState *vacrel, BlockNumber *blkno,
 		 * pages then skipping makes updating relfrozenxid unsafe, which is a
 		 * real downside.
 		 */
-		if (vacrel->next_unskippable_block - next_block >= SKIP_PAGES_THRESHOLD)
+		if (vacrel->next_unskippable_block - vacrel->current_block >=
+			SKIP_PAGES_THRESHOLD)
 		{
-			next_block = vacrel->next_unskippable_block;
+			vacrel->current_block = vacrel->next_unskippable_block;
 			if (skipsallvis)
 				vacrel->skippedallvis = true;
 		}
 	}
 
 	/* Now we must be in one of the two remaining states: */
-	if (next_block < vacrel->next_unskippable_block)
+	if (vacrel->current_block < vacrel->next_unskippable_block)
 	{
 		/*
 		 * 2. We are processing a range of blocks that we could have skipped
 		 * but chose not to.  We know that they are all-visible in the VM,
 		 * otherwise they would've been unskippable.
 		 */
-		*blkno = vacrel->current_block = next_block;
+		*blkno = vacrel->current_block;
 		*all_visible_according_to_vm = true;
 		return true;
 	}
@@ -1177,9 +1176,9 @@ heap_vac_scan_next_block(LVRelState *vacrel, BlockNumber *blkno,
 		 * 3. We reached the next unskippable block.  Process it.  On next
 		 * iteration, we will be back in state 1.
 		 */
-		Assert(next_block == vacrel->next_unskippable_block);
+		Assert(vacrel->current_block == vacrel->next_unskippable_block);
 
-		*blkno = vacrel->current_block = next_block;
+		*blkno = vacrel->current_block;
 		*all_visible_according_to_vm = vacrel->next_unskippable_allvis;
 		return true;
 	}
-- 
2.34.1

From 78ad9e022b95e024ff5bfa96af78e9e44730c970 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <[email-masked]>
Date: Mon, 28 Oct 2024 11:42:10 -0400
Subject: [PATCH v1 7/9] Make heap_vac_scan_next_block() return BlockNumber

After removing the requirement for blkno to be set to rel_pages outside
of lazy_scan_heap(), heap_vac_scan_next_block() can return the next
block number for vacuum to scan. This makes the interface more
straightforward as well as paving the way for heap_vac_scan_next_block()
to be used by the read stream API as a callback to implement streaming
vacuum.
---
 src/backend/access/heap/vacuumlazy.c | 27 +++++++++++++--------------
 1 file changed, 13 insertions(+), 14 deletions(-)

diff --git a/src/backend/access/heap/vacuumlazy.c b/src/backend/access/heap/vacuumlazy.c
index 52c9d49f2b1..7ce69953ba0 100644
--- a/src/backend/access/heap/vacuumlazy.c
+++ b/src/backend/access/heap/vacuumlazy.c
@@ -229,8 +229,8 @@ typedef struct LVSavedErrInfo
 
 /* non-export function prototypes */
 static void lazy_scan_heap(LVRelState *vacrel);
-static bool heap_vac_scan_next_block(LVRelState *vacrel, BlockNumber *blkno,
-									 bool *all_visible_according_to_vm);
+static BlockNumber heap_vac_scan_next_block(LVRelState *vacrel,
+											bool *all_visible_according_to_vm);
 static void find_next_unskippable_block(LVRelState *vacrel, bool *skipsallvis);
 static bool lazy_scan_new_or_empty(LVRelState *vacrel, Buffer buf,
 								   BlockNumber blkno, Page page,
@@ -857,7 +857,8 @@ lazy_scan_heap(LVRelState *vacrel)
 	vacrel->next_unskippable_allvis = false;
 	vacrel->next_unskippable_vmbuffer = InvalidBuffer;
 
-	while (heap_vac_scan_next_block(vacrel, &blkno, &all_visible_according_to_vm))
+	while (BlockNumberIsValid(blkno = heap_vac_scan_next_block(vacrel,
+															   &all_visible_according_to_vm)))
 	{
 		Buffer		buf;
 		Page		page;
@@ -1096,11 +1097,11 @@ lazy_scan_heap(LVRelState *vacrel)
  * lazy_scan_heap() calls here every time it needs to get the next block to
  * prune and vacuum.  The function uses the visibility map, vacuum options,
  * and various thresholds to skip blocks which do not need to be processed and
- * sets blkno to the next block to process.
+ * returns the next block to process.
  *
- * The block number and visibility status of the next block to process are set
- * in *blkno and *all_visible_according_to_vm.  The return value is false if
- * there are no further blocks to process.
+ * The block number and visibility status of the next block to process are
+ * returned and set in *all_visible_according_to_vm.  The return value is
+ * InvalidBlockNumber if there are no further blocks to process.
  *
  * vacrel is an in/out parameter here.  Vacuum options and information about
  * the relation are read.  vacrel->skippedallvis is set if we skip a block
@@ -1108,8 +1109,8 @@ lazy_scan_heap(LVRelState *vacrel)
  * relfrozenxid in that case.  vacrel also holds information about the next
  * unskippable block, as bookkeeping for this function.
  */
-static bool
-heap_vac_scan_next_block(LVRelState *vacrel, BlockNumber *blkno,
+static BlockNumber
+heap_vac_scan_next_block(LVRelState *vacrel,
 						 bool *all_visible_according_to_vm)
 {
 	/* relies on InvalidBlockNumber + 1 overflowing to 0 on first call */
@@ -1117,7 +1118,7 @@ heap_vac_scan_next_block(LVRelState *vacrel, BlockNumber *blkno,
 
 	/* Have we reached the end of the relation? */
 	if (vacrel->current_block >= vacrel->rel_pages)
-		return false;
+		return InvalidBlockNumber;
 
 	/*
 	 * We must be in one of the three following states:
@@ -1166,9 +1167,8 @@ heap_vac_scan_next_block(LVRelState *vacrel, BlockNumber *blkno,
 		 * but chose not to.  We know that they are all-visible in the VM,
 		 * otherwise they would've been unskippable.
 		 */
-		*blkno = vacrel->current_block;
 		*all_visible_according_to_vm = true;
-		return true;
+		return vacrel->current_block;
 	}
 	else
 	{
@@ -1178,9 +1178,8 @@ heap_vac_scan_next_block(LVRelState *vacrel, BlockNumber *blkno,
 		 */
 		Assert(vacrel->current_block == vacrel->next_unskippable_block);
 
-		*blkno = vacrel->current_block;
 		*all_visible_according_to_vm = vacrel->next_unskippable_allvis;
-		return true;
+		return vacrel->current_block;
 	}
 }
 
-- 
2.34.1

From 818d1c3b068c6705611256cfc3eb1f10bdc0b684 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <[email-masked]>
Date: Fri, 1 Nov 2024 18:25:05 -0400
Subject: [PATCH v1 8/9] WIP: Add more general summary to vacuumlazy.c

Currently the summary at the top of vacuumlazy.c provides some specific
details related to the new dead TID storage in 17. I plan to add a
summary and maybe some sub-sections to contextualize it.
---
 src/backend/access/heap/vacuumlazy.c | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/src/backend/access/heap/vacuumlazy.c b/src/backend/access/heap/vacuumlazy.c
index 7ce69953ba0..15a04c6b10b 100644
--- a/src/backend/access/heap/vacuumlazy.c
+++ b/src/backend/access/heap/vacuumlazy.c
@@ -3,6 +3,17 @@
  * vacuumlazy.c
  *	  Concurrent ("lazy") vacuuming.
  *
+ * Heap relations are vacuumed in three main phases. In the first phase,
+ * vacuum scans relation pages, pruning and freezing tuples and saving dead
+ * tuples' TIDs in a TID store. If that TID store fills up or vacuum finishes
+ * scanning the relation, it progresses to the second phase: index vacuuming.
+ * After index vacuuming is complete, vacuum scans the blocks of the relation
+ * indicated by the TIDs in the TID store and reaps the dead tuples, freeing
+ * that space for future tuples. Finally, vacuum may truncate the relation if
+ * it has emptied pages at the end. XXX: this summary needs work.
+ *
+ * Dead TID Storage:
+ *
  * The major space usage for vacuuming is storage for the dead tuple IDs that
  * are to be removed from indexes.  We want to ensure we can vacuum even the
  * very largest relations with finite memory space usage.  To do that, we set
-- 
2.34.1

From f21f0bab1dbe675be4b4dddcb2eea486d8a69d36 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <[email-masked]>
Date: Mon, 28 Oct 2024 12:15:08 -0400
Subject: [PATCH v1 9/9] Eagerly scan all-visible pages to amortize aggressive
 vacuum

Introduce semi-aggressive vacuums, which scan some of the all-visible
but not all-frozen pages in the relation to amortize the cost of an
aggressive vacuum.

Because the goal is to freeze these all-visible pages, all-visible pages
that are eagerly scanned and set all-frozen in the visibility map are
considered successful eager scans and those not frozen are considered
failed eager scans.

If too many eager scans fail in a row, eager scanning is temporarily
suspended until a later portion of the relation. Because the goal is to
amortize aggressive vacuums, we cap the number of successes as well.
Once we reach the maximum number of blocks successfully eager scanned
and frozen, the semi-aggressive vacuum is downgraded to an unaggressive
vacuum.
---
 src/backend/access/heap/vacuumlazy.c | 327 +++++++++++++++++++++++----
 src/backend/commands/vacuum.c        |  20 +-
 src/include/commands/vacuum.h        |  27 ++-
 src/tools/pgindent/typedefs.list     |   1 +
 4 files changed, 326 insertions(+), 49 deletions(-)

diff --git a/src/backend/access/heap/vacuumlazy.c b/src/backend/access/heap/vacuumlazy.c
index 15a04c6b10b..adabb5ff5f1 100644
--- a/src/backend/access/heap/vacuumlazy.c
+++ b/src/backend/access/heap/vacuumlazy.c
@@ -12,6 +12,40 @@
  * that space for future tuples. Finally, vacuum may truncate the relation if
  * it has emptied pages at the end. XXX: this summary needs work.
  *
+ * Relation Scanning:
+ *
+ * Vacuum scans the heap relation, starting at the beginning and progressing
+ * to the end, skipping pages as permitted by their visibility status, vacuum
+ * options, and the aggressiveness level of the vacuum.
+ *
+ * When page skipping is enabled, unaggressive vacuums may skip scanning pages
+ * that are marked all-visible in the visibility map. We may choose not to
+ * skip pages if the range of skippable pages is below SKIP_PAGES_THRESHOLD.
+ *
+ * Semi-aggressive vacuums will scan skippable pages in an effort to freeze
+ * them and decrease the backlog of all-visible but not all-frozen pages that
+ * have to be processed to advance relfrozenxid and avoid transaction ID
+ * wraparound.
+ *
+ * We count it as a success when we are able to set an eagerly scanned page
+ * all-frozen in the VM and a failure when we are not able to set the page
+ * all-frozen.
+ *
+ * Because we want to amortize the overhead of freezing pages over multiple
+ * vacuums, we cap the number of successful eager scans to
+ * EAGER_SCAN_SUCCESS_RATE of the number of all-visible but not all-frozen
+ * pages at the beginning of the vacuum.
+ *
+ * On the assumption that different regions of the table are likely to contain
+ * similarly aged data, we use a localized failure cap instead of a global cap
+ * for the whole relation. The failure count is reset on each region of the
+ * table, comprised of RELSEG_SIZE blocks (or 1/4 of the table size for a
+ * small table). In each region, we tolerate MAX_SUCCESSIVE_EAGER_SCAN_FAILS
+ * before suspending eager scanning until the end of the region.
+ *
+ * Fully aggressive vacuums must examine every unfrozen tuple and are thus not
+ * subject to failure or success caps when eagerly scanning all-visible pages.
+ *
  * Dead TID Storage:
  *
  * The major space usage for vacuuming is storage for the dead tuple IDs that
@@ -142,6 +176,27 @@ typedef enum
 	VACUUM_ERRCB_PHASE_TRUNCATE,
 } VacErrPhase;
 
+/*
+ * Semi-aggressive vacuums eagerly scan some all-visible but not all-frozen
+ * pages. Since our goal is to freeze these pages, an eager scan that fails to
+ * set the page all-frozen in the VM is considered to have "failed".
+ *
+ * On the assumption that different regions of the table tend to have
+ * similarly aged data, once we fail to freeze MAX_SUCCESSIVE_EAGER_SCAN_FAILS
+ * blocks, we suspend eager scanning until vacuum has progressed to another
+ * region of the table with potentially older data.
+ */
+#define MAX_SUCCESSIVE_EAGER_SCAN_FAILS 1024
+
+/*
+ * An eager scan of a page that is set all-frozen in the VM is considered
+ * "successful". To spread out eager scanning across multiple semi-aggressive
+ * vacuums, we limit the number of successful eager scans (as well as the
+ * number of failures). The maximum number of successful eager scans is
+ * calculated as a ratio of the all-visible but not all-frozen pages at the
+ * beginning of the vacuum.
+ */
+#define EAGER_SCAN_SUCCESS_RATE 0.2
 typedef struct LVRelState
 {
 	/* Target heap relation and its indexes */
@@ -153,8 +208,22 @@ typedef struct LVRelState
 	BufferAccessStrategy bstrategy;
 	ParallelVacuumState *pvs;
 
-	/* Aggressive VACUUM? (must set relfrozenxid >= FreezeLimit) */
-	bool		aggressive;
+	/*
+	 * Whether or not this is an aggressive, semi-aggressive, or unaggressive
+	 * VACUUM. A fully aggressive vacuum must set relfrozenxid >= FreezeLimit
+	 * and therefore must scan every unfrozen tuple. A semi-aggressive vacuum
+	 * will scan a certain number of all-visible pages until it is downgraded
+	 * to an unaggressive vacuum.
+	 */
+	VacAggressive aggressive;
+
+	/*
+	 * A semi-aggressive vacuum that has failed to freeze too many eagerly
+	 * scanned blocks in a row suspends eager scanning. unaggressive_to is the
+	 * block number of the first block eligible for resumed eager scanning.
+	 */
+	BlockNumber unaggressive_to;
+
 	/* Use visibility map to skip? (disabled by DISABLE_PAGE_SKIPPING) */
 	bool		skipwithvm;
 	/* Consider index vacuuming bypass optimization? */
@@ -227,6 +296,26 @@ typedef struct LVRelState
 	BlockNumber next_unskippable_block; /* next unskippable block */
 	bool		next_unskippable_allvis;	/* its visibility status */
 	Buffer		next_unskippable_vmbuffer;	/* buffer containing its VM bit */
+
+	/*
+	 * Count of skippable blocks eagerly scanned as part of a semi-aggressive
+	 * vacuum (for logging only).
+	 */
+	BlockNumber eager_scanned;
+
+	/*
+	 * The number of eagerly scanned blocks a semi-aggressive vacuum failed to
+	 * freeze (due to age) in the current eager scan region. It is reset each
+	 * time we hit MAX_SUCCESSIVE_EAGER_SCAN_FAILS.
+	 */
+	BlockNumber eager_scanned_failed_frozen;
+
+	/*
+	 * The remaining number of blocks a semi-aggressive vacuum will consider
+	 * eager scanning. This is initialized to EAGER_SCAN_SUCCESS_RATE of the
+	 * total number of all-visible but not all-frozen pages.
+	 */
+	BlockNumber remaining_eager_scan_successes;
 } LVRelState;
 
 /* Struct for saving and restoring vacuum error information. */
@@ -241,8 +330,13 @@ typedef struct LVSavedErrInfo
 /* non-export function prototypes */
 static void lazy_scan_heap(LVRelState *vacrel);
 static BlockNumber heap_vac_scan_next_block(LVRelState *vacrel,
-											bool *all_visible_according_to_vm);
-static void find_next_unskippable_block(LVRelState *vacrel, bool *skipsallvis);
+											bool *all_visible_according_to_vm,
+											bool *was_eager_scanned);
+static void find_next_unskippable_block(
+										LVRelState *vacrel,
+										bool consider_eager_scan,
+										bool *was_eager_scanned,
+										bool *skipsallvis);
 static bool lazy_scan_new_or_empty(LVRelState *vacrel, Buffer buf,
 								   BlockNumber blkno, Page page,
 								   bool sharelock, Buffer vmbuffer);
@@ -314,7 +408,9 @@ heap_vacuum_rel(Relation rel, VacuumParams *params,
 				minmulti_updated;
 	BlockNumber orig_rel_pages,
 				new_rel_pages,
-				new_rel_allvisible;
+				orig_rel_allvisible,
+				new_rel_allvisible,
+				orig_rel_allfrozen;
 	PGRUsage	ru0;
 	TimestampTz starttime = 0;
 	PgStat_Counter startreadtime = 0,
@@ -458,6 +554,8 @@ heap_vacuum_rel(Relation rel, VacuumParams *params,
 	 * to increase the number of dead tuples it can prune away.)
 	 */
 	vacrel->aggressive = vacuum_get_cutoffs(rel, params, &vacrel->cutoffs);
+	vacrel->unaggressive_to = 0;
+
 	vacrel->rel_pages = orig_rel_pages = RelationGetNumberOfBlocks(rel);
 	vacrel->vistest = GlobalVisTestFor(rel);
 	/* Initialize state used to track oldest extant XID/MXID */
@@ -471,24 +569,49 @@ heap_vacuum_rel(Relation rel, VacuumParams *params,
 		 * Force aggressive mode, and disable skipping blocks using the
 		 * visibility map (even those set all-frozen)
 		 */
-		vacrel->aggressive = true;
+		vacrel->aggressive = VAC_AGGRESSIVE;
 		skipwithvm = false;
 	}
 
 	vacrel->skipwithvm = skipwithvm;
+	vacrel->eager_scanned = 0;
+	vacrel->eager_scanned_failed_frozen = 0;
+
+	/*
+	 * Even if we successfully freeze them, we want to cap the number of
+	 * eagerly scanned blocks so that we spread out the overhead across
+	 * multiple vacuums. remaining_eager_scan_successes is only used by
+	 * semi-aggressive vacuums.
+	 */
+	visibilitymap_count(rel, &orig_rel_allvisible, &orig_rel_allfrozen);
+	vacrel->remaining_eager_scan_successes =
+		(BlockNumber) (EAGER_SCAN_SUCCESS_RATE * (orig_rel_allvisible - orig_rel_allfrozen));
 
 	if (verbose)
 	{
-		if (vacrel->aggressive)
-			ereport(INFO,
-					(errmsg("aggressively vacuuming \"%s.%s.%s\"",
-							vacrel->dbname, vacrel->relnamespace,
-							vacrel->relname)));
-		else
-			ereport(INFO,
-					(errmsg("vacuuming \"%s.%s.%s\"",
-							vacrel->dbname, vacrel->relnamespace,
-							vacrel->relname)));
+		switch (vacrel->aggressive)
+		{
+			case VAC_UNAGGRESSIVE:
+				ereport(INFO,
+						(errmsg("vacuuming \"%s.%s.%s\"",
+								vacrel->dbname, vacrel->relnamespace,
+								vacrel->relname)));
+				break;
+
+			case VAC_AGGRESSIVE:
+				ereport(INFO,
+						(errmsg("aggressively vacuuming \"%s.%s.%s\"",
+								vacrel->dbname, vacrel->relnamespace,
+								vacrel->relname)));
+				break;
+
+			case VAC_SEMIAGGRESSIVE:
+				ereport(INFO,
+						(errmsg("semiaggressively vacuuming \"%s.%s.%s\"",
+								vacrel->dbname, vacrel->relnamespace,
+								vacrel->relname)));
+				break;
+		}
 	}
 
 	/*
@@ -545,11 +668,13 @@ heap_vacuum_rel(Relation rel, VacuumParams *params,
 	 * Non-aggressive VACUUMs may advance them by any amount, or not at all.
 	 */
 	Assert(vacrel->NewRelfrozenXid == vacrel->cutoffs.OldestXmin ||
-		   TransactionIdPrecedesOrEquals(vacrel->aggressive ? vacrel->cutoffs.FreezeLimit :
+		   TransactionIdPrecedesOrEquals(vacrel->aggressive == VAC_AGGRESSIVE ?
+										 vacrel->cutoffs.FreezeLimit :
 										 vacrel->cutoffs.relfrozenxid,
 										 vacrel->NewRelfrozenXid));
 	Assert(vacrel->NewRelminMxid == vacrel->cutoffs.OldestMxact ||
-		   MultiXactIdPrecedesOrEquals(vacrel->aggressive ? vacrel->cutoffs.MultiXactCutoff :
+		   MultiXactIdPrecedesOrEquals(vacrel->aggressive == VAC_AGGRESSIVE ?
+									   vacrel->cutoffs.MultiXactCutoff :
 									   vacrel->cutoffs.relminmxid,
 									   vacrel->NewRelminMxid));
 	if (vacrel->skippedallvis)
@@ -559,7 +684,7 @@ heap_vacuum_rel(Relation rel, VacuumParams *params,
 		 * chose to skip an all-visible page range.  The state that tracks new
 		 * values will have missed unfrozen XIDs from the pages we skipped.
 		 */
-		Assert(!vacrel->aggressive);
+		Assert(vacrel->aggressive != VAC_AGGRESSIVE);
 		vacrel->NewRelfrozenXid = InvalidTransactionId;
 		vacrel->NewRelminMxid = InvalidMultiXactId;
 	}
@@ -654,14 +779,14 @@ heap_vacuum_rel(Relation rel, VacuumParams *params,
 				 * implies aggressive.  Produce distinct output for the corner
 				 * case all the same, just in case.
 				 */
-				if (vacrel->aggressive)
+				if (vacrel->aggressive == VAC_AGGRESSIVE)
 					msgfmt = _("automatic aggressive vacuum to prevent wraparound of table \"%s.%s.%s\": index scans: %d\n");
 				else
 					msgfmt = _("automatic vacuum to prevent wraparound of table \"%s.%s.%s\": index scans: %d\n");
 			}
 			else
 			{
-				if (vacrel->aggressive)
+				if (vacrel->aggressive == VAC_AGGRESSIVE)
 					msgfmt = _("automatic aggressive vacuum of table \"%s.%s.%s\": index scans: %d\n");
 				else
 					msgfmt = _("automatic vacuum of table \"%s.%s.%s\": index scans: %d\n");
@@ -802,6 +927,16 @@ heap_vacuum_rel(Relation rel, VacuumParams *params,
 	}
 }
 
+/*
+ * Helper to decrement a block number to 0 without wrapping around.
+ */
+static void
+decrement_blkno(BlockNumber *block)
+{
+	if ((*block) > 0)
+		(*block)--;
+}
+
 /*
  *	lazy_scan_heap() -- workhorse function for VACUUM
  *
@@ -844,7 +979,8 @@ lazy_scan_heap(LVRelState *vacrel)
 	BlockNumber rel_pages = vacrel->rel_pages,
 				blkno,
 				next_fsm_block_to_vacuum = 0;
-	bool		all_visible_according_to_vm;
+	bool		all_visible_according_to_vm,
+				was_eager_scanned = false;
 
 	TidStore   *dead_items = vacrel->dead_items;
 	VacDeadItemsInfo *dead_items_info = vacrel->dead_items_info;
@@ -855,6 +991,7 @@ lazy_scan_heap(LVRelState *vacrel)
 		PROGRESS_VACUUM_MAX_DEAD_TUPLE_BYTES
 	};
 	int64		initprog_val[3];
+	BlockNumber page_freezes = 0;
 
 	/* Report that we're scanning the heap, advertising total # of blocks */
 	initprog_val[0] = PROGRESS_VACUUM_PHASE_SCAN_HEAP;
@@ -869,7 +1006,8 @@ lazy_scan_heap(LVRelState *vacrel)
 	vacrel->next_unskippable_vmbuffer = InvalidBuffer;
 
 	while (BlockNumberIsValid(blkno = heap_vac_scan_next_block(vacrel,
-															   &all_visible_according_to_vm)))
+															   &all_visible_according_to_vm,
+															   &was_eager_scanned)))
 	{
 		Buffer		buf;
 		Page		page;
@@ -956,11 +1094,23 @@ lazy_scan_heap(LVRelState *vacrel)
 		if (!got_cleanup_lock)
 			LockBuffer(buf, BUFFER_LOCK_SHARE);
 
+		page_freezes = vacrel->vm_page_freezes;
+
 		/* Check for new or empty pages before lazy_scan_[no]prune call */
 		if (lazy_scan_new_or_empty(vacrel, buf, blkno, page, !got_cleanup_lock,
 								   vmbuffer))
 		{
 			/* Processed as new/empty page (lock and pin released) */
+
+			/* count an eagerly scanned page as a failure or a success */
+			if (was_eager_scanned)
+			{
+				if (vacrel->vm_page_freezes > page_freezes)
+					decrement_blkno(&vacrel->remaining_eager_scan_successes);
+				else
+					vacrel->eager_scanned_failed_frozen++;
+			}
+
 			continue;
 		}
 
@@ -979,7 +1129,7 @@ lazy_scan_heap(LVRelState *vacrel)
 			 * lazy_scan_noprune could not do all required processing.  Wait
 			 * for a cleanup lock, and call lazy_scan_prune in the usual way.
 			 */
-			Assert(vacrel->aggressive);
+			Assert(vacrel->aggressive == VAC_AGGRESSIVE);
 			LockBuffer(buf, BUFFER_LOCK_UNLOCK);
 			LockBufferForCleanup(buf);
 			got_cleanup_lock = true;
@@ -1003,6 +1153,15 @@ lazy_scan_heap(LVRelState *vacrel)
 							vmbuffer, all_visible_according_to_vm,
 							&has_lpdead_items);
 
+		/* count an eagerly scanned page as a failure or a success */
+		if (was_eager_scanned)
+		{
+			if (vacrel->vm_page_freezes > page_freezes)
+				decrement_blkno(&vacrel->remaining_eager_scan_successes);
+			else
+				vacrel->eager_scanned_failed_frozen++;
+		}
+
 		/*
 		 * Now drop the buffer lock and, potentially, update the FSM.
 		 *
@@ -1112,7 +1271,9 @@ lazy_scan_heap(LVRelState *vacrel)
  *
  * The block number and visibility status of the next block to process are
  * returned and set in *all_visible_according_to_vm.  The return value is
- * InvalidBlockNumber if there are no further blocks to process.
+ * InvalidBlockNumber if there are no further blocks to process. If the block
+ * is being eagerly scanned, was_eager_scanned is set so that the caller can
+ * count whether or not we successfully freeze it.
  *
  * vacrel is an in/out parameter here.  Vacuum options and information about
  * the relation are read.  vacrel->skippedallvis is set if we skip a block
@@ -1122,11 +1283,14 @@ lazy_scan_heap(LVRelState *vacrel)
  */
 static BlockNumber
 heap_vac_scan_next_block(LVRelState *vacrel,
-						 bool *all_visible_according_to_vm)
+						 bool *all_visible_according_to_vm,
+						 bool *was_eager_scanned)
 {
 	/* relies on InvalidBlockNumber + 1 overflowing to 0 on first call */
 	vacrel->current_block++;
 
+	*was_eager_scanned = false;
+
 	/* Have we reached the end of the relation? */
 	if (vacrel->current_block >= vacrel->rel_pages)
 		return InvalidBlockNumber;
@@ -1137,6 +1301,8 @@ heap_vac_scan_next_block(LVRelState *vacrel,
 	if (vacrel->current_block > vacrel->next_unskippable_block ||
 		vacrel->next_unskippable_block == InvalidBlockNumber)
 	{
+		bool		consider_eager_scan = false;
+
 		/*
 		 * 1. We have just processed an unskippable block (or we're at the
 		 * beginning of the scan).  Find the next unskippable block using the
@@ -1144,7 +1310,65 @@ heap_vac_scan_next_block(LVRelState *vacrel,
 		 */
 		bool		skipsallvis;
 
-		find_next_unskippable_block(vacrel, &skipsallvis);
+		/*
+		 * Figure out if we should disable eager scan going forward or
+		 * downgrade to an unaggressive vacuum altogether.
+		 */
+		if (vacrel->aggressive == VAC_SEMIAGGRESSIVE)
+		{
+			/*
+			 * If we hit our success limit, there is no need to eagerly scan
+			 * any additional pages. Downgrade the vacuum to unaggressive.
+			 */
+			if (vacrel->remaining_eager_scan_successes == 0)
+				vacrel->aggressive = VAC_UNAGGRESSIVE;
+
+			/*
+			 * If we hit the max number of failed eager scans for this region
+			 * of the table, figure out where the next eager scan region
+			 * should start. Eager scanning is effectively disabled until we
+			 * scan a block in that new region.
+			 */
+			else if (vacrel->eager_scanned_failed_frozen >=
+					 MAX_SUCCESSIVE_EAGER_SCAN_FAILS)
+			{
+				BlockNumber region_size,
+							offset;
+
+				/*
+				 * On the assumption that different regions of the table are
+				 * likely to have similarly aged data, we will retry eager
+				 * scanning again later. For a small table, we'll retry eager
+				 * scanning every quarter of the table. For a larger table,
+				 * we'll consider eager scanning again after processing
+				 * another region's worth of data.
+				 *
+				 * We consider the region to start from the first failure, so
+				 * calculate the block to restart eager scanning from there.
+				 */
+				region_size = Min(RELSEG_SIZE, (vacrel->rel_pages / 4));
+
+				offset = vacrel->eager_scanned_failed_frozen % region_size;
+
+				Assert(vacrel->eager_scanned > 0);
+
+				vacrel->unaggressive_to = vacrel->current_block + (region_size - offset);
+				vacrel->eager_scanned_failed_frozen = 0;
+			}
+		}
+
+		/*
+		 * If it is a fully aggressive vacuum or we haven't yet hit the fail
+		 * limit in our current eager scan region, consider eager scanning the
+		 * next block.
+		 */
+		if (vacrel->aggressive == VAC_AGGRESSIVE)
+			consider_eager_scan = true;
+		else if (vacrel->aggressive == VAC_SEMIAGGRESSIVE)
+			consider_eager_scan = vacrel->current_block >= vacrel->unaggressive_to;
+
+		find_next_unskippable_block(vacrel, consider_eager_scan,
+									was_eager_scanned, &skipsallvis);
 
 		/*
 		 * We now know the next block that we must process.  It can be the
@@ -1199,6 +1423,11 @@ heap_vac_scan_next_block(LVRelState *vacrel,
  * The next unskippable block and its visibility information is updated in
  * vacrel.
  *
+ * consider_eager_scan indicates whether or not we should consider scanning
+ * all-visible but not all-frozen blocks. was_eager_scanned is set to true if
+ * we decided to eager scan a block. In this case, next_unskippable_block is
+ * set to that block number.
+ *
  * Note: our opinion of which blocks can be skipped can go stale immediately.
  * It's okay if caller "misses" a page whose all-visible or all-frozen marking
  * was concurrently cleared, though.  All that matters is that caller scan all
@@ -1208,7 +1437,11 @@ heap_vac_scan_next_block(LVRelState *vacrel,
  * to skip such a range is actually made, making everything safe.)
  */
 static void
-find_next_unskippable_block(LVRelState *vacrel, bool *skipsallvis)
+find_next_unskippable_block(
+							LVRelState *vacrel,
+							bool consider_eager_scan,
+							bool *was_eager_scanned,
+							bool *skipsallvis)
 {
 	BlockNumber rel_pages = vacrel->rel_pages;
 	BlockNumber next_unskippable_block = vacrel->next_unskippable_block + 1;
@@ -1217,7 +1450,7 @@ find_next_unskippable_block(LVRelState *vacrel, bool *skipsallvis)
 
 	*skipsallvis = false;
 
-	for (;;)
+	for (;; next_unskippable_block++)
 	{
 		uint8		mapbits = visibilitymap_get_status(vacrel->rel,
 													   next_unskippable_block,
@@ -1253,23 +1486,31 @@ find_next_unskippable_block(LVRelState *vacrel, bool *skipsallvis)
 			break;
 
 		/*
-		 * Aggressive VACUUM caller can't skip pages just because they are
-		 * all-visible.  They may still skip all-frozen pages, which can't
-		 * contain XIDs < OldestXmin (XIDs that aren't already frozen by now).
+		 * In all other cases, we can skip all-frozen pages. Even fully
+		 * aggressive vacuums may skip all-frozen pages since all-frozen pages
+		 * cannot contain XIDs < OldestXmin (XIDs that aren't already frozen
+		 * by now).
 		 */
-		if ((mapbits & VISIBILITYMAP_ALL_FROZEN) == 0)
-		{
-			if (vacrel->aggressive)
-				break;
+		if (mapbits & VISIBILITYMAP_ALL_FROZEN)
+			continue;
 
-			/*
-			 * All-visible block is safe to skip in non-aggressive case.  But
-			 * remember that the final range contains such a block for later.
-			 */
-			*skipsallvis = true;
+		/*
+		 * Fully aggressive vacuums cannot skip all-visible pages that are not
+		 * also all-frozen. Semi-aggressive vacuums only skip such pages if
+		 * they have hit the failure limit for the current eager scan region.
+		 */
+		if (consider_eager_scan)
+		{
+			*was_eager_scanned = true;
+			vacrel->eager_scanned++;
+			break;
 		}
 
-		next_unskippable_block++;
+		/*
+		 * All-visible block is safe to skip in a semi or unaggressive vacuum.
+		 * But remember that the final range contains such a block for later.
+		 */
+		*skipsallvis = true;
 	}
 
 	/* write the local variables back to vacrel */
@@ -1781,7 +2022,7 @@ lazy_scan_noprune(LVRelState *vacrel,
 									 &NoFreezePageRelminMxid))
 		{
 			/* Tuple with XID < FreezeLimit (or MXID < MultiXactCutoff) */
-			if (vacrel->aggressive)
+			if (vacrel->aggressive == VAC_AGGRESSIVE)
 			{
 				/*
 				 * Aggressive VACUUMs must always be able to advance rel's
diff --git a/src/backend/commands/vacuum.c b/src/backend/commands/vacuum.c
index 86f36b36954..236bd2dbb98 100644
--- a/src/backend/commands/vacuum.c
+++ b/src/backend/commands/vacuum.c
@@ -1079,7 +1079,7 @@ get_all_vacuum_rels(MemoryContext vac_context, int options)
  * FreezeLimit (at a minimum), and relminmxid up to MultiXactCutoff (at a
  * minimum).
  */
-bool
+VacAggressive
 vacuum_get_cutoffs(Relation rel, const VacuumParams *params,
 				   struct VacuumCutoffs *cutoffs)
 {
@@ -1213,7 +1213,7 @@ vacuum_get_cutoffs(Relation rel, const VacuumParams *params,
 		aggressiveXIDCutoff = FirstNormalTransactionId;
 	if (TransactionIdPrecedesOrEquals(cutoffs->relfrozenxid,
 									  aggressiveXIDCutoff))
-		return true;
+		return VAC_AGGRESSIVE;
 
 	/*
 	 * Similar to the above, determine the table freeze age to use for
@@ -1234,10 +1234,22 @@ vacuum_get_cutoffs(Relation rel, const VacuumParams *params,
 		aggressiveMXIDCutoff = FirstMultiXactId;
 	if (MultiXactIdPrecedesOrEquals(cutoffs->relminmxid,
 									aggressiveMXIDCutoff))
-		return true;
+		return VAC_AGGRESSIVE;
+
+	/*
+	 * If we are not required to do a fully aggressive vacuum, we may still
+	 * eagerly scan pages as long as relfrozenxid precedes the freeze limit.
+	 * We don't bother enabling eager scanning if no tuples will be eligible
+	 * to be frozen.
+	 */
+	if ((TransactionIdIsNormal(cutoffs->relfrozenxid) &&
+		 TransactionIdPrecedesOrEquals(cutoffs->relfrozenxid, cutoffs->FreezeLimit)) ||
+		(MultiXactIdIsValid(cutoffs->relminmxid) &&
+		 MultiXactIdPrecedesOrEquals(cutoffs->relminmxid, cutoffs->MultiXactCutoff)))
+		return VAC_SEMIAGGRESSIVE;
 
 	/* Non-aggressive VACUUM */
-	return false;
+	return VAC_UNAGGRESSIVE;
 }
 
 /*
diff --git a/src/include/commands/vacuum.h b/src/include/commands/vacuum.h
index 759f9a87d38..39809f3fc83 100644
--- a/src/include/commands/vacuum.h
+++ b/src/include/commands/vacuum.h
@@ -288,6 +288,29 @@ typedef struct VacDeadItemsInfo
 	int64		num_items;		/* current # of entries */
 } VacDeadItemsInfo;
 
+/*
+ * The aggressiveness level of a vacuum determines how many all-visible but
+ * not all-frozen pages it eagerly scans.
+ *
+ * An unaggressive vacuum scans no all-visible pages unless page skipping is
+ * disabled.
+ *
+ * A fully aggressive vacuum eagerly scans all all-visible but not all-frozen
+ * pages.
+ *
+ * A semi-aggressive vacuum eagerly scans a number of pages up to a limit
+ * based on whether or not it is succeeding or failing. A semi-aggressive
+ * vacuum is downgraded to an unaggressive vacuum when it hits its success
+ * quota. An aggressive vacuum cannot be downgraded. No aggressiveness
+ * level is ever upgraded.
+ */
+typedef enum VacAggressive
+{
+	VAC_UNAGGRESSIVE,
+	VAC_AGGRESSIVE,
+	VAC_SEMIAGGRESSIVE,
+} VacAggressive;
+
 /* GUC parameters */
 extern PGDLLIMPORT int default_statistics_target;	/* PGDLLIMPORT for PostGIS */
 extern PGDLLIMPORT int vacuum_freeze_min_age;
@@ -335,8 +358,8 @@ extern void vac_update_relstats(Relation relation,
 								bool *frozenxid_updated,
 								bool *minmulti_updated,
 								bool in_outer_xact);
-extern bool vacuum_get_cutoffs(Relation rel, const VacuumParams *params,
-							   struct VacuumCutoffs *cutoffs);
+extern VacAggressive vacuum_get_cutoffs(Relation rel, const VacuumParams *params,
+										struct VacuumCutoffs *cutoffs);
 extern bool vacuum_xid_failsafe_check(const struct VacuumCutoffs *cutoffs);
 extern void vac_update_datfrozenxid(void);
 extern void vacuum_delay_point(void);
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 171a7dd5d2b..abed3008f87 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -3056,6 +3056,7 @@ UserAuth
 UserContext
 UserMapping
 UserOpts
+VacAggressive
 VacAttrStats
 VacAttrStatsP
 VacDeadItemsInfo
-- 
2.34.1