diff --git a/src/backend/access/common/heaptuple.c b/src/backend/access/common/heaptuple.c
index 1f39a72..03d47b6 100644
--- a/src/backend/access/common/heaptuple.c
+++ b/src/backend/access/common/heaptuple.c
@@ -83,7 +83,6 @@ static Datum
 getmissingattr(TupleDesc tupleDesc,
 			   int attnum, bool *isnull)
 {
-	int			missingnum;
 	Form_pg_attribute att;
 	AttrMissing *attrmiss;
 
@@ -94,21 +93,33 @@ getmissingattr(TupleDesc tupleDesc,
 
 	if (att->atthasmissing)
 	{
+		int			lo,
+					hi,
+					mid;
+
 		Assert(tupleDesc->constr);
 		Assert(tupleDesc->constr->num_missing > 0);
 
 		attrmiss = tupleDesc->constr->missing;
 
+		lo = -1;
+		hi = tupleDesc->constr->num_missing - 1;
+
 		/*
-		 * Look through the tupledesc's attribute missing values
-		 * for the one that corresponds to this attribute.
+		 * Binary search the tupledesc's attribute missing values for the one
+		 * that corresponds to this attribute.
 		 */
-		for (missingnum = tupleDesc->constr->num_missing - 1;
-			 missingnum >= 0; missingnum--)
+		while (lo < hi)
 		{
-			if (attrmiss[missingnum].amnum == attnum)
+			mid = (lo + hi + 1) / 2;
+
+			if (attrmiss[mid].amnum < attnum)
+				lo = mid;
+			else if (attrmiss[mid].amnum > attnum)
+				hi = mid - 1;
+			else
 			{
-				if (attrmiss[missingnum].ammissingNull)
+				if (attrmiss[mid].ammissingNull)
 				{
 					*isnull = true;
 					return (Datum) 0;
@@ -116,10 +127,11 @@ getmissingattr(TupleDesc tupleDesc,
 				else
 				{
 					*isnull = false;
-					return attrmiss[missingnum].ammissing;
+					return attrmiss[mid].ammissing;
 				}
 			}
 		}
+
 		Assert(false); /* should not be able to get here */
 	}