Use parameterized paths to generate inner indexscans more flexibly.

This patch fixes the planner so that it can generate nestloop-with-
inner-indexscan plans even with one or more levels of joining between
the indexscan and the nestloop join that is supplying the parameter.
The executor was fixed to handle such cases some time ago, but the
planner was not ready.  This should improve our plans in many situations
where join ordering restrictions formerly forced complete table scans.

There is probably a fair amount of tuning work yet to be done, because
of various heuristics that have been added to limit the number of
parameterized paths considered.  However, we are not going to find out
what needs to be adjusted until the code gets some real-world use, so
it's time to get it in there where it can be tested easily.

Note API change for index AM amcostestimate functions.  I'm not aware of
any non-core index AMs, but if there are any, they will need minor
adjustments.

1 files changed, 650 insertions, 247 deletions

diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 0ca161a31dc..d29b454f724 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -29,6 +29,15 @@
 #include "utils/selfuncs.h"
 
 
+typedef enum
+{
+	COSTS_EQUAL,				/* path costs are fuzzily equal */
+	COSTS_BETTER1,				/* first path is cheaper than second */
+	COSTS_BETTER2,				/* second path is cheaper than first */
+	COSTS_DIFFERENT				/* neither path dominates the other on cost */
+} PathCostComparison;
+
+static void add_parameterized_path(RelOptInfo *parent_rel, Path *new_path);
 static List *translate_sub_tlist(List *tlist, int relid);
 static bool query_is_distinct_for(Query *query, List *colnos, List *opids);
 static Oid	distinct_col_search(int colno, List *colnos, List *opids);
@@ -81,58 +90,6 @@ compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
 }
 
 /*
- * compare_fuzzy_path_costs
- *	  Return -1, 0, or +1 according as path1 is cheaper, the same cost,
- *	  or more expensive than path2 for the specified criterion.
- *
- * This differs from compare_path_costs in that we consider the costs the
- * same if they agree to within a "fuzz factor".  This is used by add_path
- * to avoid keeping both of a pair of paths that really have insignificantly
- * different cost.
- */
-static int
-compare_fuzzy_path_costs(Path *path1, Path *path2, CostSelector criterion)
-{
-	/*
-	 * We use a fuzz factor of 1% of the smaller cost.
-	 *
-	 * XXX does this percentage need to be user-configurable?
-	 */
-	if (criterion == STARTUP_COST)
-	{
-		if (path1->startup_cost > path2->startup_cost * 1.01)
-			return +1;
-		if (path2->startup_cost > path1->startup_cost * 1.01)
-			return -1;
-
-		/*
-		 * If paths have the same startup cost (not at all unlikely), order
-		 * them by total cost.
-		 */
-		if (path1->total_cost > path2->total_cost * 1.01)
-			return +1;
-		if (path2->total_cost > path1->total_cost * 1.01)
-			return -1;
-	}
-	else
-	{
-		if (path1->total_cost > path2->total_cost * 1.01)
-			return +1;
-		if (path2->total_cost > path1->total_cost * 1.01)
-			return -1;
-
-		/*
-		 * If paths have the same total cost, order them by startup cost.
-		 */
-		if (path1->startup_cost > path2->startup_cost * 1.01)
-			return +1;
-		if (path2->startup_cost > path1->startup_cost * 1.01)
-			return -1;
-	}
-	return 0;
-}
-
-/*
  * compare_path_fractional_costs
  *	  Return -1, 0, or +1 according as path1 is cheaper, the same cost,
  *	  or more expensive than path2 for fetching the specified fraction
@@ -162,38 +119,119 @@ compare_fractional_path_costs(Path *path1, Path *path2,
 }
 
 /*
+ * compare_path_costs_fuzzily
+ *	  Compare the costs of two paths to see if either can be said to
+ *	  dominate the other.
+ *
+ * We use fuzzy comparisons so that add_path() can avoid keeping both of
+ * a pair of paths that really have insignificantly different cost.
+ * The fuzz factor is 1% of the smaller cost.  (XXX does this percentage
+ * need to be user-configurable?)
+ *
+ * The two paths are said to have "equal" costs if both startup and total
+ * costs are fuzzily the same.  Path1 is said to be better than path2 if
+ * it has fuzzily better startup cost and fuzzily no worse total cost,
+ * or if it has fuzzily better total cost and fuzzily no worse startup cost.
+ * Path2 is better than path1 if the reverse holds.  Finally, if one path
+ * is fuzzily better than the other on startup cost and fuzzily worse on
+ * total cost, we just say that their costs are "different", since neither
+ * dominates the other across the whole performance spectrum.
+ */
+static PathCostComparison
+compare_path_costs_fuzzily(Path *path1, Path *path2)
+{
+	/*
+	 * Check total cost first since it's more likely to be different; many
+	 * paths have zero startup cost.
+	 */
+	if (path1->total_cost > path2->total_cost * 1.01)
+	{
+		/* path1 fuzzily worse on total cost */
+		if (path2->startup_cost > path1->startup_cost * 1.01)
+		{
+			/* ... but path2 fuzzily worse on startup, so DIFFERENT */
+			return COSTS_DIFFERENT;
+		}
+		/* else path2 dominates */
+		return COSTS_BETTER2;
+	}
+	if (path2->total_cost > path1->total_cost * 1.01)
+	{
+		/* path2 fuzzily worse on total cost */
+		if (path1->startup_cost > path2->startup_cost * 1.01)
+		{
+			/* ... but path1 fuzzily worse on startup, so DIFFERENT */
+			return COSTS_DIFFERENT;
+		}
+		/* else path1 dominates */
+		return COSTS_BETTER1;
+	}
+	/* fuzzily the same on total cost */
+	if (path1->startup_cost > path2->startup_cost * 1.01)
+	{
+		/* ... but path1 fuzzily worse on startup, so path2 wins */
+		return COSTS_BETTER2;
+	}
+	if (path2->startup_cost > path1->startup_cost * 1.01)
+	{
+		/* ... but path2 fuzzily worse on startup, so path1 wins */
+		return COSTS_BETTER1;
+	}
+	/* fuzzily the same on both costs */
+	return COSTS_EQUAL;
+}
+
+/*
  * set_cheapest
  *	  Find the minimum-cost paths from among a relation's paths,
  *	  and save them in the rel's cheapest-path fields.
  *
+ * Only unparameterized paths are considered candidates for cheapest_startup
+ * and cheapest_total.  The cheapest_parameterized_paths list collects paths
+ * that are cheapest-total for their parameterization (i.e., there is no
+ * cheaper path with the same or weaker parameterization).  This list always
+ * includes the unparameterized cheapest-total path, too.
+ *
  * This is normally called only after we've finished constructing the path
  * list for the rel node.
- *
- * If we find two paths of identical costs, try to keep the better-sorted one.
- * The paths might have unrelated sort orderings, in which case we can only
- * guess which might be better to keep, but if one is superior then we
- * definitely should keep it.
  */
 void
 set_cheapest(RelOptInfo *parent_rel)
 {
-	List	   *pathlist = parent_rel->pathlist;
-	ListCell   *p;
 	Path	   *cheapest_startup_path;
 	Path	   *cheapest_total_path;
+	bool		have_parameterized_paths;
+	ListCell   *p;
 
 	Assert(IsA(parent_rel, RelOptInfo));
 
-	if (pathlist == NIL)
-		elog(ERROR, "could not devise a query plan for the given query");
-
-	cheapest_startup_path = cheapest_total_path = (Path *) linitial(pathlist);
+	cheapest_startup_path = cheapest_total_path = NULL;
+	have_parameterized_paths = false;
 
-	for_each_cell(p, lnext(list_head(pathlist)))
+	foreach(p, parent_rel->pathlist)
 	{
 		Path	   *path = (Path *) lfirst(p);
 		int			cmp;
 
+		/* We only consider unparameterized paths in this step */
+		if (path->required_outer)
+		{
+			have_parameterized_paths = true;
+			continue;
+		}
+
+		if (cheapest_total_path == NULL)
+		{
+			cheapest_startup_path = cheapest_total_path = path;
+			continue;
+		}
+
+		/*
+		 * If we find two paths of identical costs, try to keep the
+		 * better-sorted one.  The paths might have unrelated sort orderings,
+		 * in which case we can only guess which might be better to keep, but
+		 * if one is superior then we definitely should keep that one.
+		 */
 		cmp = compare_path_costs(cheapest_startup_path, path, STARTUP_COST);
 		if (cmp > 0 ||
 			(cmp == 0 &&
@@ -209,9 +247,27 @@ set_cheapest(RelOptInfo *parent_rel)
 			cheapest_total_path = path;
 	}
 
+	if (cheapest_total_path == NULL)
+		elog(ERROR, "could not devise a query plan for the given query");
+
 	parent_rel->cheapest_startup_path = cheapest_startup_path;
 	parent_rel->cheapest_total_path = cheapest_total_path;
 	parent_rel->cheapest_unique_path = NULL;	/* computed only if needed */
+
+	/* Seed the parameterized-paths list with the cheapest total */
+	parent_rel->cheapest_parameterized_paths = list_make1(cheapest_total_path);
+
+	/* And, if there are any parameterized paths, add them in one at a time */
+	if (have_parameterized_paths)
+	{
+		foreach(p, parent_rel->pathlist)
+		{
+			Path	   *path = (Path *) lfirst(p);
+
+			if (path->required_outer)
+				add_parameterized_path(parent_rel, path);
+		}
+	}
 }
 
 /*
@@ -219,17 +275,25 @@ set_cheapest(RelOptInfo *parent_rel)
  *	  Consider a potential implementation path for the specified parent rel,
  *	  and add it to the rel's pathlist if it is worthy of consideration.
  *	  A path is worthy if it has either a better sort order (better pathkeys)
- *	  or cheaper cost (on either dimension) than any of the existing old paths.
+ *	  or cheaper cost (on either dimension) than any of the existing old paths
+ *	  that have the same or superset required_outer rels.
  *
  *	  We also remove from the rel's pathlist any old paths that are dominated
- *	  by new_path --- that is, new_path is both cheaper and at least as well
- *	  ordered.
+ *	  by new_path --- that is, new_path is cheaper, at least as well ordered,
+ *	  and requires no outer rels not required by old path.
+ *
+ *	  There is one policy decision embedded in this function, along with its
+ *	  sibling add_path_precheck: we treat all parameterized paths as having
+ *	  NIL pathkeys, so that they compete only on cost.  This is to reduce
+ *	  the number of parameterized paths that are kept.  See discussion in
+ *	  src/backend/optimizer/README.
  *
- *	  The pathlist is kept sorted by TOTAL_COST metric, with cheaper paths
- *	  at the front.  No code depends on that for correctness; it's simply
- *	  a speed hack within this routine.  Doing it that way makes it more
- *	  likely that we will reject an inferior path after a few comparisons,
- *	  rather than many comparisons.
+ *	  The pathlist is kept sorted by total_cost, with cheaper paths
+ *	  at the front.  Within this routine, that's simply a speed hack:
+ *	  doing it that way makes it more likely that we will reject an inferior
+ *	  path after a few comparisons, rather than many comparisons.
+ *	  However, add_path_precheck relies on this ordering to exit early
+ *	  when possible.
  *
  *	  NOTE: discarded Path objects are immediately pfree'd to reduce planner
  *	  memory consumption.  We dare not try to free the substructure of a Path,
@@ -250,6 +314,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 {
 	bool		accept_new = true;		/* unless we find a superior old path */
 	ListCell   *insert_after = NULL;	/* where to insert new item */
+	List	   *new_path_pathkeys;
 	ListCell   *p1;
 	ListCell   *p1_prev;
 	ListCell   *p1_next;
@@ -260,6 +325,9 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 	 */
 	CHECK_FOR_INTERRUPTS();
 
+	/* Pretend parameterized paths have no pathkeys, per comment above */
+	new_path_pathkeys = new_path->required_outer ? NIL : new_path->pathkeys;
+
 	/*
 	 * Loop to check proposed new path against old paths.  Note it is possible
 	 * for more than one old path to be tossed out because new_path dominates
@@ -273,62 +341,99 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 	{
 		Path	   *old_path = (Path *) lfirst(p1);
 		bool		remove_old = false; /* unless new proves superior */
-		int			costcmp;
+		PathCostComparison costcmp;
+		PathKeysComparison keyscmp;
+		BMS_Comparison outercmp;
 
 		p1_next = lnext(p1);
 
-		/*
-		 * As of Postgres 8.0, we use fuzzy cost comparison to avoid wasting
-		 * cycles keeping paths that are really not significantly different in
-		 * cost.
-		 */
-		costcmp = compare_fuzzy_path_costs(new_path, old_path, TOTAL_COST);
+		costcmp = compare_path_costs_fuzzily(new_path, old_path);
 
 		/*
 		 * If the two paths compare differently for startup and total cost,
-		 * then we want to keep both, and we can skip the (much slower)
-		 * comparison of pathkeys.	If they compare the same, proceed with the
-		 * pathkeys comparison.  Note: this test relies on the fact that
-		 * compare_fuzzy_path_costs will only return 0 if both costs are
-		 * effectively equal (and, therefore, there's no need to call it twice
-		 * in that case).
+		 * then we want to keep both, and we can skip comparing pathkeys and
+		 * required_outer rels.  If they compare the same, proceed with the
+		 * other comparisons.  (We make the tests in this order because the
+		 * cost comparison is most likely to turn out "different", and the
+		 * pathkeys comparison next most likely.)
 		 */
-		if (costcmp == 0 ||
-			costcmp == compare_fuzzy_path_costs(new_path, old_path,
-												STARTUP_COST))
+		if (costcmp != COSTS_DIFFERENT)
 		{
-			switch (compare_pathkeys(new_path->pathkeys, old_path->pathkeys))
+			/* Similarly check to see if either dominates on pathkeys */
+			List	   *old_path_pathkeys;
+
+			old_path_pathkeys = old_path->required_outer ? NIL : old_path->pathkeys;
+			keyscmp = compare_pathkeys(new_path_pathkeys,
+									   old_path_pathkeys);
+			if (keyscmp != PATHKEYS_DIFFERENT)
 			{
-				case PATHKEYS_EQUAL:
-					if (costcmp < 0)
-						remove_old = true;		/* new dominates old */
-					else if (costcmp > 0)
-						accept_new = false;		/* old dominates new */
-					else
-					{
+				switch (costcmp)
+				{
+					case COSTS_EQUAL:
+						outercmp = bms_subset_compare(new_path->required_outer,
+													  old_path->required_outer);
+						if (keyscmp == PATHKEYS_BETTER1)
+						{
+							if (outercmp == BMS_EQUAL ||
+								outercmp == BMS_SUBSET1)
+								remove_old = true;	/* new dominates old */
+						}
+						else if (keyscmp == PATHKEYS_BETTER2)
+						{
+							if (outercmp == BMS_EQUAL ||
+								outercmp == BMS_SUBSET2)
+								accept_new = false;	/* old dominates new */
+						}
+						else	/* keyscmp == PATHKEYS_EQUAL */
+						{
+							if (outercmp == BMS_EQUAL)
+							{
+								/*
+								 * Same pathkeys and outer rels, and fuzzily
+								 * the same cost, so keep just one --- but
+								 * we'll do an exact cost comparison to decide
+								 * which.
+								 */
+								if (compare_path_costs(new_path, old_path,
+													   TOTAL_COST) < 0)
+									remove_old = true;	/* new dominates old */
+								else
+									accept_new = false; /* old equals or dominates new */
+							}
+							else if (outercmp == BMS_SUBSET1)
+								remove_old = true;	/* new dominates old */
+							else if (outercmp == BMS_SUBSET2)
+								accept_new = false;	/* old dominates new */
+							/* else different parameterizations, keep both */
+						}
+						break;
+					case COSTS_BETTER1:
+						if (keyscmp != PATHKEYS_BETTER2)
+						{
+							outercmp = bms_subset_compare(new_path->required_outer,
+														  old_path->required_outer);
+							if (outercmp == BMS_EQUAL ||
+								outercmp == BMS_SUBSET1)
+								remove_old = true;	/* new dominates old */
+						}
+						break;
+					case COSTS_BETTER2:
+						if (keyscmp != PATHKEYS_BETTER1)
+						{
+							outercmp = bms_subset_compare(new_path->required_outer,
+														  old_path->required_outer);
+							if (outercmp == BMS_EQUAL ||
+								outercmp == BMS_SUBSET2)
+								accept_new = false;	/* old dominates new */
+						}
+						break;
+					case COSTS_DIFFERENT:
 						/*
-						 * Same pathkeys, and fuzzily the same cost, so keep
-						 * just one --- but we'll do an exact cost comparison
-						 * to decide which.
+						 * can't get here, but keep this case to keep compiler
+						 * quiet
 						 */
-						if (compare_path_costs(new_path, old_path,
-											   TOTAL_COST) < 0)
-							remove_old = true;	/* new dominates old */
-						else
-							accept_new = false; /* old equals or dominates new */
-					}
-					break;
-				case PATHKEYS_BETTER1:
-					if (costcmp <= 0)
-						remove_old = true;		/* new dominates old */
-					break;
-				case PATHKEYS_BETTER2:
-					if (costcmp >= 0)
-						accept_new = false;		/* old dominates new */
-					break;
-				case PATHKEYS_DIFFERENT:
-					/* keep both paths, since they have different ordering */
-					break;
+						break;
+				}
 			}
 		}
 
@@ -350,7 +455,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 		else
 		{
 			/* new belongs after this old path if it has cost >= old's */
-			if (costcmp >= 0)
+			if (new_path->total_cost >= old_path->total_cost)
 				insert_after = p1;
 			/* p1_prev advances */
 			p1_prev = p1;
@@ -381,6 +486,185 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 	}
 }
 
+/*
+ * add_path_precheck
+ *	  Check whether a proposed new path could possibly get accepted.
+ *	  We assume we know the path's pathkeys and parameterization accurately,
+ *	  and have lower bounds for its costs.
+ *
+ * At the time this is called, we haven't actually built a Path structure,
+ * so the required information has to be passed piecemeal.
+ */
+bool
+add_path_precheck(RelOptInfo *parent_rel,
+				  Cost startup_cost, Cost total_cost,
+				  List *pathkeys, Relids required_outer)
+{
+	List	   *new_path_pathkeys;
+	ListCell   *p1;
+
+	/* Pretend parameterized paths have no pathkeys, per comment above */
+	new_path_pathkeys = required_outer ? NIL : pathkeys;
+
+	foreach(p1, parent_rel->pathlist)
+	{
+		Path	   *old_path = (Path *) lfirst(p1);
+		PathKeysComparison keyscmp;
+		BMS_Comparison outercmp;
+
+		/*
+		 * We are looking for an old_path that dominates the new path across
+		 * all four metrics.  If we find one, we can reject the new path.
+		 *
+		 * For speed, we make exact rather than fuzzy cost comparisons.
+		 * If an old path dominates the new path exactly on both costs, it
+		 * will surely do so fuzzily.
+		 */
+		if (total_cost >= old_path->total_cost)
+		{
+			if (startup_cost >= old_path->startup_cost)
+			{
+				List	   *old_path_pathkeys;
+
+				old_path_pathkeys = old_path->required_outer ? NIL : old_path->pathkeys;
+				keyscmp = compare_pathkeys(new_path_pathkeys,
+										   old_path_pathkeys);
+				if (keyscmp == PATHKEYS_EQUAL ||
+					keyscmp == PATHKEYS_BETTER2)
+				{
+					outercmp = bms_subset_compare(required_outer,
+												  old_path->required_outer);
+					if (outercmp == BMS_EQUAL ||
+						outercmp == BMS_SUBSET2)
+						return false;
+				}
+			}
+		}
+		else
+		{
+			/*
+			 * Since the pathlist is sorted by total_cost, we can stop
+			 * looking once we reach a path with a total_cost larger
+			 * than the new path's.
+			 */
+			break;
+		}
+	}
+
+	return true;
+}
+
+/*
+ * add_parameterized_path
+ *	  Consider a parameterized implementation path for the specified rel,
+ *	  and add it to the rel's cheapest_parameterized_paths list if it
+ *	  belongs there, removing any old entries that it dominates.
+ *
+ *	  This is essentially a cut-down form of add_path(): we do not care about
+ *	  startup cost or sort ordering, only total cost and parameterization.
+ *	  Also, we should not recycle rejected paths, since they will still be
+ *	  present in the rel's pathlist.
+ *
+ * 'parent_rel' is the relation entry to which the path corresponds.
+ * 'new_path' is a parameterized path for parent_rel.
+ *
+ * Returns nothing, but modifies parent_rel->cheapest_parameterized_paths.
+ */
+static void
+add_parameterized_path(RelOptInfo *parent_rel, Path *new_path)
+{
+	bool		accept_new = true;		/* unless we find a superior old path */
+	ListCell   *insert_after = NULL;	/* where to insert new item */
+	ListCell   *p1;
+	ListCell   *p1_prev;
+	ListCell   *p1_next;
+
+	/*
+	 * Loop to check proposed new path against old paths.  Note it is possible
+	 * for more than one old path to be tossed out because new_path dominates
+	 * it.
+	 *
+	 * We can't use foreach here because the loop body may delete the current
+	 * list cell.
+	 */
+	p1_prev = NULL;
+	for (p1 = list_head(parent_rel->cheapest_parameterized_paths);
+		 p1 != NULL; p1 = p1_next)
+	{
+		Path	   *old_path = (Path *) lfirst(p1);
+		bool		remove_old = false; /* unless new proves superior */
+		int			costcmp;
+		BMS_Comparison outercmp;
+
+		p1_next = lnext(p1);
+
+		costcmp = compare_path_costs(new_path, old_path, TOTAL_COST);
+		outercmp = bms_subset_compare(new_path->required_outer,
+									  old_path->required_outer);
+		if (outercmp != BMS_DIFFERENT)
+		{
+			if (costcmp < 0)
+			{
+				if (outercmp != BMS_SUBSET2)
+					remove_old = true; /* new dominates old */
+			}
+			else if (costcmp > 0)
+			{
+				if (outercmp != BMS_SUBSET1)
+					accept_new = false;	/* old dominates new */
+			}
+			else if (outercmp == BMS_SUBSET1)
+				remove_old = true; /* new dominates old */
+			else if (outercmp == BMS_SUBSET2)
+				accept_new = false;	/* old dominates new */
+			else
+			{
+				/* Same cost and outer rels, arbitrarily keep the old */
+				accept_new = false; /* old equals or dominates new */
+			}
+		}
+
+		/*
+		 * Remove current element from cheapest_parameterized_paths if
+		 * dominated by new.
+		 */
+		if (remove_old)
+		{
+			parent_rel->cheapest_parameterized_paths =
+				list_delete_cell(parent_rel->cheapest_parameterized_paths,
+								 p1, p1_prev);
+			/* p1_prev does not advance */
+		}
+		else
+		{
+			/* new belongs after this old path if it has cost >= old's */
+			if (costcmp >= 0)
+				insert_after = p1;
+			/* p1_prev advances */
+			p1_prev = p1;
+		}
+
+		/*
+		 * If we found an old path that dominates new_path, we can quit
+		 * scanning the list; we will not add new_path, and we assume
+		 * new_path cannot dominate any other elements of the list.
+		 */
+		if (!accept_new)
+			break;
+	}
+
+	if (accept_new)
+	{
+		/* Accept the new path: insert it at proper place in list */
+		if (insert_after)
+			lappend_cell(parent_rel->cheapest_parameterized_paths,
+						 insert_after, new_path);
+		else
+			parent_rel->cheapest_parameterized_paths =
+				lcons(new_path, parent_rel->cheapest_parameterized_paths);
+	}
+}
+
 
 /*****************************************************************************
  *		PATH NODE CREATION ROUTINES
@@ -399,6 +683,8 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel)
 	pathnode->pathtype = T_SeqScan;
 	pathnode->parent = rel;
 	pathnode->pathkeys = NIL;	/* seqscan has unordered result */
+	pathnode->required_outer = NULL;
+	pathnode->param_clauses = NIL;
 
 	cost_seqscan(pathnode, root, rel);
 
@@ -423,8 +709,9 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel)
  *			for an ordered index, or NoMovementScanDirection for
  *			an unordered index.
  * 'indexonly' is true if an index-only scan is wanted.
- * 'outer_rel' is the outer relation if this is a join inner indexscan path.
- *			(pathkeys and indexscandir are ignored if so.)	NULL if not.
+ * 'required_outer' is the set of outer relids referenced in indexclauses.
+ * 'loop_count' is the number of repetitions of the indexscan to factor into
+ *		estimates of caching behavior.
  *
  * Returns the new path node.
  */
@@ -438,29 +725,35 @@ create_index_path(PlannerInfo *root,
 				  List *pathkeys,
 				  ScanDirection indexscandir,
 				  bool indexonly,
-				  RelOptInfo *outer_rel)
+				  Relids required_outer,
+				  double loop_count)
 {
 	IndexPath  *pathnode = makeNode(IndexPath);
 	RelOptInfo *rel = index->rel;
 	List	   *indexquals,
 			   *indexqualcols;
 
-	/*
-	 * For a join inner scan, there's no point in marking the path with any
-	 * pathkeys, since it will only ever be used as the inner path of a
-	 * nestloop, and so its ordering does not matter.  For the same reason we
-	 * don't really care what order it's scanned in.  (We could expect the
-	 * caller to supply the correct values, but it's easier to force it here.)
-	 */
-	if (outer_rel != NULL)
-	{
-		pathkeys = NIL;
-		indexscandir = NoMovementScanDirection;
-	}
-
 	pathnode->path.pathtype = indexonly ? T_IndexOnlyScan : T_IndexScan;
 	pathnode->path.parent = rel;
 	pathnode->path.pathkeys = pathkeys;
+	pathnode->path.required_outer = required_outer;
+	if (required_outer)
+	{
+		/* Identify index clauses that are join clauses */
+		List	   *jclauses = NIL;
+		ListCell   *lc;
+
+		foreach(lc, indexclauses)
+		{
+			RestrictInfo   *rinfo = (RestrictInfo *) lfirst(lc);
+
+			if (!bms_is_subset(rinfo->clause_relids, rel->relids))
+				jclauses = lappend(jclauses, rinfo);
+		}
+		pathnode->path.param_clauses = jclauses;
+	}
+	else
+		pathnode->path.param_clauses = NIL;
 
 	/* Convert clauses to indexquals the executor can handle */
 	expand_indexqual_conditions(index, indexclauses, indexclausecols,
@@ -473,50 +766,9 @@ create_index_path(PlannerInfo *root,
 	pathnode->indexqualcols = indexqualcols;
 	pathnode->indexorderbys = indexorderbys;
 	pathnode->indexorderbycols = indexorderbycols;
-
-	pathnode->isjoininner = (outer_rel != NULL);
 	pathnode->indexscandir = indexscandir;
 
-	if (outer_rel != NULL)
-	{
-		/*
-		 * We must compute the estimated number of output rows for the
-		 * indexscan.  This is less than rel->rows because of the additional
-		 * selectivity of the join clauses.  Since indexclauses may contain
-		 * both restriction and join clauses, we have to do a set union to get
-		 * the full set of clauses that must be considered to compute the
-		 * correct selectivity.  (Without the union operation, we might have
-		 * some restriction clauses appearing twice, which'd mislead
-		 * clauselist_selectivity into double-counting their selectivity.
-		 * However, since RestrictInfo nodes aren't copied when linking them
-		 * into different lists, it should be sufficient to use pointer
-		 * comparison to remove duplicates.)
-		 *
-		 * Note that we force the clauses to be treated as non-join clauses
-		 * during selectivity estimation.
-		 */
-		List	   *allclauses;
-
-		allclauses = list_union_ptr(rel->baserestrictinfo, indexclauses);
-		pathnode->rows = rel->tuples *
-			clauselist_selectivity(root,
-								   allclauses,
-								   rel->relid,	/* do not use 0! */
-								   JOIN_INNER,
-								   NULL);
-		/* Like costsize.c, force estimate to be at least one row */
-		pathnode->rows = clamp_row_est(pathnode->rows);
-	}
-	else
-	{
-		/*
-		 * The number of rows is the same as the parent rel's estimate, since
-		 * this isn't a join inner indexscan.
-		 */
-		pathnode->rows = rel->rows;
-	}
-
-	cost_index(pathnode, root, outer_rel);
+	cost_index(pathnode, root, loop_count);
 
 	return pathnode;
 }
@@ -526,55 +778,29 @@ create_index_path(PlannerInfo *root,
  *	  Creates a path node for a bitmap scan.
  *
  * 'bitmapqual' is a tree of IndexPath, BitmapAndPath, and BitmapOrPath nodes.
+ * 'loop_count' is the number of repetitions of the indexscan to factor into
+ *		estimates of caching behavior.
  *
- * If this is a join inner indexscan path, 'outer_rel' is the outer relation,
- * and all the component IndexPaths should have been costed accordingly.
+ * loop_count should match the value used when creating the component
+ * IndexPaths.
  */
 BitmapHeapPath *
 create_bitmap_heap_path(PlannerInfo *root,
 						RelOptInfo *rel,
 						Path *bitmapqual,
-						RelOptInfo *outer_rel)
+						double loop_count)
 {
 	BitmapHeapPath *pathnode = makeNode(BitmapHeapPath);
 
 	pathnode->path.pathtype = T_BitmapHeapScan;
 	pathnode->path.parent = rel;
 	pathnode->path.pathkeys = NIL;		/* always unordered */
+	pathnode->path.required_outer = bitmapqual->required_outer;
+	pathnode->path.param_clauses = bitmapqual->param_clauses;
 
 	pathnode->bitmapqual = bitmapqual;
-	pathnode->isjoininner = (outer_rel != NULL);
-
-	if (pathnode->isjoininner)
-	{
-		/*
-		 * We must compute the estimated number of output rows for the
-		 * indexscan.  This is less than rel->rows because of the additional
-		 * selectivity of the join clauses.  We make use of the selectivity
-		 * estimated for the bitmap to do this; this isn't really quite right
-		 * since there may be restriction conditions not included in the
-		 * bitmap ...
-		 */
-		Cost		indexTotalCost;
-		Selectivity indexSelectivity;
-
-		cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity);
-		pathnode->rows = rel->tuples * indexSelectivity;
-		if (pathnode->rows > rel->rows)
-			pathnode->rows = rel->rows;
-		/* Like costsize.c, force estimate to be at least one row */
-		pathnode->rows = clamp_row_est(pathnode->rows);
-	}
-	else
-	{
-		/*
-		 * The number of rows is the same as the parent rel's estimate, since
-		 * this isn't a join inner indexscan.
-		 */
-		pathnode->rows = rel->rows;
-	}
 
-	cost_bitmap_heap_scan(&pathnode->path, root, rel, bitmapqual, outer_rel);
+	cost_bitmap_heap_scan(&pathnode->path, root, rel, bitmapqual, loop_count);
 
 	return pathnode;
 }
@@ -589,13 +815,29 @@ create_bitmap_and_path(PlannerInfo *root,
 					   List *bitmapquals)
 {
 	BitmapAndPath *pathnode = makeNode(BitmapAndPath);
+	ListCell   *lc;
 
 	pathnode->path.pathtype = T_BitmapAnd;
 	pathnode->path.parent = rel;
 	pathnode->path.pathkeys = NIL;		/* always unordered */
+	pathnode->path.required_outer = NULL;
+	pathnode->path.param_clauses = NIL;
 
 	pathnode->bitmapquals = bitmapquals;
 
+	/* required_outer and param_clauses are the union of the inputs' values */
+	foreach(lc, bitmapquals)
+	{
+		Path   *bpath = (Path *) lfirst(lc);
+
+		pathnode->path.required_outer =
+			bms_add_members(pathnode->path.required_outer,
+							bpath->required_outer);
+		pathnode->path.param_clauses =
+			list_concat(pathnode->path.param_clauses,
+						list_copy(bpath->param_clauses));
+	}
+
 	/* this sets bitmapselectivity as well as the regular cost fields: */
 	cost_bitmap_and_node(pathnode, root);
 
@@ -612,13 +854,29 @@ create_bitmap_or_path(PlannerInfo *root,
 					  List *bitmapquals)
 {
 	BitmapOrPath *pathnode = makeNode(BitmapOrPath);
+	ListCell   *lc;
 
 	pathnode->path.pathtype = T_BitmapOr;
 	pathnode->path.parent = rel;
 	pathnode->path.pathkeys = NIL;		/* always unordered */
+	pathnode->path.required_outer = NULL;
+	pathnode->path.param_clauses = NIL;
 
 	pathnode->bitmapquals = bitmapquals;
 
+	/* required_outer and param_clauses are the union of the inputs' values */
+	foreach(lc, bitmapquals)
+	{
+		Path   *bpath = (Path *) lfirst(lc);
+
+		pathnode->path.required_outer =
+			bms_add_members(pathnode->path.required_outer,
+							bpath->required_outer);
+		pathnode->path.param_clauses =
+			list_concat(pathnode->path.param_clauses,
+						list_copy(bpath->param_clauses));
+	}
+
 	/* this sets bitmapselectivity as well as the regular cost fields: */
 	cost_bitmap_or_node(pathnode, root);
 
@@ -637,6 +895,8 @@ create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals)
 	pathnode->path.pathtype = T_TidScan;
 	pathnode->path.parent = rel;
 	pathnode->path.pathkeys = NIL;
+	pathnode->path.required_outer = NULL;
+	pathnode->path.param_clauses = NIL;
 
 	pathnode->tidquals = tidquals;
 
@@ -662,24 +922,46 @@ create_append_path(RelOptInfo *rel, List *subpaths)
 	pathnode->path.parent = rel;
 	pathnode->path.pathkeys = NIL;		/* result is always considered
 										 * unsorted */
+	pathnode->path.required_outer = NULL; /* updated below */
+	pathnode->path.param_clauses = NIL;	/* XXX see below */
 	pathnode->subpaths = subpaths;
 
 	/*
-	 * Compute cost as sum of subplan costs.  We charge nothing extra for the
-	 * Append itself, which perhaps is too optimistic, but since it doesn't do
-	 * any selection or projection, it is a pretty cheap node.
+	 * We don't bother with inventing a cost_append(), but just do it here.
+	 *
+	 * Compute rows and costs as sums of subplan rows and costs.  We charge
+	 * nothing extra for the Append itself, which perhaps is too optimistic,
+	 * but since it doesn't do any selection or projection, it is a pretty
+	 * cheap node.  If you change this, see also make_append().
 	 *
-	 * If you change this, see also make_append().
+	 * We also compute the correct required_outer set, namely the union of
+	 * the input paths' requirements.
+	 *
+	 * XXX We should also compute a proper param_clauses list, but that
+	 * will require identifying which joinclauses are enforced by all the
+	 * subplans, as well as locating the original parent RestrictInfo from
+	 * which they were generated.  For the moment we punt and leave the list
+	 * as NIL.  This will result in uselessly rechecking such joinclauses
+	 * at the parameter-supplying nestloop join, which is slightly annoying,
+	 * as well as overestimating the sizes of any intermediate joins, which
+	 * is significantly more annoying.
 	 */
+	pathnode->path.rows = 0;
 	pathnode->path.startup_cost = 0;
 	pathnode->path.total_cost = 0;
 	foreach(l, subpaths)
 	{
 		Path	   *subpath = (Path *) lfirst(l);
 
+		pathnode->path.rows += subpath->rows;
+
 		if (l == list_head(subpaths))	/* first node? */
 			pathnode->path.startup_cost = subpath->startup_cost;
 		pathnode->path.total_cost += subpath->total_cost;
+
+		pathnode->path.required_outer =
+			bms_add_members(pathnode->path.required_outer,
+							subpath->required_outer);
 	}
 
 	return pathnode;
@@ -704,6 +986,8 @@ create_merge_append_path(PlannerInfo *root,
 	pathnode->path.pathtype = T_MergeAppend;
 	pathnode->path.parent = rel;
 	pathnode->path.pathkeys = pathkeys;
+	pathnode->path.required_outer = NULL; /* updated below */
+	pathnode->path.param_clauses = NIL;	/* XXX see below */
 	pathnode->subpaths = subpaths;
 
 	/*
@@ -735,13 +1019,22 @@ create_merge_append_path(PlannerInfo *root,
 		}
 	}
 
-	/* Add up all the costs of the input paths */
+	/*
+	 * Add up the sizes and costs of the input paths, and also compute the
+	 * real required_outer value.
+	 *
+	 * XXX as in create_append_path(), we should compute param_clauses but
+	 * it will require more work.
+	 */
+	pathnode->path.rows = 0;
 	input_startup_cost = 0;
 	input_total_cost = 0;
 	foreach(l, subpaths)
 	{
 		Path	   *subpath = (Path *) lfirst(l);
 
+		pathnode->path.rows += subpath->rows;
+
 		if (pathkeys_contained_in(pathkeys, subpath->pathkeys))
 		{
 			/* Subpath is adequately ordered, we won't need to sort it */
@@ -765,6 +1058,10 @@ create_merge_append_path(PlannerInfo *root,
 			input_startup_cost += sort_path.startup_cost;
 			input_total_cost += sort_path.total_cost;
 		}
+
+		pathnode->path.required_outer =
+			bms_add_members(pathnode->path.required_outer,
+							subpath->required_outer);
 	}
 
 	/* Now we can compute total costs of the MergeAppend */
@@ -789,9 +1086,12 @@ create_result_path(List *quals)
 	pathnode->path.pathtype = T_Result;
 	pathnode->path.parent = NULL;
 	pathnode->path.pathkeys = NIL;
+	pathnode->path.required_outer = NULL;
+	pathnode->path.param_clauses = NIL;
 	pathnode->quals = quals;
 
-	/* Ideally should define cost_result(), but I'm too lazy */
+	/* Hardly worth defining a cost_result() function ... just do it */
+	pathnode->path.rows = 1;
 	pathnode->path.startup_cost = 0;
 	pathnode->path.total_cost = cpu_tuple_cost;
 
@@ -817,15 +1117,16 @@ create_material_path(RelOptInfo *rel, Path *subpath)
 
 	pathnode->path.pathtype = T_Material;
 	pathnode->path.parent = rel;
-
 	pathnode->path.pathkeys = subpath->pathkeys;
+	pathnode->path.required_outer = subpath->required_outer;
+	pathnode->path.param_clauses = subpath->param_clauses;
 
 	pathnode->subpath = subpath;
 
 	cost_material(&pathnode->path,
 				  subpath->startup_cost,
 				  subpath->total_cost,
-				  rel->rows,
+				  subpath->rows,
 				  rel->width);
 
 	return pathnode;
@@ -874,7 +1175,6 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
 	/*
 	 * We must ensure path struct and subsidiary data are allocated in main
 	 * planning context; otherwise GEQO memory management causes trouble.
-	 * (Compare best_inner_indexscan().)
 	 */
 	oldcontext = MemoryContextSwitchTo(root->planner_cxt);
 
@@ -1032,6 +1332,8 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
 	 * to represent it.  (This might get overridden below.)
 	 */
 	pathnode->path.pathkeys = NIL;
+	pathnode->path.required_outer = subpath->required_outer;
+	pathnode->path.param_clauses = subpath->param_clauses;
 
 	pathnode->subpath = subpath;
 	pathnode->in_operators = in_operators;
@@ -1048,7 +1350,7 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
 									  uniq_exprs, in_operators))
 	{
 		pathnode->umethod = UNIQUE_PATH_NOOP;
-		pathnode->rows = rel->rows;
+		pathnode->path.rows = rel->rows;
 		pathnode->path.startup_cost = subpath->startup_cost;
 		pathnode->path.total_cost = subpath->total_cost;
 		pathnode->path.pathkeys = subpath->pathkeys;
@@ -1081,7 +1383,7 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
 								  sub_tlist_colnos, in_operators))
 		{
 			pathnode->umethod = UNIQUE_PATH_NOOP;
-			pathnode->rows = rel->rows;
+			pathnode->path.rows = rel->rows;
 			pathnode->path.startup_cost = subpath->startup_cost;
 			pathnode->path.total_cost = subpath->total_cost;
 			pathnode->path.pathkeys = subpath->pathkeys;
@@ -1095,7 +1397,7 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
 	}
 
 	/* Estimate number of output rows */
-	pathnode->rows = estimate_num_groups(root, uniq_exprs, rel->rows);
+	pathnode->path.rows = estimate_num_groups(root, uniq_exprs, rel->rows);
 	numCols = list_length(uniq_exprs);
 
 	if (all_btree)
@@ -1128,12 +1430,12 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
 		 */
 		int			hashentrysize = rel->width + 64;
 
-		if (hashentrysize * pathnode->rows > work_mem * 1024L)
+		if (hashentrysize * pathnode->path.rows > work_mem * 1024L)
 			all_hash = false;	/* don't try to hash */
 		else
 			cost_agg(&agg_path, root,
 					 AGG_HASHED, NULL,
-					 numCols, pathnode->rows,
+					 numCols, pathnode->path.rows,
 					 subpath->startup_cost,
 					 subpath->total_cost,
 					 rel->rows);
@@ -1367,6 +1669,8 @@ create_subqueryscan_path(RelOptInfo *rel, List *pathkeys)
 	pathnode->pathtype = T_SubqueryScan;
 	pathnode->parent = rel;
 	pathnode->pathkeys = pathkeys;
+	pathnode->required_outer = NULL;
+	pathnode->param_clauses = NIL;
 
 	cost_subqueryscan(pathnode, rel);
 
@@ -1386,6 +1690,8 @@ create_functionscan_path(PlannerInfo *root, RelOptInfo *rel)
 	pathnode->pathtype = T_FunctionScan;
 	pathnode->parent = rel;
 	pathnode->pathkeys = NIL;	/* for now, assume unordered result */
+	pathnode->required_outer = NULL;
+	pathnode->param_clauses = NIL;
 
 	cost_functionscan(pathnode, root, rel);
 
@@ -1405,6 +1711,8 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel)
 	pathnode->pathtype = T_ValuesScan;
 	pathnode->parent = rel;
 	pathnode->pathkeys = NIL;	/* result is always unordered */
+	pathnode->required_outer = NULL;
+	pathnode->param_clauses = NIL;
 
 	cost_valuesscan(pathnode, root, rel);
 
@@ -1424,6 +1732,8 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *rel)
 	pathnode->pathtype = T_CteScan;
 	pathnode->parent = rel;
 	pathnode->pathkeys = NIL;	/* XXX for now, result is always unordered */
+	pathnode->required_outer = NULL;
+	pathnode->param_clauses = NIL;
 
 	cost_ctescan(pathnode, root, rel);
 
@@ -1443,6 +1753,8 @@ create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel)
 	pathnode->pathtype = T_WorkTableScan;
 	pathnode->parent = rel;
 	pathnode->pathkeys = NIL;	/* result is always unordered */
+	pathnode->required_outer = NULL;
+	pathnode->param_clauses = NIL;
 
 	/* Cost is the same as for a regular CTE scan */
 	cost_ctescan(pathnode, root, rel);
@@ -1466,6 +1778,8 @@ create_foreignscan_path(PlannerInfo *root, RelOptInfo *rel)
 	pathnode->path.pathtype = T_ForeignScan;
 	pathnode->path.parent = rel;
 	pathnode->path.pathkeys = NIL;		/* result is always unordered */
+	pathnode->path.required_outer = NULL;
+	pathnode->path.param_clauses = NIL;
 
 	/* Get FDW's callback info */
 	rte = planner_rt_fetch(rel->relid, root);
@@ -1479,6 +1793,7 @@ create_foreignscan_path(PlannerInfo *root, RelOptInfo *rel)
 	pathnode->fdwplan = fdwplan;
 
 	/* use costs estimated by FDW */
+	pathnode->path.rows = rel->rows;
 	pathnode->path.startup_cost = fdwplan->startup_cost;
 	pathnode->path.total_cost = fdwplan->total_cost;
 
@@ -1486,17 +1801,75 @@ create_foreignscan_path(PlannerInfo *root, RelOptInfo *rel)
 }
 
 /*
+ * calc_nestloop_required_outer
+ *	  Compute the required_outer set for a nestloop join path
+ *
+ * Note: result must not share storage with either input
+ */
+Relids
+calc_nestloop_required_outer(Path *outer_path, Path *inner_path)
+{
+	Relids	required_outer;
+
+	/* inner_path can require rels from outer path, but not vice versa */
+	Assert(!bms_overlap(outer_path->required_outer,
+						inner_path->parent->relids));
+	/* easy case if inner path is not parameterized */
+	if (!inner_path->required_outer)
+		return bms_copy(outer_path->required_outer);
+	/* else, form the union ... */
+	required_outer = bms_union(outer_path->required_outer,
+							   inner_path->required_outer);
+	/* ... and remove any mention of now-satisfied outer rels */
+	required_outer = bms_del_members(required_outer,
+									 outer_path->parent->relids);
+	/* maintain invariant that required_outer is exactly NULL if empty */
+	if (bms_is_empty(required_outer))
+	{
+		bms_free(required_outer);
+		required_outer = NULL;
+	}
+	return required_outer;
+}
+
+/*
+ * calc_non_nestloop_required_outer
+ *	  Compute the required_outer set for a merge or hash join path
+ *
+ * Note: result must not share storage with either input
+ */
+Relids
+calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
+{
+	Relids	required_outer;
+
+	/* neither path can require rels from the other */
+	Assert(!bms_overlap(outer_path->required_outer,
+						inner_path->parent->relids));
+	Assert(!bms_overlap(inner_path->required_outer,
+						outer_path->parent->relids));
+	/* form the union ... */
+	required_outer = bms_union(outer_path->required_outer,
+							   inner_path->required_outer);
+	/* we do not need an explicit test for empty; bms_union gets it right */
+	return required_outer;
+}
+
+/*
  * create_nestloop_path
  *	  Creates a pathnode corresponding to a nestloop join between two
  *	  relations.
  *
  * 'joinrel' is the join relation.
  * 'jointype' is the type of join required
+ * 'workspace' is the result from initial_cost_nestloop
  * 'sjinfo' is extra info about the join for selectivity estimation
+ * 'semifactors' contains valid data if jointype is SEMI or ANTI
  * 'outer_path' is the outer path
  * 'inner_path' is the inner path
  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
  * 'pathkeys' are the path keys of the new join path
+ * 'required_outer' is the set of required outer rels
  *
  * Returns the resulting path node.
  */
@@ -1504,23 +1877,46 @@ NestPath *
 create_nestloop_path(PlannerInfo *root,
 					 RelOptInfo *joinrel,
 					 JoinType jointype,
+					 JoinCostWorkspace *workspace,
 					 SpecialJoinInfo *sjinfo,
+					 SemiAntiJoinFactors *semifactors,
 					 Path *outer_path,
 					 Path *inner_path,
 					 List *restrict_clauses,
-					 List *pathkeys)
+					 List *pathkeys,
+					 Relids required_outer)
 {
 	NestPath   *pathnode = makeNode(NestPath);
 
 	pathnode->path.pathtype = T_NestLoop;
 	pathnode->path.parent = joinrel;
+	pathnode->path.pathkeys = pathkeys;
+	pathnode->path.required_outer = required_outer;
+	if (pathnode->path.required_outer)
+	{
+		/* Identify parameter clauses not yet applied here */
+		List	   *jclauses;
+		ListCell   *lc;
+
+		/* LHS clauses could not be satisfied here */
+		jclauses = list_copy(outer_path->param_clauses);
+		foreach(lc, inner_path->param_clauses)
+		{
+			RestrictInfo   *rinfo = (RestrictInfo *) lfirst(lc);
+
+			if (!bms_is_subset(rinfo->clause_relids, joinrel->relids))
+				jclauses = lappend(jclauses, rinfo);
+		}
+		pathnode->path.param_clauses = jclauses;
+	}
+	else
+		pathnode->path.param_clauses = NIL;
 	pathnode->jointype = jointype;
 	pathnode->outerjoinpath = outer_path;
 	pathnode->innerjoinpath = inner_path;
 	pathnode->joinrestrictinfo = restrict_clauses;
-	pathnode->path.pathkeys = pathkeys;
 
-	cost_nestloop(pathnode, root, sjinfo);
+	final_cost_nestloop(root, pathnode, workspace, sjinfo, semifactors);
 
 	return pathnode;
 }
@@ -1532,11 +1928,13 @@ create_nestloop_path(PlannerInfo *root,
  *
  * 'joinrel' is the join relation
  * 'jointype' is the type of join required
+ * 'workspace' is the result from initial_cost_mergejoin
  * 'sjinfo' is extra info about the join for selectivity estimation
  * 'outer_path' is the outer path
  * 'inner_path' is the inner path
  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
  * 'pathkeys' are the path keys of the new join path
+ * 'required_outer' is the set of required outer rels
  * 'mergeclauses' are the RestrictInfo nodes to use as merge clauses
  *		(this should be a subset of the restrict_clauses list)
  * 'outersortkeys' are the sort varkeys for the outer relation
@@ -1546,41 +1944,36 @@ MergePath *
 create_mergejoin_path(PlannerInfo *root,
 					  RelOptInfo *joinrel,
 					  JoinType jointype,
+					  JoinCostWorkspace *workspace,
 					  SpecialJoinInfo *sjinfo,
 					  Path *outer_path,
 					  Path *inner_path,
 					  List *restrict_clauses,
 					  List *pathkeys,
+					  Relids required_outer,
 					  List *mergeclauses,
 					  List *outersortkeys,
 					  List *innersortkeys)
 {
 	MergePath  *pathnode = makeNode(MergePath);
 
-	/*
-	 * If the given paths are already well enough ordered, we can skip doing
-	 * an explicit sort.
-	 */
-	if (outersortkeys &&
-		pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
-		outersortkeys = NIL;
-	if (innersortkeys &&
-		pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
-		innersortkeys = NIL;
-
 	pathnode->jpath.path.pathtype = T_MergeJoin;
 	pathnode->jpath.path.parent = joinrel;
+	pathnode->jpath.path.pathkeys = pathkeys;
+	pathnode->jpath.path.required_outer = required_outer;
+	pathnode->jpath.path.param_clauses =
+		list_concat(list_copy(outer_path->param_clauses),
+					inner_path->param_clauses);
 	pathnode->jpath.jointype = jointype;
 	pathnode->jpath.outerjoinpath = outer_path;
 	pathnode->jpath.innerjoinpath = inner_path;
 	pathnode->jpath.joinrestrictinfo = restrict_clauses;
-	pathnode->jpath.path.pathkeys = pathkeys;
 	pathnode->path_mergeclauses = mergeclauses;
 	pathnode->outersortkeys = outersortkeys;
 	pathnode->innersortkeys = innersortkeys;
-	/* pathnode->materialize_inner will be set by cost_mergejoin */
+	/* pathnode->materialize_inner will be set by final_cost_mergejoin */
 
-	cost_mergejoin(pathnode, root, sjinfo);
+	final_cost_mergejoin(root, pathnode, workspace, sjinfo);
 
 	return pathnode;
 }
@@ -1591,10 +1984,13 @@ create_mergejoin_path(PlannerInfo *root,
  *
  * 'joinrel' is the join relation
  * 'jointype' is the type of join required
+ * 'workspace' is the result from initial_cost_hashjoin
  * 'sjinfo' is extra info about the join for selectivity estimation
+ * 'semifactors' contains valid data if jointype is SEMI or ANTI
  * 'outer_path' is the cheapest outer path
  * 'inner_path' is the cheapest inner path
  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
+ * 'required_outer' is the set of required outer rels
  * 'hashclauses' are the RestrictInfo nodes to use as hash clauses
  *		(this should be a subset of the restrict_clauses list)
  */
@@ -1602,20 +1998,19 @@ HashPath *
 create_hashjoin_path(PlannerInfo *root,
 					 RelOptInfo *joinrel,
 					 JoinType jointype,
+					 JoinCostWorkspace *workspace,
 					 SpecialJoinInfo *sjinfo,
+					 SemiAntiJoinFactors *semifactors,
 					 Path *outer_path,
 					 Path *inner_path,
 					 List *restrict_clauses,
+					 Relids required_outer,
 					 List *hashclauses)
 {
 	HashPath   *pathnode = makeNode(HashPath);
 
 	pathnode->jpath.path.pathtype = T_HashJoin;
 	pathnode->jpath.path.parent = joinrel;
-	pathnode->jpath.jointype = jointype;
-	pathnode->jpath.outerjoinpath = outer_path;
-	pathnode->jpath.innerjoinpath = inner_path;
-	pathnode->jpath.joinrestrictinfo = restrict_clauses;
 
 	/*
 	 * A hashjoin never has pathkeys, since its output ordering is
@@ -1629,10 +2024,18 @@ create_hashjoin_path(PlannerInfo *root,
 	 * outer rel than it does now.)
 	 */
 	pathnode->jpath.path.pathkeys = NIL;
+	pathnode->jpath.path.required_outer = required_outer;
+	pathnode->jpath.path.param_clauses =
+		list_concat(list_copy(outer_path->param_clauses),
+					inner_path->param_clauses);
+	pathnode->jpath.jointype = jointype;
+	pathnode->jpath.outerjoinpath = outer_path;
+	pathnode->jpath.innerjoinpath = inner_path;
+	pathnode->jpath.joinrestrictinfo = restrict_clauses;
 	pathnode->path_hashclauses = hashclauses;
-	/* cost_hashjoin will fill in pathnode->num_batches */
+	/* final_cost_hashjoin will fill in pathnode->num_batches */
 
-	cost_hashjoin(pathnode, root, sjinfo);
+	final_cost_hashjoin(root, pathnode, workspace, sjinfo, semifactors);
 
 	return pathnode;
 }