diff --git a/src/backend/utils/adt/ri_triggers.c b/src/backend/utils/adt/ri_triggers.c
index 61edde9..eaec737 100644
--- a/src/backend/utils/adt/ri_triggers.c
+++ b/src/backend/utils/adt/ri_triggers.c
@@ -125,6 +125,8 @@ typedef struct RI_ConstraintInfo
 												 * PK) */
 	Oid			ff_eq_oprs[RI_MAX_NUMKEYS];		/* equality operators (FK =
 												 * FK) */
+	struct RI_ConstraintInfo *prev_valid;		/* Previous valid entry */
+	struct RI_ConstraintInfo *next_valid;		/* Next valid entry */
 } RI_ConstraintInfo;
 
 
@@ -185,6 +187,7 @@ typedef struct RI_CompareHashEntry
 static HTAB *ri_constraint_cache = NULL;
 static HTAB *ri_query_cache = NULL;
 static HTAB *ri_compare_cache = NULL;
+static RI_ConstraintInfo *ri_constraint_cache_valid_list = NULL;
 
 
 /* ----------
@@ -2924,6 +2927,19 @@ ri_LoadConstraintInfo(Oid constraintOid)
 
 	ReleaseSysCache(tup);
 
+	/*
+	 * At the time a cache invalidation message is processed there may be
+	 * active references to the cache. Because of this we never remove entries
+	 * from the cache, but only mark them invalid. For efficient processing
+	 * of invalidation messages below we keep a double linked list of
+	 * currently valid entries.
+	 */
+	if (ri_constraint_cache_valid_list != NULL)
+		ri_constraint_cache_valid_list->prev_valid = riinfo;
+	riinfo->prev_valid = NULL;
+	riinfo->next_valid = ri_constraint_cache_valid_list;
+	ri_constraint_cache_valid_list = riinfo;
+
 	riinfo->valid = true;
 
 	return riinfo;
@@ -2940,17 +2956,55 @@ ri_LoadConstraintInfo(Oid constraintOid)
 static void
 InvalidateConstraintCacheCallBack(Datum arg, int cacheid, uint32 hashvalue)
 {
-	HASH_SEQ_STATUS status;
-	RI_ConstraintInfo *hentry;
+	RI_ConstraintInfo  *hentry;
+	RI_ConstraintInfo  *hnext;
+	bool				found;
 
 	Assert(ri_constraint_cache != NULL);
 
-	hash_seq_init(&status, ri_constraint_cache);
-	while ((hentry = (RI_ConstraintInfo *) hash_seq_search(&status)) != NULL)
+	if (hashvalue == 0)
 	{
-		if (hentry->valid &&
-			(hashvalue == 0 || hentry->oidHashValue == hashvalue))
+		/*
+		 * Set all valid entries in the cache to invalid and clear the
+		 * list of valid entries.
+		 */
+		hnext = ri_constraint_cache_valid_list;
+		while (hnext)
+		{
+			hentry = hnext;
+			hnext = hnext->next_valid;
+
+			Assert(hentry->valid);
+
+			hentry->prev_valid = NULL;
+			hentry->next_valid = NULL;
 			hentry->valid = false;
+		}
+		ri_constraint_cache_valid_list = NULL;
+	}
+	else
+	{
+		/*
+		 * Search for the specified entry and set that one invalid
+		 * and remove it from the list of valid entries.
+		 */
+		hentry = (RI_ConstraintInfo *) hash_search(ri_constraint_cache,
+												   (void *) &hashvalue,
+												   HASH_FIND, &found);
+		if (found && hentry->valid)
+		{
+			Assert(hentry->oidHashValue == hashvalue);
+
+			if (hentry->prev_valid != NULL)
+				hentry->prev_valid->next_valid = hentry->next_valid;
+			else
+				ri_constraint_cache_valid_list = hentry->next_valid;
+			if (hentry->next_valid != NULL)
+				hentry->next_valid->prev_valid = hentry->prev_valid;
+			hentry->prev_valid = NULL;
+			hentry->next_valid = NULL;
+			hentry->valid = false;
+		}
 	}
 }