diff -ruN ../base/src/backend/access/heap/heapam.c src/backend/access/heap/heapam.c
--- ../base/src/backend/access/heap/heapam.c	2002-07-20 17:27:18.000000000 +0200
+++ src/backend/access/heap/heapam.c	2002-07-20 19:43:19.000000000 +0200
@@ -1123,11 +1123,14 @@
 			CheckMaxObjectId(HeapTupleGetOid(tup));
 	}
 
+	tup->t_data->t_infomask &= ~(HEAP_XACT_MASK);
 	HeapTupleHeaderSetXmin(tup->t_data, GetCurrentTransactionId());
 	HeapTupleHeaderSetCmin(tup->t_data, cid);
 	HeapTupleHeaderSetXmaxInvalid(tup->t_data);
-	HeapTupleHeaderSetCmax(tup->t_data, FirstCommandId);
-	tup->t_data->t_infomask &= ~(HEAP_XACT_MASK);
+	/*
+	 * Do *not* set Cmax!  This would overwrite Cmin.
+	 */
+	/* HeapTupleHeaderSetCmax(tup->t_data, FirstCommandId); */
 	tup->t_data->t_infomask |= HEAP_XMAX_INVALID;
 	tup->t_tableOid = relation->rd_id;
 
@@ -2147,7 +2150,11 @@
 
 	if (redo)
 	{
-		htup->t_infomask &= ~(HEAP_XMAX_COMMITTED |
+		/*
+		 * On redo from WAL we cannot rely on a tqual-routine
+		 * to have reset HEAP_MOVED.
+		 */
+		htup->t_infomask &= ~(HEAP_MOVED | HEAP_XMAX_COMMITTED |
 							  HEAP_XMAX_INVALID | HEAP_MARKED_FOR_UPDATE);
 		HeapTupleHeaderSetXmax(htup, record->xl_xid);
 		HeapTupleHeaderSetCmax(htup, FirstCommandId);
@@ -2320,7 +2327,11 @@
 		}
 		else
 		{
-			htup->t_infomask &= ~(HEAP_XMAX_COMMITTED |
+			/*
+			 * On redo from WAL we cannot rely on a tqual-routine
+			 * to have reset HEAP_MOVED.
+			 */
+			htup->t_infomask &= ~(HEAP_MOVED | HEAP_XMAX_COMMITTED |
 							 HEAP_XMAX_INVALID | HEAP_MARKED_FOR_UPDATE);
 			HeapTupleHeaderSetXmax(htup, record->xl_xid);
 			HeapTupleHeaderSetCmax(htup, FirstCommandId);
diff -ruN ../base/src/backend/utils/time/tqual.c src/backend/utils/time/tqual.c
--- ../base/src/backend/utils/time/tqual.c	2002-07-20 17:27:19.000000000 +0200
+++ src/backend/utils/time/tqual.c	2002-07-20 19:27:03.000000000 +0200
@@ -83,6 +83,7 @@
 					return false;
 				}
 				tuple->t_infomask |= HEAP_XMIN_COMMITTED;
+				tuple->t_infomask &= ~HEAP_MOVED;
 			}
 		}
 		else if (tuple->t_infomask & HEAP_MOVED_IN)