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, 1047 insertions, 951 deletions

diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 11ee2317376..920593781b2 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -61,6 +61,14 @@ typedef enum
 	ST_ANYSCAN					/* either is okay */
 } ScanTypeControl;
 
+/* Data structure for collecting qual clauses that match an index */
+typedef struct
+{
+	bool		nonempty;		/* True if lists are not all empty */
+	/* Lists of RestrictInfos, one per index column */
+	List	   *indexclauses[INDEX_MAX_KEYS];
+} IndexClauseSet;
+
 /* Per-path data used within choose_bitmap_and() */
 typedef struct
 {
@@ -71,55 +79,73 @@ typedef struct
 } PathClauseUsage;
 
 
-static List *find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
-					List *clauses, List *outer_clauses,
-					bool istoplevel, RelOptInfo *outer_rel,
-					SaOpControl saop_control, ScanTypeControl scantype);
-static List *find_saop_paths(PlannerInfo *root, RelOptInfo *rel,
-				List *clauses, List *outer_clauses,
-				bool istoplevel, RelOptInfo *outer_rel);
+static void consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel,
+							IndexOptInfo *index,
+							IndexClauseSet *rclauseset,
+							IndexClauseSet *jclauseset,
+							IndexClauseSet *eclauseset,
+							List **bitindexpaths);
+static void expand_eclass_clause_combinations(PlannerInfo *root,
+								  RelOptInfo *rel,
+								  IndexOptInfo *index,
+								  int thiscol, int lastcol,
+								  IndexClauseSet *clauseset,
+								  IndexClauseSet *eclauseset,
+								  List **bitindexpaths);
+static void get_index_paths(PlannerInfo *root, RelOptInfo *rel,
+				IndexOptInfo *index, IndexClauseSet *clauses,
+				List **bitindexpaths);
+static List *build_index_paths(PlannerInfo *root, RelOptInfo *rel,
+				  IndexOptInfo *index, IndexClauseSet *clauses,
+				  bool useful_predicate,
+				  SaOpControl saop_control, ScanTypeControl scantype);
+static List *build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
+				   List *clauses, List *other_clauses);
+static List *drop_indexable_join_clauses(RelOptInfo *rel, List *clauses);
 static Path *choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
-				  List *paths, RelOptInfo *outer_rel);
+							   List *paths);
 static int	path_usage_comparator(const void *a, const void *b);
 static Cost bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
-					 Path *ipath, RelOptInfo *outer_rel);
+								 Path *ipath);
 static Cost bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
-					List *paths, RelOptInfo *outer_rel);
+								List *paths);
 static PathClauseUsage *classify_index_clause_usage(Path *path,
 							List **clauselist);
 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);
+static double get_loop_count(PlannerInfo *root, Relids outer_relids);
+static void match_restriction_clauses_to_index(RelOptInfo *rel,
+											   IndexOptInfo *index,
+											   IndexClauseSet *clauseset);
+static void match_join_clauses_to_index(PlannerInfo *root,
+							RelOptInfo *rel, IndexOptInfo *index,
+							IndexClauseSet *clauseset,
+							List **joinorclauses);
+static void match_eclass_clauses_to_index(PlannerInfo *root,
+										  IndexOptInfo *index,
+										  IndexClauseSet *clauseset);
 static void match_clauses_to_index(IndexOptInfo *index,
-					   List *clauses, List *outer_clauses,
-					   Relids outer_relids,
-					   SaOpControl saop_control,
-					   List **index_clauses_p,
-					   List **clause_columns_p,
-					   bool *found_clause);
+					   List *clauses,
+					   IndexClauseSet *clauseset);
+static void match_clause_to_index(IndexOptInfo *index,
+					  RestrictInfo *rinfo,
+					  IndexClauseSet *clauseset);
 static bool match_clause_to_indexcol(IndexOptInfo *index,
 						 int indexcol,
-						 RestrictInfo *rinfo,
-						 Relids outer_relids,
-						 SaOpControl saop_control);
+						 RestrictInfo *rinfo);
 static bool is_indexable_operator(Oid expr_op, Oid opfamily,
 					  bool indexkey_on_left);
 static bool match_rowcompare_to_indexcol(IndexOptInfo *index,
 							 int indexcol,
 							 Oid opfamily,
 							 Oid idxcollation,
-							 RowCompareExpr *clause,
-							 Relids outer_relids);
+							 RowCompareExpr *clause);
 static void match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
 						List **orderby_clauses_p,
 						List **clause_columns_p);
 static Expr *match_clause_to_ordering_op(IndexOptInfo *index,
 							int indexcol, Expr *clause, Oid pk_opfamily);
-static Relids indexable_outerrelids(PlannerInfo *root, RelOptInfo *rel);
-static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel,
-				  Relids outer_relids);
-static List *find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
-					  Relids outer_relids, bool isouterjoin);
 static bool match_boolean_index_clause(Node *clause, int indexcol,
 						   IndexOptInfo *index);
 static bool match_special_index_operator(Expr *clause,
@@ -152,21 +178,17 @@ static Const *string_to_const(const char *str, Oid datatype);
  *
  * There are two basic kinds of index scans.  A "plain" index scan uses
  * only restriction clauses (possibly none at all) in its indexqual,
- * so it can be applied in any context.  An "innerjoin" index scan uses
+ * so it can be applied in any context.  A "parameterized" index scan uses
  * join clauses (plus restriction clauses, if available) in its indexqual.
- * Therefore it can only be used as the inner relation of a nestloop
- * join against an outer rel that includes all the other rels mentioned
- * in its join clauses.  In that context, values for the other rels'
+ * When joining such a scan to one of the relations supplying the other
+ * variables used in its indexqual, the parameterized scan must appear as
+ * the inner relation of a nestloop join; it can't be used on the outer side,
+ * nor in a merge or hash join.  In that context, values for the other rels'
  * attributes are available and fixed during any one scan of the indexpath.
  *
- * An IndexPath is generated and submitted to add_path() for each plain index
- * scan this routine deems potentially interesting for the current query.
- *
- * We also determine the set of other relids that participate in join
- * clauses that could be used with each index.	The actually best innerjoin
- * path will be generated for each outer relation later on, but knowing the
- * set of potential otherrels allows us to identify equivalent outer relations
- * and avoid repeated computation.
+ * An IndexPath is generated and submitted to add_path() for each plain or
+ * parameterized index scan this routine deems potentially interesting for
+ * the current query.
  *
  * 'rel' is the relation for which we want to generate index paths
  *
@@ -177,98 +199,631 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel)
 {
 	List	   *indexpaths;
 	List	   *bitindexpaths;
-	ListCell   *l;
+	List	   *bitjoinpaths;
+	List	   *joinorclauses;
+	IndexClauseSet rclauseset;
+	IndexClauseSet jclauseset;
+	IndexClauseSet eclauseset;
+	ListCell   *ilist;
 
 	/* Skip the whole mess if no indexes */
 	if (rel->indexlist == NIL)
-	{
-		rel->index_outer_relids = NULL;
 		return;
+
+	/* Bitmap paths are collected and then dealt with at the end */
+	bitindexpaths = bitjoinpaths = joinorclauses = NIL;
+
+	/* Examine each index in turn */
+	foreach(ilist, rel->indexlist)
+	{
+		IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
+
+		/* Protect limited-size array in IndexClauseSets */
+		Assert(index->ncolumns <= INDEX_MAX_KEYS);
+
+		/*
+		 * Ignore partial indexes that do not match the query.
+		 * (generate_bitmap_or_paths() might be able to do something with
+		 * them, but that's of no concern here.)
+		 */
+		if (index->indpred != NIL && !index->predOK)
+			continue;
+
+		/*
+		 * Identify the restriction clauses that can match the index.
+		 */
+		MemSet(&rclauseset, 0, sizeof(rclauseset));
+		match_restriction_clauses_to_index(rel, index, &rclauseset);
+
+		/*
+		 * Build index paths from the restriction clauses.  These will be
+		 * non-parameterized paths.  Plain paths go directly to add_path(),
+		 * bitmap paths are added to bitindexpaths to be handled below.
+		 */
+		get_index_paths(root, rel, index, &rclauseset,
+						&bitindexpaths);
+
+		/*
+		 * Identify the join clauses that can match the index.  For the moment
+		 * we keep them separate from the restriction clauses.  Note that
+		 * this finds only "loose" join clauses that have not been merged
+		 * into EquivalenceClasses.  Also, collect join OR clauses for later.
+		 */
+		MemSet(&jclauseset, 0, sizeof(jclauseset));
+		match_join_clauses_to_index(root, rel, index,
+									&jclauseset, &joinorclauses);
+
+		/*
+		 * Look for EquivalenceClasses that can generate joinclauses
+		 * matching the index.
+		 */
+		MemSet(&eclauseset, 0, sizeof(eclauseset));
+		match_eclass_clauses_to_index(root, index, &eclauseset);
+
+		/*
+		 * If we found any plain or eclass join clauses, decide what to
+		 * do with 'em.
+		 */
+		if (jclauseset.nonempty || eclauseset.nonempty)
+			consider_index_join_clauses(root, rel, index,
+										&rclauseset,
+										&jclauseset,
+										&eclauseset,
+										&bitjoinpaths);
 	}
 
 	/*
-	 * Examine join clauses to see which ones are potentially usable with
-	 * indexes of this rel, and generate the set of all other relids that
-	 * participate in such join clauses.  We'll use this set later to
-	 * recognize outer rels that are equivalent for joining purposes.
+	 * Generate BitmapOrPaths for any suitable OR-clauses present in the
+	 * restriction list.  Add these to bitindexpaths.
 	 */
-	rel->index_outer_relids = indexable_outerrelids(root, rel);
+	indexpaths = generate_bitmap_or_paths(root, rel,
+										  rel->baserestrictinfo, NIL,
+										  false);
+	bitindexpaths = list_concat(bitindexpaths, indexpaths);
+
+	/*
+	 * Likewise, generate BitmapOrPaths for any suitable OR-clauses present in
+	 * the joinclause list.  Add these to bitjoinpaths.
+	 */
+	indexpaths = generate_bitmap_or_paths(root, rel,
+										  joinorclauses, rel->baserestrictinfo,
+										  false);
+	bitjoinpaths = list_concat(bitjoinpaths, indexpaths);
+
+	/*
+	 * If we found anything usable, generate a BitmapHeapPath for the most
+	 * promising combination of restriction bitmap index paths.  Note there
+	 * will be only one such path no matter how many indexes exist.  This
+	 * should be sufficient since there's basically only one figure of merit
+	 * (total cost) for such a path.
+	 */
+	if (bitindexpaths != NIL)
+	{
+		Path	   *bitmapqual;
+		BitmapHeapPath *bpath;
+
+		bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
+		bpath = create_bitmap_heap_path(root, rel, bitmapqual, 1.0);
+		add_path(rel, (Path *) bpath);
+	}
+
+	/*
+	 * Likewise, if we found anything usable, generate a BitmapHeapPath for
+	 * the most promising combination of join bitmap index paths.  Note there
+	 * will be only one such path no matter how many join clauses are
+	 * available.  (XXX is that good enough, or do we need to consider even
+	 * more paths for different subsets of possible join partners?  Also,
+	 * should we add in restriction bitmap paths as well?)
+	 */
+	if (bitjoinpaths != NIL)
+	{
+		Path	   *bitmapqual;
+		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);
+		add_path(rel, (Path *) bpath);
+	}
+}
+
+/*
+ * consider_index_join_clauses
+ *	  Given sets of join clauses for an index, decide which parameterized
+ *	  index paths to build.
+ *
+ * Plain indexpaths are sent directly to add_path, while potential
+ * bitmap indexpaths are added to *bitindexpaths for later processing.
+ *
+ * 'rel' is the index's heap relation
+ * 'index' is the index for which we want to generate paths
+ * 'rclauseset' is the collection of indexable restriction clauses
+ * 'jclauseset' is the collection of indexable simple join clauses
+ * 'eclauseset' is the collection of indexable clauses from EquivalenceClasses
+ * '*bitindexpaths' is the list to add bitmap paths to
+ *
+ * Note: this changes the clause lists contained in the passed clausesets,
+ * but we don't care since the caller is done with them.
+ */
+static void
+consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel,
+							IndexOptInfo *index,
+							IndexClauseSet *rclauseset,
+							IndexClauseSet *jclauseset,
+							IndexClauseSet *eclauseset,
+							List **bitindexpaths)
+{
+	IndexClauseSet clauseset;
+	int			last_eclass_col;
+	int			indexcol;
+
+	/*
+	 * We can always include any restriction clauses in the index clauses.
+	 * However, it's not obvious which subsets of the join clauses are worth
+	 * generating paths from, and it's unlikely that considering every
+	 * possible subset is worth the cycles.  Our current heuristic is based
+	 * on the index columns, with the idea that later index columns are less
+	 * useful than earlier ones; therefore it's unlikely to be worth trying
+	 * combinations that would remove a clause from an earlier index column
+	 * while adding one to a later column.  Also, we know that all the
+	 * eclass clauses for a particular column are redundant, so we should
+	 * use only one of them.  However, eclass clauses will always represent
+	 * equality which is the strongest type of index constraint, so those
+	 * are high-value and we should try every available combination when we
+	 * have eclass clauses for more than one column.  Furthermore, it's
+	 * unlikely to be useful to combine an eclass clause with non-eclass
+	 * clauses for the same index column.  These considerations lead to the
+	 * following heuristics:
+	 *
+	 * First, start with the restriction clauses, and add on all simple join
+	 * clauses for column 1.  If there are any such join clauses, generate
+	 * paths with this collection of clauses.  Then, if there are eclass
+	 * clauses for column 1, generate paths with each one of them replacing
+	 * any other clauses we have for column 1.
+	 *
+	 * Next, add on all simple join clauses for column 2.  If there are any
+	 * such join clauses, generate paths with this collection.  If there are
+	 * eclass clauses for columns 1 or 2, generate paths with each such clause
+	 * replacing other clauses for its index column, including cases where we
+	 * use restriction or simple join clauses for one column and an eclass
+	 * clause for the other.
+	 *
+	 * Repeat for each additional index column.
+	 */
+
+	/* Set up working set with just the restriction clauses */
+	memcpy(&clauseset, rclauseset, sizeof(clauseset));
+	/* Even if it's empty right now, it won't be by the time we use it */
+	clauseset.nonempty = true;
+
+	last_eclass_col = -1;
+	for (indexcol = 0; indexcol < index->ncolumns; indexcol++)
+	{
+		/*
+		 * If we don't have either simple join clauses or eclass clauses for
+		 * this column, no new paths can be created in this iteration.
+		 */
+		if (jclauseset->indexclauses[indexcol] == NIL &&
+			eclauseset->indexclauses[indexcol] == NIL)
+			continue;
+
+		/* Add any simple join clauses to the working set */
+		clauseset.indexclauses[indexcol] =
+			list_concat(clauseset.indexclauses[indexcol],
+						jclauseset->indexclauses[indexcol]);
+
+		/* Set recursion depth to reach last col with eclass clauses */
+		if (eclauseset->indexclauses[indexcol] != NIL)
+			last_eclass_col = indexcol;
+
+		/* Do we have eclass clauses for any column now under consideration? */
+		if (last_eclass_col >= 0)
+		{
+			/* Yes, so recursively generate all eclass clause combinations */
+			expand_eclass_clause_combinations(root, rel, index,
+											  0, last_eclass_col,
+											  &clauseset, eclauseset,
+											  bitindexpaths);
+		}
+		else
+		{
+			/* No, consider the newly-enlarged set of simple join clauses */
+			get_index_paths(root, rel, index, &clauseset, bitindexpaths);
+		}
+	}
+}
+
+/*
+ * expand_eclass_clause_combinations
+ *		Generate all combinations of eclass join clauses for first N columns,
+ *		and construct parameterized index paths for each combination.
+ *
+ * Workhorse for consider_index_join_clauses; see notes therein for rationale.
+ * It's convenient to use recursion to implement the enumeration, since we
+ * can have at most INDEX_MAX_KEYS recursion levels.
+ *
+ * 'rel', 'index', 'eclauseset', 'bitindexpaths' as above
+ * 'thiscol' is the current index column number/recursion level
+ * 'lastcol' is the last index column we should consider eclass clauses for
+ * 'clauseset' is the current collection of indexable clauses
+ */
+static void
+expand_eclass_clause_combinations(PlannerInfo *root, RelOptInfo *rel,
+								  IndexOptInfo *index,
+								  int thiscol, int lastcol,
+								  IndexClauseSet *clauseset,
+								  IndexClauseSet *eclauseset,
+								  List **bitindexpaths)
+{
+	List	   *save_clauses;
+	ListCell   *lc;
+
+	/* If past last eclass column, end the recursion and generate paths */
+	if (thiscol > lastcol)
+	{
+		get_index_paths(root, rel, index, clauseset, bitindexpaths);
+		return;
+	}
+
+	/* If no eclass clauses to consider for this column, just recurse */
+	if (eclauseset->indexclauses[thiscol] == NIL)
+	{
+		Assert(thiscol < lastcol);
+		expand_eclass_clause_combinations(root, rel, index,
+										  thiscol + 1, lastcol,
+										  clauseset, eclauseset,
+										  bitindexpaths);
+		return;
+	}
+
+	/* We'll momentarily save and restore the list of non-eclass clauses */
+	save_clauses = clauseset->indexclauses[thiscol];
+
+	/* If we have non-eclass clauses for this column, first try with those */
+	if (save_clauses)
+		expand_eclass_clause_combinations(root, rel, index,
+										  thiscol + 1, lastcol,
+										  clauseset, eclauseset,
+										  bitindexpaths);
+
+	/* For each eclass clause alternative ... */
+	foreach(lc, eclauseset->indexclauses[thiscol])
+	{
+		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+
+		/* Replace any existing clauses with the eclass clause */
+		clauseset->indexclauses[thiscol] = list_make1(rinfo);
+
+		/* Recurse to advance to next column */
+		expand_eclass_clause_combinations(root, rel, index,
+										  thiscol + 1, lastcol,
+										  clauseset, eclauseset,
+										  bitindexpaths);
+	}
+
+	/* Restore previous list contents */
+	clauseset->indexclauses[thiscol] = save_clauses;
+}
+
+
+/*
+ * get_index_paths
+ *	  Given an index and a set of index clauses for it, construct IndexPaths.
+ *
+ * Plain indexpaths are sent directly to add_path, while potential
+ * bitmap indexpaths are added to *bitindexpaths for later processing.
+ *
+ * This is a fairly simple frontend to build_index_paths().  Its reason for
+ * existence is mainly to handle ScalarArrayOpExpr quals properly.  If the
+ * index AM supports them natively, we should just include them in simple
+ * index paths.  If not, we should exclude them while building simple index
+ * paths, and then make a separate attempt to include them in bitmap paths.
+ */
+static void
+get_index_paths(PlannerInfo *root, RelOptInfo *rel,
+				IndexOptInfo *index, IndexClauseSet *clauses,
+				List **bitindexpaths)
+{
+	List	   *indexpaths;
+	ListCell   *lc;
 
 	/*
-	 * Find all the index paths that are directly usable for this relation
-	 * (ie, are valid without considering OR or JOIN clauses).
+	 * Build simple index paths using the clauses.  Allow ScalarArrayOpExpr
+	 * clauses only if the index AM supports them natively.
 	 */
-	indexpaths = find_usable_indexes(root, rel,
-									 rel->baserestrictinfo, NIL,
-									 true, NULL, SAOP_PER_AM, ST_ANYSCAN);
+	indexpaths = build_index_paths(root, rel,
+								   index, clauses,
+								   index->predOK,
+								   SAOP_PER_AM, ST_ANYSCAN);
 
 	/*
 	 * Submit all the ones that can form plain IndexScan plans to add_path.
-	 * (A plain IndexPath might represent either a plain IndexScan or an
-	 * IndexOnlyScan, but for our purposes here the distinction does not
+	 * (A plain IndexPath can represent either a plain IndexScan or an
+	 * IndexOnlyScan, but for our purposes here that distinction does not
 	 * matter.  However, some of the indexes might support only bitmap scans,
-	 * and those we mustn't submit to add_path here.)  Also, pick out the ones
-	 * that might be useful as bitmap scans.  For that, we must discard
-	 * indexes that don't support bitmap scans, and we also are only
-	 * interested in paths that have some selectivity; we should discard
-	 * anything that was generated solely for ordering purposes.
+	 * and those we mustn't submit to add_path here.)
+	 *
+	 * Also, pick out the ones that are usable as bitmap scans.  For that,
+	 * we must discard indexes that don't support bitmap scans, and we
+	 * also are only interested in paths that have some selectivity; we
+	 * should discard anything that was generated solely for ordering
+	 * purposes.
 	 */
-	bitindexpaths = NIL;
-	foreach(l, indexpaths)
+	foreach(lc, indexpaths)
 	{
-		IndexPath  *ipath = (IndexPath *) lfirst(l);
+		IndexPath  *ipath = (IndexPath *) lfirst(lc);
 
-		if (ipath->indexinfo->amhasgettuple)
+		if (index->amhasgettuple)
 			add_path(rel, (Path *) ipath);
 
-		if (ipath->indexinfo->amhasgetbitmap &&
+		if (index->amhasgetbitmap &&
 			(ipath->path.pathkeys == NIL ||
 			 ipath->indexselectivity < 1.0))
-			bitindexpaths = lappend(bitindexpaths, ipath);
+			*bitindexpaths = lappend(*bitindexpaths, ipath);
 	}
 
 	/*
-	 * Generate BitmapOrPaths for any suitable OR-clauses present in the
-	 * restriction list.  Add these to bitindexpaths.
+	 * If the index doesn't handle ScalarArrayOpExpr clauses natively,
+	 * check to see if there are any such clauses, and if so generate
+	 * bitmap scan paths relying on executor-managed ScalarArrayOpExpr.
 	 */
-	indexpaths = generate_bitmap_or_paths(root, rel,
-										  rel->baserestrictinfo, NIL,
-										  NULL);
-	bitindexpaths = list_concat(bitindexpaths, indexpaths);
+	if (!index->amsearcharray)
+	{
+		indexpaths = build_index_paths(root, rel,
+									   index, clauses,
+									   false,
+									   SAOP_REQUIRE, ST_BITMAPSCAN);
+		*bitindexpaths = list_concat(*bitindexpaths, indexpaths);
+	}
+}
+
+/*
+ * build_index_paths
+ *	  Given an index and a set of index clauses for it, construct zero
+ *	  or more IndexPaths.
+ *
+ * We return a list of paths because (1) this routine checks some cases
+ * that should cause us to not generate any IndexPath, and (2) in some
+ * cases we want to consider both a forward and a backward scan, so as
+ * to obtain both sort orders.  Note that the paths are just returned
+ * to the caller and not immediately fed to add_path().
+ *
+ * At top level, useful_predicate should be exactly the index's predOK flag
+ * (ie, true if it has a predicate that was proven from the restriction
+ * clauses).  When working on an arm of an OR clause, useful_predicate
+ * should be true if the predicate required the current OR list to be proven.
+ * Note that this routine should never be called at all if the index has an
+ * unprovable predicate.
+ *
+ * saop_control indicates whether ScalarArrayOpExpr clauses can be used.
+ * When it's SAOP_REQUIRE, index paths are created only if we found at least
+ * one ScalarArrayOpExpr clause.
+ *
+ * scantype indicates whether we want to create plain indexscans, bitmap
+ * indexscans, or both.  When it's ST_BITMAPSCAN, we will not consider
+ * index ordering while deciding if a Path is worth generating.
+ *
+ * 'rel' is the index's heap relation
+ * 'index' is the index for which we want to generate paths
+ * 'clauses' is the collection of indexable clauses (RestrictInfo nodes)
+ * 'useful_predicate' indicates whether the index has a useful predicate
+ * 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used
+ * 'scantype' indicates whether we need plain or bitmap scan support
+ */
+static List *
+build_index_paths(PlannerInfo *root, RelOptInfo *rel,
+				  IndexOptInfo *index, IndexClauseSet *clauses,
+				  bool useful_predicate,
+				  SaOpControl saop_control, ScanTypeControl scantype)
+{
+	List	   *result = NIL;
+	IndexPath  *ipath;
+	List	   *index_clauses;
+	List	   *clause_columns;
+	Relids		outer_relids;
+	double		loop_count;
+	List	   *orderbyclauses;
+	List	   *orderbyclausecols;
+	List	   *index_pathkeys;
+	List	   *useful_pathkeys;
+	bool		found_clause;
+	bool		pathkeys_possibly_useful;
+	bool		index_is_ordered;
+	bool		index_only_scan;
+	int			indexcol;
 
 	/*
-	 * Likewise, generate paths using executor-managed ScalarArrayOpExpr
-	 * clauses; these can't be simple indexscans but they can be used in
-	 * bitmap scans.
+	 * Check that index supports the desired scan type(s)
 	 */
-	indexpaths = find_saop_paths(root, rel,
-								 rel->baserestrictinfo, NIL,
-								 true, NULL);
-	bitindexpaths = list_concat(bitindexpaths, indexpaths);
+	switch (scantype)
+	{
+		case ST_INDEXSCAN:
+			if (!index->amhasgettuple)
+				return NIL;
+			break;
+		case ST_BITMAPSCAN:
+			if (!index->amhasgetbitmap)
+				return NIL;
+			break;
+		case ST_ANYSCAN:
+			/* either or both are OK */
+			break;
+	}
 
 	/*
-	 * If we found anything usable, generate a BitmapHeapPath for the most
-	 * promising combination of bitmap index paths.
+	 * 1. Collect the index clauses into a single list.
+	 *
+	 * We build a list of RestrictInfo nodes for clauses to be used with
+	 * this index, along with an integer list of the index column numbers
+	 * (zero based) that each clause should be used with.  The clauses are
+	 * ordered by index key, so that the column numbers form a nondecreasing
+	 * sequence.  (This order is depended on by btree and possibly other
+	 * places.)  The lists can be empty, if the index AM allows that.
+	 *
+	 * found_clause is set true only if there's at least one index clause;
+	 * and if saop_control is SAOP_REQUIRE, it has to be a ScalarArrayOpExpr
+	 * clause.
+	 *
+	 * We also build a Relids set showing which outer rels are required
+	 * by the selected clauses.
 	 */
-	if (bitindexpaths != NIL)
+	index_clauses = NIL;
+	clause_columns = NIL;
+	found_clause = false;
+	outer_relids = NULL;
+	for (indexcol = 0; indexcol < index->ncolumns; indexcol++)
 	{
-		Path	   *bitmapqual;
-		BitmapHeapPath *bpath;
+		ListCell   *lc;
 
-		bitmapqual = choose_bitmap_and(root, rel, bitindexpaths, NULL);
-		bpath = create_bitmap_heap_path(root, rel, bitmapqual, NULL);
-		add_path(rel, (Path *) bpath);
+		foreach(lc, clauses->indexclauses[indexcol])
+		{
+			RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+
+			if (IsA(rinfo->clause, ScalarArrayOpExpr))
+			{
+				/* Ignore if not supported by index */
+				if (saop_control == SAOP_PER_AM && !index->amsearcharray)
+					continue;
+				found_clause = true;
+			}
+			else
+			{
+				if (saop_control != SAOP_REQUIRE)
+					found_clause = true;
+			}
+			index_clauses = lappend(index_clauses, rinfo);
+			clause_columns = lappend_int(clause_columns, indexcol);
+			outer_relids = bms_add_members(outer_relids,
+										   rinfo->clause_relids);
+		}
+
+		/*
+		 * If no clauses match the first index column, check for amoptionalkey
+		 * restriction.  We can't generate a scan over an index with
+		 * amoptionalkey = false unless there's at least one index clause.
+		 * (When working on columns after the first, this test cannot fail.
+		 * It is always okay for columns after the first to not have any
+		 * clauses.)
+		 */
+		if (index_clauses == NIL && !index->amoptionalkey)
+			return NIL;
 	}
-}
 
+	/* We do not want the index's rel itself listed in outer_relids */
+	outer_relids = bms_del_member(outer_relids, rel->relid);
+	/* Enforce convention that outer_relids is exactly NULL if empty */
+	if (bms_is_empty(outer_relids))
+		outer_relids = NULL;
+
+	/* Compute loop_count for cost estimation purposes */
+	loop_count = get_loop_count(root, outer_relids);
 
-/*----------
- * find_usable_indexes
- *	  Given a list of restriction clauses, find all the potentially usable
- *	  indexes for the given relation, and return a list of IndexPaths.
+	/*
+	 * 2. Compute pathkeys describing index's ordering, if any, then see how
+	 * many of them are actually useful for this query.  This is not relevant
+	 * if we are only trying to build bitmap indexscans.
+	 */
+	pathkeys_possibly_useful = (scantype != ST_BITMAPSCAN &&
+								has_useful_pathkeys(root, rel));
+	index_is_ordered = (index->sortopfamily != NULL);
+	if (index_is_ordered && pathkeys_possibly_useful)
+	{
+		index_pathkeys = build_index_pathkeys(root, index,
+											  ForwardScanDirection);
+		useful_pathkeys = truncate_useless_pathkeys(root, rel,
+													index_pathkeys);
+		orderbyclauses = NIL;
+		orderbyclausecols = NIL;
+	}
+	else if (index->amcanorderbyop && pathkeys_possibly_useful)
+	{
+		/* see if we can generate ordering operators for query_pathkeys */
+		match_pathkeys_to_index(index, root->query_pathkeys,
+								&orderbyclauses,
+								&orderbyclausecols);
+		if (orderbyclauses)
+			useful_pathkeys = root->query_pathkeys;
+		else
+			useful_pathkeys = NIL;
+	}
+	else
+	{
+		useful_pathkeys = NIL;
+		orderbyclauses = NIL;
+		orderbyclausecols = NIL;
+	}
+
+	/*
+	 * 3. Check if an index-only scan is possible.  If we're not building
+	 * plain indexscans, this isn't relevant since bitmap scans don't support
+	 * index data retrieval anyway.
+	 */
+	index_only_scan = (scantype != ST_BITMAPSCAN &&
+					   check_index_only(rel, index));
+
+	/*
+	 * 4. Generate an indexscan path if there are relevant restriction clauses
+	 * in the current clauses, OR the index ordering is potentially useful for
+	 * later merging or final output ordering, OR the index has a useful
+	 * predicate, OR an index-only scan is possible.
+	 */
+	if (found_clause || useful_pathkeys != NIL || useful_predicate ||
+		index_only_scan)
+	{
+		ipath = create_index_path(root, index,
+								  index_clauses,
+								  clause_columns,
+								  orderbyclauses,
+								  orderbyclausecols,
+								  useful_pathkeys,
+								  index_is_ordered ?
+								  ForwardScanDirection :
+								  NoMovementScanDirection,
+								  index_only_scan,
+								  outer_relids,
+								  loop_count);
+		result = lappend(result, ipath);
+	}
+
+	/*
+	 * 5. If the index is ordered, a backwards scan might be interesting.
+	 */
+	if (index_is_ordered && pathkeys_possibly_useful)
+	{
+		index_pathkeys = build_index_pathkeys(root, index,
+											  BackwardScanDirection);
+		useful_pathkeys = truncate_useless_pathkeys(root, rel,
+													index_pathkeys);
+		if (useful_pathkeys != NIL)
+		{
+			ipath = create_index_path(root, index,
+									  index_clauses,
+									  clause_columns,
+									  NIL,
+									  NIL,
+									  useful_pathkeys,
+									  BackwardScanDirection,
+									  index_only_scan,
+									  outer_relids,
+									  loop_count);
+			result = lappend(result, ipath);
+		}
+	}
+
+	return result;
+}
+
+/*
+ * build_paths_for_OR
+ *	  Given a list of restriction clauses from one arm of an OR clause,
+ *	  construct all matching IndexPaths for the relation.
+ *
+ * Here we must scan all indexes of the relation, since a bitmap OR tree
+ * can use multiple indexes.
  *
  * The caller actually supplies two lists of restriction clauses: some
- * "current" ones and some "outer" ones.  Both lists can be used freely
+ * "current" ones and some "other" ones.  Both lists can be used freely
  * to match keys of the index, but an index must use at least one of the
  * "current" clauses to be considered usable.  The motivation for this is
  * examples like
@@ -281,85 +836,34 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel)
  * When dealing with a partial index, a match of the index predicate to
  * one of the "current" clauses also makes the index usable.
  *
- * If istoplevel is true (indicating we are considering the top level of a
- * rel's restriction clauses), we will include indexes in the result that
- * have an interesting sort order, even if they have no matching restriction
- * clauses.
- *
  * 'rel' is the relation for which we want to generate index paths
  * 'clauses' is the current list of clauses (RestrictInfo nodes)
- * 'outer_clauses' is the list of additional upper-level clauses
- * 'istoplevel' is true if clauses are the rel's top-level restriction list
- *		(outer_clauses must be NIL when this is true)
- * 'outer_rel' is the outer side of the join if forming an inner indexscan
- *		(so some of the given clauses are join clauses); NULL if not
- * 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used
- * 'scantype' indicates whether we need plain or bitmap scan support
- *
- * Note: check_partial_indexes() must have been run previously.
- *----------
+ * 'other_clauses' is the list of additional upper-level clauses
  */
 static List *
-find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
-					List *clauses, List *outer_clauses,
-					bool istoplevel, RelOptInfo *outer_rel,
-					SaOpControl saop_control, ScanTypeControl scantype)
+build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
+				   List *clauses, List *other_clauses)
 {
-	Relids		outer_relids = outer_rel ? outer_rel->relids : NULL;
-	bool		possibly_useful_pathkeys = has_useful_pathkeys(root, rel);
 	List	   *result = NIL;
 	List	   *all_clauses = NIL;		/* not computed till needed */
-	ListCell   *ilist;
+	ListCell   *lc;
 
-	foreach(ilist, rel->indexlist)
+	foreach(lc, rel->indexlist)
 	{
-		IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist);
-		IndexPath  *ipath;
-		List	   *restrictclauses;
-		List	   *restrictclausecols;
-		List	   *orderbyclauses;
-		List	   *orderbyclausecols;
-		List	   *index_pathkeys;
-		List	   *useful_pathkeys;
+		IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+		IndexClauseSet clauseset;
+		List	   *indexpaths;
 		bool		useful_predicate;
-		bool		found_clause;
-		bool		index_is_ordered;
-		bool		index_only_scan;
 
-		/*
-		 * Check that index supports the desired scan type(s)
-		 */
-		switch (scantype)
-		{
-			case ST_INDEXSCAN:
-				if (!index->amhasgettuple)
-					continue;
-				break;
-			case ST_BITMAPSCAN:
-				if (!index->amhasgetbitmap)
-					continue;
-				break;
-			case ST_ANYSCAN:
-				/* either or both are OK */
-				break;
-		}
-
-		/*
-		 * If we're doing find_saop_paths(), we can skip indexes that support
-		 * ScalarArrayOpExpr natively.  We already generated all the potential
-		 * indexpaths for them, so no need to do anything more.
-		 */
-		if (saop_control == SAOP_REQUIRE && index->amsearcharray)
+		/* Ignore index if it doesn't support bitmap scans */
+		if (!index->amhasgetbitmap)
 			continue;
 
 		/*
 		 * Ignore partial indexes that do not match the query.	If a partial
-		 * index is marked predOK then we know it's OK; otherwise, if we are
-		 * at top level we know it's not OK (since predOK is exactly whether
-		 * its predicate could be proven from the toplevel clauses).
-		 * Otherwise, we have to test whether the added clauses are sufficient
-		 * to imply the predicate.	If so, we could use the index in the
-		 * current context.
+		 * index is marked predOK then we know it's OK.  Otherwise, we have
+		 * to test whether the added clauses are sufficient to imply the
+		 * predicate. If so, we can use the index in the current context.
 		 *
 		 * We set useful_predicate to true iff the predicate was proven using
 		 * the current set of clauses.	This is needed to prevent matching a
@@ -372,218 +876,87 @@ find_usable_indexes(PlannerInfo *root, RelOptInfo *rel,
 		{
 			if (index->predOK)
 			{
-				if (istoplevel)
-				{
-					/* we know predicate was proven from these clauses */
-					useful_predicate = true;
-				}
+				/* Usable, but don't set useful_predicate */
 			}
 			else
 			{
-				if (istoplevel)
-					continue;	/* no point in trying to prove it */
-
 				/* Form all_clauses if not done already */
 				if (all_clauses == NIL)
 					all_clauses = list_concat(list_copy(clauses),
-											  outer_clauses);
+											  other_clauses);
 
 				if (!predicate_implied_by(index->indpred, all_clauses))
 					continue;	/* can't use it at all */
 
-				if (!predicate_implied_by(index->indpred, outer_clauses))
+				if (!predicate_implied_by(index->indpred, other_clauses))
 					useful_predicate = true;
 			}
 		}
 
 		/*
-		 * 1. Match the index against the available restriction clauses.
-		 * found_clause is set true only if at least one of the current
-		 * clauses was used (and, if saop_control is SAOP_REQUIRE, it has to
-		 * have been a ScalarArrayOpExpr clause).
+		 * Identify the restriction clauses that can match the index.
 		 */
-		match_clauses_to_index(index,
-							   clauses,
-							   outer_clauses,
-							   outer_relids,
-							   saop_control,
-							   &restrictclauses,
-							   &restrictclausecols,
-							   &found_clause);
+		MemSet(&clauseset, 0, sizeof(clauseset));
+		match_clauses_to_index(index, clauses, &clauseset);
 
 		/*
-		 * Not all index AMs support scans with no restriction clauses. We
-		 * can't generate a scan over an index with amoptionalkey = false
-		 * unless there's at least one restriction clause.
+		 * If no matches so far, and the index predicate isn't useful,
+		 * we don't want it.
 		 */
-		if (restrictclauses == NIL && !index->amoptionalkey)
+		if (!clauseset.nonempty && !useful_predicate)
 			continue;
 
 		/*
-		 * 2. Compute pathkeys describing index's ordering, if any, then see
-		 * how many of them are actually useful for this query.  This is not
-		 * relevant unless we are at top level.
-		 */
-		index_is_ordered = (index->sortopfamily != NULL);
-		if (index_is_ordered && possibly_useful_pathkeys &&
-			istoplevel && outer_rel == NULL)
-		{
-			index_pathkeys = build_index_pathkeys(root, index,
-												  ForwardScanDirection);
-			useful_pathkeys = truncate_useless_pathkeys(root, rel,
-														index_pathkeys);
-			orderbyclauses = NIL;
-			orderbyclausecols = NIL;
-		}
-		else if (index->amcanorderbyop && possibly_useful_pathkeys &&
-				 istoplevel && outer_rel == NULL && scantype != ST_BITMAPSCAN)
-		{
-			/* see if we can generate ordering operators for query_pathkeys */
-			match_pathkeys_to_index(index, root->query_pathkeys,
-									&orderbyclauses,
-									&orderbyclausecols);
-			if (orderbyclauses)
-				useful_pathkeys = root->query_pathkeys;
-			else
-				useful_pathkeys = NIL;
-		}
-		else
-		{
-			useful_pathkeys = NIL;
-			orderbyclauses = NIL;
-			orderbyclausecols = NIL;
-		}
-
-		/*
-		 * 3. Check if an index-only scan is possible.
-		 */
-		index_only_scan = check_index_only(rel, index);
-
-		/*
-		 * 4. Generate an indexscan path if there are relevant restriction
-		 * clauses in the current clauses, OR the index ordering is
-		 * potentially useful for later merging or final output ordering, OR
-		 * the index has a predicate that was proven by the current clauses,
-		 * OR an index-only scan is possible.
+		 * Add "other" restriction clauses to the clauseset.
 		 */
-		if (found_clause || useful_pathkeys != NIL || useful_predicate ||
-			index_only_scan)
-		{
-			ipath = create_index_path(root, index,
-									  restrictclauses,
-									  restrictclausecols,
-									  orderbyclauses,
-									  orderbyclausecols,
-									  useful_pathkeys,
-									  index_is_ordered ?
-									  ForwardScanDirection :
-									  NoMovementScanDirection,
-									  index_only_scan,
-									  outer_rel);
-			result = lappend(result, ipath);
-		}
+		match_clauses_to_index(index, other_clauses, &clauseset);
 
 		/*
-		 * 5. If the index is ordered, a backwards scan might be interesting.
-		 * Again, this is only interesting at top level.
+		 * Construct paths if possible.
 		 */
-		if (index_is_ordered && possibly_useful_pathkeys &&
-			istoplevel && outer_rel == NULL)
-		{
-			index_pathkeys = build_index_pathkeys(root, index,
-												  BackwardScanDirection);
-			useful_pathkeys = truncate_useless_pathkeys(root, rel,
-														index_pathkeys);
-			if (useful_pathkeys != NIL)
-			{
-				ipath = create_index_path(root, index,
-										  restrictclauses,
-										  restrictclausecols,
-										  NIL,
-										  NIL,
-										  useful_pathkeys,
-										  BackwardScanDirection,
-										  index_only_scan,
-										  outer_rel);
-				result = lappend(result, ipath);
-			}
-		}
+		indexpaths = build_index_paths(root, rel,
+									   index, &clauseset,
+									   useful_predicate,
+									   SAOP_ALLOW, ST_BITMAPSCAN);
+		result = list_concat(result, indexpaths);
 	}
 
 	return result;
 }
 
-
-/*
- * find_saop_paths
- *		Find all the potential indexpaths that make use of executor-managed
- *		ScalarArrayOpExpr clauses.  The executor only supports these in bitmap
- *		scans, not plain indexscans, so we need to segregate them from the
- *		normal case.  Otherwise, same API as find_usable_indexes().
- *		Returns a list of IndexPaths.
- */
-static List *
-find_saop_paths(PlannerInfo *root, RelOptInfo *rel,
-				List *clauses, List *outer_clauses,
-				bool istoplevel, RelOptInfo *outer_rel)
-{
-	bool		have_saop = false;
-	ListCell   *l;
-
-	/*
-	 * Since find_usable_indexes is relatively expensive, don't bother to run
-	 * it unless there are some top-level ScalarArrayOpExpr clauses.
-	 */
-	foreach(l, clauses)
-	{
-		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
-
-		Assert(IsA(rinfo, RestrictInfo));
-		if (IsA(rinfo->clause, ScalarArrayOpExpr))
-		{
-			have_saop = true;
-			break;
-		}
-	}
-	if (!have_saop)
-		return NIL;
-
-	return find_usable_indexes(root, rel,
-							   clauses, outer_clauses,
-							   istoplevel, outer_rel,
-							   SAOP_REQUIRE, ST_BITMAPSCAN);
-}
-
-
 /*
  * generate_bitmap_or_paths
  *		Look through the list of clauses to find OR clauses, and generate
  *		a BitmapOrPath for each one we can handle that way.  Return a list
  *		of the generated BitmapOrPaths.
  *
- * outer_clauses is a list of additional clauses that can be assumed true
+ * other_clauses is a list of additional clauses that can be assumed true
  * for the purpose of generating indexquals, but are not to be searched for
- * ORs.  (See find_usable_indexes() for motivation.)  outer_rel is the outer
- * side when we are considering a nestloop inner indexpath.
+ * ORs.  (See build_paths_for_OR() for motivation.)
+ *
+ * If restriction_only is true, ignore OR elements that are join clauses.
+ * When using this feature it is caller's responsibility that neither clauses
+ * nor other_clauses contain any join clauses that are not ORs, as we do not
+ * re-filter those lists.
  */
 List *
 generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
-						 List *clauses, List *outer_clauses,
-						 RelOptInfo *outer_rel)
+						 List *clauses, List *other_clauses,
+						 bool restriction_only)
 {
 	List	   *result = NIL;
 	List	   *all_clauses;
-	ListCell   *l;
+	ListCell   *lc;
 
 	/*
-	 * We can use both the current and outer clauses as context for
-	 * find_usable_indexes
+	 * We can use both the current and other clauses as context for
+	 * build_paths_for_OR; no need to remove ORs from the lists.
 	 */
-	all_clauses = list_concat(list_copy(clauses), outer_clauses);
+	all_clauses = list_concat(list_copy(clauses), other_clauses);
 
-	foreach(l, clauses)
+	foreach(lc, clauses)
 	{
-		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
 		List	   *pathlist;
 		Path	   *bitmapqual;
 		ListCell   *j;
@@ -608,31 +981,34 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 			{
 				List	   *andargs = ((BoolExpr *) orarg)->args;
 
-				indlist = find_usable_indexes(root, rel,
-											  andargs,
-											  all_clauses,
-											  false,
-											  outer_rel,
-											  SAOP_ALLOW,
-											  ST_BITMAPSCAN);
+				if (restriction_only)
+					andargs = drop_indexable_join_clauses(rel, andargs);
+
+				indlist = build_paths_for_OR(root, rel,
+											 andargs,
+											 all_clauses);
+
 				/* Recurse in case there are sub-ORs */
 				indlist = list_concat(indlist,
 									  generate_bitmap_or_paths(root, rel,
 															   andargs,
 															   all_clauses,
-															   outer_rel));
+															   restriction_only));
 			}
 			else
 			{
+				List	   *orargs;
+
 				Assert(IsA(orarg, RestrictInfo));
 				Assert(!restriction_is_or_clause((RestrictInfo *) orarg));
-				indlist = find_usable_indexes(root, rel,
-											  list_make1(orarg),
-											  all_clauses,
-											  false,
-											  outer_rel,
-											  SAOP_ALLOW,
-											  ST_BITMAPSCAN);
+				orargs = list_make1(orarg);
+
+				if (restriction_only)
+					orargs = drop_indexable_join_clauses(rel, orargs);
+
+				indlist = build_paths_for_OR(root, rel,
+											 orargs,
+											 all_clauses);
 			}
 
 			/*
@@ -649,7 +1025,7 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 			 * OK, pick the most promising AND combination, and add it to
 			 * pathlist.
 			 */
-			bitmapqual = choose_bitmap_and(root, rel, indlist, outer_rel);
+			bitmapqual = choose_bitmap_and(root, rel, indlist);
 			pathlist = lappend(pathlist, bitmapqual);
 		}
 
@@ -667,6 +1043,34 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
 	return result;
 }
 
+/*
+ * drop_indexable_join_clauses
+ *		Remove any indexable join clauses from the list.
+ *
+ * This is a helper for generate_bitmap_or_paths().  We leave OR clauses
+ * in the list whether they are joins or not, since we might be able to
+ * extract a restriction item from an OR list.  It's safe to leave such
+ * clauses in the list because match_clauses_to_index() will ignore them,
+ * so there's no harm in passing such clauses to build_paths_for_OR().
+ */
+static List *
+drop_indexable_join_clauses(RelOptInfo *rel, List *clauses)
+{
+	List	   *result = NIL;
+	ListCell   *lc;
+
+	foreach(lc, clauses)
+	{
+		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+
+		Assert(IsA(rinfo, RestrictInfo));
+		if (restriction_is_or_clause(rinfo) ||
+			bms_is_subset(rinfo->clause_relids, rel->relids))
+			result = lappend(result, rinfo);
+	}
+	return result;
+}
+
 
 /*
  * choose_bitmap_and
@@ -680,8 +1084,7 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
  * combining multiple inputs.
  */
 static Path *
-choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
-				  List *paths, RelOptInfo *outer_rel)
+choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
 {
 	int			npaths = list_length(paths);
 	PathClauseUsage **pathinfoarray;
@@ -729,7 +1132,7 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
 	 * reduces the total cost.	Perhaps someday that code will be smarter and
 	 * we can remove this limitation.  (But note that this also defends
 	 * against flat-out duplicate input paths, which can happen because
-	 * best_inner_indexscan will find the same OR join clauses that
+	 * match_join_clauses_to_index will find the same OR join clauses that
 	 * create_or_index_quals has pulled OR restriction clauses out of.)
 	 *
 	 * For the same reason, we reject AND combinations in which an index
@@ -807,7 +1210,7 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
 
 		pathinfo = pathinfoarray[i];
 		paths = list_make1(pathinfo->path);
-		costsofar = bitmap_scan_cost_est(root, rel, pathinfo->path, outer_rel);
+		costsofar = bitmap_scan_cost_est(root, rel, pathinfo->path);
 		qualsofar = list_concat(list_copy(pathinfo->quals),
 								list_copy(pathinfo->preds));
 		clauseidsofar = bms_copy(pathinfo->clauseids);
@@ -841,7 +1244,7 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel,
 			}
 			/* tentatively add new path to paths, so we can estimate cost */
 			paths = lappend(paths, pathinfo->path);
-			newcost = bitmap_and_cost_est(root, rel, paths, outer_rel);
+			newcost = bitmap_and_cost_est(root, rel, paths);
 			if (newcost < costsofar)
 			{
 				/* keep new path in paths, update subsidiary variables */
@@ -913,14 +1316,23 @@ path_usage_comparator(const void *a, const void *b)
  * index path (no BitmapAnd, at least not at this level).
  */
 static Cost
-bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
-					 Path *ipath, RelOptInfo *outer_rel)
+bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel, Path *ipath)
 {
-	Path		bpath;
+	BitmapHeapPath bpath;
+
+	/* Set up a dummy BitmapHeapPath */
+	bpath.path.type = T_BitmapHeapPath;
+	bpath.path.pathtype = T_BitmapHeapScan;
+	bpath.path.parent = rel;
+	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(&bpath, root, rel, ipath, outer_rel);
+	cost_bitmap_heap_scan((Path *) &bpath, root, rel, ipath,
+						  get_loop_count(root, bpath.path.required_outer));
 
-	return bpath.total_cost;
+	return bpath.path.total_cost;
 }
 
 /*
@@ -928,22 +1340,32 @@ bitmap_scan_cost_est(PlannerInfo *root, RelOptInfo *rel,
  * inputs.
  */
 static Cost
-bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel,
-					List *paths, RelOptInfo *outer_rel)
+bitmap_and_cost_est(PlannerInfo *root, RelOptInfo *rel, List *paths)
 {
-	BitmapAndPath apath;
-	Path		bpath;
+	BitmapAndPath *apath;
+	BitmapHeapPath bpath;
 
-	/* Set up a dummy BitmapAndPath */
-	apath.path.type = T_BitmapAndPath;
-	apath.path.parent = rel;
-	apath.bitmapquals = paths;
-	cost_bitmap_and_node(&apath, root);
+	/*
+	 * 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 BitmapHeapPath */
+	bpath.path.type = T_BitmapHeapPath;
+	bpath.path.pathtype = T_BitmapHeapScan;
+	bpath.path.parent = rel;
+	bpath.path.pathkeys = NIL;
+	bpath.path.required_outer = apath->path.required_outer;
+	bpath.path.param_clauses = apath->path.param_clauses;
+	bpath.bitmapqual = (Path *) apath;
 
 	/* Now we can do cost_bitmap_heap_scan */
-	cost_bitmap_heap_scan(&bpath, root, rel, (Path *) &apath, outer_rel);
+	cost_bitmap_heap_scan((Path *) &bpath, root, rel, (Path *) apath,
+						  get_loop_count(root, bpath.path.required_outer));
 
-	return bpath.total_cost;
+	return bpath.path.total_cost;
 }
 
 
@@ -1150,128 +1572,253 @@ check_index_only(RelOptInfo *rel, IndexOptInfo *index)
 	return result;
 }
 
+/*
+ * get_loop_count
+ *		Choose the loop count estimate to use for costing a parameterized path
+ *		with the given set of outer relids.
+ *
+ * Since we produce parameterized paths before we've begun to generate join
+ * relations, it's impossible to predict exactly how many times a parameterized
+ * path will be iterated; we don't know the size of the relation that will be
+ * on the outside of the nestloop.  However, we should try to account for
+ * multiple iterations somehow in costing the path.  The heuristic embodied
+ * here is to use the rowcount of the smallest other base relation needed in
+ * the join clauses used by the path.  (We could alternatively consider the
+ * largest one, but that seems too optimistic.)  This is of course the right
+ * answer for single-other-relation cases, and it seems like a reasonable
+ * zero-order approximation for multiway-join cases.
+ *
+ * Note: for this to work, allpaths.c must establish all baserel size
+ * estimates before it begins to compute paths, or at least before it
+ * calls create_index_paths().
+ */
+static double
+get_loop_count(PlannerInfo *root, Relids outer_relids)
+{
+	double		result = 1.0;
+
+	/* For a non-parameterized path, just return 1.0 quickly */
+	if (outer_relids != NULL)
+	{
+		int			relid;
+
+		/* Need a working copy since bms_first_member is destructive */
+		outer_relids = bms_copy(outer_relids);
+		while ((relid = bms_first_member(outer_relids)) >= 0)
+		{
+			RelOptInfo *outer_rel;
+
+			/* Paranoia: ignore bogus relid indexes */
+			if (relid >= root->simple_rel_array_size)
+				continue;
+			outer_rel = root->simple_rel_array[relid];
+			if (outer_rel == NULL)
+				continue;
+			Assert(outer_rel->relid == relid); /* sanity check on array */
+
+			/* Other relation could be proven empty, if so ignore */
+			if (IS_DUMMY_REL(outer_rel))
+				continue;
+
+			/* Otherwise, rel's rows estimate should be valid by now */
+			Assert(outer_rel->rows > 0);
+
+			/* Remember smallest row count estimate among the outer rels */
+			if (result == 1.0 || result > outer_rel->rows)
+				result = outer_rel->rows;
+		}
+		bms_free(outer_relids);
+	}
+	return result;
+}
+
 
 /****************************************************************************
- *				----  ROUTINES TO CHECK RESTRICTIONS  ----
+ *				----  ROUTINES TO CHECK QUERY CLAUSES  ----
  ****************************************************************************/
 
+/*
+ * match_restriction_clauses_to_index
+ *	  Identify restriction clauses for the rel that match the index.
+ *	  Matching clauses are added to *clauseset.
+ */
+static void
+match_restriction_clauses_to_index(RelOptInfo *rel, IndexOptInfo *index,
+								   IndexClauseSet *clauseset)
+{
+	match_clauses_to_index(index, rel->baserestrictinfo, clauseset);
+}
 
 /*
- * match_clauses_to_index
- *	  Find restriction clauses that can be used with an index.
- *
- * Returns a list of RestrictInfo nodes for clauses that can be used with
- * this index, along with an integer list of the index column numbers
- * (zero based) that each clause would be used with.  The clauses are
- * ordered by index key, so that the column numbers form a nondecreasing
- * sequence.  (This order is depended on by btree and possibly other places.)
- * NIL lists are returned if there are no matching clauses.
- *
- * We can use clauses from either the current clauses or outer_clauses lists,
- * but *found_clause is set TRUE only if we used at least one clause from
- * the "current clauses" list.	See find_usable_indexes() for motivation.
- *
- * outer_relids determines what Vars will be allowed on the other side
- * of a possible index qual; see match_clause_to_indexcol().
- *
- * 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used.
- * When it's SAOP_REQUIRE, *found_clause is set TRUE only if we used at least
- * one ScalarArrayOpExpr from the current clauses list.
- *
- * If the index has amoptionalkey = false, we give up and return NIL when
- * there are no restriction clauses matching the first index key.  Otherwise,
- * we return NIL only if there are no restriction clauses matching any index
- * key.  There could be unused index keys after the first one in any case.
- *
- * Note: in some circumstances we may find the same RestrictInfos coming
- * from multiple places.  Defend against redundant outputs by refusing to
- * match an already-used clause (pointer equality should be a good enough
- * check for this).  This also keeps us from matching the same clause to
- * multiple columns of a badly-defined index, which is unlikely to be helpful
- * and is likely to give us an inflated idea of the index's selectivity.
+ * match_join_clauses_to_index
+ *	  Identify join clauses for the rel that match the index.
+ *	  Matching clauses are added to *clauseset.
+ *	  Also, add any potentially usable join OR clauses to *joinorclauses.
  */
 static void
-match_clauses_to_index(IndexOptInfo *index,
-					   List *clauses, List *outer_clauses,
-					   Relids outer_relids,
-					   SaOpControl saop_control,
-					   List **index_clauses_p,
-					   List **clause_columns_p,
-					   bool *found_clause)
+match_join_clauses_to_index(PlannerInfo *root,
+							RelOptInfo *rel, IndexOptInfo *index,
+							IndexClauseSet *clauseset,
+							List **joinorclauses)
 {
-	List	   *index_clauses = NIL;
-	List	   *clause_columns = NIL;
-	int			indexcol;
+	Relids		inner_baserels;
+	ListCell   *lc;
 
-	*index_clauses_p = NIL;		/* set default results */
-	*clause_columns_p = NIL;
-	*found_clause = false;
+	/*
+	 * 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 (clauses == NIL && outer_clauses == NIL)
-		return;					/* cannot succeed */
+		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);
+	}
 
-	for (indexcol = 0; indexcol < index->ncolumns; indexcol++)
+	/* Now scan the rel's join clauses */
+	foreach(lc, rel->joininfo)
 	{
-		ListCell   *l;
+		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
 
-		/* check the current clauses */
-		foreach(l, clauses)
-		{
-			RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+		/* Ignore if it mentions anything from wrong side of an outer join */
+		if (bms_overlap(rinfo->clause_relids, inner_baserels))
+			continue;
 
-			Assert(IsA(rinfo, RestrictInfo));
-			if (list_member_ptr(index_clauses, rinfo))
-				continue;
-			if (match_clause_to_indexcol(index,
-										 indexcol,
-										 rinfo,
-										 outer_relids,
-										 saop_control))
-			{
-				index_clauses = lappend(index_clauses, rinfo);
-				clause_columns = lappend_int(clause_columns, indexcol);
-				if (saop_control != SAOP_REQUIRE ||
-					IsA(rinfo->clause, ScalarArrayOpExpr))
-					*found_clause = true;
-			}
-		}
+		/*
+		 * 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
+		 * any referenced 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(rinfo->clause_relids, rinfo->nullable_relids))
+			continue;
 
-		/* check the outer clauses */
-		foreach(l, outer_clauses)
-		{
-			RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+		/* Potentially usable, so see if it matches the index or is an OR */
+		if (restriction_is_or_clause(rinfo))
+			*joinorclauses = lappend(*joinorclauses, rinfo);
+		else
+			match_clause_to_index(index, rinfo, clauseset);
+	}
+}
 
-			Assert(IsA(rinfo, RestrictInfo));
-			if (list_member_ptr(index_clauses, rinfo))
-				continue;
-			if (match_clause_to_indexcol(index,
-										 indexcol,
-										 rinfo,
-										 outer_relids,
-										 saop_control))
-			{
-				index_clauses = lappend(index_clauses, rinfo);
-				clause_columns = lappend_int(clause_columns, indexcol);
-			}
-		}
+/*
+ * match_eclass_clauses_to_index
+ *	  Identify EquivalenceClass join clauses for the rel that match the index.
+ *	  Matching clauses are added to *clauseset.
+ */
+static void
+match_eclass_clauses_to_index(PlannerInfo *root, IndexOptInfo *index,
+							  IndexClauseSet *clauseset)
+{
+	int			indexcol;
+
+	/* No work if rel is not in any such ECs */
+	if (!index->rel->has_eclass_joins)
+		return;
+
+	for (indexcol = 0; indexcol < index->ncolumns; indexcol++)
+	{
+		List	   *clauses;
+
+		clauses = generate_implied_equalities_for_indexcol(root,
+														   index,
+														   indexcol);
 
 		/*
-		 * If no clauses match this key, check for amoptionalkey restriction.
+		 * We have to check whether the results actually do match the index,
+		 * since for non-btree indexes the EC's equality operators might not
+		 * be in the index opclass (cf eclass_member_matches_indexcol).
 		 */
-		if (index_clauses == NIL && !index->amoptionalkey)
-			return;
+		match_clauses_to_index(index, clauses, clauseset);
 	}
+}
 
-	*index_clauses_p = index_clauses;
-	*clause_columns_p = clause_columns;
+/*
+ * match_clauses_to_index
+ *	  Perform match_clause_to_index() for each clause in a list.
+ *	  Matching clauses are added to *clauseset.
+ */
+static void
+match_clauses_to_index(IndexOptInfo *index,
+					   List *clauses,
+					   IndexClauseSet *clauseset)
+{
+	ListCell   *lc;
+
+	foreach(lc, clauses)
+	{
+		RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+
+		Assert(IsA(rinfo, RestrictInfo));
+		match_clause_to_index(index, rinfo, clauseset);
+	}
 }
 
+/*
+ * match_clause_to_index
+ *	  Test whether a qual clause can be used with an index.
+ *
+ * If the clause is usable, add it to the appropriate list in *clauseset.
+ * *clauseset must be initialized to zeroes before first call.
+ *
+ * Note: in some circumstances we may find the same RestrictInfos coming from
+ * multiple places.  Defend against redundant outputs by refusing to add a
+ * clause twice (pointer equality should be a good enough check for this).
+ *
+ * Note: it's possible that a badly-defined index could have multiple matching
+ * columns.  We always select the first match if so; this avoids scenarios
+ * wherein we get an inflated idea of the index's selectivity by using the
+ * same clause multiple times with different index columns.
+ */
+static void
+match_clause_to_index(IndexOptInfo *index,
+					  RestrictInfo *rinfo,
+					  IndexClauseSet *clauseset)
+{
+	int			indexcol;
+
+	for (indexcol = 0; indexcol < index->ncolumns; indexcol++)
+	{
+		if (match_clause_to_indexcol(index,
+									 indexcol,
+									 rinfo))
+		{
+			clauseset->indexclauses[indexcol] =
+				list_append_unique_ptr(clauseset->indexclauses[indexcol],
+									   rinfo);
+			clauseset->nonempty = true;
+			return;
+		}
+	}
+}
 
 /*
  * match_clause_to_indexcol()
  *	  Determines whether a restriction clause matches a column of an index.
  *
- *	  To match a normal index, the clause:
+ *	  To match an index normally, the clause:
  *
  *	  (1)  must be in the form (indexkey op const) or (const op indexkey);
  *		   and
@@ -1281,18 +1828,17 @@ match_clauses_to_index(IndexOptInfo *index,
  *		   and
  *	  (3)  must match the collation of the index, if collation is relevant.
  *
- *	  Our definition of "const" is pretty liberal: we allow Vars belonging
- *	  to the caller-specified outer_relids relations (which had better not
- *	  include the relation whose index is being tested).  outer_relids should
- *	  be NULL when checking simple restriction clauses, and the outer side
- *	  of the join when building a join inner scan.	Other than that, the
- *	  only thing we don't like is volatile functions.
+ *	  Our definition of "const" is exceedingly liberal: we allow anything that
+ *	  doesn't involve a volatile function or a Var of the index's relation.
+ *	  In particular, Vars belonging to other relations of the query are
+ *	  accepted here, since a clause of that form can be used in a
+ *	  parameterized indexscan.  It's the responsibility of higher code levels
+ *	  to manage restriction and join clauses appropriately.
  *
- *	  Note: in most cases we already know that the clause as a whole uses
- *	  vars from the interesting set of relations.  The reason for the
- *	  outer_relids test is to reject clauses like (a.f1 OP (b.f2 OP a.f3));
- *	  that's not processable by an indexscan nestloop join on A, whereas
- *	  (a.f1 OP (b.f2 OP c.f3)) is.
+ *	  Note: we do need to check for Vars of the index's relation on the
+ *	  "const" side of the clause, since clauses like (a.f1 OP (b.f2 OP a.f3))
+ *	  are not processable by a parameterized indexscan on a.f1, whereas
+ *	  something like (a.f1 OP (b.f2 OP c.f3)) is.
  *
  *	  Presently, the executor can only deal with indexquals that have the
  *	  indexkey on the left, so we can only use clauses that have the indexkey
@@ -1316,10 +1862,7 @@ match_clauses_to_index(IndexOptInfo *index,
  *	  adjust_rowcompare_for_index().
  *
  *	  It is also possible to match ScalarArrayOpExpr clauses to indexes, when
- *	  the clause is of the form "indexkey op ANY (arrayconst)".  Since not
- *	  all indexes handle these natively, and the executor implements them
- *	  only in the context of bitmap index scans, our caller specifies whether
- *	  to allow these or not.
+ *	  the clause is of the form "indexkey op ANY (arrayconst)".
  *
  *	  For boolean indexes, it is also possible to match the clause directly
  *	  to the indexkey; or perhaps the clause is (NOT indexkey).
@@ -1327,8 +1870,6 @@ match_clauses_to_index(IndexOptInfo *index,
  * 'index' is the index of interest.
  * 'indexcol' is a column number of 'index' (counting from 0).
  * 'rinfo' is the clause to be tested (as a RestrictInfo node).
- * 'outer_relids' lists rels whose Vars can be considered pseudoconstant.
- * 'saop_control' indicates whether ScalarArrayOpExpr clauses can be used.
  *
  * Returns true if the clause can be used with this index key.
  *
@@ -1338,11 +1879,10 @@ match_clauses_to_index(IndexOptInfo *index,
 static bool
 match_clause_to_indexcol(IndexOptInfo *index,
 						 int indexcol,
-						 RestrictInfo *rinfo,
-						 Relids outer_relids,
-						 SaOpControl saop_control)
+						 RestrictInfo *rinfo)
 {
 	Expr	   *clause = rinfo->clause;
+	Index		index_relid = index->rel->relid;
 	Oid			opfamily = index->opfamily[indexcol];
 	Oid			idxcollation = index->indexcollations[indexcol];
 	Node	   *leftop,
@@ -1387,8 +1927,7 @@ match_clause_to_indexcol(IndexOptInfo *index,
 		expr_coll = ((OpExpr *) clause)->inputcollid;
 		plain_op = true;
 	}
-	else if (clause && IsA(clause, ScalarArrayOpExpr) &&
-			 (index->amsearcharray || saop_control != SAOP_PER_AM))
+	else if (clause && IsA(clause, ScalarArrayOpExpr))
 	{
 		ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
 
@@ -1407,8 +1946,7 @@ match_clause_to_indexcol(IndexOptInfo *index,
 	{
 		return match_rowcompare_to_indexcol(index, indexcol,
 											opfamily, idxcollation,
-											(RowCompareExpr *) clause,
-											outer_relids);
+											(RowCompareExpr *) clause);
 	}
 	else if (index->amsearchnulls && IsA(clause, NullTest))
 	{
@@ -1427,7 +1965,7 @@ match_clause_to_indexcol(IndexOptInfo *index,
 	 * (constant operator indexkey).  See above notes about const-ness.
 	 */
 	if (match_index_to_operand(leftop, indexcol, index) &&
-		bms_is_subset(right_relids, outer_relids) &&
+		!bms_is_member(index_relid, right_relids) &&
 		!contain_volatile_functions(rightop))
 	{
 		if (IndexCollMatchesExprColl(idxcollation, expr_coll) &&
@@ -1439,14 +1977,15 @@ match_clause_to_indexcol(IndexOptInfo *index,
 		 * is a "special" indexable operator.
 		 */
 		if (plain_op &&
-		  match_special_index_operator(clause, opfamily, idxcollation, true))
+			match_special_index_operator(clause, opfamily,
+										 idxcollation, true))
 			return true;
 		return false;
 	}
 
 	if (plain_op &&
 		match_index_to_operand(rightop, indexcol, index) &&
-		bms_is_subset(left_relids, outer_relids) &&
+		!bms_is_member(index_relid, left_relids) &&
 		!contain_volatile_functions(leftop))
 	{
 		if (IndexCollMatchesExprColl(idxcollation, expr_coll) &&
@@ -1457,7 +1996,8 @@ match_clause_to_indexcol(IndexOptInfo *index,
 		 * If we didn't find a member of the index's opfamily, see whether it
 		 * is a "special" indexable operator.
 		 */
-		if (match_special_index_operator(clause, opfamily, idxcollation, false))
+		if (match_special_index_operator(clause, opfamily,
+										 idxcollation, false))
 			return true;
 		return false;
 	}
@@ -1498,9 +2038,9 @@ match_rowcompare_to_indexcol(IndexOptInfo *index,
 							 int indexcol,
 							 Oid opfamily,
 							 Oid idxcollation,
-							 RowCompareExpr *clause,
-							 Relids outer_relids)
+							 RowCompareExpr *clause)
 {
+	Index		index_relid = index->rel->relid;
 	Node	   *leftop,
 			   *rightop;
 	Oid			expr_op;
@@ -1533,13 +2073,13 @@ match_rowcompare_to_indexcol(IndexOptInfo *index,
 	 * These syntactic tests are the same as in match_clause_to_indexcol()
 	 */
 	if (match_index_to_operand(leftop, indexcol, index) &&
-		bms_is_subset(pull_varnos(rightop), outer_relids) &&
+		!bms_is_member(index_relid, pull_varnos(rightop)) &&
 		!contain_volatile_functions(rightop))
 	{
 		/* OK, indexkey is on left */
 	}
 	else if (match_index_to_operand(rightop, indexcol, index) &&
-			 bms_is_subset(pull_varnos(leftop), outer_relids) &&
+			 !bms_is_member(index_relid, pull_varnos(leftop)) &&
 			 !contain_volatile_functions(leftop))
 	{
 		/* indexkey is on right, so commute the operator */
@@ -1800,484 +2340,41 @@ check_partial_indexes(PlannerInfo *root, RelOptInfo *rel)
 }
 
 /****************************************************************************
- *				----  ROUTINES TO CHECK JOIN CLAUSES  ----
+ *				----  ROUTINES TO CHECK EXTERNALLY-VISIBLE CONDITIONS  ----
  ****************************************************************************/
 
 /*
- * indexable_outerrelids
- *	  Finds all other relids that participate in any indexable join clause
- *	  for the specified table.	Returns a set of relids.
- */
-static Relids
-indexable_outerrelids(PlannerInfo *root, RelOptInfo *rel)
-{
-	Relids		outer_relids = NULL;
-	bool		is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
-	ListCell   *lc1;
-
-	/*
-	 * Examine each joinclause in the joininfo list to see if it matches any
-	 * key of any index.  If so, add the clause's other rels to the result.
-	 */
-	foreach(lc1, rel->joininfo)
-	{
-		RestrictInfo *joininfo = (RestrictInfo *) lfirst(lc1);
-		Relids		other_rels;
-
-		other_rels = bms_difference(joininfo->required_relids, rel->relids);
-		if (matches_any_index(joininfo, rel, other_rels))
-			outer_relids = bms_join(outer_relids, other_rels);
-		else
-			bms_free(other_rels);
-	}
-
-	/*
-	 * We also have to look through the query's EquivalenceClasses to see if
-	 * any of them could generate indexable join conditions for this rel.
-	 */
-	if (rel->has_eclass_joins)
-	{
-		foreach(lc1, root->eq_classes)
-		{
-			EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
-			Relids		other_rels = NULL;
-			bool		found_index = false;
-			ListCell   *lc2;
-
-			/*
-			 * Won't generate joinclauses if const or single-member (the
-			 * latter test covers the volatile case too)
-			 */
-			if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
-				continue;
-
-			/*
-			 * Note we don't test ec_broken; if we did, we'd need a separate
-			 * code path to look through ec_sources.  Checking the members
-			 * anyway is OK as a possibly-overoptimistic heuristic.
-			 */
-
-			/*
-			 * No point in searching if rel not mentioned in eclass (but we
-			 * can't tell that for a child rel).
-			 */
-			if (!is_child_rel &&
-				!bms_is_subset(rel->relids, cur_ec->ec_relids))
-				continue;
-
-			/*
-			 * Scan members, looking for both an index match and join
-			 * candidates
-			 */
-			foreach(lc2, cur_ec->ec_members)
-			{
-				EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
-
-				/* Join candidate? */
-				if (!cur_em->em_is_child &&
-					!bms_overlap(cur_em->em_relids, rel->relids))
-				{
-					other_rels = bms_add_members(other_rels,
-												 cur_em->em_relids);
-					continue;
-				}
-
-				/* Check for index match (only need one) */
-				if (!found_index &&
-					bms_equal(cur_em->em_relids, rel->relids) &&
-					eclass_matches_any_index(cur_ec, cur_em, rel))
-					found_index = true;
-			}
-
-			if (found_index)
-				outer_relids = bms_join(outer_relids, other_rels);
-			else
-				bms_free(other_rels);
-		}
-	}
-
-	return outer_relids;
-}
-
-/*
- * matches_any_index
- *	  Workhorse for indexable_outerrelids: see if a joinclause can be
- *	  matched to any index of the given rel.
- */
-static bool
-matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel, Relids outer_relids)
-{
-	ListCell   *l;
-
-	Assert(IsA(rinfo, RestrictInfo));
-
-	if (restriction_is_or_clause(rinfo))
-	{
-		foreach(l, ((BoolExpr *) rinfo->orclause)->args)
-		{
-			Node	   *orarg = (Node *) lfirst(l);
-
-			/* OR arguments should be ANDs or sub-RestrictInfos */
-			if (and_clause(orarg))
-			{
-				ListCell   *j;
-
-				/* Recurse to examine AND items and sub-ORs */
-				foreach(j, ((BoolExpr *) orarg)->args)
-				{
-					RestrictInfo *arinfo = (RestrictInfo *) lfirst(j);
-
-					if (matches_any_index(arinfo, rel, outer_relids))
-						return true;
-				}
-			}
-			else
-			{
-				/* Recurse to examine simple clause */
-				Assert(IsA(orarg, RestrictInfo));
-				Assert(!restriction_is_or_clause((RestrictInfo *) orarg));
-				if (matches_any_index((RestrictInfo *) orarg, rel,
-									  outer_relids))
-					return true;
-			}
-		}
-
-		return false;
-	}
-
-	/* Normal case for a simple restriction clause */
-	foreach(l, rel->indexlist)
-	{
-		IndexOptInfo *index = (IndexOptInfo *) lfirst(l);
-		int			indexcol;
-
-		for (indexcol = 0; indexcol < index->ncolumns; indexcol++)
-		{
-			if (match_clause_to_indexcol(index,
-										 indexcol,
-										 rinfo,
-										 outer_relids,
-										 SAOP_ALLOW))
-				return true;
-		}
-	}
-
-	return false;
-}
-
-/*
- * eclass_matches_any_index
- *	  Workhorse for indexable_outerrelids: see if an EquivalenceClass member
- *	  can be matched to any index column of the given rel.
+ * eclass_member_matches_indexcol
+ *	  Test whether an EquivalenceClass member matches an index column.
  *
- * This is also exported for use by find_eclass_clauses_for_index_join.
+ * This is exported for use by generate_implied_equalities_for_indexcol.
  */
 bool
-eclass_matches_any_index(EquivalenceClass *ec, EquivalenceMember *em,
-						 RelOptInfo *rel)
+eclass_member_matches_indexcol(EquivalenceClass *ec, EquivalenceMember *em,
+							   IndexOptInfo *index, int indexcol)
 {
-	ListCell   *l;
-
-	foreach(l, rel->indexlist)
-	{
-		IndexOptInfo *index = (IndexOptInfo *) lfirst(l);
-		int			indexcol;
-
-		for (indexcol = 0; indexcol < index->ncolumns; indexcol++)
-		{
-			Oid			curFamily = index->opfamily[indexcol];
-			Oid			curCollation = index->indexcollations[indexcol];
-
-			/*
-			 * If it's a btree index, we can reject it if its opfamily isn't
-			 * compatible with the EC, since no clause generated from the EC
-			 * could be used with the index.  For non-btree indexes, we can't
-			 * easily tell whether clauses generated from the EC could be used
-			 * with the index, so only check for expression match.	This might
-			 * mean we return "true" for a useless index, but that will just
-			 * cause some wasted planner cycles; it's better than ignoring
-			 * useful indexes.
-			 *
-			 * We insist on collation match for all index types, though.
-			 */
-			if ((index->relam != BTREE_AM_OID ||
-				 list_member_oid(ec->ec_opfamilies, curFamily)) &&
-				IndexCollMatchesExprColl(curCollation, ec->ec_collation) &&
-				match_index_to_operand((Node *) em->em_expr, indexcol, index))
-				return true;
-		}
-	}
-
-	return false;
-}
-
-
-/*
- * best_inner_indexscan
- *	  Finds the best available inner indexscans for a nestloop join
- *	  with the given rel on the inside and the given outer_rel outside.
- *
- * *cheapest_startup gets the path with least startup cost
- * *cheapest_total gets the path with least total cost (often the same path)
- * Both are set to NULL if there are no possible inner indexscans.
- *
- * We ignore ordering considerations, since a nestloop's inner scan's order
- * is uninteresting.  Hence startup cost and total cost are the only figures
- * of merit to consider.
- *
- * Note: create_index_paths() must have been run previously for this rel,
- * else the results will always be NULL.
- */
-void
-best_inner_indexscan(PlannerInfo *root, RelOptInfo *rel,
-					 RelOptInfo *outer_rel, JoinType jointype,
-					 Path **cheapest_startup, Path **cheapest_total)
-{
-	Relids		outer_relids;
-	bool		isouterjoin;
-	List	   *clause_list;
-	List	   *indexpaths;
-	List	   *bitindexpaths;
-	List	   *allindexpaths;
-	ListCell   *l;
-	InnerIndexscanInfo *info;
-	MemoryContext oldcontext;
-
-	/* Initialize results for failure returns */
-	*cheapest_startup = *cheapest_total = NULL;
-
-	/*
-	 * Nestloop only supports inner, left, semi, and anti joins.
-	 */
-	switch (jointype)
-	{
-		case JOIN_INNER:
-		case JOIN_SEMI:
-			isouterjoin = false;
-			break;
-		case JOIN_LEFT:
-		case JOIN_ANTI:
-			isouterjoin = true;
-			break;
-		default:
-			return;
-	}
-
-	/*
-	 * If there are no indexable joinclauses for this rel, exit quickly.
-	 */
-	if (bms_is_empty(rel->index_outer_relids))
-		return;
+	Oid			curFamily = index->opfamily[indexcol];
+	Oid			curCollation = index->indexcollations[indexcol];
 
 	/*
-	 * Otherwise, we have to do path selection in the main planning context,
-	 * so that any created path can be safely attached to the rel's cache of
-	 * best inner paths.  (This is not currently an issue for normal planning,
-	 * but it is an issue for GEQO planning.)
+	 * If it's a btree index, we can reject it if its opfamily isn't
+	 * compatible with the EC, since no clause generated from the EC could be
+	 * used with the index.  For non-btree indexes, we can't easily tell
+	 * whether clauses generated from the EC could be used with the index,
+	 * so don't check the opfamily.  This might mean we return "true" for a
+	 * useless EC, so we have to recheck the results of
+	 * generate_implied_equalities_for_indexcol; see
+	 * match_eclass_clauses_to_index.
 	 */
-	oldcontext = MemoryContextSwitchTo(root->planner_cxt);
-
-	/*
-	 * Intersect the given outer relids with index_outer_relids to find the
-	 * set of outer relids actually relevant for this rel. If there are none,
-	 * again we can fail immediately.
-	 */
-	outer_relids = bms_intersect(rel->index_outer_relids, outer_rel->relids);
-	if (bms_is_empty(outer_relids))
-	{
-		bms_free(outer_relids);
-		MemoryContextSwitchTo(oldcontext);
-		return;
-	}
-
-	/*
-	 * Look to see if we already computed the result for this set of relevant
-	 * outerrels.  (We include the isouterjoin status in the cache lookup key
-	 * for safety.	In practice I suspect this is not necessary because it
-	 * should always be the same for a given combination of rels.)
-	 *
-	 * NOTE: because we cache on outer_relids rather than outer_rel->relids,
-	 * we will report the same paths and hence path cost for joins with
-	 * different sets of irrelevant rels on the outside.  Now that cost_index
-	 * is sensitive to outer_rel->rows, this is not really right.  However the
-	 * error is probably not large.  Is it worth establishing a separate cache
-	 * entry for each distinct outer_rel->relids set to get this right?
-	 */
-	foreach(l, rel->index_inner_paths)
-	{
-		info = (InnerIndexscanInfo *) lfirst(l);
-		if (bms_equal(info->other_relids, outer_relids) &&
-			info->isouterjoin == isouterjoin)
-		{
-			bms_free(outer_relids);
-			MemoryContextSwitchTo(oldcontext);
-			*cheapest_startup = info->cheapest_startup_innerpath;
-			*cheapest_total = info->cheapest_total_innerpath;
-			return;
-		}
-	}
-
-	/*
-	 * Find all the relevant restriction and join clauses.
-	 *
-	 * Note: because we include restriction clauses, we will find indexscans
-	 * that could be plain indexscans, ie, they don't require the join context
-	 * at all.	This may seem redundant, but we need to include those scans in
-	 * the input given to choose_bitmap_and() to be sure we find optimal AND
-	 * combinations of join and non-join scans.  Also, even if the "best inner
-	 * indexscan" is just a plain indexscan, it will have a different cost
-	 * estimate because of cache effects.
-	 */
-	clause_list = find_clauses_for_join(root, rel, outer_relids, isouterjoin);
-
-	/*
-	 * Find all the index paths that are usable for this join, except for
-	 * stuff involving OR and executor-managed ScalarArrayOpExpr clauses.
-	 */
-	allindexpaths = find_usable_indexes(root, rel,
-										clause_list, NIL,
-										false, outer_rel,
-										SAOP_PER_AM,
-										ST_ANYSCAN);
-
-	/*
-	 * Include the ones that are usable as plain indexscans in indexpaths, and
-	 * include the ones that are usable as bitmap scans in bitindexpaths.
-	 */
-	indexpaths = bitindexpaths = NIL;
-	foreach(l, allindexpaths)
-	{
-		IndexPath  *ipath = (IndexPath *) lfirst(l);
-
-		if (ipath->indexinfo->amhasgettuple)
-			indexpaths = lappend(indexpaths, ipath);
-
-		if (ipath->indexinfo->amhasgetbitmap)
-			bitindexpaths = lappend(bitindexpaths, ipath);
-	}
-
-	/*
-	 * Generate BitmapOrPaths for any suitable OR-clauses present in the
-	 * clause list.
-	 */
-	bitindexpaths = list_concat(bitindexpaths,
-								generate_bitmap_or_paths(root, rel,
-														 clause_list, NIL,
-														 outer_rel));
-
-	/*
-	 * Likewise, generate paths using executor-managed ScalarArrayOpExpr
-	 * clauses; these can't be simple indexscans but they can be used in
-	 * bitmap scans.
-	 */
-	bitindexpaths = list_concat(bitindexpaths,
-								find_saop_paths(root, rel,
-												clause_list, NIL,
-												false, outer_rel));
-
-	/*
-	 * If we found anything usable, generate a BitmapHeapPath for the most
-	 * promising combination of bitmap index paths.
-	 */
-	if (bitindexpaths != NIL)
-	{
-		Path	   *bitmapqual;
-		BitmapHeapPath *bpath;
-
-		bitmapqual = choose_bitmap_and(root, rel, bitindexpaths, outer_rel);
-		bpath = create_bitmap_heap_path(root, rel, bitmapqual, outer_rel);
-		indexpaths = lappend(indexpaths, bpath);
-	}
-
-	/*
-	 * Now choose the cheapest members of indexpaths.
-	 */
-	if (indexpaths != NIL)
-	{
-		*cheapest_startup = *cheapest_total = (Path *) linitial(indexpaths);
-
-		for_each_cell(l, lnext(list_head(indexpaths)))
-		{
-			Path	   *path = (Path *) lfirst(l);
-
-			if (compare_path_costs(path, *cheapest_startup, STARTUP_COST) < 0)
-				*cheapest_startup = path;
-			if (compare_path_costs(path, *cheapest_total, TOTAL_COST) < 0)
-				*cheapest_total = path;
-		}
-	}
-
-	/* Cache the results --- whether positive or negative */
-	info = makeNode(InnerIndexscanInfo);
-	info->other_relids = outer_relids;
-	info->isouterjoin = isouterjoin;
-	info->cheapest_startup_innerpath = *cheapest_startup;
-	info->cheapest_total_innerpath = *cheapest_total;
-	rel->index_inner_paths = lcons(info, rel->index_inner_paths);
-
-	MemoryContextSwitchTo(oldcontext);
-}
-
-/*
- * find_clauses_for_join
- *	  Generate a list of clauses that are potentially useful for
- *	  scanning rel as the inner side of a nestloop join.
- *
- * We consider both join and restriction clauses.  Any joinclause that uses
- * only otherrels in the specified outer_relids is fair game.  But there must
- * be at least one such joinclause in the final list, otherwise we return NIL
- * indicating that there isn't any potential win here.
- */
-static List *
-find_clauses_for_join(PlannerInfo *root, RelOptInfo *rel,
-					  Relids outer_relids, bool isouterjoin)
-{
-	List	   *clause_list = NIL;
-	Relids		join_relids;
-	ListCell   *l;
-
-	/*
-	 * Look for joinclauses that are usable with given outer_relids.  Note
-	 * we'll take anything that's applicable to the join whether it has
-	 * anything to do with an index or not; since we're only building a list,
-	 * it's not worth filtering more finely here.
-	 */
-	join_relids = bms_union(rel->relids, outer_relids);
-
-	foreach(l, rel->joininfo)
-	{
-		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
-
-		/* Can't use pushed-down join clauses in outer join */
-		if (isouterjoin && rinfo->is_pushed_down)
-			continue;
-		if (!bms_is_subset(rinfo->required_relids, join_relids))
-			continue;
-
-		clause_list = lappend(clause_list, rinfo);
-	}
-
-	bms_free(join_relids);
-
-	/*
-	 * Also check to see if any EquivalenceClasses can produce a relevant
-	 * joinclause.	Since all such clauses are effectively pushed-down, this
-	 * doesn't apply to outer joins.
-	 */
-	if (!isouterjoin && rel->has_eclass_joins)
-		clause_list = list_concat(clause_list,
-								  find_eclass_clauses_for_index_join(root,
-																	 rel,
-															  outer_relids));
-
-	/* If no join clause was matched then forget it, per comments above */
-	if (clause_list == NIL)
-		return NIL;
+	if (index->relam == BTREE_AM_OID &&
+		!list_member_oid(ec->ec_opfamilies, curFamily))
+		return false;
 
-	/* We can also use any plain restriction clauses for the rel */
-	clause_list = list_concat(list_copy(rel->baserestrictinfo), clause_list);
+	/* We insist on collation match for all index types, though */
+	if (!IndexCollMatchesExprColl(curCollation, ec->ec_collation))
+		return false;
 
-	return clause_list;
+	return match_index_to_operand((Node *) em->em_expr, indexcol, index);
 }
 
 /*
@@ -2473,6 +2570,8 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
  *
  * Note that we aren't interested in collations here; the caller must check
  * for a collation match, if it's dealing with an operator where that matters.
+ *
+ * This is exported for use in selfuncs.c.
  */
 bool
 match_index_to_operand(Node *operand,
@@ -2543,7 +2642,7 @@ match_index_to_operand(Node *operand,
  *			----  ROUTINES FOR "SPECIAL" INDEXABLE OPERATORS  ----
  ****************************************************************************/
 
-/*----------
+/*
  * These routines handle special optimization of operators that can be
  * used with index scans even though they are not known to the executor's
  * indexscan machinery.  The key idea is that these operators allow us
@@ -2590,7 +2689,6 @@ match_index_to_operand(Node *operand,
  * the index's opfamily this transformation is a no-op, but clauses recognized
  * by match_special_index_operator() or match_boolean_index_clause() must be
  * converted into one or more "regular" indexqual conditions.
- *----------
  */
 
 /*
@@ -3168,9 +3266,7 @@ adjust_rowcompare_for_index(RowCompareExpr *clause,
 
 	/*
 	 * See how many of the remaining columns match some index column in the
-	 * same way.  A note about rel membership tests: we assume that the clause
-	 * as a whole is already known to use only Vars from the indexed relation
-	 * and possibly some acceptable outer relations. So the "other" side of
+	 * same way.  As in match_clause_to_indexcol(), the "other" side of
 	 * any potential index condition is OK as long as it doesn't use Vars from
 	 * the indexed relation.
 	 */