LCOV - code coverage report
Current view: top level - src/backend/optimizer/plan - analyzejoins.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 649 673 96.4 %
Date: 2025-04-01 23:17:00 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      324872 : 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      324872 : restart:
      97      364070 :     foreach(lc, root->join_info_list)
      98             :     {
      99       49438 :         SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
     100             :         int         innerrelid;
     101             :         int         nremoved;
     102             : 
     103             :         /* Skip if not removable */
     104       49438 :         if (!join_is_removable(root, sjinfo))
     105       39198 :             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       10240 :         innerrelid = bms_singleton_member(sjinfo->min_righthand);
     113             : 
     114       10240 :         remove_leftjoinrel_from_query(root, innerrelid, sjinfo);
     115             : 
     116             :         /* We verify that exactly one reference gets removed from joinlist */
     117       10240 :         nremoved = 0;
     118       10240 :         joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
     119       10240 :         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       10240 :         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       10240 :         goto restart;
     136             :     }
     137             : 
     138      314632 :     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       49438 : join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
     154             : {
     155             :     int         innerrelid;
     156             :     RelOptInfo *innerrel;
     157             :     Relids      inputrelids;
     158             :     Relids      joinrelids;
     159       49438 :     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       49438 :     if (sjinfo->jointype != JOIN_LEFT)
     168        7068 :         return false;
     169             : 
     170       42370 :     if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
     171        1296 :         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       41074 :     if (innerrelid == root->parse->resultRelation)
     179         746 :         return false;
     180             : 
     181       40328 :     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       40328 :     if (!rel_supports_distinctness(root, innerrel))
     189        3010 :         return false;
     190             : 
     191             :     /* Compute the relid set for the join we are considering */
     192       37318 :     inputrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
     193             :     Assert(sjinfo->ojrelid != 0);
     194       37318 :     joinrelids = bms_copy(inputrelids);
     195       37318 :     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      337324 :     for (attroff = innerrel->max_attr - innerrel->min_attr;
     209             :          attroff >= 0;
     210      300006 :          attroff--)
     211             :     {
     212      326922 :         if (!bms_is_subset(innerrel->attr_needed[attroff], inputrelids))
     213       26916 :             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       10594 :     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       21066 :     foreach(l, innerrel->joininfo)
     258             :     {
     259       10700 :         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       10700 :         if (restrictinfo->is_clone)
     270         124 :             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       10576 :         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       10456 :         if (!restrictinfo->can_join ||
     283       10386 :             restrictinfo->mergeopfamilies == NIL)
     284          70 :             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       10386 :         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       10380 :         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       10366 :     if (rel_is_distinct_for(root, innerrel, clause_list, NULL))
     303       10240 :         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       10828 : remove_rel_from_query(PlannerInfo *root, RelOptInfo *rel,
     324             :                       int subst, SpecialJoinInfo *sjinfo,
     325             :                       Relids joinrelids)
     326             : {
     327       10828 :     int         relid = rel->relid;
     328             :     Index       rti;
     329             :     ListCell   *l;
     330             : 
     331             :     /*
     332             :      * Update all_baserels and related relid sets.
     333             :      */
     334       10828 :     root->all_baserels = adjust_relid_set(root->all_baserels, relid, subst);
     335       10828 :     root->all_query_rels = adjust_relid_set(root->all_query_rels, relid, subst);
     336             : 
     337       10828 :     if (sjinfo != NULL)
     338             :     {
     339       20480 :         root->outer_join_rels = bms_del_member(root->outer_join_rels,
     340       10240 :                                                sjinfo->ojrelid);
     341       10240 :         root->all_query_rels = bms_del_member(root->all_query_rels,
     342       10240 :                                               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       24886 :     foreach(l, root->join_info_list)
     354             :     {
     355       14058 :         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       14058 :         sjinf->min_lefthand = bms_copy(sjinf->min_lefthand);
     364       14058 :         sjinf->min_righthand = bms_copy(sjinf->min_righthand);
     365       14058 :         sjinf->syn_lefthand = bms_copy(sjinf->syn_lefthand);
     366       14058 :         sjinf->syn_righthand = bms_copy(sjinf->syn_righthand);
     367             :         /* Now remove relid from the sets: */
     368       14058 :         sjinf->min_lefthand = adjust_relid_set(sjinf->min_lefthand, relid, subst);
     369       14058 :         sjinf->min_righthand = adjust_relid_set(sjinf->min_righthand, relid, subst);
     370       14058 :         sjinf->syn_lefthand = adjust_relid_set(sjinf->syn_lefthand, relid, subst);
     371       14058 :         sjinf->syn_righthand = adjust_relid_set(sjinf->syn_righthand, relid, subst);
     372             : 
     373       14058 :         if (sjinfo != NULL)
     374             :         {
     375             :             Assert(subst <= 0);
     376             : 
     377             :             /* Remove sjinfo->ojrelid bits from the sets: */
     378       27924 :             sjinf->min_lefthand = bms_del_member(sjinf->min_lefthand,
     379       13962 :                                                  sjinfo->ojrelid);
     380       27924 :             sjinf->min_righthand = bms_del_member(sjinf->min_righthand,
     381       13962 :                                                   sjinfo->ojrelid);
     382       27924 :             sjinf->syn_lefthand = bms_del_member(sjinf->syn_lefthand,
     383       13962 :                                                  sjinfo->ojrelid);
     384       27924 :             sjinf->syn_righthand = bms_del_member(sjinf->syn_righthand,
     385       13962 :                                                   sjinfo->ojrelid);
     386             :             /* relid cannot appear in these fields, but ojrelid can: */
     387       27924 :             sjinf->commute_above_l = bms_del_member(sjinf->commute_above_l,
     388       13962 :                                                     sjinfo->ojrelid);
     389       27924 :             sjinf->commute_above_r = bms_del_member(sjinf->commute_above_r,
     390       13962 :                                                     sjinfo->ojrelid);
     391       27924 :             sjinf->commute_below_l = bms_del_member(sjinf->commute_below_l,
     392       13962 :                                                     sjinfo->ojrelid);
     393       13962 :             sjinf->commute_below_r = bms_del_member(sjinf->commute_below_r,
     394       13962 :                                                     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       11038 :     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       57704 :     foreach(l, root->eq_classes)
     471             :     {
     472       46876 :         EquivalenceClass *ec = (EquivalenceClass *) lfirst(l);
     473             : 
     474       46876 :         if (bms_is_member(relid, ec->ec_relids) ||
     475       31152 :             (sjinfo == NULL || bms_is_member(sjinfo->ojrelid, ec->ec_relids)))
     476       15724 :             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       67756 :     for (rti = 1; rti < root->simple_rel_array_size; rti++)
     494             :     {
     495       56928 :         RelOptInfo *otherrel = root->simple_rel_array[rti];
     496             :         int         attroff;
     497             : 
     498             :         /* there may be empty slots corresponding to non-baserel RTEs */
     499       56928 :         if (otherrel == NULL)
     500       27746 :             continue;
     501             : 
     502             :         Assert(otherrel->relid == rti); /* sanity check on array */
     503             : 
     504      649966 :         for (attroff = otherrel->max_attr - otherrel->min_attr;
     505             :              attroff >= 0;
     506      620784 :              attroff--)
     507             :         {
     508      620784 :             if (bms_is_member(0, otherrel->attr_needed[attroff]))
     509       45650 :                 otherrel->attr_needed[attroff] = bms_make_singleton(0);
     510             :             else
     511      575134 :                 otherrel->attr_needed[attroff] = NULL;
     512             :         }
     513             : 
     514       29182 :         if (subst > 0)
     515        1460 :             ChangeVarNodes((Node *) otherrel->lateral_vars, relid, subst, 0);
     516             :     }
     517       10828 : }
     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       10240 : remove_leftjoinrel_from_query(PlannerInfo *root, int relid,
     529             :                               SpecialJoinInfo *sjinfo)
     530             : {
     531       10240 :     RelOptInfo *rel = find_base_rel(root, relid);
     532       10240 :     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       10240 :     joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
     540             :     Assert(ojrelid != 0);
     541       10240 :     joinrelids = bms_add_member(joinrelids, ojrelid);
     542             : 
     543       10240 :     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       10240 :     join_plus_commute = bms_union(joinrelids,
     562       10240 :                                   sjinfo->commute_above_r);
     563       10240 :     join_plus_commute = bms_add_members(join_plus_commute,
     564       10240 :                                         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       10240 :     joininfos = list_copy(rel->joininfo);
     572       20838 :     foreach(l, joininfos)
     573             :     {
     574       10598 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
     575             : 
     576       10598 :         remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
     577             : 
     578       10598 :         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       10240 :     root->simple_rel_array[relid] = NULL;
     618             : 
     619             :     /* And nuke the RelOptInfo, just in case there's another access path */
     620       10240 :     pfree(rel);
     621             : 
     622             :     /*
     623             :      * Now repeat construction of attr_needed bits coming from all other
     624             :      * sources.
     625             :      */
     626       10240 :     rebuild_placeholder_attr_needed(root);
     627       10240 :     rebuild_joinclause_attr_needed(root);
     628       10240 :     rebuild_eclass_attr_needed(root);
     629       10240 :     rebuild_lateral_attr_needed(root);
     630       10240 : }
     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        4480 : 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        4480 :     rinfo->clause_relids = bms_copy(rinfo->clause_relids);
     651        4480 :     rinfo->clause_relids = bms_del_member(rinfo->clause_relids, relid);
     652        4480 :     rinfo->clause_relids = bms_del_member(rinfo->clause_relids, ojrelid);
     653             :     /* Likewise for required_relids */
     654        4480 :     rinfo->required_relids = bms_copy(rinfo->required_relids);
     655        4480 :     rinfo->required_relids = bms_del_member(rinfo->required_relids, relid);
     656        4480 :     rinfo->required_relids = bms_del_member(rinfo->required_relids, ojrelid);
     657             : 
     658             :     /* If it's an OR, recurse to clean up sub-clauses */
     659        4480 :     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        4480 : }
     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       15724 : 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       15724 :     ec->ec_relids = adjust_relid_set(ec->ec_relids, relid, subst);
     709       15724 :     if (sjinfo != NULL)
     710       14686 :         ec->ec_relids = adjust_relid_set(ec->ec_relids,
     711       14686 :                                          sjinfo->ojrelid, subst);
     712             : 
     713             :     /*
     714             :      * Fix up the member expressions.  Any non-const member that ends with
     715             :      * empty em_relids must be a Var or PHV of the removed relation.  We don't
     716             :      * need it anymore, so we can drop it.
     717             :      */
     718       36566 :     foreach(lc, ec->ec_members)
     719             :     {
     720       20842 :         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
     721             : 
     722       20842 :         if (bms_is_member(relid, cur_em->em_relids) ||
     723        4348 :             (sjinfo != NULL && bms_is_member(sjinfo->ojrelid,
     724        4348 :                                              cur_em->em_relids)))
     725             :         {
     726             :             Assert(!cur_em->em_is_const);
     727       14686 :             cur_em->em_relids = adjust_relid_set(cur_em->em_relids, relid, subst);
     728       14686 :             if (sjinfo != NULL)
     729       14686 :                 cur_em->em_relids = adjust_relid_set(cur_em->em_relids,
     730       14686 :                                                      sjinfo->ojrelid, subst);
     731       14686 :             if (bms_is_empty(cur_em->em_relids))
     732       14674 :                 ec->ec_members = foreach_delete_current(ec->ec_members, lc);
     733             :         }
     734             :     }
     735             : 
     736             :     /* Fix up the source clauses, in case we can re-use them later */
     737       21110 :     foreach(lc, ec->ec_sources)
     738             :     {
     739        5386 :         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
     740             : 
     741        5386 :         if (sjinfo == NULL)
     742        1038 :             ChangeVarNodes((Node *) rinfo, relid, subst, 0);
     743             :         else
     744        4348 :             remove_rel_from_restrictinfo(rinfo, relid, sjinfo->ojrelid);
     745             :     }
     746             : 
     747             :     /*
     748             :      * Rather than expend code on fixing up any already-derived clauses, just
     749             :      * drop them.  (At this point, any such clauses would be base restriction
     750             :      * clauses, which we'd not need anymore anyway.)
     751             :      */
     752       15724 :     ec->ec_derives = NIL;
     753       15724 : }
     754             : 
     755             : /*
     756             :  * Remove any occurrences of the target relid from a joinlist structure.
     757             :  *
     758             :  * It's easiest to build a whole new list structure, so we handle it that
     759             :  * way.  Efficiency is not a big deal here.
     760             :  *
     761             :  * *nremoved is incremented by the number of occurrences removed (there
     762             :  * should be exactly one, but the caller checks that).
     763             :  */
     764             : static List *
     765       11092 : remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
     766             : {
     767       11092 :     List       *result = NIL;
     768             :     ListCell   *jl;
     769             : 
     770       40538 :     foreach(jl, joinlist)
     771             :     {
     772       29446 :         Node       *jlnode = (Node *) lfirst(jl);
     773             : 
     774       29446 :         if (IsA(jlnode, RangeTblRef))
     775             :         {
     776       29182 :             int         varno = ((RangeTblRef *) jlnode)->rtindex;
     777             : 
     778       29182 :             if (varno == relid)
     779       10828 :                 (*nremoved)++;
     780             :             else
     781       18354 :                 result = lappend(result, jlnode);
     782             :         }
     783         264 :         else if (IsA(jlnode, List))
     784             :         {
     785             :             /* Recurse to handle subproblem */
     786             :             List       *sublist;
     787             : 
     788         264 :             sublist = remove_rel_from_joinlist((List *) jlnode,
     789             :                                                relid, nremoved);
     790             :             /* Avoid including empty sub-lists in the result */
     791         264 :             if (sublist)
     792         264 :                 result = lappend(result, sublist);
     793             :         }
     794             :         else
     795             :         {
     796           0 :             elog(ERROR, "unrecognized joinlist node type: %d",
     797             :                  (int) nodeTag(jlnode));
     798             :         }
     799             :     }
     800             : 
     801       11092 :     return result;
     802             : }
     803             : 
     804             : 
     805             : /*
     806             :  * reduce_unique_semijoins
     807             :  *      Check for semijoins that can be simplified to plain inner joins
     808             :  *      because the inner relation is provably unique for the join clauses.
     809             :  *
     810             :  * Ideally this would happen during reduce_outer_joins, but we don't have
     811             :  * enough information at that point.
     812             :  *
     813             :  * To perform the strength reduction when applicable, we need only delete
     814             :  * the semijoin's SpecialJoinInfo from root->join_info_list.  (We don't
     815             :  * bother fixing the join type attributed to it in the query jointree,
     816             :  * since that won't be consulted again.)
     817             :  */
     818             : void
     819      314632 : reduce_unique_semijoins(PlannerInfo *root)
     820             : {
     821             :     ListCell   *lc;
     822             : 
     823             :     /*
     824             :      * Scan the join_info_list to find semijoins.
     825             :      */
     826      353604 :     foreach(lc, root->join_info_list)
     827             :     {
     828       38972 :         SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
     829             :         int         innerrelid;
     830             :         RelOptInfo *innerrel;
     831             :         Relids      joinrelids;
     832             :         List       *restrictlist;
     833             : 
     834             :         /*
     835             :          * Must be a semijoin to a single baserel, else we aren't going to be
     836             :          * able to do anything with it.
     837             :          */
     838       38972 :         if (sjinfo->jointype != JOIN_SEMI)
     839       38662 :             continue;
     840             : 
     841        2208 :         if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
     842         164 :             continue;
     843             : 
     844        2044 :         innerrel = find_base_rel(root, innerrelid);
     845             : 
     846             :         /*
     847             :          * Before we trouble to run generate_join_implied_equalities, make a
     848             :          * quick check to eliminate cases in which we will surely be unable to
     849             :          * prove uniqueness of the innerrel.
     850             :          */
     851        2044 :         if (!rel_supports_distinctness(root, innerrel))
     852         878 :             continue;
     853             : 
     854             :         /* Compute the relid set for the join we are considering */
     855        1166 :         joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
     856             :         Assert(sjinfo->ojrelid == 0);    /* SEMI joins don't have RT indexes */
     857             : 
     858             :         /*
     859             :          * Since we're only considering a single-rel RHS, any join clauses it
     860             :          * has must be clauses linking it to the semijoin's min_lefthand.  We
     861             :          * can also consider EC-derived join clauses.
     862             :          */
     863             :         restrictlist =
     864        1166 :             list_concat(generate_join_implied_equalities(root,
     865             :                                                          joinrelids,
     866             :                                                          sjinfo->min_lefthand,
     867             :                                                          innerrel,
     868             :                                                          NULL),
     869        1166 :                         innerrel->joininfo);
     870             : 
     871             :         /* Test whether the innerrel is unique for those clauses. */
     872        1166 :         if (!innerrel_is_unique(root,
     873             :                                 joinrelids, sjinfo->min_lefthand, innerrel,
     874             :                                 JOIN_SEMI, restrictlist, true))
     875         856 :             continue;
     876             : 
     877             :         /* OK, remove the SpecialJoinInfo from the list. */
     878         310 :         root->join_info_list = foreach_delete_current(root->join_info_list, lc);
     879             :     }
     880      314632 : }
     881             : 
     882             : 
     883             : /*
     884             :  * rel_supports_distinctness
     885             :  *      Could the relation possibly be proven distinct on some set of columns?
     886             :  *
     887             :  * This is effectively a pre-checking function for rel_is_distinct_for().
     888             :  * It must return true if rel_is_distinct_for() could possibly return true
     889             :  * with this rel, but it should not expend a lot of cycles.  The idea is
     890             :  * that callers can avoid doing possibly-expensive processing to compute
     891             :  * rel_is_distinct_for()'s argument lists if the call could not possibly
     892             :  * succeed.
     893             :  */
     894             : static bool
     895      569176 : rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
     896             : {
     897             :     /* We only know about baserels ... */
     898      569176 :     if (rel->reloptkind != RELOPT_BASEREL)
     899      187370 :         return false;
     900      381806 :     if (rel->rtekind == RTE_RELATION)
     901             :     {
     902             :         /*
     903             :          * For a plain relation, we only know how to prove uniqueness by
     904             :          * reference to unique indexes.  Make sure there's at least one
     905             :          * suitable unique index.  It must be immediately enforced, and not a
     906             :          * partial index. (Keep these conditions in sync with
     907             :          * relation_has_unique_index_for!)
     908             :          */
     909             :         ListCell   *lc;
     910             : 
     911      489290 :         foreach(lc, rel->indexlist)
     912             :         {
     913      439728 :             IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
     914             : 
     915      439728 :             if (ind->unique && ind->immediate && ind->indpred == NIL)
     916      304882 :                 return true;
     917             :         }
     918             :     }
     919       27362 :     else if (rel->rtekind == RTE_SUBQUERY)
     920             :     {
     921        4656 :         Query      *subquery = root->simple_rte_array[rel->relid]->subquery;
     922             : 
     923             :         /* Check if the subquery has any qualities that support distinctness */
     924        4656 :         if (query_supports_distinctness(subquery))
     925        3136 :             return true;
     926             :     }
     927             :     /* We have no proof rules for any other rtekinds. */
     928       73788 :     return false;
     929             : }
     930             : 
     931             : /*
     932             :  * rel_is_distinct_for
     933             :  *      Does the relation return only distinct rows according to clause_list?
     934             :  *
     935             :  * clause_list is a list of join restriction clauses involving this rel and
     936             :  * some other one.  Return true if no two rows emitted by this rel could
     937             :  * possibly join to the same row of the other rel.
     938             :  *
     939             :  * The caller must have already determined that each condition is a
     940             :  * mergejoinable equality with an expression in this relation on one side, and
     941             :  * an expression not involving this relation on the other.  The transient
     942             :  * outer_is_left flag is used to identify which side references this relation:
     943             :  * left side if outer_is_left is false, right side if it is true.
     944             :  *
     945             :  * Note that the passed-in clause_list may be destructively modified!  This
     946             :  * is OK for current uses, because the clause_list is built by the caller for
     947             :  * the sole purpose of passing to this function.
     948             :  *
     949             :  * (*extra_clauses) to be set to the right sides of baserestrictinfo clauses,
     950             :  * looking like "x = const" if distinctness is derived from such clauses, not
     951             :  * joininfo clauses.  Pass NULL to the extra_clauses if this value is not
     952             :  * needed.
     953             :  */
     954             : static bool
     955      196472 : rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list,
     956             :                     List **extra_clauses)
     957             : {
     958             :     /*
     959             :      * We could skip a couple of tests here if we assume all callers checked
     960             :      * rel_supports_distinctness first, but it doesn't seem worth taking any
     961             :      * risk for.
     962             :      */
     963      196472 :     if (rel->reloptkind != RELOPT_BASEREL)
     964           0 :         return false;
     965      196472 :     if (rel->rtekind == RTE_RELATION)
     966             :     {
     967             :         /*
     968             :          * Examine the indexes to see if we have a matching unique index.
     969             :          * relation_has_unique_index_ext automatically adds any usable
     970             :          * restriction clauses for the rel, so we needn't do that here.
     971             :          */
     972      194338 :         if (relation_has_unique_index_ext(root, rel, clause_list, NIL, NIL,
     973             :                                           extra_clauses))
     974      115096 :             return true;
     975             :     }
     976        2134 :     else if (rel->rtekind == RTE_SUBQUERY)
     977             :     {
     978        2134 :         Index       relid = rel->relid;
     979        2134 :         Query      *subquery = root->simple_rte_array[relid]->subquery;
     980        2134 :         List       *colnos = NIL;
     981        2134 :         List       *opids = NIL;
     982             :         ListCell   *l;
     983             : 
     984             :         /*
     985             :          * Build the argument lists for query_is_distinct_for: a list of
     986             :          * output column numbers that the query needs to be distinct over, and
     987             :          * a list of equality operators that the output columns need to be
     988             :          * distinct according to.
     989             :          *
     990             :          * (XXX we are not considering restriction clauses attached to the
     991             :          * subquery; is that worth doing?)
     992             :          */
     993        4232 :         foreach(l, clause_list)
     994             :         {
     995        2098 :             RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
     996             :             Oid         op;
     997             :             Var        *var;
     998             : 
     999             :             /*
    1000             :              * Get the equality operator we need uniqueness according to.
    1001             :              * (This might be a cross-type operator and thus not exactly the
    1002             :              * same operator the subquery would consider; that's all right
    1003             :              * since query_is_distinct_for can resolve such cases.)  The
    1004             :              * caller's mergejoinability test should have selected only
    1005             :              * OpExprs.
    1006             :              */
    1007        2098 :             op = castNode(OpExpr, rinfo->clause)->opno;
    1008             : 
    1009             :             /* caller identified the inner side for us */
    1010        2098 :             if (rinfo->outer_is_left)
    1011        1760 :                 var = (Var *) get_rightop(rinfo->clause);
    1012             :             else
    1013         338 :                 var = (Var *) get_leftop(rinfo->clause);
    1014             : 
    1015             :             /*
    1016             :              * We may ignore any RelabelType node above the operand.  (There
    1017             :              * won't be more than one, since eval_const_expressions() has been
    1018             :              * applied already.)
    1019             :              */
    1020        2098 :             if (var && IsA(var, RelabelType))
    1021         638 :                 var = (Var *) ((RelabelType *) var)->arg;
    1022             : 
    1023             :             /*
    1024             :              * If inner side isn't a Var referencing a subquery output column,
    1025             :              * this clause doesn't help us.
    1026             :              */
    1027        2098 :             if (!var || !IsA(var, Var) ||
    1028        2086 :                 var->varno != relid || var->varlevelsup != 0)
    1029          12 :                 continue;
    1030             : 
    1031        2086 :             colnos = lappend_int(colnos, var->varattno);
    1032        2086 :             opids = lappend_oid(opids, op);
    1033             :         }
    1034             : 
    1035        2134 :         if (query_is_distinct_for(subquery, colnos, opids))
    1036         212 :             return true;
    1037             :     }
    1038       81164 :     return false;
    1039             : }
    1040             : 
    1041             : 
    1042             : /*
    1043             :  * query_supports_distinctness - could the query possibly be proven distinct
    1044             :  *      on some set of output columns?
    1045             :  *
    1046             :  * This is effectively a pre-checking function for query_is_distinct_for().
    1047             :  * It must return true if query_is_distinct_for() could possibly return true
    1048             :  * with this query, but it should not expend a lot of cycles.  The idea is
    1049             :  * that callers can avoid doing possibly-expensive processing to compute
    1050             :  * query_is_distinct_for()'s argument lists if the call could not possibly
    1051             :  * succeed.
    1052             :  */
    1053             : bool
    1054        5402 : query_supports_distinctness(Query *query)
    1055             : {
    1056             :     /* SRFs break distinctness except with DISTINCT, see below */
    1057        5402 :     if (query->hasTargetSRFs && query->distinctClause == NIL)
    1058        1004 :         return false;
    1059             : 
    1060             :     /* check for features we can prove distinctness with */
    1061        4398 :     if (query->distinctClause != NIL ||
    1062        4254 :         query->groupClause != NIL ||
    1063        4066 :         query->groupingSets != NIL ||
    1064        4066 :         query->hasAggs ||
    1065        3794 :         query->havingQual ||
    1066        3794 :         query->setOperations)
    1067        3846 :         return true;
    1068             : 
    1069         552 :     return false;
    1070             : }
    1071             : 
    1072             : /*
    1073             :  * query_is_distinct_for - does query never return duplicates of the
    1074             :  *      specified columns?
    1075             :  *
    1076             :  * query is a not-yet-planned subquery (in current usage, it's always from
    1077             :  * a subquery RTE, which the planner avoids scribbling on).
    1078             :  *
    1079             :  * colnos is an integer list of output column numbers (resno's).  We are
    1080             :  * interested in whether rows consisting of just these columns are certain
    1081             :  * to be distinct.  "Distinctness" is defined according to whether the
    1082             :  * corresponding upper-level equality operators listed in opids would think
    1083             :  * the values are distinct.  (Note: the opids entries could be cross-type
    1084             :  * operators, and thus not exactly the equality operators that the subquery
    1085             :  * would use itself.  We use equality_ops_are_compatible() to check
    1086             :  * compatibility.  That looks at opfamily membership for index AMs that have
    1087             :  * declared that they support consistent equality semantics within an
    1088             :  * opfamily, and so should give trustworthy answers for all operators that we
    1089             :  * might need to deal with here.)
    1090             :  */
    1091             : bool
    1092        2330 : query_is_distinct_for(Query *query, List *colnos, List *opids)
    1093             : {
    1094             :     ListCell   *l;
    1095             :     Oid         opid;
    1096             : 
    1097             :     Assert(list_length(colnos) == list_length(opids));
    1098             : 
    1099             :     /*
    1100             :      * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
    1101             :      * columns in the DISTINCT clause appear in colnos and operator semantics
    1102             :      * match.  This is true even if there are SRFs in the DISTINCT columns or
    1103             :      * elsewhere in the tlist.
    1104             :      */
    1105        2330 :     if (query->distinctClause)
    1106             :     {
    1107         150 :         foreach(l, query->distinctClause)
    1108             :         {
    1109         120 :             SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
    1110         120 :             TargetEntry *tle = get_sortgroupclause_tle(sgc,
    1111             :                                                        query->targetList);
    1112             : 
    1113         120 :             opid = distinct_col_search(tle->resno, colnos, opids);
    1114         120 :             if (!OidIsValid(opid) ||
    1115          48 :                 !equality_ops_are_compatible(opid, sgc->eqop))
    1116             :                 break;          /* exit early if no match */
    1117             :         }
    1118         102 :         if (l == NULL)          /* had matches for all? */
    1119          30 :             return true;
    1120             :     }
    1121             : 
    1122             :     /*
    1123             :      * Otherwise, a set-returning function in the query's targetlist can
    1124             :      * result in returning duplicate rows, despite any grouping that might
    1125             :      * occur before tlist evaluation.  (If all tlist SRFs are within GROUP BY
    1126             :      * columns, it would be safe because they'd be expanded before grouping.
    1127             :      * But it doesn't currently seem worth the effort to check for that.)
    1128             :      */
    1129        2300 :     if (query->hasTargetSRFs)
    1130           0 :         return false;
    1131             : 
    1132             :     /*
    1133             :      * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if all
    1134             :      * the grouped columns appear in colnos and operator semantics match.
    1135             :      */
    1136        2300 :     if (query->groupClause && !query->groupingSets)
    1137             :     {
    1138         234 :         foreach(l, query->groupClause)
    1139             :         {
    1140         164 :             SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
    1141         164 :             TargetEntry *tle = get_sortgroupclause_tle(sgc,
    1142             :                                                        query->targetList);
    1143             : 
    1144         164 :             opid = distinct_col_search(tle->resno, colnos, opids);
    1145         164 :             if (!OidIsValid(opid) ||
    1146         112 :                 !equality_ops_are_compatible(opid, sgc->eqop))
    1147             :                 break;          /* exit early if no match */
    1148             :         }
    1149         122 :         if (l == NULL)          /* had matches for all? */
    1150          70 :             return true;
    1151             :     }
    1152        2178 :     else if (query->groupingSets)
    1153             :     {
    1154             :         /*
    1155             :          * If we have grouping sets with expressions, we probably don't have
    1156             :          * uniqueness and analysis would be hard. Punt.
    1157             :          */
    1158           0 :         if (query->groupClause)
    1159           0 :             return false;
    1160             : 
    1161             :         /*
    1162             :          * If we have no groupClause (therefore no grouping expressions), we
    1163             :          * might have one or many empty grouping sets. If there's just one,
    1164             :          * then we're returning only one row and are certainly unique. But
    1165             :          * otherwise, we know we're certainly not unique.
    1166             :          */
    1167           0 :         if (list_length(query->groupingSets) == 1 &&
    1168           0 :             ((GroupingSet *) linitial(query->groupingSets))->kind == GROUPING_SET_EMPTY)
    1169           0 :             return true;
    1170             :         else
    1171           0 :             return false;
    1172             :     }
    1173             :     else
    1174             :     {
    1175             :         /*
    1176             :          * If we have no GROUP BY, but do have aggregates or HAVING, then the
    1177             :          * result is at most one row so it's surely unique, for any operators.
    1178             :          */
    1179        2178 :         if (query->hasAggs || query->havingQual)
    1180         100 :             return true;
    1181             :     }
    1182             : 
    1183             :     /*
    1184             :      * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
    1185             :      * except with ALL.
    1186             :      */
    1187        2130 :     if (query->setOperations)
    1188             :     {
    1189        2006 :         SetOperationStmt *topop = castNode(SetOperationStmt, query->setOperations);
    1190             : 
    1191             :         Assert(topop->op != SETOP_NONE);
    1192             : 
    1193        2006 :         if (!topop->all)
    1194             :         {
    1195             :             ListCell   *lg;
    1196             : 
    1197             :             /* We're good if all the nonjunk output columns are in colnos */
    1198          72 :             lg = list_head(topop->groupClauses);
    1199          90 :             foreach(l, query->targetList)
    1200             :             {
    1201          78 :                 TargetEntry *tle = (TargetEntry *) lfirst(l);
    1202             :                 SortGroupClause *sgc;
    1203             : 
    1204          78 :                 if (tle->resjunk)
    1205           0 :                     continue;   /* ignore resjunk columns */
    1206             : 
    1207             :                 /* non-resjunk columns should have grouping clauses */
    1208             :                 Assert(lg != NULL);
    1209          78 :                 sgc = (SortGroupClause *) lfirst(lg);
    1210          78 :                 lg = lnext(topop->groupClauses, lg);
    1211             : 
    1212          78 :                 opid = distinct_col_search(tle->resno, colnos, opids);
    1213          78 :                 if (!OidIsValid(opid) ||
    1214          18 :                     !equality_ops_are_compatible(opid, sgc->eqop))
    1215             :                     break;      /* exit early if no match */
    1216             :             }
    1217          72 :             if (l == NULL)      /* had matches for all? */
    1218          12 :                 return true;
    1219             :         }
    1220             :     }
    1221             : 
    1222             :     /*
    1223             :      * XXX Are there any other cases in which we can easily see the result
    1224             :      * must be distinct?
    1225             :      *
    1226             :      * If you do add more smarts to this function, be sure to update
    1227             :      * query_supports_distinctness() to match.
    1228             :      */
    1229             : 
    1230        2118 :     return false;
    1231             : }
    1232             : 
    1233             : /*
    1234             :  * distinct_col_search - subroutine for query_is_distinct_for
    1235             :  *
    1236             :  * If colno is in colnos, return the corresponding element of opids,
    1237             :  * else return InvalidOid.  (Ordinarily colnos would not contain duplicates,
    1238             :  * but if it does, we arbitrarily select the first match.)
    1239             :  */
    1240             : static Oid
    1241         362 : distinct_col_search(int colno, List *colnos, List *opids)
    1242             : {
    1243             :     ListCell   *lc1,
    1244             :                *lc2;
    1245             : 
    1246         574 :     forboth(lc1, colnos, lc2, opids)
    1247             :     {
    1248         390 :         if (colno == lfirst_int(lc1))
    1249         178 :             return lfirst_oid(lc2);
    1250             :     }
    1251         184 :     return InvalidOid;
    1252             : }
    1253             : 
    1254             : 
    1255             : /*
    1256             :  * innerrel_is_unique
    1257             :  *    Check if the innerrel provably contains at most one tuple matching any
    1258             :  *    tuple from the outerrel, based on join clauses in the 'restrictlist'.
    1259             :  *
    1260             :  * We need an actual RelOptInfo for the innerrel, but it's sufficient to
    1261             :  * identify the outerrel by its Relids.  This asymmetry supports use of this
    1262             :  * function before joinrels have been built.  (The caller is expected to
    1263             :  * also supply the joinrelids, just to save recalculating that.)
    1264             :  *
    1265             :  * The proof must be made based only on clauses that will be "joinquals"
    1266             :  * rather than "otherquals" at execution.  For an inner join there's no
    1267             :  * difference; but if the join is outer, we must ignore pushed-down quals,
    1268             :  * as those will become "otherquals".  Note that this means the answer might
    1269             :  * vary depending on whether IS_OUTER_JOIN(jointype); since we cache the
    1270             :  * answer without regard to that, callers must take care not to call this
    1271             :  * with jointypes that would be classified differently by IS_OUTER_JOIN().
    1272             :  *
    1273             :  * The actual proof is undertaken by is_innerrel_unique_for(); this function
    1274             :  * is a frontend that is mainly concerned with caching the answers.
    1275             :  * In particular, the force_cache argument allows overriding the internal
    1276             :  * heuristic about whether to cache negative answers; it should be "true"
    1277             :  * if making an inquiry that is not part of the normal bottom-up join search
    1278             :  * sequence.
    1279             :  */
    1280             : bool
    1281      627934 : innerrel_is_unique(PlannerInfo *root,
    1282             :                    Relids joinrelids,
    1283             :                    Relids outerrelids,
    1284             :                    RelOptInfo *innerrel,
    1285             :                    JoinType jointype,
    1286             :                    List *restrictlist,
    1287             :                    bool force_cache)
    1288             : {
    1289      627934 :     return innerrel_is_unique_ext(root, joinrelids, outerrelids, innerrel,
    1290             :                                   jointype, restrictlist, force_cache, NULL);
    1291             : }
    1292             : 
    1293             : /*
    1294             :  * innerrel_is_unique_ext
    1295             :  *    Do the same as innerrel_is_unique(), but also set to (*extra_clauses)
    1296             :  *    additional clauses from a baserestrictinfo list used to prove the
    1297             :  *    uniqueness.
    1298             :  *
    1299             :  * A non-NULL extra_clauses indicates that we're checking for self-join and
    1300             :  * correspondingly dealing with filtered clauses.
    1301             :  */
    1302             : bool
    1303      629910 : innerrel_is_unique_ext(PlannerInfo *root,
    1304             :                        Relids joinrelids,
    1305             :                        Relids outerrelids,
    1306             :                        RelOptInfo *innerrel,
    1307             :                        JoinType jointype,
    1308             :                        List *restrictlist,
    1309             :                        bool force_cache,
    1310             :                        List **extra_clauses)
    1311             : {
    1312             :     MemoryContext old_context;
    1313             :     ListCell   *lc;
    1314             :     UniqueRelInfo *uniqueRelInfo;
    1315      629910 :     List       *outer_exprs = NIL;
    1316      629910 :     bool        self_join = (extra_clauses != NULL);
    1317             : 
    1318             :     /* Certainly can't prove uniqueness when there are no joinclauses */
    1319      629910 :     if (restrictlist == NIL)
    1320      103106 :         return false;
    1321             : 
    1322             :     /*
    1323             :      * Make a quick check to eliminate cases in which we will surely be unable
    1324             :      * to prove uniqueness of the innerrel.
    1325             :      */
    1326      526804 :     if (!rel_supports_distinctness(root, innerrel))
    1327      257270 :         return false;
    1328             : 
    1329             :     /*
    1330             :      * Query the cache to see if we've managed to prove that innerrel is
    1331             :      * unique for any subset of this outerrel.  For non-self-join search, we
    1332             :      * don't need an exact match, as extra outerrels can't make the innerrel
    1333             :      * any less unique (or more formally, the restrictlist for a join to a
    1334             :      * superset outerrel must be a superset of the conditions we successfully
    1335             :      * used before). For self-join search, we require an exact match of
    1336             :      * outerrels because we need extra clauses to be valid for our case. Also,
    1337             :      * for self-join checking we've filtered the clauses list.  Thus, we can
    1338             :      * match only the result cached for a self-join search for another
    1339             :      * self-join check.
    1340             :      */
    1341      300258 :     foreach(lc, innerrel->unique_for_rels)
    1342             :     {
    1343      113828 :         uniqueRelInfo = (UniqueRelInfo *) lfirst(lc);
    1344             : 
    1345      113828 :         if ((!self_join && bms_is_subset(uniqueRelInfo->outerrelids, outerrelids)) ||
    1346          68 :             (self_join && bms_equal(uniqueRelInfo->outerrelids, outerrelids) &&
    1347          56 :              uniqueRelInfo->self_join))
    1348             :         {
    1349       83104 :             if (extra_clauses)
    1350          12 :                 *extra_clauses = uniqueRelInfo->extra_clauses;
    1351       83104 :             return true;        /* Success! */
    1352             :         }
    1353             :     }
    1354             : 
    1355             :     /*
    1356             :      * Conversely, we may have already determined that this outerrel, or some
    1357             :      * superset thereof, cannot prove this innerrel to be unique.
    1358             :      */
    1359      186914 :     foreach(lc, innerrel->non_unique_for_rels)
    1360             :     {
    1361         808 :         Relids      unique_for_rels = (Relids) lfirst(lc);
    1362             : 
    1363         808 :         if (bms_is_subset(outerrelids, unique_for_rels))
    1364         324 :             return false;
    1365             :     }
    1366             : 
    1367             :     /* No cached information, so try to make the proof. */
    1368      186106 :     if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
    1369             :                                jointype, restrictlist,
    1370             :                                self_join ? &outer_exprs : NULL))
    1371             :     {
    1372             :         /*
    1373             :          * Cache the positive result for future probes, being sure to keep it
    1374             :          * in the planner_cxt even if we are working in GEQO.
    1375             :          *
    1376             :          * Note: one might consider trying to isolate the minimal subset of
    1377             :          * the outerrels that proved the innerrel unique.  But it's not worth
    1378             :          * the trouble, because the planner builds up joinrels incrementally
    1379             :          * and so we'll see the minimally sufficient outerrels before any
    1380             :          * supersets of them anyway.
    1381             :          */
    1382      105068 :         old_context = MemoryContextSwitchTo(root->planner_cxt);
    1383      105068 :         uniqueRelInfo = makeNode(UniqueRelInfo);
    1384      105068 :         uniqueRelInfo->outerrelids = bms_copy(outerrelids);
    1385      105068 :         uniqueRelInfo->self_join = self_join;
    1386      105068 :         uniqueRelInfo->extra_clauses = outer_exprs;
    1387      105068 :         innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
    1388             :                                             uniqueRelInfo);
    1389      105068 :         MemoryContextSwitchTo(old_context);
    1390             : 
    1391      105068 :         if (extra_clauses)
    1392         642 :             *extra_clauses = outer_exprs;
    1393      105068 :         return true;            /* Success! */
    1394             :     }
    1395             :     else
    1396             :     {
    1397             :         /*
    1398             :          * None of the join conditions for outerrel proved innerrel unique, so
    1399             :          * we can safely reject this outerrel or any subset of it in future
    1400             :          * checks.
    1401             :          *
    1402             :          * However, in normal planning mode, caching this knowledge is totally
    1403             :          * pointless; it won't be queried again, because we build up joinrels
    1404             :          * from smaller to larger.  It is useful in GEQO mode, where the
    1405             :          * knowledge can be carried across successive planning attempts; and
    1406             :          * it's likely to be useful when using join-search plugins, too. Hence
    1407             :          * cache when join_search_private is non-NULL.  (Yeah, that's a hack,
    1408             :          * but it seems reasonable.)
    1409             :          *
    1410             :          * Also, allow callers to override that heuristic and force caching;
    1411             :          * that's useful for reduce_unique_semijoins, which calls here before
    1412             :          * the normal join search starts.
    1413             :          */
    1414       81038 :         if (force_cache || root->join_search_private)
    1415             :         {
    1416        1180 :             old_context = MemoryContextSwitchTo(root->planner_cxt);
    1417        1180 :             innerrel->non_unique_for_rels =
    1418        1180 :                 lappend(innerrel->non_unique_for_rels,
    1419        1180 :                         bms_copy(outerrelids));
    1420        1180 :             MemoryContextSwitchTo(old_context);
    1421             :         }
    1422             : 
    1423       81038 :         return false;
    1424             :     }
    1425             : }
    1426             : 
    1427             : /*
    1428             :  * is_innerrel_unique_for
    1429             :  *    Check if the innerrel provably contains at most one tuple matching any
    1430             :  *    tuple from the outerrel, based on join clauses in the 'restrictlist'.
    1431             :  */
    1432             : static bool
    1433      186106 : is_innerrel_unique_for(PlannerInfo *root,
    1434             :                        Relids joinrelids,
    1435             :                        Relids outerrelids,
    1436             :                        RelOptInfo *innerrel,
    1437             :                        JoinType jointype,
    1438             :                        List *restrictlist,
    1439             :                        List **extra_clauses)
    1440             : {
    1441      186106 :     List       *clause_list = NIL;
    1442             :     ListCell   *lc;
    1443             : 
    1444             :     /*
    1445             :      * Search for mergejoinable clauses that constrain the inner rel against
    1446             :      * the outer rel.  If an operator is mergejoinable then it behaves like
    1447             :      * equality for some btree opclass, so it's what we want.  The
    1448             :      * mergejoinability test also eliminates clauses containing volatile
    1449             :      * functions, which we couldn't depend on.
    1450             :      */
    1451      412052 :     foreach(lc, restrictlist)
    1452             :     {
    1453      225946 :         RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
    1454             : 
    1455             :         /*
    1456             :          * As noted above, if it's a pushed-down clause and we're at an outer
    1457             :          * join, we can't use it.
    1458             :          */
    1459      225946 :         if (IS_OUTER_JOIN(jointype) &&
    1460       95106 :             RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
    1461        4166 :             continue;
    1462             : 
    1463             :         /* Ignore if it's not a mergejoinable clause */
    1464      221780 :         if (!restrictinfo->can_join ||
    1465      203466 :             restrictinfo->mergeopfamilies == NIL)
    1466       19240 :             continue;           /* not mergejoinable */
    1467             : 
    1468             :         /*
    1469             :          * Check if the clause has the form "outer op inner" or "inner op
    1470             :          * outer", and if so mark which side is inner.
    1471             :          */
    1472      202540 :         if (!clause_sides_match_join(restrictinfo, outerrelids,
    1473             :                                      innerrel->relids))
    1474          40 :             continue;           /* no good for these input relations */
    1475             : 
    1476             :         /* OK, add to the list */
    1477      202500 :         clause_list = lappend(clause_list, restrictinfo);
    1478             :     }
    1479             : 
    1480             :     /* Let rel_is_distinct_for() do the hard work */
    1481      186106 :     return rel_is_distinct_for(root, innerrel, clause_list, extra_clauses);
    1482             : }
    1483             : 
    1484             : /*
    1485             :  * Update EC members to point to the remaining relation instead of the removed
    1486             :  * one, removing duplicates.
    1487             :  *
    1488             :  * Restriction clauses for base relations are already distributed to
    1489             :  * the respective baserestrictinfo lists (see
    1490             :  * generate_implied_equalities_for_column). The above code has already processed
    1491             :  * this list and updated these clauses to reference the remaining
    1492             :  * relation, so that we can skip them here based on their relids.
    1493             :  *
    1494             :  * Likewise, we have already processed the join clauses that join the
    1495             :  * removed relation to the remaining one.
    1496             :  *
    1497             :  * Finally, there might be join clauses tying the removed relation to
    1498             :  * some third relation.  We can't just delete the source clauses and
    1499             :  * regenerate them from the EC because the corresponding equality
    1500             :  * operators might be missing (see the handling of ec_broken).
    1501             :  * Therefore, we will update the references in the source clauses.
    1502             :  *
    1503             :  * Derived clauses can be generated again, so it is simpler just to
    1504             :  * delete them.
    1505             :  */
    1506             : static void
    1507         900 : update_eclasses(EquivalenceClass *ec, int from, int to)
    1508             : {
    1509         900 :     List       *new_members = NIL;
    1510         900 :     List       *new_sources = NIL;
    1511             : 
    1512        3636 :     foreach_node(EquivalenceMember, em, ec->ec_members)
    1513             :     {
    1514        1836 :         bool        is_redundant = false;
    1515             : 
    1516        1836 :         if (!bms_is_member(from, em->em_relids))
    1517             :         {
    1518         918 :             new_members = lappend(new_members, em);
    1519         918 :             continue;
    1520             :         }
    1521             : 
    1522         918 :         em->em_relids = adjust_relid_set(em->em_relids, from, to);
    1523         918 :         em->em_jdomain->jd_relids = adjust_relid_set(em->em_jdomain->jd_relids, from, to);
    1524             : 
    1525             :         /* We only process inner joins */
    1526         918 :         ChangeVarNodes((Node *) em->em_expr, from, to, 0);
    1527             : 
    1528        1860 :         foreach_node(EquivalenceMember, other, new_members)
    1529             :         {
    1530         298 :             if (!equal(em->em_relids, other->em_relids))
    1531          24 :                 continue;
    1532             : 
    1533         274 :             if (equal(em->em_expr, other->em_expr))
    1534             :             {
    1535         274 :                 is_redundant = true;
    1536         274 :                 break;
    1537             :             }
    1538             :         }
    1539             : 
    1540         918 :         if (!is_redundant)
    1541         644 :             new_members = lappend(new_members, em);
    1542             :     }
    1543             : 
    1544         900 :     list_free(ec->ec_members);
    1545         900 :     ec->ec_members = new_members;
    1546             : 
    1547         900 :     list_free(ec->ec_derives);
    1548         900 :     ec->ec_derives = NULL;
    1549             : 
    1550             :     /* Update EC source expressions */
    1551        2736 :     foreach_node(RestrictInfo, rinfo, ec->ec_sources)
    1552             :     {
    1553         936 :         bool        is_redundant = false;
    1554             : 
    1555         936 :         if (!bms_is_member(from, rinfo->required_relids))
    1556             :         {
    1557         118 :             new_sources = lappend(new_sources, rinfo);
    1558         118 :             continue;
    1559             :         }
    1560             : 
    1561         818 :         ChangeVarNodes((Node *) rinfo, from, to, 0);
    1562             : 
    1563             :         /*
    1564             :          * After switching the clause to the remaining relation, check it for
    1565             :          * redundancy with existing ones. We don't have to check for
    1566             :          * redundancy with derived clauses, because we've just deleted them.
    1567             :          */
    1568        1660 :         foreach_node(RestrictInfo, other, new_sources)
    1569             :         {
    1570          36 :             if (!equal(rinfo->clause_relids, other->clause_relids))
    1571          24 :                 continue;
    1572             : 
    1573          12 :             if (equal(rinfo->clause, other->clause))
    1574             :             {
    1575          12 :                 is_redundant = true;
    1576          12 :                 break;
    1577             :             }
    1578             :         }
    1579             : 
    1580         818 :         if (!is_redundant)
    1581         806 :             new_sources = lappend(new_sources, rinfo);
    1582             :     }
    1583             : 
    1584         900 :     list_free(ec->ec_sources);
    1585         900 :     ec->ec_sources = new_sources;
    1586         900 :     ec->ec_relids = adjust_relid_set(ec->ec_relids, from, to);
    1587         900 : }
    1588             : 
    1589             : /*
    1590             :  * "Logically" compares two RestrictInfo's ignoring the 'rinfo_serial' field,
    1591             :  * which makes almost every RestrictInfo unique.  This type of comparison is
    1592             :  * useful when removing duplicates while moving RestrictInfo's from removed
    1593             :  * relation to remaining relation during self-join elimination.
    1594             :  *
    1595             :  * XXX: In the future, we might remove the 'rinfo_serial' field completely and
    1596             :  * get rid of this function.
    1597             :  */
    1598             : static bool
    1599         506 : restrict_infos_logically_equal(RestrictInfo *a, RestrictInfo *b)
    1600             : {
    1601         506 :     int         saved_rinfo_serial = a->rinfo_serial;
    1602             :     bool        result;
    1603             : 
    1604         506 :     a->rinfo_serial = b->rinfo_serial;
    1605         506 :     result = equal(a, b);
    1606         506 :     a->rinfo_serial = saved_rinfo_serial;
    1607             : 
    1608         506 :     return result;
    1609             : }
    1610             : 
    1611             : /*
    1612             :  * This function adds all non-redundant clauses to the keeping relation
    1613             :  * during self-join elimination.  That is a contradictory operation. On the
    1614             :  * one hand, we reduce the length of the `restrict` lists, which can
    1615             :  * impact planning or executing time.  Additionally, we improve the
    1616             :  * accuracy of cardinality estimation.  On the other hand, it is one more
    1617             :  * place that can make planning time much longer in specific cases.  It
    1618             :  * would have been better to avoid calling the equal() function here, but
    1619             :  * it's the only way to detect duplicated inequality expressions.
    1620             :  *
    1621             :  * (*keep_rinfo_list) is given by pointer because it might be altered by
    1622             :  * distribute_restrictinfo_to_rels().
    1623             :  */
    1624             : static void
    1625        1176 : add_non_redundant_clauses(PlannerInfo *root,
    1626             :                           List *rinfo_candidates,
    1627             :                           List **keep_rinfo_list,
    1628             :                           Index removed_relid)
    1629             : {
    1630        3250 :     foreach_node(RestrictInfo, rinfo, rinfo_candidates)
    1631             :     {
    1632         898 :         bool        is_redundant = false;
    1633             : 
    1634             :         Assert(!bms_is_member(removed_relid, rinfo->required_relids));
    1635             : 
    1636        2160 :         foreach_node(RestrictInfo, src, (*keep_rinfo_list))
    1637             :         {
    1638         518 :             if (!bms_equal(src->clause_relids, rinfo->clause_relids))
    1639             :                 /* Can't compare trivially different clauses */
    1640           6 :                 continue;
    1641             : 
    1642         512 :             if (src == rinfo ||
    1643         512 :                 (rinfo->parent_ec != NULL &&
    1644         804 :                  src->parent_ec == rinfo->parent_ec) ||
    1645         506 :                 restrict_infos_logically_equal(rinfo, src))
    1646             :             {
    1647         154 :                 is_redundant = true;
    1648         154 :                 break;
    1649             :             }
    1650             :         }
    1651         898 :         if (!is_redundant)
    1652         744 :             distribute_restrictinfo_to_rels(root, rinfo);
    1653             :     }
    1654        1176 : }
    1655             : 
    1656             : /*
    1657             :  * Remove a relation after we have proven that it participates only in an
    1658             :  * unneeded unique self-join.
    1659             :  *
    1660             :  * Replace any links in planner info structures.
    1661             :  *
    1662             :  * Transfer join and restriction clauses from the removed relation to the
    1663             :  * remaining one. We change the Vars of the clause to point to the
    1664             :  * remaining relation instead of the removed one. The clauses that require
    1665             :  * a subset of joinrelids become restriction clauses of the remaining
    1666             :  * relation, and others remain join clauses. We append them to
    1667             :  * baserestrictinfo and joininfo, respectively, trying not to introduce
    1668             :  * duplicates.
    1669             :  *
    1670             :  * We also have to process the 'joinclauses' list here, because it
    1671             :  * contains EC-derived join clauses which must become filter clauses. It
    1672             :  * is not enough to just correct the ECs because the EC-derived
    1673             :  * restrictions are generated before join removal (see
    1674             :  * generate_base_implied_equalities).
    1675             :  *
    1676             :  * NOTE: Remember to keep the code in sync with PlannerInfo to be sure all
    1677             :  * cached relids and relid bitmapsets can be correctly cleaned during the
    1678             :  * self-join elimination procedure.
    1679             :  */
    1680             : static void
    1681         588 : remove_self_join_rel(PlannerInfo *root, PlanRowMark *kmark, PlanRowMark *rmark,
    1682             :                      RelOptInfo *toKeep, RelOptInfo *toRemove,
    1683             :                      List *restrictlist)
    1684             : {
    1685             :     List       *joininfos;
    1686             :     ListCell   *lc;
    1687             :     int         i;
    1688         588 :     List       *jinfo_candidates = NIL;
    1689         588 :     List       *binfo_candidates = NIL;
    1690             : 
    1691             :     Assert(toKeep->relid > 0);
    1692             :     Assert(toRemove->relid > 0);
    1693             : 
    1694             :     /*
    1695             :      * Replace the index of the removing table with the keeping one. The
    1696             :      * technique of removing/distributing restrictinfo is used here to attach
    1697             :      * just appeared (for keeping relation) join clauses and avoid adding
    1698             :      * duplicates of those that already exist in the joininfo list.
    1699             :      */
    1700         588 :     joininfos = list_copy(toRemove->joininfo);
    1701        1254 :     foreach_node(RestrictInfo, rinfo, joininfos)
    1702             :     {
    1703          78 :         remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
    1704          78 :         ChangeVarNodes((Node *) rinfo, toRemove->relid, toKeep->relid, 0);
    1705             : 
    1706          78 :         if (bms_membership(rinfo->required_relids) == BMS_MULTIPLE)
    1707          60 :             jinfo_candidates = lappend(jinfo_candidates, rinfo);
    1708             :         else
    1709          18 :             binfo_candidates = lappend(binfo_candidates, rinfo);
    1710             :     }
    1711             : 
    1712             :     /*
    1713             :      * Concatenate restrictlist to the list of base restrictions of the
    1714             :      * removing table just to simplify the replacement procedure: all of them
    1715             :      * weren't connected to any keeping relations and need to be added to some
    1716             :      * rels.
    1717             :      */
    1718         588 :     toRemove->baserestrictinfo = list_concat(toRemove->baserestrictinfo,
    1719             :                                              restrictlist);
    1720        1996 :     foreach_node(RestrictInfo, rinfo, toRemove->baserestrictinfo)
    1721             :     {
    1722         820 :         ChangeVarNodes((Node *) rinfo, toRemove->relid, toKeep->relid, 0);
    1723             : 
    1724         820 :         if (bms_membership(rinfo->required_relids) == BMS_MULTIPLE)
    1725           0 :             jinfo_candidates = lappend(jinfo_candidates, rinfo);
    1726             :         else
    1727         820 :             binfo_candidates = lappend(binfo_candidates, rinfo);
    1728             :     }
    1729             : 
    1730             :     /*
    1731             :      * Now, add all non-redundant clauses to the keeping relation.
    1732             :      */
    1733         588 :     add_non_redundant_clauses(root, binfo_candidates,
    1734             :                               &toKeep->baserestrictinfo, toRemove->relid);
    1735         588 :     add_non_redundant_clauses(root, jinfo_candidates,
    1736             :                               &toKeep->joininfo, toRemove->relid);
    1737             : 
    1738         588 :     list_free(binfo_candidates);
    1739         588 :     list_free(jinfo_candidates);
    1740             : 
    1741             :     /*
    1742             :      * Arrange equivalence classes, mentioned removing a table, with the
    1743             :      * keeping one: varno of removing table should be replaced in members and
    1744             :      * sources lists. Also, remove duplicated elements if this replacement
    1745             :      * procedure created them.
    1746             :      */
    1747         588 :     i = -1;
    1748        1488 :     while ((i = bms_next_member(toRemove->eclass_indexes, i)) >= 0)
    1749             :     {
    1750         900 :         EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
    1751             : 
    1752         900 :         update_eclasses(ec, toRemove->relid, toKeep->relid);
    1753         900 :         toKeep->eclass_indexes = bms_add_member(toKeep->eclass_indexes, i);
    1754             :     }
    1755             : 
    1756             :     /*
    1757             :      * Transfer the targetlist and attr_needed flags.
    1758             :      */
    1759             : 
    1760        2360 :     foreach(lc, toRemove->reltarget->exprs)
    1761             :     {
    1762        1772 :         Node       *node = lfirst(lc);
    1763             : 
    1764        1772 :         ChangeVarNodes(node, toRemove->relid, toKeep->relid, 0);
    1765        1772 :         if (!list_member(toKeep->reltarget->exprs, node))
    1766         174 :             toKeep->reltarget->exprs = lappend(toKeep->reltarget->exprs, node);
    1767             :     }
    1768             : 
    1769        7470 :     for (i = toKeep->min_attr; i <= toKeep->max_attr; i++)
    1770             :     {
    1771        6882 :         int         attno = i - toKeep->min_attr;
    1772             : 
    1773       13764 :         toRemove->attr_needed[attno] = adjust_relid_set(toRemove->attr_needed[attno],
    1774        6882 :                                                         toRemove->relid, toKeep->relid);
    1775        6882 :         toKeep->attr_needed[attno] = bms_add_members(toKeep->attr_needed[attno],
    1776        6882 :                                                      toRemove->attr_needed[attno]);
    1777             :     }
    1778             : 
    1779             :     /*
    1780             :      * If the removed relation has a row mark, transfer it to the remaining
    1781             :      * one.
    1782             :      *
    1783             :      * If both rels have row marks, just keep the one corresponding to the
    1784             :      * remaining relation because we verified earlier that they have the same
    1785             :      * strength.
    1786             :      */
    1787         588 :     if (rmark)
    1788             :     {
    1789          74 :         if (kmark)
    1790             :         {
    1791             :             Assert(kmark->markType == rmark->markType);
    1792             : 
    1793          74 :             root->rowMarks = list_delete_ptr(root->rowMarks, rmark);
    1794             :         }
    1795             :         else
    1796             :         {
    1797             :             /* Shouldn't have inheritance children here. */
    1798             :             Assert(rmark->rti == rmark->prti);
    1799             : 
    1800           0 :             rmark->rti = rmark->prti = toKeep->relid;
    1801             :         }
    1802             :     }
    1803             : 
    1804             :     /*
    1805             :      * Replace varno in all the query structures, except nodes RangeTblRef
    1806             :      * otherwise later remove_rel_from_joinlist will yield errors.
    1807             :      */
    1808         588 :     ChangeVarNodesExtended((Node *) root->parse, toRemove->relid, toKeep->relid, 0, false);
    1809             : 
    1810             :     /* Replace links in the planner info */
    1811         588 :     remove_rel_from_query(root, toRemove, toKeep->relid, NULL, NULL);
    1812             : 
    1813             :     /* At last, replace varno in root targetlist and HAVING clause */
    1814         588 :     ChangeVarNodes((Node *) root->processed_tlist, toRemove->relid, toKeep->relid, 0);
    1815         588 :     ChangeVarNodes((Node *) root->processed_groupClause, toRemove->relid, toKeep->relid, 0);
    1816             : 
    1817         588 :     adjust_relid_set(root->all_result_relids, toRemove->relid, toKeep->relid);
    1818         588 :     adjust_relid_set(root->leaf_result_relids, toRemove->relid, toKeep->relid);
    1819             : 
    1820             :     /*
    1821             :      * There may be references to the rel in root->fkey_list, but if so,
    1822             :      * match_foreign_keys_to_quals() will get rid of them.
    1823             :      */
    1824             : 
    1825             :     /*
    1826             :      * Finally, remove the rel from the baserel array to prevent it from being
    1827             :      * referenced again.  (We can't do this earlier because
    1828             :      * remove_join_clause_from_rels will touch it.)
    1829             :      */
    1830         588 :     root->simple_rel_array[toRemove->relid] = NULL;
    1831             : 
    1832             :     /* And nuke the RelOptInfo, just in case there's another access path. */
    1833         588 :     pfree(toRemove);
    1834             : 
    1835             :     /*
    1836             :      * Now repeat construction of attr_needed bits coming from all other
    1837             :      * sources.
    1838             :      */
    1839         588 :     rebuild_placeholder_attr_needed(root);
    1840         588 :     rebuild_joinclause_attr_needed(root);
    1841         588 :     rebuild_eclass_attr_needed(root);
    1842         588 :     rebuild_lateral_attr_needed(root);
    1843         588 : }
    1844             : 
    1845             : /*
    1846             :  * split_selfjoin_quals
    1847             :  *      Processes 'joinquals' by building two lists: one containing the quals
    1848             :  *      where the columns/exprs are on either side of the join match and
    1849             :  *      another one containing the remaining quals.
    1850             :  *
    1851             :  * 'joinquals' must only contain quals for a RTE_RELATION being joined to
    1852             :  * itself.
    1853             :  */
    1854             : static void
    1855        1976 : split_selfjoin_quals(PlannerInfo *root, List *joinquals, List **selfjoinquals,
    1856             :                      List **otherjoinquals, int from, int to)
    1857             : {
    1858        1976 :     List       *sjoinquals = NIL;
    1859        1976 :     List       *ojoinquals = NIL;
    1860             : 
    1861        6062 :     foreach_node(RestrictInfo, rinfo, joinquals)
    1862             :     {
    1863             :         OpExpr     *expr;
    1864             :         Node       *leftexpr;
    1865             :         Node       *rightexpr;
    1866             : 
    1867             :         /* In general, clause looks like F(arg1) = G(arg2) */
    1868        4220 :         if (!rinfo->mergeopfamilies ||
    1869        4220 :             bms_num_members(rinfo->clause_relids) != 2 ||
    1870        4220 :             bms_membership(rinfo->left_relids) != BMS_SINGLETON ||
    1871        2110 :             bms_membership(rinfo->right_relids) != BMS_SINGLETON)
    1872             :         {
    1873           0 :             ojoinquals = lappend(ojoinquals, rinfo);
    1874           0 :             continue;
    1875             :         }
    1876             : 
    1877        2110 :         expr = (OpExpr *) rinfo->clause;
    1878             : 
    1879        2110 :         if (!IsA(expr, OpExpr) || list_length(expr->args) != 2)
    1880             :         {
    1881           0 :             ojoinquals = lappend(ojoinquals, rinfo);
    1882           0 :             continue;
    1883             :         }
    1884             : 
    1885        2110 :         leftexpr = get_leftop(rinfo->clause);
    1886        2110 :         rightexpr = copyObject(get_rightop(rinfo->clause));
    1887             : 
    1888        2110 :         if (leftexpr && IsA(leftexpr, RelabelType))
    1889          12 :             leftexpr = (Node *) ((RelabelType *) leftexpr)->arg;
    1890        2110 :         if (rightexpr && IsA(rightexpr, RelabelType))
    1891           6 :             rightexpr = (Node *) ((RelabelType *) rightexpr)->arg;
    1892             : 
    1893             :         /*
    1894             :          * Quite an expensive operation, narrowing the use case. For example,
    1895             :          * when we have cast of the same var to different (but compatible)
    1896             :          * types.
    1897             :          */
    1898        2110 :         ChangeVarNodes(rightexpr, bms_singleton_member(rinfo->right_relids),
    1899        2110 :                        bms_singleton_member(rinfo->left_relids), 0);
    1900             : 
    1901        2110 :         if (equal(leftexpr, rightexpr))
    1902        1624 :             sjoinquals = lappend(sjoinquals, rinfo);
    1903             :         else
    1904         486 :             ojoinquals = lappend(ojoinquals, rinfo);
    1905             :     }
    1906             : 
    1907        1976 :     *selfjoinquals = sjoinquals;
    1908        1976 :     *otherjoinquals = ojoinquals;
    1909        1976 : }
    1910             : 
    1911             : /*
    1912             :  * Check for a case when uniqueness is at least partly derived from a
    1913             :  * baserestrictinfo clause. In this case, we have a chance to return only
    1914             :  * one row (if such clauses on both sides of SJ are equal) or nothing (if they
    1915             :  * are different).
    1916             :  */
    1917             : static bool
    1918         654 : match_unique_clauses(PlannerInfo *root, RelOptInfo *outer, List *uclauses,
    1919             :                      Index relid)
    1920             : {
    1921        1326 :     foreach_node(RestrictInfo, rinfo, uclauses)
    1922             :     {
    1923             :         Expr       *clause;
    1924             :         Node       *iclause;
    1925             :         Node       *c1;
    1926         150 :         bool        matched = false;
    1927             : 
    1928             :         Assert(outer->relid > 0 && relid > 0);
    1929             : 
    1930             :         /* Only filters like f(R.x1,...,R.xN) == expr we should consider. */
    1931             :         Assert(bms_is_empty(rinfo->left_relids) ^
    1932             :                bms_is_empty(rinfo->right_relids));
    1933             : 
    1934         150 :         clause = (Expr *) copyObject(rinfo->clause);
    1935         150 :         ChangeVarNodes((Node *) clause, relid, outer->relid, 0);
    1936             : 
    1937         150 :         iclause = bms_is_empty(rinfo->left_relids) ? get_rightop(clause) :
    1938         144 :             get_leftop(clause);
    1939         150 :         c1 = bms_is_empty(rinfo->left_relids) ? get_leftop(clause) :
    1940         144 :             get_rightop(clause);
    1941             : 
    1942             :         /*
    1943             :          * Compare these left and right sides with the corresponding sides of
    1944             :          * the outer's filters. If no one is detected - return immediately.
    1945             :          */
    1946         408 :         foreach_node(RestrictInfo, orinfo, outer->baserestrictinfo)
    1947             :         {
    1948             :             Node       *oclause;
    1949             :             Node       *c2;
    1950             : 
    1951         192 :             if (orinfo->mergeopfamilies == NIL)
    1952             :                 /* Don't consider clauses that aren't similar to 'F(X)=G(Y)' */
    1953          60 :                 continue;
    1954             : 
    1955             :             Assert(is_opclause(orinfo->clause));
    1956             : 
    1957         264 :             oclause = bms_is_empty(orinfo->left_relids) ?
    1958         132 :                 get_rightop(orinfo->clause) : get_leftop(orinfo->clause);
    1959         264 :             c2 = (bms_is_empty(orinfo->left_relids) ?
    1960         132 :                   get_leftop(orinfo->clause) : get_rightop(orinfo->clause));
    1961             : 
    1962         132 :             if (equal(iclause, oclause) && equal(c1, c2))
    1963             :             {
    1964          84 :                 matched = true;
    1965          84 :                 break;
    1966             :             }
    1967             :         }
    1968             : 
    1969         150 :         if (!matched)
    1970          66 :             return false;
    1971             :     }
    1972             : 
    1973         588 :     return true;
    1974             : }
    1975             : 
    1976             : /*
    1977             :  * Find and remove unique self-joins in a group of base relations that have
    1978             :  * the same Oid.
    1979             :  *
    1980             :  * Returns a set of relids that were removed.
    1981             :  */
    1982             : static Relids
    1983       10788 : remove_self_joins_one_group(PlannerInfo *root, Relids relids)
    1984             : {
    1985       10788 :     Relids      result = NULL;
    1986             :     int         k;              /* Index of kept relation */
    1987       10788 :     int         r = -1;         /* Index of removed relation */
    1988             : 
    1989       33524 :     while ((r = bms_next_member(relids, r)) > 0)
    1990             :     {
    1991       22736 :         RelOptInfo *inner = root->simple_rel_array[r];
    1992             : 
    1993       22736 :         k = r;
    1994             : 
    1995       35468 :         while ((k = bms_next_member(relids, k)) > 0)
    1996             :         {
    1997       13320 :             Relids      joinrelids = NULL;
    1998       13320 :             RelOptInfo *outer = root->simple_rel_array[k];
    1999             :             List       *restrictlist;
    2000             :             List       *selfjoinquals;
    2001             :             List       *otherjoinquals;
    2002             :             ListCell   *lc;
    2003       13320 :             bool        jinfo_check = true;
    2004       13320 :             PlanRowMark *omark = NULL;
    2005       13320 :             PlanRowMark *imark = NULL;
    2006       13320 :             List       *uclauses = NIL;
    2007             : 
    2008             :             /* A sanity check: the relations have the same Oid. */
    2009             :             Assert(root->simple_rte_array[k]->relid ==
    2010             :                    root->simple_rte_array[r]->relid);
    2011             : 
    2012             :             /*
    2013             :              * It is impossible to eliminate the join of two relations if they
    2014             :              * belong to different rules of order. Otherwise, the planner
    2015             :              * can't find any variants of the correct query plan.
    2016             :              */
    2017       16470 :             foreach(lc, root->join_info_list)
    2018             :             {
    2019       10526 :                 SpecialJoinInfo *info = (SpecialJoinInfo *) lfirst(lc);
    2020             : 
    2021       21052 :                 if ((bms_is_member(k, info->syn_lefthand) ^
    2022       14942 :                      bms_is_member(r, info->syn_lefthand)) ||
    2023        4416 :                     (bms_is_member(k, info->syn_righthand) ^
    2024        4416 :                      bms_is_member(r, info->syn_righthand)))
    2025             :                 {
    2026        7376 :                     jinfo_check = false;
    2027        7376 :                     break;
    2028             :                 }
    2029             :             }
    2030       13320 :             if (!jinfo_check)
    2031       12732 :                 continue;
    2032             : 
    2033             :             /*
    2034             :              * Check Row Marks equivalence. We can't remove the join if the
    2035             :              * relations have row marks of different strength (e.g., one is
    2036             :              * locked FOR UPDATE, and another just has ROW_MARK_REFERENCE for
    2037             :              * EvalPlanQual rechecking).
    2038             :              */
    2039        6152 :             foreach(lc, root->rowMarks)
    2040             :             {
    2041         380 :                 PlanRowMark *rowMark = (PlanRowMark *) lfirst(lc);
    2042             : 
    2043         380 :                 if (rowMark->rti == k)
    2044             :                 {
    2045             :                     Assert(imark == NULL);
    2046         172 :                     imark = rowMark;
    2047             :                 }
    2048         208 :                 else if (rowMark->rti == r)
    2049             :                 {
    2050             :                     Assert(omark == NULL);
    2051         172 :                     omark = rowMark;
    2052             :                 }
    2053             : 
    2054         380 :                 if (omark && imark)
    2055         172 :                     break;
    2056             :             }
    2057        5944 :             if (omark && imark && omark->markType != imark->markType)
    2058          52 :                 continue;
    2059             : 
    2060             :             /*
    2061             :              * We only deal with base rels here, so their relids bitset
    2062             :              * contains only one member -- their relid.
    2063             :              */
    2064        5892 :             joinrelids = bms_add_member(joinrelids, r);
    2065        5892 :             joinrelids = bms_add_member(joinrelids, k);
    2066             : 
    2067             :             /*
    2068             :              * PHVs should not impose any constraints on removing self-joins.
    2069             :              */
    2070             : 
    2071             :             /*
    2072             :              * At this stage, joininfo lists of inner and outer can contain
    2073             :              * only clauses required for a superior outer join that can't
    2074             :              * influence this optimization. So, we can avoid to call the
    2075             :              * build_joinrel_restrictlist() routine.
    2076             :              */
    2077        5892 :             restrictlist = generate_join_implied_equalities(root, joinrelids,
    2078             :                                                             inner->relids,
    2079             :                                                             outer, NULL);
    2080        5892 :             if (restrictlist == NIL)
    2081        3916 :                 continue;
    2082             : 
    2083             :             /*
    2084             :              * Process restrictlist to separate the self-join quals from the
    2085             :              * other quals. e.g., "x = x" goes to selfjoinquals and "a = b" to
    2086             :              * otherjoinquals.
    2087             :              */
    2088        1976 :             split_selfjoin_quals(root, restrictlist, &selfjoinquals,
    2089        1976 :                                  &otherjoinquals, inner->relid, outer->relid);
    2090             : 
    2091             :             Assert(list_length(restrictlist) ==
    2092             :                    (list_length(selfjoinquals) + list_length(otherjoinquals)));
    2093             : 
    2094             :             /*
    2095             :              * To enable SJE for the only degenerate case without any self
    2096             :              * join clauses at all, add baserestrictinfo to this list. The
    2097             :              * degenerate case works only if both sides have the same clause.
    2098             :              * So doesn't matter which side to add.
    2099             :              */
    2100        1976 :             selfjoinquals = list_concat(selfjoinquals, outer->baserestrictinfo);
    2101             : 
    2102             :             /*
    2103             :              * Determine if the inner table can duplicate outer rows.  We must
    2104             :              * bypass the unique rel cache here since we're possibly using a
    2105             :              * subset of join quals. We can use 'force_cache' == true when all
    2106             :              * join quals are self-join quals.  Otherwise, we could end up
    2107             :              * putting false negatives in the cache.
    2108             :              */
    2109        1976 :             if (!innerrel_is_unique_ext(root, joinrelids, inner->relids,
    2110             :                                         outer, JOIN_INNER, selfjoinquals,
    2111        1976 :                                         list_length(otherjoinquals) == 0,
    2112             :                                         &uclauses))
    2113        1322 :                 continue;
    2114             : 
    2115             :             /*
    2116             :              * 'uclauses' is the copy of outer->baserestrictinfo that are
    2117             :              * associated with an index.  We proved by matching selfjoinquals
    2118             :              * to a unique index that the outer relation has at most one
    2119             :              * matching row for each inner row.  Sometimes that is not enough.
    2120             :              * e.g. "WHERE s1.b = s2.b AND s1.a = 1 AND s2.a = 2" when the
    2121             :              * unique index is (a,b).  Having non-empty uclauses, we must
    2122             :              * validate that the inner baserestrictinfo contains the same
    2123             :              * expressions, or we won't match the same row on each side of the
    2124             :              * join.
    2125             :              */
    2126         654 :             if (!match_unique_clauses(root, inner, uclauses, outer->relid))
    2127          66 :                 continue;
    2128             : 
    2129             :             /*
    2130             :              * We can remove either relation, so remove the inner one in order
    2131             :              * to simplify this loop.
    2132             :              */
    2133         588 :             remove_self_join_rel(root, omark, imark, outer, inner, restrictlist);
    2134             : 
    2135         588 :             result = bms_add_member(result, r);
    2136             : 
    2137             :             /* We have removed the outer relation, try the next one. */
    2138         588 :             break;
    2139             :         }
    2140             :     }
    2141             : 
    2142       10788 :     return result;
    2143             : }
    2144             : 
    2145             : /*
    2146             :  * Gather indexes of base relations from the joinlist and try to eliminate self
    2147             :  * joins.
    2148             :  */
    2149             : static Relids
    2150       95934 : remove_self_joins_recurse(PlannerInfo *root, List *joinlist, Relids toRemove)
    2151             : {
    2152             :     ListCell   *jl;
    2153       95934 :     Relids      relids = NULL;
    2154       95934 :     SelfJoinCandidate *candidates = NULL;
    2155             :     int         i;
    2156             :     int         j;
    2157             :     int         numRels;
    2158             : 
    2159             :     /* Collect indexes of base relations of the join tree */
    2160      320622 :     foreach(jl, joinlist)
    2161             :     {
    2162      224688 :         Node       *jlnode = (Node *) lfirst(jl);
    2163             : 
    2164      224688 :         if (IsA(jlnode, RangeTblRef))
    2165             :         {
    2166      221322 :             int         varno = ((RangeTblRef *) jlnode)->rtindex;
    2167      221322 :             RangeTblEntry *rte = root->simple_rte_array[varno];
    2168             : 
    2169             :             /*
    2170             :              * We only consider ordinary relations as candidates to be
    2171             :              * removed, and these relations should not have TABLESAMPLE
    2172             :              * clauses specified.  Removing a relation with TABLESAMPLE clause
    2173             :              * could potentially change the syntax of the query. Because of
    2174             :              * UPDATE/DELETE EPQ mechanism, currently Query->resultRelation or
    2175             :              * Query->mergeTargetRelation associated rel cannot be eliminated.
    2176             :              */
    2177      221322 :             if (rte->rtekind == RTE_RELATION &&
    2178      194984 :                 rte->relkind == RELKIND_RELATION &&
    2179      189802 :                 rte->tablesample == NULL &&
    2180      189778 :                 varno != root->parse->resultRelation &&
    2181      188006 :                 varno != root->parse->mergeTargetRelation)
    2182             :             {
    2183             :                 Assert(!bms_is_member(varno, relids));
    2184      188006 :                 relids = bms_add_member(relids, varno);
    2185             :             }
    2186             :         }
    2187        3366 :         else if (IsA(jlnode, List))
    2188             :         {
    2189             :             /* Recursively go inside the sub-joinlist */
    2190        3366 :             toRemove = remove_self_joins_recurse(root, (List *) jlnode,
    2191             :                                                  toRemove);
    2192             :         }
    2193             :         else
    2194           0 :             elog(ERROR, "unrecognized joinlist node type: %d",
    2195             :                  (int) nodeTag(jlnode));
    2196             :     }
    2197             : 
    2198       95934 :     numRels = bms_num_members(relids);
    2199             : 
    2200             :     /* Need at least two relations for the join */
    2201       95934 :     if (numRels < 2)
    2202       26946 :         return toRemove;
    2203             : 
    2204             :     /*
    2205             :      * In order to find relations with the same oid we first build an array of
    2206             :      * candidates and then sort it by oid.
    2207             :      */
    2208       68988 :     candidates = (SelfJoinCandidate *) palloc(sizeof(SelfJoinCandidate) *
    2209             :                                               numRels);
    2210       68988 :     i = -1;
    2211       68988 :     j = 0;
    2212      238030 :     while ((i = bms_next_member(relids, i)) >= 0)
    2213             :     {
    2214      169042 :         candidates[j].relid = i;
    2215      169042 :         candidates[j].reloid = root->simple_rte_array[i]->relid;
    2216      169042 :         j++;
    2217             :     }
    2218             : 
    2219       68988 :     qsort(candidates, numRels, sizeof(SelfJoinCandidate),
    2220             :           self_join_candidates_cmp);
    2221             : 
    2222             :     /*
    2223             :      * Iteratively form a group of relation indexes with the same oid and
    2224             :      * launch the routine that detects self-joins in this group and removes
    2225             :      * excessive range table entries.
    2226             :      *
    2227             :      * At the end of the iteration, exclude the group from the overall relids
    2228             :      * list. So each next iteration of the cycle will involve less and less
    2229             :      * value of relids.
    2230             :      */
    2231       68988 :     i = 0;
    2232      238030 :     for (j = 1; j < numRels + 1; j++)
    2233             :     {
    2234      169042 :         if (j == numRels || candidates[j].reloid != candidates[i].reloid)
    2235             :         {
    2236      157166 :             if (j - i >= 2)
    2237             :             {
    2238             :                 /* Create a group of relation indexes with the same oid */
    2239       10722 :                 Relids      group = NULL;
    2240             :                 Relids      removed;
    2241             : 
    2242       33320 :                 while (i < j)
    2243             :                 {
    2244       22598 :                     group = bms_add_member(group, candidates[i].relid);
    2245       22598 :                     i++;
    2246             :                 }
    2247       10722 :                 relids = bms_del_members(relids, group);
    2248             : 
    2249             :                 /*
    2250             :                  * Try to remove self-joins from a group of identical entries.
    2251             :                  * Make the next attempt iteratively - if something is deleted
    2252             :                  * from a group, changes in clauses and equivalence classes
    2253             :                  * can give us a chance to find more candidates.
    2254             :                  */
    2255             :                 do
    2256             :                 {
    2257             :                     Assert(!bms_overlap(group, toRemove));
    2258       10788 :                     removed = remove_self_joins_one_group(root, group);
    2259       10788 :                     toRemove = bms_add_members(toRemove, removed);
    2260       10788 :                     group = bms_del_members(group, removed);
    2261         564 :                 } while (!bms_is_empty(removed) &&
    2262       10788 :                          bms_membership(group) == BMS_MULTIPLE);
    2263       10722 :                 bms_free(removed);
    2264       10722 :                 bms_free(group);
    2265             :             }
    2266             :             else
    2267             :             {
    2268             :                 /* Single relation, just remove it from the set */
    2269      146444 :                 relids = bms_del_member(relids, candidates[i].relid);
    2270      146444 :                 i = j;
    2271             :             }
    2272             :         }
    2273             :     }
    2274             : 
    2275             :     Assert(bms_is_empty(relids));
    2276             : 
    2277       68988 :     return toRemove;
    2278             : }
    2279             : 
    2280             : /*
    2281             :  * Compare self-join candidates by their oids.
    2282             :  */
    2283             : static int
    2284      125212 : self_join_candidates_cmp(const void *a, const void *b)
    2285             : {
    2286      125212 :     const SelfJoinCandidate *ca = (const SelfJoinCandidate *) a;
    2287      125212 :     const SelfJoinCandidate *cb = (const SelfJoinCandidate *) b;
    2288             : 
    2289      125212 :     if (ca->reloid != cb->reloid)
    2290      113282 :         return (ca->reloid < cb->reloid ? -1 : 1);
    2291             :     else
    2292       11930 :         return 0;
    2293             : }
    2294             : 
    2295             : /*
    2296             :  * Find and remove useless self joins.
    2297             :  *
    2298             :  * Search for joins where a relation is joined to itself. If the join clause
    2299             :  * for each tuple from one side of the join is proven to match the same
    2300             :  * physical row (or nothing) on the other side, that self-join can be
    2301             :  * eliminated from the query.  Suitable join clauses are assumed to be in the
    2302             :  * form of X = X, and can be replaced with NOT NULL clauses.
    2303             :  *
    2304             :  * For the sake of simplicity, we don't apply this optimization to special
    2305             :  * joins. Here is a list of what we could do in some particular cases:
    2306             :  * 'a a1 semi join a a2': is reduced to inner by reduce_unique_semijoins,
    2307             :  * and then removed normally.
    2308             :  * 'a a1 anti join a a2': could simplify to a scan with 'outer quals AND
    2309             :  * (IS NULL on join columns OR NOT inner quals)'.
    2310             :  * 'a a1 left join a a2': could simplify to a scan like inner but without
    2311             :  * NOT NULL conditions on join columns.
    2312             :  * 'a a1 left join (a a2 join b)': can't simplify this, because join to b
    2313             :  * can both remove rows and introduce duplicates.
    2314             :  *
    2315             :  * To search for removable joins, we order all the relations on their Oid,
    2316             :  * go over each set with the same Oid, and consider each pair of relations
    2317             :  * in this set.
    2318             :  *
    2319             :  * To remove the join, we mark one of the participating relations as dead
    2320             :  * and rewrite all references to it to point to the remaining relation.
    2321             :  * This includes modifying RestrictInfos, EquivalenceClasses, and
    2322             :  * EquivalenceMembers. We also have to modify the row marks. The join clauses
    2323             :  * of the removed relation become either restriction or join clauses, based on
    2324             :  * whether they reference any relations not participating in the removed join.
    2325             :  *
    2326             :  * 'joinlist' is the top-level joinlist of the query. If it has any
    2327             :  * references to the removed relations, we update them to point to the
    2328             :  * remaining ones.
    2329             :  */
    2330             : List *
    2331      314632 : remove_useless_self_joins(PlannerInfo *root, List *joinlist)
    2332             : {
    2333      314632 :     Relids      toRemove = NULL;
    2334      314632 :     int         relid = -1;
    2335             : 
    2336      629264 :     if (!enable_self_join_elimination || joinlist == NIL ||
    2337      537564 :         (list_length(joinlist) == 1 && !IsA(linitial(joinlist), List)))
    2338      222064 :         return joinlist;
    2339             : 
    2340             :     /*
    2341             :      * Merge pairs of relations participated in self-join. Remove unnecessary
    2342             :      * range table entries.
    2343             :      */
    2344       92568 :     toRemove = remove_self_joins_recurse(root, joinlist, toRemove);
    2345             : 
    2346       92568 :     if (unlikely(toRemove != NULL))
    2347             :     {
    2348             :         /* At the end, remove orphaned relation links */
    2349        1146 :         while ((relid = bms_next_member(toRemove, relid)) >= 0)
    2350             :         {
    2351         588 :             int         nremoved = 0;
    2352             : 
    2353         588 :             joinlist = remove_rel_from_joinlist(joinlist, relid, &nremoved);
    2354         588 :             if (nremoved != 1)
    2355           0 :                 elog(ERROR, "failed to find relation %d in joinlist", relid);
    2356             :         }
    2357             :     }
    2358             : 
    2359       92568 :     return joinlist;
    2360             : }

Generated by: LCOV version 1.14