diff --git a/src/backend/storage/ipc/procarray.c b/src/backend/storage/ipc/procarray.c
index afe1c03..b2dae85 100644
--- a/src/backend/storage/ipc/procarray.c
+++ b/src/backend/storage/ipc/procarray.c
@@ -1758,6 +1758,8 @@ GetSnapshotData(Snapshot snapshot)
 	snapshot->active_count = 0;
 	snapshot->regd_count = 0;
 	snapshot->copied = false;
+	snapshot->xip_sorted = false;
+	snapshot->subxip_sorted = false;
 
 	if (old_snapshot_threshold < 0)
 	{
diff --git a/src/backend/utils/time/tqual.c b/src/backend/utils/time/tqual.c
index f7c4c91..f155267 100644
--- a/src/backend/utils/time/tqual.c
+++ b/src/backend/utils/time/tqual.c
@@ -1461,6 +1461,45 @@ HeapTupleIsSurelyDead(HeapTuple htup, TransactionId OldestXmin)
 	return TransactionIdPrecedes(HeapTupleHeaderGetRawXmax(tuple), OldestXmin);
 }
 
+static int
+cmp_transaction_id(const void *a, const void *b)
+{
+	return memcmp(a, b, sizeof(TransactionId));
+}
+
+/*
+ * XidInXip searches xid in xip array.
+ *
+ * When xcnt is smaller than SnapshotSortThreshold, then the array is unsorted
+ * and we can simply do a linear search. If there are more elements, the array
+ * is sorted, and we can do a bsearch.
+ */
+static bool
+XidInXip(TransactionId xid, TransactionId *xip, uint32 xcnt, bool *sorted)
+{
+	if (!TransactionIdIsNormal(xid))
+		return false;
+
+	if (xcnt < SnapshotSortThreshold)
+	{
+		uint32 i;
+
+		/* linear scan for small snapshots */
+		for (i = 0; i < xcnt; i++)
+			if (TransactionIdEquals(xid, xip[i]))
+				return true;
+		return false;
+	}
+
+	if (!(*sorted))
+	{
+		pg_qsort(xip, xcnt, sizeof(TransactionId), cmp_transaction_id);
+		*sorted = true;
+	}
+
+	return (bsearch(&xid, xip, xcnt, sizeof(TransactionId), cmp_transaction_id) != NULL);
+}
+
 /*
  * XidInMVCCSnapshot
  *		Is the given XID still-in-progress according to the snapshot?
@@ -1474,8 +1513,6 @@ HeapTupleIsSurelyDead(HeapTuple htup, TransactionId OldestXmin)
 bool
 XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
 {
-	uint32		i;
-
 	/*
 	 * Make a quick range check to eliminate most XIDs without looking at the
 	 * xip arrays.  Note that this is OK even if we convert a subxact XID to
@@ -1507,13 +1544,8 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
 		if (!snapshot->suboverflowed)
 		{
 			/* we have full data, so search subxip */
-			int32		j;
-
-			for (j = 0; j < snapshot->subxcnt; j++)
-			{
-				if (TransactionIdEquals(xid, snapshot->subxip[j]))
-					return true;
-			}
+			if (XidInXip(xid, snapshot->subxip, snapshot->subxcnt, &snapshot->subxip_sorted))
+				return true;
 
 			/* not there, fall through to search xip[] */
 		}
@@ -1534,16 +1566,12 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
 				return false;
 		}
 
-		for (i = 0; i < snapshot->xcnt; i++)
-		{
-			if (TransactionIdEquals(xid, snapshot->xip[i]))
-				return true;
-		}
+
+		if (XidInXip(xid, snapshot->xip, snapshot->xcnt, &snapshot->xip_sorted))
+			return true;
 	}
 	else
 	{
-		int32		j;
-
 		/*
 		 * In recovery we store all xids in the subxact array because it is by
 		 * far the bigger array, and we mostly don't know which xids are
@@ -1573,11 +1601,8 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
 		 * indeterminate xid. We don't know whether it's top level or subxact
 		 * but it doesn't matter. If it's present, the xid is visible.
 		 */
-		for (j = 0; j < snapshot->subxcnt; j++)
-		{
-			if (TransactionIdEquals(xid, snapshot->subxip[j]))
-				return true;
-		}
+		if (XidInXip(xid, snapshot->subxip, snapshot->subxcnt, &snapshot->subxip_sorted))
+			return true;
 	}
 
 	return false;
diff --git a/src/include/utils/snapshot.h b/src/include/utils/snapshot.h
index a8a5a8f..85301c7 100644
--- a/src/include/utils/snapshot.h
+++ b/src/include/utils/snapshot.h
@@ -25,6 +25,11 @@ typedef struct SnapshotData *Snapshot;
 #define InvalidSnapshot		((Snapshot) NULL)
 
 /*
+ * SnapshotSortThreshold ... TODO comment
+ */
+#define SnapshotSortThreshold	60
+
+/*
  * We use SnapshotData structures to represent both "regular" (MVCC)
  * snapshots and "special" snapshots that have non-MVCC semantics.
  * The specific semantics of a snapshot are encoded by the "satisfies"
@@ -78,6 +83,7 @@ typedef struct SnapshotData
 	 */
 	TransactionId *xip;
 	uint32		xcnt;			/* # of xact ids in xip[] */
+	bool		xip_sorted;		/* is xip array sorted */
 
 	/*
 	 * For non-historic MVCC snapshots, this contains subxact IDs that are in
@@ -94,6 +100,7 @@ typedef struct SnapshotData
 
 	bool		takenDuringRecovery;	/* recovery-shaped snapshot? */
 	bool		copied;			/* false if it's a static snapshot */
+	bool		subxip_sorted;	/* is subxip array sorted */
 
 	CommandId	curcid;			/* in my xact, CID < curcid are visible */