/*-------------------------------------------------------------------------

 *

 * prepjointree.c

 *    Planner preprocessing for subqueries and join tree manipulation.

 *

 * NOTE: the intended sequence for invoking these operations is

 *    preprocess_relation_rtes

 *    replace_empty_jointree

 *    pull_up_sublinks

 *    preprocess_function_rtes

 *    pull_up_subqueries

 *    flatten_simple_union_all

 *    do expression preprocessing (including flattening JOIN alias vars)

 *    reduce_outer_joins

 *    remove_useless_result_rtes

 *

 *

 * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group

 * Portions Copyright (c) 1994, Regents of the University of California

 *

 *

 * IDENTIFICATION

 *    src/backend/optimizer/prep/prepjointree.c

 *

 *-------------------------------------------------------------------------

 */

#include "postgres.h"

#include "access/table.h"

#include "catalog/pg_type.h"

#include "funcapi.h"

#include "miscadmin.h"

#include "nodes/makefuncs.h"

#include "nodes/multibitmapset.h"

#include "nodes/nodeFuncs.h"

#include "optimizer/clauses.h"

#include "optimizer/optimizer.h"

#include "optimizer/placeholder.h"

#include "optimizer/plancat.h"

#include "optimizer/prep.h"

#include "optimizer/subselect.h"

#include "optimizer/tlist.h"

#include "parser/parse_relation.h"

#include "parser/parsetree.h"

#include "rewrite/rewriteHandler.h"

#include "rewrite/rewriteManip.h"

#include "utils/rel.h"

typedef struct nullingrel_info

{

  /*

   * For each leaf RTE, nullingrels[rti] is the set of relids of outer joins

   * that potentially null that RTE.

   */

  Relids     *nullingrels;

  /* Length of range table (maximum index in nullingrels[]) */

  int     rtlength;   /* used only for assertion checks */

} nullingrel_info;

/* Options for wrapping an expression for identification purposes */

typedef enum ReplaceWrapOption

{

  REPLACE_WRAP_NONE,      /* no expressions need to be wrapped */

  REPLACE_WRAP_ALL,     /* all expressions need to be wrapped */

  REPLACE_WRAP_VARFREE,   /* variable-free expressions need to be

                 * wrapped */

} ReplaceWrapOption;

typedef struct pullup_replace_vars_context

{

  PlannerInfo *root;

  List     *targetlist;   /* tlist of subquery being pulled up */

  RangeTblEntry *target_rte;  /* RTE of subquery */

  int     result_relation;  /* the index of the result relation in the

                   * rewritten query */

  Relids    relids;     /* relids within subquery, as numbered after

                 * pullup (set only if target_rte->lateral) */

  nullingrel_info *nullinfo;  /* per-RTE nullingrel info (set only if

                 * target_rte->lateral) */

  bool     *outer_hasSubLinks;  /* -> outer query's hasSubLinks */

  int     varno;      /* varno of subquery */

  ReplaceWrapOption wrap_option;  /* do we need certain outputs to be PHVs? */

  Node    **rv_cache;   /* cache for results with PHVs */

} pullup_replace_vars_context;

typedef struct reduce_outer_joins_pass1_state

{

  Relids    relids;     /* base relids within this subtree */

  bool    contains_outer; /* does subtree contain outer join(s)? */

  Relids    nullable_rels;  /* base relids that are nullable within this

                 * subtree */

  Node     *jtnode;     /* the jointree node this state describes */

  List     *sub_states;   /* List of states for subtree components */

} reduce_outer_joins_pass1_state;

typedef struct reduce_outer_joins_pass2_state

{

  Relids    inner_reduced;  /* OJ relids reduced to plain inner joins */

  List     *partial_reduced;  /* List of partially reduced FULL joins */

  Relids    anti_reduced; /* OJ relids reduced to antijoins */

} reduce_outer_joins_pass2_state;

typedef struct reduce_outer_joins_partial_state

{

  int     full_join_rti;  /* RT index of a formerly-FULL join */

  Relids    unreduced_side; /* relids in its still-nullable side */

} reduce_outer_joins_partial_state;

static Query *expand_virtual_generated_columns(PlannerInfo *root, Query *parse,

                         RangeTblEntry *rte, int rt_index,

                         Relation relation);

static Node *pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode,

                         Relids *relids);

static Node *pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,

                       Node **jtlink1, Relids available_rels1,

                       Node **jtlink2, Relids available_rels2);

static Node *pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode,

                    JoinExpr *lowest_outer_join,

                    AppendRelInfo *containing_appendrel);

static Node *pull_up_simple_subquery(PlannerInfo *root, Node *jtnode,

                   RangeTblEntry *rte,

                   JoinExpr *lowest_outer_join,

                   AppendRelInfo *containing_appendrel);

static Node *pull_up_simple_union_all(PlannerInfo *root, Node *jtnode,

                    RangeTblEntry *rte);

static void pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root,

                     int parentRTindex, Query *setOpQuery,

                     int childRToffset);

static void make_setop_translation_list(Query *query, int newvarno,

                    AppendRelInfo *appinfo);

static bool is_simple_subquery(PlannerInfo *root, Query *subquery,

                 RangeTblEntry *rte,

                 JoinExpr *lowest_outer_join);

static Node *pull_up_simple_values(PlannerInfo *root, Node *jtnode,

                   RangeTblEntry *rte);

static bool is_simple_values(PlannerInfo *root, RangeTblEntry *rte);

static Node *pull_up_constant_function(PlannerInfo *root, Node *jtnode,

                     RangeTblEntry *rte,

                     AppendRelInfo *containing_appendrel);

static bool is_simple_union_all(Query *subquery);

static bool is_simple_union_all_recurse(Node *setOp, Query *setOpQuery,

                    List *colTypes);

static bool is_safe_append_member(Query *subquery);

static bool jointree_contains_lateral_outer_refs(PlannerInfo *root,

                         Node *jtnode, bool restricted,

                         Relids safe_upper_varnos);

static void flatten_join_alias_vars_in_jointree(PlannerInfo *root,

                        Node *jtnode);

static void perform_pullup_replace_vars(PlannerInfo *root,

                    pullup_replace_vars_context *rvcontext,

                    AppendRelInfo *containing_appendrel);

static void replace_vars_in_jointree(Node *jtnode,

                   pullup_replace_vars_context *context);

static Node *pullup_replace_vars(Node *expr,

                 pullup_replace_vars_context *context);

static Node *pullup_replace_vars_callback(const Var *var,

                      replace_rte_variables_context *context);

static Query *pullup_replace_vars_subquery(Query *query,

                       pullup_replace_vars_context *context);

static reduce_outer_joins_pass1_state *reduce_outer_joins_pass1(Node *jtnode);

static void reduce_outer_joins_pass2(Node *jtnode,

                   reduce_outer_joins_pass1_state *state1,

                   reduce_outer_joins_pass2_state *state2,

                   PlannerInfo *root,

                   Relids nonnullable_rels,

                   List *forced_null_vars);

static void report_reduced_full_join(reduce_outer_joins_pass2_state *state2,

                   int rtindex, Relids relids);

static void remove_redundant_nullability_quals(Node *jtnode,

                         Relids antijoins);

static Node *strip_redundant_nullability_quals(Node *quals, Relids antijoins);

static bool forced_null_var_is_attnotnull(PlannerInfo *root,

                      List *forced_null_vars,

                      reduce_outer_joins_pass1_state *state);

static bool forced_null_var_is_nonnullable(PlannerInfo *root,

                       List *forced_null_vars,

                       reduce_outer_joins_pass1_state *state,

                       List *extra_quals);

static Node *remove_useless_results_recurse(PlannerInfo *root, Node *jtnode,

                      Relids baserels,

                      Node **parent_quals,

                      Relids *dropped_outer_joins);

static int  get_result_relid(PlannerInfo *root, Node *jtnode);

static void remove_result_refs(PlannerInfo *root, int varno, Node *newjtloc);

static bool find_dependent_phvs(PlannerInfo *root, int varno, Relids baserels);

static bool find_dependent_phvs_in_jointree(PlannerInfo *root,

                      Node *node, int varno,

                      Relids baserels);

static void substitute_phv_relids(Node *node,

                  int varno, Relids subrelids);

static void fix_append_rel_relids(PlannerInfo *root, int varno,

                  Relids subrelids);

static Node *find_jointree_node_for_rel(Node *jtnode, int relid);

static nullingrel_info *get_nullingrels(Query *parse);

static void get_nullingrels_recurse(Node *jtnode, Relids upper_nullingrels,

                  nullingrel_info *info);

/*

 * transform_MERGE_to_join

 *    Replace a MERGE's jointree to also include the target relation.

 */

void

transform_MERGE_to_join(Query *parse)

{

  RangeTblEntry *joinrte;

  JoinExpr   *joinexpr;

  bool    have_action[NUM_MERGE_MATCH_KINDS];

  JoinType  jointype;

  int     joinrti;

  List     *vars;

  RangeTblRef *rtr;

  FromExpr   *target;

  Node     *source;

  int     sourcerti;

  if (parse->commandType != CMD_MERGE)

    return;

  /* XXX probably bogus */

  vars = NIL;

  /*

   * Work out what kind of join is required.  If there any WHEN NOT MATCHED

   * BY SOURCE/TARGET actions, an outer join is required so that we process

   * all unmatched tuples from the source and/or target relations.

   * Otherwise, we can use an inner join.

   */

  have_action[MERGE_WHEN_MATCHED] = false;

  have_action[MERGE_WHEN_NOT_MATCHED_BY_SOURCE] = false;

  have_action[MERGE_WHEN_NOT_MATCHED_BY_TARGET] = false;

  foreach_node(MergeAction, action, parse->mergeActionList)

  {

    if (action->commandType != CMD_NOTHING)

      have_action[action->matchKind] = true;

  }

  if (have_action[MERGE_WHEN_NOT_MATCHED_BY_SOURCE] &&

    have_action[MERGE_WHEN_NOT_MATCHED_BY_TARGET])

    jointype = JOIN_FULL;

  else if (have_action[MERGE_WHEN_NOT_MATCHED_BY_SOURCE])

    jointype = JOIN_LEFT;

  else if (have_action[MERGE_WHEN_NOT_MATCHED_BY_TARGET])

    jointype = JOIN_RIGHT;

  else

    jointype = JOIN_INNER;

  /* Manufacture a join RTE to use. */

  joinrte = makeNode(RangeTblEntry);

  joinrte->rtekind = RTE_JOIN;

  joinrte->jointype = jointype;

  joinrte->joinmergedcols = 0;

  joinrte->joinaliasvars = vars;

  joinrte->joinleftcols = NIL; /* MERGE does not allow JOIN USING */

  joinrte->joinrightcols = NIL; /* ditto */

  joinrte->join_using_alias = NULL;

  joinrte->alias = NULL;

  joinrte->eref = makeAlias("*MERGE*", NIL);

  joinrte->lateral = false;

  joinrte->inh = false;

  joinrte->inFromCl = true;

  /*

   * Add completed RTE to pstate's range table list, so that we know its

   * index.

   */

  parse->rtable = lappend(parse->rtable, joinrte);

  joinrti = list_length(parse->rtable);

  /*

   * Create a JOIN between the target and the source relation.

   *

   * Here the target is identified by parse->mergeTargetRelation.  For a

   * regular table, this will equal parse->resultRelation, but for a

   * trigger-updatable view, it will be the expanded view subquery that we

   * need to pull data from.

   *

   * The source relation is in parse->jointree->fromlist, but any quals in

   * parse->jointree->quals are restrictions on the target relation (if the

   * target relation is an auto-updatable view).

   */

  /* target rel, with any quals */

  rtr = makeNode(RangeTblRef);

  rtr->rtindex = parse->mergeTargetRelation;

  target = makeFromExpr(list_make1(rtr), parse->jointree->quals);

  /* source rel (expect exactly one -- see transformMergeStmt()) */

  Assert(list_length(parse->jointree->fromlist) == 1);

  source = linitial(parse->jointree->fromlist);

  /*

   * index of source rel (expect either a RangeTblRef or a JoinExpr -- see

   * transformFromClauseItem()).

   */

  if (IsA(source, RangeTblRef))

    sourcerti = ((RangeTblRef *) source)->rtindex;

  else if (IsA(source, JoinExpr))

    sourcerti = ((JoinExpr *) source)->rtindex;

  else

  {

    elog(ERROR, "unrecognized source node type: %d",

       (int) nodeTag(source));

    sourcerti = 0;      /* keep compiler quiet */

  }

  /* Join the source and target */

  joinexpr = makeNode(JoinExpr);

  joinexpr->jointype = jointype;

  joinexpr->isNatural = false;

  joinexpr->larg = (Node *) target;

  joinexpr->rarg = source;

  joinexpr->usingClause = NIL;

  joinexpr->join_using_alias = NULL;

  joinexpr->quals = parse->mergeJoinCondition;

  joinexpr->alias = NULL;

  joinexpr->rtindex = joinrti;

  /* Make the new join be the sole entry in the query's jointree */

  parse->jointree->fromlist = list_make1(joinexpr);

  parse->jointree->quals = NULL;

  /*

   * If necessary, mark parse->targetlist entries that refer to the target

   * as nullable by the join.  Normally the targetlist will be empty for a

   * MERGE, but if the target is a trigger-updatable view, it will contain a

   * whole-row Var referring to the expanded view query.

   */

  if (parse->targetList != NIL &&

    (jointype == JOIN_RIGHT || jointype == JOIN_FULL))

    parse->targetList = (List *)

      add_nulling_relids((Node *) parse->targetList,

                 bms_make_singleton(parse->mergeTargetRelation),

                 bms_make_singleton(joinrti));

  /*

   * If the source relation is on the outer side of the join, mark any

   * source relation Vars in the join condition, actions, and RETURNING list

   * as nullable by the join.  These Vars will be added to the targetlist by

   * preprocess_targetlist(), so it's important to mark them correctly here.

   *

   * It might seem that this is not necessary for Vars in the join

   * condition, since it is inside the join, but it is also needed above the

   * join (in the ModifyTable node) to distinguish between the MATCHED and

   * NOT MATCHED BY SOURCE cases -- see ExecMergeMatched().  Note that this

   * creates a modified copy of the join condition, for use above the join,

   * without modifying the original join condition, inside the join.

   */

  if (jointype == JOIN_LEFT || jointype == JOIN_FULL)

  {

    parse->mergeJoinCondition =

      add_nulling_relids(parse->mergeJoinCondition,

                 bms_make_singleton(sourcerti),

                 bms_make_singleton(joinrti));

    foreach_node(MergeAction, action, parse->mergeActionList)

    {

      action->qual =

        add_nulling_relids(action->qual,

                   bms_make_singleton(sourcerti),

                   bms_make_singleton(joinrti));

      action->targetList = (List *)

        add_nulling_relids((Node *) action->targetList,

                   bms_make_singleton(sourcerti),

                   bms_make_singleton(joinrti));

    }

    parse->returningList = (List *)

      add_nulling_relids((Node *) parse->returningList,

                 bms_make_singleton(sourcerti),

                 bms_make_singleton(joinrti));

  }

  /*

   * If there are any WHEN NOT MATCHED BY SOURCE actions, the executor will

   * use the join condition to distinguish between MATCHED and NOT MATCHED

   * BY SOURCE cases.  Otherwise, it's no longer needed, and we set it to

   * NULL, saving cycles during planning and execution.

   *

   * We need to be careful though: the executor evaluates this condition

   * using the output of the join subplan node, which nulls the output from

   * the source relation when the join condition doesn't match.  That risks

   * producing incorrect results when rechecking using a "non-strict" join

   * condition, such as "src.col IS NOT DISTINCT FROM tgt.col".  To guard

   * against that, we add an additional "src IS NOT NULL" check to the join

   * condition, so that it does the right thing when performing a recheck

   * based on the output of the join subplan.

   */

  if (have_action[MERGE_WHEN_NOT_MATCHED_BY_SOURCE])

  {

    Var      *var;

    NullTest   *ntest;

    /* source wholerow Var (nullable by the new join) */

    var = makeWholeRowVar(rt_fetch(sourcerti, parse->rtable),

                sourcerti, 0, false);

    var->varnullingrels = bms_make_singleton(joinrti);

    /* "src IS NOT NULL" check */

    ntest = makeNode(NullTest);

    ntest->arg = (Expr *) var;

    ntest->nulltesttype = IS_NOT_NULL;

    ntest->argisrow = false;

    ntest->location = -1;

    /* combine it with the original join condition */

    parse->mergeJoinCondition =

      (Node *) make_and_qual((Node *) ntest, parse->mergeJoinCondition);

  }

  else

    parse->mergeJoinCondition = NULL; /* join condition not needed */

}

/*

 * preprocess_relation_rtes

 *    Do the preprocessing work for any relation RTEs in the FROM clause.

 *

 * This scans the rangetable for relation RTEs and retrieves the necessary

 * catalog information for each relation.  Using this information, it clears

 * the inh flag for any relation that has no children, collects not-null

 * attribute numbers for any relation that has column not-null constraints, and

 * expands virtual generated columns for any relation that contains them.

 *

 * Note that expanding virtual generated columns may cause the query tree to

 * have new copies of rangetable entries.  Therefore, we have to use list_nth

 * instead of foreach when iterating over the query's rangetable.

 *

 * Returns a modified copy of the query tree, if any relations with virtual

 * generated columns are present.

 */

Query *

preprocess_relation_rtes(PlannerInfo *root)

{

  Query    *parse = root->parse;

  int     rtable_size;

  int     rt_index;

  rtable_size = list_length(parse->rtable);

  for (rt_index = 0; rt_index < rtable_size; rt_index++)

  {

    RangeTblEntry *rte = rt_fetch(rt_index + 1, parse->rtable);

    Relation  relation;

    /* We only care about relation RTEs. */

    if (rte->rtekind != RTE_RELATION)

      continue;

    /*

     * We need not lock the relation since it was already locked by the

     * rewriter.

     */

    relation = table_open(rte->relid, NoLock);

    /*

     * Check to see if the relation actually has any children; if not,

     * clear the inh flag so we can treat it as a plain base relation.

     *

     * Note: this could give a false-positive result, if the rel once had

     * children but no longer does.  We used to be able to clear rte->inh

     * later on when we discovered that, but no more; we have to handle

     * such cases as full-fledged inheritance.

     */

    if (rte->inh)

      rte->inh = relation->rd_rel->relhassubclass;

    /*

     * Check to see if the relation has any column not-null constraints;

     * if so, retrieve the constraint information and store it in a

     * relation OID based hash table.

     */

    get_relation_notnullatts(root, relation);

    /*

     * Check to see if the relation has any virtual generated columns; if

     * so, replace all Var nodes in the query that reference these columns

     * with the generation expressions.

     */

    parse = expand_virtual_generated_columns(root, parse,

                         rte, rt_index + 1,

                         relation);

    table_close(relation, NoLock);

  }

  return parse;

}

/*

 * expand_virtual_generated_columns

 *    Expand virtual generated columns for the given relation.

 *

 * This checks whether the given relation has any virtual generated columns,

 * and if so, replaces all Var nodes in the query that reference those columns

 * with their generation expressions.

 *

 * Returns a modified copy of the query tree if the relation contains virtual

 * generated columns.

 */

static Query *

expand_virtual_generated_columns(PlannerInfo *root, Query *parse,

                 RangeTblEntry *rte, int rt_index,

                 Relation relation)

{

  TupleDesc tupdesc;

  /* Only normal relations can have virtual generated columns */

  Assert(rte->rtekind == RTE_RELATION);

  tupdesc = RelationGetDescr(relation);

  if (tupdesc->constr && tupdesc->constr->has_generated_virtual)

  {

    List     *tlist = NIL;

    pullup_replace_vars_context rvcontext;

    List     *save_exclRelTlist = NIL;

    for (int i = 0; i < tupdesc->natts; i++)

    {

      Form_pg_attribute attr = TupleDescAttr(tupdesc, i);

      TargetEntry *tle;

      if (attr->attgenerated == ATTRIBUTE_GENERATED_VIRTUAL)

      {

        Node     *defexpr;

        defexpr = build_generation_expression(relation, i + 1);

        ChangeVarNodes(defexpr, 1, rt_index, 0);

        tle = makeTargetEntry((Expr *) defexpr, i + 1, 0, false);

        tlist = lappend(tlist, tle);

      }

      else

      {

        Var      *var;

        var = makeVar(rt_index,

                i + 1,

                attr->atttypid,

                attr->atttypmod,

                attr->attcollation,

                0);

        tle = makeTargetEntry((Expr *) var, i + 1, 0, false);

        tlist = lappend(tlist, tle);

      }

    }

    Assert(list_length(tlist) > 0);

    Assert(!rte->lateral);

    /*

     * The relation's targetlist items are now in the appropriate form to

     * insert into the query, except that we may need to wrap them in

     * PlaceHolderVars.  Set up required context data for

     * pullup_replace_vars.

     */

    rvcontext.root = root;

    rvcontext.targetlist = tlist;

    rvcontext.target_rte = rte;

    rvcontext.result_relation = parse->resultRelation;

    /* won't need these values */

    rvcontext.relids = NULL;

    rvcontext.nullinfo = NULL;

    /* pass NULL for outer_hasSubLinks */

    rvcontext.outer_hasSubLinks = NULL;

    rvcontext.varno = rt_index;

    /* this flag will be set below, if needed */

    rvcontext.wrap_option = REPLACE_WRAP_NONE;

    /* initialize cache array with indexes 0 .. length(tlist) */

    rvcontext.rv_cache = palloc0_array(Node *, list_length(tlist) + 1);

    /*

     * If the query uses grouping sets, we need a PlaceHolderVar for each

     * expression of the relation's targetlist items.  (See comments in

     * pull_up_simple_subquery().)

     */

    if (parse->groupingSets)

      rvcontext.wrap_option = REPLACE_WRAP_ALL;

    /*

     * Apply pullup variable replacement throughout the query tree.

     *

     * We intentionally do not touch the EXCLUDED pseudo-relation's

     * targetlist here.  Various places in the planner assume that it

     * contains only Vars, and we want that to remain the case.  More

     * importantly, we don't want setrefs.c to turn any expanded

     * EXCLUDED.virtual_column expressions in other parts of the query

     * back into Vars referencing the original virtual column, which

     * set_plan_refs() would do if exclRelTlist contained matching

     * expressions.

     */

    if (parse->onConflict)

    {

      save_exclRelTlist = parse->onConflict->exclRelTlist;

      parse->onConflict->exclRelTlist = NIL;

    }

    parse = (Query *) pullup_replace_vars((Node *) parse, &rvcontext);

    if (parse->onConflict)

      parse->onConflict->exclRelTlist = save_exclRelTlist;

  }

  return parse;

}

/*

 * replace_empty_jointree

 *    If the Query's jointree is empty, replace it with a dummy RTE_RESULT

 *    relation.

 *

 * By doing this, we can avoid a bunch of corner cases that formerly existed

 * for SELECTs with omitted FROM clauses.  An example is that a subquery

 * with empty jointree previously could not be pulled up, because that would

 * have resulted in an empty relid set, making the subquery not uniquely

 * identifiable for join or PlaceHolderVar processing.

 *

 * Unlike most other functions in this file, this function doesn't recurse;

 * we rely on other processing to invoke it on sub-queries at suitable times.

 */

void

replace_empty_jointree(Query *parse)

{

  RangeTblEntry *rte;

  Index   rti;

  RangeTblRef *rtr;

  /* Nothing to do if jointree is already nonempty */

  if (parse->jointree->fromlist != NIL)

    return;

  /* We mustn't change it in the top level of a setop tree, either */

  if (parse->setOperations)

    return;

  /* Create suitable RTE */

  rte = makeNode(RangeTblEntry);

  rte->rtekind = RTE_RESULT;

  rte->eref = makeAlias("*RESULT*", NIL);

  /* Add it to rangetable */

  parse->rtable = lappend(parse->rtable, rte);

  rti = list_length(parse->rtable);

  /* And jam a reference into the jointree */

  rtr = makeNode(RangeTblRef);

  rtr->rtindex = rti;

  parse->jointree->fromlist = list_make1(rtr);

}

/*

 * pull_up_sublinks

 *    Attempt to pull up ANY and EXISTS SubLinks to be treated as

 *    semijoins or anti-semijoins.

 *

 * A clause "foo op ANY (sub-SELECT)" can be processed by pulling the

 * sub-SELECT up to become a rangetable entry and treating the implied

 * comparisons as quals of a semijoin.  However, this optimization *only*

 * works at the top level of WHERE or a JOIN/ON clause, because we cannot

 * distinguish whether the ANY ought to return FALSE or NULL in cases

 * involving NULL inputs.  Also, in an outer join's ON clause we can only

 * do this if the sublink is degenerate (ie, references only the nullable

 * side of the join).  In that case it is legal to push the semijoin

 * down into the nullable side of the join.  If the sublink references any

 * nonnullable-side variables then it would have to be evaluated as part

 * of the outer join, which makes things way too complicated.

 *

 * Under similar conditions, EXISTS and NOT EXISTS clauses can be handled

 * by pulling up the sub-SELECT and creating a semijoin or anti-semijoin.

 *

 * This routine searches for such clauses and does the necessary parsetree

 * transformations if any are found.

 *

 * This routine has to run before preprocess_expression(), so the quals

 * clauses are not yet reduced to implicit-AND format, and are not guaranteed

 * to be AND/OR-flat either.  That means we need to recursively search through

 * explicit AND clauses.  We stop as soon as we hit a non-AND item.

 */

void

pull_up_sublinks(PlannerInfo *root)

{

  Node     *jtnode;

  Relids    relids;

  /* Begin recursion through the jointree */

  jtnode = pull_up_sublinks_jointree_recurse(root,

                         (Node *) root->parse->jointree,

                         &relids);

  /*

   * root->parse->jointree must always be a FromExpr, so insert a dummy one

   * if we got a bare RangeTblRef or JoinExpr out of the recursion.

   */

  if (IsA(jtnode, FromExpr))

    root->parse->jointree = (FromExpr *) jtnode;

  else

    root->parse->jointree = makeFromExpr(list_make1(jtnode), NULL);

}

/*

 * Recurse through jointree nodes for pull_up_sublinks()

 *

 * In addition to returning the possibly-modified jointree node, we return

 * a relids set of the contained rels into *relids.

 */

static Node *

pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode,

                  Relids *relids)

{

  /* Since this function recurses, it could be driven to stack overflow. */

  check_stack_depth();

  if (jtnode == NULL)

  {

    *relids = NULL;

  }

  else if (IsA(jtnode, RangeTblRef))

  {

    int     varno = ((RangeTblRef *) jtnode)->rtindex;

    *relids = bms_make_singleton(varno);

    /* jtnode is returned unmodified */

  }

  else if (IsA(jtnode, FromExpr))

  {

    FromExpr   *f = (FromExpr *) jtnode;

    List     *newfromlist = NIL;

    Relids    frelids = NULL;

    FromExpr   *newf;

    Node     *jtlink;

    ListCell   *l;

    /* First, recurse to process children and collect their relids */

    foreach(l, f->fromlist)

    {

      Node     *newchild;

      Relids    childrelids;

      newchild = pull_up_sublinks_jointree_recurse(root,

                             lfirst(l),

                             &childrelids);

      newfromlist = lappend(newfromlist, newchild);

      frelids = bms_join(frelids, childrelids);

    }

    /* Build the replacement FromExpr; no quals yet */

    newf = makeFromExpr(newfromlist, NULL);

    /* Set up a link representing the rebuilt jointree */

    jtlink = (Node *) newf;

    /* Now process qual --- all children are available for use */

    newf->quals = pull_up_sublinks_qual_recurse(root, f->quals,

                          &jtlink, frelids,

                          NULL, NULL);

    /*

     * Note that the result will be either newf, or a stack of JoinExprs

     * with newf at the base.  We rely on subsequent optimization steps to

     * flatten this and rearrange the joins as needed.

     *

     * Although we could include the pulled-up subqueries in the returned

     * relids, there's no need since upper quals couldn't refer to their

     * outputs anyway.

     */

    *relids = frelids;

    jtnode = jtlink;

  }

  else if (IsA(jtnode, JoinExpr))

  {

    JoinExpr   *j;

    Relids    leftrelids;

    Relids    rightrelids;

    Node     *jtlink;

    /*

     * Make a modifiable copy of join node, but don't bother copying its

     * subnodes (yet).

     */

    j = palloc_object(JoinExpr);

    memcpy(j, jtnode, sizeof(JoinExpr));

    jtlink = (Node *) j;

    /* Recurse to process children and collect their relids */

    j->larg = pull_up_sublinks_jointree_recurse(root, j->larg,

                          &leftrelids);

    j->rarg = pull_up_sublinks_jointree_recurse(root, j->rarg,

                          &rightrelids);

    /*

     * Now process qual, showing appropriate child relids as available,

     * and attach any pulled-up jointree items at the right place. In the

     * inner-join case we put new JoinExprs above the existing one (much

     * as for a FromExpr-style join).  In outer-join cases the new

     * JoinExprs must go into the nullable side of the outer join. The

     * point of the available_rels machinations is to ensure that we only

     * pull up quals for which that's okay.

     *

     * We don't expect to see any pre-existing JOIN_SEMI, JOIN_ANTI,

     * JOIN_RIGHT_SEMI, or JOIN_RIGHT_ANTI jointypes here.

     */

    switch (j->jointype)

    {

      case JOIN_INNER:

        j->quals = pull_up_sublinks_qual_recurse(root, j->quals,

                             &jtlink,

                             bms_union(leftrelids,

                                   rightrelids),

                             NULL, NULL);

        break;

      case JOIN_LEFT:

        j->quals = pull_up_sublinks_qual_recurse(root, j->quals,

                             &j->rarg,

                             rightrelids,

                             NULL, NULL);

        break;

      case JOIN_FULL:

        /* can't do anything with full-join quals */

        break;

      case JOIN_RIGHT:

        j->quals = pull_up_sublinks_qual_recurse(root, j->quals,

                             &j->larg,

                             leftrelids,

                             NULL, NULL);

        break;

      default:

        elog(ERROR, "unrecognized join type: %d",

           (int) j->jointype);

        break;

    }

    /*

     * Although we could include the pulled-up subqueries in the returned

     * relids, there's no need since upper quals couldn't refer to their

     * outputs anyway.  But we *do* need to include the join's own rtindex

     * because we haven't yet collapsed join alias variables, so upper

     * levels would mistakenly think they couldn't use references to this

     * join.

     */

    *relids = bms_join(leftrelids, rightrelids);

    if (j->rtindex)

      *relids = bms_add_member(*relids, j->rtindex);

    jtnode = jtlink;

  }

  else

    elog(ERROR, "unrecognized node type: %d",

       (int) nodeTag(jtnode));

  return jtnode;

}

/*

 * Recurse through top-level qual nodes for pull_up_sublinks()

 *

 * jtlink1 points to the link in the jointree where any new JoinExprs should

 * be inserted if they reference available_rels1 (i.e., available_rels1

 * denotes the relations present underneath jtlink1).  Optionally, jtlink2 can

 * point to a second link where new JoinExprs should be inserted if they

 * reference available_rels2 (pass NULL for both those arguments if not used).

 * Note that SubLinks referencing both sets of variables cannot be optimized.

 * If we find multiple pull-up-able SubLinks, they'll get stacked onto jtlink1

 * and/or jtlink2 in the order we encounter them.  We rely on subsequent

 * optimization to rearrange the stack if appropriate.

 *

 * Returns the replacement qual node, or NULL if the qual should be removed.

 */

static Node *

pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node,

                Node **jtlink1, Relids available_rels1,

                Node **jtlink2, Relids available_rels2)

{

  if (node == NULL)

    return NULL;

  if (IsA(node, SubLink))

  {

    SubLink    *sublink = (SubLink *) node;

    JoinExpr   *j;

    Relids    child_rels;

    /* Is it a convertible ANY or EXISTS clause? */

    if (sublink->subLinkType == ANY_SUBLINK)

    {

      ScalarArrayOpExpr *saop;

      if ((saop = convert_VALUES_to_ANY(root,

                        sublink->testexpr,

                        (Query *) sublink->subselect)) != NULL)

      {

        /*

         * The VALUES sequence was simplified.  Nothing more to do

         * here.

         */

        return (Node *) saop;

      }

      if ((j = convert_ANY_sublink_to_join(root, sublink, false,

                         available_rels1)) != NULL)

      {

        /* Yes; insert the new join node into the join tree */

        j->larg = *jtlink1;

        *jtlink1 = (Node *) j;

        /* Recursively process pulled-up jointree nodes */

        j->rarg = pull_up_sublinks_jointree_recurse(root,

                              j->rarg,

                              &child_rels);

        /*

         * Now recursively process the pulled-up quals.  Any inserted

         * joins can get stacked onto either j->larg or j->rarg,

         * depending on which rels they reference.

         */

        j->quals = pull_up_sublinks_qual_recurse(root,

                             j->quals,

                             &j->larg,

                             available_rels1,

                             &j->rarg,

                             child_rels);

        /* Return NULL representing constant TRUE */

        return NULL;

      }

      if (available_rels2 != NULL &&

        (j = convert_ANY_sublink_to_join(root, sublink, false,

                         available_rels2)) != NULL)

      {

        /* Yes; insert the new join node into the join tree */

        j->larg = *jtlink2;

        *jtlink2 = (Node *) j;

        /* Recursively process pulled-up jointree nodes */

        j->rarg = pull_up_sublinks_jointree_recurse(root,

                              j->rarg,

                              &child_rels);

        /*

         * Now recursively process the pulled-up quals.  Any inserted

         * joins can get stacked onto either j->larg or j->rarg,

         * depending on which rels they reference.

         */

        j->quals = pull_up_sublinks_qual_recurse(root,

                             j->quals,

                             &j->larg,

                             available_rels2,

                             &j->rarg,

                             child_rels);

        /* Return NULL representing constant TRUE */

        return NULL;

      }

    }

    else if (sublink->subLinkType == EXISTS_SUBLINK)

    {

      if ((j = convert_EXISTS_sublink_to_join(root, sublink, false,

                          available_rels1)) != NULL)

      {

        /* Yes; insert the new join node into the join tree */

        j->larg = *jtlink1;

        *jtlink1 = (Node *) j;

        /* Recursively process pulled-up jointree nodes */

        j->rarg = pull_up_sublinks_jointree_recurse(root,

                              j->rarg,

                              &child_rels);

        /*

         * Now recursively process the pulled-up quals.  Any inserted

         * joins can get stacked onto either j->larg or j->rarg,

         * depending on which rels they reference.

         */

        j->quals = pull_up_sublinks_qual_recurse(root,

                             j->quals,

                             &j->larg,

                             available_rels1,

                             &j->rarg,

                             child_rels);

        /* Return NULL representing constant TRUE */

        return NULL;

      }

      if (available_rels2 != NULL &&

        (j = convert_EXISTS_sublink_to_join(root, sublink, false,