*** src/backend/commands/vacuumlazy.c
--- src/backend/commands/vacuumlazy.c
***************
*** 271,276 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
--- 271,277 ----
  	int			i;
  	PGRUsage	ru0;
  	Buffer		vmbuffer = InvalidBuffer;
+ 	BlockNumber	all_visible_streak;
  
  	pg_rusage_init(&ru0);
  
***************
*** 292,297 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
--- 293,299 ----
  
  	lazy_space_alloc(vacrelstats, nblocks);
  
+ 	all_visible_streak = 0;
  	for (blkno = 0; blkno < nblocks; blkno++)
  	{
  		Buffer		buf;
***************
*** 309,315 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
  
  		/*
  		 * Skip pages that don't require vacuuming according to the
! 		 * visibility map.
  		 */
  		if (!scan_all)
  		{
--- 311,324 ----
  
  		/*
  		 * Skip pages that don't require vacuuming according to the
! 		 * visibility map. But only if we've seen a streak of at least
! 		 * 20 pages marked as clean. Since we're reading sequentially,
! 		 * the OS should be doing readahead for us and there's no gain
! 		 * in skipping a page now and then. You need a longer run of
! 		 * consecutive skipped pages before it's worthwhile. Also,
! 		 * skipping even a single page means that we can't update
! 		 * relfrozenxid or reltuples, so we only want to do it if
! 		 * there's a good chance to skip a goodly number of pages.
  		 */
  		if (!scan_all)
  		{
***************
*** 317,325 **** lazy_scan_heap(Relation onerel, LVRelStats *vacrelstats,
  				visibilitymap_test(onerel, blkno, &vmbuffer);
  			if (all_visible_according_to_vm)
  			{
! 				vacrelstats->scanned_all = false;
! 				continue;
  			}
  		}
  
  		vacuum_delay_point();
--- 326,340 ----
  				visibilitymap_test(onerel, blkno, &vmbuffer);
  			if (all_visible_according_to_vm)
  			{
! 				all_visible_streak++;
! 				if (all_visible_streak >= 20)
! 				{
! 					vacrelstats->scanned_all = false;
! 					continue;
! 				}
  			}
+ 			else
+ 				all_visible_streak = 0;
  		}
  
  		vacuum_delay_point();