Revise parameterized-path mechanism to fix assorted issues.

This patch adjusts the treatment of parameterized paths so that all paths
with the same parameterization (same set of required outer rels) for the
same relation will have the same rowcount estimate.  We cache the rowcount
estimates to ensure that property, and hopefully save a few cycles too.
Doing this makes it practical for add_path_precheck to operate without
a rowcount estimate: it need only assume that paths with different
parameterizations never dominate each other, which is close enough to
true anyway for coarse filtering, because normally a more-parameterized
path should yield fewer rows thanks to having more join clauses to apply.

In add_path, we do the full nine yards of comparing rowcount estimates
along with everything else, so that we can discard parameterized paths that
don't actually have an advantage.  This fixes some issues I'd found with
add_path rejecting parameterized paths on the grounds that they were more
expensive than not-parameterized ones, even though they yielded many fewer
rows and hence would be cheaper once subsequent joining was considered.

To make the same-rowcounts assumption valid, we have to require that any
parameterized path enforce *all* join clauses that could be obtained from
the particular set of outer rels, even if not all of them are useful for
indexing.  This is required at both base scans and joins.  It's a good
thing anyway since the net impact is that join quals are checked at the
lowest practical level in the join tree.  Hence, discard the original
rather ad-hoc mechanism for choosing parameterization joinquals, and build
a better one that has a more principled rule for when clauses can be moved.
The original rule was actually buggy anyway for lack of knowledge about
which relations are part of an outer join's outer side; getting this right
requires adding an outer_relids field to RestrictInfo.

1 files changed, 81 insertions, 65 deletions

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index e23cc5eb7b2..8f0eaf448c6 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -111,6 +111,7 @@ static Cost bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
 								List *paths);
 static PathClauseUsage *classify_index_clause_usage(Path *path,
 							List **clauselist);
+static Relids get_bitmap_tree_required_outer(Path *bitmapqual);
 static void find_indexpath_quals(Path *bitmapqual, List **quals, List **preds);
 static int	find_list_position(Node *node, List **nodelist);
 static bool check_index_only(RelOptInfo *rel, IndexOptInfo *index);
@@ -303,7 +304,7 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel)
 		BitmapHeapPath *bpath;
 
 		bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
-		bpath = create_bitmap_heap_path(root, rel, bitmapqual, 1.0);
+		bpath = create_bitmap_heap_path(root, rel, bitmapqual, NULL, 1.0);
 		add_path(rel, (Path *) bpath);
 	}
 
@@ -318,12 +319,15 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel)
 	if (bitjoinpaths != NIL)
 	{
 		Path	   *bitmapqual;
+		Relids		required_outer;
 		double		loop_count;
 		BitmapHeapPath *bpath;
 
 		bitmapqual = choose_bitmap_and(root, rel, bitjoinpaths);
-		loop_count = get_loop_count(root, bitmapqual->required_outer);
-		bpath = create_bitmap_heap_path(root, rel, bitmapqual, loop_count);
+		required_outer = get_bitmap_tree_required_outer(bitmapqual);
+		loop_count = get_loop_count(root, required_outer);
+		bpath = create_bitmap_heap_path(root, rel, bitmapqual,
+										required_outer, loop_count);
 		add_path(rel, (Path *) bpath);
 	}
 }
@@ -1320,17 +1324,21 @@ bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel, Path *ipath)
 {
 	BitmapHeapPath bpath;
 
+	/* Must be a simple IndexPath so that we can just copy its param_info */
+	Assert(IsA(ipath, IndexPath));
+
 	/* Set up a dummy BitmapHeapPath */
 	bpath.path.type = T_BitmapHeapPath;
 	bpath.path.pathtype = T_BitmapHeapScan;
 	bpath.path.parent = rel;
+	bpath.path.param_info = ipath->param_info;
 	bpath.path.pathkeys = NIL;
-	bpath.path.required_outer = ipath->required_outer;
-	bpath.path.param_clauses = ipath->param_clauses;
 	bpath.bitmapqual = ipath;
 
-	cost_bitmap_heap_scan((Path *) &bpath, root, rel, ipath,
-						  get_loop_count(root, bpath.path.required_outer));
+	cost_bitmap_heap_scan(&bpath.path, root, rel,
+						  bpath.path.param_info,
+						  ipath,
+						  get_loop_count(root, PATH_REQ_OUTER(ipath)));
 
 	return bpath.path.total_cost;
 }
@@ -1342,28 +1350,36 @@ bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel, Path *ipath)
 static Cost
 bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel, List *paths)
 {
-	BitmapAndPath *apath;
+	BitmapAndPath apath;
 	BitmapHeapPath bpath;
+	Relids		required_outer;
 
-	/*
-	 * Create a temporary BitmapAndPath.  (Because it needs realistic
-	 * required_outer and param_clauses values, making a dummy one would
-	 * take more code than it's worth.)
-	 */
-	apath = create_bitmap_and_path(root, rel, paths);
+	/* Set up a dummy BitmapAndPath */
+	apath.path.type = T_BitmapAndPath;
+	apath.path.pathtype = T_BitmapAnd;
+	apath.path.parent = rel;
+	apath.path.param_info = NULL;	/* not used in bitmap trees */
+	apath.path.pathkeys = NIL;
+	apath.bitmapquals = paths;
+	cost_bitmap_and_node(&apath, root);
+
+	/* Identify required outer rels, in case it's a parameterized scan */
+	required_outer = get_bitmap_tree_required_outer((Path *) &apath);
 
 	/* Set up a dummy BitmapHeapPath */
 	bpath.path.type = T_BitmapHeapPath;
 	bpath.path.pathtype = T_BitmapHeapScan;
 	bpath.path.parent = rel;
+	bpath.path.param_info = get_baserel_parampathinfo(root, rel,
+													  required_outer);
 	bpath.path.pathkeys = NIL;
-	bpath.path.required_outer = apath->path.required_outer;
-	bpath.path.param_clauses = apath->path.param_clauses;
-	bpath.bitmapqual = (Path *) apath;
+	bpath.bitmapqual = (Path *) &apath;
 
 	/* Now we can do cost_bitmap_heap_scan */
-	cost_bitmap_heap_scan((Path *) &bpath, root, rel, (Path *) apath,
-						  get_loop_count(root, bpath.path.required_outer));
+	cost_bitmap_heap_scan(&bpath.path, root, rel,
+						  bpath.path.param_info,
+						  (Path *) &apath,
+						  get_loop_count(root, required_outer));
 
 	return bpath.path.total_cost;
 }
@@ -1421,6 +1437,49 @@ classify_index_clause_usage(Path *path, List **clauselist)
 
 
 /*
+ * get_bitmap_tree_required_outer
+ *		Find the required outer rels for a bitmap tree (index/and/or)
+ *
+ * We don't associate any particular parameterization with a BitmapAnd or
+ * BitmapOr node; however, the IndexPaths have parameterization info, in
+ * their capacity as standalone access paths.  The parameterization required
+ * for the bitmap heap scan node is the union of rels referenced in the
+ * child IndexPaths.
+ */
+static Relids
+get_bitmap_tree_required_outer(Path *bitmapqual)
+{
+	Relids		result = NULL;
+	ListCell   *lc;
+
+	if (IsA(bitmapqual, IndexPath))
+	{
+		return bms_copy(PATH_REQ_OUTER(bitmapqual));
+	}
+	else if (IsA(bitmapqual, BitmapAndPath))
+	{
+		foreach(lc, ((BitmapAndPath *) bitmapqual)->bitmapquals)
+		{
+			result = bms_join(result,
+						  get_bitmap_tree_required_outer((Path *) lfirst(lc)));
+		}
+	}
+	else if (IsA(bitmapqual, BitmapOrPath))
+	{
+		foreach(lc, ((BitmapOrPath *) bitmapqual)->bitmapquals)
+		{
+			result = bms_join(result,
+						  get_bitmap_tree_required_outer((Path *) lfirst(lc)));
+		}
+	}
+	else
+		elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
+
+	return result;
+}
+
+
+/*
  * find_indexpath_quals
  *
  * Given the Path structure for a plain or bitmap indexscan, extract lists
@@ -1661,58 +1720,15 @@ match_join_clauses_to_index(PlannerInfo *root,
 							IndexClauseSet *clauseset,
 							List **joinorclauses)
 {
-	Relids		inner_baserels;
 	ListCell   *lc;
 
-	/*
-	 * There is no value in considering join clauses for outer joins in which
-	 * the indexed relation is on the outside, since there'd be no way to
-	 * perform such a join with a parameterized nestloop.  So first, identify
-	 * all baserels that are on the inside of such joins.
-	 */
-	inner_baserels = NULL;
-	foreach(lc, root->join_info_list)
-	{
-		SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
-
-		if (bms_overlap(rel->relids, sjinfo->min_lefthand))
-			inner_baserels = bms_add_members(inner_baserels,
-											 sjinfo->min_righthand);
-		/* full joins constrain both sides symmetrically */
-		if (sjinfo->jointype == JOIN_FULL &&
-			bms_overlap(rel->relids, sjinfo->min_righthand))
-			inner_baserels = bms_add_members(inner_baserels,
-											 sjinfo->min_lefthand);
-	}
-
-	/* Now scan the rel's join clauses */
+	/* Scan the rel's join clauses */
 	foreach(lc, rel->joininfo)
 	{
 		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
 
-		/* Ignore if it mentions anything from wrong side of an outer join */
-		if (bms_overlap(rinfo->clause_relids, inner_baserels))
-			continue;
-
-		/*
-		 * Note that we ignore required_relids; that's okay because we are
-		 * intentionally ignoring the normal rules for placing evaluation of
-		 * join clauses.  The whole point here is to evaluate join clauses
-		 * below their join, even if they would normally be delayed by
-		 * outer join rules.
-		 *
-		 * Instead of considering required_relids, we ignore clauses for which
-		 * the indexed rel is in nullable_relids; that means there's an outer
-		 * join below the clause and so it can't be checked at the relation
-		 * scan level.
-		 *
-		 * Note: unlike create_or_index_quals(), we can accept clauses that
-		 * are marked !is_pushed_down (ie they are themselves outer-join
-		 * clauses).  This is OK because any path generated with these clauses
-		 * could only be used in the inside of a nestloop join, which will be
-		 * the nullable side.
-		 */
-		if (bms_overlap(rel->relids, rinfo->nullable_relids))
+		/* Check if clause can be moved to this rel */
+		if (!join_clause_is_movable_to(rinfo, rel->relid))
 			continue;
 
 		/* Potentially usable, so see if it matches the index or is an OR */