diff --git a/contrib/pgstattuple/pgstatbloat.c b/contrib/pgstattuple/pgstatbloat.c
index 2dd1900..b19459a 100644
--- a/contrib/pgstattuple/pgstatbloat.c
+++ b/contrib/pgstattuple/pgstatbloat.c
@@ -193,6 +193,12 @@ pgstatbloat(PG_FUNCTION_ARGS)
 }
 
 /*
+ * Before we consider skipping a page that's marked as clean in
+ * visibility map, we must've seen at least this many clean pages.
+ */
+#define SKIP_PAGES_THRESHOLD    ((BlockNumber) 32)
+
+/*
  * This function takes an already open relation and scans its pages,
  * skipping those that have the corresponding visibility map bit set.
  * For pages we skip, we find the free space from the free space map
@@ -213,6 +219,8 @@ pgstatbloat_heap(Relation rel, FunctionCallInfo fcinfo)
 	pgstatbloat_output_type stat = {0};
 	BufferAccessStrategy bstrategy;
 	TransactionId OldestXmin;
+	BlockNumber next_not_all_visible_block;
+	bool		skipping_all_visible_blocks;
 
 	OldestXmin = GetOldestXmin(rel, true);
 	bstrategy = GetAccessStrategy(BAS_BULKREAD);
@@ -220,6 +228,24 @@ pgstatbloat_heap(Relation rel, FunctionCallInfo fcinfo)
 	scanned = 0;
 	nblocks = RelationGetNumberOfBlocks(rel);
 
+	/*
+	 * We use the visibility map to skip over SKIP_PAGES_THRESHOLD or
+	 * more contiguous all-visible pages. See the explanation in
+	 * lazy_scan_heap for the rationale.
+	 */
+
+	for (next_not_all_visible_block = 0;
+		 next_not_all_visible_block < nblocks;
+		 next_not_all_visible_block++)
+	{
+		if (!visibilitymap_test(rel, next_not_all_visible_block, &vmbuffer))
+			break;
+	}
+	if (next_not_all_visible_block >= SKIP_PAGES_THRESHOLD)
+		skipping_all_visible_blocks = true;
+	else
+		skipping_all_visible_blocks = false;
+
 	for (blkno = 0; blkno < nblocks; blkno++)
 	{
 		Buffer		buf;
@@ -230,13 +256,34 @@ pgstatbloat_heap(Relation rel, FunctionCallInfo fcinfo)
 
 		CHECK_FOR_INTERRUPTS();
 
-		/*
-		 * If the page has only visible tuples, then we can find out the
-		 * free space from the FSM and move on.
-		 */
+		if (blkno == next_not_all_visible_block)
+		{
+			/* Time to advance next_not_all_visible_block */
+			for (next_not_all_visible_block++;
+				 next_not_all_visible_block < nblocks;
+				 next_not_all_visible_block++)
+			{
+				if (!visibilitymap_test(rel, next_not_all_visible_block,
+										&vmbuffer))
+					break;
+			}
 
-		if (visibilitymap_test(rel, blkno, &vmbuffer))
+			/*
+			 * We know we can't skip the current block.  But set up
+			 * skipping_all_visible_blocks to do the right thing at the
+			 * following blocks.
+			 */
+			if (next_not_all_visible_block - blkno > SKIP_PAGES_THRESHOLD)
+				skipping_all_visible_blocks = true;
+			else
+				skipping_all_visible_blocks = false;
+		}
+		else if (skipping_all_visible_blocks)
 		{
+			/*
+			 * We can skip this all-visible page, so we just find out
+			 * the free space from the FSM.
+			 */
 			freespace = GetRecordedFreeSpace(rel, blkno);
 			stat.tuple_len += BLCKSZ - freespace;
 			stat.free_space += freespace;