LCOV - code coverage report
Current view: top level - src/backend/optimizer/plan - analyzejoins.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 648 672 96.4 %
Date: 2025-04-24 12:15:10 Functions: 26 26 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * analyzejoins.c
       4             :  *    Routines for simplifying joins after initial query analysis
       5             :  *
       6             :  * While we do a great deal of join simplification in prep/prepjointree.c,
       7             :  * certain optimizations cannot be performed at that stage for lack of
       8             :  * detailed information about the query.  The routines here are invoked
       9             :  * after initsplan.c has done its work, and can do additional join removal
      10             :  * and simplification steps based on the information extracted.  The penalty
      11             :  * is that we have to work harder to clean up after ourselves when we modify
      12             :  * the query, since the derived data structures have to be updated too.
      13             :  *
      14             :  * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
      15             :  * Portions Copyright (c) 1994, Regents of the University of California
      16             :  *
      17             :  *
      18             :  * IDENTIFICATION
      19             :  *    src/backend/optimizer/plan/analyzejoins.c
      20             :  *
      21             :  *-------------------------------------------------------------------------
      22             :  */
      23             : #include "postgres.h"
      24             : 
      25             : #include "catalog/pg_class.h"
      26             : #include "nodes/nodeFuncs.h"
      27             : #include "optimizer/joininfo.h"
      28             : #include "optimizer/optimizer.h"
      29             : #include "optimizer/pathnode.h"
      30             : #include "optimizer/paths.h"
      31             : #include "optimizer/placeholder.h"
      32             : #include "optimizer/planmain.h"
      33             : #include "optimizer/restrictinfo.h"
      34             : #include "rewrite/rewriteManip.h"
      35             : #include "utils/lsyscache.h"
      36             : 
      37             : /*
      38             :  * Utility structure.  A sorting procedure is needed to simplify the search
      39             :  * of SJE-candidate baserels referencing the same database relation.  Having
      40             :  * collected all baserels from the query jointree, the planner sorts them
      41             :  * according to the reloid value, groups them with the next pass and attempts
      42             :  * to remove self-joins.
      43             :  *
      44             :  * Preliminary sorting prevents quadratic behavior that can be harmful in the
      45             :  * case of numerous joins.
      46             :  */
      47             : typedef struct
      48             : {
      49             :     int         relid;
      50             :     Oid         reloid;
      51             : } SelfJoinCandidate;
      52             : 
      53             : bool        enable_self_join_elimination;
      54             : 
      55             : /* local functions */
      56             : static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
      57             : static void remove_leftjoinrel_from_query(PlannerInfo *root, int relid,
      58             :                                           SpecialJoinInfo *sjinfo);
      59             : static void remove_rel_from_restrictinfo(RestrictInfo *rinfo,
      60             :                                          int relid, int ojrelid);
      61             : static void remove_rel_from_eclass(EquivalenceClass *ec,
      62             :                                    SpecialJoinInfo *sjinfo,
      63             :                                    int relid, int subst);
      64             : static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
      65             : static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel);
      66             : static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel,
      67             :                                 List *clause_list, List **extra_clauses);
      68             : static Oid  distinct_col_search(int colno, List *colnos, List *opids);
      69             : static bool is_innerrel_unique_for(PlannerInfo *root,
      70             :                                    Relids joinrelids,
      71             :                                    Relids outerrelids,
      72             :                                    RelOptInfo *innerrel,
      73             :                                    JoinType jointype,
      74             :                                    List *restrictlist,
      75             :                                    List **extra_clauses);
      76             : static int  self_join_candidates_cmp(const void *a, const void *b);
      77             : 
      78             : 
      79             : /*
      80             :  * remove_useless_joins
      81             :  *      Check for relations that don't actually need to be joined at all,
      82             :  *      and remove them from the query.
      83             :  *
      84             :  * We are passed the current joinlist and return the updated list.  Other
      85             :  * data structures that have to be updated are accessible via "root".
      86             :  */
      87             : List *
      88      339930 : remove_useless_joins(PlannerInfo *root, List *joinlist)
      89             : {
      90             :     ListCell   *lc;
      91             : 
      92             :     /*
      93             :      * We are only interested in relations that are left-joined to, so we can
      94             :      * scan the join_info_list to find them easily.
      95             :      */
      96      339930 : restart:
      97      383872 :     foreach(lc, root->join_info_list)
      98             :     {
      99       54904 :         SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
     100             :         int         innerrelid;
     101             :         int         nremoved;
     102             : 
     103             :         /* Skip if not removable */
     104       54904 :         if (!join_is_removable(root, sjinfo))
     105       43942 :             continue;
     106             : 
     107             :         /*
     108             :          * Currently, join_is_removable can only succeed when the sjinfo's
     109             :          * righthand is a single baserel.  Remove that rel from the query and
     110             :          * joinlist.
     111             :          */
     112       10962 :         innerrelid = bms_singleton_member(sjinfo->min_righthand);
     113             : 
     114       10962 :         remove_leftjoinrel_from_query(root, innerrelid, sjinfo);
     115             : 
     116             :         /* We verify that exactly one reference gets removed from joinlist */
     117       10962 :         nremoved = 0;
     118       10962 :         joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
     119       10962 :         if (nremoved != 1)
     120           0 :             elog(ERROR, "failed to find relation %d in joinlist", innerrelid);
     121             : 
     122             :         /*
     123             :          * We can delete this SpecialJoinInfo from the list too, since it's no
     124             :          * longer of interest.  (Since we'll restart the foreach loop
     125             :          * immediately, we don't bother with foreach_delete_current.)
     126             :          */
     127       10962 :         root->join_info_list = list_delete_cell(root->join_info_list, lc);
     128             : 
     129             :         /*
     130             :          * Restart the scan.  This is necessary to ensure we find all
     131             :          * removable joins independently of ordering of the join_info_list
     132             :          * (note that removal of attr_needed bits may make a join appear
     133             :          * removable that did not before).
     134             :          */
     135       10962 :         goto restart;
     136             :     }
     137             : 
     138      328968 :     return joinlist;
     139             : }
     140             : 
     141             : /*
     142             :  * join_is_removable
     143             :  *    Check whether we need not perform this special join at all, because
     144             :  *    it will just duplicate its left input.
     145             :  *
     146             :  * This is true for a left join for which the join condition cannot match
     147             :  * more than one inner-side row.  (There are other possibly interesting
     148             :  * cases, but we don't have the infrastructure to prove them.)  We also
     149             :  * have to check that the inner side doesn't generate any variables needed
     150             :  * above the join.
     151             :  */
     152             : static bool
     153       54904 : join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
     154             : {
     155             :     int         innerrelid;
     156             :     RelOptInfo *innerrel;
     157             :     Relids      inputrelids;
     158             :     Relids      joinrelids;
     159       54904 :     List       *clause_list = NIL;
     160             :     ListCell   *l;
     161             :     int         attroff;
     162             : 
     163             :     /*
     164             :      * Must be a left join to a single baserel, else we aren't going to be
     165             :      * able to do anything with it.
     166             :      */
     167       54904 :     if (sjinfo->jointype != JOIN_LEFT)
     168        9940 :         return false;
     169             : 
     170       44964 :     if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
     171        1298 :         return false;
     172             : 
     173             :     /*
     174             :      * Never try to eliminate a left join to the query result rel.  Although
     175             :      * the case is syntactically impossible in standard SQL, MERGE will build
     176             :      * a join tree that looks exactly like that.
     177             :      */
     178       43666 :     if (innerrelid == root->parse->resultRelation)
     179         758 :         return false;
     180             : 
     181       42908 :     innerrel = find_base_rel(root, innerrelid);
     182             : 
     183             :     /*
     184             :      * Before we go to the effort of checking whether any innerrel variables
     185             :      * are needed above the join, make a quick check to eliminate cases in
     186             :      * which we will surely be unable to prove uniqueness of the innerrel.
     187             :      */
     188       42908 :     if (!rel_supports_distinctness(root, innerrel))
     189        3116 :         return false;
     190             : 
     191             :     /* Compute the relid set for the join we are considering */
     192       39792 :     inputrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
     193             :     Assert(sjinfo->ojrelid != 0);
     194       39792 :     joinrelids = bms_copy(inputrelids);
     195       39792 :     joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid);
     196             : 
     197             :     /*
     198             :      * We can't remove the join if any inner-rel attributes are used above the
     199             :      * join.  Here, "above" the join includes pushed-down conditions, so we
     200             :      * should reject if attr_needed includes the OJ's own relid; therefore,
     201             :      * compare to inputrelids not joinrelids.
     202             :      *
     203             :      * As a micro-optimization, it seems better to start with max_attr and
     204             :      * count down rather than starting with min_attr and counting up, on the
     205             :      * theory that the system attributes are somewhat less likely to be wanted
     206             :      * and should be tested last.
     207             :      */
     208      356730 :     for (attroff = innerrel->max_attr - innerrel->min_attr;
     209             :          attroff >= 0;
     210      316938 :          attroff--)
     211             :     {
     212      345606 :         if (!bms_is_subset(innerrel->attr_needed[attroff], inputrelids))
     213       28668 :             return false;
     214             :     }
     215             : 
     216             :     /*
     217             :      * Similarly check that the inner rel isn't needed by any PlaceHolderVars
     218             :      * that will be used above the join.  The PHV case is a little bit more
     219             :      * complicated, because PHVs may have been assigned a ph_eval_at location
     220             :      * that includes the innerrel, yet their contained expression might not
     221             :      * actually reference the innerrel (it could be just a constant, for
     222             :      * instance).  If such a PHV is due to be evaluated above the join then it
     223             :      * needn't prevent join removal.
     224             :      */
     225       11316 :     foreach(l, root->placeholder_list)
     226             :     {
     227         228 :         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
     228             : 
     229         228 :         if (bms_overlap(phinfo->ph_lateral, innerrel->relids))
     230          36 :             return false;       /* it references innerrel laterally */
     231         228 :         if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
     232          54 :             continue;           /* it definitely doesn't reference innerrel */
     233         174 :         if (bms_is_subset(phinfo->ph_needed, inputrelids))
     234           6 :             continue;           /* PHV is not used above the join */
     235         168 :         if (!bms_is_member(sjinfo->ojrelid, phinfo->ph_eval_at))
     236          30 :             return false;       /* it has to be evaluated below the join */
     237             : 
     238             :         /*
     239             :          * We need to be sure there will still be a place to evaluate the PHV
     240             :          * if we remove the join, ie that ph_eval_at wouldn't become empty.
     241             :          */
     242         138 :         if (!bms_overlap(sjinfo->min_lefthand, phinfo->ph_eval_at))
     243           6 :             return false;       /* there isn't any other place to eval PHV */
     244             :         /* Check contained expression last, since this is a bit expensive */
     245         132 :         if (bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),
     246         132 :                         innerrel->relids))
     247           0 :             return false;       /* contained expression references innerrel */
     248             :     }
     249             : 
     250             :     /*
     251             :      * Search for mergejoinable clauses that constrain the inner rel against
     252             :      * either the outer rel or a pseudoconstant.  If an operator is
     253             :      * mergejoinable then it behaves like equality for some btree opclass, so
     254             :      * it's what we want.  The mergejoinability test also eliminates clauses
     255             :      * containing volatile functions, which we couldn't depend on.
     256             :      */
     257       22486 :     foreach(l, innerrel->joininfo)
     258             :     {
     259       11398 :         RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
     260             : 
     261             :         /*
     262             :          * If the current join commutes with some other outer join(s) via
     263             :          * outer join identity 3, there will be multiple clones of its join
     264             :          * clauses in the joininfo list.  We want to consider only the
     265             :          * has_clone form of such clauses.  Processing more than one form
     266             :          * would be wasteful, and also some of the others would confuse the
     267             :          * RINFO_IS_PUSHED_DOWN test below.
     268             :          */
     269       11398 :         if (restrictinfo->is_clone)
     270         100 :             continue;           /* ignore it */
     271             : 
     272             :         /*
     273             :          * If it's not a join clause for this outer join, we can't use it.
     274             :          * Note that if the clause is pushed-down, then it is logically from
     275             :          * above the outer join, even if it references no other rels (it might
     276             :          * be from WHERE, for example).
     277             :          */
     278       11298 :         if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
     279         120 :             continue;           /* ignore; not useful here */
     280             : 
     281             :         /* Ignore if it's not a mergejoinable clause */
     282       11178 :         if (!restrictinfo->can_join ||
     283       11106 :             restrictinfo->mergeopfamilies == NIL)
     284          72 :             continue;           /* not mergejoinable */
     285             : 
     286             :         /*
     287             :          * Check if the clause has the form "outer op inner" or "inner op
     288             :          * outer", and if so mark which side is inner.
     289             :          */
     290       11106 :         if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
     291             :                                      innerrel->relids))
     292           6 :             continue;           /* no good for these input relations */
     293             : 
     294             :         /* OK, add to list */
     295       11100 :         clause_list = lappend(clause_list, restrictinfo);
     296             :     }
     297             : 
     298             :     /*
     299             :      * Now that we have the relevant equality join clauses, try to prove the
     300             :      * innerrel distinct.
     301             :      */
     302       11088 :     if (rel_is_distinct_for(root, innerrel, clause_list, NULL))
     303       10962 :         return true;
     304             : 
     305             :     /*
     306             :      * Some day it would be nice to check for other methods of establishing
     307             :      * distinctness.
     308             :      */
     309         126 :     return false;
     310             : }
     311             : 
     312             : 
     313             : /*
     314             :  * Remove the target rel->relid and references to the target join from the
     315             :  * planner's data structures, having determined that there is no need
     316             :  * to include them in the query. Optionally replace them with subst if subst
     317             :  * is non-negative.
     318             :  *
     319             :  * This function updates only parts needed for both left-join removal and
     320             :  * self-join removal.
     321             :  */
     322             : static void
     323       11550 : remove_rel_from_query(PlannerInfo *root, RelOptInfo *rel,
     324             :                       int subst, SpecialJoinInfo *sjinfo,
     325             :                       Relids joinrelids)
     326             : {
     327       11550 :     int         relid = rel->relid;
     328             :     Index       rti;
     329             :     ListCell   *l;
     330             : 
     331             :     /*
     332             :      * Update all_baserels and related relid sets.
     333             :      */
     334       11550 :     root->all_baserels = adjust_relid_set(root->all_baserels, relid, subst);
     335       11550 :     root->all_query_rels = adjust_relid_set(root->all_query_rels, relid, subst);
     336             : 
     337       11550 :     if (sjinfo != NULL)
     338             :     {
     339       21924 :         root->outer_join_rels = bms_del_member(root->outer_join_rels,
     340       10962 :                                                sjinfo->ojrelid);
     341       10962 :         root->all_query_rels = bms_del_member(root->all_query_rels,
     342       10962 :                                               sjinfo->ojrelid);
     343             :     }
     344             : 
     345             :     /*
     346             :      * Likewise remove references from SpecialJoinInfo data structures.
     347             :      *
     348             :      * This is relevant in case the outer join we're deleting is nested inside
     349             :      * other outer joins: the upper joins' relid sets have to be adjusted. The
     350             :      * RHS of the target outer join will be made empty here, but that's OK
     351             :      * since caller will delete that SpecialJoinInfo entirely.
     352             :      */
     353       26318 :     foreach(l, root->join_info_list)
     354             :     {
     355       14768 :         SpecialJoinInfo *sjinf = (SpecialJoinInfo *) lfirst(l);
     356             : 
     357             :         /*
     358             :          * initsplan.c is fairly cavalier about allowing SpecialJoinInfos'
     359             :          * lefthand/righthand relid sets to be shared with other data
     360             :          * structures.  Ensure that we don't modify the original relid sets.
     361             :          * (The commute_xxx sets are always per-SpecialJoinInfo though.)
     362             :          */
     363       14768 :         sjinf->min_lefthand = bms_copy(sjinf->min_lefthand);
     364       14768 :         sjinf->min_righthand = bms_copy(sjinf->min_righthand);
     365       14768 :         sjinf->syn_lefthand = bms_copy(sjinf->syn_lefthand);
     366       14768 :         sjinf->syn_righthand = bms_copy(sjinf->syn_righthand);
     367             :         /* Now remove relid from the sets: */
     368       14768 :         sjinf->min_lefthand = adjust_relid_set(sjinf->min_lefthand, relid, subst);
     369       14768 :         sjinf->min_righthand = adjust_relid_set(sjinf->min_righthand, relid, subst);
     370       14768 :         sjinf->syn_lefthand = adjust_relid_set(sjinf->syn_lefthand, relid, subst);
     371       14768 :         sjinf->syn_righthand = adjust_relid_set(sjinf->syn_righthand, relid, subst);
     372             : 
     373       14768 :         if (sjinfo != NULL)
     374             :         {
     375             :             Assert(subst <= 0);
     376             : 
     377             :             /* Remove sjinfo->ojrelid bits from the sets: */
     378       29344 :             sjinf->min_lefthand = bms_del_member(sjinf->min_lefthand,
     379       14672 :                                                  sjinfo->ojrelid);
     380       29344 :             sjinf->min_righthand = bms_del_member(sjinf->min_righthand,
     381       14672 :                                                   sjinfo->ojrelid);
     382       29344 :             sjinf->syn_lefthand = bms_del_member(sjinf->syn_lefthand,
     383       14672 :                                                  sjinfo->ojrelid);
     384       29344 :             sjinf->syn_righthand = bms_del_member(sjinf->syn_righthand,
     385       14672 :                                                   sjinfo->ojrelid);
     386             :             /* relid cannot appear in these fields, but ojrelid can: */
     387       29344 :             sjinf->commute_above_l = bms_del_member(sjinf->commute_above_l,
     388       14672 :                                                     sjinfo->ojrelid);
     389       29344 :             sjinf->commute_above_r = bms_del_member(sjinf->commute_above_r,
     390       14672 :                                                     sjinfo->ojrelid);
     391       29344 :             sjinf->commute_below_l = bms_del_member(sjinf->commute_below_l,
     392       14672 :                                                     sjinfo->ojrelid);
     393       14672 :             sjinf->commute_below_r = bms_del_member(sjinf->commute_below_r,
     394       14672 :                                                     sjinfo->ojrelid);
     395             :         }
     396             :         else
     397             :         {
     398             :             Assert(subst > 0);
     399             : 
     400          96 :             ChangeVarNodes((Node *) sjinf->semi_rhs_exprs, relid, subst, 0);
     401             :         }
     402             :     }
     403             : 
     404             :     /*
     405             :      * Likewise remove references from PlaceHolderVar data structures,
     406             :      * removing any no-longer-needed placeholders entirely.
     407             :      *
     408             :      * Removal is a bit trickier than it might seem: we can remove PHVs that
     409             :      * are used at the target rel and/or in the join qual, but not those that
     410             :      * are used at join partner rels or above the join.  It's not that easy to
     411             :      * distinguish PHVs used at partner rels from those used in the join qual,
     412             :      * since they will both have ph_needed sets that are subsets of
     413             :      * joinrelids.  However, a PHV used at a partner rel could not have the
     414             :      * target rel in ph_eval_at, so we check that while deciding whether to
     415             :      * remove or just update the PHV.  There is no corresponding test in
     416             :      * join_is_removable because it doesn't need to distinguish those cases.
     417             :      */
     418       11760 :     foreach(l, root->placeholder_list)
     419             :     {
     420         210 :         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
     421             : 
     422             :         Assert(sjinfo == NULL || !bms_is_member(relid, phinfo->ph_lateral));
     423         246 :         if (bms_is_subset(phinfo->ph_needed, joinrelids) &&
     424          54 :             bms_is_member(relid, phinfo->ph_eval_at) &&
     425          12 :             (sjinfo == NULL || !bms_is_member(sjinfo->ojrelid, phinfo->ph_eval_at)))
     426             :         {
     427          12 :             root->placeholder_list = foreach_delete_current(root->placeholder_list,
     428             :                                                             l);
     429          12 :             root->placeholder_array[phinfo->phid] = NULL;
     430             :         }
     431             :         else
     432             :         {
     433         198 :             PlaceHolderVar *phv = phinfo->ph_var;
     434             : 
     435         198 :             phinfo->ph_eval_at = adjust_relid_set(phinfo->ph_eval_at, relid, subst);
     436         198 :             if (sjinfo != NULL)
     437         168 :                 phinfo->ph_eval_at = adjust_relid_set(phinfo->ph_eval_at,
     438         168 :                                                       sjinfo->ojrelid, subst);
     439             :             Assert(!bms_is_empty(phinfo->ph_eval_at));   /* checked previously */
     440             :             /* Reduce ph_needed to contain only "relation 0"; see below */
     441         198 :             if (bms_is_member(0, phinfo->ph_needed))
     442         102 :                 phinfo->ph_needed = bms_make_singleton(0);
     443             :             else
     444          96 :                 phinfo->ph_needed = NULL;
     445             : 
     446         198 :             phinfo->ph_lateral = adjust_relid_set(phinfo->ph_lateral, relid, subst);
     447             : 
     448             :             /*
     449             :              * ph_lateral might contain rels mentioned in ph_eval_at after the
     450             :              * replacement, remove them.
     451             :              */
     452         198 :             phinfo->ph_lateral = bms_difference(phinfo->ph_lateral, phinfo->ph_eval_at);
     453             :             /* ph_lateral might or might not be empty */
     454             : 
     455         198 :             phv->phrels = adjust_relid_set(phv->phrels, relid, subst);
     456         198 :             if (sjinfo != NULL)
     457         168 :                 phv->phrels = adjust_relid_set(phv->phrels,
     458         168 :                                                sjinfo->ojrelid, subst);
     459             :             Assert(!bms_is_empty(phv->phrels));
     460             : 
     461         198 :             ChangeVarNodes((Node *) phv->phexpr, relid, subst, 0);
     462             : 
     463             :             Assert(phv->phnullingrels == NULL); /* no need to adjust */
     464             :         }
     465             :     }
     466             : 
     467             :     /*
     468             :      * Likewise remove references from EquivalenceClasses.
     469             :      */
     470       60642 :     foreach(l, root->eq_classes)
     471             :     {
     472       49092 :         EquivalenceClass *ec = (EquivalenceClass *) lfirst(l);
     473             : 
     474       49092 :         if (bms_is_member(relid, ec->ec_relids) ||
     475       32340 :             (sjinfo == NULL || bms_is_member(sjinfo->ojrelid, ec->ec_relids)))
     476       16752 :             remove_rel_from_eclass(ec, sjinfo, relid, subst);
     477             :     }
     478             : 
     479             :     /*
     480             :      * Finally, we must recompute per-Var attr_needed and per-PlaceHolderVar
     481             :      * ph_needed relid sets.  These have to be known accurately, else we may
     482             :      * fail to remove other now-removable outer joins.  And our removal of the
     483             :      * join clause(s) for this outer join may mean that Vars that were
     484             :      * formerly needed no longer are.  So we have to do this honestly by
     485             :      * repeating the construction of those relid sets.  We can cheat to one
     486             :      * small extent: we can avoid re-examining the targetlist and HAVING qual
     487             :      * by preserving "relation 0" bits from the existing relid sets.  This is
     488             :      * safe because we'd never remove such references.
     489             :      *
     490             :      * So, start by removing all other bits from attr_needed sets and
     491             :      * lateral_vars lists.  (We already did this above for ph_needed.)
     492             :      */
     493       71978 :     for (rti = 1; rti < root->simple_rel_array_size; rti++)
     494             :     {
     495       60428 :         RelOptInfo *otherrel = root->simple_rel_array[rti];
     496             :         int         attroff;
     497             : 
     498             :         /* there may be empty slots corresponding to non-baserel RTEs */
     499       60428 :         if (otherrel == NULL)
     500       29440 :             continue;
     501             : 
     502             :         Assert(otherrel->relid == rti); /* sanity check on array */
     503             : 
     504      687478 :         for (attroff = otherrel->max_attr - otherrel->min_attr;
     505             :              attroff >= 0;
     506      656490 :              attroff--)
     507             :         {
     508      656490 :             if (bms_is_member(0, otherrel->attr_needed[attroff]))
     509       46828 :                 otherrel->attr_needed[attroff] = bms_make_singleton(0);
     510             :             else
     511      609662 :                 otherrel->attr_needed[attroff] = NULL;
     512             :         }
     513             : 
     514       30988 :         if (subst > 0)
     515        1460 :             ChangeVarNodes((Node *) otherrel->lateral_vars, relid, subst, 0);
     516             :     }
     517       11550 : }
     518             : 
     519             : /*
     520             :  * Remove the target relid and references to the target join from the
     521             :  * planner's data structures, having determined that there is no need
     522             :  * to include them in the query.
     523             :  *
     524             :  * We are not terribly thorough here.  We only bother to update parts of
     525             :  * the planner's data structures that will actually be consulted later.
     526             :  */
     527             : static void
     528       10962 : remove_leftjoinrel_from_query(PlannerInfo *root, int relid,
     529             :                               SpecialJoinInfo *sjinfo)
     530             : {
     531       10962 :     RelOptInfo *rel = find_base_rel(root, relid);
     532       10962 :     int         ojrelid = sjinfo->ojrelid;
     533             :     Relids      joinrelids;
     534             :     Relids      join_plus_commute;
     535             :     List       *joininfos;
     536             :     ListCell   *l;
     537             : 
     538             :     /* Compute the relid set for the join we are considering */
     539       10962 :     joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
     540             :     Assert(ojrelid != 0);
     541       10962 :     joinrelids = bms_add_member(joinrelids, ojrelid);
     542             : 
     543       10962 :     remove_rel_from_query(root, rel, -1, sjinfo, joinrelids);
     544             : 
     545             :     /*
     546             :      * Remove any joinquals referencing the rel from the joininfo lists.
     547             :      *
     548             :      * In some cases, a joinqual has to be put back after deleting its
     549             :      * reference to the target rel.  This can occur for pseudoconstant and
     550             :      * outerjoin-delayed quals, which can get marked as requiring the rel in
     551             :      * order to force them to be evaluated at or above the join.  We can't
     552             :      * just discard them, though.  Only quals that logically belonged to the
     553             :      * outer join being discarded should be removed from the query.
     554             :      *
     555             :      * We might encounter a qual that is a clone of a deletable qual with some
     556             :      * outer-join relids added (see deconstruct_distribute_oj_quals).  To
     557             :      * ensure we get rid of such clones as well, add the relids of all OJs
     558             :      * commutable with this one to the set we test against for
     559             :      * pushed-down-ness.
     560             :      */
     561       10962 :     join_plus_commute = bms_union(joinrelids,
     562       10962 :                                   sjinfo->commute_above_r);
     563       10962 :     join_plus_commute = bms_add_members(join_plus_commute,
     564       10962 :                                         sjinfo->commute_below_l);
     565             : 
     566             :     /*
     567             :      * We must make a copy of the rel's old joininfo list before starting the
     568             :      * loop, because otherwise remove_join_clause_from_rels would destroy the
     569             :      * list while we're scanning it.
     570             :      */
     571       10962 :     joininfos = list_copy(rel->joininfo);
     572       22258 :     foreach(l, joininfos)
     573             :     {
     574       11296 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
     575             : 
     576       11296 :         remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
     577             : 
     578       11296 :         if (RINFO_IS_PUSHED_DOWN(rinfo, join_plus_commute))
     579             :         {
     580             :             /*
     581             :              * There might be references to relid or ojrelid in the
     582             :              * RestrictInfo's relid sets, as a consequence of PHVs having had
     583             :              * ph_eval_at sets that include those.  We already checked above
     584             :              * that any such PHV is safe (and updated its ph_eval_at), so we
     585             :              * can just drop those references.
     586             :              */
     587         120 :             remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
     588             : 
     589             :             /*
     590             :              * Cross-check that the clause itself does not reference the
     591             :              * target rel or join.
     592             :              */
     593             : #ifdef USE_ASSERT_CHECKING
     594             :             {
     595             :                 Relids      clause_varnos = pull_varnos(root,
     596             :                                                         (Node *) rinfo->clause);
     597             : 
     598             :                 Assert(!bms_is_member(relid, clause_varnos));
     599             :                 Assert(!bms_is_member(ojrelid, clause_varnos));
     600             :             }
     601             : #endif
     602             :             /* Now throw it back into the joininfo lists */
     603         120 :             distribute_restrictinfo_to_rels(root, rinfo);
     604             :         }
     605             :     }
     606             : 
     607             :     /*
     608             :      * There may be references to the rel in root->fkey_list, but if so,
     609             :      * match_foreign_keys_to_quals() will get rid of them.
     610             :      */
     611             : 
     612             :     /*
     613             :      * Now remove the rel from the baserel array to prevent it from being
     614             :      * referenced again.  (We can't do this earlier because
     615             :      * remove_join_clause_from_rels will touch it.)
     616             :      */
     617       10962 :     root->simple_rel_array[relid] = NULL;
     618             : 
     619             :     /* And nuke the RelOptInfo, just in case there's another access path */
     620       10962 :     pfree(rel);
     621             : 
     622             :     /*
     623             :      * Now repeat construction of attr_needed bits coming from all other
     624             :      * sources.
     625             :      */
     626       10962 :     rebuild_placeholder_attr_needed(root);
     627       10962 :     rebuild_joinclause_attr_needed(root);
     628       10962 :     rebuild_eclass_attr_needed(root);
     629       10962 :     rebuild_lateral_attr_needed(root);
     630       10962 : }
     631             : 
     632             : /*
     633             :  * Remove any references to relid or ojrelid from the RestrictInfo.
     634             :  *
     635             :  * We only bother to clean out bits in clause_relids and required_relids,
     636             :  * not nullingrel bits in contained Vars and PHVs.  (This might have to be
     637             :  * improved sometime.)  However, if the RestrictInfo contains an OR clause
     638             :  * we have to also clean up the sub-clauses.
     639             :  */
     640             : static void
     641        4788 : remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
     642             : {
     643             :     /*
     644             :      * initsplan.c is fairly cavalier about allowing RestrictInfos to share
     645             :      * relid sets with other RestrictInfos, and SpecialJoinInfos too.  Make
     646             :      * sure this RestrictInfo has its own relid sets before we modify them.
     647             :      * (In present usage, clause_relids is probably not shared, but
     648             :      * required_relids could be; let's not assume anything.)
     649             :      */
     650        4788 :     rinfo->clause_relids = bms_copy(rinfo->clause_relids);
     651        4788 :     rinfo->clause_relids = bms_del_member(rinfo->clause_relids, relid);
     652        4788 :     rinfo->clause_relids = bms_del_member(rinfo->clause_relids, ojrelid);
     653             :     /* Likewise for required_relids */
     654        4788 :     rinfo->required_relids = bms_copy(rinfo->required_relids);
     655        4788 :     rinfo->required_relids = bms_del_member(rinfo->required_relids, relid);
     656        4788 :     rinfo->required_relids = bms_del_member(rinfo->required_relids, ojrelid);
     657             : 
     658             :     /* If it's an OR, recurse to clean up sub-clauses */
     659        4788 :     if (restriction_is_or_clause(rinfo))
     660             :     {
     661             :         ListCell   *lc;
     662             : 
     663             :         Assert(is_orclause(rinfo->orclause));
     664          18 :         foreach(lc, ((BoolExpr *) rinfo->orclause)->args)
     665             :         {
     666          12 :             Node       *orarg = (Node *) lfirst(lc);
     667             : 
     668             :             /* OR arguments should be ANDs or sub-RestrictInfos */
     669          12 :             if (is_andclause(orarg))
     670             :             {
     671           0 :                 List       *andargs = ((BoolExpr *) orarg)->args;
     672             :                 ListCell   *lc2;
     673             : 
     674           0 :                 foreach(lc2, andargs)
     675             :                 {
     676           0 :                     RestrictInfo *rinfo2 = lfirst_node(RestrictInfo, lc2);
     677             : 
     678           0 :                     remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
     679             :                 }
     680             :             }
     681             :             else
     682             :             {
     683          12 :                 RestrictInfo *rinfo2 = castNode(RestrictInfo, orarg);
     684             : 
     685          12 :                 remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
     686             :             }
     687             :         }
     688             :     }
     689        4788 : }
     690             : 
     691             : /*
     692             :  * Remove any references to relid or sjinfo->ojrelid (if sjinfo != NULL)
     693             :  * from the EquivalenceClass.
     694             :  *
     695             :  * Like remove_rel_from_restrictinfo, we don't worry about cleaning out
     696             :  * any nullingrel bits in contained Vars and PHVs.  (This might have to be
     697             :  * improved sometime.)  We do need to fix the EC and EM relid sets to ensure
     698             :  * that implied join equalities will be generated at the appropriate join
     699             :  * level(s).
     700             :  */
     701             : static void
     702       16752 : remove_rel_from_eclass(EquivalenceClass *ec, SpecialJoinInfo *sjinfo,
     703             :                        int relid, int subst)
     704             : {
     705             :     ListCell   *lc;
     706             : 
     707             :     /* Fix up the EC's overall relids */
     708       16752 :     ec->ec_relids = adjust_relid_set(ec->ec_relids, relid, subst);
     709       16752 :     if (sjinfo != NULL)
     710       15714 :         ec->ec_relids = adjust_relid_set(ec->ec_relids,
     711       15714 :                                          sjinfo->ojrelid, subst);
     712             : 
     713             :     /*
     714             :      * We don't expect any EC child members to exist at this point.  Ensure
     715             :      * that's the case, otherwise, we might be getting asked to do something
     716             :      * this function hasn't been coded for.
     717             :      */
     718             :     Assert(ec->ec_childmembers == NULL);
     719             : 
     720             :     /*
     721             :      * Fix up the member expressions.  Any non-const member that ends with
     722             :      * empty em_relids must be a Var or PHV of the removed relation.  We don't
     723             :      * need it anymore, so we can drop it.
     724             :      */
     725       38930 :     foreach(lc, ec->ec_members)
     726             :     {
     727       22178 :         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
     728             : 
     729       22178 :         if (bms_is_member(relid, cur_em->em_relids) ||
     730        4656 :             (sjinfo != NULL && bms_is_member(sjinfo->ojrelid,
     731        4656 :                                              cur_em->em_relids)))
     732             :         {
     733             :             Assert(!cur_em->em_is_const);
     734       15714 :             cur_em->em_relids = adjust_relid_set(cur_em->em_relids, relid, subst);
     735       15714 :             if (sjinfo != NULL)
     736       15714 :                 cur_em->em_relids = adjust_relid_set(cur_em->em_relids,
     737       15714 :                                                      sjinfo->ojrelid, subst);
     738       15714 :             if (bms_is_empty(cur_em->em_relids))
     739       15702 :                 ec->ec_members = foreach_delete_current(ec->ec_members, lc);
     740             :         }
     741             :     }
     742             : 
     743             :     /* Fix up the source clauses, in case we can re-use them later */
     744       22446 :     foreach(lc, ec->ec_sources)
     745             :     {
     746        5694 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
     747             : 
     748        5694 :         if (sjinfo == NULL)
     749        1038 :             ChangeVarNodes((Node *) rinfo, relid, subst, 0);
     750             :         else
     751        4656 :             remove_rel_from_restrictinfo(rinfo, relid, sjinfo->ojrelid);
     752             :     }
     753             : 
     754             :     /*
     755             :      * Rather than expend code on fixing up any already-derived clauses, just
     756             :      * drop them.  (At this point, any such clauses would be base restriction
     757             :      * clauses, which we'd not need anymore anyway.)
     758             :      */
     759       16752 :     ec_clear_derived_clauses(ec);
     760       16752 : }
     761             : 
     762             : /*
     763             :  * Remove any occurrences of the target relid from a joinlist structure.
     764             :  *
     765             :  * It's easiest to build a whole new list structure, so we handle it that
     766             :  * way.  Efficiency is not a big deal here.
     767             :  *
     768             :  * *nremoved is incremented by the number of occurrences removed (there
     769             :  * should be exactly one, but the caller checks that).
     770             :  */
     771             : static List *
     772       11814 : remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
     773             : {
     774       11814 :     List       *result = NIL;
     775             :     ListCell   *jl;
     776             : 
     777       43066 :     foreach(jl, joinlist)
     778             :     {
     779       31252 :         Node       *jlnode = (Node *) lfirst(jl);
     780             : 
     781       31252 :         if (IsA(jlnode, RangeTblRef))
     782             :         {
     783       30988 :             int         varno = ((RangeTblRef *) jlnode)->rtindex;
     784             : 
     785       30988 :             if (varno == relid)
     786       11550 :                 (*nremoved)++;
     787             :             else
     788       19438 :                 result = lappend(result, jlnode);
     789             :         }
     790         264 :         else if (IsA(jlnode, List))
     791             :         {
     792             :             /* Recurse to handle subproblem */
     793             :             List       *sublist;
     794             : 
     795         264 :             sublist = remove_rel_from_joinlist((List *) jlnode,
     796             :                                                relid, nremoved);
     797             :             /* Avoid including empty sub-lists in the result */
     798         264 :             if (sublist)
     799         264 :                 result = lappend(result, sublist);
     800             :         }
     801             :         else
     802             :         {
     803           0 :             elog(ERROR, "unrecognized joinlist node type: %d",
     804             :                  (int) nodeTag(jlnode));
     805             :         }
     806             :     }
     807             : 
     808       11814 :     return result;
     809             : }
     810             : 
     811             : 
     812             : /*
     813             :  * reduce_unique_semijoins
     814             :  *      Check for semijoins that can be simplified to plain inner joins
     815             :  *      because the inner relation is provably unique for the join clauses.
     816             :  *
     817             :  * Ideally this would happen during reduce_outer_joins, but we don't have
     818             :  * enough information at that point.
     819             :  *
     820             :  * To perform the strength reduction when applicable, we need only delete
     821             :  * the semijoin's SpecialJoinInfo from root->join_info_list.  (We don't
     822             :  * bother fixing the join type attributed to it in the query jointree,
     823             :  * since that won't be consulted again.)
     824             :  */
     825             : void
     826      328968 : reduce_unique_semijoins(PlannerInfo *root)
     827             : {
     828             :     ListCell   *lc;
     829             : 
     830             :     /*
     831             :      * Scan the join_info_list to find semijoins.
     832             :      */
     833      372684 :     foreach(lc, root->join_info_list)
     834             :     {
     835       43716 :         SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
     836             :         int         innerrelid;
     837             :         RelOptInfo *innerrel;
     838             :         Relids      joinrelids;
     839             :         List       *restrictlist;
     840             : 
     841             :         /*
     842             :          * Must be a semijoin to a single baserel, else we aren't going to be
     843             :          * able to do anything with it.
     844             :          */
     845       43716 :         if (sjinfo->jointype != JOIN_SEMI)
     846       43406 :             continue;
     847             : 
     848        4812 :         if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
     849         164 :             continue;
     850             : 
     851        4648 :         innerrel = find_base_rel(root, innerrelid);
     852             : 
     853             :         /*
     854             :          * Before we trouble to run generate_join_implied_equalities, make a
     855             :          * quick check to eliminate cases in which we will surely be unable to
     856             :          * prove uniqueness of the innerrel.
     857             :          */
     858        4648 :         if (!rel_supports_distinctness(root, innerrel))
     859         944 :             continue;
     860             : 
     861             :         /* Compute the relid set for the join we are considering */
     862        3704 :         joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
     863             :         Assert(sjinfo->ojrelid == 0);    /* SEMI joins don't have RT indexes */
     864             : 
     865             :         /*
     866             :          * Since we're only considering a single-rel RHS, any join clauses it
     867             :          * has must be clauses linking it to the semijoin's min_lefthand.  We
     868             :          * can also consider EC-derived join clauses.
     869             :          */
     870             :         restrictlist =
     871        3704 :             list_concat(generate_join_implied_equalities(root,
     872             :                                                          joinrelids,
     873             :                                                          sjinfo->min_lefthand,
     874             :                                                          innerrel,
     875             :                                                          NULL),
     876        3704 :                         innerrel->joininfo);
     877             : 
     878             :         /* Test whether the innerrel is unique for those clauses. */
     879        3704 :         if (!innerrel_is_unique(root,
     880             :                                 joinrelids, sjinfo->min_lefthand, innerrel,
     881             :                                 JOIN_SEMI, restrictlist, true))
     882        3394 :             continue;
     883             : 
     884             :         /* OK, remove the SpecialJoinInfo from the list. */
     885         310 :         root->join_info_list = foreach_delete_current(root->join_info_list, lc);
     886             :     }
     887      328968 : }
     888             : 
     889             : 
     890             : /*
     891             :  * rel_supports_distinctness
     892             :  *      Could the relation possibly be proven distinct on some set of columns?
     893             :  *
     894             :  * This is effectively a pre-checking function for rel_is_distinct_for().
     895             :  * It must return true if rel_is_distinct_for() could possibly return true
     896             :  * with this rel, but it should not expend a lot of cycles.  The idea is
     897             :  * that callers can avoid doing possibly-expensive processing to compute
     898             :  * rel_is_distinct_for()'s argument lists if the call could not possibly
     899             :  * succeed.
     900             :  */
     901             : static bool
     902      614782 : rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
     903             : {
     904             :     /* We only know about baserels ... */
     905      614782 :     if (rel->reloptkind != RELOPT_BASEREL)
     906      201298 :         return false;
     907      413484 :     if (rel->rtekind == RTE_RELATION)
     908             :     {
     909             :         /*
     910             :          * For a plain relation, we only know how to prove uniqueness by
     911             :          * reference to unique indexes.  Make sure there's at least one
     912             :          * suitable unique index.  It must be immediately enforced, and not a
     913             :          * partial index. (Keep these conditions in sync with
     914             :          * relation_has_unique_index_for!)
     915             :          */
     916             :         ListCell   *lc;
     917             : 
     918      523678 :         foreach(lc, rel->indexlist)
     919             :         {
     920      470414 :             IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
     921             : 
     922      470414 :             if (ind->unique && ind->immediate && ind->indpred == NIL)
     923      322472 :                 return true;
     924             :         }
     925             :     }
     926       37748 :     else if (rel->rtekind == RTE_SUBQUERY)
     927             :     {
     928       10130 :         Query      *subquery = root->simple_rte_array[rel->relid]->subquery;
     929             : 
     930             :         /* Check if the subquery has any qualities that support distinctness */
     931       10130 :         if (query_supports_distinctness(subquery))
     932        8212 :             return true;
     933             :     }
     934             :     /* We have no proof rules for any other rtekinds. */
     935       82800 :     return false;
     936             : }
     937             : 
     938             : /*
     939             :  * rel_is_distinct_for
     940             :  *      Does the relation return only distinct rows according to clause_list?
     941             :  *
     942             :  * clause_list is a list of join restriction clauses involving this rel and
     943             :  * some other one.  Return true if no two rows emitted by this rel could
     944             :  * possibly join to the same row of the other rel.
     945             :  *
     946             :  * The caller must have already determined that each condition is a
     947             :  * mergejoinable equality with an expression in this relation on one side, and
     948             :  * an expression not involving this relation on the other.  The transient
     949             :  * outer_is_left flag is used to identify which side references this relation:
     950             :  * left side if outer_is_left is false, right side if it is true.
     951             :  *
     952             :  * Note that the passed-in clause_list may be destructively modified!  This
     953             :  * is OK for current uses, because the clause_list is built by the caller for
     954             :  * the sole purpose of passing to this function.
     955             :  *
     956             :  * (*extra_clauses) to be set to the right sides of baserestrictinfo clauses,
     957             :  * looking like "x = const" if distinctness is derived from such clauses, not
     958             :  * joininfo clauses.  Pass NULL to the extra_clauses if this value is not
     959             :  * needed.
     960             :  */
     961             : static bool
     962      209214 : rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list,
     963             :                     List **extra_clauses)
     964             : {
     965             :     /*
     966             :      * We could skip a couple of tests here if we assume all callers checked
     967             :      * rel_supports_distinctness first, but it doesn't seem worth taking any
     968             :      * risk for.
     969             :      */
     970      209214 :     if (rel->reloptkind != RELOPT_BASEREL)
     971           0 :         return false;
     972      209214 :     if (rel->rtekind == RTE_RELATION)
     973             :     {
     974             :         /*
     975             :          * Examine the indexes to see if we have a matching unique index.
     976             :          * relation_has_unique_index_ext automatically adds any usable
     977             :          * restriction clauses for the rel, so we needn't do that here.
     978             :          */
     979      204542 :         if (relation_has_unique_index_ext(root, rel, clause_list, NIL, NIL,
     980             :                                           extra_clauses))
     981      117166 :             return true;
     982             :     }
     983        4672 :     else if (rel->rtekind == RTE_SUBQUERY)
     984             :     {
     985        4672 :         Index       relid = rel->relid;
     986        4672 :         Query      *subquery = root->simple_rte_array[relid]->subquery;
     987        4672 :         List       *colnos = NIL;
     988        4672 :         List       *opids = NIL;
     989             :         ListCell   *l;
     990             : 
     991             :         /*
     992             :          * Build the argument lists for query_is_distinct_for: a list of
     993             :          * output column numbers that the query needs to be distinct over, and
     994             :          * a list of equality operators that the output columns need to be
     995             :          * distinct according to.
     996             :          *
     997             :          * (XXX we are not considering restriction clauses attached to the
     998             :          * subquery; is that worth doing?)
     999             :          */
    1000        9308 :         foreach(l, clause_list)
    1001             :         {
    1002        4636 :             RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
    1003             :             Oid         op;
    1004             :             Var        *var;
    1005             : 
    1006             :             /*
    1007             :              * Get the equality operator we need uniqueness according to.
    1008             :              * (This might be a cross-type operator and thus not exactly the
    1009             :              * same operator the subquery would consider; that's all right
    1010             :              * since query_is_distinct_for can resolve such cases.)  The
    1011             :              * caller's mergejoinability test should have selected only
    1012             :              * OpExprs.
    1013             :              */
    1014        4636 :             op = castNode(OpExpr, rinfo->clause)->opno;
    1015             : 
    1016             :             /* caller identified the inner side for us */
    1017        4636 :             if (rinfo->outer_is_left)
    1018        4298 :                 var = (Var *) get_rightop(rinfo->clause);
    1019             :             else
    1020         338 :                 var = (Var *) get_leftop(rinfo->clause);
    1021             : 
    1022             :             /*
    1023             :              * We may ignore any RelabelType node above the operand.  (There
    1024             :              * won't be more than one, since eval_const_expressions() has been
    1025             :              * applied already.)
    1026             :              */
    1027        4636 :             if (var && IsA(var, RelabelType))
    1028        3176 :                 var = (Var *) ((RelabelType *) var)->arg;
    1029             : 
    1030             :             /*
    1031             :              * If inner side isn't a Var referencing a subquery output column,
    1032             :              * this clause doesn't help us.
    1033             :              */
    1034        4636 :             if (!var || !IsA(var, Var) ||
    1035        4624 :                 var->varno != relid || var->varlevelsup != 0)
    1036          12 :                 continue;
    1037             : 
    1038        4624 :             colnos = lappend_int(colnos, var->varattno);
    1039        4624 :             opids = lappend_oid(opids, op);
    1040             :         }
    1041             : 
    1042        4672 :         if (query_is_distinct_for(subquery, colnos, opids))
    1043         212 :             return true;
    1044             :     }
    1045       91836 :     return false;
    1046             : }
    1047             : 
    1048             : 
    1049             : /*
    1050             :  * query_supports_distinctness - could the query possibly be proven distinct
    1051             :  *      on some set of output columns?
    1052             :  *
    1053             :  * This is effectively a pre-checking function for query_is_distinct_for().
    1054             :  * It must return true if query_is_distinct_for() could possibly return true
    1055             :  * with this query, but it should not expend a lot of cycles.  The idea is
    1056             :  * that callers can avoid doing possibly-expensive processing to compute
    1057             :  * query_is_distinct_for()'s argument lists if the call could not possibly
    1058             :  * succeed.
    1059             :  */
    1060             : bool
    1061       13432 : query_supports_distinctness(Query *query)
    1062             : {
    1063             :     /* SRFs break distinctness except with DISTINCT, see below */
    1064       13432 :     if (query->hasTargetSRFs && query->distinctClause == NIL)
    1065        1008 :         return false;
    1066             : 
    1067             :     /* check for features we can prove distinctness with */
    1068       12424 :     if (query->distinctClause != NIL ||
    1069       12280 :         query->groupClause != NIL ||
    1070       12092 :         query->groupingSets != NIL ||
    1071       12092 :         query->hasAggs ||
    1072       11820 :         query->havingQual ||
    1073       11820 :         query->setOperations)
    1074       11460 :         return true;
    1075             : 
    1076         964 :     return false;
    1077             : }
    1078             : 
    1079             : /*
    1080             :  * query_is_distinct_for - does query never return duplicates of the
    1081             :  *      specified columns?
    1082             :  *
    1083             :  * query is a not-yet-planned subquery (in current usage, it's always from
    1084             :  * a subquery RTE, which the planner avoids scribbling on).
    1085             :  *
    1086             :  * colnos is an integer list of output column numbers (resno's).  We are
    1087             :  * interested in whether rows consisting of just these columns are certain
    1088             :  * to be distinct.  "Distinctness" is defined according to whether the
    1089             :  * corresponding upper-level equality operators listed in opids would think
    1090             :  * the values are distinct.  (Note: the opids entries could be cross-type
    1091             :  * operators, and thus not exactly the equality operators that the subquery
    1092             :  * would use itself.  We use equality_ops_are_compatible() to check
    1093             :  * compatibility.  That looks at opfamily membership for index AMs that have
    1094             :  * declared that they support consistent equality semantics within an
    1095             :  * opfamily, and so should give trustworthy answers for all operators that we
    1096             :  * might need to deal with here.)
    1097             :  */
    1098             : bool
    1099        4868 : query_is_distinct_for(Query *query, List *colnos, List *opids)
    1100             : {
    1101             :     ListCell   *l;
    1102             :     Oid         opid;
    1103             : 
    1104             :     Assert(list_length(colnos) == list_length(opids));
    1105             : 
    1106             :     /*
    1107             :      * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
    1108             :      * columns in the DISTINCT clause appear in colnos and operator semantics
    1109             :      * match.  This is true even if there are SRFs in the DISTINCT columns or
    1110             :      * elsewhere in the tlist.
    1111             :      */
    1112        4868 :     if (query->distinctClause)
    1113             :     {
    1114         150 :         foreach(l, query->distinctClause)
    1115             :         {
    1116         120 :             SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
    1117         120 :             TargetEntry *tle = get_sortgroupclause_tle(sgc,
    1118             :                                                        query->targetList);
    1119             : 
    1120         120 :             opid = distinct_col_search(tle->resno, colnos, opids);
    1121         120 :             if (!OidIsValid(opid) ||
    1122          48 :                 !equality_ops_are_compatible(opid, sgc->eqop))
    1123             :                 break;          /* exit early if no match */
    1124             :         }
    1125         102 :         if (l == NULL)          /* had matches for all? */
    1126          30 :             return true;
    1127             :     }
    1128             : 
    1129             :     /*
    1130             :      * Otherwise, a set-returning function in the query's targetlist can
    1131             :      * result in returning duplicate rows, despite any grouping that might
    1132             :      * occur before tlist evaluation.  (If all tlist SRFs are within GROUP BY
    1133             :      * columns, it would be safe because they'd be expanded before grouping.
    1134             :      * But it doesn't currently seem worth the effort to check for that.)
    1135             :      */
    1136        4838 :     if (query->hasTargetSRFs)
    1137           0 :         return false;
    1138             : 
    1139             :     /*
    1140             :      * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if all
    1141             :      * the grouped columns appear in colnos and operator semantics match.
    1142             :      */
    1143        4838 :     if (query->groupClause && !query->groupingSets)
    1144             :     {
    1145         234 :         foreach(l, query->groupClause)
    1146             :         {
    1147         164 :             SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
    1148         164 :             TargetEntry *tle = get_sortgroupclause_tle(sgc,
    1149             :                                                        query->targetList);
    1150             : 
    1151         164 :             opid = distinct_col_search(tle->resno, colnos, opids);
    1152         164 :             if (!OidIsValid(opid) ||
    1153         112 :                 !equality_ops_are_compatible(opid, sgc->eqop))
    1154             :                 break;          /* exit early if no match */
    1155             :         }
    1156         122 :         if (l == NULL)          /* had matches for all? */
    1157          70 :             return true;
    1158             :     }
    1159        4716 :     else if (query->groupingSets)
    1160             :     {
    1161             :         /*
    1162             :          * If we have grouping sets with expressions, we probably don't have
    1163             :          * uniqueness and analysis would be hard. Punt.
    1164             :          */
    1165           0 :         if (query->groupClause)
    1166           0 :             return false;
    1167             : 
    1168             :         /*
    1169             :          * If we have no groupClause (therefore no grouping expressions), we
    1170             :          * might have one or many empty grouping sets. If there's just one,
    1171             :          * then we're returning only one row and are certainly unique. But
    1172             :          * otherwise, we know we're certainly not unique.
    1173             :          */
    1174           0 :         if (list_length(query->groupingSets) == 1 &&
    1175           0 :             ((GroupingSet *) linitial(query->groupingSets))->kind == GROUPING_SET_EMPTY)
    1176           0 :             return true;
    1177             :         else
    1178           0 :             return false;
    1179             :     }
    1180             :     else
    1181             :     {
    1182             :         /*
    1183             :          * If we have no GROUP BY, but do have aggregates or HAVING, then the
    1184             :          * result is at most one row so it's surely unique, for any operators.
    1185             :          */
    1186        4716 :         if (query->hasAggs || query->havingQual)
    1187         100 :             return true;
    1188             :     }
    1189             : 
    1190             :     /*
    1191             :      * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
    1192             :      * except with ALL.
    1193             :      */
    1194        4668 :     if (query->setOperations)
    1195             :     {
    1196        4544 :         SetOperationStmt *topop = castNode(SetOperationStmt, query->setOperations);
    1197             : 
    1198             :         Assert(topop->op != SETOP_NONE);
    1199             : 
    1200        4544 :         if (!topop->all)
    1201             :         {
    1202             :             ListCell   *lg;
    1203             : 
    1204             :             /* We're good if all the nonjunk output columns are in colnos */
    1205          72 :             lg = list_head(topop->groupClauses);
    1206          90 :             foreach(l, query->targetList)
    1207             :             {
    1208          78 :                 TargetEntry *tle = (TargetEntry *) lfirst(l);
    1209             :                 SortGroupClause *sgc;
    1210             : 
    1211          78 :                 if (tle->resjunk)
    1212           0 :                     continue;   /* ignore resjunk columns */
    1213             : 
    1214             :                 /* non-resjunk columns should have grouping clauses */
    1215             :                 Assert(lg != NULL);
    1216          78 :                 sgc = (SortGroupClause *) lfirst(lg);
    1217          78 :                 lg = lnext(topop->groupClauses, lg);
    1218             : 
    1219          78 :                 opid = distinct_col_search(tle->resno, colnos, opids);
    1220          78 :                 if (!OidIsValid(opid) ||
    1221          18 :                     !equality_ops_are_compatible(opid, sgc->eqop))
    1222             :                     break;      /* exit early if no match */
    1223             :             }
    1224          72 :             if (l == NULL)      /* had matches for all? */
    1225          12 :                 return true;
    1226             :         }
    1227             :     }
    1228             : 
    1229             :     /*
    1230             :      * XXX Are there any other cases in which we can easily see the result
    1231             :      * must be distinct?
    1232             :      *
    1233             :      * If you do add more smarts to this function, be sure to update
    1234             :      * query_supports_distinctness() to match.
    1235             :      */
    1236             : 
    1237        4656 :     return false;
    1238             : }
    1239             : 
    1240             : /*
    1241             :  * distinct_col_search - subroutine for query_is_distinct_for
    1242             :  *
    1243             :  * If colno is in colnos, return the corresponding element of opids,
    1244             :  * else return InvalidOid.  (Ordinarily colnos would not contain duplicates,
    1245             :  * but if it does, we arbitrarily select the first match.)
    1246             :  */
    1247             : static Oid
    1248         362 : distinct_col_search(int colno, List *colnos, List *opids)
    1249             : {
    1250             :     ListCell   *lc1,
    1251             :                *lc2;
    1252             : 
    1253         574 :     forboth(lc1, colnos, lc2, opids)
    1254             :     {
    1255         390 :         if (colno == lfirst_int(lc1))
    1256         178 :             return lfirst_oid(lc2);
    1257             :     }
    1258         184 :     return InvalidOid;
    1259             : }
    1260             : 
    1261             : 
    1262             : /*
    1263             :  * innerrel_is_unique
    1264             :  *    Check if the innerrel provably contains at most one tuple matching any
    1265             :  *    tuple from the outerrel, based on join clauses in the 'restrictlist'.
    1266             :  *
    1267             :  * We need an actual RelOptInfo for the innerrel, but it's sufficient to
    1268             :  * identify the outerrel by its Relids.  This asymmetry supports use of this
    1269             :  * function before joinrels have been built.  (The caller is expected to
    1270             :  * also supply the joinrelids, just to save recalculating that.)
    1271             :  *
    1272             :  * The proof must be made based only on clauses that will be "joinquals"
    1273             :  * rather than "otherquals" at execution.  For an inner join there's no
    1274             :  * difference; but if the join is outer, we must ignore pushed-down quals,
    1275             :  * as those will become "otherquals".  Note that this means the answer might
    1276             :  * vary depending on whether IS_OUTER_JOIN(jointype); since we cache the
    1277             :  * answer without regard to that, callers must take care not to call this
    1278             :  * with jointypes that would be classified differently by IS_OUTER_JOIN().
    1279             :  *
    1280             :  * The actual proof is undertaken by is_innerrel_unique_for(); this function
    1281             :  * is a frontend that is mainly concerned with caching the answers.
    1282             :  * In particular, the force_cache argument allows overriding the internal
    1283             :  * heuristic about whether to cache negative answers; it should be "true"
    1284             :  * if making an inquiry that is not part of the normal bottom-up join search
    1285             :  * sequence.
    1286             :  */
    1287             : bool
    1288      667872 : innerrel_is_unique(PlannerInfo *root,
    1289             :                    Relids joinrelids,
    1290             :                    Relids outerrelids,
    1291             :                    RelOptInfo *innerrel,
    1292             :                    JoinType jointype,
    1293             :                    List *restrictlist,
    1294             :                    bool force_cache)
    1295             : {
    1296      667872 :     return innerrel_is_unique_ext(root, joinrelids, outerrelids, innerrel,
    1297             :                                   jointype, restrictlist, force_cache, NULL);
    1298             : }
    1299             : 
    1300             : /*
    1301             :  * innerrel_is_unique_ext
    1302             :  *    Do the same as innerrel_is_unique(), but also set to (*extra_clauses)
    1303             :  *    additional clauses from a baserestrictinfo list used to prove the
    1304             :  *    uniqueness.
    1305             :  *
    1306             :  * A non-NULL extra_clauses indicates that we're checking for self-join and
    1307             :  * correspondingly dealing with filtered clauses.
    1308             :  */
    1309             : bool
    1310      669848 : innerrel_is_unique_ext(PlannerInfo *root,
    1311             :                        Relids joinrelids,
    1312             :                        Relids outerrelids,
    1313             :                        RelOptInfo *innerrel,
    1314             :                        JoinType jointype,
    1315             :                        List *restrictlist,
    1316             :                        bool force_cache,
    1317             :                        List **extra_clauses)
    1318             : {
    1319             :     MemoryContext old_context;
    1320             :     ListCell   *lc;
    1321             :     UniqueRelInfo *uniqueRelInfo;
    1322      669848 :     List       *outer_exprs = NIL;
    1323      669848 :     bool        self_join = (extra_clauses != NULL);
    1324             : 
    1325             :     /* Certainly can't prove uniqueness when there are no joinclauses */
    1326      669848 :     if (restrictlist == NIL)
    1327      102622 :         return false;
    1328             : 
    1329             :     /*
    1330             :      * Make a quick check to eliminate cases in which we will surely be unable
    1331             :      * to prove uniqueness of the innerrel.
    1332             :      */
    1333      567226 :     if (!rel_supports_distinctness(root, innerrel))
    1334      280038 :         return false;
    1335             : 
    1336             :     /*
    1337             :      * Query the cache to see if we've managed to prove that innerrel is
    1338             :      * unique for any subset of this outerrel.  For non-self-join search, we
    1339             :      * don't need an exact match, as extra outerrels can't make the innerrel
    1340             :      * any less unique (or more formally, the restrictlist for a join to a
    1341             :      * superset outerrel must be a superset of the conditions we successfully
    1342             :      * used before). For self-join search, we require an exact match of
    1343             :      * outerrels because we need extra clauses to be valid for our case. Also,
    1344             :      * for self-join checking we've filtered the clauses list.  Thus, we can
    1345             :      * match only the result cached for a self-join search for another
    1346             :      * self-join check.
    1347             :      */
    1348      317602 :     foreach(lc, innerrel->unique_for_rels)
    1349             :     {
    1350      119152 :         uniqueRelInfo = (UniqueRelInfo *) lfirst(lc);
    1351             : 
    1352      119152 :         if ((!self_join && bms_is_subset(uniqueRelInfo->outerrelids, outerrelids)) ||
    1353          68 :             (self_join && bms_equal(uniqueRelInfo->outerrelids, outerrelids) &&
    1354          56 :              uniqueRelInfo->self_join))
    1355             :         {
    1356       88738 :             if (extra_clauses)
    1357          12 :                 *extra_clauses = uniqueRelInfo->extra_clauses;
    1358       88738 :             return true;        /* Success! */
    1359             :         }
    1360             :     }
    1361             : 
    1362             :     /*
    1363             :      * Conversely, we may have already determined that this outerrel, or some
    1364             :      * superset thereof, cannot prove this innerrel to be unique.
    1365             :      */
    1366      198934 :     foreach(lc, innerrel->non_unique_for_rels)
    1367             :     {
    1368         808 :         Relids      unique_for_rels = (Relids) lfirst(lc);
    1369             : 
    1370         808 :         if (bms_is_subset(outerrelids, unique_for_rels))
    1371         324 :             return false;
    1372             :     }
    1373             : 
    1374             :     /* No cached information, so try to make the proof. */
    1375      198126 :     if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
    1376             :                                jointype, restrictlist,
    1377             :                                self_join ? &outer_exprs : NULL))
    1378             :     {
    1379             :         /*
    1380             :          * Cache the positive result for future probes, being sure to keep it
    1381             :          * in the planner_cxt even if we are working in GEQO.
    1382             :          *
    1383             :          * Note: one might consider trying to isolate the minimal subset of
    1384             :          * the outerrels that proved the innerrel unique.  But it's not worth
    1385             :          * the trouble, because the planner builds up joinrels incrementally
    1386             :          * and so we'll see the minimally sufficient outerrels before any
    1387             :          * supersets of them anyway.
    1388             :          */
    1389      106416 :         old_context = MemoryContextSwitchTo(root->planner_cxt);
    1390      106416 :         uniqueRelInfo = makeNode(UniqueRelInfo);
    1391      106416 :         uniqueRelInfo->outerrelids = bms_copy(outerrelids);
    1392      106416 :         uniqueRelInfo->self_join = self_join;
    1393      106416 :         uniqueRelInfo->extra_clauses = outer_exprs;
    1394      106416 :         innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
    1395             :                                             uniqueRelInfo);
    1396      106416 :         MemoryContextSwitchTo(old_context);
    1397             : 
    1398      106416 :         if (extra_clauses)
    1399         642 :             *extra_clauses = outer_exprs;
    1400      106416 :         return true;            /* Success! */
    1401             :     }
    1402             :     else
    1403             :     {
    1404             :         /*
    1405             :          * None of the join conditions for outerrel proved innerrel unique, so
    1406             :          * we can safely reject this outerrel or any subset of it in future
    1407             :          * checks.
    1408             :          *
    1409             :          * However, in normal planning mode, caching this knowledge is totally
    1410             :          * pointless; it won't be queried again, because we build up joinrels
    1411             :          * from smaller to larger.  It is useful in GEQO mode, where the
    1412             :          * knowledge can be carried across successive planning attempts; and
    1413             :          * it's likely to be useful when using join-search plugins, too. Hence
    1414             :          * cache when join_search_private is non-NULL.  (Yeah, that's a hack,
    1415             :          * but it seems reasonable.)
    1416             :          *
    1417             :          * Also, allow callers to override that heuristic and force caching;
    1418             :          * that's useful for reduce_unique_semijoins, which calls here before
    1419             :          * the normal join search starts.
    1420             :          */
    1421       91710 :         if (force_cache || root->join_search_private)
    1422             :         {
    1423        3718 :             old_context = MemoryContextSwitchTo(root->planner_cxt);
    1424        3718 :             innerrel->non_unique_for_rels =
    1425        3718 :                 lappend(innerrel->non_unique_for_rels,
    1426        3718 :                         bms_copy(outerrelids));
    1427        3718 :             MemoryContextSwitchTo(old_context);
    1428             :         }
    1429             : 
    1430       91710 :         return false;
    1431             :     }
    1432             : }
    1433             : 
    1434             : /*
    1435             :  * is_innerrel_unique_for
    1436             :  *    Check if the innerrel provably contains at most one tuple matching any
    1437             :  *    tuple from the outerrel, based on join clauses in the 'restrictlist'.
    1438             :  */
    1439             : static bool
    1440      198126 : is_innerrel_unique_for(PlannerInfo *root,
    1441             :                        Relids joinrelids,
    1442             :                        Relids outerrelids,
    1443             :                        RelOptInfo *innerrel,
    1444             :                        JoinType jointype,
    1445             :                        List *restrictlist,
    1446             :                        List **extra_clauses)
    1447             : {
    1448      198126 :     List       *clause_list = NIL;
    1449             :     ListCell   *lc;
    1450             : 
    1451             :     /*
    1452             :      * Search for mergejoinable clauses that constrain the inner rel against
    1453             :      * the outer rel.  If an operator is mergejoinable then it behaves like
    1454             :      * equality for some btree opclass, so it's what we want.  The
    1455             :      * mergejoinability test also eliminates clauses containing volatile
    1456             :      * functions, which we couldn't depend on.
    1457             :      */
    1458      436700 :     foreach(lc, restrictlist)
    1459             :     {
    1460      238574 :         RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
    1461             : 
    1462             :         /*
    1463             :          * As noted above, if it's a pushed-down clause and we're at an outer
    1464             :          * join, we can't use it.
    1465             :          */
    1466      238574 :         if (IS_OUTER_JOIN(jointype) &&
    1467      106470 :             RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
    1468        5030 :             continue;
    1469             : 
    1470             :         /* Ignore if it's not a mergejoinable clause */
    1471      233544 :         if (!restrictinfo->can_join ||
    1472      215750 :             restrictinfo->mergeopfamilies == NIL)
    1473       18720 :             continue;           /* not mergejoinable */
    1474             : 
    1475             :         /*
    1476             :          * Check if the clause has the form "outer op inner" or "inner op
    1477             :          * outer", and if so mark which side is inner.
    1478             :          */
    1479      214824 :         if (!clause_sides_match_join(restrictinfo, outerrelids,
    1480             :                                      innerrel->relids))
    1481          40 :             continue;           /* no good for these input relations */
    1482             : 
    1483             :         /* OK, add to the list */
    1484      214784 :         clause_list = lappend(clause_list, restrictinfo);
    1485             :     }
    1486             : 
    1487             :     /* Let rel_is_distinct_for() do the hard work */
    1488      198126 :     return rel_is_distinct_for(root, innerrel, clause_list, extra_clauses);
    1489             : }
    1490             : 
    1491             : /*
    1492             :  * Update EC members to point to the remaining relation instead of the removed
    1493             :  * one, removing duplicates.
    1494             :  *
    1495             :  * Restriction clauses for base relations are already distributed to
    1496             :  * the respective baserestrictinfo lists (see
    1497             :  * generate_implied_equalities_for_column). The above code has already processed
    1498             :  * this list and updated these clauses to reference the remaining
    1499             :  * relation, so that we can skip them here based on their relids.
    1500             :  *
    1501             :  * Likewise, we have already processed the join clauses that join the
    1502             :  * removed relation to the remaining one.
    1503             :  *
    1504             :  * Finally, there might be join clauses tying the removed relation to
    1505             :  * some third relation.  We can't just delete the source clauses and
    1506             :  * regenerate them from the EC because the corresponding equality
    1507             :  * operators might be missing (see the handling of ec_broken).
    1508             :  * Therefore, we will update the references in the source clauses.
    1509             :  *
    1510             :  * Derived clauses can be generated again, so it is simpler just to
    1511             :  * delete them.
    1512             :  */
    1513             : static void
    1514         900 : update_eclasses(EquivalenceClass *ec, int from, int to)
    1515             : {
    1516         900 :     List       *new_members = NIL;
    1517         900 :     List       *new_sources = NIL;
    1518             : 
    1519             :     /*
    1520             :      * We don't expect any EC child members to exist at this point.  Ensure
    1521             :      * that's the case, otherwise, we might be getting asked to do something
    1522             :      * this function hasn't been coded for.
    1523             :      */
    1524             :     Assert(ec->ec_childmembers == NULL);
    1525             : 
    1526        3636 :     foreach_node(EquivalenceMember, em, ec->ec_members)
    1527             :     {
    1528        1836 :         bool        is_redundant = false;
    1529             : 
    1530        1836 :         if (!bms_is_member(from, em->em_relids))
    1531             :         {
    1532         918 :             new_members = lappend(new_members, em);
    1533         918 :             continue;
    1534             :         }
    1535             : 
    1536         918 :         em->em_relids = adjust_relid_set(em->em_relids, from, to);
    1537         918 :         em->em_jdomain->jd_relids = adjust_relid_set(em->em_jdomain->jd_relids, from, to);
    1538             : 
    1539             :         /* We only process inner joins */
    1540         918 :         ChangeVarNodes((Node *) em->em_expr, from, to, 0);
    1541             : 
    1542        1860 :         foreach_node(EquivalenceMember, other, new_members)
    1543             :         {
    1544         298 :             if (!equal(em->em_relids, other->em_relids))
    1545          24 :                 continue;
    1546             : 
    1547         274 :             if (equal(em->em_expr, other->em_expr))
    1548             :             {
    1549         274 :                 is_redundant = true;
    1550         274 :                 break;
    1551             :             }
    1552             :         }
    1553             : 
    1554         918 :         if (!is_redundant)
    1555         644 :             new_members = lappend(new_members, em);
    1556             :     }
    1557             : 
    1558         900 :     list_free(ec->ec_members);
    1559         900 :     ec->ec_members = new_members;
    1560             : 
    1561         900 :     ec_clear_derived_clauses(ec);
    1562             : 
    1563             :     /* Update EC source expressions */
    1564        2736 :     foreach_node(RestrictInfo, rinfo, ec->ec_sources)
    1565             :     {
    1566         936 :         bool        is_redundant = false;
    1567             : 
    1568         936 :         if (!bms_is_member(from, rinfo->required_relids))
    1569             :         {
    1570         118 :             new_sources = lappend(new_sources, rinfo);
    1571         118 :             continue;
    1572             :         }
    1573             : 
    1574         818 :         ChangeVarNodes((Node *) rinfo, from, to, 0);
    1575             : 
    1576             :         /*
    1577             :          * After switching the clause to the remaining relation, check it for
    1578             :          * redundancy with existing ones. We don't have to check for
    1579             :          * redundancy with derived clauses, because we've just deleted them.
    1580             :          */
    1581        1660 :         foreach_node(RestrictInfo, other, new_sources)
    1582             :         {
    1583          36 :             if (!equal(rinfo->clause_relids, other->clause_relids))
    1584          24 :                 continue;
    1585             : 
    1586          12 :             if (equal(rinfo->clause, other->clause))
    1587             :             {
    1588          12 :                 is_redundant = true;
    1589          12 :                 break;
    1590             :             }
    1591             :         }
    1592             : 
    1593         818 :         if (!is_redundant)
    1594         806 :             new_sources = lappend(new_sources, rinfo);
    1595             :     }
    1596             : 
    1597         900 :     list_free(ec->ec_sources);
    1598         900 :     ec->ec_sources = new_sources;
    1599         900 :     ec->ec_relids = adjust_relid_set(ec->ec_relids, from, to);
    1600         900 : }
    1601             : 
    1602             : /*
    1603             :  * "Logically" compares two RestrictInfo's ignoring the 'rinfo_serial' field,
    1604             :  * which makes almost every RestrictInfo unique.  This type of comparison is
    1605             :  * useful when removing duplicates while moving RestrictInfo's from removed
    1606             :  * relation to remaining relation during self-join elimination.
    1607             :  *
    1608             :  * XXX: In the future, we might remove the 'rinfo_serial' field completely and
    1609             :  * get rid of this function.
    1610             :  */
    1611             : static bool
    1612         506 : restrict_infos_logically_equal(RestrictInfo *a, RestrictInfo *b)
    1613             : {
    1614         506 :     int         saved_rinfo_serial = a->rinfo_serial;
    1615             :     bool        result;
    1616             : 
    1617         506 :     a->rinfo_serial = b->rinfo_serial;
    1618         506 :     result = equal(a, b);
    1619         506 :     a->rinfo_serial = saved_rinfo_serial;
    1620             : 
    1621         506 :     return result;
    1622             : }
    1623             : 
    1624             : /*
    1625             :  * This function adds all non-redundant clauses to the keeping relation
    1626             :  * during self-join elimination.  That is a contradictory operation. On the
    1627             :  * one hand, we reduce the length of the `restrict` lists, which can
    1628             :  * impact planning or executing time.  Additionally, we improve the
    1629             :  * accuracy of cardinality estimation.  On the other hand, it is one more
    1630             :  * place that can make planning time much longer in specific cases.  It
    1631             :  * would have been better to avoid calling the equal() function here, but
    1632             :  * it's the only way to detect duplicated inequality expressions.
    1633             :  *
    1634             :  * (*keep_rinfo_list) is given by pointer because it might be altered by
    1635             :  * distribute_restrictinfo_to_rels().
    1636             :  */
    1637             : static void
    1638        1176 : add_non_redundant_clauses(PlannerInfo *root,
    1639             :                           List *rinfo_candidates,
    1640             :                           List **keep_rinfo_list,
    1641             :                           Index removed_relid)
    1642             : {
    1643        3250 :     foreach_node(RestrictInfo, rinfo, rinfo_candidates)
    1644             :     {
    1645         898 :         bool        is_redundant = false;
    1646             : 
    1647             :         Assert(!bms_is_member(removed_relid, rinfo->required_relids));
    1648             : 
    1649        2160 :         foreach_node(RestrictInfo, src, (*keep_rinfo_list))
    1650             :         {
    1651         518 :             if (!bms_equal(src->clause_relids, rinfo->clause_relids))
    1652             :                 /* Can't compare trivially different clauses */
    1653           6 :                 continue;
    1654             : 
    1655         512 :             if (src == rinfo ||
    1656         512 :                 (rinfo->parent_ec != NULL &&
    1657         804 :                  src->parent_ec == rinfo->parent_ec) ||
    1658         506 :                 restrict_infos_logically_equal(rinfo, src))
    1659             :             {
    1660         154 :                 is_redundant = true;
    1661         154 :                 break;
    1662             :             }
    1663             :         }
    1664         898 :         if (!is_redundant)
    1665         744 :             distribute_restrictinfo_to_rels(root, rinfo);
    1666             :     }
    1667        1176 : }
    1668             : 
    1669             : /*
    1670             :  * Remove a relation after we have proven that it participates only in an
    1671             :  * unneeded unique self-join.
    1672             :  *
    1673             :  * Replace any links in planner info structures.
    1674             :  *
    1675             :  * Transfer join and restriction clauses from the removed relation to the
    1676             :  * remaining one. We change the Vars of the clause to point to the
    1677             :  * remaining relation instead of the removed one. The clauses that require
    1678             :  * a subset of joinrelids become restriction clauses of the remaining
    1679             :  * relation, and others remain join clauses. We append them to
    1680             :  * baserestrictinfo and joininfo, respectively, trying not to introduce
    1681             :  * duplicates.
    1682             :  *
    1683             :  * We also have to process the 'joinclauses' list here, because it
    1684             :  * contains EC-derived join clauses which must become filter clauses. It
    1685             :  * is not enough to just correct the ECs because the EC-derived
    1686             :  * restrictions are generated before join removal (see
    1687             :  * generate_base_implied_equalities).
    1688             :  *
    1689             :  * NOTE: Remember to keep the code in sync with PlannerInfo to be sure all
    1690             :  * cached relids and relid bitmapsets can be correctly cleaned during the
    1691             :  * self-join elimination procedure.
    1692             :  */
    1693             : static void
    1694         588 : remove_self_join_rel(PlannerInfo *root, PlanRowMark *kmark, PlanRowMark *rmark,
    1695             :                      RelOptInfo *toKeep, RelOptInfo *toRemove,
    1696             :                      List *restrictlist)
    1697             : {
    1698             :     List       *joininfos;
    1699             :     ListCell   *lc;
    1700             :     int         i;
    1701         588 :     List       *jinfo_candidates = NIL;
    1702         588 :     List       *binfo_candidates = NIL;
    1703             : 
    1704             :     Assert(toKeep->relid > 0);
    1705             :     Assert(toRemove->relid > 0);
    1706             : 
    1707             :     /*
    1708             :      * Replace the index of the removing table with the keeping one. The
    1709             :      * technique of removing/distributing restrictinfo is used here to attach
    1710             :      * just appeared (for keeping relation) join clauses and avoid adding
    1711             :      * duplicates of those that already exist in the joininfo list.
    1712             :      */
    1713         588 :     joininfos = list_copy(toRemove->joininfo);
    1714        1254 :     foreach_node(RestrictInfo, rinfo, joininfos)
    1715             :     {
    1716          78 :         remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
    1717          78 :         ChangeVarNodes((Node *) rinfo, toRemove->relid, toKeep->relid, 0);
    1718             : 
    1719          78 :         if (bms_membership(rinfo->required_relids) == BMS_MULTIPLE)
    1720          60 :             jinfo_candidates = lappend(jinfo_candidates, rinfo);
    1721             :         else
    1722          18 :             binfo_candidates = lappend(binfo_candidates, rinfo);
    1723             :     }
    1724             : 
    1725             :     /*
    1726             :      * Concatenate restrictlist to the list of base restrictions of the
    1727             :      * removing table just to simplify the replacement procedure: all of them
    1728             :      * weren't connected to any keeping relations and need to be added to some
    1729             :      * rels.
    1730             :      */
    1731         588 :     toRemove->baserestrictinfo = list_concat(toRemove->baserestrictinfo,
    1732             :                                              restrictlist);
    1733        1996 :     foreach_node(RestrictInfo, rinfo, toRemove->baserestrictinfo)
    1734             :     {
    1735         820 :         ChangeVarNodes((Node *) rinfo, toRemove->relid, toKeep->relid, 0);
    1736             : 
    1737         820 :         if (bms_membership(rinfo->required_relids) == BMS_MULTIPLE)
    1738           0 :             jinfo_candidates = lappend(jinfo_candidates, rinfo);
    1739             :         else
    1740         820 :             binfo_candidates = lappend(binfo_candidates, rinfo);
    1741             :     }
    1742             : 
    1743             :     /*
    1744             :      * Now, add all non-redundant clauses to the keeping relation.
    1745             :      */
    1746         588 :     add_non_redundant_clauses(root, binfo_candidates,
    1747             :                               &toKeep->baserestrictinfo, toRemove->relid);
    1748         588 :     add_non_redundant_clauses(root, jinfo_candidates,
    1749             :                               &toKeep->joininfo, toRemove->relid);
    1750             : 
    1751         588 :     list_free(binfo_candidates);
    1752         588 :     list_free(jinfo_candidates);
    1753             : 
    1754             :     /*
    1755             :      * Arrange equivalence classes, mentioned removing a table, with the
    1756             :      * keeping one: varno of removing table should be replaced in members and
    1757             :      * sources lists. Also, remove duplicated elements if this replacement
    1758             :      * procedure created them.
    1759             :      */
    1760         588 :     i = -1;
    1761        1488 :     while ((i = bms_next_member(toRemove->eclass_indexes, i)) >= 0)
    1762             :     {
    1763         900 :         EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
    1764             : 
    1765         900 :         update_eclasses(ec, toRemove->relid, toKeep->relid);
    1766         900 :         toKeep->eclass_indexes = bms_add_member(toKeep->eclass_indexes, i);
    1767             :     }
    1768             : 
    1769             :     /*
    1770             :      * Transfer the targetlist and attr_needed flags.
    1771             :      */
    1772             : 
    1773        2360 :     foreach(lc, toRemove->reltarget->exprs)
    1774             :     {
    1775        1772 :         Node       *node = lfirst(lc);
    1776             : 
    1777        1772 :         ChangeVarNodes(node, toRemove->relid, toKeep->relid, 0);
    1778        1772 :         if (!list_member(toKeep->reltarget->exprs, node))
    1779         174 :             toKeep->reltarget->exprs = lappend(toKeep->reltarget->exprs, node);
    1780             :     }
    1781             : 
    1782        7470 :     for (i = toKeep->min_attr; i <= toKeep->max_attr; i++)
    1783             :     {
    1784        6882 :         int         attno = i - toKeep->min_attr;
    1785             : 
    1786       13764 :         toRemove->attr_needed[attno] = adjust_relid_set(toRemove->attr_needed[attno],
    1787        6882 :                                                         toRemove->relid, toKeep->relid);
    1788        6882 :         toKeep->attr_needed[attno] = bms_add_members(toKeep->attr_needed[attno],
    1789        6882 :                                                      toRemove->attr_needed[attno]);
    1790             :     }
    1791             : 
    1792             :     /*
    1793             :      * If the removed relation has a row mark, transfer it to the remaining
    1794             :      * one.
    1795             :      *
    1796             :      * If both rels have row marks, just keep the one corresponding to the
    1797             :      * remaining relation because we verified earlier that they have the same
    1798             :      * strength.
    1799             :      */
    1800         588 :     if (rmark)
    1801             :     {
    1802          74 :         if (kmark)
    1803             :         {
    1804             :             Assert(kmark->markType == rmark->markType);
    1805             : 
    1806          74 :             root->rowMarks = list_delete_ptr(root->rowMarks, rmark);
    1807             :         }
    1808             :         else
    1809             :         {
    1810             :             /* Shouldn't have inheritance children here. */
    1811             :             Assert(rmark->rti == rmark->prti);
    1812             : 
    1813           0 :             rmark->rti = rmark->prti = toKeep->relid;
    1814             :         }
    1815             :     }
    1816             : 
    1817             :     /*
    1818             :      * Replace varno in all the query structures, except nodes RangeTblRef
    1819             :      * otherwise later remove_rel_from_joinlist will yield errors.
    1820             :      */
    1821         588 :     ChangeVarNodesExtended((Node *) root->parse, toRemove->relid, toKeep->relid, 0, false);
    1822             : 
    1823             :     /* Replace links in the planner info */
    1824         588 :     remove_rel_from_query(root, toRemove, toKeep->relid, NULL, NULL);
    1825             : 
    1826             :     /* At last, replace varno in root targetlist and HAVING clause */
    1827         588 :     ChangeVarNodes((Node *) root->processed_tlist, toRemove->relid, toKeep->relid, 0);
    1828         588 :     ChangeVarNodes((Node *) root->processed_groupClause, toRemove->relid, toKeep->relid, 0);
    1829             : 
    1830         588 :     adjust_relid_set(root->all_result_relids, toRemove->relid, toKeep->relid);
    1831         588 :     adjust_relid_set(root->leaf_result_relids, toRemove->relid, toKeep->relid);
    1832             : 
    1833             :     /*
    1834             :      * There may be references to the rel in root->fkey_list, but if so,
    1835             :      * match_foreign_keys_to_quals() will get rid of them.
    1836             :      */
    1837             : 
    1838             :     /*
    1839             :      * Finally, remove the rel from the baserel array to prevent it from being
    1840             :      * referenced again.  (We can't do this earlier because
    1841             :      * remove_join_clause_from_rels will touch it.)
    1842             :      */
    1843         588 :     root->simple_rel_array[toRemove->relid] = NULL;
    1844             : 
    1845             :     /* And nuke the RelOptInfo, just in case there's another access path. */
    1846         588 :     pfree(toRemove);
    1847             : 
    1848             :     /*
    1849             :      * Now repeat construction of attr_needed bits coming from all other
    1850             :      * sources.
    1851             :      */
    1852         588 :     rebuild_placeholder_attr_needed(root);
    1853         588 :     rebuild_joinclause_attr_needed(root);
    1854         588 :     rebuild_eclass_attr_needed(root);
    1855         588 :     rebuild_lateral_attr_needed(root);
    1856         588 : }
    1857             : 
    1858             : /*
    1859             :  * split_selfjoin_quals
    1860             :  *      Processes 'joinquals' by building two lists: one containing the quals
    1861             :  *      where the columns/exprs are on either side of the join match and
    1862             :  *      another one containing the remaining quals.
    1863             :  *
    1864             :  * 'joinquals' must only contain quals for a RTE_RELATION being joined to
    1865             :  * itself.
    1866             :  */
    1867             : static void
    1868        1976 : split_selfjoin_quals(PlannerInfo *root, List *joinquals, List **selfjoinquals,
    1869             :                      List **otherjoinquals, int from, int to)
    1870             : {
    1871        1976 :     List       *sjoinquals = NIL;
    1872        1976 :     List       *ojoinquals = NIL;
    1873             : 
    1874        6062 :     foreach_node(RestrictInfo, rinfo, joinquals)
    1875             :     {
    1876             :         OpExpr     *expr;
    1877             :         Node       *leftexpr;
    1878             :         Node       *rightexpr;
    1879             : 
    1880             :         /* In general, clause looks like F(arg1) = G(arg2) */
    1881        4220 :         if (!rinfo->mergeopfamilies ||
    1882        4220 :             bms_num_members(rinfo->clause_relids) != 2 ||
    1883        4220 :             bms_membership(rinfo->left_relids) != BMS_SINGLETON ||
    1884        2110 :             bms_membership(rinfo->right_relids) != BMS_SINGLETON)
    1885             :         {
    1886           0 :             ojoinquals = lappend(ojoinquals, rinfo);
    1887           0 :             continue;
    1888             :         }
    1889             : 
    1890        2110 :         expr = (OpExpr *) rinfo->clause;
    1891             : 
    1892        2110 :         if (!IsA(expr, OpExpr) || list_length(expr->args) != 2)
    1893             :         {
    1894           0 :             ojoinquals = lappend(ojoinquals, rinfo);
    1895           0 :             continue;
    1896             :         }
    1897             : 
    1898        2110 :         leftexpr = get_leftop(rinfo->clause);
    1899        2110 :         rightexpr = copyObject(get_rightop(rinfo->clause));
    1900             : 
    1901        2110 :         if (leftexpr && IsA(leftexpr, RelabelType))
    1902          12 :             leftexpr = (Node *) ((RelabelType *) leftexpr)->arg;
    1903        2110 :         if (rightexpr && IsA(rightexpr, RelabelType))
    1904           6 :             rightexpr = (Node *) ((RelabelType *) rightexpr)->arg;
    1905             : 
    1906             :         /*
    1907             :          * Quite an expensive operation, narrowing the use case. For example,
    1908             :          * when we have cast of the same var to different (but compatible)
    1909             :          * types.
    1910             :          */
    1911        2110 :         ChangeVarNodes(rightexpr, bms_singleton_member(rinfo->right_relids),
    1912        2110 :                        bms_singleton_member(rinfo->left_relids), 0);
    1913             : 
    1914        2110 :         if (equal(leftexpr, rightexpr))
    1915        1624 :             sjoinquals = lappend(sjoinquals, rinfo);
    1916             :         else
    1917         486 :             ojoinquals = lappend(ojoinquals, rinfo);
    1918             :     }
    1919             : 
    1920        1976 :     *selfjoinquals = sjoinquals;
    1921        1976 :     *otherjoinquals = ojoinquals;
    1922        1976 : }
    1923             : 
    1924             : /*
    1925             :  * Check for a case when uniqueness is at least partly derived from a
    1926             :  * baserestrictinfo clause. In this case, we have a chance to return only
    1927             :  * one row (if such clauses on both sides of SJ are equal) or nothing (if they
    1928             :  * are different).
    1929             :  */
    1930             : static bool
    1931         654 : match_unique_clauses(PlannerInfo *root, RelOptInfo *outer, List *uclauses,
    1932             :                      Index relid)
    1933             : {
    1934        1326 :     foreach_node(RestrictInfo, rinfo, uclauses)
    1935             :     {
    1936             :         Expr       *clause;
    1937             :         Node       *iclause;
    1938             :         Node       *c1;
    1939         150 :         bool        matched = false;
    1940             : 
    1941             :         Assert(outer->relid > 0 && relid > 0);
    1942             : 
    1943             :         /* Only filters like f(R.x1,...,R.xN) == expr we should consider. */
    1944             :         Assert(bms_is_empty(rinfo->left_relids) ^
    1945             :                bms_is_empty(rinfo->right_relids));
    1946             : 
    1947         150 :         clause = (Expr *) copyObject(rinfo->clause);
    1948         150 :         ChangeVarNodes((Node *) clause, relid, outer->relid, 0);
    1949             : 
    1950         150 :         iclause = bms_is_empty(rinfo->left_relids) ? get_rightop(clause) :
    1951         144 :             get_leftop(clause);
    1952         150 :         c1 = bms_is_empty(rinfo->left_relids) ? get_leftop(clause) :
    1953         144 :             get_rightop(clause);
    1954             : 
    1955             :         /*
    1956             :          * Compare these left and right sides with the corresponding sides of
    1957             :          * the outer's filters. If no one is detected - return immediately.
    1958             :          */
    1959         408 :         foreach_node(RestrictInfo, orinfo, outer->baserestrictinfo)
    1960             :         {
    1961             :             Node       *oclause;
    1962             :             Node       *c2;
    1963             : 
    1964         192 :             if (orinfo->mergeopfamilies == NIL)
    1965             :                 /* Don't consider clauses that aren't similar to 'F(X)=G(Y)' */
    1966          60 :                 continue;
    1967             : 
    1968             :             Assert(is_opclause(orinfo->clause));
    1969             : 
    1970         264 :             oclause = bms_is_empty(orinfo->left_relids) ?
    1971         132 :                 get_rightop(orinfo->clause) : get_leftop(orinfo->clause);
    1972         264 :             c2 = (bms_is_empty(orinfo->left_relids) ?
    1973         132 :                   get_leftop(orinfo->clause) : get_rightop(orinfo->clause));
    1974             : 
    1975         132 :             if (equal(iclause, oclause) && equal(c1, c2))
    1976             :             {
    1977          84 :                 matched = true;
    1978          84 :                 break;
    1979             :             }
    1980             :         }
    1981             : 
    1982         150 :         if (!matched)
    1983          66 :             return false;
    1984             :     }
    1985             : 
    1986         588 :     return true;
    1987             : }
    1988             : 
    1989             : /*
    1990             :  * Find and remove unique self-joins in a group of base relations that have
    1991             :  * the same Oid.
    1992             :  *
    1993             :  * Returns a set of relids that were removed.
    1994             :  */
    1995             : static Relids
    1996       11430 : remove_self_joins_one_group(PlannerInfo *root, Relids relids)
    1997             : {
    1998       11430 :     Relids      result = NULL;
    1999             :     int         k;              /* Index of kept relation */
    2000       11430 :     int         r = -1;         /* Index of removed relation */
    2001             : 
    2002       35466 :     while ((r = bms_next_member(relids, r)) > 0)
    2003             :     {
    2004       24036 :         RelOptInfo *inner = root->simple_rel_array[r];
    2005             : 
    2006       24036 :         k = r;
    2007             : 
    2008       37442 :         while ((k = bms_next_member(relids, k)) > 0)
    2009             :         {
    2010       13994 :             Relids      joinrelids = NULL;
    2011       13994 :             RelOptInfo *outer = root->simple_rel_array[k];
    2012             :             List       *restrictlist;
    2013             :             List       *selfjoinquals;
    2014             :             List       *otherjoinquals;
    2015             :             ListCell   *lc;
    2016       13994 :             bool        jinfo_check = true;
    2017       13994 :             PlanRowMark *omark = NULL;
    2018       13994 :             PlanRowMark *imark = NULL;
    2019       13994 :             List       *uclauses = NIL;
    2020             : 
    2021             :             /* A sanity check: the relations have the same Oid. */
    2022             :             Assert(root->simple_rte_array[k]->relid ==
    2023             :                    root->simple_rte_array[r]->relid);
    2024             : 
    2025             :             /*
    2026             :              * It is impossible to eliminate the join of two relations if they
    2027             :              * belong to different rules of order. Otherwise, the planner
    2028             :              * can't find any variants of the correct query plan.
    2029             :              */
    2030       17388 :             foreach(lc, root->join_info_list)
    2031             :             {
    2032       11096 :                 SpecialJoinInfo *info = (SpecialJoinInfo *) lfirst(lc);
    2033             : 
    2034       22192 :                 if ((bms_is_member(k, info->syn_lefthand) ^
    2035       15806 :                      bms_is_member(r, info->syn_lefthand)) ||
    2036        4710 :                     (bms_is_member(k, info->syn_righthand) ^
    2037        4710 :                      bms_is_member(r, info->syn_righthand)))
    2038             :                 {
    2039        7702 :                     jinfo_check = false;
    2040        7702 :                     break;
    2041             :                 }
    2042             :             }
    2043       13994 :             if (!jinfo_check)
    2044       13406 :                 continue;
    2045             : 
    2046             :             /*
    2047             :              * Check Row Marks equivalence. We can't remove the join if the
    2048             :              * relations have row marks of different strength (e.g., one is
    2049             :              * locked FOR UPDATE, and another just has ROW_MARK_REFERENCE for
    2050             :              * EvalPlanQual rechecking).
    2051             :              */
    2052        6500 :             foreach(lc, root->rowMarks)
    2053             :             {
    2054         380 :                 PlanRowMark *rowMark = (PlanRowMark *) lfirst(lc);
    2055             : 
    2056         380 :                 if (rowMark->rti == k)
    2057             :                 {
    2058             :                     Assert(imark == NULL);
    2059         172 :                     imark = rowMark;
    2060             :                 }
    2061         208 :                 else if (rowMark->rti == r)
    2062             :                 {
    2063             :                     Assert(omark == NULL);
    2064         172 :                     omark = rowMark;
    2065             :                 }
    2066             : 
    2067         380 :                 if (omark && imark)
    2068         172 :                     break;
    2069             :             }
    2070        6292 :             if (omark && imark && omark->markType != imark->markType)
    2071          52 :                 continue;
    2072             : 
    2073             :             /*
    2074             :              * We only deal with base rels here, so their relids bitset
    2075             :              * contains only one member -- their relid.
    2076             :              */
    2077        6240 :             joinrelids = bms_add_member(joinrelids, r);
    2078        6240 :             joinrelids = bms_add_member(joinrelids, k);
    2079             : 
    2080             :             /*
    2081             :              * PHVs should not impose any constraints on removing self-joins.
    2082             :              */
    2083             : 
    2084             :             /*
    2085             :              * At this stage, joininfo lists of inner and outer can contain
    2086             :              * only clauses required for a superior outer join that can't
    2087             :              * influence this optimization. So, we can avoid to call the
    2088             :              * build_joinrel_restrictlist() routine.
    2089             :              */
    2090        6240 :             restrictlist = generate_join_implied_equalities(root, joinrelids,
    2091             :                                                             inner->relids,
    2092             :                                                             outer, NULL);
    2093        6240 :             if (restrictlist == NIL)
    2094        4264 :                 continue;
    2095             : 
    2096             :             /*
    2097             :              * Process restrictlist to separate the self-join quals from the
    2098             :              * other quals. e.g., "x = x" goes to selfjoinquals and "a = b" to
    2099             :              * otherjoinquals.
    2100             :              */
    2101        1976 :             split_selfjoin_quals(root, restrictlist, &selfjoinquals,
    2102        1976 :                                  &otherjoinquals, inner->relid, outer->relid);
    2103             : 
    2104             :             Assert(list_length(restrictlist) ==
    2105             :                    (list_length(selfjoinquals) + list_length(otherjoinquals)));
    2106             : 
    2107             :             /*
    2108             :              * To enable SJE for the only degenerate case without any self
    2109             :              * join clauses at all, add baserestrictinfo to this list. The
    2110             :              * degenerate case works only if both sides have the same clause.
    2111             :              * So doesn't matter which side to add.
    2112             :              */
    2113        1976 :             selfjoinquals = list_concat(selfjoinquals, outer->baserestrictinfo);
    2114             : 
    2115             :             /*
    2116             :              * Determine if the inner table can duplicate outer rows.  We must
    2117             :              * bypass the unique rel cache here since we're possibly using a
    2118             :              * subset of join quals. We can use 'force_cache' == true when all
    2119             :              * join quals are self-join quals.  Otherwise, we could end up
    2120             :              * putting false negatives in the cache.
    2121             :              */
    2122        1976 :             if (!innerrel_is_unique_ext(root, joinrelids, inner->relids,
    2123             :                                         outer, JOIN_INNER, selfjoinquals,
    2124        1976 :                                         list_length(otherjoinquals) == 0,
    2125             :                                         &uclauses))
    2126        1322 :                 continue;
    2127             : 
    2128             :             /*
    2129             :              * 'uclauses' is the copy of outer->baserestrictinfo that are
    2130             :              * associated with an index.  We proved by matching selfjoinquals
    2131             :              * to a unique index that the outer relation has at most one
    2132             :              * matching row for each inner row.  Sometimes that is not enough.
    2133             :              * e.g. "WHERE s1.b = s2.b AND s1.a = 1 AND s2.a = 2" when the
    2134             :              * unique index is (a,b).  Having non-empty uclauses, we must
    2135             :              * validate that the inner baserestrictinfo contains the same
    2136             :              * expressions, or we won't match the same row on each side of the
    2137             :              * join.
    2138             :              */
    2139         654 :             if (!match_unique_clauses(root, inner, uclauses, outer->relid))
    2140          66 :                 continue;
    2141             : 
    2142             :             /*
    2143             :              * We can remove either relation, so remove the inner one in order
    2144             :              * to simplify this loop.
    2145             :              */
    2146         588 :             remove_self_join_rel(root, omark, imark, outer, inner, restrictlist);
    2147             : 
    2148         588 :             result = bms_add_member(result, r);
    2149             : 
    2150             :             /* We have removed the outer relation, try the next one. */
    2151         588 :             break;
    2152             :         }
    2153             :     }
    2154             : 
    2155       11430 :     return result;
    2156             : }
    2157             : 
    2158             : /*
    2159             :  * Gather indexes of base relations from the joinlist and try to eliminate self
    2160             :  * joins.
    2161             :  */
    2162             : static Relids
    2163      101154 : remove_self_joins_recurse(PlannerInfo *root, List *joinlist, Relids toRemove)
    2164             : {
    2165             :     ListCell   *jl;
    2166      101154 :     Relids      relids = NULL;
    2167      101154 :     SelfJoinCandidate *candidates = NULL;
    2168             :     int         i;
    2169             :     int         j;
    2170             :     int         numRels;
    2171             : 
    2172             :     /* Collect indexes of base relations of the join tree */
    2173      337084 :     foreach(jl, joinlist)
    2174             :     {
    2175      235930 :         Node       *jlnode = (Node *) lfirst(jl);
    2176             : 
    2177      235930 :         if (IsA(jlnode, RangeTblRef))
    2178             :         {
    2179      232564 :             int         varno = ((RangeTblRef *) jlnode)->rtindex;
    2180      232564 :             RangeTblEntry *rte = root->simple_rte_array[varno];
    2181             : 
    2182             :             /*
    2183             :              * We only consider ordinary relations as candidates to be
    2184             :              * removed, and these relations should not have TABLESAMPLE
    2185             :              * clauses specified.  Removing a relation with TABLESAMPLE clause
    2186             :              * could potentially change the syntax of the query. Because of
    2187             :              * UPDATE/DELETE EPQ mechanism, currently Query->resultRelation or
    2188             :              * Query->mergeTargetRelation associated rel cannot be eliminated.
    2189             :              */
    2190      232564 :             if (rte->rtekind == RTE_RELATION &&
    2191      201150 :                 rte->relkind == RELKIND_RELATION &&
    2192      195968 :                 rte->tablesample == NULL &&
    2193      195944 :                 varno != root->parse->resultRelation &&
    2194      194160 :                 varno != root->parse->mergeTargetRelation)
    2195             :             {
    2196             :                 Assert(!bms_is_member(varno, relids));
    2197      194160 :                 relids = bms_add_member(relids, varno);
    2198             :             }
    2199             :         }
    2200        3366 :         else if (IsA(jlnode, List))
    2201             :         {
    2202             :             /* Recursively go inside the sub-joinlist */
    2203        3366 :             toRemove = remove_self_joins_recurse(root, (List *) jlnode,
    2204             :                                                  toRemove);
    2205             :         }
    2206             :         else
    2207           0 :             elog(ERROR, "unrecognized joinlist node type: %d",
    2208             :                  (int) nodeTag(jlnode));
    2209             :     }
    2210             : 
    2211      101154 :     numRels = bms_num_members(relids);
    2212             : 
    2213             :     /* Need at least two relations for the join */
    2214      101154 :     if (numRels < 2)
    2215       30868 :         return toRemove;
    2216             : 
    2217             :     /*
    2218             :      * In order to find relations with the same oid we first build an array of
    2219             :      * candidates and then sort it by oid.
    2220             :      */
    2221       70286 :     candidates = (SelfJoinCandidate *) palloc(sizeof(SelfJoinCandidate) *
    2222             :                                               numRels);
    2223       70286 :     i = -1;
    2224       70286 :     j = 0;
    2225      242286 :     while ((i = bms_next_member(relids, i)) >= 0)
    2226             :     {
    2227      172000 :         candidates[j].relid = i;
    2228      172000 :         candidates[j].reloid = root->simple_rte_array[i]->relid;
    2229      172000 :         j++;
    2230             :     }
    2231             : 
    2232       70286 :     qsort(candidates, numRels, sizeof(SelfJoinCandidate),
    2233             :           self_join_candidates_cmp);
    2234             : 
    2235             :     /*
    2236             :      * Iteratively form a group of relation indexes with the same oid and
    2237             :      * launch the routine that detects self-joins in this group and removes
    2238             :      * excessive range table entries.
    2239             :      *
    2240             :      * At the end of the iteration, exclude the group from the overall relids
    2241             :      * list. So each next iteration of the cycle will involve less and less
    2242             :      * value of relids.
    2243             :      */
    2244       70286 :     i = 0;
    2245      242286 :     for (j = 1; j < numRels + 1; j++)
    2246             :     {
    2247      172000 :         if (j == numRels || candidates[j].reloid != candidates[i].reloid)
    2248             :         {
    2249      159466 :             if (j - i >= 2)
    2250             :             {
    2251             :                 /* Create a group of relation indexes with the same oid */
    2252       11364 :                 Relids      group = NULL;
    2253             :                 Relids      removed;
    2254             : 
    2255       35262 :                 while (i < j)
    2256             :                 {
    2257       23898 :                     group = bms_add_member(group, candidates[i].relid);
    2258       23898 :                     i++;
    2259             :                 }
    2260       11364 :                 relids = bms_del_members(relids, group);
    2261             : 
    2262             :                 /*
    2263             :                  * Try to remove self-joins from a group of identical entries.
    2264             :                  * Make the next attempt iteratively - if something is deleted
    2265             :                  * from a group, changes in clauses and equivalence classes
    2266             :                  * can give us a chance to find more candidates.
    2267             :                  */
    2268             :                 do
    2269             :                 {
    2270             :                     Assert(!bms_overlap(group, toRemove));
    2271       11430 :                     removed = remove_self_joins_one_group(root, group);
    2272       11430 :                     toRemove = bms_add_members(toRemove, removed);
    2273       11430 :                     group = bms_del_members(group, removed);
    2274         564 :                 } while (!bms_is_empty(removed) &&
    2275       11430 :                          bms_membership(group) == BMS_MULTIPLE);
    2276       11364 :                 bms_free(removed);
    2277       11364 :                 bms_free(group);
    2278             :             }
    2279             :             else
    2280             :             {
    2281             :                 /* Single relation, just remove it from the set */
    2282      148102 :                 relids = bms_del_member(relids, candidates[i].relid);
    2283      148102 :                 i = j;
    2284             :             }
    2285             :         }
    2286             :     }
    2287             : 
    2288             :     Assert(bms_is_empty(relids));
    2289             : 
    2290       70286 :     return toRemove;
    2291             : }
    2292             : 
    2293             : /*
    2294             :  * Compare self-join candidates by their oids.
    2295             :  */
    2296             : static int
    2297      127170 : self_join_candidates_cmp(const void *a, const void *b)
    2298             : {
    2299      127170 :     const SelfJoinCandidate *ca = (const SelfJoinCandidate *) a;
    2300      127170 :     const SelfJoinCandidate *cb = (const SelfJoinCandidate *) b;
    2301             : 
    2302      127170 :     if (ca->reloid != cb->reloid)
    2303      114582 :         return (ca->reloid < cb->reloid ? -1 : 1);
    2304             :     else
    2305       12588 :         return 0;
    2306             : }
    2307             : 
    2308             : /*
    2309             :  * Find and remove useless self joins.
    2310             :  *
    2311             :  * Search for joins where a relation is joined to itself. If the join clause
    2312             :  * for each tuple from one side of the join is proven to match the same
    2313             :  * physical row (or nothing) on the other side, that self-join can be
    2314             :  * eliminated from the query.  Suitable join clauses are assumed to be in the
    2315             :  * form of X = X, and can be replaced with NOT NULL clauses.
    2316             :  *
    2317             :  * For the sake of simplicity, we don't apply this optimization to special
    2318             :  * joins. Here is a list of what we could do in some particular cases:
    2319             :  * 'a a1 semi join a a2': is reduced to inner by reduce_unique_semijoins,
    2320             :  * and then removed normally.
    2321             :  * 'a a1 anti join a a2': could simplify to a scan with 'outer quals AND
    2322             :  * (IS NULL on join columns OR NOT inner quals)'.
    2323             :  * 'a a1 left join a a2': could simplify to a scan like inner but without
    2324             :  * NOT NULL conditions on join columns.
    2325             :  * 'a a1 left join (a a2 join b)': can't simplify this, because join to b
    2326             :  * can both remove rows and introduce duplicates.
    2327             :  *
    2328             :  * To search for removable joins, we order all the relations on their Oid,
    2329             :  * go over each set with the same Oid, and consider each pair of relations
    2330             :  * in this set.
    2331             :  *
    2332             :  * To remove the join, we mark one of the participating relations as dead
    2333             :  * and rewrite all references to it to point to the remaining relation.
    2334             :  * This includes modifying RestrictInfos, EquivalenceClasses, and
    2335             :  * EquivalenceMembers. We also have to modify the row marks. The join clauses
    2336             :  * of the removed relation become either restriction or join clauses, based on
    2337             :  * whether they reference any relations not participating in the removed join.
    2338             :  *
    2339             :  * 'joinlist' is the top-level joinlist of the query. If it has any
    2340             :  * references to the removed relations, we update them to point to the
    2341             :  * remaining ones.
    2342             :  */
    2343             : List *
    2344      328968 : remove_useless_self_joins(PlannerInfo *root, List *joinlist)
    2345             : {
    2346      328968 :     Relids      toRemove = NULL;
    2347      328968 :     int         relid = -1;
    2348             : 
    2349      657936 :     if (!enable_self_join_elimination || joinlist == NIL ||
    2350      561016 :         (list_length(joinlist) == 1 && !IsA(linitial(joinlist), List)))
    2351      231180 :         return joinlist;
    2352             : 
    2353             :     /*
    2354             :      * Merge pairs of relations participated in self-join. Remove unnecessary
    2355             :      * range table entries.
    2356             :      */
    2357       97788 :     toRemove = remove_self_joins_recurse(root, joinlist, toRemove);
    2358             : 
    2359       97788 :     if (unlikely(toRemove != NULL))
    2360             :     {
    2361             :         /* At the end, remove orphaned relation links */
    2362        1146 :         while ((relid = bms_next_member(toRemove, relid)) >= 0)
    2363             :         {
    2364         588 :             int         nremoved = 0;
    2365             : 
    2366         588 :             joinlist = remove_rel_from_joinlist(joinlist, relid, &nremoved);
    2367         588 :             if (nremoved != 1)
    2368           0 :                 elog(ERROR, "failed to find relation %d in joinlist", relid);
    2369             :         }
    2370             :     }
    2371             : 
    2372       97788 :     return joinlist;
    2373             : }

Generated by: LCOV version 1.14