diff options
22 files changed, 1015 insertions, 586 deletions
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c index e26406365de..7e8d2db677b 100644 --- a/src/backend/commands/explain.c +++ b/src/backend/commands/explain.c @@ -7,7 +7,7 @@ * Portions Copyright (c) 1994-5, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/commands/explain.c,v 1.133 2005/04/19 22:35:10 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/commands/explain.c,v 1.134 2005/04/22 21:58:31 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -847,9 +847,14 @@ explain_outNode(StringInfo str, for (i = 0; i < indent; i++) appendStringInfo(str, " "); appendStringInfo(str, " -> "); + /* + * Ordinarily we don't pass down our own outer_plan value to our + * child nodes, but in bitmap scan trees we must, since the bottom + * BitmapIndexScan nodes may have outer references. + */ explain_outNode(str, outerPlan(plan), outerPlanState(planstate), - NULL, + IsA(plan, BitmapHeapScan) ? outer_plan : NULL, indent + 3, es); } @@ -907,7 +912,7 @@ explain_outNode(StringInfo str, explain_outNode(str, subnode, bitmapandstate->bitmapplans[j], - NULL, + outer_plan, /* pass down same outer plan */ indent + 3, es); j++; } @@ -931,7 +936,7 @@ explain_outNode(StringInfo str, explain_outNode(str, subnode, bitmaporstate->bitmapplans[j], - NULL, + outer_plan, /* pass down same outer plan */ indent + 3, es); j++; } diff --git a/src/backend/executor/nodeBitmapIndexscan.c b/src/backend/executor/nodeBitmapIndexscan.c index 0c802ea49b0..c877d69b9be 100644 --- a/src/backend/executor/nodeBitmapIndexscan.c +++ b/src/backend/executor/nodeBitmapIndexscan.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/executor/nodeBitmapIndexscan.c,v 1.2 2005/04/20 15:48:36 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/executor/nodeBitmapIndexscan.c,v 1.3 2005/04/22 21:58:31 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -492,7 +492,8 @@ ExecInitBitmapIndexScan(BitmapIndexScan *node, EState *estate) indexstate->biss_RuntimeKeyInfo = NULL; indexstate->biss_RuntimeContext = NULL; /* Get rid of the speculatively-allocated flag array, too */ - pfree(runtimeKeyInfo); + if (runtimeKeyInfo) + pfree(runtimeKeyInfo); } /* diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 2afaa2a655e..c721a85d880 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -49,7 +49,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.144 2005/04/21 19:18:12 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.145 2005/04/22 21:58:31 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -104,7 +104,6 @@ bool enable_hashjoin = true; static bool cost_qual_eval_walker(Node *node, QualCost *total); -static void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec); static Selectivity approx_selectivity(Query *root, List *quals, JoinType jointype); static Selectivity join_in_selectivity(JoinPath *path, Query *root); @@ -474,8 +473,11 @@ cost_bitmap_heap_scan(Path *path, Query *root, RelOptInfo *baserel, * For lack of a better idea, interpolate like this to determine the * cost per page. */ - cost_per_page = random_page_cost - - (random_page_cost - 1.0) * sqrt(pages_fetched / T); + if (pages_fetched >= 2.0) + cost_per_page = random_page_cost - + (random_page_cost - 1.0) * sqrt(pages_fetched / T); + else + cost_per_page = random_page_cost; run_cost += pages_fetched * cost_per_page; @@ -500,7 +502,7 @@ cost_bitmap_heap_scan(Path *path, Query *root, RelOptInfo *baserel, * cost_bitmap_tree_node * Extract cost and selectivity from a bitmap tree node (index/and/or) */ -static void +void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec) { if (IsA(path, IndexPath)) diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index e387a7bd768..faf410c9556 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -1,15 +1,15 @@ /*------------------------------------------------------------------------- * * indxpath.c - * Routines to determine which indices are usable for scanning a - * given relation, and create IndexPaths accordingly. + * Routines to determine which indexes are usable for scanning a + * given relation, and create Paths accordingly. * * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.175 2005/04/21 02:28:01 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.176 2005/04/22 21:58:31 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -54,23 +54,30 @@ ((opclass) == BOOL_BTREE_OPS_OID || (opclass) == BOOL_HASH_OPS_OID) -static List *group_clauses_by_indexkey_for_join(Query *root, - IndexOptInfo *index, - Relids outer_relids, - JoinType jointype, bool isouterjoin); +static List *find_usable_indexes(Query *root, RelOptInfo *rel, + List *clauses, List *outer_clauses, + bool istoplevel, bool isjoininner, + Relids outer_relids); +static List *generate_bitmap_or_paths(Query *root, RelOptInfo *rel, + List *clauses, List *outer_clauses, + bool isjoininner, + Relids outer_relids); +static Path *choose_bitmap_and(Query *root, RelOptInfo *rel, List *paths); static bool match_clause_to_indexcol(IndexOptInfo *index, int indexcol, Oid opclass, - RestrictInfo *rinfo); -static bool match_join_clause_to_indexcol(IndexOptInfo *index, - int indexcol, Oid opclass, - RestrictInfo *rinfo); + RestrictInfo *rinfo, + Relids outer_relids); static Oid indexable_operator(Expr *clause, Oid opclass, bool indexkey_on_left); static bool pred_test_recurse(Node *clause, Node *predicate); static bool pred_test_simple_clause(Expr *predicate, Node *clause); -static Relids indexable_outerrelids(IndexOptInfo *index); -static Path *make_innerjoin_index_path(Query *root, IndexOptInfo *index, - List *clausegroups); +static Relids indexable_outerrelids(RelOptInfo *rel); +static bool list_matches_any_index(List *clauses, RelOptInfo *rel, + Relids outer_relids); +static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel, + Relids outer_relids); +static List *find_clauses_for_join(Query *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, Oid opclass, @@ -120,34 +127,168 @@ static Const *string_to_const(const char *str, Oid datatype); void create_index_paths(Query *root, RelOptInfo *rel) { - Relids all_join_outerrelids = NULL; + List *indexpaths; + List *bitindexpaths; + ListCell *l; + + /* Skip the whole mess if no indexes */ + if (rel->indexlist == NIL) + { + rel->index_outer_relids = NULL; + return; + } + + /* + * 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. + */ + rel->index_outer_relids = indexable_outerrelids(rel); + + /* + * Find all the index paths that are directly usable for this relation + * (ie, are valid without considering OR or JOIN clauses). + */ + indexpaths = find_usable_indexes(root, rel, + rel->baserestrictinfo, NIL, + true, false, NULL); + + /* + * We can submit them all to add_path. (This generates access paths for + * plain IndexScan plans.) However, for the next step we will only want + * the ones that have some selectivity; we must discard anything that was + * generated solely for ordering purposes. + */ + bitindexpaths = NIL; + foreach(l, indexpaths) + { + IndexPath *ipath = (IndexPath *) lfirst(l); + + add_path(rel, (Path *) ipath); + + if (ipath->indexselectivity < 1.0 && + !ScanDirectionIsBackward(ipath->indexscandir)) + bitindexpaths = lappend(bitindexpaths, ipath); + } + + /* + * Generate BitmapOrPaths for any suitable OR-clauses present in the + * restriction list. Add these to bitindexpaths. + */ + indexpaths = generate_bitmap_or_paths(root, rel, + rel->baserestrictinfo, NIL, + false, NULL); + bitindexpaths = list_concat(bitindexpaths, indexpaths); + + /* + * 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); + bpath = create_bitmap_heap_path(root, rel, bitmapqual, false); + add_path(rel, (Path *) bpath); + } +} + + +/*---------- + * 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. + * + * The caller actually supplies two lists of restriction clauses: some + * "current" ones and some "outer" 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 + * WHERE (x = 42) AND (... OR (y = 52 AND z = 77) OR ....) + * While we are considering the y/z subclause of the OR, we can use "x = 42" + * as one of the available index conditions; but we shouldn't match the + * subclause to any index on x alone, because such a Path would already have + * been generated at the upper level. So we could use an index on x,y,z + * or an index on x,y for the OR subclause, but not an index on just x. + * + * 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 + * 'isjoininner' is true if forming an inner indexscan (so some of the + * given clauses are join clauses) + * 'outer_relids' identifies the outer side of the join (pass NULL + * if not isjoininner) + * + * Note: check_partial_indexes() must have been run previously. + *---------- + */ +static List * +find_usable_indexes(Query *root, RelOptInfo *rel, + List *clauses, List *outer_clauses, + bool istoplevel, bool isjoininner, + Relids outer_relids) +{ + List *result = NIL; + List *all_clauses = NIL; /* not computed till needed */ ListCell *ilist; foreach(ilist, rel->indexlist) { IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist); + IndexPath *ipath; List *restrictclauses; List *index_pathkeys; List *useful_pathkeys; bool index_is_ordered; - Relids join_outerrelids; - /* Ignore partial indexes that do not match the query */ + /* + * 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. + */ if (index->indpred != NIL && !index->predOK) - continue; + { + 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); + + if (!pred_test(index->indpred, all_clauses) || + pred_test(index->indpred, outer_clauses)) + continue; + } /* - * 1. Match the index against non-OR restriction clauses. (OR - * clauses will be considered later by orindxpath.c.) + * 1. Match the index against the available restriction clauses. */ - restrictclauses = group_clauses_by_indexkey(index); + restrictclauses = group_clauses_by_indexkey(index, + clauses, + outer_clauses, + outer_relids); /* * 2. Compute pathkeys describing index's ordering, if any, then - * see how many of them are actually useful for this query. + * see how many of them are actually useful for this query. This + * is not relevant unless we are at top level. */ index_is_ordered = OidIsValid(index->ordering[0]); - if (index_is_ordered) + if (istoplevel && index_is_ordered && !isjoininner) { index_pathkeys = build_index_pathkeys(root, index, ForwardScanDirection); @@ -174,48 +315,174 @@ create_index_paths(Query *root, RelOptInfo *rel) if (restrictclauses != NIL || useful_pathkeys != NIL || (index->indpred != NIL && index_is_ordered)) - add_path(rel, (Path *) - create_index_path(root, index, - restrictclauses, - useful_pathkeys, - index_is_ordered ? - ForwardScanDirection : - NoMovementScanDirection)); + { + ipath = create_index_path(root, index, + restrictclauses, + useful_pathkeys, + index_is_ordered ? + ForwardScanDirection : + NoMovementScanDirection, + isjoininner); + result = lappend(result, ipath); + } /* * 4. If the index is ordered, a backwards scan might be * interesting. Currently this is only possible for a DESC query * result ordering. */ - if (index_is_ordered) + if (istoplevel && index_is_ordered && !isjoininner) { index_pathkeys = build_index_pathkeys(root, index, BackwardScanDirection); useful_pathkeys = truncate_useless_pathkeys(root, rel, index_pathkeys); if (useful_pathkeys != NIL) - add_path(rel, (Path *) - create_index_path(root, index, - restrictclauses, - useful_pathkeys, - BackwardScanDirection)); + { + ipath = create_index_path(root, index, + restrictclauses, + useful_pathkeys, + BackwardScanDirection, + false); + result = lappend(result, ipath); + } } + } + + return result; +} + + +/* + * 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 + * for the purpose of generating indexquals, but are not to be searched for + * ORs. (See find_usable_indexes() for motivation.) + */ +static List * +generate_bitmap_or_paths(Query *root, RelOptInfo *rel, + List *clauses, List *outer_clauses, + bool isjoininner, + Relids outer_relids) +{ + List *result = NIL; + List *all_clauses; + ListCell *l; + + /* + * We can use both the current and outer clauses as context for + * find_usable_indexes + */ + all_clauses = list_concat(list_copy(clauses), outer_clauses); + + foreach(l, clauses) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); + List *pathlist; + Path *bitmapqual; + ListCell *j; + + Assert(IsA(rinfo, RestrictInfo)); + /* Ignore RestrictInfos that aren't ORs */ + if (!restriction_is_or_clause(rinfo)) + continue; /* - * 5. Examine join clauses to see which ones are potentially - * usable with this index, 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. We compute both per-index and - * overall-for-relation sets. + * We must be able to match at least one index to each of the arms + * of the OR, else we can't use it. */ - join_outerrelids = indexable_outerrelids(index); - index->outer_relids = join_outerrelids; - all_join_outerrelids = bms_add_members(all_join_outerrelids, - join_outerrelids); + pathlist = NIL; + foreach(j, ((BoolExpr *) rinfo->orclause)->args) + { + Node *orarg = (Node *) lfirst(j); + List *indlist; + + /* OR arguments should be ANDs or sub-RestrictInfos */ + if (and_clause(orarg)) + { + List *andargs = ((BoolExpr *) orarg)->args; + + indlist = find_usable_indexes(root, rel, + andargs, + all_clauses, + false, + isjoininner, + outer_relids); + /* Recurse in case there are sub-ORs */ + indlist = list_concat(indlist, + generate_bitmap_or_paths(root, rel, + andargs, + all_clauses, + isjoininner, + outer_relids)); + } + else + { + Assert(IsA(orarg, RestrictInfo)); + Assert(!restriction_is_or_clause((RestrictInfo *) orarg)); + indlist = find_usable_indexes(root, rel, + list_make1(orarg), + all_clauses, + false, + isjoininner, + outer_relids); + } + /* + * If nothing matched this arm, we can't do anything + * with this OR clause. + */ + if (indlist == NIL) + { + pathlist = NIL; + break; + } + /* + * OK, pick the most promising AND combination, + * and add it to pathlist. + */ + bitmapqual = choose_bitmap_and(root, rel, indlist); + pathlist = lappend(pathlist, bitmapqual); + } + /* + * If we have a match for every arm, then turn them + * into a BitmapOrPath, and add to result list. + */ + if (pathlist != NIL) + { + bitmapqual = (Path *) create_bitmap_or_path(root, rel, pathlist); + result = lappend(result, bitmapqual); + } } - rel->index_outer_relids = all_join_outerrelids; + return result; +} + + +/* + * choose_bitmap_and + * Given a nonempty list of bitmap paths, AND them into one path. + * + * This is a nontrivial decision since we can legally use any subset of the + * given path set. We want to choose a good tradeoff between selectivity + * and cost of computing the bitmap. + * + * The result is either a single one of the inputs, or a BitmapAndPath + * combining multiple inputs. + */ +static Path * +choose_bitmap_and(Query *root, RelOptInfo *rel, List *paths) +{ + Assert(paths != NIL); /* else caller error */ + if (list_length(paths) == 1) + return (Path *) linitial(paths); /* easy case */ + /* + * XXX temporary stopgap: always use all available paths + */ + return (Path *) create_bitmap_and_path(root, rel, paths); } @@ -228,6 +495,14 @@ create_index_paths(Query *root, RelOptInfo *rel) * group_clauses_by_indexkey * Find restriction clauses that can be used with an index. * + * As explained in the comments for find_usable_indexes(), we can use + * clauses from either of the given lists, but the result is required to + * use at least one clause from the "current clauses" list. We return + * NIL if we don't find any such clause. + * + * outer_relids determines what Vars will be allowed on the other side + * of a possible index qual; see match_clause_to_indexcol(). + * * Returns a list of sublists of RestrictInfo nodes for clauses that can be * used with this index. Each sublist contains clauses that can be used * with one index key (in no particular order); the top list is ordered by @@ -242,15 +517,17 @@ create_index_paths(Query *root, RelOptInfo *rel) * Therefore, there are no empty sublists in the result. */ List * -group_clauses_by_indexkey(IndexOptInfo *index) +group_clauses_by_indexkey(IndexOptInfo *index, + List *clauses, List *outer_clauses, + Relids outer_relids) { List *clausegroup_list = NIL; - List *restrictinfo_list = index->rel->baserestrictinfo; + bool found_clause = false; int indexcol = 0; Oid *classes = index->classlist; - if (restrictinfo_list == NIL) - return NIL; + if (clauses == NIL) + return NIL; /* cannot succeed */ do { @@ -258,135 +535,37 @@ group_clauses_by_indexkey(IndexOptInfo *index) List *clausegroup = NIL; ListCell *l; - foreach(l, restrictinfo_list) + /* check the current clauses */ + foreach(l, clauses) { RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); + Assert(IsA(rinfo, RestrictInfo)); if (match_clause_to_indexcol(index, indexcol, curClass, - rinfo)) + rinfo, + outer_relids)) + { clausegroup = lappend(clausegroup, rinfo); + found_clause = true; + } } - /* - * If no clauses match this key, we're done; we don't want to look - * at keys to its right. - */ - if (clausegroup == NIL) - break; - - clausegroup_list = lappend(clausegroup_list, clausegroup); - - indexcol++; - classes++; - - } while (!DoneMatchingIndexKeys(classes)); - - return clausegroup_list; -} - -/* - * group_clauses_by_indexkey_for_join - * Generate a list of sublists of clauses that can be used with an index - * to scan the inner side of a nestloop join. - * - * This is much like group_clauses_by_indexkey(), but 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 this index isn't interesting as an inner indexscan. (A scan using - * only restriction clauses shouldn't be created here, because a regular Path - * will already have been generated for it.) - */ -static List * -group_clauses_by_indexkey_for_join(Query *root, IndexOptInfo *index, - Relids outer_relids, - JoinType jointype, bool isouterjoin) -{ - List *clausegroup_list = NIL; - bool jfound = false; - int indexcol = 0; - Oid *classes = index->classlist; - - do - { - Oid curClass = classes[0]; - List *clausegroup = NIL; - int numsources; - ListCell *l; - - /* - * We can always use plain restriction clauses for the rel. We - * scan these first because we want them first in the clausegroup - * list for the convenience of remove_redundant_join_clauses, - * which can never remove non-join clauses and hence won't be able - * to get rid of a non-join clause if it appears after a join - * clause it is redundant with. - */ - foreach(l, index->rel->baserestrictinfo) + /* check the outer clauses */ + foreach(l, outer_clauses) { RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); - /* Can't use pushed-down clauses in outer join */ - if (isouterjoin && rinfo->is_pushed_down) - continue; - + Assert(IsA(rinfo, RestrictInfo)); if (match_clause_to_indexcol(index, indexcol, curClass, - rinfo)) + rinfo, + outer_relids)) clausegroup = lappend(clausegroup, rinfo); } - /* found anything in base restrict list? */ - numsources = (clausegroup != NIL) ? 1 : 0; - - /* Look for joinclauses that are usable with given outer_relids */ - foreach(l, index->rel->joininfo) - { - JoinInfo *joininfo = (JoinInfo *) lfirst(l); - bool jfoundhere = false; - ListCell *j; - - if (!bms_is_subset(joininfo->unjoined_relids, outer_relids)) - continue; - - foreach(j, joininfo->jinfo_restrictinfo) - { - RestrictInfo *rinfo = (RestrictInfo *) lfirst(j); - - /* Can't use pushed-down clauses in outer join */ - if (isouterjoin && rinfo->is_pushed_down) - continue; - - if (match_join_clause_to_indexcol(index, - indexcol, - curClass, - rinfo)) - { - clausegroup = lappend(clausegroup, rinfo); - if (!jfoundhere) - { - jfoundhere = true; - jfound = true; - numsources++; - } - } - } - } - - /* - * If we found clauses in more than one list, we may now have - * clauses that are known redundant. Get rid of 'em. - */ - if (numsources > 1) - { - clausegroup = remove_redundant_join_clauses(root, - clausegroup, - jointype); - } - /* * If no clauses match this key, we're done; we don't want to look * at keys to its right. @@ -401,8 +580,7 @@ group_clauses_by_indexkey_for_join(Query *root, IndexOptInfo *index, } while (!DoneMatchingIndexKeys(classes)); - /* if no join clause was matched then forget it, per comments above */ - if (!jfound) + if (!found_clause) return NIL; return clausegroup_list; @@ -419,7 +597,7 @@ group_clauses_by_indexkey_for_join(Query *root, IndexOptInfo *index, * top-level restriction clauses of the relation. Furthermore, we demand * that at least one such use be made, otherwise we fail and return NIL. * (Any path we made without such a use would be redundant with non-OR - * indexscans. Compare also group_clauses_by_indexkey_for_join.) + * indexscans.) * * XXX When we generate an indexqual list that uses both the OR subclause * and top-level restriction clauses, we end up with a slightly inefficient @@ -446,7 +624,8 @@ group_clauses_by_indexkey_for_or(IndexOptInfo *index, Expr *orsubclause) if (IsA(orsubclause, RestrictInfo)) { if (match_clause_to_indexcol(index, indexcol, curClass, - (RestrictInfo *) orsubclause)) + (RestrictInfo *) orsubclause, + NULL)) { clausegroup = lappend(clausegroup, orsubclause); matched = true; @@ -460,7 +639,8 @@ group_clauses_by_indexkey_for_or(IndexOptInfo *index, Expr *orsubclause) if (IsA(subsubclause, RestrictInfo) && match_clause_to_indexcol(index, indexcol, curClass, - subsubclause)) + subsubclause, + NULL)) { clausegroup = lappend(clausegroup, subsubclause); matched = true; @@ -482,7 +662,8 @@ group_clauses_by_indexkey_for_or(IndexOptInfo *index, Expr *orsubclause) RestrictInfo *rinfo = (RestrictInfo *) lfirst(item); if (match_clause_to_indexcol(index, indexcol, curClass, - rinfo)) + rinfo, + NULL)) clausegroup = lappend(clausegroup, rinfo); } } @@ -520,6 +701,19 @@ group_clauses_by_indexkey_for_or(IndexOptInfo *index, Expr *orsubclause) * operator for this column, or is a "special" operator as recognized * by match_special_index_operator(). * + * 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. + * + * 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. + * * 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 * on the right if we can commute the clause to put the key on the left. @@ -543,7 +737,8 @@ static bool match_clause_to_indexcol(IndexOptInfo *index, int indexcol, Oid opclass, - RestrictInfo *rinfo) + RestrictInfo *rinfo, + Relids outer_relids) { Expr *clause = rinfo->clause; Node *leftop, @@ -566,11 +761,11 @@ match_clause_to_indexcol(IndexOptInfo *index, /* * Check for clauses of the form: (indexkey operator constant) or - * (constant operator indexkey). Anything that is a "pseudo constant" - * expression will do. + * (constant operator indexkey). See above notes about const-ness. */ if (match_index_to_operand(leftop, indexcol, index) && - is_pseudo_constant_clause_relids(rightop, rinfo->right_relids)) + bms_is_subset(rinfo->right_relids, outer_relids) && + !contain_volatile_functions(rightop)) { if (is_indexable_operator(clause, opclass, true)) return true; @@ -585,7 +780,8 @@ match_clause_to_indexcol(IndexOptInfo *index, } if (match_index_to_operand(rightop, indexcol, index) && - is_pseudo_constant_clause_relids(leftop, rinfo->left_relids)) + bms_is_subset(rinfo->left_relids, outer_relids) && + !contain_volatile_functions(leftop)) { if (is_indexable_operator(clause, opclass, false)) return true; @@ -603,90 +799,6 @@ match_clause_to_indexcol(IndexOptInfo *index, } /* - * match_join_clause_to_indexcol() - * Determines whether a join clause matches a column of an index. - * - * To match, the clause: - * - * (1) must be in the form (indexkey op others) or (others op indexkey), - * where others is an expression involving only vars of the other - * relation(s); and - * (2) must contain an operator which is in the same class as the index - * operator for this column, or is a "special" operator as recognized - * by match_special_index_operator(). - * - * The boolean-index cases don't apply. - * - * As above, we must be able to commute the clause to put the indexkey - * on the left. - * - * Note that we already know that the clause as a whole uses vars from - * the interesting set of relations. But we need to defend against - * expressions like (a.f1 OP (b.f2 OP a.f3)); that's not processable by - * an indexscan nestloop join, whereas (a.f1 OP (b.f2 OP c.f3)) is. - * - * 'index' is the index of interest. - * 'indexcol' is a column number of 'index' (counting from 0). - * 'opclass' is the corresponding operator class. - * 'rinfo' is the clause to be tested (as a RestrictInfo node). - * - * Returns true if the clause can be used with this index key. - * - * NOTE: returns false if clause is an OR or AND clause; it is the - * responsibility of higher-level routines to cope with those. - */ -static bool -match_join_clause_to_indexcol(IndexOptInfo *index, - int indexcol, - Oid opclass, - RestrictInfo *rinfo) -{ - Expr *clause = rinfo->clause; - Node *leftop, - *rightop; - - /* Clause must be a binary opclause. */ - if (!is_opclause(clause)) - return false; - leftop = get_leftop(clause); - rightop = get_rightop(clause); - if (!leftop || !rightop) - return false; - - /* - * Check for an indexqual that could be handled by a nestloop join. We - * need the index key to be compared against an expression that uses - * none of the indexed relation's vars and contains no volatile - * functions. - */ - if (match_index_to_operand(leftop, indexcol, index)) - { - Relids othervarnos = rinfo->right_relids; - bool isIndexable; - - isIndexable = - !bms_overlap(index->rel->relids, othervarnos) && - !contain_volatile_functions(rightop) && - is_indexable_operator(clause, opclass, true); - return isIndexable; - } - - if (match_index_to_operand(rightop, indexcol, index)) - { - Relids othervarnos = rinfo->left_relids; - bool isIndexable; - - isIndexable = - !bms_overlap(index->rel->relids, othervarnos) && - !contain_volatile_functions(leftop) && - is_indexable_operator(clause, opclass, false); - return isIndexable; - } - - return false; -} - -/* * indexable_operator * Does a binary opclause contain an operator matching the index opclass? * @@ -1407,63 +1519,123 @@ pred_test_simple_clause(Expr *predicate, Node *clause) /* * indexable_outerrelids * Finds all other relids that participate in any indexable join clause - * for the specified index. Returns a set of relids. + * for the specified table. Returns a set of relids. */ static Relids -indexable_outerrelids(IndexOptInfo *index) +indexable_outerrelids(RelOptInfo *rel) { Relids outer_relids = NULL; ListCell *l; - foreach(l, index->rel->joininfo) + foreach(l, rel->joininfo) { JoinInfo *joininfo = (JoinInfo *) lfirst(l); - bool match_found = false; - ListCell *j; /* * Examine each joinclause in the JoinInfo node's list to see if - * it matches any key of the index. If so, add the JoinInfo's + * it matches any key of any index. If so, add the JoinInfo's * otherrels to the result. We can skip examining other - * joinclauses in the same list as soon as we find a match (since - * by definition they all have the same otherrels). + * joinclauses in the same list as soon as we find a match, since + * by definition they all have the same otherrels. */ - foreach(j, joininfo->jinfo_restrictinfo) - { - RestrictInfo *rinfo = (RestrictInfo *) lfirst(j); - int indexcol = 0; - Oid *classes = index->classlist; + if (list_matches_any_index(joininfo->jinfo_restrictinfo, + rel, + joininfo->unjoined_relids)) + outer_relids = bms_add_members(outer_relids, + joininfo->unjoined_relids); + } - do - { - Oid curClass = classes[0]; + return outer_relids; +} - if (match_join_clause_to_indexcol(index, - indexcol, - curClass, - rinfo)) - { - match_found = true; - break; - } +/* + * list_matches_any_index + * Workhorse for indexable_outerrelids: given a list of RestrictInfos, + * see if any of them match any index of the given rel. + * + * We define it like this so that we can recurse into OR subclauses. + */ +static bool +list_matches_any_index(List *clauses, RelOptInfo *rel, Relids outer_relids) +{ + ListCell *l; - indexcol++; - classes++; + foreach(l, clauses) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); + ListCell *j; - } while (!DoneMatchingIndexKeys(classes)); + Assert(IsA(rinfo, RestrictInfo)); - if (match_found) - break; + /* RestrictInfos that aren't ORs are easy */ + if (!restriction_is_or_clause(rinfo)) + { + if (matches_any_index(rinfo, rel, outer_relids)) + return true; + continue; } - if (match_found) + foreach(j, ((BoolExpr *) rinfo->orclause)->args) { - outer_relids = bms_add_members(outer_relids, - joininfo->unjoined_relids); + Node *orarg = (Node *) lfirst(j); + + /* OR arguments should be ANDs or sub-RestrictInfos */ + if (and_clause(orarg)) + { + List *andargs = ((BoolExpr *) orarg)->args; + + /* Recurse to examine AND items and sub-ORs */ + if (list_matches_any_index(andargs, rel, outer_relids)) + return true; + } + else + { + Assert(IsA(orarg, RestrictInfo)); + Assert(!restriction_is_or_clause((RestrictInfo *) orarg)); + if (matches_any_index((RestrictInfo *) orarg, rel, + outer_relids)) + return true; + } } } - return outer_relids; + return false; +} + +/* + * matches_any_index + * Workhorse for indexable_outerrelids: see if a simple 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; + + /* Normal case for a simple restriction clause */ + foreach(l, rel->indexlist) + { + IndexOptInfo *index = (IndexOptInfo *) lfirst(l); + int indexcol = 0; + Oid *classes = index->classlist; + + do + { + Oid curClass = classes[0]; + + if (match_clause_to_indexcol(index, + indexcol, + curClass, + rinfo, + outer_relids)) + return true; + + indexcol++; + classes++; + } while (!DoneMatchingIndexKeys(classes)); + } + + return false; } /* @@ -1483,10 +1655,12 @@ Path * best_inner_indexscan(Query *root, RelOptInfo *rel, Relids outer_relids, JoinType jointype) { - Path *cheapest = NULL; + Path *cheapest; bool isouterjoin; - ListCell *ilist; - ListCell *jlist; + List *clause_list; + List *indexpaths; + List *bitindexpaths; + ListCell *l; InnerIndexscanInfo *info; MemoryContext oldcontext; @@ -1523,7 +1697,7 @@ best_inner_indexscan(Query *root, RelOptInfo *rel, /* * Intersect the given outer_relids with index_outer_relids to find - * the set of outer relids actually relevant for this index. If there + * 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_relids); @@ -1541,9 +1715,9 @@ best_inner_indexscan(Query *root, RelOptInfo *rel, * necessary because it should always be the same for a given * innerrel.) */ - foreach(jlist, rel->index_inner_paths) + foreach(l, rel->index_inner_paths) { - info = (InnerIndexscanInfo *) lfirst(jlist); + info = (InnerIndexscanInfo *) lfirst(l); if (bms_equal(info->other_relids, outer_relids) && info->isouterjoin == isouterjoin) { @@ -1554,69 +1728,57 @@ best_inner_indexscan(Query *root, RelOptInfo *rel, } /* - * For each index of the rel, find the best path; then choose the best - * overall. We cache the per-index results as well as the overall - * result. (This is useful because different indexes may have - * different relevant outerrel sets, so different overall outerrel - * sets might still map to the same computation for a given index.) + * Find all the relevant restriction and join clauses. */ - foreach(ilist, rel->indexlist) - { - IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist); - Relids index_outer_relids; - Path *path = NULL; + clause_list = find_clauses_for_join(root, rel, outer_relids, isouterjoin); - /* identify set of relevant outer relids for this index */ - index_outer_relids = bms_intersect(index->outer_relids, outer_relids); - /* skip if none */ - if (bms_is_empty(index_outer_relids)) - { - bms_free(index_outer_relids); - continue; - } + /* + * Find all the index paths that are usable for this join, except for + * stuff involving OR clauses. + */ + indexpaths = find_usable_indexes(root, rel, + clause_list, NIL, + false, true, + outer_relids); - /* - * Look to see if we already computed the result for this index. - */ - foreach(jlist, index->inner_paths) - { - info = (InnerIndexscanInfo *) lfirst(jlist); - if (bms_equal(info->other_relids, index_outer_relids) && - info->isouterjoin == isouterjoin) - { - path = info->best_innerpath; - bms_free(index_outer_relids); /* not needed anymore */ - break; - } - } + /* + * Generate BitmapOrPaths for any suitable OR-clauses present in the + * clause list. + */ + bitindexpaths = generate_bitmap_or_paths(root, rel, + clause_list, NIL, + true, + outer_relids); - if (jlist == NULL) /* failed to find a match? */ - { - List *clausegroups; - - /* find useful clauses for this index and outerjoin set */ - clausegroups = group_clauses_by_indexkey_for_join(root, - index, - index_outer_relids, - jointype, - isouterjoin); - if (clausegroups) - { - /* make the path */ - path = make_innerjoin_index_path(root, index, clausegroups); - } + /* + * Include the regular index paths in bitindexpaths. + */ + bitindexpaths = list_concat(bitindexpaths, list_copy(indexpaths)); - /* Cache the result --- whether positive or negative */ - info = makeNode(InnerIndexscanInfo); - info->other_relids = index_outer_relids; - info->isouterjoin = isouterjoin; - info->best_innerpath = path; - index->inner_paths = lcons(info, index->inner_paths); - } + /* + * 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); + bpath = create_bitmap_heap_path(root, rel, bitmapqual, true); + indexpaths = lappend(indexpaths, bpath); + } - if (path != NULL && - (cheapest == NULL || - compare_path_costs(path, cheapest, TOTAL_COST) < 0)) + /* + * Now choose the cheapest member of indexpaths. + */ + cheapest = NULL; + foreach(l, indexpaths) + { + Path *path = (Path *) lfirst(l); + + if (cheapest == NULL || + compare_path_costs(path, cheapest, TOTAL_COST) < 0) cheapest = path; } @@ -1632,89 +1794,96 @@ best_inner_indexscan(Query *root, RelOptInfo *rel, return cheapest; } -/**************************************************************************** - * ---- PATH CREATION UTILITIES ---- - ****************************************************************************/ - /* - * make_innerjoin_index_path - * Create an index path node for a path to be used as an inner - * relation in a nestloop join. - * - * 'index' is the index of interest - * 'clausegroups' is a list of lists of RestrictInfos that can use 'index' + * 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 Path * -make_innerjoin_index_path(Query *root, - IndexOptInfo *index, - List *clausegroups) +static List * +find_clauses_for_join(Query *root, RelOptInfo *rel, + Relids outer_relids, bool isouterjoin) { - IndexPath *pathnode = makeNode(IndexPath); - RelOptInfo *rel = index->rel; - List *indexquals, - *allclauses; - - /* XXX perhaps this code should be merged with create_index_path? */ - - pathnode->path.pathtype = T_IndexScan; - pathnode->path.parent = rel; + List *clause_list = NIL; + bool jfound = false; + int numsources; + ListCell *l; /* - * There's no point in marking the path with any pathkeys, since it - * will only ever be used as the inner path of a nestloop, and so its - * ordering does not matter. + * We can always use plain restriction clauses for the rel. We + * scan these first because we want them first in the clause + * list for the convenience of remove_redundant_join_clauses, + * which can never remove non-join clauses and hence won't be able + * to get rid of a non-join clause if it appears after a join + * clause it is redundant with. */ - pathnode->path.pathkeys = NIL; + foreach(l, rel->baserestrictinfo) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); - /* Convert clauses to indexquals the executor can handle */ - indexquals = expand_indexqual_conditions(index, clausegroups); + /* Can't use pushed-down clauses in outer join */ + if (isouterjoin && rinfo->is_pushed_down) + continue; + clause_list = lappend(clause_list, rinfo); + } - /* Flatten the clausegroups list to produce indexclauses list */ - allclauses = flatten_clausegroups_list(clausegroups); + /* found anything in base restrict list? */ + numsources = (clause_list != NIL) ? 1 : 0; - /* - * Note that we are making a pathnode for a single-scan indexscan; - * therefore, indexinfo etc should be single-element lists. - */ - pathnode->indexinfo = list_make1(index); - pathnode->indexclauses = list_make1(allclauses); - pathnode->indexquals = list_make1(indexquals); + /* Look for joinclauses that are usable with given outer_relids */ + foreach(l, rel->joininfo) + { + JoinInfo *joininfo = (JoinInfo *) lfirst(l); + bool jfoundhere = false; + ListCell *j; - pathnode->isjoininner = true; + if (!bms_is_subset(joininfo->unjoined_relids, outer_relids)) + continue; - /* We don't actually care what order the index scans in ... */ - pathnode->indexscandir = NoMovementScanDirection; + foreach(j, joininfo->jinfo_restrictinfo) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(j); + + /* Can't use pushed-down clauses in outer join */ + if (isouterjoin && rinfo->is_pushed_down) + continue; + + clause_list = lappend(clause_list, rinfo); + if (!jfoundhere) + { + jfoundhere = true; + jfound = true; + numsources++; + } + } + } + + /* if no join clause was matched then forget it, per comments above */ + if (!jfound) + return NIL; /* - * We must compute the estimated number of output rows for the - * indexscan. This is less than rel->rows because of the additional - * selectivity of the join clauses. Since clausegroups may contain - * both restriction and join clauses, we have to do a set union to get - * the full set of clauses that must be considered to compute the - * correct selectivity. (Without the union operation, we might have - * some restriction clauses appearing twice, which'd mislead - * clauselist_selectivity into double-counting their selectivity. - * However, since RestrictInfo nodes aren't copied when linking them - * into different lists, it should be sufficient to use pointer - * comparison to remove duplicates.) - * - * Always assume the join type is JOIN_INNER; even if some of the join - * clauses come from other contexts, that's not our problem. + * If we found clauses in more than one list, we may now have + * clauses that are known redundant. Get rid of 'em. */ - allclauses = list_union_ptr(rel->baserestrictinfo, allclauses); - pathnode->rows = rel->tuples * - clauselist_selectivity(root, - allclauses, - rel->relid, /* do not use 0! */ - JOIN_INNER); - /* Like costsize.c, force estimate to be at least one row */ - pathnode->rows = clamp_row_est(pathnode->rows); - - cost_index(pathnode, root, index, indexquals, true); - - return (Path *) pathnode; + if (numsources > 1) + { + clause_list = remove_redundant_join_clauses(root, + clause_list, + isouterjoin); + } + + return clause_list; } +/**************************************************************************** + * ---- PATH CREATION UTILITIES ---- + ****************************************************************************/ + /* * flatten_clausegroups_list * Given a list of lists of RestrictInfos, flatten it to a list diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index faaf727da0d..e7a695e5725 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -10,7 +10,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.182 2005/04/21 19:18:12 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.183 2005/04/22 21:58:31 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -870,6 +870,9 @@ create_bitmap_scan_plan(Query *root, /* Also extract the true index conditions */ indexquals = create_bitmap_indxqual(best_path->bitmapqual); + /* Reduce RestrictInfo list to bare expressions */ + scan_clauses = get_actual_clauses(scan_clauses); + /* * If this is a innerjoin scan, the indexclauses will contain join * clauses that are not present in scan_clauses (since the passed-in @@ -881,16 +884,9 @@ create_bitmap_scan_plan(Query *root, */ if (best_path->isjoininner) { - /* - * Pointer comparison should be enough to determine RestrictInfo - * matches. - */ - scan_clauses = list_union_ptr(scan_clauses, bitmapqualorig); + scan_clauses = list_union(scan_clauses, bitmapqualorig); } - /* Reduce RestrictInfo list to bare expressions */ - scan_clauses = get_actual_clauses(scan_clauses); - /* * The qpqual list must contain all restrictions not automatically * handled by the index. All the predicates in the indexquals will be @@ -1322,7 +1318,38 @@ create_nestloop_plan(Query *root, select_nonredundant_join_clauses(root, joinrestrictclauses, linitial(indexclauses), - best_path->jointype); + IS_OUTER_JOIN(best_path->jointype)); + } + } + else if (IsA(best_path->innerjoinpath, BitmapHeapPath)) + { + /* + * Same deal for bitmapped index scans. + */ + BitmapHeapPath *innerpath = (BitmapHeapPath *) best_path->innerjoinpath; + + if (innerpath->isjoininner) + { + List *bitmapquals; + List *bitmapclauses; + ListCell *l; + + bitmapquals = create_bitmap_qual(innerpath->bitmapqual); + + /* must convert qual list to restrictinfos ... painful ... */ + bitmapclauses = NIL; + foreach(l, bitmapquals) + { + bitmapclauses = lappend(bitmapclauses, + make_restrictinfo((Expr *) lfirst(l), + true, true)); + } + + joinrestrictclauses = + select_nonredundant_join_clauses(root, + joinrestrictclauses, + bitmapclauses, + IS_OUTER_JOIN(best_path->jointype)); } } diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c index 9c3b151f201..38c859dfbcb 100644 --- a/src/backend/optimizer/plan/planagg.c +++ b/src/backend/optimizer/plan/planagg.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/planagg.c,v 1.3 2005/04/12 05:11:28 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/planagg.c,v 1.4 2005/04/22 21:58:31 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -343,7 +343,10 @@ build_minmax_path(Query *root, RelOptInfo *rel, MinMaxAggInfo *info) * to build the path, it's convenient to extract that first and then * look through it for the equality restrictions. */ - restrictclauses = group_clauses_by_indexkey(index); + restrictclauses = group_clauses_by_indexkey(index, + index->rel->baserestrictinfo, + NIL, + NULL); if (list_length(restrictclauses) < indexcol) continue; /* definitely haven't got enough */ @@ -376,7 +379,8 @@ build_minmax_path(Query *root, RelOptInfo *rel, MinMaxAggInfo *info) new_path = create_index_path(root, index, restrictclauses, NIL, - indexscandir); + indexscandir, + false); /* * Estimate actual cost of fetching just one row. diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index 0688d86b1b1..7ddcb26833d 100644 --- a/src/backend/optimizer/plan/setrefs.c +++ b/src/backend/optimizer/plan/setrefs.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/setrefs.c,v 1.107 2005/04/19 22:35:16 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/setrefs.c,v 1.108 2005/04/22 21:58:31 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -44,6 +44,10 @@ typedef struct static void fix_expr_references(Plan *plan, Node *node); static bool fix_expr_references_walker(Node *node, void *context); static void set_join_references(Join *join, List *rtable); +static void set_inner_join_references(Plan *inner_plan, + List *rtable, + List *outer_tlist, + bool tlists_have_non_vars); static void set_uppernode_references(Plan *plan, Index subvarno); static bool targetlist_has_non_vars(List *tlist); static List *join_references(List *clauses, @@ -325,7 +329,7 @@ fix_expr_references_walker(Node *node, void *context) * * In the case of a nestloop with inner indexscan, we will also need to * apply the same transformation to any outer vars appearing in the - * quals of the child indexscan. + * quals of the child indexscan. set_inner_join_references does that. * * 'join' is a join plan node * 'rtable' is the associated range table @@ -365,62 +369,11 @@ set_join_references(Join *join, List *rtable) /* Now do join-type-specific stuff */ if (IsA(join, NestLoop)) { - if (IsA(inner_plan, IndexScan)) - { - /* - * An index is being used to reduce the number of tuples - * scanned in the inner relation. If there are join clauses - * being used with the index, we must update their outer-rel - * var nodes to refer to the outer side of the join. - */ - IndexScan *innerscan = (IndexScan *) inner_plan; - List *indxqualorig = innerscan->indxqualorig; - - /* No work needed if indxqual refers only to its own rel... */ - if (NumRelids((Node *) indxqualorig) > 1) - { - Index innerrel = innerscan->scan.scanrelid; - - /* only refs to outer vars get changed in the inner qual */ - innerscan->indxqualorig = join_references(indxqualorig, - rtable, - outer_tlist, - NIL, - innerrel, - tlists_have_non_vars); - innerscan->indxqual = join_references(innerscan->indxqual, - rtable, - outer_tlist, - NIL, - innerrel, - tlists_have_non_vars); - - /* - * We must fix the inner qpqual too, if it has join - * clauses (this could happen if special operators are - * involved: some indxquals may get rechecked as qpquals). - */ - if (NumRelids((Node *) inner_plan->qual) > 1) - inner_plan->qual = join_references(inner_plan->qual, - rtable, - outer_tlist, - NIL, - innerrel, - tlists_have_non_vars); - } - } - else if (IsA(inner_plan, TidScan)) - { - TidScan *innerscan = (TidScan *) inner_plan; - Index innerrel = innerscan->scan.scanrelid; - - innerscan->tideval = join_references(innerscan->tideval, - rtable, - outer_tlist, - NIL, - innerrel, - tlists_have_non_vars); - } + /* This processing is split out to handle possible recursion */ + set_inner_join_references(inner_plan, + rtable, + outer_tlist, + tlists_have_non_vars); } else if (IsA(join, MergeJoin)) { @@ -447,6 +400,178 @@ set_join_references(Join *join, List *rtable) } /* + * set_inner_join_references + * Handle join references appearing in an inner indexscan's quals + * + * To handle bitmap-scan plan trees, we have to be able to recurse down + * to the bottom BitmapIndexScan nodes, so this is split out as a separate + * function. + */ +static void +set_inner_join_references(Plan *inner_plan, + List *rtable, + List *outer_tlist, + bool tlists_have_non_vars) +{ + if (IsA(inner_plan, IndexScan)) + { + /* + * An index is being used to reduce the number of tuples + * scanned in the inner relation. If there are join clauses + * being used with the index, we must update their outer-rel + * var nodes to refer to the outer side of the join. + */ + IndexScan *innerscan = (IndexScan *) inner_plan; + List *indxqualorig = innerscan->indxqualorig; + + /* No work needed if indxqual refers only to its own rel... */ + if (NumRelids((Node *) indxqualorig) > 1) + { + Index innerrel = innerscan->scan.scanrelid; + + /* only refs to outer vars get changed in the inner qual */ + innerscan->indxqualorig = join_references(indxqualorig, + rtable, + outer_tlist, + NIL, + innerrel, + tlists_have_non_vars); + innerscan->indxqual = join_references(innerscan->indxqual, + rtable, + outer_tlist, + NIL, + innerrel, + tlists_have_non_vars); + + /* + * We must fix the inner qpqual too, if it has join + * clauses (this could happen if special operators are + * involved: some indxquals may get rechecked as qpquals). + */ + if (NumRelids((Node *) inner_plan->qual) > 1) + inner_plan->qual = join_references(inner_plan->qual, + rtable, + outer_tlist, + NIL, + innerrel, + tlists_have_non_vars); + } + } + else if (IsA(inner_plan, BitmapIndexScan)) + { + /* + * Same, but index is being used within a bitmap plan. + */ + BitmapIndexScan *innerscan = (BitmapIndexScan *) inner_plan; + List *indxqualorig = innerscan->indxqualorig; + + /* No work needed if indxqual refers only to its own rel... */ + if (NumRelids((Node *) indxqualorig) > 1) + { + Index innerrel = innerscan->scan.scanrelid; + + /* only refs to outer vars get changed in the inner qual */ + innerscan->indxqualorig = join_references(indxqualorig, + rtable, + outer_tlist, + NIL, + innerrel, + tlists_have_non_vars); + innerscan->indxqual = join_references(innerscan->indxqual, + rtable, + outer_tlist, + NIL, + innerrel, + tlists_have_non_vars); + /* no need to fix inner qpqual */ + Assert(inner_plan->qual == NIL); + } + } + else if (IsA(inner_plan, BitmapHeapScan)) + { + /* + * The inner side is a bitmap scan plan. Fix the top node, + * and recurse to get the lower nodes. + */ + BitmapHeapScan *innerscan = (BitmapHeapScan *) inner_plan; + List *bitmapqualorig = innerscan->bitmapqualorig; + + /* No work needed if bitmapqual refers only to its own rel... */ + if (NumRelids((Node *) bitmapqualorig) > 1) + { + Index innerrel = innerscan->scan.scanrelid; + + /* only refs to outer vars get changed in the inner qual */ + innerscan->bitmapqualorig = join_references(bitmapqualorig, + rtable, + outer_tlist, + NIL, + innerrel, + tlists_have_non_vars); + + /* + * We must fix the inner qpqual too, if it has join + * clauses (this could happen if special operators are + * involved: some indxquals may get rechecked as qpquals). + */ + if (NumRelids((Node *) inner_plan->qual) > 1) + inner_plan->qual = join_references(inner_plan->qual, + rtable, + outer_tlist, + NIL, + innerrel, + tlists_have_non_vars); + + /* Now recurse */ + set_inner_join_references(inner_plan->lefttree, + rtable, + outer_tlist, + tlists_have_non_vars); + } + } + else if (IsA(inner_plan, BitmapAnd)) + { + /* All we need do here is recurse */ + BitmapAnd *innerscan = (BitmapAnd *) inner_plan; + ListCell *l; + + foreach(l, innerscan->bitmapplans) + { + set_inner_join_references((Plan *) lfirst(l), + rtable, + outer_tlist, + tlists_have_non_vars); + } + } + else if (IsA(inner_plan, BitmapOr)) + { + /* All we need do here is recurse */ + BitmapOr *innerscan = (BitmapOr *) inner_plan; + ListCell *l; + + foreach(l, innerscan->bitmapplans) + { + set_inner_join_references((Plan *) lfirst(l), + rtable, + outer_tlist, + tlists_have_non_vars); + } + } + else if (IsA(inner_plan, TidScan)) + { + TidScan *innerscan = (TidScan *) inner_plan; + Index innerrel = innerscan->scan.scanrelid; + + innerscan->tideval = join_references(innerscan->tideval, + rtable, + outer_tlist, + NIL, + innerrel, + tlists_have_non_vars); + } +} + +/* * set_uppernode_references * Update the targetlist and quals of an upper-level plan node * to refer to the tuples returned by its lefttree subplan. diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index d0c81073c3f..c1736678ab3 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.118 2005/04/21 19:18:12 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.119 2005/04/22 21:58:31 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -260,6 +260,9 @@ set_cheapest(RelOptInfo *parent_rel) * but just recycling discarded Path nodes is a very useful savings in * a large join tree. We can recycle the List nodes of pathlist, too. * + * BUT: we do not pfree IndexPath objects, since they may be referenced as + * children of BitmapHeapPaths as well as being paths in their own right. + * * 'parent_rel' is the relation entry to which the path corresponds. * 'new_path' is a potential path for parent_rel. * @@ -349,8 +352,12 @@ add_path(RelOptInfo *parent_rel, Path *new_path) { parent_rel->pathlist = list_delete_cell(parent_rel->pathlist, p1, p1_prev); - /* Delete the data pointed-to by the deleted cell */ - pfree(old_path); + /* + * Delete the data pointed-to by the deleted cell, if possible + */ + if (!IsA(old_path, IndexPath)) + pfree(old_path); + /* Advance list pointer */ if (p1_prev) p1 = lnext(p1_prev); else @@ -361,6 +368,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path) /* new belongs after this old path if it has cost >= old's */ if (costcmp >= 0) insert_after = p1; + /* Advance list pointers */ p1_prev = p1; p1 = lnext(p1); } @@ -385,7 +393,8 @@ add_path(RelOptInfo *parent_rel, Path *new_path) else { /* Reject and recycle the new path */ - pfree(new_path); + if (!IsA(new_path, IndexPath)) + pfree(new_path); } } @@ -418,55 +427,102 @@ create_seqscan_path(Query *root, RelOptInfo *rel) * Creates a path node for an index scan. * * 'index' is a usable index. - * 'restriction_clauses' is a list of lists of RestrictInfo nodes + * 'clause_groups' is a list of lists of RestrictInfo nodes * to be used as index qual conditions in the scan. * 'pathkeys' describes the ordering of the path. * 'indexscandir' is ForwardScanDirection or BackwardScanDirection * for an ordered index, or NoMovementScanDirection for * an unordered index. + * 'isjoininner' is TRUE if this is a join inner indexscan path. + * (pathkeys and indexscandir are ignored if so.) * * Returns the new path node. */ IndexPath * create_index_path(Query *root, IndexOptInfo *index, - List *restriction_clauses, + List *clause_groups, List *pathkeys, - ScanDirection indexscandir) + ScanDirection indexscandir, + bool isjoininner) { IndexPath *pathnode = makeNode(IndexPath); - List *indexquals; + RelOptInfo *rel = index->rel; + List *indexquals, + *allclauses; + + /* + * For a join inner scan, there's no point in marking the path with any + * pathkeys, since it will only ever be used as the inner path of a + * nestloop, and so its ordering does not matter. For the same reason + * we don't really care what order it's scanned in. (We could expect + * the caller to supply the correct values, but it's easier to force + * it here.) + */ + if (isjoininner) + { + pathkeys = NIL; + indexscandir = NoMovementScanDirection; + } pathnode->path.pathtype = T_IndexScan; - pathnode->path.parent = index->rel; + pathnode->path.parent = rel; pathnode->path.pathkeys = pathkeys; /* Convert clauses to indexquals the executor can handle */ - indexquals = expand_indexqual_conditions(index, restriction_clauses); + indexquals = expand_indexqual_conditions(index, clause_groups); /* Flatten the clause-groups list to produce indexclauses list */ - restriction_clauses = flatten_clausegroups_list(restriction_clauses); + allclauses = flatten_clausegroups_list(clause_groups); /* * We are making a pathnode for a single-scan indexscan; therefore, * indexinfo etc should be single-element lists. */ pathnode->indexinfo = list_make1(index); - pathnode->indexclauses = list_make1(restriction_clauses); + pathnode->indexclauses = list_make1(allclauses); pathnode->indexquals = list_make1(indexquals); - /* It's not an innerjoin path. */ - pathnode->isjoininner = false; - + pathnode->isjoininner = isjoininner; pathnode->indexscandir = indexscandir; - /* - * The number of rows is the same as the parent rel's estimate, since - * this isn't a join inner indexscan. - */ - pathnode->rows = index->rel->rows; + if (isjoininner) + { + /* + * We must compute the estimated number of output rows for the + * indexscan. This is less than rel->rows because of the additional + * selectivity of the join clauses. Since clause_groups may + * contain both restriction and join clauses, we have to do a set + * union to get the full set of clauses that must be considered to + * compute the correct selectivity. (Without the union operation, + * we might have some restriction clauses appearing twice, which'd + * mislead clauselist_selectivity into double-counting their + * selectivity. However, since RestrictInfo nodes aren't copied when + * linking them into different lists, it should be sufficient to use + * pointer comparison to remove duplicates.) + * + * Always assume the join type is JOIN_INNER; even if some of the join + * clauses come from other contexts, that's not our problem. + */ + allclauses = list_union_ptr(rel->baserestrictinfo, allclauses); + pathnode->rows = rel->tuples * + clauselist_selectivity(root, + allclauses, + rel->relid, /* do not use 0! */ + JOIN_INNER); + /* Like costsize.c, force estimate to be at least one row */ + pathnode->rows = clamp_row_est(pathnode->rows); + } + else + { + /* + * The number of rows is the same as the parent rel's estimate, + * since this isn't a join inner indexscan. + */ + pathnode->rows = rel->rows; + } - cost_index(pathnode, root, index, indexquals, false); + cost_index(pathnode, root, index, indexquals, isjoininner); return pathnode; } @@ -480,7 +536,8 @@ create_index_path(Query *root, BitmapHeapPath * create_bitmap_heap_path(Query *root, RelOptInfo *rel, - Path *bitmapqual) + Path *bitmapqual, + bool isjoininner) { BitmapHeapPath *pathnode = makeNode(BitmapHeapPath); @@ -489,15 +546,36 @@ create_bitmap_heap_path(Query *root, pathnode->path.pathkeys = NIL; /* always unordered */ pathnode->bitmapqual = bitmapqual; + pathnode->isjoininner = isjoininner; - /* It's not an innerjoin path. */ - pathnode->isjoininner = false; + if (isjoininner) + { + /* + * We must compute the estimated number of output rows for the + * indexscan. This is less than rel->rows because of the additional + * selectivity of the join clauses. We make use of the selectivity + * estimated for the bitmap to do this; this isn't really quite + * right since there may be restriction conditions not included + * in the bitmap ... + */ + Cost indexTotalCost; + Selectivity indexSelectivity; - /* - * The number of rows is the same as the parent rel's estimate, since - * this isn't a join inner indexscan. - */ - pathnode->rows = rel->rows; + cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity); + pathnode->rows = rel->tuples * indexSelectivity; + if (pathnode->rows > rel->rows) + pathnode->rows = rel->rows; + /* Like costsize.c, force estimate to be at least one row */ + pathnode->rows = clamp_row_est(pathnode->rows); + } + else + { + /* + * The number of rows is the same as the parent rel's estimate, + * since this isn't a join inner indexscan. + */ + pathnode->rows = rel->rows; + } cost_bitmap_heap_scan(&pathnode->path, root, rel, bitmapqual, false); diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c index b908f320a5f..8c9b34f0fe7 100644 --- a/src/backend/optimizer/util/plancat.c +++ b/src/backend/optimizer/util/plancat.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/plancat.c,v 1.105 2005/04/14 20:03:24 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/plancat.c,v 1.106 2005/04/22 21:58:31 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -194,10 +194,6 @@ get_relation_info(Oid relationObjectId, RelOptInfo *rel) info->tuples = rel->tuples; } - /* initialize cached join info to empty */ - info->outer_relids = NULL; - info->inner_paths = NIL; - index_close(indexRelation); indexinfos = lcons(info, indexinfos); diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 5a45b4a4444..4192d9b805b 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.64 2004/12/31 22:00:23 pgsql Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.65 2005/04/22 21:58:31 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -461,7 +461,8 @@ build_joinrel_restrictlist(Query *root, * previous clauses (see optimizer/README for discussion). We detect * that case and omit the redundant clause from the result list. */ - result = remove_redundant_join_clauses(root, rlist, jointype); + result = remove_redundant_join_clauses(root, rlist, + IS_OUTER_JOIN(jointype)); list_free(rlist); diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c index 3dad1a16072..414a583e9a3 100644 --- a/src/backend/optimizer/util/restrictinfo.c +++ b/src/backend/optimizer/util/restrictinfo.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.32 2005/03/28 00:58:24 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.33 2005/04/22 21:58:31 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -31,7 +31,7 @@ static Expr *make_sub_restrictinfos(Expr *clause, static RestrictInfo *join_clause_is_redundant(Query *root, RestrictInfo *rinfo, List *reference_list, - JoinType jointype); + bool isouterjoin); /* @@ -49,27 +49,19 @@ static RestrictInfo *join_clause_is_redundant(Query *root, RestrictInfo * make_restrictinfo(Expr *clause, bool is_pushed_down, bool valid_everywhere) { - Expr *orclause; - /* * If it's an OR clause, build a modified copy with RestrictInfos * inserted above each subclause of the top-level AND/OR structure. */ if (or_clause((Node *) clause)) - { - orclause = make_sub_restrictinfos(clause, - is_pushed_down, - valid_everywhere); - } - else - { - /* Shouldn't be an AND clause, else AND/OR flattening messed up */ - Assert(!and_clause((Node *) clause)); + return (RestrictInfo *) make_sub_restrictinfos(clause, + is_pushed_down, + valid_everywhere); - orclause = NULL; - } + /* Shouldn't be an AND clause, else AND/OR flattening messed up */ + Assert(!and_clause((Node *) clause)); - return make_restrictinfo_internal(clause, orclause, + return make_restrictinfo_internal(clause, NULL, is_pushed_down, valid_everywhere); } @@ -198,6 +190,12 @@ make_restrictinfo_internal(Expr *clause, Expr *orclause, /* * Recursively insert sub-RestrictInfo nodes into a boolean expression. + * + * We put RestrictInfos above simple (non-AND/OR) clauses and above + * sub-OR clauses, but not above sub-AND clauses, because there's no need. + * This may seem odd but it is closely related to the fact that we use + * implicit-AND lists at top level of RestrictInfo lists. Only ORs and + * simple clauses are valid RestrictInfos. */ static Expr * make_sub_restrictinfos(Expr *clause, bool is_pushed_down, @@ -213,7 +211,10 @@ make_sub_restrictinfos(Expr *clause, bool is_pushed_down, make_sub_restrictinfos(lfirst(temp), is_pushed_down, valid_everywhere)); - return make_orclause(orlist); + return (Expr *) make_restrictinfo_internal(clause, + make_orclause(orlist), + is_pushed_down, + valid_everywhere); } else if (and_clause((Node *) clause)) { @@ -314,7 +315,7 @@ get_actual_join_clauses(List *restrictinfo_list, */ List * remove_redundant_join_clauses(Query *root, List *restrictinfo_list, - JoinType jointype) + bool isouterjoin) { List *result = NIL; ListCell *item; @@ -341,7 +342,7 @@ remove_redundant_join_clauses(Query *root, List *restrictinfo_list, RestrictInfo *prevrinfo; /* is it redundant with any prior clause? */ - prevrinfo = join_clause_is_redundant(root, rinfo, result, jointype); + prevrinfo = join_clause_is_redundant(root, rinfo, result, isouterjoin); if (prevrinfo == NULL) { /* no, so add it to result list */ @@ -377,7 +378,7 @@ List * select_nonredundant_join_clauses(Query *root, List *restrictinfo_list, List *reference_list, - JoinType jointype) + bool isouterjoin) { List *result = NIL; ListCell *item; @@ -387,7 +388,7 @@ select_nonredundant_join_clauses(Query *root, RestrictInfo *rinfo = (RestrictInfo *) lfirst(item); /* drop it if redundant with any reference clause */ - if (join_clause_is_redundant(root, rinfo, reference_list, jointype) != NULL) + if (join_clause_is_redundant(root, rinfo, reference_list, isouterjoin) != NULL) continue; /* otherwise, add it to result list */ @@ -429,7 +430,7 @@ static RestrictInfo * join_clause_is_redundant(Query *root, RestrictInfo *rinfo, List *reference_list, - JoinType jointype) + bool isouterjoin) { ListCell *refitem; @@ -463,7 +464,7 @@ join_clause_is_redundant(Query *root, if (rinfo->left_pathkey == refrinfo->left_pathkey && rinfo->right_pathkey == refrinfo->right_pathkey && (rinfo->is_pushed_down == refrinfo->is_pushed_down || - !IS_OUTER_JOIN(jointype))) + !isouterjoin)) { /* Yup, it's redundant */ return refrinfo; diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h index 53cd96b6b28..945858e8a60 100644 --- a/src/include/nodes/relation.h +++ b/src/include/nodes/relation.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.107 2005/04/21 19:18:13 tgl Exp $ + * $PostgreSQL: pgsql/src/include/nodes/relation.h,v 1.108 2005/04/22 21:58:32 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -274,10 +274,6 @@ typedef struct IndexOptInfo bool predOK; /* true if predicate matches query */ bool unique; /* true if a unique index */ - - /* cached info about inner indexscan paths for index */ - Relids outer_relids; /* other relids in usable join clauses */ - List *inner_paths; /* List of InnerIndexscanInfo nodes */ } IndexOptInfo; @@ -764,16 +760,13 @@ typedef struct JoinInfo * thus varies depending on which outer relation we consider; so we have * to recompute the best such path for every join. To avoid lots of * redundant computation, we cache the results of such searches. For - * each index we compute the set of possible otherrelids (all relids - * appearing in joinquals that could become indexquals for this index). + * each relation we compute the set of possible otherrelids (all relids + * appearing in joinquals that could become indexquals for this table). * Two outer relations whose relids have the same intersection with this * set will have the same set of available joinclauses and thus the same - * best inner indexscan for that index. Similarly, for each base relation, - * we form the union of the per-index otherrelids sets. Two outer relations - * with the same intersection with that set will have the same best overall - * inner indexscan for the base relation. We use lists of InnerIndexscanInfo - * nodes to cache the results of these searches at both the index and - * relation level. + * best inner indexscan for the inner relation. By taking the intersection + * before scanning the cache, we avoid recomputing when considering + * join rels that differ only by the inclusion of irrelevant other rels. * * The search key also includes a bool showing whether the join being * considered is an outer join. Since we constrain the join order for diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h index b55c2366cf9..0f9e56880d5 100644 --- a/src/include/optimizer/cost.h +++ b/src/include/optimizer/cost.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.66 2005/04/21 19:18:13 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/cost.h,v 1.67 2005/04/22 21:58:32 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -58,6 +58,7 @@ extern void cost_bitmap_heap_scan(Path *path, Query *root, RelOptInfo *baserel, Path *bitmapqual, bool is_injoin); extern void cost_bitmap_and_node(BitmapAndPath *path, Query *root); extern void cost_bitmap_or_node(BitmapOrPath *path, Query *root); +extern void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec); extern void cost_tidscan(Path *path, Query *root, RelOptInfo *baserel, List *tideval); extern void cost_subqueryscan(Path *path, RelOptInfo *baserel); diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index 7881ed17536..f5c11ff58e3 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/pathnode.h,v 1.59 2005/04/21 19:18:13 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/pathnode.h,v 1.60 2005/04/22 21:58:32 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -30,12 +30,14 @@ extern void add_path(RelOptInfo *parent_rel, Path *new_path); extern Path *create_seqscan_path(Query *root, RelOptInfo *rel); extern IndexPath *create_index_path(Query *root, IndexOptInfo *index, - List *restriction_clauses, + List *clause_groups, List *pathkeys, - ScanDirection indexscandir); + ScanDirection indexscandir, + bool isjoininner); extern BitmapHeapPath *create_bitmap_heap_path(Query *root, RelOptInfo *rel, - Path *bitmapqual); + Path *bitmapqual, + bool isjoininner); extern BitmapAndPath *create_bitmap_and_path(Query *root, RelOptInfo *rel, List *bitmapquals); diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index e5ca24807d0..a91744fd5f0 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -8,7 +8,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.81 2005/04/11 23:06:56 tgl Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/paths.h,v 1.82 2005/04/22 21:58:32 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -38,7 +38,9 @@ extern void debug_print_rel(Query *root, RelOptInfo *rel); extern void create_index_paths(Query *root, RelOptInfo *rel); extern Path *best_inner_indexscan(Query *root, RelOptInfo *rel, Relids outer_relids, JoinType jointype); -extern List *group_clauses_by_indexkey(IndexOptInfo *index); +extern List *group_clauses_by_indexkey(IndexOptInfo *index, + List *clauses, List *outer_clauses, + Relids outer_relids); extern List *group_clauses_by_indexkey_for_or(IndexOptInfo *index, Expr *orsubclause); extern bool match_index_to_operand(Node *operand, int indexcol, diff --git a/src/include/optimizer/restrictinfo.h b/src/include/optimizer/restrictinfo.h index a9e3bcac25e..77c03bb4ec2 100644 --- a/src/include/optimizer/restrictinfo.h +++ b/src/include/optimizer/restrictinfo.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/optimizer/restrictinfo.h,v 1.26 2004/12/31 22:03:36 pgsql Exp $ + * $PostgreSQL: pgsql/src/include/optimizer/restrictinfo.h,v 1.27 2005/04/22 21:58:32 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -27,10 +27,10 @@ extern void get_actual_join_clauses(List *restrictinfo_list, List **joinquals, List **otherquals); extern List *remove_redundant_join_clauses(Query *root, List *restrictinfo_list, - JoinType jointype); + bool isouterjoin); extern List *select_nonredundant_join_clauses(Query *root, List *restrictinfo_list, List *reference_list, - JoinType jointype); + bool isouterjoin); #endif /* RESTRICTINFO_H */ diff --git a/src/test/regress/expected/alter_table.out b/src/test/regress/expected/alter_table.out index b9edbc649d4..54205395e2b 100644 --- a/src/test/regress/expected/alter_table.out +++ b/src/test/regress/expected/alter_table.out @@ -131,8 +131,10 @@ ALTER INDEX tmp_onek_unique1 RENAME TO onek_unique1; -- renaming views CREATE VIEW tmp_view (unique1) AS SELECT unique1 FROM tenk1; ALTER TABLE tmp_view RENAME TO tmp_view_new; --- analyze to ensure we get an indexscan here +-- hack to ensure we get an indexscan here ANALYZE tenk1; +set enable_seqscan to off; +set enable_bitmapscan to off; -- 5 values, sorted SELECT unique1 FROM tenk1 WHERE unique1 < 5; unique1 @@ -144,6 +146,8 @@ SELECT unique1 FROM tenk1 WHERE unique1 < 5; 4 (5 rows) +reset enable_seqscan; +reset enable_bitmapscan; DROP VIEW tmp_view_new; -- toast-like relation name alter table stud_emp rename to pg_toast_stud_emp; diff --git a/src/test/regress/expected/arrays.out b/src/test/regress/expected/arrays.out index edcfa900a58..80eab4a13da 100644 --- a/src/test/regress/expected/arrays.out +++ b/src/test/regress/expected/arrays.out @@ -367,6 +367,7 @@ insert into arr_tbl values ('{2,3,4}'); insert into arr_tbl values ('{1,5,3}'); insert into arr_tbl values ('{1,2,10}'); set enable_seqscan to off; +set enable_bitmapscan to off; select * from arr_tbl where f1 > '{1,2,3}' and f1 <= '{1,5,3}'; f1 ---------- @@ -376,6 +377,8 @@ select * from arr_tbl where f1 > '{1,2,3}' and f1 <= '{1,5,3}'; -- note: if above select doesn't produce the expected tuple order, -- then you didn't get an indexscan plan, and something is busted. +reset enable_seqscan; +reset enable_bitmapscan; -- test [not] (like|ilike) (any|all) (...) select 'foo' like any (array['%a', '%o']); -- t ?column? diff --git a/src/test/regress/expected/stats.out b/src/test/regress/expected/stats.out index 8013ab65b29..e366f76cb9c 100644 --- a/src/test/regress/expected/stats.out +++ b/src/test/regress/expected/stats.out @@ -11,6 +11,8 @@ SHOW stats_start_collector; -- must be on on (1 row) +-- XXX stopgap until we figure out how bitmap scans should be counted +SET enable_bitmapscan = off; -- save counters CREATE TEMP TABLE prevstats AS SELECT t.seq_scan, t.seq_tup_read, t.idx_scan, t.idx_tup_fetch, diff --git a/src/test/regress/sql/alter_table.sql b/src/test/regress/sql/alter_table.sql index 2659efbfac5..aa3d17ccf7d 100644 --- a/src/test/regress/sql/alter_table.sql +++ b/src/test/regress/sql/alter_table.sql @@ -171,10 +171,16 @@ ALTER INDEX tmp_onek_unique1 RENAME TO onek_unique1; -- renaming views CREATE VIEW tmp_view (unique1) AS SELECT unique1 FROM tenk1; ALTER TABLE tmp_view RENAME TO tmp_view_new; --- analyze to ensure we get an indexscan here + +-- hack to ensure we get an indexscan here ANALYZE tenk1; +set enable_seqscan to off; +set enable_bitmapscan to off; -- 5 values, sorted SELECT unique1 FROM tenk1 WHERE unique1 < 5; +reset enable_seqscan; +reset enable_bitmapscan; + DROP VIEW tmp_view_new; -- toast-like relation name alter table stud_emp rename to pg_toast_stud_emp; diff --git a/src/test/regress/sql/arrays.sql b/src/test/regress/sql/arrays.sql index a2308353575..37ef80bb5c4 100644 --- a/src/test/regress/sql/arrays.sql +++ b/src/test/regress/sql/arrays.sql @@ -178,10 +178,14 @@ insert into arr_tbl values ('{1,2,3}'); insert into arr_tbl values ('{2,3,4}'); insert into arr_tbl values ('{1,5,3}'); insert into arr_tbl values ('{1,2,10}'); + set enable_seqscan to off; +set enable_bitmapscan to off; select * from arr_tbl where f1 > '{1,2,3}' and f1 <= '{1,5,3}'; -- note: if above select doesn't produce the expected tuple order, -- then you didn't get an indexscan plan, and something is busted. +reset enable_seqscan; +reset enable_bitmapscan; -- test [not] (like|ilike) (any|all) (...) select 'foo' like any (array['%a', '%o']); -- t diff --git a/src/test/regress/sql/stats.sql b/src/test/regress/sql/stats.sql index 948a81f0c40..d5dcbd92cee 100644 --- a/src/test/regress/sql/stats.sql +++ b/src/test/regress/sql/stats.sql @@ -8,6 +8,9 @@ -- conditio sine qua non SHOW stats_start_collector; -- must be on +-- XXX stopgap until we figure out how bitmap scans should be counted +SET enable_bitmapscan = off; + -- save counters CREATE TEMP TABLE prevstats AS SELECT t.seq_scan, t.seq_tup_read, t.idx_scan, t.idx_tup_fetch, |