Line data    Source code

       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * joininfo.c
       4             :  *    joininfo list manipulation routines
       5             :  *
       6             :  * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
       7             :  * Portions Copyright (c) 1994, Regents of the University of California
       8             :  *
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *    src/backend/optimizer/util/joininfo.c
      12             :  *
      13             :  *-------------------------------------------------------------------------
      14             :  */
      15             : #include "postgres.h"
      16             : 
      17             : #include "optimizer/joininfo.h"
      18             : #include "optimizer/pathnode.h"
      19             : #include "optimizer/paths.h"
      20             : 
      21             : 
      22             : /*
      23             :  * have_relevant_joinclause
      24             :  *      Detect whether there is a joinclause that involves
      25             :  *      the two given relations.
      26             :  *
      27             :  * Note: the joinclause does not have to be evaluable with only these two
      28             :  * relations.  This is intentional.  For example consider
      29             :  *      SELECT * FROM a, b, c WHERE a.x = (b.y + c.z)
      30             :  * If a is much larger than the other tables, it may be worthwhile to
      31             :  * cross-join b and c and then use an inner indexscan on a.x.  Therefore
      32             :  * we should consider this joinclause as reason to join b to c, even though
      33             :  * it can't be applied at that join step.
      34             :  */
      35             : bool
      36      317602 : have_relevant_joinclause(PlannerInfo *root,
      37             :                          RelOptInfo *rel1, RelOptInfo *rel2)
      38             : {
      39      317602 :     bool        result = false;
      40             :     List       *joininfo;
      41             :     Relids      other_relids;
      42             :     ListCell   *l;
      43             : 
      44             :     /*
      45             :      * We could scan either relation's joininfo list; may as well use the
      46             :      * shorter one.
      47             :      */
      48      317602 :     if (list_length(rel1->joininfo) <= list_length(rel2->joininfo))
      49             :     {
      50      234034 :         joininfo = rel1->joininfo;
      51      234034 :         other_relids = rel2->relids;
      52             :     }
      53             :     else
      54             :     {
      55       83568 :         joininfo = rel2->joininfo;
      56       83568 :         other_relids = rel1->relids;
      57             :     }
      58             : 
      59      350812 :     foreach(l, joininfo)
      60             :     {
      61      169808 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
      62             : 
      63      169808 :         if (bms_overlap(other_relids, rinfo->required_relids))
      64             :         {
      65      136598 :             result = true;
      66      136598 :             break;
      67             :         }
      68             :     }
      69             : 
      70             :     /*
      71             :      * We also need to check the EquivalenceClass data structure, which might
      72             :      * contain relationships not emitted into the joininfo lists.
      73             :      */
      74      317602 :     if (!result && rel1->has_eclass_joins && rel2->has_eclass_joins)
      75      133198 :         result = have_relevant_eclass_joinclause(root, rel1, rel2);
      76             : 
      77      317602 :     return result;
      78             : }
      79             : 
      80             : 
      81             : /*
      82             :  * add_join_clause_to_rels
      83             :  *    Add 'restrictinfo' to the joininfo list of each relation it requires.
      84             :  *
      85             :  * Note that the same copy of the restrictinfo node is linked to by all the
      86             :  * lists it is in.  This allows us to exploit caching of information about
      87             :  * the restriction clause (but we must be careful that the information does
      88             :  * not depend on context).
      89             :  *
      90             :  * 'restrictinfo' describes the join clause
      91             :  * 'join_relids' is the set of relations participating in the join clause
      92             :  *               (some of these could be outer joins)
      93             :  */
      94             : void
      95       59088 : add_join_clause_to_rels(PlannerInfo *root,
      96             :                         RestrictInfo *restrictinfo,
      97             :                         Relids join_relids)
      98             : {
      99             :     int         cur_relid;
     100             : 
     101       59088 :     cur_relid = -1;
     102      190726 :     while ((cur_relid = bms_next_member(join_relids, cur_relid)) >= 0)
     103             :     {
     104      131638 :         RelOptInfo *rel = find_base_rel_ignore_join(root, cur_relid);
     105             : 
     106             :         /* We only need to add the clause to baserels */
     107      131638 :         if (rel == NULL)
     108        7850 :             continue;
     109      123788 :         rel->joininfo = lappend(rel->joininfo, restrictinfo);
     110             :     }
     111       59088 : }
     112             : 
     113             : /*
     114             :  * remove_join_clause_from_rels
     115             :  *    Delete 'restrictinfo' from all the joininfo lists it is in
     116             :  *
     117             :  * This reverses the effect of add_join_clause_to_rels.  It's used when we
     118             :  * discover that a relation need not be joined at all.
     119             :  *
     120             :  * 'restrictinfo' describes the join clause
     121             :  * 'join_relids' is the set of relations participating in the join clause
     122             :  *               (some of these could be outer joins)
     123             :  */
     124             : void
     125        8672 : remove_join_clause_from_rels(PlannerInfo *root,
     126             :                              RestrictInfo *restrictinfo,
     127             :                              Relids join_relids)
     128             : {
     129             :     int         cur_relid;
     130             : 
     131        8672 :     cur_relid = -1;
     132       26348 :     while ((cur_relid = bms_next_member(join_relids, cur_relid)) >= 0)
     133             :     {
     134       17676 :         RelOptInfo *rel = find_base_rel_ignore_join(root, cur_relid);
     135             : 
     136             :         /* We would only have added the clause to baserels */
     137       17676 :         if (rel == NULL)
     138         224 :             continue;
     139             : 
     140             :         /*
     141             :          * Remove the restrictinfo from the list.  Pointer comparison is
     142             :          * sufficient.
     143             :          */
     144             :         Assert(list_member_ptr(rel->joininfo, restrictinfo));
     145       17452 :         rel->joininfo = list_delete_ptr(rel->joininfo, restrictinfo);
     146             :     }
     147        8672 : }