/src/postgres/src/backend/optimizer/plan/initsplan.c

Source
/*-------------------------------------------------------------------------
 *
 * initsplan.c
 *    Target list, group by, qualification, joininfo initialization routines
 *
 * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *    src/backend/optimizer/plan/initsplan.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/nbtree.h"
#include "access/sysattr.h"
#include "catalog/pg_constraint.h"
#include "catalog/pg_type.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/inherit.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 "parser/analyze.h"
#include "rewrite/rewriteManip.h"
#include "utils/lsyscache.h"
#include "utils/rel.h"
#include "utils/typcache.h"

/* These parameters are set by GUC */
int     from_collapse_limit;
int     join_collapse_limit;


/*
 * deconstruct_jointree requires multiple passes over the join tree, because we
 * need to finish computing JoinDomains before we start distributing quals.
 * As long as we have to do that, other information such as the relevant
 * qualscopes might as well be computed in the first pass too.
 *
 * deconstruct_recurse recursively examines the join tree and builds a List
 * (in depth-first traversal order) of JoinTreeItem structs, which are then
 * processed iteratively by deconstruct_distribute.  If there are outer
 * joins, non-degenerate outer join clauses are processed in a third pass
 * deconstruct_distribute_oj_quals.
 *
 * The JoinTreeItem structs themselves can be freed at the end of
 * deconstruct_jointree, but do not modify or free their substructure,
 * as the relid sets may also be pointed to by RestrictInfo and
 * SpecialJoinInfo nodes.
 */
typedef struct JoinTreeItem
{
  /* Fields filled during deconstruct_recurse: */
  Node     *jtnode;     /* jointree node to examine */
  JoinDomain *jdomain;    /* join domain for its ON/WHERE clauses */
  struct JoinTreeItem *jti_parent;  /* JoinTreeItem for this node's
                     * parent, or NULL if it's the top */
  Relids    qualscope;    /* base+OJ Relids syntactically included in
                 * this jointree node */
  Relids    inner_join_rels;  /* base+OJ Relids syntactically included
                   * in inner joins appearing at or below
                   * this jointree node */
  Relids    left_rels;    /* if join node, Relids of the left side */
  Relids    right_rels;   /* if join node, Relids of the right side */
  Relids    nonnullable_rels; /* if outer join, Relids of the
                   * non-nullable side */
  /* Fields filled during deconstruct_distribute: */
  SpecialJoinInfo *sjinfo;  /* if outer join, its SpecialJoinInfo */
  List     *oj_joinclauses; /* outer join quals not yet distributed */
  List     *lateral_clauses;  /* quals postponed from children due to
                   * lateral references */
} JoinTreeItem;

/*
 * Compatibility info for one GROUP BY item, precomputed for use by
 * remove_useless_groupby_columns() when matching unique-index columns against
 * GROUP BY items.
 */
typedef struct GroupByColInfo
{
  AttrNumber  attno;      /* var->varattno */
  List     *eq_opfamilies;  /* mergejoin opfamilies of sgc->eqop */
  Oid     coll;     /* var->varcollid */
} GroupByColInfo;


static bool is_partial_agg_memory_risky(PlannerInfo *root);
static void create_agg_clause_infos(PlannerInfo *root);
static void create_grouping_expr_infos(PlannerInfo *root);
static EquivalenceClass *get_eclass_for_sortgroupclause(PlannerInfo *root,
                            SortGroupClause *sgc,
                            Expr *expr);
static void extract_lateral_references(PlannerInfo *root, RelOptInfo *brel,
                     Index rtindex);
static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
                 JoinDomain *parent_domain,
                 JoinTreeItem *parent_jtitem,
                 List **item_list);
static void deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem);
static void process_security_barrier_quals(PlannerInfo *root,
                       int rti, JoinTreeItem *jtitem);
static void mark_rels_nulled_by_join(PlannerInfo *root, Index ojrelid,
                   Relids lower_rels);
static SpecialJoinInfo *make_outerjoininfo(PlannerInfo *root,
                       Relids left_rels, Relids right_rels,
                       Relids inner_join_rels,
                       JoinType jointype, Index ojrelid,
                       List *clause);
static void compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo,
                  List *clause);
static void deconstruct_distribute_oj_quals(PlannerInfo *root,
                      List *jtitems,
                      JoinTreeItem *jtitem);
static void distribute_quals_to_rels(PlannerInfo *root, List *clauses,
                   JoinTreeItem *jtitem,
                   SpecialJoinInfo *sjinfo,
                   Index security_level,
                   Relids qualscope,
                   Relids ojscope,
                   Relids outerjoin_nonnullable,
                   Relids incompatible_relids,
                   bool allow_equivalence,
                   bool has_clone,
                   bool is_clone,
                   List **postponed_oj_qual_list);
static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
                  JoinTreeItem *jtitem,
                  SpecialJoinInfo *sjinfo,
                  Index security_level,
                  Relids qualscope,
                  Relids ojscope,
                  Relids outerjoin_nonnullable,
                  Relids incompatible_relids,
                  bool allow_equivalence,
                  bool has_clone,
                  bool is_clone,
                  List **postponed_oj_qual_list);
static Relids get_join_domain_min_rels(PlannerInfo *root, Relids domain_relids);
static void check_mergejoinable(RestrictInfo *restrictinfo);
static void check_hashjoinable(RestrictInfo *restrictinfo);
static void check_memoizable(RestrictInfo *restrictinfo);


/*****************************************************************************
 *
 *   JOIN TREES
 *
 *****************************************************************************/

/*
 * add_base_rels_to_query
 *
 *    Scan the query's jointree and create baserel RelOptInfos for all
 *    the base relations (e.g., table, subquery, and function RTEs)
 *    appearing in the jointree.
 *
 * The initial invocation must pass root->parse->jointree as the value of
 * jtnode.  Internally, the function recurses through the jointree.
 *
 * At the end of this process, there should be one baserel RelOptInfo for
 * every non-join RTE that is used in the query.  Some of the baserels
 * may be appendrel parents, which will require additional "otherrel"
 * RelOptInfos for their member rels, but those are added later.
 */
void
add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
{
  if (jtnode == NULL)
    return;
  if (IsA(jtnode, RangeTblRef))
  {
    int     varno = ((RangeTblRef *) jtnode)->rtindex;

    (void) build_simple_rel(root, varno, NULL);
  }
  else if (IsA(jtnode, FromExpr))
  {
    FromExpr   *f = (FromExpr *) jtnode;
    ListCell   *l;

    foreach(l, f->fromlist)
      add_base_rels_to_query(root, lfirst(l));
  }
  else if (IsA(jtnode, JoinExpr))
  {
    JoinExpr   *j = (JoinExpr *) jtnode;

    add_base_rels_to_query(root, j->larg);
    add_base_rels_to_query(root, j->rarg);
  }
  else
    elog(ERROR, "unrecognized node type: %d",
       (int) nodeTag(jtnode));
}

/*
 * add_other_rels_to_query
 *    create "otherrel" RelOptInfos for the children of appendrel baserels
 *
 * At the end of this process, there should be RelOptInfos for all relations
 * that will be scanned by the query.
 */
void
add_other_rels_to_query(PlannerInfo *root)
{
  int     rti;

  for (rti = 1; rti < root->simple_rel_array_size; rti++)
  {
    RelOptInfo *rel = root->simple_rel_array[rti];
    RangeTblEntry *rte = root->simple_rte_array[rti];

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

    /* Ignore any "otherrels" that were already added. */
    if (rel->reloptkind != RELOPT_BASEREL)
      continue;

    /* If it's marked as inheritable, look for children. */
    if (rte->inh)
      expand_inherited_rtentry(root, rel, rte, rti);
  }
}


/*****************************************************************************
 *
 *   TARGET LISTS
 *
 *****************************************************************************/

/*
 * build_base_rel_tlists
 *    Add targetlist entries for each var needed in the query's final tlist
 *    (and HAVING clause, if any) to the appropriate base relations.
 *
 * We mark such vars as needed by "relation 0" to ensure that they will
 * propagate up through all join plan steps.
 */
void
build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
{
  List     *tlist_vars = pull_var_clause((Node *) final_tlist,
                       PVC_RECURSE_AGGREGATES |
                       PVC_RECURSE_WINDOWFUNCS |
                       PVC_INCLUDE_PLACEHOLDERS);

  if (tlist_vars != NIL)
  {
    add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0));
    list_free(tlist_vars);
  }

  /*
   * If there's a HAVING clause, we'll need the Vars it uses, too.  Note
   * that HAVING can contain Aggrefs but not WindowFuncs.
   */
  if (root->parse->havingQual)
  {
    List     *having_vars = pull_var_clause(root->parse->havingQual,
                          PVC_RECURSE_AGGREGATES |
                          PVC_INCLUDE_PLACEHOLDERS);

    if (having_vars != NIL)
    {
      add_vars_to_targetlist(root, having_vars,
                   bms_make_singleton(0));
      list_free(having_vars);
    }
  }
}

/*
 * add_vars_to_targetlist
 *    For each variable appearing in the list, add it to the owning
 *    relation's targetlist if not already present, and mark the variable
 *    as being needed for the indicated join (or for final output if
 *    where_needed includes "relation 0").
 *
 *    The list may also contain PlaceHolderVars.  These don't necessarily
 *    have a single owning relation; we keep their attr_needed info in
 *    root->placeholder_list instead.  Find or create the associated
 *    PlaceHolderInfo entry, and update its ph_needed.
 */
void
add_vars_to_targetlist(PlannerInfo *root, List *vars,
             Relids where_needed)
{
  ListCell   *temp;

  Assert(!bms_is_empty(where_needed));

  foreach(temp, vars)
  {
    Node     *node = (Node *) lfirst(temp);

    if (IsA(node, Var))
    {
      Var      *var = (Var *) node;
      RelOptInfo *rel = find_base_rel(root, var->varno);
      int     attno = var->varattno;

      if (bms_is_subset(where_needed, rel->relids))
        continue;
      Assert(attno >= rel->min_attr && attno <= rel->max_attr);
      attno -= rel->min_attr;
      if (rel->attr_needed[attno] == NULL)
      {
        /*
         * Variable not yet requested, so add to rel's targetlist.
         *
         * The value available at the rel's scan level has not been
         * nulled by any outer join, so drop its varnullingrels.
         * (We'll put those back as we climb up the join tree.)
         */
        var = copyObject(var);
        var->varnullingrels = NULL;
        rel->reltarget->exprs = lappend(rel->reltarget->exprs, var);
        /* reltarget cost and width will be computed later */
      }
      rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno],
                            where_needed);
    }
    else if (IsA(node, PlaceHolderVar))
    {
      PlaceHolderVar *phv = (PlaceHolderVar *) node;
      PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);

      phinfo->ph_needed = bms_add_members(phinfo->ph_needed,
                        where_needed);
    }
    else
      elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
  }
}

/*****************************************************************************
 *
 *    GROUP BY
 *
 *****************************************************************************/

/*
 * remove_useless_groupby_columns
 *    Remove any columns in the GROUP BY clause that are redundant due to
 *    being functionally dependent on other GROUP BY columns.
 *
 * Since some other DBMSes do not allow references to ungrouped columns, it's
 * not unusual to find all columns listed in GROUP BY even though listing the
 * primary-key columns, or columns of a unique constraint would be sufficient.
 * Deleting such excess columns avoids redundant sorting or hashing work, so
 * it's worth doing.
 *
 * Relcache invalidations will ensure that cached plans become invalidated
 * when the underlying supporting indexes are dropped or if a column's NOT
 * NULL attribute is removed.
 */
void
remove_useless_groupby_columns(PlannerInfo *root)
{
  Query    *parse = root->parse;
  Bitmapset **groupbyattnos;
  List    **groupbycols;
  Bitmapset **surplusvars;
  bool    tryremove = false;
  ListCell   *lc;
  int     relid;

  /* No chance to do anything if there are less than two GROUP BY items */
  if (list_length(root->processed_groupClause) < 2)
    return;

  /* Don't fiddle with the GROUP BY clause if the query has grouping sets */
  if (parse->groupingSets)
    return;

  /*
   * Scan the GROUP BY clause to find GROUP BY items that are simple Vars.
   * Fill groupbyattnos[k] with a bitmapset of the column attnos of RTE k
   * that are GROUP BY items, and groupbycols[k] with a parallel list of
   * GroupByColInfo records.  We need the latter so that, when checking a
   * unique index against this rel's GROUP BY items, we can verify that the
   * index's notion of equality agrees with at least one GROUP BY item per
   * index column.
   */
  groupbyattnos = palloc0_array(Bitmapset *, list_length(parse->rtable) + 1);
  groupbycols = palloc0_array(List *, list_length(parse->rtable) + 1);
  foreach(lc, root->processed_groupClause)
  {
    SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
    TargetEntry *tle = get_sortgroupclause_tle(sgc, parse->targetList);
    Var      *var = (Var *) tle->expr;
    GroupByColInfo *info;

    /*
     * Ignore non-Vars and Vars from other query levels.
     *
     * XXX in principle, stable expressions containing Vars could also be
     * removed, if all the Vars are functionally dependent on other GROUP
     * BY items.  But it's not clear that such cases occur often enough to
     * be worth troubling over.
     */
    if (!IsA(var, Var) ||
      var->varlevelsup > 0)
      continue;

    /* OK, remember we have this Var */
    relid = var->varno;
    Assert(relid <= list_length(parse->rtable));

    /*
     * If this isn't the first column for this relation then we now have
     * multiple columns.  That means there might be some that can be
     * removed.
     */
    tryremove |= !bms_is_empty(groupbyattnos[relid]);
    groupbyattnos[relid] = bms_add_member(groupbyattnos[relid],
                        var->varattno - FirstLowInvalidHeapAttributeNumber);

    info = palloc_object(GroupByColInfo);
    info->attno = var->varattno;
    info->eq_opfamilies = get_mergejoin_opfamilies(sgc->eqop);
    info->coll = var->varcollid;
    groupbycols[relid] = lappend(groupbycols[relid], info);
  }

  /*
   * No Vars or didn't find multiple Vars for any relation in the GROUP BY?
   * If so, nothing can be removed, so don't waste more effort trying.
   */
  if (!tryremove)
    return;

  /*
   * Consider each relation and see if it is possible to remove some of its
   * Vars from GROUP BY.  For simplicity and speed, we do the actual removal
   * in a separate pass.  Here, we just fill surplusvars[k] with a bitmapset
   * of the column attnos of RTE k that are removable GROUP BY items.
   */
  surplusvars = NULL;     /* don't allocate array unless required */
  relid = 0;
  foreach(lc, parse->rtable)
  {
    RangeTblEntry *rte = lfirst_node(RangeTblEntry, lc);
    RelOptInfo *rel;
    Bitmapset  *relattnos;
    Bitmapset  *best_keycolumns = NULL;
    int32   best_nkeycolumns = PG_INT32_MAX;

    relid++;

    /* Only plain relations could have primary-key constraints */
    if (rte->rtekind != RTE_RELATION)
      continue;

    /*
     * We must skip inheritance parent tables as some of the child rels
     * may cause duplicate rows.  This cannot happen with partitioned
     * tables, however.
     */
    if (rte->inh && rte->relkind != RELKIND_PARTITIONED_TABLE)
      continue;

    /* Nothing to do unless this rel has multiple Vars in GROUP BY */
    relattnos = groupbyattnos[relid];
    if (bms_membership(relattnos) != BMS_MULTIPLE)
      continue;

    rel = root->simple_rel_array[relid];

    /*
     * Now check each index for this relation to see if there are any with
     * columns which are a proper subset of the grouping columns for this
     * relation.
     */
    foreach_node(IndexOptInfo, index, rel->indexlist)
    {
      Bitmapset  *ind_attnos;
      bool    index_check_ok;

      /*
       * Skip any non-unique and deferrable indexes.  Predicate indexes
       * have not been checked yet, so we must skip those too as the
       * predOK check that's done later might fail.
       */
      if (!index->unique || !index->immediate || index->indpred != NIL)
        continue;

      /* For simplicity, we currently don't support expression indexes */
      if (index->indexprs != NIL)
        continue;

      ind_attnos = NULL;
      index_check_ok = true;
      for (int i = 0; i < index->nkeycolumns; i++)
      {
        AttrNumber  indkey_attno = index->indexkeys[i];
        Oid     indkey_opfamily = index->opfamily[i];
        Oid     indkey_coll = index->indexcollations[i];
        ListCell   *lc2;

        /*
         * We must insist that the index columns are all defined NOT
         * NULL otherwise duplicate NULLs could exist.  However, we
         * can relax this check when the index is defined with NULLS
         * NOT DISTINCT as there can only be 1 NULL row, therefore
         * functional dependency on the unique columns is maintained,
         * despite the NULL.
         */
        if (!index->nullsnotdistinct &&
          !bms_is_member(indkey_attno, rel->notnullattnums))
        {
          index_check_ok = false;
          break;
        }

        /*
         * The index proves uniqueness only under its own opfamily and
         * collation.  Require some GROUP BY item on this column to
         * use a compatible eqop and collation, the same check
         * relation_has_unique_index_for() applies to join clauses.
         */
        foreach(lc2, groupbycols[relid])
        {
          GroupByColInfo *info = (GroupByColInfo *) lfirst(lc2);

          if (info->attno != indkey_attno)
            continue;
          if (list_member_oid(info->eq_opfamilies, indkey_opfamily) &&
            collations_agree_on_equality(indkey_coll, info->coll))
            break;
        }
        if (lc2 == NULL)
        {
          index_check_ok = false;
          break;
        }

        ind_attnos =
          bms_add_member(ind_attnos,
                   indkey_attno -
                   FirstLowInvalidHeapAttributeNumber);
      }

      if (!index_check_ok)
        continue;

      /*
       * Skip any indexes where the indexed columns aren't a proper
       * subset of the GROUP BY.
       */
      if (bms_subset_compare(ind_attnos, relattnos) != BMS_SUBSET1)
        continue;

      /*
       * Record the attribute numbers from the index with the fewest
       * columns.  This allows the largest number of columns to be
       * removed from the GROUP BY clause.  In the future, we may wish
       * to consider using the narrowest set of columns and looking at
       * pg_statistic.stawidth as it might be better to use an index
       * with, say two INT4s, rather than, say, one long varlena column.
       */
      if (index->nkeycolumns < best_nkeycolumns)
      {
        best_keycolumns = ind_attnos;
        best_nkeycolumns = index->nkeycolumns;
      }
    }

    /* Did we find a suitable index? */
    if (!bms_is_empty(best_keycolumns))
    {
      /*
       * To easily remember whether we've found anything to do, we don't
       * allocate the surplusvars[] array until we find something.
       */
      if (surplusvars == NULL)
        surplusvars = palloc0_array(Bitmapset *, list_length(parse->rtable) + 1);

      /* Remember the attnos of the removable columns */
      surplusvars[relid] = bms_difference(relattnos, best_keycolumns);
    }
  }

  /*
   * If we found any surplus Vars, build a new GROUP BY clause without them.
   * (Note: this may leave some TLEs with unreferenced ressortgroupref
   * markings, but that's harmless.)
   */
  if (surplusvars != NULL)
  {
    List     *new_groupby = NIL;

    foreach(lc, root->processed_groupClause)
    {
      SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
      TargetEntry *tle = get_sortgroupclause_tle(sgc, parse->targetList);
      Var      *var = (Var *) tle->expr;

      /*
       * New list must include non-Vars, outer Vars, and anything not
       * marked as surplus.
       */
      if (!IsA(var, Var) ||
        var->varlevelsup > 0 ||
        !bms_is_member(var->varattno - FirstLowInvalidHeapAttributeNumber,
                 surplusvars[var->varno]))
        new_groupby = lappend(new_groupby, sgc);
    }

    root->processed_groupClause = new_groupby;
  }
}

/*
 * setup_eager_aggregation
 *    Check if eager aggregation is applicable, and if so collect suitable
 *    aggregate expressions and grouping expressions in the query.
 */
void
setup_eager_aggregation(PlannerInfo *root)
{
  /*
   * Don't apply eager aggregation if disabled by user.
   */
  if (!enable_eager_aggregate)
    return;

  /*
   * Don't apply eager aggregation if there are no available GROUP BY
   * clauses.
   */
  if (!root->processed_groupClause)
    return;

  /*
   * For now we don't try to support grouping sets.
   */
  if (root->parse->groupingSets)
    return;

  /*
   * For now we don't try to support DISTINCT or ORDER BY aggregates.
   */
  if (root->numOrderedAggs > 0)
    return;

  /*
   * If there are any aggregates that do not support partial mode, or any
   * partial aggregates that are non-serializable, do not apply eager
   * aggregation.
   */
  if (root->hasNonPartialAggs || root->hasNonSerialAggs)
    return;

  /*
   * We don't try to apply eager aggregation if there are set-returning
   * functions in targetlist.
   */
  if (root->parse->hasTargetSRFs)
    return;

  /*
   * Eager aggregation only makes sense if there are multiple base rels in
   * the query.
   */
  if (bms_membership(root->all_baserels) != BMS_MULTIPLE)
    return;

  /*
   * Don't apply eager aggregation if any aggregate poses a risk of
   * excessive memory usage during partial aggregation.
   */
  if (is_partial_agg_memory_risky(root))
    return;

  /*
   * Collect aggregate expressions and plain Vars that appear in the
   * targetlist and havingQual.
   */
  create_agg_clause_infos(root);

  /*
   * If there are no suitable aggregate expressions, we cannot apply eager
   * aggregation.
   */
  if (root->agg_clause_list == NIL)
    return;

  /*
   * Collect grouping expressions that appear in grouping clauses.
   */
  create_grouping_expr_infos(root);
}

/*
 * is_partial_agg_memory_risky
 *    Check if any aggregate poses a risk of excessive memory usage during
 *    partial aggregation.
 *
 * We check if any aggregate has a negative aggtransspace value, which
 * indicates that its transition state data can grow unboundedly in size.
 * Applying eager aggregation in such cases risks high memory usage since
 * partial aggregation results might be stored in join hash tables or
 * materialized nodes.
 */
static bool
is_partial_agg_memory_risky(PlannerInfo *root)
{
  ListCell   *lc;

  foreach(lc, root->aggtransinfos)
  {
    AggTransInfo *transinfo = lfirst_node(AggTransInfo, lc);

    if (transinfo->aggtransspace < 0)
      return true;
  }

  return false;
}

/*
 * create_agg_clause_infos
 *    Search the targetlist and havingQual for Aggrefs and plain Vars, and
 *    create an AggClauseInfo for each Aggref node.
 */
static void
create_agg_clause_infos(PlannerInfo *root)
{
  List     *tlist_exprs;
  List     *agg_clause_list = NIL;
  List     *tlist_vars = NIL;
  Relids    aggregate_relids = NULL;
  bool    eager_agg_applicable = true;
  ListCell   *lc;

  Assert(root->agg_clause_list == NIL);
  Assert(root->tlist_vars == NIL);

  tlist_exprs = pull_var_clause((Node *) root->processed_tlist,
                  PVC_INCLUDE_AGGREGATES |
                  PVC_RECURSE_WINDOWFUNCS |
                  PVC_RECURSE_PLACEHOLDERS);

  /*
   * Aggregates within the HAVING clause need to be processed in the same
   * way as those in the targetlist.  Note that HAVING can contain Aggrefs
   * but not WindowFuncs.
   */
  if (root->parse->havingQual != NULL)
  {
    List     *having_exprs;

    having_exprs = pull_var_clause((Node *) root->parse->havingQual,
                     PVC_INCLUDE_AGGREGATES |
                     PVC_RECURSE_PLACEHOLDERS);
    if (having_exprs != NIL)
    {
      tlist_exprs = list_concat(tlist_exprs, having_exprs);
      list_free(having_exprs);
    }
  }

  foreach(lc, tlist_exprs)
  {
    Expr     *expr = (Expr *) lfirst(lc);
    Aggref     *aggref;
    Relids    agg_eval_at;
    AggClauseInfo *ac_info;

    /* For now we don't try to support GROUPING() expressions */
    if (IsA(expr, GroupingFunc))
    {
      eager_agg_applicable = false;
      break;
    }

    /* Collect plain Vars for future reference */
    if (IsA(expr, Var))
    {
      tlist_vars = list_append_unique(tlist_vars, expr);
      continue;
    }

    aggref = castNode(Aggref, expr);

    Assert(aggref->aggorder == NIL);
    Assert(aggref->aggdistinct == NIL);

    /*
     * We cannot push down aggregates that contain volatile functions.
     * Doing so would change the number of times the function is
     * evaluated.
     */
    if (contain_volatile_functions((Node *) aggref))
    {
      eager_agg_applicable = false;
      break;
    }

    /*
     * If there are any securityQuals, do not try to apply eager
     * aggregation if any non-leakproof aggregate functions are present.
     * This is overly strict, but for now...
     */
    if (root->qual_security_level > 0 &&
      !get_func_leakproof(aggref->aggfnoid))
    {
      eager_agg_applicable = false;
      break;
    }

    agg_eval_at = pull_varnos(root, (Node *) aggref);

    /*
     * If all base relations in the query are referenced by aggregate
     * functions, then eager aggregation is not applicable.
     */
    aggregate_relids = bms_add_members(aggregate_relids, agg_eval_at);
    if (bms_is_subset(root->all_baserels, aggregate_relids))
    {
      eager_agg_applicable = false;
      break;
    }

    /* OK, create the AggClauseInfo node */
    ac_info = makeNode(AggClauseInfo);
    ac_info->aggref = aggref;
    ac_info->agg_eval_at = agg_eval_at;

    /* ... and add it to the list */
    agg_clause_list = list_append_unique(agg_clause_list, ac_info);
  }

  list_free(tlist_exprs);

  if (eager_agg_applicable)
  {
    root->agg_clause_list = agg_clause_list;
    root->tlist_vars = tlist_vars;
  }
  else
  {
    list_free_deep(agg_clause_list);
    list_free(tlist_vars);
  }
}

/*
 * create_grouping_expr_infos
 *    Create a GroupingExprInfo for each expression usable as grouping key.
 *
 * If any grouping expression is not suitable, we will just return with
 * root->group_expr_list being NIL.
 */
static void
create_grouping_expr_infos(PlannerInfo *root)
{
  List     *exprs = NIL;
  List     *sortgrouprefs = NIL;
  List     *ecs = NIL;
  ListCell   *lc,
         *lc1,
         *lc2,
         *lc3;

  Assert(root->group_expr_list == NIL);

  foreach(lc, root->processed_groupClause)
  {
    SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
    TargetEntry *tle = get_sortgroupclause_tle(sgc, root->processed_tlist);
    TypeCacheEntry *tce;
    Oid     equalimageproc;

    Assert(tle->ressortgroupref > 0);

    /*
     * For now we only support plain Vars as grouping expressions.
     */
    if (!IsA(tle->expr, Var))
      return;

    /*
     * Eager aggregation is only possible if equality implies image
     * equality for each grouping key.  Otherwise, placing keys with
     * different byte images into the same group may result in the loss of
     * information that could be necessary to evaluate upper qual clauses.
     *
     * For instance, the NUMERIC data type is not supported, as values
     * that are considered equal by the equality operator (e.g., 0 and
     * 0.0) can have different scales.
     */
    tce = lookup_type_cache(exprType((Node *) tle->expr),
                TYPECACHE_BTREE_OPFAMILY);
    if (!OidIsValid(tce->btree_opf) ||
      !OidIsValid(tce->btree_opintype))
      return;

    equalimageproc = get_opfamily_proc(tce->btree_opf,
                       tce->btree_opintype,
                       tce->btree_opintype,
                       BTEQUALIMAGE_PROC);

    /*
     * If there is no BTEQUALIMAGE_PROC, eager aggregation is assumed to
     * be unsafe.  Otherwise, we call the procedure to check.  We must be
     * careful to pass the expression's actual collation, rather than the
     * data type's default collation, to ensure that non-deterministic
     * collations are correctly handled.
     */
    if (!OidIsValid(equalimageproc) ||
      !DatumGetBool(OidFunctionCall1Coll(equalimageproc,
                         exprCollation((Node *) tle->expr),
                         ObjectIdGetDatum(tce->btree_opintype))))
      return;

    exprs = lappend(exprs, tle->expr);
    sortgrouprefs = lappend_int(sortgrouprefs, tle->ressortgroupref);
    ecs = lappend(ecs, get_eclass_for_sortgroupclause(root, sgc, tle->expr));
  }

  /*
   * Construct a GroupingExprInfo for each expression.
   */
  forthree(lc1, exprs, lc2, sortgrouprefs, lc3, ecs)
  {
    Expr     *expr = (Expr *) lfirst(lc1);
    int     sortgroupref = lfirst_int(lc2);
    EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc3);
    GroupingExprInfo *ge_info;

    ge_info = makeNode(GroupingExprInfo);
    ge_info->expr = (Expr *) copyObject(expr);
    ge_info->sortgroupref = sortgroupref;
    ge_info->ec = ec;

    root->group_expr_list = lappend(root->group_expr_list, ge_info);
  }
}

/*
 * get_eclass_for_sortgroupclause
 *    Given a group clause and an expression, find an existing equivalence
 *    class that the expression is a member of; return NULL if none.
 */
static EquivalenceClass *
get_eclass_for_sortgroupclause(PlannerInfo *root, SortGroupClause *sgc,
                 Expr *expr)
{
  Oid     opfamily,
        opcintype,
        collation;
  CompareType cmptype;
  Oid     equality_op;
  List     *opfamilies;

  /* Punt if the group clause is not sortable */
  if (!OidIsValid(sgc->sortop))
    return NULL;

  /* Find the operator in pg_amop --- failure shouldn't happen */
  if (!get_ordering_op_properties(sgc->sortop,
                  &opfamily, &opcintype, &cmptype))
    elog(ERROR, "operator %u is not a valid ordering operator",
       sgc->sortop);

  /* Because SortGroupClause doesn't carry collation, consult the expr */
  collation = exprCollation((Node *) expr);

  /*
   * EquivalenceClasses need to contain opfamily lists based on the family
   * membership of mergejoinable equality operators, which could belong to
   * more than one opfamily.  So we have to look up the opfamily's equality
   * operator and get its membership.
   */
  equality_op = get_opfamily_member_for_cmptype(opfamily,
                          opcintype,
                          opcintype,
                          COMPARE_EQ);
  if (!OidIsValid(equality_op))  /* shouldn't happen */
    elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
       COMPARE_EQ, opcintype, opcintype, opfamily);
  opfamilies = get_mergejoin_opfamilies(equality_op);
  if (!opfamilies)     /* certainly should find some */
    elog(ERROR, "could not find opfamilies for equality operator %u",
       equality_op);

  /* Now find a matching EquivalenceClass */
  return get_eclass_for_sort_expr(root, expr, opfamilies, opcintype,
                  collation, sgc->tleSortGroupRef,
                  NULL, false);
}

/*****************************************************************************
 *
 *    LATERAL REFERENCES
 *
 *****************************************************************************/

/*
 * find_lateral_references
 *    For each LATERAL subquery, extract all its references to Vars and
 *    PlaceHolderVars of the current query level, and make sure those values
 *    will be available for evaluation of the subquery.
 *
 * While later planning steps ensure that the Var/PHV source rels are on the
 * outside of nestloops relative to the LATERAL subquery, we also need to
 * ensure that the Vars/PHVs propagate up to the nestloop join level; this
 * means setting suitable where_needed values for them.
 *
 * Note that this only deals with lateral references in unflattened LATERAL
 * subqueries.  When we flatten a LATERAL subquery, its lateral references
 * become plain Vars in the parent query, but they may have to be wrapped in
 * PlaceHolderVars if they need to be forced NULL by outer joins that don't
 * also null the LATERAL subquery.  That's all handled elsewhere.
 *
 * This has to run before deconstruct_jointree, since it might result in
 * creation of PlaceHolderInfos.
 */
void
find_lateral_references(PlannerInfo *root)
{
  Index   rti;

  /* We need do nothing if the query contains no LATERAL RTEs */
  if (!root->hasLateralRTEs)
    return;

  /*
   * Examine all baserels (the rel array has been set up by now).
   */
  for (rti = 1; rti < root->simple_rel_array_size; rti++)
  {
    RelOptInfo *brel = root->simple_rel_array[rti];

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

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

    /*
     * This bit is less obvious than it might look.  We ignore appendrel
     * otherrels and consider only their parent baserels.  In a case where
     * a LATERAL-containing UNION ALL subquery was pulled up, it is the
     * otherrel that is actually going to be in the plan.  However, we
     * want to mark all its lateral references as needed by the parent,
     * because it is the parent's relid that will be used for join
     * planning purposes.  And the parent's RTE will contain all the
     * lateral references we need to know, since the pulled-up member is
     * nothing but a copy of parts of the original RTE's subquery.  We
     * could visit the parent's children instead and transform their
     * references back to the parent's relid, but it would be much more
     * complicated for no real gain.  (Important here is that the child
     * members have not yet received any processing beyond being pulled
     * up.)  Similarly, in appendrels created by inheritance expansion,
     * it's sufficient to look at the parent relation.
     */

    /* ignore RTEs that are "other rels" */
    if (brel->reloptkind != RELOPT_BASEREL)
      continue;

    extract_lateral_references(root, brel, rti);
  }
}

static void
extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex)
{
  RangeTblEntry *rte = root->simple_rte_array[rtindex];
  List     *vars;
  List     *newvars;
  Relids    where_needed;
  ListCell   *lc;

  /* No cross-references are possible if it's not LATERAL */
  if (!rte->lateral)
    return;

  /* Fetch the appropriate variables */
  if (rte->rtekind == RTE_RELATION)
    vars = pull_vars_of_level((Node *) rte->tablesample, 0);
  else if (rte->rtekind == RTE_SUBQUERY)
    vars = pull_vars_of_level((Node *) rte->subquery, 1);
  else if (rte->rtekind == RTE_FUNCTION)
    vars = pull_vars_of_level((Node *) rte->functions, 0);
  else if (rte->rtekind == RTE_TABLEFUNC)
    vars = pull_vars_of_level((Node *) rte->tablefunc, 0);
  else if (rte->rtekind == RTE_VALUES)
    vars = pull_vars_of_level((Node *) rte->values_lists, 0);
  else
  {
    Assert(false);
    return;         /* keep compiler quiet */
  }

  if (vars == NIL)
    return;         /* nothing to do */

  /* Copy each Var (or PlaceHolderVar) and adjust it to match our level */
  newvars = NIL;
  foreach(lc, vars)
  {
    Node     *node = (Node *) lfirst(lc);

    node = copyObject(node);
    if (IsA(node, Var))
    {
      Var      *var = (Var *) node;

      /* Adjustment is easy since it's just one node */
      var->varlevelsup = 0;
    }
    else if (IsA(node, PlaceHolderVar))
    {
      PlaceHolderVar *phv = (PlaceHolderVar *) node;
      int     levelsup = phv->phlevelsup;

      /*
       * Have to work harder to adjust the contained expression too.
       * (Its expression has already been preprocessed by
       * subquery_planner(), so we must not do that again here.)
       */
      if (levelsup != 0)
        IncrementVarSublevelsUp(node, -levelsup, 0);
    }
    else
      Assert(false);
    newvars = lappend(newvars, node);
  }

  list_free(vars);

  /*
   * We mark the Vars as being "needed" at the LATERAL RTE.  This is a bit
   * of a cheat: a more formal approach would be to mark each one as needed
   * at the join of the LATERAL RTE with its source RTE.  But it will work,
   * and it's much less tedious than computing a separate where_needed for
   * each Var.
   */
  where_needed = bms_make_singleton(rtindex);

  /*
   * Push Vars into their source relations' targetlists, and PHVs into
   * root->placeholder_list.
   */
  add_vars_to_targetlist(root, newvars, where_needed);

  /* Remember the lateral references for create_lateral_join_info */
  brel->lateral_vars = newvars;
}

/*
 * create_lateral_join_info
 *    Fill in the per-base-relation direct_lateral_relids, lateral_relids
 *    and lateral_referencers sets.
 */
void
create_lateral_join_info(PlannerInfo *root)
{
  bool    found_laterals = false;
  Index   rti;
  ListCell   *lc;

  /* We need do nothing if the query contains no LATERAL RTEs */
  if (!root->hasLateralRTEs)
    return;

  /* We'll need to have the ph_eval_at values for PlaceHolderVars */
  Assert(root->placeholdersFrozen);

  /*
   * Examine all baserels (the rel array has been set up by now).
   */
  for (rti = 1; rti < root->simple_rel_array_size; rti++)
  {
    RelOptInfo *brel = root->simple_rel_array[rti];
    Relids    lateral_relids;

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

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

    /* ignore RTEs that are "other rels" */
    if (brel->reloptkind != RELOPT_BASEREL)
      continue;

    lateral_relids = NULL;

    /* consider each laterally-referenced Var or PHV */
    foreach(lc, brel->lateral_vars)
    {
      Node     *node = (Node *) lfirst(lc);

      if (IsA(node, Var))
      {
        Var      *var = (Var *) node;

        found_laterals = true;
        lateral_relids = bms_add_member(lateral_relids,
                        var->varno);
      }
      else if (IsA(node, PlaceHolderVar))
      {
        PlaceHolderVar *phv = (PlaceHolderVar *) node;
        PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);

        found_laterals = true;
        lateral_relids = bms_add_members(lateral_relids,
                         phinfo->ph_eval_at);
      }
      else
        Assert(false);
    }

    /* We now have all the simple lateral refs from this rel */
    brel->direct_lateral_relids = lateral_relids;
    brel->lateral_relids = bms_copy(lateral_relids);
  }

  /*
   * Now check for lateral references within PlaceHolderVars, and mark their
   * eval_at rels as having lateral references to the source rels.
   *
   * For a PHV that is due to be evaluated at a baserel, mark its source(s)
   * as direct lateral dependencies of the baserel (adding onto the ones
   * recorded above).  If it's due to be evaluated at a join, mark its
   * source(s) as indirect lateral dependencies of each baserel in the join,
   * ie put them into lateral_relids but not direct_lateral_relids.  This is
   * appropriate because we can't put any such baserel on the outside of a
   * join to one of the PHV's lateral dependencies, but on the other hand we
   * also can't yet join it directly to the dependency.
   */
  foreach(lc, root->placeholder_list)
  {
    PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
    Relids    eval_at = phinfo->ph_eval_at;
    Relids    lateral_refs;
    int     varno;

    if (phinfo->ph_lateral == NULL)
      continue;     /* PHV is uninteresting if no lateral refs */

    found_laterals = true;

    /*
     * Include only baserels not outer joins in the evaluation sites'
     * lateral relids.  This avoids problems when outer join order gets
     * rearranged, and it should still ensure that the lateral values are
     * available when needed.
     */
    lateral_refs = bms_intersect(phinfo->ph_lateral, root->all_baserels);
    Assert(!bms_is_empty(lateral_refs));

    if (bms_get_singleton_member(eval_at, &varno))
    {
      /* Evaluation site is a baserel */
      RelOptInfo *brel = find_base_rel(root, varno);

      brel->direct_lateral_relids =
        bms_add_members(brel->direct_lateral_relids,
                lateral_refs);
      brel->lateral_relids =
        bms_add_members(brel->lateral_relids,
                lateral_refs);
    }
    else
    {
      /* Evaluation site is a join */
      varno = -1;
      while ((varno = bms_next_member(eval_at, varno)) >= 0)
      {
        RelOptInfo *brel = find_base_rel_ignore_join(root, varno);

        if (brel == NULL)
          continue; /* ignore outer joins in eval_at */
        brel->lateral_relids = bms_add_members(brel->lateral_relids,
                             lateral_refs);
      }
    }
  }

  /*
   * If we found no actual lateral references, we're done; but reset the
   * hasLateralRTEs flag to avoid useless work later.
   */
  if (!found_laterals)
  {
    root->hasLateralRTEs = false;
    return;
  }

  /*
   * Calculate the transitive closure of the lateral_relids sets, so that
   * they describe both direct and indirect lateral references.  If relation
   * X references Y laterally, and Y references Z laterally, then we will
   * have to scan X on the inside of a nestloop with Z, so for all intents
   * and purposes X is laterally dependent on Z too.
   *
   * This code is essentially Warshall's algorithm for transitive closure.
   * The outer loop considers each baserel, and propagates its lateral
   * dependencies to those baserels that have a lateral dependency on it.
   */
  for (rti = 1; rti < root->simple_rel_array_size; rti++)
  {
    RelOptInfo *brel = root->simple_rel_array[rti];
    Relids    outer_lateral_relids;
    Index   rti2;

    if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
      continue;

    /* need not consider baserel further if it has no lateral refs */
    outer_lateral_relids = brel->lateral_relids;
    if (outer_lateral_relids == NULL)
      continue;

    /* else scan all baserels */
    for (rti2 = 1; rti2 < root->simple_rel_array_size; rti2++)
    {
      RelOptInfo *brel2 = root->simple_rel_array[rti2];

      if (brel2 == NULL || brel2->reloptkind != RELOPT_BASEREL)
        continue;

      /* if brel2 has lateral ref to brel, propagate brel's refs */
      if (bms_is_member(rti, brel2->lateral_relids))
        brel2->lateral_relids = bms_add_members(brel2->lateral_relids,
                            outer_lateral_relids);
    }
  }

  /*
   * Now that we've identified all lateral references, mark each baserel
   * with the set of relids of rels that reference it laterally (possibly
   * indirectly) --- that is, the inverse mapping of lateral_relids.
   */
  for (rti = 1; rti < root->simple_rel_array_size; rti++)
  {
    RelOptInfo *brel = root->simple_rel_array[rti];
    Relids    lateral_relids;
    int     rti2;

    if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
      continue;

    /* Nothing to do at rels with no lateral refs */
    lateral_relids = brel->lateral_relids;
    if (bms_is_empty(lateral_relids))
      continue;

    /* No rel should have a lateral dependency on itself */
    Assert(!bms_is_member(rti, lateral_relids));

    /* Mark this rel's referencees */
    rti2 = -1;
    while ((rti2 = bms_next_member(lateral_relids, rti2)) >= 0)
    {
      RelOptInfo *brel2 = root->simple_rel_array[rti2];

      if (brel2 == NULL)
        continue;   /* must be an OJ */

      Assert(brel2->reloptkind == RELOPT_BASEREL);
      brel2->lateral_referencers =
        bms_add_member(brel2->lateral_referencers, rti);
    }
  }
}


/*****************************************************************************
 *
 *    JOIN TREE PROCESSING
 *
 *****************************************************************************/

/*
 * deconstruct_jointree
 *    Recursively scan the query's join tree for WHERE and JOIN/ON qual
 *    clauses, and add these to the appropriate restrictinfo and joininfo
 *    lists belonging to base RelOptInfos.  Also, add SpecialJoinInfo nodes
 *    to root->join_info_list for any outer joins appearing in the query tree.
 *    Return a "joinlist" data structure showing the join order decisions
 *    that need to be made by make_one_rel().
 *
 * The "joinlist" result is a list of items that are either RangeTblRef
 * jointree nodes or sub-joinlists.  All the items at the same level of
 * joinlist must be joined in an order to be determined by make_one_rel()
 * (note that legal orders may be constrained by SpecialJoinInfo nodes).
 * A sub-joinlist represents a subproblem to be planned separately. Currently
 * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of
 * subproblems is stopped by join_collapse_limit or from_collapse_limit.
 */
List *
deconstruct_jointree(PlannerInfo *root)
{
  List     *result;
  JoinDomain *top_jdomain;
  List     *item_list = NIL;
  ListCell   *lc;

  /*
   * After this point, no more PlaceHolderInfos may be made, because
   * make_outerjoininfo requires all active placeholders to be present in
   * root->placeholder_list while we crawl up the join tree.
   */
  root->placeholdersFrozen = true;

  /* Fetch the already-created top-level join domain for the query */
  top_jdomain = linitial_node(JoinDomain, root->join_domains);
  top_jdomain->jd_relids = NULL; /* filled during deconstruct_recurse */

  /* Start recursion at top of jointree */
  Assert(root->parse->jointree != NULL &&
       IsA(root->parse->jointree, FromExpr));

  /* These are filled as we scan the jointree */
  root->all_baserels = NULL;
  root->outer_join_rels = NULL;

  /* Perform the initial scan of the jointree */
  result = deconstruct_recurse(root, (Node *) root->parse->jointree,
                 top_jdomain, NULL,
                 &item_list);

  /* Now we can form the value of all_query_rels, too */
  root->all_query_rels = bms_union(root->all_baserels, root->outer_join_rels);

  /* ... which should match what we computed for the top join domain */
  Assert(bms_equal(root->all_query_rels, top_jdomain->jd_relids));

  /* Now scan all the jointree nodes again, and distribute quals */
  foreach(lc, item_list)
  {
    JoinTreeItem *jtitem = (JoinTreeItem *) lfirst(lc);

    deconstruct_distribute(root, jtitem);
  }

  /*
   * If there were any special joins then we may have some postponed LEFT
   * JOIN clauses to deal with.
   */
  if (root->join_info_list)
  {
    foreach(lc, item_list)
    {
      JoinTreeItem *jtitem = (JoinTreeItem *) lfirst(lc);

      if (jtitem->oj_joinclauses != NIL)
        deconstruct_distribute_oj_quals(root, item_list, jtitem);
    }
  }

  /* Don't need the JoinTreeItems any more */
  list_free_deep(item_list);

  return result;
}

/*
 * deconstruct_recurse
 *    One recursion level of deconstruct_jointree's initial jointree scan.
 *
 * jtnode is the jointree node to examine, and parent_domain is the
 * enclosing join domain.  (We must add all base+OJ relids appearing
 * here or below to parent_domain.)  parent_jtitem is the JoinTreeItem
 * for the parent jointree node, or NULL at the top of the recursion.
 *
 * item_list is an in/out parameter: we add a JoinTreeItem struct to
 * that list for each jointree node, in depth-first traversal order.
 * (Hence, after each call, the last list item corresponds to its jtnode.)
 *
 * Return value is the appropriate joinlist for this jointree node.
 */
static List *
deconstruct_recurse(PlannerInfo *root, Node *jtnode,
          JoinDomain *parent_domain,
          JoinTreeItem *parent_jtitem,
          List **item_list)
{
  List     *joinlist;
  JoinTreeItem *jtitem;

  Assert(jtnode != NULL);

  /* Make the new JoinTreeItem, but don't add it to item_list yet */
  jtitem = palloc0_object(JoinTreeItem);
  jtitem->jtnode = jtnode;
  jtitem->jti_parent = parent_jtitem;

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

    /* Fill all_baserels as we encounter baserel jointree nodes */
    root->all_baserels = bms_add_member(root->all_baserels, varno);
    /* This node belongs to parent_domain */
    jtitem->jdomain = parent_domain;
    parent_domain->jd_relids = bms_add_member(parent_domain->jd_relids,
                          varno);
    /* qualscope is just the one RTE */
    jtitem->qualscope = bms_make_singleton(varno);
    /* A single baserel does not create an inner join */
    jtitem->inner_join_rels = NULL;
    joinlist = list_make1(jtnode);
  }
  else if (IsA(jtnode, FromExpr))
  {
    FromExpr   *f = (FromExpr *) jtnode;
    int     remaining;
    ListCell   *l;

    /* This node belongs to parent_domain, as do its children */
    jtitem->jdomain = parent_domain;

    /*
     * Recurse to handle child nodes, and compute output joinlist.  We
     * collapse subproblems into a single joinlist whenever the resulting
     * joinlist wouldn't exceed from_collapse_limit members.  Also, always
     * collapse one-element subproblems, since that won't lengthen the
     * joinlist anyway.
     */
    jtitem->qualscope = NULL;
    jtitem->inner_join_rels = NULL;
    joinlist = NIL;
    remaining = list_length(f->fromlist);
    foreach(l, f->fromlist)
    {
      JoinTreeItem *sub_item;
      List     *sub_joinlist;
      int     sub_members;

      sub_joinlist = deconstruct_recurse(root, lfirst(l),
                         parent_domain,
                         jtitem,
                         item_list);
      sub_item = (JoinTreeItem *) llast(*item_list);
      jtitem->qualscope = bms_add_members(jtitem->qualscope,
                        sub_item->qualscope);
      jtitem->inner_join_rels = sub_item->inner_join_rels;
      sub_members = list_length(sub_joinlist);
      remaining--;
      if (sub_members <= 1 ||
        list_length(joinlist) + sub_members + remaining <= from_collapse_limit)
        joinlist = list_concat(joinlist, sub_joinlist);
      else
        joinlist = lappend(joinlist, sub_joinlist);
    }

    /*
     * A FROM with more than one list element is an inner join subsuming
     * all below it, so we should report inner_join_rels = qualscope. If
     * there was exactly one element, we should (and already did) report
     * whatever its inner_join_rels were.  If there were no elements (is
     * that still possible?) the initialization before the loop fixed it.
     */
    if (list_length(f->fromlist) > 1)
      jtitem->inner_join_rels = jtitem->qualscope;
  }
  else if (IsA(jtnode, JoinExpr))
  {
    JoinExpr   *j = (JoinExpr *) jtnode;
    JoinDomain *child_domain,
           *fj_domain;
    JoinTreeItem *left_item,
           *right_item;
    List     *leftjoinlist,
           *rightjoinlist;

    switch (j->jointype)
    {
      case JOIN_INNER:
        /* This node belongs to parent_domain, as do its children */
        jtitem->jdomain = parent_domain;
        /* Recurse */
        leftjoinlist = deconstruct_recurse(root, j->larg,
                           parent_domain,
                           jtitem,
                           item_list);
        left_item = (JoinTreeItem *) llast(*item_list);
        rightjoinlist = deconstruct_recurse(root, j->rarg,
                          parent_domain,
                          jtitem,
                          item_list);
        right_item = (JoinTreeItem *) llast(*item_list);
        /* Compute qualscope etc */
        jtitem->qualscope = bms_union(left_item->qualscope,
                        right_item->qualscope);
        jtitem->inner_join_rels = jtitem->qualscope;
        jtitem->left_rels = left_item->qualscope;
        jtitem->right_rels = right_item->qualscope;
        /* Inner join adds no restrictions for quals */
        jtitem->nonnullable_rels = NULL;
        break;
      case JOIN_LEFT:
      case JOIN_ANTI:
        /* Make new join domain for my quals and the RHS */
        child_domain = makeNode(JoinDomain);
        child_domain->jd_relids = NULL; /* filled by recursion */
        root->join_domains = lappend(root->join_domains, child_domain);
        jtitem->jdomain = child_domain;
        /* Recurse */
        leftjoinlist = deconstruct_recurse(root, j->larg,
                           parent_domain,
                           jtitem,
                           item_list);
        left_item = (JoinTreeItem *) llast(*item_list);
        rightjoinlist = deconstruct_recurse(root, j->rarg,
                          child_domain,
                          jtitem,
                          item_list);
        right_item = (JoinTreeItem *) llast(*item_list);
        /* Compute join domain contents, qualscope etc */
        parent_domain->jd_relids =
          bms_add_members(parent_domain->jd_relids,
                  child_domain->jd_relids);
        jtitem->qualscope = bms_union(left_item->qualscope,
                        right_item->qualscope);
        /* caution: ANTI join derived from SEMI will lack rtindex */
        if (j->rtindex != 0)
        {
          parent_domain->jd_relids =
            bms_add_member(parent_domain->jd_relids,
                     j->rtindex);
          jtitem->qualscope = bms_add_member(jtitem->qualscope,
                             j->rtindex);
          root->outer_join_rels = bms_add_member(root->outer_join_rels,
                               j->rtindex);
          mark_rels_nulled_by_join(root, j->rtindex,
                       right_item->qualscope);
        }
        jtitem->inner_join_rels = bms_union(left_item->inner_join_rels,
                          right_item->inner_join_rels);
        jtitem->left_rels = left_item->qualscope;
        jtitem->right_rels = right_item->qualscope;
        jtitem->nonnullable_rels = left_item->qualscope;
        break;
      case JOIN_SEMI:
        /* This node belongs to parent_domain, as do its children */
        jtitem->jdomain = parent_domain;
        /* Recurse */
        leftjoinlist = deconstruct_recurse(root, j->larg,
                           parent_domain,
                           jtitem,
                           item_list);
        left_item = (JoinTreeItem *) llast(*item_list);
        rightjoinlist = deconstruct_recurse(root, j->rarg,
                          parent_domain,
                          jtitem,
                          item_list);
        right_item = (JoinTreeItem *) llast(*item_list);
        /* Compute qualscope etc */
        jtitem->qualscope = bms_union(left_item->qualscope,
                        right_item->qualscope);
        /* SEMI join never has rtindex, so don't add to anything */
        Assert(j->rtindex == 0);
        jtitem->inner_join_rels = bms_union(left_item->inner_join_rels,
                          right_item->inner_join_rels);
        jtitem->left_rels = left_item->qualscope;
        jtitem->right_rels = right_item->qualscope;
        /* Semi join adds no restrictions for quals */
        jtitem->nonnullable_rels = NULL;
        break;
      case JOIN_FULL:
        /* The FULL JOIN's quals need their very own domain */
        fj_domain = makeNode(JoinDomain);
        root->join_domains = lappend(root->join_domains, fj_domain);
        jtitem->jdomain = fj_domain;
        /* Recurse, giving each side its own join domain */
        child_domain = makeNode(JoinDomain);
        child_domain->jd_relids = NULL; /* filled by recursion */
        root->join_domains = lappend(root->join_domains, child_domain);
        leftjoinlist = deconstruct_recurse(root, j->larg,
                           child_domain,
                           jtitem,
                           item_list);
        left_item = (JoinTreeItem *) llast(*item_list);
        fj_domain->jd_relids = bms_copy(child_domain->jd_relids);
        child_domain = makeNode(JoinDomain);
        child_domain->jd_relids = NULL; /* filled by recursion */
        root->join_domains = lappend(root->join_domains, child_domain);
        rightjoinlist = deconstruct_recurse(root, j->rarg,
                          child_domain,
                          jtitem,
                          item_list);
        right_item = (JoinTreeItem *) llast(*item_list);
        /* Compute qualscope etc */
        fj_domain->jd_relids = bms_add_members(fj_domain->jd_relids,
                             child_domain->jd_relids);
        parent_domain->jd_relids = bms_add_members(parent_domain->jd_relids,
                               fj_domain->jd_relids);
        jtitem->qualscope = bms_union(left_item->qualscope,
                        right_item->qualscope);
        Assert(j->rtindex != 0);
        parent_domain->jd_relids = bms_add_member(parent_domain->jd_relids,
                              j->rtindex);
        jtitem->qualscope = bms_add_member(jtitem->qualscope,
                           j->rtindex);
        root->outer_join_rels = bms_add_member(root->outer_join_rels,
                             j->rtindex);
        mark_rels_nulled_by_join(root, j->rtindex,
                     left_item->qualscope);
        mark_rels_nulled_by_join(root, j->rtindex,
                     right_item->qualscope);
        jtitem->inner_join_rels = bms_union(left_item->inner_join_rels,
                          right_item->inner_join_rels);
        jtitem->left_rels = left_item->qualscope;
        jtitem->right_rels = right_item->qualscope;
        /* each side is both outer and inner */
        jtitem->nonnullable_rels = jtitem->qualscope;
        break;
      default:
        /* JOIN_RIGHT was eliminated during reduce_outer_joins() */
        elog(ERROR, "unrecognized join type: %d",
           (int) j->jointype);
        leftjoinlist = rightjoinlist = NIL; /* keep compiler quiet */
        break;
    }

    /*
     * Compute the output joinlist.  We fold subproblems together except
     * at a FULL JOIN or where join_collapse_limit would be exceeded.
     */
    if (j->jointype == JOIN_FULL)
    {
      /* force the join order exactly at this node */
      joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
    }
    else if (list_length(leftjoinlist) + list_length(rightjoinlist) <=
         join_collapse_limit)
    {
      /* OK to combine subproblems */
      joinlist = list_concat(leftjoinlist, rightjoinlist);
    }
    else
    {
      /* can't combine, but needn't force join order above here */
      Node     *leftpart,
             *rightpart;

      /* avoid creating useless 1-element sublists */
      if (list_length(leftjoinlist) == 1)
        leftpart = (Node *) linitial(leftjoinlist);
      else
        leftpart = (Node *) leftjoinlist;
      if (list_length(rightjoinlist) == 1)
        rightpart = (Node *) linitial(rightjoinlist);
      else
        rightpart = (Node *) rightjoinlist;
      joinlist = list_make2(leftpart, rightpart);
    }
  }
  else
  {
    elog(ERROR, "unrecognized node type: %d",
       (int) nodeTag(jtnode));
    joinlist = NIL;     /* keep compiler quiet */
  }

  /* Finally, we can add the new JoinTreeItem to item_list */
  *item_list = lappend(*item_list, jtitem);

  return joinlist;
}

/*
 * deconstruct_distribute
 *    Process one jointree node in phase 2 of deconstruct_jointree processing.
 *
 * Distribute quals of the node to appropriate restriction and join lists.
 * In addition, entries will be added to root->join_info_list for outer joins.
 */
static void
deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem)
{
  Node     *jtnode = jtitem->jtnode;

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

    /* Deal with any securityQuals attached to the RTE */
    if (root->qual_security_level > 0)
      process_security_barrier_quals(root,
                       varno,
                       jtitem);
  }
  else if (IsA(jtnode, FromExpr))
  {
    FromExpr   *f = (FromExpr *) jtnode;

    /*
     * Process any lateral-referencing quals that were postponed to this
     * level by children.
     */
    distribute_quals_to_rels(root, jtitem->lateral_clauses,
                 jtitem,
                 NULL,
                 root->qual_security_level,
                 jtitem->qualscope,
                 NULL, NULL, NULL,
                 true, false, false,
                 NULL);

    /*
     * Now process the top-level quals.
     */
    distribute_quals_to_rels(root, (List *) f->quals,
                 jtitem,
                 NULL,
                 root->qual_security_level,
                 jtitem->qualscope,
                 NULL, NULL, NULL,
                 true, false, false,
                 NULL);
  }
  else if (IsA(jtnode, JoinExpr))
  {
    JoinExpr   *j = (JoinExpr *) jtnode;
    Relids    ojscope;
    List     *my_quals;
    SpecialJoinInfo *sjinfo;
    List    **postponed_oj_qual_list;

    /*
     * Include lateral-referencing quals postponed from children in
     * my_quals, so that they'll be handled properly in
     * make_outerjoininfo.  (This is destructive to
     * jtitem->lateral_clauses, but we won't use that again.)
     */
    my_quals = list_concat(jtitem->lateral_clauses,
                 (List *) j->quals);

    /*
     * For an OJ, form the SpecialJoinInfo now, so that we can pass it to
     * distribute_qual_to_rels.  We must compute its ojscope too.
     *
     * Semijoins are a bit of a hybrid: we build a SpecialJoinInfo, but we
     * want ojscope = NULL for distribute_qual_to_rels.
     */
    if (j->jointype != JOIN_INNER)
    {
      sjinfo = make_outerjoininfo(root,
                    jtitem->left_rels,
                    jtitem->right_rels,
                    jtitem->inner_join_rels,
                    j->jointype,
                    j->rtindex,
                    my_quals);
      jtitem->sjinfo = sjinfo;
      if (j->jointype == JOIN_SEMI)
        ojscope = NULL;
      else
        ojscope = bms_union(sjinfo->min_lefthand,
                  sjinfo->min_righthand);
    }
    else
    {
      sjinfo = NULL;
      ojscope = NULL;
    }

    /*
     * If it's a left join with a join clause that is strict for the LHS,
     * then we need to postpone handling of any non-degenerate join
     * clauses, in case the join is able to commute with another left join
     * per identity 3.  (Degenerate clauses need not be postponed, since
     * they will drop down below this join anyway.)
     */
    if (j->jointype == JOIN_LEFT && sjinfo->lhs_strict)
    {
      postponed_oj_qual_list = &jtitem->oj_joinclauses;

      /*
       * Add back any commutable lower OJ relids that were removed from
       * min_lefthand or min_righthand, else the ojscope cross-check in
       * distribute_qual_to_rels will complain.  Since we are postponing
       * processing of non-degenerate clauses, this addition doesn't
       * affect anything except that cross-check.  Real clause
       * positioning decisions will be made later, when we revisit the
       * postponed clauses.
       */
      ojscope = bms_add_members(ojscope, sjinfo->commute_below_l);
      ojscope = bms_add_members(ojscope, sjinfo->commute_below_r);
    }
    else
      postponed_oj_qual_list = NULL;

    /* Process the JOIN's qual clauses */
    distribute_quals_to_rels(root, my_quals,
                 jtitem,
                 sjinfo,
                 root->qual_security_level,
                 jtitem->qualscope,
                 ojscope, jtitem->nonnullable_rels,
                 NULL, /* incompatible_relids */
                 true, /* allow_equivalence */
                 false, false,  /* not clones */
                 postponed_oj_qual_list);

    /* And add the SpecialJoinInfo to join_info_list */
    if (sjinfo)
      root->join_info_list = lappend(root->join_info_list, sjinfo);
  }
  else
  {
    elog(ERROR, "unrecognized node type: %d",
       (int) nodeTag(jtnode));
  }
}

/*
 * process_security_barrier_quals
 *    Transfer security-barrier quals into relation's baserestrictinfo list.
 *
 * The rewriter put any relevant security-barrier conditions into the RTE's
 * securityQuals field, but it's now time to copy them into the rel's
 * baserestrictinfo.
 *
 * In inheritance cases, we only consider quals attached to the parent rel
 * here; they will be valid for all children too, so it's okay to consider
 * them for purposes like equivalence class creation.  Quals attached to
 * individual child rels will be dealt with during path creation.
 */
static void
process_security_barrier_quals(PlannerInfo *root,
                 int rti, JoinTreeItem *jtitem)
{
  RangeTblEntry *rte = root->simple_rte_array[rti];
  Index   security_level = 0;
  ListCell   *lc;

  /*
   * Each element of the securityQuals list has been preprocessed into an
   * implicitly-ANDed list of clauses.  All the clauses in a given sublist
   * should get the same security level, but successive sublists get higher
   * levels.
   */
  foreach(lc, rte->securityQuals)
  {
    List     *qualset = (List *) lfirst(lc);

    /*
     * We cheat to the extent of passing ojscope = qualscope rather than
     * its more logical value of NULL.  The only effect this has is to
     * force a Var-free qual to be evaluated at the rel rather than being
     * pushed up to top of tree, which we don't want.
     */
    distribute_quals_to_rels(root, qualset,
                 jtitem,
                 NULL,
                 security_level,
                 jtitem->qualscope,
                 jtitem->qualscope,
                 NULL,
                 NULL,
                 true,
                 false, false,  /* not clones */
                 NULL);
    security_level++;
  }

  /* Assert that qual_security_level is higher than anything we just used */
  Assert(security_level <= root->qual_security_level);
}

/*
 * mark_rels_nulled_by_join
 *    Fill RelOptInfo.nulling_relids of baserels nulled by this outer join
 *
 * Inputs:
 *  ojrelid: RT index of the join RTE (must not be 0)
 *  lower_rels: the base+OJ Relids syntactically below nullable side of join
 */
static void
mark_rels_nulled_by_join(PlannerInfo *root, Index ojrelid,
             Relids lower_rels)
{
  int     relid = -1;

  while ((relid = bms_next_member(lower_rels, relid)) > 0)
  {
    RelOptInfo *rel = root->simple_rel_array[relid];

    /* ignore the RTE_GROUP RTE */
    if (relid == root->group_rtindex)
      continue;

    if (rel == NULL)   /* must be an outer join */
    {
      Assert(bms_is_member(relid, root->outer_join_rels));
      continue;
    }
    rel->nulling_relids = bms_add_member(rel->nulling_relids, ojrelid);
  }
}

/*
 * make_outerjoininfo
 *    Build a SpecialJoinInfo for the current outer join
 *
 * Inputs:
 *  left_rels: the base+OJ Relids syntactically on outer side of join
 *  right_rels: the base+OJ Relids syntactically on inner side of join
 *  inner_join_rels: base+OJ Relids participating in inner joins below this one
 *  jointype: what it says (must always be LEFT, FULL, SEMI, or ANTI)
 *  ojrelid: RT index of the join RTE (0 for SEMI, which isn't in the RT list)
 *  clause: the outer join's join condition (in implicit-AND format)
 *
 * The node should eventually be appended to root->join_info_list, but we
 * do not do that here.
 *
 * Note: we assume that this function is invoked bottom-up, so that
 * root->join_info_list already contains entries for all outer joins that are
 * syntactically below this one.
 */
static SpecialJoinInfo *
make_outerjoininfo(PlannerInfo *root,
           Relids left_rels, Relids right_rels,
           Relids inner_join_rels,
           JoinType jointype, Index ojrelid,
           List *clause)
{
  SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo);
  Relids    clause_relids;
  Relids    strict_relids;
  Relids    min_lefthand;
  Relids    min_righthand;
  Relids    commute_below_l;
  Relids    commute_below_r;
  ListCell   *l;

  /*
   * We should not see RIGHT JOIN here because left/right were switched
   * earlier
   */
  Assert(jointype != JOIN_INNER);
  Assert(jointype != JOIN_RIGHT);

  /*
   * Presently the executor cannot support FOR [KEY] UPDATE/SHARE marking of
   * rels appearing on the nullable side of an outer join. (It's somewhat
   * unclear what that would mean, anyway: what should we mark when a result
   * row is generated from no element of the nullable relation?)  So,
   * complain if any nullable rel is FOR [KEY] UPDATE/SHARE.
   *
   * You might be wondering why this test isn't made far upstream in the
   * parser.  It's because the parser hasn't got enough info --- consider
   * FOR UPDATE applied to a view.  Only after rewriting and flattening do
   * we know whether the view contains an outer join.
   *
   * We use the original RowMarkClause list here; the PlanRowMark list would
   * list everything.
   */
  foreach(l, root->parse->rowMarks)
  {
    RowMarkClause *rc = (RowMarkClause *) lfirst(l);

    if (bms_is_member(rc->rti, right_rels) ||
      (jointype == JOIN_FULL && bms_is_member(rc->rti, left_rels)))
      ereport(ERROR,
          (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
      /*------
       translator: %s is a SQL row locking clause such as FOR UPDATE */
           errmsg("%s cannot be applied to the nullable side of an outer join",
              LCS_asString(rc->strength))));
  }

  sjinfo->syn_lefthand = left_rels;
  sjinfo->syn_righthand = right_rels;
  sjinfo->jointype = jointype;
  sjinfo->ojrelid = ojrelid;
  /* these fields may get added to later: */
  sjinfo->commute_above_l = NULL;
  sjinfo->commute_above_r = NULL;
  sjinfo->commute_below_l = NULL;
  sjinfo->commute_below_r = NULL;

  compute_semijoin_info(root, sjinfo, clause);

  /* If it's a full join, no need to be very smart */
  if (jointype == JOIN_FULL)
  {
    sjinfo->min_lefthand = bms_copy(left_rels);
    sjinfo->min_righthand = bms_copy(right_rels);
    sjinfo->lhs_strict = false; /* don't care about this */
    return sjinfo;
  }

  /*
   * Retrieve all relids mentioned within the join clause.
   */
  clause_relids = pull_varnos(root, (Node *) clause);

  /*
   * For which relids is the clause strict, ie, it cannot succeed if the
   * rel's columns are all NULL?
   */
  strict_relids = find_nonnullable_rels((Node *) clause);

  /* Remember whether the clause is strict for any LHS relations */
  sjinfo->lhs_strict = bms_overlap(strict_relids, left_rels);

  /*
   * Required LHS always includes the LHS rels mentioned in the clause. We
   * may have to add more rels based on lower outer joins; see below.
   */
  min_lefthand = bms_intersect(clause_relids, left_rels);

  /*
   * Similarly for required RHS.  But here, we must also include any lower
   * inner joins, to ensure we don't try to commute with any of them.
   */
  min_righthand = bms_int_members(bms_union(clause_relids, inner_join_rels),
                  right_rels);

  /*
   * Now check previous outer joins for ordering restrictions.
   *
   * commute_below_l and commute_below_r accumulate the relids of lower
   * outer joins that we think this one can commute with.  These decisions
   * are just tentative within this loop, since we might find an
   * intermediate outer join that prevents commutation.  Surviving relids
   * will get merged into the SpecialJoinInfo structs afterwards.
   */
  commute_below_l = commute_below_r = NULL;
  foreach(l, root->join_info_list)
  {
    SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
    bool    have_unsafe_phvs;

    /*
     * A full join is an optimization barrier: we can't associate into or
     * out of it.  Hence, if it overlaps either LHS or RHS of the current
     * rel, expand that side's min relset to cover the whole full join.
     */
    if (otherinfo->jointype == JOIN_FULL)
    {
      Assert(otherinfo->ojrelid != 0);
      if (bms_overlap(left_rels, otherinfo->syn_lefthand) ||
        bms_overlap(left_rels, otherinfo->syn_righthand))
      {
        min_lefthand = bms_add_members(min_lefthand,
                         otherinfo->syn_lefthand);
        min_lefthand = bms_add_members(min_lefthand,
                         otherinfo->syn_righthand);
        min_lefthand = bms_add_member(min_lefthand,
                        otherinfo->ojrelid);
      }
      if (bms_overlap(right_rels, otherinfo->syn_lefthand) ||
        bms_overlap(right_rels, otherinfo->syn_righthand))
      {
        min_righthand = bms_add_members(min_righthand,
                        otherinfo->syn_lefthand);
        min_righthand = bms_add_members(min_righthand,
                        otherinfo->syn_righthand);
        min_righthand = bms_add_member(min_righthand,
                         otherinfo->ojrelid);
      }
      /* Needn't do anything else with the full join */
      continue;
    }

    /*
     * If our join condition contains any PlaceHolderVars that need to be
     * evaluated above the lower OJ, then we can't commute with it.
     */
    if (otherinfo->ojrelid != 0)
      have_unsafe_phvs =
        contain_placeholder_references_to(root,
                          (Node *) clause,
                          otherinfo->ojrelid);
    else
      have_unsafe_phvs = false;

    /*
     * For a lower OJ in our LHS, if our join condition uses the lower
     * join's RHS and is not strict for that rel, we must preserve the
     * ordering of the two OJs, so add lower OJ's full syntactic relset to
     * min_lefthand.  (We must use its full syntactic relset, not just its
     * min_lefthand + min_righthand.  This is because there might be other
     * OJs below this one that this one can commute with, but we cannot
     * commute with them if we don't with this one.)  Also, if we have
     * unsafe PHVs or the current join is a semijoin or antijoin, we must
     * preserve ordering regardless of strictness.
     *
     * Note: I believe we have to insist on being strict for at least one
     * rel in the lower OJ's min_righthand, not its whole syn_righthand.
     *
     * When we don't need to preserve ordering, check to see if outer join
     * identity 3 applies, and if so, remove the lower OJ's ojrelid from
     * our min_lefthand so that commutation is allowed.
     */
    if (bms_overlap(left_rels, otherinfo->syn_righthand))
    {
      if (bms_overlap(clause_relids, otherinfo->syn_righthand) &&
        (have_unsafe_phvs ||
         jointype == JOIN_SEMI || jointype == JOIN_ANTI ||
         !bms_overlap(strict_relids, otherinfo->min_righthand)))
      {
        /* Preserve ordering */
        min_lefthand = bms_add_members(min_lefthand,
                         otherinfo->syn_lefthand);
        min_lefthand = bms_add_members(min_lefthand,
                         otherinfo->syn_righthand);
        if (otherinfo->ojrelid != 0)
          min_lefthand = bms_add_member(min_lefthand,
                          otherinfo->ojrelid);
      }
      else if (jointype == JOIN_LEFT &&
           otherinfo->jointype == JOIN_LEFT &&
           bms_overlap(strict_relids, otherinfo->min_righthand) &&
           !bms_overlap(clause_relids, otherinfo->syn_lefthand))
      {
        /* Identity 3 applies, so remove the ordering restriction */
        min_lefthand = bms_del_member(min_lefthand, otherinfo->ojrelid);
        /* Record the (still tentative) commutability relationship */
        commute_below_l =
          bms_add_member(commute_below_l, otherinfo->ojrelid);
      }
    }

    /*
     * For a lower OJ in our RHS, if our join condition does not use the
     * lower join's RHS and the lower OJ's join condition is strict, we
     * can interchange the ordering of the two OJs; otherwise we must add
     * the lower OJ's full syntactic relset to min_righthand.
     *
     * Also, if our join condition does not use the lower join's LHS
     * either, force the ordering to be preserved.  Otherwise we can end
     * up with SpecialJoinInfos with identical min_righthands, which can
     * confuse join_is_legal (see discussion in backend/optimizer/README).
     *
     * Also, we must preserve ordering anyway if we have unsafe PHVs, or
     * if either this join or the lower OJ is a semijoin or antijoin.
     *
     * When we don't need to preserve ordering, check to see if outer join
     * identity 3 applies, and if so, remove the lower OJ's ojrelid from
     * our min_righthand so that commutation is allowed.
     */
    if (bms_overlap(right_rels, otherinfo->syn_righthand))
    {
      if (bms_overlap(clause_relids, otherinfo->syn_righthand) ||
        !bms_overlap(clause_relids, otherinfo->min_lefthand) ||
        have_unsafe_phvs ||
        jointype == JOIN_SEMI ||
        jointype == JOIN_ANTI ||
        otherinfo->jointype == JOIN_SEMI ||
        otherinfo->jointype == JOIN_ANTI ||
        !otherinfo->lhs_strict)
      {
        /* Preserve ordering */
        min_righthand = bms_add_members(min_righthand,
                        otherinfo->syn_lefthand);
        min_righthand = bms_add_members(min_righthand,
                        otherinfo->syn_righthand);
        if (otherinfo->ojrelid != 0)
          min_righthand = bms_add_member(min_righthand,
                           otherinfo->ojrelid);
      }
      else if (jointype == JOIN_LEFT &&
           otherinfo->jointype == JOIN_LEFT &&
           otherinfo->lhs_strict)
      {
        /* Identity 3 applies, so remove the ordering restriction */
        min_righthand = bms_del_member(min_righthand,
                         otherinfo->ojrelid);
        /* Record the (still tentative) commutability relationship */
        commute_below_r =
          bms_add_member(commute_below_r, otherinfo->ojrelid);
      }
    }
  }

  /*
   * Examine PlaceHolderVars.  If a PHV is supposed to be evaluated within
   * this join's nullable side, then ensure that min_righthand contains the
   * full eval_at set of the PHV.  This ensures that the PHV actually can be
   * evaluated within the RHS.  Note that this works only because we should
   * already have determined the final eval_at level for any PHV
   * syntactically within this join.
   */
  foreach(l, root->placeholder_list)
  {
    PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
    Relids    ph_syn_level = phinfo->ph_var->phrels;

    /* Ignore placeholder if it didn't syntactically come from RHS */
    if (!bms_is_subset(ph_syn_level, right_rels))
      continue;

    /* Else, prevent join from being formed before we eval the PHV */
    min_righthand = bms_add_members(min_righthand, phinfo->ph_eval_at);
  }

  /*
   * If we found nothing to put in min_lefthand, punt and make it the full
   * LHS, to avoid having an empty min_lefthand which will confuse later
   * processing. (We don't try to be smart about such cases, just correct.)
   * Likewise for min_righthand.
   */
  if (bms_is_empty(min_lefthand))
    min_lefthand = bms_copy(left_rels);
  if (bms_is_empty(min_righthand))
    min_righthand = bms_copy(right_rels);

  /* Now they'd better be nonempty */
  Assert(!bms_is_empty(min_lefthand));
  Assert(!bms_is_empty(min_righthand));
  /* Shouldn't overlap either */
  Assert(!bms_overlap(min_lefthand, min_righthand));

  sjinfo->min_lefthand = min_lefthand;
  sjinfo->min_righthand = min_righthand;

  /*
   * Now that we've identified the correct min_lefthand and min_righthand,
   * any commute_below_l or commute_below_r relids that have not gotten
   * added back into those sets (due to intervening outer joins) are indeed
   * commutable with this one.
   *
   * First, delete any subsequently-added-back relids (this is easier than
   * maintaining commute_below_l/r precisely through all the above).
   */
  commute_below_l = bms_del_members(commute_below_l, min_lefthand);
  commute_below_r = bms_del_members(commute_below_r, min_righthand);

  /* Anything left? */
  if (commute_below_l || commute_below_r)
  {
    /* Yup, so we must update the derived data in the SpecialJoinInfos */
    sjinfo->commute_below_l = commute_below_l;
    sjinfo->commute_below_r = commute_below_r;
    foreach(l, root->join_info_list)
    {
      SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);

      if (bms_is_member(otherinfo->ojrelid, commute_below_l))
        otherinfo->commute_above_l =
          bms_add_member(otherinfo->commute_above_l, ojrelid);
      else if (bms_is_member(otherinfo->ojrelid, commute_below_r))
        otherinfo->commute_above_r =
          bms_add_member(otherinfo->commute_above_r, ojrelid);
    }
  }

  return sjinfo;
}

/*
 * compute_semijoin_info
 *    Fill semijoin-related fields of a new SpecialJoinInfo
 *
 * Note: this relies on only the jointype and syn_righthand fields of the
 * SpecialJoinInfo; the rest may not be set yet.
 */
static void
compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *clause)
{
  List     *semi_operators;
  List     *semi_rhs_exprs;
  bool    all_btree;
  bool    all_hash;
  ListCell   *lc;

  /* Initialize semijoin-related fields in case we can't unique-ify */
  sjinfo->semi_can_btree = false;
  sjinfo->semi_can_hash = false;
  sjinfo->semi_operators = NIL;
  sjinfo->semi_rhs_exprs = NIL;

  /* Nothing more to do if it's not a semijoin */
  if (sjinfo->jointype != JOIN_SEMI)
    return;

  /*
   * Look to see whether the semijoin's join quals consist of AND'ed
   * equality operators, with (only) RHS variables on only one side of each
   * one.  If so, we can figure out how to enforce uniqueness for the RHS.
   *
   * Note that the input clause list is the list of quals that are
   * *syntactically* associated with the semijoin, which in practice means
   * the synthesized comparison list for an IN or the WHERE of an EXISTS.
   * Particularly in the latter case, it might contain clauses that aren't
   * *semantically* associated with the join, but refer to just one side or
   * the other.  We can ignore such clauses here, as they will just drop
   * down to be processed within one side or the other.  (It is okay to
   * consider only the syntactically-associated clauses here because for a
   * semijoin, no higher-level quals could refer to the RHS, and so there
   * can be no other quals that are semantically associated with this join.
   * We do things this way because it is useful to have the set of potential
   * unique-ification expressions before we can extract the list of quals
   * that are actually semantically associated with the particular join.)
   *
   * Note that the semi_operators list consists of the joinqual operators
   * themselves (but commuted if needed to put the RHS value on the right).
   * These could be cross-type operators, in which case the operator
   * actually needed for uniqueness is a related single-type operator. We
   * assume here that that operator will be available from the btree or hash
   * opclass when the time comes ... if not, create_unique_plan() will fail.
   */
  semi_operators = NIL;
  semi_rhs_exprs = NIL;
  all_btree = true;
  all_hash = enable_hashagg;  /* don't consider hash if not enabled */
  foreach(lc, clause)
  {
    OpExpr     *op = (OpExpr *) lfirst(lc);
    Oid     opno;
    Node     *left_expr;
    Node     *right_expr;
    Relids    left_varnos;
    Relids    right_varnos;
    Relids    all_varnos;
    Oid     opinputtype;

    /* Is it a binary opclause? */
    if (!IsA(op, OpExpr) ||
      list_length(op->args) != 2)
    {
      /* No, but does it reference both sides? */
      all_varnos = pull_varnos(root, (Node *) op);
      if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
        bms_is_subset(all_varnos, sjinfo->syn_righthand))
      {
        /*
         * Clause refers to only one rel, so ignore it --- unless it
         * contains volatile functions, in which case we'd better
         * punt.
         */
        if (contain_volatile_functions((Node *) op))
          return;
        continue;
      }
      /* Non-operator clause referencing both sides, must punt */
      return;
    }

    /* Extract data from binary opclause */
    opno = op->opno;
    left_expr = linitial(op->args);
    right_expr = lsecond(op->args);
    left_varnos = pull_varnos(root, left_expr);
    right_varnos = pull_varnos(root, right_expr);
    all_varnos = bms_union(left_varnos, right_varnos);
    opinputtype = exprType(left_expr);

    /* Does it reference both sides? */
    if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
      bms_is_subset(all_varnos, sjinfo->syn_righthand))
    {
      /*
       * Clause refers to only one rel, so ignore it --- unless it
       * contains volatile functions, in which case we'd better punt.
       */
      if (contain_volatile_functions((Node *) op))
        return;
      continue;
    }

    /* check rel membership of arguments */
    if (!bms_is_empty(right_varnos) &&
      bms_is_subset(right_varnos, sjinfo->syn_righthand) &&
      !bms_overlap(left_varnos, sjinfo->syn_righthand))
    {
      /* typical case, right_expr is RHS variable */
    }
    else if (!bms_is_empty(left_varnos) &&
         bms_is_subset(left_varnos, sjinfo->syn_righthand) &&
         !bms_overlap(right_varnos, sjinfo->syn_righthand))
    {
      /* flipped case, left_expr is RHS variable */
      opno = get_commutator(opno);
      if (!OidIsValid(opno))
        return;
      right_expr = left_expr;
    }
    else
    {
      /* mixed membership of args, punt */
      return;
    }

    /* all operators must be btree equality or hash equality */
    if (all_btree)
    {
      /* oprcanmerge is considered a hint... */
      if (!op_mergejoinable(opno, opinputtype) ||
        get_mergejoin_opfamilies(opno) == NIL)
        all_btree = false;
    }
    if (all_hash)
    {
      /* ... but oprcanhash had better be correct */
      if (!op_hashjoinable(opno, opinputtype))
        all_hash = false;
    }
    if (!(all_btree || all_hash))
      return;

    /*
     * Ensure the RHS expression exposes the join's input collation (its
     * type should be OK already); see comments for
     * canonicalize_ec_expression.
     */
    right_expr = (Node *) canonicalize_ec_expression((Expr *) copyObject(right_expr),
                             exprType(right_expr),
                             op->inputcollid);

    /* so far so good, keep building lists */
    semi_operators = lappend_oid(semi_operators, opno);
    semi_rhs_exprs = lappend(semi_rhs_exprs, right_expr);
  }

  /* Punt if we didn't find at least one column to unique-ify */
  if (semi_rhs_exprs == NIL)
    return;

  /*
   * The expressions we'd need to unique-ify mustn't be volatile.
   */
  if (contain_volatile_functions((Node *) semi_rhs_exprs))
    return;

  /*
   * If we get here, we can unique-ify the semijoin's RHS using at least one
   * of sorting and hashing.  Save the information about how to do that.
   */
  sjinfo->semi_can_btree = all_btree;
  sjinfo->semi_can_hash = all_hash;
  sjinfo->semi_operators = semi_operators;
  sjinfo->semi_rhs_exprs = semi_rhs_exprs;
}

/*
 * deconstruct_distribute_oj_quals
 *    Adjust LEFT JOIN quals to be suitable for commuted-left-join cases,
 *    then push them into the joinqual lists and EquivalenceClass structures.
 *
 * This runs immediately after we've completed the deconstruct_distribute scan.
 * jtitems contains all the JoinTreeItems (in depth-first order), and jtitem
 * is one that has postponed oj_joinclauses to deal with.
 */
static void
deconstruct_distribute_oj_quals(PlannerInfo *root,
                List *jtitems,
                JoinTreeItem *jtitem)
{
  SpecialJoinInfo *sjinfo = jtitem->sjinfo;
  Relids    qualscope,
        ojscope,
        nonnullable_rels;

  /* Recompute syntactic and semantic scopes of this left join */
  qualscope = bms_union(sjinfo->syn_lefthand, sjinfo->syn_righthand);
  qualscope = bms_add_member(qualscope, sjinfo->ojrelid);
  ojscope = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
  nonnullable_rels = sjinfo->syn_lefthand;

  /*
   * If this join can commute with any other ones per outer-join identity 3,
   * and it is the one providing the join clause with flexible semantics,
   * then we have to generate variants of the join clause with different
   * nullingrels labeling.  Otherwise, just push out the postponed clause
   * as-is.
   */
  Assert(sjinfo->lhs_strict); /* else we shouldn't be here */
  if (sjinfo->commute_above_r || sjinfo->commute_below_l)
  {
    Relids    joins_above;
    Relids    joins_below;
    Relids    incompatible_joins;
    Relids    joins_so_far;
    List     *quals;
    int     save_last_rinfo_serial;
    ListCell   *lc;

    /* Identify the outer joins this one commutes with */
    joins_above = sjinfo->commute_above_r;
    joins_below = sjinfo->commute_below_l;

    /*
     * Generate qual variants with different sets of nullingrels bits.
     *
     * We only need bit-sets that correspond to the successively less
     * deeply syntactically-nested subsets of this join and its
     * commutators.  That's true first because obviously only those forms
     * of the Vars and PHVs could appear elsewhere in the query, and
     * second because the outer join identities do not provide a way to
     * re-order such joins in a way that would require different marking.
     * (That is, while the current join may commute with several others,
     * none of those others can commute with each other.)  To visit the
     * interesting joins in syntactic nesting order, we rely on the
     * jtitems list to be ordered that way.
     *
     * We first strip out all the nullingrels bits corresponding to
     * commuting joins below this one, and then successively put them back
     * as we crawl up the join stack.
     */
    quals = jtitem->oj_joinclauses;
    if (!bms_is_empty(joins_below))
      quals = (List *) remove_nulling_relids((Node *) quals,
                           joins_below,
                           NULL);

    /*
     * We'll need to mark the lower versions of the quals as not safe to
     * apply above not-yet-processed joins of the stack.  This prevents
     * possibly applying a cloned qual at the wrong join level.
     */
    incompatible_joins = bms_union(joins_below, joins_above);
    incompatible_joins = bms_add_member(incompatible_joins,
                      sjinfo->ojrelid);

    /*
     * Each time we produce RestrictInfo(s) from these quals, reset the
     * last_rinfo_serial counter, so that the RestrictInfos for the "same"
     * qual condition get identical serial numbers.  (This relies on the
     * fact that we're not changing the qual list in any way that'd affect
     * the number of RestrictInfos built from it.) This'll allow us to
     * detect duplicative qual usage later.
     */
    save_last_rinfo_serial = root->last_rinfo_serial;

    joins_so_far = NULL;
    foreach(lc, jtitems)
    {
      JoinTreeItem *otherjtitem = (JoinTreeItem *) lfirst(lc);
      SpecialJoinInfo *othersj = otherjtitem->sjinfo;
      bool    below_sjinfo = false;
      bool    above_sjinfo = false;
      Relids    this_qualscope;
      Relids    this_ojscope;
      bool    allow_equivalence,
            has_clone,
            is_clone;

      if (othersj == NULL)
        continue;   /* not an outer-join item, ignore */

      if (bms_is_member(othersj->ojrelid, joins_below))
      {
        /* othersj commutes with sjinfo from below left */
        below_sjinfo = true;
      }
      else if (othersj == sjinfo)
      {
        /* found our join in syntactic order */
        Assert(bms_equal(joins_so_far, joins_below));
      }
      else if (bms_is_member(othersj->ojrelid, joins_above))
      {
        /* othersj commutes with sjinfo from above */
        above_sjinfo = true;
      }
      else
      {
        /* othersj is not relevant, ignore */
        continue;
      }

      /* Reset serial counter for this version of the quals */
      root->last_rinfo_serial = save_last_rinfo_serial;

      /*
       * When we are looking at joins above sjinfo, we are envisioning
       * pushing sjinfo to above othersj, so add othersj's nulling bit
       * before distributing the quals.  We should add it to Vars coming
       * from the current join's LHS: we want to transform the second
       * form of OJ identity 3 to the first form, in which Vars of
       * relation B will appear nulled by the syntactically-upper OJ
       * within the Pbc clause, but those of relation C will not.  (In
       * the notation used by optimizer/README, we're converting a qual
       * of the form Pbc to Pb*c.)  Of course, we must also remove that
       * bit from the incompatible_joins value, else we'll make a qual
       * that can't be placed anywhere.
       */
      if (above_sjinfo)
      {
        quals = (List *)
          add_nulling_relids((Node *) quals,
                     sjinfo->syn_lefthand,
                     bms_make_singleton(othersj->ojrelid));
        incompatible_joins = bms_del_member(incompatible_joins,
                          othersj->ojrelid);
      }

      /* Compute qualscope and ojscope for this join level */
      this_qualscope = bms_union(qualscope, joins_so_far);
      this_ojscope = bms_union(ojscope, joins_so_far);
      if (above_sjinfo)
      {
        /* othersj is not yet in joins_so_far, but we need it */
        this_qualscope = bms_add_member(this_qualscope,
                        othersj->ojrelid);
        this_ojscope = bms_add_member(this_ojscope,
                        othersj->ojrelid);
        /* sjinfo is in joins_so_far, and we don't want it */
        this_ojscope = bms_del_member(this_ojscope,
                        sjinfo->ojrelid);
      }

      /*
       * We generate EquivalenceClasses only from the first form of the
       * quals, with the fewest nullingrels bits set.  An EC made from
       * this version of the quals can be useful below the outer-join
       * nest, whereas versions with some nullingrels bits set would not
       * be.  We cannot generate ECs from more than one version, or
       * we'll make nonsensical conclusions that Vars with nullingrels
       * bits set are equal to their versions without.  Fortunately,
       * such ECs wouldn't be very useful anyway, because they'd equate
       * values not observable outside the join nest.  (See
       * optimizer/README.)
       *
       * The first form of the quals is also the only one marked as
       * has_clone rather than is_clone.
       */
      allow_equivalence = (joins_so_far == NULL);
      has_clone = allow_equivalence;
      is_clone = !has_clone;

      distribute_quals_to_rels(root, quals,
                   otherjtitem,
                   sjinfo,
                   root->qual_security_level,
                   this_qualscope,
                   this_ojscope, nonnullable_rels,
                   bms_copy(incompatible_joins),
                   allow_equivalence,
                   has_clone,
                   is_clone,
                   NULL); /* no more postponement */

      /*
       * Adjust qual nulling bits for next level up, if needed.  We
       * don't want to put sjinfo's own bit in at all, and if we're
       * above sjinfo then we did it already.  Here, we should mark all
       * Vars coming from the lower join's RHS.  (Again, we are
       * converting a qual of the form Pbc to Pb*c, but now we are
       * putting back bits that were there in the parser output and were
       * temporarily stripped above.)  Update incompatible_joins too.
       */
      if (below_sjinfo)
      {
        quals = (List *)
          add_nulling_relids((Node *) quals,
                     othersj->syn_righthand,
                     bms_make_singleton(othersj->ojrelid));
        incompatible_joins = bms_del_member(incompatible_joins,
                          othersj->ojrelid);
      }

      /* ... and track joins processed so far */
      joins_so_far = bms_add_member(joins_so_far, othersj->ojrelid);
    }
  }
  else
  {
    /* No commutation possible, just process the postponed clauses */
    distribute_quals_to_rels(root, jtitem->oj_joinclauses,
                 jtitem,
                 sjinfo,
                 root->qual_security_level,
                 qualscope,
                 ojscope, nonnullable_rels,
                 NULL, /* incompatible_relids */
                 true, /* allow_equivalence */
                 false, false,  /* not clones */
                 NULL); /* no more postponement */
  }
}


/*****************************************************************************
 *
 *    QUALIFICATIONS
 *
 *****************************************************************************/

/*
 * distribute_quals_to_rels
 *    Convenience routine to apply distribute_qual_to_rels to each element
 *    of an AND'ed list of clauses.
 */
static void
distribute_quals_to_rels(PlannerInfo *root, List *clauses,
             JoinTreeItem *jtitem,
             SpecialJoinInfo *sjinfo,
             Index security_level,
             Relids qualscope,
             Relids ojscope,
             Relids outerjoin_nonnullable,
             Relids incompatible_relids,
             bool allow_equivalence,
             bool has_clone,
             bool is_clone,
             List **postponed_oj_qual_list)
{
  ListCell   *lc;

  foreach(lc, clauses)
  {
    Node     *clause = (Node *) lfirst(lc);

    distribute_qual_to_rels(root, clause,
                jtitem,
                sjinfo,
                security_level,
                qualscope,
                ojscope,
                outerjoin_nonnullable,
                incompatible_relids,
                allow_equivalence,
                has_clone,
                is_clone,
                postponed_oj_qual_list);
  }
}

/*
 * distribute_qual_to_rels
 *    Add clause information to either the baserestrictinfo or joininfo list
 *    (depending on whether the clause is a join) of each base relation
 *    mentioned in the clause.  A RestrictInfo node is created and added to
 *    the appropriate list for each rel.  Alternatively, if the clause uses a
 *    mergejoinable operator, enter its left- and right-side expressions into
 *    the query's EquivalenceClasses.
 *
 * In some cases, quals will be added to parent jtitems' lateral_clauses
 * or to postponed_oj_qual_list instead of being processed right away.
 * These will be dealt with in later calls of deconstruct_distribute.
 *
 * 'clause': the qual clause to be distributed
 * 'jtitem': the JoinTreeItem for the containing jointree node
 * 'sjinfo': join's SpecialJoinInfo (NULL for an inner join or WHERE clause)
 * 'security_level': security_level to assign to the qual
 * 'qualscope': set of base+OJ rels the qual's syntactic scope covers
 * 'ojscope': NULL if not an outer-join qual, else the minimum set of base+OJ
 *    rels needed to form this join
 * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of
 *    base+OJ rels appearing on the outer (nonnullable) side of the join
 *    (for FULL JOIN this includes both sides of the join, and must in fact
 *    equal qualscope)
 * 'incompatible_relids': the set of outer-join relid(s) that must not be
 *    computed below this qual.  We only bother to compute this for
 *    "clone" quals, otherwise it can be left NULL.
 * 'allow_equivalence': true if it's okay to convert clause into an
 *    EquivalenceClass
 * 'has_clone': has_clone property to assign to the qual
 * 'is_clone': is_clone property to assign to the qual
 * 'postponed_oj_qual_list': if not NULL, non-degenerate outer join clauses
 *    should be added to this list instead of being processed (list entries
 *    are just the bare clauses)
 *
 * 'qualscope' identifies what level of JOIN the qual came from syntactically.
 * 'ojscope' is needed if we decide to force the qual up to the outer-join
 * level, which will be ojscope not necessarily qualscope.
 */
static void
distribute_qual_to_rels(PlannerInfo *root, Node *clause,
            JoinTreeItem *jtitem,
            SpecialJoinInfo *sjinfo,
            Index security_level,
            Relids qualscope,
            Relids ojscope,
            Relids outerjoin_nonnullable,
            Relids incompatible_relids,
            bool allow_equivalence,
            bool has_clone,
            bool is_clone,
            List **postponed_oj_qual_list)
{
  Relids    relids;
  bool    is_pushed_down;
  bool    pseudoconstant = false;
  bool    maybe_equivalence;
  bool    maybe_outer_join;
  RestrictInfo *restrictinfo;

  /*
   * Retrieve all relids mentioned within the clause.
   */
  relids = pull_varnos(root, clause);

  /*
   * In ordinary SQL, a WHERE or JOIN/ON clause can't reference any rels
   * that aren't within its syntactic scope; however, if we pulled up a
   * LATERAL subquery then we might find such references in quals that have
   * been pulled up.  We need to treat such quals as belonging to the join
   * level that includes every rel they reference.  Although we could make
   * pull_up_subqueries() place such quals correctly to begin with, it's
   * easier to handle it here.  When we find a clause that contains Vars
   * outside its syntactic scope, locate the nearest parent join level that
   * includes all the required rels and add the clause to that level's
   * lateral_clauses list.  We'll process it when we reach that join level.
   */
  if (!bms_is_subset(relids, qualscope))
  {
    JoinTreeItem *pitem;

    Assert(root->hasLateralRTEs); /* shouldn't happen otherwise */
    Assert(sjinfo == NULL); /* mustn't postpone past outer join */
    for (pitem = jtitem->jti_parent; pitem; pitem = pitem->jti_parent)
    {
      if (bms_is_subset(relids, pitem->qualscope))
      {
        pitem->lateral_clauses = lappend(pitem->lateral_clauses,
                         clause);
        return;
      }

      /*
       * We should not be postponing any quals past an outer join.  If
       * this Assert fires, pull_up_subqueries() messed up.
       */
      Assert(pitem->sjinfo == NULL);
    }
    elog(ERROR, "failed to postpone qual containing lateral reference");
  }

  /*
   * If it's an outer-join clause, also check that relids is a subset of
   * ojscope.  (This should not fail if the syntactic scope check passed.)
   */
  if (ojscope && !bms_is_subset(relids, ojscope))
    elog(ERROR, "JOIN qualification cannot refer to other relations");

  /*
   * If the clause is variable-free, our normal heuristic for pushing it
   * down to just the mentioned rels doesn't work, because there are none.
   *
   * If the clause is an outer-join clause, we must force it to the OJ's
   * semantic level to preserve semantics.
   *
   * Otherwise, when the clause contains volatile functions, we force it to
   * be evaluated at its original syntactic level.  This preserves the
   * expected semantics.
   *
   * When the clause contains no volatile functions either, it is actually a
   * pseudoconstant clause that will not change value during any one
   * execution of the plan, and hence can be used as a one-time qual in a
   * gating Result plan node.  We put such a clause into the regular
   * RestrictInfo lists for the moment, but eventually createplan.c will
   * pull it out and make a gating Result node immediately above whatever
   * plan node the pseudoconstant clause is assigned to.  It's usually best
   * to put a gating node as high in the plan tree as possible.
   */
  if (bms_is_empty(relids))
  {
    if (ojscope)
    {
      /* clause is attached to outer join, eval it there */
      relids = bms_copy(ojscope);
      /* mustn't use as gating qual, so don't mark pseudoconstant */
    }
    else if (contain_volatile_functions(clause))
    {
      /* eval at original syntactic level */
      relids = bms_copy(qualscope);
      /* again, can't mark pseudoconstant */
    }
    else
    {
      /*
       * If we are in the top-level join domain, we can push the qual to
       * the top of the plan tree.  Otherwise, be conservative and eval
       * it at original syntactic level.  (Ideally we'd push it to the
       * top of the current join domain in all cases, but that causes
       * problems if we later rearrange outer-join evaluation order.
       * Pseudoconstant quals below the top level are a pretty odd case,
       * so it's not clear that it's worth working hard on.)
       */
      if (jtitem->jdomain == (JoinDomain *) linitial(root->join_domains))
        relids = bms_copy(jtitem->jdomain->jd_relids);
      else
        relids = bms_copy(qualscope);
      /* mark as gating qual */
      pseudoconstant = true;
      /* tell createplan.c to check for gating quals */
      root->hasPseudoConstantQuals = true;
    }
  }

  /*----------
   * Check to see if clause application must be delayed by outer-join
   * considerations.
   *
   * A word about is_pushed_down: we mark the qual as "pushed down" if
   * it is (potentially) applicable at a level different from its original
   * syntactic level.  This flag is used to distinguish OUTER JOIN ON quals
   * from other quals pushed down to the same joinrel.  The rules are:
   *    WHERE quals and INNER JOIN quals: is_pushed_down = true.
   *    Non-degenerate OUTER JOIN quals: is_pushed_down = false.
   *    Degenerate OUTER JOIN quals: is_pushed_down = true.
   * A "degenerate" OUTER JOIN qual is one that doesn't mention the
   * non-nullable side, and hence can be pushed down into the nullable side
   * without changing the join result.  It is correct to treat it as a
   * regular filter condition at the level where it is evaluated.
   *
   * Note: it is not immediately obvious that a simple boolean is enough
   * for this: if for some reason we were to attach a degenerate qual to
   * its original join level, it would need to be treated as an outer join
   * qual there.  However, this cannot happen, because all the rels the
   * clause mentions must be in the outer join's min_righthand, therefore
   * the join it needs must be formed before the outer join; and we always
   * attach quals to the lowest level where they can be evaluated.  But
   * if we were ever to re-introduce a mechanism for delaying evaluation
   * of "expensive" quals, this area would need work.
   *
   * Note: generally, use of is_pushed_down has to go through the macro
   * RINFO_IS_PUSHED_DOWN, because that flag alone is not always sufficient
   * to tell whether a clause must be treated as pushed-down in context.
   * This seems like another reason why it should perhaps be rethought.
   *----------
   */
  if (bms_overlap(relids, outerjoin_nonnullable))
  {
    /*
     * The qual is attached to an outer join and mentions (some of the)
     * rels on the nonnullable side, so it's not degenerate.  If the
     * caller wants to postpone handling such clauses, just add it to
     * postponed_oj_qual_list and return.  (The work we've done up to here
     * will have to be redone later, but there's not much of it.)
     */
    if (postponed_oj_qual_list != NULL)
    {
      *postponed_oj_qual_list = lappend(*postponed_oj_qual_list, clause);
      return;
    }

    /*
     * We can't use such a clause to deduce equivalence (the left and
     * right sides might be unequal above the join because one of them has
     * gone to NULL) ... but we might be able to use it for more limited
     * deductions, if it is mergejoinable.  So consider adding it to the
     * lists of set-aside outer-join clauses.
     */
    is_pushed_down = false;
    maybe_equivalence = false;
    maybe_outer_join = true;

    /*
     * Now force the qual to be evaluated exactly at the level of joining
     * corresponding to the outer join.  We cannot let it get pushed down
     * into the nonnullable side, since then we'd produce no output rows,
     * rather than the intended single null-extended row, for any
     * nonnullable-side rows failing the qual.
     */
    Assert(ojscope);
    relids = ojscope;
    Assert(!pseudoconstant);
  }
  else
  {
    /*
     * Normal qual clause or degenerate outer-join clause.  Either way, we
     * can mark it as pushed-down.
     */
    is_pushed_down = true;

    /* Feed qual to the equivalence machinery, if allowed by caller */
    maybe_equivalence = allow_equivalence;

    /*
     * Since it doesn't mention the LHS, it's certainly not useful as a
     * set-aside OJ clause, even if it's in an OJ.
     */
    maybe_outer_join = false;
  }

  /*
   * Build the RestrictInfo node itself.
   */
  restrictinfo = make_restrictinfo(root,
                   (Expr *) clause,
                   is_pushed_down,
                   has_clone,
                   is_clone,
                   pseudoconstant,
                   security_level,
                   relids,
                   incompatible_relids,
                   outerjoin_nonnullable);

  /*
   * If it's a join clause, add vars used in the clause to targetlists of
   * their relations, so that they will be emitted by the plan nodes that
   * scan those relations (else they won't be available at the join node!).
   *
   * Normally we mark the vars as needed at the join identified by "relids".
   * However, if this is a clone clause then ignore the outer-join relids in
   * that set.  Otherwise, vars appearing in a cloned clause would end up
   * marked as having to propagate to the highest one of the commuting
   * joins, which would often be an overestimate.  For such clauses, correct
   * var propagation is ensured by making ojscope include input rels from
   * both sides of the join.
   *
   * Note: if the clause gets absorbed into an EquivalenceClass then this
   * may be unnecessary, but for now we have to do it to cover the case
   * where the EC becomes ec_broken and we end up reinserting the original
   * clauses into the plan.
   */
  if (bms_membership(relids) == BMS_MULTIPLE)
  {
    List     *vars = pull_var_clause(clause,
                       PVC_RECURSE_AGGREGATES |
                       PVC_RECURSE_WINDOWFUNCS |
                       PVC_INCLUDE_PLACEHOLDERS);
    Relids    where_needed;

    if (is_clone)
      where_needed = bms_intersect(relids, root->all_baserels);
    else
      where_needed = relids;
    add_vars_to_targetlist(root, vars, where_needed);
    list_free(vars);
  }

  /*
   * We check "mergejoinability" of every clause, not only join clauses,
   * because we want to know about equivalences between vars of the same
   * relation, or between vars and consts.
   */
  check_mergejoinable(restrictinfo);

  /*
   * If it is a true equivalence clause, send it to the EquivalenceClass
   * machinery.  We do *not* attach it directly to any restriction or join
   * lists.  The EC code will propagate it to the appropriate places later.
   *
   * If the clause has a mergejoinable operator, yet isn't an equivalence
   * because it is an outer-join clause, the EC code may still be able to do
   * something with it.  We add it to appropriate lists for further
   * consideration later.  Specifically:
   *
   * If it is a left or right outer-join qualification that relates the two
   * sides of the outer join (no funny business like leftvar1 = leftvar2 +
   * rightvar), we add it to root->left_join_clauses or
   * root->right_join_clauses according to which side the nonnullable
   * variable appears on.
   *
   * If it is a full outer-join qualification, we add it to
   * root->full_join_clauses.  (Ideally we'd discard cases that aren't
   * leftvar = rightvar, as we do for left/right joins, but this routine
   * doesn't have the info needed to do that; and the current usage of the
   * full_join_clauses list doesn't require that, so it's not currently
   * worth complicating this routine's API to make it possible.)
   *
   * If none of the above hold, pass it off to
   * distribute_restrictinfo_to_rels().
   *
   * In all cases, it's important to initialize the left_ec and right_ec
   * fields of a mergejoinable clause, so that all possibly mergejoinable
   * expressions have representations in EquivalenceClasses.  If
   * process_equivalence is successful, it will take care of that;
   * otherwise, we have to call initialize_mergeclause_eclasses to do it.
   */
  if (restrictinfo->mergeopfamilies)
  {
    if (maybe_equivalence)
    {
      if (process_equivalence(root, &restrictinfo, jtitem->jdomain))
        return;
      /* EC rejected it, so set left_ec/right_ec the hard way ... */
      if (restrictinfo->mergeopfamilies) /* EC might have changed this */
        initialize_mergeclause_eclasses(root, restrictinfo);
      /* ... and fall through to distribute_restrictinfo_to_rels */
    }
    else if (maybe_outer_join && restrictinfo->can_join)
    {
      /* we need to set up left_ec/right_ec the hard way */
      initialize_mergeclause_eclasses(root, restrictinfo);
      /* now see if it should go to any outer-join lists */
      Assert(sjinfo != NULL);
      if (bms_is_subset(restrictinfo->left_relids,
                outerjoin_nonnullable) &&
        !bms_overlap(restrictinfo->right_relids,
               outerjoin_nonnullable))
      {
        /* we have outervar = innervar */
        OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo);

        ojcinfo->rinfo = restrictinfo;
        ojcinfo->sjinfo = sjinfo;
        root->left_join_clauses = lappend(root->left_join_clauses,
                          ojcinfo);
        return;
      }
      if (bms_is_subset(restrictinfo->right_relids,
                outerjoin_nonnullable) &&
        !bms_overlap(restrictinfo->left_relids,
               outerjoin_nonnullable))
      {
        /* we have innervar = outervar */
        OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo);

        ojcinfo->rinfo = restrictinfo;
        ojcinfo->sjinfo = sjinfo;
        root->right_join_clauses = lappend(root->right_join_clauses,
                           ojcinfo);
        return;
      }
      if (sjinfo->jointype == JOIN_FULL)
      {
        /* FULL JOIN (above tests cannot match in this case) */
        OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo);

        ojcinfo->rinfo = restrictinfo;
        ojcinfo->sjinfo = sjinfo;
        root->full_join_clauses = lappend(root->full_join_clauses,
                          ojcinfo);
        return;
      }
      /* nope, so fall through to distribute_restrictinfo_to_rels */
    }
    else
    {
      /* we still need to set up left_ec/right_ec */
      initialize_mergeclause_eclasses(root, restrictinfo);
    }
  }

  /* No EC special case applies, so push it into the clause lists */
  distribute_restrictinfo_to_rels(root, restrictinfo);
}

/*
 * add_base_clause_to_rel
 *    Add 'restrictinfo' as a baserestrictinfo to the base relation denoted
 *    by 'relid'.  We offer some simple prechecks to try to determine if the
 *    qual is always true, in which case we ignore it rather than add it.
 *    If we detect the qual is always false, we replace it with
 *    constant-FALSE.
 */
static void
add_base_clause_to_rel(PlannerInfo *root, Index relid,
             RestrictInfo *restrictinfo)
{
  RelOptInfo *rel = find_base_rel(root, relid);
  RangeTblEntry *rte = root->simple_rte_array[relid];

  Assert(bms_membership(restrictinfo->required_relids) == BMS_SINGLETON);

  /*
   * For inheritance parent tables, we must always record the RestrictInfo
   * in baserestrictinfo as is.  If we were to transform or skip adding it,
   * then the original wouldn't be available in apply_child_basequals. Since
   * there are two RangeTblEntries for inheritance parents, one with
   * inh==true and the other with inh==false, we're still able to apply this
   * optimization to the inh==false one.  The inh==true one is what
   * apply_child_basequals() sees, whereas the inh==false one is what's used
   * for the scan node in the final plan.
   *
   * We make an exception to this for partitioned tables.  For these, we
   * always apply the constant-TRUE and constant-FALSE transformations.  A
   * qual which is either of these for a partitioned table must also be that
   * for all of its child partitions.
   */
  if (!rte->inh || rte->relkind == RELKIND_PARTITIONED_TABLE)
  {
    /* Don't add the clause if it is always true */
    if (restriction_is_always_true(root, restrictinfo))
      return;

    /*
     * Substitute the origin qual with constant-FALSE if it is provably
     * always false.
     *
     * Note that we need to keep the same rinfo_serial, since it is in
     * practice the same condition.  We also need to reset the
     * last_rinfo_serial counter, which is essential to ensure that the
     * RestrictInfos for the "same" qual condition get identical serial
     * numbers (see deconstruct_distribute_oj_quals).
     */
    if (restriction_is_always_false(root, restrictinfo))
    {
      int     save_rinfo_serial = restrictinfo->rinfo_serial;
      int     save_last_rinfo_serial = root->last_rinfo_serial;

      restrictinfo = make_restrictinfo(root,
                       (Expr *) makeBoolConst(false, false),
                       restrictinfo->is_pushed_down,
                       restrictinfo->has_clone,
                       restrictinfo->is_clone,
                       restrictinfo->pseudoconstant,
                       0, /* security_level */
                       restrictinfo->required_relids,
                       restrictinfo->incompatible_relids,
                       restrictinfo->outer_relids);
      restrictinfo->rinfo_serial = save_rinfo_serial;
      root->last_rinfo_serial = save_last_rinfo_serial;
    }
  }

  /* Add clause to rel's restriction list */
  rel->baserestrictinfo = lappend(rel->baserestrictinfo, restrictinfo);

  /* Update security level info */
  rel->baserestrict_min_security = Min(rel->baserestrict_min_security,
                     restrictinfo->security_level);
}

/*
 * restriction_is_always_true
 *    Check to see if the RestrictInfo is always true.
 *
 * Currently we only check for NullTest quals and OR clauses that include
 * NullTest quals.  We may extend it in the future.
 */
bool
restriction_is_always_true(PlannerInfo *root,
               RestrictInfo *restrictinfo)
{
  /*
   * For a clone clause, we don't have a reliable way to determine if the
   * input expression of a NullTest is non-nullable: nullingrel bits in
   * clone clauses may not reflect reality, so we dare not draw conclusions
   * from clones about whether Vars are guaranteed not-null.
   */
  if (restrictinfo->has_clone || restrictinfo->is_clone)
    return false;

  /* Check for NullTest qual */
  if (IsA(restrictinfo->clause, NullTest))
  {
    NullTest   *nulltest = (NullTest *) restrictinfo->clause;

    /* is this NullTest an IS_NOT_NULL qual? */
    if (nulltest->nulltesttype != IS_NOT_NULL)
      return false;

    /*
     * Empty rows can appear NULL in some contexts and NOT NULL in others,
     * so avoid this optimization for row expressions.
     */
    if (nulltest->argisrow)
      return false;

    return expr_is_nonnullable(root, nulltest->arg, NOTNULL_SOURCE_RELOPT);
  }

  /* If it's an OR, check its sub-clauses */
  if (restriction_is_or_clause(restrictinfo))
  {
    ListCell   *lc;

    Assert(is_orclause(restrictinfo->orclause));

    /*
     * if any of the given OR branches is provably always true then the
     * entire condition is true.
     */
    foreach(lc, ((BoolExpr *) restrictinfo->orclause)->args)
    {
      Node     *orarg = (Node *) lfirst(lc);

      if (!IsA(orarg, RestrictInfo))
        continue;

      if (restriction_is_always_true(root, (RestrictInfo *) orarg))
        return true;
    }
  }

  return false;
}

/*
 * restriction_is_always_false
 *    Check to see if the RestrictInfo is always false.
 *
 * Currently we only check for NullTest quals and OR clauses that include
 * NullTest quals.  We may extend it in the future.
 */
bool
restriction_is_always_false(PlannerInfo *root,
              RestrictInfo *restrictinfo)
{
  /*
   * For a clone clause, we don't have a reliable way to determine if the
   * input expression of a NullTest is non-nullable: nullingrel bits in
   * clone clauses may not reflect reality, so we dare not draw conclusions
   * from clones about whether Vars are guaranteed not-null.
   */
  if (restrictinfo->has_clone || restrictinfo->is_clone)
    return false;

  /* Check for NullTest qual */
  if (IsA(restrictinfo->clause, NullTest))
  {
    NullTest   *nulltest = (NullTest *) restrictinfo->clause;

    /* is this NullTest an IS_NULL qual? */
    if (nulltest->nulltesttype != IS_NULL)
      return false;

    /*
     * Empty rows can appear NULL in some contexts and NOT NULL in others,
     * so avoid this optimization for row expressions.
     */
    if (nulltest->argisrow)
      return false;

    return expr_is_nonnullable(root, nulltest->arg, NOTNULL_SOURCE_RELOPT);
  }

  /* If it's an OR, check its sub-clauses */
  if (restriction_is_or_clause(restrictinfo))
  {
    ListCell   *lc;

    Assert(is_orclause(restrictinfo->orclause));

    /*
     * Currently, when processing OR expressions, we only return true when
     * all of the OR branches are always false.  This could perhaps be
     * expanded to remove OR branches that are provably false.  This may
     * be a useful thing to do as it could result in the OR being left
     * with a single arg.  That's useful as it would allow the OR
     * condition to be replaced with its single argument which may allow
     * use of an index for faster filtering on the remaining condition.
     */
    foreach(lc, ((BoolExpr *) restrictinfo->orclause)->args)
    {
      Node     *orarg = (Node *) lfirst(lc);

      if (!IsA(orarg, RestrictInfo) ||
        !restriction_is_always_false(root, (RestrictInfo *) orarg))
        return false;
    }
    return true;
  }

  return false;
}

/*
 * distribute_restrictinfo_to_rels
 *    Push a completed RestrictInfo into the proper restriction or join
 *    clause list(s).
 *
 * This is the last step of distribute_qual_to_rels() for ordinary qual
 * clauses.  Clauses that are interesting for equivalence-class processing
 * are diverted to the EC machinery, but may ultimately get fed back here.
 */
void
distribute_restrictinfo_to_rels(PlannerInfo *root,
                RestrictInfo *restrictinfo)
{
  Relids    relids = restrictinfo->required_relids;

  if (!bms_is_empty(relids))
  {
    int     relid;

    if (bms_get_singleton_member(relids, &relid))
    {
      /*
       * There is only one relation participating in the clause, so it
       * is a restriction clause for that relation.
       */
      add_base_clause_to_rel(root, relid, restrictinfo);
    }
    else
    {
      /*
       * The clause is a join clause, since there is more than one rel
       * in its relid set.
       */

      /*
       * Check for hashjoinable operators.  (We don't bother setting the
       * hashjoin info except in true join clauses.)
       */
      check_hashjoinable(restrictinfo);

      /*
       * Likewise, check if the clause is suitable to be used with a
       * Memoize node to cache inner tuples during a parameterized
       * nested loop.
       */
      check_memoizable(restrictinfo);

      /*
       * Add clause to the join lists of all the relevant relations.
       */
      add_join_clause_to_rels(root, restrictinfo, relids);
    }
  }
  else
  {
    /*
     * clause references no rels, and therefore we have no place to attach
     * it.  Shouldn't get here if callers are working properly.
     */
    elog(ERROR, "cannot cope with variable-free clause");
  }
}

/*
 * process_implied_equality
 *    Create a restrictinfo item that says "item1 op item2", and push it
 *    into the appropriate lists.  (In practice opno is always a btree
 *    equality operator.)
 *
 * "qualscope" is the nominal syntactic level to impute to the restrictinfo.
 * This must contain at least all the rels used in the expressions, but it
 * is used only to set the qual application level when both exprs are
 * variable-free.  (Hence, it should usually match the join domain in which
 * the clause applies.)  Otherwise the qual is applied at the lowest join
 * level that provides all its variables.
 *
 * "security_level" is the security level to assign to the new restrictinfo.
 *
 * "both_const" indicates whether both items are known pseudo-constant;
 * in this case it is worth applying eval_const_expressions() in case we
 * can produce constant TRUE or constant FALSE.  (Otherwise it's not,
 * because the expressions went through eval_const_expressions already.)
 *
 * Returns the generated RestrictInfo, if any.  The result will be NULL
 * if both_const is true and we successfully reduced the clause to
 * constant TRUE.
 *
 * Note: this function will copy item1 and item2, but it is caller's
 * responsibility to make sure that the Relids parameters are fresh copies
 * not shared with other uses.
 *
 * Note: we do not do initialize_mergeclause_eclasses() here.  It is
 * caller's responsibility that left_ec/right_ec be set as necessary.
 */
RestrictInfo *
process_implied_equality(PlannerInfo *root,
             Oid opno,
             Oid collation,
             Expr *item1,
             Expr *item2,
             Relids qualscope,
             Index security_level,
             bool both_const)
{
  RestrictInfo *restrictinfo;
  Node     *clause;
  Relids    relids;
  bool    pseudoconstant = false;

  /*
   * Build the new clause.  Copy to ensure it shares no substructure with
   * original (this is necessary in case there are subselects in there...)
   */
  clause = (Node *) make_opclause(opno,
                  BOOLOID, /* opresulttype */
                  false,  /* opretset */
                  copyObject(item1),
                  copyObject(item2),
                  InvalidOid,
                  collation);

  /* If both constant, try to reduce to a boolean constant. */
  if (both_const)
  {
    clause = eval_const_expressions(root, clause);

    /* If we produced const TRUE, just drop the clause */
    if (clause && IsA(clause, Const))
    {
      Const    *cclause = (Const *) clause;

      Assert(cclause->consttype == BOOLOID);
      if (!cclause->constisnull && DatumGetBool(cclause->constvalue))
        return NULL;
    }
  }

  /*
   * The rest of this is a very cut-down version of distribute_qual_to_rels.
   * We can skip most of the work therein, but there are a couple of special
   * cases we still have to handle.
   *
   * Retrieve all relids mentioned within the possibly-simplified clause.
   */
  relids = pull_varnos(root, clause);
  Assert(bms_is_subset(relids, qualscope));

  /*
   * If the clause is variable-free, our normal heuristic for pushing it
   * down to just the mentioned rels doesn't work, because there are none.
   * Apply it as a gating qual at the appropriate level (see comments for
   * get_join_domain_min_rels).
   */
  if (bms_is_empty(relids))
  {
    /* eval at join domain's safe level */
    relids = get_join_domain_min_rels(root, qualscope);
    /* mark as gating qual */
    pseudoconstant = true;
    /* tell createplan.c to check for gating quals */
    root->hasPseudoConstantQuals = true;
  }

  /*
   * Build the RestrictInfo node itself.
   */
  restrictinfo = make_restrictinfo(root,
                   (Expr *) clause,
                   true, /* is_pushed_down */
                   false, /* !has_clone */
                   false, /* !is_clone */
                   pseudoconstant,
                   security_level,
                   relids,
                   NULL, /* incompatible_relids */
                   NULL); /* outer_relids */

  /*
   * If it's a join clause, add vars used in the clause to targetlists of
   * their relations, so that they will be emitted by the plan nodes that
   * scan those relations (else they won't be available at the join node!).
   *
   * Typically, we'd have already done this when the component expressions
   * were first seen by distribute_qual_to_rels; but it is possible that
   * some of the Vars could have missed having that done because they only
   * appeared in single-relation clauses originally.  So do it here for
   * safety.
   */
  if (bms_membership(relids) == BMS_MULTIPLE)
  {
    List     *vars = pull_var_clause(clause,
                       PVC_RECURSE_AGGREGATES |
                       PVC_RECURSE_WINDOWFUNCS |
                       PVC_INCLUDE_PLACEHOLDERS);

    add_vars_to_targetlist(root, vars, relids);
    list_free(vars);
  }

  /*
   * Check mergejoinability.  This will usually succeed, since the op came
   * from an EquivalenceClass; but we could have reduced the original clause
   * to a constant.
   */
  check_mergejoinable(restrictinfo);

  /*
   * Note we don't do initialize_mergeclause_eclasses(); the caller can
   * handle that much more cheaply than we can.  It's okay to call
   * distribute_restrictinfo_to_rels() before that happens.
   */

  /*
   * Push the new clause into all the appropriate restrictinfo lists.
   */
  distribute_restrictinfo_to_rels(root, restrictinfo);

  return restrictinfo;
}

/*
 * build_implied_join_equality --- build a RestrictInfo for a derived equality
 *
 * This overlaps the functionality of process_implied_equality(), but we
 * must not push the RestrictInfo into the joininfo tree.
 *
 * Note: this function will copy item1 and item2, but it is caller's
 * responsibility to make sure that the Relids parameters are fresh copies
 * not shared with other uses.
 *
 * Note: we do not do initialize_mergeclause_eclasses() here.  It is
 * caller's responsibility that left_ec/right_ec be set as necessary.
 */
RestrictInfo *
build_implied_join_equality(PlannerInfo *root,
              Oid opno,
              Oid collation,
              Expr *item1,
              Expr *item2,
              Relids qualscope,
              Index security_level)
{
  RestrictInfo *restrictinfo;
  Expr     *clause;

  /*
   * Build the new clause.  Copy to ensure it shares no substructure with
   * original (this is necessary in case there are subselects in there...)
   */
  clause = make_opclause(opno,
               BOOLOID, /* opresulttype */
               false,  /* opretset */
               copyObject(item1),
               copyObject(item2),
               InvalidOid,
               collation);

  /*
   * Build the RestrictInfo node itself.
   */
  restrictinfo = make_restrictinfo(root,
                   clause,
                   true, /* is_pushed_down */
                   false, /* !has_clone */
                   false, /* !is_clone */
                   false, /* pseudoconstant */
                   security_level,  /* security_level */
                   qualscope, /* required_relids */
                   NULL, /* incompatible_relids */
                   NULL); /* outer_relids */

  /* Set mergejoinability/hashjoinability flags */
  check_mergejoinable(restrictinfo);
  check_hashjoinable(restrictinfo);
  check_memoizable(restrictinfo);

  return restrictinfo;
}

/*
 * get_join_domain_min_rels
 *    Identify the appropriate join level for derived quals belonging
 *    to the join domain with the given relids.
 *
 * When we derive a pseudoconstant (Var-free) clause from an EquivalenceClass,
 * we'd ideally apply the clause at the top level of the EC's join domain.
 * However, if there are any outer joins inside that domain that get commuted
 * with joins outside it, that leads to not finding a correct place to apply
 * the clause.  Instead, remove any lower outer joins from the relid set,
 * and apply the clause to just the remaining rels.  This still results in a
 * correct answer, since if the clause produces FALSE then the LHS of these
 * joins will be empty leading to an empty join result.
 *
 * However, there's no need to remove outer joins if this is the top-level
 * join domain of the query, since then there's nothing else to commute with.
 *
 * Note: it's tempting to use this in distribute_qual_to_rels where it's
 * dealing with pseudoconstant quals; but we can't because the necessary
 * SpecialJoinInfos aren't all formed at that point.
 *
 * The result is always freshly palloc'd; we do not modify domain_relids.
 */
static Relids
get_join_domain_min_rels(PlannerInfo *root, Relids domain_relids)
{
  Relids    result = bms_copy(domain_relids);
  ListCell   *lc;

  /* Top-level join domain? */
  if (bms_equal(result, root->all_query_rels))
    return result;

  /* Nope, look for lower outer joins that could potentially commute out */
  foreach(lc, root->join_info_list)
  {
    SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);

    if (sjinfo->jointype == JOIN_LEFT &&
      bms_is_member(sjinfo->ojrelid, result))
    {
      result = bms_del_member(result, sjinfo->ojrelid);
      result = bms_del_members(result, sjinfo->syn_righthand);
    }
  }
  return result;
}


/*
 * match_foreign_keys_to_quals
 *    Match foreign-key constraints to equivalence classes and join quals
 *
 * The idea here is to see which query join conditions match equality
 * constraints of a foreign-key relationship.  For such join conditions,
 * we can use the FK semantics to make selectivity estimates that are more
 * reliable than estimating from statistics, especially for multiple-column
 * FKs, where the normal assumption of independent conditions tends to fail.
 *
 * In this function we annotate the ForeignKeyOptInfos in root->fkey_list
 * with info about which eclasses and join qual clauses they match, and
 * discard any ForeignKeyOptInfos that are irrelevant for the query.
 */
void
match_foreign_keys_to_quals(PlannerInfo *root)
{
  List     *newlist = NIL;
  ListCell   *lc;

  foreach(lc, root->fkey_list)
  {
    ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
    RelOptInfo *con_rel;
    RelOptInfo *ref_rel;
    int     colno;

    /*
     * Either relid might identify a rel that is in the query's rtable but
     * isn't referenced by the jointree (typically because it's been
     * removed by join removal), so that it won't have a RelOptInfo. Hence
     * don't use find_base_rel() here.  We can ignore such FKs.
     */
    if (fkinfo->con_relid >= root->simple_rel_array_size ||
      fkinfo->ref_relid >= root->simple_rel_array_size)
      continue;     /* just paranoia */
    con_rel = root->simple_rel_array[fkinfo->con_relid];
    if (con_rel == NULL)
      continue;
    ref_rel = root->simple_rel_array[fkinfo->ref_relid];
    if (ref_rel == NULL)
      continue;

    /*
     * Ignore FK unless both rels are baserels.  This gets rid of FKs that
     * link to inheritance child rels (otherrels).
     */
    if (con_rel->reloptkind != RELOPT_BASEREL ||
      ref_rel->reloptkind != RELOPT_BASEREL)
      continue;

    /*
     * Scan the columns and try to match them to eclasses and quals.
     *
     * Note: for simple inner joins, any match should be in an eclass.
     * "Loose" quals that syntactically match an FK equality must have
     * been rejected for EC status because they are outer-join quals or
     * similar.  We can still consider them to match the FK.
     */
    for (colno = 0; colno < fkinfo->nkeys; colno++)
    {
      EquivalenceClass *ec;
      AttrNumber  con_attno,
            ref_attno;
      Oid     fpeqop;
      ListCell   *lc2;

      ec = match_eclasses_to_foreign_key_col(root, fkinfo, colno);
      /* Don't bother looking for loose quals if we got an EC match */
      if (ec != NULL)
      {
        fkinfo->nmatched_ec++;
        if (ec->ec_has_const)
          fkinfo->nconst_ec++;
        continue;
      }

      /*
       * Scan joininfo list for relevant clauses.  Either rel's joininfo
       * list would do equally well; we use con_rel's.
       */
      con_attno = fkinfo->conkey[colno];
      ref_attno = fkinfo->confkey[colno];
      fpeqop = InvalidOid; /* we'll look this up only if needed */

      foreach(lc2, con_rel->joininfo)
      {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc2);
        OpExpr     *clause = (OpExpr *) rinfo->clause;
        Var      *leftvar;
        Var      *rightvar;

        /* Only binary OpExprs are useful for consideration */
        if (!IsA(clause, OpExpr) ||
          list_length(clause->args) != 2)
          continue;
        leftvar = (Var *) get_leftop((Expr *) clause);
        rightvar = (Var *) get_rightop((Expr *) clause);

        /* Operands must be Vars, possibly with RelabelType */
        while (leftvar && IsA(leftvar, RelabelType))
          leftvar = (Var *) ((RelabelType *) leftvar)->arg;
        if (!(leftvar && IsA(leftvar, Var)))
          continue;
        while (rightvar && IsA(rightvar, RelabelType))
          rightvar = (Var *) ((RelabelType *) rightvar)->arg;
        if (!(rightvar && IsA(rightvar, Var)))
          continue;

        /* Now try to match the vars to the current foreign key cols */
        if (fkinfo->ref_relid == leftvar->varno &&
          ref_attno == leftvar->varattno &&
          fkinfo->con_relid == rightvar->varno &&
          con_attno == rightvar->varattno)
        {
          /* Vars match, but is it the right operator? */
          if (clause->opno == fkinfo->conpfeqop[colno])
          {
            fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
                            rinfo);
            fkinfo->nmatched_ri++;
          }
        }
        else if (fkinfo->ref_relid == rightvar->varno &&
             ref_attno == rightvar->varattno &&
             fkinfo->con_relid == leftvar->varno &&
             con_attno == leftvar->varattno)
        {
          /*
           * Reverse match, must check commutator operator.  Look it
           * up if we didn't already.  (In the worst case we might
           * do multiple lookups here, but that would require an FK
           * equality operator without commutator, which is
           * unlikely.)
           */
          if (!OidIsValid(fpeqop))
            fpeqop = get_commutator(fkinfo->conpfeqop[colno]);
          if (clause->opno == fpeqop)
          {
            fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
                            rinfo);
            fkinfo->nmatched_ri++;
          }
        }
      }
      /* If we found any matching loose quals, count col as matched */
      if (fkinfo->rinfos[colno])
        fkinfo->nmatched_rcols++;
    }

    /*
     * Currently, we drop multicolumn FKs that aren't fully matched to the
     * query.  Later we might figure out how to derive some sort of
     * estimate from them, in which case this test should be weakened to
     * "if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) > 0)".
     */
    if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) == fkinfo->nkeys)
      newlist = lappend(newlist, fkinfo);
  }
  /* Replace fkey_list, thereby discarding any useless entries */
  root->fkey_list = newlist;
}


/*****************************************************************************
 *
 *   CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
 *
 *****************************************************************************/

/*
 * check_mergejoinable
 *    If the restrictinfo's clause is mergejoinable, set the mergejoin
 *    info fields in the restrictinfo.
 *
 *    Currently, we support mergejoin for binary opclauses where
 *    the operator is a mergejoinable operator.  The arguments can be
 *    anything --- as long as there are no volatile functions in them.
 */
static void
check_mergejoinable(RestrictInfo *restrictinfo)
{
  Expr     *clause = restrictinfo->clause;
  Oid     opno;
  Node     *leftarg;

  if (restrictinfo->pseudoconstant)
    return;
  if (!is_opclause(clause))
    return;
  if (list_length(((OpExpr *) clause)->args) != 2)
    return;

  opno = ((OpExpr *) clause)->opno;
  leftarg = linitial(((OpExpr *) clause)->args);

  if (op_mergejoinable(opno, exprType(leftarg)) &&
    !contain_volatile_functions((Node *) restrictinfo))
    restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);

  /*
   * Note: op_mergejoinable is just a hint; if we fail to find the operator
   * in any btree opfamilies, mergeopfamilies remains NIL and so the clause
   * is not treated as mergejoinable.
   */
}

/*
 * check_hashjoinable
 *    If the restrictinfo's clause is hashjoinable, set the hashjoin
 *    info fields in the restrictinfo.
 *
 *    Currently, we support hashjoin for binary opclauses where
 *    the operator is a hashjoinable operator.  The arguments can be
 *    anything --- as long as there are no volatile functions in them.
 */
static void
check_hashjoinable(RestrictInfo *restrictinfo)
{
  Expr     *clause = restrictinfo->clause;
  Oid     opno;
  Node     *leftarg;

  if (restrictinfo->pseudoconstant)
    return;
  if (!is_opclause(clause))
    return;
  if (list_length(((OpExpr *) clause)->args) != 2)
    return;

  opno = ((OpExpr *) clause)->opno;
  leftarg = linitial(((OpExpr *) clause)->args);

  if (op_hashjoinable(opno, exprType(leftarg)) &&
    !contain_volatile_functions((Node *) restrictinfo))
    restrictinfo->hashjoinoperator = opno;
}

/*
 * check_memoizable
 *    If the restrictinfo's clause is suitable to be used for a Memoize node,
 *    set the left_hasheqoperator and right_hasheqoperator to the hash equality
 *    operator that will be needed during caching.
 */
static void
check_memoizable(RestrictInfo *restrictinfo)
{
  TypeCacheEntry *typentry;
  Expr     *clause = restrictinfo->clause;
  Oid     lefttype;
  Oid     righttype;

  if (restrictinfo->pseudoconstant)
    return;
  if (!is_opclause(clause))
    return;
  if (list_length(((OpExpr *) clause)->args) != 2)
    return;

  lefttype = exprType(linitial(((OpExpr *) clause)->args));

  typentry = lookup_type_cache(lefttype, TYPECACHE_HASH_PROC |
                 TYPECACHE_EQ_OPR);

  if (OidIsValid(typentry->hash_proc) && OidIsValid(typentry->eq_opr))
    restrictinfo->left_hasheqoperator = typentry->eq_opr;

  righttype = exprType(lsecond(((OpExpr *) clause)->args));

  /*
   * Lookup the right type, unless it's the same as the left type, in which
   * case typentry is already pointing to the required TypeCacheEntry.
   */
  if (lefttype != righttype)
    typentry = lookup_type_cache(righttype, TYPECACHE_HASH_PROC |
                   TYPECACHE_EQ_OPR);

  if (OidIsValid(typentry->hash_proc) && OidIsValid(typentry->eq_opr))
    restrictinfo->right_hasheqoperator = typentry->eq_opr;
}

Coverage Report

Created: 2026-09-28 06:55