diff options
Diffstat (limited to 'src/backend/optimizer/path/indxpath.c')
| -rw-r--r-- | src/backend/optimizer/path/indxpath.c | 1998 |
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. */ |