diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 64aecf2..b83b10e 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -281,7 +281,7 @@ heapgetpage(HeapScanDesc scan, BlockNumber page)
 			ItemPointerSet(&(loctup.t_self), page, lineoff);
 
 			if (all_visible)
-				valid = true;
+				valid = HeapTupleSatisfiesAllVisible(loctup.t_data, snapshot, buffer);
 			else
 				valid = HeapTupleSatisfiesVisibility(&loctup, snapshot, buffer);
 
diff --git a/src/backend/utils/time/tqual.c b/src/backend/utils/time/tqual.c
index b531db5..707184e 100644
--- a/src/backend/utils/time/tqual.c
+++ b/src/backend/utils/time/tqual.c
@@ -1044,6 +1044,64 @@ HeapTupleSatisfiesMVCC(HeapTupleHeader tuple, Snapshot snapshot,
 	return false;
 }
 
+/*
+ * When we know that the page this tuple is on *was* marked all visible
+ * we can skip all clog lookups altogether and just rely on MVCC rules.
+ * Clog lookups might reveal come committed transactions but this is
+ * relatively unlikely since they would need to win the race against
+ * our recent test of the VM. And even if they did, our scan can't see
+ * them anyway, so we just avoid all that work completely.
+ */
+bool
+HeapTupleSatisfiesAllVisible(HeapTupleHeader tuple, Snapshot snapshot,
+					   Buffer buffer)
+{
+	/*
+	 * At the start we know all visible inserting transactions are committed -
+	 * - so we only have to check visibility against our snapshot.
+	 */
+	if (XidInMVCCSnapshot(HeapTupleHeaderGetXmin(tuple), snapshot))
+		return false;			/* treat as still in progress */
+
+	if (tuple->t_infomask & HEAP_XMAX_INVALID)	/* xid invalid or aborted */
+		return true;
+
+	if (tuple->t_infomask & HEAP_IS_LOCKED)
+		return true;
+
+	if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
+	{
+		/* MultiXacts are currently only allowed to lock tuples */
+		Assert(tuple->t_infomask & HEAP_IS_LOCKED);
+		return true;
+	}
+
+	/*
+	 * Need to be careful here to ensure we don't insert rows
+	 * ourselves during the scan. Test is cheap when we have no xid.
+	 */
+	if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tuple)))
+	{
+		if (HeapTupleHeaderGetCmin(tuple) >= snapshot->curcid)
+			return false;	/* inserted after scan started */
+		else
+			return true;	/* inserted before scan started */
+	}
+
+	/*
+	 * Similar tests for our own deletes. Test is very cheap when xmax
+	 * is invalid and also cheap when we don't have an xid ourselves.
+	 */
+	if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmax(tuple)))
+	{
+		if (HeapTupleHeaderGetCmax(tuple) >= snapshot->curcid)
+			return true;	/* deleted after scan started */
+		else
+			return false;	/* deleted before scan started */
+	}
+
+	return true;
+}
 
 /*
  * HeapTupleSatisfiesVacuum
diff --git a/src/include/utils/tqual.h b/src/include/utils/tqual.h
index ff74f86..342c861 100644
--- a/src/include/utils/tqual.h
+++ b/src/include/utils/tqual.h
@@ -67,6 +67,8 @@ typedef enum
 /* These are the "satisfies" test routines for the various snapshot types */
 extern bool HeapTupleSatisfiesMVCC(HeapTupleHeader tuple,
 					   Snapshot snapshot, Buffer buffer);
+extern bool HeapTupleSatisfiesAllVisible(HeapTupleHeader tuple,
+					   Snapshot snapshot, Buffer buffer);
 extern bool HeapTupleSatisfiesNow(HeapTupleHeader tuple,
 					  Snapshot snapshot, Buffer buffer);
 extern bool HeapTupleSatisfiesSelf(HeapTupleHeader tuple,