PATCH: use foreign keys to improve join estimates v1

>From d5e966d91ff3e30c81b3de2d9c6e8949fcf1e527 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@pgaddict.com>
Date: Tue, 18 Aug 2015 19:15:02 +0200
Subject: [PATCH] foreign key estimation patch

---
 src/backend/nodes/outfuncs.c              |  13 +
 src/backend/optimizer/path/costsize.c     | 629 +++++++++++++++++++++++++++++-
 src/backend/optimizer/plan/analyzejoins.c |   1 -
 src/backend/optimizer/util/plancat.c      |  85 ++++
 src/backend/utils/cache/relcache.c        |  69 ++++
 src/include/nodes/nodes.h                 |   1 +
 src/include/nodes/relation.h              |  15 +
 src/include/optimizer/paths.h             |   2 +
 src/include/utils/rel.h                   |   4 +
 src/include/utils/relcache.h              |   1 +
 10 files changed, 809 insertions(+), 11 deletions(-)

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index a878498..fb9fe24 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1904,6 +1904,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)
 {
 	/*
@@ -3293,6 +3303,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 7069f60..633792d 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3732,6 +3732,614 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
 }
 
 /*
+ * clause_is_fk_compatible
+ *		Verify that the clause may be compatible with foreign keys (i.e. it's
+ * 		a simple operator clause with two Vars, referencing two different
+ * 		relations).
+ *
+ * This only checks form of the clause (and returns 'true' if it may match
+ * a foreign key), but does not cross-check the clause against existing foreign
+ * keys for example.
+ *
+ * It also extracts data from the clause - rangetable indexes and attnums for
+ * each Var (if the function returns 'false' then those values are undefined
+ * and may contain garbage).
+ */
+static bool
+clause_is_fk_compatible(RestrictInfo *rinfo,
+						Index *varnoa, AttrNumber *attnoa,
+						Index *varnob, AttrNumber *attnob,
+						Oid *opno)
+{
+	OpExpr *clause;
+	Var	   *var0, *var1;
+
+	/* We only expect restriction clauses here, with operator expression. */
+
+	if (! IsA(rinfo, RestrictInfo))
+		return false;
+
+	if (! IsA(rinfo->clause, OpExpr))
+		return false;
+
+	clause = (OpExpr*)rinfo->clause;
+
+	/* The clause has to use exactly two simple variables. */
+
+	if (list_length(clause->args) != 2)
+		return false;
+
+	var0 = list_nth(clause->args, 0);
+	var1 = list_nth(clause->args, 1);
+
+	if (! (IsA(var0, Var) && IsA(var1, Var)))
+		return false;
+
+	/* The variables has to reference two different rangetable entries. */
+
+	if (var0->varno == var1->varno)
+		return false;
+
+	/*
+	 * At this point we know the clause has the right structure, so extract
+	 * the interesting info we'll need outside. We don't really track which
+	 * relation is inner/outer, so we'll check both directions.
+	 */
+
+	*varnoa = var0->varno;
+	*attnoa = var0->varattno;
+
+	*varnob = var1->varno;
+	*attnob = var1->varattno;
+
+	*opno = clause->opno;
+
+	return true;
+}
+
+
+/*
+ * fkey_is_matched_by_clauses
+ * 		Check whether the foreign key is "fully" matched by the clauses.
+ *
+ * This checks whether the foreign key is fully matched by clauses, i.e. if
+ * there's a clause matching perfectly all the parts of the foreign key.
+ */
+static bool
+fkey_is_matched_by_clauses(PlannerInfo *root, ForeignKeyOptInfo *fkinfo,
+						   List *clauses, int relid, int frelid)
+{
+	int			i;
+	ListCell   *lc;
+	bool		r;
+	bool	   *matched;
+
+	/* we should only get multi-column foreign keys here */
+	Assert(fkinfo->nkeys > 1);
+
+	/* flags for each part of the foreign key */
+	matched = palloc0(fkinfo->nkeys);
+
+	foreach (lc, clauses)
+	{
+		RestrictInfo   *rinfo = (RestrictInfo*)lfirst(lc);
+
+		/* info extracted from the clause (opno, varnos and varattnos) */
+		Oid				opno;
+		Index			relida, relidb;
+		AttrNumber		attnoa, attnob;
+
+		/* we'll look this up in the simple_rte_array table */
+		Oid				oida, oidb;
+
+		/*
+		 * If the clause has structure incompatible with foreign keys (not an
+		 * operator clause with two Var nodes), just skip it.
+		 */
+		if (! clause_is_fk_compatible(rinfo, &relida, &attnoa,
+											 &relidb, &attnob, &opno))
+			continue;
+
+		/* lookup range table entries for the indexes */
+		oida = root->simple_rte_array[relida]->relid;
+		oidb = root->simple_rte_array[relidb]->relid;
+
+		/*
+		 * Check if the clause matches any part of the foreign key.
+		 */
+		for (i = 0; i < fkinfo->nkeys; i++)
+		{
+			/* if the operator does not match, try next key */
+			if (! fkinfo->conpfeqop[i] == opno)
+				continue;
+
+			/*
+			 * We don't know in what order the clause lists the Vars, so we'll check
+			 * the foreign key in both directions (it does not really matter).
+			 */
+			if ((oida == fkinfo->conrelid) && (oidb == fkinfo->confrelid))
+			{
+				if ((fkinfo->confkeys[i] == attnob) &&
+					(fkinfo->conkeys[i] == attnoa))
+					matched[i] = true;
+			}
+
+			if ((oida == fkinfo->confrelid) && (oidb == fkinfo->conrelid))
+			{
+				if ((fkinfo->confkeys[i] == attnoa) &&
+					(fkinfo->conkeys[i] == attnob))
+						matched[i] = true;
+			}
+		}
+	}
+
+	/* return 'true' if all the parts of the foreign key were matched */
+	r = true;
+	for (i = 0; i < fkinfo->nkeys; i++)
+		r &= matched[i];
+
+	pfree(matched);
+
+	return r;
+}
+
+/*
+ * find_satisfied_fkeys
+ * 		Searches for all foreign keys fully-satisfied by the join clauses.
+ *
+ * A join is fully-satisfied if all the parts are matched by at least one
+ * join condition (same operator and attnos).
+ *
+ * This returns a list of foreign keys of identified foreign keys (or NIL),
+ * and also selectivity for all the (matched) foreign keys.
+ */
+static List *
+find_satisfied_fkeys(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *joinquals,
+					 Selectivity *sel)
+{
+	int	inner, outer;
+	List *fkeys = NIL;
+
+	/*
+	 * We'll take all combinations of inner/outer relations, and check if
+	 * there are foreign keys between them. If we found a foreign key for
+	 * the pair of base relations, we'll try matching it to clauses.
+	 *
+	 * We don't know in which direction the foreign keys are created, so
+	 * we'll check both directions (it's allways between inner and outer
+	 * side of the join).
+	 */
+
+	inner = -1;
+	while ((inner = bms_next_member(sjinfo->min_righthand, inner)) >= 0)
+	{
+		RelOptInfo *rel_inner = find_base_rel(root, inner);
+		RangeTblEntry *rt_inner = planner_rt_fetch(inner, root);
+
+		Assert(rel_inner->reloptkind == RELOPT_BASEREL);
+
+		outer = -1;
+		while ((outer = bms_next_member(sjinfo->min_lefthand, outer)) >= 0)
+		{
+			ListCell   *lc;
+			RelOptInfo *rel_outer = find_base_rel(root, outer);
+			RangeTblEntry *rt_outer = planner_rt_fetch(outer, root);
+
+			Assert(rel_outer->reloptkind == RELOPT_BASEREL);
+
+			/*
+			 * Walk through foreign keys defined on the inner side, referencing
+			 * relation on the outer side.
+			 */
+			foreach (lc, rel_inner->fkeylist)
+			{
+				ForeignKeyOptInfo  *fkinfo = (ForeignKeyOptInfo *)lfirst(lc);
+
+				/* We only care about keys referencing the current outer relation */
+				if (fkinfo->confrelid != rt_outer->relid)
+					continue;
+
+				/*
+				 * And we don't care about foreign keys with less than two columns
+				 * (those clauses will be handled by the regular estimation, unless
+				 * matched by some other key).
+				 *
+				 * XXX Maybe we should estimate even the single-column keys here,
+				 *     as it's really cheap. But it can't do any cross-table check
+				 *     of MCV lists or whatever clauselist_selectivity() does.
+				 */
+				if (fkinfo->nkeys < 2)
+					continue;
+
+				/*
+				 * Finally check if the foreign key is full matched by clauses,
+				 * and update the selectivity (simply use 1/cardinality of the
+				 * table referenced by the foreign key).
+				 *
+				 * XXX Notice we're using 'rel->tuples' here and not 'rows',
+				 *     because we need the cardinality (before applying clauses).
+				 */
+				if (fkey_is_matched_by_clauses(root, fkinfo, joinquals, inner, outer))
+				{
+					fkeys = lappend(fkeys, fkinfo);
+					*sel *= (1.0 / rel_outer->tuples);
+				}
+
+			}
+
+			/*
+			 * And now check foreign keys in the other direction (defined on
+			 * outer relation, referencing inner).
+			 *
+			 * XXX This does exactly the same thing as the previous loop, so no
+			 *     comments.
+			 *
+			 * TODO Merge those two blocks into a single utility function to
+			 *      reduce the code duplication.
+			 */
+			foreach (lc, rel_outer->fkeylist)
+			{
+				ForeignKeyOptInfo  *fkinfo = (ForeignKeyOptInfo *)lfirst(lc);
+
+				if (fkinfo->confrelid != rt_inner->relid)
+					continue;
+
+				if (fkinfo->nkeys < 2)
+					continue;
+
+				if (fkey_is_matched_by_clauses(root, fkinfo, joinquals, outer, inner))
+				{
+					fkeys = lappend(fkeys, fkinfo);
+					*sel *= (1.0 / rel_inner->tuples);
+				}
+
+			}
+
+		}
+	}
+
+	return fkeys;
+}
+
+/*
+ * filter_fk_join_clauses
+ *		Remove the clauses that were used to match foreign keys (and will be
+ * 		estimated using the selectivity from  keys).
+ *
+ * Once we identify the foreign keys matched by clauses, we need to remove the
+ * clauses so that we don't include them into the estimate twice. This method
+ * performs that - cross-checks the foreign keys and clauses and removes all
+ * clauses matching any of the foreign keys.
+ *
+ * If there are no foreign keys, this simply returns the original list of
+ * clauses. Otherwise it builds a new list (without modifying the source one).
+ */
+static List *
+filter_fk_join_clauses(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *fkeys,
+					   List *joinquals)
+{
+	ListCell   *lc,
+			   *lc2;
+	List	   *clauses = NIL;
+
+	/* if there are no foreign keys, return the original list */
+	if (list_length(fkeys) == 0)
+		return joinquals;
+
+	foreach (lc, joinquals)
+	{
+		Oid				opno;
+		Index			relida, relidb;
+		AttrNumber		attnoa, attnob;
+		Oid				oida, oidb;
+
+		/* was the clause matched by at least one key? */
+		bool			matched = false;
+
+		RestrictInfo   *rinfo = (RestrictInfo*)lfirst(lc);
+
+		/* if the clause is not compatible with foreign keys, just add it */
+		if (! clause_is_fk_compatible(rinfo, &relida, &attnoa,
+											 &relidb, &attnob, &opno))
+		{
+			clauses = lappend(clauses, rinfo);
+			continue;
+		}
+
+		oida = root->simple_rte_array[relida]->relid;
+		oidb = root->simple_rte_array[relidb]->relid;
+
+		/*
+		 * Walk through the matched foreign keys, and try to match the clause
+		 * against each one. We don't know in what order are the Vars listed
+		 * in the clause, so try both ways.
+		 */
+		foreach (lc2, fkeys)
+		{
+			int i;
+			ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo*)lfirst(lc2);
+
+			/* now check the keys - we can stop after finding the first match */
+			for (i = 0; i < fkinfo->nkeys; i++)
+			{
+				/* check the operator first */
+				if (fkinfo->conpfeqop[i] != opno)
+					continue;
+
+				/* now check the attnums */
+				if ((fkinfo->conrelid == oida) && (fkinfo->confrelid == oidb))
+				{
+					if ((fkinfo->confkeys[i] == attnob) &&
+						(fkinfo->conkeys[i] == attnoa))
+					{
+						matched = true;
+						break;
+					}
+				}
+				else if ((fkinfo->conrelid == oidb) && (fkinfo->confrelid == oida))
+				{
+					if ((fkinfo->confkeys[i] == attnoa) &&
+						(fkinfo->conkeys[i] == attnob))
+					{
+						matched = true;
+						break;
+					}
+				}
+			}
+
+			/* no need to try more keys, single match is enough */
+			if (matched)
+				break;
+		}
+
+		/* if a clause was not matched by any foreign key, continue */
+		if (! matched)
+			clauses = lappend(clauses, rinfo);
+
+	}
+
+	return clauses;
+}
+
+
+
+/*
+ * Estimate selectivity of join clauses - either by using foreign key info or
+ * by using the regular clauselist_selectivity().
+ *
+ * If there are multiple join clauses, we check whether the clauses match
+ * a foreign key between the tables - in that case we can use this information
+ * to derive a better estimate (otherwise we'd multiply the selectivities for
+ * each clause, which often causes significant underestimates).
+ *
+ * We only need to care about multi-clause join conditions and simply defer
+ * simple clauses to clauselist_selectivity().
+ *
+ * Let's see a few examples of foreign-key joins, illustrating the estimation
+ * ideas here.
+ *
+ * CREATE TABLE a (
+ *     a1 INT,
+ *     a2 INT,
+ *     a3 INT,
+ *     a4 INT,
+ *     PRIMARY KEY (a1, a2, a3)
+ * );
+ *
+ * CREATE TABLE b (
+ *     b1 INT,
+ *     b2 INT,
+ *     b3 INT,
+ *     b4 INT,
+ *     FOREIGN KEY (b1, b2, b3) REFERENCES (a1, a2, a3)
+ * );
+ *
+ * clauses exactly match a foreign key
+ * -----------------------------------
+ *
+ *   SELECT * FROM a JOIN b ON (a1=b1 AND a2=b2 AND a3=b3);
+ *
+ * - trivial, just use 1/card(a)
+ *
+ * clauses match a foreign key, with additional conditions exist
+ * -------------------------------------------------------------
+ *
+ *   SELECT * FROM a JOIN b ON (a1=b1 AND a2=b2 AND a3=b3 AND a4=b4);
+ *
+ * - trivial, just use 1/card(a) * selectivity(remaining_clauses)
+ *
+ * incomplete foreign key match
+ * ----------------------------
+ *
+ *   SELECT * FROM a JOIN b ON (a1=b1 AND a2=b2);
+ *
+ * - not sure, we'd need to compensate for the "missing part" somehow (we know
+ *   the row exists, but we don't know much many rows - it's likely more than
+ *   unique)
+ *
+ * - one way would be to assume each clause is responsible for (1/card(a))^(1/n)
+ *   where 'n' is number of clauses - this way 'multiplying the FK clauses' would
+ *   gets us the 1/card(a) selectivity if we had all the clauses
+ *
+ * - another thing is we might use 1/card(a) as a lower boundary - we can't
+ *   possibly get lower selectivity, we know the rows exist (also this is not
+ *   based on assumptions like the previous idea)
+ *
+ * multiple distinct foreign keys matching
+ * ---------------------------------------
+ *
+ * CREATE TABLE a (
+ *     a1 INT,
+ *     a2 INT,
+ *     a3 INT,
+ *     a4 INT,
+ *     PRIMARY KEY (a1, a2),
+ *     UNIQUE (a3, a4)
+ * );
+ *
+ * CREATE TABLE b (
+ *     b1 INT,
+ *     b2 INT,
+ *     b3 INT,
+ *     b4 INT,
+ *     FOREIGN KEY (b1, b2) REFERENCES (a1, a2),
+ *     FOREIGN KEY (b3, b4) REFERENCES (a3, a4)
+ * );
+ *
+ * - simply just use 1/card(a) for each foreign key (assumes independence of the
+ *   foreign keys, but well - we're assuming attribute independence so this is
+ *   an improvement)
+ *
+ * multiple overlapping foreign keys matching
+ * ------------------------------------------
+ *
+ * CREATE TABLE a (
+ *     a1 INT,
+ *     a2 INT,
+ *     a3 INT,
+ *     PRIMARY KEY (a1, a2),
+ *     UNIQUE (a2, a3)
+ * );
+ *
+ * CREATE TABLE b (
+ *     b1 INT,
+ *     b2 INT,
+ *     b3 INT,
+ *     b4 INT,
+ *     FOREIGN KEY (b1, b2) REFERENCES (a1, a2),
+ *     FOREIGN KEY (b3, b4) REFERENCES (a2, a3)
+ * );
+ *
+ * - probably just use 1/card(a) for each foreign key, as in the previous
+ *   example (assumes independence of the foreign keys, but well - we're
+ *   assuming attribute independence so this is an improvement)
+ *
+ * There are strange cases with multiple foreign keys, where one FK implies
+ * the other FK. For example consider this:
+ *
+ * CREATE TABLE a (
+ *     a1 INT,
+ *     a2 INT,
+ *     a3 INT,
+ *     UNIQUE (a1, a2, a3),
+ *     UNIQUE (a1, a2)
+ * );
+ *
+ * CREATE TABLE b (
+ *     b1 INT,
+ *     b2 INT,
+ *     b3 INT,
+ *     FOREIGN KEY (b1, b2, b3) REFERENCES a (a1, a2, a3),
+ *     FOREIGN KEY (b1, b2) REFERENCES a (a1, a2)
+ * );
+ *
+ * Clearly the (b1,b2) is implied by (b1,b2,b3) - if the latter exists, then
+ * the former exists too. Not sure how to handle this (or if it's actually
+ * needed).
+ *
+ * Another slightly strange case is FK constraints in both directions (these
+ * statements don't work - the foreign keys need to be established using
+ * ALTER, but for illustration it's sufficient).
+ *
+ * CREATE TABLE a (
+ *     a1 INT,
+ *     a2 INT,
+ *     UNIQUE (a1, a2),
+ *     FOREIGN KEY (a1, a2) REFERENCES a (b1, b2)
+ * );
+ *
+ * CREATE TABLE b (
+ *     b1 INT,
+ *     b2 INT,
+ *     UNIQUE (b1, b2),
+ *     FOREIGN KEY (b1, b2) REFERENCES a (a1, a2)
+ * );
+ *
+ * which effectively establishes 1:1 relationship, or with distinct groups of
+ * columns for each direction
+ *
+ * CREATE TABLE a (
+ *     a1 INT,
+ *     a2 INT,
+ *     a3 INT,
+ *     a4 INT,
+ *     UNIQUE (a1, a2),
+ *     FOREIGN KEY (a3, a4) REFERENCES a (b1, b2)
+ * );
+ *
+ * CREATE TABLE b (
+ *     b1 INT,
+ *     b2 INT,
+ *     b3 INT,
+ *     b4 INT,
+ *     UNIQUE (b1, b2),
+ *     FOREIGN KEY (b3, b4) REFERENCES a (a1, a2)
+ * );
+ *
+ * which creates a cycle of foreign keys.
+ *
+ * In the first case the foreign keys should be counted only once into the
+ * selectivity, because it's effectively a 1:1 relationship - each row has
+ * to have one matching row in the other table (not matched by other) rows.
+ *
+ * In the other case, it's probably right to factor in both foreign keys.
+ */
+static Selectivity
+clauselist_join_selectivity(PlannerInfo *root, List *joinquals, int varno,
+							JoinType jointype, SpecialJoinInfo *sjinfo)
+{
+	Selectivity sel = 1.0;
+
+	List	   *fkeys;		/* list of satisfied foreign keys */
+	List	   *unmatched;	/* clauses remaining after removing FK clauses */
+
+	Assert(list_length(joinquals) >= 0);
+
+	/*
+	 * If we only have a single clause, we don't need to mess with the foreign
+	 * keys - that's only useful with multi-column clauses anyway. Just use the
+	 * simple clauselist_selectivity.
+	 */
+	if (list_length(joinquals) <= 1)
+		return clauselist_selectivity(root,
+									  joinquals,
+									  0,
+									  jointype,
+									  sjinfo);
+
+	/*
+	 * First we'll identify foreign keys that are fully matched by the join
+	 * clauses, and we'll update the selectivity accordingly while doing so.
+	 */
+	fkeys = find_satisfied_fkeys(root, sjinfo, joinquals, &sel);
+
+	/*
+	 * Now that we have the foreign keys, we can get rid of the clauses
+	 * matching any of them, and only keep the remaining clauses, so that
+	 * we can estimate them using the regular selectivity estimation.
+	 */
+	unmatched = filter_fk_join_clauses(root, sjinfo, fkeys, joinquals);
+
+	/*
+	 * Estimate the remaining clauses (not matching any FK), if still have any.
+	 */
+	if (list_length(unmatched) > 0)
+	{
+		sel *= clauselist_selectivity(root,
+									  unmatched,
+									  0,
+									  jointype,
+									  sjinfo);
+
+		/* Only free the list if we actually found any foreign keys. */
+		if (list_length(fkeys) > 0)
+			list_free(unmatched);
+	}
+
+	return sel;
+}
+
+/*
  * calc_joinrel_size_estimate
  *		Workhorse for set_joinrel_size_estimates and
  *		get_parameterized_joinrel_size.
@@ -3777,11 +4385,12 @@ calc_joinrel_size_estimate(PlannerInfo *root,
 		}
 
 		/* Get the separate selectivities */
-		jselec = clauselist_selectivity(root,
-										joinquals,
-										0,
-										jointype,
-										sjinfo);
+		jselec = clauselist_join_selectivity(root,
+											 joinquals,
+											 0,
+											 jointype,
+											 sjinfo);
+
 		pselec = clauselist_selectivity(root,
 										pushedquals,
 										0,
@@ -3794,11 +4403,11 @@ calc_joinrel_size_estimate(PlannerInfo *root,
 	}
 	else
 	{
-		jselec = clauselist_selectivity(root,
-										restrictlist,
-										0,
-										jointype,
-										sjinfo);
+		jselec = clauselist_join_selectivity(root,
+											 restrictlist,
+											 0,
+											 jointype,
+											 sjinfo);
 		pselec = 0.0;			/* not used, keep compiler quiet */
 	}
 
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 7912b15..05c8698 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -562,7 +562,6 @@ remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
 	return result;
 }
 
-
 /*
  * query_supports_distinctness - could the query possibly be proven distinct
  *		on some set of output columns?
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 9442e5f..fbc5579 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -27,6 +27,7 @@
 #include "catalog/catalog.h"
 #include "catalog/dependency.h"
 #include "catalog/heap.h"
+#include "catalog/pg_constraint.h"
 #include "foreign/fdwapi.h"
 #include "miscadmin.h"
 #include "nodes/makefuncs.h"
@@ -40,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"
 
@@ -93,6 +95,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	Relation	relation;
 	bool		hasindex;
 	List	   *indexinfos = NIL;
+	List	   *fkinfos = NIL;
 
 	/*
 	 * We need not lock the relation since it was already locked, either by
@@ -380,6 +383,88 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	}
 
 	rel->indexlist = indexinfos;
+ 
+	/*
+	 * TODO Can we do something like (hasindex) here? Is it necessary? The
+	 *      trouble with that is that we don't have a good place to reset that
+	 *      flag (relhasindex is reset by vacuum, but is has nothing to do with
+	 *      foreign keys at this point).
+	 */
+	if (true)
+	{
+		List	   *fkoidlist;
+		ListCell   *l;
+
+		fkoidlist = RelationGetFKeyList(relation);
+
+		foreach(l, fkoidlist)
+		{
+			int			i;
+			ArrayType  *arr;
+			Datum		adatum;
+			bool		isnull;
+			int			numkeys;
+			Oid			fkoid = lfirst_oid(l);
+
+			HeapTuple	htup = SearchSysCache1(CONSTROID, ObjectIdGetDatum(fkoid));
+			Form_pg_constraint constraint = (Form_pg_constraint) GETSTRUCT(htup);
+
+			ForeignKeyOptInfo *info;
+
+			Assert(constraint->contype == CONSTRAINT_FOREIGN);
+
+			info = makeNode(ForeignKeyOptInfo);
+
+			info->conrelid = constraint->conrelid;
+			info->confrelid = constraint->confrelid;
+
+			/* conkey */
+			adatum = SysCacheGetAttr(CONSTROID, htup,
+									 Anum_pg_constraint_conkey, &isnull);
+			Assert(!isnull);
+
+			arr = DatumGetArrayTypeP(adatum);
+			numkeys = ARR_DIMS(arr)[0];
+			info->conkeys = (int*)palloc0(numkeys * sizeof(int));
+
+			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);
+			numkeys = ARR_DIMS(arr)[0];
+			info->confkeys = (int*)palloc0(numkeys * sizeof(int));
+
+			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);
+			numkeys = ARR_DIMS(arr)[0];
+			info->conpfeqop = (Oid*)palloc0(numkeys * sizeof(Oid));
+
+			for (i = 0; i < numkeys; i++)
+				info->conpfeqop[i] = ((Oid *) ARR_DATA_PTR(arr))[i];
+
+			info->nkeys = numkeys;
+
+			ReleaseSysCache(htup);
+
+			fkinfos = lcons(info, fkinfos);
+		}
+
+		list_free(fkoidlist);
+	}
+
+	rel->fkeylist = fkinfos;
 
 	/* Grab foreign-table info using the relcache, while we have it */
 	if (relation->rd_rel->relkind == RELKIND_FOREIGN_TABLE)
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index 44e9509..a599ca5 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -3896,6 +3896,73 @@ RelationGetIndexList(Relation relation)
 }
 
 /*
+ * RelationGetFKeyList -- get a list of foreign key oids
+ *
+ * TODO blah blah blah
+ */
+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_fkeyvalid)
+		return list_copy(relation->rd_fkeylist);
+
+	/*
+	 * 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);
+
+		/* return only foreign keys */
+		if (constraint->contype != CONSTRAINT_FOREIGN)
+			continue;
+
+		/* Add index's OID to result list in the proper order */
+		result = insert_ordered_oid(result, HeapTupleGetOid(htup));
+	}
+
+	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);
+	relation->rd_fkeyvalid = true;
+	MemoryContextSwitchTo(oldcxt);
+
+	/* Don't leak the old list, if there is one */
+	list_free(oldlist);
+
+	return result;
+}
+
+/*
  * insert_ordered_oid
  *		Insert a new Oid into a sorted list of Oids, preserving ordering
  *
@@ -4864,6 +4931,8 @@ load_relcache_init_file(bool shared)
 		rel->rd_indexattr = NULL;
 		rel->rd_keyattr = NULL;
 		rel->rd_idattr = NULL;
+		rel->rd_fkeylist = NIL;
+		rel->rd_fkeyvalid = false;
 		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 748e434..31b40af 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -221,6 +221,7 @@ typedef enum NodeTag
 	T_PlannerGlobal,
 	T_RelOptInfo,
 	T_IndexOptInfo,
+	T_ForeignKeyOptInfo,
 	T_ParamPathInfo,
 	T_Path,
 	T_IndexPath,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 5dc23d9..b887949 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -468,6 +468,7 @@ typedef struct RelOptInfo
 	Relids		lateral_relids; /* minimum parameterization of 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;
@@ -562,6 +563,20 @@ typedef struct IndexOptInfo
 	bool		amhasgetbitmap; /* does AM have amgetbitmap interface? */
 } IndexOptInfo;
 
+/* TODO add info*/
+typedef struct ForeignKeyOptInfo
+{
+	NodeTag		type;
+
+	Oid			conrelid;
+	Oid			confrelid;
+
+	int			nkeys;
+	int		   *conkeys;
+	int		   *confkeys;
+	Oid		   *conpfeqop;
+
+} ForeignKeyOptInfo;
 
 /*
  * EquivalenceClasses
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 87123a5..da1fd58 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -73,6 +73,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 8a55a09..c56cf8a 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -79,6 +79,7 @@ typedef struct RelationData
 	bool		rd_isvalid;		/* relcache entry is valid */
 	char		rd_indexvalid;	/* state of rd_indexlist: 0 = not valid, 1 =
 								 * valid, 2 = temporarily forced */
+	bool		rd_fkeyvalid;	/* state of rd_fkeylist: 0 = not valid, 1 = valid */
 
 	/*
 	 * rd_createSubid is the ID of the highest subtransaction the rel has
@@ -112,6 +113,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;		/* OIDs of foreign keys */
+
 	/* 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 6953281..8878478 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);
-- 
1.9.3

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index e1b49d5..8dbfeba 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1907,6 +1907,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)
 {
 	/*
@@ -3297,6 +3307,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 d107d76..d30d715 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3732,6 +3732,251 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
 }
 
 /*
+ * find_best_match_foreign_key
+ *		Returns a Bitmapset with bits set for each 0 based index of 'joinquals'
+ *		which to a foreign key which is defined on fkrel.
+ *
+ * Note: in the event that there's more than 1 foreign key between these two
+ * relations, the largest match, i.e. the bitmask for the one with the most
+ * matching 'joinquals' items, is returned.
+ *
+ * XXX it's possible to trick this code when the joinquals contain duplicate
+ * quals. Is this worth fixing?
+ */
+static Bitmapset *
+find_best_match_foreign_key(PlannerInfo *root, RelOptInfo *fkrel,
+							RelOptInfo *foreignrel, List *joinquals)
+{
+	Bitmapset	   *bestmatch;
+	Bitmapset	   *usefulquals;
+	ListCell	   *lc;
+	int				lstidx;
+	Oid				frelid;
+
+	/* fast path out when there's no foreign keys on fkrel */
+	if (fkrel->fkeylist == NIL)
+		return NULL;
+
+	bestmatch = NULL;
+	lstidx = -1;
+	usefulquals = NULL;
+
+	/*
+	 * First build a bitmapset with all possibly useful quals. This will save
+	 * from having to do this for each foreign key later. The only quals that
+	 * are useful to us are in the form "var op var", so here we'll ignore
+	 * things like "function(var1, var2)".
+	 */
+	foreach(lc, joinquals)
+	{
+		RestrictInfo   *rinfo = (RestrictInfo *) lfirst(lc);
+		OpExpr		   *clause;
+		Var			   *leftvar, *rightvar;
+
+		/*
+		 * Increment this at the start of the loop to save doing it before each
+		 * continue statement.
+		 */
+		lstidx++;
+
+		if (!IsA(rinfo, RestrictInfo))
+			continue;
+
+		if (!IsA(rinfo->clause, OpExpr))
+			continue;
+
+		clause = (OpExpr *) rinfo->clause;
+
+		if (list_length(clause->args) != 2)
+			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;
+
+		usefulquals = bms_add_member(usefulquals, lstidx);
+	}
+
+	frelid = root->simple_rte_array[foreignrel->relid]->relid;
+
+	/* now check the matches for each foreign key defined on the fkrel */
+	foreach(lc, fkrel->fkeylist)
+	{
+		ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+		Bitmapset *matches;
+		int i;
+
+		/* skip any foreign keys which don't reference frelid */
+		if (fkinfo->confrelid != frelid)
+			continue;
+
+		matches = NULL;
+
+		/*
+		 * Loop over each column of the foreign key and build a bitmap index
+		 * of each joinqual which matches. Note that we don't stop when we find
+		 * the first match, as the expression could be duplicated in the
+		 * joinquals, and we want to match as many as possible.
+		 */
+		for (i = 0; i < fkinfo->nkeys; i++)
+		{
+			ListCell *lc2;
+
+			lstidx = -1;
+			foreach(lc2, joinquals)
+			{
+				RestrictInfo   *rinfo;
+				OpExpr		   *clause;
+				Var			   *leftvar;
+				Var			   *rightvar;
+
+				lstidx++;
+
+				/* skip anything we didn't mark as useful above. */
+				if (!bms_is_member(lstidx, usefulquals))
+					continue;
+
+				/*
+				 * Here we can safely assume that we have an OpExpr, in  the
+				 * from of "var op var"
+				 */
+				rinfo = (RestrictInfo *) lfirst(lc2);
+				clause = (OpExpr *) rinfo->clause;
+
+				/* skip if the operator does not match */
+				if (clause->opno != fkinfo->conpfeqop[i])
+					continue;
+
+				leftvar = (Var *) get_leftop((Expr *) clause);
+				rightvar = (Var *) get_rightop((Expr *) clause);
+
+				/*
+				 * Check if the OpExpr matches the foreign key. Remember that
+				 * this could be written with the Vars in either order, so we
+				 * test both permutations of the expression.
+				 */
+				if (fkinfo->confkeys[i] == leftvar->varattno &&
+					fkinfo->conkeys[i] == rightvar->varattno)
+					matches = bms_add_member(matches, lstidx);
+
+				else if (fkinfo->confkeys[i] == rightvar->varattno &&
+					fkinfo->conkeys[i] == leftvar->varattno)
+					matches = bms_add_member(matches, lstidx);
+			}
+		}
+
+		/* Is this match better than the current best match? */
+		if (bms_num_members(matches) > bms_num_members(bestmatch))
+		{
+			bms_free(bestmatch);
+			bestmatch = matches;
+		}
+	}
+
+	return bestmatch;
+}
+
+/*
+ * 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().
+ *
+ * XXX is it worth adding code to do something smart when we only get a partial
+ * foreign key match?
+ */
+static Selectivity
+clauselist_join_selectivity(PlannerInfo *root, List *joinquals,
+							JoinType jointype, SpecialJoinInfo *sjinfo)
+{
+	int outerrelid;
+	int innerrelid;
+
+	/*
+	 * Since foreign keys can only references a single relation, and each
+	 * foreign key belongs to at most a single relation, we require that only
+	 * a single relation be at either side of the join condition. We'll fall
+	 * back on clauselist_selectivity() if this is not the case.
+	 */
+	if (bms_get_singleton_member(sjinfo->min_righthand, &innerrelid) &&
+		bms_get_singleton_member(sjinfo->min_lefthand, &outerrelid))
+	{
+		Bitmapset *outer2inner, *inner2outer;
+		RelOptInfo *innerrel = find_base_rel(root, innerrelid);
+		RelOptInfo *outerrel = find_base_rel(root, outerrelid);
+
+		/* check which quals are matched by a foreign key referencing the innerrel */
+		outer2inner = find_best_match_foreign_key(root, outerrel, innerrel, joinquals);
+
+		/* do the same again, but with relations swapped */
+		inner2outer = find_best_match_foreign_key(root, innerrel, outerrel, joinquals);
+
+		/*
+		 * did we find any matches at all? If so we need to see which one is
+		 * the best/longest match
+		 */
+		if (outer2inner || inner2outer)
+		{
+			Selectivity sel;
+			ListCell *lc;
+			int lstidx;
+			List *nonfkeyclauses;
+
+			/* either could be NULL, but bms_num_members will handle that */
+			if (bms_num_members(outer2inner) < bms_num_members(inner2outer))
+			{
+				/*
+				 * We can now disgard the lesser of the two and save the best
+				 * match into one of the bitmaps. Let's just use outer2inner
+				 */
+				bms_free(outer2inner);
+				outer2inner = inner2outer;
+
+				if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+					sel = 1.0;
+				else
+					sel = 1.0 / Max(outerrel->tuples, 1.0);
+			}
+			else
+			{
+				bms_free(inner2outer);
+
+				if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+					sel = 1.0;
+				else
+					sel = 1.0 / Max(innerrel->tuples, 1.0);
+			}
+
+			/*
+			 * build a list of all non-fkey joinquals, we'll need to enlist
+			 * clauselist_selectivity() to estimate these
+			 */
+			lstidx = 0;
+			nonfkeyclauses = NIL;
+			foreach (lc, joinquals)
+			{
+				if (!bms_is_member(lstidx, outer2inner))
+					nonfkeyclauses = lappend(nonfkeyclauses, lfirst(lc));
+				lstidx++;
+			}
+			return sel * clauselist_selectivity(root, nonfkeyclauses, 0, jointype, sjinfo);
+		}
+	}
+
+	/* perform normal estimation without the help of foreign keys */
+	return clauselist_selectivity(root, joinquals, 0, jointype, sjinfo);
+}
+
+/*
  * calc_joinrel_size_estimate
  *		Workhorse for set_joinrel_size_estimates and
  *		get_parameterized_joinrel_size.
@@ -3777,11 +4022,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,
@@ -3794,11 +4039,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/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 9442e5f..dbe6038 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -27,6 +27,7 @@
 #include "catalog/catalog.h"
 #include "catalog/dependency.h"
 #include "catalog/heap.h"
+#include "catalog/pg_constraint.h"
 #include "foreign/fdwapi.h"
 #include "miscadmin.h"
 #include "nodes/makefuncs.h"
@@ -40,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"
 
@@ -93,6 +95,9 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	Relation	relation;
 	bool		hasindex;
 	List	   *indexinfos = NIL;
+	List	   *fkinfos = NIL;
+	List	   *fkoidlist;
+	ListCell   *l;
 
 	/*
 	 * We need not lock the relation since it was already locked, either by
@@ -140,7 +145,6 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	if (hasindex)
 	{
 		List	   *indexoidlist;
-		ListCell   *l;
 		LOCKMODE	lmode;
 
 		indexoidlist = RelationGetIndexList(relation);
@@ -380,6 +384,77 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	}
 
 	rel->indexlist = indexinfos;
+ 
+	/* load foreign keys */
+	fkoidlist = RelationGetFKeyList(relation);
+
+	foreach(l, fkoidlist)
+	{
+		int			i;
+		ArrayType  *arr;
+		Datum		adatum;
+		bool		isnull;
+		int			numkeys;
+		Oid			fkoid = lfirst_oid(l);
+
+		HeapTuple	htup = SearchSysCache1(CONSTROID, ObjectIdGetDatum(fkoid));
+		Form_pg_constraint constraint = (Form_pg_constraint) GETSTRUCT(htup);
+
+		ForeignKeyOptInfo *info;
+
+		Assert(constraint->contype == CONSTRAINT_FOREIGN);
+
+		info = makeNode(ForeignKeyOptInfo);
+
+		info->conrelid = constraint->conrelid;
+		info->confrelid = constraint->confrelid;
+
+		/* conkey */
+		adatum = SysCacheGetAttr(CONSTROID, htup,
+									Anum_pg_constraint_conkey, &isnull);
+		Assert(!isnull);
+
+		arr = DatumGetArrayTypeP(adatum);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conkeys = (int*)palloc0(numkeys * sizeof(int));
+
+		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);
+		numkeys = ARR_DIMS(arr)[0];
+		info->confkeys = (int*)palloc0(numkeys * sizeof(int));
+
+		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);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conpfeqop = (Oid*)palloc0(numkeys * sizeof(Oid));
+
+		for (i = 0; i < numkeys; i++)
+			info->conpfeqop[i] = ((Oid *) ARR_DATA_PTR(arr))[i];
+
+		info->nkeys = numkeys;
+
+		ReleaseSysCache(htup);
+
+		fkinfos = lcons(info, fkinfos);
+	}
+
+	list_free(fkoidlist);
+
+	rel->fkeylist = fkinfos;
 
 	/* Grab foreign-table info using the relcache, while we have it */
 	if (relation->rd_rel->relkind == RELKIND_FOREIGN_TABLE)
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index 9c3d096..3ae9022 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -3923,6 +3923,73 @@ RelationGetIndexList(Relation relation)
 }
 
 /*
+ * RelationGetFKeyList -- get a list of foreign key oids
+ *
+ * TODO blah blah blah
+ */
+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_fkeyvalid)
+		return list_copy(relation->rd_fkeylist);
+
+	/*
+	 * 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);
+
+		/* return only foreign keys */
+		if (constraint->contype != CONSTRAINT_FOREIGN)
+			continue;
+
+		/* Add index's OID to result list in the proper order */
+		result = insert_ordered_oid(result, HeapTupleGetOid(htup));
+	}
+
+	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);
+	relation->rd_fkeyvalid = true;
+	MemoryContextSwitchTo(oldcxt);
+
+	/* Don't leak the old list, if there is one */
+	list_free(oldlist);
+
+	return result;
+}
+
+/*
  * insert_ordered_oid
  *		Insert a new Oid into a sorted list of Oids, preserving ordering
  *
@@ -4891,6 +4958,8 @@ load_relcache_init_file(bool shared)
 		rel->rd_indexattr = NULL;
 		rel->rd_keyattr = NULL;
 		rel->rd_idattr = NULL;
+		rel->rd_fkeylist = NIL;
+		rel->rd_fkeyvalid = false;
 		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 274480e..5c40b83 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -221,6 +221,7 @@ typedef enum NodeTag
 	T_PlannerGlobal,
 	T_RelOptInfo,
 	T_IndexOptInfo,
+	T_ForeignKeyOptInfo,
 	T_ParamPathInfo,
 	T_Path,
 	T_IndexPath,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 79bed33..8ce35e7 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -472,6 +472,7 @@ typedef struct RelOptInfo
 	Relids		lateral_relids; /* minimum parameterization of 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;
@@ -566,6 +567,20 @@ typedef struct IndexOptInfo
 	bool		amhasgetbitmap; /* does AM have amgetbitmap interface? */
 } IndexOptInfo;
 
+/* TODO add info*/
+typedef struct ForeignKeyOptInfo
+{
+	NodeTag		type;
+
+	Oid			conrelid;
+	Oid			confrelid;
+
+	int			nkeys;
+	int		   *conkeys;
+	int		   *confkeys;
+	Oid		   *conpfeqop;
+
+} ForeignKeyOptInfo;
 
 /*
  * EquivalenceClasses
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 87123a5..da1fd58 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -73,6 +73,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 8a55a09..c56cf8a 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -79,6 +79,7 @@ typedef struct RelationData
 	bool		rd_isvalid;		/* relcache entry is valid */
 	char		rd_indexvalid;	/* state of rd_indexlist: 0 = not valid, 1 =
 								 * valid, 2 = temporarily forced */
+	bool		rd_fkeyvalid;	/* state of rd_fkeylist: 0 = not valid, 1 = valid */
 
 	/*
 	 * rd_createSubid is the ID of the highest subtransaction the rel has
@@ -112,6 +113,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;		/* OIDs of foreign keys */
+
 	/* 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 6953281..8878478 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/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index c00fa30..d30d715 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3732,611 +3732,248 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
 }
 
 /*
- * clause_is_fk_compatible
- *		Verify that the clause may be compatible with foreign keys (i.e. it's
- * 		a simple operator clause with two Vars, referencing two different
- * 		relations).
+ * find_best_match_foreign_key
+ *		Returns a Bitmapset with bits set for each 0 based index of 'joinquals'
+ *		which to a foreign key which is defined on fkrel.
  *
- * This only checks form of the clause (and returns 'true' if it may match
- * a foreign key), but does not cross-check the clause against existing foreign
- * keys for example.
+ * Note: in the event that there's more than 1 foreign key between these two
+ * relations, the largest match, i.e. the bitmask for the one with the most
+ * matching 'joinquals' items, is returned.
  *
- * It also extracts data from the clause - rangetable indexes and attnums for
- * each Var (if the function returns 'false' then those values are undefined
- * and may contain garbage).
+ * XXX it's possible to trick this code when the joinquals contain duplicate
+ * quals. Is this worth fixing?
  */
-static bool
-clause_is_fk_compatible(RestrictInfo *rinfo,
-						Index *varnoa, AttrNumber *attnoa,
-						Index *varnob, AttrNumber *attnob,
-						Oid *opno)
+static Bitmapset *
+find_best_match_foreign_key(PlannerInfo *root, RelOptInfo *fkrel,
+							RelOptInfo *foreignrel, List *joinquals)
 {
-	OpExpr *clause;
-	Var	   *var0, *var1;
-
-	/* We only expect restriction clauses here, with operator expression. */
-
-	if (! IsA(rinfo, RestrictInfo))
-		return false;
-
-	if (! IsA(rinfo->clause, OpExpr))
-		return false;
+	Bitmapset	   *bestmatch;
+	Bitmapset	   *usefulquals;
+	ListCell	   *lc;
+	int				lstidx;
+	Oid				frelid;
 
-	clause = (OpExpr*)rinfo->clause;
-
-	/* The clause has to use exactly two simple variables. */
-
-	if (list_length(clause->args) != 2)
-		return false;
-
-	var0 = list_nth(clause->args, 0);
-	var1 = list_nth(clause->args, 1);
-
-	if (! (IsA(var0, Var) && IsA(var1, Var)))
-		return false;
+	/* fast path out when there's no foreign keys on fkrel */
+	if (fkrel->fkeylist == NIL)
+		return NULL;
 
-	/* The variables has to reference two different rangetable entries. */
-
-	if (var0->varno == var1->varno)
-		return false;
+	bestmatch = NULL;
+	lstidx = -1;
+	usefulquals = NULL;
 
 	/*
-	 * At this point we know the clause has the right structure, so extract
-	 * the interesting info we'll need outside. We don't really track which
-	 * relation is inner/outer, so we'll check both directions.
+	 * First build a bitmapset with all possibly useful quals. This will save
+	 * from having to do this for each foreign key later. The only quals that
+	 * are useful to us are in the form "var op var", so here we'll ignore
+	 * things like "function(var1, var2)".
 	 */
+	foreach(lc, joinquals)
+	{
+		RestrictInfo   *rinfo = (RestrictInfo *) lfirst(lc);
+		OpExpr		   *clause;
+		Var			   *leftvar, *rightvar;
 
-	*varnoa = var0->varno;
-	*attnoa = var0->varattno;
-
-	*varnob = var1->varno;
-	*attnob = var1->varattno;
+		/*
+		 * Increment this at the start of the loop to save doing it before each
+		 * continue statement.
+		 */
+		lstidx++;
 
-	*opno = clause->opno;
+		if (!IsA(rinfo, RestrictInfo))
+			continue;
 
-	return true;
-}
+		if (!IsA(rinfo->clause, OpExpr))
+			continue;
 
+		clause = (OpExpr *) rinfo->clause;
 
-/*
- * fkey_is_matched_by_clauses
- * 		Check whether the foreign key is "fully" matched by the clauses.
- *
- * This checks whether the foreign key is fully matched by clauses, i.e. if
- * there's a clause matching perfectly all the parts of the foreign key.
- */
-static bool
-fkey_is_matched_by_clauses(PlannerInfo *root, ForeignKeyOptInfo *fkinfo,
-						   List *clauses, int relid, int frelid)
-{
-	int			i;
-	ListCell   *lc;
-	bool		r;
-	bool	   *matched;
+		if (list_length(clause->args) != 2)
+			continue;
 
-	/* we should only get multi-column foreign keys here */
-	Assert(fkinfo->nkeys > 1);
+		leftvar = (Var *) get_leftop((Expr *) clause);
+		rightvar = (Var *) get_rightop((Expr *) clause);
 
-	/* flags for each part of the foreign key */
-	matched = palloc0(fkinfo->nkeys);
+		/* Foreign keys only support Vars, so ignore anything more complex */
+		if (!IsA(leftvar, Var) || !IsA(rightvar, Var))
+			continue;
 
-	foreach (lc, clauses)
-	{
-		RestrictInfo   *rinfo = (RestrictInfo*)lfirst(lc);
+		usefulquals = bms_add_member(usefulquals, lstidx);
+	}
 
-		/* info extracted from the clause (opno, varnos and varattnos) */
-		Oid				opno;
-		Index			relida, relidb;
-		AttrNumber		attnoa, attnob;
+	frelid = root->simple_rte_array[foreignrel->relid]->relid;
 
-		/* we'll look this up in the simple_rte_array table */
-		Oid				oida, oidb;
+	/* now check the matches for each foreign key defined on the fkrel */
+	foreach(lc, fkrel->fkeylist)
+	{
+		ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+		Bitmapset *matches;
+		int i;
 
-		/*
-		 * If the clause has structure incompatible with foreign keys (not an
-		 * operator clause with two Var nodes), just skip it.
-		 */
-		if (! clause_is_fk_compatible(rinfo, &relida, &attnoa,
-											 &relidb, &attnob, &opno))
+		/* skip any foreign keys which don't reference frelid */
+		if (fkinfo->confrelid != frelid)
 			continue;
 
-		/* lookup range table entries for the indexes */
-		oida = root->simple_rte_array[relida]->relid;
-		oidb = root->simple_rte_array[relidb]->relid;
+		matches = NULL;
 
 		/*
-		 * Check if the clause matches any part of the foreign key.
+		 * Loop over each column of the foreign key and build a bitmap index
+		 * of each joinqual which matches. Note that we don't stop when we find
+		 * the first match, as the expression could be duplicated in the
+		 * joinquals, and we want to match as many as possible.
 		 */
 		for (i = 0; i < fkinfo->nkeys; i++)
 		{
-			/* if the operator does not match, try next key */
-			if (! fkinfo->conpfeqop[i] == opno)
-				continue;
-
-			/*
-			 * We don't know in what order the clause lists the Vars, so we'll check
-			 * the foreign key in both directions (it does not really matter).
-			 */
-			if ((oida == fkinfo->conrelid) && (oidb == fkinfo->confrelid))
-			{
-				if ((fkinfo->confkeys[i] == attnob) &&
-					(fkinfo->conkeys[i] == attnoa))
-					matched[i] = true;
-			}
-
-			if ((oida == fkinfo->confrelid) && (oidb == fkinfo->conrelid))
-			{
-				if ((fkinfo->confkeys[i] == attnoa) &&
-					(fkinfo->conkeys[i] == attnob))
-						matched[i] = true;
-			}
-		}
-	}
-
-	/* return 'true' if all the parts of the foreign key were matched */
-	r = true;
-	for (i = 0; i < fkinfo->nkeys; i++)
-		r &= matched[i];
-
-	pfree(matched);
-
-	return r;
-}
-
-/*
- * find_satisfied_fkeys
- * 		Searches for all foreign keys fully-satisfied by the join clauses.
- *
- * A join is fully-satisfied if all the parts are matched by at least one
- * join condition (same operator and attnos).
- *
- * This returns a list of foreign keys of identified foreign keys (or NIL),
- * and also selectivity for all the (matched) foreign keys.
- */
-static List *
-find_satisfied_fkeys(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *joinquals,
-					 Selectivity *sel)
-{
-	int	inner, outer;
-	List *fkeys = NIL;
-
-	/*
-	 * We'll take all combinations of inner/outer relations, and check if
-	 * there are foreign keys between them. If we found a foreign key for
-	 * the pair of base relations, we'll try matching it to clauses.
-	 *
-	 * We don't know in which direction the foreign keys are created, so
-	 * we'll check both directions (it's allways between inner and outer
-	 * side of the join).
-	 */
-
-	inner = -1;
-	while ((inner = bms_next_member(sjinfo->min_righthand, inner)) >= 0)
-	{
-		RelOptInfo *rel_inner = find_base_rel(root, inner);
-		RangeTblEntry *rt_inner = planner_rt_fetch(inner, root);
-
-		Assert(rel_inner->reloptkind == RELOPT_BASEREL);
-
-		outer = -1;
-		while ((outer = bms_next_member(sjinfo->min_lefthand, outer)) >= 0)
-		{
-			ListCell   *lc;
-			RelOptInfo *rel_outer = find_base_rel(root, outer);
-			RangeTblEntry *rt_outer = planner_rt_fetch(outer, root);
-
-			Assert(rel_outer->reloptkind == RELOPT_BASEREL);
+			ListCell *lc2;
 
-			/*
-			 * Walk through foreign keys defined on the inner side, referencing
-			 * relation on the outer side.
-			 */
-			foreach (lc, rel_inner->fkeylist)
+			lstidx = -1;
+			foreach(lc2, joinquals)
 			{
-				ForeignKeyOptInfo  *fkinfo = (ForeignKeyOptInfo *)lfirst(lc);
+				RestrictInfo   *rinfo;
+				OpExpr		   *clause;
+				Var			   *leftvar;
+				Var			   *rightvar;
 
-				/* We only care about keys referencing the current outer relation */
-				if (fkinfo->confrelid != rt_outer->relid)
-					continue;
+				lstidx++;
 
-				/*
-				 * And we don't care about foreign keys with less than two columns
-				 * (those clauses will be handled by the regular estimation, unless
-				 * matched by some other key).
-				 *
-				 * XXX Maybe we should estimate even the single-column keys here,
-				 *     as it's really cheap. But it can't do any cross-table check
-				 *     of MCV lists or whatever clauselist_selectivity() does.
-				 */
-				if (fkinfo->nkeys < 2)
+				/* skip anything we didn't mark as useful above. */
+				if (!bms_is_member(lstidx, usefulquals))
 					continue;
 
 				/*
-				 * Finally check if the foreign key is full matched by clauses,
-				 * and update the selectivity (simply use 1/cardinality of the
-				 * table referenced by the foreign key).
-				 *
-				 * XXX Notice we're using 'rel->tuples' here and not 'rows',
-				 *     because we need the cardinality (before applying clauses).
+				 * Here we can safely assume that we have an OpExpr, in  the
+				 * from of "var op var"
 				 */
-				if (fkey_is_matched_by_clauses(root, fkinfo, joinquals, inner, outer))
-				{
-					fkeys = lappend(fkeys, fkinfo);
-					*sel *= (1.0 / rel_outer->tuples);
-				}
-
-			}
-
-			/*
-			 * And now check foreign keys in the other direction (defined on
-			 * outer relation, referencing inner).
-			 *
-			 * XXX This does exactly the same thing as the previous loop, so no
-			 *     comments.
-			 *
-			 * TODO Merge those two blocks into a single utility function to
-			 *      reduce the code duplication.
-			 */
-			foreach (lc, rel_outer->fkeylist)
-			{
-				ForeignKeyOptInfo  *fkinfo = (ForeignKeyOptInfo *)lfirst(lc);
+				rinfo = (RestrictInfo *) lfirst(lc2);
+				clause = (OpExpr *) rinfo->clause;
 
-				if (fkinfo->confrelid != rt_inner->relid)
+				/* skip if the operator does not match */
+				if (clause->opno != fkinfo->conpfeqop[i])
 					continue;
 
-				if (fkinfo->nkeys < 2)
-					continue;
+				leftvar = (Var *) get_leftop((Expr *) clause);
+				rightvar = (Var *) get_rightop((Expr *) clause);
 
-				if (fkey_is_matched_by_clauses(root, fkinfo, joinquals, outer, inner))
-				{
-					fkeys = lappend(fkeys, fkinfo);
-					*sel *= (1.0 / rel_inner->tuples);
-				}
+				/*
+				 * Check if the OpExpr matches the foreign key. Remember that
+				 * this could be written with the Vars in either order, so we
+				 * test both permutations of the expression.
+				 */
+				if (fkinfo->confkeys[i] == leftvar->varattno &&
+					fkinfo->conkeys[i] == rightvar->varattno)
+					matches = bms_add_member(matches, lstidx);
 
+				else if (fkinfo->confkeys[i] == rightvar->varattno &&
+					fkinfo->conkeys[i] == leftvar->varattno)
+					matches = bms_add_member(matches, lstidx);
 			}
+		}
 
+		/* Is this match better than the current best match? */
+		if (bms_num_members(matches) > bms_num_members(bestmatch))
+		{
+			bms_free(bestmatch);
+			bestmatch = matches;
 		}
 	}
 
-	return fkeys;
+	return bestmatch;
 }
 
 /*
- * filter_fk_join_clauses
- *		Remove the clauses that were used to match foreign keys (and will be
- * 		estimated using the selectivity from  keys).
- *
- * Once we identify the foreign keys matched by clauses, we need to remove the
- * clauses so that we don't include them into the estimate twice. This method
- * performs that - cross-checks the foreign keys and clauses and removes all
- * clauses matching any of the foreign keys.
- *
- * If there are no foreign keys, this simply returns the original list of
- * clauses. Otherwise it builds a new list (without modifying the source one).
+ * 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().
+ *
+ * XXX is it worth adding code to do something smart when we only get a partial
+ * foreign key match?
  */
-static List *
-filter_fk_join_clauses(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *fkeys,
-					   List *joinquals)
+static Selectivity
+clauselist_join_selectivity(PlannerInfo *root, List *joinquals,
+							JoinType jointype, SpecialJoinInfo *sjinfo)
 {
-	ListCell   *lc,
-			   *lc2;
-	List	   *clauses = NIL;
-
-	/* if there are no foreign keys, return the original list */
-	if (list_length(fkeys) == 0)
-		return joinquals;
+	int outerrelid;
+	int innerrelid;
 
-	foreach (lc, joinquals)
+	/*
+	 * Since foreign keys can only references a single relation, and each
+	 * foreign key belongs to at most a single relation, we require that only
+	 * a single relation be at either side of the join condition. We'll fall
+	 * back on clauselist_selectivity() if this is not the case.
+	 */
+	if (bms_get_singleton_member(sjinfo->min_righthand, &innerrelid) &&
+		bms_get_singleton_member(sjinfo->min_lefthand, &outerrelid))
 	{
-		Oid				opno;
-		Index			relida, relidb;
-		AttrNumber		attnoa, attnob;
-		Oid				oida, oidb;
-
-		/* was the clause matched by at least one key? */
-		bool			matched = false;
-
-		RestrictInfo   *rinfo = (RestrictInfo*)lfirst(lc);
+		Bitmapset *outer2inner, *inner2outer;
+		RelOptInfo *innerrel = find_base_rel(root, innerrelid);
+		RelOptInfo *outerrel = find_base_rel(root, outerrelid);
 
-		/* if the clause is not compatible with foreign keys, just add it */
-		if (! clause_is_fk_compatible(rinfo, &relida, &attnoa,
-											 &relidb, &attnob, &opno))
-		{
-			clauses = lappend(clauses, rinfo);
-			continue;
-		}
+		/* check which quals are matched by a foreign key referencing the innerrel */
+		outer2inner = find_best_match_foreign_key(root, outerrel, innerrel, joinquals);
 
-		oida = root->simple_rte_array[relida]->relid;
-		oidb = root->simple_rte_array[relidb]->relid;
+		/* do the same again, but with relations swapped */
+		inner2outer = find_best_match_foreign_key(root, innerrel, outerrel, joinquals);
 
 		/*
-		 * Walk through the matched foreign keys, and try to match the clause
-		 * against each one. We don't know in what order are the Vars listed
-		 * in the clause, so try both ways.
+		 * did we find any matches at all? If so we need to see which one is
+		 * the best/longest match
 		 */
-		foreach (lc2, fkeys)
+		if (outer2inner || inner2outer)
 		{
-			int i;
-			ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo*)lfirst(lc2);
+			Selectivity sel;
+			ListCell *lc;
+			int lstidx;
+			List *nonfkeyclauses;
 
-			/* now check the keys - we can stop after finding the first match */
-			for (i = 0; i < fkinfo->nkeys; i++)
+			/* either could be NULL, but bms_num_members will handle that */
+			if (bms_num_members(outer2inner) < bms_num_members(inner2outer))
 			{
-				/* check the operator first */
-				if (fkinfo->conpfeqop[i] != opno)
-					continue;
+				/*
+				 * We can now disgard the lesser of the two and save the best
+				 * match into one of the bitmaps. Let's just use outer2inner
+				 */
+				bms_free(outer2inner);
+				outer2inner = inner2outer;
 
-				/* now check the attnums */
-				if ((fkinfo->conrelid == oida) && (fkinfo->confrelid == oidb))
-				{
-					if ((fkinfo->confkeys[i] == attnob) &&
-						(fkinfo->conkeys[i] == attnoa))
-					{
-						matched = true;
-						break;
-					}
-				}
-				else if ((fkinfo->conrelid == oidb) && (fkinfo->confrelid == oida))
-				{
-					if ((fkinfo->confkeys[i] == attnoa) &&
-						(fkinfo->conkeys[i] == attnob))
-					{
-						matched = true;
-						break;
-					}
-				}
+				if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+					sel = 1.0;
+				else
+					sel = 1.0 / Max(outerrel->tuples, 1.0);
 			}
+			else
+			{
+				bms_free(inner2outer);
 
-			/* no need to try more keys, single match is enough */
-			if (matched)
-				break;
-		}
-
-		/* if a clause was not matched by any foreign key, continue */
-		if (! matched)
-			clauses = lappend(clauses, rinfo);
-
-	}
-
-	return clauses;
-}
-
-
-
-/*
- * Estimate selectivity of join clauses - either by using foreign key info or
- * by using the regular clauselist_selectivity().
- *
- * If there are multiple join clauses, we check whether the clauses match
- * a foreign key between the tables - in that case we can use this information
- * to derive a better estimate (otherwise we'd multiply the selectivities for
- * each clause, which often causes significant underestimates).
- *
- * We only need to care about multi-clause join conditions and simply defer
- * simple clauses to clauselist_selectivity().
- *
- * Let's see a few examples of foreign-key joins, illustrating the estimation
- * ideas here.
- *
- * CREATE TABLE a (
- *     a1 INT,
- *     a2 INT,
- *     a3 INT,
- *     a4 INT,
- *     PRIMARY KEY (a1, a2, a3)
- * );
- *
- * CREATE TABLE b (
- *     b1 INT,
- *     b2 INT,
- *     b3 INT,
- *     b4 INT,
- *     FOREIGN KEY (b1, b2, b3) REFERENCES (a1, a2, a3)
- * );
- *
- * clauses exactly match a foreign key
- * -----------------------------------
- *
- *   SELECT * FROM a JOIN b ON (a1=b1 AND a2=b2 AND a3=b3);
- *
- * - trivial, just use 1/card(a)
- *
- * clauses match a foreign key, with additional conditions exist
- * -------------------------------------------------------------
- *
- *   SELECT * FROM a JOIN b ON (a1=b1 AND a2=b2 AND a3=b3 AND a4=b4);
- *
- * - trivial, just use 1/card(a) * selectivity(remaining_clauses)
- *
- * incomplete foreign key match
- * ----------------------------
- *
- *   SELECT * FROM a JOIN b ON (a1=b1 AND a2=b2);
- *
- * - not sure, we'd need to compensate for the "missing part" somehow (we know
- *   the row exists, but we don't know much many rows - it's likely more than
- *   unique)
- *
- * - one way would be to assume each clause is responsible for (1/card(a))^(1/n)
- *   where 'n' is number of clauses - this way 'multiplying the FK clauses' would
- *   gets us the 1/card(a) selectivity if we had all the clauses
- *
- * - another thing is we might use 1/card(a) as a lower boundary - we can't
- *   possibly get lower selectivity, we know the rows exist (also this is not
- *   based on assumptions like the previous idea)
- *
- * multiple distinct foreign keys matching
- * ---------------------------------------
- *
- * CREATE TABLE a (
- *     a1 INT,
- *     a2 INT,
- *     a3 INT,
- *     a4 INT,
- *     PRIMARY KEY (a1, a2),
- *     UNIQUE (a3, a4)
- * );
- *
- * CREATE TABLE b (
- *     b1 INT,
- *     b2 INT,
- *     b3 INT,
- *     b4 INT,
- *     FOREIGN KEY (b1, b2) REFERENCES (a1, a2),
- *     FOREIGN KEY (b3, b4) REFERENCES (a3, a4)
- * );
- *
- * - simply just use 1/card(a) for each foreign key (assumes independence of the
- *   foreign keys, but well - we're assuming attribute independence so this is
- *   an improvement)
- *
- * multiple overlapping foreign keys matching
- * ------------------------------------------
- *
- * CREATE TABLE a (
- *     a1 INT,
- *     a2 INT,
- *     a3 INT,
- *     PRIMARY KEY (a1, a2),
- *     UNIQUE (a2, a3)
- * );
- *
- * CREATE TABLE b (
- *     b1 INT,
- *     b2 INT,
- *     b3 INT,
- *     b4 INT,
- *     FOREIGN KEY (b1, b2) REFERENCES (a1, a2),
- *     FOREIGN KEY (b3, b4) REFERENCES (a2, a3)
- * );
- *
- * - probably just use 1/card(a) for each foreign key, as in the previous
- *   example (assumes independence of the foreign keys, but well - we're
- *   assuming attribute independence so this is an improvement)
- *
- * There are strange cases with multiple foreign keys, where one FK implies
- * the other FK. For example consider this:
- *
- * CREATE TABLE a (
- *     a1 INT,
- *     a2 INT,
- *     a3 INT,
- *     UNIQUE (a1, a2, a3),
- *     UNIQUE (a1, a2)
- * );
- *
- * CREATE TABLE b (
- *     b1 INT,
- *     b2 INT,
- *     b3 INT,
- *     FOREIGN KEY (b1, b2, b3) REFERENCES a (a1, a2, a3),
- *     FOREIGN KEY (b1, b2) REFERENCES a (a1, a2)
- * );
- *
- * Clearly the (b1,b2) is implied by (b1,b2,b3) - if the latter exists, then
- * the former exists too. Not sure how to handle this (or if it's actually
- * needed).
- *
- * Another slightly strange case is FK constraints in both directions (these
- * statements don't work - the foreign keys need to be established using
- * ALTER, but for illustration it's sufficient).
- *
- * CREATE TABLE a (
- *     a1 INT,
- *     a2 INT,
- *     UNIQUE (a1, a2),
- *     FOREIGN KEY (a1, a2) REFERENCES a (b1, b2)
- * );
- *
- * CREATE TABLE b (
- *     b1 INT,
- *     b2 INT,
- *     UNIQUE (b1, b2),
- *     FOREIGN KEY (b1, b2) REFERENCES a (a1, a2)
- * );
- *
- * which effectively establishes 1:1 relationship, or with distinct groups of
- * columns for each direction
- *
- * CREATE TABLE a (
- *     a1 INT,
- *     a2 INT,
- *     a3 INT,
- *     a4 INT,
- *     UNIQUE (a1, a2),
- *     FOREIGN KEY (a3, a4) REFERENCES a (b1, b2)
- * );
- *
- * CREATE TABLE b (
- *     b1 INT,
- *     b2 INT,
- *     b3 INT,
- *     b4 INT,
- *     UNIQUE (b1, b2),
- *     FOREIGN KEY (b3, b4) REFERENCES a (a1, a2)
- * );
- *
- * which creates a cycle of foreign keys.
- *
- * In the first case the foreign keys should be counted only once into the
- * selectivity, because it's effectively a 1:1 relationship - each row has
- * to have one matching row in the other table (not matched by other) rows.
- *
- * In the other case, it's probably right to factor in both foreign keys.
- */
-static Selectivity
-clauselist_join_selectivity(PlannerInfo *root, List *joinquals, int varno,
-							JoinType jointype, SpecialJoinInfo *sjinfo)
-{
-	Selectivity sel = 1.0;
-
-	List	   *fkeys;		/* list of satisfied foreign keys */
-	List	   *unmatched;	/* clauses remaining after removing FK clauses */
-
-	Assert(list_length(joinquals) >= 0);
-
-	/*
-	 * If we only have a single clause, we don't need to mess with the foreign
-	 * keys - that's only useful with multi-column clauses anyway. Just use the
-	 * simple clauselist_selectivity.
-	 */
-	if (list_length(joinquals) <= 1)
-		return clauselist_selectivity(root,
-									  joinquals,
-									  0,
-									  jointype,
-									  sjinfo);
-
-	/*
-	 * First we'll identify foreign keys that are fully matched by the join
-	 * clauses, and we'll update the selectivity accordingly while doing so.
-	 */
-	fkeys = find_satisfied_fkeys(root, sjinfo, joinquals, &sel);
-
-	/*
-	 * Now that we have the foreign keys, we can get rid of the clauses
-	 * matching any of them, and only keep the remaining clauses, so that
-	 * we can estimate them using the regular selectivity estimation.
-	 */
-	unmatched = filter_fk_join_clauses(root, sjinfo, fkeys, joinquals);
+				if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+					sel = 1.0;
+				else
+					sel = 1.0 / Max(innerrel->tuples, 1.0);
+			}
 
-	/*
-	 * Estimate the remaining clauses (not matching any FK), if still have any.
-	 */
-	if (list_length(unmatched) > 0)
-	{
-		sel *= clauselist_selectivity(root,
-									  unmatched,
-									  0,
-									  jointype,
-									  sjinfo);
-
-		/* Only free the list if we actually found any foreign keys. */
-		if (list_length(fkeys) > 0)
-			list_free(unmatched);
+			/*
+			 * build a list of all non-fkey joinquals, we'll need to enlist
+			 * clauselist_selectivity() to estimate these
+			 */
+			lstidx = 0;
+			nonfkeyclauses = NIL;
+			foreach (lc, joinquals)
+			{
+				if (!bms_is_member(lstidx, outer2inner))
+					nonfkeyclauses = lappend(nonfkeyclauses, lfirst(lc));
+				lstidx++;
+			}
+			return sel * clauselist_selectivity(root, nonfkeyclauses, 0, jointype, sjinfo);
+		}
 	}
 
-	return sel;
+	/* perform normal estimation without the help of foreign keys */
+	return clauselist_selectivity(root, joinquals, 0, jointype, sjinfo);
 }
 
 /*
@@ -4387,7 +4024,6 @@ calc_joinrel_size_estimate(PlannerInfo *root,
 		/* Get the separate selectivities */
 		jselec = clauselist_join_selectivity(root,
 											 joinquals,
-											 0,
 											 jointype,
 											 sjinfo);
 
@@ -4405,7 +4041,6 @@ calc_joinrel_size_estimate(PlannerInfo *root,
 	{
 		jselec = clauselist_join_selectivity(root,
 											 restrictlist,
-											 0,
 											 jointype,
 											 sjinfo);
 		pselec = 0.0;			/* not used, keep compiler quiet */
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 05c8698..7912b15 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -562,6 +562,7 @@ remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
 	return result;
 }
 
+
 /*
  * query_supports_distinctness - could the query possibly be proven distinct
  *		on some set of output columns?
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index fbc5579..dbe6038 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -96,6 +96,8 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	bool		hasindex;
 	List	   *indexinfos = NIL;
 	List	   *fkinfos = NIL;
+	List	   *fkoidlist;
+	ListCell   *l;
 
 	/*
 	 * We need not lock the relation since it was already locked, either by
@@ -143,7 +145,6 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	if (hasindex)
 	{
 		List	   *indexoidlist;
-		ListCell   *l;
 		LOCKMODE	lmode;
 
 		indexoidlist = RelationGetIndexList(relation);
@@ -384,86 +385,75 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 
 	rel->indexlist = indexinfos;
  
-	/*
-	 * TODO Can we do something like (hasindex) here? Is it necessary? The
-	 *      trouble with that is that we don't have a good place to reset that
-	 *      flag (relhasindex is reset by vacuum, but is has nothing to do with
-	 *      foreign keys at this point).
-	 */
-	if (true)
-	{
-		List	   *fkoidlist;
-		ListCell   *l;
-
-		fkoidlist = RelationGetFKeyList(relation);
-
-		foreach(l, fkoidlist)
-		{
-			int			i;
-			ArrayType  *arr;
-			Datum		adatum;
-			bool		isnull;
-			int			numkeys;
-			Oid			fkoid = lfirst_oid(l);
+	/* load foreign keys */
+	fkoidlist = RelationGetFKeyList(relation);
 
-			HeapTuple	htup = SearchSysCache1(CONSTROID, ObjectIdGetDatum(fkoid));
-			Form_pg_constraint constraint = (Form_pg_constraint) GETSTRUCT(htup);
+	foreach(l, fkoidlist)
+	{
+		int			i;
+		ArrayType  *arr;
+		Datum		adatum;
+		bool		isnull;
+		int			numkeys;
+		Oid			fkoid = lfirst_oid(l);
 
-			ForeignKeyOptInfo *info;
+		HeapTuple	htup = SearchSysCache1(CONSTROID, ObjectIdGetDatum(fkoid));
+		Form_pg_constraint constraint = (Form_pg_constraint) GETSTRUCT(htup);
 
-			Assert(constraint->contype == CONSTRAINT_FOREIGN);
+		ForeignKeyOptInfo *info;
 
-			info = makeNode(ForeignKeyOptInfo);
+		Assert(constraint->contype == CONSTRAINT_FOREIGN);
 
-			info->conrelid = constraint->conrelid;
-			info->confrelid = constraint->confrelid;
+		info = makeNode(ForeignKeyOptInfo);
 
-			/* conkey */
-			adatum = SysCacheGetAttr(CONSTROID, htup,
-									 Anum_pg_constraint_conkey, &isnull);
-			Assert(!isnull);
+		info->conrelid = constraint->conrelid;
+		info->confrelid = constraint->confrelid;
 
-			arr = DatumGetArrayTypeP(adatum);
-			numkeys = ARR_DIMS(arr)[0];
-			info->conkeys = (int*)palloc0(numkeys * sizeof(int));
+		/* conkey */
+		adatum = SysCacheGetAttr(CONSTROID, htup,
+									Anum_pg_constraint_conkey, &isnull);
+		Assert(!isnull);
 
-			for (i = 0; i < numkeys; i++)
-				info->conkeys[i] = ((int16 *) ARR_DATA_PTR(arr))[i];
+		arr = DatumGetArrayTypeP(adatum);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conkeys = (int*)palloc0(numkeys * sizeof(int));
 
-			/* confkey */
-			adatum = SysCacheGetAttr(CONSTROID, htup,
-									 Anum_pg_constraint_confkey, &isnull);
-			Assert(!isnull);
+		for (i = 0; i < numkeys; i++)
+			info->conkeys[i] = ((int16 *) ARR_DATA_PTR(arr))[i];
 
-			arr = DatumGetArrayTypeP(adatum);
-			numkeys = ARR_DIMS(arr)[0];
-			info->confkeys = (int*)palloc0(numkeys * sizeof(int));
+		/* confkey */
+		adatum = SysCacheGetAttr(CONSTROID, htup,
+									Anum_pg_constraint_confkey, &isnull);
+		Assert(!isnull);
 
-			for (i = 0; i < numkeys; i++)
-				info->confkeys[i] = ((int16 *) ARR_DATA_PTR(arr))[i];
+		arr = DatumGetArrayTypeP(adatum);
+		numkeys = ARR_DIMS(arr)[0];
+		info->confkeys = (int*)palloc0(numkeys * sizeof(int));
 
-			/* conpfeqop */
-			adatum = SysCacheGetAttr(CONSTROID, htup,
-									 Anum_pg_constraint_conpfeqop, &isnull);
-			Assert(!isnull);
+		for (i = 0; i < numkeys; i++)
+			info->confkeys[i] = ((int16 *) ARR_DATA_PTR(arr))[i];
 
-			arr = DatumGetArrayTypeP(adatum);
-			numkeys = ARR_DIMS(arr)[0];
-			info->conpfeqop = (Oid*)palloc0(numkeys * sizeof(Oid));
+		/* conpfeqop */
+		adatum = SysCacheGetAttr(CONSTROID, htup,
+									Anum_pg_constraint_conpfeqop, &isnull);
+		Assert(!isnull);
 
-			for (i = 0; i < numkeys; i++)
-				info->conpfeqop[i] = ((Oid *) ARR_DATA_PTR(arr))[i];
+		arr = DatumGetArrayTypeP(adatum);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conpfeqop = (Oid*)palloc0(numkeys * sizeof(Oid));
 
-			info->nkeys = numkeys;
+		for (i = 0; i < numkeys; i++)
+			info->conpfeqop[i] = ((Oid *) ARR_DATA_PTR(arr))[i];
 
-			ReleaseSysCache(htup);
+		info->nkeys = numkeys;
 
-			fkinfos = lcons(info, fkinfos);
-		}
+		ReleaseSysCache(htup);
 
-		list_free(fkoidlist);
+		fkinfos = lcons(info, fkinfos);
 	}
 
+	list_free(fkoidlist);
+
 	rel->fkeylist = fkinfos;
 
 	/* Grab foreign-table info using the relcache, while we have it */

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index e1b49d5..8dbfeba 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1907,6 +1907,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)
 {
 	/*
@@ -3297,6 +3307,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 d107d76..d9083b2 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3732,6 +3732,253 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
 }
 
 /*
+ * find_best_match_foreign_key
+ *		Returns a Bitmapset with bits set for each 0 based index of 'joinquals'
+ *		which to a foreign key which is defined on fkrel.
+ *
+ * Note: in the event that there's more than 1 foreign key between these two
+ * relations, the largest match, i.e. the bitmask which was generated from the
+ * foreign key with the highest number of keys is returned.
+ */
+static Bitmapset *
+find_best_match_foreign_key(PlannerInfo *root, RelOptInfo *fkrel,
+							RelOptInfo *foreignrel, List *joinquals)
+{
+	Bitmapset	   *qualbestmatch;
+	Bitmapset	   *usefulquals;
+	ListCell	   *lc;
+	int				quallstidx;
+	int				bestmatchnkeys;
+	Oid				frelid;
+
+	/* fast path out when there's no foreign keys on fkrel */
+	if (fkrel->fkeylist == NIL)
+		return NULL;
+
+	qualbestmatch = NULL;
+	quallstidx = -1;
+	usefulquals = NULL;
+	bestmatchnkeys = 0;
+
+	/*
+	 * First build a bitmapset with all possibly useful quals. This will save
+	 * from having to do this for each foreign key later. The only quals that
+	 * are useful to us are in the form "var op var", so here we'll ignore
+	 * things like "function(var1, var2)".
+	 */
+	foreach(lc, joinquals)
+	{
+		RestrictInfo   *rinfo = (RestrictInfo *) lfirst(lc);
+		OpExpr		   *clause;
+		Var			   *leftvar, *rightvar;
+
+		/*
+		 * Increment this at the start of the loop to save doing it before each
+		 * continue statement.
+		 */
+		quallstidx++;
+
+		if (!IsA(rinfo, RestrictInfo))
+			continue;
+
+		if (!IsA(rinfo->clause, OpExpr))
+			continue;
+
+		clause = (OpExpr *) rinfo->clause;
+
+		if (list_length(clause->args) != 2)
+			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;
+
+		usefulquals = bms_add_member(usefulquals, quallstidx);
+	}
+
+	frelid = root->simple_rte_array[foreignrel->relid]->relid;
+
+	/* now check the matches for each foreign key defined on the fkrel */
+	foreach(lc, fkrel->fkeylist)
+	{
+		ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+		Bitmapset *qualmatches;
+		Bitmapset *fkmatches;
+		int i;
+		int nkeys;
+
+		/* skip any foreign keys which don't reference frelid */
+		if (fkinfo->confrelid != frelid)
+			continue;
+
+		qualmatches = NULL;
+		fkmatches = NULL;
+		nkeys = fkinfo->nkeys;
+
+		/*
+		 * Loop over each column of the foreign key and build a bitmap index
+		 * of each joinqual which matches. Note that we don't stop when we find
+		 * the first match, as the expression could be duplicated in the
+		 * joinquals, and we want to match as many as possible.
+		 */
+		for (i = 0; i < nkeys; i++)
+		{
+			ListCell *lc2;
+
+			quallstidx = -1;
+			foreach(lc2, joinquals)
+			{
+				RestrictInfo   *rinfo;
+				OpExpr		   *clause;
+				Var			   *leftvar;
+				Var			   *rightvar;
+
+				quallstidx++;
+
+				/* skip anything we didn't mark as useful above. */
+				if (!bms_is_member(quallstidx, usefulquals))
+					continue;
+
+				/*
+				 * Here we can safely assume that we have an OpExpr, in  the
+				 * from of "var op var"
+				 */
+				rinfo = (RestrictInfo *) lfirst(lc2);
+				clause = (OpExpr *) rinfo->clause;
+
+				/* skip if the operator does not match */
+				if (clause->opno != fkinfo->conpfeqop[i])
+					continue;
+
+				leftvar = (Var *) get_leftop((Expr *) clause);
+				rightvar = (Var *) get_rightop((Expr *) clause);
+
+				/*
+				 * Check if the OpExpr matches the foreign key. Remember that
+				 * this could be written with the Vars in either order, so we
+				 * test both permutations of the expression.
+				 */
+				if ((fkinfo->confkeys[i] == leftvar->varattno &&
+					fkinfo->conkeys[i] == rightvar->varattno) ||
+					(fkinfo->confkeys[i] == rightvar->varattno &&
+					fkinfo->conkeys[i] == leftvar->varattno))
+				{
+					qualmatches = bms_add_member(qualmatches, quallstidx);
+					fkmatches = bms_add_member(fkmatches, i);
+				}
+			}
+		}
+
+		/* did we get a complete match to the foreign key? */
+		if (bms_num_members(fkmatches) == nkeys)
+		{
+			/* does this match match more keys than any previous match? */
+			if (nkeys > bestmatchnkeys)
+			{
+				bms_free(qualbestmatch);
+				qualbestmatch = qualmatches;
+				bestmatchnkeys = nkeys;
+			}
+		}
+
+		bms_free(fkmatches);
+	}
+
+	return qualbestmatch;
+}
+
+/*
+ * 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().
+ */
+static Selectivity
+clauselist_join_selectivity(PlannerInfo *root, List *joinquals,
+							JoinType jointype, SpecialJoinInfo *sjinfo)
+{
+	int outerrelid;
+	int innerrelid;
+
+	if (bms_get_singleton_member(sjinfo->min_righthand, &innerrelid) &&
+		bms_get_singleton_member(sjinfo->min_lefthand, &outerrelid))
+	{
+		Bitmapset *outer2inner, *inner2outer;
+		RelOptInfo *innerrel = find_base_rel(root, innerrelid);
+		RelOptInfo *outerrel = find_base_rel(root, outerrelid);
+
+		/* check which quals are matched by a foreign key referencing the innerrel */
+		outer2inner = find_best_match_foreign_key(root, outerrel, innerrel, joinquals);
+
+		/* do the same again, but with relations swapped */
+		inner2outer = find_best_match_foreign_key(root, innerrel, outerrel, joinquals);
+
+		/*
+		 * did we find any matches at all? If so we need to see which one is
+		 * the best/longest match
+		 */
+		if (outer2inner || inner2outer)
+		{
+			Selectivity sel;
+			ListCell *lc;
+			int lstidx;
+			List *nonfkeyclauses;
+
+			/* either could be NULL, but bms_num_members will handle that */
+			if (bms_num_members(outer2inner) < bms_num_members(inner2outer))
+			{
+				/*
+				 * We can now disgard the lesser of the two and save the best
+				 * match into one of the bitmaps. Let's just use outer2inner
+				 */
+				bms_free(outer2inner);
+				outer2inner = inner2outer;
+
+				if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+					sel = 1.0;
+				else
+					sel = 1.0 / Max(outerrel->tuples, 1.0);
+			}
+			else
+			{
+				bms_free(inner2outer);
+
+				if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+					sel = 1.0;
+				else
+					sel = 1.0 / Max(innerrel->tuples, 1.0);
+			}
+
+			/*
+			 * build a list of all non-fkey joinquals, we'll need to enlist
+			 * clauselist_selectivity() to estimate these
+			 */
+			lstidx = 0;
+			nonfkeyclauses = NIL;
+			foreach (lc, joinquals)
+			{
+				if (!bms_is_member(lstidx, outer2inner))
+					nonfkeyclauses = lappend(nonfkeyclauses, lfirst(lc));
+				lstidx++;
+			}
+			return sel * clauselist_selectivity(root, nonfkeyclauses, 0, jointype, sjinfo);
+		}
+	}
+
+	/* perform normal estimation without the help of foreign keys */
+	return clauselist_selectivity(root, joinquals, 0, jointype, sjinfo);
+}
+
+/*
  * calc_joinrel_size_estimate
  *		Workhorse for set_joinrel_size_estimates and
  *		get_parameterized_joinrel_size.
@@ -3777,11 +4024,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,
@@ -3794,11 +4041,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/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 9442e5f..dbe6038 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -27,6 +27,7 @@
 #include "catalog/catalog.h"
 #include "catalog/dependency.h"
 #include "catalog/heap.h"
+#include "catalog/pg_constraint.h"
 #include "foreign/fdwapi.h"
 #include "miscadmin.h"
 #include "nodes/makefuncs.h"
@@ -40,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"
 
@@ -93,6 +95,9 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	Relation	relation;
 	bool		hasindex;
 	List	   *indexinfos = NIL;
+	List	   *fkinfos = NIL;
+	List	   *fkoidlist;
+	ListCell   *l;
 
 	/*
 	 * We need not lock the relation since it was already locked, either by
@@ -140,7 +145,6 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	if (hasindex)
 	{
 		List	   *indexoidlist;
-		ListCell   *l;
 		LOCKMODE	lmode;
 
 		indexoidlist = RelationGetIndexList(relation);
@@ -380,6 +384,77 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	}
 
 	rel->indexlist = indexinfos;
+ 
+	/* load foreign keys */
+	fkoidlist = RelationGetFKeyList(relation);
+
+	foreach(l, fkoidlist)
+	{
+		int			i;
+		ArrayType  *arr;
+		Datum		adatum;
+		bool		isnull;
+		int			numkeys;
+		Oid			fkoid = lfirst_oid(l);
+
+		HeapTuple	htup = SearchSysCache1(CONSTROID, ObjectIdGetDatum(fkoid));
+		Form_pg_constraint constraint = (Form_pg_constraint) GETSTRUCT(htup);
+
+		ForeignKeyOptInfo *info;
+
+		Assert(constraint->contype == CONSTRAINT_FOREIGN);
+
+		info = makeNode(ForeignKeyOptInfo);
+
+		info->conrelid = constraint->conrelid;
+		info->confrelid = constraint->confrelid;
+
+		/* conkey */
+		adatum = SysCacheGetAttr(CONSTROID, htup,
+									Anum_pg_constraint_conkey, &isnull);
+		Assert(!isnull);
+
+		arr = DatumGetArrayTypeP(adatum);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conkeys = (int*)palloc0(numkeys * sizeof(int));
+
+		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);
+		numkeys = ARR_DIMS(arr)[0];
+		info->confkeys = (int*)palloc0(numkeys * sizeof(int));
+
+		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);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conpfeqop = (Oid*)palloc0(numkeys * sizeof(Oid));
+
+		for (i = 0; i < numkeys; i++)
+			info->conpfeqop[i] = ((Oid *) ARR_DATA_PTR(arr))[i];
+
+		info->nkeys = numkeys;
+
+		ReleaseSysCache(htup);
+
+		fkinfos = lcons(info, fkinfos);
+	}
+
+	list_free(fkoidlist);
+
+	rel->fkeylist = fkinfos;
 
 	/* Grab foreign-table info using the relcache, while we have it */
 	if (relation->rd_rel->relkind == RELKIND_FOREIGN_TABLE)
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index 9c3d096..3ae9022 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -3923,6 +3923,73 @@ RelationGetIndexList(Relation relation)
 }
 
 /*
+ * RelationGetFKeyList -- get a list of foreign key oids
+ *
+ * TODO blah blah blah
+ */
+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_fkeyvalid)
+		return list_copy(relation->rd_fkeylist);
+
+	/*
+	 * 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);
+
+		/* return only foreign keys */
+		if (constraint->contype != CONSTRAINT_FOREIGN)
+			continue;
+
+		/* Add index's OID to result list in the proper order */
+		result = insert_ordered_oid(result, HeapTupleGetOid(htup));
+	}
+
+	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);
+	relation->rd_fkeyvalid = true;
+	MemoryContextSwitchTo(oldcxt);
+
+	/* Don't leak the old list, if there is one */
+	list_free(oldlist);
+
+	return result;
+}
+
+/*
  * insert_ordered_oid
  *		Insert a new Oid into a sorted list of Oids, preserving ordering
  *
@@ -4891,6 +4958,8 @@ load_relcache_init_file(bool shared)
 		rel->rd_indexattr = NULL;
 		rel->rd_keyattr = NULL;
 		rel->rd_idattr = NULL;
+		rel->rd_fkeylist = NIL;
+		rel->rd_fkeyvalid = false;
 		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 274480e..5c40b83 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -221,6 +221,7 @@ typedef enum NodeTag
 	T_PlannerGlobal,
 	T_RelOptInfo,
 	T_IndexOptInfo,
+	T_ForeignKeyOptInfo,
 	T_ParamPathInfo,
 	T_Path,
 	T_IndexPath,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 79bed33..8ce35e7 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -472,6 +472,7 @@ typedef struct RelOptInfo
 	Relids		lateral_relids; /* minimum parameterization of 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;
@@ -566,6 +567,20 @@ typedef struct IndexOptInfo
 	bool		amhasgetbitmap; /* does AM have amgetbitmap interface? */
 } IndexOptInfo;
 
+/* TODO add info*/
+typedef struct ForeignKeyOptInfo
+{
+	NodeTag		type;
+
+	Oid			conrelid;
+	Oid			confrelid;
+
+	int			nkeys;
+	int		   *conkeys;
+	int		   *confkeys;
+	Oid		   *conpfeqop;
+
+} ForeignKeyOptInfo;
 
 /*
  * EquivalenceClasses
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 87123a5..da1fd58 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -73,6 +73,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 8a55a09..c56cf8a 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -79,6 +79,7 @@ typedef struct RelationData
 	bool		rd_isvalid;		/* relcache entry is valid */
 	char		rd_indexvalid;	/* state of rd_indexlist: 0 = not valid, 1 =
 								 * valid, 2 = temporarily forced */
+	bool		rd_fkeyvalid;	/* state of rd_fkeylist: 0 = not valid, 1 = valid */
 
 	/*
 	 * rd_createSubid is the ID of the highest subtransaction the rel has
@@ -112,6 +113,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;		/* OIDs of foreign keys */
+
 	/* 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 6953281..8878478 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/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index e1b49d5..8dbfeba 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1907,6 +1907,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)
 {
 	/*
@@ -3297,6 +3307,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 d107d76..0a57bc9 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3732,6 +3732,322 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
 }
 
 /*
+ * find_best_foreign_key_quals
+ *		Analyzes joinquals to determine if any quals match foreign keys defined
+ *		on 'fkrel' which reference 'foreignrel'. We return the number of keys
+ *		of the best matching foreign key. We assume the best matching foreign
+ *		key is the one with the most keys, not the most quals matching quals,
+ *		as quals could be duplicated. We also set 'joinqualsbitmap' bits to
+ *		mark which quals in 'joinquals' were matched. Zero is returned if no
+ *		match is found. In this case 'joinqualsbitmap' is set to NULL. Partial
+ *		foreign key matches are currently ignored.
+ */
+static int
+find_best_foreign_key_quals(PlannerInfo *root, RelOptInfo *fkrel,
+							RelOptInfo *foreignrel, List *joinquals,
+							Bitmapset **joinqualsbitmap)
+{
+	Bitmapset	   *qualbestmatch;
+	Bitmapset	   *usefulquals;
+	ListCell	   *lc;
+	int				quallstidx;
+	int				bestmatchnkeys;
+	Oid				frelid;
+
+	/* fast path out when there's no foreign keys on fkrel */
+	if (fkrel->fkeylist == NIL)
+	{
+		*joinqualsbitmap = NULL;
+		return 0;
+	}
+
+	qualbestmatch = NULL;
+	quallstidx = -1;
+	usefulquals = NULL;
+	bestmatchnkeys = 0;
+
+	/*
+	 * First build a bitmapset with all possibly useful quals. This will save
+	 * from having to do this for each foreign key later. The only quals that
+	 * are useful to us are in the form "var op var", so here we'll ignore
+	 * things like "function(var1, var2)".
+	 */
+	foreach(lc, joinquals)
+	{
+		RestrictInfo   *rinfo = (RestrictInfo *) lfirst(lc);
+		OpExpr		   *clause;
+		Var			   *leftvar, *rightvar;
+
+		/*
+		 * Increment this at the start of the loop to save doing it before each
+		 * continue statement.
+		 */
+		quallstidx++;
+
+		if (!IsA(rinfo, RestrictInfo))
+			continue;
+
+		if (!IsA(rinfo->clause, OpExpr))
+			continue;
+
+		clause = (OpExpr *) rinfo->clause;
+
+		if (list_length(clause->args) != 2)
+			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;
+
+		usefulquals = bms_add_member(usefulquals, quallstidx);
+	}
+
+	frelid = root->simple_rte_array[foreignrel->relid]->relid;
+
+	/* now check the matches for each foreign key defined on the fkrel */
+	foreach(lc, fkrel->fkeylist)
+	{
+		ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+		Bitmapset *qualmatches;
+		Bitmapset *fkmatches;
+		int i;
+		int nkeys;
+
+		/* skip any foreign keys which don't reference frelid */
+		if (fkinfo->confrelid != frelid)
+			continue;
+
+		qualmatches = NULL;
+		fkmatches = NULL;
+		nkeys = fkinfo->nkeys;
+
+		/*
+		 * Loop over each column of the foreign key and build a bitmap index
+		 * of each joinqual which matches. Note that we don't stop when we find
+		 * the first match, as the expression could be duplicated in the
+		 * joinquals, and we want to match as many as possible.
+		 */
+		for (i = 0; i < nkeys; i++)
+		{
+			ListCell *lc2;
+
+			quallstidx = -1;
+			foreach(lc2, joinquals)
+			{
+				RestrictInfo   *rinfo;
+				OpExpr		   *clause;
+
+				quallstidx++;
+
+				/* skip anything we didn't mark as useful above. */
+				if (!bms_is_member(quallstidx, usefulquals))
+					continue;
+
+				/*
+				 * Here we can safely assume that we have an OpExpr, in  the
+				 * from of "var op var"
+				 */
+				rinfo = (RestrictInfo *) lfirst(lc2);
+				clause = (OpExpr *) rinfo->clause;
+
+				/*
+				 * if the operator does not match then there's little point in
+				 * checking the operands
+				 */
+				if (clause->opno != fkinfo->conpfeqop[i])
+					continue;
+
+				/*
+				 * For RestrictInfos built from an eclass we must consider
+				 * each member of the eclass, as rinfo may not be using the
+				 * foreign key Vars. For efficient tracking of which Vars we've
+				 * found, since we're only tracking 2 Vars, we use a bitmask.
+				 * We can safely finish searching when both of the least
+				 * significant bits are set.
+				 */
+				if (rinfo->parent_ec)
+				{
+					EquivalenceClass   *ec = rinfo->parent_ec;
+					ListCell		   *lc3;
+					int					foundvarmask = 0;
+
+					foreach(lc3, ec->ec_members)
+					{
+						EquivalenceMember *em = (EquivalenceMember *) lfirst(lc3);
+						Var *var = (Var *) em->em_expr;
+
+						if (!IsA(var, Var))
+							continue;
+
+						if (foreignrel->relid == var->varno &&
+							fkinfo->confkeys[i] == var->varattno)
+							foundvarmask |= 1;
+
+						else if (fkrel->relid == var->varno &&
+							fkinfo->conkeys[i] == var->varattno)
+							foundvarmask |= 2;
+
+						/*
+						 * Check if we've found both matches. If found we add
+						 * this qual to the matched list and mark this key as
+						 * matched too.
+						 */
+						if (foundvarmask == 3)
+						{
+							qualmatches = bms_add_member(qualmatches, quallstidx);
+							fkmatches = bms_add_member(fkmatches, i);
+							break;
+						}
+					}
+				}
+				else
+				{
+					Var *leftvar = (Var *) get_leftop((Expr *) clause);
+					Var *rightvar = (Var *) get_rightop((Expr *) clause);
+
+					/*
+					 * In this non eclass RestrictInfo case we'll check if the
+					 * left and right Vars match to this part of the foreign
+					 * key. Remember that this could be written with the Vars
+					 * in either order, so we test both permutations of the
+					 * expression.
+					 */
+					if (foreignrel->relid == leftvar->varno &&
+						fkrel->relid == rightvar->varno &&
+						fkinfo->confkeys[i] == leftvar->varattno &&
+						fkinfo->conkeys[i] == rightvar->varattno)
+					{
+						qualmatches = bms_add_member(qualmatches, quallstidx);
+						fkmatches = bms_add_member(fkmatches, i);
+					}
+					else if (foreignrel->relid == rightvar->varno &&
+						fkrel->relid == leftvar->varno &&
+						fkinfo->confkeys[i] == rightvar->varattno &&
+						fkinfo->conkeys[i] == leftvar->varattno)
+					{
+						qualmatches = bms_add_member(qualmatches, quallstidx);
+						fkmatches = bms_add_member(fkmatches, i);
+					}
+				}
+			}
+		}
+
+		/* did we get a complete match to the foreign key? */
+		if (bms_num_members(fkmatches) == nkeys)
+		{
+			/* does this match match more keys than any previous match? */
+			if (nkeys > bestmatchnkeys)
+			{
+				bms_free(qualbestmatch);
+				qualbestmatch = qualmatches;
+				bestmatchnkeys = nkeys;
+			}
+		}
+
+		bms_free(fkmatches);
+	}
+
+	*joinqualsbitmap = qualbestmatch;
+	return bestmatchnkeys;
+}
+
+/*
+ * 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().
+ */
+static Selectivity
+clauselist_join_selectivity(PlannerInfo *root, List *joinquals,
+							JoinType jointype, SpecialJoinInfo *sjinfo)
+{
+	int				outerid;
+	int				innerid;
+	Selectivity		sel = 1.0;
+	Bitmapset	   *nonfkquals = NULL;
+
+	innerid = -1;
+	while ((innerid = bms_next_member(sjinfo->min_righthand, innerid)) >= 0)
+	{
+		RelOptInfo *innerrel = find_base_rel(root, innerid);
+
+		outerid = -1;
+		while ((outerid = bms_next_member(sjinfo->min_lefthand, outerid)) >= 0)
+		{
+			RelOptInfo	   *outerrel = find_base_rel(root, outerid);
+			Bitmapset	   *outer2inner;
+			Bitmapset	   *inner2outer;
+			int				innermatches;
+			int				outermatches;
+
+			/*
+			 * check which quals are matched by a foreign key referencing the
+			 * innerrel.
+			 */
+			outermatches = find_best_foreign_key_quals(root, outerrel,
+											innerrel, joinquals, &outer2inner);
+
+			/* do the same, but with relations swapped */
+			innermatches = find_best_foreign_key_quals(root, innerrel,
+											outerrel, joinquals, &inner2outer);
+
+			/*
+			 * did we find any matches at all? If so we need to see which one is
+			 * the best/longest match
+			 */
+			if (outermatches != 0 || innermatches != 0)
+			{
+				/* either could be zero, but not both. */
+				if (outermatches < innermatches)
+				{
+					nonfkquals = bms_add_members(nonfkquals, inner2outer);
+
+					if (jointype != JOIN_SEMI && jointype != JOIN_ANTI)
+						sel *= 1.0 / Max(outerrel->tuples, 1.0);
+				}
+				else
+				{
+					nonfkquals = bms_add_members(nonfkquals, outer2inner);
+
+					if (jointype != JOIN_SEMI && jointype != JOIN_ANTI)
+						sel *= 1.0 / Max(innerrel->tuples, 1.0);
+				}
+			}
+		}
+	}
+
+	/*
+	 * If any non matched quals exist then we build a list of the non-matches
+	 * and use clauselist_selectivity() to estimate the selectivity of these.
+	 */
+	if (bms_num_members(nonfkquals) < list_length(joinquals))
+	{
+		ListCell *lc;
+		int lstidx = 0;
+		List *nonfkeyclauses = NIL;
+
+		foreach (lc, joinquals)
+		{
+			if (!bms_is_member(lstidx, nonfkquals))
+				nonfkeyclauses = lappend(nonfkeyclauses, lfirst(lc));
+			lstidx++;
+		}
+		sel *= clauselist_selectivity(root, nonfkeyclauses, 0, jointype, sjinfo);
+	}
+
+	return sel;
+}
+
+/*
  * calc_joinrel_size_estimate
  *		Workhorse for set_joinrel_size_estimates and
  *		get_parameterized_joinrel_size.
@@ -3777,11 +4093,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,
@@ -3794,11 +4110,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/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 9442e5f..dbe6038 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -27,6 +27,7 @@
 #include "catalog/catalog.h"
 #include "catalog/dependency.h"
 #include "catalog/heap.h"
+#include "catalog/pg_constraint.h"
 #include "foreign/fdwapi.h"
 #include "miscadmin.h"
 #include "nodes/makefuncs.h"
@@ -40,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"
 
@@ -93,6 +95,9 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	Relation	relation;
 	bool		hasindex;
 	List	   *indexinfos = NIL;
+	List	   *fkinfos = NIL;
+	List	   *fkoidlist;
+	ListCell   *l;
 
 	/*
 	 * We need not lock the relation since it was already locked, either by
@@ -140,7 +145,6 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	if (hasindex)
 	{
 		List	   *indexoidlist;
-		ListCell   *l;
 		LOCKMODE	lmode;
 
 		indexoidlist = RelationGetIndexList(relation);
@@ -380,6 +384,77 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	}
 
 	rel->indexlist = indexinfos;
+ 
+	/* load foreign keys */
+	fkoidlist = RelationGetFKeyList(relation);
+
+	foreach(l, fkoidlist)
+	{
+		int			i;
+		ArrayType  *arr;
+		Datum		adatum;
+		bool		isnull;
+		int			numkeys;
+		Oid			fkoid = lfirst_oid(l);
+
+		HeapTuple	htup = SearchSysCache1(CONSTROID, ObjectIdGetDatum(fkoid));
+		Form_pg_constraint constraint = (Form_pg_constraint) GETSTRUCT(htup);
+
+		ForeignKeyOptInfo *info;
+
+		Assert(constraint->contype == CONSTRAINT_FOREIGN);
+
+		info = makeNode(ForeignKeyOptInfo);
+
+		info->conrelid = constraint->conrelid;
+		info->confrelid = constraint->confrelid;
+
+		/* conkey */
+		adatum = SysCacheGetAttr(CONSTROID, htup,
+									Anum_pg_constraint_conkey, &isnull);
+		Assert(!isnull);
+
+		arr = DatumGetArrayTypeP(adatum);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conkeys = (int*)palloc0(numkeys * sizeof(int));
+
+		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);
+		numkeys = ARR_DIMS(arr)[0];
+		info->confkeys = (int*)palloc0(numkeys * sizeof(int));
+
+		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);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conpfeqop = (Oid*)palloc0(numkeys * sizeof(Oid));
+
+		for (i = 0; i < numkeys; i++)
+			info->conpfeqop[i] = ((Oid *) ARR_DATA_PTR(arr))[i];
+
+		info->nkeys = numkeys;
+
+		ReleaseSysCache(htup);
+
+		fkinfos = lcons(info, fkinfos);
+	}
+
+	list_free(fkoidlist);
+
+	rel->fkeylist = fkinfos;
 
 	/* Grab foreign-table info using the relcache, while we have it */
 	if (relation->rd_rel->relkind == RELKIND_FOREIGN_TABLE)
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index 9c3d096..3ae9022 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -3923,6 +3923,73 @@ RelationGetIndexList(Relation relation)
 }
 
 /*
+ * RelationGetFKeyList -- get a list of foreign key oids
+ *
+ * TODO blah blah blah
+ */
+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_fkeyvalid)
+		return list_copy(relation->rd_fkeylist);
+
+	/*
+	 * 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);
+
+		/* return only foreign keys */
+		if (constraint->contype != CONSTRAINT_FOREIGN)
+			continue;
+
+		/* Add index's OID to result list in the proper order */
+		result = insert_ordered_oid(result, HeapTupleGetOid(htup));
+	}
+
+	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);
+	relation->rd_fkeyvalid = true;
+	MemoryContextSwitchTo(oldcxt);
+
+	/* Don't leak the old list, if there is one */
+	list_free(oldlist);
+
+	return result;
+}
+
+/*
  * insert_ordered_oid
  *		Insert a new Oid into a sorted list of Oids, preserving ordering
  *
@@ -4891,6 +4958,8 @@ load_relcache_init_file(bool shared)
 		rel->rd_indexattr = NULL;
 		rel->rd_keyattr = NULL;
 		rel->rd_idattr = NULL;
+		rel->rd_fkeylist = NIL;
+		rel->rd_fkeyvalid = false;
 		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 274480e..5c40b83 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -221,6 +221,7 @@ typedef enum NodeTag
 	T_PlannerGlobal,
 	T_RelOptInfo,
 	T_IndexOptInfo,
+	T_ForeignKeyOptInfo,
 	T_ParamPathInfo,
 	T_Path,
 	T_IndexPath,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 79bed33..8ce35e7 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -472,6 +472,7 @@ typedef struct RelOptInfo
 	Relids		lateral_relids; /* minimum parameterization of 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;
@@ -566,6 +567,20 @@ typedef struct IndexOptInfo
 	bool		amhasgetbitmap; /* does AM have amgetbitmap interface? */
 } IndexOptInfo;
 
+/* TODO add info*/
+typedef struct ForeignKeyOptInfo
+{
+	NodeTag		type;
+
+	Oid			conrelid;
+	Oid			confrelid;
+
+	int			nkeys;
+	int		   *conkeys;
+	int		   *confkeys;
+	Oid		   *conpfeqop;
+
+} ForeignKeyOptInfo;
 
 /*
  * EquivalenceClasses
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 87123a5..da1fd58 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -73,6 +73,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 8a55a09..c56cf8a 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -79,6 +79,7 @@ typedef struct RelationData
 	bool		rd_isvalid;		/* relcache entry is valid */
 	char		rd_indexvalid;	/* state of rd_indexlist: 0 = not valid, 1 =
 								 * valid, 2 = temporarily forced */
+	bool		rd_fkeyvalid;	/* state of rd_fkeylist: 0 = not valid, 1 = valid */
 
 	/*
 	 * rd_createSubid is the ID of the highest subtransaction the rel has
@@ -112,6 +113,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;		/* OIDs of foreign keys */
+
 	/* 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 6953281..8878478 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/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index c91273c..cc1cb78 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1909,6 +1909,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)
 {
 	/*
@@ -3299,6 +3309,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 d107d76..50828f2 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3732,6 +3732,405 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
 }
 
 /*
+ * quals_match_foreign_key
+ *		Determines if 'joinquals' contains quals which match up to the foreign
+ *		key 'fkinfo'. If a complete match is made to the foreign key, then a
+ *		bitmap is returned with bits set for each of the 'joinquals' 0 based
+ *		list position of each match. If 'joinquals' only partially matches the
+ *		foreign key, then NULL is returned.
+ */
+static Bitmapset *
+quals_match_foreign_key(PlannerInfo *root, ForeignKeyOptInfo *fkinfo,
+						RelOptInfo *fkrel, RelOptInfo *foreignrel,
+						List *joinquals)
+{
+	int i;
+	int nkeys = fkinfo->nkeys;
+	Bitmapset *qualmatches = NULL;
+	Bitmapset *fkmatches = NULL;
+
+	/*
+	 * Loop over each column of the foreign key and build a bitmap index
+	 * of each joinqual which matches. Note that we don't stop when we find
+	 * the first match, as the expression could be duplicated in the
+	 * joinquals, and we want to generate a bitmap index which has bits set for
+	 * every matching join qual.
+	 */
+	for (i = 0; i < nkeys; i++)
+	{
+		ListCell *lc;
+		int quallstidx = -1;
+
+		foreach(lc, joinquals)
+		{
+			RestrictInfo   *rinfo;
+			OpExpr		   *clause;
+			Var			   *leftvar;
+			Var			   *rightvar;
+
+			quallstidx++;
+
+			/*
+			 * Technically we don't need to, but here we skip this qual if
+			 * we've matched it to part of the foreign key already. This
+			 * should prove to be a useful optimization when the quals appear
+			 * in the same order as the foreign key's keys. We need only bother
+			 * doing this when the foreign key is made up of more than 1 set
+			 * of columns, and we're not testing the first column.
+			 */
+			if (i > 0 && bms_is_member(quallstidx, qualmatches))
+				continue;
+
+			/*
+			 * Here since 'usefulquals' only contains bitmap indexes for quals
+			 * of type "var op var" we can safely skip checking this.
+			 */
+			rinfo = (RestrictInfo *) lfirst(lc);
+			clause = (OpExpr *) rinfo->clause;
+
+			/*
+			 * If the operator does not match then there's little point in
+			 * checking the operands
+			 */
+			if (clause->opno != fkinfo->conpfeqop[i])
+				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;
+
+			/*
+			 * For RestrictInfos built from an eclass we must consider each
+			 * member of the eclass as rinfo's operands may not belong to the
+			 * foreign key. For efficient tracking of which Vars we've found,
+			 * since we're only tracking 2 Vars, we use a bitmask. We can
+			 * safely finish searching when both of the least significant bits
+			 * are set.
+			 */
+			if (rinfo->parent_ec)
+			{
+				EquivalenceClass   *ec = rinfo->parent_ec;
+				ListCell		   *lc2;
+				int					foundvarmask = 0;
+
+				foreach(lc2, ec->ec_members)
+				{
+					EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+					Var *var = (Var *) em->em_expr;
+
+					if (!IsA(var, Var))
+						continue;
+
+					if (foreignrel->relid == var->varno &&
+						fkinfo->confkeys[i] == var->varattno)
+						foundvarmask |= 1;
+
+					else if (fkrel->relid == var->varno &&
+						fkinfo->conkeys[i] == var->varattno)
+						foundvarmask |= 2;
+
+					/*
+					 * Check if we've found both matches. If found we add
+					 * this qual to the matched list and mark this key as
+					 * matched too.
+					 */
+					if (foundvarmask == 3)
+					{
+						qualmatches = bms_add_member(qualmatches, quallstidx);
+						fkmatches = bms_add_member(fkmatches, i);
+						break;
+					}
+				}
+			}
+			else
+			{
+				/*
+				 * In this non eclass RestrictInfo case we'll check if the left
+				 * and right Vars match to this part of the foreign key.
+				 * Remember that this could be written with the Vars in either
+				 * order, so we test both permutations of the expression.
+				 */
+				if (foreignrel->relid == leftvar->varno &&
+					fkrel->relid == rightvar->varno &&
+					fkinfo->confkeys[i] == leftvar->varattno &&
+					fkinfo->conkeys[i] == rightvar->varattno)
+				{
+					qualmatches = bms_add_member(qualmatches, quallstidx);
+					fkmatches = bms_add_member(fkmatches, i);
+				}
+				else if (foreignrel->relid == rightvar->varno &&
+					fkrel->relid == leftvar->varno &&
+					fkinfo->confkeys[i] == rightvar->varattno &&
+					fkinfo->conkeys[i] == leftvar->varattno)
+				{
+					qualmatches = bms_add_member(qualmatches, quallstidx);
+					fkmatches = bms_add_member(fkmatches, i);
+				}
+			}
+		}
+	}
+
+	/*
+	 * We only return the matches if we found a match for every column in
+	 * the foreign key.
+	 */
+	if (bms_num_members(fkmatches) == nkeys)
+	{
+		bms_free(fkmatches);
+		return qualmatches;
+	}
+
+	bms_free(fkmatches);
+	return NULL;
+}
+
+/*
+ * find_best_foreign_key_quals
+ *		Analyzes joinquals to determine if any quals match foreign keys defined
+ *		on 'fkrel' which reference 'foreignrel'. We return the number of keys
+ *		of the best matching foreign key. We assume the best matching foreign
+ *		key is the one with the most keys, not the most quals matching quals,
+ *		as quals could be duplicated. We also set 'joinqualsbitmap' bits to
+ *		mark which quals in 'joinquals' were matched. Zero is returned if no
+ *		match is found. In this case the value of 'joinqualsbitmap' will be set
+ *		to NULL.  Partial foreign key matches are currently ignored.
+ */
+static int
+find_best_foreign_key_quals(PlannerInfo *root, RelOptInfo *fkrel,
+							RelOptInfo *foreignrel, List *joinquals,
+							Bitmapset **joinqualsbitmap)
+{
+	Bitmapset	   *qualbestmatch;
+	ListCell	   *lc;
+	int				bestmatchnkeys;
+
+	/* fast path out when there's no foreign keys on fkrel */
+	if (fkrel->fkeylist == NIL)
+	{
+		*joinqualsbitmap = NULL;
+		return 0;
+	}
+
+	qualbestmatch = NULL;
+	bestmatchnkeys = 0;
+
+	/* now check the matches for each foreign key defined on the fkrel */
+	foreach(lc, fkrel->fkeylist)
+	{
+		ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+		Bitmapset *qualsmatched;
+
+		/*
+		 * We make no attempt in checking that this foreign key actually
+		 * references 'foreignrel', the reasoning here is that we may be able
+		 * to match the foreign key to an eclass member Var of a RestrictInfo
+		 * that's in qualslist, this Var may belong to some other relation.
+		 */
+		qualsmatched = quals_match_foreign_key(root, fkinfo, fkrel, foreignrel,
+											   joinquals);
+
+		/* Did we get a match? And is that match better than a previous one? */
+		if (qualsmatched != NULL && fkinfo->nkeys > bestmatchnkeys)
+		{
+			/* save the new best match */
+			bms_free(qualbestmatch);
+			qualbestmatch = qualsmatched;
+			bestmatchnkeys = fkinfo->nkeys;
+		}
+	}
+
+	/*
+	 * If no match was found, then make one last ditch attempt to find a match
+	 * by looking at foreign keys for other rels that we may exist in one of
+	 * the eclasses which the joinquals were built from.
+	 *
+	 * XXX Perhaps we should actually be looking for a better match using this
+	 * method, even if the code above already found a match.
+	 */
+	if (bestmatchnkeys == 0)
+	{
+		int				fkrelid;
+		Bitmapset	   *otherfkrels = NULL;
+
+		/*
+		 * First build a list of all rels seen in eclasses that joinquals were
+		 * build from.
+		 */
+		foreach(lc, joinquals)
+		{
+			RestrictInfo   *rinfo = (RestrictInfo *) lfirst(lc);
+			if (rinfo->parent_ec)
+				otherfkrels = bms_add_members(otherfkrels, rinfo->parent_ec->ec_relids);
+		}
+
+		/*
+		 * Remove both 'fkrel' and 'foreignrel' from the bitmap so that we're
+		 * left with only the extra rels that were seen.
+		 */
+		otherfkrels = bms_del_member(otherfkrels, fkrel->relid);
+		otherfkrels = bms_del_member(otherfkrels, foreignrel->relid);
+
+		if (bms_is_empty(otherfkrels))
+			return 0;
+
+		fkrelid = -1;
+		while ((fkrelid = bms_next_member(otherfkrels, fkrelid)) >= 0)
+		{
+			fkrel = find_base_rel(root, fkrelid);
+
+			/* The eclass may have some dead rels. We'll skip these. */
+			if (fkrel->reloptkind != RELOPT_BASEREL)
+				continue;
+
+			foreach(lc, fkrel->fkeylist)
+			{
+				ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+				Bitmapset *qualsmatched;
+
+				/*
+				 * We make no attempt in checking that this foreign key
+				 * actually references 'foreignrel', the reasoning here is
+				 * that we may be able to match the foreign key to an eclass
+				 * member Var of a RestrictInfo that's in qualslist, this Var
+				 * may belong to some other relation.
+				 */
+				qualsmatched = quals_match_foreign_key(root, fkinfo, fkrel,
+													   foreignrel, joinquals);
+
+				/* does this match match more keys than any previous match? */
+				if (qualsmatched != NULL && fkinfo->nkeys > bestmatchnkeys)
+				{
+					bms_free(qualbestmatch);
+					qualbestmatch = qualsmatched;
+					bestmatchnkeys = fkinfo->nkeys;
+				}
+			}
+		}
+	}
+
+	*joinqualsbitmap = qualbestmatch;
+	return bestmatchnkeys;
+}
+
+/*
+ * 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().
+ */
+static Selectivity
+clauselist_join_selectivity(PlannerInfo *root, List *joinquals,
+							JoinType jointype, SpecialJoinInfo *sjinfo)
+{
+	int				outerid;
+	int				innerid;
+	Selectivity		sel = 1.0;
+	Bitmapset	   *foundfkquals = NULL;
+
+	innerid = -1;
+	while ((innerid = bms_next_member(sjinfo->min_righthand, innerid)) >= 0)
+	{
+		RelOptInfo *innerrel = find_base_rel(root, innerid);
+
+		outerid = -1;
+		while ((outerid = bms_next_member(sjinfo->min_lefthand, outerid)) >= 0)
+		{
+			RelOptInfo	   *outerrel = find_base_rel(root, outerid);
+			Bitmapset	   *outer2inner;
+			Bitmapset	   *inner2outer;
+			int				innermatches;
+			int				outermatches;
+
+			/*
+			 * check which quals are matched by a foreign key referencing the
+			 * innerrel.
+			 */
+			outermatches = find_best_foreign_key_quals(root, outerrel,
+											innerrel, joinquals, &outer2inner);
+
+			/* do the same, but with relations swapped */
+			innermatches = find_best_foreign_key_quals(root, innerrel,
+											outerrel, joinquals, &inner2outer);
+
+			/*
+			 * did we find any matches at all? If so we need to see which one is
+			 * the best/longest match
+			 */
+			if (outermatches != 0 || innermatches != 0)
+			{
+				double	referenced_tuples;
+				bool overlap;
+
+				/* either could be zero, but not both. */
+				if (outermatches < innermatches)
+				{
+					overlap = bms_overlap(foundfkquals, inner2outer);
+
+					foundfkquals = bms_add_members(foundfkquals, inner2outer);
+					referenced_tuples = Max(outerrel->tuples, 1.0);
+				}
+				else
+				{
+					overlap = bms_overlap(foundfkquals, outer2inner);
+
+					foundfkquals = bms_add_members(foundfkquals, outer2inner);
+					referenced_tuples = Max(innerrel->tuples, 1.0);
+				}
+
+				/*
+				 * XXX should we ignore these overlapping matches?
+				 * Or perhaps take the Max() or Min()?
+				 */
+				if (overlap)
+				{
+					if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+						sel = Min(sel,Min(1.0 / (outerrel->tuples / Max(innerrel->tuples, 1.0)), 1.0));
+					else
+						sel = Min(sel, 1.0 / referenced_tuples);
+				}
+				else
+				{
+					if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+						sel *= Min(1.0 / (outerrel->tuples / Max(innerrel->tuples, 1.0)), 1.0);
+					else
+						sel *= 1.0 / referenced_tuples;
+				}
+			}
+		}
+	}
+
+	/*
+	 * If any non matched quals exist then we build a list of the non-matches
+	 * and use clauselist_selectivity() to estimate the selectivity of these.
+	 */
+	if (bms_num_members(foundfkquals) < list_length(joinquals))
+	{
+		ListCell *lc;
+		int lstidx = 0;
+		List *nonfkeyclauses = NIL;
+
+		foreach (lc, joinquals)
+		{
+			if (!bms_is_member(lstidx, foundfkquals))
+				nonfkeyclauses = lappend(nonfkeyclauses, lfirst(lc));
+			lstidx++;
+		}
+		sel *= clauselist_selectivity(root, nonfkeyclauses, 0, jointype, sjinfo);
+	}
+
+	return sel;
+}
+
+/*
  * calc_joinrel_size_estimate
  *		Workhorse for set_joinrel_size_estimates and
  *		get_parameterized_joinrel_size.
@@ -3777,11 +4176,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,
@@ -3794,11 +4193,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/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 9442e5f..dbe6038 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -27,6 +27,7 @@
 #include "catalog/catalog.h"
 #include "catalog/dependency.h"
 #include "catalog/heap.h"
+#include "catalog/pg_constraint.h"
 #include "foreign/fdwapi.h"
 #include "miscadmin.h"
 #include "nodes/makefuncs.h"
@@ -40,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"
 
@@ -93,6 +95,9 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	Relation	relation;
 	bool		hasindex;
 	List	   *indexinfos = NIL;
+	List	   *fkinfos = NIL;
+	List	   *fkoidlist;
+	ListCell   *l;
 
 	/*
 	 * We need not lock the relation since it was already locked, either by
@@ -140,7 +145,6 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	if (hasindex)
 	{
 		List	   *indexoidlist;
-		ListCell   *l;
 		LOCKMODE	lmode;
 
 		indexoidlist = RelationGetIndexList(relation);
@@ -380,6 +384,77 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	}
 
 	rel->indexlist = indexinfos;
+ 
+	/* load foreign keys */
+	fkoidlist = RelationGetFKeyList(relation);
+
+	foreach(l, fkoidlist)
+	{
+		int			i;
+		ArrayType  *arr;
+		Datum		adatum;
+		bool		isnull;
+		int			numkeys;
+		Oid			fkoid = lfirst_oid(l);
+
+		HeapTuple	htup = SearchSysCache1(CONSTROID, ObjectIdGetDatum(fkoid));
+		Form_pg_constraint constraint = (Form_pg_constraint) GETSTRUCT(htup);
+
+		ForeignKeyOptInfo *info;
+
+		Assert(constraint->contype == CONSTRAINT_FOREIGN);
+
+		info = makeNode(ForeignKeyOptInfo);
+
+		info->conrelid = constraint->conrelid;
+		info->confrelid = constraint->confrelid;
+
+		/* conkey */
+		adatum = SysCacheGetAttr(CONSTROID, htup,
+									Anum_pg_constraint_conkey, &isnull);
+		Assert(!isnull);
+
+		arr = DatumGetArrayTypeP(adatum);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conkeys = (int*)palloc0(numkeys * sizeof(int));
+
+		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);
+		numkeys = ARR_DIMS(arr)[0];
+		info->confkeys = (int*)palloc0(numkeys * sizeof(int));
+
+		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);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conpfeqop = (Oid*)palloc0(numkeys * sizeof(Oid));
+
+		for (i = 0; i < numkeys; i++)
+			info->conpfeqop[i] = ((Oid *) ARR_DATA_PTR(arr))[i];
+
+		info->nkeys = numkeys;
+
+		ReleaseSysCache(htup);
+
+		fkinfos = lcons(info, fkinfos);
+	}
+
+	list_free(fkoidlist);
+
+	rel->fkeylist = fkinfos;
 
 	/* Grab foreign-table info using the relcache, while we have it */
 	if (relation->rd_rel->relkind == RELKIND_FOREIGN_TABLE)
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index 9c3d096..3ae9022 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -3923,6 +3923,73 @@ RelationGetIndexList(Relation relation)
 }
 
 /*
+ * RelationGetFKeyList -- get a list of foreign key oids
+ *
+ * TODO blah blah blah
+ */
+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_fkeyvalid)
+		return list_copy(relation->rd_fkeylist);
+
+	/*
+	 * 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);
+
+		/* return only foreign keys */
+		if (constraint->contype != CONSTRAINT_FOREIGN)
+			continue;
+
+		/* Add index's OID to result list in the proper order */
+		result = insert_ordered_oid(result, HeapTupleGetOid(htup));
+	}
+
+	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);
+	relation->rd_fkeyvalid = true;
+	MemoryContextSwitchTo(oldcxt);
+
+	/* Don't leak the old list, if there is one */
+	list_free(oldlist);
+
+	return result;
+}
+
+/*
  * insert_ordered_oid
  *		Insert a new Oid into a sorted list of Oids, preserving ordering
  *
@@ -4891,6 +4958,8 @@ load_relcache_init_file(bool shared)
 		rel->rd_indexattr = NULL;
 		rel->rd_keyattr = NULL;
 		rel->rd_idattr = NULL;
+		rel->rd_fkeylist = NIL;
+		rel->rd_fkeyvalid = false;
 		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 274480e..5c40b83 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -221,6 +221,7 @@ typedef enum NodeTag
 	T_PlannerGlobal,
 	T_RelOptInfo,
 	T_IndexOptInfo,
+	T_ForeignKeyOptInfo,
 	T_ParamPathInfo,
 	T_Path,
 	T_IndexPath,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 79bed33..8ce35e7 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -472,6 +472,7 @@ typedef struct RelOptInfo
 	Relids		lateral_relids; /* minimum parameterization of 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;
@@ -566,6 +567,20 @@ typedef struct IndexOptInfo
 	bool		amhasgetbitmap; /* does AM have amgetbitmap interface? */
 } IndexOptInfo;
 
+/* TODO add info*/
+typedef struct ForeignKeyOptInfo
+{
+	NodeTag		type;
+
+	Oid			conrelid;
+	Oid			confrelid;
+
+	int			nkeys;
+	int		   *conkeys;
+	int		   *confkeys;
+	Oid		   *conpfeqop;
+
+} ForeignKeyOptInfo;
 
 /*
  * EquivalenceClasses
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 87123a5..da1fd58 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -73,6 +73,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 8a55a09..c56cf8a 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -79,6 +79,7 @@ typedef struct RelationData
 	bool		rd_isvalid;		/* relcache entry is valid */
 	char		rd_indexvalid;	/* state of rd_indexlist: 0 = not valid, 1 =
 								 * valid, 2 = temporarily forced */
+	bool		rd_fkeyvalid;	/* state of rd_fkeylist: 0 = not valid, 1 = valid */
 
 	/*
 	 * rd_createSubid is the ID of the highest subtransaction the rel has
@@ -112,6 +113,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;		/* OIDs of foreign keys */
+
 	/* 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 6953281..8878478 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/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index eb0fc1e..3d38384 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -2153,6 +2153,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)
 {
 	/*
@@ -3603,6 +3613,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 5350329..4399a9f 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3870,6 +3870,347 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
 }
 
 /*
+ * quals_match_foreign_key
+ *		Determines if the foreign key is matched by joinquals.
+ *
+ * Checks that there are conditions on all columns of the foreign key, matching
+ * the operator used by the foreign key etc. If such complete match is found,
+ * the function returns bitmap identifying the matching quals (0-based).
+ *
+ * Otherwise (no match at all or incomplete match), NULL is returned.
+ */
+static Bitmapset *
+quals_match_foreign_key(PlannerInfo *root, ForeignKeyOptInfo *fkinfo,
+						RelOptInfo *fkrel, RelOptInfo *foreignrel,
+						List *joinquals)
+{
+	int i;
+	int nkeys = fkinfo->nkeys;
+	Bitmapset *qualmatches = NULL;
+	Bitmapset *fkmatches = NULL;
+
+	/*
+	 * Loop over each column of the foreign key and build a bitmap index
+	 * of each joinqual which matches. Note that we don't stop when we find
+	 * the first match, as the expression could be duplicated in the
+	 * joinquals, and we want to generate a bitmap index which has bits set for
+	 * every matching join qual.
+	 */
+	for (i = 0; i < nkeys; i++)
+	{
+		ListCell *lc;
+		int quallstidx = -1;
+
+		foreach(lc, joinquals)
+		{
+			RestrictInfo   *rinfo;
+			OpExpr		   *clause;
+			Var			   *leftvar;
+			Var			   *rightvar;
+
+			quallstidx++;
+
+			/*
+			 * Technically we don't need to, but here we skip this qual if
+			 * we've matched it to part of the foreign key already. This
+			 * should prove to be a useful optimization when the quals appear
+			 * in the same order as the foreign key's keys. We need only bother
+			 * doing this when the foreign key is made up of more than 1 set
+			 * of columns, and we're not testing the first column.
+			 */
+			if (i > 0 && bms_is_member(quallstidx, qualmatches))
+				continue;
+
+			/*
+			 * Here since 'usefulquals' only contains bitmap indexes for quals
+			 * of type "var op var" we can safely skip checking this.
+			 */
+			rinfo = (RestrictInfo *) lfirst(lc);
+			clause = (OpExpr *) rinfo->clause;
+
+			/*
+			 * If the operator does not match then there's little point in
+			 * checking the operands
+			 */
+			if (clause->opno != fkinfo->conpfeqop[i])
+				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;
+
+			/*
+			 * For RestrictInfos built from an eclass we must consider each
+			 * member of the eclass as rinfo's operands may not belong to the
+			 * foreign key. For efficient tracking of which Vars we've found,
+			 * since we're only tracking 2 Vars, we use a bitmask. We can
+			 * safely finish searching when both of the least significant bits
+			 * are set.
+			 */
+			if (rinfo->parent_ec)
+			{
+				EquivalenceClass   *ec = rinfo->parent_ec;
+				ListCell		   *lc2;
+				int					foundvarmask = 0;
+
+				foreach(lc2, ec->ec_members)
+				{
+					EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+					Var *var = (Var *) em->em_expr;
+
+					if (!IsA(var, Var))
+						continue;
+
+					if (foreignrel->relid == var->varno &&
+						fkinfo->confkeys[i] == var->varattno)
+						foundvarmask |= 1;
+
+					else if (fkrel->relid == var->varno &&
+						fkinfo->conkeys[i] == var->varattno)
+						foundvarmask |= 2;
+
+					/*
+					 * Check if we've found both matches. If found we add
+					 * this qual to the matched list and mark this key as
+					 * matched too.
+					 */
+					if (foundvarmask == 3)
+					{
+						qualmatches = bms_add_member(qualmatches, quallstidx);
+						fkmatches = bms_add_member(fkmatches, i);
+						break;
+					}
+				}
+			}
+			else
+			{
+				/*
+				 * In this non eclass RestrictInfo case we'll check if the left
+				 * and right Vars match to this part of the foreign key.
+				 * Remember that this could be written with the Vars in either
+				 * order, so we test both permutations of the expression.
+				 */
+				if ((foreignrel->relid == leftvar->varno) &&
+					(fkrel->relid == rightvar->varno) &&
+					(fkinfo->confkeys[i] == leftvar->varattno) &&
+					(fkinfo->conkeys[i] == rightvar->varattno))
+				{
+					qualmatches = bms_add_member(qualmatches, quallstidx);
+					fkmatches = bms_add_member(fkmatches, i);
+				}
+				else if ((foreignrel->relid == rightvar->varno) &&
+						 (fkrel->relid == leftvar->varno) &&
+						 (fkinfo->confkeys[i] == rightvar->varattno) &&
+						 (fkinfo->conkeys[i] == leftvar->varattno))
+				{
+					qualmatches = bms_add_member(qualmatches, quallstidx);
+					fkmatches = bms_add_member(fkmatches, i);
+				}
+			}
+		}
+	}
+
+	/* can't find more matches than columns in the foreign key */
+	Assert(bms_num_members(fkmatches) <= nkeys);
+
+	/* Only return the matches if we the foreign key is matched fully. */
+	if (bms_num_members(fkmatches) == nkeys)
+	{
+		bms_free(fkmatches);
+		return qualmatches;
+	}
+
+	bms_free(fkmatches);
+	bms_free(qualmatches);
+
+	return NULL;
+}
+
+/*
+ * find_best_foreign_key_quals
+ * 		Finds the foreign key best matching the joinquals.
+ *
+ * Analyzes joinquals to determine if any quals match foreign keys defined the
+ * two relations (fkrel referencing foreignrel). When multiple foreign keys
+ * match, we do choose the one with the most keys as the best one. We might
+ * also choose the one matching the most quals, however we assume the quals
+ * may be duplicated.
+ *
+ * We also track which joinquals match the current foreign key, so that we can
+ * easily skip then when computing the selectivity.
+ *
+ * When no matching foreign key is found we return 0, otherwise we return the
+ * number of keys in the foreign key.
+ *
+ * Foreign keys matched only partially ( are currently ignored.
+ */
+static int
+find_best_foreign_key_quals(PlannerInfo *root, RelOptInfo *fkrel,
+							RelOptInfo *foreignrel, List *joinquals,
+							Bitmapset **joinqualsbitmap)
+{
+	Bitmapset	   *qualbestmatch;
+	ListCell	   *lc;
+	int				bestmatchnkeys;
+
+	/* fast path out when there's no foreign keys on fkrel */
+	if (fkrel->fkeylist == NIL)
+	{
+		*joinqualsbitmap = NULL;
+		return 0;
+	}
+
+	qualbestmatch = NULL;
+	bestmatchnkeys = 0;
+
+	/* now check the matches for each foreign key defined on the fkrel */
+	foreach(lc, fkrel->fkeylist)
+	{
+		ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+		Bitmapset *qualsmatched;
+
+		/*
+		 * We make no attempt in checking that this foreign key actually
+		 * references 'foreignrel', the reasoning here is that we may be able
+		 * to match the foreign key to an eclass member Var of a RestrictInfo
+		 * that's in qualslist, this Var may belong to some other relation.
+		 */
+		qualsmatched = quals_match_foreign_key(root, fkinfo, fkrel, foreignrel,
+											   joinquals);
+
+		/* Did we get a match? And is that match better than a previous one? */
+		if (qualsmatched != NULL && fkinfo->nkeys > bestmatchnkeys)
+		{
+			/* save the new best match */
+			bms_free(qualbestmatch);
+			qualbestmatch = qualsmatched;
+			bestmatchnkeys = fkinfo->nkeys;
+		}
+	}
+
+	*joinqualsbitmap = qualbestmatch;
+	return bestmatchnkeys;
+}
+
+/*
+ * 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().
+ */
+static Selectivity
+clauselist_join_selectivity(PlannerInfo *root, List *joinquals,
+							JoinType jointype, SpecialJoinInfo *sjinfo)
+{
+	int				outerid;
+	int				innerid;
+	Selectivity		sel = 1.0;
+	Bitmapset	   *foundfkquals = NULL;
+
+	innerid = -1;
+	while ((innerid = bms_next_member(sjinfo->min_righthand, innerid)) >= 0)
+	{
+		RelOptInfo *innerrel = find_base_rel(root, innerid);
+
+		outerid = -1;
+		while ((outerid = bms_next_member(sjinfo->min_lefthand, outerid)) >= 0)
+		{
+			RelOptInfo	   *outerrel = find_base_rel(root, outerid);
+			Bitmapset	   *outer2inner;
+			Bitmapset	   *inner2outer;
+			int				innermatches;
+			int				outermatches;
+
+			/*
+			 * check which quals are matched by a foreign key referencing the
+			 * innerrel.
+			 */
+			outermatches = find_best_foreign_key_quals(root, outerrel,
+											innerrel, joinquals, &outer2inner);
+
+			/* do the same, but with relations swapped */
+			innermatches = find_best_foreign_key_quals(root, innerrel,
+											outerrel, joinquals, &inner2outer);
+
+			/*
+			 * did we find any matches at all? If so we need to see which one is
+			 * the best/longest match
+			 */
+			if (outermatches != 0 || innermatches != 0)
+			{
+				double	referenced_tuples;
+				bool overlap;
+
+				/* either could be zero, but not both. */
+				if (outermatches < innermatches)
+				{
+					overlap = bms_overlap(foundfkquals, inner2outer);
+
+					foundfkquals = bms_add_members(foundfkquals, inner2outer);
+					referenced_tuples = Max(outerrel->tuples, 1.0);
+				}
+				else
+				{
+					overlap = bms_overlap(foundfkquals, outer2inner);
+
+					foundfkquals = bms_add_members(foundfkquals, outer2inner);
+					referenced_tuples = Max(innerrel->tuples, 1.0);
+				}
+
+				/*
+				 * XXX should we ignore these overlapping matches?
+				 * Or perhaps take the Max() or Min()?
+				 */
+				if (overlap)
+				{
+					if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+						sel = Min(sel,Min(1.0 / (outerrel->tuples / Max(innerrel->tuples, 1.0)), 1.0));
+					else
+						sel = Min(sel, 1.0 / referenced_tuples);
+				}
+				else
+				{
+					if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+						sel *= Min(1.0 / (outerrel->tuples / Max(innerrel->tuples, 1.0)), 1.0);
+					else
+						sel *= 1.0 / referenced_tuples;
+				}
+			}
+		}
+	}
+
+	/*
+	 * If any non matched quals exist then we build a list of the non-matches
+	 * and use clauselist_selectivity() to estimate the selectivity of these.
+	 */
+	if (bms_num_members(foundfkquals) < list_length(joinquals))
+	{
+		ListCell *lc;
+		int lstidx = 0;
+		List *nonfkeyclauses = NIL;
+
+		foreach (lc, joinquals)
+		{
+			if (!bms_is_member(lstidx, foundfkquals))
+				nonfkeyclauses = lappend(nonfkeyclauses, lfirst(lc));
+			lstidx++;
+		}
+		sel *= clauselist_selectivity(root, nonfkeyclauses, 0, jointype, sjinfo);
+	}
+
+	return sel;
+}
+
+/*
  * calc_joinrel_size_estimate
  *		Workhorse for set_joinrel_size_estimates and
  *		get_parameterized_joinrel_size.
@@ -3915,11 +4256,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,
@@ -3932,11 +4273,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/util/plancat.c b/src/backend/optimizer/util/plancat.c
index ad715bb..481911e 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -28,6 +28,7 @@
 #include "catalog/dependency.h"
 #include "catalog/heap.h"
 #include "catalog/pg_am.h"
+#include "catalog/pg_constraint.h"
 #include "foreign/fdwapi.h"
 #include "miscadmin.h"
 #include "nodes/makefuncs.h"
@@ -41,6 +42,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"
 
@@ -94,6 +96,9 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	Relation	relation;
 	bool		hasindex;
 	List	   *indexinfos = NIL;
+	List	   *fkinfos = NIL;
+	List	   *fkoidlist;
+	ListCell   *l;
 
 	/*
 	 * We need not lock the relation since it was already locked, either by
@@ -141,7 +146,6 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	if (hasindex)
 	{
 		List	   *indexoidlist;
-		ListCell   *l;
 		LOCKMODE	lmode;
 
 		indexoidlist = RelationGetIndexList(relation);
@@ -387,6 +391,77 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 
 	rel->indexlist = indexinfos;
 
+	/* load foreign keys */
+	fkoidlist = RelationGetFKeyList(relation);
+
+	foreach(l, fkoidlist)
+	{
+		int			i;
+		ArrayType  *arr;
+		Datum		adatum;
+		bool		isnull;
+		int			numkeys;
+		Oid			fkoid = lfirst_oid(l);
+
+		HeapTuple	htup = SearchSysCache1(CONSTROID, ObjectIdGetDatum(fkoid));
+		Form_pg_constraint constraint = (Form_pg_constraint) GETSTRUCT(htup);
+
+		ForeignKeyOptInfo *info;
+
+		Assert(constraint->contype == CONSTRAINT_FOREIGN);
+
+		info = makeNode(ForeignKeyOptInfo);
+
+		info->conrelid = constraint->conrelid;
+		info->confrelid = constraint->confrelid;
+
+		/* conkey */
+		adatum = SysCacheGetAttr(CONSTROID, htup,
+									Anum_pg_constraint_conkey, &isnull);
+		Assert(!isnull);
+
+		arr = DatumGetArrayTypeP(adatum);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conkeys = (int*)palloc0(numkeys * sizeof(int));
+
+		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);
+		numkeys = ARR_DIMS(arr)[0];
+		info->confkeys = (int*)palloc0(numkeys * sizeof(int));
+
+		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);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conpfeqop = (Oid*)palloc0(numkeys * sizeof(Oid));
+
+		for (i = 0; i < numkeys; i++)
+			info->conpfeqop[i] = ((Oid *) ARR_DATA_PTR(arr))[i];
+
+		info->nkeys = numkeys;
+
+		ReleaseSysCache(htup);
+
+		fkinfos = lcons(info, fkinfos);
+	}
+
+	list_free(fkoidlist);
+
+	rel->fkeylist = fkinfos;
+
 	/* Grab foreign-table info using the relcache, while we have it */
 	if (relation->rd_rel->relkind == RELKIND_FOREIGN_TABLE)
 	{
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index 130c06d..9390235 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -3957,6 +3957,73 @@ RelationGetIndexList(Relation relation)
 }
 
 /*
+ * RelationGetFKeyList -- get a list of foreign key oids
+ *
+ * TODO blah blah blah
+ */
+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_fkeyvalid)
+		return list_copy(relation->rd_fkeylist);
+
+	/*
+	 * 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);
+
+		/* return only foreign keys */
+		if (constraint->contype != CONSTRAINT_FOREIGN)
+			continue;
+
+		/* Add index's OID to result list in the proper order */
+		result = insert_ordered_oid(result, HeapTupleGetOid(htup));
+	}
+
+	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);
+	relation->rd_fkeyvalid = true;
+	MemoryContextSwitchTo(oldcxt);
+
+	/* Don't leak the old list, if there is one */
+	list_free(oldlist);
+
+	return result;
+}
+
+/*
  * insert_ordered_oid
  *		Insert a new Oid into a sorted list of Oids, preserving ordering
  *
@@ -4920,6 +4987,8 @@ load_relcache_init_file(bool shared)
 		rel->rd_indexattr = NULL;
 		rel->rd_keyattr = NULL;
 		rel->rd_idattr = NULL;
+		rel->rd_fkeylist = NIL;
+		rel->rd_fkeyvalid = false;
 		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 fad9988..18f42b3 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -223,6 +223,7 @@ typedef enum NodeTag
 	T_PlannerGlobal,
 	T_RelOptInfo,
 	T_IndexOptInfo,
+	T_ForeignKeyOptInfo,
 	T_ParamPathInfo,
 	T_Path,
 	T_IndexPath,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 641728b..e88e9a2 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -539,6 +539,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;
@@ -634,6 +635,27 @@ typedef struct IndexOptInfo
 	void		(*amcostestimate) ();	/* AM's cost estimator */
 } IndexOptInfo;
 
+/*
+ * 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;
 
 /*
  * EquivalenceClasses
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 2fccc3a..f0840e5 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 f2bebf2..f1fe4dc 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -61,6 +61,7 @@ typedef struct RelationData
 	bool		rd_isvalid;		/* relcache entry is valid */
 	char		rd_indexvalid;	/* state of rd_indexlist: 0 = not valid, 1 =
 								 * valid, 2 = temporarily forced */
+	bool		rd_fkeyvalid;	/* state of rd_fkeylist: 0 = not valid, 1 = valid */
 
 	/*
 	 * rd_createSubid is the ID of the highest subtransaction the rel has
@@ -94,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;		/* OIDs of foreign keys */
+
 	/* 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);

From bb07024646068a0bd82258495496ebac61f7e763 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@pgaddict.com>
Date: Thu, 7 Apr 2016 00:57:44 +0200
Subject: [PATCH 1/2] add foreign key info into relcache

---
 src/backend/nodes/outfuncs.c         | 13 ++++++
 src/backend/optimizer/util/plancat.c | 77 +++++++++++++++++++++++++++++++++++-
 src/backend/utils/cache/relcache.c   | 68 +++++++++++++++++++++++++++++++
 src/include/nodes/nodes.h            |  1 +
 src/include/nodes/relation.h         | 22 +++++++++++
 src/include/utils/rel.h              |  3 ++
 src/include/utils/relcache.h         |  1 +
 7 files changed, 184 insertions(+), 1 deletion(-)

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index e39c374..f783a49 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/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 5bdeac0..e5c5551 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -28,6 +28,7 @@
 #include "catalog/dependency.h"
 #include "catalog/heap.h"
 #include "catalog/pg_am.h"
+#include "catalog/pg_constraint.h"
 #include "foreign/fdwapi.h"
 #include "miscadmin.h"
 #include "nodes/makefuncs.h"
@@ -41,6 +42,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"
 
@@ -94,6 +96,9 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	Relation	relation;
 	bool		hasindex;
 	List	   *indexinfos = NIL;
+	List	   *fkinfos = NIL;
+	List	   *fkoidlist;
+	ListCell   *l;
 
 	/*
 	 * We need not lock the relation since it was already locked, either by
@@ -141,7 +146,6 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 	if (hasindex)
 	{
 		List	   *indexoidlist;
-		ListCell   *l;
 		LOCKMODE	lmode;
 
 		indexoidlist = RelationGetIndexList(relation);
@@ -388,6 +392,77 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
 
 	rel->indexlist = indexinfos;
 
+	/* load foreign keys */
+	fkoidlist = RelationGetFKeyList(relation);
+
+	foreach(l, fkoidlist)
+	{
+		int			i;
+		ArrayType  *arr;
+		Datum		adatum;
+		bool		isnull;
+		int			numkeys;
+		Oid			fkoid = lfirst_oid(l);
+
+		HeapTuple	htup = SearchSysCache1(CONSTROID, ObjectIdGetDatum(fkoid));
+		Form_pg_constraint constraint = (Form_pg_constraint) GETSTRUCT(htup);
+
+		ForeignKeyOptInfo *info;
+
+		Assert(constraint->contype == CONSTRAINT_FOREIGN);
+
+		info = makeNode(ForeignKeyOptInfo);
+
+		info->conrelid = constraint->conrelid;
+		info->confrelid = constraint->confrelid;
+
+		/* conkey */
+		adatum = SysCacheGetAttr(CONSTROID, htup,
+									Anum_pg_constraint_conkey, &isnull);
+		Assert(!isnull);
+
+		arr = DatumGetArrayTypeP(adatum);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conkeys = (int*)palloc0(numkeys * sizeof(int));
+
+		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);
+		numkeys = ARR_DIMS(arr)[0];
+		info->confkeys = (int*)palloc0(numkeys * sizeof(int));
+
+		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);
+		numkeys = ARR_DIMS(arr)[0];
+		info->conpfeqop = (Oid*)palloc0(numkeys * sizeof(Oid));
+
+		for (i = 0; i < numkeys; i++)
+			info->conpfeqop[i] = ((Oid *) ARR_DATA_PTR(arr))[i];
+
+		info->nkeys = numkeys;
+
+		ReleaseSysCache(htup);
+
+		fkinfos = lcons(info, fkinfos);
+	}
+
+	list_free(fkoidlist);
+
+	rel->fkeylist = fkinfos;
+
 	/* Grab foreign-table info using the relcache, while we have it */
 	if (relation->rd_rel->relkind == RELKIND_FOREIGN_TABLE)
 	{
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index 130c06d..273d70e 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,72 @@ RelationGetIndexList(Relation relation)
 }
 
 /*
+ * RelationGetFKeyList -- get a list of foreign key oids
+ *
+ * TODO blah blah blah
+ */
+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);
+
+	/*
+	 * 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);
+
+		/* return only foreign keys */
+		if (constraint->contype != CONSTRAINT_FOREIGN)
+			continue;
+
+		/* Add index's OID to result list in the proper order */
+		result = insert_ordered_oid(result, HeapTupleGetOid(htup));
+	}
+
+	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 */
+	list_free(oldlist);
+
+	return result;
+}
+
+/*
  * insert_ordered_oid
  *		Insert a new Oid into a sorted list of Oids, preserving ordering
  *
@@ -4920,6 +4987,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 3f22bdb..84efa8e 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -223,6 +223,7 @@ typedef enum NodeTag
 	T_PlannerGlobal,
 	T_RelOptInfo,
 	T_IndexOptInfo,
+	T_ForeignKeyOptInfo,
 	T_ParamPathInfo,
 	T_Path,
 	T_IndexPath,
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 5264d3c..d430f6e 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -516,6 +516,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;
@@ -621,6 +622,27 @@ typedef struct IndexOptInfo
 	void		(*amcostestimate) ();	/* AM's cost estimator */
 } IndexOptInfo;
 
+/*
+ * 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;
 
 /*
  * EquivalenceClasses
diff --git a/src/include/utils/rel.h b/src/include/utils/rel.h
index f2bebf2..51eb27a 100644
--- a/src/include/utils/rel.h
+++ b/src/include/utils/rel.h
@@ -94,6 +94,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;		/* OIDs of foreign keys */
+
 	/* 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);
-- 
2.5.5

From a662c85b18c126e67a07aa68c613a7555150ec02 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@pgaddict.com>
Date: Thu, 7 Apr 2016 00:58:03 +0200
Subject: [PATCH 2/2] use fkeys in join estimation

---
 src/backend/optimizer/path/costsize.c | 360 +++++++++++++++++++++++++++++++++-
 src/include/optimizer/paths.h         |   2 +
 2 files changed, 352 insertions(+), 10 deletions(-)

diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 70a4c27..b403558 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3888,6 +3888,347 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
 }
 
 /*
+ * quals_match_foreign_key
+ *		Determines if the foreign key is matched by joinquals.
+ *
+ * Checks that there are conditions on all columns of the foreign key, matching
+ * the operator used by the foreign key etc. If such complete match is found,
+ * the function returns bitmap identifying the matching quals (0-based).
+ *
+ * Otherwise (no match at all or incomplete match), NULL is returned.
+ */
+static Bitmapset *
+quals_match_foreign_key(PlannerInfo *root, ForeignKeyOptInfo *fkinfo,
+						RelOptInfo *fkrel, RelOptInfo *foreignrel,
+						List *joinquals)
+{
+	int i;
+	int nkeys = fkinfo->nkeys;
+	Bitmapset *qualmatches = NULL;
+	Bitmapset *fkmatches = NULL;
+
+	/*
+	 * Loop over each column of the foreign key and build a bitmap index
+	 * of each joinqual which matches. Note that we don't stop when we find
+	 * the first match, as the expression could be duplicated in the
+	 * joinquals, and we want to generate a bitmap index which has bits set for
+	 * every matching join qual.
+	 */
+	for (i = 0; i < nkeys; i++)
+	{
+		ListCell *lc;
+		int quallstidx = -1;
+
+		foreach(lc, joinquals)
+		{
+			RestrictInfo   *rinfo;
+			OpExpr		   *clause;
+			Var			   *leftvar;
+			Var			   *rightvar;
+
+			quallstidx++;
+
+			/*
+			 * Technically we don't need to, but here we skip this qual if
+			 * we've matched it to part of the foreign key already. This
+			 * should prove to be a useful optimization when the quals appear
+			 * in the same order as the foreign key's keys. We need only bother
+			 * doing this when the foreign key is made up of more than 1 set
+			 * of columns, and we're not testing the first column.
+			 */
+			if (i > 0 && bms_is_member(quallstidx, qualmatches))
+				continue;
+
+			/*
+			 * Here since 'usefulquals' only contains bitmap indexes for quals
+			 * of type "var op var" we can safely skip checking this.
+			 */
+			rinfo = (RestrictInfo *) lfirst(lc);
+			clause = (OpExpr *) rinfo->clause;
+
+			/*
+			 * If the operator does not match then there's little point in
+			 * checking the operands
+			 */
+			if (clause->opno != fkinfo->conpfeqop[i])
+				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;
+
+			/*
+			 * For RestrictInfos built from an eclass we must consider each
+			 * member of the eclass as rinfo's operands may not belong to the
+			 * foreign key. For efficient tracking of which Vars we've found,
+			 * since we're only tracking 2 Vars, we use a bitmask. We can
+			 * safely finish searching when both of the least significant bits
+			 * are set.
+			 */
+			if (rinfo->parent_ec)
+			{
+				EquivalenceClass   *ec = rinfo->parent_ec;
+				ListCell		   *lc2;
+				int					foundvarmask = 0;
+
+				foreach(lc2, ec->ec_members)
+				{
+					EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+					Var *var = (Var *) em->em_expr;
+
+					if (!IsA(var, Var))
+						continue;
+
+					if (foreignrel->relid == var->varno &&
+						fkinfo->confkeys[i] == var->varattno)
+						foundvarmask |= 1;
+
+					else if (fkrel->relid == var->varno &&
+						fkinfo->conkeys[i] == var->varattno)
+						foundvarmask |= 2;
+
+					/*
+					 * Check if we've found both matches. If found we add
+					 * this qual to the matched list and mark this key as
+					 * matched too.
+					 */
+					if (foundvarmask == 3)
+					{
+						qualmatches = bms_add_member(qualmatches, quallstidx);
+						fkmatches = bms_add_member(fkmatches, i);
+						break;
+					}
+				}
+			}
+			else
+			{
+				/*
+				 * In this non eclass RestrictInfo case we'll check if the left
+				 * and right Vars match to this part of the foreign key.
+				 * Remember that this could be written with the Vars in either
+				 * order, so we test both permutations of the expression.
+				 */
+				if ((foreignrel->relid == leftvar->varno) &&
+					(fkrel->relid == rightvar->varno) &&
+					(fkinfo->confkeys[i] == leftvar->varattno) &&
+					(fkinfo->conkeys[i] == rightvar->varattno))
+				{
+					qualmatches = bms_add_member(qualmatches, quallstidx);
+					fkmatches = bms_add_member(fkmatches, i);
+				}
+				else if ((foreignrel->relid == rightvar->varno) &&
+						 (fkrel->relid == leftvar->varno) &&
+						 (fkinfo->confkeys[i] == rightvar->varattno) &&
+						 (fkinfo->conkeys[i] == leftvar->varattno))
+				{
+					qualmatches = bms_add_member(qualmatches, quallstidx);
+					fkmatches = bms_add_member(fkmatches, i);
+				}
+			}
+		}
+	}
+
+	/* can't find more matches than columns in the foreign key */
+	Assert(bms_num_members(fkmatches) <= nkeys);
+
+	/* Only return the matches if we the foreign key is matched fully. */
+	if (bms_num_members(fkmatches) == nkeys)
+	{
+		bms_free(fkmatches);
+		return qualmatches;
+	}
+
+	bms_free(fkmatches);
+	bms_free(qualmatches);
+
+	return NULL;
+}
+
+/*
+ * find_best_foreign_key_quals
+ * 		Finds the foreign key best matching the joinquals.
+ *
+ * Analyzes joinquals to determine if any quals match foreign keys defined the
+ * two relations (fkrel referencing foreignrel). When multiple foreign keys
+ * match, we do choose the one with the most keys as the best one. We might
+ * also choose the one matching the most quals, however we assume the quals
+ * may be duplicated.
+ *
+ * We also track which joinquals match the current foreign key, so that we can
+ * easily skip then when computing the selectivity.
+ *
+ * When no matching foreign key is found we return 0, otherwise we return the
+ * number of keys in the foreign key.
+ *
+ * Foreign keys matched only partially ( are currently ignored.
+ */
+static int
+find_best_foreign_key_quals(PlannerInfo *root, RelOptInfo *fkrel,
+							RelOptInfo *foreignrel, List *joinquals,
+							Bitmapset **joinqualsbitmap)
+{
+	Bitmapset	   *qualbestmatch;
+	ListCell	   *lc;
+	int				bestmatchnkeys;
+
+	/* fast path out when there's no foreign keys on fkrel */
+	if (fkrel->fkeylist == NIL)
+	{
+		*joinqualsbitmap = NULL;
+		return 0;
+	}
+
+	qualbestmatch = NULL;
+	bestmatchnkeys = 0;
+
+	/* now check the matches for each foreign key defined on the fkrel */
+	foreach(lc, fkrel->fkeylist)
+	{
+		ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+		Bitmapset *qualsmatched;
+
+		/*
+		 * We make no attempt in checking that this foreign key actually
+		 * references 'foreignrel', the reasoning here is that we may be able
+		 * to match the foreign key to an eclass member Var of a RestrictInfo
+		 * that's in qualslist, this Var may belong to some other relation.
+		 */
+		qualsmatched = quals_match_foreign_key(root, fkinfo, fkrel, foreignrel,
+											   joinquals);
+
+		/* Did we get a match? And is that match better than a previous one? */
+		if (qualsmatched != NULL && fkinfo->nkeys > bestmatchnkeys)
+		{
+			/* save the new best match */
+			bms_free(qualbestmatch);
+			qualbestmatch = qualsmatched;
+			bestmatchnkeys = fkinfo->nkeys;
+		}
+	}
+
+	*joinqualsbitmap = qualbestmatch;
+	return bestmatchnkeys;
+}
+
+/*
+ * 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().
+ */
+static Selectivity
+clauselist_join_selectivity(PlannerInfo *root, List *joinquals,
+							JoinType jointype, SpecialJoinInfo *sjinfo)
+{
+	int				outerid;
+	int				innerid;
+	Selectivity		sel = 1.0;
+	Bitmapset	   *foundfkquals = NULL;
+
+	innerid = -1;
+	while ((innerid = bms_next_member(sjinfo->min_righthand, innerid)) >= 0)
+	{
+		RelOptInfo *innerrel = find_base_rel(root, innerid);
+
+		outerid = -1;
+		while ((outerid = bms_next_member(sjinfo->min_lefthand, outerid)) >= 0)
+		{
+			RelOptInfo	   *outerrel = find_base_rel(root, outerid);
+			Bitmapset	   *outer2inner;
+			Bitmapset	   *inner2outer;
+			int				innermatches;
+			int				outermatches;
+
+			/*
+			 * check which quals are matched by a foreign key referencing the
+			 * innerrel.
+			 */
+			outermatches = find_best_foreign_key_quals(root, outerrel,
+											innerrel, joinquals, &outer2inner);
+
+			/* do the same, but with relations swapped */
+			innermatches = find_best_foreign_key_quals(root, innerrel,
+											outerrel, joinquals, &inner2outer);
+
+			/*
+			 * did we find any matches at all? If so we need to see which one is
+			 * the best/longest match
+			 */
+			if (outermatches != 0 || innermatches != 0)
+			{
+				double	referenced_tuples;
+				bool overlap;
+
+				/* either could be zero, but not both. */
+				if (outermatches < innermatches)
+				{
+					overlap = bms_overlap(foundfkquals, inner2outer);
+
+					foundfkquals = bms_add_members(foundfkquals, inner2outer);
+					referenced_tuples = Max(outerrel->tuples, 1.0);
+				}
+				else
+				{
+					overlap = bms_overlap(foundfkquals, outer2inner);
+
+					foundfkquals = bms_add_members(foundfkquals, outer2inner);
+					referenced_tuples = Max(innerrel->tuples, 1.0);
+				}
+
+				/*
+				 * XXX should we ignore these overlapping matches?
+				 * Or perhaps take the Max() or Min()?
+				 */
+				if (overlap)
+				{
+					if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+						sel = Min(sel,Min(1.0 / (outerrel->tuples / Max(innerrel->tuples, 1.0)), 1.0));
+					else
+						sel = Min(sel, 1.0 / referenced_tuples);
+				}
+				else
+				{
+					if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+						sel *= Min(1.0 / (outerrel->tuples / Max(innerrel->tuples, 1.0)), 1.0);
+					else
+						sel *= 1.0 / referenced_tuples;
+				}
+			}
+		}
+	}
+
+	/*
+	 * If any non matched quals exist then we build a list of the non-matches
+	 * and use clauselist_selectivity() to estimate the selectivity of these.
+	 */
+	if (bms_num_members(foundfkquals) < list_length(joinquals))
+	{
+		ListCell *lc;
+		int lstidx = 0;
+		List *nonfkeyclauses = NIL;
+
+		foreach (lc, joinquals)
+		{
+			if (!bms_is_member(lstidx, foundfkquals))
+				nonfkeyclauses = lappend(nonfkeyclauses, lfirst(lc));
+			lstidx++;
+		}
+		sel *= clauselist_selectivity(root, nonfkeyclauses, 0, jointype, sjinfo);
+	}
+
+	return sel;
+}
+
+/*
  * calc_joinrel_size_estimate
  *		Workhorse for set_joinrel_size_estimates and
  *		get_parameterized_joinrel_size.
@@ -3933,11 +4274,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 +4291,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/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 7ad4f02..d9a3c1f 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
-- 
2.5.5

From e7bee70ee85a8413f494719bb5f1acf8d24007c6 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@pgaddict.com>
Date: Thu, 7 Apr 2016 00:58:03 +0200
Subject: [PATCH 2/2] use fkeys in join estimation

---
 src/backend/optimizer/path/costsize.c | 364 +++++++++++++++++++++++++++++++++-
 src/backend/utils/misc/guc.c          |   9 +
 src/include/optimizer/cost.h          |   1 +
 src/include/optimizer/paths.h         |   2 +
 4 files changed, 366 insertions(+), 10 deletions(-)

diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 70a4c27..f1cd11b 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -126,6 +126,7 @@ bool		enable_nestloop = true;
 bool		enable_material = true;
 bool		enable_mergejoin = true;
 bool		enable_hashjoin = true;
+bool		enable_fkey_estimates = true;
 
 typedef struct
 {
@@ -3888,6 +3889,350 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
 }
 
 /*
+ * quals_match_foreign_key
+ *		Determines if the foreign key is matched by joinquals.
+ *
+ * Checks that there are conditions on all columns of the foreign key, matching
+ * the operator used by the foreign key etc. If such complete match is found,
+ * the function returns bitmap identifying the matching quals (0-based).
+ *
+ * Otherwise (no match at all or incomplete match), NULL is returned.
+ */
+static Bitmapset *
+quals_match_foreign_key(PlannerInfo *root, ForeignKeyOptInfo *fkinfo,
+						RelOptInfo *fkrel, RelOptInfo *foreignrel,
+						List *joinquals)
+{
+	int i;
+	int nkeys = fkinfo->nkeys;
+	Bitmapset *qualmatches = NULL;
+	Bitmapset *fkmatches = NULL;
+
+	/*
+	 * Loop over each column of the foreign key and build a bitmap index
+	 * of each joinqual which matches. Note that we don't stop when we find
+	 * the first match, as the expression could be duplicated in the
+	 * joinquals, and we want to generate a bitmap index which has bits set for
+	 * every matching join qual.
+	 */
+	for (i = 0; i < nkeys; i++)
+	{
+		ListCell *lc;
+		int quallstidx = -1;
+
+		foreach(lc, joinquals)
+		{
+			RestrictInfo   *rinfo;
+			OpExpr		   *clause;
+			Var			   *leftvar;
+			Var			   *rightvar;
+
+			quallstidx++;
+
+			/*
+			 * Technically we don't need to, but here we skip this qual if
+			 * we've matched it to part of the foreign key already. This
+			 * should prove to be a useful optimization when the quals appear
+			 * in the same order as the foreign key's keys. We need only bother
+			 * doing this when the foreign key is made up of more than 1 set
+			 * of columns, and we're not testing the first column.
+			 */
+			if (i > 0 && bms_is_member(quallstidx, qualmatches))
+				continue;
+
+			/*
+			 * Here since 'usefulquals' only contains bitmap indexes for quals
+			 * of type "var op var" we can safely skip checking this.
+			 */
+			rinfo = (RestrictInfo *) lfirst(lc);
+			clause = (OpExpr *) rinfo->clause;
+
+			/*
+			 * If the operator does not match then there's little point in
+			 * checking the operands
+			 */
+			if (clause->opno != fkinfo->conpfeqop[i])
+				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;
+
+			/*
+			 * For RestrictInfos built from an eclass we must consider each
+			 * member of the eclass as rinfo's operands may not belong to the
+			 * foreign key. For efficient tracking of which Vars we've found,
+			 * since we're only tracking 2 Vars, we use a bitmask. We can
+			 * safely finish searching when both of the least significant bits
+			 * are set.
+			 */
+			if (rinfo->parent_ec)
+			{
+				EquivalenceClass   *ec = rinfo->parent_ec;
+				ListCell		   *lc2;
+				int					foundvarmask = 0;
+
+				foreach(lc2, ec->ec_members)
+				{
+					EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+					Var *var = (Var *) em->em_expr;
+
+					if (!IsA(var, Var))
+						continue;
+
+					if (foreignrel->relid == var->varno &&
+						fkinfo->confkeys[i] == var->varattno)
+						foundvarmask |= 1;
+
+					else if (fkrel->relid == var->varno &&
+						fkinfo->conkeys[i] == var->varattno)
+						foundvarmask |= 2;
+
+					/*
+					 * Check if we've found both matches. If found we add
+					 * this qual to the matched list and mark this key as
+					 * matched too.
+					 */
+					if (foundvarmask == 3)
+					{
+						qualmatches = bms_add_member(qualmatches, quallstidx);
+						fkmatches = bms_add_member(fkmatches, i);
+						break;
+					}
+				}
+			}
+			else
+			{
+				/*
+				 * In this non eclass RestrictInfo case we'll check if the left
+				 * and right Vars match to this part of the foreign key.
+				 * Remember that this could be written with the Vars in either
+				 * order, so we test both permutations of the expression.
+				 */
+				if ((foreignrel->relid == leftvar->varno) &&
+					(fkrel->relid == rightvar->varno) &&
+					(fkinfo->confkeys[i] == leftvar->varattno) &&
+					(fkinfo->conkeys[i] == rightvar->varattno))
+				{
+					qualmatches = bms_add_member(qualmatches, quallstidx);
+					fkmatches = bms_add_member(fkmatches, i);
+				}
+				else if ((foreignrel->relid == rightvar->varno) &&
+						 (fkrel->relid == leftvar->varno) &&
+						 (fkinfo->confkeys[i] == rightvar->varattno) &&
+						 (fkinfo->conkeys[i] == leftvar->varattno))
+				{
+					qualmatches = bms_add_member(qualmatches, quallstidx);
+					fkmatches = bms_add_member(fkmatches, i);
+				}
+			}
+		}
+	}
+
+	/* can't find more matches than columns in the foreign key */
+	Assert(bms_num_members(fkmatches) <= nkeys);
+
+	/* Only return the matches if we the foreign key is matched fully. */
+	if (bms_num_members(fkmatches) == nkeys)
+	{
+		bms_free(fkmatches);
+		return qualmatches;
+	}
+
+	bms_free(fkmatches);
+	bms_free(qualmatches);
+
+	return NULL;
+}
+
+/*
+ * find_best_foreign_key_quals
+ * 		Finds the foreign key best matching the joinquals.
+ *
+ * Analyzes joinquals to determine if any quals match foreign keys defined the
+ * two relations (fkrel referencing foreignrel). When multiple foreign keys
+ * match, we do choose the one with the most keys as the best one. We might
+ * also choose the one matching the most quals, however we assume the quals
+ * may be duplicated.
+ *
+ * We also track which joinquals match the current foreign key, so that we can
+ * easily skip then when computing the selectivity.
+ *
+ * When no matching foreign key is found we return 0, otherwise we return the
+ * number of keys in the foreign key.
+ *
+ * Foreign keys matched only partially ( are currently ignored.
+ */
+static int
+find_best_foreign_key_quals(PlannerInfo *root, RelOptInfo *fkrel,
+							RelOptInfo *foreignrel, List *joinquals,
+							Bitmapset **joinqualsbitmap)
+{
+	Bitmapset	   *qualbestmatch;
+	ListCell	   *lc;
+	int				bestmatchnkeys;
+
+	/*
+	 * fast path out when there's no foreign keys on fkrel, or when use of
+	 * foreign keys for estimation is disabled by GUC
+	 */
+	if ((fkrel->fkeylist == NIL) || (!enable_fkey_estimates))
+	{
+		*joinqualsbitmap = NULL;
+		return 0;
+	}
+
+	qualbestmatch = NULL;
+	bestmatchnkeys = 0;
+
+	/* now check the matches for each foreign key defined on the fkrel */
+	foreach(lc, fkrel->fkeylist)
+	{
+		ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+		Bitmapset *qualsmatched;
+
+		/*
+		 * We make no attempt in checking that this foreign key actually
+		 * references 'foreignrel', the reasoning here is that we may be able
+		 * to match the foreign key to an eclass member Var of a RestrictInfo
+		 * that's in qualslist, this Var may belong to some other relation.
+		 */
+		qualsmatched = quals_match_foreign_key(root, fkinfo, fkrel, foreignrel,
+											   joinquals);
+
+		/* Did we get a match? And is that match better than a previous one? */
+		if (qualsmatched != NULL && fkinfo->nkeys > bestmatchnkeys)
+		{
+			/* save the new best match */
+			bms_free(qualbestmatch);
+			qualbestmatch = qualsmatched;
+			bestmatchnkeys = fkinfo->nkeys;
+		}
+	}
+
+	*joinqualsbitmap = qualbestmatch;
+	return bestmatchnkeys;
+}
+
+/*
+ * 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().
+ */
+static Selectivity
+clauselist_join_selectivity(PlannerInfo *root, List *joinquals,
+							JoinType jointype, SpecialJoinInfo *sjinfo)
+{
+	int				outerid;
+	int				innerid;
+	Selectivity		sel = 1.0;
+	Bitmapset	   *foundfkquals = NULL;
+
+	innerid = -1;
+	while ((innerid = bms_next_member(sjinfo->min_righthand, innerid)) >= 0)
+	{
+		RelOptInfo *innerrel = find_base_rel(root, innerid);
+
+		outerid = -1;
+		while ((outerid = bms_next_member(sjinfo->min_lefthand, outerid)) >= 0)
+		{
+			RelOptInfo	   *outerrel = find_base_rel(root, outerid);
+			Bitmapset	   *outer2inner;
+			Bitmapset	   *inner2outer;
+			int				innermatches;
+			int				outermatches;
+
+			/*
+			 * check which quals are matched by a foreign key referencing the
+			 * innerrel.
+			 */
+			outermatches = find_best_foreign_key_quals(root, outerrel,
+											innerrel, joinquals, &outer2inner);
+
+			/* do the same, but with relations swapped */
+			innermatches = find_best_foreign_key_quals(root, innerrel,
+											outerrel, joinquals, &inner2outer);
+
+			/*
+			 * did we find any matches at all? If so we need to see which one is
+			 * the best/longest match
+			 */
+			if (outermatches != 0 || innermatches != 0)
+			{
+				double	referenced_tuples;
+				bool overlap;
+
+				/* either could be zero, but not both. */
+				if (outermatches < innermatches)
+				{
+					overlap = bms_overlap(foundfkquals, inner2outer);
+
+					foundfkquals = bms_add_members(foundfkquals, inner2outer);
+					referenced_tuples = Max(outerrel->tuples, 1.0);
+				}
+				else
+				{
+					overlap = bms_overlap(foundfkquals, outer2inner);
+
+					foundfkquals = bms_add_members(foundfkquals, outer2inner);
+					referenced_tuples = Max(innerrel->tuples, 1.0);
+				}
+
+				/*
+				 * XXX should we ignore these overlapping matches?
+				 * Or perhaps take the Max() or Min()?
+				 */
+				if (overlap)
+				{
+					if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+						sel = Min(sel,Min(1.0 / (outerrel->tuples / Max(innerrel->tuples, 1.0)), 1.0));
+					else
+						sel = Min(sel, 1.0 / referenced_tuples);
+				}
+				else
+				{
+					if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
+						sel *= Min(1.0 / (outerrel->tuples / Max(innerrel->tuples, 1.0)), 1.0);
+					else
+						sel *= 1.0 / referenced_tuples;
+				}
+			}
+		}
+	}
+
+	/*
+	 * If any non matched quals exist then we build a list of the non-matches
+	 * and use clauselist_selectivity() to estimate the selectivity of these.
+	 */
+	if (bms_num_members(foundfkquals) < list_length(joinquals))
+	{
+		ListCell *lc;
+		int lstidx = 0;
+		List *nonfkeyclauses = NIL;
+
+		foreach (lc, joinquals)
+		{
+			if (!bms_is_member(lstidx, foundfkquals))
+				nonfkeyclauses = lappend(nonfkeyclauses, lfirst(lc));
+			lstidx++;
+		}
+		sel *= clauselist_selectivity(root, nonfkeyclauses, 0, jointype, sjinfo);
+	}
+
+	return sel;
+}
+
+/*
  * calc_joinrel_size_estimate
  *		Workhorse for set_joinrel_size_estimates and
  *		get_parameterized_joinrel_size.
@@ -3933,11 +4278,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 +4295,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/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index b7afe6b..a070500 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -877,6 +877,15 @@ static struct config_bool ConfigureNamesBool[] =
 		true,
 		NULL, NULL, NULL
 	},
+	{
+		{"enable_fkey_estimates", PGC_USERSET, QUERY_TUNING_METHOD,
+			gettext_noop("Enables use of foreign keys for estimating joins."),
+			NULL
+		},
+		&enable_fkey_estimates,
+		true,
+		NULL, NULL, NULL
+	},
 
 	{
 		{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index d4adca6..58ac163 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -66,6 +66,7 @@ extern bool enable_nestloop;
 extern bool enable_material;
 extern bool enable_mergejoin;
 extern bool enable_hashjoin;
+extern bool enable_fkey_estimates;
 extern int	constraint_exclusion;
 
 extern double clamp_row_est(double nrows);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 7ad4f02..d9a3c1f 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
-- 
2.5.5