Header And Logo

PostgreSQL
| The world's most advanced open source database.

joininfo.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * joininfo.c
00004  *    joininfo list manipulation routines
00005  *
00006  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00007  * Portions Copyright (c) 1994, Regents of the University of California
00008  *
00009  *
00010  * IDENTIFICATION
00011  *    src/backend/optimizer/util/joininfo.c
00012  *
00013  *-------------------------------------------------------------------------
00014  */
00015 #include "postgres.h"
00016 
00017 #include "optimizer/joininfo.h"
00018 #include "optimizer/pathnode.h"
00019 #include "optimizer/paths.h"
00020 
00021 
00022 /*
00023  * have_relevant_joinclause
00024  *      Detect whether there is a joinclause that involves
00025  *      the two given relations.
00026  *
00027  * Note: the joinclause does not have to be evaluatable with only these two
00028  * relations.  This is intentional.  For example consider
00029  *      SELECT * FROM a, b, c WHERE a.x = (b.y + c.z)
00030  * If a is much larger than the other tables, it may be worthwhile to
00031  * cross-join b and c and then use an inner indexscan on a.x.  Therefore
00032  * we should consider this joinclause as reason to join b to c, even though
00033  * it can't be applied at that join step.
00034  */
00035 bool
00036 have_relevant_joinclause(PlannerInfo *root,
00037                          RelOptInfo *rel1, RelOptInfo *rel2)
00038 {
00039     bool        result = false;
00040     List       *joininfo;
00041     Relids      other_relids;
00042     ListCell   *l;
00043 
00044     /*
00045      * We could scan either relation's joininfo list; may as well use the
00046      * shorter one.
00047      */
00048     if (list_length(rel1->joininfo) <= list_length(rel2->joininfo))
00049     {
00050         joininfo = rel1->joininfo;
00051         other_relids = rel2->relids;
00052     }
00053     else
00054     {
00055         joininfo = rel2->joininfo;
00056         other_relids = rel1->relids;
00057     }
00058 
00059     foreach(l, joininfo)
00060     {
00061         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
00062 
00063         if (bms_overlap(other_relids, rinfo->required_relids))
00064         {
00065             result = true;
00066             break;
00067         }
00068     }
00069 
00070     /*
00071      * We also need to check the EquivalenceClass data structure, which might
00072      * contain relationships not emitted into the joininfo lists.
00073      */
00074     if (!result && rel1->has_eclass_joins && rel2->has_eclass_joins)
00075         result = have_relevant_eclass_joinclause(root, rel1, rel2);
00076 
00077     return result;
00078 }
00079 
00080 
00081 /*
00082  * add_join_clause_to_rels
00083  *    Add 'restrictinfo' to the joininfo list of each relation it requires.
00084  *
00085  * Note that the same copy of the restrictinfo node is linked to by all the
00086  * lists it is in.  This allows us to exploit caching of information about
00087  * the restriction clause (but we must be careful that the information does
00088  * not depend on context).
00089  *
00090  * 'restrictinfo' describes the join clause
00091  * 'join_relids' is the list of relations participating in the join clause
00092  *               (there must be more than one)
00093  */
00094 void
00095 add_join_clause_to_rels(PlannerInfo *root,
00096                         RestrictInfo *restrictinfo,
00097                         Relids join_relids)
00098 {
00099     Relids      tmprelids;
00100     int         cur_relid;
00101 
00102     tmprelids = bms_copy(join_relids);
00103     while ((cur_relid = bms_first_member(tmprelids)) >= 0)
00104     {
00105         RelOptInfo *rel = find_base_rel(root, cur_relid);
00106 
00107         rel->joininfo = lappend(rel->joininfo, restrictinfo);
00108     }
00109     bms_free(tmprelids);
00110 }
00111 
00112 /*
00113  * remove_join_clause_from_rels
00114  *    Delete 'restrictinfo' from all the joininfo lists it is in
00115  *
00116  * This reverses the effect of add_join_clause_to_rels.  It's used when we
00117  * discover that a relation need not be joined at all.
00118  *
00119  * 'restrictinfo' describes the join clause
00120  * 'join_relids' is the list of relations participating in the join clause
00121  *               (there must be more than one)
00122  */
00123 void
00124 remove_join_clause_from_rels(PlannerInfo *root,
00125                              RestrictInfo *restrictinfo,
00126                              Relids join_relids)
00127 {
00128     Relids      tmprelids;
00129     int         cur_relid;
00130 
00131     tmprelids = bms_copy(join_relids);
00132     while ((cur_relid = bms_first_member(tmprelids)) >= 0)
00133     {
00134         RelOptInfo *rel = find_base_rel(root, cur_relid);
00135 
00136         /*
00137          * Remove the restrictinfo from the list.  Pointer comparison is
00138          * sufficient.
00139          */
00140         Assert(list_member_ptr(rel->joininfo, restrictinfo));
00141         rel->joininfo = list_delete_ptr(rel->joininfo, restrictinfo);
00142     }
00143     bms_free(tmprelids);
00144 }