diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index b22b36ec0e..dbe0c1cb14 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -2029,6 +2029,8 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
  */
 EquivalenceClass *
 match_eclasses_to_foreign_key_col(PlannerInfo *root,
+								  EquivalenceClass **eclasses,
+								  Bitmapset **eclass_index,
 								  ForeignKeyOptInfo *fkinfo,
 								  int colno)
 {
@@ -2038,23 +2040,29 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
 	AttrNumber	var2attno = fkinfo->confkey[colno];
 	Oid			eqop = fkinfo->conpfeqop[colno];
 	List	   *opfamilies = NIL;	/* compute only if needed */
-	ListCell   *lc1;
+	Bitmapset  *matching_ecs;
+	int			i;
 
-	foreach(lc1, root->eq_classes)
+	/* Determine which eclasses contain members for both of the relations */
+	matching_ecs = bms_intersect(eclass_index[var1varno],
+								 eclass_index[var2varno]);
+
+	i = -1;
+	while ((i = bms_next_member(matching_ecs, i)) >= 0)
 	{
-		EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
+		EquivalenceClass *ec = eclasses[i];
 		bool		item1member = false;
 		bool		item2member = false;
-		ListCell   *lc2;
+		ListCell   *lc;
 
 		/* Never match to a volatile EC */
 		if (ec->ec_has_volatile)
 			continue;
 		/* Note: it seems okay to match to "broken" eclasses here */
 
-		foreach(lc2, ec->ec_members)
+		foreach(lc, ec->ec_members)
 		{
-			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
 			Var		   *var;
 
 			if (em->em_is_child)
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 01335db511..f826a4612a 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -2440,6 +2440,41 @@ match_foreign_keys_to_quals(PlannerInfo *root)
 {
 	List	   *newlist = NIL;
 	ListCell   *lc;
+	EquivalenceClass   **eclasses;
+	Bitmapset		   **eclass_index;
+	int			i;
+
+	eclasses = palloc(sizeof(EquivalenceClass *) *
+					  list_length(root->eq_classes));
+	eclass_index = palloc0(sizeof(Bitmapset *) * root->simple_rel_array_size);
+
+	/*
+	 * Index the eclass list so that we can quickly identify eclasses
+	 * belonging to a given relation.  First we build an array to store
+	 * each eclasss, this allows us to quickly lookup the eclass by array
+	 * index.  We then build an index using a Bitmapset for each relation to
+	 * mark which eclass array element contains a member for that relation.
+	 */
+	i = 0;
+	foreach(lc, root->eq_classes)
+		eclasses[i++] = lfirst(lc);
+
+	/*
+	 * We could build the indexes in the loop above, but looping backwards
+	 * allows the Bitmapset to be allocated to its final size on the first
+	 * allocation.  Doing this forward could cause small incremental
+	 * allocations which can be slower.
+	 */
+	for (i--; i >= 0; i--)
+	{
+		int j = -1;
+
+		while ((j = bms_next_member(eclasses[i]->ec_relids, j)) > 0)
+		{
+			Assert(j < root->simple_rel_array_size);
+			eclass_index[j] = bms_add_member(eclass_index[j], i);
+		}
+	}
 
 	foreach(lc, root->fkey_list)
 	{
@@ -2489,6 +2524,8 @@ match_foreign_keys_to_quals(PlannerInfo *root)
 			ListCell   *lc2;
 
 			fkinfo->eclass[colno] = match_eclasses_to_foreign_key_col(root,
+																	  eclasses,
+																	  eclass_index,
 																	  fkinfo,
 																	  colno);
 			/* Don't bother looking for loose quals if we got an EC match */
@@ -2586,6 +2623,9 @@ match_foreign_keys_to_quals(PlannerInfo *root)
 	}
 	/* Replace fkey_list, thereby discarding any useless entries */
 	root->fkey_list = newlist;
+
+	pfree(eclasses);
+	pfree(eclass_index);
 }
 
 
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index cafde307ad..123946b50f 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -156,6 +156,8 @@ extern List *generate_join_implied_equalities_for_ecs(PlannerInfo *root,
 										 RelOptInfo *inner_rel);
 extern bool exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2);
 extern EquivalenceClass *match_eclasses_to_foreign_key_col(PlannerInfo *root,
+								  EquivalenceClass **eclasses,
+								  Bitmapset **eclass_index,
 								  ForeignKeyOptInfo *fkinfo,
 								  int colno);
 extern void add_child_rel_equivalences(PlannerInfo *root,