diff options
Diffstat (limited to 'src/backend/optimizer/util')
| -rw-r--r-- | src/backend/optimizer/util/joininfo.c | 118 | ||||
| -rw-r--r-- | src/backend/optimizer/util/relnode.c | 75 | ||||
| -rw-r--r-- | src/backend/optimizer/util/restrictinfo.c | 32 |
3 files changed, 91 insertions, 134 deletions
diff --git a/src/backend/optimizer/util/joininfo.c b/src/backend/optimizer/util/joininfo.c index b49ead13163..9e66f2db0c6 100644 --- a/src/backend/optimizer/util/joininfo.c +++ b/src/backend/optimizer/util/joininfo.c @@ -1,14 +1,14 @@ /*------------------------------------------------------------------------- * * joininfo.c - * JoinInfo node manipulation routines + * joininfo list manipulation routines * * 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/util/joininfo.c,v 1.42 2005/06/05 22:32:56 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/joininfo.c,v 1.43 2005/06/09 04:19:00 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -19,58 +19,49 @@ /* - * find_joininfo_node - * Find the joininfo node within a relation entry corresponding - * to a join between 'this_rel' and the relations in 'join_relids'. - * If there is no such node, return NULL. - * - * Returns a joininfo node, or NULL. + * have_relevant_joinclause + * Detect whether there is a joinclause that can be used to join + * the two given relations. */ -JoinInfo * -find_joininfo_node(RelOptInfo *this_rel, Relids join_relids) +bool +have_relevant_joinclause(RelOptInfo *rel1, RelOptInfo *rel2) { + bool result = false; + Relids join_relids; + List *joininfo; ListCell *l; - foreach(l, this_rel->joininfo) + join_relids = bms_union(rel1->relids, rel2->relids); + + /* + * We could scan either relation's joininfo list; may as well use the + * shorter one. + */ + if (list_length(rel1->joininfo) <= list_length(rel2->joininfo)) + joininfo = rel1->joininfo; + else + joininfo = rel2->joininfo; + + foreach(l, joininfo) { - JoinInfo *joininfo = (JoinInfo *) lfirst(l); + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); - if (bms_equal(join_relids, joininfo->unjoined_relids)) - return joininfo; + if (bms_is_subset(rinfo->required_relids, join_relids)) + { + result = true; + break; + } } - return NULL; -} -/* - * make_joininfo_node - * Find the joininfo node within a relation entry corresponding - * to a join between 'this_rel' and the relations in 'join_relids'. - * A new node is created and added to the relation entry's joininfo - * field if the desired one can't be found. - * - * Returns a joininfo node. - */ -JoinInfo * -make_joininfo_node(RelOptInfo *this_rel, Relids join_relids) -{ - JoinInfo *joininfo = find_joininfo_node(this_rel, join_relids); + bms_free(join_relids); - if (joininfo == NULL) - { - joininfo = makeNode(JoinInfo); - joininfo->unjoined_relids = join_relids; - joininfo->jinfo_restrictinfo = NIL; - this_rel->joininfo = lcons(joininfo, this_rel->joininfo); - } - return joininfo; + return result; } /* * add_join_clause_to_rels - * For every relation participating in a join clause, add 'restrictinfo' to - * the appropriate joininfo list (creating a new list and adding it to the - * appropriate rel node if necessary). + * Add 'restrictinfo' to the joininfo list of each relation it requires. * * Note that the same copy of the restrictinfo node is linked to by all the * lists it is in. This allows us to exploit caching of information about @@ -89,32 +80,12 @@ add_join_clause_to_rels(PlannerInfo *root, Relids tmprelids; int cur_relid; - /* For every relid, find the joininfo, and add the proper join entries */ tmprelids = bms_copy(join_relids); while ((cur_relid = bms_first_member(tmprelids)) >= 0) { - Relids unjoined_relids; - JoinInfo *joininfo; + RelOptInfo *rel = find_base_rel(root, cur_relid); - /* Get the relids not equal to the current relid */ - unjoined_relids = bms_copy(join_relids); - unjoined_relids = bms_del_member(unjoined_relids, cur_relid); - Assert(!bms_is_empty(unjoined_relids)); - - /* - * Find or make the joininfo node for this combination of rels, - * and add the restrictinfo node to it. - */ - joininfo = make_joininfo_node(find_base_rel(root, cur_relid), - unjoined_relids); - joininfo->jinfo_restrictinfo = lappend(joininfo->jinfo_restrictinfo, - restrictinfo); - - /* - * Can't bms_free(unjoined_relids) because new joininfo node may - * link to it. We could avoid leaking memory by doing bms_copy() - * in make_joininfo_node, but for now speed seems better. - */ + rel->joininfo = lappend(rel->joininfo, restrictinfo); } bms_free(tmprelids); } @@ -138,34 +109,17 @@ remove_join_clause_from_rels(PlannerInfo *root, Relids tmprelids; int cur_relid; - /* For every relid, find the joininfo */ tmprelids = bms_copy(join_relids); while ((cur_relid = bms_first_member(tmprelids)) >= 0) { - Relids unjoined_relids; - JoinInfo *joininfo; - - /* Get the relids not equal to the current relid */ - unjoined_relids = bms_copy(join_relids); - unjoined_relids = bms_del_member(unjoined_relids, cur_relid); - Assert(!bms_is_empty(unjoined_relids)); - - /* - * Find the joininfo node for this combination of rels; it should - * exist already, if add_join_clause_to_rels was called. - */ - joininfo = find_joininfo_node(find_base_rel(root, cur_relid), - unjoined_relids); - Assert(joininfo); + RelOptInfo *rel = find_base_rel(root, cur_relid); /* * Remove the restrictinfo from the list. Pointer comparison is * sufficient. */ - Assert(list_member_ptr(joininfo->jinfo_restrictinfo, restrictinfo)); - joininfo->jinfo_restrictinfo = list_delete_ptr(joininfo->jinfo_restrictinfo, - restrictinfo); - bms_free(unjoined_relids); + 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/relnode.c b/src/backend/optimizer/util/relnode.c index fbaf0de83a8..d66796d5cce 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.69 2005/06/08 23:02:05 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.70 2005/06/09 04:19:00 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -479,8 +479,8 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, * * These routines are separate because the restriction list must be * built afresh for each pair of input sub-relations we consider, whereas - * the join lists need only be computed once for any join RelOptInfo. - * The join lists are fully determined by the set of rels making up the + * the join list need only be computed once for any join RelOptInfo. + * The join list is fully determined by the set of rels making up the * joinrel, so we should get the same results (up to ordering) from any * candidate pair of sub-relations. But the restriction list is whatever * is not handled in the sub-relations, so it depends on which @@ -488,7 +488,7 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, * * If a join clause from an input relation refers to base rels still not * present in the joinrel, then it is still a join clause for the joinrel; - * we put it into an appropriate JoinInfo list for the joinrel. Otherwise, + * we put it into the joininfo list for the joinrel. Otherwise, * the clause is now a restrict clause for the joined relation, and we * return it to the caller of build_joinrel_restrictlist() to be stored in * join paths made from this pair of sub-relations. (It will not need to @@ -506,7 +506,7 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, * * build_joinrel_restrictlist() returns a list of relevant restrictinfos, * whereas build_joinrel_joinlist() stores its results in the joinrel's - * joininfo lists. One or the other must accept each given clause! + * joininfo list. One or the other must accept each given clause! * * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass * up to the join relation. I believe this is no longer necessary, because @@ -562,29 +562,27 @@ subbuild_joinrel_restrictlist(RelOptInfo *joinrel, List *joininfo_list) { List *restrictlist = NIL; - ListCell *xjoininfo; + ListCell *l; - foreach(xjoininfo, joininfo_list) + foreach(l, joininfo_list) { - JoinInfo *joininfo = (JoinInfo *) lfirst(xjoininfo); + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); - if (bms_is_subset(joininfo->unjoined_relids, joinrel->relids)) + if (bms_is_subset(rinfo->required_relids, joinrel->relids)) { /* - * Clauses in this JoinInfo list become restriction clauses - * for the joinrel, since they refer to no outside rels. - * - * We must copy the list to avoid disturbing the input relation, - * but we can use a shallow copy. + * 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. */ - restrictlist = list_concat(restrictlist, - list_copy(joininfo->jinfo_restrictinfo)); + restrictlist = lappend(restrictlist, rinfo); } else { /* - * These clauses are still join clauses at this level, so we - * ignore them in this routine. + * This clause is still a join clause at this level, so we + * ignore it in this routine. */ } } @@ -596,42 +594,33 @@ static void subbuild_joinrel_joinlist(RelOptInfo *joinrel, List *joininfo_list) { - ListCell *xjoininfo; + ListCell *l; - foreach(xjoininfo, joininfo_list) + foreach(l, joininfo_list) { - JoinInfo *joininfo = (JoinInfo *) lfirst(xjoininfo); - Relids new_unjoined_relids; + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); - new_unjoined_relids = bms_difference(joininfo->unjoined_relids, - joinrel->relids); - if (bms_is_empty(new_unjoined_relids)) + if (bms_is_subset(rinfo->required_relids, joinrel->relids)) { /* - * Clauses in this JoinInfo list become restriction clauses - * for the joinrel, since they refer to no outside rels. So we - * can ignore them in this routine. + * This clause becomes a restriction clause for the joinrel, + * since it refers to no outside rels. So we can ignore it + * in this routine. */ - bms_free(new_unjoined_relids); } else { /* - * These clauses are still join clauses at this level, so find - * or make the appropriate JoinInfo item for the joinrel, and - * add the clauses to it, eliminating 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.) + * 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.) */ - JoinInfo *new_joininfo; - - new_joininfo = make_joininfo_node(joinrel, new_unjoined_relids); - new_joininfo->jinfo_restrictinfo = - list_union_ptr(new_joininfo->jinfo_restrictinfo, - joininfo->jinfo_restrictinfo); + if (!list_member_ptr(joinrel->joininfo, rinfo)) + joinrel->joininfo = lappend(joinrel->joininfo, rinfo); } } } diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c index 460ccc9546d..a76f1bb7a2e 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.36 2005/06/05 22:32:56 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/util/restrictinfo.c,v 1.37 2005/06/09 04:19:00 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -24,7 +24,8 @@ static RestrictInfo *make_restrictinfo_internal(Expr *clause, Expr *orclause, bool is_pushed_down, - bool valid_everywhere); + bool valid_everywhere, + Relids required_relids); static Expr *make_sub_restrictinfos(Expr *clause, bool is_pushed_down, bool valid_everywhere); @@ -40,14 +41,16 @@ static RestrictInfo *join_clause_is_redundant(PlannerInfo *root, * Build a RestrictInfo node containing the given subexpression. * * The is_pushed_down and valid_everywhere flags must be supplied by the - * caller. + * caller. required_relids can be NULL, in which case it defaults to the + * actual clause contents (i.e., clause_relids). * * We initialize fields that depend only on the given subexpression, leaving * others that depend on context (or may never be needed at all) to be filled * later. */ RestrictInfo * -make_restrictinfo(Expr *clause, bool is_pushed_down, bool valid_everywhere) +make_restrictinfo(Expr *clause, bool is_pushed_down, bool valid_everywhere, + Relids required_relids) { /* * If it's an OR clause, build a modified copy with RestrictInfos @@ -62,7 +65,8 @@ make_restrictinfo(Expr *clause, bool is_pushed_down, bool valid_everywhere) Assert(!and_clause((Node *) clause)); return make_restrictinfo_internal(clause, NULL, - is_pushed_down, valid_everywhere); + is_pushed_down, valid_everywhere, + required_relids); } /* @@ -133,7 +137,8 @@ make_restrictinfo_from_bitmapqual(Path *bitmapqual, list_make1(make_restrictinfo_internal(make_orclause(withoutris), make_orclause(withris), is_pushed_down, - valid_everywhere)); + valid_everywhere, + NULL)); } else if (IsA(bitmapqual, IndexPath)) { @@ -157,7 +162,8 @@ make_restrictinfo_from_bitmapqual(Path *bitmapqual, */ static RestrictInfo * make_restrictinfo_internal(Expr *clause, Expr *orclause, - bool is_pushed_down, bool valid_everywhere) + bool is_pushed_down, bool valid_everywhere, + Relids required_relids) { RestrictInfo *restrictinfo = makeNode(RestrictInfo); @@ -200,6 +206,12 @@ make_restrictinfo_internal(Expr *clause, Expr *orclause, restrictinfo->clause_relids = pull_varnos((Node *) clause); } + /* required_relids defaults to clause_relids */ + if (required_relids != NULL) + restrictinfo->required_relids = required_relids; + else + restrictinfo->required_relids = restrictinfo->clause_relids; + /* * Fill in all the cacheable fields with "not yet set" markers. None * of these will be computed until/unless needed. Note in particular @@ -254,7 +266,8 @@ make_sub_restrictinfos(Expr *clause, bool is_pushed_down, return (Expr *) make_restrictinfo_internal(clause, make_orclause(orlist), is_pushed_down, - valid_everywhere); + valid_everywhere, + NULL); } else if (and_clause((Node *) clause)) { @@ -272,7 +285,8 @@ make_sub_restrictinfos(Expr *clause, bool is_pushed_down, return (Expr *) make_restrictinfo_internal(clause, NULL, is_pushed_down, - valid_everywhere); + valid_everywhere, + NULL); } /* |