SSL analyzejoins.c

/*-------------------------------------------------------------------------
 *
 * analyzejoins.c
 *   Routines for simplifying joins after initial query analysis
 *
 * While we do a great deal of join simplification in prep/prepjointree.c,
 * certain optimizations cannot be performed at that stage for lack of
 * detailed information about the query.  The routines here are invoked
 * after initsplan.c has done its work, and can do additional join removal
 * and simplification steps based on the information extracted.  The penalty
 * is that we have to work harder to clean up after ourselves when we modify
 * the query, since the derived data structures have to be updated too.
 *
 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *   src/backend/optimizer/plan/analyzejoins.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "catalog/pg_class.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/joininfo.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/placeholder.h"
#include "optimizer/planmain.h"
#include "optimizer/restrictinfo.h"
#include "rewrite/rewriteManip.h"
#include "utils/lsyscache.h"

/*
 * One element of the list passed to query_is_distinct_for_with_collations().
 * Each entry names a subquery output column that the caller needs to be
 * distinct over, plus the upper-level equality operator and its input
 * collation, so that the subquery's own DISTINCT/GROUP BY/set-op clauses can
 * be compared for compatibility.
 */
typedef struct DistinctColInfo
{
 int   colno;   /* subquery output column resno */
 Oid   opid;   /* upper-level equality operator */
 Oid   collid;   /* input collation of opid */
} DistinctColInfo;

/*
 * Utility structure.  A sorting procedure is needed to simplify the search
 * of SJE-candidate baserels referencing the same database relation.  Having
 * collected all baserels from the query jointree, the planner sorts them
 * according to the reloid value, groups them with the next pass and attempts
 * to remove self-joins.
 *
 * Preliminary sorting prevents quadratic behavior that can be harmful in the
 * case of numerous joins.
 */
typedef struct
{
 int   relid;
 Oid   reloid;
} SelfJoinCandidate;

bool  enable_self_join_elimination;

/* local functions */
static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
static void remove_leftjoinrel_from_query(PlannerInfo *root, int relid,
            SpecialJoinInfo *sjinfo);
static void remove_rel_from_restrictinfo(RestrictInfo *rinfo,
           int relid, int ojrelid);
static void remove_rel_from_eclass(EquivalenceClass *ec,
           SpecialJoinInfo *sjinfo,
           int relid, int subst);
static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel);
static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel,
        List *clause_list, List **extra_clauses);
static bool query_is_distinct_for_with_collations(Query *query,
              List *distinct_cols);
static DistinctColInfo *distinct_col_search(int colno, List *distinct_cols);
static bool is_innerrel_unique_for(PlannerInfo *root,
           Relids joinrelids,
           Relids outerrelids,
           RelOptInfo *innerrel,
           JoinType jointype,
           List *restrictlist,
           List **extra_clauses);
static int self_join_candidates_cmp(const void *a, const void *b);
static bool replace_relid_callback(Node *node,
           ChangeVarNodes_context *context);


/*
 * remove_useless_joins
 *  Check for relations that don't actually need to be joined at all,
 *  and remove them from the query.
 *
 * We are passed the current joinlist and return the updated list.  Other
 * data structures that have to be updated are accessible via "root".
 */
List *
remove_useless_joins(PlannerInfo *root, List *joinlist)
{
 ListCell   *lc;

 /*
  * We are only interested in relations that are left-joined to, so we can
  * scan the join_info_list to find them easily.
 */
restart:
 foreach(lc, root->join_info_list)
 {
  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
  int   innerrelid;
  int   nremoved;

  /* Skip if not removable */
  if (!join_is_removable(root, sjinfo))
   continue;

  /*
   * Currently, join_is_removable can only succeed when the sjinfo's
   * righthand is a single baserel.  Remove that rel from the query and
   * joinlist.
 */
  innerrelid = bms_singleton_member(sjinfo->min_righthand);

  remove_leftjoinrel_from_query(root, innerrelid, sjinfo);

  /* We verify that exactly one reference gets removed from joinlist */
  nremoved = 0;
  joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
  if (nremoved != 1)
   elog(ERROR, "failed to find relation %d in joinlist", innerrelid);

  /*
   * We can delete this SpecialJoinInfo from the list too, since it's no
   * longer of interest.  (Since we'll restart the foreach loop
   * immediately, we don't bother with foreach_delete_current.)
 */
  root->join_info_list = list_delete_cell(root->join_info_list, lc);

  /*
   * Restart the scan.  This is necessary to ensure we find all
   * removable joins independently of ordering of the join_info_list
   * (note that removal of attr_needed bits may make a join appear
   * removable that did not before).
 */
  goto restart;
 }

 return joinlist;
}

/*
 * join_is_removable
 *   Check whether we need not perform this special join at all, because
 *   it will just duplicate its left input.
 *
 * This is true for a left join for which the join condition cannot match
 * more than one inner-side row.  (There are other possibly interesting
 * cases, but we don't have the infrastructure to prove them.)  We also
 * have to check that the inner side doesn't generate any variables needed
 * above the join.
 */
static bool
join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
{
 int   innerrelid;
 RelOptInfo *innerrel;
 Relids  inputrelids;
 Relids  joinrelids;
 List    *clause_list = NIL;
 ListCell   *l;
 int   attroff;

 /*
  * Must be a left join to a single baserel, else we aren't going to be
  * able to do anything with it.
 */
 if (sjinfo->jointype != JOIN_LEFT)
  return false;

 if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
  return false;

 /*
  * Never try to eliminate a left join to the query result rel.  Although
  * the case is syntactically impossible in standard SQL, MERGE will build
  * a join tree that looks exactly like that.
 */
 if (innerrelid == root->parse->resultRelation)
  return false;

 innerrel = find_base_rel(root, innerrelid);

 /*
  * Before we go to the effort of checking whether any innerrel variables
  * are needed above the join, make a quick check to eliminate cases in
  * which we will surely be unable to prove uniqueness of the innerrel.
 */
 if (!rel_supports_distinctness(root, innerrel))
  return false;

 /* Compute the relid set for the join we are considering */
 inputrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
 Assert(sjinfo->ojrelid != 0);
 joinrelids = bms_copy(inputrelids);
 joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid);

 /*
  * We can't remove the join if any inner-rel attributes are used above the
  * join.  Here, "above" the join includes pushed-down conditions, so we
  * should reject if attr_needed includes the OJ's own relid; therefore,
  * compare to inputrelids not joinrelids.
  *
  * As a micro-optimization, it seems better to start with max_attr and
  * count down rather than starting with min_attr and counting up, on the
  * theory that the system attributes are somewhat less likely to be wanted
  * and should be tested last.
 */
 for (attroff = innerrel->max_attr - innerrel->min_attr;
   attroff >= 0;
   attroff--)
 {
  if (!bms_is_subset(innerrel->attr_needed[attroff], inputrelids))
   return false;
 }

 /*
  * Similarly check that the inner rel isn't needed by any PlaceHolderVars
  * that will be used above the join.  The PHV case is a little bit more
  * complicated, because PHVs may have been assigned a ph_eval_at location
  * that includes the innerrel, yet their contained expression might not
  * actually reference the innerrel (it could be just a constant, for
  * instance).  If such a PHV is due to be evaluated above the join then it
  * needn't prevent join removal.
 */
 foreach(l, root->placeholder_list)
 {
  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);

  if (bms_overlap(phinfo->ph_lateral, innerrel->relids))
   return false;  /* it references innerrel laterally */
  if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
   continue;   /* it definitely doesn't reference innerrel */
  if (bms_is_subset(phinfo->ph_needed, inputrelids))
   continue;   /* PHV is not used above the join */
  if (!bms_is_member(sjinfo->ojrelid, phinfo->ph_eval_at))
   return false;  /* it has to be evaluated below the join */

  /*
   * We need to be sure there will still be a place to evaluate the PHV
   * if we remove the join, ie that ph_eval_at wouldn't become empty.
 */
  if (!bms_overlap(sjinfo->min_lefthand, phinfo->ph_eval_at))
   return false;  /* there isn't any other place to eval PHV */
  /* Check contained expression last, since this is a bit expensive */
  if (bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),
      innerrel->relids))
   return false;  /* contained expression references innerrel */
 }

 /*
  * Search for mergejoinable clauses that constrain the inner rel against
  * either the outer rel or a pseudoconstant.  If an operator is
  * mergejoinable then it behaves like equality for some btree opclass, so
  * it's what we want.  The mergejoinability test also eliminates clauses
  * containing volatile functions, which we couldn't depend on.
 */
 foreach(l, innerrel->joininfo)
 {
  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);

  /*
   * If the current join commutes with some other outer join(s) via
   * outer join identity 3, there will be multiple clones of its join
   * clauses in the joininfo list.  We want to consider only the
   * has_clone form of such clauses.  Processing more than one form
   * would be wasteful, and also some of the others would confuse the
   * RINFO_IS_PUSHED_DOWN test below.
 */
  if (restrictinfo->is_clone)
   continue;   /* ignore it */

  /*
   * If it's not a join clause for this outer join, we can't use it.
   * Note that if the clause is pushed-down, then it is logically from
   * above the outer join, even if it references no other rels (it might
   * be from WHERE, for example).
 */
  if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
   continue;   /* ignore; not useful here */

  /* Ignore if it's not a mergejoinable clause */
  if (!restrictinfo->can_join ||
   restrictinfo->mergeopfamilies == NIL)
   continue;   /* not mergejoinable */

  /*
   * Check if the clause has the form "outer op inner" or "inner op
   * outer", and if so mark which side is inner.
 */
  if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
          innerrel->relids))
   continue;   /* no good for these input relations */

  /* OK, add to list */
  clause_list = lappend(clause_list, restrictinfo);
 }

 /*
  * Now that we have the relevant equality join clauses, try to prove the
  * innerrel distinct.
 */
 if (rel_is_distinct_for(root, innerrel, clause_list, NULL))
  return true;

 /*
  * Some day it would be nice to check for other methods of establishing
  * distinctness.
 */
 return false;
}


/*
 * Remove the target rel->relid and references to the target join from the
 * planner's data structures, having determined that there is no need
 * to include them in the query. Optionally replace them with subst if subst
 * is non-negative.
 *
 * This function updates only parts needed for both left-join removal and
 * self-join removal.
 */
static void
remove_rel_from_query(PlannerInfo *root, RelOptInfo *rel,
       int subst, SpecialJoinInfo *sjinfo,
       Relids joinrelids)
{
 int   relid = rel->relid;
 Index  rti;
 ListCell   *l;

 /*
  * Update all_baserels and related relid sets.
 */
 root->all_baserels = adjust_relid_set(root->all_baserels, relid, subst);
 root->all_query_rels = adjust_relid_set(root->all_query_rels, relid, subst);

 if (sjinfo != NULL)
 {
  root->outer_join_rels = bms_del_member(root->outer_join_rels,
              sjinfo->ojrelid);
  root->all_query_rels = bms_del_member(root->all_query_rels,
             sjinfo->ojrelid);
 }

 /*
  * Likewise remove references from SpecialJoinInfo data structures.
  *
  * This is relevant in case the outer join we're deleting is nested inside
  * other outer joins: the upper joins' relid sets have to be adjusted. The
  * RHS of the target outer join will be made empty here, but that's OK
  * since caller will delete that SpecialJoinInfo entirely.
 */
 foreach(l, root->join_info_list)
 {
  SpecialJoinInfo *sjinf = (SpecialJoinInfo *) lfirst(l);

  /*
   * initsplan.c is fairly cavalier about allowing SpecialJoinInfos'
   * lefthand/righthand relid sets to be shared with other data
   * structures.  Ensure that we don't modify the original relid sets.
   * (The commute_xxx sets are always per-SpecialJoinInfo though.)
 */
  sjinf->min_lefthand = bms_copy(sjinf->min_lefthand);
  sjinf->min_righthand = bms_copy(sjinf->min_righthand);
  sjinf->syn_lefthand = bms_copy(sjinf->syn_lefthand);
  sjinf->syn_righthand = bms_copy(sjinf->syn_righthand);
  /* Now remove relid from the sets: */
  sjinf->min_lefthand = adjust_relid_set(sjinf->min_lefthand, relid, subst);
  sjinf->min_righthand = adjust_relid_set(sjinf->min_righthand, relid, subst);
  sjinf->syn_lefthand = adjust_relid_set(sjinf->syn_lefthand, relid, subst);
  sjinf->syn_righthand = adjust_relid_set(sjinf->syn_righthand, relid, subst);

  if (sjinfo != NULL)
  {
   Assert(subst <= 0);

   /* Remove sjinfo->ojrelid bits from the sets: */
   sjinf->min_lefthand = bms_del_member(sjinf->min_lefthand,
             sjinfo->ojrelid);
   sjinf->min_righthand = bms_del_member(sjinf->min_righthand,
              sjinfo->ojrelid);
   sjinf->syn_lefthand = bms_del_member(sjinf->syn_lefthand,
             sjinfo->ojrelid);
   sjinf->syn_righthand = bms_del_member(sjinf->syn_righthand,
              sjinfo->ojrelid);
   /* relid cannot appear in these fields, but ojrelid can: */
   sjinf->commute_above_l = bms_del_member(sjinf->commute_above_l,
             sjinfo->ojrelid);
   sjinf->commute_above_r = bms_del_member(sjinf->commute_above_r,
             sjinfo->ojrelid);
   sjinf->commute_below_l = bms_del_member(sjinf->commute_below_l,
             sjinfo->ojrelid);
   sjinf->commute_below_r = bms_del_member(sjinf->commute_below_r,
             sjinfo->ojrelid);
  }
  else
  {
   Assert(subst > 0);

   ChangeVarNodesExtended((Node *) sjinf->semi_rhs_exprs, relid, subst,
           0, replace_relid_callback);
  }
 }

 /*
  * Likewise remove references from PlaceHolderVar data structures,
  * removing any no-longer-needed placeholders entirely.  We remove PHV
  * only for left-join removal.  With self-join elimination, PHVs already
  * get moved to the remaining relation, where they might still be needed.
  * It might also happen that we skip the removal of some PHVs that could
  * be removed.  However, the overhead of extra PHVs is small compared to
  * the complexity of analysis needed to remove them.
  *
  * Removal is a bit trickier than it might seem: we can remove PHVs that
  * are used at the target rel and/or in the join qual, but not those that
  * are used at join partner rels or above the join.  It's not that easy to
  * distinguish PHVs used at partner rels from those used in the join qual,
  * since they will both have ph_needed sets that are subsets of
  * joinrelids.  However, a PHV used at a partner rel could not have the
  * target rel in ph_eval_at, so we check that while deciding whether to
  * remove or just update the PHV.  There is no corresponding test in
  * join_is_removable because it doesn't need to distinguish those cases.
 */
 foreach(l, root->placeholder_list)
 {
  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);

  Assert(sjinfo == NULL || !bms_is_member(relid, phinfo->ph_lateral));
  if (sjinfo != NULL &&
   bms_is_subset(phinfo->ph_needed, joinrelids) &&
   bms_is_member(relid, phinfo->ph_eval_at) &&
   !bms_is_member(sjinfo->ojrelid, phinfo->ph_eval_at))
  {
   /*
    * This code shouldn't be executed if one relation is substituted
    * with another: in this case, the placeholder may be employed in
    * a filter inside the scan node the SJE removes.
 */
   root->placeholder_list = foreach_delete_current(root->placeholder_list,
               l);
   root->placeholder_array[phinfo->phid] = NULL;
  }
  else
  {
   PlaceHolderVar *phv = phinfo->ph_var;

   phinfo->ph_eval_at = adjust_relid_set(phinfo->ph_eval_at, relid, subst);
   if (sjinfo != NULL)
    phinfo->ph_eval_at = adjust_relid_set(phinfo->ph_eval_at,
               sjinfo->ojrelid, subst);
   Assert(!bms_is_empty(phinfo->ph_eval_at)); /* checked previously */
   /* Reduce ph_needed to contain only "relation 0"; see below */
   if (bms_is_member(0, phinfo->ph_needed))
    phinfo->ph_needed = bms_make_singleton(0);
   else
    phinfo->ph_needed = NULL;

   phinfo->ph_lateral = adjust_relid_set(phinfo->ph_lateral, relid, subst);

   /*
    * ph_lateral might contain rels mentioned in ph_eval_at after the
    * replacement, remove them.
 */
   phinfo->ph_lateral = bms_difference(phinfo->ph_lateral, phinfo->ph_eval_at);
   /* ph_lateral might or might not be empty */

   phv->phrels = adjust_relid_set(phv->phrels, relid, subst);
   if (sjinfo != NULL)
    phv->phrels = adjust_relid_set(phv->phrels,
              sjinfo->ojrelid, subst);
   Assert(!bms_is_empty(phv->phrels));

   ChangeVarNodesExtended((Node *) phv->phexpr, relid, subst, 0,
           replace_relid_callback);

   Assert(phv->phnullingrels == NULL); /* no need to adjust */
  }
 }

 /*
  * Likewise remove references from EquivalenceClasses.
 */
 foreach(l, root->eq_classes)
 {
  EquivalenceClass *ec = (EquivalenceClass *) lfirst(l);

  if (bms_is_member(relid, ec->ec_relids) ||
   (sjinfo == NULL || bms_is_member(sjinfo->ojrelid, ec->ec_relids)))
   remove_rel_from_eclass(ec, sjinfo, relid, subst);
 }

 /*
  * Finally, we must recompute per-Var attr_needed and per-PlaceHolderVar
  * ph_needed relid sets.  These have to be known accurately, else we may
  * fail to remove other now-removable outer joins.  And our removal of the
  * join clause(s) for this outer join may mean that Vars that were
  * formerly needed no longer are.  So we have to do this honestly by
  * repeating the construction of those relid sets.  We can cheat to one
  * small extent: we can avoid re-examining the targetlist and HAVING qual
  * by preserving "relation 0" bits from the existing relid sets.  This is
  * safe because we'd never remove such references.
  *
  * So, start by removing all other bits from attr_needed sets and
  * lateral_vars lists.  (We already did this above for ph_needed.)
 */
 for (rti = 1; rti < root->simple_rel_array_size; rti++)
 {
  RelOptInfo *otherrel = root->simple_rel_array[rti];
  int   attroff;

  /* there may be empty slots corresponding to non-baserel RTEs */
  if (otherrel == NULL)
   continue;

  Assert(otherrel->relid == rti); /* sanity check on array */

  for (attroff = otherrel->max_attr - otherrel->min_attr;
    attroff >= 0;
    attroff--)
  {
   if (bms_is_member(0, otherrel->attr_needed[attroff]))
    otherrel->attr_needed[attroff] = bms_make_singleton(0);
   else
    otherrel->attr_needed[attroff] = NULL;
  }

  if (subst > 0)
   ChangeVarNodesExtended((Node *) otherrel->lateral_vars, relid,
           subst, 0, replace_relid_callback);
 }
}

/*
 * Remove the target relid and references to the target join from the
 * planner's data structures, having determined that there is no need
 * to include them in the query.
 *
 * We are not terribly thorough here.  We only bother to update parts of
 * the planner's data structures that will actually be consulted later.
 */
static void
remove_leftjoinrel_from_query(PlannerInfo *root, int relid,
         SpecialJoinInfo *sjinfo)
{
 RelOptInfo *rel = find_base_rel(root, relid);
 int   ojrelid = sjinfo->ojrelid;
 Relids  joinrelids;
 Relids  join_plus_commute;
 List    *joininfos;
 ListCell   *l;

 /* Compute the relid set for the join we are considering */
 joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
 Assert(ojrelid != 0);
 joinrelids = bms_add_member(joinrelids, ojrelid);

 remove_rel_from_query(root, rel, -1, sjinfo, joinrelids);

 /*
  * Remove any joinquals referencing the rel from the joininfo lists.
  *
  * In some cases, a joinqual has to be put back after deleting its
  * reference to the target rel.  This can occur for pseudoconstant and
  * outerjoin-delayed quals, which can get marked as requiring the rel in
  * order to force them to be evaluated at or above the join.  We can't
  * just discard them, though.  Only quals that logically belonged to the
  * outer join being discarded should be removed from the query.
  *
  * We might encounter a qual that is a clone of a deletable qual with some
  * outer-join relids added (see deconstruct_distribute_oj_quals).  To
  * ensure we get rid of such clones as well, add the relids of all OJs
  * commutable with this one to the set we test against for
  * pushed-down-ness.
 */
 join_plus_commute = bms_union(joinrelids,
          sjinfo->commute_above_r);
 join_plus_commute = bms_add_members(join_plus_commute,
          sjinfo->commute_below_l);

 /*
  * We must make a copy of the rel's old joininfo list before starting the
  * loop, because otherwise remove_join_clause_from_rels would destroy the
  * list while we're scanning it.
 */
 joininfos = list_copy(rel->joininfo);
 foreach(l, joininfos)
 {
  RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

  remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);

  if (RINFO_IS_PUSHED_DOWN(rinfo, join_plus_commute))
  {
   /*
    * There might be references to relid or ojrelid in the
    * RestrictInfo's relid sets, as a consequence of PHVs having had
    * ph_eval_at sets that include those.  We already checked above
    * that any such PHV is safe (and updated its ph_eval_at), so we
    * can just drop those references.
 */
   remove_rel_from_restrictinfo(rinfo, relid, ojrelid);

   /*
    * Cross-check that the clause itself does not reference the
    * target rel or join.
 */
#ifdef USE_ASSERT_CHECKING
   {
    Relids  clause_varnos = pull_varnos(root,
              (Node *) rinfo->clause);

    Assert(!bms_is_member(relid, clause_varnos));
    Assert(!bms_is_member(ojrelid, clause_varnos));
   }
#endif
   /* Now throw it back into the joininfo lists */
   distribute_restrictinfo_to_rels(root, rinfo);
  }
 }

 /*
  * There may be references to the rel in root->fkey_list, but if so,
  * match_foreign_keys_to_quals() will get rid of them.
 */

 /*
  * Now remove the rel from the baserel array to prevent it from being
  * referenced again.  (We can't do this earlier because
  * remove_join_clause_from_rels will touch it.)
 */
 root->simple_rel_array[relid] = NULL;
 root->simple_rte_array[relid] = NULL;

 /* And nuke the RelOptInfo, just in case there's another access path */
 pfree(rel);

 /*
  * Now repeat construction of attr_needed bits coming from all other
  * sources.
 */
 rebuild_placeholder_attr_needed(root);
 rebuild_joinclause_attr_needed(root);
 rebuild_eclass_attr_needed(root);
 rebuild_lateral_attr_needed(root);
}

/*
 * Remove any references to relid or ojrelid from the RestrictInfo.
 *
 * We only bother to clean out bits in the RestrictInfo's various relid sets,
 * not nullingrel bits in contained Vars and PHVs.  (This might have to be
 * improved sometime.)  However, if the RestrictInfo contains an OR clause
 * we have to also clean up the sub-clauses.
 */
static void
remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
{
 /*
  * initsplan.c is fairly cavalier about allowing RestrictInfos to share
  * relid sets with other RestrictInfos, and SpecialJoinInfos too.  Make
  * sure this RestrictInfo has its own relid sets before we modify them.
  * (In present usage, clause_relids is probably not shared, but
  * required_relids could be; let's not assume anything.)
 */
 rinfo->clause_relids = bms_copy(rinfo->clause_relids);
 rinfo->clause_relids = bms_del_member(rinfo->clause_relids, relid);
 rinfo->clause_relids = bms_del_member(rinfo->clause_relids, ojrelid);
 /* Likewise for required_relids */
 rinfo->required_relids = bms_copy(rinfo->required_relids);
 rinfo->required_relids = bms_del_member(rinfo->required_relids, relid);
 rinfo->required_relids = bms_del_member(rinfo->required_relids, ojrelid);
 /* Likewise for incompatible_relids */
 rinfo->incompatible_relids = bms_copy(rinfo->incompatible_relids);
 rinfo->incompatible_relids = bms_del_member(rinfo->incompatible_relids, relid);
 rinfo->incompatible_relids = bms_del_member(rinfo->incompatible_relids, ojrelid);
 /* Likewise for outer_relids */
 rinfo->outer_relids = bms_copy(rinfo->outer_relids);
 rinfo->outer_relids = bms_del_member(rinfo->outer_relids, relid);
 rinfo->outer_relids = bms_del_member(rinfo->outer_relids, ojrelid);
 /* Likewise for left_relids */
 rinfo->left_relids = bms_copy(rinfo->left_relids);
 rinfo->left_relids = bms_del_member(rinfo->left_relids, relid);
 rinfo->left_relids = bms_del_member(rinfo->left_relids, ojrelid);
 /* Likewise for right_relids */
 rinfo->right_relids = bms_copy(rinfo->right_relids);
 rinfo->right_relids = bms_del_member(rinfo->right_relids, relid);
 rinfo->right_relids = bms_del_member(rinfo->right_relids, ojrelid);

 /* If it's an OR, recurse to clean up sub-clauses */
 if (restriction_is_or_clause(rinfo))
 {
  ListCell   *lc;

  Assert(is_orclause(rinfo->orclause));
  foreach(lc, ((BoolExpr *) rinfo->orclause)->args)
  {
   Node    *orarg = (Node *) lfirst(lc);

   /* OR arguments should be ANDs or sub-RestrictInfos */
   if (is_andclause(orarg))
   {
    List    *andargs = ((BoolExpr *) orarg)->args;
    ListCell   *lc2;

    foreach(lc2, andargs)
    {
     RestrictInfo *rinfo2 = lfirst_node(RestrictInfo, lc2);

     remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
    }
   }
   else
   {
    RestrictInfo *rinfo2 = castNode(RestrictInfo, orarg);

    remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
   }
  }
 }
}

/*
 * Remove any references to relid or sjinfo->ojrelid (if sjinfo != NULL)
 * from the EquivalenceClass.
 *
 * Like remove_rel_from_restrictinfo, we don't worry about cleaning out
 * any nullingrel bits in contained Vars and PHVs.  (This might have to be
 * improved sometime.)  We do need to fix the EC and EM relid sets to ensure
 * that implied join equalities will be generated at the appropriate join
 * level(s).
 */
static void
remove_rel_from_eclass(EquivalenceClass *ec, SpecialJoinInfo *sjinfo,
        int relid, int subst)
{
 ListCell   *lc;

 /* Fix up the EC's overall relids */
 ec->ec_relids = adjust_relid_set(ec->ec_relids, relid, subst);
 if (sjinfo != NULL)
  ec->ec_relids = adjust_relid_set(ec->ec_relids,
           sjinfo->ojrelid, subst);

 /*
  * We don't expect any EC child members to exist at this point.  Ensure
  * that's the case, otherwise, we might be getting asked to do something
  * this function hasn't been coded for.
 */
 Assert(ec->ec_childmembers == NULL);

 /*
  * Fix up the member expressions.  Any non-const member that ends with
  * empty em_relids must be a Var or PHV of the removed relation.  We don't
  * need it anymore, so we can drop it.
 */
 foreach(lc, ec->ec_members)
 {
  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);

  if (bms_is_member(relid, cur_em->em_relids) ||
   (sjinfo != NULL && bms_is_member(sjinfo->ojrelid,
            cur_em->em_relids)))
  {
   Assert(!cur_em->em_is_const);
   cur_em->em_relids = adjust_relid_set(cur_em->em_relids, relid, subst);
   if (sjinfo != NULL)
    cur_em->em_relids = adjust_relid_set(cur_em->em_relids,
              sjinfo->ojrelid, subst);
   if (bms_is_empty(cur_em->em_relids))
    ec->ec_members = foreach_delete_current(ec->ec_members, lc);
  }
 }

 /* Fix up the source clauses, in case we can re-use them later */
 foreach(lc, ec->ec_sources)
 {
  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);

  if (sjinfo == NULL)
   ChangeVarNodesExtended((Node *) rinfo, relid, subst, 0,
           replace_relid_callback);
  else
   remove_rel_from_restrictinfo(rinfo, relid, sjinfo->ojrelid);
 }

 /*
  * Rather than expend code on fixing up any already-derived clauses, just
  * drop them.  (At this point, any such clauses would be base restriction
  * clauses, which we'd not need anymore anyway.)
 */
 ec_clear_derived_clauses(ec);
}

/*
 * Remove any occurrences of the target relid from a joinlist structure.
 *
 * It's easiest to build a whole new list structure, so we handle it that
 * way.  Efficiency is not a big deal here.
 *
 * *nremoved is incremented by the number of occurrences removed (there
 * should be exactly one, but the caller checks that).
 */
static List *
remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
{
 List    *result = NIL;
 ListCell   *jl;

 foreach(jl, joinlist)
 {
  Node    *jlnode = (Node *) lfirst(jl);

  if (IsA(jlnode, RangeTblRef))
  {
   int   varno = ((RangeTblRef *) jlnode)->rtindex;

   if (varno == relid)
    (*nremoved)++;
   else
    result = lappend(result, jlnode);
  }
  else if (IsA(jlnode, List))
  {
   /* Recurse to handle subproblem */
   List    *sublist;

   sublist = remove_rel_from_joinlist((List *) jlnode,
              relid, nremoved);
   /* Avoid including empty sub-lists in the result */
   if (sublist)
    result = lappend(result, sublist);
  }
  else
  {
   elog(ERROR, "unrecognized joinlist node type: %d",
     (int) nodeTag(jlnode));
  }
 }

 return result;
}


/*
 * reduce_unique_semijoins
 *  Check for semijoins that can be simplified to plain inner joins
 *  because the inner relation is provably unique for the join clauses.
 *
 * Ideally this would happen during reduce_outer_joins, but we don't have
 * enough information at that point.
 *
 * To perform the strength reduction when applicable, we need only delete
 * the semijoin's SpecialJoinInfo from root->join_info_list.  (We don't
 * bother fixing the join type attributed to it in the query jointree,
 * since that won't be consulted again.)
 */
void
reduce_unique_semijoins(PlannerInfo *root)
{
 ListCell   *lc;

 /*
  * Scan the join_info_list to find semijoins.
 */
 foreach(lc, root->join_info_list)
 {
  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
  int   innerrelid;
  RelOptInfo *innerrel;
  Relids  joinrelids;
  List    *restrictlist;

  /*
   * Must be a semijoin to a single baserel, else we aren't going to be
   * able to do anything with it.
 */
  if (sjinfo->jointype != JOIN_SEMI)
   continue;

  if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
   continue;

  innerrel = find_base_rel(root, innerrelid);

  /*
   * Before we trouble to run generate_join_implied_equalities, make a
   * quick check to eliminate cases in which we will surely be unable to
   * prove uniqueness of the innerrel.
 */
  if (!rel_supports_distinctness(root, innerrel))
   continue;

  /* Compute the relid set for the join we are considering */
  joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
  Assert(sjinfo->ojrelid == 0); /* SEMI joins don't have RT indexes */

  /*
   * Since we're only considering a single-rel RHS, any join clauses it
   * has must be clauses linking it to the semijoin's min_lefthand.  We
   * can also consider EC-derived join clauses.
 */
  restrictlist =
   list_concat(generate_join_implied_equalities(root,
               joinrelids,
               sjinfo->min_lefthand,
               innerrel,
               NULL),
      innerrel->joininfo);

  /* Test whether the innerrel is unique for those clauses. */
  if (!innerrel_is_unique(root,
        joinrelids, sjinfo->min_lefthand, innerrel,
        JOIN_SEMI, restrictlist, true))
   continue;

  /* OK, remove the SpecialJoinInfo from the list. */
  root->join_info_list = foreach_delete_current(root->join_info_list, lc);
 }
}


/*
 * rel_supports_distinctness
 *  Could the relation possibly be proven distinct on some set of columns?
 *
 * This is effectively a pre-checking function for rel_is_distinct_for().
 * It must return true if rel_is_distinct_for() could possibly return true
 * with this rel, but it should not expend a lot of cycles.  The idea is
 * that callers can avoid doing possibly-expensive processing to compute
 * rel_is_distinct_for()'s argument lists if the call could not possibly
 * succeed.
 */
static bool
rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
{
 /* We only know about baserels ... */
 if (rel->reloptkind != RELOPT_BASEREL)
  return false;
 if (rel->rtekind == RTE_RELATION)
 {
  /*
   * For a plain relation, we only know how to prove uniqueness by
   * reference to unique indexes.  Make sure there's at least one
   * suitable unique index.  It must be immediately enforced, and not a
   * partial index. (Keep these conditions in sync with
   * relation_has_unique_index_for!)
 */
  ListCell   *lc;

  foreach(lc, rel->indexlist)
  {
   IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);

   if (ind->unique && ind->immediate && ind->indpred == NIL)
    return true;
  }
 }
 else if (rel->rtekind == RTE_SUBQUERY)
 {
  Query    *subquery = root->simple_rte_array[rel->relid]->subquery;

  /* Check if the subquery has any qualities that support distinctness */
  if (query_supports_distinctness(subquery))
   return true;
 }
 /* We have no proof rules for any other rtekinds. */
 return false;
}

/*
 * rel_is_distinct_for
 *  Does the relation return only distinct rows according to clause_list?
 *
 * clause_list is a list of join restriction clauses involving this rel and
 * some other one.  Return true if no two rows emitted by this rel could
 * possibly join to the same row of the other rel.
 *
 * The caller must have already determined that each condition is a
 * mergejoinable equality with an expression in this relation on one side, and
 * an expression not involving this relation on the other.  The transient
 * outer_is_left flag is used to identify which side references this relation:
 * left side if outer_is_left is false, right side if it is true.
 *
 * Note that the passed-in clause_list may be destructively modified!  This
 * is OK for current uses, because the clause_list is built by the caller for
 * the sole purpose of passing to this function.
 *
 * (*extra_clauses) to be set to the right sides of baserestrictinfo clauses,
 * looking like "x = const" if distinctness is derived from such clauses, not
 * joininfo clauses.  Pass NULL to the extra_clauses if this value is not
 * needed.
 */
static bool
rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list,
     List **extra_clauses)
{
 /*
  * We could skip a couple of tests here if we assume all callers checked
  * rel_supports_distinctness first, but it doesn't seem worth taking any
  * risk for.
 */
 if (rel->reloptkind != RELOPT_BASEREL)
  return false;
 if (rel->rtekind == RTE_RELATION)
 {
  /*
   * Examine the indexes to see if we have a matching unique index.
   * relation_has_unique_index_ext automatically adds any usable
   * restriction clauses for the rel, so we needn't do that here.
 */
  if (relation_has_unique_index_ext(root, rel, clause_list, NIL, NIL,
            extra_clauses))
   return true;
 }
 else if (rel->rtekind == RTE_SUBQUERY)
 {
  Index  relid = rel->relid;
  Query    *subquery = root->simple_rte_array[relid]->subquery;
  List    *distinct_cols = NIL;
  ListCell   *l;

  /*
   * Build the argument list for query_is_distinct_for_with_collations:
   * a list of DistinctColInfo entries, each holding an output column
   * number that the query needs to be distinct over, the equality
   * operator that the column needs to be distinct according to, and
   * that operator's input collation.  The collation matters because the
   * subquery's own DISTINCT / GROUP BY / set-op proves uniqueness under
   * its own collation, which need not agree with the operator's.
   *
   * (XXX we are not considering restriction clauses attached to the
   * subquery; is that worth doing?)
 */
  foreach(l, clause_list)
  {
   RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
   OpExpr    *opexpr;
   Var     *var;
   DistinctColInfo *dcinfo;

   /*
    * The caller's mergejoinability test should have selected only
    * OpExprs.  The operator might be a cross-type operator and thus
    * not exactly the same operator the subquery would consider;
    * that's all right since query_is_distinct_for_with_collations
    * can resolve such cases.
 */
   opexpr = castNode(OpExpr, rinfo->clause);

   /* caller identified the inner side for us */
   if (rinfo->outer_is_left)
    var = (Var *) get_rightop(rinfo->clause);
   else
    var = (Var *) get_leftop(rinfo->clause);

   /*
    * We may ignore any RelabelType node above the operand.  (There
    * won't be more than one, since eval_const_expressions() has been
    * applied already.)
 */
   if (var && IsA(var, RelabelType))
    var = (Var *) ((RelabelType *) var)->arg;

   /*
    * If inner side isn't a Var referencing a subquery output column,
    * this clause doesn't help us.
 */
   if (!var || !IsA(var, Var) ||
    var->varno != relid || var->varlevelsup != 0)
    continue;

   dcinfo = palloc(sizeof(DistinctColInfo));
   dcinfo->colno = var->varattno;
   dcinfo->opid = opexpr->opno;
   dcinfo->collid = opexpr->inputcollid;
   distinct_cols = lappend(distinct_cols, dcinfo);
  }

  if (query_is_distinct_for_with_collations(subquery, distinct_cols))
   return true;
 }
 return false;
}


/*
 * query_supports_distinctness - could the query possibly be proven distinct
 *  on some set of output columns?
 *
 * This is effectively a pre-checking function for query_is_distinct_for().
 * It must return true if query_is_distinct_for() could possibly return true
 * with this query, but it should not expend a lot of cycles.  The idea is
 * that callers can avoid doing possibly-expensive processing to compute
 * query_is_distinct_for()'s argument lists if the call could not possibly
 * succeed.
 */
bool
query_supports_distinctness(Query *query)
{
 /* SRFs break distinctness except with DISTINCT, see below */
 if (query->hasTargetSRFs && query->distinctClause == NIL)
  return false;

 /* check for features we can prove distinctness with */
 if (query->distinctClause != NIL ||
  query->groupClause != NIL ||
  query->groupingSets != NIL ||
  query->hasAggs ||
  query->havingQual ||
  query->setOperations)
  return true;

 return false;
}

/*
 * query_is_distinct_for - ABI-preserving wrapper around
 *  query_is_distinct_for_with_collations().
 *
 * The original signature took parallel colnos/opids lists and did not
 * consider collations.  External callers built against earlier minor
 * releases continue to call it with the historical (collation-blind)
 * semantics; we forward with InvalidOid collations, which makes the
 * collation check a no-op (see collations_agree_on_equality()).
 */
bool
query_is_distinct_for(Query *query, List *colnos, List *opids)
{
 List    *distinct_cols = NIL;
 ListCell   *lc1;
 ListCell   *lc2;

 Assert(list_length(colnos) == list_length(opids));

 forboth(lc1, colnos, lc2, opids)
 {
  DistinctColInfo *dcinfo = palloc(sizeof(DistinctColInfo));

  dcinfo->colno = lfirst_int(lc1);
  dcinfo->opid = lfirst_oid(lc2);
  dcinfo->collid = InvalidOid;
  distinct_cols = lappend(distinct_cols, dcinfo);
 }

 return query_is_distinct_for_with_collations(query, distinct_cols);
}

/*
 * query_is_distinct_for_with_collations - does query never return duplicates
 *  of the specified columns?
 *
 * query is a not-yet-planned subquery (in current usage, it's always from
 * a subquery RTE, which the planner avoids scribbling on).
 *
 * distinct_cols is a list of DistinctColInfo, one per requested output column.
 * Each entry names the subquery output column number we want distinct, the
 * upper-level equality operator we'll compare values with, and that operator's
 * input collation.  We are interested in whether rows consisting of just these
 * columns are certain to be distinct.
 *
 * "Distinctness" is defined according to whether the corresponding upper-level
 * equality operators would think the values are distinct.  (Note: each opid
 * could be a cross-type operator, and thus not exactly the equality operator
 * that the subquery would use itself.  We use equality_ops_are_compatible() to
 * check compatibility.  That looks at opfamily membership for index AMs that
 * have declared that they support consistent equality semantics within an
 * opfamily, and so should give trustworthy answers for all operators that we
 * might need to deal with here.)
 *
 * The collid must also agree on equality with the collation the subquery's own
 * DISTINCT/GROUP BY/set-op uses to deduplicate the column, else the subquery's
 * distinctness does not carry over to the caller's equality semantics.  Two
 * collations agree on equality if they match or if both are deterministic (in
 * which case both reduce equality to byte-equality; see CREATE COLLATION).
 */
static bool
query_is_distinct_for_with_collations(Query *query, List *distinct_cols)
{
 ListCell   *l;
 DistinctColInfo *dcinfo;

 /*
  * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
  * columns in the DISTINCT clause appear in colnos and operator semantics
  * match.  This is true even if there are SRFs in the DISTINCT columns or
  * elsewhere in the tlist.
 */
 if (query->distinctClause)
 {
  foreach(l, query->distinctClause)
  {
   SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
   TargetEntry *tle = get_sortgroupclause_tle(sgc,
                query->targetList);

   dcinfo = distinct_col_search(tle->resno, distinct_cols);
   if (dcinfo == NULL ||
    !equality_ops_are_compatible(dcinfo->opid, sgc->eqop) ||
    !collations_agree_on_equality(dcinfo->collid,
             exprCollation((Node *) tle->expr)))
    break;   /* exit early if no match */
  }
  if (l == NULL)   /* had matches for all? */
   return true;
 }

 /*
  * Otherwise, a set-returning function in the query's targetlist can
  * result in returning duplicate rows, despite any grouping that might
  * occur before tlist evaluation.  (If all tlist SRFs are within GROUP BY
  * columns, it would be safe because they'd be expanded before grouping.
  * But it doesn't currently seem worth the effort to check for that.)
 */
 if (query->hasTargetSRFs)
  return false;

 /*
  * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if all
  * the grouped columns appear in colnos and operator semantics match.
 */
 if (query->groupClause && !query->groupingSets)
 {
  foreach(l, query->groupClause)
  {
   SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
   TargetEntry *tle = get_sortgroupclause_tle(sgc,
                query->targetList);

   dcinfo = distinct_col_search(tle->resno, distinct_cols);
   if (dcinfo == NULL ||
    !equality_ops_are_compatible(dcinfo->opid, sgc->eqop) ||
    !collations_agree_on_equality(dcinfo->collid,
             exprCollation((Node *) tle->expr)))
    break;   /* exit early if no match */
  }
  if (l == NULL)   /* had matches for all? */
   return true;
 }
 else if (query->groupingSets)
 {
  /*
   * If we have grouping sets with expressions, we probably don't have
   * uniqueness and analysis would be hard. Punt.
 */
  if (query->groupClause)
   return false;

  /*
   * If we have no groupClause (therefore no grouping expressions), we
   * might have one or many empty grouping sets. If there's just one,
   * then we're returning only one row and are certainly unique. But
   * otherwise, we know we're certainly not unique.
 */
  if (list_length(query->groupingSets) == 1 &&
   ((GroupingSet *) linitial(query->groupingSets))->kind == GROUPING_SET_EMPTY)
   return true;
  else
   return false;
 }
 else
 {
  /*
   * If we have no GROUP BY, but do have aggregates or HAVING, then the
   * result is at most one row so it's surely unique, for any operators.
 */
  if (query->hasAggs || query->havingQual)
   return true;
 }

 /*
  * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
  * except with ALL.
 */
 if (query->setOperations)
 {
  SetOperationStmt *topop = castNode(SetOperationStmt, query->setOperations);

  Assert(topop->op != SETOP_NONE);

  if (!topop->all)
  {
   ListCell   *lg;

   /* We're good if all the nonjunk output columns are in colnos */
   lg = list_head(topop->groupClauses);
   foreach(l, query->targetList)
   {
    TargetEntry *tle = (TargetEntry *) lfirst(l);
    SortGroupClause *sgc;

    if (tle->resjunk)
     continue; /* ignore resjunk columns */

    /* non-resjunk columns should have grouping clauses */
    Assert(lg != NULL);
    sgc = (SortGroupClause *) lfirst(lg);
    lg = lnext(topop->groupClauses, lg);

    dcinfo = distinct_col_search(tle->resno, distinct_cols);
    if (dcinfo == NULL ||
     !equality_ops_are_compatible(dcinfo->opid, sgc->eqop) ||
     !collations_agree_on_equality(dcinfo->collid,
              exprCollation((Node *) tle->expr)))
     break;  /* exit early if no match */
   }
   if (l == NULL)  /* had matches for all? */
    return true;
  }
 }

 /*
  * XXX Are there any other cases in which we can easily see the result
  * must be distinct?
  *
  * If you do add more smarts to this function, be sure to update
  * query_supports_distinctness() to match.
 */

 return false;
}

/*
 * distinct_col_search - subroutine for query_is_distinct_for_with_collations
 *
 * If colno matches the colno field of an entry in distinct_cols, return a
 * pointer to that entry; else return NULL.  (Ordinarily distinct_cols would
 * not contain duplicate colnos, but if it does, we arbitrarily select the
 * first match.)
 */
static DistinctColInfo *
distinct_col_search(int colno, List *distinct_cols)
{
 foreach_ptr(DistinctColInfo, dcinfo, distinct_cols)
 {
  if (dcinfo->colno == colno)
   return dcinfo;
 }

 return NULL;
}


/*
 * innerrel_is_unique
 *   Check if the innerrel provably contains at most one tuple matching any
 *   tuple from the outerrel, based on join clauses in the 'restrictlist'.
 *
 * We need an actual RelOptInfo for the innerrel, but it's sufficient to
 * identify the outerrel by its Relids.  This asymmetry supports use of this
 * function before joinrels have been built.  (The caller is expected to
 * also supply the joinrelids, just to save recalculating that.)
 *
 * The proof must be made based only on clauses that will be "joinquals"
 * rather than "otherquals" at execution.  For an inner join there's no
 * difference; but if the join is outer, we must ignore pushed-down quals,
 * as those will become "otherquals".  Note that this means the answer might
 * vary depending on whether IS_OUTER_JOIN(jointype); since we cache the
 * answer without regard to that, callers must take care not to call this
 * with jointypes that would be classified differently by IS_OUTER_JOIN().
 *
 * The actual proof is undertaken by is_innerrel_unique_for(); this function
 * is a frontend that is mainly concerned with caching the answers.
 * In particular, the force_cache argument allows overriding the internal
 * heuristic about whether to cache negative answers; it should be "true"
 * if making an inquiry that is not part of the normal bottom-up join search
 * sequence.
 */
bool
innerrel_is_unique(PlannerInfo *root,
       Relids joinrelids,
       Relids outerrelids,
       RelOptInfo *innerrel,
       JoinType jointype,
       List *restrictlist,
       bool force_cache)
{
 return innerrel_is_unique_ext(root, joinrelids, outerrelids, innerrel,
          jointype, restrictlist, force_cache, NULL);
}

/*
 * innerrel_is_unique_ext
 *   Do the same as innerrel_is_unique(), but also set to (*extra_clauses)
 *   additional clauses from a baserestrictinfo list used to prove the
 *   uniqueness.
 *
 * A non-NULL extra_clauses indicates that we're checking for self-join and
 * correspondingly dealing with filtered clauses.
 */
bool
innerrel_is_unique_ext(PlannerInfo *root,
        Relids joinrelids,
        Relids outerrelids,
        RelOptInfo *innerrel,
        JoinType jointype,
        List *restrictlist,
        bool force_cache,
        List **extra_clauses)
{
 MemoryContext old_context;
 ListCell   *lc;
 UniqueRelInfo *uniqueRelInfo;
 List    *outer_exprs = NIL;
 bool  self_join = (extra_clauses != NULL);

 /* Certainly can't prove uniqueness when there are no joinclauses */
 if (restrictlist == NIL)
  return false;

 /*
  * Make a quick check to eliminate cases in which we will surely be unable
  * to prove uniqueness of the innerrel.
 */
 if (!rel_supports_distinctness(root, innerrel))
  return false;

 /*
  * Query the cache to see if we've managed to prove that innerrel is
  * unique for any subset of this outerrel.  For non-self-join search, we
  * don't need an exact match, as extra outerrels can't make the innerrel
  * any less unique (or more formally, the restrictlist for a join to a
  * superset outerrel must be a superset of the conditions we successfully
  * used before). For self-join search, we require an exact match of
  * outerrels because we need extra clauses to be valid for our case. Also,
  * for self-join checking we've filtered the clauses list.  Thus, we can
  * match only the result cached for a self-join search for another
  * self-join check.
 */
 foreach(lc, innerrel->unique_for_rels)
 {
  uniqueRelInfo = (UniqueRelInfo *) lfirst(lc);

  if ((!self_join && bms_is_subset(uniqueRelInfo->outerrelids, outerrelids)) ||
   (self_join && bms_equal(uniqueRelInfo->outerrelids, outerrelids) &&
    uniqueRelInfo->self_join))
  {
   if (extra_clauses)
    *extra_clauses = uniqueRelInfo->extra_clauses;
   return true;  /* Success! */
  }
 }

 /*
  * Conversely, we may have already determined that this outerrel, or some
  * superset thereof, cannot prove this innerrel to be unique.
 */
 foreach(lc, innerrel->non_unique_for_rels)
 {
  Relids  unique_for_rels = (Relids) lfirst(lc);

  if (bms_is_subset(outerrelids, unique_for_rels))
   return false;
 }

 /* No cached information, so try to make the proof. */
 if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
          jointype, restrictlist,
          self_join ? &outer_exprs : NULL))
 {
  /*
   * Cache the positive result for future probes, being sure to keep it
   * in the planner_cxt even if we are working in GEQO.
   *
   * Note: one might consider trying to isolate the minimal subset of
   * the outerrels that proved the innerrel unique.  But it's not worth
   * the trouble, because the planner builds up joinrels incrementally
   * and so we'll see the minimally sufficient outerrels before any
   * supersets of them anyway.
 */
  old_context = MemoryContextSwitchTo(root->planner_cxt);
  uniqueRelInfo = makeNode(UniqueRelInfo);
  uniqueRelInfo->outerrelids = bms_copy(outerrelids);
  uniqueRelInfo->self_join = self_join;
  uniqueRelInfo->extra_clauses = outer_exprs;
  innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
           uniqueRelInfo);
  MemoryContextSwitchTo(old_context);

  if (extra_clauses)
   *extra_clauses = outer_exprs;
  return true;   /* Success! */
 }
 else
 {
  /*
   * None of the join conditions for outerrel proved innerrel unique, so
   * we can safely reject this outerrel or any subset of it in future
   * checks.
   *
   * However, in normal planning mode, caching this knowledge is totally
   * pointless; it won't be queried again, because we build up joinrels
   * from smaller to larger.  It is useful in GEQO mode, where the
   * knowledge can be carried across successive planning attempts; and
   * it's likely to be useful when using join-search plugins, too. Hence
   * cache when join_search_private is non-NULL.  (Yeah, that's a hack,
   * but it seems reasonable.)
   *
   * Also, allow callers to override that heuristic and force caching;
   * that's useful for reduce_unique_semijoins, which calls here before
   * the normal join search starts.
 */
  if (force_cache || root->join_search_private)
  {
   old_context = MemoryContextSwitchTo(root->planner_cxt);
   innerrel->non_unique_for_rels =
    lappend(innerrel->non_unique_for_rels,
      bms_copy(outerrelids));
   MemoryContextSwitchTo(old_context);
  }

  return false;
 }
}

/*
 * is_innerrel_unique_for
 *   Check if the innerrel provably contains at most one tuple matching any
 *   tuple from the outerrel, based on join clauses in the 'restrictlist'.
 */
static bool
is_innerrel_unique_for(PlannerInfo *root,
        Relids joinrelids,
        Relids outerrelids,
        RelOptInfo *innerrel,
        JoinType jointype,
        List *restrictlist,
        List **extra_clauses)
{
 List    *clause_list = NIL;
 ListCell   *lc;

 /*
  * Search for mergejoinable clauses that constrain the inner rel against
  * the outer rel.  If an operator is mergejoinable then it behaves like
  * equality for some btree opclass, so it's what we want.  The
  * mergejoinability test also eliminates clauses containing volatile
  * functions, which we couldn't depend on.
 */
 foreach(lc, restrictlist)
 {
  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);

  /*
   * As noted above, if it's a pushed-down clause and we're at an outer
   * join, we can't use it.
 */
  if (IS_OUTER_JOIN(jointype) &&
   RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
   continue;

  /* Ignore if it's not a mergejoinable clause */
  if (!restrictinfo->can_join ||
   restrictinfo->mergeopfamilies == NIL)
   continue;   /* not mergejoinable */

  /*
   * Check if the clause has the form "outer op inner" or "inner op
   * outer", and if so mark which side is inner.
 */
  if (!clause_sides_match_join(restrictinfo, outerrelids,
          innerrel->relids))
   continue;   /* no good for these input relations */

  /* OK, add to the list */
  clause_list = lappend(clause_list, restrictinfo);
 }

 /* Let rel_is_distinct_for() do the hard work */
 return rel_is_distinct_for(root, innerrel, clause_list, extra_clauses);
}

/*
 * Update EC members to point to the remaining relation instead of the removed
 * one, removing duplicates.
 *
 * Restriction clauses for base relations are already distributed to
 * the respective baserestrictinfo lists (see
 * generate_implied_equalities_for_column). The above code has already processed
 * this list and updated these clauses to reference the remaining
 * relation, so that we can skip them here based on their relids.
 *
 * Likewise, we have already processed the join clauses that join the
 * removed relation to the remaining one.
 *
 * Finally, there might be join clauses tying the removed relation to
 * some third relation.  We can't just delete the source clauses and
 * regenerate them from the EC because the corresponding equality
 * operators might be missing (see the handling of ec_broken).
 * Therefore, we will update the references in the source clauses.
 *
 * Derived clauses can be generated again, so it is simpler just to
 * delete them.
 */
static void
update_eclasses(EquivalenceClass *ec, int from, int to)
{
 List    *new_members = NIL;
 List    *new_sources = NIL;

 /*
  * We don't expect any EC child members to exist at this point.  Ensure
  * that's the case, otherwise, we might be getting asked to do something
  * this function hasn't been coded for.
 */
 Assert(ec->ec_childmembers == NULL);

 foreach_node(EquivalenceMember, em, ec->ec_members)
 {
  bool  is_redundant = false;

  if (!bms_is_member(from, em->em_relids))
  {
   new_members = lappend(new_members, em);
   continue;
  }

  em->em_relids = adjust_relid_set(em->em_relids, from, to);
  em->em_jdomain->jd_relids = adjust_relid_set(em->em_jdomain->jd_relids, from, to);

  /* We only process inner joins */
  ChangeVarNodesExtended((Node *) em->em_expr, from, to, 0,
          replace_relid_callback);

  foreach_node(EquivalenceMember, other, new_members)
  {
   if (!equal(em->em_relids, other->em_relids))
    continue;

   if (equal(em->em_expr, other->em_expr))
   {
    is_redundant = true;
    break;
   }
  }

  if (!is_redundant)
   new_members = lappend(new_members, em);
 }

 list_free(ec->ec_members);
 ec->ec_members = new_members;

 ec_clear_derived_clauses(ec);

 /* Update EC source expressions */
 foreach_node(RestrictInfo, rinfo, ec->ec_sources)
 {
  bool  is_redundant = false;

  if (!bms_is_member(from, rinfo->required_relids))
  {
   new_sources = lappend(new_sources, rinfo);
   continue;
  }

  ChangeVarNodesExtended((Node *) rinfo, from, to, 0,
          replace_relid_callback);

  /*
   * After switching the clause to the remaining relation, check it for
   * redundancy with existing ones. We don't have to check for
   * redundancy with derived clauses, because we've just deleted them.
 */
  foreach_node(RestrictInfo, other, new_sources)
  {
   if (!equal(rinfo->clause_relids, other->clause_relids))
    continue;

   if (equal(rinfo->clause, other->clause))
   {
    is_redundant = true;
    break;
   }
  }

  if (!is_redundant)
   new_sources = lappend(new_sources, rinfo);
 }

 list_free(ec->ec_sources);
 ec->ec_sources = new_sources;
 ec->ec_relids = adjust_relid_set(ec->ec_relids, from, to);
}

/*
 * "Logically" compares two RestrictInfo's ignoring the 'rinfo_serial' field,
 * which makes almost every RestrictInfo unique.  This type of comparison is
 * useful when removing duplicates while moving RestrictInfo's from removed
 * relation to remaining relation during self-join elimination.
 *
 * XXX: In the future, we might remove the 'rinfo_serial' field completely and
 * get rid of this function.
 */
static bool
restrict_infos_logically_equal(RestrictInfo *a, RestrictInfo *b)
{
 int   saved_rinfo_serial = a->rinfo_serial;
 bool  result;

 a->rinfo_serial = b->rinfo_serial;
 result = equal(a, b);
 a->rinfo_serial = saved_rinfo_serial;

 return result;
}

/*
 * This function adds all non-redundant clauses to the keeping relation
 * during self-join elimination.  That is a contradictory operation. On the
 * one hand, we reduce the length of the `restrict` lists, which can
 * impact planning or executing time.  Additionally, we improve the
 * accuracy of cardinality estimation.  On the other hand, it is one more
 * place that can make planning time much longer in specific cases.  It
 * would have been better to avoid calling the equal() function here, but
 * it's the only way to detect duplicated inequality expressions.
 *
 * (*keep_rinfo_list) is given by pointer because it might be altered by
 * distribute_restrictinfo_to_rels().
 */
static void
add_non_redundant_clauses(PlannerInfo *root,
        List *rinfo_candidates,
        List **keep_rinfo_list,
        Index removed_relid)
{
 foreach_node(RestrictInfo, rinfo, rinfo_candidates)
 {
  bool  is_redundant = false;

  Assert(!bms_is_member(removed_relid, rinfo->required_relids));

  foreach_node(RestrictInfo, src, (*keep_rinfo_list))
  {
   if (!bms_equal(src->clause_relids, rinfo->clause_relids))
    /* Can't compare trivially different clauses */
    continue;

   if (src == rinfo ||
    (rinfo->parent_ec != NULL &&
     src->parent_ec == rinfo->parent_ec) ||
    restrict_infos_logically_equal(rinfo, src))
   {
    is_redundant = true;
    break;
   }
  }
  if (!is_redundant)
   distribute_restrictinfo_to_rels(root, rinfo);
 }
}

/*
 * A custom callback for ChangeVarNodesExtended() providing Self-join
 * elimination (SJE) related functionality
 *
 * SJE needs to skip the RangeTblRef node type.  During SJE's last
 * step, remove_rel_from_joinlist() removes remaining RangeTblRefs
 * with target relid.  If ChangeVarNodes() replaces the target relid
 * before, remove_rel_from_joinlist() would fail to identify the nodes
 * to delete.
 *
 * SJE also needs to change the relids within RestrictInfo's.
 */
static bool
replace_relid_callback(Node *node, ChangeVarNodes_context *context)
{
 if (IsA(node, RangeTblRef))
 {
  return true;
 }
 else if (IsA(node, RestrictInfo))
 {
  RestrictInfo *rinfo = (RestrictInfo *) node;
  int   relid = -1;
  bool  is_req_equal =
   (rinfo->required_relids == rinfo->clause_relids);
  bool  clause_relids_is_multiple =
   (bms_membership(rinfo->clause_relids) == BMS_MULTIPLE);

  /*
   * Recurse down into clauses if the target relation is present in
   * clause_relids or required_relids.  We must check required_relids
   * because the relation not present in clause_relids might still be
   * present somewhere in orclause.
 */
  if (bms_is_member(context->rt_index, rinfo->clause_relids) ||
   bms_is_member(context->rt_index, rinfo->required_relids))
  {
   Relids  new_clause_relids;

   ChangeVarNodesWalkExpression((Node *) rinfo->clause, context);
   ChangeVarNodesWalkExpression((Node *) rinfo->orclause, context);

   new_clause_relids = adjust_relid_set(rinfo->clause_relids,
             context->rt_index,
             context->new_index);

   /*
    * Incrementally adjust num_base_rels based on the change of
    * clause_relids, which could contain both base relids and
    * outer-join relids.  This operation is legal until we remove
    * only baserels.
 */
   rinfo->num_base_rels -= bms_num_members(rinfo->clause_relids) -
    bms_num_members(new_clause_relids);

   rinfo->clause_relids = new_clause_relids;
   rinfo->left_relids =
    adjust_relid_set(rinfo->left_relids, context->rt_index, context->new_index);
   rinfo->right_relids =
    adjust_relid_set(rinfo->right_relids, context->rt_index, context->new_index);
  }

  if (is_req_equal)
   rinfo->required_relids = rinfo->clause_relids;
  else
   rinfo->required_relids =
    adjust_relid_set(rinfo->required_relids, context->rt_index, context->new_index);

  rinfo->outer_relids =
   adjust_relid_set(rinfo->outer_relids, context->rt_index, context->new_index);
  rinfo->incompatible_relids =
   adjust_relid_set(rinfo->incompatible_relids, context->rt_index, context->new_index);

  if (rinfo->mergeopfamilies &&
   bms_get_singleton_member(rinfo->clause_relids, &relid) &&
   clause_relids_is_multiple &&
   relid == context->new_index && IsA(rinfo->clause, OpExpr))
  {
   Expr    *leftOp;
   Expr    *rightOp;

   leftOp = (Expr *) get_leftop(rinfo->clause);
   rightOp = (Expr *) get_rightop(rinfo->clause);

   /*
    * For self-join elimination, changing varnos could transform
    * "t1.a = t2.a" into "t1.a = t1.a".  That is always true as long
    * as "t1.a" is not null.  We use equal() to check for such a
    * case, and then we replace the qual with a check for not null
    * (NullTest).
 */
   if (leftOp != NULL && equal(leftOp, rightOp))
   {
    NullTest   *ntest = makeNode(NullTest);

    ntest->arg = leftOp;
    ntest->nulltesttype = IS_NOT_NULL;
    ntest->argisrow = false;
    ntest->location = -1;
    rinfo->clause = (Expr *) ntest;
    rinfo->mergeopfamilies = NIL;
    rinfo->left_em = NULL;
    rinfo->right_em = NULL;
   }
   Assert(rinfo->orclause == NULL);
  }
  return true;
 }

 return false;
}

/*
 * Remove a relation after we have proven that it participates only in an
 * unneeded unique self-join.
 *
 * Replace any links in planner info structures.
 *
 * Transfer join and restriction clauses from the removed relation to the
 * remaining one. We change the Vars of the clause to point to the
 * remaining relation instead of the removed one. The clauses that require
 * a subset of joinrelids become restriction clauses of the remaining
 * relation, and others remain join clauses. We append them to
 * baserestrictinfo and joininfo, respectively, trying not to introduce
 * duplicates.
 *
 * We also have to process the 'joinclauses' list here, because it
 * contains EC-derived join clauses which must become filter clauses. It
 * is not enough to just correct the ECs because the EC-derived
 * restrictions are generated before join removal (see
 * generate_base_implied_equalities).
 *
 * NOTE: Remember to keep the code in sync with PlannerInfo to be sure all
 * cached relids and relid bitmapsets can be correctly cleaned during the
 * self-join elimination procedure.
 */
static void
remove_self_join_rel(PlannerInfo *root, PlanRowMark *kmark, PlanRowMark *rmark,
      RelOptInfo *toKeep, RelOptInfo *toRemove,
      List *restrictlist)
{
 List    *joininfos;
 ListCell   *lc;
 int   i;
 List    *jinfo_candidates = NIL;
 List    *binfo_candidates = NIL;

 Assert(toKeep->relid > 0);
 Assert(toRemove->relid > 0);

 /*
  * Replace the index of the removing table with the keeping one. The
  * technique of removing/distributing restrictinfo is used here to attach
  * just appeared (for keeping relation) join clauses and avoid adding
  * duplicates of those that already exist in the joininfo list.
 */
 joininfos = list_copy(toRemove->joininfo);
 foreach_node(RestrictInfo, rinfo, joininfos)
 {
  remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
  ChangeVarNodesExtended((Node *) rinfo, toRemove->relid, toKeep->relid,
          0, replace_relid_callback);

  if (bms_membership(rinfo->required_relids) == BMS_MULTIPLE)
   jinfo_candidates = lappend(jinfo_candidates, rinfo);
  else
   binfo_candidates = lappend(binfo_candidates, rinfo);
 }

 /*
  * Concatenate restrictlist to the list of base restrictions of the
  * removing table just to simplify the replacement procedure: all of them
  * weren't connected to any keeping relations and need to be added to some
  * rels.
 */
 toRemove->baserestrictinfo = list_concat(toRemove->baserestrictinfo,
            restrictlist);
 foreach_node(RestrictInfo, rinfo, toRemove->baserestrictinfo)
 {
  ChangeVarNodesExtended((Node *) rinfo, toRemove->relid, toKeep->relid,
          0, replace_relid_callback);

  if (bms_membership(rinfo->required_relids) == BMS_MULTIPLE)
   jinfo_candidates = lappend(jinfo_candidates, rinfo);
  else
   binfo_candidates = lappend(binfo_candidates, rinfo);
 }

 /*
  * Now, add all non-redundant clauses to the keeping relation.
 */
 add_non_redundant_clauses(root, binfo_candidates,
         &toKeep->baserestrictinfo, toRemove->relid);
 add_non_redundant_clauses(root, jinfo_candidates,
         &toKeep->joininfo, toRemove->relid);

 list_free(binfo_candidates);
 list_free(jinfo_candidates);

 /*
  * Arrange equivalence classes, mentioned removing a table, with the
  * keeping one: varno of removing table should be replaced in members and
  * sources lists. Also, remove duplicated elements if this replacement
  * procedure created them.
 */
 i = -1;
 while ((i = bms_next_member(toRemove->eclass_indexes, i)) >= 0)
 {
  EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);

  update_eclasses(ec, toRemove->relid, toKeep->relid);
  toKeep->eclass_indexes = bms_add_member(toKeep->eclass_indexes, i);
 }

 /*
  * Transfer the targetlist and attr_needed flags.
 */

 foreach(lc, toRemove->reltarget->exprs)
 {
  Node    *node = lfirst(lc);

  ChangeVarNodesExtended(node, toRemove->relid, toKeep->relid, 0,
          replace_relid_callback);
  if (!list_member(toKeep->reltarget->exprs, node))
   toKeep->reltarget->exprs = lappend(toKeep->reltarget->exprs, node);
 }

 for (i = toKeep->min_attr; i <= toKeep->max_attr; i++)
 {
  int   attno = i - toKeep->min_attr;

  toRemove->attr_needed[attno] = adjust_relid_set(toRemove->attr_needed[attno],
              toRemove->relid, toKeep->relid);
  toKeep->attr_needed[attno] = bms_add_members(toKeep->attr_needed[attno],
              toRemove->attr_needed[attno]);
 }

 /*
  * If the removed relation has a row mark, transfer it to the remaining
  * one.
  *
  * If both rels have row marks, just keep the one corresponding to the
  * remaining relation because we verified earlier that they have the same
  * strength.
 */
 if (rmark)
 {
  if (kmark)
  {
   Assert(kmark->markType == rmark->markType);

   root->rowMarks = list_delete_ptr(root->rowMarks, rmark);
  }
  else
  {
   /* Shouldn't have inheritance children here. */
   Assert(rmark->rti == rmark->prti);

   rmark->rti = rmark->prti = toKeep->relid;
  }
 }

 /*
  * Replace varno in all the query structures, except nodes RangeTblRef
  * otherwise later remove_rel_from_joinlist will yield errors.
 */
 ChangeVarNodesExtended((Node *) root->parse, toRemove->relid, toKeep->relid,
         0, replace_relid_callback);

 /* Replace links in the planner info */
 remove_rel_from_query(root, toRemove, toKeep->relid, NULL, NULL);

 /* At last, replace varno in root targetlist and HAVING clause */
 ChangeVarNodesExtended((Node *) root->processed_tlist, toRemove->relid,
         toKeep->relid, 0, replace_relid_callback);
 ChangeVarNodesExtended((Node *) root->processed_groupClause,
         toRemove->relid, toKeep->relid, 0,
         replace_relid_callback);

 adjust_relid_set(root->all_result_relids, toRemove->relid, toKeep->relid);
 adjust_relid_set(root->leaf_result_relids, toRemove->relid, toKeep->relid);

 /*
  * There may be references to the rel in root->fkey_list, but if so,
  * match_foreign_keys_to_quals() will get rid of them.
 */

 /*
  * Finally, remove the rel from the baserel array to prevent it from being
  * referenced again.  (We can't do this earlier because
  * remove_join_clause_from_rels will touch it.)
 */
 root->simple_rel_array[toRemove->relid] = NULL;
 root->simple_rte_array[toRemove->relid] = NULL;

 /* And nuke the RelOptInfo, just in case there's another access path. */
 pfree(toRemove);


 /*
  * Now repeat construction of attr_needed bits coming from all other
  * sources.
 */
 rebuild_placeholder_attr_needed(root);
 rebuild_joinclause_attr_needed(root);
 rebuild_eclass_attr_needed(root);
 rebuild_lateral_attr_needed(root);
}

/*
 * split_selfjoin_quals
 *  Processes 'joinquals' by building two lists: one containing the quals
 *  where the columns/exprs are on either side of the join match and
 *  another one containing the remaining quals.
 *
 * 'joinquals' must only contain quals for a RTE_RELATION being joined to
 * itself.
 */
static void
split_selfjoin_quals(PlannerInfo *root, List *joinquals, List **selfjoinquals,
      List **otherjoinquals, int from, int to)
{
 List    *sjoinquals = NIL;
 List    *ojoinquals = NIL;

 foreach_node(RestrictInfo, rinfo, joinquals)
 {
  OpExpr    *expr;
  Node    *leftexpr;
  Node    *rightexpr;

  /* In general, clause looks like F(arg1) = G(arg2) */
  if (!rinfo->mergeopfamilies ||
   bms_num_members(rinfo->clause_relids) != 2 ||
   bms_membership(rinfo->left_relids) != BMS_SINGLETON ||
   bms_membership(rinfo->right_relids) != BMS_SINGLETON)
  {
   ojoinquals = lappend(ojoinquals, rinfo);
   continue;
  }

  expr = (OpExpr *) rinfo->clause;

  if (!IsA(expr, OpExpr) || list_length(expr->args) != 2)
  {
   ojoinquals = lappend(ojoinquals, rinfo);
   continue;
  }

  leftexpr = get_leftop(rinfo->clause);
  rightexpr = copyObject(get_rightop(rinfo->clause));

  if (leftexpr && IsA(leftexpr, RelabelType))
   leftexpr = (Node *) ((RelabelType *) leftexpr)->arg;
  if (rightexpr && IsA(rightexpr, RelabelType))
   rightexpr = (Node *) ((RelabelType *) rightexpr)->arg;

  /*
   * Quite an expensive operation, narrowing the use case. For example,
   * when we have cast of the same var to different (but compatible)
   * types.
 */
  ChangeVarNodesExtended(rightexpr,
          bms_singleton_member(rinfo->right_relids),
          bms_singleton_member(rinfo->left_relids), 0,
          replace_relid_callback);

  if (equal(leftexpr, rightexpr))
   sjoinquals = lappend(sjoinquals, rinfo);
  else
   ojoinquals = lappend(ojoinquals, rinfo);
 }

 *selfjoinquals = sjoinquals;
 *otherjoinquals = ojoinquals;
}

/*
 * Check for a case when uniqueness is at least partly derived from a
 * baserestrictinfo clause. In this case, we have a chance to return only
 * one row (if such clauses on both sides of SJ are equal) or nothing (if they
 * are different).
 */
static bool
match_unique_clauses(PlannerInfo *root, RelOptInfo *outer, List *uclauses,
      Index relid)
{
 foreach_node(RestrictInfo, rinfo, uclauses)
 {
  Expr    *clause;
  Node    *iclause;
  Node    *c1;
  bool  matched = false;

  Assert(outer->relid > 0 && relid > 0);

  /* Only filters like f(R.x1,...,R.xN) == expr we should consider. */
  Assert(bms_is_empty(rinfo->left_relids) ^
      bms_is_empty(rinfo->right_relids));

  clause = (Expr *) copyObject(rinfo->clause);
  ChangeVarNodesExtended((Node *) clause, relid, outer->relid, 0,
          replace_relid_callback);

  iclause = bms_is_empty(rinfo->left_relids) ? get_rightop(clause) :
   get_leftop(clause);
  c1 = bms_is_empty(rinfo->left_relids) ? get_leftop(clause) :
   get_rightop(clause);

  /*
   * Compare these left and right sides with the corresponding sides of
   * the outer's filters. If no one is detected - return immediately.
 */
  foreach_node(RestrictInfo, orinfo, outer->baserestrictinfo)
  {
   Node    *oclause;
   Node    *c2;

   if (orinfo->mergeopfamilies == NIL)
    /* Don't consider clauses that aren't similar to 'F(X)=G(Y)' */
    continue;

   Assert(is_opclause(orinfo->clause));

   oclause = bms_is_empty(orinfo->left_relids) ?
    get_rightop(orinfo->clause) : get_leftop(orinfo->clause);
   c2 = (bms_is_empty(orinfo->left_relids) ?
      get_leftop(orinfo->clause) : get_rightop(orinfo->clause));

   if (equal(iclause, oclause) && equal(c1, c2))
   {
    matched = true;
    break;
   }
  }

  if (!matched)
   return false;
 }

 return true;
}

/*
 * Find and remove unique self-joins in a group of base relations that have
 * the same Oid.
 *
 * Returns a set of relids that were removed.
 */
static Relids
remove_self_joins_one_group(PlannerInfo *root, Relids relids)
{
 Relids  result = NULL;
 int   k;    /* Index of kept relation */
 int   r = -1;   /* Index of removed relation */

 while ((r = bms_next_member(relids, r)) > 0)
 {
  RelOptInfo *rrel = root->simple_rel_array[r];

  k = r;

  while ((k = bms_next_member(relids, k)) > 0)
  {
   Relids  joinrelids = NULL;
   RelOptInfo *krel = root->simple_rel_array[k];
   List    *restrictlist;
   List    *selfjoinquals;
   List    *otherjoinquals;
   ListCell   *lc;
   bool  jinfo_check = true;
   PlanRowMark *kmark = NULL;
   PlanRowMark *rmark = NULL;
   List    *uclauses = NIL;

   /* A sanity check: the relations have the same Oid. */
   Assert(root->simple_rte_array[k]->relid ==
       root->simple_rte_array[r]->relid);

   /*
    * It is impossible to eliminate the join of two relations if they
    * belong to different rules of order. Otherwise, the planner
    * can't find any variants of the correct query plan.
 */
   foreach(lc, root->join_info_list)
   {
    SpecialJoinInfo *info = (SpecialJoinInfo *) lfirst(lc);

    if ((bms_is_member(k, info->syn_lefthand) ^
      bms_is_member(r, info->syn_lefthand)) ||
     (bms_is_member(k, info->syn_righthand) ^
      bms_is_member(r, info->syn_righthand)))
    {
     jinfo_check = false;
     break;
    }
   }
   if (!jinfo_check)
    continue;

   /*
    * Check Row Marks equivalence. We can't remove the join if the
    * relations have row marks of different strength (e.g., one is
    * locked FOR UPDATE, and another just has ROW_MARK_REFERENCE for
    * EvalPlanQual rechecking).
 */
   foreach(lc, root->rowMarks)
   {
    PlanRowMark *rowMark = (PlanRowMark *) lfirst(lc);

    if (rowMark->rti == r)
    {
     Assert(rmark == NULL);
     rmark = rowMark;
    }
    else if (rowMark->rti == k)
    {
     Assert(kmark == NULL);
     kmark = rowMark;
    }

    if (kmark && rmark)
     break;
   }
   if (kmark && rmark && kmark->markType != rmark->markType)
    continue;

   /*
    * We only deal with base rels here, so their relids bitset
    * contains only one member -- their relid.
 */
   joinrelids = bms_add_member(joinrelids, r);
   joinrelids = bms_add_member(joinrelids, k);

   /*
    * PHVs should not impose any constraints on removing self-joins.
 */

   /*
    * At this stage, joininfo lists of inner and outer can contain
    * only clauses required for a superior outer join that can't
    * influence this optimization. So, we can avoid to call the
    * build_joinrel_restrictlist() routine.
 */
   restrictlist = generate_join_implied_equalities(root, joinrelids,
               rrel->relids,
               krel, NULL);
   if (restrictlist == NIL)
    continue;

   /*
    * Process restrictlist to separate the self-join quals from the
    * other quals. e.g., "x = x" goes to selfjoinquals and "a = b" to
    * otherjoinquals.
 */
   split_selfjoin_quals(root, restrictlist, &selfjoinquals,
         &otherjoinquals, rrel->relid, krel->relid);

   Assert(list_length(restrictlist) ==
       (list_length(selfjoinquals) + list_length(otherjoinquals)));

   /*
    * To enable SJE for the only degenerate case without any self
    * join clauses at all, add baserestrictinfo to this list. The
    * degenerate case works only if both sides have the same clause.
    * So doesn't matter which side to add.
 */
   selfjoinquals = list_concat(selfjoinquals, krel->baserestrictinfo);

   /*
    * Determine if the rrel can duplicate outer rows. We must bypass
    * the unique rel cache here since we're possibly using a subset
    * of join quals. We can use 'force_cache' == true when all join
    * quals are self-join quals.  Otherwise, we could end up putting
    * false negatives in the cache.
 */
   if (!innerrel_is_unique_ext(root, joinrelids, rrel->relids,
          krel, JOIN_INNER, selfjoinquals,
          list_length(otherjoinquals) == 0,
          &uclauses))
    continue;

   /*
    * 'uclauses' is the copy of outer->baserestrictinfo that are
    * associated with an index.  We proved by matching selfjoinquals
    * to a unique index that the outer relation has at most one
    * matching row for each inner row.  Sometimes that is not enough.
    * e.g. "WHERE s1.b = s2.b AND s1.a = 1 AND s2.a = 2" when the
    * unique index is (a,b).  Having non-empty uclauses, we must
    * validate that the inner baserestrictinfo contains the same
    * expressions, or we won't match the same row on each side of the
    * join.
 */
   if (!match_unique_clauses(root, rrel, uclauses, krel->relid))
    continue;

   /*
    * Remove rrel ReloptInfo from the planner structures and the
    * corresponding row mark.
 */
   remove_self_join_rel(root, kmark, rmark, krel, rrel, restrictlist);

   result = bms_add_member(result, r);

   /* We have removed the outer relation, try the next one. */
   break;
  }
 }

 return result;
}

/*
 * Gather indexes of base relations from the joinlist and try to eliminate self
 * joins.
 */
static Relids
remove_self_joins_recurse(PlannerInfo *root, List *joinlist, Relids toRemove)
{
 ListCell   *jl;
 Relids  relids = NULL;
 SelfJoinCandidate *candidates = NULL;
 int   i;
 int   j;
 int   numRels;

 /* Collect indexes of base relations of the join tree */
 foreach(jl, joinlist)
 {
  Node    *jlnode = (Node *) lfirst(jl);

  if (IsA(jlnode, RangeTblRef))
  {
   int   varno = ((RangeTblRef *) jlnode)->rtindex;
   RangeTblEntry *rte = root->simple_rte_array[varno];

   /*
    * We only consider ordinary relations as candidates to be
    * removed, and these relations should not have TABLESAMPLE
    * clauses specified.  Removing a relation with TABLESAMPLE clause
    * could potentially change the syntax of the query. Because of
    * UPDATE/DELETE EPQ mechanism, currently Query->resultRelation or
    * Query->mergeTargetRelation associated rel cannot be eliminated.
 */
   if (rte->rtekind == RTE_RELATION &&
    rte->relkind == RELKIND_RELATION &&
    rte->tablesample == NULL &&
    varno != root->parse->resultRelation &&
    varno != root->parse->mergeTargetRelation)
   {
    Assert(!bms_is_member(varno, relids));
    relids = bms_add_member(relids, varno);
   }
  }
  else if (IsA(jlnode, List))
  {
   /* Recursively go inside the sub-joinlist */
   toRemove = remove_self_joins_recurse(root, (List *) jlnode,
             toRemove);
  }
  else
   elog(ERROR, "unrecognized joinlist node type: %d",
     (int) nodeTag(jlnode));
 }

 numRels = bms_num_members(relids);

 /* Need at least two relations for the join */
 if (numRels < 2)
  return toRemove;

 /*
  * In order to find relations with the same oid we first build an array of
  * candidates and then sort it by oid.
 */
 candidates = (SelfJoinCandidate *) palloc(sizeof(SelfJoinCandidate) *
             numRels);
 i = -1;
 j = 0;
 while ((i = bms_next_member(relids, i)) >= 0)
 {
  candidates[j].relid = i;
  candidates[j].reloid = root->simple_rte_array[i]->relid;
  j++;
 }

 qsort(candidates, numRels, sizeof(SelfJoinCandidate),
    self_join_candidates_cmp);

 /*
  * Iteratively form a group of relation indexes with the same oid and
  * launch the routine that detects self-joins in this group and removes
  * excessive range table entries.
  *
  * At the end of the iteration, exclude the group from the overall relids
  * list. So each next iteration of the cycle will involve less and less
  * value of relids.
 */
 i = 0;
 for (j = 1; j < numRels + 1; j++)
 {
  if (j == numRels || candidates[j].reloid != candidates[i].reloid)
  {
   if (j - i >= 2)
   {
    /* Create a group of relation indexes with the same oid */
    Relids  group = NULL;
    Relids  removed;

    while (i < j)
    {
     group = bms_add_member(group, candidates[i].relid);
     i++;
    }
    relids = bms_del_members(relids, group);

    /*
     * Try to remove self-joins from a group of identical entries.
     * Make the next attempt iteratively - if something is deleted
     * from a group, changes in clauses and equivalence classes
     * can give us a chance to find more candidates.
 */
    do
    {
     Assert(!bms_overlap(group, toRemove));
     removed = remove_self_joins_one_group(root, group);
     toRemove = bms_add_members(toRemove, removed);
     group = bms_del_members(group, removed);
    } while (!bms_is_empty(removed) &&
       bms_membership(group) == BMS_MULTIPLE);
    bms_free(removed);
    bms_free(group);
   }
   else
   {
    /* Single relation, just remove it from the set */
    relids = bms_del_member(relids, candidates[i].relid);
    i = j;
   }
  }
 }

 Assert(bms_is_empty(relids));

 return toRemove;
}

/*
 * Compare self-join candidates by their oids.
 */
static int
self_join_candidates_cmp(const void *a, const void *b)
{
 const SelfJoinCandidate *ca = (const SelfJoinCandidate *) a;
 const SelfJoinCandidate *cb = (const SelfJoinCandidate *) b;

 if (ca->reloid != cb->reloid)
  return (ca->reloid < cb->reloid ? -1 : 1);
 else
  return 0;
}

/*
 * Find and remove useless self joins.
 *
 * Search for joins where a relation is joined to itself. If the join clause
 * for each tuple from one side of the join is proven to match the same
 * physical row (or nothing) on the other side, that self-join can be
 * eliminated from the query.  Suitable join clauses are assumed to be in the
 * form of X = X, and can be replaced with NOT NULL clauses.
 *
 * For the sake of simplicity, we don't apply this optimization to special
 * joins. Here is a list of what we could do in some particular cases:
 * 'a a1 semi join a a2': is reduced to inner by reduce_unique_semijoins,
 * and then removed normally.
 * 'a a1 anti join a a2': could simplify to a scan with 'outer quals AND
 * (IS NULL on join columns OR NOT inner quals)'.
 * 'a a1 left join a a2': could simplify to a scan like inner but without
 * NOT NULL conditions on join columns.
 * 'a a1 left join (a a2 join b)': can't simplify this, because join to b
 * can both remove rows and introduce duplicates.
 *
 * To search for removable joins, we order all the relations on their Oid,
 * go over each set with the same Oid, and consider each pair of relations
 * in this set.
 *
 * To remove the join, we mark one of the participating relations as dead
 * and rewrite all references to it to point to the remaining relation.
 * This includes modifying RestrictInfos, EquivalenceClasses, and
 * EquivalenceMembers. We also have to modify the row marks. The join clauses
 * of the removed relation become either restriction or join clauses, based on
 * whether they reference any relations not participating in the removed join.
 *
 * 'joinlist' is the top-level joinlist of the query. If it has any
 * references to the removed relations, we update them to point to the
 * remaining ones.
 */
List *
remove_useless_self_joins(PlannerInfo *root, List *joinlist)
{
 Relids  toRemove = NULL;
 int   relid = -1;

 if (!enable_self_join_elimination || joinlist == NIL ||
  (list_length(joinlist) == 1 && !IsA(linitial(joinlist), List)))
  return joinlist;

 /*
  * Merge pairs of relations participated in self-join. Remove unnecessary
  * range table entries.
 */
 toRemove = remove_self_joins_recurse(root, joinlist, toRemove);

 if (unlikely(toRemove != NULL))
 {
  /* At the end, remove orphaned relation links */
  while ((relid = bms_next_member(toRemove, relid)) >= 0)
  {
   int   nremoved = 0;

   joinlist = remove_rel_from_joinlist(joinlist, relid, &nremoved);
   if (nremoved != 1)
    elog(ERROR, "failed to find relation %d in joinlist", relid);
  }
 }

 return joinlist;
}