*** a/src/backend/storage/lmgr/predicate.c
--- b/src/backend/storage/lmgr/predicate.c
***************
*** 3846,3855 **** XidIsConcurrent(TransactionId xid)
  
  /*
   * CheckForSerializableConflictOut
!  *		We are reading a tuple which has been modified.  If it is visible to
!  *		us but has been deleted, that indicates a rw-conflict out.	If it's
!  *		not visible and was created by a concurrent (overlapping)
!  *		serializable transaction, that is also a rw-conflict out,
   *
   * We will determine the top level xid of the writing transaction with which
   * we may be in conflict, and check for overlap with our own transaction.
--- 3846,3857 ----
  
  /*
   * CheckForSerializableConflictOut
!  *		We are reading a tuple which may have been modified since this
!  *		transaction started.  If it is visible to us but has been deleted,
!  *		that indicates a rw-conflict out.  If it's not visible and was created
!  *		by a concurrent (overlapping) serializable transaction, that is also a
!  *		rw-conflict out.  Visibility must be determined by the caller using
!  *		HeapTupleSatisfiesVisibility() before calling this function.
   *
   * We will determine the top level xid of the writing transaction with which
   * we may be in conflict, and check for overlap with our own transaction.
***************
*** 3896,3918 **** CheckForSerializableConflictOut(bool visible, Relation relation,
--- 3898,3974 ----
  	switch (htsvResult)
  	{
  		case HEAPTUPLE_LIVE:
+ 
+ 			/*
+ 			 * The transaction which created the tuple has committed, and the
+ 			 * tuple has not been deleted.	If that insert committed in time
+ 			 * for us to see it, there is no conflict; otherwise we conflict
+ 			 * with the inserting transaction.
+ 			 */
  			if (visible)
  				return;
  			xid = HeapTupleHeaderGetXmin(tuple->t_data);
  			break;
+ 
  		case HEAPTUPLE_RECENTLY_DEAD:
+ 
+ 			/*
+ 			 * The tuple has been deleted, but is still visible to some
+ 			 * transactions (possibly including our own).  If the delete
+ 			 * committed in time to make the tuple not-visible to us, we do
+ 			 * not conflict with that; otherwise we conflict with the deleting
+ 			 * transaction.
+ 			 *
+ 			 * TODO: Handle the case that the deleted tuple was both created
+ 			 * and deleted after our transaction started.
+ 			 */
  			if (!visible)
  				return;
  			xid = HeapTupleHeaderGetUpdateXid(tuple->t_data);
  			break;
+ 
  		case HEAPTUPLE_DELETE_IN_PROGRESS:
+ 
+ 			/*
+ 			 * The tuple has been deleted, but that delete has not yet been
+ 			 * committed.  In fact, the delete may have occurred in a
+ 			 * subtransaction which has subsequently been rolled back, in
+ 			 * which case the deleting transaction ID will be invalid, and the
+ 			 * delete should be ignored.  If the delete committed in time to
+ 			 * make the tuple not-visible to us, we do not conflict with that;
+ 			 * otherwise we conflict with the deleting transaction.
+ 			 *
+ 			 * TODO: Handle the case that the deleted tuple was both created
+ 			 * and deleted after our transaction started.
+ 			 */
+ 			if (!visible)
+ 				return;
  			xid = HeapTupleHeaderGetUpdateXid(tuple->t_data);
+ 			if (!TransactionIdIsValid(xid))
+ 				return;
  			break;
+ 
  		case HEAPTUPLE_INSERT_IN_PROGRESS:
+ 
+ 			/*
+ 			 * The tuple has been inserted, but that insert has not yet been
+ 			 * committed.  Since the insert is not yet committed, it cannot be
+ 			 * visible to us unless we inserted it; otherwise we conflict with
+ 			 * the inserting transaction.
+ 			 */
+ 			if (visible)
+ 				return;
  			xid = HeapTupleHeaderGetXmin(tuple->t_data);
  			break;
+ 
  		case HEAPTUPLE_DEAD:
+ 
+ 			/*
+ 			 * The tuple was gone before our transaction started; there is no
+ 			 * conflict.
+ 			 */
  			return;
+ 
  		default:
  
  			/*
***************
*** 3931,3942 **** CheckForSerializableConflictOut(bool visible, Relation relation,
  			xid = InvalidTransactionId;
  	}
  	Assert(TransactionIdIsValid(xid));
- 	Assert(TransactionIdFollowsOrEquals(xid, TransactionXmin));
  
  	/*
  	 * Find top level xid.	Bail out if xid is too early to be a conflict, or
  	 * if it's our own xid.
  	 */
  	if (TransactionIdEquals(xid, GetTopTransactionIdIfAny()))
  		return;
  	xid = SubTransGetTopmostTransaction(xid);
--- 3987,3999 ----
  			xid = InvalidTransactionId;
  	}
  	Assert(TransactionIdIsValid(xid));
  
  	/*
  	 * Find top level xid.	Bail out if xid is too early to be a conflict, or
  	 * if it's our own xid.
  	 */
+ 	if (TransactionIdPrecedes(xid, TransactionXmin))
+ 		return;
  	if (TransactionIdEquals(xid, GetTopTransactionIdIfAny()))
  		return;
  	xid = SubTransGetTopmostTransaction(xid);