New design for FK-based join selectivity estimation

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index c7b4153..001781a 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -2138,6 +2138,16 @@ _outIndexOptInfo(StringInfo str, const IndexOptInfo *node)
 }
 
 static void
+_outForeignKeyOptInfo(StringInfo str, const ForeignKeyOptInfo *node)
+{
+	WRITE_NODE_TYPE("FOREIGNKEYOPTINFO");
+
+	WRITE_OID_FIELD(conrelid);
+	WRITE_OID_FIELD(confrelid);
+	WRITE_INT_FIELD(nkeys);
+}
+
+static void
 _outEquivalenceClass(StringInfo str, const EquivalenceClass *node)
 {
 	/*
@@ -3607,6 +3617,9 @@ outNode(StringInfo str, const void *obj)
 			case T_IndexOptInfo:
 				_outIndexOptInfo(str, obj);
 				break;
+			case T_ForeignKeyOptInfo:
+				_outForeignKeyOptInfo(str, obj);
+				break;
 			case T_EquivalenceClass:
 				_outEquivalenceClass(str, obj);
 				break;
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index e7f63f4..54d2222 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3888,6 +3888,219 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
 }
 
 /*
+ * find_matching_foreign_keys
+ * 		identifies foreign keys matched by joinquals (or eclasses)
+ *
+ * Searches foreign keys connecting the left and right side of the join, and
+ * returns those with all conditions matches by an eclass or a regular qual.
+ *
+ * The function may return multiple foreign keys for a single pair of tables
+ */
+static List *
+find_matching_foreign_keys(PlannerInfo *root, List *joinquals,
+							JoinType jointype, SpecialJoinInfo *sjinfo,
+							List **remaining_joinquals)
+{
+	int				j;
+	ListCell	   *lc;
+	List		   *keys = NIL;
+
+	/* make a local copy of joinquals so that we can remove items from it */
+	*remaining_joinquals = list_copy(joinquals);
+
+	/* find a combination of foreign keys */
+	while (true)
+	{
+		FKInfo *best = NULL;
+		List   *remove = NIL;
+
+		foreach(lc, root->foreign_keys)
+		{
+			FKInfo *info = (FKInfo *)lfirst(lc);
+
+			/* if we've already added this key, skip it */
+			if (list_member_ptr(keys, info))
+				continue;
+
+			/*
+			 * We can only use foreign keys connecting the two sides of the join.
+			 *
+			 * XXX In Tom's design proposal, this works with inner_rel/outer_rel,
+			 * but we don't have that here. So we use relids from sjinfo instead.
+			 */
+			if ((bms_is_member(info->src_relid, sjinfo->min_lefthand) &&
+				 bms_is_member(info->dst_relid, sjinfo->min_righthand)) ||
+				(bms_is_member(info->dst_relid, sjinfo->min_lefthand) &&
+				 bms_is_member(info->src_relid, sjinfo->min_righthand)))
+			{
+				int		i;
+
+				/* FIXME this needs to consider the remaining quals. */
+				info->nmatched = 0;
+				for (i = 0; i < info->nkeys; i++)
+					if ((info->eclass[i] != NULL) || (info->rinfos[i] != NULL))
+						info->nmatched += 1;
+
+				/* compare the current key to the best key so far */
+				if ((info->nmatched == info->nkeys) &&
+					((best == NULL) || (info->nmatched > best->nmatched)))
+					best = info;
+			}
+		}
+
+		/* if we found no foreign key, terminate the search */
+		if (!best)
+			break;
+
+		keys = lappend(keys, best);
+
+		/* now remove the quals used to match the new key from joinquals */
+		for (j = 0; j < best->nkeys; j++)
+			if (best->rinfos[j] != NULL)
+			{
+				ListCell *lc2;
+				foreach(lc2, best->rinfos[j])
+					*remaining_joinquals
+						= list_delete_ptr(*remaining_joinquals, best->rinfos[j]);
+			}
+
+		/*
+		 * we also need to remove clauses implied by an eclass
+		 *
+		 * We can't simplye remove clauses using parent_ec, we need to
+		 * actually check the clause matches the foreign key.
+		 */
+		foreach(lc, *remaining_joinquals)
+		{
+			int				i;
+			RestrictInfo   *rinfo = (RestrictInfo *)lfirst(lc);
+
+			Assert(IsA(rinfo, RestrictInfo));	/* sanity check */
+
+			/* we can ignore clauses not generated from an eclass */
+			if (! rinfo->parent_ec)
+				continue;
+
+			for (i = 0; i < best->nkeys; i++)
+			{
+				ListCell *lc3;
+				int foundvarmask = 0;
+
+				/* if not matched by the same eclass, skip */
+				if (best->eclass[i] != rinfo->parent_ec)
+					continue;
+
+				foreach(lc3, rinfo->parent_ec->ec_members)
+				{
+					EquivalenceMember *em = (EquivalenceMember *) lfirst(lc3);
+					Var *var = (Var *) em->em_expr;
+
+					/* we can only use simple (Var = Var) eclasses for FKs */
+					if (!IsA(var, Var))
+						continue;
+
+					/* check which side of the foreign key is satisfied */
+					if (best->src_relid == var->varno &&
+						best->conkeys[i] == var->varattno)
+						foundvarmask |= 1;
+
+					else if (best->dst_relid == var->varno &&
+						best->confkeys[i] == var->varattno)
+						foundvarmask |= 2;
+
+					if (foundvarmask == 3)
+						remove = lappend(remove, rinfo);
+				}
+			}
+		}
+
+		/* actually delete the EC-quals */
+		foreach(lc, remove)
+			*remaining_joinquals
+				= list_delete_ptr(*remaining_joinquals, lfirst(lc));
+	}
+
+	return keys;
+}
+
+/*
+ * clauselist_join_selectivity
+ *		Estimate selectivity of join clauses either by using foreign key info
+ *		or by using the regular clauselist_selectivity().
+ *
+ * Since selectivity estimates for each joinqual are multiplied together, this
+ * can cause significant underestimates on the number of join tuples in cases
+ * where there's more than 1 clause in the join condition. To help ease the
+ * pain here we make use of foreign keys, and we assume that 1 row will match
+ * when *all* of the foreign key columns are present in the join condition, any
+ * additional clauses are estimated using clauselist_selectivity().
+ *
+ * Note this ignores whether the FK is invalid or currently deferred; we don't
+ * rely on this assumption for correctness of the query, so it is a reasonable
+ * and safe assumption for planning purposes.
+ *
+ * XXX Currently this applies all fully-matched foreign keys, but maybe
+ * that's not the right thing to do - e.g. when there's a duplicate foreign
+ * key, we'll apply it twice (clearly wrong). Also, overlapping foreign keys
+ * are likely correlated, but multiplication assumes independence.
+ *
+ * XXX We might also apply even foreign keys that are matched only partially,
+ * by estimating the selectivity as (1/N)^(nmatch/nkeys) where nmatch is number
+ * of matched conditions and nkeys is the total number of conditions.
+ *
+ * FIXME Consired NULL values properly (although that'll be tricky due to
+ * correlated columns, which is likely for multi-column keys).
+ */
+static Selectivity
+clauselist_join_selectivity(PlannerInfo *root, List *joinquals,
+							JoinType jointype, SpecialJoinInfo *sjinfo)
+{
+	ListCell	   *lc;
+	Selectivity		sel = 1.0;
+	List		   *matches;
+	List		   *remaining = NIL;
+
+	/* find all foreign keys matched by join quals (or eclasses) */
+	matches = find_matching_foreign_keys(root, joinquals, jointype, sjinfo, &remaining);
+
+	/* did we find any matches at all */
+	foreach(lc, matches)
+	{
+		RelOptInfo *inner_rel, *outer_rel;
+		FKInfo *info = (FKInfo *) lfirst(lc);
+		double	ntuples;
+
+		/*
+		 * We know the foreign key connects the relations on the inner and
+		 * outer side of the join, but we don't know which is which, so we
+		 * have to decide using min_righthand (in) and min_lefthand (out).
+		 *
+		 * XXX This feature is enforced in find_matching_foreign_keys().
+		 */
+		if (bms_is_member(info->src_relid, sjinfo->min_righthand))
+		{
+			inner_rel = find_base_rel(root, info->src_relid);
+			outer_rel = find_base_rel(root, info->dst_relid);
+			ntuples = outer_rel->tuples;
+		}
+		else
+		{
+			inner_rel = find_base_rel(root, info->dst_relid);
+			outer_rel = find_base_rel(root, info->src_relid);
+			ntuples = inner_rel->tuples;
+		}
+
+		/* XXX this needs more thought I guess */
+		if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+			sel *= Min(outer_rel->tuples / inner_rel->tuples, 1.0);
+		else
+			sel *= 1.0 / Max(ntuples, 1.0);
+	}
+
+	return sel * clauselist_selectivity(root, remaining, 0, jointype, sjinfo);
+}
+
+/*
  * calc_joinrel_size_estimate
  *		Workhorse for set_joinrel_size_estimates and
  *		get_parameterized_joinrel_size.
@@ -3933,11 +4146,11 @@ calc_joinrel_size_estimate(PlannerInfo *root,
 		}
 
 		/* Get the separate selectivities */
-		jselec = clauselist_selectivity(root,
-										joinquals,
-										0,
-										jointype,
-										sjinfo);
+		jselec = clauselist_join_selectivity(root,
+											 joinquals,
+											 jointype,
+											 sjinfo);
+
 		pselec = clauselist_selectivity(root,
 										pushedquals,
 										0,
@@ -3950,11 +4163,10 @@ calc_joinrel_size_estimate(PlannerInfo *root,
 	}
 	else
 	{
-		jselec = clauselist_selectivity(root,
-										restrictlist,
-										0,
-										jointype,
-										sjinfo);
+		jselec = clauselist_join_selectivity(root,
+											 restrictlist,
+											 jointype,
+											 sjinfo);
 		pselec = 0.0;			/* not used, keep compiler quiet */
 	}
 
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index edd95d8..0d824e2 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -170,6 +170,17 @@ query_planner(PlannerInfo *root, List *tlist,
 	generate_base_implied_equalities(root);
 
 	/*
+	 * Fetch information about foreign keys potentially useful for cardinality
+	 * estimation (i.e. only those with both sides referenced in the query).
+	 */
+	collect_foreign_keys(root);
+
+	/*
+	 * Match foreign keys to eclasses and quals (mark satisfied conditions).
+	 */
+	match_foreign_keys_to_quals(root);
+
+	/*
 	 * We have completed merging equivalence sets, so it's now possible to
 	 * generate pathkeys in canonical form; so compute query_pathkeys and
 	 * other pathkeys fields in PlannerInfo.
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 6aa8192..2d2eaaf 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -41,6 +41,7 @@
 #include "rewrite/rewriteManip.h"
 #include "storage/bufmgr.h"
 #include "utils/lsyscache.h"
+#include "utils/syscache.h"
 #include "utils/rel.h"
 #include "utils/snapmgr.h"
 
@@ -391,6 +392,17 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 
 	rel->indexlist = indexinfos;
 
+	/*
+	 * Load foreign key data. Note this is the definitional data from the
+	 * catalog only and does not lock the referenced tables here. The
+	 * precise definition of the FK is important and may affect the usage
+	 * elsewhere in the planner, e.g. if the constraint is deferred or
+	 * if the constraint is not valid then relying upon this in the executor
+	 * may not be accurate, though might be considered a useful estimate for
+	 * planning purposes.
+	 */
+	rel->fkeylist = RelationGetFKeyList(relation);
+
 	/* Grab foreign-table info using the relcache, while we have it */
 	if (relation->rd_rel->relkind == RELKIND_FOREIGN_TABLE)
 	{
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index ba185ae..2349937 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -81,6 +81,311 @@ setup_simple_rel_arrays(PlannerInfo *root)
 }
 
 /*
+ * collect_foreign_keys
+ *	  fetch info about foreign keys applicable to join estimation
+ *
+ * Builds a list of foreign keys potentially usable for join cardinality
+ * estimation. We only keep foreign keys where both tables are present in
+ * the query. We only care about foreign keys with multiple columns, so
+ * keys with a single column are simply skipped.
+ *
+ * When building the list, we also replace the OIDs with relids, so that
+ * we can match the keys to eclasses/quals later (which use relids). This
+ * also means that if a relation has multiple RTEs (e.g. in a self-join),
+ * we will create multiple copies of the foreign key, one for each RTE.
+ *
+ * FIXME Perhaps this should further optimize the case with a single base
+ * relation (when there are no joins). Sadly we can't use all_baserels here
+ * because that's computed in make_one_rel() and that's too late. So we'd
+ * have to walk through the rels just like now, and count the baserels on
+ * our own. Which we kinda do anyway already.
+ */
+void
+collect_foreign_keys(PlannerInfo *root)
+{
+	List	   *reloids;
+	Index		rti, rti1, rti2;
+
+	/*
+	 * Let's compile a list of OIDs of tables, so that we can optimize the
+	 * case with many foreign keys a bit.
+	 */
+	reloids = NIL;
+	for (rti = 1; rti < root->simple_rel_array_size; rti++)
+	{
+		RelOptInfo	   *rel = root->simple_rel_array[rti];
+		RangeTblEntry  *rte = root->simple_rte_array[rti];
+
+		if (rel == NULL)	/* empty slot for non-baserel RTEs */
+			continue;
+
+		Assert(rel->relid == rti);		/* sanity check on array */
+
+		/* ignore RTEs that are "other rels" or not relations */
+		if ((rel->reloptkind != RELOPT_BASEREL) ||
+			(rel->rtekind != RTE_RELATION))
+			continue;
+
+		reloids = list_append_unique_oid(reloids, rte->relid);
+	}
+
+	/*
+	 * Identify foreign keys referencing pairs of base relations in query.
+	 *
+	 * The code is optimized for possibly large number of foreign keys, so
+	 * it only walks through each fkeylist once. It skips foreign keys on
+	 * a single column and foreign keys where the other relation is not in
+	 * the query (detected using the OID list compiled above).
+	 */
+	for (rti1 = 1; rti1 < root->simple_rel_array_size; rti1++)
+	{
+		ListCell	   *lc;
+		RelOptInfo	   *rel1 = root->simple_rel_array[rti1];
+		RangeTblEntry  *rte1 = root->simple_rte_array[rti1];
+
+		/* there may be empty slots corresponding to non-baserel RTEs */
+		if (rel1 == NULL)
+			continue;
+
+		/* sanity check on array */
+		Assert(rel1->relid == rti1);
+
+		/* ignore rel types that can't have foreign keys */
+		if ((rel1->reloptkind != RELOPT_BASEREL) ||
+			(rel1->rtekind != RTE_RELATION))
+			continue;
+
+		/* sanity check */
+		Assert(rte1 != NULL);
+
+		/* we only check one direction here */
+		foreach(lc, rel1->fkeylist)
+		{
+			ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+
+			/*
+			 * Skip foreign keys on a single column, as those are not useful
+			 * for join cardinality estimation (which is about improving
+			 * estimates for multi-column keys).
+			 */
+			if (fkinfo->nkeys == 1)
+				continue;
+
+			/* Check if the other side of the foreign key is in the query. */
+			if (! list_member_oid(reloids, fkinfo->confrelid))
+				continue;
+
+			/* We need to build both (rti1 < rti2) and (rti2 < rti1) here. */
+			for (rti2 = 1; rti2 < root->simple_rel_array_size; rti2++)
+			{
+				RelOptInfo	   *rel2 = root->simple_rel_array[rti2];
+				RangeTblEntry  *rte2 = root->simple_rte_array[rti2];
+
+				/* we never join a RTE to itself */
+				if (rti1 == rti2)
+					continue;
+
+				/* there may be empty slots corresponding to non-baserel RTEs */
+				if (rel2 == NULL)
+					continue;
+
+				/* sanity check on array */
+				Assert(rel2->relid == rti2);
+
+				/* ignore rel types that can't have foreign keys */
+				if ((rel2->reloptkind != RELOPT_BASEREL) ||
+					(rel2->rtekind != RTE_RELATION))
+					continue;
+
+				/* sanity check */
+				Assert(rte2 != NULL);
+
+				/*
+				 * We only need to check confrelid, as conrelid is the current
+				 * relation, so it's implicitly satisfied.
+				 */
+				if (fkinfo->confrelid == rte2->relid)
+				{
+					/* build a struct with relids instead of OIDs */
+					FKInfo *info = makeNode(FKInfo);
+
+					info->src_relid = rti1;
+					info->dst_relid = rti2;
+
+					info->nkeys = fkinfo->nkeys;
+
+					/* XXX Are pointers back to relcache OK, or do we need a copy? */
+					info->conkeys = fkinfo->conkeys;
+					info->confkeys = fkinfo->confkeys;
+					info->conpfeqop = fkinfo->conpfeqop;
+
+					info->eclass = (EquivalenceClass **)palloc0(info->nkeys * sizeof(EquivalenceClass*));
+					info->rinfos = (List **)palloc0(info->nkeys * sizeof(List *));
+
+					root->foreign_keys = lappend(root->foreign_keys, info);
+				}
+			}
+		}
+	}
+}
+
+/*
+ * match_foreign_keys_to_quals
+ *	  identify foreign key conditions satisfied by eclasses or regular quals
+ *
+ * For each foreign key we walk through all equivalence classes and try to
+ * match them to the foreign key conditions. Later when matching quals to
+ * keys we can count those conditions as matched.
+ *
+ * Then we try to do the same with foreign keys and regular join conditions
+ * (in RTE->joininfo). Currently this is a separate loop over foreign_keys,
+ * but it might as well be merged into the eclass one.
+ */
+void
+match_foreign_keys_to_quals(PlannerInfo *root)
+{
+	ListCell *lc;
+
+	/* if there are no eclasses or foreign keys, bail out immediately */
+	if ((root->foreign_keys == NIL) || (root->eq_classes == NIL))
+		return;
+
+	/* walk through the foreign keys once, and check them against eclasses */
+	foreach(lc, root->foreign_keys)
+	{
+		int		i;
+		FKInfo *info = (FKInfo *) lfirst(lc);
+
+		/* try to match FK conditions to an equivalence class */
+		for (i = 0; i < info->nkeys; i++)
+		{
+			ListCell   *lc2;
+
+			foreach(lc2, root->eq_classes)
+			{
+				ListCell *lc3;
+				EquivalenceClass   *ec = (EquivalenceClass *) lfirst(lc2);
+				int foundvarmask = 0;
+
+				foreach(lc3, ec->ec_members)
+				{
+					EquivalenceMember *em = (EquivalenceMember *) lfirst(lc3);
+					Var *var = (Var *) em->em_expr;
+
+					/* we can only use simple (Var = Var) eclasses for FKs */
+					if (!IsA(var, Var))
+						continue;
+
+					/* check which side of the foreign key is satisfied */
+					if (info->src_relid == var->varno &&
+						info->conkeys[i] == var->varattno)
+						foundvarmask |= 1;
+
+					else if (info->dst_relid == var->varno &&
+						info->confkeys[i] == var->varattno)
+						foundvarmask |= 2;
+
+					/*
+					 * Check if we've found both matches in the same equivalence
+					 * class, we can mark it accordingly.
+					 */
+					if (foundvarmask == 3)
+					{
+						info->eclass[i] = ec;
+						break;
+					}
+				}
+
+				/*
+				 * If we have just matched this part of the FK, we're done (no
+				 * need to try the other eclasses)
+				 */
+				if (info->eclass[i] != NULL)
+					break;
+			}
+		}
+	}
+
+	/* now also match the fkeys to regular join conditions */
+	foreach(lc, root->foreign_keys)
+	{
+		ListCell *lc2;
+		FKInfo *info = (FKInfo *) lfirst(lc);
+
+		RelOptInfo	*rel = root->simple_rel_array[info->src_relid];
+
+		foreach (lc2, rel->joininfo)
+		{
+			RestrictInfo   *rinfo;
+			OpExpr		   *clause;
+			Var			   *leftvar;
+			Var			   *rightvar;
+
+			rinfo = (RestrictInfo *) lfirst(lc2);
+
+			Assert(IsA(rinfo, RestrictInfo));		/* sanity check */
+
+			/*
+			 * XXX should we skip rinfo with parent_ec here (EC clauses are
+			 * already matched in the preceding loop)?
+			 */
+
+			clause = (OpExpr *) rinfo->clause;
+
+			/* only OpExprs are useful for consideration */
+			if (!IsA(clause, OpExpr))
+				continue;
+
+			leftvar = (Var *) get_leftop((Expr *) clause);
+			rightvar = (Var *) get_rightop((Expr *) clause);
+
+			/* Foreign keys only support Vars, so ignore anything more complex */
+			if (!IsA(leftvar, Var) || !IsA(rightvar, Var))
+				continue;
+
+			/* now try to match the vars to the current foreign key */
+			if ((info->src_relid == leftvar->varno) &&
+				(info->dst_relid == rightvar->varno))
+			{
+				int i;
+				for (i = 0; i < info->nkeys; i++)
+				{
+					/*
+					 * If the operator does not match the FK, there's no point
+					 * in checking the operands.
+					 */
+					if (clause->opno != info->conpfeqop[i])
+						continue;
+
+					if ((info->conkeys[i] == leftvar->varattno) &&
+						(info->confkeys[i] == rightvar->varattno))
+						info->rinfos[i] = lappend(info->rinfos[i], rinfo);
+				}
+			}
+			else if ((info->src_relid == rightvar->varno) &&
+					 (info->dst_relid == leftvar->varno))
+			{
+				int i;
+				for (i = 0; i < info->nkeys; i++)
+				{
+					/*
+					 * If the operator does not match the FK, there's no point
+					 * in checking the operands.
+					 */
+					if (clause->opno != info->conpfeqop[i])
+						continue;
+
+					if ((info->conkeys[i] == rightvar->varattno) &&
+						(info->confkeys[i] == leftvar->varattno))
+						info->rinfos[i] = lappend(info->rinfos[i], rinfo);
+				}
+			}
+		}
+	}
+}
+
+
+/*
  * build_simple_rel
  *	  Construct a new RelOptInfo for a base relation or 'other' relation.
  */
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index c958758..37bcee2 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -2031,6 +2031,7 @@ RelationDestroyRelation(Relation relation, bool remember_tupdesc)
 			FreeTupleDesc(relation->rd_att);
 	}
 	list_free(relation->rd_indexlist);
+	list_free(relation->rd_fkeylist);
 	bms_free(relation->rd_indexattr);
 	bms_free(relation->rd_keyattr);
 	bms_free(relation->rd_idattr);
@@ -3957,6 +3958,139 @@ RelationGetIndexList(Relation relation)
 }
 
 /*
+ * RelationGetFKeyList -- get a list of foreign key oids
+ *
+ * Use an index scan on pg_constraint to load in FK definitions,
+ * intended for use within the planner, not for enforcing FKs.
+ *
+ * Data is ordered by Oid, though this is not critical at this point
+ * since we do not lock the referenced relations.
+ */
+List *
+RelationGetFKeyList(Relation relation)
+{
+	Relation	conrel;
+	SysScanDesc conscan;
+	ScanKeyData skey;
+	HeapTuple	htup;
+	List	   *result;
+	List	   *oldlist;
+	MemoryContext oldcxt;
+
+	/* Quick exit if we already computed the list. */
+	if (relation->rd_fkeylist)
+		return list_copy(relation->rd_fkeylist);
+
+	/* Fast path if no FKs... if it doesn't have a trigger, it can't have a FK */
+	if (!relation->rd_rel->relhastriggers)
+		return NIL;
+	/*
+	 * We build the list we intend to return (in the caller's context) while
+	 * doing the scan.  After successfully completing the scan, we copy that
+	 * list into the relcache entry.  This avoids cache-context memory leakage
+	 * if we get some sort of error partway through.
+	 */
+	result = NIL;
+
+	/* Prepare to scan pg_constraint for entries having conrelid = this rel. */
+	ScanKeyInit(&skey,
+				Anum_pg_constraint_conrelid,
+				BTEqualStrategyNumber, F_OIDEQ,
+				ObjectIdGetDatum(RelationGetRelid(relation)));
+
+	conrel = heap_open(ConstraintRelationId, AccessShareLock);
+	conscan = systable_beginscan(conrel, ConstraintRelidIndexId, true,
+								 NULL, 1, &skey);
+
+	while (HeapTupleIsValid(htup = systable_getnext(conscan)))
+	{
+		Form_pg_constraint constraint = (Form_pg_constraint) GETSTRUCT(htup);
+
+		ForeignKeyOptInfo *info;
+		Datum		adatum;
+		bool		isnull;
+		ArrayType  *arr;
+		int			numkeys;
+		int			i;
+
+		/* return only foreign keys */
+		if (constraint->contype != CONSTRAINT_FOREIGN)
+			continue;
+
+		/* lookup number of keys first, and allocate all the pieces at once */
+		adatum = SysCacheGetAttr(CONSTROID, htup,
+									Anum_pg_constraint_conkey, &isnull);
+		Assert(!isnull);
+
+		arr = DatumGetArrayTypeP(adatum);
+		numkeys = ARR_DIMS(arr)[0];
+
+		oldcxt = MemoryContextSwitchTo(CacheMemoryContext);
+
+		info = makeNode(ForeignKeyOptInfo);
+
+		info->nkeys = numkeys;
+		info->conrelid = constraint->conrelid;
+		info->confrelid = constraint->confrelid;
+
+		info->conkeys = (int*)palloc(numkeys * sizeof(int));
+		info->confkeys = (int*)palloc(numkeys * sizeof(int));
+		info->conpfeqop = (Oid*)palloc(numkeys * sizeof(Oid));
+
+		MemoryContextSwitchTo(oldcxt);
+
+		/* conkey */
+		for (i = 0; i < numkeys; i++)
+			info->conkeys[i] = ((int16 *) ARR_DATA_PTR(arr))[i];
+
+		/* confkey */
+		adatum = SysCacheGetAttr(CONSTROID, htup,
+									Anum_pg_constraint_confkey, &isnull);
+		Assert(!isnull);
+
+		arr = DatumGetArrayTypeP(adatum);
+		Assert(numkeys == ARR_DIMS(arr)[0]);
+
+		for (i = 0; i < numkeys; i++)
+			info->confkeys[i] = ((int16 *) ARR_DATA_PTR(arr))[i];
+
+		/* conpfeqop */
+		adatum = SysCacheGetAttr(CONSTROID, htup,
+									Anum_pg_constraint_conpfeqop, &isnull);
+		Assert(!isnull);
+
+		arr = DatumGetArrayTypeP(adatum);
+		Assert(numkeys == ARR_DIMS(arr)[0]);
+
+		for (i = 0; i < numkeys; i++)
+			info->conpfeqop[i] = ((Oid *) ARR_DATA_PTR(arr))[i];
+
+		/* Add FK's node to the result list */
+		result = lappend(result, info);
+	}
+
+	systable_endscan(conscan);
+
+	heap_close(conrel, AccessShareLock);
+
+	/* Now save a copy of the completed list in the relcache entry. */
+	oldcxt = MemoryContextSwitchTo(CacheMemoryContext);
+	oldlist = relation->rd_fkeylist;
+	relation->rd_fkeylist = list_copy(result);
+	MemoryContextSwitchTo(oldcxt);
+
+	/*
+	 * Don't leak the old list, if there is one
+	 *
+	 * FIXME This is insufficient, as it only frees the list, not the contents
+	 * (so we end up with old ForeignKeyOptInto entries).
+	 */
+	list_free(oldlist);
+
+	return result;
+}
+
+/*
  * insert_ordered_oid
  *		Insert a new Oid into a sorted list of Oids, preserving ordering
  *
@@ -4920,6 +5054,7 @@ load_relcache_init_file(bool shared)
 		rel->rd_indexattr = NULL;
 		rel->rd_keyattr = NULL;
 		rel->rd_idattr = NULL;
+		rel->rd_fkeylist = NIL;
 		rel->rd_createSubid = InvalidSubTransactionId;
 		rel->rd_newRelfilenodeSubid = InvalidSubTransactionId;
 		rel->rd_amcache = NULL;
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index c4b9c14..1f71031 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -223,6 +223,8 @@ typedef enum NodeTag
 	T_PlannerGlobal,
 	T_RelOptInfo,
 	T_IndexOptInfo,
+	T_ForeignKeyOptInfo,
+	T_FKInfo,
 	T_ParamPathInfo,
 	T_Path,
 	T_IndexPath,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index a4892cb..2b5fc2a 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -303,6 +303,10 @@ typedef struct PlannerInfo
 
 	/* optional private data for join_search_hook, e.g., GEQO */
 	void	   *join_search_private;
+
+	/* list of foreign keys potentially useful for join estimation */
+	List	   *foreign_keys;
+
 } PlannerInfo;
 
 
@@ -516,6 +520,7 @@ typedef struct RelOptInfo
 	List	   *lateral_vars;	/* LATERAL Vars and PHVs referenced by rel */
 	Relids		lateral_referencers;	/* rels that reference me laterally */
 	List	   *indexlist;		/* list of IndexOptInfo */
+	List	   *fkeylist;			/* list of ForeignKeyOptInfo */
 	BlockNumber pages;			/* size estimates derived from pg_class */
 	double		tuples;
 	double		allvisfrac;
@@ -724,6 +729,49 @@ typedef struct EquivalenceMember
 } EquivalenceMember;
 
 /*
+ * ForeignKeyOptInfo
+ *		Per-foreign-key information for planning/optimization
+ *
+ * Only includes columns from pg_constraint related to foreign keys.
+ *
+ * conkeys[], confkeys[] and conpfeqop[] each have nkeys entries.
+ */
+typedef struct ForeignKeyOptInfo
+{
+	NodeTag		type;
+
+	Oid			conrelid;	/* relation constrained by the foreign key */
+	Oid			confrelid;	/* relation referenced by the foreign key */
+
+	int			nkeys;		/* number of columns in the foreign key */
+	int		   *conkeys;	/* attnums of columns in the constrained table */
+	int		   *confkeys;	/* attnums of columns in the referenced table */
+	Oid		   *conpfeqop;	/* OIDs of equality operators used by the FK */
+
+} ForeignKeyOptInfo;
+
+/* only used in planner when matching foreign keys to conditions/eclasses */
+typedef struct FKInfo
+{
+	NodeTag		type;
+
+	Index		src_relid;	/* relid of the source relation (conrelid) */
+	Index		dst_relid;	/* relid of the target relation (confrelid) */
+
+	int			nkeys;		/* number of columns in the foreign key */
+	int			nmatched;	/* number of conditions matched */
+	int		   *conkeys;	/* attnums of columns in the constrained table */
+	int		   *confkeys;	/* attnums of columns in the referenced table */
+	Oid		   *conpfeqop;	/* OIDs of equality operators used by the FK */
+
+	/* used in costsize.c */
+	EquivalenceClass **eclass;	/* pointer to eclass matching the condition */
+	List			 **rinfos;	/* list of non-EC clauses matched to key */
+
+} FKInfo;
+
+
+/*
  * PathKeys
  *
  * The sort ordering of a path is represented by a list of PathKey nodes.
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 5de4c34..8cd5762 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -236,6 +236,8 @@ extern Path *reparameterize_path(PlannerInfo *root, Path *path,
  * prototypes for relnode.c
  */
 extern void setup_simple_rel_arrays(PlannerInfo *root);
+extern void collect_foreign_keys(PlannerInfo *root);
+extern void match_foreign_keys_to_quals(PlannerInfo *root);
 extern RelOptInfo *build_simple_rel(PlannerInfo *root, int relid,
 				 RelOptKind reloptkind);
 extern RelOptInfo *find_base_rel(PlannerInfo *root, int relid);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index f3b25e2..e0ac451 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -76,6 +76,8 @@ extern Expr *adjust_rowcompare_for_index(RowCompareExpr *clause,
 							int indexcol,
 							List **indexcolnos,
 							bool *var_on_left_p);
+extern bool has_matching_fkey(RelOptInfo *rel, RelOptInfo *frel, List *clauses,
+							  bool reverse);
 
 /*
  * tidpath.h
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index fd858fd..d00a765 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -95,6 +95,9 @@ typedef struct RelationData
 	Oid			rd_oidindex;	/* OID of unique index on OID, if any */
 	Oid			rd_replidindex; /* OID of replica identity index, if any */
 
+	/* data managed by RelationGetFKList: */
+	List	   *rd_fkeylist;	/* list of ForeignKeyOptInfo entries */
+
 	/* data managed by RelationGetIndexAttrBitmap: */
 	Bitmapset  *rd_indexattr;	/* identifies columns used in indexes */
 	Bitmapset  *rd_keyattr;		/* cols that can be ref'd by foreign keys */
diff --git a/src/include/utils/relcache.h b/src/include/utils/relcache.h
index 1b48304..7f07c26 100644
--- a/src/include/utils/relcache.h
+++ b/src/include/utils/relcache.h
@@ -38,6 +38,7 @@ extern void RelationClose(Relation relation);
  * Routines to compute/retrieve additional cached information
  */
 extern List *RelationGetIndexList(Relation relation);
+extern List *RelationGetFKeyList(Relation relation);
 extern Oid	RelationGetOidIndex(Relation relation);
 extern Oid	RelationGetReplicaIndex(Relation relation);
 extern List *RelationGetIndexExpressions(Relation relation);
diff --git a/src/test/regress/expected/rangefuncs.out b/src/test/regress/expected/rangefuncs.out
index 00ef421..6b2ec7f 100644
--- a/src/test/regress/expected/rangefuncs.out
+++ b/src/test/regress/expected/rangefuncs.out
@@ -1,18 +1,18 @@
 SELECT name, setting FROM pg_settings WHERE name LIKE 'enable%';
-         name         | setting 
-----------------------+---------
- enable_bitmapscan    | on
- enable_hashagg       | on
- enable_hashjoin      | on
- enable_indexonlyscan | on
- enable_indexscan     | on
- enable_material      | on
- enable_mergejoin     | on
- enable_nestloop      | on
- enable_seqscan       | on
- enable_sort          | on
- enable_tidscan       | on
-(11 rows)
+         name          | setting 
+-----------------------+---------
+ enable_bitmapscan     | on
+ enable_hashagg        | on
+ enable_hashjoin       | on
+ enable_indexonlyscan  | on
+ enable_indexscan      | on
+ enable_material       | on
+ enable_mergejoin      | on
+ enable_nestloop       | on
+ enable_seqscan        | on
+ enable_sort           | on
+ enable_tidscan        | on
+(12 rows)
 
 CREATE TABLE foo2(fooid int, f2 int);
 INSERT INTO foo2 VALUES(1, 11);

diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
index 08ed990..8e5b33c 100644
*** a/src/backend/nodes/copyfuncs.c
--- b/src/backend/nodes/copyfuncs.c
***************
*** 27,32 ****
--- 27,33 ----
  #include "nodes/plannodes.h"
  #include "nodes/relation.h"
  #include "utils/datum.h"
+ #include "utils/rel.h"
  
  
  /*
*************** _copyValue(const Value *from)
*** 4252,4257 ****
--- 4253,4276 ----
  	return newnode;
  }
  
+ 
+ static ForeignKeyCacheInfo *
+ _copyForeignKeyCacheInfo(const ForeignKeyCacheInfo *from)
+ {
+ 	ForeignKeyCacheInfo *newnode = makeNode(ForeignKeyCacheInfo);
+ 
+ 	COPY_SCALAR_FIELD(conrelid);
+ 	COPY_SCALAR_FIELD(confrelid);
+ 	COPY_SCALAR_FIELD(nkeys);
+ 	/* COPY_SCALAR_FIELD might work for these, but let's not assume that */
+ 	memcpy(newnode->conkey, from->conkey, sizeof(newnode->conkey));
+ 	memcpy(newnode->confkey, from->confkey, sizeof(newnode->confkey));
+ 	memcpy(newnode->conpfeqop, from->conpfeqop, sizeof(newnode->conpfeqop));
+ 
+ 	return newnode;
+ }
+ 
+ 
  /*
   * copyObject
   *
*************** copyObject(const void *from)
*** 5050,5055 ****
--- 5069,5081 ----
  			retval = _copyRoleSpec(from);
  			break;
  
+ 			/*
+ 			 * MISCELLANEOUS NODES
+ 			 */
+ 		case T_ForeignKeyCacheInfo:
+ 			retval = _copyForeignKeyCacheInfo(from);
+ 			break;
+ 
  		default:
  			elog(ERROR, "unrecognized node type: %d", (int) nodeTag(from));
  			retval = 0;			/* keep compiler quiet */
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index c7b4153..eaaa370 100644
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
***************
*** 30,35 ****
--- 30,36 ----
  #include "nodes/plannodes.h"
  #include "nodes/relation.h"
  #include "utils/datum.h"
+ #include "utils/rel.h"
  
  
  /*
*************** _outPlannerInfo(StringInfo str, const Pl
*** 2048,2053 ****
--- 2049,2055 ----
  	WRITE_NODE_FIELD(append_rel_list);
  	WRITE_NODE_FIELD(rowMarks);
  	WRITE_NODE_FIELD(placeholder_list);
+ 	WRITE_NODE_FIELD(fkey_list);
  	WRITE_NODE_FIELD(query_pathkeys);
  	WRITE_NODE_FIELD(group_pathkeys);
  	WRITE_NODE_FIELD(window_pathkeys);
*************** _outIndexOptInfo(StringInfo str, const I
*** 2138,2143 ****
--- 2140,2174 ----
  }
  
  static void
+ _outForeignKeyOptInfo(StringInfo str, const ForeignKeyOptInfo *node)
+ {
+ 	int			i;
+ 
+ 	WRITE_NODE_TYPE("FOREIGNKEYOPTINFO");
+ 
+ 	WRITE_UINT_FIELD(con_relid);
+ 	WRITE_UINT_FIELD(ref_relid);
+ 	WRITE_INT_FIELD(nkeys);
+ 	appendStringInfoString(str, " :conkey");
+ 	for (i = 0; i < node->nkeys; i++)
+ 		appendStringInfo(str, " %d", node->conkey[i]);
+ 	appendStringInfoString(str, " :confkey");
+ 	for (i = 0; i < node->nkeys; i++)
+ 		appendStringInfo(str, " %d", node->confkey[i]);
+ 	appendStringInfoString(str, " :conpfeqop");
+ 	for (i = 0; i < node->nkeys; i++)
+ 		appendStringInfo(str, " %u", node->conpfeqop[i]);
+ 	WRITE_INT_FIELD(nmatched);
+ 	/* for compactness, just print the number of matches per column: */
+ 	appendStringInfoString(str, " :eclass");
+ 	for (i = 0; i < node->nkeys; i++)
+ 		appendStringInfo(str, " %d", (node->eclass[i] != NULL));
+ 	appendStringInfoString(str, " :rinfos");
+ 	for (i = 0; i < node->nkeys; i++)
+ 		appendStringInfo(str, " %d", list_length(node->rinfos[i]));
+ }
+ 
+ static void
  _outEquivalenceClass(StringInfo str, const EquivalenceClass *node)
  {
  	/*
*************** _outConstraint(StringInfo str, const Con
*** 3207,3212 ****
--- 3238,3264 ----
  	}
  }
  
+ static void
+ _outForeignKeyCacheInfo(StringInfo str, const ForeignKeyCacheInfo *node)
+ {
+ 	int			i;
+ 
+ 	WRITE_NODE_TYPE("FOREIGNKEYCACHEINFO");
+ 
+ 	WRITE_OID_FIELD(conrelid);
+ 	WRITE_OID_FIELD(confrelid);
+ 	WRITE_INT_FIELD(nkeys);
+ 	appendStringInfoString(str, " :conkey");
+ 	for (i = 0; i < node->nkeys; i++)
+ 		appendStringInfo(str, " %d", node->conkey[i]);
+ 	appendStringInfoString(str, " :confkey");
+ 	for (i = 0; i < node->nkeys; i++)
+ 		appendStringInfo(str, " %d", node->confkey[i]);
+ 	appendStringInfoString(str, " :conpfeqop");
+ 	for (i = 0; i < node->nkeys; i++)
+ 		appendStringInfo(str, " %u", node->conpfeqop[i]);
+ }
+ 
  
  /*
   * outNode -
*************** outNode(StringInfo str, const void *obj)
*** 3607,3612 ****
--- 3659,3667 ----
  			case T_IndexOptInfo:
  				_outIndexOptInfo(str, obj);
  				break;
+ 			case T_ForeignKeyOptInfo:
+ 				_outForeignKeyOptInfo(str, obj);
+ 				break;
  			case T_EquivalenceClass:
  				_outEquivalenceClass(str, obj);
  				break;
*************** outNode(StringInfo str, const void *obj)
*** 3783,3788 ****
--- 3838,3846 ----
  			case T_XmlSerialize:
  				_outXmlSerialize(str, obj);
  				break;
+ 			case T_ForeignKeyCacheInfo:
+ 				_outForeignKeyCacheInfo(str, obj);
+ 				break;
  
  			default:
  
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index e7f63f4..7ea6d57 100644
*** a/src/backend/optimizer/path/costsize.c
--- b/src/backend/optimizer/path/costsize.c
*************** static bool has_indexed_join_quals(NestP
*** 147,156 ****
--- 147,163 ----
  static double approx_tuple_count(PlannerInfo *root, JoinPath *path,
  				   List *quals);
  static double calc_joinrel_size_estimate(PlannerInfo *root,
+ 						   RelOptInfo *outer_rel,
+ 						   RelOptInfo *inner_rel,
  						   double outer_rows,
  						   double inner_rows,
  						   SpecialJoinInfo *sjinfo,
  						   List *restrictlist);
+ static Selectivity get_foreign_key_join_selectivity(PlannerInfo *root,
+ 								 Relids outer_relids,
+ 								 Relids inner_relids,
+ 								 SpecialJoinInfo *sjinfo,
+ 								 List **restrictlist);
  static void set_rel_width(PlannerInfo *root, RelOptInfo *rel);
  static double relation_byte_size(double tuples, int width);
  static double page_size(double tuples, int width);
*************** set_joinrel_size_estimates(PlannerInfo *
*** 3837,3842 ****
--- 3844,3851 ----
  						   List *restrictlist)
  {
  	rel->rows = calc_joinrel_size_estimate(root,
+ 										   outer_rel,
+ 										   inner_rel,
  										   outer_rel->rows,
  										   inner_rel->rows,
  										   sjinfo,
*************** set_joinrel_size_estimates(PlannerInfo *
*** 3848,3855 ****
   *		Make a size estimate for a parameterized scan of a join relation.
   *
   * 'rel' is the joinrel under consideration.
!  * 'outer_rows', 'inner_rows' are the sizes of the (probably also
!  *		parameterized) join inputs under consideration.
   * 'sjinfo' is any SpecialJoinInfo relevant to this join.
   * 'restrict_clauses' lists the join clauses that need to be applied at the
   * join node (including any movable clauses that were moved down to this join,
--- 3857,3864 ----
   *		Make a size estimate for a parameterized scan of a join relation.
   *
   * 'rel' is the joinrel under consideration.
!  * 'outer_path', 'inner_path' are (probably also parameterized) Paths that
!  *		produce the relations being joined.
   * 'sjinfo' is any SpecialJoinInfo relevant to this join.
   * 'restrict_clauses' lists the join clauses that need to be applied at the
   * join node (including any movable clauses that were moved down to this join,
*************** set_joinrel_size_estimates(PlannerInfo *
*** 3860,3867 ****
   */
  double
  get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
! 							   double outer_rows,
! 							   double inner_rows,
  							   SpecialJoinInfo *sjinfo,
  							   List *restrict_clauses)
  {
--- 3869,3876 ----
   */
  double
  get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
! 							   Path *outer_path,
! 							   Path *inner_path,
  							   SpecialJoinInfo *sjinfo,
  							   List *restrict_clauses)
  {
*************** get_parameterized_joinrel_size(PlannerIn
*** 3877,3884 ****
  	 * estimate for any pair with the same parameterization.
  	 */
  	nrows = calc_joinrel_size_estimate(root,
! 									   outer_rows,
! 									   inner_rows,
  									   sjinfo,
  									   restrict_clauses);
  	/* For safety, make sure result is not more than the base estimate */
--- 3886,3895 ----
  	 * estimate for any pair with the same parameterization.
  	 */
  	nrows = calc_joinrel_size_estimate(root,
! 									   outer_path->parent,
! 									   inner_path->parent,
! 									   outer_path->rows,
! 									   inner_path->rows,
  									   sjinfo,
  									   restrict_clauses);
  	/* For safety, make sure result is not more than the base estimate */
*************** get_parameterized_joinrel_size(PlannerIn
*** 3891,3905 ****
--- 3902,3923 ----
   * calc_joinrel_size_estimate
   *		Workhorse for set_joinrel_size_estimates and
   *		get_parameterized_joinrel_size.
+  *
+  * outer_rel/inner_rel are the relations being joined, but they should be
+  * assumed to have sizes outer_rows/inner_rows; those numbers might be less
+  * than what rel->rows says, when we are considering parameterized paths.
   */
  static double
  calc_joinrel_size_estimate(PlannerInfo *root,
+ 						   RelOptInfo *outer_rel,
+ 						   RelOptInfo *inner_rel,
  						   double outer_rows,
  						   double inner_rows,
  						   SpecialJoinInfo *sjinfo,
  						   List *restrictlist)
  {
  	JoinType	jointype = sjinfo->jointype;
+ 	Selectivity fkselec;
  	Selectivity jselec;
  	Selectivity pselec;
  	double		nrows;
*************** calc_joinrel_size_estimate(PlannerInfo *
*** 3910,3915 ****
--- 3928,3949 ----
  	 * double-counting them because they were not considered in estimating the
  	 * sizes of the component rels.
  	 *
+ 	 * First, see whether any of the joinclauses can be matched to known FK
+ 	 * constraints.  If so, drop those clauses from the restrictlist, and
+ 	 * instead estimate their selectivity using FK semantics.  (We do this
+ 	 * without regard to whether said clauses are local or "pushed down".
+ 	 * Probably, an FK-matching clause could never be seen as pushed down at
+ 	 * an outer join, since it would be strict and hence would be grounds for
+ 	 * join strength reduction.)  fkselec gets the net selectivity for
+ 	 * FK-matching clauses, or 1.0 if there are none.
+ 	 */
+ 	fkselec = get_foreign_key_join_selectivity(root,
+ 											   outer_rel->relids,
+ 											   inner_rel->relids,
+ 											   sjinfo,
+ 											   &restrictlist);
+ 
+ 	/*
  	 * For an outer join, we have to distinguish the selectivity of the join's
  	 * own clauses (JOIN/ON conditions) from any clauses that were "pushed
  	 * down".  For inner joins we just count them all as joinclauses.
*************** calc_joinrel_size_estimate(PlannerInfo *
*** 3973,3988 ****
  	switch (jointype)
  	{
  		case JOIN_INNER:
! 			nrows = outer_rows * inner_rows * jselec;
  			break;
  		case JOIN_LEFT:
! 			nrows = outer_rows * inner_rows * jselec;
  			if (nrows < outer_rows)
  				nrows = outer_rows;
  			nrows *= pselec;
  			break;
  		case JOIN_FULL:
! 			nrows = outer_rows * inner_rows * jselec;
  			if (nrows < outer_rows)
  				nrows = outer_rows;
  			if (nrows < inner_rows)
--- 4007,4023 ----
  	switch (jointype)
  	{
  		case JOIN_INNER:
! 			nrows = outer_rows * inner_rows * fkselec * jselec;
! 			/* pselec not used */
  			break;
  		case JOIN_LEFT:
! 			nrows = outer_rows * inner_rows * fkselec * jselec;
  			if (nrows < outer_rows)
  				nrows = outer_rows;
  			nrows *= pselec;
  			break;
  		case JOIN_FULL:
! 			nrows = outer_rows * inner_rows * fkselec * jselec;
  			if (nrows < outer_rows)
  				nrows = outer_rows;
  			if (nrows < inner_rows)
*************** calc_joinrel_size_estimate(PlannerInfo *
*** 3990,4000 ****
  			nrows *= pselec;
  			break;
  		case JOIN_SEMI:
! 			nrows = outer_rows * jselec;
  			/* pselec not used */
  			break;
  		case JOIN_ANTI:
! 			nrows = outer_rows * (1.0 - jselec);
  			nrows *= pselec;
  			break;
  		default:
--- 4025,4035 ----
  			nrows *= pselec;
  			break;
  		case JOIN_SEMI:
! 			nrows = outer_rows * fkselec * jselec;
  			/* pselec not used */
  			break;
  		case JOIN_ANTI:
! 			nrows = outer_rows * (1.0 - fkselec * jselec);
  			nrows *= pselec;
  			break;
  		default:
*************** calc_joinrel_size_estimate(PlannerInfo *
*** 4008,4013 ****
--- 4043,4261 ----
  }
  
  /*
+  * get_foreign_key_join_selectivity
+  *		Estimate join selectivity for foreign-key-related clauses.
+  *
+  * Remove any clauses that can be matched to FK constraints from *restrictlist,
+  * and return a substitute estimate of their selectivity.  1.0 is returned
+  * when there are no such clauses.
+  *
+  * The reason for treating such clauses specially is that we can get better
+  * estimates this way than by relying on clauselist_selectivity(), especially
+  * for multi-column FKs where that function's assumption that the clauses are
+  * independent falls down badly.  But even with single-column FKs, we may be
+  * able to get a better answer when the pg_statistic stats are missing or out
+  * of date.
+  */
+ static Selectivity
+ get_foreign_key_join_selectivity(PlannerInfo *root,
+ 								 Relids outer_relids,
+ 								 Relids inner_relids,
+ 								 SpecialJoinInfo *sjinfo,
+ 								 List **restrictlist)
+ {
+ 	Selectivity fkselec = 1.0;
+ 	JoinType	jointype = sjinfo->jointype;
+ 	List	   *worklist = *restrictlist;
+ 	ListCell   *lc;
+ 
+ 	/* Consider each FK constraint that is known to match the query */
+ 	foreach(lc, root->fkey_list)
+ 	{
+ 		ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+ 		bool		ref_is_outer;
+ 		List	   *removedlist;
+ 		ListCell   *cell;
+ 		ListCell   *prev;
+ 		ListCell   *next;
+ 
+ 		/*
+ 		 * This FK is not relevant unless it connects a baserel on one side of
+ 		 * this join to a baserel on the other side.
+ 		 */
+ 		if (bms_is_member(fkinfo->con_relid, outer_relids) &&
+ 			bms_is_member(fkinfo->ref_relid, inner_relids))
+ 			ref_is_outer = false;
+ 		else if (bms_is_member(fkinfo->ref_relid, outer_relids) &&
+ 				 bms_is_member(fkinfo->con_relid, inner_relids))
+ 			ref_is_outer = true;
+ 		else
+ 			continue;
+ 
+ 		/*
+ 		 * Modify the restrictlist by removing clauses that match the FK (and
+ 		 * putting them into removedlist instead).  It seems unsafe to modify
+ 		 * the originally-passed List structure, so we make a shallow copy the
+ 		 * first time through.
+ 		 */
+ 		if (worklist == *restrictlist)
+ 			worklist = list_copy(worklist);
+ 
+ 		removedlist = NIL;
+ 		prev = NULL;
+ 		for (cell = list_head(worklist); cell; cell = next)
+ 		{
+ 			RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
+ 			bool		remove_it = false;
+ 			int			i;
+ 
+ 			next = lnext(cell);
+ 			/* Drop this clause if it matches any column of the FK */
+ 			for (i = 0; i < fkinfo->nkeys; i++)
+ 			{
+ 				if (rinfo->parent_ec)
+ 				{
+ 					/*
+ 					 * EC-derived clauses can only match by EC.  Note that
+ 					 * checking parent_ec is a bit of a cheat because there
+ 					 * are EC-derived clauses that don't have parent_ec set;
+ 					 * but such clauses must compare expressions that aren't
+ 					 * just Vars, so they cannot match the FK anyway.
+ 					 */
+ 					if (fkinfo->eclass[i] == rinfo->parent_ec)
+ 					{
+ 						remove_it = true;
+ 						break;
+ 					}
+ 				}
+ 				else
+ 				{
+ 					/* Otherwise, see if rinfo was previously matched to EC */
+ 					if (list_member_ptr(fkinfo->rinfos[i], rinfo))
+ 					{
+ 						remove_it = true;
+ 						break;
+ 					}
+ 				}
+ 			}
+ 			if (remove_it)
+ 			{
+ 				worklist = list_delete_cell(worklist, cell, prev);
+ 				removedlist = lappend(removedlist, rinfo);
+ 			}
+ 			else
+ 				prev = cell;
+ 		}
+ 
+ 		/*
+ 		 * If we failed to remove any matching clauses, chicken out and ignore
+ 		 * this FK; applying its selectivity might result in double-counting.
+ 		 * It's not obvious that this is correct, but remember that we already
+ 		 * know the FK matches query quals someplace.  There are just two
+ 		 * reasons we might fail to find matching clauses in this join:
+ 		 *
+ 		 * Some FK we matched earlier might have removed the relevant clause.
+ 		 * This is particularly likely with EC matches, since equivclass.c
+ 		 * provides only a single EC-derived clause per join.  But that means
+ 		 * we have something like A.R1 and B.R2 on one side of the join that
+ 		 * each reference C.PK on the other side, in which case applying the
+ 		 * selectivities of both FK constraints would be double-counting.
+ 		 *
+ 		 * Otherwise, if we didn't find the matching clause in this join, it
+ 		 * must be outerjoin-delayed and will be applied at some higher join
+ 		 * level.  Applying the FK's selectivity anyway would result in
+ 		 * underestimating both this join size and the higher join level's.
+ 		 *
+ 		 * For a multi-column FK, it's possible that we found matches to some
+ 		 * columns but not all, implying that one of the above effects applied
+ 		 * to just some of the columns.  For the moment, we go ahead and
+ 		 * remove those clauses and apply the FK's selectivity anyway.  It
+ 		 * might be better to put back the removed clauses and ignore the FK;
+ 		 * but that amounts to betting on independence of the clauses, which
+ 		 * doesn't seem like a good bet in such messy cases.
+ 		 */
+ 		if (removedlist == NIL)
+ 			continue;
+ 
+ 		/*
+ 		 * Finally we get to the payoff: estimate selectivity using the
+ 		 * knowledge that each referencing row will match exactly one row in
+ 		 * the referenced table.
+ 		 *
+ 		 * XXX that's not true in the presence of nulls in the referencing
+ 		 * column(s), so in principle we should derate the estimate for those.
+ 		 * However (1) if there are any strict restriction clauses for the
+ 		 * referencing column(s) elsewhere in the query, derating here would
+ 		 * be double-counting the null fraction, and (2) it's not very clear
+ 		 * how to combine null fractions for multiple referencing columns.
+ 		 *
+ 		 * In the first branch of the logic below, null derating is done
+ 		 * implicitly by relying on clause_selectivity(); in the other two
+ 		 * paths, we do nothing for now about correcting for nulls.
+ 		 *
+ 		 * XXX another point here is that if either side of an FK constraint
+ 		 * is an inheritance parent, we estimate as though the constraint
+ 		 * covers all its children as well.  This is not an unreasonable
+ 		 * assumption for a referencing table, ie the user probably applied
+ 		 * identical constraints to all child tables (though perhaps we ought
+ 		 * to check that).  But it's not possible to have done that for a
+ 		 * referenced table.  Fortunately, precisely because that doesn't
+ 		 * work, it is uncommon in practice to have an FK referencing a parent
+ 		 * table.  So, at least for now, disregard inheritance here.
+ 		 */
+ 		if (ref_is_outer && jointype != JOIN_INNER)
+ 		{
+ 			/*
+ 			 * When the referenced table is on the outer side of a non-inner
+ 			 * join, knowing that each inner row has exactly one match is not
+ 			 * as useful as one could wish, since we really need to know the
+ 			 * fraction of outer rows with a match.  Still, we can avoid the
+ 			 * folly of multiplying the per-column estimates together.  Take
+ 			 * the smallest per-column selectivity, instead.  (This should
+ 			 * correspond to the FK column with the most nulls.)
+ 			 */
+ 			Selectivity thisfksel = 1.0;
+ 
+ 			foreach(cell, removedlist)
+ 			{
+ 				RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
+ 				Selectivity csel;
+ 
+ 				csel = clause_selectivity(root, (Node *) rinfo,
+ 										  0, jointype, sjinfo);
+ 				thisfksel = Min(thisfksel, csel);
+ 			}
+ 			fkselec *= thisfksel;
+ 		}
+ 		else if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+ 		{
+ 			/*
+ 			 * For JOIN_SEMI and JOIN_ANTI, the selectivity is defined as the
+ 			 * fraction of LHS rows that have matches.  If the referenced
+ 			 * table is on the inner side, that means the selectivity is 1.0
+ 			 * (modulo nulls, which we're ignoring for now).  We already
+ 			 * covered the other case, so no work here.
+ 			 */
+ 		}
+ 		else
+ 		{
+ 			/*
+ 			 * Otherwise, selectivity is exactly 1/referenced-table-size; but
+ 			 * guard against tuples == 0.  Note we should use the raw table
+ 			 * tuple count, not any estimate of its filtered or joined size.
+ 			 */
+ 			RelOptInfo *ref_rel = find_base_rel(root, fkinfo->ref_relid);
+ 			double		ref_tuples = Max(ref_rel->tuples, 1.0);
+ 
+ 			fkselec *= 1.0 / ref_tuples;
+ 		}
+ 	}
+ 
+ 	*restrictlist = worklist;
+ 	return fkselec;
+ }
+ 
+ /*
   * set_subquery_size_estimates
   *		Set the size estimates for a base relation that is a subquery.
   *
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index bfa0c65..0e50ad5 100644
*** a/src/backend/optimizer/path/equivclass.c
--- b/src/backend/optimizer/path/equivclass.c
*************** exprs_known_equal(PlannerInfo *root, Nod
*** 1926,1931 ****
--- 1926,2010 ----
  
  
  /*
+  * match_eclasses_to_foreign_key_col
+  *	  See whether a foreign key column match is proven by any eclass.
+  *
+  * If the referenced and referencing Vars of the fkey's colno'th column are
+  * known equal due to any eclass, return that eclass; otherwise return NULL.
+  * (In principle there might be more than one matching eclass if multiple
+  * collations are involved, but since collation doesn't matter for equality,
+  * we ignore that fine point here.)  This is much like exprs_known_equal,
+  * except that we insist on the comparison operator matching the eclass, so
+  * that the result is definite not approximate.
+  */
+ EquivalenceClass *
+ match_eclasses_to_foreign_key_col(PlannerInfo *root,
+ 								  ForeignKeyOptInfo *fkinfo,
+ 								  int colno)
+ {
+ 	Index		var1varno = fkinfo->con_relid;
+ 	AttrNumber	var1attno = fkinfo->conkey[colno];
+ 	Index		var2varno = fkinfo->ref_relid;
+ 	AttrNumber	var2attno = fkinfo->confkey[colno];
+ 	Oid			eqop = fkinfo->conpfeqop[colno];
+ 	List	   *opfamilies = NIL;		/* compute only if needed */
+ 	ListCell   *lc1;
+ 
+ 	foreach(lc1, root->eq_classes)
+ 	{
+ 		EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
+ 		bool		item1member = false;
+ 		bool		item2member = false;
+ 		ListCell   *lc2;
+ 
+ 		/* 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)
+ 		{
+ 			EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+ 			Var		   *var;
+ 
+ 			if (em->em_is_child)
+ 				continue;		/* ignore children here */
+ 
+ 			/* EM must be a Var, possibly with RelabelType */
+ 			var = (Var *) em->em_expr;
+ 			while (var && IsA(var, RelabelType))
+ 				var = (Var *) ((RelabelType *) var)->arg;
+ 			if (!(var && IsA(var, Var)))
+ 				continue;
+ 
+ 			/* Match? */
+ 			if (var->varno == var1varno && var->varattno == var1attno)
+ 				item1member = true;
+ 			else if (var->varno == var2varno && var->varattno == var2attno)
+ 				item2member = true;
+ 
+ 			/* Have we found both PK and FK column in this EC? */
+ 			if (item1member && item2member)
+ 			{
+ 				/*
+ 				 * Succeed if eqop matches EC's opfamilies.  We could test
+ 				 * this before scanning the members, but it's probably cheaper
+ 				 * to test for member matches first.
+ 				 */
+ 				if (opfamilies == NIL)	/* compute if we didn't already */
+ 					opfamilies = get_mergejoin_opfamilies(eqop);
+ 				if (equal(opfamilies, ec->ec_opfamilies))
+ 					return ec;
+ 				/* Otherwise, done with this EC, move on to the next */
+ 				break;
+ 			}
+ 		}
+ 	}
+ 	return NULL;
+ }
+ 
+ 
+ /*
   * add_child_rel_equivalences
   *	  Search for EC members that reference the parent_rel, and
   *	  add transformed members referencing the child_rel.
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 3d305eb..e28a8dc 100644
*** a/src/backend/optimizer/plan/analyzejoins.c
--- b/src/backend/optimizer/plan/analyzejoins.c
*************** remove_rel_from_query(PlannerInfo *root,
*** 433,438 ****
--- 433,443 ----
  			distribute_restrictinfo_to_rels(root, rinfo);
  		}
  	}
+ 
+ 	/*
+ 	 * There may be references to the rel in root->fkey_list, but if so,
+ 	 * match_foreign_keys_to_quals() will get rid of them.
+ 	 */
  }
  
  /*
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 1a1c26a..4d8cf9f 100644
*** a/src/backend/optimizer/plan/initsplan.c
--- b/src/backend/optimizer/plan/initsplan.c
*************** build_implied_join_equality(Oid opno,
*** 2306,2311 ****
--- 2306,2454 ----
  }
  
  
+ /*
+  * match_foreign_keys_to_quals
+  *		Match foreign-key constraints to equivalence classes and join quals
+  *
+  * The idea here is to see which query join conditions match equality
+  * constraints of a foreign-key relationship.  For such join conditions,
+  * we can use the FK semantics to make selectivity estimates that are more
+  * reliable than estimating from statistics, especially for multiple-column
+  * FKs, where the normal assumption of independent conditions tends to fail.
+  *
+  * In this function we annotate the ForeignKeyOptInfos in root->fkey_list
+  * with info about which eclasses and join qual clauses they match, and
+  * discard any ForeignKeyOptInfos that are irrelevant for the query.
+  */
+ void
+ match_foreign_keys_to_quals(PlannerInfo *root)
+ {
+ 	List	   *newlist = NIL;
+ 	ListCell   *lc;
+ 
+ 	foreach(lc, root->fkey_list)
+ 	{
+ 		ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+ 		RelOptInfo *con_rel = find_base_rel(root, fkinfo->con_relid);
+ 		RelOptInfo *ref_rel = find_base_rel(root, fkinfo->ref_relid);
+ 		int			colno;
+ 
+ 		/*
+ 		 * Ignore FK unless both rels are baserels.  This gets rid of FKs that
+ 		 * link to inheritance child rels (otherrels) and those that link to
+ 		 * rels removed by join removal (dead rels).
+ 		 */
+ 		if (con_rel->reloptkind != RELOPT_BASEREL ||
+ 			ref_rel->reloptkind != RELOPT_BASEREL)
+ 			continue;
+ 
+ 		/*
+ 		 * Scan the columns and try to match them to eclasses and quals.
+ 		 *
+ 		 * Note: for simple inner joins, any match should be in an eclass.
+ 		 * "Loose" quals that match an FK equality must have been rejected for
+ 		 * EC status because they are outer-join quals or similar.  We still
+ 		 * consider them to match the FK, though, since that produces better
+ 		 * selectivity estimates than not matching.
+ 		 */
+ 		for (colno = 0; colno < fkinfo->nkeys; colno++)
+ 		{
+ 			AttrNumber	con_attno,
+ 						ref_attno;
+ 			Oid			fpeqop;
+ 			ListCell   *lc2;
+ 
+ 			fkinfo->eclass[colno] = match_eclasses_to_foreign_key_col(root,
+ 																	  fkinfo,
+ 																	  colno);
+ 			/* Don't bother looking for loose quals if we got an EC match */
+ 			if (fkinfo->eclass[colno] != NULL)
+ 			{
+ 				fkinfo->nmatched++;
+ 				continue;
+ 			}
+ 
+ 			/*
+ 			 * Scan joininfo list for relevant clauses.  Either rel's joininfo
+ 			 * list would do equally well; we use con_rel's.
+ 			 */
+ 			con_attno = fkinfo->conkey[colno];
+ 			ref_attno = fkinfo->confkey[colno];
+ 			fpeqop = InvalidOid;	/* we'll look this up only if needed */
+ 
+ 			foreach(lc2, con_rel->joininfo)
+ 			{
+ 				RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc2);
+ 				OpExpr	   *clause = (OpExpr *) rinfo->clause;
+ 				Var		   *leftvar;
+ 				Var		   *rightvar;
+ 
+ 				/* only binary OpExprs are useful for consideration */
+ 				if (!IsA(clause, OpExpr) ||
+ 					list_length(clause->args) != 2)
+ 					continue;
+ 				leftvar = (Var *) get_leftop((Expr *) clause);
+ 				rightvar = (Var *) get_rightop((Expr *) clause);
+ 
+ 				/* Operands must be Vars, possibly with RelabelType */
+ 				while (leftvar && IsA(leftvar, RelabelType))
+ 					leftvar = (Var *) ((RelabelType *) leftvar)->arg;
+ 				if (!(leftvar && IsA(leftvar, Var)))
+ 					continue;
+ 				while (rightvar && IsA(rightvar, RelabelType))
+ 					rightvar = (Var *) ((RelabelType *) rightvar)->arg;
+ 				if (!(rightvar && IsA(rightvar, Var)))
+ 					continue;
+ 
+ 				/* Now try to match the vars to the current foreign key cols */
+ 				if (fkinfo->ref_relid == leftvar->varno &&
+ 					ref_attno == leftvar->varattno &&
+ 					fkinfo->con_relid == rightvar->varno &&
+ 					con_attno == rightvar->varattno)
+ 				{
+ 					/* Vars match, but is it the right operator? */
+ 					if (clause->opno == fkinfo->conpfeqop[colno])
+ 						fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
+ 														rinfo);
+ 				}
+ 				else if (fkinfo->ref_relid == rightvar->varno &&
+ 						 ref_attno == rightvar->varattno &&
+ 						 fkinfo->con_relid == leftvar->varno &&
+ 						 con_attno == leftvar->varattno)
+ 				{
+ 					/*
+ 					 * Reverse match, must check commutator operator.  Look it
+ 					 * up if we didn't already.  (In the worst case we might
+ 					 * do multiple lookups here, but that would require an FK
+ 					 * equality operator without commutator, which is
+ 					 * unlikely.)
+ 					 */
+ 					if (!OidIsValid(fpeqop))
+ 						fpeqop = get_commutator(fkinfo->conpfeqop[colno]);
+ 					if (clause->opno == fpeqop)
+ 						fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
+ 														rinfo);
+ 				}
+ 			}
+ 			/* If we found any matching loose quals, count col as matched */
+ 			if (fkinfo->rinfos[colno])
+ 				fkinfo->nmatched++;
+ 		}
+ 
+ 		/*
+ 		 * Currently, we drop multicolumn FKs that aren't fully matched to the
+ 		 * query.  Later we might figure out how to derive some sort of
+ 		 * weakened estimate from them, in which case this test should be
+ 		 * weakened to "if (fkinfo->nmatched > 0)".
+ 		 */
+ 		if (fkinfo->nmatched == fkinfo->nkeys)
+ 			newlist = lappend(newlist, fkinfo);
+ 	}
+ 	/* Replace fkey_list, thereby discarding any useless entries */
+ 	root->fkey_list = newlist;
+ }
+ 
+ 
  /*****************************************************************************
   *
   *	 CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index edd95d8..27234ff 100644
*** a/src/backend/optimizer/plan/planmain.c
--- b/src/backend/optimizer/plan/planmain.c
*************** query_planner(PlannerInfo *root, List *t
*** 115,120 ****
--- 115,121 ----
  	root->full_join_clauses = NIL;
  	root->join_info_list = NIL;
  	root->placeholder_list = NIL;
+ 	root->fkey_list = NIL;
  	root->initial_rels = NIL;
  
  	/*
*************** query_planner(PlannerInfo *root, List *t
*** 206,211 ****
--- 207,220 ----
  	create_lateral_join_info(root);
  
  	/*
+ 	 * Match foreign keys to equivalence classes and join quals.  This must be
+ 	 * done after finalizing equivalence classes, and it's useful to wait till
+ 	 * after join removal so that we can skip processing foreign keys
+ 	 * involving removed relations.
+ 	 */
+ 	match_foreign_keys_to_quals(root);
+ 
+ 	/*
  	 * Look for join OR clauses that we can extract single-relation
  	 * restriction OR clauses from.
  	 */
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 6aa8192..b0658f2 100644
*** a/src/backend/optimizer/util/plancat.c
--- b/src/backend/optimizer/util/plancat.c
*************** int			constraint_exclusion = CONSTRAINT_
*** 52,57 ****
--- 52,59 ----
  get_relation_info_hook_type get_relation_info_hook = NULL;
  
  
+ static void get_relation_foreign_keys(PlannerInfo *root, RelOptInfo *rel,
+ 						  Relation relation);
  static bool infer_collation_opclass_match(InferenceElem *elem, Relation idxRel,
  							  List *idxExprs);
  static int32 get_rel_data_width(Relation rel, int32 *attr_widths);
*************** static List *build_index_tlist(PlannerIn
*** 77,82 ****
--- 79,86 ----
   *	pages		number of pages
   *	tuples		number of tuples
   *
+  * Also, add information about the relation's foreign keys to root->fkey_list.
+  *
   * Also, initialize the attr_needed[] and attr_widths[] arrays.  In most
   * cases these are left as zeroes, but sometimes we need to compute attr
   * widths here, and we may as well cache the results for costsize.c.
*************** get_relation_info(PlannerInfo *root, Oid
*** 403,408 ****
--- 407,415 ----
  		rel->fdwroutine = NULL;
  	}
  
+ 	/* Collect info about relation's foreign keys, if relevant */
+ 	get_relation_foreign_keys(root, rel, relation);
+ 
  	heap_close(relation, NoLock);
  
  	/*
*************** get_relation_info(PlannerInfo *root, Oid
*** 415,420 ****
--- 422,516 ----
  }
  
  /*
+  * get_relation_foreign_keys -
+  *	  Retrieves foreign key information for a given relation.
+  *
+  * ForeignKeyOptInfos for relevant foreign keys are created and added to
+  * root->fkey_list.  We do this now while we have the relcache entry open.
+  * We could sometimes avoid making useless ForeignKeyOptInfos if we waited
+  * until all RelOptInfos have been built, but the cost of re-opening the
+  * relcache entries would probably exceed any savings.
+  */
+ static void
+ get_relation_foreign_keys(PlannerInfo *root, RelOptInfo *rel,
+ 						  Relation relation)
+ {
+ 	List	   *rtable = root->parse->rtable;
+ 	List	   *cachedfkeys;
+ 	ListCell   *lc;
+ 
+ 	/*
+ 	 * If it's not a baserel, we don't care about its FKs.  Also, if the query
+ 	 * references only a single relation, we can skip the lookup since no FKs
+ 	 * could satisfy the requirements below.
+ 	 */
+ 	if (rel->reloptkind != RELOPT_BASEREL ||
+ 		list_length(rtable) < 2)
+ 		return;
+ 
+ 	/*
+ 	 * Extract data about relation's FKs from the relcache.  Note that this
+ 	 * list belongs to the relcache and might disappear in a cache flush, so
+ 	 * we must not do any further catalog access within this function.
+ 	 */
+ 	cachedfkeys = RelationGetFKeyList(relation);
+ 
+ 	/*
+ 	 * Figure out which FKs are of interest for this query, and create
+ 	 * ForeignKeyOptInfos for them.  We want only FKs that reference some
+ 	 * other RTE of the current query.  In queries containing self-joins,
+ 	 * there might be more than one other RTE for a referenced table, and we
+ 	 * should make a ForeignKeyOptInfo for each occurrence.
+ 	 *
+ 	 * Ideally, we would ignore RTEs that correspond to non-baserels, but it's
+ 	 * too hard to identify those here, so we might end up making some useless
+ 	 * ForeignKeyOptInfos.  If so, match_foreign_keys_to_quals() will remove
+ 	 * them again.
+ 	 */
+ 	foreach(lc, cachedfkeys)
+ 	{
+ 		ForeignKeyCacheInfo *cachedfk = (ForeignKeyCacheInfo *) lfirst(lc);
+ 		Index		rti;
+ 		ListCell   *lc2;
+ 
+ 		/* conrelid should always be that of the table we're considering */
+ 		Assert(cachedfk->conrelid == RelationGetRelid(relation));
+ 
+ 		/* Scan to find other RTEs matching confrelid */
+ 		rti = 0;
+ 		foreach(lc2, rtable)
+ 		{
+ 			RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc2);
+ 			ForeignKeyOptInfo *info;
+ 
+ 			rti++;
+ 			/* Ignore if not the correct table */
+ 			if (rte->rtekind != RTE_RELATION ||
+ 				rte->relid != cachedfk->confrelid)
+ 				continue;
+ 			/* Ignore self-referential FKs; we only care about joins */
+ 			if (rti == rel->relid)
+ 				continue;
+ 
+ 			/* OK, let's make an entry */
+ 			info = makeNode(ForeignKeyOptInfo);
+ 			info->con_relid = rel->relid;
+ 			info->ref_relid = rti;
+ 			info->nkeys = cachedfk->nkeys;
+ 			memcpy(info->conkey, cachedfk->conkey, sizeof(info->conkey));
+ 			memcpy(info->confkey, cachedfk->confkey, sizeof(info->confkey));
+ 			memcpy(info->conpfeqop, cachedfk->conpfeqop, sizeof(info->conpfeqop));
+ 			/* zero out fields to be filled by match_foreign_keys_to_quals */
+ 			info->nmatched = 0;
+ 			memset(info->eclass, 0, sizeof(info->eclass));
+ 			memset(info->rinfos, 0, sizeof(info->rinfos));
+ 
+ 			root->fkey_list = lappend(root->fkey_list, info);
+ 		}
+ 	}
+ }
+ 
+ /*
   * infer_arbiter_indexes -
   *	  Determine the unique indexes used to arbitrate speculative insertion.
   *
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index ba185ae..a0a284b 100644
*** a/src/backend/optimizer/util/relnode.c
--- b/src/backend/optimizer/util/relnode.c
*************** get_joinrel_parampathinfo(PlannerInfo *r
*** 1264,1271 ****
  
  	/* Estimate the number of rows returned by the parameterized join */
  	rows = get_parameterized_joinrel_size(root, joinrel,
! 										  outer_path->rows,
! 										  inner_path->rows,
  										  sjinfo,
  										  *restrict_clauses);
  
--- 1264,1271 ----
  
  	/* Estimate the number of rows returned by the parameterized join */
  	rows = get_parameterized_joinrel_size(root, joinrel,
! 										  outer_path,
! 										  inner_path,
  										  sjinfo,
  										  *restrict_clauses);
  
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index c958758..8d2ad01 100644
*** a/src/backend/utils/cache/relcache.c
--- b/src/backend/utils/cache/relcache.c
*************** RelationBuildDesc(Oid targetRelId, bool 
*** 1049,1054 ****
--- 1049,1058 ----
  	else
  		relation->rd_rsdesc = NULL;
  
+ 	/* foreign key data is not loaded till asked for */
+ 	relation->rd_fkeylist = NIL;
+ 	relation->rd_fkeyvalid = false;
+ 
  	/*
  	 * if it's an index, initialize index-related information
  	 */
*************** RelationDestroyRelation(Relation relatio
*** 2030,2040 ****
  		else
  			FreeTupleDesc(relation->rd_att);
  	}
  	list_free(relation->rd_indexlist);
  	bms_free(relation->rd_indexattr);
  	bms_free(relation->rd_keyattr);
  	bms_free(relation->rd_idattr);
- 	FreeTriggerDesc(relation->trigdesc);
  	if (relation->rd_options)
  		pfree(relation->rd_options);
  	if (relation->rd_indextuple)
--- 2034,2045 ----
  		else
  			FreeTupleDesc(relation->rd_att);
  	}
+ 	FreeTriggerDesc(relation->trigdesc);
+ 	list_free_deep(relation->rd_fkeylist);
  	list_free(relation->rd_indexlist);
  	bms_free(relation->rd_indexattr);
  	bms_free(relation->rd_keyattr);
  	bms_free(relation->rd_idattr);
  	if (relation->rd_options)
  		pfree(relation->rd_options);
  	if (relation->rd_indextuple)
*************** CheckConstraintCmp(const void *a, const 
*** 3804,3809 ****
--- 3809,3955 ----
  }
  
  /*
+  * RelationGetFKeyList -- get a list of foreign key info for the relation
+  *
+  * Returns a list of ForeignKeyCacheInfo structs, one per FK constraining
+  * the given relation.  This data is a direct copy of relevant fields from
+  * pg_constraint.  The list items are in no particular order.
+  *
+  * CAUTION: the returned list is part of the relcache's data, and could
+  * vanish in a relcache entry reset.  Callers must inspect or copy it
+  * before doing anything that might trigger a cache flush, such as
+  * system catalog accesses.  copyObject() can be used if desired.
+  * (We define it this way because current callers want to filter and
+  * modify the list entries anyway, so copying would be a waste of time.)
+  */
+ List *
+ RelationGetFKeyList(Relation relation)
+ {
+ 	List	   *result;
+ 	Relation	conrel;
+ 	SysScanDesc conscan;
+ 	ScanKeyData skey;
+ 	HeapTuple	htup;
+ 	List	   *oldlist;
+ 	MemoryContext oldcxt;
+ 
+ 	/* Quick exit if we already computed the list. */
+ 	if (relation->rd_fkeyvalid)
+ 		return relation->rd_fkeylist;
+ 
+ 	/* Fast path: if it doesn't have any triggers, it can't have FKs */
+ 	if (!relation->rd_rel->relhastriggers)
+ 		return NIL;
+ 
+ 	/*
+ 	 * We build the list we intend to return (in the caller's context) while
+ 	 * doing the scan.  After successfully completing the scan, we copy that
+ 	 * list into the relcache entry.  This avoids cache-context memory leakage
+ 	 * if we get some sort of error partway through.
+ 	 */
+ 	result = NIL;
+ 
+ 	/* Prepare to scan pg_constraint for entries having conrelid = this rel. */
+ 	ScanKeyInit(&skey,
+ 				Anum_pg_constraint_conrelid,
+ 				BTEqualStrategyNumber, F_OIDEQ,
+ 				ObjectIdGetDatum(RelationGetRelid(relation)));
+ 
+ 	conrel = heap_open(ConstraintRelationId, AccessShareLock);
+ 	conscan = systable_beginscan(conrel, ConstraintRelidIndexId, true,
+ 								 NULL, 1, &skey);
+ 
+ 	while (HeapTupleIsValid(htup = systable_getnext(conscan)))
+ 	{
+ 		Form_pg_constraint constraint = (Form_pg_constraint) GETSTRUCT(htup);
+ 		ForeignKeyCacheInfo *info;
+ 		Datum		adatum;
+ 		bool		isnull;
+ 		ArrayType  *arr;
+ 		int			nelem;
+ 
+ 		/* consider only foreign keys */
+ 		if (constraint->contype != CONSTRAINT_FOREIGN)
+ 			continue;
+ 
+ 		info = makeNode(ForeignKeyCacheInfo);
+ 		info->conrelid = constraint->conrelid;
+ 		info->confrelid = constraint->confrelid;
+ 
+ 		/* Extract data from conkey field */
+ 		adatum = fastgetattr(htup, Anum_pg_constraint_conkey,
+ 							 conrel->rd_att, &isnull);
+ 		if (isnull)
+ 			elog(ERROR, "null conkey for rel %s",
+ 				 RelationGetRelationName(relation));
+ 
+ 		arr = DatumGetArrayTypeP(adatum);		/* ensure not toasted */
+ 		nelem = ARR_DIMS(arr)[0];
+ 		if (ARR_NDIM(arr) != 1 ||
+ 			nelem < 1 ||
+ 			nelem > INDEX_MAX_KEYS ||
+ 			ARR_HASNULL(arr) ||
+ 			ARR_ELEMTYPE(arr) != INT2OID)
+ 			elog(ERROR, "conkey is not a 1-D smallint array");
+ 
+ 		info->nkeys = nelem;
+ 		memcpy(info->conkey, ARR_DATA_PTR(arr), nelem * sizeof(AttrNumber));
+ 
+ 		/* Likewise for confkey */
+ 		adatum = fastgetattr(htup, Anum_pg_constraint_confkey,
+ 							 conrel->rd_att, &isnull);
+ 		if (isnull)
+ 			elog(ERROR, "null confkey for rel %s",
+ 				 RelationGetRelationName(relation));
+ 
+ 		arr = DatumGetArrayTypeP(adatum);		/* ensure not toasted */
+ 		nelem = ARR_DIMS(arr)[0];
+ 		if (ARR_NDIM(arr) != 1 ||
+ 			nelem != info->nkeys ||
+ 			ARR_HASNULL(arr) ||
+ 			ARR_ELEMTYPE(arr) != INT2OID)
+ 			elog(ERROR, "confkey is not a 1-D smallint array");
+ 
+ 		memcpy(info->confkey, ARR_DATA_PTR(arr), nelem * sizeof(AttrNumber));
+ 
+ 		/* Likewise for conpfeqop */
+ 		adatum = fastgetattr(htup, Anum_pg_constraint_conpfeqop,
+ 							 conrel->rd_att, &isnull);
+ 		if (isnull)
+ 			elog(ERROR, "null conpfeqop for rel %s",
+ 				 RelationGetRelationName(relation));
+ 
+ 		arr = DatumGetArrayTypeP(adatum);		/* ensure not toasted */
+ 		nelem = ARR_DIMS(arr)[0];
+ 		if (ARR_NDIM(arr) != 1 ||
+ 			nelem != info->nkeys ||
+ 			ARR_HASNULL(arr) ||
+ 			ARR_ELEMTYPE(arr) != OIDOID)
+ 			elog(ERROR, "conpfeqop is not a 1-D OID array");
+ 
+ 		memcpy(info->conpfeqop, ARR_DATA_PTR(arr), nelem * sizeof(Oid));
+ 
+ 		/* Add FK's node to the result list */
+ 		result = lappend(result, info);
+ 	}
+ 
+ 	systable_endscan(conscan);
+ 	heap_close(conrel, AccessShareLock);
+ 
+ 	/* Now save a copy of the completed list in the relcache entry. */
+ 	oldcxt = MemoryContextSwitchTo(CacheMemoryContext);
+ 	oldlist = relation->rd_fkeylist;
+ 	relation->rd_fkeylist = copyObject(result);
+ 	relation->rd_fkeyvalid = true;
+ 	MemoryContextSwitchTo(oldcxt);
+ 
+ 	/* Don't leak the old list, if there is one */
+ 	list_free_deep(oldlist);
+ 
+ 	return result;
+ }
+ 
+ /*
   * RelationGetIndexList -- get a list of OIDs of indexes on this relation
   *
   * The index list is created only if someone requests it.  We scan pg_index
*************** load_relcache_init_file(bool shared)
*** 4892,4898 ****
  		 * format is complex and subject to change).  They must be rebuilt if
  		 * needed by RelationCacheInitializePhase3.  This is not expected to
  		 * be a big performance hit since few system catalogs have such. Ditto
! 		 * for index expressions, predicates, exclusion info, and FDW info.
  		 */
  		rel->rd_rules = NULL;
  		rel->rd_rulescxt = NULL;
--- 5038,5045 ----
  		 * format is complex and subject to change).  They must be rebuilt if
  		 * needed by RelationCacheInitializePhase3.  This is not expected to
  		 * be a big performance hit since few system catalogs have such. Ditto
! 		 * for RLS policy data, index expressions, predicates, exclusion info,
! 		 * and FDW info.
  		 */
  		rel->rd_rules = NULL;
  		rel->rd_rulescxt = NULL;
*************** load_relcache_init_file(bool shared)
*** 4914,4919 ****
--- 5061,5068 ----
  		else
  			rel->rd_refcnt = 0;
  		rel->rd_indexvalid = 0;
+ 		rel->rd_fkeylist = NIL;
+ 		rel->rd_fkeyvalid = false;
  		rel->rd_indexlist = NIL;
  		rel->rd_oidindex = InvalidOid;
  		rel->rd_replidindex = InvalidOid;
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index c4b9c14..8f46091 100644
*** a/src/include/nodes/nodes.h
--- b/src/include/nodes/nodes.h
*************** typedef enum NodeTag
*** 223,228 ****
--- 223,229 ----
  	T_PlannerGlobal,
  	T_RelOptInfo,
  	T_IndexOptInfo,
+ 	T_ForeignKeyOptInfo,
  	T_ParamPathInfo,
  	T_Path,
  	T_IndexPath,
*************** typedef enum NodeTag
*** 478,484 ****
  	T_InlineCodeBlock,			/* in nodes/parsenodes.h */
  	T_FdwRoutine,				/* in foreign/fdwapi.h */
  	T_IndexAmRoutine,			/* in access/amapi.h */
! 	T_TsmRoutine				/* in access/tsmapi.h */
  } NodeTag;
  
  /*
--- 479,486 ----
  	T_InlineCodeBlock,			/* in nodes/parsenodes.h */
  	T_FdwRoutine,				/* in foreign/fdwapi.h */
  	T_IndexAmRoutine,			/* in access/amapi.h */
! 	T_TsmRoutine,				/* in access/tsmapi.h */
! 	T_ForeignKeyCacheInfo		/* in utils/rel.h */
  } NodeTag;
  
  /*
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index a4892cb..4d0cb2e 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct PlannerInfo
*** 251,256 ****
--- 251,258 ----
  
  	List	   *placeholder_list;		/* list of PlaceHolderInfos */
  
+ 	List	   *fkey_list;		/* list of ForeignKeyOptInfos */
+ 
  	List	   *query_pathkeys; /* desired pathkeys for query_planner() */
  
  	List	   *group_pathkeys; /* groupClause pathkeys, if any */
*************** typedef struct IndexOptInfo
*** 622,627 ****
--- 624,657 ----
  	void		(*amcostestimate) ();	/* AM's cost estimator */
  } IndexOptInfo;
  
+ /*
+  * ForeignKeyOptInfo
+  *		Per-foreign-key information for planning/optimization
+  *
+  * The per-FK-column arrays can be fixed-size because we allow at most
+  * INDEX_MAX_KEYS columns in a foreign key constraint.  Each array has
+  * nkeys valid entries.
+  */
+ typedef struct ForeignKeyOptInfo
+ {
+ 	NodeTag		type;
+ 
+ 	/* Basic data about the foreign key (fetched from catalogs): */
+ 	Index		con_relid;		/* RT index of the referencing table */
+ 	Index		ref_relid;		/* RT index of the referenced table */
+ 	int			nkeys;			/* number of columns in the foreign key */
+ 	AttrNumber	conkey[INDEX_MAX_KEYS]; /* cols in referencing table */
+ 	AttrNumber	confkey[INDEX_MAX_KEYS];		/* cols in referenced table */
+ 	Oid			conpfeqop[INDEX_MAX_KEYS];		/* PK = FK operator OIDs */
+ 
+ 	/* Derived info about whether FK's equality conditions match the query: */
+ 	int			nmatched;		/* number of column conditions matched */
+ 	/* Pointer to eclass matching each column's condition, if there is one */
+ 	struct EquivalenceClass *eclass[INDEX_MAX_KEYS];
+ 	/* List of non-EC RestrictInfos matching each column's condition */
+ 	List	   *rinfos[INDEX_MAX_KEYS];
+ } ForeignKeyOptInfo;
+ 
  
  /*
   * EquivalenceClasses
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index f41f9e9..2a4df2f 100644
*** a/src/include/optimizer/cost.h
--- b/src/include/optimizer/cost.h
*************** extern double get_parameterized_baserel_
*** 167,174 ****
  							   List *param_clauses);
  extern double get_parameterized_joinrel_size(PlannerInfo *root,
  							   RelOptInfo *rel,
! 							   double outer_rows,
! 							   double inner_rows,
  							   SpecialJoinInfo *sjinfo,
  							   List *restrict_clauses);
  extern void set_joinrel_size_estimates(PlannerInfo *root, RelOptInfo *rel,
--- 167,174 ----
  							   List *param_clauses);
  extern double get_parameterized_joinrel_size(PlannerInfo *root,
  							   RelOptInfo *rel,
! 							   Path *outer_path,
! 							   Path *inner_path,
  							   SpecialJoinInfo *sjinfo,
  							   List *restrict_clauses);
  extern void set_joinrel_size_estimates(PlannerInfo *root, RelOptInfo *rel,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index f3b25e2..a0008ad 100644
*** a/src/include/optimizer/paths.h
--- b/src/include/optimizer/paths.h
*************** extern List *generate_join_implied_equal
*** 139,144 ****
--- 139,147 ----
  										 Relids outer_relids,
  										 RelOptInfo *inner_rel);
  extern bool exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2);
+ extern EquivalenceClass *match_eclasses_to_foreign_key_col(PlannerInfo *root,
+ 								  ForeignKeyOptInfo *fkinfo,
+ 								  int colno);
  extern void add_child_rel_equivalences(PlannerInfo *root,
  						   AppendRelInfo *appinfo,
  						   RelOptInfo *parent_rel,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index a48400b..c529085 100644
*** a/src/include/optimizer/planmain.h
--- b/src/include/optimizer/planmain.h
*************** extern RestrictInfo *build_implied_join_
*** 95,100 ****
--- 95,101 ----
  							Expr *item2,
  							Relids qualscope,
  							Relids nullable_relids);
+ extern void match_foreign_keys_to_quals(PlannerInfo *root);
  
  /*
   * prototypes for plan/analyzejoins.c
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index fd858fd..ed14442 100644
*** a/src/include/utils/rel.h
--- b/src/include/utils/rel.h
*************** typedef struct RelationData
*** 90,95 ****
--- 90,99 ----
  	/* use "struct" here to avoid needing to include rowsecurity.h: */
  	struct RowSecurityDesc *rd_rsdesc;	/* row security policies, or NULL */
  
+ 	/* data managed by RelationGetFKeyList: */
+ 	List	   *rd_fkeylist;	/* list of ForeignKeyCacheInfo (see below) */
+ 	bool		rd_fkeyvalid;	/* true if list has been computed */
+ 
  	/* data managed by RelationGetIndexList: */
  	List	   *rd_indexlist;	/* list of OIDs of indexes on relation */
  	Oid			rd_oidindex;	/* OID of unique index on OID, if any */
*************** typedef struct RelationData
*** 170,175 ****
--- 174,207 ----
  	struct PgStat_TableStatus *pgstat_info;		/* statistics collection area */
  } RelationData;
  
+ 
+ /*
+  * ForeignKeyCacheInfo
+  *		Information the relcache can cache about foreign key constraints
+  *
+  * This is basically just an image of relevant columns from pg_constraint.
+  * We make it a subclass of Node so that copyObject() can be used on a list
+  * of these, but we also ensure it is a "flat" object without substructure,
+  * so that list_free_deep() is sufficient to free such a list.
+  * The per-FK-column arrays can be fixed-size because we allow at most
+  * INDEX_MAX_KEYS columns in a foreign key constraint.
+  *
+  * Currently, we only cache fields of interest to the planner, but the
+  * set of fields could be expanded in future.
+  */
+ typedef struct ForeignKeyCacheInfo
+ {
+ 	NodeTag		type;
+ 	Oid			conrelid;		/* relation constrained by the foreign key */
+ 	Oid			confrelid;		/* relation referenced by the foreign key */
+ 	int			nkeys;			/* number of columns in the foreign key */
+ 	/* these arrays each have nkeys valid entries: */
+ 	AttrNumber	conkey[INDEX_MAX_KEYS]; /* cols in referencing table */
+ 	AttrNumber	confkey[INDEX_MAX_KEYS];		/* cols in referenced table */
+ 	Oid			conpfeqop[INDEX_MAX_KEYS];		/* PK = FK operator OIDs */
+ } ForeignKeyCacheInfo;
+ 
+ 
  /*
   * StdRdOptions
   *		Standard contents of rd_options for heaps and generic indexes.
diff --git a/src/include/utils/relcache.h b/src/include/utils/relcache.h
index 1b48304..6ea7dd2 100644
*** a/src/include/utils/relcache.h
--- b/src/include/utils/relcache.h
*************** extern void RelationClose(Relation relat
*** 37,42 ****
--- 37,43 ----
  /*
   * Routines to compute/retrieve additional cached information
   */
+ extern List *RelationGetFKeyList(Relation relation);
  extern List *RelationGetIndexList(Relation relation);
  extern Oid	RelationGetOidIndex(Relation relation);
  extern Oid	RelationGetReplicaIndex(Relation relation);

diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index e42895d..415edad 100644
*** a/src/backend/optimizer/path/costsize.c
--- b/src/backend/optimizer/path/costsize.c
*************** get_foreign_key_join_selectivity(Planner
*** 4085,4090 ****
--- 4085,4091 ----
  	{
  		ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
  		bool		ref_is_outer;
+ 		bool		use_smallest_selectivity = false;
  		List	   *removedlist;
  		ListCell   *cell;
  		ListCell   *prev;
*************** get_foreign_key_join_selectivity(Planner
*** 4205,4213 ****
  		 * be double-counting the null fraction, and (2) it's not very clear
  		 * how to combine null fractions for multiple referencing columns.
  		 *
! 		 * In the first branch of the logic below, null derating is done
! 		 * implicitly by relying on clause_selectivity(); in the other two
! 		 * paths, we do nothing for now about correcting for nulls.
  		 *
  		 * XXX another point here is that if either side of an FK constraint
  		 * is an inheritance parent, we estimate as though the constraint
--- 4206,4214 ----
  		 * be double-counting the null fraction, and (2) it's not very clear
  		 * how to combine null fractions for multiple referencing columns.
  		 *
! 		 * In the use_smallest_selectivity code below, null derating is done
! 		 * implicitly by relying on clause_selectivity(); in the other cases,
! 		 * we do nothing for now about correcting for nulls.
  		 *
  		 * XXX another point here is that if either side of an FK constraint
  		 * is an inheritance parent, we estimate as though the constraint
*************** get_foreign_key_join_selectivity(Planner
*** 4230,4257 ****
  			 * the smallest per-column selectivity, instead.  (This should
  			 * correspond to the FK column with the most nulls.)
  			 */
! 			Selectivity thisfksel = 1.0;
! 
! 			foreach(cell, removedlist)
! 			{
! 				RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
! 				Selectivity csel;
! 
! 				csel = clause_selectivity(root, (Node *) rinfo,
! 										  0, jointype, sjinfo);
! 				thisfksel = Min(thisfksel, csel);
! 			}
! 			fkselec *= thisfksel;
  		}
  		else if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
  		{
  			/*
  			 * For JOIN_SEMI and JOIN_ANTI, the selectivity is defined as the
! 			 * fraction of LHS rows that have matches.  If the referenced
! 			 * table is on the inner side, that means the selectivity is 1.0
! 			 * (modulo nulls, which we're ignoring for now).  We already
! 			 * covered the other case, so no work here.
  			 */
  		}
  		else
  		{
--- 4231,4271 ----
  			 * the smallest per-column selectivity, instead.  (This should
  			 * correspond to the FK column with the most nulls.)
  			 */
! 			use_smallest_selectivity = true;
  		}
  		else if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
  		{
  			/*
  			 * For JOIN_SEMI and JOIN_ANTI, the selectivity is defined as the
! 			 * fraction of LHS rows that have matches.  The referenced table
! 			 * is on the inner side (we already handled the other case above),
! 			 * so the FK implies that every LHS row has a match *in the
! 			 * referenced table*.  But any restriction or join clauses below
! 			 * here will reduce the number of matches.
  			 */
+ 			if (bms_membership(inner_relids) == BMS_SINGLETON)
+ 			{
+ 				/*
+ 				 * When the inner side of the semi/anti join is just the
+ 				 * referenced table, we may take the FK selectivity as equal
+ 				 * to the selectivity of the table's restriction clauses.
+ 				 */
+ 				RelOptInfo *ref_rel = find_base_rel(root, fkinfo->ref_relid);
+ 				double		ref_tuples = Max(ref_rel->tuples, 1.0);
+ 
+ 				fkselec *= ref_rel->rows / ref_tuples;
+ 			}
+ 			else
+ 			{
+ 				/*
+ 				 * When the inner side of the semi/anti join is itself a join,
+ 				 * it's hard to guess what fraction of the referenced table
+ 				 * will get through the join.  But we still don't want to
+ 				 * multiply per-column estimates together.  Take the smallest
+ 				 * per-column selectivity, instead.
+ 				 */
+ 				use_smallest_selectivity = true;
+ 			}
  		}
  		else
  		{
*************** get_foreign_key_join_selectivity(Planner
*** 4265,4270 ****
--- 4279,4304 ----
  
  			fkselec *= 1.0 / ref_tuples;
  		}
+ 
+ 		/*
+ 		 * Common code for cases where we should use the smallest selectivity
+ 		 * that would be computed for any one of the FK's clauses.
+ 		 */
+ 		if (use_smallest_selectivity)
+ 		{
+ 			Selectivity thisfksel = 1.0;
+ 
+ 			foreach(cell, removedlist)
+ 			{
+ 				RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
+ 				Selectivity csel;
+ 
+ 				csel = clause_selectivity(root, (Node *) rinfo,
+ 										  0, jointype, sjinfo);
+ 				thisfksel = Min(thisfksel, csel);
+ 			}
+ 			fkselec *= thisfksel;
+ 		}
  	}
  
  	*restrictlist = worklist;