diff options
Diffstat (limited to 'src/backend/optimizer/util')
| -rw-r--r-- | src/backend/optimizer/util/joininfo.c | 44 | ||||
| -rw-r--r-- | src/backend/optimizer/util/pathnode.c | 18 | ||||
| -rw-r--r-- | src/backend/optimizer/util/relnode.c | 127 | ||||
| -rw-r--r-- | src/backend/optimizer/util/restrictinfo.c | 169 |
4 files changed, 108 insertions, 250 deletions
diff --git a/src/backend/optimizer/util/joininfo.c b/src/backend/optimizer/util/joininfo.c index 2971282bf3f..e58903c5d0a 100644 --- a/src/backend/optimizer/util/joininfo.c +++ b/src/backend/optimizer/util/joininfo.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/util/joininfo.c,v 1.46 2007/01/05 22:19:32 momjian Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/joininfo.c,v 1.47 2007/01/20 20:45:39 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -16,6 +16,7 @@ #include "optimizer/joininfo.h" #include "optimizer/pathnode.h" +#include "optimizer/paths.h" /* @@ -55,6 +56,13 @@ have_relevant_joinclause(PlannerInfo *root, } /* + * We also need to check the EquivalenceClass data structure, which + * might contain relationships not emitted into the joininfo lists. + */ + if (!result && rel1->has_eclass_joins && rel2->has_eclass_joins) + result = have_relevant_eclass_joinclause(root, rel1, rel2); + + /* * It's possible that the rels correspond to the left and right sides * of a degenerate outer join, that is, one with no joinclause mentioning * the non-nullable side. The above scan will then have failed to locate @@ -124,37 +132,3 @@ add_join_clause_to_rels(PlannerInfo *root, } bms_free(tmprelids); } - -/* - * remove_join_clause_from_rels - * Delete 'restrictinfo' from all the joininfo lists it is in - * - * This reverses the effect of add_join_clause_to_rels. It's used when we - * discover that a join clause is redundant. - * - * 'restrictinfo' describes the join clause - * 'join_relids' is the list of relations participating in the join clause - * (there must be more than one) - */ -void -remove_join_clause_from_rels(PlannerInfo *root, - RestrictInfo *restrictinfo, - Relids join_relids) -{ - Relids tmprelids; - int cur_relid; - - tmprelids = bms_copy(join_relids); - while ((cur_relid = bms_first_member(tmprelids)) >= 0) - { - RelOptInfo *rel = find_base_rel(root, cur_relid); - - /* - * Remove the restrictinfo from the list. Pointer comparison is - * sufficient. - */ - Assert(list_member_ptr(rel->joininfo, restrictinfo)); - rel->joininfo = list_delete_ptr(rel->joininfo, restrictinfo); - } - bms_free(tmprelids); -} diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 8ee6346e5b1..5832d145ef0 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.136 2007/01/10 18:06:04 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.137 2007/01/20 20:45:39 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -26,7 +26,6 @@ #include "parser/parse_expr.h" #include "parser/parse_oper.h" #include "parser/parsetree.h" -#include "utils/memutils.h" #include "utils/selfuncs.h" #include "utils/lsyscache.h" #include "utils/syscache.h" @@ -747,11 +746,11 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath) return (UniquePath *) rel->cheapest_unique_path; /* - * We must ensure path struct is allocated in same context as parent rel; + * We must ensure path struct is allocated in main planning context; * otherwise GEQO memory management causes trouble. (Compare * best_inner_indexscan().) */ - oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel)); + oldcontext = MemoryContextSwitchTo(root->planner_cxt); pathnode = makeNode(UniquePath); @@ -1198,11 +1197,6 @@ create_nestloop_path(PlannerInfo *root, * 'pathkeys' are the path keys of the new join path * 'mergeclauses' are the RestrictInfo nodes to use as merge clauses * (this should be a subset of the restrict_clauses list) - * 'mergefamilies' are the btree opfamily OIDs identifying the merge - * ordering for each merge clause - * 'mergestrategies' are the btree operator strategies identifying the merge - * ordering for each merge clause - * 'mergenullsfirst' are the nulls first/last flags for each merge clause * 'outersortkeys' are the sort varkeys for the outer relation * 'innersortkeys' are the sort varkeys for the inner relation */ @@ -1215,9 +1209,6 @@ create_mergejoin_path(PlannerInfo *root, List *restrict_clauses, List *pathkeys, List *mergeclauses, - Oid *mergefamilies, - int *mergestrategies, - bool *mergenullsfirst, List *outersortkeys, List *innersortkeys) { @@ -1258,9 +1249,6 @@ create_mergejoin_path(PlannerInfo *root, pathnode->jpath.joinrestrictinfo = restrict_clauses; pathnode->jpath.path.pathkeys = pathkeys; pathnode->path_mergeclauses = mergeclauses; - pathnode->path_mergeFamilies = mergefamilies; - pathnode->path_mergeStrategies = mergestrategies; - pathnode->path_mergeNullsFirst = mergenullsfirst; pathnode->outersortkeys = outersortkeys; pathnode->innersortkeys = innersortkeys; diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 86d8107e631..8cc6c81746f 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.84 2007/01/05 22:19:33 momjian Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.85 2007/01/20 20:45:40 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -16,6 +16,7 @@ #include "optimizer/cost.h" #include "optimizer/pathnode.h" +#include "optimizer/paths.h" #include "optimizer/plancat.h" #include "optimizer/restrictinfo.h" #include "parser/parsetree.h" @@ -31,17 +32,18 @@ typedef struct JoinHashEntry static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *input_rel); static List *build_joinrel_restrictlist(PlannerInfo *root, - RelOptInfo *joinrel, - RelOptInfo *outer_rel, - RelOptInfo *inner_rel, - JoinType jointype); + RelOptInfo *joinrel, + RelOptInfo *outer_rel, + RelOptInfo *inner_rel); static void build_joinrel_joinlist(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel); static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel, - List *joininfo_list); -static void subbuild_joinrel_joinlist(RelOptInfo *joinrel, - List *joininfo_list); + List *joininfo_list, + List *new_restrictlist); +static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel, + List *joininfo_list, + List *new_joininfo); /* @@ -84,6 +86,7 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptKind reloptkind) rel->baserestrictcost.startup = 0; rel->baserestrictcost.per_tuple = 0; rel->joininfo = NIL; + rel->has_eclass_joins = false; rel->index_outer_relids = NULL; rel->index_inner_paths = NIL; @@ -303,8 +306,7 @@ build_join_rel(PlannerInfo *root, *restrictlist_ptr = build_joinrel_restrictlist(root, joinrel, outer_rel, - inner_rel, - jointype); + inner_rel); return joinrel; } @@ -335,6 +337,7 @@ build_join_rel(PlannerInfo *root, joinrel->baserestrictcost.startup = 0; joinrel->baserestrictcost.per_tuple = 0; joinrel->joininfo = NIL; + joinrel->has_eclass_joins = false; joinrel->index_outer_relids = NULL; joinrel->index_inner_paths = NIL; @@ -354,16 +357,19 @@ build_join_rel(PlannerInfo *root, * caller might or might not need the restrictlist, but I need it anyway * for set_joinrel_size_estimates().) */ - restrictlist = build_joinrel_restrictlist(root, - joinrel, - outer_rel, - inner_rel, - jointype); + restrictlist = build_joinrel_restrictlist(root, joinrel, + outer_rel, inner_rel); if (restrictlist_ptr) *restrictlist_ptr = restrictlist; build_joinrel_joinlist(joinrel, outer_rel, inner_rel); /* + * This is also the right place to check whether the joinrel has any + * pending EquivalenceClass joins. + */ + joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel); + + /* * Set estimates of the joinrel's size. */ set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel, @@ -468,15 +474,15 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, * join paths made from this pair of sub-relations. (It will not need to * be considered further up the join tree.) * - * When building a restriction list, we eliminate redundant clauses. - * We don't try to do that for join clause lists, since the join clauses - * aren't really doing anything, just waiting to become part of higher - * levels' restriction lists. + * In many case we will find the same RestrictInfos in both input + * relations' joinlists, so be careful to eliminate duplicates. + * Pointer equality should be a sufficient test for dups, since all + * the various joinlist entries ultimately refer to RestrictInfos + * pushed into them by distribute_restrictinfo_to_rels(). * * 'joinrel' is a join relation node * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined * to form joinrel. - * 'jointype' is the type of join used. * * build_joinrel_restrictlist() returns a list of relevant restrictinfos, * whereas build_joinrel_joinlist() stores its results in the joinrel's @@ -491,33 +497,27 @@ static List * build_joinrel_restrictlist(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outer_rel, - RelOptInfo *inner_rel, - JoinType jointype) + RelOptInfo *inner_rel) { List *result; - List *rlist; /* - * Collect all the clauses that syntactically belong at this level. + * Collect all the clauses that syntactically belong at this level, + * eliminating any duplicates (important since we will see many of the + * same clauses arriving from both input relations). */ - rlist = list_concat(subbuild_joinrel_restrictlist(joinrel, - outer_rel->joininfo), - subbuild_joinrel_restrictlist(joinrel, - inner_rel->joininfo)); - + result = subbuild_joinrel_restrictlist(joinrel, outer_rel->joininfo, NIL); + result = subbuild_joinrel_restrictlist(joinrel, inner_rel->joininfo, result); /* - * Eliminate duplicate and redundant clauses. - * - * We must eliminate duplicates, since we will see many of the same - * clauses arriving from both input relations. Also, if a clause is a - * mergejoinable clause, it's possible that it is redundant with previous - * clauses (see optimizer/README for discussion). We detect that case and - * omit the redundant clause from the result list. + * Add on any clauses derived from EquivalenceClasses. These cannot be + * redundant with the clauses in the joininfo lists, so don't bother + * checking. */ - result = remove_redundant_join_clauses(root, rlist, - IS_OUTER_JOIN(jointype)); - - list_free(rlist); + result = list_concat(result, + generate_join_implied_equalities(root, + joinrel, + outer_rel, + inner_rel)); return result; } @@ -527,15 +527,24 @@ build_joinrel_joinlist(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel) { - subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo); - subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo); + List *result; + + /* + * Collect all the clauses that syntactically belong above this level, + * eliminating any duplicates (important since we will see many of the + * same clauses arriving from both input relations). + */ + result = subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo, NIL); + result = subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo, result); + + joinrel->joininfo = result; } static List * subbuild_joinrel_restrictlist(RelOptInfo *joinrel, - List *joininfo_list) + List *joininfo_list, + List *new_restrictlist) { - List *restrictlist = NIL; ListCell *l; foreach(l, joininfo_list) @@ -546,10 +555,12 @@ subbuild_joinrel_restrictlist(RelOptInfo *joinrel, { /* * This clause becomes a restriction clause for the joinrel, since - * it refers to no outside rels. We don't bother to check for - * duplicates here --- build_joinrel_restrictlist will do that. + * it refers to no outside rels. Add it to the list, being + * careful to eliminate duplicates. (Since RestrictInfo nodes in + * different joinlists will have been multiply-linked rather than + * copied, pointer equality should be a sufficient test.) */ - restrictlist = lappend(restrictlist, rinfo); + new_restrictlist = list_append_unique_ptr(new_restrictlist, rinfo); } else { @@ -560,12 +571,13 @@ subbuild_joinrel_restrictlist(RelOptInfo *joinrel, } } - return restrictlist; + return new_restrictlist; } -static void +static List * subbuild_joinrel_joinlist(RelOptInfo *joinrel, - List *joininfo_list) + List *joininfo_list, + List *new_joininfo) { ListCell *l; @@ -585,15 +597,14 @@ subbuild_joinrel_joinlist(RelOptInfo *joinrel, { /* * This clause is still a join clause at this level, so add it to - * the joininfo list for the joinrel, being careful to eliminate - * duplicates. (Since RestrictInfo nodes are normally - * multiply-linked rather than copied, pointer equality should be - * a sufficient test. If two equal() nodes should happen to sneak - * in, no great harm is done --- they'll be detected by - * redundant-clause testing when they reach a restriction list.) + * the new joininfo list, being careful to eliminate + * duplicates. (Since RestrictInfo nodes in different joinlists + * will have been multiply-linked rather than copied, pointer + * equality should be a sufficient test.) */ - joinrel->joininfo = list_append_unique_ptr(joinrel->joininfo, - rinfo); + new_joininfo = list_append_unique_ptr(new_joininfo, rinfo); } } + + return new_joininfo; } diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c index e35d00bff7b..ea8bb5c970b 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.51 2007/01/05 22:19:33 momjian Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.52 2007/01/20 20:45:40 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -33,10 +33,9 @@ static Expr *make_sub_restrictinfos(Expr *clause, bool outerjoin_delayed, bool pseudoconstant, Relids required_relids); -static RestrictInfo *join_clause_is_redundant(PlannerInfo *root, +static bool join_clause_is_redundant(PlannerInfo *root, RestrictInfo *rinfo, - List *reference_list, - bool isouterjoin); + List *reference_list); /* @@ -336,19 +335,17 @@ make_restrictinfo_internal(Expr *clause, * that happens only if it appears in the right context (top level of a * joinclause list). */ + restrictinfo->parent_ec = NULL; + restrictinfo->eval_cost.startup = -1; restrictinfo->this_selec = -1; - restrictinfo->mergejoinoperator = InvalidOid; - restrictinfo->left_sortop = InvalidOid; - restrictinfo->right_sortop = InvalidOid; - restrictinfo->mergeopfamily = InvalidOid; + restrictinfo->mergeopfamilies = NIL; - restrictinfo->left_pathkey = NIL; - restrictinfo->right_pathkey = NIL; + restrictinfo->left_ec = NULL; + restrictinfo->right_ec = NULL; - restrictinfo->left_mergescansel = -1; - restrictinfo->right_mergescansel = -1; + restrictinfo->outer_is_left = false; restrictinfo->hashjoinoperator = InvalidOid; @@ -530,77 +527,17 @@ extract_actual_join_clauses(List *restrictinfo_list, } /* - * remove_redundant_join_clauses - * - * Given a list of RestrictInfo clauses that are to be applied in a join, - * remove any duplicate or redundant clauses. - * - * We must eliminate duplicates when forming the restrictlist for a joinrel, - * since we will see many of the same clauses arriving from both input - * relations. Also, if a clause is a mergejoinable clause, it's possible that - * it is redundant with previous clauses (see optimizer/README for - * discussion). We detect that case and omit the redundant clause from the - * result list. - * - * The result is a fresh List, but it points to the same member nodes - * as were in the input. - */ -List * -remove_redundant_join_clauses(PlannerInfo *root, List *restrictinfo_list, - bool isouterjoin) -{ - List *result = NIL; - ListCell *item; - QualCost cost; - - /* - * If there are any redundant clauses, we want to eliminate the ones that - * are more expensive in favor of the ones that are less so. Run - * cost_qual_eval() to ensure the eval_cost fields are set up. - */ - cost_qual_eval(&cost, restrictinfo_list); - - /* - * We don't have enough knowledge yet to be able to estimate the number of - * times a clause might be evaluated, so it's hard to weight the startup - * and per-tuple costs appropriately. For now just weight 'em the same. - */ -#define CLAUSECOST(r) ((r)->eval_cost.startup + (r)->eval_cost.per_tuple) - - foreach(item, restrictinfo_list) - { - RestrictInfo *rinfo = (RestrictInfo *) lfirst(item); - RestrictInfo *prevrinfo; - - /* is it redundant with any prior clause? */ - prevrinfo = join_clause_is_redundant(root, rinfo, result, isouterjoin); - if (prevrinfo == NULL) - { - /* no, so add it to result list */ - result = lappend(result, rinfo); - } - else if (CLAUSECOST(rinfo) < CLAUSECOST(prevrinfo)) - { - /* keep this one, drop the previous one */ - result = list_delete_ptr(result, prevrinfo); - result = lappend(result, rinfo); - } - /* else, drop this one */ - } - - return result; -} - -/* * select_nonredundant_join_clauses * * Given a list of RestrictInfo clauses that are to be applied in a join, * select the ones that are not redundant with any clause in the - * reference_list. + * reference_list. This is used only for nestloop-with-inner-indexscan + * joins: any clauses being checked by the index should be removed from + * the qpquals list. * - * This is similar to remove_redundant_join_clauses, but we are looking for - * redundancies with a separate list of clauses (i.e., clauses that have - * already been applied below the join itself). + * "Redundant" means either equal() or derived from the same EquivalenceClass. + * We have to check the latter because indxqual.c may select different derived + * clauses than were selected by generate_join_implied_equalities(). * * Note that we assume the given restrictinfo_list has already been checked * for local redundancies, so we don't check again. @@ -608,8 +545,7 @@ remove_redundant_join_clauses(PlannerInfo *root, List *restrictinfo_list, List * select_nonredundant_join_clauses(PlannerInfo *root, List *restrictinfo_list, - List *reference_list, - bool isouterjoin) + List *reference_list) { List *result = NIL; ListCell *item; @@ -619,7 +555,7 @@ select_nonredundant_join_clauses(PlannerInfo *root, RestrictInfo *rinfo = (RestrictInfo *) lfirst(item); /* drop it if redundant with any reference clause */ - if (join_clause_is_redundant(root, rinfo, reference_list, isouterjoin) != NULL) + if (join_clause_is_redundant(root, rinfo, reference_list)) continue; /* otherwise, add it to result list */ @@ -631,79 +567,28 @@ select_nonredundant_join_clauses(PlannerInfo *root, /* * join_clause_is_redundant - * If rinfo is redundant with any clause in reference_list, - * return one such clause; otherwise return NULL. - * - * This is the guts of both remove_redundant_join_clauses and - * select_nonredundant_join_clauses. See the docs above for motivation. - * - * We can detect redundant mergejoinable clauses very cheaply by using their - * left and right pathkeys, which uniquely identify the sets of equijoined - * variables in question. All the members of a pathkey set that are in the - * left relation have already been forced to be equal; likewise for those in - * the right relation. So, we need to have only one clause that checks - * equality between any set member on the left and any member on the right; - * by transitivity, all the rest are then equal. - * - * However, clauses that are of the form "var expr = const expr" cannot be - * eliminated as redundant. This is because when there are const expressions - * in a pathkey set, generate_implied_equalities() suppresses "var = var" - * clauses in favor of "var = const" clauses. We cannot afford to drop any - * of the latter, even though they might seem redundant by the pathkey - * membership test. - * - * Weird special case: if we have two clauses that seem redundant - * except one is pushed down into an outer join and the other isn't, - * then they're not really redundant, because one constrains the - * joined rows after addition of null fill rows, and the other doesn't. + * Test whether rinfo is redundant with any clause in reference_list. */ -static RestrictInfo * +static bool join_clause_is_redundant(PlannerInfo *root, RestrictInfo *rinfo, - List *reference_list, - bool isouterjoin) + List *reference_list) { ListCell *refitem; - /* always consider exact duplicates redundant */ foreach(refitem, reference_list) { RestrictInfo *refrinfo = (RestrictInfo *) lfirst(refitem); + /* always consider exact duplicates redundant */ if (equal(rinfo, refrinfo)) - return refrinfo; - } - - /* check for redundant merge clauses */ - if (rinfo->mergejoinoperator != InvalidOid) - { - /* do the cheap test first: is it a "var = const" clause? */ - if (bms_is_empty(rinfo->left_relids) || - bms_is_empty(rinfo->right_relids)) - return NULL; /* var = const, so not redundant */ - - cache_mergeclause_pathkeys(root, rinfo); - - foreach(refitem, reference_list) - { - RestrictInfo *refrinfo = (RestrictInfo *) lfirst(refitem); + return true; - if (refrinfo->mergejoinoperator != InvalidOid) - { - cache_mergeclause_pathkeys(root, refrinfo); - - if (rinfo->left_pathkey == refrinfo->left_pathkey && - rinfo->right_pathkey == refrinfo->right_pathkey && - (rinfo->is_pushed_down == refrinfo->is_pushed_down || - !isouterjoin)) - { - /* Yup, it's redundant */ - return refrinfo; - } - } - } + /* check if derived from same EquivalenceClass */ + if (rinfo->parent_ec != NULL && + rinfo->parent_ec == refrinfo->parent_ec) + return true; } - /* otherwise, not redundant */ - return NULL; + return false; } |